]> https://gitweb.dealii.org/ - dealii-svn.git/blob
d52f6299cb76556825cc6338dcfa599a9ed77ae1
[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 #include <iostream>
30 #include <string>
31 #include <algorithm>
32
33 #include "tbb/parallel_for.h"
34 #include "tbb/blocked_range.h"
35 #include "tbb/tick_count.h"
36
37 using namespace tbb;
38 using namespace std;
39 static const size_t N = 22;
40
41 void SerialSubStringFinder ( const string &str, size_t *max_array, size_t *pos_array) {
42  for ( size_t i = 0; i < str.size(); ++i ) {
43    size_t max_size = 0, max_pos = 0;
44    for (size_t j = 0; j < str.size(); ++j)
45     if (j != i) {
46      size_t limit = str.size()-( i > j ? i : j );
47      for (size_t k = 0; k < limit; ++k) {
48       if (str[i + k] != str[j + k]) break;
49       if (k > max_size) {
50        max_size = k;
51        max_pos = j;
52       }
53      }
54     }
55    max_array[i] = max_size;
56    pos_array[i] = max_pos;
57   }
58 }
59
60 class SubStringFinder {
61  const string str;
62  size_t *max_array;
63  size_t *pos_array;
64  public:
65  void operator() ( const blocked_range<size_t>& r ) const {
66   for ( size_t i = r.begin(); i != r.end(); ++i ) {
67    size_t max_size = 0, max_pos = 0;
68    for (size_t j = 0; j < str.size(); ++j) 
69     if (j != i) {
70      size_t limit = str.size()-( i > j ? i : j );
71      for (size_t k = 0; k < limit; ++k) {
72       if (str[i + k] != str[j + k]) break;
73       if (k > max_size) {
74        max_size = k;
75        max_pos = j;
76       }
77      }
78     }
79    max_array[i] = max_size;
80    pos_array[i] = max_pos;
81   }
82  }
83  SubStringFinder(string &s, size_t *m, size_t *p) : 
84   str(s), max_array(m), pos_array(p) { }
85 };
86
87 int main(int argc, char *argv[]) {
88  
89
90  string str[N] = { string("a"), string("b") };
91  for (size_t i = 2; i < N; ++i) str[i] = str[i-1]+str[i-2];
92  string &to_scan = str[N-1]; 
93
94  size_t *max = new size_t[to_scan.size()];
95  size_t *max2 = new size_t[to_scan.size()];
96  size_t *pos = new size_t[to_scan.size()];
97  size_t *pos2 = new size_t[to_scan.size()];
98  cout << " Done building string." << endl;
99
100  
101  tick_count serial_t0 = tick_count::now();
102  SerialSubStringFinder(to_scan, max2, pos2);
103  tick_count serial_t1 = tick_count::now();
104  cout << " Done with serial version." << endl;
105
106  tick_count parallel_t0 = tick_count::now();
107  parallel_for(blocked_range<size_t>(0, to_scan.size(), 100),
108        SubStringFinder( to_scan, max, pos ) );
109  tick_count parallel_t1 = tick_count::now();
110  cout << " Done with parallel version." << endl;
111
112  for (size_t i = 0; i < to_scan.size(); ++i) {
113    if (max[i] != max2[i] || pos[i] != pos2[i]) {
114      cout << "ERROR: Serial and Parallel Results are Different!" << endl;
115    }
116  }
117  cout << " Done validating results." << endl;
118
119  cout << "Serial version ran in " << (serial_t1 - serial_t0).seconds() << " seconds" << endl
120            << "Parallel version ran in " <<  (parallel_t1 - parallel_t0).seconds() << " seconds" << endl
121            << "Resulting in a speedup of " << (serial_t1 - serial_t0).seconds() / (parallel_t1 - parallel_t0).seconds() << endl;
122  delete[] max;
123  delete[] pos;
124  delete[] max2;
125  delete[] pos2;
126  return 0;
127 }
128

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.