@article {14770, title = {Critical path profiling of message passing and shared-memory programs}, journal = {IEEE Transactions on Parallel and Distributed Systems}, volume = {9}, year = {1998}, month = {1998/10//}, pages = {1029 - 1040}, abstract = {We introduce a runtime, nontrace-based algorithm to compute the critical path profile of the execution of message passing and shared-memory parallel programs. Our algorithm permits starting or stopping the critical path computation during program execution and reporting intermediate values. We also present an online algorithm to compute a variant of critical path, called critical path zeroing, that measures the reduction in application execution time that improving a selected procedure will have. Finally, we present a brief case study to quantify the runtime overhead of our algorithm and to show that online critical path profiling can be used to find program bottlenecks}, keywords = {Computer Society, Concurrent computing, critical path computation, critical path profile, critical path zeroing, distributed processing, distributed shared memory systems, Instruments, Message passing, Monitoring, online algorithm, online critical path profiling, Parallel algorithms, program bottlenecks, Runtime, runtime nontrace-based algorithm, runtime overhead, shared-memory programs, system monitoring, Time measurement, Yarn}, isbn = {1045-9219}, doi = {10.1109/71.730530}, author = {Hollingsworth, Jeffrey K} }