source: trunk/test/test_adjacency_iteration.cpp @ 4060

Revision 4060, 15.7 KB checked in by gemacke, 4 months ago (diff)

Formatting updates.

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