[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

A derivation of a systolic rank order filter with constant response time

  • Contributed Lectures
  • Conference paper
  • First Online:
Mathematics of Program Construction (MPC 1989)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 375))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bird, R., Wadler, P. Introduction to Functional Programming Prentice-Hall International, London, 1988

    Google Scholar 

  2. Hoare, C.A.R. Communicating Sequential Processes Comm. of the ACM 21 (1978), 666–677

    Article  Google Scholar 

  3. 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

    Google Scholar 

  4. Kung, S.Y. VLSI Array Processors Prentice-Hall, Englewood Cliffs, 1988

    Google Scholar 

  5. Martin, A.J. Compiling communicating processes into delay-insensitive VLSI circuits Distributed Computing 1 (1986), 226–234

    Google Scholar 

  6. 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

    Google Scholar 

  7. 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

    Google Scholar 

  8. 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

    Google Scholar 

  9. Zwaan, G. Parallel Computations Doctoral Dissertation, Eindhoven University of Technology, Eindhoven, 1989

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

J. L. A. van de Snepscheut

Rights and permissions

Reprints 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

Publish with us

Policies and ethics