https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Blocking-Aware Partitioning for Multiprocessors
Mälardalen University, School of Innovation, Design and Engineering. (MRTC)
Mälardalen University, School of Innovation, Design and Engineering. (MRTC)ORCID iD: 0000-0001-6132-7945
Mälardalen University, School of Innovation, Design and Engineering. (MRTC)ORCID iD: 0000-0002-1687-930X
2010 (English)Report (Other academic)
Abstract [en]

In the multi-core and multiprocessor domain there are two scheduling approaches, global and partitioned scheduling. Under global scheduling each task can execute on any processor while under partitioned scheduling tasks are allocated to processors and migration of tasks among processors is not allowed. Under global scheduling the higher utilization bound can be achieved, but in practice the overheads of migrating tasks is high. On the other hand, besides simplicity and efficiency of partitioned scheduling protocols, existing scheduling and synchronization methods developed for uniprocessor platforms can more easily be extended to partitioned scheduling. This also simplifies migration of existing systems to multi-cores. An important issue related to partitioned scheduling is how to distribute tasks among processors/cores to increase performance offered by the platform. However, existing methods mostly assume independent tasks while in practice a typical real-time system contains tasks that share resources and they may block each other. In this paper we propose a blocking-aware partitioning algorithm to distribute tasks onto different processors. The proposed algorithm allocates a task set onto processors in a way that blocking times of tasks are decreased. This reduces the total utilization which has the potential to decrease the total number of needed processors/cores.

Place, publisher, year, edition, pages
2010. , p. 10
Identifiers
URN: urn:nbn:se:mdh:diva-9591OAI: oai:DiVA.org:mdh-9591DiVA, id: diva2:319361
Available from: 2010-05-17 Created: 2010-05-17 Last updated: 2013-12-03Bibliographically approved
In thesis
1. Partitioned Scheduling of Real-Time Tasks on Multi-core Platforms
Open this publication in new window or tab >>Partitioned Scheduling of Real-Time Tasks on Multi-core Platforms
2010 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

In recent years multiprocessor architectures have become mainstream, and multi-core processors are found in products ranging from small portable cell phones to large computer servers. In parallel, research on real-time systems has mainly focused on traditional single-core processors. Hence, in order for real-time systems to fully leverage on the extra capacity offered by new multi-core processors, new design techniques, scheduling approaches, and real-time analysis methods have to be developed.

In the multi-core and multiprocessor domain there are mainly two scheduling approaches, global and partitioned scheduling. Under global scheduling each task can execute on any processor at any time while under partitioned scheduling tasks are statically allocated to processors and migration of tasks among processors is not allowed. Besides simplicity and efficiency of partitioned scheduling protocols, existing scheduling and synchronization methods developed for single-core processor platforms can more easily be extended to partitioned scheduling. This also simplifies migration of existing systems to multi-cores. An important issue related to partitioned scheduling is distribution of tasks among processors which is a bin-packing problem.

In this thesis we propose a partitioning framework for distributing tasks on the processors of multi-core platforms. Depending on the type of performance we desire to achieve, the framework may distribute a task set differently, e.g., in an application in which tasks process huge amounts of data the goal of the framework may be to decrease cache misses.Furthermore, we propose a blocking-aware partitioning heuristic algorithm to distribute tasks onto the processors of a multi-core architecture. The objective of the proposed algorithm is to decrease blocking overhead of tasks which reduces the total utilization and has the potential to reduce the number of required processors.Finally, we have implemented a tool to facilitate evaluation and comparison of different multiprocessor scheduling and synchronization approaches, as well as different partitioning heuristics. We have applied the tool in the evaluation of several partitioning heuristic algorithms, and the tool is flexible to which any new scheduling or synchronization protocol as well as any new partitioning heuristic can easily be added.

Place, publisher, year, edition, pages
Mälardalen University: Västerås, 2010
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 119
National Category
Computer Engineering Software Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-9595 (URN)978-91-86135-74-4 (ISBN)
Presentation
2010-05-28, Gamma, Högskoleplan 1, Västerås, 10:15 (English)
Opponent
Supervisors
Available from: 2010-05-18 Created: 2010-05-17 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

fulltext(260 kB)462 downloads
File information
File name FULLTEXT01.pdfFile size 260 kBChecksum SHA-512
f2861cd5f01e8acc0df933ad8ce88859bb7a09b7b30a4096f5dfd1367002dca6b75f700a2bc55294ff861d9b9aee7e2a50d0da24c1f68be8b87c3a5d436a49fb
Type fulltextMimetype application/pdf

Authority records

Nolte, ThomasBehnam, Moris

Search in DiVA

By author/editor
Nemati, FarhangNolte, ThomasBehnam, Moris
By organisation
School of Innovation, Design and Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 462 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: 221 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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