Introduction
In this response to Perlis, there should be
B! versions of monotonic sort for a relative array V of length 2^B,
each using a different permutation of the sequence of dividing bits.
In addition, since postadjust with Left-Right division and combination
is identical operationally to preadjust with Even-Odd, for each
permutation P its reverse-ordered permutation P' used to sequence the
levels of a preadjustment will do the same operations as P does in a
postadjustment.
We may consider the unpermuted permutation as P = [0 .. B-1] with 0
understood as the least significant bit in a sequential address within
V. Then in left-right division, the sequence of dividing bits picks
the last first, and generally steps backward from the end for each
successive division. On the other hand in left-right combination the
sequence is the same but the step direction opposite, the dividing bit
counts forward from 0 to B-1 since the promise of a combination is not
finally computed until after all levels of division are complete, that is,
at d=0.
Definition
In divacon notation, Mou's Monotonic sort algorithm is:
$$
\begin{align}
sort = & PDC(d_{lr},c_{lr},id, & nest : (min!,max!) : \#!mirr, & atom? id) \\
nest = & PDC(d_{lr},c_{lr}, (!min,!max) : \#!corr, & id, & atom? id) \\
\end{align}
$$
A Divacon, a.k.a. PDC, or parallel divide-and-conquer function, is
specified using six elements most of which are from a small vocabulary
of operations. At each of B levels a vector of input data of length
2^{B} is subdivided in half using, in this case, left-right division,
and later after division can proceed no further, and after the base
predicate is done, and postadjustment is also complete at each level,
results are combined together using left right combination.
This can be visualized as a computation graph comprising two binary
trees with leaf nodes attached; computation proceeds from a root node
examining the entire input data vector, down a level at a time
dividing the input data vector in half and perhaps carrying out a
preadjustment on that vector, finally reaching the leaf nodes which
pass the base predicate since they are finally atomic vectors. At that
leaf level the data in each computation node is converted into the
output data type using the base function, in this case \(f_b = id\),
meaning no change. Continuing onto the combining tree, the
computation applies a postadjustment, then a combine operation.
Adjusting and combining B times, we come to a final result which is
the output of the PDC.
In Mou's Monotonic Sort, the top level PDC or parallel-recursion uses
mirror communication while the nested PDC uses correspondent
communication.
Communication
Communication retrieves a copy of an element to its communicating
partner.
In a now-divided, or may I say, sub, array, each element has a partner
in the other related array. The partner in the case of correspondent
communication has the identical index but in the related array. When
communication is bidirectional (the ! in #!mirr or #!corr indicates
bidirectionality) then obviously both have the same index. On the
other hand in the case of mirror communication, the communicating
elements have indices each being the binary complement of the other.
As an example 000 mirror-communicates with 111, because the complement
of each 0 is a 1.
Conceptually speaking, with respect to the parent array, a dividing
bit is removed from its indexes while sending its values to the
address of the remainder of their indexes, to the left or to the right
sub-arrays according as the dividing bit value is zero or one. Left
right division removes the most-significant bit, while even-odd
division removes the least significant bit. In actual implementation,
nothing necessarily moves anywhere, but the variable keeping track of
the dividing bit is adjusted.
#!corr communicates with the element of the same address in the related array. i=i
#!mirr communicates with the element of the opposite address in the related array. i=!i
My point in hypersort is that the dividing bits need not be taken out
and put back in a particular counting order, but could be according to
any permutation of the bits.
Let permuteAddress(a,P,B) return a', a copy of a with same number of
bits B, but with the bits of A permuted according to P. That is,
considering each of a and a' as an array of bits indexed 0 to B-1 from
least to most significant and P as an array of B bit indexes (0 to B-1
but in any order), then a'[P[i]] = a[i] for i in 0..B-1.
Let permuteVector(V,P) return V', a copy of V with the same number of
elements V'.L = V.L, and the same set of elements as V but for each
address a in V the value of V at address a, V[a], is at address
a' = permuteAddress(a,P,V.B) in V'.
foreach (a in 0..V.L-1)
V'[permuteAddress(a,P,B)] = V[a];
It may be noticed that V' has the same information as V, but in a
address-bit-permuted order. There are B! such equivalent permutations
and therefore B! equivalent versions of V. I think of these not as
rotations of V since rotation implies conversion of 1's to 0's and
vice versa. Rather these are hypercube revectorings.
From each corner, say 0,
there are B dimensions each to another corner having an address identical
to 0 except with the opposite bit (here 1) in that ...
TO BE CONTINUED.
|
