#
source:
trunk/test/test_adjacency_iteration.cpp
@
4089

Revision 4089, 15.7 KB checked in by gemacke, 2 weeks ago (diff) |
---|

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 | |

45 | using namespace mtgl; |

46 | |

47 | typedef compressed_sparse_row_graph<directedS> Graph; |

48 | typedef graph_traits<Graph>::size_type size_type; |

49 | typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; |

50 | typedef 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. |

54 | template <typename Graph> |

55 | void |

56 | count_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 | |

79 | typedef bool (*pred_t)(size_type, size_type); |

80 | |

81 | #pragma mta inline |

82 | inline 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. |

89 | template <typename Graph> |

90 | void |

91 | count_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 | |

116 | template <typename Graph> |

117 | class test_pred_func_obj { |

118 | public: |

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. |

126 | template <typename Graph, typename pred> |

127 | void |

128 | count_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. |

153 | template <typename Graph, typename predicate> |

154 | void 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. |

185 | template <typename Graph, typename predicate> |

186 | class adjacencies_higher_id_computer { |

187 | public: |

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 | |

205 | private: |

206 | const vertex_id_map<Graph>& vid_map; |

207 | size_type* in_degree; |

208 | predicate f; |

209 | }; |

210 | |

211 | template <typename Graph, typename visitor> |

212 | void 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 | |

241 | template <typename Graph, typename visitor> |

242 | void 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 | |

270 | template <typename Graph, typename visitor> |

271 | void 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 | |

299 | template <typename Graph, typename visitor> |

300 | void 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 | |

328 | void 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 | |

343 | int main(int argc, char* argv[]) |

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.