MCFX: a parallel programming framework for non-trivial task based parallelism
MCFX was a skunk project I did with Liang Chen and Deepankar Bairagi at Sun. It is a C++ programming framework that aims to make writing a limited domain of parallel applications more efficiently. There are many different ways to describe what MCFX really is. Since the core of the MCFX framework is a task scheduler, I will explain what MCFX can do from the point of view of a task scheduler.
Before describing the task scheduler in MCFX, let’s take a look at Cilk, Thread Building Block and OpenMP 3.0. All of them have a task scheduler at the core. As pioneered by Cilk, these schedulers aims to improve the efficiency of parallel execution by using a unfair and cache friend scheduling scheme. Which task being picked to execute or stolen is, generally speaking, based on the execution path of the program and data affiliation. This scheme serves the purpose of being a runtime for general parallel applications well. However, tasks are individual items and their relationship that exist in the application level are not exposed to the scheduler.
MCFX scheduler is different. The scheduling decision of MCFX is based not only on the execution history of the program and cache behavior, but also on the relationship between the tasks. Tasks can have priorities; the execution of one task can cancel the execution of another task (or a set of tasks); tasks can have dependencies amongst themselves; certain tasks can be allowed to executed multiple times. These properties are exposed to the scheduler and become the critical part of the scheduling decision.
Why would we want to do this? Because in many applications, the jobs that can be executed concurrently do have such properties. And sometimes, these jobs can be executed correctly in parallel only when the non-trivial concurrency are being honored by the scheduler. Such jobs appear quite frequently in applications that use branch and bound algorithms, A* algorithms, etc..
MCFX is designed for such applications. It has a task scheduler for non-trivial parallel tasks at its core and provides high level abstract classes and templates for end users to describe the non-trivial tasks.
Liang is going to present our work at this year’s International Supercomputing Conference. A full description of MCFX will be available in the proceedings of this conference.
