Performance optimization using extended critical path analysis in multithreaded programs on multiprocessors

Efficient performance tuning of parallel programs is often hard. Optimizati on is often done when the program is written as a last effort to increase t he performance. With sequential programs each (executed) code segment will affect the completion time. In the case of a parallel program executed on a multiprocessor this is not always true, due to dependencies between the di fferent threads. Thus. certain code segments of the execution may not affec t the completion time of the program. Optimization of such code segments wi ll not increase the performance. In this paper we present an approach to op timize performance by finding the extended critical path of the multithread ed program. The extended critical path analysis is a generalization of the critical path analysis in the sense that it also deals with more threads th an processors. We have implemented the extended critical path analysis in a performance optimization tool. The tool allows the user to determine the e xtended critical path of a multithreaded application written ibr the Solari s operating system for any number of processors based on execution on a sin gle processor workstation. (C) 2001 Academic Press.