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
Multiprocessor Scheduling of Synchronous Data Flow Graphs using Local Search Algorithms
KTH, School of Information and Communication Technology (ICT).
KTH, School of Information and Communication Technology (ICT).
2014 (English)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Design space exploration (DSE) is the process of exploring design alternatives before implementing real-time multiprocessor systems. One part of DSE is scheduling of the applications the system is developed for and to evaluate the performance to ensure that the real-time requirements are satisfied. Many real-time systems today use multiprocessors and finding the optimal schedule for an application on a multiprocessor system is known to be an NP-hard problem. Such an optimization problem can be time-consuming which justifies the use of heuristics. This thesis presents an approach for scheduling applications onto multiprocessors using local search algorithms. The applications are represented by SDF-graphs and the assumed platform has homogeneous processors without constraints regarding communication delays, memory consumption or buffer sizes. The goal of this thesis project was to investigate if heuristic search algorithms could find sufficiently good solutions in a reasonable amount of time. Experimental results show that local search algorithms have potential of contributing to DSE by finding high-performance schedules with reduced search time compared to algorithms trying to find the optimal scheduling solution.

Place, publisher, year, edition, pages
2014. , 68 p.
Series
TRITA-ICT-EX, 2014:62
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-177144OAI: oai:DiVA.org:kth-177144DiVA: diva2:871572
Examiners
Available from: 2015-12-08 Created: 2015-11-16 Last updated: 2017-08-03Bibliographically approved

Open Access in DiVA

fulltext(836 kB)8 downloads
File information
File name FULLTEXT01.pdfFile size 836 kBChecksum SHA-512
7077bf5ab47fd395baa7671045eb9908adfb6eeeb30ff7673e1d79288c6aec74292ee626960dd2441a7f03171d69046694da897f1ea5f28f99c51473a4706f31
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 86 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