Basic Operations on the OTIS-Mesh Optoelectronic Computer.
AbstractIn this paper, we develop algorithms for some basic operationsbroadcast, window broadcast, prefix sum, data sum, rank, shift, data accumulation, consecutive sum, adjacent sum, concentrate, distribute, generalize, sorting, random access read and writeon the OTIS-Mesh [1] model. These operations are useful in the development of efficient algorithms for numerous applications [2].
Introduction
The Optical Transpose Interconnection System ( OTIS ), proposed by Marsden et al. [4], is a hybrid
optical and electronic interconnection system for large parallel computers. The OTIS architecture
space optics to connect distant processors and electronic interconnect to connect
nearby processors. Specifically, to maximize bandwidth, power efficiency, and to minimize system
area and volume [1], the processors of an N 2 processor OTIS computer are partitioned into N
groups of N processors each. Each processor is indexed by a tuple (G; G;
G is the group index ( i.e., the group the processor is in ), and P the processor index within a
group. The inter group interconnects are optical while the intra group interconnects are electronic.
The optical or OTIS interconnects connect pairs of processors of the form [(G; P ); (P; G)]; that is,
the group and processor indices are transposed by an optical interconnect. The electrical or intra
group interconnections are according to any of the well studied electronic interconnection networks
- mesh, hypercube, mesh of trees, and so forth. The choice if the electronic interconnection network
defines a sub-family of OTIS computers - OTIS-Mesh, OTIS-Hypercube, and so forth. Figure 1
shows a 16 processor OTIS-Mesh. Each small square represents a processor. The number inside a
processor square is the processor index P . Some processor squares have a pair (P
The pair gives the row and column index of the processor P within its
N \Theta
N mesh. Each large
This work was supported, in part, by the Army Research Office under grant DAA H04-95-1-0111.
group 3

Figure

1:
square encloses a group of processors. A group index G may also be given as a pair (G x ; G y ) where
G x and G y are the row and column indices of the group assuming a
N \Theta
N layout of groups.
Zane et al. [11] have shown that an N 2 processor OTIS-Mesh can simulate each move of a
N \Theta
N \Theta
N \Theta
four-dimensional ( 4D ) mesh computer using either one electronic move or
one electronic and two OTIS moves ( depending on which dimension of the 4D mesh we are to move
along ). They have also shown that an N 2 processor OTIS-Hypercube can simulate each move of
an N 2 processor hypercube using either one electronic move or one electronic and two OTIS moves.
Sahni and Wang [10, 9] have developed efficient algorithms to rearrange data according to bit-
permute-complement permutations on OTIS-Mesh and OTIS-Hypercube computers,
respectively. Rajasekaran and Sahni [7] have developed efficient randomized algorithms for routing,
selection, and sorting on an OTIS-Mesh.
In this paper, we develop deterministic OTIS-Mesh algorithms for the basic data operations for
parallel computation that are studied in [8]. As shown in [8], algorithms for these operations can
be used to arrive at efficient parallel algorithms for numerous applications, from image processing,
computational geometry, matrix algebra, graph theory, and so forth.
We consider both the synchronous SIMD and synchronous MIMD models. In both, all processors
operate in lock-step fashion. In the SIMD model, all active processors perform the same
operation in any step and all active processors move data along the same dimension or along OTIS
connections. In the MIMD model, processors can perform different operations in the same step
and can move data along different dimensions.
2 Basic Operations
2.1 Data Broadcast
Data broadcast is, perhaps, the most fundamental operation for a parallel computer. In this
operation, data that is initially in a single processor (G; P ) is to be broadcast or transmitted to all
processors of the OTIS-Mesh. Data broadcast can be accomplished using the following three
step algorithm:
its data to all other processors in group G.
Step 2: Perform an OTIS move.
Step 3: Processor G of each group broadcasts the data within its group.
Following Step 2, one processor of each group has a copy of the data, and following Step 3
each processor of the OTIS-Mesh has a copy. In the SIMD model, Steps 1 and 3 take 2(
electronic moves each, and Step 2 takes one OTIS move. The SIMD complexity is 4(
electronic moves and 1 OTIS move, or a total of 4
moves. Note that our algorithm is
optimal because the diameter of the OTIS-Mesh is 4
example, if the data to be
broadcast is initially in processor (0,0), the data needs to reach processor which is
at a distance of 4
3. In the MIMD model, the complexity of Steps 1 and 3 depends on the
value of ranges from a low of approximately
to a high of 2(
The overall complexity is at most 4(
moves and one OTIS move. By contrast,
simulating the 4D-mesh broadcast algorithm using the simulation method of [11] takes 4(
electronic moves and 4(
moves in the SIMD model and up to this many moves in
the MIMD model.
2.2 Window Broadcast
In a window broadcast, we start with data in the top left w \Theta w submesh of a single group G.
Here w divides
N . Following the window broadcast operation, the initial w \Theta w window tiles all
groups; that is, the window is broadcast both within and across groups. Our algorithm for window
broadcast is:
Step 1: Do a window broadcast within group G.
Step 2: Perform an OTIS move.
Step 3: Do an intra group data broadcast from processor G of each group.
Step 4: Perform an OTIS move.
Following Step 1 the initial window properly tiles group G and we are left with the task of
broadcasting from group G to all other groups. In Step 2, data d(G; P ) from (G; P ) is moved to
In Step 3, d(G; P ) is broadcast to all processors
moved to (i; P
Step 1 of our window broadcast algorithm takes 2(
moves in both the SIMD
and MIMD models, and Step 3 takes 2(
moves in the SIMD model and up to
moves in the MIMD model. The total cost is 4
moves in the SIMD model and up to this many moves in the MIMD model. A simulation
of the 4D mesh window broadcast algorithm takes the same number of electronic moves, but also
takes 4(
moves.
2.3 Prefix Sum
The index (G; P ) of a processor may be transformed into a scalar I = GN+P with 0 - I ! N 2 . Let
D(I) be the data in processor I, 0 - I ! N 2 . In a prefix sum, each processor I computes
I
. A simple prefix sum algorithm results from the following observation:
where SD(I) is the sum of D(i) over all processors i that are in a group smaller than the group of
I and LP (I) is the local prefix sum within the group of I. The simple prefix sum algorithm is:
Step 1: Perform a local prefix sum in each group.
Step 2: Perform an OTIS move of the prefix sums computed in Step 1 for all processors (G; N \Gamma 1).
Step 3: Group modified prefix sum of the values, A, received in Step 2. In this
modification, processor P computes
rather than
Step 4: Perform an OTIS move of the modified prefix sums computed in Step 3.
Step 5: Each group does a local broadcast of the modified prefix sum received by its
processor.
Step Each processor adds the local prefix sum computed in Step 1 and the modified prefix sum
it received in Step 5.
The local prefix sums of Steps 1 and 3 take 3(
moves in both the SIMD
and MIMD models, and the local data broadcast of Step 5 takes 2(
moves.
The overall complexity is 8(
moves and 2 OTIS moves. This can be reduced to
moves and 2 OTIS moves by deferring some of the Step 1 moves to Step 5 as
below.
Step 1: In each group, compute the row prefix sums R.
Step 2: Column
of each group computes the modified prefix sums of its R values.
Step 3: Perform an OTIS move on the prefix sums computed in Step 2 for all processors (G; N \Gamma 1).
Step 4: Group modified prefix sum of the values, A, received in Step 3.
Step 5: Perform an OTIS move of the modified prefix sums computed in Step 4.
Step Each group broadcasts the modified prefix sum received in Step 5 along column
of its mesh.
Step 7: The column
processors add the modified prefix sum received in Step 6 and the
prefix sum of R values computed in Step 2 minus its own R value computed in Step 1.
Step 8: The result computed by column
processors in Step 7 is broadcast along mesh
rows.
Step 9: Each processor adds its R value and the value it received in Step 8.
If we simulate the best 4D mesh prefix sum algorithm, the resulting OTIS mesh algorithm takes
moves.
2.4 Data Sum
In this operation, each processor is to compute the sum of the D values of all processors. An
optimal SIMD data sum algorithm is:
Step 1: Each group performs the data sum.
Step 2: Perform an OTIS move.
Step 3: Each group performs the data sum.
In the SIMD model Steps 1 and 3 take 4(
moves, and step 2 takes 1 OTIS
move. The total cost is 8(
moves. Note that since the distance
between processors (0;
moves and since
each needs to get information from the other, at least 8(
are needed ( the moves needed to send information from (0; 0) to (N \Gamma and those from
cannot be overlapped in the SIMD model ). Also, note that a simulation
of the 4D mesh data sum algorithm takes 8(
moves.
The MIMD complexity can be reduced by computing the group sums in the middle processor
of each group rather than in the bottom right processor. The complexity now becomes 4(
electronic and 1 OTIS moves when
N is odd and 4
N electronic and 1 OTIS moves when
is even. The simulation of the 4D mesh, however, takes 4(
moves. Notice that the MIMD algorithm is near optimal as the diameter of the OTIS-Mesh isp
2.5 Rank
In the rank operation, each processor I has a flag S(I) 2 f0; 1g, 0 - I ! N 2 . We are to compute
the prefix sums of the processors with This operation can be performed in 7(
electronic and 2 OTIS moves using the prefix sum algorithm of Section 2.3.
2.6 Shift
Although there are many variations of the shift operation, the ones we believe are most useful in
application development are:
(a) mesh row shift with zero fill - in this we shift data from processor (G x
N . The shift is done with zero fill and end discard ( i.e.,
if
or P y the data from P y is discarded ).
(b) mesh column shift with zero fill - similar to (a), but along mesh column P x .
(c) circular shift on a mesh row - in this we shift data from processor (G x
(d) circular shift on a mesh column - similar to (c), but instead P x is used.
row shift with zero fill - similar to (a), except that G y is used in place of P y .
(f) group column shift with zero fill - similar to (e), but along group column G x .
circular shift on a group row - similar to (c), but with G y rather than P y .
circular shift on a group column - similar to (g), with G x in place of G y .
Shifts of types (a) through (d) are done using the best mesh algorithms while those of types (e)
through (h) are done as below:
1: Perform an OTIS move.
Step 2: Do the shift as a P x ( if originally a G x shift ) or a P y ( if originally a G y shift ) shift.
Step 3: Perform an OTIS move.
Shifts of types (a) and (b) take s electronic moves on the SIMD and MIMD models; (c) and
(d) take
electronic moves on the SIMD model and maxfjsj;
moves on the
MIMD model; (e) and (f) take s electronic and 2 OTIS moves on both SIMD and MIMD models;
and (g) and (h) take
N electronic and 2 OTIS moves on the SIMD model and maxfjsj;
electronic and 2 OTIS moves on the MIMD model.
If we simulate the corresponding 4D mesh algorithms, we obtain the same complexity for (a)
- (d), but (e) and (f) take an additional 2s \Gamma 2 OTIS moves, and (g) and (h) take an additional
2 \Theta maxfjsj;
moves.
2.7 Data Accumulation
Each processor is to accumulate M ,
, values from its neighboring processors along
one of the four dimensions G x , G y , be the data in processor
In a data accumulation along the G x dimension ( for example ), each processor
accumulates in an array A the data values from ((G x
Specifically, we have
Accumulation in other dimensions is similar.
The accumulation operation can be done using a circular shift of \GammaM in the appropriate dimen-
sion. The complexity is readily obtained from that for the circular shift operation ( see Section 2.6
2.8 Consecutive Sum
The N 2 processor OTIS-Mesh is tiled with one-dimensional blocks of size M . These blocks may
align with any of the four dimensions G x , G y , P x , and P y . Each processor has M values X[j],
. The ith processor in a block is to compute the sum of the X[i]s in that block.
Specifically, processor i of a block computes
where i and j are indices relative to a block.
When the one-dimensional blocks of size M align with the P x or P y dimensions, a consecutive
sum can be performed by using M tokens in each block to accumulate the M sums S(i),
Assume the blocks align along P x . Each processor in a block initiates a token labeled with the
processor's intra block index. The tokens from processors 0 through are right bound and
that from M \Gamma 1 is left bound. In odd time steps, right bound tokens move one processor right
along the block, and in even time steps left bound tokens move one processor left along the block.
When a token reaches the rightmost or leftmost processor in the block, it reverses direction. Each
token visits each processor in its block twice - once while moving left and once while moving right.
During the rightward visits it adds in the appropriate X value from the processor. After
time steps ( and hence moves ), all tokens return to their originating processors,
and we are done.
In the MIMD model, the left and right moves can be done simultaneously, and only
electronic moves are needed.
When the one-dimensional size M blocks align with G x or G y , we first do an OTIS move; then
run either a P x or P y consecutive sum algorithm; and then do an OTIS move. The number of
electronic moves is the same as for P x or P y alignment. However, two additional OTIS moves are
needed.
Simulation of the corresponding 4D mesh algorithm takes an additional
for the case of G x or G y alignment in the SIMD model and an additional moves in
the MIMD model.
2.9 Adjacent Sum
This operation is similar to the data accumulation operation of Section 2.7 except that the M
accumulated values are to be summed. The operation can be done with the same complexity as
data accumulation using a similar algorithm.
2.10 Concentrate
A subset of the processors contain data. These processors have been ranked as in Section 2.5. So
the data is really a pair (D; r); D is the data in the processor and r is its rank. Each pair (D; r) is
to be moved to processor r, 0 - r ! b, where b is the number of processors with data. Using the
(G; P ) format for a processor index, we see that (D; r) is to be routed from its originating processor
to processor (br=Nc; r mod N ). We accomplish this using the steps:
Step 1: Each pair (D; r) is routed to processor r mod N within its current group.
Step 2: Perform an OTIS move.
Step 3: Each pair (D; r) is routed to processor br=Nc within its current group.
Step 4: Perform an OTIS move.
Theorem 1 The four step algorithm given above correctly routes every pair (D; r) to processor
Proof Step 1 does the routing on the second coordinate. This step does not route two pairs to
the same processor provided no group has two pairs (D
Since each group has at most N pairs and the ranks of these pairs are contiguous integers, no group
can have two pairs with r 1 mod each processor has at most
one pair and each pair is in the correct processor of the group, though possibly in the wrong group.
To get the pairs to their correct groups without changing the within group index, Step 2 performs
an OTIS move, which moves data from processor (G; P ) to processor (P; G). Now all pairs in a
group have the same r mod N value and different br=Nc values. The routing on the br=Nc values,
as in Step 3, routes at most one pair to each processor. The OTIS move of Step 4, therefore, gets
every pair to its correct destination processor. 2
In group 0, Step 1 is a concentrate localized to the group, and in the remaining groups, Step
1 is a generalized concentrate in which the ranks have been increased by the same amount. In all
groups we may use the mesh concentrate algorithm of [6] to accomplish the routing in 4(
moves. Step 3 is also a concentrate as the br=Nc values of the pairs are in ascending order
from 0;
moves each in the SIMD model and
in the MIMD model [6]. Therefore, the overall complexity of concentrate is 8(
electronic and 2 OTIS moves in the SIMD model and 4(
moves in
the MIMD model.
We can improve the SIMD time to 7(
moves by using a better
mesh concentrate algorithm than the one in [6]. The new and simpler algorithm is given below for
the case of a generalized concentration on a
N \Theta
mesh.
Step 1: Move data that is to be in a column right of the current one rightwards to the proper
processor in the same row.
Step 2: Move data that is to be in a column left of the current one leftwards to the proper processor
in the same row.
Step 3: Move data that is to be in a smaller row upwards to the proper processor in the same
column.
Step 4: Move data that is to be in a bigger row downwards to the proper processor in the same
column.
In a concentrate operation on a square mesh data that begins in two processors of the same row
ends up in different columns as the rank of these two data differs by at most
and 2 do not leave two or more data in the same processor. Steps 3 and 4 get data to the proper
row and hence to the proper processor. Note that it is possible to have up to two data items in
a processor following Step 1 and Step 3. The complexity of the above concentrate algorithm is
on a SIMD mesh and 2(
on an MIMD mesh ( we can overlap Steps 1 and 2 as
well as Steps 3 and 4 on an MIMD mesh ).
For an ordinary concentrate in which the ranks begin at 1, Step 4 can be omitted as no data
moves down a column to a row with bigger index. So an ordinary concentrate takes only 3(
moves. This improves the SIMD concentration algorithm of [6], which takes 4(
moves to
do an ordinary concentrate.
Actually, we can show that the four step concentration algorithm just stated is optimal for the
SIMD model. Consider the ordinary concentrate instance in which the selected elements are in
processors (0;
0). The ranks are 0, 1, \Delta \Delta \Delta,
1. So the data
in processor (0;
is to be moved to processor (0,0). This requires moves that yield a net of
moves. Also, the data in processor (
is to be moved to processor (0;
This requires a net of
moves and
moves. None of these moves
can be overlapped in the SIMD model. So every SIMD concentrate algorithm must take at least
moves in each of the directions left, right, and up; a total of at least 3(
moves.
For the generalized concentrate algorithm, the ranks need not start at zero. Suppose we have
two elements to concentrate. One is at processor (0,0) and has rank N \Gamma 1, and the other is at
processor (
has rank N . The data in (0,0) is to be moved to (
at a cost of
right and down moves. The data in (
is to be moved to
(0,0) at a cost of
net left and up moves. So at least 4(
are needed.
Theorem 2 The OTIS-Mesh data concentration algorithm described above is optimal for both the
SIMD and MIMD models; that is, (a) every SIMD concentration algorithm must make 7(
electronic and 2 OTIS moves in the worst case, and (b) every MIMD concentration algorithm must
make 4(
moves.
Proof (a) Suppose that the data to be concentrated are in the processors shown in Table 1. Let
a denote processor (
and let c denote processor (0,1,0,0). The ranks of a, b, and c are N 3=2 , N 3=2
respectively. Therefore, following the concentration the data D(a), D(b), and D(c) initially
in processors a, b, and c will be in processors (0,1,0,0), (0;
respectively. Figure 2 shows the initial and concentrated data layout for the case when
The change in G x , G y , P x , and P y values between the final and initial locations of D(a), D(b), and
D(c) is shown in Table 2.
a
c
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
(b)
a
c
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
(a)

Figure

2: Data Configuration: (a) Initial; (b) Concentrated

Table

1: Processors with data to concentrate
data G x G y
D(a) \Gamma(

Table

2: Net change in G x , G y , P x , and P y
The maximum net negative change in each of G x , G y , P x , and P y is \Gamma(
1). Since a net
negative change in G x can only be overlapped with a net negative change in P x and since D(b)
needs \Gamma(
negative change in both G x and P x , we must make at least 2(
moves that decrease the row index within a mesh. Similarly, because of D(a)'s requirements, at
least 2(
moves that increase the column index within a
N \Theta
mesh must be
made. Turning our attention to net positive changes, we see that because of D(b)'s requirements
there must be at least 2(
moves that increase the column index. D(c) requires
moves that increase the row index. Since positive net moves cannot be overlapped
with negative net moves, and since net moves along G x and P x cannot be overlapped with net moves
along G y and P y , the concentration of the configuration of Table 1 must take at least 7(
moves.
In addition to 7(
moves, we need at least 2 OTIS moves to concentrate the
data of Table 1. To see this consider the data initially in group (0,1). This data is in group (0,0)
following the concentration. At least one OTIS move is needed to move the data out of group
(0,1). A nontrivial OTIS-Mesh has - 2 processors on a row of a
N \Theta
N submesh. For such
an OTIS-Mesh, at least two pieces of data must move from group (0,1) to group (0,0). A single
OTIS move scatters data from group (0,1) to different groups with each data going to a different
group. At least one additional OTIS move must be made to get the data back into the same group.
Therefore the concentration of the configuration of Table 1 cannot be done with fewer than 2 OTIS
moves.
(b) Consider the initial configuration of Table 1. Since the shortest path between processor
b and its destination processor is 4(
and one OTIS move, at least that many
electronic moves are made, in the worst case, by every concentration algorithm. The reason that
at least 2 OTIS moves are needed to complete the concentration is the same as for (a). 2
2.11 Distribute
This is the inverse of the concentrate operation of Section 2.10. We start with pairs (D
in the first q +1 processors 0; and are to route pair (D i ; d i ) to processor
q. The algorithm of Section 2.10 tells us how to start with pairs (D i ; i) in processor
move them so that D i is in i. By running this backwards, we can start with
D i in i and route it to d i . The complexity of the distribute operation is the same as that of the
concentrate operation. We have shown that the concentrate algorithm of Section 2.10 is optimal;
it follows that the distribute algorithm is also optimal.
2.12 Generalize
We start with the same initial configuration as for the distribute operation. The objective is to
have D i in all processors j such that d i we simulate the 4D
mesh algorithm for generalize using the simulation strategy of [11], it takes 8(
and 8(
moves to perform the generalize operation on an SIMD OTIS-Mesh. We can
improve this to 8(
moves if we run the generalize algorithm of [6]
adapted to use OTIS moves as necessary. The outer loop of the algorithm of [6] examines processor
index bits from 2p \Gamma 1 to 0 where . So in the first p iterations we are moving along bits
of the G index and in the last p iterations along bits of the P index. On an OTIS-Mesh we would
break this into two parts as below:
1: Perform an OTIS move.
Step 2: Run the GENERALIZE procedure of [6] from bit while maintaining the original
index.
Step 3: Perform an OTIS move.
Step 4: Run the GENERALIZE algorithm of [6] from bit
On an MIMD OTIS-Mesh the above algorithm takes 4(
moves.
We can reduce the SIMD complexity to 7(
moves by using a
better algorithm to do the generalize operation on a 2D SIMD mesh. This algorithm uses the
same observation as used by us in Section 2.10 to speed the 2D SIMD mesh concentrate algorithm;
that is, of the four possible move directions, only three are possible. When doing a generalize on
a 2D
N \Theta
N mesh the possible move directions for data are to increasing row indexes and to
decreasing and increasing column indexes. With this observation, the algorithm to generalize on a
2D mesh becomes:
Step 1: Move data along columns to increasing row indexes if the data is needed in a row with
higher index.
Step 2: Move data along rows to increasing column indexes if the data is needed in a processor in
that row with higher column index.
Step 3: Move data along rows to decreasing column indexes if the data is needed in a processor
in that row with smaller column index.
The correctness of the preceding generalize algorithm can be established using the argument of
Theorem 1, and its optimality follows from Theorem 2 and the fact that the distribute operation,
which is the inverse of the concentrate operation, is a special case of the generalize operation.
The new and more efficient generalize algorithm may be used in Step 2 of the OTIS-Mesh
generalize algorithm. It cannot be used in Step 4 because the generalize of this step requires the
full capability of the code of [6] which permits data movement in all four directions of a mesh.
When we use the new generalize algorithm for Step 2 of the OTIS-Mesh generalize algorithm,
we can perform a generalize on a SIMD OTIS-Mesh using 7(
moves.
The new algorithm is optimal for both SIMD and MIMD models. This follows from the lower
bound on a concentrate operation established in Theorem 2 and the observation made above that
the distribute operation, which is a special case of the generalize operation, is the inverse of the
concentrate operation and so has the same lower bound.
2.13 Sorting
As was the case for the operations considered so far, an O(
time algorithm to sort can be
obtained by simulating a similar complexity 4D mesh algorithm. For sorting a 4D Mesh, the
Figure

3: Row-Column Transformation of Leighton's Column Sort
algorithm of Kunde [2] is the fastest. Its simulation will sort into snake-like row-major order usingp
N) electronic and 12
OTIS moves on the SIMD model and 7
electronic and 6
OTIS moves on the MIMD model. To sort into row-major order,
additional moves to reverse alternate dimensions are needed. This means that an OTIS-Mesh
simulation of Kunde's 4D mesh algorithm to sort into row-major order will take
electronic and 16
OTIS moves on the SIMD model. We show that Leighton's column
sort [3] can be implemented on an OTIS-Mesh to sort into row-major order using 22
electronic and O(N 3=8 ) OTIS moves on the SIMD model and 11
N) electronic and O(N 3=8 )
OTIS moves on the MIMD model.
Our OTIS-Mesh sorting algorithm is based on Leighton's column sort [3]. This sorting algorithm
sorts an r \Theta s array, with r - using the following seven steps:
Step 1: Sort each column.
Step 2: Perform a row-column transformation.
Step 3: Sort each column.
Step 4: Perform the inverse transformation of Step 2.
Step 5: Sort each column in alternating order.
Step Apply two steps of comparison-exchange to adjacent rows.
Step 7: Sort each column.

Figure

3 shows an example of the transformation of Step 2, and its inverse. Figure 4 shows a
step by step example of Leighton's column sort.
\Gamma! 11
\Gamma!

Figure

4: Example of Leighton's Column Sort
Although Leighton's column sort is explicitly stated for r \Theta s arrays with r -
can be used to sort arrays with s - into row-major order by interchanging the roles of
rows and columns. We shall do this and use Leighton's method to sort an N 1=2 \Theta N 3=2 array. We
interpret our N 2 OTIS-Mesh as an N 1=2 \Theta N 3=2 array with G x giving the row index and G y
giving the column index of an element processor. We shall further subdivide G x ( G y , P x , P y
, and G x 4
from left to right. We use G x 2\Gamma4
, for example, to
. Since bits and G x i
has p=8 bits. These notations
are helpful in describing the transformations in Steps 2 and 4 of the column sort, as we use the
BPC permutations of [5] to realize these transformations. A BPC permutation [5] is specified by a
vector
(a) A i 2 f\Sigma0;
(b) [jA is a permutation of [0;
The destination for the data in any processor may be computed in the following manner. Let
be the binary representation of the processor's index. Let d be that
of the destination processor's index. Then,
In this definition, \Gamma0 is to be regarded as ! 0, while +0 is - 0. Table 3 shows an example
of the BPC permutation defined by the permutation vector \Gamma3] on a 16 processor
OTIS-Mesh.
Source Destination
Processor (G; P ) Binary Binary (G; P ) Processor
9 (2,1) 1001 0000 (0,0) 0

Table

3: Source and destination of the BPC permutation [\Gamma0; 1; 2; \Gamma3] in a 16 processor OTIS-
Mesh
In describing our sorting algorithm, we shall, at times, use a 4D array interpretation of an
OTIS-Mesh. In this interpretation, processor of the OTIS-Mesh corresponds to
processor of the 4D mesh. We use g x to denote the bit positions of G x , that is
the leftmost p=2 bits in a processor index, g x1 to represent the leftmost p=8 bit positions, p y to
represent the rightmost p=2 bit positions, p y 3\Gamma4
to represent the rightmost p=4 bit positions, and
so on. Our strategy for the sorting steps 1, 3, 5, and 7 of Leighton's method is to collect each row
( recall that since we are sorting an N 1=2 \Theta N 3=2 array, the column-sort steps of Leighton's method
become row-sort steps ) of our N 1=2 \Theta N 3=2 array into an N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 4D submesh
of the OTIS-Mesh, and then sort this row by simulating the 4D mesh sort algorithm of [2]. This
strategy translates into the following sorting algorithm:
rows of the N 1=2 \Theta N 3=2 array into N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 4D submeshes
Perform the BPC permutation P
2: [ Sort each row of the N 1=2 \Theta N 3=2 array
Sort each 4D submesh of size N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 .
3: [ Do the inverse of Step 1, perform a column-row transformation, and move rows into
3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 submeshes
Perform the BPC permutation P
each row of the N 1=2 \Theta N 3=2 array
Sort each 4D submesh of size N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 .
5: [ Do the inverse of Step 1, perform a row-column transformation, and move rows into
3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 submeshes
Perform the BPC permutation P 0
x 1\Gamma3
each row in alternating order ]
Sort each 4D submesh of size N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 .
7: [ Move rows back from 4D submeshes
Perform the BPC permutation P 0
Step 8: Apply two steps of comparison-exchange to adjacent rows.
into submeshes of size N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 ]
Perform the BPC permutation P
each row of the N 1=2 \Theta N 3=2 array
Sort each 4D submesh of size N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 .
rows back from 4D submeshes
Perform the BPC permutation P 0
y 2\Gamma4
Notice that the row to 4D submesh transform is accomplished by the BPC permutation P
y 2\Gamma4
Elements in the same row of our N 1=2 \Theta N 3=2 array interpretation
have the same G x value; but in our 4D mesh interpretation, elements in the same
3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8 submesh have the same G x 1
value. P a results in this prop-
erty. To go from Step 2 to Step 3 of Leighton's method, we need to first restore the N 1=2 \Theta N 3=2
array interpretation using the inverse permutation of P a , that is, perform the BPC permutation
y 2\Gamma4
]; then perform a column-row transform using BPC permutation
finally map the rows of our N 1=2 \Theta N 3=2 array into 4D submeshes of
size N 3=8 \ThetaN 3=8 \ThetaN 3=8 \ThetaN 3=8 using the BPC permutation P a . The three BPC permutation sequence
a a is equivalent to the single BPC permutation P
The preceding OTIS-Mesh implementation of column sort performs 6 BPC permutations, 4
4D mesh sorts, and two steps of comparison-exchange on adjacent rows. Since the sorting steps
take O(N 3=8 ) time each ( use Kunde's 4D mesh sort [2] followed by a transform from snake-like
row-major to row-major ), and since the remaining steps take O(N 1=2 ) time, we shall ignore the
complexity of the sort steps.
We can reduce the number of BPC permutations from 6 to 3 as follows. First note that the P a
of Step 1 just moves elements from rows of the N 1=2 \Theta N 3=2 array into N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8
4D submeshes. For the sort of Step 2, it doesn't really matter which N 3=2 elements go to each 4D
submesh as the initial configuration is an arbitrary unsorted configuration. So we may eliminate
note that the BPC permutations of Steps 7 and 9 cancel each other and we
can perform the comparison-exchange of Step 8 by moving data from one N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8
4D submesh to an adjacent one and back in O(N 3=8 ) time.
With these observations, the algorithm to sort on an OTIS-Mesh becomes:
1: Sort in each subarray of size N 3=8 \Theta N 3=8 \Theta N 3=8 \Theta N 3=8
Step 2: Perform the BPC permutation P c .
Step 3: Sort in each subarray.
Step 4: Perform the BPC permutation P 0
c .
Step 5: Sort in each subarray.
Step Apply two steps of comparison-exchange to adjacent subarrays.
Step 7: Sort in each subarray.
Step 8: Perform the BPC permutation P 0
a .
Using the BPC routing algorithm of [10], the three BPC permutations can be done usingp
N electronic and 3 log moves on the SIMD model and
N electronic and
moves on the MIMD model. A more careful analysis based on the development
in [5] and [10] reveals that the permutations P 0
a , P c , and P 0
c can be done with 28
N electronic and
log moves on the SIMD model and 14
N electronic and 3 log
on the MIMD model. By using p 0
y 2\Gamma4
], the permutation
cost becomes 22
N electronic and log 2 N+5 OTIS moves on the SIMD model and 11
and log 2 N+5 OTIS moves on the MIMD model. The total number of moves is thus 22
electronic and O(N 3=8 ) OTIS moves on the SIMD model and 11
O(N 3=8 ) OTIS moves on the MIMD model. This is superior to the cost of the sorting algorithm
that results from simulating the 4D row-major mesh sort of Kunde [2].
2.14 Random Access Read ( RAR )
In a random access read (RAR) [8] processor I wishes to read data variable D of processor d I ,
. The steps suggested in [8] for this operation are:
Step 0: Processor I creates a triple (I; D; d I ) where D is initially empty.
1: Sort the triples by d I .
Step 2: Processor I checks processor I +1 and deactivates if both have triples with the same third
coordinate.
Step 3: Rank the remaining processors.
Step 4: Concentrate the triples using the ranks of Step 3.
Step 5: Distribute the triples according to their third coordinates.
Step Load each triple with the D value of the processor it is in.
Step 7: Concentrate the triples using the ranks in Step 3.
Step 8: Generalize the triples to get the configuration we had following Step 1.
Step 9: Sort the triples by their first coordinates.
Using the SIMD model the RAR algorithm of [8] take 79(
moves and O(N 3=8 )
OTIS moves. On the MIMD model, it takes 45(
moves.
2.15 Random Access Write ( RAW )
Now processor I wants to write its D data to processor d I , 0 - I ! N 2 . The steps in the RAW
algorithm of [8] are:
Step 0: Processor I creates the tuple (D(I); d I
1: Sort the tuples by their second coordinates.
Step 2: Processor I deactivates if the second coordinate of its tuple is the same as the second
coordinate of the tuple in I
Step 3: Rank the remaining processors.
Step 4: Concentrate the tuples using the ranks of Step 3.
Step 5: Distribute the tuples according to their second coordinates.
implements the arbitrary write method for a concurrent write. In this, any one of the
processors wishing to write to the same location is permitted to succeed. The priority model may
be implemented by sorting in Step 1 by d I and within d I by priority. The common and combined
models can also be implemented, but with increased complexity.
On the SIMD model, an RAW takes 43(
moves while on
the MIMD model, it takes 26(
moves.
3 Conclusion
We have developed OTIS-Mesh algorithms for the basic parallel computing algorithms of [8]. Our
algorithms run faster than the simulation of the fastest algorithms known for 4D meshes. Table 4
summarizes the complexities of our algorithms and those of the corresponding ones obtained by
simulating the best 4D-mesh algorithms. Note that the worst case complexities are listed for the
broadcast and window broadcast operation, and that of the case when
N is even is presented for
the data sum operation on the MIMD model. Also, the complexities listed for circular shift, data
accumulation, and adjacent sum assume that the shift distance is -
N=2 on the MIMD model.

Table

4 gives only the dominating
N terms for sorting. Our algorithms for data broadcast, data
sum, concentrate, distribute, and generalize are optimal.



--R


Routing and sorting on mesh-connected arrays
Tight bounds on the complexity of parallel sorting.
Optical transpose interconnection system architectures.
An optimal routing algorithm for mesh-connected parallel computers
Data broadcasting in SIMD computers.
Randomized routing
Hypercube Algorithms with Applications to Image processing and Pattern Recognition.
BPC permutations on the OTIS-Hypercube optoelectronic computer
BPC permutations on the OTIS-Mesh optoelectronic computer
Scalable network architectures using the optical transpose interconnection system (OTIS).
--TR

--CTR
A. Al-Ayyoub , A. Awwad , K. Day , M. Ould-Khaoua, Generalized methods for algorithm development on optical systems, The Journal of Supercomputing, v.38 n.2, p.111-125, November  2006
Behrooz Parhami, The Hamiltonicity of swapped (OTIS) networks built of Hamiltonian component networks, Information Processing Letters, v.95 n.4, p.441-445, 31 August 2005
Ahmad M. Awwad, OTIS-star an attractive alternative network, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-6, February 13-15, 2005, Salzburg, Austria
Khaled Day , Abdel-Elah Al-Ayyoub, Topological Properties of OTIS-Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.4, p.359-366, April 2002
Xiaofan Yang , Graham M. Megson , David J. Evans, An oblivious shortest-path routing algorithm for fully connected cubic networks, Journal of Parallel and Distributed Computing, v.66 n.10, p.1294-1303, October 2006
Behrooz Parhami, Swapped interconnection networks: topological, performance, and robustness attributes, Journal of Parallel and Distributed Computing, v.65 n.11, p.1443-1452, November 2005
Ahmad M. Awwad, OTIS-star an attractive alternative network, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-6, February 13-15, 2005, Salzburg, Austria
Khaled Day, Optical transpose k-ary n-cube networks, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.11, p.697-705, November 2004
Prasanta K. Jana, Polynomial interpolation and polynomial root finding on OTIS-mesh, Parallel Computing, v.32 n.4, p.301-312, April 2006
Chih-fang Wang , Sartaj Sahni, Matrix Multiplication on the OTIS-Mesh Optoelectronic Computer, IEEE Transactions on Computers, v.50 n.7, p.635-646, July 2001
Chih-Fang Wang , Sartaj Sahni, Image Processing on the OTIS-Mesh Optoelectronic Computer, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.97-109, February 2000
optoelectronic;random access write;distribute;adjacent sum;random access read;prefix sum;OTIS-Mesh;concentrate;data accumulation;window broadcast;consecutive sum;sorting;broadcast;data sum;generalize;shift