Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/18865
Title: | An Approximation Algorithm Based Approach to Instruction Scheduling |
Authors: | Costa, Kriston |
Advisor: | Anand, Christopher Wolfram, Kahl |
Department: | Computer Science |
Publication Date: | 2016 |
Abstract: | Instruction scheduling is an NP-complete problem which allows for deciding the execution order of instructions in a function without altering the function's semantics. By modifying instruction execution order, CPU resource usage can be maximized resulting in increased instruction throughput and decreased overall execution times. In this thesis, a novel approximation-algorithm-based scheduler is introduced and a prototype is implemented for the IBM(c) z13(tm) processor. The algorithm is a modified version of Karger's minimum cut algorithm which is applied to a directed acyclic graph that defines instruction dependencies, also called the codegraph. Rather than finding the minimum cut of a codegraph, the algorithm produces multiple large groups of instructions that are independently scheduled and dispatched in software pipelined stages. Each iteration of this approximation algorithm produces a random feasible schedule. The likelihood that the performance of a schedule falls within a given range of the optimal solution improves as the total number of schedules produced increases. This allows for an explicit trade-off between schedule performance and scheduling time. The prototype was tested by scheduling functions from the IBM Mathematical Acceleration Subsystem (MASS) libraries for the z13 processor, and was found to be capable of producing production-quality schedules with minimal user involvement. |
URI: | http://hdl.handle.net/11375/18865 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
costa_kriston_p_201602_msc.pdf | 1.69 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.