Changes between Version 32 and Version 33 of FirstMtglExample


Ignore:
Timestamp:
04/14/10 16:48:32 (9 years ago)
Author:
gemacke
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FirstMtglExample

    v32 v33  
    573573 
    574574 
    575 If you look at the loop annotations further below, you will see that loops 45, 62, 79, and 123 in parallel region 4 are for static_graph_adapter.  Loops 46, 63, 80, and 124 in parallel region 5 are for adjacency_list_adapter.  For both versions all of the MTGL function calls are still inlined, and both versions perform a manhattan loop collapse.  Both versions also remove the reduction completely out of the loop and atomicize access to id_sum.  As we will see below, however, the adjacency_list_adapter version performs more work than the static_graph_adapter version. 
     575If you look at the loop annotations further below, you will see that loops 43, 59, 75, and 116 in parallel region 4 are for static_graph_adapter.  Loops 44, 60, 76, and 117 in parallel region 5 are for adjacency_list_adapter.  For both versions all of the MTGL function calls are still inlined, and both versions perform a manhattan loop collapse.  Both versions also remove the reduction completely out of the loop and atomicize access to id_sum.  As we will see below, however, the adjacency_list_adapter version performs more work than the static_graph_adapter version. 
    576576 
    577577{{{ 
     
    584584            |   for (size_type i = 0; i < order; i++) 
    585585            |   { 
    586    80 P     |     vertex_descriptor u = verts[i]; 
    587    46 P:e   + 
     586   76 P     |     vertex_descriptor u = verts[i]; 
     587   44 P:e   + 
    588588++ function T1 mtgl::static_vertex_iterator<T1, T2>::operator [] inlined 
    589    80 P:m   |     adjacency_iterator adjs = adjacent_vertices(u, g); 
     589   76 P:m   |     adjacency_iterator adjs = adjacent_vertices(u, g); 
    590590++ function mtgl::adjacency_list_adapter<N1>::adjacency_iterator mtgl::adjacent_vertices<N1> inlined 
    591591++ function mtgl::static_graph_adapter<N1>::adjacency_iterator mtgl::adjacent_vertices<N1> inlined 
    592    79 P:e   |     size_type end = out_degree(u, g); 
     592   75 P:e   |     size_type end = out_degree(u, g); 
    593593++ function mtgl::graph_traits<mtgl::adjacency_list_adapter<N1>>::size_type mtgl::out_degree<N1> inlined 
    594594++ function mtgl::static_graph_adapter<N1>::size_type mtgl::out_degree<N1> inlined 
    595595            |     for (size_type j = 0; j < end; j++) 
    596596            |     { 
    597   124 PP:m  |       vertex_descriptor v = adjs[j]; 
     597  117 PP:m  |       vertex_descriptor v = adjs[j]; 
    598598++ function T1::Vertex *mtgl::al_adjacency_iterator<T1>::operator [] inlined 
    599599++ function T1 mtgl::static_adjacency_iterator<T1, T2>::operator [] inlined 
    600   124 PP:m  |       size_type vid = get(vid_map, v); 
     600  116 PP:m  |       size_type vid = get(vid_map, v); 
    601601++ function T2 mtgl::get<T1, T2, T3> inlined 
    602602++ function T2 mtgl::get<T1, T2, T3> inlined 
    603   124 PP:m$ |       id_sum += vid; 
    604   123 PP:m$ + 
     603  117 PP:m$ |       id_sum += vid; 
     604  116 PP:m$ + 
    605605** reduction moved out of 2 loops 
    606606            |     } 
     
    608608}}} 
    609609 
    610 Let's do a loop-by-loop comparison of the work required for each adapter.  We'll look first at loops 45 and 46 which perform stage 1 of the recurrence.  Loop 45 is for static_graph_adapter, and it performs 2 instructions with 1 load.  Loop 46 is for adjacency_list_adapter, and it performs 2 instructions with 2 loads. 
    611  
    612 {{{ 
    613 Loop  45 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
     610Let's do a loop-by-loop comparison of the work required for each adapter.  We'll look first at loops 43 and 44 which perform stage 1 of the recurrence.  Loop 43 is for static_graph_adapter, and it performs 2 instructions with 1 load.  Loop 44 is for adjacency_list_adapter, and it performs 2 instructions with 2 loads. 
     611 
     612{{{ 
     613Loop  43 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
    614614at line 61 in region 4 
    615615       Stage 1 of recurrence 
     
    618618                pipelined 
    619619 
    620 Loop  46 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
     620Loop  44 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
    621621at line 59 in region 5 
    622622       Stage 1 of recurrence 
     
    626626}}} 
    627627 
    628 Loops 62 and 63 perform the communication phase of stage 1 of the recurrence.  Loop 62 is for static_graph_adapter, and loop 63 is for adjacency_list_adapter.  They both perform 11 instructions with 1 load, 1 store, and 3 branches. 
    629  
    630 {{{ 
    631 Loop  62 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
     628Loops 59 and 60 perform the communication phase of stage 1 of the recurrence.  Loop 59 is for static_graph_adapter, and loop 60 is for adjacency_list_adapter.  They both perform 11 instructions with 1 load, 1 store, and 3 branches. 
     629 
     630{{{ 
     631Loop  59 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
    632632in region 4 
    633633       Stage 1 recurrence communication 
     
    637637                1 loads, 1 stores, 0 reloads, 0 spills, 3 branches, 0 calls 
    638638 
    639 Loop  63 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
     639Loop  60 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
    640640in region 5 
    641641       Stage 1 recurrence communication 
     
    646646}}} 
    647647 
    648 Loops 79 and 80 perform stage 2 of the recurrence.  Loop 79 is for static_graph_adapter, and it performs 3 instructions with 1 load and 2 stores.  Loop 80 is for adjacency_list_adapter, and it performs 5 instructions with 2 loads and 3 stores. 
    649  
    650 {{{ 
    651 Loop  79 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
     648Loops 75 and 76 perform stage 2 of the recurrence.  Loop 75 is for static_graph_adapter, and it performs 3 instructions with 1 load and 2 stores.  Loop 76 is for adjacency_list_adapter, and it performs 5 instructions with 2 loads and 3 stores. 
     649 
     650{{{ 
     651Loop  75 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
    652652at line 61 in region 4 
    653653       Stage 2 of recurrence 
     
    656656                pipelined 
    657657 
    658 Loop  80 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
     658Loop  76 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
    659659at line 59 in region 5 
    660660       Stage 2 of recurrence 
     
    664664}}} 
    665665 
    666 Loops 123 and 124 are the collapsed versions of the work in the inner loop minus the work for the reduction.  Loop 123 is for static_graph_adapter, and it performs 1 instruction with 1 load.  Loop 124 is for adjacency_list_adapter, and it performs 7 instructions with 7 loads. 
    667  
    668 {{{ 
    669 Loop 123 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
    670 at line 60 in loop 109 
     666Loops 116 and 117 are the collapsed versions of the work in the inner loop minus the work for the reduction.  Loop 116 is for static_graph_adapter, and it performs 1 instruction with 1 load.  Loop 117 is for adjacency_list_adapter, and it performs 4 instructions with 4 loads. 
     667 
     668{{{ 
     669Loop 116 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::static_graph_adapter<(int)1>] 
     670at line 60 in loop 103 
    671671       Parallel section of loop from level 2 
    672672       Loop summary: 1 loads, 0 stores, 0 floating point operations 
     
    674674                pipelined 
    675675 
    676 Loop 124 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
    677 at line 64 in loop 110 
     676Loop 117 in mtgl::graph_traits<T1>::size_type compute_id_sum<T1>(T1 &) [with T1=mtgl::adjacency_list_adapter<(int)1>] 
     677at line 64 in loop 104 
    678678       Parallel section of loop from level 2 
    679        Loop summary: 7 loads, 0 stores, 0 floating point operations 
    680                 7 instructions, needs 46 streams for full utilization 
    681                 pipelined 
    682 }}} 
    683  
    684 In total, the static_graph_adapter version performed 17 instructions with 4 loads, 3 stores, and 3 branches.  The adjacency_list_adapter version performed 25 instructions with 12 loads, 4 stores, and 3 branches.  We see that there is a cost associated with using an adjacency list graph vs. a compressed sparse row graph. 
     679       Loop summary: 4 loads, 0 stores, 0 floating point operations 
     680                4 instructions, needs 45 streams for full utilization 
     681                pipelined 
     682}}} 
     683 
     684In total, the static_graph_adapter version performed 17 instructions with 4 loads, 3 stores, and 3 branches.  The adjacency_list_adapter version performed 22 instructions with 9 loads, 4 stores, and 3 branches.  We see that there is a cost associated with using an adjacency list graph vs. a compressed sparse row graph.