Browse Prior Art Database

Method and Apparatus to Support Source Code Level Transformation in Work-Stealing Parallel Scheduling

IP.com Disclosure Number: IPCOM000205872D
Publication Date: 2011-Apr-06
Document File: 7 page(s) / 131K

Publishing Venue

The IP.com Prior Art Database

Abstract

This article introduces a new way to transform source code to enable work-stealing scheduling for fork-join style parallel applications. Two key technologies in the source to source transformation are invented , 1) dividing control flows to separated but linked frames to overcome the "switch" statement’s limitation in work-stealing slow path; 2) transforming "return" statement in all the frames to maintain the original semantic of the return.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 36% of the total text.

Page 01 of 7

Method and Apparatus to Support Source Code Level Transformation in Work-Stealing Parallel Scheduling

Multi-core based servers are becoming the mainstream systems to support the IT infrastructure . In order to leverage the underlying computation power, applications should execute in parallel. There are typically three types of parallel task scheduling approaches, Each task as one thread, Work Sharing, and Work Stealing, among which Work-Stealing has many advantages, such as automatic load balancing, and easy to scale to massive parallel.

However, in order to enable Work-Stealing scheduling in a typical parallel application, the original application should be transformed to Work-Stealing style, and connect the Work-Stealing runtime to do the parallel scheduling. The original execution path will be transformed into two clones
# Fast Clone: Never got stolen. Make bookmarks (continuation and stack status ) for other workers to steal
# Slow Clone: Executed by thief worker. Contain all fast/slow clones interaction procedures. Migrate work, restore stack status, and keep executing at the right place.

Also contains bookmark codes since it could be stolen

, too.

For a thief, it could re-execute the slow clone in any pre-bookmarked place (marked by PC, int type),

a switch.

One traditional transformation of application for work-stealing is on application byte-code or executable code directly. For example, Raghavan Raman, Compiler Support for Work-Stealing Parallel Runtime Systems, RICE UNIVERSITY. There are two big disadvantages
#

Very complex to analyze the byte-code to extract control logic

# Lose the opportunities to do further code optimization in source level

Another way is to transform in source code level.

limited cases of source code.

This disclosure provides a new way to transform the original application in source code level. In order to solve the "switch" limitation, it transform the execution path into different connected frames. In each frame, the "switch" could jump into any place.

And "switch" now appears in different frames

which is typically achieved by

But because "switch" cannot cross different code section, it can only transform

, so no cross block boundary violation again.

1



Page 02 of 7

class fib
pc:Int;

def fib_slow(n:Int, pc:Int):Int {
switch (pc){
case 0:
var t1:Int; var t2:Int;
if (n < 2) return 1;
SET_BOOKMARK(pc=1);
finish_slow(0);
case 1:
return t1 + t2;

}

class finish_body
pc:Int;

def finish_body_slow(pc:Int){
switch (pc){
case 0:
SET_BOOKMARK(pc=1);
t1 = async fib(n-1);
case 1:
SET_BOOKMARK(pc=2);
t2 = fib(n-2);
case 2:
...

}

class finish
pc:Int;

def finish_slow(pc:Int){
switch (pc){
case 0:
SET_BOOKMARK(PC=1);
finish_body_slow(0);
case 1:

}

Figure 1, Transform original execution path to connected frames

But the connected frames approach has another problem of "return" handling. The "return" statement of the original code path will force return the whole execution. While the return in a deeper frame will only cause the return from the de...