| Popis: |
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, theHeterogeneous Earliest Finish Time with Mutually Exclusive Processor Groups (HEFT-MEG) scheduling heuristic. HEFT-MEG schedules reconfigurations using a novel back-tracking algorithm to evaluatehow 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 schedulingto 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 performanceto gracefully degrade when processor availability diminishes, and increase when processor availability increases. |
