Complexity Modeling Analysis and Prediction Tool

People associated with the project

Dr James E. Lumpp Jr

Arun P. Muthukumar

Shashi Mazumdar


Parallel computing has become the solution for achieving high performance in recent years. Faster solutions to grand challenge problems and high performance in scientific applications are possible with parallel computing. However parallel programs are not easy to develop because of the inherent complexity involved. It is very difficult to accurately quantify the factors on which the performance of the program depends.Hence tools and techniques are required for performance analysis and improvement of parallel programs.

Approaches to Modeling and Analysis

Numerous techniques have been developed for performance analysis,all of which are based on either measurement,analytical modeling or simulation. Measurement involves direct measurement of execution time of the program and then identifying the bottlenecks and correcting them. This is done until a satisfactory performance level is attained. This method though accurate is often not feasible. In simulation methods a model is developed in a specific simulation language and the execution is simulated on a machine with some specific characteristics. These models are sufficiently accurate but again this method is limited by the fact that large amounts of memory is required for simulating large problem sizes. The third and more commonly used method for performance analysis is analytic modeling. In this method the complexity of the program is analyzed and an expression for execution time in terms of N and P is obtained. This method is used to model programs before they are written or can also be used to test the scalability of an existing program.

The CAMP Tool Approach

The CAMP tool is based on the analytic modeling method and it analyses a given parallel program to arrive at an expression for the execution time in terms of N and P. The complexity of the program is obtained automatically by the tool and complexities that cannot be determined are requested from the programmer. Overall execution time is needed to complete the static model and this can be used to identify bottlenecks and also for scalability analysis. Trace based instrumentation is not required here and this simplifies the model development considerably with a small sacrifice in accuracy. The tool can also be used to determine the complexities of sequential programs.

Go Back