CSC/ECE 506 Spring 2012/1c 12

This article is a discussion on systolic arrays and their relation to MISD architectures. Since very little information and no examples are available on MISD, this article gives a brief introduction using Flynn's 1966 taxonomy on the subject. The article then presents a brief introduction to systolic arrays and discusses their mathematical uses and real-world engineering uses as examples. From these applications, the article shows where the claim that systolic arrays are examples of MISD is acceptable, and where it stretches the argued definition of MISD.

MISD

Micheal J. Flynn introduced the idea of an MISD (Multiple Instruction, Single Data) computer architectures in his original taxonomy in 1966.^[1] The basic Flynn's architecture is as below

From the notes of Cornell Theory center ^[30].

The MISD Architecture

Dr. Yan Solihin defines MISD as "..an architecture in which multiple processing elements execute from different instruction streams, and data is passed from one processing element to the next."^[2] He also notes that MISD architectures are restricted to certain types of computations due to the requirement of data-passing between processing elements.^[2] Each processing element executes different instructions on the data stream.^[3] Every time the data is processed by a processing element, we can always argue that the data is no longer the original data introduced at the start of the stream.^[4]

From NCSU CSC/ECE 506 Spring 2012 Lecture 1 notes^[5].

From this image, we see that the data stream has one clear entrance and exit into the system. What we are unsure of is if each processing element has access to a collective instruction storage or if all processing elements are embedded with an individual instruction storage. Depending on the specific system described, each processing element is generally function specific or predestined; but in some systems (similar to iWarp), each processing element may be quite advanced.

From Flynn's paper "Very High-Speed Computing Systems," 1966^[14].

For this image, Flynn describes each processing element as an independent virtual machine that operates on independent program sequences. He explicitly states that each processing element has it's own private instruction memory, which limits the data stream as being the only interaction between instruction streams.^[14]

From Flynn's paper "Very High-Speed Computing Systems," 1966. "Under such an arrangement, only the first execution unit sees the source data stream and while it is processing the ith operand, the ith execution unit is processing the ith derivation of the first operand of the source stream."^[14]

In this image, Flynn demonstrates a version of MISD in which the data stream is a force forwarding of operands between the execution units. An instruction that any individual execution unit sees can be fixed (flexible setup of units), semi-fixed (one pass of a data file), or variable (stream of instructions could operate on any point of the data stream)^[14].

MISD Computers

While it is widely believed that no actual MISD computer exists in practice, it is controversially argued that a systolic array is the most common example of MISD^[6]. One often cited example of MISD (most notable from the MISD wiki article) is the space shuttle flight-control computers. The authors of this article found no source material backing this claim (even the MISD wiki is awaiting a citation on the claim), and found very little on the actual architectures of those computers. The closest assumption for the claim the authors of this article could find is the system designed for redundancy management/fault tolerance^[29], which [26] discusses the uses of systolic array in fault-tolerant systems.

Some arguments exist that pipelined vector processors could be considered an example of MISD architecture due to the fact that a different operation is performed on the data stream as it flows from stage to stage^[6]. The argument against this idea is that individual processing elements in each stage do not technically fetch their operations from an instruction cache^[6], but are more similar to a function specific, or ASIC, chip.

One application that exists for MISD VLSI architectures are applications which require multiple pattern matching in large data streams that lack any preprocessed indexes for lookups^[8]. This research presents a set of recursive query semantics: "concatenation of basic strings and patterns, alphanumerical comparisons of simple strings, boolean operations on subexpressions, and hamming distance filtering"^[12], and then explains that the recursion process of the semantics is best understood as a "..recursion tree where the result is found by propagating the results from the leaf nodes...to the root of the tree"^[12].

Recently, Stanford University and Maxeler Technologies have been working on acceleration methodologies that benefit from combining different computer architectures. One of the proposed methodologies based on FPGA arrays uses SIMD for multiple data strips until the pin bandwidth limits the acceleration, then switches to an MISD-style pipeline of the FPGA arrays until acceleration is limited by circuit limitations^[13]. Similar research on implementing MISD pipelines via FPGAs for biologicaly-inspired machine vision (VI-like) algorithms has been introduced in [18].

Systolic Array

The systolic array was first introduced in 1978 by Kung and Leiserson.^[20]

What is a Systolic Array?

"A systolic array is an arrangement of processors in an array (often rectangular) where data flows synchronously across the array between neighbors"^[7] Systolic arrays have data processing units (DPU) arranged in the form an matrix such that they are connected to their neighbors in the form of a mesh.^[9]

The two models of systolic arrays are shown below:

From systolic array and their architecture by Jonathan break^{[23 ]}.

The above diagram represents a systolic array where each DPU performs a specific operation on the data which can be input/output from an external source in the case of embedded systems or could be system generated by a auto sequencing memory unit. Each DPU performs a different computation based on the instruction set given to it and takes in data from the top or the left and then outputs it to it's right or below. A systolic array may or may not have local memory based on the application it is being used for.

Matrix multiplication using systolic array^[10].

An example of an application of systolic array is a matrix multiplication. The systolic array can have a 4X4 mesh to multiply two 4X4 matrices where the data of all the rows and columns to be multiplied can be entered as the input into each DPU and the instruction executed by each DPU would be to multiply the incoming stream of numbers and add them to a previous value stored in it if there is any. The final output that is the resultant matrix would be the values stored in each DPU.

The function of  each DPU in the above example is as follows
1)Each DPU takes as input a and b 
2)Multiplies a ,b
3)It adds the value of multiplication to a previous value and stores the value of addition
4)Sends value of a to DPUij+1 if j is not 4
5)Sends value of b to DPUi+1j if i is not 4

Systolic arrays can be used to make algorithms involving a lot of parallel computation much easier. "Systolic array processors have been known to be extremely efficient at executing the class of algorithms that exhibit tight coupling between neighboring cells via data transfers in an N-dimensional model space."^[11] Though the size of the array does affect the performance. Small systolic arrays present timing issues, limitations on bus width and chip pins, as well as pipeline drain caused by interruptions in the data flow. Approaches discussed to resolve these issues were problem partition (either the specified algorithm or the data array), array emulation (time-sharing a small array's processors to mimic a larger array more properly suited to the specified algorithm), and software based scheduling programs.^[15] The size of a systolic array is primarily determined by the number of individual processing elements and the total computation time needed for the specific algorithm, but then this also depends on the length of the loop and the transformation matrix of the specific algorithm.^[17]

Applications of Systolic Arrays

Various complex systems that can be optimized with systolic arrays include:

• Video Filtering
• Data Compression
• Image Processing
• Signal Processing
• Graphic Algorithms
• Biological Sequence Comparison

Systolic arrays are useful in these applications due to their usefulness in efficiently accelerating computation-intense problems ("..problems where the amount of computation required to solve the problem is very large compared to the amount of input/output"^[25]) like vector-matrix multiplication, Discrete Fourier Transforms (DFT), Fast Fourier Transforms (FFT), convolution, Dynamic Time Warping (DTW), and differential equations. [26] also presents data supporting the use of systolic array for algorithm-based fault tolerant systems, using Laplace's equation as an example.

Discrete Fourier Transforms

Systolic Array architecture as used in Efficient One-Dimensional Systolic Array Realization of the Discrete Fourier Transform break^{[19 ]}.

The advancement of VLSI systolic arrays became the first preference to use for the digital processing algorithms as systolic array's could solve complicated problems by just using array which are similar.A Discrete Fourier transform (DFT) could be efficiently calculated using a one dimensional systolic array which was formed by using a modification of First order Goertzel algorithm.

The picture on the right shows a systolic array for a 3 point DFT.The data is sent continuously into the array and a each cell takes in a sample to calculate one DFT sample.Each cell has an adder and PROM multiplier .After calculating one sample the cells send the data to their neighbors and hence a new sample is available at each cell again for computation.The input given is {a(0),a(1),a(2)} ,{b(0),b(1),b(2)}, {c(0),c(1),c(2)} and the output DFT vectors are {A(0),A(1),A(2)} , {B(0),B(1),B(2)} , {C(0),C(1),C(2)}. "Each cell accumulates partial terms of one particular DFT sample" ^{[19 ]}

Fast Fourier transform

^[28] uses a special type of systolic array called Tagged Systolic Array(TSA)to solve Fast Fourier Transform , as they cannot be represented in the form of uniform recurrence equations which makes the formulation of a simple systolic array to solve it difficult.

In a TSA "tags are attached to the results of a particular computation for properly routing them to other processing elements (PES)/DPU's where the result of that particular computation is required." ^[28] It uses the communication links of only the nearest neighbors to send its data.

To design a systolic array for an FFT the index points should be mapped to a smaller number of processing elements which should be connected. But the problem arises as the PE's which generate the variable and the PE which use the variable might not necessarily be neighbors in this case and also the location of destination PE might change with time and location of the source." In such cases tags (evaluated based on location and time) are attached to the data generated at the source PE for proper routing of data. This type of architecture that uses tags for data routing is called a Tagged Systolic Array (TSA)"

The TSA for FFT is a linear array and uses tags to pass data.

Tagged systolic array for FFT^{[28 ]}.

Each PE stores two kinds of data one for computation and the other is an intermediate result as well as two tags which are always constant. "The tag of a data is checked at a PE to determine its further direction of movement or to decide whether the data is required at the PE itself." If the data is required by the PE it stores it else it forwards it to its neighboring PE.

All the PE's in the pipeline are divided into various groups such that each group is used for calculating a different stage of a FFT. PE's in one group perform a similar operation. In the figure "PE1 performs the computations of stage 1, PE2 & PE3 perform computations of stage 2 and PE4, PE5,PE6 & PE7 are responsible for stage 3 computation."^[28]

Convolution

In 2003, the idea of a super-systolic array was introduced by Jae-Jin Lee and Gi-Yong Son. [16] explains that a super-systolic array involves making cells of systolic array themselves a systolic array and defines the use of a super-systolic array for convolution as "..a logical systolic array in a sense that the array assumes all operation to complete in a unit delay to maintain rhythmic data flow." For the convolution problem in [16], each cell in the systolic array is capable of performing multiplication and addition. It is the multiplication process that benefits highly from systolization, and is implemented as a systolic array in itself. Converting the cells of systolic array into systolic array themselves results in higher degrees of concurrency and lower resource consumption^[16].

Synthesized schematic for systolic multiplier in [16].

[22] introduces the concept of the moment-based systolic array of convolutions, which generally decreased to total delay associated with convolution implementations.

Moment-based systolic array of convolutions from [22].

Dynamic Time Warping (DTW)

[24] introduces DTW as an array of identical processing units, each designed to compute local distance and global measurements of dissimilarity. Systolic arrays were discovered in [24] to reduce design costs and speed up processing time by processing a new reference pattern immediately following the completion of the previous reference pattern. [24] found that by precisely defining the kind of interconnections between each individual processing unit to suit particular application requirements bypassed the problem of only half the processing units working only half the time, thus they were able to obtain optimal performance for individual circuits and the system as a whole. Although, for [24], the individual processing units themselves are ASIC to the DTW algorithm being implemented.

Differential Equations (DEQ)

[25] discusses the use of systolic array for real-time simulations of industrial systems. They propose a system of three DEQs (N=3, four terms). The systolic array operates through each function, evaluating the four terms (simultaneously) and feeding the results back into itself. [25] explains that if the system is linear, the initial elements of the differential matrix are constant throughout the simulation; but if the system is nonlinear, new matrix elements are computed and loaded into the proper nodes of the systolic array. The proposed systolic array in [25] is seemingly re-configurable, in that as N changes, the array can adjust.

"Systolic array for real-time simulation of dynamic systems (N = 3) of DEQs" ^[25].

[27] discusses use of the Runge-Katta method to solve ordinary dynamic equations (ODE) and partial dynamic equations (PDE) within the Yau filtering system. The ability to perform parallel computations on systolic architectures became one advantage for using the Runge-Katta method. [27] is another example of the use of systolic array for matrix-vector multiplication, as well as vector addition.

Systolic Array vs. MISD

If relating to an MISD architecture, a systolic array is "..a network of small computing elements connected in a regular grid. All the elements are controlled by a global clock. On each cycle, an element will read a piece of data from one of its neighbors, perform a simple operation (e.g. add the incoming element to a stored value), and prepare a value to be written to a neighbor on the next step"[6]. This of course relates to the idea that typically the inner processing units (or nodes) of a systolic array do not access memory or buffers, but pass the data from node-to-node via registers. This relates to Flynn's taxonomy of MISD architecture correctly in that only the first and last processing units (nodes) will access the original data stream. Conversely, [21] describes a systolic array system quite unlike an MISD architecture by emphasizing that the systolic array pipeline reduces the need for control logic, control signal generation, and the cost of FSM design.

If a systolic array is not designed with a local memory, the individual processing units are then generally designed to be non-programmable (basically ASIC) and data is then introduced to the systolioc array through an outside shared memory controller (perhaps even through buffers to ease memory traffic)^[15]. If designed without a local memory, then, a systolic array does not fit Flynn's taxonomy of MISD architecture: the data stream is still the only means of interaction between the individual processing units, but those individual processing units lack individual intruction memories. It could be argued to mimic SISD (single instruction, single data) at this point, since the processing units themself are generally application-specific. If a systolic array is designed with a local memory, it gains not only the ability to fetch data from that local memory^[15], but also instructions. It could: a) have a local instruction memory, in which a program fetches and transmits instructions to each individual processing unit (on the assumption that each of those units is beyond application-specific), or b) attempt to mimic Flynn's MISD taxonomy and grant each of those individiaul processing units an individual instruction memory. The second option does present much overhead, and if not necessarily application or algorithm dependant, will be quite costly for no appearnt reason.

Consistently we see that one major design characteristic that either places a systolic array in the MISD list or forces it to stretch the definition is the idea of application-specification, or being problem specific. The MISD architecture Flynn describes are individual processing units that are typically the same as it's neighbors,^[14] which we presume are guided by an ISA (instruction set architecture) capable of identification and execution of multiple operations. To achieve a systolic array that is more purely MISD, it must be re-configurable in some way. [17] defines a re-configurable systolic array as one "..that can be adapted to computing multiple problems through either software or hardware configuration, or both." [17] shows that one such way is to design the systolic array architecture such that two or more algorithms can mapped to a single re-configurable systolic array. This is done in two steps: compute individual algorithms one at a time with their proper control settings, then extend the array using time or space redundancy to compute multiple algorithms simultaneously. The space-time mapping procedure in [17] is achieved by mapping different algorithms to individual systolic arrays using one common transformation matrix, then extracting common parts of each circuit within processing units and merging those arrays into one re-configurable systolic array.

One final argument for the claim that calling systolic array an MISD architecture is stretching the definition of MISD is that generally, for most applications, both the data and instruction streams for systolic array are serial. This conflicts with Flynn's taxonomy of MISD because he classifies it as an example of parallel computer architecture^[14] in which the instruction stream is parallel.

References

1. Flynn, M. (1972). "Some Computer Organizations and Their Effectiveness". IEEE Trans. Comput. C-21: 948.
2. Solihin, Y. (2008). "Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems". Solihin Publishing & Consulting LLC. C-1: 12.
3. CSC 8383 Lecuture 5
4. MISD wiki
5. ECE506 Spring 2012 Lecture 1
6. 3.1.3 MISD Computers
7. Laiq hasan,Yahya M.Khawaja,Abdul Bais,"A Systolic Array Architecture for the Smith-Waterman Algorithm with High Performance Cell Design" in IADIS European Conference Data Mining, 2008, pp. 37
8. Arne Halaas, Børge Svingen, Magnar Nedland, Pål Sætrom, Ola Snøve, Jr., Olaf René Birkelan, "A Recursive MISD Architecture for Pattern Matching," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 12, No. 7, pp. 727, July 2004.
9. Systolic array
10. Systolic array architecture
11. Robert E. Morley, Jr.Thomas J. Sullivan ,"A Massively Parallel Systolic Array Processor System," in Electronic Systems and Signals Research Laboratory,Department of Electrical Engineering,Washington University, pp. 217.
12. Arne Halaas, Børge Svingen, Magnar Nedland, Pål Sætrom, Ola Snøve, Jr., Olaf René Birkelan, "A Recursive MISD Architecture for Pattern Matching," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 12, No. 7, pp. 728, July 2004.
13. Michael Flynn, R. Dimond, O. Mencer, O. Pell, "Finding Speedup in Parallel Processors," in International Symposium on Parallel and Distributed Computing, pp. 3, 2008.
14. Michael J. Flnn, "Very High-Speed Computing Systems," Proceedings of the IEEE, Vol. 54, No. 12, pp.1908, December 1966.
15. Henry Y. H. Chuang, Ling Chen, "A General Approach to Solving Arbitrarily Large Problems in a Fixed Size Systolic Array," in Proceedings of the Twenty-First Annual Hawaii International Conference on System Sciences, Vol. 2, Software Track, pp. 195-204, 1988.
16. Jae-Jin Lee, Gi-Yong Song, "Implementation of the Super-Systolic Array for Convolution," in Proceedings of the ASP-DAC Asia and South Pacific Design Automation Conference, pp. 491-494, 2003.
17. Wei Jin, Cang N. Zhang, and Hua Li, "Mapping Multiple Algorithms into a Reconfigurable Systolic Array," in Canadian Conference on Electrical and Computer Engineering, pp. 1187-1191, 2008.
18. Vinay Sriram, David Cox, Kuen Hung Tsoi, and Wayne Luk, "Towards an Embedded Biologically-Inspired Machine Vision Processor," in International Conference on Field-Programmable Technology (FPT), pp. 273-278, 2010.
19. J.A. Beraldin, Tyseer Aboulnasar, and Willem Steenart, "Efficient One-Dimensional Systolic Array Realization of the Discrete Fourier Transform," in IEEE Transactions of circuits and systems, Vol. 36, No. 1, pp. 95-100, January 1989.
20. H. Kung, and C. Leiserson, “Systolic arrays (for VLSI),” in Sparse matrix proceedings, 1978. Society for Industrial & Appl. Mathematics, pp. 256–309, 1979.
21. Liang Lu, Weiqiang Liu, Maire O’Neill, and Earl E. Swartzlander Jr., "QCA Systolic Array Design," in IEEE Transactions on Computers, Issue 99, December 2011.
22. Jianguo Liu, Chao Pan, and Zhenbing Li, "Novel Convolutions using First-order Moments, in IEEE Transactions on Computers, Issue 99, July 2011.
23. Matrix Multiplication using systolic array
24. F. Jutand, N. Dennassieux, D. Vicard, and G Chollet, "VLSI Architectures For Dynamic Time Warping Using Systolic Arrays," in Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP, Vol. 9, pp. 778-781, March 1984.
25. Machiraju Vijay and C. Siva Ram Murth, "Real-Time Simulations of Dynamic Systems on Systolic Arrays," in IEEE Transactions on Industrial Electronics, Vol. 45, No. 2, pp. 326-332, April 1998.
26. Amber Roy-Chowdhury and Prithviraj Banerjee, "A Fault-Tolerant Parallel Algorithm for Iterative Solution of the Laplace Equation," in the International Conference on Parallel Processing, Vol. 3, pp. 133-140, Augus 1993.
27. Yen-Tai Lai, Stephen S. T. Yau, and Ping-Hua Chen, "Design of The Ordinary Differential Equation Solver in The Yau Filterin System," in Proceedings of the 2002 American Control Conference, Vol. 6, pp. 5144-5149, May 2002.
28. Susanta Sarkar, A. K. Majumdar "Fast Fourier transform using Linear Tagged Systolic Array" in IEEE Region 10 Conference on Computer and Communication Systems, Hong Kong, pp. 289-293, September 1990.
29. "EVOLUTION OF SHUTTLE AVIONICS REDUNDANCY MANAGEMENT/FAULT TOLERANCE"
30. http://mpc.uci.edu/wget/www.tc.cornell.edu/Services/Edu/Topics/ParProgCons/