Abstract:
A technique is described for partitioning 2-D signal flow graph (SFG)/systolic arrays to a 2-D triangular array (triarray) of N(N+1)/2 processors. The folding technique c...Show MoreMetadata
Abstract:
A technique is described for partitioning 2-D signal flow graph (SFG)/systolic arrays to a 2-D triangular array (triarray) of N(N+1)/2 processors. The folding technique can be used to partition 2-D SFGs onto smaller subarrays of the SFG. The stages of development are all highly suited to CAD from algorithm specification to array implementation, and can be performed in an integrated mapping methodology using the Occam algebra. Because of the Occam algebra-based partitioning, the data flow of the SFG has been preserved and the SFG implementation on the triarray is guaranteed to be functionally correct. The control overheads introduced by this scheme are minimal and very straightforward, i.e. a very simple mux and demux processes at the link interfaces of each transputer to code and decode the data flow tags. It is concluded that a triarray of transputers (or transputer link wavefront devices) is a highly versatile and flexible array processor when the folding scheme is used.<>
Date of Conference: 11-14 April 1988
Date Added to IEEE Xplore: 06 August 2002
Print ISSN: 1520-6149
References is not available for this document.
Select All
1.
S. Y. Kung, VLSI Array Processors, Prentice-Hall, 1987.
2.
Transputer Reference Manual.
3.
D. Pountain, A Tutorial Introduction to Occam Progra.Tming, 1986.
4.
K. Jainandunsing, "Optimal Partitioning Schemes for Wavefront/Systolic Array Processors", Proc. of ICCAS 86, pp. 940-943.
5.
R. W Stewart, An Integrated Design Methodology for Mapping Algorithms to Fixed Array Architectures, December 1987.
6.
S. Y. Kung and J. N. Hwang, "A Systolic Array Processor for Kaiman Filtering", IEEE Trans. on ASSP, Sept 1987.
7.
S. Y. Kung and R. W. Stewart, "Kaiman Filtiering on a Fixed Transputer Array", EUSIPCO Conference on Signal Processing, 1988-Spetember.
8.
Navarro, "Efficient Mapping of Some Numerical Linear Algebra Problems on SAPs", Proc. Intnl. Wrkshp. on Systolic Arrays, 1987-July.
9.
J. McWhirter, "A Novel Algrithm and Architecture for Adaptive Digital Beamforining", IEEE Trans on AP, pp. 338-346, March 1986.
10.
R. Chapman, T. Willey and T. S. Durrani, "Qesign Strategies for Implementing Systollc/Wavefront Arrays using Occam", Proc. TCASSP 85, 1985.
11.
S. Y. Kung, "Wavefront Array Processor: Language Architecture and Applications", IEEE Trans. on Computers, vol. C-31, no. 11, pp. 1054-1066, Nov. 1982.
12.
K. Hwang and Y. H. Cheng, "Partitioned Matrix Algorithms for VLSI Arithmetic Systems", IEEE Trans. on Computers, vol. C-31, no. 12, Dec. 1982.
