]> https://gitweb.dealii.org/ - dealii-svn.git/blob
f129b75d53cc6aeaa1a55e6452553668d753bdd0
[dealii-svn.git] /
1 /*
2     Copyright 2005-2009 Intel Corporation.  All Rights Reserved.
3
4     This file is part of Threading Building Blocks.
5
6     Threading Building Blocks is free software; you can redistribute it
7     and/or modify it under the terms of the GNU General Public License
8     version 2 as published by the Free Software Foundation.
9
10     Threading Building Blocks is distributed in the hope that it will be
11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13     GNU General Public License for more details.
14
15     You should have received a copy of the GNU General Public License
16     along with Threading Building Blocks; if not, write to the Free Software
17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
19     As a special exception, you may use this file as part of a free software
20     library without restriction.  Specifically, if other files instantiate
21     templates or use macros or inline functions from this file, or you compile
22     this file and link it with other files to produce an executable, this
23     file does not by itself cause the resulting executable to be covered by
24     the GNU General Public License.  This exception does not however
25     invalidate any other reasons why the executable file might be covered by
26     the GNU General Public License.
27 */
28
29 /* Example program that shows how to use parallel_while to do parallel preorder 
30    traversal of a directed acyclic graph. */
31
32 #include "tbb/parallel_while.h"
33 #include "tbb/atomic.h"
34 #include <vector>
35 #include <algorithm>
36 #include <cstring>
37 #include <cstdio>
38 #include "Graph.h"
39
40 using namespace std;
41
42 //! Number of trials. Can be changed from command line
43 int ntrial = 50;
44
45 class Body {
46     tbb::parallel_while<Body>& my_while; 
47 public:
48     Body( tbb::parallel_while<Body>& w ) : my_while(w) {};
49
50     //------------------------------------------------------------------------
51     // Following signatures required by parallel_while
52     //------------------------------------------------------------------------
53     typedef Cell* argument_type;
54     void operator()( Cell* c ) const {
55         c->update();
56         // Restore ref_count in preparation for subsequent traversal.
57         c->ref_count = ArityOfOp[c->op];
58         for( size_t k=0; k<c->successor.size(); ++k ) {
59             Cell* successor = c->successor[k];
60             if( 0 == --(successor->ref_count) ) {
61                 my_while.add( successor );
62             }
63         }
64     }
65 };   
66
67 class Stream {
68     size_t k;
69     const vector<Cell*>& my_roots;
70 public:
71     Stream( const vector<Cell*>& root_set ) : my_roots(root_set), k(0) {}
72     bool pop_if_present( Cell*& item ) {
73         bool result = k<my_roots.size();
74         if( result ) 
75             item = my_roots[k++];
76         return result;
77     }
78 };    
79
80 void ParallelPreorderTraversal( const vector<Cell*>& root_set ) {
81     tbb::parallel_while<Body> w;
82     Stream s(root_set);
83     w.run(s,Body(w));
84 }
85
86 //------------------------------------------------------------------------
87 // Test driver
88 //------------------------------------------------------------------------
89
90 #include <cctype>
91 #include "tbb/task_scheduler_init.h"
92 #include "tbb/tick_count.h"
93
94 //! A closed range of int.
95 struct IntRange {
96     int low;
97     int high;
98     void set_from_string( const char* s );
99     IntRange( int low_, int high_ ) : low(low_), high(high_) {}
100 };
101
102 void IntRange::set_from_string( const char* s ) {
103     char* end;
104     high = low = strtol(s,&end,0);
105     switch( *end ) {
106     case ':': 
107         high = strtol(end+1,0,0); 
108         break;
109     case '\0':
110         break;
111     default:
112         printf("unexpected character = %c\n",*end);
113     }
114 }
115
116 //! Number of threads to use.
117 static IntRange NThread(1,4);
118
119 //! If true, then at end wait for user to hit return
120 static bool PauseFlag = false;
121
122 //! Displays usage message
123 void Usage(char * argv0) {
124     fprintf(stderr, "Usage: %s [nthread [ntrials ['pause']]]\n", argv0);
125     fprintf(stderr, "where nthread is a non-negative integer, or range of the form low:high [%d:%d]\n", NThread.low, NThread.high);
126     fprintf(stderr, "ntrials is a positive integer. Default value is 50, reduce it (e.g. to 5) to shorten example run time\n");
127     fprintf(stderr, "The application waits for user to hit return if 'pause' is specified\n");
128 }
129
130 //! Parse the command line.
131 static void ParseCommandLine( int argc, char* argv[] ) {
132     int i = 1;
133         if( i<argc && !isdigit(argv[i][0]) ) { 
134         // Command line is garbled.
135         Usage(argv[0]);
136         exit(1);
137     }
138     if( i<argc )
139         NThread.set_from_string(argv[i++]);
140     if( i<argc && !isdigit(argv[i][0]) ) { 
141         // Command line is garbled.
142         Usage(argv[0]);
143         exit(1);
144     }
145     if (i<argc) {
146         ntrial = strtol(argv[i++], 0, 0);
147     }
148     if (ntrial == 0) {
149         // Command line is garbled.
150         Usage(argv[0]);
151         exit(1);
152     }
153     if (i<argc && strcmp( argv[i], "pause" )==0 ) {
154         PauseFlag = true;
155     }
156 }
157
158 int main( int argc, char* argv[] ) {
159     ParseCommandLine(argc,argv);
160
161     // Start scheduler with given number of threads.
162     for( int p=NThread.low; p<=NThread.high; ++p ) {
163         tbb::task_scheduler_init init(p);
164         srand(2);
165         tbb::tick_count::interval_t interval;
166         size_t total_root_set_size = 0;
167         for( int trial=0; trial<ntrial; ++trial ) {
168             Graph g;
169             g.create_random_dag(1000);
170             vector<Cell*> root_set;
171             g.get_root_set(root_set);
172             total_root_set_size += root_set.size();
173
174             tbb::tick_count t0 = tbb::tick_count::now();
175             for( int i=0; i<10; ++i ) {
176                 ParallelPreorderTraversal(root_set);
177             }
178             tbb::tick_count t1 = tbb::tick_count::now();
179
180             interval += t1-t0;
181         }
182         printf("%g seconds using %d threads (average of %g nodes in root_set)\n",interval.seconds(),p,(double)total_root_set_size/ntrial);
183     }
184
185     if (PauseFlag) {
186         printf ("Press return key to exit");
187         char c;
188         int n = scanf("%c", &c);
189         if( n!=1 ) {
190             fprintf(stderr,"Fatal error: unexpected end of input\n");
191             exit(1);
192         }
193     }
194
195     return 0;
196 }

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.

Douglas Adams


Typeset in Trocchi and Trocchi Bold Sans Serif.