Lifting sequential graph algorithms for distributed-memory parallel computation

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