wiki:FirstMtglExample

Version 1 (modified by jberry, 10 years ago) (diff)

--

There are already several algorithms in the MTGL that run well on the Cray MTA-2. These live in the "mtgl" directory, which uses autoconf to configure and build. If you simply can't wait, you build that with

autoreconf -f -i -s

./configure cd test

make <test_executable>

Where one of the test_executables is "cc_test."

However, we'll start here without worrying about configuration or building. Rather, we'll take an existing "C" code, write (more accurately, just use) an adapter [[media:static_graph_adapter.hpp]] for its graph data structure, and "MTGL-ize" key portions of the code. Consider the data structure below. This is a typical compressed sparse row adjacency matrix representation of a graph, as implemented by Kamesh Madduri. It is useful when the graph doesn't change often, hence the name "static graph." Algorithms written with the MTGL will work on arbitrary graph types, including those intended for more dynamic situations, but we'll focus this tutorial on the simple structure below.

[[image:static_graph_nw.jpg|JPG]]

Here is C code ([[media:static_graph.h]]) that defines and initializes this data structure:

[jberry@sancha test]$ more static_graph.h #ifndef STATIC_GRAPH_H #define STATIC_GRAPH_H typedef struct {

int m; int n; int* end_points; the adjacency array int* index; the index array

} static_graph; void init_graph(static_graph* G, int n, int m,

int* srcs, int* dests, int undirected);

#endif [jberry@sancha test]$

You will find this file in the mtgl/test subdirectory, along with [[media:static_graph.c]], which contains the init_graph function. Here is a simple test program ([[media:test_static_graph.c]]) that builds a directed graph (a directed triangle), then prints its adjacency structure.

[jberry@sancha test]$ more test_static_graph.c #include "static_graph.h" void print(static_graph *g) {

int i, j; for (i=0; i<g->n; i++) {

int begin = g->index[i]; int end = g->index[i+1]; printf("%d: ", i); for (j=begin; j<end; j++) {

printf("%d ", g->end_points[j]);

} printf("\n");

}

} int main() {

int srcs[] = {0,1,2}; int dests[] = {1,2,0}; static_graph G; init_graph(&G, 3,3, srcs,dests, 0); print(&G); return 0;

} [jberry@sancha test]$ gcc static_graph.c test_static_graph.c [jberry@sancha test]$ ./a.out 0: 1 1: 2 2: 0 [jberry@sancha test]$

Now we have a complete, albeit small, example of a C code that implements a graph algorithm. In order to "MTGL-ize" this code, we need to avoid any explicit use of the underlying data structure. For example, the "print" function above uses the "index" and "end_points" fields of "static_graph," and therefore can be used only with this data structure. To make that function generic, we instantiate an adapter object and use its API to access the graph. The following program uses MTGL primitives to print the graph. We'll consider it ([[media:test_static_graph1.cpp]]) first in its entirety, then dissect it.

[jberry@sancha test]$ more test_static_graph1.cpp #include "static_graph.h" #include <mtgl/static_graph_adapter.hpp> using namespace mtgl; void print(static_graph_adapter& g) {

typedef graph_traits<static_graph_adapter>::vertex_descriptor vertex_descriptor_t; typedef graph_traits<static_graph_adapter>::adj_vertex_iterator adj_iterator_t; int i, j; int n = g.get_order(); adj_iterator_t begin_v, end_v; vertex_id_map<static_graph_adapter> vid_map = get(_vertex_id_map,g); for (i=0; i<n; i++) {

vertex_descriptor_t v = g.get_vertex(i); tie(begin_v,end_v) = adj_vertices(v,g); int deg = degree(v,g); int vid = get(vid_map, v); printf("%d: ", vid); for (j=0; j<deg; j++) {

begin_v.set_position(j); vertex_descriptor_t neighbor = *begin_v; int nid = get(vid_map, neighbor); printf("%d ", nid);

} printf("\n");

}

} int main() {

int srcs[] = {0,1,2}; int dests[] = {1,2,0}; static_graph G; init_graph(&G, 3,3, srcs,dests, 0); static_graph_adapter ga(&G); print(ga); return 0;

} [jberry@sancha test]$ g++ -I/home/jberry/mtgl -I. static_graph.c test_static_graph1.cpp [jberry@sancha test]$ ./a.out 0: 1 1: 2 2: 0 [jberry@sancha test]$

Those familiar with the Boost Graph Library (BGL) will note a Boost-like look and feel, though they will also note some usage differences. These relate to computing on the MTA-2/XMT, and will be explained in time. Now, let us break down the test_static_graph1.cpp example. The MTGL include files are accessed through an "mtgl" directory, as Boost Graph Library files are accessed with "boost/graph/foo.hpp." Perhaps some time in the future, the MTGL might be merged into BGL. However, MTA-2/XMT compatibility issues prevent this for the moment. The static_graph_adapter.hpp file is included in the MTGL distribution as an example, but typically users will write their own adapters and include them from user space.

The MTGL has its own namespace, so the first thing is to use that.

#include <mtgl/static_graph_adapter.hpp> using namespace mtgl;

Our print function now takes a static_graph_adapter. This is put to use immediately as it provides the compiler with information about the types of graph primitives such as vertices and edges, and about iterators. In the MTGL, all iterators are required to provide random access, as MTA-2/XMT threads will need to find the iterations intended for them.

void print(static_graph_adapter& g) {

typedef graph_traits<static_graph_adapter>::vertex_descriptor vertex_descriptor_t; typedef graph_traits<static_graph_adapter>::adj_vertex_iterator adj_iterator_t;

The "graph_traits" class is a BGL idiom that provides a standard way to query graph adapters for pertinent types and iterators. The code above is not truly generic since we specify static_graph_adapter rather than leaving that as a template argument. Check the mtgl distribution for mtgl_adapter.hpp, which contains a completely generic print function.

We have now discovered the type of a "vertex_descriptor," which in BGL lingo means a handle for a vertex. We also know the type of iterator that we'll use to find the adjacencies of a vertex. Peeking into the static_graph_adapter class, we see that this is merely an "int" -- the index of the vertex in static_graph's "index" array.

class static_graph_adapter { public:

typedef int vertex_descriptor;

Turning our attention back to test_static_graph1.cpp, we begin using the static_graph_adapter API by requesting the number of vertices in the graph via the "get_order" method. Once we know the order, we'll use a "for" loop to iterate through the vertices. This is not the way things would be done in the BGL. There, we would say "for (tie(begin_v, end_v) = vertices(ga); begin_v != end_v; begin_v++)", where "begin_v" and "end_v" are vertex iterators. However, this is not an MTA-friendly loop. The MTA compiler matches very simple templates to determine which loops can be parallelized. Therefore, throughout the MTGL, you will find requests for counts of objects, followed by simple "for" loops that tell the MTA compiler exactly how many iterations are required.

int n = g.get_order();

Given a vertex, however, we will use more BGL-like code. The adjacencies of a vertex will be traversed using an "adj_iterator_t" (retrieved from the static_graph_adapter class), along with the Boost "tie" method, which initializes beginning and ending iterators to traverse the adjacency structure of one vertex. Recall that in this generic code, we can't be sure exactly what a vertex descriptor actually is. Since we can't rely on it being a simply integer index, we'll have to ask for its id. This is done using a "property map," which in turn is retrieved by the generic "get" function. Both of these are inspired by the BGL, but are custom MTGL implementations. The BGL property map construct is quite detailed, the MTA-2/XMT compiler does not yet compile Boost reliably out of the box. Hopefully this will change with time, and we will be able to use native Boost property maps.

As for now, though, we'll use MTGL imitations of the BGL property map mechanism. In particular, the MTGL expects graph adapters to provide a "vertex_id_map" in order to map vertex_descriptors to unique identifiers and a couple of other maps that will be described later (though you can look through static_graph_adapter.hpp to find them). In the BGL, there is a distinction between native property maps, which are tied directly into the graph representation, and auxiliary property maps, which are added by the user after graph creation. There is currently no such distinction in the MTGL. In the call to "get," the identifier "_vertex_id_map" is simply a hardcoded MTGL tag indicating which map to return.

adj_iterator_t begin_v, end_v; vertex_id_map<static_graph_adapter> vid_map = get(_vertex_id_map,g);

Now we loop through the vertices of the graph in MTGL (as opposed to BGL) style. There is some awkwardness here, as we must retrieve the vertex in question at each iteration. In a BGL program, we would use the indirection operator of an iterator to retrieve the next vertex. However, either alternative is handled effectively by the compiler. In our case, the "g.get_vertex(i)" call is inlined away by the compiler, and "v" is simply set to "i" logically, perhaps never to exist at run time.

for (i=0; i<n; i++) {

vertex_descriptor_t v = g.get_vertex(i); tie(begin_v,end_v) = adj_vertices(v,g); int deg = degree(v,g); int vid = get(vid_map, v); printf("%d: ", vid); for (j=0; j<deg; j++) {

begin_v.set_position(j); vertex_descriptor_t neighbor = *begin_v;

The "tie" function is a Boost idiom for initializing iterators to traverse a given range of iterations over some data structure. The MTGL provides a generic function "adj_vertices(v,g)" that returns a pair of iterators set to traverse v's adjacency structure, and "tie" initializes them gracefully. As noted before, a BGL program would now use the iterators in its loop control. This is elegant, but not MTA-friendly. We must find the number of iterators explicitly, so we'll use the generic function "degree(v,g)," loop explicitly.

TO BE CONTINUED

Attachments