|
|
LinkTest can test different process-process combinations in parallel. What connections are tested in parallel to other connections and when is defined by the communication pattern. Given an even number of processes, say 16, LinkTest, in its default configuration, can test 16 of the potential 240 connections by testing between 8 exclusive pairs forwards and backwards. To test the remaining 224 possible connections requires repeating this 14 additional times. Each time LinkTest can test connections in parallel is called a step, so to test the connections between 16 processes takes about 15 steps.
|
|
|
|
|
|
A communication pattern defines which connections are tested together in parallel. Continue with our example of
|
|
|
A communication pattern defines which connections are tested together in parallel. Continue with our example of 16 processes, the communication patterns defines which 8 connection pairs are tested in parallel. A common way to generate this pairing is the [1-Factor algorithm](https://en.wikipedia.org/wiki/All-to-all_(parallel_pattern)#1-factor_algorithm), however, given an even number $`n`$ processes there are $`P(n)`$ possible permutations, where $`P(n)`$ is:
|
|
|
```math
|
|
|
P=\prod\limits_{j=0}^{n-2}\prod\limits_{i=0}^{n/2-1}\bigg[\begin{pmatrix}n-2i\\2\end{pmatrix}-j\frac{n-2i}{2}\bigg].
|
|
|
```
|
|
|
For large $`n`$ this behaves like:
|
|
|
```math
|
|
|
P\approx(n!)^n.
|
|
|
```
|
|
|
Note that this is an upper bound on the possible number of permutations. For the derivation of these expressions see [here](#derivation:-number-of-permutation).
|
|
|
|
|
|
This potential space is for large $`n`$ neigh impossible to iterate through. As a result we use the 1-factor algorithm as the default. Using randomization, see [TODO:usage](#XXX), we can cover a part of this space, however, common pseudo-random number generators have periods on this magnitude and are thus unsuitable for statistical analysis of the possible permutation space.
|
|
|
|
|
|
```math
|
|
|
\\Delta = \\nabla^2 = \\frac{\\partial^2 f}{\\partial x^2} + \\frac{\\partial^2 f}{\\partial y^2}
|
|
|
## Bisection Testing
|
|
|
Aside from the 1-factor algorithm LinkTest also offers other options to define the communication pattern. One of these is to do a bisection test.
|
|
|
|
|
|
In a bisection test the even number of $`n`$ processes available to LinkTest is split into two bisecting halves. Connection testing is only done between the two halves in $`n/2`$ two steps. In each step $`n/2`$ connections are tested in parallel. Note that the possible permutation space exhibits a similar behavior as to the full test, i.e. for large $`n`$ it becomes neigh impossible to iterate through all possible combinations.
|
|
|
|
|
|
## Grouping According to Hostname
|
|
|
LinkTest can also group processes according to their hostname. In this case testing exclusively occurs between all processes of a group and another group during a step, i.e. no two processes from the same group will communicate to different groups. The group-to-group communication pattern is determined in this case using the 1-Factor algorithm. When testing between two groups all possible connection pairs between the two groups are iterated through. Note that the possible permutation space exhibits a similar behavior as to the full test, i.e. for large $`n`$ it becomes neigh impossible to iterate through all possible combinations.
|
|
|
|
|
|
## Grouping According to Hostname with bBisection
|
|
|
Differs from the previous in that the even number of groups is split into bisecting halves and only the connections between the two halves are tested. Note that the possible permutation space exhibits a similar behavior as to the full test, i.e. for large $`n`$ it becomes neigh impossible to iterate through all possible combinations.
|
|
|
|
|
|
## Comparison
|
|
|
|
|
|
|
|
|
## Derivation: Number of Permutations
|
|
|
|
|
|
Given an even number of $`n`$ processes we wish to partition them into $`n/2`$ groups of size $`2`$, each group denotes a connection between a pair of processes here. From [partitioning](https://en.wikipedia.org/wiki/Partition\_(number_theory)) $`n`$ elements into $`k`$ groups we can write the number of possible partitions for the first group $`P_{0,0}`$ as:
|
|
|
```math
|
|
|
P_{0,0}=\begin{pmatrix}n\\2\end{pmatrix},
|
|
|
```
|
|
|
where the bracketed term denotes an entry in [Pascal's triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle). For the second group the number of possible partitions is smaller as two of the $`n`$ elements is already in the first group. For the second group the number of partitions $`P_1`$ is hence:
|
|
|
```math
|
|
|
P_{0,1}=\begin{pmatrix}n-2\\2\end{pmatrix}.
|
|
|
```
|
|
|
More generally the number of possible partitions for any group $`i`$ is:
|
|
|
```math
|
|
|
P_{0,i}=\begin{pmatrix}n-2i\\2\end{pmatrix}.
|
|
|
```
|
|
|
The total number of possible ways to partition the $`n`$ processes into $`n/2`$ groups $`P`$ is then:
|
|
|
```math
|
|
|
P_{0}=\prod\limits_{i=0}^{n/2-1}P_{0,i}=\prod\limits_{i=0}^{n/2-1}\begin{pmatrix}n-2i\\2\end{pmatrix}=\frac{n!}{(2!)^{n/2}}.
|
|
|
```
|
|
|
|
|
|
We now wish to find an additional $`n-2`$ partitions without any repeats in them. For the second partition the first group now has $`P_{1,0}`$ possibilities:
|
|
|
```math
|
|
|
P_{1,0}=\begin{pmatrix}n\\2\end{pmatrix}-\frac{n}{2}.
|
|
|
```
|
|
|
The additional term here removes the groups from the first partition. For the second group "P_{1,1}" is:
|
|
|
```math
|
|
|
P_{1,1}=\begin{pmatrix}n-2\\2\end{pmatrix}-\frac{n-2}{2}.
|
|
|
```
|
|
|
The additional term here because the potential groups from the first partition to remove are now two smaller because those possibilities have already been removed with the subtraction of two in the coordinate for Pascal's triangle. More generally the possible partitions for the i<sup>th</sup> group in the second partitioning are:
|
|
|
```math
|
|
|
P_{1,i}=\begin{pmatrix}n-2i\\2\end{pmatrix}-\frac{n-2i}{2}.
|
|
|
```
|
|
|
From this we can find that the number of possible partitions for the second partitioning is:
|
|
|
```math
|
|
|
P_{1}=\prod\limits_{i=0}^{n/2-1}P_{1,i}=\prod\limits_{i=0}^{n/2-1}\bigg[\begin{pmatrix}n-2i\\2\end{pmatrix}-\frac{n-2i}{2}\bigg].
|
|
|
```
|
|
|
|
|
|
More generally for the j<sup>th</sup> partitioning into groups we find:
|
|
|
```math
|
|
|
P_{j,i}=\begin{pmatrix}n-2i\\2\end{pmatrix}-j\frac{n-2i}{2}.
|
|
|
```
|
|
|
The number of possible partitions for the j<sup>th</sup> partitioning is then:
|
|
|
```math
|
|
|
P_{j}=\prod\limits_{i=0}^{n/2-1}P_{j,i}=\prod\limits_{i=0}^{n/2-1}\bigg[\begin{pmatrix}n-2i\\2\end{pmatrix}-j\frac{n-2i}{2}\bigg].
|
|
|
```
|
|
|
|
|
|
From this we can find the total number of $`n-1`$ partitions without repetition $`P`$ as:
|
|
|
```math
|
|
|
P=\prod\limits_{j=0}^{n-2}\prod\limits_{i=0}^{n/2-1}\bigg[\begin{pmatrix}n-2i\\2\end{pmatrix}-j\frac{n-2i}{2}\bigg].
|
|
|
```
|
|
|
|
|
|
In the limit as $`n`$ tends to infinity $`P`$ tends towards:
|
|
|
```math
|
|
|
\lim\limits_{n\to\infty}P=(n!)^n
|
|
|
```
|
|
|
|
|
|
```math
|
|
|
\Delta = \nabla^2 = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2}
|
|
|
``` |
|
|
\ No newline at end of file |