This chapter is from the book
This chapter is from the book
This chapter is from the book
3.9 Parallel Compilation Time
Now that we have a generic topological sort and DFS, we are ready to solve the problem of finding how long the compilation will take on a parallel computer. First, we perform a topological sort, storing the results in the topo_order vector. We pass the reverse iterator of the vector into topo_sort() so that we end up with the topological order (and not the reverse topological order).
std::vector<vertex t> topo_order(num_vertices(g)); topo sort(g, topo order.rbegin(), color map);
Before calculating the compile times we need to set up the distance map (which we are using to store the compile time totals). For vertices that have no incoming edges (we call these source vertices), we initialize their distance to zero because compilation of these makefile targets can start right away. All other vertices are given a distance of infinity. We find the source vertices by marking all vertices that have incoming edges.
Graph_traits<file_dep_graph2>::vertex_iterator i, I_end; Graph_traits<file_dep_graph2>::adjacency iterator_vi, vi_end; // find source vertices with zero in-degree by marking all verticeswith incoming edges for (tie(i, I_end) = vertices(g); i != I_end; ++i) color_map[*i] = white_color; for (tie(i, I_end) = vertices(g); i != I_end; ++i) for (tie(vi, vi_end) = adjacent_vertices(*i, g); vi != vi_end; ++vi) color_map[*vi] = black_color; // initialize distances to zero, or for source vertices to the
Now we are ready to compute the distances. We go through all of the vertices stored in topo order, and for each one we update the distance (total compile time) for each adjacent vertex. What we are doing here is somewhat different than what was described earlier. Before, we talked about each vertex looking "up" the graph to compute its distance. Here, we have reformulated the computation so that instead we are pushing distances "down" the graph. The reason for this change is that looking "up" the graph requires access to in-edges, which our graph type does not provide.
std::vector<vertex_t>::iterator ui;
for (ui = topo_order.begin(); ui != topo_order.end(); ++ui) {
vertex_t u = *ui;
for (tie(vi, vi_end) = adjacent_vertices(u, g); vi != vi_end; ++vi)
if (distance_map[*vi] < distance_map[u] + compile_cost_map[*vi])
distance_map[*vi] = distance_map[u] + compile_cost_map[*vi];
}
The maximum distance value from among all the vertices tells us the total parallel compile time. Again we use graph_property_iter_range to create property iterators over vertex distances. The std::max element() function does the work of locating the maximum.
Graph_property_iter_range<file_dep_graph2,
The output is
total (parallel) compile time: 11.9
Figure 3.4 shows two numbers for each makefile target: the compile cost for the target and the time at which the target will finish compiling during a parallel compile.
){kind=link}
Figure 3.4 For each vertex there are two numbers: compile cost and accumulated compile time. The critical path consists of black lines.