Project #2: OpenMP Task Scheduling Visualization

In this project you will be working with LLVM OpenMP runtime library, which is also used in the commercial Intel compiler. The runtime is the part of the OpenMP implementation that your code is linked with, and that manages execution of an OpenMP program by multiple threads. When a compiler encounters an OpenMP directive, it generates code that makes calls to the runtime library. The compiler outlines sections of code that are to run in parallel into separate functions that can then be invoked in multiple threads. For instance, simple code like this

void foo()
{
    #pragma omp parallel
    {
        ... do something ...
    }
}

is converted into something that looks conceptually like this

static void outlinedFooBody()
{
    ... do something ...
}
void foo()
{
    __kmpc_fork_call(outlinedFooBody, (void*)0, …); // Not the real function name!
}

When encountering an OpenMP tasking construct, i.e., #pragma omp task, a task is generated and forwarded to the runtime for execution using work-stealing algorithm. The goal of this project is to visualize the scheduling of tasks among threads by creating a scheduling graph. You will need to modify the OpenMP runtime source codes that handle the task creation, scheduling and synchronizations and have the runtime to store task-scheduling information to memory buffers. By the time the execution finishes, those info stored in the memory buffer are dumped to a text file in DOT format, which can be visualized using DOT tool.

A task in the runtime is represented as objects of and kmp_task_t and kmp_taskdata_t, which are basically in the same memory location and you can use KMP_TASKDATA_TO_TASK to find the kmp_taskdata_t object from an kmp_task_t address. The kmp_taskdata_t object has the td_task_id field for uniquely representing a task. kmp_tasking.cpp is the file where operations such as task generation, push or pop tasks to the local queue, stealing of tasks and execution of tasks. The __kmp_omp_task, __kmp_steal_task, __kmp_push_task, __kmp_execute_tasks_template, and __kmp_remove_my_task methods are the main functions to implement those operations.

Development Setup

About runtime tracing

The runtime tracing, when being turned on, prints out tracing information of task execution that can help you understand the work-stealing algorithm. To enable tracing, you need to set KMP_A_DEBUG=<n> where n is necessary level of trace messages. For example, to get messages with level <=20: set KMP_A_DEBUG=20.

Schedule and submission in each phase (submit from Moodle) :

Phase Deadline Tasks Submission
1 03/17 OpenMP runtime study, motivations, and design of the implementation. In the report, you will describe OpenMP runtime architecture, the motivation and design of the schedule graph. Written report.
2 03/27 Initial graph generation for fib example Implementation, doc and evaluation report
3 04/17 Refine graph generation to include more complicated examples, tasks with dependency and information such as timing, and CPU counter info by using PAPI interface. Project presentation. Implementation, doc, evaluation report and presentation
4 04/24 Final project report due. Modified files, final report and presentation

Resources:

  1. DOT graph format, DOT visualization: xdot on Linux
  2. Read the source code from web browswer with cross-link and search(need VPN to access from off-campus): http://orion.ec.oakland.edu:8080/llvm/xref/projects/openmp/runtime/. E.g. code browser

Sections in your report:

  1. Introduction (introduce the background, motivation and contribution of the work)
  2. Motivation and Proposed Solution
  3. Implementation: which discusses how Intel OpenMP runtime works that are relevant to what you are doing, how do you implement, and the challenge and solution you faced while implementing the proposed solution.
  4. Experimental Results: show off your work using real results or figures.
  5. Related Work: discuss the similarity and differences of yours with others and why yours are better
  6. Conclusion: conclusion, implication and future work
  7. References

Your submission should include everything in one zipped package: the report in editable form, presentation slide and sources code/makefile, and a file that provides a summary of your changes to the original Intel OpenMP runtime.