Milestone Report
15-745 Optimizing Compilers, Spring 2014
Project Summary
We are building a framework for compiling the source of imperative C functions to an accelerated yet approximated version of those functions. The approximating functions retain the same signature as the original functions, making them suitable for direct substitution in the source program. We are interested in the accuracy and speed of different approximation types when computing outputs over a 2D spatial grid, such as used in the Robocup challenge. In this domain, it is important to preserve topological features of the grid such as the locations of the maximum and minimum values.
Progress Update
So far, we've implemented a compilation framework that loads a specified source function; generates a suite of test inputs; and automatically trains and then generates the source for a linear approximation of the original function. The neural network approximator, originally targeted for this milestone, is still being implemented.
We have conducted preliminary evaluation of the accuracy and runtime speed of the linear approximation against an MDP value iteration problem over the spatial grid. The figure below shows an example of the approximator output compared to the original function.
Figure 1: Original (left) and linearly approximated (right) result of value iteration for an MDP problem with a reward state located in lower left corner of grid.
Surprises & Changes
While we initially considered using lookup tables as one type of approximator, we eliminated them as a viable option for our purposes, as the memory cost of this approach is intractable for the high dimensionality of our function inputs and outputs.
We also decided to focus on a single, strictly defined C function signature rather than support arbitrary C++ functions, which are difficult to map to our numeric approximation interface. This is in keeping with Esmaeilizadeh et al, 2012, which allowed only a restricted functional interface to their approximate neural network compilation scheme. Time permitting, we hope to support modest variation in the functional signatures, such as allowing variable arguments or structs.
Revised Schedule
Week | Ben | Danny | Yuzi |
April 17th - 19th | Research methods for topological feature preservation | Approximator A & B debugging & evaluation | Approximator C implementation |
April 20th - 26th | Approximator A & B | Approximator A & B additional evaluation | Approximator C |
April 27th - 30th | Final Report/Poster | Final Report/Poster | Final Report/Poster |
Remaining work
We don’t require any additional resources in order to complete the project.
Unless requested by the instructors, we do not believe a meeting to review our progress is necessary.
Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger.
"Neural Acceleration for General-Purpose Approximate Programs," in Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-45),
December 2012.
