wiki:PropertyMaps

Property maps associate properties to vertices and edges. The library provides an id property map for both vertices and edges, and it provides a mechanism for the user to create additional property maps.

Example Graph

The examples in this tutorial all use the following graph.

Property Map Functions

There are three functions defined to access property maps. The first two are global functions.

value_type
get(const property_map& p, vertex_descriptor v)
Returns the value associated with v.

void
put(property_map& p, vertex_descriptor v, value_type val)
Sets the value associated with v to val.

The third is a member function of property maps.

value_type&
operator[](vertex_descriptor v)
Returns a reference to the value associated with v.

For map property maps, the functions get() and put() are cheaper and parallelize better than operator[]. Thus, get() and put() should be preferred over operator[] when writing generic code that uses property maps whenever possible. One instance where operator[] must be used is if you need to lock on the value in the property map using mt_incr() or mt_readfe() / mt_write().

Vertex and Edge Id Maps

The id maps convert from a vertex or edge to their corresponding ids. Here is code that shows getting vertex and edge id maps for the graph g and using it to print out the edges in the graph, where printing an edge involves printing the edge id and each of its vertex ids. The complete code for this example is at tutorial/property_maps1.cpp.

  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
  edge_id_map<Graph> eid_map = get(_edge_id_map, g);

  edge_iterator edgs = edges(g);
  size_type size = num_edges(g);
  for (size_type i = 0; i < size; ++i)
  {
    edge_descriptor e = edgs[i];

    size_type eid = get(eid_map, e);
    size_type uid = get(vid_map, source(e, g));
    size_type vid = get(vid_map, target(e, g));

    printf("%lu: (%lu,%lu)\n", eid, uid, vid);
  }

The first two lines get the vertex and edge id maps. The next two lines get an edge_iterator and the number of edges so we can iterate over all the edges. Inside the body of the for loop, we get the edge_descriptor, get its id, and get the ids of its source and target vertices. Finally, the ids are printed out.

To compile and run this example on the XMT, issue the following commands from the tutorial directory

c++ -I.. -o property_maps1 property_maps1.cpp
mtarun -m <num processors> property_maps1

The output should look like

0: (0,1)
1: (0,2)
2: (1,2)
3: (1,3)
4: (2,4)
5: (3,4)
6: (3,5)
7: (4,5)

User-defined Vertex Array Property Map

Users can also create their own property maps. A user defined property map wraps around a data structure to perform the translation between the vertex or edge object and a value in the data structure. To use a property map a user must first declare the underlying data structure and then declare the property map.

Let's do an example where we create an array property map that stores boolean values indicating if a vertex id is divisible by three and then use that property map to print out the ids of the vertices that are divisible by three. The complete code for this example is at tutorial/property_maps2.cpp.

Here is the code to create and initialize the property map.

  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);

  bool div_by_3[numVerts];

  array_property_map<bool, vertex_id_map<Graph> >
    divisible_by_3(div_by_3, vid_map);

  // Find the vertices whose id is divisible by 3.
  vertex_iterator verts = vertices(g);
  size_type order = num_vertices(g);
  for (size_type i = 0; i < order; ++i)
  {
    vertex_descriptor v = verts[i];
    size_type vid = get(vid_map, v);
    put(divisible_by_3, v, vid % 3 == 0);
  }

The first line gets the vertex id map. The second line declares a boolean array where the results will be stored. The third line creates a property map that wraps around the array. The array_property_map type takes two type templates: the type of the underlying array, and the type of the object that translates between the vertex or edge and the entry in the array. This will almost always be either a vertex or edge id map. The array_property_map constructor takes two parameters: the underlying C-style array (or dynamic_array) and the object that does the translation. The next several lines do the iteration. The first two lines in the loop body get the vertex descriptor and its id. The last line assigns a value to the array property map for vertex v.

Here is the code to print out the vertices that are divisible by three.

  // Print the vertices whose id is divisible by 3.
  for (size_type i = 0; i < order; ++i)
  {
    vertex_descriptor v = verts[i];
    size_type vid = get(vid_map, v);

    if (get(divisible_by_3, v)) printf("%lu  ", vid);
  }
  printf("\n");

The important line is the last in the loop body. That line tests the property map to see if a vertex is divisible by three. If it is, the vertex's id is printed out.

Now, let's look at the canal output for the code that initializes the property map. We see that the compiler automatically parallelized the loop. So, vertex array property maps with compressed_sparse_row_graph parallelize just fine.

        |   // Find the vertices whose id is divisible by 3.
        |   vertex_iterator verts = vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_iterator mtgl::vertices<T1> inlined
        |   size_type order = num_vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::num_vertices<T1> inlined
        |   for (size_type i = 0; i < order; ++i)
        |   {
        |     vertex_descriptor v = verts[i];
++ function T1 mtgl::detail::csr_vertex_iterator<T1, T2>::operator [] inlined
        |     size_type vid = get(vid_map, v);
++ function T2 mtgl::get<T1, T2, T3> inlined
   22 P |     put(divisible_by_3, v, vid % 3 == 0);
++ function void mtgl::put<T1, T2, T3, T4> inlined
        |   }

To compile and run this example on the XMT, issue the following commands from the tutorial directory

c++ -I.. -o property_maps2 property_maps2.cpp
mtarun -m <num processors> property_maps2

The output should look like

0 3

There are six vertices in the graph with ids of 0 to 5. So, 0 and 3 are the only ids that are divisible by 3.

User-defined Edge Array Property Map

Now, let's do a more complicated example that uses edge id maps. We want to create an edge property map that will store the lowest degree of the edge's two vertices. We will do this using two different iteration schemes and using an array property map initialized with a dynamic_array. The complete code for this example is at tutorial/property_maps3.cpp.

The following code shows how to declare the property map.

  size_type order = num_vertices(g);
  size_type size = num_edges(g);

  edge_id_map<Graph> eid_map = get(_edge_id_map, g);

  // Declare the dynamic_array and set it to the appropriate size.
  dynamic_array<size_type> lowest_degree_array;
  lowest_degree_array.resize(size);

  // Declare the property map.
  array_property_map<size_type, edge_id_map<Graph> >
    lowest_degree(lowest_degree_array, eid_map);

The first two lines get the number of vertices and edges in g. The third line gets an edge id map for g. The next two lines declare a dynamic_array and set it to be of size the number of edges. The last line declares the property map.

The values in the property map need to be initialized to 0, and it is done as follows.

  // Set the lowest degree property map to 0.
  edge_iterator eIter = edges(g);
  #pragma mta assert nodep
  for (size_type i = 0; i < size; ++i) lowest_degree[eIter[i]] = 0;

The first iteration scheme is to iterate over the out edges of each vertex in the graph.

  // For each edge store the lower degree of its endpoints.
  // Loop using double loop with out_edge_iterator.
  vertex_iterator vIter = vertices(g);
  #pragma mta assert nodep
  for (size_type i = 0; i < order; ++i)
  {
    vertex_descriptor u = vIter[i];

    size_type u_deg = out_degree(u, g);
    out_edge_iterator oeIter = out_edges(u, g);
    #pragma mta assert nodep
    for (size_type j = 0; j < u_deg; ++j)
    {
      edge_descriptor e = oeIter[j];

      vertex_descriptor v = target(e, g);
      size_type v_deg = out_degree(v, g);

      size_type val = u_deg < v_deg ? u_deg : v_deg;
      put(lowest_degree, e, val);
    }
  }

The first three lines get a vertex iterator and loop over the vertices in the graph. The first three lines of the outer loop body get the current vertex, its out degree, and an iterator for its out edges. The first three lines of the inner loop body get the current edge, its target vertex, and the out degree of the target vertex. The last two lines find the lowest degree of either of the edge's vertices and store that value in the property map.

Notice the nodep assert statements for both of the loops. Sometimes, nodep pragmas are required when using property maps for the compiler to parallelize the loop. This is true when using edge array property maps with compressed_sparse_row_graph.

Looking at the canal output, we see that the compiler automatically parallelized the loop and performed a manhattan loop collapse.

           |   // For each edge store the lower degree of its endpoints.
           |   // Loop using double loop with out_edge_iterator.
           |   vertex_iterator vIter = vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_iterator mtgl::vertices<T1> inlined
           |   #pragma mta assert nodep
           |   for (size_type i = 0; i < order; ++i)
           |   {
           |     vertex_descriptor u = vIter[i];
++ function T1 mtgl::detail::csr_vertex_iterator<T1, T2>::operator [] inlined
           | 
   33 P    |     size_type u_deg = out_degree(u, g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::out_degree<T1> inlined
   33 P    |     out_edge_iterator oeIter = out_edges(u, g);
++ function mtgl::compressed_sparse_row_graph<T1>::out_edge_iterator mtgl::out_edges<T1> inlined
           |     #pragma mta assert nodep
           |     for (size_type j = 0; j < u_deg; ++j)
           |     {
   36 PP:m |       edge_descriptor e = oeIter[j];
++ function mtgl::detail::csr_edge_adapter<T1, T2> mtgl::detail::csr_out_edge_iterator<T1, T2>::operator [] inlined
           | 
           |       vertex_descriptor v = target(e, g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_descriptor mtgl::target<T1> inlined
   36 PP:m |       size_type v_deg = out_degree(v, g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::out_degree<T1> inlined
           | 
   36 PP:m |       size_type val = u_deg < v_deg ? u_deg : v_deg;
   36 PP:m |       put(lowest_degree, e, val);
++ function void mtgl::put<T1, T2, T3, T4> inlined
           |     }
           |   }

The second iteration scheme is to iterate over all the edges in the graph.

  // For each edge store the lower degree of its endpoints.
  // Loop using double loop with out_edge_iterator.
  #pragma mta assert nodep
  for (size_type i = 0; i < size; ++i)
  {
    edge_descriptor e = eIter[i];
    vertex_descriptor u = source(e, g);
    vertex_descriptor v = target(e, g);

    size_type u_deg = out_degree(u, g);
    size_type v_deg = out_degree(v, g);

    size_type val = u_deg < v_deg ? u_deg : v_deg;
    put(lowest_degree, e, val);
  }

The first three lines get an edge iterator and loop over the edges in the graph. The first three lines of the loop body get the current edge and its source and target vertices. The next two lines get the degree of the source and target vertices. The last two lines find the lowest degree of either of the edge's vertices and store that value in the property map.

Notice that again we have to use a nodep assert statement to get the compiler to parallelize the loop.

Looking at the canal output, we see that the compiler automatically parallelized the loop.

           |   // For each edge store the lower degree of its endpoints.
           |   // Loop using double loop with out_edge_iterator.
           |   #pragma mta assert nodep
           |   for (size_type i = 0; i < size; ++i)
           |   {
   42 P    |     edge_descriptor e = eIter[i];
++ function mtgl::detail::csr_edge_adapter<T1, T2> mtgl::detail::csr_edge_iterator<T1, T2>::operator [] inlined
           |     vertex_descriptor u = source(e, g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_descriptor mtgl::source<T1> inlined
           |     vertex_descriptor v = target(e, g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_descriptor mtgl::target<T1> inlined
           | 
   42 P    |     size_type u_deg = out_degree(u, g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::out_degree<T1> inlined
   42 P    |     size_type v_deg = out_degree(v, g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::out_degree<T1> inlined
           | 
   42 P    |     size_type val = u_deg < v_deg ? u_deg : v_deg;
   42 P    |     put(lowest_degree, e, val);
++ function void mtgl::put<T1, T2, T3, T4> inlined
           |   }

To compile and run this example on the XMT, issue the following commands from the tutorial directory

c++ -I.. -o property_maps3 property_maps3.cpp
mtarun -m <num processors> property_maps3

The output should look like

Using out edges:
0: 2
1: 1
2: 1
3: 2
4: 1
5: 1
6: 0
7: 0

Using edges:
0: 2
1: 1
2: 1
3: 2
4: 1
5: 1
6: 0
7: 0

Looking at the example graph, we see that these results do indeed give the lowest degree of each edge's two vertices.

User-defined Vertex Map Property Map

Now, let's do an example that shows using map property maps and the performance impact that comes with using them. We're going to rewrite tutorial/property_maps2.cpp to use a map property map and compare the canal output. The new code can be found at tutorial/property_maps4.cpp. The first change is that we need to include the xmt_hash_table.

#include <mtgl/xmt_hash_table.hpp>

The next change is to declare an xmt_hash_table and map_property_map instead of a C-style array and array property map. Here is the code to do that. Note that the map_property_map takes the same template and function parameters as the array_property_map. The parameter passed to the constructor of the hash table is the size of the table. The xmt_hash_table uses open addressing and doesn't provide automatic resizing. Both of these design decisions increase the performance of the table. We set the initial size so that the hash table will be about two-thirds full as a good balance of performance and space.

  xmt_hash_table<size_type, bool> div_by_3(static_cast<int>(1.5 * numVerts));

  map_property_map<bool, vertex_id_map<Graph> >
    divisible_by_3(div_by_3, vid_map);

Now, let's look at the loop that finds the vertex ids divisible by 3. The only difference here is the addition of the assert parallel pragma before the loop. Calling put() on a map_property_map calls the update_insert() function of the xmt_hash_table. When this function is in a loop, the assert parallel pragma is required to parallelize the loop.

  // Find the vertices whose id is divisible by 3.
  vertex_iterator verts = vertices(g);
  size_type order = num_vertices(g);
  #pragma mta assert parallel
  for (size_type i = 0; i < order; ++i)
  {
    vertex_descriptor v = verts[i];
    size_type vid = get(vid_map, v);
    put(divisible_by_3, v, vid % 3 == 0);
  }

Consider the canal output for the loop.

         |   // Find the vertices whose id is divisible by 3.
         |   vertex_iterator verts = vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_iterator mtgl::vertices<T1> inlined
         |   size_type order = num_vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::num_vertices<T1> inlined
         |   #pragma mta assert parallel
         |   for (size_type i = 0; i < order; ++i)
         |   {
         |     vertex_descriptor v = verts[i];
++ function T1 mtgl::detail::csr_vertex_iterator<T1, T2>::operator [] inlined
         |     size_type vid = get(vid_map, v);
++ function T2 mtgl::get<T1, T2, T3> inlined
   25 DX |     put(divisible_by_3, v, vid % 3 == 0);
++ function void mtgl::put<T1, T2, T3> inlined
         |   }

The "D" means that the compiler parallelized the loop because of the assert parallel statement but that it found a dependency in the loop. This is okay as we know that there are no dependencies in the loop. On the surface this seems just as good as using an array_property_map. However, looking at the loop annotations, we see that things are far different.

Here are the loop annotations for the version using the array_property_map. The loop is pipelined, and there are only 4 instructions with 1 store.

Loop  22 in main at line 46 in loop 19
       Loop summary: 0 loads, 1 stores, 0 floating point operations
        4 instructions, needs 45 streams for full utilization
        pipelined
       1 instructions added to satisfy dependences

Here are the loop annotations for the version using the map_property_map. This loop is not pipelined, and it has 37 instructions with 11 loads, 4 stores, and 10 branches. This is a significant change in cost compared to the array_property_map version. The lesson to learn here is that having noncontiguous ids for vertices or edges (which require map_property_maps) has a pretty large cost when using property maps. The graphs in the MTGL stick to contiguous ids to avoid this extra cost.

Loop  28 in main at line 48 in loop 25
       Loop not pipelined: not structurally ok
       Loop summary: 37 instructions, 0 floating point operations
        11 loads, 4 stores, 0 reloads, 0 spills, 10 branches, 0 calls

To compile and run this example on the XMT, issue the following commands from the tutorial directory

c++ -I.. -o property_maps4 property_maps4.cpp
mtarun -m <num processors> property_maps4

The output should look like

0 3

As mentioned before, loops using the put() function for a map_property_map need an assert parallel pragma to parallelize. Loops using the get() function for a map_property_map usually only require an assert node pragma, though, as get() calls the lookup() function of the xmt_hash_table which usually only requires an assert nodep to be parallelized in a loop. Using the [] operator on a map_property_map, however, calls the [] operator of the xmt_hash_table. An assert parallel pragma is required to parallelize loops including that operator, and the operator is more expensive than either of the other functions called by get() or put().

User-defined Vertex Property Map

The classes vertex_property_map and edge_property_map are defined by the graph API to allow for generic programming with property maps. The types are defined to be an array_property_map if the vertices and edges use contiguous ids or a map_property_map otherwise. They also encapsulate the declaration, initialization, and destruction of the underlying data structures.

Let's rewrite tutorial/property_maps2.cpp to use a vertex_property_map. The new code can be found at tutorial/property_maps5.cpp. The only difference is in the declaration of the property map. Here is code showing how to declare the vertex_property_map. Note that you don't have to declare the underlying array or hash table to hold the data. The vertex_property_map takes care of that. The class takes two template parameters. The first is the graph type, and the second is the type of the property. The graph must be passed to the constructor of the map.

  vertex_property_map<Graph, bool> divisible_by_3(g);

Now, let's look at the canal output. Since we are using the compressed_sparse_row_graph, the vertex_property_map is set to be an array_property_map. We see that the loop is automatically parallelized, is pipelined, and performs 4 instructions with 1 store. This is the same as when we used the array_property_map.

        |   // Find the vertices whose id is divisible by 3.
        |   vertex_iterator verts = vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::vertex_iterator mtgl::vertices<T1> inlined
        |   size_type order = num_vertices(g);
++ function mtgl::compressed_sparse_row_graph<T1>::size_type mtgl::num_vertices<T1> inlined
        |   for (size_type i = 0; i < order; ++i)
        |   {
        |     vertex_descriptor v = verts[i];
++ function T1 mtgl::detail::csr_vertex_iterator<T1, T2>::operator [] inlined
        |     size_type vid = get(vid_map, v);
++ function T2 mtgl::get<T1, T2, T3> inlined
   22 P |     put(divisible_by_3, v, vid % 3 == 0);
++ function void mtgl::put<T1, T2, T3, T4> inlined
        |   }
Loop  22 in main at line 43 in loop 19
       Loop summary: 0 loads, 1 stores, 0 floating point operations
		4 instructions, needs 45 streams for full utilization
		pipelined
       1 instructions added to satisfy dependences

To compile and run this example on the XMT, issue the following commands from the tutorial directory

c++ -I.. -o property_maps5 property_maps5.cpp
mtarun -m <num processors> property_maps5

The output should look like

0 3

Conclusions

We have seen in this tutorial how to use vertex and edge id maps, user-defined array property maps, user-defined map property maps, and user-defined vertex and edge property maps. The compiler is able to parallelize loops using property maps effectively, but sometimes it requires a nodep or assert parallel statement. We have also seen that the compiler is able to effectively parallelize the out_edge_iterator and the edge_iterator.

Attachments