boost_1_45_0/libs/graph_parallel/doc/html/overview.html - nest-learning-thermostat/5.0/boost - Git at Google

 <?xml version="1.0" encoding="utf-8" ?>
 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
 <head>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
 <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
 <title>An Overview of the Parallel Boost Graph Library</title>
 <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
 </head>
 <body>
 <div class="document" id="an-overview-of-the-parallel-boost-graph-library">
 <h1 class="title">An Overview of the Parallel Boost Graph Library</h1>

 <!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
 Use, modification and distribution is subject to the Boost Software
 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 http://www.boost.org/LICENSE_1_0.txt) -->
 <img align="right" alt="An example graph" class="align-right" src="../graph.png" style="width: 206px; height: 184px;" />
 <p>The Parallel Boost Graph Library (Parallel BGL) is a C++ library for
 parallel, distributed computation on graphs. The Parallel BGL contains
 distributed graph data structures, distributed graph algorithms,
 abstractions over the communication medium (such as MPI), and
 supporting data structures. A graph (also called a <em>network</em>) consists
 of a set of <em>vertices</em> and a set of relationships between vertices,
 called <em>edges</em>. The edges may be <em>undirected</em>, meaning that the
 relationship between vertices is mutual, e.g., &quot;X is related to Y&quot;, or
 they can be <em>directed</em>, meaning that the relationship goes only one
 way, e.g., &quot;X is the child of Y&quot;. The following figure illustrates a
 typical directed graph, where <em>a-i</em> are the vertices and the arrows
 represent edges.</p>
 <img align="right" alt="A distributed graph" class="align-right" src="../distributed-graph.png" style="width: 229px; height: 199px;" />
 <p>The Parallel BGL is primarily concerned with <em>distributed</em>
 graphs. Distributed graphs are conceptually graphs, but their storage
 is spread across multiple processors. The following figure
 demonstrates a distributed version of the graph above, where the graph
 has been divided among three processors (represented by the grey
 rectangles). Edges in the graph may be either local (with both
 endpoints stored on the same processor) or remote (the target of the
 edge is stored on a different processor).</p>
 <p>The Parallel BGL is a generic library. At its core are <em>generic</em>
 distributed graph algorithms, which can operate on any distributed
 graph data structure provided that data structure meets certain
 requirements. For instance, the algorithm may need to enumerate the
 set of vertices stored on the current processor, enumerate the set of
 outgoing edges from a particular vertex, and determine on which
 processor the target of each edge resides. The graph algorithms in the
 Parallel BGL are also generic with respect to the <em>properties</em>
 attached to edges and vertices in a graph; for instance, the weight of
 each edge can be stored as part of the graph or allocated in a
 completely separate data structure.</p>
 <p>The genericity available in the algorithms of the Parallel BGL allows
 them to be applied to existing graph data structures. However, most
 users will instead be writing new code that takes advantage of the
 Parallel BGL. The Parallel BGL provides distributed graph data
 structures that meet the requirements of the Parallel BGL
 algorithms. The primary data structure is the <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency
 list</a>, which allows storage and manipulation of a (distributed)
 graph. The vertices in the graph are divided among the various
 processors, and each of the edges outgoing from a vertex are stored on
 the processor that &quot;owns&quot; (stores) that vertex. The following figure
 illustrates the distributed adjacency list representation.</p>
 <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>
 <img align="right" alt="A distributed property map" class="align-right" src="../dist-pmap.png" style="width: 271px; height: 175px;" />
 <p>The <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a> distributes the structure of a graph
 over multiple processors. While graph structure is in important part
 of many graph problems, there are typically other properties attached
 to the vertices and edges, such as edge weights or the position of
 vertices within a grid. These properties are stored in <em>property
 maps</em>, which associate a single piece of data with each edge or vertex
 in a graph. Distributed property maps extend this notion to
 distributed computing, where properties are stored on the same
 processor as the vertex or edge. The following figure illustrates the
 distribution of a property map storing colors (white, gray, black) for
 each vertex. In addition to the storage for each vertex, the
 processors store some &quot;ghost cells&quot; that cache values actually stored
 on other processors, represented by the dashed boxes.</p>
 <p>Tying together all of the distributed data structures of the Parallel
 BGL are its process groups and distributed graph algorithms. Process
 groups coordinate the interactions between multiple processes and
 distributed data structures by abstracting the communication
 mechanism. The algorithms are typically written using the SPMD model
 (Single Program, Multiple Data) and interact with both the distributed
 data structures and the process group itself. At various points in the
 algorithm's execution, all processes execute a synchronization point,
 which allows all of the distributed data structures to ensure an
 appropriate degree of consistency across processes. The following
 diagram illustrates the communication patterns within the the
 execution of a distributed algorithm in the Parallel BGL. In
 particular, the diagram illustrates the distributed data structures
 used in a distributed breadth-first search, from the top-left and
 proceeding clockwise:</p>
 <blockquote>
 <ul class="simple">
 <li>a user-defined property map that tracks the distance from the
 source vertex to all other vertices,</li>
 <li>an automatically-generated property map that tracks the &quot;color&quot;
 of vertices in the (distributed) graph, to determine which
 vertices have been seen before,</li>
 <li>a distributed queue, which coordinates the breadth-first search
 and distributes new vertices to search, and</li>
 <li>a distributed graph, on which the breadth-first search is
 operating.</li>
 </ul>
 </blockquote>
 <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>
 <hr class="docutils" />
 <p>Copyright (C) 2005 The Trustees of Indiana University.</p>
 <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
 <span class="target" id="process-groups"></span>
 </div>
 <div class="footer">
 <hr class="footer" />
 Generated on: 2009-05-31 00:22 UTC.
 Generated 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.

 </div>
 </body>
 </html>
	<?xml version="1.0" encoding="utf-8" ?>
	<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
	<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
	<title>An Overview of the Parallel Boost Graph Library</title>
	<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
	</head>
	<body>
	<div class="document" id="an-overview-of-the-parallel-boost-graph-library">
	<h1 class="title">An Overview of the Parallel Boost Graph Library</h1>

	<!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
	Use, modification and distribution is subject to the Boost Software
	License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	http://www.boost.org/LICENSE_1_0.txt) -->
	<img align="right" alt="An example graph" class="align-right" src="../graph.png" style="width: 206px; height: 184px;" />
	<p>The Parallel Boost Graph Library (Parallel BGL) is a C++ library for
	parallel, distributed computation on graphs. The Parallel BGL contains
	distributed graph data structures, distributed graph algorithms,
	abstractions over the communication medium (such as MPI), and
	supporting data structures. A graph (also called a <em>network</em>) consists
	of a set of <em>vertices</em> and a set of relationships between vertices,
	called <em>edges</em>. The edges may be <em>undirected</em>, meaning that the
	relationship between vertices is mutual, e.g., "X is related to Y", or
	they can be <em>directed</em>, meaning that the relationship goes only one
	way, e.g., "X is the child of Y". The following figure illustrates a
	typical directed graph, where <em>a-i</em> are the vertices and the arrows
	represent edges.</p>
	<img align="right" alt="A distributed graph" class="align-right" src="../distributed-graph.png" style="width: 229px; height: 199px;" />
	<p>The Parallel BGL is primarily concerned with <em>distributed</em>
	graphs. Distributed graphs are conceptually graphs, but their storage
	is spread across multiple processors. The following figure
	demonstrates a distributed version of the graph above, where the graph
	has been divided among three processors (represented by the grey
	rectangles). Edges in the graph may be either local (with both
	endpoints stored on the same processor) or remote (the target of the
	edge is stored on a different processor).</p>
	<p>The Parallel BGL is a generic library. At its core are <em>generic</em>
	distributed graph algorithms, which can operate on any distributed
	graph data structure provided that data structure meets certain
	requirements. For instance, the algorithm may need to enumerate the
	set of vertices stored on the current processor, enumerate the set of
	outgoing edges from a particular vertex, and determine on which
	processor the target of each edge resides. The graph algorithms in the
	Parallel BGL are also generic with respect to the <em>properties</em>
	attached to edges and vertices in a graph; for instance, the weight of
	each edge can be stored as part of the graph or allocated in a
	completely separate data structure.</p>
	<p>The genericity available in the algorithms of the Parallel BGL allows
	them to be applied to existing graph data structures. However, most
	users will instead be writing new code that takes advantage of the
	Parallel BGL. The Parallel BGL provides distributed graph data
	structures that meet the requirements of the Parallel BGL
	algorithms. The primary data structure is the <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency
	list</a>, which allows storage and manipulation of a (distributed)
	graph. The vertices in the graph are divided among the various
	processors, and each of the edges outgoing from a vertex are stored on
	the processor that "owns" (stores) that vertex. The following figure
	illustrates the distributed adjacency list representation.</p>
	<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>
	<img align="right" alt="A distributed property map" class="align-right" src="../dist-pmap.png" style="width: 271px; height: 175px;" />
	<p>The <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a> distributes the structure of a graph
	over multiple processors. While graph structure is in important part
	of many graph problems, there are typically other properties attached
	to the vertices and edges, such as edge weights or the position of
	vertices within a grid. These properties are stored in <em>property
	maps</em>, which associate a single piece of data with each edge or vertex
	in a graph. Distributed property maps extend this notion to
	distributed computing, where properties are stored on the same
	processor as the vertex or edge. The following figure illustrates the
	distribution of a property map storing colors (white, gray, black) for
	each vertex. In addition to the storage for each vertex, the
	processors store some "ghost cells" that cache values actually stored
	on other processors, represented by the dashed boxes.</p>
	<p>Tying together all of the distributed data structures of the Parallel
	BGL are its process groups and distributed graph algorithms. Process
	groups coordinate the interactions between multiple processes and
	distributed data structures by abstracting the communication
	mechanism. The algorithms are typically written using the SPMD model
	(Single Program, Multiple Data) and interact with both the distributed
	data structures and the process group itself. At various points in the
	algorithm's execution, all processes execute a synchronization point,
	which allows all of the distributed data structures to ensure an
	appropriate degree of consistency across processes. The following
	diagram illustrates the communication patterns within the the
	execution of a distributed algorithm in the Parallel BGL. In
	particular, the diagram illustrates the distributed data structures
	used in a distributed breadth-first search, from the top-left and
	proceeding clockwise:</p>
	<blockquote>
	<ul class="simple">
	<li>a user-defined property map that tracks the distance from the
	source vertex to all other vertices,</li>
	<li>an automatically-generated property map that tracks the "color"
	of vertices in the (distributed) graph, to determine which
	vertices have been seen before,</li>
	<li>a distributed queue, which coordinates the breadth-first search
	and distributes new vertices to search, and</li>
	<li>a distributed graph, on which the breadth-first search is
	operating.</li>
	</ul>
	</blockquote>
	<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>
	<hr class="docutils" />
	<p>Copyright (C) 2005 The Trustees of Indiana University.</p>
	<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
	<span class="target" id="process-groups"></span>
	</div>
	<div class="footer">
	<hr class="footer" />
	Generated on: 2009-05-31 00:22 UTC.
	Generated 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.

	</div>
	</body>
	</html>