Systolic array

Both word-level and bit-level parallelism should be exploited to reach the extreme throughputs which are needed in particular applications like radar processing [33]. Extensions in this direction are introduced in chapter 5. Employing the features of various arithmetic systems, such as 2 s complement and residue number systems (RNS) [42], bit-level systolic arrays can now be derived automatically. 

J. Annevelink and P. Dewilde. HiFi A functional design system for VLSI processing arrays. Proc. IEEE International Conf. on Systolic Arrays, San Diego, pages 413-452, May 1988. 

J. Bu and E. Deprettere. Processor clustering for the design of optimal fixed-size systolic arrays. Algorithms and Parallel VLSI Architectures, Vol. A, pages 341-362. North Holland, Elsevier, Amsterdam, 1991. 

J.-M. Delosme and L Ipsen. Efficient systolic arrays for the solution of Toeplitz systems. In W. Moore, A. McCabe, and R. Urquhart, editors. Systolic arrays, pages 37-46. Adam Hilger, Bristol, 1987. 

D. Moldovan. Advis a software package for the design of systolic arrays. Proc, IEEE Int Conf on Computer Design, Port Chester NY, pages 158-164, Oct 1984. 

V. Paliouras, D. Soudris, and T. Stouraitis. Systematic derivation of the processing element of a systolic array based on residue mnnber system. Proc. IEEE Int. Symp. on Circuits and Systems, San Diego, 1992. 

P. Quinton. Automatic synthesis of systolic arrays from recurrent uniform equations. 11th Int. Symp. Computer Architecture, Ann Arbor, pages 208-214, Jun 1984. 

Definition 3.2 A systolic array is space-time-minimal when it is scheduled in minimal time and when it uses the minimal number of processors among all possible minimal-time solutions. 

Theoretical considerations show that any systolic array that solves the APP using the previous formulation requires an execution time T > 5n — 2 time-steps. 

Table 2 Comparison of some systolic arrays solving the APR...

The second approach, independently studied by several researchers [5, 12, 11], is totally different. A virtual array is obtained by the usual method, and it is then partitioned into p blocks of virtual processors, each block being allocated to one physical processor. Of course, the different points allocated to the same processor have to be computed at different times in the array in such a way that they can be sequentially executed by the physical processor. This method permits synthesizing systolic arrays with a fixed number of cells and, as a particular case, permits improving the efficiency of the cells in a systolic array obtained by the usual projection method. It is described in chapter 4. This method is largely oriented towards applications where the period or throughput is important. 

A. Benaini and Y. Robert. Space-time-minimal systolic arrays for gaussian elimination and the algebraic path problem. Parallel Computing, 15, pages 211-225, 1990. 

A. Benaini, Y. Robert, B. Tourancheau. A new systolic architecture for the algebraic path problem. In J. McCanny et al., editors, Systolic array processors, pages 73-82. Prentice Hall, 1989. 

J. Bu, P. Dewilde, and E. F. Deprettere. A design methodology for fixed-size systolic arrays. In S. Y. Kung et al., editors. Application specific array processors, pages 591-602. IEEE Computer Society Press, 1991. 

P. Cappello and Y. Yaacoby. Bounded broadcast in systolic arrays. Technical Report TRCS88-13, Department of Computer Science, University of California, Santa Barbara, 1988. 

A. Darte. Regular partitioning for synthesizing fixed-size systolic arrays. Integration, the VLSI Journal, 12, number 3, pages 293-304,1991. 

V. Van Dongen and P. Quinton. Uniformization of linear recurrence equations a step towards the automatic synthesis of systolic arrays. In K. Bromley et al, editors. International Conference on Systolic Arrays, pages 473-482. IEEE Computer Society Press, 1988. 

H. T. Kung and M. S. Lam. Fault-tolerance and two-level pipelining in vlsi systolic arrays. Journal of Parallel and Distributed Computing 1, pages 32-63, 1984. 

H. T. Kung and C. E. Leiserson. Systolic arrays for VLSI. In C. A. Mead and L. A. Conway, Introduction to VLSI systems, chapter 8.3. Addison-Wesley, 1980. 

S. Y. Kung and P. S. Lewis. An optimal systolic array for the algebraic path problem. IEEE Trans, on Computers, C-40, pages 100-105,1991. 

D. I. Moldovan. Mapping an arbitrarily large QR algorithm into fixed size systolic arrays. IEEE Trans, on Computers, C-35, number 1, pages 1-12, 1986. 

T. Risset. Linear systolic arrays for matrix multiplication comparisons of existing methods and new results. In Proc. 2nd Workshop on Algorithms and VLSI parallel architecture, pages 163-174, 1991. 

G. Rote. A systolic array algorithm for the algebraic path problem (shortest paths matrix inversion). Computing, 34, pages 191-219, 1985. 

In case of a systolic array, the schedule vector A specifies that the AST node at index point 7 is to be executed at time step A 7. The vector A also specifies that the data which are transmitted over an edge defined by a dependence vector di is delayed A di time steps, so that the data will arrive in time at the node of the DG by which they are to be processed. In case of a wavefront processor array, the schedule vector A only specifies the ordering of the computations and the data storage capacity of the edges. Furthermore, the node at index point 7 will be mapped onto the processor at index point P j during the array synthesis step. Note that the S-T transformation only defines the S-T allocation... 

J. Bu, E. Deprettere, and L. Thiele. Systolic array implementation of nested loop programs. Proc. Int. Conf Application Specific Array Pro-cessing, Vol. 4, pages 31-42, Sep 1990. 

A. K. Jainandunsing. Parallel algorithms for solving systems of linear equations and their mapping on systolic arrays. PhD thesis. Delft University of Technology, January 1989. 

P. Quinton. Systolic Arrays. Esprit Project BRA 3280, Deliverable report INRIA/Ylml2/2.2/l, IRISA, Rennes, Prance, April 1990. 

S. Rajopadhye. Synthesizing systolic arrays with control signals from recurrence equations. Distributed Computing, 3, pages 88-105, 1989. 

V. Van Dongen. Quasi-regular arrays definition and design methodology. Proc. IEEE Int. Con, on Systolic Arrays, 1989. 

Based on the denotational semantics of Alpha [11], axiomatic rules are defined, and semantic-preserving transformations oriented towards the synthesis of systolic arrays are built from these rules. The Alpha du Centaur program offers an interactive environment for applying these transformations, either for the generation of a parallel program [8] or for the synthesis of a chip [2]. A few of these transformations will be discussed in more depth for the motion estimator below. 

C. Dezan, E. Gautrin, H. Le Verge, P. Quinton, and Y. Saouter. Synthesis of systolic arrays by equation transformations. Proc. of the IEEE International Conference on Application Specific Array Processors. IEEE Computer Society Press, Sep 1991. 

S. Y. Kung. Systolic array processors performance analysis and design optimization, chapter 4.4, pages 226-248. Prentice Hall, 1988. 

---