source: trunk/test/test_adjacency_iteration.cpp @ 4148

Revision 4148, 15.9 KB checked in by gemacke, 3 months ago (diff)

Merging Kokkos branch into trunk.

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
45using namespace mtgl;
46
47typedef compressed_sparse_row_graph<directedS> Graph;
48typedef graph_traits<Graph>::size_type size_type;
49typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
50typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
51
52/// Counts the number of adjacencies with a higher id than the source using a
53/// pure C traveral.
54template <typename Graph>
55void
56count_adjacencies_higher_id(Graph& g,
57                            typename graph_traits<Graph>::size_type* indeg)
58{
59  typedef typename graph_traits<Graph>::size_type size_type;
60  typedef typename Graph::edge_data edge_data;
61
62  size_type order = g.get_order();
63  size_type* index = g.get_index();
64  edge_data* 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].dest) mt_incr(indeg[end_points[j].dest], 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  typedef typename Graph::edge_data edge_data;
96
97  size_type order = g.get_order();
98  size_type* index = g.get_index();
99  edge_data* end_points = g.get_end_points();
100
101  #pragma mta assert noalias *indeg
102  #pragma mta assert parallel
103  for (size_type i = 0; i < order; ++i)
104  {
105    size_type begin = index[i];
106    size_type end = index[i + 1];
107
108    #pragma mta assert parallel
109    for (size_type j = begin; j < end; ++j)
110    {
111      if (my_func(i, end_points[j].dest)) mt_incr(indeg[end_points[j].dest], 1);
112    }
113  }
114}
115
116template <typename Graph>
117class test_pred_func_obj {
118public:
119  typedef typename graph_traits<Graph>::size_type size_type;
120
121  inline bool operator()(size_type i, size_type j) { return (i < j); }
122};
123
124/// Counts the number of adjacencies with a higher id than the source using a
125/// pure C traveral with a function object.
126template <typename Graph, typename pred>
127void
128count_adjacencies_higher_id_func_obj(
129    Graph& g, typename graph_traits<Graph>::size_type* indeg, pred my_func)
130{
131  typedef typename graph_traits<Graph>::size_type size_type;
132  typedef typename Graph::edge_data edge_data;
133
134  size_type order = g.get_order();
135  size_type* index = g.get_index();
136  edge_data* end_points = g.get_end_points();
137
138  #pragma mta assert noalias *indeg
139  for (size_type i = 0; i < order; ++i)
140  {
141    size_type begin = index[i];
142    size_type end = index[i + 1];
143
144    for (size_type j = begin; j < end; ++j)
145    {
146      if (my_func(i, end_points[j].dest)) mt_incr(indeg[end_points[j].dest], 1);
147    }
148  }
149}
150
151/// Counts the number of adjacencies with a higher id than the source using an
152/// MTGL traveral.
153template <typename Graph, typename predicate>
154void count_adjacencies_higher_id_mtgl(
155    Graph& g, typename graph_traits<Graph>::size_type* indeg, predicate f)
156{
157  typedef typename graph_traits<Graph>::size_type size_type;
158  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
159  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
160  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
161
162  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
163  size_type order = num_vertices(g);
164  vertex_iterator verts = vertices(g);
165
166  #pragma mta assert noalias *indeg
167  for (size_type i = 0; i < order; ++i)
168  {
169    vertex_descriptor u = verts[i];
170    size_type uid = get(vid_map, u);
171    adjacency_iterator adjs = adjacent_vertices(u, g);
172    size_type end = out_degree(u, g);
173
174    for (size_type j = 0; j < end; ++j)
175    {
176      vertex_descriptor v = adjs[j];
177      size_type vid = get(vid_map, v);
178
179      if (f(uid, vid)) mt_incr(indeg[vid], 1);
180    }
181  }
182}
183
184/// A visitor to the load-balanced visit_adj function.
185template <typename Graph, typename predicate>
186class adjacencies_higher_id_computer {
187public:
188  typedef typename graph_traits<Graph>::size_type size_type;
189  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
190
191  adjacencies_higher_id_computer(const vertex_id_map<Graph>& vm, size_type *ind,
192                                 predicate ff) :
193    vid_map(vm), in_degree(ind), f(ff) {}
194
195  inline void operator()(vertex_descriptor src, vertex_descriptor dest)
196  {
197    size_type v1id = get(vid_map, src);
198    size_type v2id = get(vid_map, dest);
199
200    if (f(v1id, v2id)) mt_incr(in_degree[v2id], 1);
201  }
202
203  void post_visit() {}
204
205private:
206  const vertex_id_map<Graph>& vid_map;
207  size_type* in_degree;
208  predicate f;
209};
210
211template <typename Graph, typename visitor>
212void visit_adj_partial(Graph& g, visitor f)
213{
214  typedef typename graph_traits<Graph>::size_type size_type;
215  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
216  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
217  typedef typename Graph::edge_data edge_data;
218
219  const size_type* index = g.get_index();
220  const edge_data* end_points = g.get_end_points();
221  const size_type order = num_vertices(g);
222
223  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
224  vertex_iterator verts = vertices(g);
225
226  #pragma mta assert parallel
227  for (size_type i = 0; i < order; ++i)
228  {
229    vertex_descriptor u = verts[i];
230    size_type begin = index[get(vid_map, u)];
231    size_type end = index[get(vid_map, u) + 1];
232    #pragma mta assert parallel
233    for (size_type j = begin; j < end; ++j)
234    {
235      vertex_descriptor v = verts[end_points[j].dest];
236      f(u, v);
237    }
238  }
239}
240
241template <typename Graph, typename visitor>
242void visit_adj_full(Graph& g, visitor f)
243{
244  typedef typename graph_traits<Graph>::size_type size_type;
245  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
246  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
247  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
248
249  const size_type *index = g.get_index();
250  const size_type order = num_vertices(g);
251
252  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
253  vertex_iterator verts = vertices(g);
254
255  #pragma mta assert parallel
256  for (size_type i = 0; i < order; ++i)
257  {
258    vertex_descriptor u = verts[i];
259    adjacency_iterator adjs = adjacent_vertices(u, g);
260    size_type end = out_degree(u, g);
261    #pragma mta assert parallel
262    for (size_type j = 0; j < end; ++j)
263    {
264      vertex_descriptor v = adjs[j];
265      f(u, v);
266    }
267  }
268}
269
270template <typename Graph, typename visitor>
271void visit_adj_partial(Graph& g,
272         typename graph_traits<Graph>::vertex_descriptor* to_visit,
273         typename graph_traits<Graph>::size_type num_to_visit,
274         visitor f)
275{
276  typedef typename graph_traits<Graph>::size_type size_type;
277  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
278  typedef typename Graph::edge_data edge_data;
279
280  const size_type *index = g.get_index();
281  const edge_data *end_points = g.get_end_points();
282
283  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
284
285  #pragma mta assert parallel
286  for (size_type i = 0; i < num_to_visit; ++i)
287  {
288    vertex_descriptor u = to_visit[i];
289    size_type begin = index[get(vid_map, u)];
290    size_type end = index[get(vid_map, u) + 1];
291    #pragma mta assert parallel
292    for (size_type j = begin; j < end; ++j)
293    {
294      f(u, end_points[j].dest);
295    }
296  }
297}
298
299template <typename Graph, typename visitor>
300void visit_adj(Graph& g,
301         typename graph_traits<Graph>::vertex_descriptor* to_visit,
302         typename graph_traits<Graph>::size_type num_to_visit,
303         visitor f)
304{
305  typedef typename graph_traits<Graph>::size_type size_type;
306  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
307  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
308
309  const size_type *index = g.get_index();
310  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
311
312  #pragma mta assert parallel
313  for (size_type i = 0; i < num_to_visit; ++i)
314  {
315    vertex_descriptor u = to_visit[i];
316    adjacency_iterator adjs = adjacent_vertices(u, g);
317    size_type deg = out_degree(u, g);
318
319    #pragma mta assert parallel
320    for (size_type j = 0; j < deg; ++j)
321    {
322      vertex_descriptor v = adjs[j];
323      f(u, j);
324    }
325  }
326}
327
328void checkError(size_type* indeg, size_type* indeg2, size_type order)
329{
330  size_type error = (std::numeric_limits<size_type>::max)();
331
332  for (size_type i = 0; i < order; ++i)
333  {
334    if (indeg[i] != indeg2[i]) error = i;
335  }
336
337  if (error != (std::numeric_limits<size_type>::max)())
338  {
339    std::cout << "Error in computation: pos " << error << std::endl;
340  }
341}
342
343int main(int argc, char* argv[])
344{
345  unsigned num_threads = init_test(argc, argv);
346  mtgl_initialize(num_threads);
347
348  Graph g;
349  create_test_graph(g, argc, argv);
350
351  size_type order = num_vertices(g);
352  size_type size = num_edges(g);
353  size_type* indeg = new size_type[order];
354  size_type* indeg2 = new size_type[order];
355
356  test_pred_func_obj<Graph> tpc;
357
358  printf("order: %lu, size: %lu\n", order, size);
359
360  for (size_type i = 0; i < order; ++i) indeg[i] = 0;
361
362  mt_timer timer;
363  int issues, memrefs, concur, streams, traps;
364
365  MTGL_FENCE()
366  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
367
368#ifdef __MTA__
369  int phantoms = mta_get_task_counter(RT_PHANTOM);
370  int ready = mta_get_task_counter(RT_READY);
371#endif
372
373  count_adjacencies_higher_id(g, indeg);
374
375  MTGL_FENCE()
376  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
377
378#ifdef __MTA__
379  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
380  ready = mta_get_task_counter(RT_READY) - ready;
381#endif
382
383  printf("---------------------------------------------\n");
384  printf("count_adjacencies_higher_id(): \n");
385  printf("---------------------------------------------\n");
386  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
387                     traps);
388#ifdef __MTA__
389  printf("phantoms: %d\n", phantoms);
390  printf("ready: %d\n", ready);
391#endif
392
393  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
394
395  MTGL_FENCE()
396  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
397
398#ifdef __MTA__
399  phantoms = mta_get_task_counter(RT_PHANTOM);
400  ready = mta_get_task_counter(RT_READY);
401#endif
402
403  count_adjacencies_higher_id_func_ptr(g, indeg2, test_pred_func);
404
405  MTGL_FENCE()
406  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
407
408#ifdef __MTA__
409  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
410  ready = mta_get_task_counter(RT_READY) - ready;
411#endif
412
413  printf("---------------------------------------------\n");
414  printf("count_adjacencies_higher_id_func_ptr(): \n");
415  printf("---------------------------------------------\n");
416  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
417                     traps);
418
419#ifdef __MTA__
420  printf("phantoms: %d\n", phantoms);
421  printf("ready: %d\n", ready);
422#endif
423
424  checkError(indeg, indeg2, order);
425
426  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
427
428  MTGL_FENCE()
429  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
430
431#ifdef __MTA__
432  phantoms = mta_get_task_counter(RT_PHANTOM);
433  ready = mta_get_task_counter(RT_READY);
434#endif
435
436  count_adjacencies_higher_id_func_obj(g, indeg2, tpc);
437
438  MTGL_FENCE()
439  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
440
441#ifdef __MTA__
442  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
443  ready = mta_get_task_counter(RT_READY) - ready;
444#endif
445
446  printf("---------------------------------------------\n");
447  printf("count_adjacencies_higher_id_func_obj(): \n");
448  printf("---------------------------------------------\n");
449  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
450                     traps);
451
452#ifdef __MTA__
453  printf("phantoms: %d\n", phantoms);
454  printf("ready: %d\n", ready);
455#endif
456
457  checkError(indeg, indeg2, order);
458
459  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
460
461  MTGL_FENCE()
462  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
463
464#ifdef __MTA__
465  phantoms = mta_get_task_counter(RT_PHANTOM);
466  ready = mta_get_task_counter(RT_READY);
467#endif
468
469  count_adjacencies_higher_id_mtgl(g, indeg2, tpc);
470
471  MTGL_FENCE()
472  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
473
474#ifdef __MTA__
475  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
476  ready = mta_get_task_counter(RT_READY) - ready;
477#endif
478
479  printf("---------------------------------------------\n");
480  printf("count_adjacencies_higher_id_mtgl(): \n");
481  printf("---------------------------------------------\n");
482  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
483                     traps);
484
485#ifdef __MTA__
486  printf("phantoms: %d\n", phantoms);
487  printf("ready: %d\n", ready);
488#endif
489
490  checkError(indeg, indeg2, order);
491
492  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
493
494  adjacencies_higher_id_computer<Graph, test_pred_func_obj<Graph> >
495    idc(get(_vertex_id_map, g), indeg2, tpc);
496
497  size_type* prefix_counts = 0;
498  size_type* started_nodes = 0;
499  size_type nthreads;
500
501  MTGL_FENCE()
502  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
503
504#ifdef __MTA__
505  phantoms = mta_get_task_counter(RT_PHANTOM);
506  ready = mta_get_task_counter(RT_READY);
507#endif
508
509  visit_adj(g, idc, prefix_counts, started_nodes, nthreads);
510
511  MTGL_FENCE()
512  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
513
514#ifdef __MTA__
515  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
516  ready = mta_get_task_counter(RT_READY) - ready;
517#endif
518
519  printf("---------------------------------------------\n");
520  printf("visit_adj(): \n");
521  printf("---------------------------------------------\n");
522  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
523                     traps);
524
525  free(prefix_counts);
526  free(started_nodes);
527
528#ifdef __MTA__
529  printf("phantoms: %d\n", phantoms);
530  printf("ready: %d\n", ready);
531#endif
532
533  checkError(indeg, indeg2, order);
534
535  delete [] indeg;
536  delete [] indeg2;
537
538  mtgl_finalize();
539
540  return 0;
541}
Note: See TracBrowser for help on using the repository browser.