Modeling and performance bounds for concurrent processing

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.<>