Accession Number:

ADA238631

Title:

Optimal Iterative Task Scheduling for Parallel Simulations.

Descriptive Note:

Master's thesis,

Corporate Author:

AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING

Personal Author(s):

Report Date:

1991-03-01

Pagination or Media Count:

133.0

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 iPSC2 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.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE