Presents a new data flow graph model for describing the real-time execution of iterative control and signal processing algorithms on multiprocessor data flow architectures. Identified by the acronym ATAMM, for Algorithm to Architecture Mapping Model, the model is important because it specifies criteria for a multiprocessor operating system to achieve predictable and reliable performance. Algorithm performance is characterized by execution time and iteration period. For a given data flow graph representation, the model facilitates calculation of greatest lower bounds for these performance measures. When sufficient processors are available, the system executes algorithms with minimum execution time and minimum iteration period, and the number of processors required is calculated. When only limited processors are available or when processors fail, performance is made to degrade gracefully and predictably. The user off-line is able to specify tradeoffs between increasing execution time or increasing iteration period. The approach to achieving predictable performance is to control the injection rate of input data and to modify the data flow graph precedence relations so that a processor is always available to execute an enabled graph node. An implementation of the ATAMM model in a four-processor architecture based on Westinghouse's VHSIC 1750A Instruction Set Processor is described.>

Consideration is given to the development of strategies for predictable performance in homogeneous multicomputer data-flow architectures operating in real-time. Algorithms are restricted to the class of large-grained, decision-free algorithms. The mapping of such algorithms onto the specified class of data-flow architectures is realized by a new marked graph model called ATAMM (algorithm to architecture mapping model). Algorithm performance and resource needs are determined for predictable periodic execution of algorithms, which is achieved by algorithm modification and input data injection control. Performance is gracefully degraded to adapt to decreasing numbers of resources. The realization of the ATAMM model on a VHSIC four processor testbed is described. A software design tool for prediction of performance and resource requirements is described and is used to evaluate the performance of a space surveillance algorithm.>

A novel graph-theoretic model for describing the relation between a decomposed algorithm and its execution in a multiprocessor environment is developed. Called ATAMM, the model consists of a set of Petri-net marked graphs that incorporates the general specifications of a data-flow architecture. The model is useful for representing decision-free algorithms having large-grained, computationally complex primitive operations. Performance measures of computing speed and throughput capacity are defined. The ATAMM model is used to develop analytically lower bounds for these parameters.>

Modification of the original algorithm by Allum1yields a computationally efficient algorithm. The computational improvement, nominally 20 percent, is significant when real-time digital signal processing applications are involved.