Models of Computational Systems-Cyclic to Acyclic Graph Transformations

Abstract

This paper discusses cyclic to acyclic transformations performed on graphs representing computational sequences. Such transformations are critical to the development of models of computations and computer systems for performance prediction. The nature of cycles in computer programs for parallel processors is discussed. Transformations are then developed which replace cyclic graph structures by mean-value equivalent acyclic structures. The acyclic equivalents retain the noncyclic part of the structure in the original graph by evaluating a multiplicative factor associated with the mean time required for each vertex execution in the original graph. Bias introduced in the acyclic approximation is explored.