Building Systolic Messy Arrays for Infinite Iterative Algorithms

Makio ISHIHARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.8   pp.1719-1723
Publication Date: 2007/08/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.8.1719
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: General Fundamentals and Boundaries
Keyword: 
infinite iterative algorithms,  systolic messy arrays,  systolic arrays,  

Full Text: PDF>>
Buy this Article




Summary: 
The size-dependent array problem is a problem with systolic arrays such that the size of systolic arrays limits the size of calculations, which in a do-loop structure controls how many times it is repeated and how deep the nesting loops are. A systolic array cannot deal with larger calculations. For the size-dependent array problem, a spiral systolic array has been studied so far. It has non-adjacent connections between PEs, such as loop paths for sending data back so that data flows over the array independently of its own size. This paper takes an approach to the problem without non-adjacent connections. This paper discusses systolic messy arrays for infinite iterative algorithms so that they are independent from the size of calculations. First a systolic messy array called two-square shape is introduced then the properties of two-square shape are summarized: memory function, cyclic addition, and cyclic multiplication. Finally a way of building systolic messy arrays that calculate infinite iterative algorithms is illustrated with concrete examples such as an arithmetic progression, a geometric progression, N factorial, and Fibonacci numbers.