Static Analysis of Barrier Synchronization in Explicitly Parallel Programs.pdfVIP

Static Analysis of Barrier Synchronization in Explicitly Parallel Programs Tor E. Jeremiassen and Susan J. Eggers Department of Computer Science and Engineering FR-35, University of Washington, Seattle, Washington 98195 Abstract: Many coarse-grained, explicitly parallel programs execute in phases delimited by barriers to preserve sets of cross pro cess data dep endencies. One of the ma jor obstacles to optimizing these programs is the necessity to conservatively assume that any two statements in the program may execute concurrently. Consequently, compilers fail to take advantage of opp ortunities to apply optimizing transformations, particularly those designed to improve data lo cality, b oth within and across the phases of the program. We present a simple and ecient compile time algorithm that uses the presence of barriers to p erform non-concurrency analysis on coarse-grain, explicitly parallel programs. It works by dividing the program into a set of phases and computing the control ow b etween them. Each phase consists of one or more sequences of program statements that are delimited by barrier synchronization events and can execute concurrently. We show that the algorithm p erforms p erfectly on all but one of our b enchmarks. Keyword Co des: D.1.3; I.1.3 Keywords: Concurrent Programming; Langua ges and Systems 1 Intro duction On cache coherent shared memory multipro cessors, much of the \unnecessary commu- nication, i.e., that which could b e eliminated with lo cality enhancing optimizations, is coherency overhead caused by false sharing [22, 10 ]. False sharing o ccurs when multiple pro cessors access dierent words in the same cache blo ck. Although they do not actually share data, they incur its costs, b ecause coherency op erations are cache