Abstract
A design technique for systolic computations is explained by means of an example. The example is the derivation of a fast, parallel program for rank order filtering. The derivation proceeds in a calculational manner, originating from a formal specification and guided by performance considerations. The resulting solution is a linear systolic array of N cells, where N is the window size. It has constant response time and latency N.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bird, R., Wadler, P. Introduction to Functional Programming Prentice-Hall International, London, 1988
Hoare, C.A.R. Communicating Sequential Processes Comm. of the ACM 21 (1978), 666–677
Kung, H.T. Let's design algorithms for VLSI systems In Proc 1st Caltech Conference on VLSI (C.L. Seitz, ed.) California Institute of Technology, Pasadena, 1979, 65–90
Kung, S.Y. VLSI Array Processors Prentice-Hall, Englewood Cliffs, 1988
Martin, A.J. Compiling communicating processes into delay-insensitive VLSI circuits Distributed Computing 1 (1986), 226–234
Rem, M. Trace theory and systolic computations In PARLE Parallel Architectures and Languages Europe Vol. 1 (J.W. de Bakker et al., eds.) Lecture Notes in Computer Science 258, Springer-Verlag, Berlin, 1987, 14–33
Van Berkel, C.H., Rem, M., Saeijs, R.W.J.J. VLSI programming In Proc. 1988 IEEE Int. Conf. on Computer Design IEEE Computer Society Press, Washington, 1988, 150–156
Van Berkel, C.H., Saeijs, R.W.J.J. Compilation of communicating processes into delay-insensitive circuits In Proc. 1988 IEEE Int. Conf. on Computer Design IEEE Computer Society Press, Washington, 1988, 157–162
Zwaan, G. Parallel Computations Doctoral Dissertation, Eindhoven University of Technology, Eindhoven, 1989
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kaldewaij, A., Rem, M. (1989). A derivation of a systolic rank order filter with constant response time. In: van de Snepscheut, J.L.A. (eds) Mathematics of Program Construction. MPC 1989. Lecture Notes in Computer Science, vol 375. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51305-1_16
Download citation
DOI: https://doi.org/10.1007/3-540-51305-1_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51305-6
Online ISBN: 978-3-540-46191-3
eBook Packages: Springer Book Archive