Figure 2: Carnival visualization of Ocean
Our second example examines Ocean, an application in the Splash2 suite [16] that models large-scale ocean movements based on eddy and boundary currents. The original Splash2 code was ported to Treadmarks by colleagues at the Federal University in Rio de Janeiro without any changes to the data layout scheme. We executed the program on four processors with a grid size of 258 x 258, a grid resolution of 20000, and a time between relaxations of 28800. This execution took 151 seconds.
The global execution-time profiles show that, for Ocean, processors are idle for 60% of the overall execution time, while another 31% of the execution time is spent in the Treadmarks protocol (including garbage collection). Of the overall waiting time, about half is spent by processors waiting for page requests to be satisfied, with the other half spent by processors waiting at a synchronization point. Waiting time analysis identifies two parallel loops (relax_red_eveni_ploop - basic block 88 and relax_black_eveni_ploop - basic block 90) as the source of most of the page requests, and two barriers as the source of most synchronization overhead (Figure 2b). Furthermore, the analysis shows (Figure 2c) that most waiting time spent at the barriers is caused by the communication in the loops. From this analysis we conclude that communication is responsible (directly or indirectly) for approximately 75% of the overall execution time.
The communication profiles show that the two parallel loops account for 62% of the overall communication in the program. The profiles also show that the variable multi, a shared data structure containing the various grids used in the red-black Gauss-Seidel multigrid equation solver, is the only shared variable accessed in those portions of the code. In fact, accesses to multi are responsible for 75% of the overall communication cost of the application.
At this point in the analysis, we know that the communication costs of two parallel loops are a major cause of performance degradation and the only variable involved in this communication is multi. We use communication analysis to examine the access patterns for multi and discover that each page in this data structure has multiple producers and multiple consumers (MPMC). In the graph presented in Figure 2a, we can see that 86% of the communication costs can be attributed to a MPMC access pattern (the sum of percentages in columns 0 and 1), and the two loops are always writing on each page (i.e., the data written in basic block 88 is requested by basic block 90 and vice-versa). Furthermore, each page is always accessed by the same set of processors. An examination of the two loops reveals that the boundary conditions do not overlap among processors, and therefore we attribute the MPMC behavior to false sharing.
The Splash2 implementation of Ocean adopts a tiling allocation policy to improve the communication-to-computation ratio [16]. Under this allocation, less than two percent of all accesses are to boundary entries shared with another processor. However, using a tiling allocation of sub-matrices of 500K each, coupled with the 8K page size in Treadmarks, means that every access to multi under Treadmarks is a shared access. Since the boundaries of multi sub-matrices are not aligned on page boundaries, every write access to a page in this data structure generates an invalidation. Adopting the blocked allocation policy of the original Splash version of Ocean, and padding sub-arrays to align on 8K page boundaries, alleviates this problem, and improves the running time on four processors by a factor of 8.
It is not surprising that a program written for a shared-memory machine with relatively small units of coherency exhibits false sharing on a DSM system with large units of coherency, nor is it surprising that padding of data structures in such a program improves performance on a DSM system. The point of this example is to illustrate how waiting time analysis and communication analysis can be used to find the sources of excess communication in the source code, and suggest changes. In this particular example, our analysis lead us to focus on communication in the two loops, even though a global profile would have suggested a focus on synchronization at two barriers elsewhere in the program.