Graph Based Characterization of Distributed Applications

A critical task in the development and execution of distributed applications is to identify the potential degree of parallelism contained in the application. This information is necessary in the design of applications in order to pursue only a promising algorithmic idea for implementation, but also in the execution of existing applications for resource allocation and scheduling decisions. In this paper, we present analytical techniques to derive the potential degree of parallelism of distributed applications described by means of Timed Structural Parallelism Graphs (TSPGs). A TSPG allows a specification of a distributed application in terms of its components, the activation and dependence relations among the components, and histogram/interval based estimates on the execution times of components. Based on an analysis of paths through the TSPG (corresponding to paths in the execution) and by applying interval arithmetics, we are able to derive from the TSPG model a set of potential parallelism profiles. From these profiles further performance indices as the average degree of parallelism as well as hypothetical speedup can be derived. We focus on an evaluation of the analysis technique with respect to its computational complexity and validate the proposed approach by a comparison with results obtained from simulation.