... | ... | @@ -10,7 +10,9 @@ 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 [Usage](Usage), 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.
|
|
|
Furthermore these expression over exaggerate the possible space as two steps in which the same pair order is tested, but the ordering of the pairs is different, are considered to be different communication patterns, when in reality this is not the case. As a result $`P`$ should be divided by $`n!`$. We have also likely forgotten to include other effects, as such consider these numbers to be an upper bound.
|
|
|
|
|
|
This potential space is for large $`n`$ neigh impossible to iterate through. As a result the 1-factor algorithm is the default generation method for creating communication patterns. Using randomization, see [Usage](Usage), we can cover a part of this space. More precisely, when using step randomization only the order in which steps are executed is permuted, this results in $`(n-1)!`$ different combinations. When randomizing processes IDs the process ID of each process, think MPI rank, is permuted. This can cover $`n!`$ different combinations. Furthermore, common pseudo-random number generators have periods of this magnitude and are thus unsuitable for statistical analysis of the possible permutation space we make available to the user. This means that the pseudo-random number generators cannot cover the entire $`n!`$ possible permutation space for large $`n`$, e.g. 100.
|
|
|
|
|
|
## 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.
|
... | ... | @@ -82,3 +84,5 @@ In the limit as $`n`$ tends to infinity $`P`$ tends towards: |
|
|
```math
|
|
|
\lim\limits_{n\to\infty}P=(n!)^n
|
|
|
```
|
|
|
|
|
|
Note that in this derivation two partitions are considered to be different even when the groups in the partition are the same. In this case the two partitions only differ by a permutation. |
|
|
\ No newline at end of file |