A Hybrid Placement Algorithm for Independent Tasks
Date Issued
2008
Date
2008
Author(s)
Chen, Hui-Lin
Abstract
This paper studies the placement strategies of independent tasks. We assign a large number of tasks with unknown execution time to multiple processors in chunks, and each chunk assignment is associated with a fixed communication overhead. The goal is to minimize the total execution time of all tasks. We propose a heuristic algorithm Hybrid that combines static and dynamic scheduling. We present a technique that determines the percentage of tasks that should be scheduled statically, based on statistic analysis. Then we apply a fixed chunk size based on the work of Kruskal and Weiss for the dynamic scheduling part. We conduct extensive experiments and the results are consistent with our theoretical prediction, and our algorithm outperforms other strategies suggested in the literature.
Subjects
Hybrid
Independent Task
Communication Overhead
Static-Workload Ratio
Dynamic Chunk Size
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922002-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):7221ffc4217fce6b2fb1e1e15d77a1e1