التفاصيل البيبلوغرافية
| العنوان: |
Dynamic DAG Scheduling on Multiprocessor Systems: Reliability, Energy, and Makespan. |
| المؤلفون: |
Huang, Jing, Li, Renfa, Jiao, Xun, Jiang, Yu, Chang, Wanli |
| المصدر: |
IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems; Nov2020, Vol. 39 Issue 11, p3336-3347, 12p |
| مصطلحات موضوعية: |
PRODUCTION scheduling, RELIABILITY in engineering, MULTIPROCESSORS, DIRECTED acyclic graphs, SCHEDULING, REDUNDANCY in engineering |
| مصطلحات جغرافية: |
TRIPOLI (Libya) |
| مستخلص: |
Multiprocessor systems are increasingly deployed in real-time applications, where reliability, energy consumption, and makespan are often the main scheduling objectives. In this work, we investigate the dynamic scheduling of tasks modeled by directed acyclic graphs (DAGs), which is an NP-hard problem with all existing methods being heuristics. Our contributions have two steps: 1) assuming that the allocation of DAG nodes to processors is given, we propose optimal energy allocation (OEA) and search-based OEA (SOEA)—the first optimal methods that minimize the energy consumption while satisfying the reliability requirement—for homogeneous and heterogeneous systems, respectively and 2) we present a novel scheduling algorithm out-degree scheduling (ODS) that allocates the DAG nodes according to their out-degrees, and considering energy consumption, reliability, as well as dynamic finish time. ODS dominates the widely applied heterogeneous earliest finish time (HEFT) in makespan. Combining SOEA with ODS makes a complete solution to the problem of dynamic DAG scheduling on multiprocessor systems, and achieves generally better results compared to the existing approaches. Specifically, in most cases, we are better on all the three objectives, i.e., reliability, energy, as well as makespan, and in other cases, we are better on some of the objectives. [ABSTRACT FROM AUTHOR] |
|
Copyright of IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems is the property of IEEE and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
