Systolic Array Synthesis using SFG Representations

One of the important design problems in systolic array processing is the development of a systematic methodology for transforming an algorithm represented in some high level constructs into a systolic architecture specified by the timing of data movement and the interconnection of processing elements such that the design requirements are satisfied. In this paper a method using the SFG (signal flow graph) of a given algorithm to design systolic arrays through graphic mapping and retiming is presented. An algorithm is first represented by a DG (dependence graph). Then the DG is mapped into an SFG by a graph projection. Cut-set retiming procedures are then applied to derive a regular localised SFG from which a systolic array design can be obtained for the given matrix examples i.e. LU and QR decompositions.

Keywords:

• Signal Flow Graph (SFG)
• Dependence Graph (DG)
• Systolic Array (SA)
• Mapping
• Lu And Qr Matrix Decompositions
• Optimal Design