Towards automated design of multicomputer system for real-time applications (architecture, task division)
Girish Chandra Pathak · 1984
With the recent advances in VLSI technology it has now become feasible to design and implement computer systems consisting of a large number of processors. The suitability of such systems for specific applications depends primarily upon how well the system architecture corresponds to the structure of the algorithm(s) to be implemented. This work aims at the development of a software tool for designing an application-oriented or application-driven inhomogeneous multicomputer system (MCS) by evaluating the performance of the candidate architectures with respect to the algorithmic requirements of the application (task). The structure and the run-time ordering (data dependency of subtasks) of the applications are modeled by computation flow graphs (CFGs). The operating environments of the various MCSs have been represented by computing resource graphs (CRGs). CFG represents the degree of parallelism present in the task and the amount of computation and communication at each of its subtasks. Real-time applications in which continuous streams of input data are to be analyzed are considered in this work. An O(N('2)) time heuristic static allocation algorithm is presented to map the CFG to some CRG. The allocation algorithm provides a unique approach for reducing the interprocessor communication caused by the assignment of two communicating subtasks to different processors. This particular scheduling problem is shown to be NP-complete, and the heuristic algorithm presented in the thesis is shown to be bounded by a simple function of the number of levels in the CFG and the degree of inhomogeneity in the CRG. Performance of MCS for some application is evaluated in terms of speed-up, turn around time, resource utilization, and cardinality of the mapping, with the objective of evaluating an optimization function which could provide guidelines for selecting an architecture. The usefulness of the approach is demonstrated by comparing various MCSs for applications such as dynamic scene analysis problems, weather forecasting problems, fast fourier transforms, etc. The performance of the multicomputer systems for real-time applications is shown to be greatly influenced by its architecture. The software for the allocation algorithm and the simulation of MCS has been implemented on VAX 11/780 4.2 BSD UNIX using PASCAL and C. Finally, extensions of the project as a CAD tool and directions for the further research are outlined.