Distributed Shared Abstractions (DSA) on Large-Scale Multiprocessors

Any parallel program has abstractions that are shared by the program's multiple processes, including data structures containing shared data, code implementing operations, type instances used for synchronization or communication, etc. Such shared abstractions can considerably affect parallel program performance, on distributed and on shared memory multiprocessors. As a result, their implementation must be efficient, and such efficiency should be achieved without unduly compromising program portability and maintainability.

The primary contribution of the DSA library is the encapsulation of shared abstractions as objects that may be internally distributed across different nodes of the parallel machine. Such distributed shared abstractions (DSA) are encapsulated so that program portability can be maintained across parallel architectures ranging from small-scale multiprocessors, to large-scale shared and distributed memory machines, to networks of computer workstations. This paper demonstrates an implementation of the DSA library on shared memory multiprocessors. The library is evaluated using a parallel implementation of a branch-and-bound algorithm for solving the Traveling Salesperson Problem (TSP). This evaluation is performed on a 32-node GP1000 BBN Butterfly multiprocessor, and such experimental results are compared to measurements attained on a 32-node Kendall Square Supercomputer.