<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T18:06:56Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/3612" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/3612</identifier><datestamp>2017-03-21T16:14:14Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="d41718f2-1c8f-4e33-b643-d5e1229c1e67" confidence="600">Malik, Abid</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-04-21T18:33:28Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2008-04-21T18:33:28Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-04-21T18:33:28Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2008-03</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/3612</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Modern processors have multiple pipelined functional units&#xd;
and can issue more than one instruction per clock cycle. This&#xd;
puts great pressure on the instruction scheduling phase in&#xd;
a compiler to expose maximum instruction level parallelism.&#xd;
Basic blocks and superblocks are commonly used regions of code&#xd;
in a program for instruction scheduling. Instruction scheduling&#xd;
coupled with register allocation is also a well studied problem&#xd;
to produce better machine code. Scheduling basic blocks and&#xd;
superblocks optimally with or with out register allocation is&#xd;
NP-complete, and is done sub-optimally in production compilers&#xd;
using heuristic approaches. In this thesis, I present a&#xd;
constraint programming approach to the superblock and basic&#xd;
block instruction scheduling problems for both idealized and&#xd;
realistic architectures. Basic block scheduling with register&#xd;
allocation with no spilling allowed is also considered. My&#xd;
models for both basic block and superblock scheduling are&#xd;
optimal and fast enough to be incorporated into production&#xd;
compilers. I experimentally evaluated my optimal schedulers on&#xd;
the SPEC 2000 integer and floating point benchmarks. On this&#xd;
benchmark suite, the optimal schedulers were very robust and&#xd;
scaled to the largest basic blocks and superblocks. Depending&#xd;
on the architectural model, between 99.991\% to 99.999\% of all&#xd;
basic blocks and superblocks were solved to optimality. The&#xd;
schedulers were able to routinely solve the largest blocks,&#xd;
including blocks with up to 2600 instructions. My results compare&#xd;
favorably to the best previous optimal approaches, which are based&#xd;
on integer programming and enumeration.&#xd;
My approach for basic block scheduling without allowing spilling was good&#xd;
enough to solve 97.496\% of all basic blocks in the SPEC 2000&#xd;
benchmark. The approach was able to solve basic blocks as&#xd;
large as 50 instructions for both idealized and realistic&#xd;
architectures within reasonable time limits.&#xd;
Again, my results compare favorably to recent work &#xd;
on optimal integrated code generation, which is&#xd;
based on integer programming.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Constraint Programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Compiler Optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Instruction Scheduling</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Register Allocation</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Constraint Programming Techniques for Optimal Instruction Scheduling</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>