Static mapping heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in heterogeneous environments Braun, Tracy D. ; Siegel, Howard Jay ; Maciejewski, Anthony A. "This research was supported in part by the DARPA/ITO Quorum Program under GSA subcontract number GS09K99BH0250 and a Purdue University Dean of Engineering Donnan Scholarship." Heterogeneous computing (HC) environments composed of interconnected machines with varied computational capabilities are well suited to meet the computational demands of large, diverse groups of tasks. The problem of mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environment has been shown, in general, to be NP-complete. Therefore, the development of heuristic techniques to find near-optimal solutions is required. In the HC environment investigated, tasks had deadlines, priorities, multiple versions, and may be composed of communicating subtasks. The best static (off-line) techniques from some previous studies were adapted and applied to this mapping problem: a genetic algorithm (GA), a GENITOR-style algorithm, and a greedy Min-min technique. Simulation studies compared the performance of these heuristics in several overloaded scenarios, i.e., not all tasks executed. The performance measure used was a sum of weighted priorities of tasks that completed before their deadline, adjusted based on the version of the task used. It is shown that for the cases studied here, the GENITOR technique found the best results, but the faster Min-min approach also performed very well. Colorado State University. Libraries 2002 text ; image application/pdf ECEaam00092.pdf FACFECEN100092ARTI eng c2002 IEEE
Static mapping heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in heterogeneous environments
Braun, Tracy D. ; Siegel, Howard Jay ; Maciejewski, Anthony A.
"This research was supported in part by the DARPA/ITO Quorum Program under GSA subcontract number GS09K99BH0250 and a Purdue University Dean of Engineering Donnan Scholarship."
Heterogeneous computing (HC) environments composed of interconnected machines with varied computational capabilities are well suited to meet the computational demands of large, diverse groups of tasks. The problem of mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environment has been shown, in general, to be NP-complete. Therefore, the development of heuristic techniques to find near-optimal solutions is required. In the HC environment investigated, tasks had deadlines, priorities, multiple versions, and may be composed of communicating subtasks. The best static (off-line) techniques from some previous studies were adapted and applied to this mapping problem: a genetic algorithm (GA), a GENITOR-style algorithm, and a greedy Min-min technique. Simulation studies compared the performance of these heuristics in several overloaded scenarios, i.e., not all tasks executed. The performance measure used was a sum of weighted priorities of tasks that completed before their deadline, adjusted based on the version of the task used. It is shown that for the cases studied here, the GENITOR technique found the best results, but the faster Min-min approach also performed very well.
Colorado State University. Libraries
2002
text ; image
application/pdf
ECEaam00092.pdf
FACFECEN100092ARTI
eng
c2002 IEEE