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

Scalable hardware-algorithms for binary prefix sums

  • Conference paper
  • First Online:
Parallel and Distributed Processing (IPPS 1999)

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

Included in the following conference series:

  • 127 Accesses

Abstract

The main contribution of this work is to propose a number of broadcast-efficient VLSI architectures for computing the sum and the prefix sums of a w k-bit, k≥2, binary sequence using, as basic building blocks, linear arrays of at most w 2 shift switches. An immediate consequence of this feature is that in our designs broadcasts are limited to buses of length at most w 2 making them eminently practical. Using our design, the sum of a w k-bit binary sequence can be obtained in the time of 2k−2 broadcasts, using 2w k−2+O(w k−3) blocks, while the corresponding prefix sums can be computed in 3k−4 broadcasts using (k+2)w k−2+O(kw k−3) blocks.

Work supported by NSF grants CCR-9522092 and MIP-9630870, by NASA grant NAS1-19858, by ONR grants N00014-95-1-0779 and N00014-97-1-0562 and by ARC grant 04/15/412/194.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. G. Blelloch, Scans as primitives parallel operations, IEEE Transactions on Computers, C-18, (1989), 1526–1538.

    Article  Google Scholar 

  2. J. J. F. Cavanaugh, Digital Computer Arithmetic Design and Implementation, McGraw-Hill, New York, 1984.

    Google Scholar 

  3. H. T. Kung and C. E. Leiserson, Algorithms for VLSI processor arrays, in C. Mead and L. Conway, Eds, Introduction to VLSI Systems, Addison-Wesley, Reading MA, 1980.

    Google Scholar 

  4. R. E. Ladner and M. J. Fisher, Parallel prefix computation, Journal of the ACM 27, (1980), 831–838.

    Article  MATH  Google Scholar 

  5. R. Lin, and S. Olariu, Reconfigurable buses with shift switching-architectures and applications, IEEE Transactions on Parallel and Distributed Systems, 6, (1995), 93–102.

    Article  Google Scholar 

  6. K. Nakano, An efficient algorithm for summing up binary values on a reconfigurable mesh, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, E77-A, 4, (1994), 652–657.

    Google Scholar 

  7. K. Nakano, Prefix-sums algorithms on reconfigurable meshes, Parallel Processing Letters, 5, (1995), 23–35.

    Article  Google Scholar 

  8. S. Olariu, J. L. Schwing, and J. Zhang. Fundamental data movement algorithms for reconfigurable meshes. International Journal of High Speed Computing, 6, (1994), 311–323.

    Article  Google Scholar 

  9. E. E. Swartzlander, Jr., Computer Arithmetic Vol. 1, IEEE CSP, 1990.

    Google Scholar 

  10. Thinking Machines Corporation, Connection machine parallel instruction set (PARIS), July 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, SUNY Geneseo, 14454, Geneseo, NY, USA

    R. Lin

  2. Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa-ku, 466-8555, Nagoya, Japan

    K. Nakano

  3. Department of Computer Science, Old Dominion University, 23529, Norfolk, VA, USA

    S. Olariu

  4. I.E.I., C.N.R., Pisa, Italy

    M. C. Pinotti

  5. Department of Computer Science, Central Washington University, 98926, Ellensburg, WA, USA

    J. L. Schwing

  6. Parallel Computing Research Lab, Dept. of Electrical and Electronic Eng, University of Western Australia, Perth, Australia

    A. Y. Zomaya

Authors
  1. R. Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. K. Nakano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Olariu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. M. C. Pinotti
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. J. L. Schwing
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. A. Y. Zomaya
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

José Rolim Frank Mueller Albert Y. Zomaya Fikret Ercal Stephan Olariu Binoy Ravindran Jan Gustafsson Hiroaki Takada Ron Olsson Laxmikant V. Kale Pete Beckman Matthew Haines Hossam ElGindy Denis Caromel Serge Chaumette Geoffrey Fox Yi Pan Keqin Li Tao Yang G. Chiola G. Conte L. V. Mancini Domenique Méry Beverly Sanders Devesh Bhatt Viktor Prasanna

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag

About this paper

Cite this paper

Lin, R., Nakano, K., Olariu, S., Pinotti, M.C., Schwing, J.L., Zomaya, A.Y. (1999). Scalable hardware-algorithms for binary prefix sums. In: Rolim, J., et al. Parallel and Distributed Processing. IPPS 1999. Lecture Notes in Computer Science, vol 1586. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0097948

Download citation

  • DOI: https://doi.org/10.1007/BFb0097948

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-65831-3

  • Online ISBN: 978-3-540-48932-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation