[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Federated Scheduling of Sporadic DAGs on Unrelated Multiprocessors

Published: 22 September 2021 Publication History

Abstract

This paper presents a federated scheduling algorithm for implicit-deadline sporadic DAGs that execute on an unrelated heterogeneous multiprocessor platform. We consider a global work-conserving scheduler to execute a single DAG exclusively on a subset of the unrelated processors. Formal schedulability analysis to find the makespan of a DAG on its dedicated subset of the processors is proposed. The problem of determining each subset of dedicated unrelated processors for each DAG such that the DAG meets its deadline (i.e., designing the federated scheduling algorithm) is tackled by proposing a novel processors-to-task assignment heuristic using a new concept called processor value. Empirical evaluation is presented to show the effectiveness of our approach.

References

[1]
Björn Andersson and Gurulingesh Raravi. 2014. Real-time scheduling with resource sharing on heterogeneous multiprocessors. Real-time Systems 50, 2 (2014), 270–314.
[2]
Björn Andersson and Gurulingesh Raravi. 2016. Scheduling constrained-deadline parallel tasks on two-type heterogeneous multiprocessors. In Proceedings of the 24th International Conference on Real-time Networks and Systems. Association for Computing Machinery, Brest, France, 247–256.
[3]
ARM. 2011. big.LITTLE technology: The future of mobile. White paper, https://www.arm.com/files/pdf/big_LITTLE_Technology_the_Futue_of_Mobile.pdf.
[4]
ARM. 2017. The future of compute, re-imagined. https://www.arm.com/why-arm/technologies/dynamiq.
[5]
Eduard Ayguadé et al. 2010. Extending OpenMP to survive the heterogeneous multi-core era. International Journal of Parallel Programming 38, 5 (2010), 440–459.
[6]
Sanjoy Baruah. 2015. Federated scheduling of sporadic DAG task systems. In 2015 IEEE International Parallel and Distributed Processing Symposium. IEEE, IEEE, Hyderabad, India, 179–186.
[7]
Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. 2015. Multiprocessor Scheduling for Real-time Systems. Springer.
[8]
Sanjoy K. Baruah, Vincenzo Bonifaci, Renato Bruni, and Alberto Marchetti-Spaccamela. 2019. ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. Journal of Scheduling 22, 2 (2019), 195–209.
[9]
Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. 1990. Preemptively scheduling hard-real-time sporadic tasks on one processor. In [1990] Proceedings 11th Real-time Systems Symposium. IEEE, IEEE, Lake Buena Vista, Florida, USA, 182–190.
[10]
Andrea Bastoni, Björn Brandenburg, and James Anderson. 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. Proceedings of OSPERT (2010).
[11]
Michael A. Bender and Michael O. Rabin. 2000. Scheduling cilk multithreaded parallel programs on processors of different speeds. In Spaa.
[12]
Antoine Bertout, Joël Goossens, Emmanuel Grolleau, and Xavier Poczekajlo. 2020. Workload assignment for global real-time scheduling on unrelated multicore platforms. In Rtns.
[13]
Ashikahmed Bhuiyan, Zhishan Guo, Abusayeed Saifullah, Nan Guan, and Haoyi Xiong. 2018. Energy-efficient real-time scheduling of DAG tasks. Acm Tecs (2018).
[14]
Enrico Bini and Giorgio C. Buttazzo. 2004. Biasing effects in schedulability measures. In Ecrts. IEEE.
[15]
Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling multithreaded computations by work stealing. Jacm (1999).
[16]
Tracy D. Braun et al. 2001. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Jpdc (2001).
[17]
Peng Chen, Weichen Liu, Xu Jiang, Qingqiang He, and Nan Guan. 2019. Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems. Acm Tecs (2019).
[18]
Kallia Chronaki et al. 2015. Criticality-aware dynamic task scheduling for heterogeneous architectures. In Acm, Ics.
[19]
Kallia Chronaki, Miquel Moretó, Marc Casas, Alejandro Rico, Rosa M. Badia, Eduard Ayguadé, and Mateo Valero. 2019. On the maturity of parallel applications for asymmetric multi-core processors. J. Parallel and Distrib. Comput. (2019).
[20]
Benoît Dupont de Dinechin, Pierre Guironnet de Massas, Guillaume Lager, Clément Léger, Benjamin Orgogozo, Jérôme Reybert, and Thierry Strudel. 2013. A distributed run-time environment for the kalray mppa®-256 integrated manycore processor. Procedia Computer Science (2013).
[21]
Matthew DeVuyst, Ashish Venkat, and Dean M. Tullsen. 2012. Execution migration in a heterogeneous-ISA chip multiprocessor. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems.
[22]
Son Dinh, Christopher Gill, and Kunal Agrawal. 2020. Efficient deterministic federated scheduling for parallel real-time tasks. In Rtcsa. IEEE.
[23]
Alejandro Duran et al. 2002. Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp. In Icpp.
[24]
Hadi Esmaeilzadeh, Emily Blem, Renee St Amant, Karthikeyan Sankaralingam, and Doug Burger. 2011. Dark silicon and the end of multicore scaling. In Ieee Isca.
[25]
José Fonseca, Geoffrey Nelissen, and Vincent Nélis. 2019. Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling. Real-time Systems (2019).
[26]
Michael R. Garey and David S. Johnson. 1979. Computers and intractability. A Guide to the (1979).
[27]
Ronald L. Graham. 1966. Bounds for certain multiprocessing anomalies. Bell System Technical Journal (1966).
[28]
Ronald L. Graham. 1969. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics (1969).
[29]
Meiling Han, Nan Guan, Jinghao Sun, Qingqiang He, Qingxu Deng, and Weichen Liu. 2019. Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. Ieee Tpds (2019).
[30]
Meiling Han, Tianyu Zhang, Yuhan Lin, and Qingxu Deng. 2020. Federated scheduling for typed DAG tasks scheduling analysis on heterogeneous multi-cores. Journal of Systems Architecture (2020).
[31]
John L. Hennessy and David A. Patterson. 2017. Computer Architecture a Quantitative Approach, Sixth Edition, Chapter 7. Morgan Kaufmann.
[32]
John L. Hennessy and David A. Patterson. 2019. A new golden age for computer architecture. Commun. ACM (2019).
[33]
Xu Jiang, Nan Guan, Xiang Long, and Wang Yi. 2017. Semi-federated scheduling of parallel real-time tasks on multiprocessors. Ieee Rtss (2017).
[34]
Eugene L. Lawler and Jacques Labetoulle. 1978. On preemptive scheduling of unrelated parallel processors by linear programming. Jacm (1978).
[35]
Jing Li, Jian Jia Chen, Kunal Agrawal, Chenyang Lu, Chris Gill, and Abusayeed Saifullah. 2014. Analysis of federated and global scheduling for parallel real-time tasks. In Ieee Ecrts.
[36]
Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne Van Der Ster, and Andreas Wiese. 2015. Assigning sporadic tasks to unrelated machines. Mathematical Programming (2015).
[37]
Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio C. Buttazzo. 2015. Response-time analysis of conditional DAG tasks in multiprocessor systems. In Ecrts.
[38]
Alba Melo, Jesus Carretero, Per Stenstrom, Sanjay Ranka, and Eduard Ayguade. 2019. Trends on heterogeneous and innovative hardware and software systems.
[39]
NVIDIA. 2018. Nvidia jetson AGX xavier and the new era of autonomous machines. Nvidia presentation, http://info.nvidia.com/rs/156-OFN-742/images/Jetson_AGX_Xavier_New_Era_Autonomous_Machines.pdf.
[40]
Risat Pathan, Petros Voudouris, and Per Stenström. 2018. Scheduling parallel real-time recurrent tasks on multicore platforms. Ieee Tpds (2018).
[41]
Xuemei Peng, Meiling Han, and Qingxu Deng. 2019. Response time analysis of typed DAG tasks for G-FP scheduling. In International Symposium on Dependable Software Engineering: Theories, Tools, and Applications. Springer.
[42]
Gilbert C. Sih and Edward A. Lee. 1993. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. Ieee Tpds (1993).
[43]
Jinghao Sun, Jing Li, Zhishan Guo, An Zou, Xuan Zhang, Kunal Agrawal, and Sanjoy Baruah. 2020. Real-time scheduling upon a host-centric acceleration architecture with data offloading. In 2020 Real-time and Embedded Technology and Applications Symposium (RTAS). IEEE.
[44]
Haluk Topcuoglu, Salim Hariri, and Min-you Wu. 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. Ieee Tpds (2002).
[45]
Niklas Ueter, Georg von der Brüggen, Jian-Jia Chen, Jing Li, and Kunal Agrawal. 2018. Reservation-based federated scheduling for parallel real-time tasks. In Ieee Rtss.
[46]
Ashish Venkat and Dean M. Tullsen. 2014. Harnessing ISA diversity: Design of a heterogeneous-ISA chip multiprocessor. In 2014 ACM/IEEE 41st International Symposium on Computer Architecture (ISCA). IEEE.
[47]
Kecheng Yang and James H. Anderson. 2014. Optimal GEDF-based schedulers that allow intra-task parallelism on heterogeneous multiprocessors. In Ieee Estimedia.
[48]
Kecheng Yang, Ming Yang, and James H. Anderson. 2016. Reducing response-time bounds for dag-based task systems on heterogeneous multicore platforms. In Acm Rtns.
[49]
Houssam-Eddine Zahaf, Zahaf Houssam-Eddine, Nicola Capodieci, Roberto Cavicchioli, Giuseppe Lipari, and Marko Bertogna. 2020. The HPC-DAG task model for heterogeneous real-time systems. IEEE Trans. Comput. (2020).

Cited By

View all
  • (2023)The shape of a DAG: bounding the response time using long pathsReal-Time Systems10.1007/s11241-023-09397-y60:2(199-238)Online publication date: 25-May-2023

Index Terms

  1. Federated Scheduling of Sporadic DAGs on Unrelated Multiprocessors

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Embedded Computing Systems
    ACM Transactions on Embedded Computing Systems  Volume 20, Issue 5s
    Special Issue ESWEEK 2021, CASES 2021, CODES+ISSS 2021 and EMSOFT 2021
    October 2021
    1367 pages
    ISSN:1539-9087
    EISSN:1558-3465
    DOI:10.1145/3481713
    • Editor:
    • Tulika Mitra
    Issue’s Table of Contents
    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

    Publication History

    Published: 22 September 2021
    Accepted: 01 July 2021
    Revised: 01 June 2021
    Received: 01 April 2021
    Published in TECS Volume 20, Issue 5s

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Federated
    2. work-conserving
    3. multiprocessor
    4. scheduling
    5. heterogeneous
    6. unrelated
    7. sporadic
    8. DAGs

    Qualifiers

    • Research-article
    • Refereed

    Funding Sources

    • ERC

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)25
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 06 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)The shape of a DAG: bounding the response time using long pathsReal-Time Systems10.1007/s11241-023-09397-y60:2(199-238)Online publication date: 25-May-2023

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    HTML Format

    View this article in HTML Format.

    HTML Format

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media