mdh.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
Partitioned Scheduling of Real-Time Tasks on Multi-core Platforms
Mälardalen University, School of Innovation, Design and Engineering. (MRTC)
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: urn:nbn:se:mdh:diva-9595ISBN: 978-91-86135-74-4 (print)OAI: oai:DiVA.org:mdh-9595DiVA: diva2:319396
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: 2010-05-27Bibliographically approved
List of papers
1. Efficiently Migrating Real-Time Systems to Multi-Cores
Open this publication in new window or tab >>Efficiently Migrating Real-Time Systems to Multi-Cores
2009 (English)In: Proceedings of 14th IEEE International Conference on Emerging Techonologies and Factory (ETFA'09), 2009, 1205-1212 p.Conference paper, Published paper (Refereed)
Abstract [en]

Power consumption and thermal problems limit a further increase of speed in single-core processors. Multi-core architectures have therefore received significant interest. However, a shift to multi-core processors is a big challenge for developers of embedded real-time systems, especially considering existing “legacy” systems which have been developed with uniprocessor assumptions. These systems have been developed and maintained by many developers over many years, and cannot easily be replaced due to the huge development investments they represent. An important issue while migrating to multi-cores is how to distribute tasks among cores to increase performance offered by the multi-core platform. In this paper we propose a partitioning algorithm to efficiently distribute legacy system tasks along with newly developed ones onto different cores. The target of the partitioning is increasing system performance while ensuring correctness.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-8967 (URN)10.1109/ETFA.2009.5347136 (DOI)2-s2.0-77949885068 (Scopus ID)9781424427284 (ISBN)
Conference
2009 IEEE Conference on Emerging Technologies and Factory Automation, ETFA 2009; Mallorca; Spain; 22 September 2009 through 26 September 2009
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-03Bibliographically approved
2. A Flexible Tool for Evaluating Scheduling, Synchronization and Partitioning Algorithms on Multiprocessors
Open this publication in new window or tab >>A Flexible Tool for Evaluating Scheduling, Synchronization and Partitioning Algorithms on Multiprocessors
2010 (English)In: 2010 IEEE CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION (ETFA), 2010, 1-4 p.Conference paper, Published paper (Refereed)
Abstract [en]

Multi-core platforms seem to be the way towards increasing performance of processors. Single-chip multiprocessors (multi-cores) are today the dominating technology for desktop computing. As the multi-cores are becoming the defacto processors, the need for new scheduling and resource sharing protocols has arisen.There are two major types of scheduling under multiprocessor/multi-core platforms. Global scheduling, under which migration of tasks among processors is allowed, and partitioned scheduling under which tasks are allocated onto processors and task migration is not allowed. The partitioned scheduling protocols suffer from the problem of partitioning tasks among processors/cores, which is a bin-packing problem. Heuristic algorithms have been developed for partitioning a task set on multiprocessor platforms.However, taking such technology to an industrial setting, it needs to be evaluated such that appropriate scheduling, synchronization and partitioning algorithms are selected.

In this paper we present our work on a tool for investigation and evaluation of different approaches to scheduling, synchronization and partitioning on multi-core platforms. Our tool allows for comparison of different approaches with respect to a number of parameters such as number of schedulable systems and number of processors required for scheduling.The output of the tool includes a set of information and graphs to facilitate evaluation and comparison of different approaches.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-9593 (URN)10.1109/ETFA.2010.5641282 (DOI)000313616400158 ()2-s2.0-78650575245 (Scopus ID)978-1-4244-6850-8 (ISBN)
Conference
15th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA) Location: Univ Basque Country, Fac Engn, Bilbao, SPAIN Date: SEP 13-16, 2010
Available from: 2010-05-17 Created: 2010-05-17 Last updated: 2013-12-03Bibliographically approved
3. Blocking-Aware Partitioning for Multiprocessors
Open this publication in new window or tab >>Blocking-Aware Partitioning for Multiprocessors
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.

Publisher
10 p.
Identifiers
urn:nbn:se:mdh:diva-9591 (URN)
Available from: 2010-05-17 Created: 2010-05-17 Last updated: 2013-12-03Bibliographically approved
4. Partitioning Real-Time Systems on Multiprocessors with Shared Resources
Open this publication in new window or tab >>Partitioning Real-Time Systems on Multiprocessors with Shared Resources
2010 (English)In: Lecture Notes in Computer Science, vol. 6490, Springer, 2010, 253-269 p.Chapter in book (Refereed)
Abstract [en]

There are two main approaches to task scheduling on multiprocessor/multi-core platforms; 1) global scheduling, under which migration of tasks among processors is allowed, and 2) partitioned scheduling under which tasks are allocated onto processors and task migration is not allowed. Under global scheduling a higher utilization bound can be achieved, but in practice the overheads of migrating tasks is high. On the other hand under partitioned scheduling, besides simplicity and efficiency, existing scheduling and synchronization methods developed for uniprocessor platforms can more easily be extended to partitioned scheduling. However the partitioned scheduling protocols suffer from the problem of partitioning tasks among processors/cores which is a bin-packing problem. Therefore, several heuristic algorithms have been developed for partitioning a task set on multiprocessor platforms. However, these algorithms typically assume independent tasks while in practice real-time systems often contain tasks that share resources and hence may block each other.

In this paper we propose a blocking-aware partitioning algorithm which allocates a task~set onto processors in a way that the overall amount of blocking times of tasks are decreased. The algorithm reduces the total utilization which, in turn, has the potential to decrease the total number of required processors (cores). In this paper we evaluate our algorithm and compare it with an existing similar algorithm. The comparison criteria includes both number of schedulable systems as well as processor reduction performance.

Place, publisher, year, edition, pages
Springer, 2010
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6490
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-9592 (URN)10.1007/978-3-642-17653-1_20 (DOI)2-s2.0-78650872347 (Scopus ID)978-364217652-4 (ISBN)
Note

14th International Conference on Principles of Distributed Systems, OPODIS 2010; Tozeur;14 December 2010 through 17 December 2010

Available from: 2010-05-17 Created: 2010-05-17 Last updated: 2016-05-17Bibliographically approved

Open Access in DiVA

fulltext(220 kB)389 downloads
File information
File name FULLTEXT02.pdfFile size 220 kBChecksum SHA-512
d0c4e73e2c34577dd6d1cae94dac5744c5e8135f01685753603a05f88dd0bb3ee7934b661717242a03e6909354bfda2d9f0f2735b57073267559876cf667f2b2
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nemati, Farhang
By organisation
School of Innovation, Design and Engineering
Computer EngineeringSoftware Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 389 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

Total: 191 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