Title of Presentation: An ASIP Architecture Framework to Facilitate Automated Design Space Exploration and Synthesis for Iterative Repair Solvers

Primary (Corresponding) Author: Aravind Dasu

Organization of Primary Author: Utah State University

Co-Authors: Jonathan Phillips


Abstract:  Autonomous dynamic event scheduling, using Iterative Repair techniques such as those employed by CASPER and ASPEN (NASA tools), is an essential component of successful space missions, as it enables spacecraft to adaptively schedule tasks in a dynamic, real-time environment.  Event rescheduling is a compute-intensive process.  Typical applications involve scheduling hundreds of events that share tens or hundreds of resources.  We are developing a set of tools for automating the derivation of application-specific processors (ASIPs) from ANSI C source code that perform this scheduling in an efficient manner.  The tools will produce VHDL code targeted for a Xilinx Virtex 4 FPGA (Field Programmable Gate Array).  Features of FPGAs, including large processing bandwidth and embedded ASICs and block RAMs, are exploited to optimize the design.  Efficiency is measured by combining the factors of execution speed, circuit size, power consumption, and fault tolerance.

Iterative Repair problems are generally solved using a combinatorial search heuristic, such as Simulated Annealing (which is used by CASPER and ASPEN), Genetic Algorithms, or Stochastic Beam Search.  All of these methods operate by gradually improving an initial solution over hundreds or thousands of iterations.  We propose an FPGA-based architectural framework derived from ANSI C function-level blocks for accelerating these computations.  At a function level, 99% of the work done by any Simulated Annealing algorithm is the repeated execution of three high-level steps:  (1) generating a new solution, (2) evaluating the solution, and (3) determining whether the new solution should be accepted.  The specifics of how each step operates vary with the application, and are implemented in VHDL through data- and control-flow analysis of the source C code.  We present an ASIP implementation of Iterative Repair using Simulated Annealing and compare its performance with that of conventional sequential processors.