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

Revision 4060, 15.7 KB checked in by gemacke, 4 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 | 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 | |

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

81 | |

82 | #pragma mta inline |

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

90 | template <typename Graph> |

91 | void |

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

117 | template <typename Graph> |

118 | class test_pred_func_obj { |

119 | public: |

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

127 | template <typename Graph, typename pred> |

128 | void |

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

154 | template <typename Graph, typename predicate> |

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

186 | template <typename Graph, typename predicate> |

187 | class adjacencies_higher_id_computer { |

188 | public: |

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

206 | private: |

207 | const vertex_id_map<Graph>& vid_map; |

208 | size_type* in_degree; |

209 | predicate f; |

210 | }; |

211 | |

212 | template <typename Graph, typename visitor> |

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

242 | template <typename Graph, typename visitor> |

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

271 | template <typename Graph, typename visitor> |

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

300 | template <typename Graph, typename visitor> |

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

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

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