Soumen Chakrabarti, Etienne Deprit, Eun-Jin Im, Jeff Jones, Arvind Krishnamurthy, Chi-Po Wen and Katherine Yelick

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-95-879
July 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/CSD-95-879.pdf

Applications with dynamic data structures, unpredictable computational costs, and irregular data access patterns require substantial effort to parallelize. Much of their programming complexity comes from the implementation of distributed data structures. We describe a library of such data structures, Multipol, which includes parallel versions of classic data structures such as trees, sets, lists, graphs, and queues. The library is built on a portable runtime layer that provides basic communication, synchronization, and caching. The data structures address the classic trade-off between locality and load balance through a combination of replication, partitioning, and dynamic caching. To tolerate remote communication latencies, some of the operations are split into a separate initiation and completion phase, allowing for computation and communication overlap at the library interface level. This leads to a form of relaxed consistency semantics for the data types. In this paper we give an overview of Multipol, discuss the performance trade-offs and interface issues, and describe some of the applications that motivated its development.

BibTeX citation:

@techreport{Chakrabarti:CSD-95-879,
    Author = {Chakrabarti, Soumen and Deprit, Etienne and Im, Eun-Jin and Jones, Jeff and Krishnamurthy, Arvind and Wen, Chi-Po and Yelick, Katherine},
    Title = {Multipol: A Distributed Data Structure Library},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5483.html},
    Number = {UCB/CSD-95-879},
    Abstract = {Applications with dynamic data structures, unpredictable computational costs, and irregular data access patterns require substantial effort to parallelize.  Much of their programming complexity comes from the implementation of distributed data structures.  We describe a library of such data structures, Multipol, which includes parallel versions of classic data structures such as trees, sets, lists, graphs, and queues.  The library is built on a portable runtime layer that provides basic communication, synchronization, and caching.  The data structures address the classic trade-off between locality and load balance through a combination of replication, partitioning, and dynamic caching.  To tolerate remote communication latencies, some of the operations are split into a separate initiation and completion phase, allowing for computation and communication overlap at the library interface level.  This leads to a form of relaxed consistency semantics for the data types.  In this paper we give an overview of Multipol, discuss the performance trade-offs and interface issues, and describe some of the applications that motivated its development.}
}

EndNote citation:

%0 Report
%A Chakrabarti, Soumen
%A Deprit, Etienne
%A Im, Eun-Jin
%A Jones, Jeff
%A Krishnamurthy, Arvind
%A Wen, Chi-Po
%A Yelick, Katherine
%T Multipol: A Distributed Data Structure Library
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/CSD-95-879
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5483.html
%F Chakrabarti:CSD-95-879