×

Using fixed-point semantics to prove retiming lemmas. (English) Zbl 0774.68077

Summary: Algorithms designed for VLSI implementation are commonly described for directed graphs, in which the nodes represent functional units and the arcs indicate communication links. We give a denotational semantics for such a graph in terms of the least fixed point of a set of (mutually recursive) functions definition, describing the outputs produced at each node as a function of time. This semantics is consistent with the conventional clocked operational semantics of the system. A retiming is a systematic modification of the intermode delays of a design, often used to convert an algorithm design into a systolic form. The utility of such retimings in optimizing the behavior of designs is well known. We use fixed-point semantics to provide simple proofs of the correctness of certain retiming transformations from the literature and to just other design transformations such as pipelining.

MSC:

68Q55 Semantics in the theory of computing
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
Full Text: DOI

References:

[1] Charles E. Leiserson and James B. Saxe. Optimizing synchronous systems.Journal of VLSI and Computer Systems, 1(1): 41-68 (1983). · Zbl 0532.94015
[2] H.T. Kung and W.T. Lin. An algebra for VLSI computation. InElliptic Problem Solvers II, G. Birkhoff and A.L. Schoenstadt (eds.). Academic Press, New York, January 1983.
[3] M.C. Chen.Space-time Algorithms: Semantics and Methodology. Ph.D. thesis, Department of Computer Science, California Institute of Technology, May 1983.
[4] M.C. Chen and C.A. Mead. A hierarchical simulator based on formal semantics. InProceedings of the Third Caltech Conference on Very Large Scale Integration, R. Bryant (ed.). Computer Science Press, Rockville, Maryland, March 1983, papes 207-223.
[5] M.J.C. Gordon. A model of register transfer systems with applications to microcode and VLSI correctness. Department of Computer Science Technical Report CSR-82-81, University of Edinburgh, 1981.
[6] J.E. Stoy.Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics. MIT Press, Cambridge, MA, 1977. · Zbl 0503.68059
[7] D.S. Scott and C. Strachey. Toward a mathematical semantics for computer languages. InProceedings of the Symposium on Computers and Automata, J. Box (ed.). Polytechnic Institute of Brooklyn Press, New York, 1971, pp. 19-46.
[8] H.T. Kung and M. Lam. Fault-tolerance and two-level pipelining in VLSI systolic arrays. InProceedings of the Conference on Advanced Research in VLSI, MIT, Cambridge, MA, January 1984.
[9] J.W. de Bakker and D.S. Scott. A theory of programs.Seminar on Programming Theory, Vienna, 1969.
[10] G. Kahn and D.B. MacQueen. Coroutines and networks of parallel processes. InInformation Processing 1977. North Holland, Amsterdam, 1977, pp. 993-998. · Zbl 0363.68076
[11] M. Lam and J. Mostow. A transformational model of VLSI systolic design. InProceedings of the 6 th International Symposium on Computer Hardware Description Languages and their Applications, T. Uehara and M. Barbacci (eds.). IFIP, Pittsburgh, PA, May 1983.
[12] Stephen N. Cole. Real-time computation byn-dimensional iterative arrays of finite-state machines.IEEE Transactions on Computers, C-18:349-365 (April 1969). · Zbl 0172.20804 · doi:10.1109/T-C.1969.222663
[13] H.T. Kung and Charles E. Leiserson. Systolic arrays (for VLSI). InSparse Matrix Proceedings 1978, I.S. Duff and G.W. Stewart (eds.). Society for Industrial and Applied Mathematics, 1978, Philadelphia, PA, pp. 256-282.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.