Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Schedulin
#1

Abstract :-
Many DAG scheduling algorithms generate schedules that require prohibitively large number of processors. To addressthis problem, we propose a generic algorithm, SC, to minimize the processor requirement of any given valid schedule. SC preserves theschedule 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. Onaverage, 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 (O jN j3 ) compared to most duplication-based algorithms. Moreover, it decouplesprocessor economization from schedule length minimization problem. To take advantage of these features of SC, we also propose ascheduling algorithm SDS, having the same time complexity as SC. Our experiments demonstrate that schedules generated by SDS areonly 3 percent longer than CPFD (O jN j4 ), 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 comparablealgorithms that produce similar high-quality results.
Index Terms Scheduling and task partitioning, task duplication, algorithms, multiprocessor systems
Reply



Forum Jump:


Users browsing this thread:
1 Guest(s)

Powered By MyBB, © 2002-2024 iAndrew & Melroy van den Berg.