March 31, 2020
// There are 3 meta phases of the Dynamic Programming (DP) algorithm. The input is a CostGraph, and the goal // is to compute the strategy for each operator in the CostGraph. // // Phase 1: Shrink the CostGraph using 6 operations, and record them in the order // Using for operations: Operator Elimination, Edge Elimination, Merge Elimination, and Contract Elimination, // each connected component in the CostGraph can be shrunk in to the final graph: u --> v. See the // interpretation of 6 operations in costmodel.h. // Phase 2: Search the cost_list in the final graph, and determine the optimal one // Create the cost_list for the final graph, and choose the optimal one: one the minimum quantity // COST_MODEL_ALPHA * memory_cost + COST_MODEL_BETA * communication_cost // Phase 3: Recover the original CostGraph, the determine strategy for each operator // After determining the optimal cost for the final graph, the algorithm recovers the original graph by applying // the 4 operations in the reverse order in the Phase 1. Because each operation decision contains the strategy, // the operators' strategies can be all determined.