Google Summer of Code 2011 に採択されました

どうもこんばんは! @laysakura です．

周りの方々からたくさんの助けを賜りながら，この度 Google Summer of Code 2011 に採択される運びとなりました．
とっても嬉しいです^^

今日から大体9月までの間， GCCのOpenMP実装をベターなものにしていくプロジェクトに取り組んでいきます．
このblogでも折りにつけて途中経過を報告していくつもりですので，どうぞよろしくお願いします．

おそらく最も情報量が多そうな，Proposalを晒しておきます．
来年以降に挑戦される方のご参考になれば嬉しいです．

Proposalへのリンク

以下，消えたときのためにコピペ
(書式が読みづらいのはご勘弁願います)

===

Email: XXX

Short description: GCC's implementation of OpenMP Task is slower compared to other implementations like that of Intel C Compiler, Cilk, and Nanos4. This project aims to give speed-up to `task' construct in libgomp. This will be done by migrating the implementation of Nanos4. Also, to make reasonable and sophisticated implementation, learning of many `task' implementations is involved in this project.

Additional info: http://gcc.gnu.org/ml/gcc/2011-04/msg00107.html
Proposal

The biggest goal for this project is to add speed-up to OpenMP Task in libgomp, GCC. Currently, the implementation of `task' in libgomp has two problems:

    `tied task' is slower than other implementations.
    See: Evaluating OpenMP 3.0 Run Time Systems on Unbalanced Task Graphs [PDF]
    `untied task' is not implemented.

First, I try to implement faster `tied task' in libgomp.
If this could be successfully done, I would also try to implement `untied task' in libgomp, which has not been implemented in it yet.

There are a lot of possible implementations for OpenMP Task since OpenMP doesn't specify how to deal with task scheduling in detail. For instance, should worker be on every CPU core or exist globally, should tasks be created in breadth-first or depth-first order, should queue be FIFO or LIFO.
Therefore, it is quite important to decide what kind of implementation is the best (at least better than current one in libgomp). So this project involves investigating and testing other existing implementations. NANOS group , which provides OpenMP runtime library called Nanos4, has conducted detailed evaluation of many `task' implementations. My objective during GSoC is to extend the survey presented in Evaluation of OpenMP Task Scheduling Strategies [PDF] in order to implement the different scheduling schemes in libgomp. After that, I will evaluate the GCC implementation of these schedulers over a set of task benchmarks, including the testsuite of libgomp and Barcelona OpenMP Tasks Suite (ref: Barcelona OpenMP Tasks Suite: A Set of Benchmarks Targeting the Exploitation of Task Parallelism in OpenMP [PDF]) to select the appropriate scheduler for libgomp.
About Myself

Name
    XXX
E-mail
    XXX
University
    The University of Tokyo, Japan
Position
    Undergraduate

Open Source Activities

    Would be an Emacs contributor for improving DocViewMode.
    Currently in the process of copyright assignment.
    See the discussion about my work.

Other Activities

    Implemented very simple C Compiler (PyCC)

Surroundings

This project is closely related to my graduation thesis, so I MUST try hard on it.

I have good advisers, not only the members of GCC ML but my teacher and senior associates.

Machine with 32 cores is accessible. It'll help testing so much.

Better libgomp `task' will help many researchers and programmers, including me, so I'm so motivated in this work.
Schedule
Milestone 0: (4/25 - May)

    Evaluate various implementations in Nanos4
    Read articles related to OpenMP Task
    Read the code of Nanos4 and understand the implementation

Milestone 1: week 1 - week 2

    Read the code of libgomp and understand the current implementation
    Specify where to fix in libgomp/

Milestone 2: week 3 - week 4

    Determine what kind of `tied task' implementation to migrate from Nanos4
    Start implementing new task scheduling in libgomp

Milestone 3: week 5

    Continue to implement the new task scheduling in libgomp

Milestone 4: week 6 - week 7

    Evaluate the new implementation

Milestone 5: week 8 (mid-term)

    Submit the new implementation of `tied task' and its evaluation
    Have the mentor examine the evaluation results

Milestone 6: week 9 - week 11
o If already succeeded in implementing `tied task'

    Start implementing `untied task'

o Otherwise

    Fix `tied task' implementation

Milestone 7: week 12
o If already started implementing `untied task'

    Finish the implementation of it
    Evaluation

o Otherwise

    Evaluation of `tied task' implementation

Milestone 13: week 13 (pencil down)

    Write helpful document about the implementation