1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
<HTML>
<BODY>
<H2>Overview</H2>
Example that uses parallel_while to do parallel preorder traversal of a sparse graph.
<P>
Each vertex in the graph is called a "cell".
Each cell has a value.
The value is a matrix.
Some of the cells have operators
that compute the cell's value, using other cell's values as input.
A cell that uses the value of cell x is called a successor of x.
</P><P>
The algorithm works as follows.
<OL>
<LI> Compute the set of cells that have no inputs. This set is called <TT>root_set</TT>.
<LI> Each cell has an associated field <TT>ref_count</TT> that is an atomic integer.
Initialize <TT>ref_count</TT> to the number of inputs for the Cell.
<LI> Update each cell in <TT>root_set</TT>, by applying a <TT>parallel_while</TT> to a stream
that iterates over <TT>root_set</TT>
<LI> After updating a cell, for each of its successors
<OL>
<LI> Atomically decrement the successor's <TT>ref_count</TT>
<LI> If the count became zero, add the cell to the set of cells to be updated,
by calling <TT>parallel_while::add</TT>.
</OL>
</OL>
</P><P>
The times printed are for the traversal and update,
and do not include time for computing the root_set.
</P>
<B>NOTE: </B>It is important to understand that this example is unlikely to show speedup
if the cell values are changed to type "float". The reason is twofold.
<UL>
<LI> The smaller value type causes each Cell to be significantly smaller than a cache line,
which leads to false sharing conflicts.
<LI> The time to update the cells becomes very small, and consequently the overhead of
parallel_while swamps the useful work.
</UL>
<H2>Files</H2>
<DL>
<DT><A HREF="parallel_preorder.cpp">parallel_preorder.cpp</A>
<DD>Source code for example.
<DT><A HREF="Graph.cpp">Graph.cpp</A>
<DD>Source code for example.
<DT><A HREF="Graph.h">Graph.h</A>
<DD>Source code for example.
<DT><A HREF="Matrix.h">Matrix.h</A>
<DD>Source code for example.
<DT><A HREF="Makefile">Makefile</A>
<DD>Makefile for building example.
</DL>
<H2>Directories</H2>
<DL>
<DT><A HREF="vc7.1">vc7.1</A>
<DD>Contains Microsoft* Visual Studio* .NET 2003 workspace for building and running the example.
<DT><A HREF="vc8">vc8</A>
<DD>Contains Microsoft* Visual Studio* 2005 workspace for building and running the example.
<DT><A HREF="vc9">vc9</A>
<DD>Contains Microsoft* Visual Studio* 2008 workspace for building and running the example.
<DT><A HREF="xcode">xcode</A>
<DD>Contains Xcode* IDE workspace for building and running the example.
</DL>
<H2>To Build</H2>
General build directions can be found <A HREF=../../index.html#build>here</A>.
<H2>Usage</H2>
<DL>
<DT><TT>parallel_preorder [<I>M</I>[:<I>N</I>] [<I>Rounds</I> [<I>'pause'</I>]]]</TT>
<DD><I>M</I> and <I>N</I> are a range of numbers of threads to be used.
<DD><I>Rounds</I> is the number of rounds the example runs internally. Default value
is 50; reduce it to shorten example run time.
<DD>If 'pause' is specified, the application will wait for a user to hit return before it exits.
<DT>To run a short version of this example, e.g., for use with Intel® Threading Tools:
<DD>Build a <I>debug</I> version of the example
(see the <A HREF=../../index.html#build>build directions</A>).
<BR>Run it with the desired number of threads and smaller number of rounds, e.g., <TT>parallel_preorder 4 5</TT>.
</DL>
<HR>
<A HREF="../index.html">Up to parent directory</A>
<p></p>
Copyright © 2005-2008 Intel Corporation. All Rights Reserved.
<p></p>
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.
<p></p>
* Other names and brands may be claimed as the property of others.
</BODY>
</HTML>
|
