Skip to Main Content
 

Global Search Box

 
 
 
 

Files

ETD Abstract Container

Abstract Header

Scheduling Tasks on Heterogeneous Chip Multiprocessors with Reconfigurable Hardware

Teller, Justin Stevenson

Abstract Details

2008, Doctor of Philosophy, Ohio State University, Electrical and Computer Engineering.

This dissertation presents several methods to more efficiently use the computational resources availableon a Heterogeneous Chip Multiprocessor (H-CMP). Using task scheduling techniques, three challenges to the effective usage of H-CMPs are addressed: the emergence of reconfigurable hardware in general purpose computing, utilization of the network on a chip (NoC), and fault tolerance.

To utilize reconfigurable hardware, we introduce the Mutually Exclusive Processor Groups reconfiguration model, and an accompanying task scheduler, the Heterogeneous Earliest Finish Time with Mutually Exclusive Processor Groups (HEFT-MEG) scheduling heuristic. HEFT-MEG schedules reconfigurations using a novel back-tracking algorithm to evaluate how different reconfiguration decisions affect previously scheduled tasks. In both simulation and real execution, HEFT-MEG successfully schedules reconfiguration allowing the architecture to adapt to changing application requirements.

After an analysis of IBM's Cell Processor NoC and generation of a simple stochastic model, we propose a hybrid task scheduling system using a Compile- and Run-time Scheduler (CtS and RtS) that work in concert. The CtS, Contention Aware HEFT (CA-HEFT), updates task start and finish times when scheduling to account for network contention. The RtS, the Contention Aware Dynamic Scheduler (CADS), adjusts the schedule generated by CA-HEFT to account for variation in the communication pattern and actual task finish times, using a novel dynamic block algorithm. We find that using a CtS and RtS in concert improves the performance of several application types in real execution on the Cell processor.

To enhance fault tolerance, we modify the previously proposed hybrid scheduling system to accommodate variability in the processor availability. The RtS is divided into two portions, the Fault Tolerant Re-Mapper (FTRM) and the Reconfiguration and Recovery Scheduler (RRS). FTRM examines the current processor availability and remaps tasks to the available set of processors. RRS changes the reconfiguration schedule so that the reconfigurations more accurately reflect the new hardware capabilities. The proposed hybrid scheduling system enables application performance to gracefully degrade when processor availability diminishes, and increase when processor availability increases.

Fusun Ozguner (Advisor)
Umit Catalyurek (Committee Member)
Eylem Ekici (Committee Member)
145 p.

Recommended Citations

Citations

  • Teller, J. S. (2008). Scheduling Tasks on Heterogeneous Chip Multiprocessors with Reconfigurable Hardware [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1211985748

    APA Style (7th edition)

  • Teller, Justin. Scheduling Tasks on Heterogeneous Chip Multiprocessors with Reconfigurable Hardware. 2008. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1211985748.

    MLA Style (8th edition)

  • Teller, Justin. "Scheduling Tasks on Heterogeneous Chip Multiprocessors with Reconfigurable Hardware." Doctoral dissertation, Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1211985748

    Chicago Manual of Style (17th edition)