Static Task Scheduling Algorithm with Minimum Distance for Multiprocessor System (STMD)

다국어 초록 (Multilingual Abstract)

Task scheduling in the multiprocessor environment is considered to be a NP-complete problem. It is also called a multiprocessor scheduling. Here, a parallel program is divided into a number of subtasks and it is mapped on the processors for concurrent execution. The objective of task scheduling is to reduce scheduling length of a given application program. Considering that task scheduling is represented by Directed Acyclic Grape (DAG). There are two types of task scheduling algorithms: static task scheduling and dynamic task scheduling algorithms. In this paper, we propose a new task scheduling algorithm based on minimum distance and an entry task duplicated on the processors. The minimum distance computes between an entry task and its successors. It includes, minimum distance of parent task, execution time and communication time Here , also considering a priority list (PL) attribute that contains tasks information of a given application program whose distance is minimum from an entry task. Finally, we will do comparative study of the proposed algorithm with Bounded Number of Processors (BNP) class of scheduling algorithms. It has done based on the following matrices: Scheduling Length, Speedup, Efficiency, Load Balancing and Normalized Scheduling Length (NSL). It showed proposed algorithm gives better result than BNP class of scheduling algorithms.

목차 (Table of Contents)

• Abstract
• Introduction
• Task scheduling problem
• BNP CLASS OF SCHEDULING ALGORITHMS
• Proposed Algorithm: STMD Algorithm
• COMPARISON METRICS
• PERFORMANCE EVALUATION
• CONCLUSION
• References