Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling

Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling

Abstract

Many DAG scheduling algorithms generate schedules that require prohibitively large number of processors. To address this problem, we propose a generic algorithm, SC, to minimize the processor requirement of any given valid schedule. SC preserves the schedule length of the original schedule and reduces processor count by merging processor schedules and removing redundant duplicate tasks. To the best of our knowledge, this is the first algorithm to address this highly unexplored aspect of DAG scheduling. On average, SC reduced the processor requirement 91, 82, and 72 percent for schedules generated by PLW, TCSD, and CPFD algorithms, respectively. SC algorithm has a low complexity compared to most duplication-based algorithms. Moreover, it decouples processor economization from schedule length minimization problem. To take advantage of these features of SC, we also propose a scheduling algorithm SDS, having the same time complexity as SC. Our experiments demonstrate that schedules generated by SDS are only 3 percent longer than CPFD, one of the best algorithms in that respect. SDS and SC together form a two-stage scheduling algorithm that produces schedules with high quality and low processor requirement, and has lower complexity than the comparable algorithms that produce similar high-quality results.

Algorithm / Technique used:

SC Algorithm.

Algorithm Description:

The goal of the SC algorithm is to reduce the processor requirement of a valid input schedule without degrading the schedule length.

Existing System:

They proposed a method to reduce the time complexity of non duplication-based algorithms without significantly affecting the quality of solutions. Nevertheless, we are not aware of any work that focuses on minimizing the

processor requirement of an existing schedule. Duplication- based algorithms especially suffer from large processor requirement due to large number of replicated tasks. There is also plenty of room for improvement for algorithms designed for scheduling on bounded number of processors as well.

Proposed System:

the proposed SC algorithm compacts the schedule on fewer number of processors without increasing the schedule length. Experiments on DAGs representing three applications as well as random DAGs verified that SC algorithm dramatically reduces the processor requirement of the schedules generated.

Hardware Requirements:

•         System                : Pentium IV 2.4 GHz.

•         Hard Disk            : 40 GB.

•         Floppy Drive      : 1.44 Mb.

•         Monitor               : 15 VGA Colour.

•         Mouse                 : Logitech.

•         Ram                     : 256 Mb.

Software Requirements:

•         Operating system         : - Windows XP Professional.

•         Front End             : - Visual Studio 2005.

•         Coding Language         : - Visual C# .Net.