检索结果-内蒙古大学图书馆

An efficient list scheduling algorithm with task duplication for scientific big data workflow in heterogeneous computing environments

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2021年第5期33卷

作者： Ahmad, Wakar Alam, Bashir Jamia Millia Islamia Dept Comp Engn New Delhi India

A high-performance heterogeneous computing environment provides computing resources for efficient computation of scientific Big Data workflow applications. A Big Data workflow application comprises thousands of interdependent tasks with precedence constraints. Basically, the performance of heterogeneous computing systems mainly depends on the workflow scheduling algorithms. These workflow scheduling algorithms are considered an NP-complete problem. In this article, a List scheduling with task duplication (LSTD) algorithm is proposed that efficiently minimizes the makespan of workflow applications. The LSTD introduces task duplication strategy in the list scheduling algorithm without increasing the overall time complexity. The overall functionality of LSTD mainly consists of three phases. In the first phase, it calculates the rank of the tasks for deciding the scheduling order. The next step is responsible for duplicating the entry task on the processor only if it increases the overall efficiency and avoids processor overloading. Finally, in the last step, the processor is assigned to the tasks based on the popular insertion-based policy that attempts to insert the task among two earlier assigned tasks on a given processor in earliest idle time. In order to verify the usefulness of the proposed algorithm, several existing well-known algorithms, such as Heterogeneous Earliest Finish Time (HEFT), Critical Path on a Processor (CPOP), and Predict Earliest Finish Time (PEFT) are considered for comparison. A non-duplication version of LSTD named List scheduling without task duplication algorithm is also considered for performance evaluation. The experimental analysis based on scientific Big Data workflows (CyberShake, Montage, and LIGO) proves that LSTD significantly surpasses all considered scheduling heuristics concerning schedule length ratio, the percentage of best results, and average running time metrics.

关键词： big data workflows heterogeneous computing systems list scheduling task duplication scheduling

来源：评论

学校读者我要写书评

暂无评论

Limited duplication-Based List scheduling Algorithm for Heterogeneous Computing System

引用

MICROMACHINES 2022年第7期13卷 1067页

作者： Guo, Hong Zhou, Jiayin Gu, Haonan Wuhan Univ Sci & Technol Coll Comp Sci & Technol Hubei Prov Key Lab Intelligent Informat Proc & Re Wuhan 430065 Peoples R China Wuhan Qingchuan Univ Coll Comp Sci Wuhan 430204 Peoples R China

Efficient scheduling algorithms have been a leading research topic for heterogeneous computing systems. Although duplication-based scheduling algorithms can significantly reduce the total completion time, they are generally accompanied by an exorbitant time complexity. In this paper, we propose a new task duplication-based heuristic scheduling algorithm, LDLS, that can reduce the total completion time and maintains a low time complexity. The scheduling procedure of LDLS is composed of three main phases: In the beginning phase, the maximum number of duplications per level and per task is calculated to prevent excessive duplications from blocking regular tasks. In the next phase, the optimistic cost table (OCT) and ranking of tasks are calculated with reference to PEFT. In the final phase, scheduling is conducted based on the ranking, and the duplication of each task is dynamically determined, enabling the duplicated tasks to effectively reduce the start execution time of its successor tasks. Experiments of algorithms on randomly generated graphs and real-world applications indicate that both the scheduling length and the number of better case occurrences of LDLS are better than others.

关键词： heterogeneous computing systems list scheduling task duplication scheduling limited duplication random graph generator

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：