A statically scheduling compiler for a parameterized numerical accelerator

In this work, I present a statically scheduling compiler for a numerical accelerator that parallelizes and maps algorithms to instances of a processor template. The processor template that makes up the numerical accelerator is a collection of floating point units (FPUs) connected to memories through an interconnect structure. The task of the compiler is to create schedules for the interconnect structure and the memories to perform the desired algorithm as fast as possible. The compiler does this by representing the algorithm as a data flow graph (DFG) and scheduling the graph using depth-first list scheduling. The compiler then assigns memory addresses to the intermediate values of the DFG through a graph coloring heuristic to avoid structural hazards. The final result of the compiler is a set of instructions that can be loaded onto an instance of the processor template to create the desired numerical accelerator. This work also covers how algorithms are inputted into the compiler. One of the methods of algorithm input uses C++ function templates that express the numerical algorithm on a template data type. That type can be replaced with the graphMaker class to create a DFG, or it can be replaced with float, double, or int to check the correctness and the performance of the algorithm with different precisions. This enables algorithm designers to create a single version of the algorithm for both simulation and compilation. Multiple algorithms were compiled with this custom compiler to show how schedules change with the size of the processor, to show how the distribution of units within processors can be specialized for algorithms, and to show how algorithms can be optimized by the compiler to rival hand optimization of algorithms.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Wright, Andrew Charles

Advisor dc:contributor.advisor

• Vladimir Stojanović.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/82361

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/82361