Ph.D. Preliminary Exam - Sean Stanek

Date: 14 Oct, 2009
Time: 9:30 AM
Location: 223 Atanasoff Hall
Topic: SAPPHIRE: Semi-Automated Parallel Programming in Heterogeneous Intelligent Reconfigurable Environment
Major Professor(s): Carl K. Chang


Abstract:

With the growing demands of modern computing, large clusters of processors in conjunction with heterogeneous computing elements (e.g., CPU, GPU, and FPGA) have been put together to parallelize the execution of lengthy programs, in an effort to finish computation as fast as possible. However, the configurations of computing elements as well as the types of programs themselves have become more and more complex.

Of specific interest to us is the stream programming paradigm -- a programming methodology where a program is constructed from a set of concurrently executing repetitive tasks to create a parallel task graph (PTG), while a large data set is streamed through the PTG, data item after data item, also in parallel. This is similar to the way that microprocessor pipelines work on data and machine code.

While the ultimate goal of parallel and heterogeneous programming is to increase the speed of computation (i.e., reduce the overall execution time of a program), little related work exists for the scheduling of stream programs on heterogeneous computing clusters. Most related work involves the unrolling of a parallel task graph several times to simulate the parallel data flow, followed by conventional task scheduling of the unrolled graph. To the best of our knowledge, no work exists for heterogeneous stream task scheduling operating directly on the parallel task graph.

We present a novel heterogeneous stream task scheduling technique that operates on the original parallel task graph. We anticipate that this could provide a more optimal schedule in a shorter amount of time. To facilitate the evaluation of the new approach, as well as to ease the design and implementation of any heterogeneous stream program, we also formulate a semi-automated program construction technique and implement a framework for it. This will be used to implement our case study: a real-time colonoscopy video analysis software.