Proper exploitation of the potential power of parallel computers requires an efficient solution to tasks-to processors scheduling problem. This paper discusses the scheduling problem of real-time graphics geometry operations to be executed on a multicomputer system. Assuming a run-time scheduling approach, a pre-scheduling operation will be defined as a cluster partitioning of processes with a view at minimising the parallel execution tune on a vinual architecture with unbounded number of processors. Such partitioning compensates for the finding or a mapping that minimises a cost function in a large configuration space, defined as p• configurations (where p is the number of processors and v is the number or processes). with a problem of dynamically mapping a reduced number of clusters onto processors. A weighted program dependence graph is used for representing the program for the scheduling problem and a heuristic clustering algorithm reduces the granularity of the program, preserving the whole embedded parallelism. For load balancing of the processors, dynamic mapping of clusters onto physical processors in the network is implemented as a receiver initiated distribution of computing work.
Real-time image synthesis, Multiple Instruction Stream, Multiple Data Stream Architecture, program dependence graph, cluster partitioning, dynamic mapping, scheduling, parallel overhead.
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).