Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An Optimal Lower Bound on the Maximal Speedup in Multiprocessors with Clusters
Responsible organisation
1995 (English)Conference paper, (Refereed) Published
Abstract [en]

We consider an ideal multiprocessor system with q processors and a centralized scheduler without overhead that select processes from one common pool, permitting dynamic relocation of processes. A parallel program P consisting of n processes is executed on this system and terminates when all processes are completed. Due to synchronizations, processes may be blocked while waiting for events in other processes. The parallel program is executed using some schedule of processes to processors, resulting in a speedup $sigma@. We then consider an ideal multiprocessor with k clusters containing u processors each. In this system processes may not be relocated between clusters. Finding a schedule which results in maximum speedup is NP-hard. Here, we present a formula for the optimal lower bound on the maximum speedup for program P, as a function of q, n, $sigma@, k and u. We also present a formula for the optimal lower bound when the number of processes (n) is unknown. Using these results we are able to decide if a certain schedule is close to optimal or if it is worth-while to look for other schedules. This is demonstrated by evaluating the speedup of a specific schedule of a particular program.

Place, publisher, year, edition, pages
Brisbane: IEEE; New York, NY, USA , 1995.
Keyword [en]
Multiprocessing systems, Parallel processing systems, Program processors, Optimization, Synchronization, Scheduling, Calculations, Telecommunication networks, Computational complexity
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-10254Local ID: oai:bth.se:forskinfo173B3E19CCC4E3FBC12568A3002CAB56ISBN: 0780320182 (print)OAI: oai:DiVA.org:bth-10254DiVA: diva2:838336
Conference
Proceedings 1st International Conference on Algorithms and Architectures for Parallel Processing
Note
This article is written under the Project "Optimal Combinatorial Bounds Comparing Multiprocessor Architectures"Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Lundberg, LarsLennerstad, Håkan
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Total: 19 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf