Reading a Bus-Connected Processor Array.

An area of active research in computer science is concerned with the design and programming of parallel computing devices. In one design, an M by N array of processing elements communicates with a host computer using a series of busses. Each row and column of the array has a bus. Although a processing element can write a value to either its row bus or its column bus (see FIGURE 1), only one value can be output to each bus at a time. It is therefore possible to transfer to the host one entry from each row and one entry from each column in a single operation cycle. Now imagine that an M by N matrix resides in the processor array with one entry stored in each processing element. This might be the situation, for example, if the processor array has just finished computing a matrix product. How many operation cycles are required to transmit the entire M by N matrix to the host? Since there are MN memory entries and M+N can be read at once, it appears that approximately MN/(M + N) cycles should suffice to transmit the matrix. However, in order to be sure that all M + N busses are used at each step, some care is required. For example, transmitting all the entries from the first row and column at the first step would only yield MVf + N 1 matrix entries. Sending the remaining entries of the second row and column at the next step would only produce M + N 3 entries. Continuing in this *fashion would require as many steps to finish as the smaller of M and N. This is no better than using only the larger set of busses (the column busses if N > M). A little exploration with special cases should convince you that it is possible to schedule the reading operations so that N + M entries are obtained at each step, although it may not be clear how to establish a generally applicable procedure. Our goal is to present a simple scheduling algorithm that uses all the busses at each step (except possibly the last) for any rectangular array. First, impose an order on the processing elements as follows. The (1, 1) element is first. The successor of element (i, j) is (i + 1, j + 1) where the addition in the first component is performed modulo M, and the addition in the second component is performed modulo N. This shall be referred to as the diagonal order. TABLE 1 lists the ordered elements for a 3 by 8 array. The ordering can also be understood geometrically as a path that traverses all the entries of the array. That is, begin in the (1, 1) position and travel down the diagonal, wrapping from the bottom edge of the matrix to the top, and from the right side to the left as if the matrix were a torus. FIGURE 2 shows this geometric interpretation for the ordering listed in TABLE 1. Note that it is possible for the ordering procedure to repeat the (1, 1) position without traversing all the array entries. In this case only a subset of the entries are ordered. Otherwise, we may say that the array is exhausted by the diagonal order. Note further that among the ordered elements, any M consecutive entries come from different rows, while any N consecutive entries come from different columns. When it exhausts an array, the diagonal order can be used to schedule reading operations, as formalized in the following lemma.