Thomas L. Rodeheffer

Compiling Ordinary Programs for Executions on an Asynchronous Multiprocessor Degree Type: Ph.D. in Computer Science
Advisor(s): Peter Hibbard
Graduated: May 1985

Abstract:

Although the asynchronous multiprocessor can perform several simultaneous sequences of actions, its separate processors do not execute in unison, but require explicit operations to achieve coordination. An optimizing compiler for such a machine must weigh the cost of these synchronizing operations against the benefits which might accrue from the additional parallelism. This dissertation investigates techniques for scheduling the constituent operations of arithmetic expressions and basic blocks onto the separate processors of an asynchronous multiprocessor, paying particular attention to the problems caused by interprocessor synchronization. Based on an execution thread model for the target machine, two efficient heuristic methods for scheduling expressions are compared by simulation against optimality and the better method, "assume parallel", is recommended.