Scheduling DAGs on heterogeneous multiprocessor systems to minimize finish time

被引：0
|
作者：
Baskiyar, S [1 ]
SaiRanga, PC [1 ]
机构：
[1] Auburn Univ, Dept Comp Sci & Software Engn, Auburn, AL 36849 USA
来源：
PARALLEL AND DISTRIBUTED COMPUTING SYSTEMS, PROCEEDINGS | 2003年
关键词：
DAG scheduling; task graphs; heterogeneous computing; list scheduling; makespan;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A network of heterogeneous workstations is an efficient, cost-effective alternative to parallel supercomputers. We present a non-preemptive heuristic algorithm called. Heterogeneous Critical Node First (HCNF) that statically schedules directed a-cyclic task graphs on heterogeneous multiprocessor systems with an objective of minimizing the finish time. Using simulations on randomly generated graphs as well as real applications we show that HCNF outperforms HEFT significantly in schedule length ratio, speedup and efficiency.
引用
收藏
页码：30 / 35
页数：6
相关论文
共 50 条
  • [11] Scheduling in Multiprocessor Systems using Parallel PSO
    Singh, Sunil Kr
    Kumar, Rajesh
    2015 INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION & AUTOMATION (ICCCA), 2015, : 175 - 180
  • [12] On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems
    Marchetti-Spaccamela, Alberto
    Megow, Nicole
    Schloeter, Jens
    Skutella, Martin
    Stougie, Leen
    2020 IEEE 34TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM IPDPS 2020, 2020, : 1061 - 1070
  • [13] Scheduling real-time DAGs in heterogeneous clusters by combining imprecise computations and bin packing techniques for the exploitation of schedule holes
    Stavrinides, Georgios L.
    Karatza, Helen D.
    FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2012, 28 (07): : 977 - 988
  • [14] Multi-Criteria Decision-Making for Heterogeneous Multiprocessor Scheduling
    Saroja, S.
    Revathi, T.
    Auluck, Nitin
    INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY & DECISION MAKING, 2018, 17 (05) : 1399 - 1427
  • [15] List scheduling with duplication for heterogeneous computing systems
    Tang, Xiaoyong
    Li, Kenli
    Liao, Guiping
    Li, Renfa
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2010, 70 (04) : 323 - 329
  • [16] A hybrid optimization algorithm for energy-aware multi-objective task scheduling in heterogeneous multiprocessor systems
    Sahoo, Ronali Madhusmita
    Padhy, Sasmita Kumari
    EVOLUTIONARY INTELLIGENCE, 2024, 17 (5-6) : 3441 - 3467
  • [17] Scheduling arbitrary number of malleable tasks on multiprocessor systems
    Barketau, M. S.
    Kovalyov, M. Y.
    Weglarz, J.
    Machowiak, M.
    BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES, 2014, 62 (02) : 255 - 261
  • [18] Scheduling directed a-cyclic task graphs on heterogeneous network of workstations to minimize schedule length
    Baskiyar, S
    SaiRanga, PC
    2003 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING WORKSHOPS, PROCEEDINGS, 2003, : 97 - 103
  • [19] A dynamic matching and scheduling algorithm for heterogeneous computing systems
    Maheswaran, M
    Siegel, HJ
    SEVENTH HETEROGENEOUS COMPUTING WORKSHOP (HCW '98), 1998, : 57 - 69
  • [20] Static task scheduling with low complexity in the heterogeneous systems
    Chen, Hsin-An
    Lai, Guan-Joe
    WMSCI 2005: 9TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL 4, 2005, : 142 - 147
12345