We investigate the use of a software distributed shared memory (DSM) layer to support irregular computations on distributed memory machines. Software DSM supports irregular computation through demand fetching of data in response to memory access faults. With the addition of a very limited form of compiler support, namely the identification of the section of the indirection array accessed by each processor, many of these on-demand page fetches can be aggregated into a single message, and prefetched prior to the access fault. We have measured the performance of this approach for two irregular applications, moldyn and nbf, using the TreadMarks DSM system on an 8-processor IBM SP2. We find that it has similar performance to the inspector-executor method supported by the CHAOS run-time library, while requiring much simpler compile-time support. For moldyn, it is up to 23~0 faster than CHAOS, depending on the input problem's characteristics; and for nbf, it is no worse than 14% slower. If we include the execution time of the inspector, the software DSM-based approach is always faster than CHAOS. The advantage of this approach increases as the frequency of changes to the indirection array increases. The disadvantage of this approach is the potentiaJ for false sharing overhead when the data set is small or has poor spatial locality, Inspector-executor methods have been proposed as a way to efficiently execute irregular computations on distributed memory machines [18]. A separate loop, the inspector-, precedes the actual computational loop (called the ezecutor). The inspector loop determines the data read and written by the individual processors executing the computational loop. This information is then used to compute a communication schedule, moving the data from the producers to the consumers at the beginning and/or end of each loop. Communication aggregation is used to reduce the number of messages exchanged. In order to further reduce over- head, an attempt is made to execute the inspector loop only once for a large number of iterations of the executor loop. It has been argued that part or all of the above procedure can be automated by a compiler [21]. The compiler analysis involved can, however, be quite complicated [1, 6, 20]. In this paper we propose an alternative approach. We use a software distributed shared memory (DSM) layer that provides a shared memory interface on top of the message layer [13]. In its simplest form, the DSM layer supports irregular computations by demand-driven fetching of data. Our approach involves, in addition, a simple compiler frontend that generates data access information, enabling the run-time system to efficiently precompute the set of pages that will be accessed by each processor during the next iteration. These pages are then requested, prior to that iteration, in a single message exchange with each processor from which data is needed. In other words, our approach extends the base software DSM layer by enabling it to aggregate the communication of data for irregular programs. The compiler support required for our approach is very simple: it suffices to determine the indirection array, and the part of the indirection array being accessed by each processor. This is usually a regular section [4]. In contrast, the inspector-executor approach requires complex analysis to determine whether the inspector loop can be hoisted out of the main loop [1, 20]. This paper presents our approach in detail. In order to gather experimental results, we use a modified version of TreadM arks [2] that supports prefetching and aggregation in the manner described above. Furthermore, we have augmented the Parascope parallel programming environment [12] to carry out the required compiler analysis. We present performance results for two irregular applications, moldyn and nbf. The results were obtained on an 8-processor IBM SP2 using base Tread Marks and Tread Marks with aggregation support. We compare these results to measurements of hand-coded inspector-executor versions of the same applications that use the CHAOS run-time library [7]. We find that TreadMarks augmented with compiler support for communication aggregation in irregular programs has similar performance to the inspector-executor method supported by the CHAOS run-time library. For moldyn, it is up to 23~o faster than CHAOS, depending on the input problem's characteristics; and for nbf, it is no worse than 14% slower. In addition, it is up to 38% faster than the base TreadMarks system. If we include the execution time of the inspector, our approach is always faster than CHAOS. The advantage of our approach incre.mes as the frequency of changes to the indirection array increases. Its disadvantage 48
Lu et al REF proposed compiler support for irregular applications on software distributed shared memory.
Compiler and software distributed shared memory support for irregular applications
PPOPP '97
Computer Science