## 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 vertices with 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 compile cost for (tie(i, I_end) = vertices(g); i != I_end; ++i) if (color_map[*i] == white_color) distance_map[*i] = compile_cost_map[*i]; else distance_map[*i] = 0;

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, vertex_distance_t>::iterator ci, ci_end; tie(ci, ci_end) = get_property_iter_range(g, vertex_distance); std::cout << "total (parallel) compile time: " << *std::max element(ci, ci end) << std::endl;

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.

**Figure 3.4 For each vertex there are two numbers: compile cost and
accumulated compile time. The critical path consists of black lines. **