Efficient support for two-dimensional data distributions in distributed shared memory systems

Despite their clear advantage in scalability, two-dimensional data distributions are not efficiently supported by current software distributed shared memory (SDSM) systems. This is because sharing between nodes occurs on both columns and rows. Sharing in two dimensions is not a good match for SDSM systems, because either a row- or column-major data layout of pages leads to (1) severe thrashing if a strong memory consistency is used, or (2) exchange of unnecessary data between nodes, if a relaxed memory consistency is used. We examine two alternatives for efficiently supporting two-dimensional data distributions in SDSM systems. We develop two new page consistency protocols for this purpose. One protocol, called Explicit-2D, requires that the user or compiler explicitly identify truly shared elements within a page; the other, called Implicit-2D, infers such elements implicitly. Knowledge of truly shared elements allows the SDSM, at synchronization points, to send only truly shared data, which reduces diff sizes. As the problem size or the number of nodes grows, programs written using a two-dimensional distributions with our new protocols are superior to those using a one-dimensional one. The difference in our tests is as much as 12% for Red-Black SOR, and increases with the problem size and number of nodes.