1995 IEEE International Conference on Application-Specific Array Processors (ASAP'95)
The naive execution of affine recurrence equations
Strasbourg, France
July 24-July 26
ISBN: 0-8186-7109-2
D. Wilde, Dept. of Comput. Sci., Oregon State Univ., Corvallis, OR, USA
S. Rajopadhye, Dept. of Comput. Sci., Oregon State Univ., Corvallis, OR, USA
In recognition of the fundamental relation between regular arrays and systems of affine recurrence equations, the ALPHA language was developed as the basis of a computer aided design methodology for regular array architectures. ALPHA is used to initially specify algorithms at a very high algorithmic level. Regular array architectures can then be derived from the algorithmic specification using a transformational approach supported by the ALPHA environment. This design methodology guarantees the final design to be correct by construction, assuming the initial algorithm was correct. In this paper, we address the problem of validating an initial specification. We demonstrate a translation methodology which compiles ALPHA into the imperative sequential language C. The C-code may then be compiled and executed to test the specification. We show how an ALPHA program can be naively implemented by viewing it as a set of monolithic arrays and their filing functions, implemented using applicative caching. This is the approach which is used by the translator. We discuss two problems that had to be solved before implementing the translator. The first is how to allocate 1-dimensional storage for a polyhedron, and the second is how to scan a polyhedron with nested loops.
Index Terms:
formal specification; algorithmic languages; circuit CAD; hardware description languages; affine recurrence equations; regular arrays; ALPHA language; computer aided design methodology; regular array architectures; algorithmic specification; transformational approach; imperative sequential language C; C-code; applicative caching; 1-dimensional storage; polyhedron; nested loops
Citation:
D. Wilde, S. Rajopadhye, "The naive execution of affine recurrence equations," asap, pp.1, 1995 IEEE International Conference on Application-Specific Array Processors (ASAP'95), 1995