PREDICTION OF PERFORMANCE AND PROCESSOR REQUIREMENTS IN REAL-TIME DATA-FLOW ARCHITECTURES

The purpose of this paper is to present a new data how graph model for describing the real-time execution of iterative control and signal pr ocessing algorithms on multiprocessor data flow architectures. Identif ied by the acronym ATAMM, for Algorithm to Architecture Mapping Model, the model is important because it specifies criteria for a multiproce ssor operating system to achieve predictable and reliable performance. Algorithm performance is characterized by execution time and iteratio n period. For a given data flow graph representation, the model facili tates calculation of greatest lower bounds for these performance measu res. When sufficient processors are available, the system executes alg orithms with minimum execution time and minimum iteration period, and the number of processors required is calculated, When only limited pro cessors are available or when processors fail, performance is made to degrade gracefully and predictably. The user off-line is able to speci fy tradeoffs between increasing execution time or increasing iteration period. The approach to achieving predictable performance is to contr ol the injection rate of input data and to modify the data flow graph precedence relations so that a processor is always available to execut e an enabled graph node. An implementation of the ATAMM model in a fou r-processor architecture based on Westinghouse's VHSIC 1750A Instructi on Set Processor is described, and the performance of a real-time spac e surveillance algorithm on this system is investigated.