Back to search

McMaster University

An Approximation Algorithm Based Approach to Instruction Scheduling

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Computer Science
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Costa, Kriston
Advisors dc:contributor.advisor
  • Anand, Christopher
  • Wolfram, Kahl

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Costa, Kriston. An Approximation Algorithm Based Approach to Instruction Scheduling. 2016. http://hdl.handle.net/11375/18865