source: trunk/test/test_adjacency_iteration.cpp @ 3983

Revision 3983, 15.6 KB checked in by gemacke, 13 months ago (diff)

Fixes compile errors when using Apple LLVM compiler. (#4166)

Line 
1/*  _________________________________________________________________________
2 *
3 *  MTGL: The MultiThreaded Graph Library
4 *  Copyright (c) 2008 Sandia Corporation.
5 *  This software is distributed under the BSD License.
6 *  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
7 *  the U.S. Government retains certain rights in this software.
8 *  For more information, see the COPYING file in the top MTGL directory.
9 *  _________________________________________________________________________
10 */
11
12/****************************************************************************/
13/*! \file test_adjacency_iteration.cpp
14
15    \brief Compares visiting the adjacencies of a graph by accessing a CSR
16           graph structure directly with using the MTGL interface with using
17           the manually load-balanced version of visit_adj().
18
19    \author Jon Berry (jberry@sandia.gov)
20    \author Greg Mackey (gemacke@sandia.gov)
21
22    /date 8/15/2009
23
24    The inlined function test_pred_func() below represents a typical predicate
25    that users may wish to introduce as an algorithmic filter.  Unfortunately,
26    the use of this predicate via a function pointer in the inner loop of the
27    function count_adjacencies_higher_id_func_ptr() prevents the loop-merge
28    necessary for good performance.  The result is a serial inner loop, which
29    has severe consequences when processing power-law data.
30     
31    The predicate is easily introduced into the function object
32    test_pred_func_obj.  Using this function object instead of the function
33    pointer restores the loop merge as demonstrated in the function
34    count_adjacencies_higher_id_func_obj().
35*/
36/****************************************************************************/
37
38#include <cstdlib>
39#include <climits>
40
41#include <mtgl/visit_adj.hpp>
42#include <mtgl/compressed_sparse_row_graph.hpp>
43#include <mtgl/mtgl_test.hpp>
44#include <mtgl/random.hpp>
45
46using namespace mtgl;
47
48typedef compressed_sparse_row_graph<directedS> Graph;
49typedef graph_traits<Graph>::size_type size_type;
50typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
51typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
52
53/// Counts the number of adjacencies with a higher id than the source using a
54/// pure C traveral.
55template <typename Graph>
56void
57count_adjacencies_higher_id(Graph& g,
58                            typename graph_traits<Graph>::size_type* indeg)
59{
60  typedef typename graph_traits<Graph>::size_type size_type;
61
62  size_type order = g.get_order();
63  size_type* index = g.get_index();
64  size_type* end_points = g.get_end_points();
65
66  #pragma mta assert noalias *indeg
67  for (size_type i = 0; i < order; ++i)
68  {
69    size_type begin = index[i];
70    size_type end = index[i + 1];
71
72    for (size_type j = begin; j < end; ++j)
73    {
74      if (i < end_points[j]) mt_incr(indeg[end_points[j]], 1);
75    }
76  }
77}
78
79typedef bool (*pred_t)(size_type, size_type);
80
81#pragma mta inline
82inline bool test_pred_func(size_type i, size_type j)
83{
84  return (i < j);
85}
86
87/// Counts the number of adjacencies with a higher id than the source using a
88/// pure C traveral with a function pointer.
89template <typename Graph>
90void
91count_adjacencies_higher_id_func_ptr(
92    Graph& g, typename graph_traits<Graph>::size_type* indeg, pred_t my_func)
93{
94  typedef typename graph_traits<Graph>::size_type size_type;
95
96  size_type order = g.get_order();
97  size_type* index = g.get_index();
98  size_type* end_points = g.get_end_points();
99
100  #pragma mta assert noalias *indeg
101  #pragma mta assert parallel
102  for (size_type i = 0; i < order; ++i)
103  {
104    size_type begin = index[i];
105    size_type end = index[i + 1];
106
107    #pragma mta assert parallel
108    for (size_type j = begin; j < end; ++j)
109    {
110      if (my_func(i, end_points[j])) mt_incr(indeg[end_points[j]], 1);
111    }
112  }
113}
114
115template <typename Graph>
116class test_pred_func_obj {
117public:
118  typedef typename graph_traits<Graph>::size_type size_type;
119
120  inline bool operator()(size_type i, size_type j) { return (i < j); }
121};
122
123/// Counts the number of adjacencies with a higher id than the source using a
124/// pure C traveral with a function object.
125template <typename Graph, typename pred>
126void
127count_adjacencies_higher_id_func_obj(
128    Graph& g, typename graph_traits<Graph>::size_type* indeg, pred my_func)
129{
130  typedef typename graph_traits<Graph>::size_type size_type;
131
132  size_type order = g.get_order();
133  size_type* index = g.get_index();
134  size_type* end_points = g.get_end_points();
135
136  #pragma mta assert noalias *indeg
137  for (size_type i = 0; i < order; ++i)
138  {
139    size_type begin = index[i];
140    size_type end = index[i + 1];
141
142    for (size_type j = begin; j < end; ++j)
143    {
144      if (my_func(i, end_points[j])) mt_incr(indeg[end_points[j]], 1);
145    }
146  }
147}
148
149/// Counts the number of adjacencies with a higher id than the source using an
150/// MTGL traveral.
151template <typename Graph, typename predicate>
152void count_adjacencies_higher_id_mtgl(
153    Graph& g, typename graph_traits<Graph>::size_type* indeg, predicate f)
154{
155  typedef typename graph_traits<Graph>::size_type size_type;
156  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
157  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
158  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
159
160  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
161  size_type order = num_vertices(g);
162  vertex_iterator verts = vertices(g);
163
164  #pragma mta assert noalias *indeg
165  for (size_type i = 0; i < order; ++i)
166  {
167    vertex_descriptor u = verts[i];
168    size_type uid = get(vid_map, u);
169    adjacency_iterator adjs = adjacent_vertices(u, g);
170    size_type end = out_degree(u, g);
171
172    for (size_type j = 0; j < end; ++j)
173    {
174      vertex_descriptor v = adjs[j];
175      size_type vid = get(vid_map, v);
176
177      if (f(uid, vid)) mt_incr(indeg[vid], 1);
178    }
179  }
180}
181
182/// A visitor to the load-balanced visit_adj function.
183template <typename Graph, typename predicate>
184class adjacencies_higher_id_computer {
185public:
186  typedef typename graph_traits<Graph>::size_type size_type;
187  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
188
189  adjacencies_higher_id_computer(const vertex_id_map<Graph>& vm, size_type *ind,
190                                 predicate ff) :
191    vid_map(vm), in_degree(ind), f(ff) {}
192
193  inline void operator()(vertex_descriptor src, vertex_descriptor dest)
194  {
195    size_type v1id = get(vid_map, src);
196    size_type v2id = get(vid_map, dest);
197
198    if (f(v1id, v2id)) mt_incr(in_degree[v2id], 1);
199  }
200
201  void post_visit() {}
202
203private:
204  const vertex_id_map<Graph>& vid_map;
205  size_type* in_degree;
206  predicate f;
207};
208
209template <typename Graph, typename visitor>
210void visit_adj_partial(Graph& g, visitor f)
211{
212  typedef typename graph_traits<Graph>::size_type size_type;
213  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
214  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
215
216  const size_type* index = g.get_index();
217  const vertex_descriptor* end_points = g.get_end_points();
218  const size_type order = num_vertices(g);
219
220  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
221  vertex_iterator verts = vertices(g);
222
223  #pragma mta assert parallel
224  for (size_type i = 0; i < order; ++i)
225  {
226    vertex_descriptor u = verts[i];
227    size_type begin = index[get(vid_map, u)];
228    size_type end = index[get(vid_map, u) + 1];
229    #pragma mta assert parallel
230    for (size_type j = begin; j < end; ++j)
231    {
232      vertex_descriptor v = verts[end_points[j]];
233      f(u, v);
234    }
235  }
236}
237
238template <typename Graph, typename visitor>
239void visit_adj_full(Graph& g, visitor f)
240{
241  typedef typename graph_traits<Graph>::size_type size_type;
242  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
243  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
244  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
245
246  const size_type *index = g.get_index();
247  const vertex_descriptor *end_points = g.get_end_points();
248  const size_type order = num_vertices(g);
249
250  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
251  vertex_iterator verts = vertices(g);
252
253  #pragma mta assert parallel
254  for (size_type i = 0; i < order; ++i)
255  {
256    vertex_descriptor u = verts[i];
257    adjacency_iterator adjs = adjacent_vertices(u, g);
258    size_type end = out_degree(u, g);
259    #pragma mta assert parallel
260    for (size_type j = 0; j < end; ++j)
261    {
262      vertex_descriptor v = adjs[j];
263      f(u, v);
264    }
265  }
266}
267
268template <typename Graph, typename visitor>
269void visit_adj_partial(Graph& g,
270         typename graph_traits<Graph>::vertex_descriptor* to_visit,
271         typename graph_traits<Graph>::size_type num_to_visit,
272         visitor f)
273{
274  typedef typename graph_traits<Graph>::size_type size_type;
275  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
276
277  const size_type *index = g.get_index();
278  const vertex_descriptor *end_points = g.get_end_points();
279
280  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
281
282  #pragma mta assert parallel
283  for (size_type i = 0; i < num_to_visit; ++i)
284  {
285    vertex_descriptor u = to_visit[i];
286    size_type begin = index[get(vid_map, u)];
287    size_type end = index[get(vid_map, u) + 1];
288    #pragma mta assert parallel
289    for (size_type j = begin; j < end; ++j)
290    {
291      f(end_points[i], end_points[j]);
292    }
293  }
294}
295
296template <typename Graph, typename visitor>
297void visit_adj(Graph& g,
298         typename graph_traits<Graph>::vertex_descriptor* to_visit,
299         typename graph_traits<Graph>::size_type num_to_visit,
300         visitor f)
301{
302  typedef typename graph_traits<Graph>::size_type size_type;
303  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
304  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
305
306  const size_type *index = g.get_index();
307  const vertex_descriptor *end_points = g.get_end_points();
308  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
309
310  #pragma mta assert parallel
311  for (size_type i = 0; i < num_to_visit; ++i)
312  {
313    vertex_descriptor u = to_visit[i];
314    adjacency_iterator adjs = adjacent_vertices(u, g);
315    size_type deg = out_degree(u, g);
316
317    #pragma mta assert parallel
318    for (size_type j = 0; j < deg; ++j)
319    {
320      vertex_descriptor v = adjs[j];
321      f(u, j);
322    }
323  }
324}
325
326void checkError(size_type* indeg, size_type* indeg2, size_type order)
327{
328  size_type error = (std::numeric_limits<size_type>::max)();
329
330  for (size_type i = 0; i < order; ++i)
331  {
332    if (indeg[i] != indeg2[i]) error = i;
333  }
334
335  if (error != (std::numeric_limits<size_type>::max)())
336  {
337    std::cout << "Error in computation: pos " << error << std::endl;
338  }
339}
340
341int main(int argc, char* argv[])
342{
343  mt_srand48(0);
344
345  init_test(argc, argv);
346
347  Graph g;
348  create_test_graph(g, argc, argv);
349
350  size_type order = num_vertices(g);
351  size_type size = num_edges(g);
352  size_type* indeg = new size_type[order];
353  size_type* indeg2 = new size_type[order];
354
355  test_pred_func_obj<Graph> tpc;
356
357  printf("order: %lu, size: %lu\n", order, size);
358
359  for (size_type i = 0; i < order; ++i) indeg[i] = 0;
360
361  mt_timer timer;
362  int issues, memrefs, concur, streams, traps;
363
364  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
365
366#ifdef __MTA__
367  int phantoms = mta_get_task_counter(RT_PHANTOM);
368  int ready = mta_get_task_counter(RT_READY);
369#endif
370
371  count_adjacencies_higher_id(g, indeg);
372
373  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
374
375#ifdef __MTA__
376  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
377  ready = mta_get_task_counter(RT_READY) - ready;
378#endif
379
380  printf("---------------------------------------------\n");
381  printf("count_adjacencies_higher_id(): \n");
382  printf("---------------------------------------------\n");
383  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
384                     traps);
385#ifdef __MTA__
386  printf("phantoms: %d\n", phantoms);
387  printf("ready: %d\n", ready);
388#endif
389
390  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
391
392  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
393
394#ifdef __MTA__
395  phantoms = mta_get_task_counter(RT_PHANTOM);
396  ready = mta_get_task_counter(RT_READY);
397#endif
398
399  count_adjacencies_higher_id_func_ptr(g, indeg2, test_pred_func);
400
401  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
402
403#ifdef __MTA__
404  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
405  ready = mta_get_task_counter(RT_READY) - ready;
406#endif
407
408  printf("---------------------------------------------\n");
409  printf("count_adjacencies_higher_id_func_ptr(): \n");
410  printf("---------------------------------------------\n");
411  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
412                     traps);
413
414#ifdef __MTA__
415  printf("phantoms: %d\n", phantoms);
416  printf("ready: %d\n", ready);
417#endif
418
419  checkError(indeg, indeg2, order);
420
421  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
422
423  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
424
425#ifdef __MTA__
426  phantoms = mta_get_task_counter(RT_PHANTOM);
427  ready = mta_get_task_counter(RT_READY);
428#endif
429
430  count_adjacencies_higher_id_func_obj(g, indeg2, tpc);
431
432  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
433
434#ifdef __MTA__
435  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
436  ready = mta_get_task_counter(RT_READY) - ready;
437#endif
438
439  printf("---------------------------------------------\n");
440  printf("count_adjacencies_higher_id_func_obj(): \n");
441  printf("---------------------------------------------\n");
442  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
443                     traps);
444
445#ifdef __MTA__
446  printf("phantoms: %d\n", phantoms);
447  printf("ready: %d\n", ready);
448#endif
449
450  checkError(indeg, indeg2, order);
451
452  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
453
454  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
455
456#ifdef __MTA__
457  phantoms = mta_get_task_counter(RT_PHANTOM);
458  ready = mta_get_task_counter(RT_READY);
459#endif
460
461  count_adjacencies_higher_id_mtgl(g, indeg2, tpc);
462
463  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
464
465#ifdef __MTA__
466  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
467  ready = mta_get_task_counter(RT_READY) - ready;
468#endif
469
470  printf("---------------------------------------------\n");
471  printf("count_adjacencies_higher_id_mtgl(): \n");
472  printf("---------------------------------------------\n");
473  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
474                     traps);
475
476#ifdef __MTA__
477  printf("phantoms: %d\n", phantoms);
478  printf("ready: %d\n", ready);
479#endif
480
481  checkError(indeg, indeg2, order);
482
483  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
484
485  adjacencies_higher_id_computer<Graph, test_pred_func_obj<Graph> >
486    idc(get(_vertex_id_map, g), indeg2, tpc);
487
488  size_type* prefix_counts = 0;
489  size_type* started_nodes = 0;
490  size_type num_threads;
491
492  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
493
494#ifdef __MTA__
495  phantoms = mta_get_task_counter(RT_PHANTOM);
496  ready = mta_get_task_counter(RT_READY);
497#endif
498
499  visit_adj(g, idc, prefix_counts, started_nodes, num_threads);
500  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
501
502#ifdef __MTA__
503  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
504  ready = mta_get_task_counter(RT_READY) - ready;
505#endif
506
507  printf("---------------------------------------------\n");
508  printf("visit_adj(): \n");
509  printf("---------------------------------------------\n");
510  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
511                     traps);
512
513  free(prefix_counts);
514  free(started_nodes);
515
516#ifdef __MTA__
517  printf("phantoms: %d\n", phantoms);
518  printf("ready: %d\n", ready);
519#endif
520
521  checkError(indeg, indeg2, order);
522
523  delete [] indeg;
524  delete [] indeg2;
525
526  return 0;
527}
Note: See TracBrowser for help on using the repository browser.