Overview
This directory contains a simple example that solves the single source
shortest path problem. It is parameterized by N, a number of nodes,
and a start and end node in [0..N). A graph is generated with N nodes
and some random number of connections between those nodes. A parallel
algorithm based on A* is used to find the shortest path. This
algorithm varies from serial A* in that it needs to add nodes back to
the open set when the g estimate (shortest path from start to the
node) is improved, even if the node has already been "visited". This
is because nodes are added and removed from the open-set in parallel,
resulting in some less optimal paths being explored. The open-set is
implemented with the concurrent_priority_queue. Note that since we
re-visit nodes, the f estimate (on which the priority queue is sorted)
is not technically needed, so we could use this same parallel
algorithm with just a concurrent_queue. However, keeping the f
estimate and using concurrent_priority_queue results in much better
performance. Silent mode prints run time only, regular mode prints
shortest path length, and verbose mode prints out the shortest path.
The generated graph follows a pattern in which the closer two pairs of
node ids are together, the fewer hops there are in a typical path
between those nodes. So, for example, the path between 5 and 7 likely
has few hops whereas 14 to 78 has more and 0 to 9999 has even more,
etc.
Files
- shortpath.cpp
- Driver.
- Makefile
- Makefile for building example.
Directories
- msvs
- Contains Microsoft* Visual Studio* 2008 workspace for building and running the example with the Intel® C++ compiler.
- xcode
- Contains Mac OS* Xcode* workspace for building and running the example.
To Build
General build directions can be found here.
Usage
- shortpath -h
- Prints the help for command line options
- shortpath [#threads=value] [verbose] [silent] [N=value] [start=value] [end=value] [#threads]
- #threads is the number of threads to use; a range of the form low[:high] where low and optional high are non-negative integers, or 'auto' for the TBB default.
verbose print full path to screen
silent limits output to timing info; overrides verbose
N number of nodes in graph
start node to start path at
end node to end path at
- To run a short version of this example, e.g., for use with Intel® Parallel Inspector:
- Build a debug version of the example
(see the build directions).
Run it with a small problem size and the desired number of threads, e.g., shortpath 4 N=20 start=0 end=19.
Up to parent directory
Copyright © 2005-2011 Intel Corporation. All Rights Reserved.
Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are
registered trademarks or trademarks of Intel Corporation or its
subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.