We consider the problem of partitioning applications that operateon a regular grid but have irregular boundaries for a cache-coherentmultiprocessor. Domain decomposition techniques such as RSB havecommonly been used to reduce interprocessor communication in messagepassing multiprocessors. We apply these partitioning algorithms oncache-coherent multiprocessors to reduce cache-coherency traffic. Wefind that the actual cache-coherency traffic is approximately double theestimated true coherency traffic, primarily due to false-sharing and theconsequent false coherency traffic. We devise two techniques thateliminate false sharing traffic in partitions produced using the commondomain decomposition algorithms. In our compensation algorithm, wemodify the partition produced by the domain decomposition to ensure thatall the nodes on a cache line are assigned to the same processor. In ourcoalescing algorithm, nodes belonging to the same cache line arecoalesced into a single node and the weights on nodes and arcs adjustedto represent the overall computation and communication costs of thecoalesced nodes. This coalesced graph is partitioned using a domaindecomposition algorithm and then the coalesced nodes in the partitionare expanded. Our experimental results using an Indian Ocean circulationapplication on the KSR1 multiprocessor demonstrate that compensationreduces coherency traffic by as much as 55% and execution time by up to18% and that graph coalescing reduces coherency traffic by up to 74%
展开▼
