MCP: Modified Critical-Path Algorithm

What is MCP?

MCP (Modified Critical-Path) algorithm [1] schedules Directed Acyclic Graphs (DAGs) with communication costs to a bounded number of processors. It is one of the six most popular algorithms in this category and performs the best among them [2]. A detailed programming code of MCP is provided here. This algorithm implementation can be used as a basis for comparison of newly invented algorithms in terms of schedule length, complexity, and running time. MCP was also used as the basis of parallel scheduling of DAGs [3] and as the back-end of project CASCH [4].

Glossary

• MCP --- Modified Critical-Path
• DAG --- Directed Acyclic Graph
• CP --- Critical Path
• ALAP --- As-Late-As-Possible
• w(n) --- Computation weight of node n
• blevel(n) --- bottom level, the length of the longest path (including the node weights and edge weights) from node n to the exit node, including node n itself [5]
• flevel(n) --- floor level, blevel(n)-w(n)

Source Code

• In C++ with STL, compiled with g++ under Solaris.
• If the executable file is "mcp", input graph file is "tstgau", output file "outgau", and the number of PEs is 2, the code will run as:
  "mcp 2 tstgau > outgau"
  • a sample input file
  • a sample output file with 2 target PEs

Paper Draft

• MCP Revisited

Bibliography

• [1] M.Y. Wu and D. D. Gajski, "Hypertool: A Programming Aid for Message-passing Systems", IEEE Trans. Parallel and Distributed Systems, Vol.1, No.3, pages 330-343, July 1990.
• [2] Y.K. Kwok and I. Ahmad, "Benchmarking and Comparison of the Task Graph Scheduling Algorithms", Journal of Parallel and Distributed Computing, Vol.59, No.2, pages 381-422, 1999.
• [3] M.Y. Wu and W. Shu, "On Parallelization of Static Scheduling Algorithms", IEEE Transactions on Software Engineering, Vol.23, No.8, pages 517-528, August 1997.
• [4] I. Ahmad, Y.K. Kwok, M.Y. Wu, and W. Shu, "CASCH: A Software Tool for Automatic Parallelization and Scheduling of Programs on Multiprocessors", IEEE Concurrency, Vol.8, No.4, pages 21-33, October 2000.
• [5] T. Yang and A. Gerasoulis, PYRROS: Static Task Scheduling and Code Generation for Message-passing Multiprocessors", The 6th ACM Int'l Conf. on Supercomputing, July 1992.