Optimal parallel conflict-free access to extended binary trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

Optimal parallel conflict-free access to extended binary trees

  • General Methodologies
  • Chapter
  • First Online:
Recent Issues in Pattern Analysis and Recognition

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

Abstract

In this paper the parallel conflict-free access to complete extended binary subtrees of complete binary trees is investigated. Thereby linear and also nonlinear memory module assignment functions S are considered. Furthermore, the problem of optimal parallel access to extended binary trees is solved.

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. Andrews, L.: On parallel isotropic conflict-free access to tree-like data structures. Diploma work, Humboldt-University Berlin, Dept. Mathematics, June 1989

    Google Scholar 

  2. Allen, J. R.: Anatomy of LISP. McGraw-Hill: New York 1978

    Google Scholar 

  3. Barnes, G. H. et. al.: The ILLIAC IV computer. IEEE Trans. Comput. C-17 (1968), pp. 746–757

    Google Scholar 

  4. Batcher, K. E.: STARAN parallel processor system hardware. Proc. Fall Joint Computer Conf. AFIPS Conf., AFIPS Press, 43, 1974, pp. 405–410

    Google Scholar 

  5. Budnik, P., and D. J. Kuck: The organization and use of parallel memories. IEEE Trans. Comput. C-20 (1971), pp. 1566–1569

    Google Scholar 

  6. Creutzburg, R.: Parallel optimal subtree access with recursively linear memory function. Proc. PARCELLA '86 Berlin, (Eds.: T. Legendi, D. Parkinson, R. Vollmar, G. Wolf) North-Holland: Amsterdam 1987, pp. 203–209

    Google Scholar 

  7. Creutzburg, R.: Parallel linear conflict-free subtree access. Proc. Internat. Workshop Parallel Algorithms Architectures (Suhl 1987), (Eds.: A. Albrecht, H. Jung, K. Mehlhorn) Lecture Notes in Computer Science 269 Springer: Berlin 1987, pp. 89–96

    Google Scholar 

  8. Creutzburg, R.: Parallel conflict-free access to extended binary trees. Preprint, Berlin 1988

    Google Scholar 

  9. Creutzburg, R.: Parallel conflict-free optimal access to complete extended q-ary trees. Proc. PARCELLA '88 (Eds. G. Wolf, T. Legendi, U. Schendel), Lecture Notes in Computer Science 342, Springer: Berlin 1989, pp.248–255.

    Google Scholar 

  10. Gőssel, M., and B. Rebel: Parallel memory with recursive address computation. Proc. Int. Conf. Parallel Computing '83 Berlin, (Ed.: M. Feilmeier) Elsevier: Amsterdam 1984, pp. 515–520

    Google Scholar 

  11. Gőssel, M., and B. Rebel: Data structures and parallel memories. Proc. PARCELLA '86 Berlin, (Eds.: T. Legendi, D. Parkinson, R. Vollmar, G. Wolf) North-Holland: Amsterdam 1987, pp. 49–60

    Google Scholar 

  12. Gőssel, M., and B. Rebel: Memories for parallel subtree access. Proc. Intern. Worksh. Parall. Algorithms Architect. (Suhl 1987), (Eds.: A. Albrecht, H. Jung, K. Mehlhorn) Lect. Notes Comp. Science 269, Springer: Berlin 1987, pp. 122–130

    Google Scholar 

  13. Gőssel, M., B. Rebel, and R. Creutzburg: Memory Architecture and Parallel Access (in German). Akademie-Verlag: Berlin 1989 (English translation in preparation)

    Google Scholar 

  14. Hockney, R. W., and C. R. Jesshope: Parallel Computers. Hilger: Bristol 1981

    Google Scholar 

  15. Horowitz, E., and S. Sahni: Fundamentals of Data Structures. Computer Science Press. Woodland Hills (Ca.) 1976

    Google Scholar 

  16. Knuth, D. E.: The Art of Computer Programming, Fundamental Algorithms. Addison-Wesley: Reading (MA) 1968

    Google Scholar 

  17. Kuck, D. J., and R. A. Stokes: The Burroughs scientific processor. IEEE Trans. Comput. C-31 (1982), pp. 363–376

    Google Scholar 

  18. Lawrie, D. H.: Access and alignment in an array processor. IEEE Trans. Comput. C-24 (1975), pp. 1145–1155

    Google Scholar 

  19. Lawrie, D. H., and Ch. R. Vora: The prime memory system for array access. IEEE Trans. Comput. C-31 (1982), pp. 435–442

    Google Scholar 

  20. Rebel, B., and M. Gőssel: Ein paralleler Speicher. Report ZKI der AdW, Berlin, Nov. 1982

    Google Scholar 

  21. Shapiro, H. D.: Theoretical limitations on the use of parallel memories. Univ. Illinois, Dept. Comp. Sci., Rep. No. 75–776 Dec. 1975

    Google Scholar 

  22. Shirakawa, H.: On a parallel memory to access trees. Memoirs of Research Institute of Science and Engineering of Ritsumeikan University Kyoto, Japan, No. 46 (1987), pp. 57–62 (same as unpublished report of 1984)

    Google Scholar 

  23. Wijshoff, H. A. G., and J. van Leeuwen: The structure of periodic storage schemes for parallel memories. IEEE Trans. Comput. C-34 (1985), pp. 501–505

    Google Scholar 

  24. Wijshoff, H. A. G.: Storing trees into parallel memories. Proc. 1985 Int. Conf. Parallel Computing, (Eds.: M. Feilmeier, J. Joubert, U. Schendel) Elsevier: Amsterdam 1986, pp. 253–261

    Google Scholar 

  25. Wijshoff, H. A. G.: Data organization in parallel computers. Ph.D. Diss. (Rijksuniv. Utrecht, Netherlands) 1987

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Central Institute of Cybernetics and Information Processes International Basic Laboratory for Image Processing and Computer Graphics, Academy of Sciences of the G.D.R., Kurstrasse 33, P.O.Box 1298, DDR - 1086, Berlin

    Reiner Creutzburg

  2. Department of Mathematics, Humboldt-University of Berlin, Unter den Linden 6, P.O.Box 1297, DDR - 1086, Berlin

    Lutz Andrews

Authors
  1. Reiner Creutzburg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lutz Andrews
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Virginio Cantoni Reiner Creutzburg Stefano Levialdi G. Wolf

Rights and permissions

Reprints and permissions

Copyright information

© 1989 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Creutzburg, R., Andrews, L. (1989). Optimal parallel conflict-free access to extended binary trees. In: Cantoni, V., Creutzburg, R., Levialdi, S., Wolf, G. (eds) Recent Issues in Pattern Analysis and Recognition. Lecture Notes in Computer Science, vol 399. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51815-0_55

Download citation

  • DOI: https://doi.org/10.1007/3-540-51815-0_55

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-51815-0

  • Online ISBN: 978-3-540-46815-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics