Optimal Iterative Task Scheduling for Parallel Simulations.
Abstract
The ultimate purpose of this research is to reduce the time needed for execution of parallel computer simulations. In particular, the impact of task assignment strategies is determined for parallel VHDL circuit simulations. The classical scheduling problem, which assigns n precedence-constrained tasks to m processors is NP-complete in all but the simplest cases. The problem of assigning simulation tasks is further complicated by the iterative nature of computer simulations: each task is required to execute multiple times as the simulation executes. This investigation develops a polynomial-time algorithm (the level strategy) which provides optimal assignment for iterative systems with specific constraints. A mathematical foundation for iterative task systems is proved. In particular, it is shown that restricted cases of iterative systems achieve minimal latency,(time between successive iterations of a given task), when the level strategy is used for task assignment. To verify the theoretical results, various task scheduling strategies are compared using VHDL logic- circuit simulations on the iPSC/2 Hypercube computer. Tests are run with mappings based on the level strategy, the classical optimal assignment, a greedy technique for assignment, and an unbalanced assignment. The best results of these experiments, in terms of speedup, occur consistently in cases where the level strategy is used.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1991
- Accession Number
- ADA238631
Entities
People
- Joann M. Sartor
Organizations
- Air Force Institute of Technology