Using parallel simulated annealing in the mapping problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

Using parallel simulated annealing in the mapping problem

  • Poster Session
  • Conference paper
  • First Online:
PARLE'94 Parallel Architectures and Languages Europe (PARLE 1994)

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

  • 127 Accesses

Abstract

This paper presents a parallel simulated annealing algorithm for solving the problem of mapping irregular parallel programs onto homogeneous processor arrays with regular topology. The algorithm constructs and uses joint transformations. These transformations guarantee a high degree of parallelism that is bounded below by ⌈¦N p /deg(G p +1⌋, where ¦N p ¦ is the number of task nodes in the mapped program graph G p and deg(G p ) is the maximal degree of a node in G p . The mapping algorithm provides good program mappings (in terms of program execution time and the number of processors used) in a reasonable number of steps.

This research is supported by the Ministry of Science and Technology of the Republic of Slovenia under grants P2-5092-106 and P2-5509-106.

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. N. Boissin and J.-L. Lutton. A parallel simulated annealing algorithm. Parallel Computing, 19(8):859–872, August 1993.

    MathSciNet  Google Scholar 

  2. I. Koren, B. Mendelson, I. Peled and G. M. Silberman. A data-driven VLSI array for arbitrary algorithms. IEEE Computer, 21(1):30–43, October 1988.

    Google Scholar 

  3. B. RobiŠilc, P. Kolbezen and J. šilc. Area optimization of dataflow-graph mappings. Parallel Computing, 18(3):297–311, March 1992.

    Article  Google Scholar 

  4. B. Robič and J. šilc. High-performance computing on a honeycomb architecture. Lecture Notes in Computer Science 734, pp. 1–13, Springer-Verlag, 1993.

    Google Scholar 

  5. B. Robič. Optimization of parallel algorithm mappings onto regular processor arrays. PhD Thesis, University of Ljubljana, 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory for Computer Architectures, Institute Jožef Stefan, Jamova 39, 61111, Ljubljana, Slovenia

    Borut Robič & Jurij Šilc

Authors
  1. Borut Robič
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jurij Šilc
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Costas Halatsis Dimitrios Maritsas George Philokyprou Sergios Theodoridis

Rights and permissions

Reprints and permissions

Copyright information

© 1994 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Robič, B., Šilc, J. (1994). Using parallel simulated annealing in the mapping problem. In: Halatsis, C., Maritsas, D., Philokyprou, G., Theodoridis, S. (eds) PARLE'94 Parallel Architectures and Languages Europe. PARLE 1994. Lecture Notes in Computer Science, vol 817. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58184-7_160

Download citation

  • DOI: https://doi.org/10.1007/3-540-58184-7_160

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

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

  • Online ISBN: 978-3-540-48477-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation