Horizons of parallel computation | SpringerLink
Skip to main content
Springer Nature Link
Log in

Horizons of parallel computation

  • II. Symbolic Computation, Programming, and Software Engineering
  • Conference paper
  • First Online:
Future Tendencies in Computer Science, Control and Applied Mathematics (INRIA 1992)

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

Included in the following conference series:

Abstract

This paper considers the ultimate impact of fundamental physical limitations—notably, speed of light and device size—on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, we take here the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency-hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.

This author's work was supported in part by NSF Grant CCR91-96152 and by ONR Contract N00014-91-J-4052, ARPA order 8225.

This author's work was supported in part by the Italian National Research Council and the Italian Ministry of University and Research.

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.

Similar content being viewed by others

References

  1. Alt, H., Hagerup, T., Mehlhorn, K., Preparata, F.P.: Simulation of idealized parallel computers on more realistic ones, S1AM Journal on Computing, 16, 5 (1987) 808–835

    Article  MATH  MathSciNet  Google Scholar 

  2. Bay, P., Bilardi, G.: Deterministic on-line routing on area-universal networks. Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 297–306, October 1990

    Google Scholar 

  3. Bell, G.: A teraflop before its time, Comm. of the ACM, 35, 8 (1992), 26–47

    Article  Google Scholar 

  4. Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems, Journal of Computer and Systems Sciences, 28, 2 (1984), 300–342

    Article  MATH  MathSciNet  Google Scholar 

  5. Bilardi, G., Preparata, F. P.: Area-time lower-bound techniques with application to sorting, Algorithmica, 1, (1986), 65–91

    Article  MATH  MathSciNet  Google Scholar 

  6. Bilardi, G., Pracchi, M., Preparata, F.P.: A critique of network speed in VLSI models of computation, IEEE Journal Solid-State Circuits, 17 (1982), 696–702

    Article  Google Scholar 

  7. Brent, R.P.: The parallel evaluation of general arithmetic expressions, Journal of the ACM, 21, 2 (1974)201–206

    Article  MATH  MathSciNet  Google Scholar 

  8. Chazelle, B., Monier, L.: A model of computation for VLSI with related complexity results, Journal of the ACM, 32, (1985) 573–588

    Article  MATH  MathSciNet  Google Scholar 

  9. Cook, S.A.: An observation of time-storage tradeoff, JCSS, 9, 3, (1974)308–316

    MATH  Google Scholar 

  10. Cook, S.A.: Towards a complexity theory of synchronous parallel computation, Enseign. Math. 27, (1981) 99–124

    MATH  MathSciNet  Google Scholar 

  11. Cook, S.A., Reckhow, R.A.: Time bounded random access machines, Journal of Comput. System Science, 7 (1973) 354–375

    MATH  MathSciNet  Google Scholar 

  12. Flynn, M.J.: Very high-speed computing systems, Proc. IEEE 54, 12, (1966), 1901–1909

    Article  Google Scholar 

  13. Greenberg, R. I., Leiserson, C.E.: Randomized routing on fat-trees. In Micali, S., editor, Randomness and Computation, 345–374. JAI Press, Inc., 1989.

    Google Scholar 

  14. Herley, K., Bilardi, G.: Deterministic simulations of PRAMs on bounded-degree networks, Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, (1988), 1084–1093

    Google Scholar 

  15. Karlin, A., Upfal, E.: Parallel hashing — an efficient implementation of shared memory, Journal of the ACM, 35, 4(1988) 876–892

    Article  MATH  MathSciNet  Google Scholar 

  16. Karp, R.M., Ramachandran, V.: Parallel algorithms for shared-memory machines, Handbook of Theoretical Computer Science: Algorithms and Complexity (J.v. Leeuwen, ed.) Elsevier-The MIT Press, 1990

    Google Scholar 

  17. Kruskal, C.P., Rudolf, L., Snir, M.: A complexity theory of efficient parallel algorithms, Theoretical Computer Science, 71 (1990) 95–132

    Article  MATH  MathSciNet  Google Scholar 

  18. Kung, H.T.: Why systolic architectures? Computer Magazine, 15, 1, (1982), 37–46

    Google Scholar 

  19. Ladner, R.E.: The Circuit Value problem is logspace complete for P, SIGACT News 7, 1(1975), 18–20

    Article  MathSciNet  Google Scholar 

  20. Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes, Morgan Kaufmann, 1991

    Google Scholar 

  21. Leighton, F.T.: Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI, Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, Massachusetts, September 1981

    Google Scholar 

  22. Leiserson, C.E.: Fat-trees: Universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, C-34, 10 (1985) 892–900

    Google Scholar 

  23. Leiserson, C.E., Maggs, B.M.: Communication-efficient parallel algorithms for distributed random-access machines. Algorithmica, 3 (1988) 53–77

    Article  MATH  MathSciNet  Google Scholar 

  24. Mead, C., Conway, L.: Introduction to VLSI Systems, Addison-Wesley, 1980

    Google Scholar 

  25. Mehlhorn, K., Vishkin, U.: Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, 21, 4 (1984) 339–374

    Article  MATH  MathSciNet  Google Scholar 

  26. Pease, M.C.: The indirect binary n-cube microprocessor array, IEEE Transactions on Computers, C-26, 5, (1977), 458–473

    Article  Google Scholar 

  27. Pippenger, N.: On simultaneous resource bounds, Proceedings of the 20th IEEE Symposium Foundation of Computer Sicence, (1979) 307–311

    Google Scholar 

  28. Preparata, F.P., Vuillemin, J.: The cube-connected cycles: A versatile network for parallel computation, Communications of the ACM, 24, 5 (1981)300–309

    Article  MathSciNet  Google Scholar 

  29. Ranade, A.G.: How to emulate shared memory, Proceedings of the 28th Annual Symposium on the Foundations of Computer Science,(1987), 185–192

    Google Scholar 

  30. Rosenberg, A.L.: Three-dimensional integrated circuitry. In H.T. Kung, B. Sproull, and G. Steele, editors, Proceedings of the CMU Conference on VLSI Systems and Computations, Computer Science Press (1981), 69–80

    Google Scholar 

  31. Smith, B. J.: Architecture and applications of the HEP multiprocessor system, Signal Processing IV, 298, (1981), 241–248

    Google Scholar 

  32. Snyder, L.: Type architectures, shared memory, and the corollary of modest potential, Annual Review of Computer Science, 1 (1986) 289–317

    Article  Google Scholar 

  33. Thompson, C.D.: A Complexity Theory for VLSI. Ph.D. dissertation, Carnegie-Mellon University, August 1980

    Google Scholar 

  34. Upfal, E., Wigderson, A.: How to share memory in a distributed system, Journal of the ACM, 34, 1(1987) 116–127

    Article  MATH  MathSciNet  Google Scholar 

  35. Valiant, L.G.: A bridging model for parallel computation, Communications of the ACM, 33, 8 (1990), 103–111

    Article  Google Scholar 

  36. Valiant, L.G.: General purpose parallel architectures, Handbook for Theor. Computer Science [J.v. Leeuwen, ed.], Elsevier-MIT Press, 1990

    Google Scholar 

  37. Valiant, L.G.: Universality considerations in VLSI circuits, IEEE Transactions on Computers, C-30, 2, (1981) 135–140

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Elettronica ed Informatica, Università di Padova, Via Gradenigo 6/A, 3513, Padova, Italy

    Gianfranco Bilardi

  2. Department of Computer Science, Brown University, 02912-1910, Providence, RI

    Franco P. Preparata

Authors
  1. Gianfranco Bilardi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Franco P. Preparata
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

A. Bensoussan J. -P. Verjus

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bilardi, G., Preparata, F.P. (1992). Horizons of parallel computation. In: Bensoussan, A., Verjus, J.P. (eds) Future Tendencies in Computer Science, Control and Applied Mathematics. INRIA 1992. Lecture Notes in Computer Science, vol 653. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56320-2_57

Download citation

  • DOI: https://doi.org/10.1007/3-540-56320-2_57

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56320-4

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics