Critical path profiling of message passing and shared-memory programs

TitleCritical path profiling of message passing and shared-memory programs
Publication TypeJournal Articles
Year of Publication1998
AuthorsHollingsworth J
JournalIEEE Transactions on Parallel and Distributed Systems
Pagination1029 - 1040
Date Published1998/10//
ISBN Number1045-9219
KeywordsComputer 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

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