# An Efficient Library for Reliability Block Diagram Evaluation
## 3 RBD Computation Library-librbd
### Design
#### 3.1.1 Optimizations for Koo\(N\) Computation  
Several optimizations have been designed and implemented for RBD Koo\(N\) blocks. Two trivial optimizations, applicable to both RBD Koo\(N\) blocks with generic and identical components, have been implemented. A Koo\(N\) system with \(K=N\) is solved as an RBD series block, while a Koo\(N\) system with \(K=1\) is solved as an RBD parallel block. A major optimization, applicable to both RBD Koo\(N\) blocks with generic and identical components, minimizes the number of computational steps. This optimization exploits the formula of the trivial configuration 0 oo\(N\), which is shown in Equation (13):  
\[R_{0 ooN}=\sum_{l=0}^{N}\sum_{j=1}^{\binom{N}{j}}P_{path(N,i,j)}=1 \tag{13}\]  
Starting from Equation (13), we divide the outer sum into two separate sums, the first one ranging from 0 to \(K-1\), the second one ranging from \(K\) to \(N\), and we substitute the contribution shown in Equation (6). Finally, we resolve for \(R_{KooN}\) as:  
\[ \begin{split}\sum_{i=0}^{K-1}\sum_{j=1}^{\binom{N}{j}}P_{path(N, i,j)}+\sum_{i=K}^{N}\sum_{j=1}^{\binom{N}{j}}P_{path(N,i,j)}=1\\ F_{KooN}+R_{KooN}=1\\ R_{KooN}=1-F_{KooN}\end{split}  \tag{14}\]  
where \(F_{KooN}\) is the unreliability of a Koo\(N\) block, i.e., the probability of having at least \(N-K+1\) components _failed_ in a block of \(N\) components. We finally observe that, when \(N-K>K-1\), we can compute \(R_{KooN}\) exploiting Equation (14) decreasing the mathematical complexity. For RBD Koo\(N\) blocks with identical components, we compute and store all coefficients \(\binom{N}{i}\), \(\forall i\in[K,N]\) that will be used during the computation of the reliability for each time instant. For RBD Koo\(N\) blocks with generic components, we try to compute all combinations of \(i\) out of \(N\) components with \(i\in[K,N]\) that are needed to compute the reliability for each time instant. The number of these combinations is equal to \(\sum_{i=K}^{N}\binom{N}{i}\). The last optimization, which is applicable to RBD Koo\(N\) blocks with generic components, is the adoption of a heuristic to decrease the computation time by using either Equation (7) or Equation (14). The number of recursion steps performed while applying Equation (7) is limited to \(N^{2}\)[41]. On the other hand, the number of iterative steps performed while applying Equation (14) is limited to \(\sum_{i=K}^{N}{N\choose i}\), with \(K\geq N/2\). The chosen heuristic used to compute reliability of a Koo\(N\) block with generic components is the following one:  
* Use Equation (7) when all the following conditions are true:
* The OS is able to allocate the memory to store all combinations of \(i\) out of \(N\) components with \(i\in[K,N]\) that are needed to compute the reliability for each time instant;
* Use Equation (14) otherwise. Algorithm 1, together with auxiliary functions shown in Algorithm 2, is used to compute the reliability of an RBD Koo\(N\) block with generic components, while Algorithm 3 is used to compute the reliability of an RBD Koo\(N\) block with identical components. ```
Input: Reliability \(R_{i}\) of each component Result: Reliability \(R\) of Koo\(N\) block begin \(N\_square=N\cdot N\); \(sum\_nCi=0\); if\((N-K)\leq(K-1)\)then for\(i\in[K,N]\)do \(sum\_nCi=sum\_nCi+{N\choose i}\); if\(sum\_nCi<=N\_square\)then \(R=0\); for\(i\in[K,N]\)do for\(j\in{N\choose i}\)do \(R=R+ReliabilityStep(N,i,j)\); else \(R=ReliabilityRecursive(N,K)\); else for\(i\in[0,K-1]\)do \(sum\_nCi=sum\_nCi+{N\choose i}\); if\(sum\_nCi<=N\_square\)then \(R=1\); for\(i\in[0,(K-1)]\)do for\(j\in{N\choose i}\)do \(R=R-ReliabilityStep(N,i,j)\); else \(R=R-ReliabilityRecursive(N,K)\); else \(R=R-ReliabilityStep(N,i,j)\); else \(R=R-ReliabilityRecursive(N,K)\);
```  
**Algorithm 1**Computation of RBD Koo\(N\) block with generic components.