Runtime

Bubblesched

Summer 2010 internships

More information

Back to the Marcel page

Contact

For any questions regarding BubbleSched, please contact Olivier Aumage and Samuel Thibault.

OpenMP bubbles: ForestGOMP

We developped a patch against GNU OpenMP, the GCC 4.2 support for OpenMP, which is now known as ForestGOMP. It permits to use BubbleSched very easily with nested OpenMP applications: nested parallel sections are simply expressed in terms of bubbles and permit to improve the speedup.

Bubble-based scheduling

Exploiting full computational power of current more and more hierarchical multiprocessor machines requires a very careful distribution of threads and data among the underlying non-uniform architecture, so as to minimize the number of remote memory accesses, to favor cache affinities, or to guarantee fast completion of synchronization steps. Unfortunately, most operating systems only provide a poor thread scheduling API that does not allow applications to transmit valuable scheduling hints to the system.

We propose to extend classical thread schedulers with high-level abstractions called Bubbles, which are used to dynamically describe relations betweens threads in order to improve applications' performance in a portable way. Programmers can model the relationships between the threads of their applications using (nested) bubbles. The concept of bubbles can be understood as a coset with respect to a specific affinity relation, and bubble nesting expresses refinement of a relation by another one. This lets express relations like data sharing, collective operations, good behavior with regards to co-scheduling on a SMT processor, or more generally a particular scheduling policy need (serialization, preemption, gang scheduling, etc.).

Example

BubbleSched is actually a framework that allows scheduling experts to implement and experiment with powerful user-level bubble-based thread schedulers. It provides a powerful API for dynamically distributing bubbles among the machine in a high-level, portable, and efficient way. Programmers can hence focus on algorithmic issues rather than on nasty technical details.

A documentation of the API can be found here

BubbleSched in Action

With BubbleSched, experts can not only develop their own portable scheduling policy, they can also debug and tune their scheduler thanks to integrated tracing tools. Programs using the BubbleSched can generate traces that can be analyzed offline to inspect the dynamic behavior of the scheduler, thanks to a tool which turns them into animations like below.

BubbleGum

BubbleSched is shipped with BubbleGum, a tool which permits scheduling experts to quickly build several bubble examples and test their bubble schedulers on them.