1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>An Overview of the Parallel Boost Graph Library</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="an-overview-of-the-parallel-boost-graph-library"> 12<h1 class="title">An Overview of the Parallel Boost Graph Library</h1> 13 14<!-- Copyright (C) 2004-2008 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<img align="right" alt="An example graph" class="align-right" src="../graph.png" style="width: 206px; height: 184px;" /> 19<p>The Parallel Boost Graph Library (Parallel BGL) is a C++ library for 20parallel, distributed computation on graphs. The Parallel BGL contains 21distributed graph data structures, distributed graph algorithms, 22abstractions over the communication medium (such as MPI), and 23supporting data structures. A graph (also called a <em>network</em>) consists 24of a set of <em>vertices</em> and a set of relationships between vertices, 25called <em>edges</em>. The edges may be <em>undirected</em>, meaning that the 26relationship between vertices is mutual, e.g., "X is related to Y", or 27they can be <em>directed</em>, meaning that the relationship goes only one 28way, e.g., "X is the child of Y". The following figure illustrates a 29typical directed graph, where <em>a-i</em> are the vertices and the arrows 30represent edges.</p> 31<img align="right" alt="A distributed graph" class="align-right" src="../distributed-graph.png" style="width: 229px; height: 199px;" /> 32<p>The Parallel BGL is primarily concerned with <em>distributed</em> 33graphs. Distributed graphs are conceptually graphs, but their storage 34is spread across multiple processors. The following figure 35demonstrates a distributed version of the graph above, where the graph 36has been divided among three processors (represented by the grey 37rectangles). Edges in the graph may be either local (with both 38endpoints stored on the same processor) or remote (the target of the 39edge is stored on a different processor).</p> 40<p>The Parallel BGL is a generic library. At its core are <em>generic</em> 41distributed graph algorithms, which can operate on any distributed 42graph data structure provided that data structure meets certain 43requirements. For instance, the algorithm may need to enumerate the 44set of vertices stored on the current processor, enumerate the set of 45outgoing edges from a particular vertex, and determine on which 46processor the target of each edge resides. The graph algorithms in the 47Parallel BGL are also generic with respect to the <em>properties</em> 48attached to edges and vertices in a graph; for instance, the weight of 49each edge can be stored as part of the graph or allocated in a 50completely separate data structure.</p> 51<p>The genericity available in the algorithms of the Parallel BGL allows 52them to be applied to existing graph data structures. However, most 53users will instead be writing new code that takes advantage of the 54Parallel BGL. The Parallel BGL provides distributed graph data 55structures that meet the requirements of the Parallel BGL 56algorithms. The primary data structure is the <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency 57list</a>, which allows storage and manipulation of a (distributed) 58graph. The vertices in the graph are divided among the various 59processors, and each of the edges outgoing from a vertex are stored on 60the processor that "owns" (stores) that vertex. The following figure 61illustrates the distributed adjacency list representation.</p> 62<div align="center" class="align-center"><img alt="A distributed adjacency list" class="align-center" src="../dist-adjlist.png" style="width: 446px; height: 154px;" /></div> 63<img align="right" alt="A distributed property map" class="align-right" src="../dist-pmap.png" style="width: 271px; height: 175px;" /> 64<p>The <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a> distributes the structure of a graph 65over multiple processors. While graph structure is in important part 66of many graph problems, there are typically other properties attached 67to the vertices and edges, such as edge weights or the position of 68vertices within a grid. These properties are stored in <em>property 69maps</em>, which associate a single piece of data with each edge or vertex 70in a graph. Distributed property maps extend this notion to 71distributed computing, where properties are stored on the same 72processor as the vertex or edge. The following figure illustrates the 73distribution of a property map storing colors (white, gray, black) for 74each vertex. In addition to the storage for each vertex, the 75processors store some "ghost cells" that cache values actually stored 76on other processors, represented by the dashed boxes.</p> 77<p>Tying together all of the distributed data structures of the Parallel 78BGL are its process groups and distributed graph algorithms. Process 79groups coordinate the interactions between multiple processes and 80distributed data structures by abstracting the communication 81mechanism. The algorithms are typically written using the SPMD model 82(Single Program, Multiple Data) and interact with both the distributed 83data structures and the process group itself. At various points in the 84algorithm's execution, all processes execute a synchronization point, 85which allows all of the distributed data structures to ensure an 86appropriate degree of consistency across processes. The following 87diagram illustrates the communication patterns within the the 88execution of a distributed algorithm in the Parallel BGL. In 89particular, the diagram illustrates the distributed data structures 90used in a distributed breadth-first search, from the top-left and 91proceeding clockwise:</p> 92<blockquote> 93<ul class="simple"> 94<li>a user-defined property map that tracks the distance from the 95source vertex to all other vertices,</li> 96<li>an automatically-generated property map that tracks the "color" 97of vertices in the (distributed) graph, to determine which 98vertices have been seen before,</li> 99<li>a distributed queue, which coordinates the breadth-first search 100and distributes new vertices to search, and</li> 101<li>a distributed graph, on which the breadth-first search is 102operating.</li> 103</ul> 104</blockquote> 105<div align="center" class="align-center"><img alt="Parallel Boost Graph Library architecture" class="align-center" src="../architecture.png" style="width: 485px; height: 410px;" /></div> 106<hr class="docutils" /> 107<p>Copyright (C) 2005 The Trustees of Indiana University.</p> 108<p>Authors: Douglas Gregor and Andrew Lumsdaine</p> 109<span class="target" id="process-groups"></span> 110</div> 111<div class="footer"> 112<hr class="footer" /> 113Generated on: 2009-05-31 00:22 UTC. 114Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. 115 116</div> 117</body> 118</html> 119
