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

Revision 3983, 15.6 KB checked in by gemacke, 13 months 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 | #include <mtgl/random.hpp> |

45 | |

46 | using namespace mtgl; |

47 | |

48 | typedef compressed_sparse_row_graph<directedS> Graph; |

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

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

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

55 | template <typename Graph> |

56 | void |

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

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

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

115 | template <typename Graph> |

116 | class test_pred_func_obj { |

117 | public: |

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

125 | template <typename Graph, typename pred> |

126 | void |

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

151 | template <typename Graph, typename predicate> |

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

183 | template <typename Graph, typename predicate> |

184 | class adjacencies_higher_id_computer { |

185 | public: |

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

203 | private: |

204 | const vertex_id_map<Graph>& vid_map; |

205 | size_type* in_degree; |

206 | predicate f; |

207 | }; |

208 | |

209 | template <typename Graph, typename visitor> |

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

238 | template <typename Graph, typename visitor> |

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

268 | template <typename Graph, typename visitor> |

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

296 | template <typename Graph, typename visitor> |

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

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

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