For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Building Systolic Messy Arrays for Infinite Iterative Algorithms
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/08/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: General Fundamentals and Boundaries
infinite iterative algorithms, systolic messy arrays, systolic arrays,
Full Text: PDF>>
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.