source: trunk/test/test_adjacency_iteration.cpp @ 4165

Revision 4165, 15.9 KB checked in by gemacke, 2 months ago (diff)

Further pull things out of util.hpp. Gets rid of util.hpp in favor of directly including base_include.hpp. Simplifies includes in many files. Updates autoconf files to know about file additions and deletions.

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