OBJECT-ORIENTED PROGRAMMING, SYSTEMS, LANGUAGES and APPLICATIONS
 
 
Program
 


Program (2mb PDF)

Explore
  Invited Speakers
  Onward!
  Panels
  Workshops
Discover
  Research Papers
  Student Research Comp.
  Posters
  Doctoral Symposium
  Educators' Symposium
  Wiki Symposium
  Dynamic Lang. Symp.
Understand
  Tutorials
  Essays
  Practitioner Reports
  Demonstrations
Create
  DesignFest
  Lightning Talks
  FlashBoF
  Instant Arts School Exp.
 
Other Events
 
Resort Map (364kb PDF)
 
Resort Map (JPG)

 

 
Basket
 

view, help

"Lifting Sequential Graph Algorithms for Distributed-Memory Parallel Computation"

 

 
Page
 

Printer-friendly

 
 
  > Research Papers > Concurrency || Concurrency

 : Thursday

Lifting Sequential Graph Algorithms for Distributed-Memory Parallel Computation

San Diego Room
Thursday, 11:00, 30 minutes

 


 
7·8·9·10·11·12·13·14·15·16·17·18·19·20·21

Douglas Gregor, Indiana University
Andrew Lumsdaine, Indiana University

This paper describes the process used to extend the Boost Graph Library (BGL) for parallel operation with distributed memory. The BGL consists of a rich set of generic graph algorithms and supporting data structures, but it was not originally designed with parallelism in mind. In this paper, we revisit the abstractions comprising the BGL in the context of distributed-memory parallelism, lifting away the implicit requirements of sequential execution and a single shared address space. We illustrate our approach by describing the process as applied to one of the core algorithms in the BGL, breadth-first search. The result is a generic algorithm that is unchanged from the sequential algorithm, requiring only the introduction of external (distributed) data structures for parallel execution. More importantly, the generic implementation retains its interface and semantics, such that other distributed algorithms can be built upon it, just as algorithms are layered in the sequential case. By characterizing these extensions as well as the extension process, we develop general principles and patterns for using (and reusing) generic, object-oriented parallel software libraries. We demonstrate that the resulting algorithm implementations are both efficient and scalable with performance results for several algorithms.

 
.