Processor Allocation and Reallocation in a Macro-Dataflow Multiprocessor System.

The problem of processor allocation in a macro-dataflow multiprocessor system is studied. Being a hierarchal hybrid system, processor scheduling is performed at two different levels, namely, the processor-cluster level and the processor level. A program to be executed on a macro-dataflow machine is represented by a macro-dataflow graph. Unlike the traditional dataflow program graph (in which every node is a scalar operation) the nodes of a macro-dataflow graph are high-level program tasks, each of which consists of a set of instructions. The computational model of these macro-nodes follows the dataflow principle. We define dataflow allocation as the problem of assigning these program tasks to the processor-clusters in order to minimize the total execution time of the program. Similarly, instructions within a macro-node must be allocated to processors of the processor-cluster to which the macro-node is assigned. Since instructions at the processor level are executed according to the control-flow model of computation, we define the control-flow allocation as the problem of mapping these instructions onto the processors in such a way as to minimize the total execution time. We have developed a hierarchal mapping scheme. A fast heuristic is used for the dataflow allocation. The algorithm takes into consideration realistic system parameters such as the interprocessor communication time, non-uniform task processing times, finite system resources, and common control constructs. Simulation results indicate that the proposed algorithm provides a good and efficient solution for minimizing the total execution time, and compares favorably against the other existing algorithms. We also provide an algorithm to derive the optimal schedule for the control-flow allocation problem. The algorithm is based on modelling the control-flow allocation environment with a Markov decision model. Optimal allocation of a set of instructions with non-uniform processing times to a set of non-homogeneous processors is accomplished by applying a policy improvement algorithm to the model. Based on the optimal schedule, the total execution time of the entire program task can easily be determined and can be used as an input parameter to the dataflow allocation. The problem of reallocating a processing element's workload when it fails is also studied. An analytical model has been developed to represent the queueing behavior of the processing element to which the workload of the failed unit is sent. For the class of reallocation algorithms considered, closed-form expressions with respect to different performance measures are derived.PhDElectrical engineeringUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/160533/1/8512428.pd