Approximating Functions for Grid Domains

Project Proposal

15-745 Optimizing Compilers, Spring 2014

Group Info

Danny Zhu (dannyz)

Yuzi Nakamura (ynakamur)

Ben Humberston (bhumbers)

Project Web Page

https://cs.cmu.edu/~dannyz/compilers/

Project Description

We propose to build a system for compiling imperative functions in C++ to an accelerated yet approximated version of that function (also C++ code). The approximating functions will retain the same signature as the original functions, making them suitable for substitution in the source program without modification.

Our project is inspired by the work "Neural Acceleration for General-Purpose Approximate Programs", though we will only be using software approximators rather than implementing specialized neural network hardware. The compiler itself will be implemented in Python.

We'd like to apply this system to problems that involve the computation of some function over a 2D spatial grid. Applications which use this output may require that the approximations preserve important features of the grid such as the locations of the maximum and minimum values.

75% Goal

System for compiling unoptimized C++ to approximate, but faster-running C++
One approximator and comparisons of performance for at least one application

100% Goal

Two approximator types

125% Goal

Three or more approximator types
Additional input problems to which this approximation system could be applied.

System

Generate test inputs for function to be approximated
Generate & compile C++ code for model
Test performance of a list of approximators on generated inputs

Add evaluation harness for conveniently outputting performance results

Select best performing approximator, output approximating C++ function to user

Approximators:

Neural network approximator
Lookup table approximator
Nonlinear SVMs
Additional approximator types, time-permitting

Applications:

RoboCup
Image processing

Plan of Attack

The compilation system is the critical path. We also need at least one approximator that demonstrates how future approximators could be implemented for the system.

Schedule

Week	Ben	Danny	Yuzi
March 16th - 22nd	Compiler interface design	Compiler interface design & marshall test functions from domain application	Compiler interface design
March 23rd - 29th	Implement compiler structure (using placeholder approximator)	Implement compiler structure	Literature search & some compiler implementation
March 30th - April 5th	Implement approximator quality evaluator	Begin Approximator A implementation	Implement approximator quality evaluator
April 6th - April 12th	Implement Approximator B	Complete initial Approximator A implementation	Begin writing Approximator C
April 13th - April 19th	Write milestone report Initial Approximator A & B evaluations	Write milestone report Initial Approximator A & B evaluations	Complete initial Approximator C implementation
April 20th - April 26th	Final Approximator A & B debugging & evaluation	Final Approximator A & B debugging & evaluation	Approximator C evaluation & debugging
April 27th - April 30th	Final Report/Poster	Final Report/Poster	Final Report/Poster

Milestone (April 17th)

By April 17th, we aim to implement a compiler which generates different variations of approximating functions for a given C++ function. The output is also a C++ function, ready for integration into a final system. We aim to have at least two variations by this date: a neural network as well as one other approximation model. We also will have preliminary evaluation of the effectiveness of each model for a particular domain application (eg: RoboCup).

Motivating Reference

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.

Resources

We plan to implement our C++-to-C++ compiler using Python. We may make use of popular machine learning toolkits in order to aid in generating the approximators.

To provide test inputs for our quality evaluation, we may use C++ functions from one of the group member’s code for RoboCup, or numerical benchmarks such as those used in the neural acceleration paper.