research-article

Task Assignment Algorithms for Heterogeneous Multiprocessors

Authors:

Gurulingesh Raravi,

Vincent NélisAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 13, Issue 5s

Article No.: 159, Pages 1 - 26

https://doi.org/10.1145/2660494

Published: 06 October 2014 Publication History

Abstract

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t) of distinct types of processors—such a platform is referred to as a t-type platform. We present two algorithms, LPG_IM and LPG_NM, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then: (i) LPG_IM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t-1/t times faster and (ii) LPG_NM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPG_IM, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPG_NM, has superior performance compared to state-of-the-art.

References

[1]

Jonah Alben. 2013. NVIDIA brings kepler, world's most advanced graphics architecture, to mobile devices. http://blogs.nvidia.com/blog/2013/07/24/kepler-to-mobile/.

[2]

AMD. 2013. AMD accelerated processing units. http://www.amd.com/fusion.

[3]

James Anderson and Anand Srinivasan. 2000. Early-release fair scheduling. In Proceedings of the 12^th Euromicro Conference on Real-time Systems (RTS'00). 35--43.

Digital Library

[4]

Apple. 2013. Apple A5X: Dual-core cpu and quad-core gpu. http://www.apple.com/ipad/specs/.

[5]

Sanjoy Baruah. 2004a. Partitioning real-time tasks among heterogeneous multiprocessors. In Proceedings of the 33^rd International Conference on Parallel Processing (ICPP'04). 467--474.

Digital Library

[6]

Sanjoy Baruah. 2004b. Task partitioning upon heterogeneous multiprocessor platforms. In Proceedings of the 10^th International Real-Time and Embedded Technology and Applications Symposium (RTAS'04). 536--543.

Digital Library

[7]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms 2^nd Ed. McGraw-Hill.

Digital Library

[8]

Jose Correa, Martin Skutella, and Jose Verschae. 2012. The power of preemption on unrelated machines and applications to scheduling orders. Math. Oper. Res. 37, 2, 379--398.

Digital Library

[9]

Michael Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress (IFIP'74). 807--813.

[10]

Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co.

Digital Library

[11]

W. A. Horn. 1974. Some simple scheduling algorithms. Naval Res. Logist. Quart. 21, 1, 177--185.

[12]

Ellis Horowitz and Sartaj Sahni. 1976. Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23, 2, 317--327.

Digital Library

[13]

IBM. 2013. CPLEX optimizer. http://www.ibm.com/developerworks/downloads/ws/ilogcplex/.

[14]

INTEL. 2013a. Bay trail: Multicore soc family for mobile devices. http://www.intel.com/newsroom/kits/idf/2013 fall/pdfs/bay trail factsheet.pdf.

[15]

INTEL. 2013b. Intel atom processor. http://ark.intel.com/products/family/75023.

[16]

INTEL. 2013c. The 4^th generation core i7 processors. http://ark.intel.com/products/family/75023.

[17]

Klaus Jansen and Lorant Porkolab. 1999. Improved approximation schemes for scheduling unrelated parallel machines. In Proceedings of the 31^st Annual ACM Symposium on Theory of Computing (STOC'99). 408--417.

Digital Library

[18]

David Johnson. 1973. Near-optimal bin packing algorithm. Ph.D. dissertation, Department of Mathematics, MIT.

[19]

Narendra Karmakar. 1984. A new polynomial-time algorithm for linear programming. Combinatorica 4, 4, 373--395.

Digital Library

[20]

Jan Lenstra, David Shmoys, and Eva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 3, 259--271.

Digital Library

[21]

Greg Levin, Shelby Funk, Caitlin Sadowskin, Ian Pye, and Scott Brandt. 2010. DP-fair: A simple model for understanding optimal multiprocessor scheduling. In Proceedings of the 22^nd Euromicro Conference on Real-time Systems (RTS'10). 3--13.

Digital Library

[22]

Chang L. Liu and James W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. J. ACM 20, 46--61.

Digital Library

[23]

David Luenberger and Yinyu Ye. 2008. Linear and Nonlinear Programming 3^rd Ed. International Series in Operations Research Management Science, Springer.

[24]

Geoffrey Nelissen, Vandy Berten, Vincent Nelis, Joel Goossens, and Milojevic Milojevic. 2012. U-EDF: An unfair but optimal multiprocessor scheduling algorithm for sporadic tasks. In Proceedings of the 24^th Euromicro Conference on Real-time Systems (RTS'12). 13--23.

Digital Library

[25]

Nvidia. 2013. Tegra 4: Mobility at the speed of life. http://www.nvidia.com/object/tegra.html.

[26]

Cynthia A. Phillips, Cliff Stein, Eric Torng, and Joel Wein. 1997. Optimal time-critical scheduling via resource augmentation. In Proceedings of the 29^th ACM Symposium on Theory of Computing (STOC'97). 140--149.

Digital Library

[27]

Qualcomm. 2013. Snapdragon processors: All-in-one mobile processor. http://www.qualcomm.com/snapdragon.

[28]

Gurulingesh Raravi, Bjorn Andersson, and Konstantinos Bletsas. 2013. Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors. Real-Time Syst. 49, 1, 29--72.

Digital Library

[29]

Gurulingesh Raravi, Bjorn Andersson, Konstantinos Bletsas, and Vincent Nelis. 2012. Task assignment algorithms for two-type heterogeneous multiprocessors. In Proceedings of the 24^th Euromicro Conference on Real-Time Systems (RTS'12). 34--43.

Digital Library

[30]

Gurulingesh Raravi and Vincent Nelis. 2012. A ptas for assigning sporadic tasks on two-type heterogeneous multiprocessors. In Proceedings of the 33^rd IEEE Real-Time Systems Symposium (RTSS'12). 117--126.

Digital Library

[31]

Samsung. 2013. Exynos 5 octa processor. www.samsung.com/exynos/.

[32]

Texas Instruments. 2013. OMAP applications processors. http://www.ti.com/omap.

[33]

Douglas B. West. 2000. Introduction to Graph Theory 2^nd Ed. Prentice Hall.

[34]

Andreas Wiese, Vincenzo Bonifaci, and Sanjoy Baruah. 2013. Partitioned edf scheduling on a few types of unrelated multiprocessors. Real-Time Syst. 49, 2, 219--238.

Digital Library

Cited By

Moulik SDevaraj RSarkar A(2018)COST: A Cluster-Oriented Scheduling Technique for Heterogeneous Multi-cores2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2018.00337(1951-1957)Online publication date: Oct-2018
https://doi.org/10.1109/SMC.2018.00337
Andersson BRaravi GPlantec ASinghoff FFaucou SPinho L(2016)Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous MultiprocessorsProceedings of the 24th International Conference on Real-Time Networks and Systems10.1145/2997465.2997482(247-256)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2997465.2997482
Chwa HSeo JLee JShin I(2015)Optimal Real-Time Scheduling on Two-Type Heterogeneous Multicore PlatformsProceedings of the 2015 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2015.19(119-129)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/RTSS.2015.19
Show More Cited By

Index Terms

Task Assignment Algorithms for Heterogeneous Multiprocessors

Recommendations

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes
Special Issue on Risk and Trust in Embedded Critical Systems, Special Issue on Real-Time, Embedded and Cyber-Physical Systems, Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES)

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor ...
Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors--such a platform is referred to as two-type platform . We present two low degree polynomial time-...
Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m _k ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 13, Issue 5s

Special Issue on Risk and Trust in Embedded Critical Systems, Special Issue on Real-Time, Embedded and Cyber-Physical Systems, Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES)

November 2014

501 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2660459

Editor:
Sandeep K. Shukla
Virginia Tech, USA

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 06 October 2014

Accepted: 01 May 2014

Received: 01 September 2013

Published in TECS Volume 13, Issue 5s

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

FCT and the EU ARTEMIS JU funding, within projects ARTEMIS/0003/2012 - JU
National Funds through FCT and by ERDF through COMPETE, within project(s) FCOMP-01-0124-FEDER-037281 (CISTER) and FCOMP-01-0124-FEDER-020447 (REGAIN)
North Portugal Regional Operational Programme (ON.2 O Novo Norte), under the NSRF, through the ERDF
Fundação para a Ciência e a Tecnologia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
236
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moulik SDevaraj RSarkar A(2018)COST: A Cluster-Oriented Scheduling Technique for Heterogeneous Multi-cores2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2018.00337(1951-1957)Online publication date: Oct-2018
https://doi.org/10.1109/SMC.2018.00337
Andersson BRaravi GPlantec ASinghoff FFaucou SPinho L(2016)Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous MultiprocessorsProceedings of the 24th International Conference on Real-Time Networks and Systems10.1145/2997465.2997482(247-256)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2997465.2997482
Chwa HSeo JLee JShin I(2015)Optimal Real-Time Scheduling on Two-Type Heterogeneous Multicore PlatformsProceedings of the 2015 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2015.19(119-129)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/RTSS.2015.19
Emeretlis ATheodoridis GAlefragis PVoros N(2015)Mapping DAGs on Heterogeneous Platforms Using Logic-Based Benders Decompostion2015 IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2015.98(119-124)Online publication date: Jul-2015
https://doi.org/10.1109/ISVLSI.2015.98

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents