15740: Computer Architecture
Fall 1999 Final Project Proposal

Genetic Algorithms for Data Value Prediction

Group Info

• Scott R Lenser (slenser@cs.cmu.edu)
• Desney S Tan (desney@cs.cmu.edu)

Project Web Page

http://www.cs.cmu.edu/~slenser/ca_project/index.html

Project Description

Data dependeces present a major hurdle to the amount of instruction-level parallelism that can be exploited. Data value prediction is a technique which bypasses these dependences by speculating on the outcomes of producer instructions, allowing consumer instructions to execute in parallel. The goal of our project is to explore the application of genetic algorithms (GAs) to the design of value prediction hardware. We will compare the results of the genetic algorithm to two simple value prediction methods (stride and context predictors) and one hand coded value prediction scheme. We will also calculate an estimated performance improvement over no value prediction by calculating correct, incorrect, and no prediction rates and using a simple cost/saving-per-prediction model to calculate the performance improvement.

Logistics

Plan of Attack and Schedule

We will use GAlib, a C++ genetic algorithm package developed at MIT, as the basis of the GA. The code base supports tree structured GA's (among others), parallel execution (important assuming simulation run times are fairly long), and many mutation and crossover operations. We plan on using a tree based data structure for the GA. We expect to have to modify the GA to handle trees specific to hardware type modules and code custom crossover/mutation operators. We chose this code base for its clean design, built-in support for trees, and parallel execution capabilities.

We will use ATOM (analysis tools with OM) to track data values used by programs in a small benchmark test suite. ATOM will allow us to instrument the GA in order to trace both predicted and actual values in order to analyze results. The test suite will consist of programs that would usually take 2-4 minutes to run. We expect simulation overhead to slow things down by a factor of about 10. We think a population of 24 individuals run for 25 generations will be enough to get good results. This implies 600 evaluations of 20-40 minutes each for a worst case run time of 400 hours. Since this is too long to run serially, we plan on using the parallel execution capabilities of GAlib to run on as many of the ECE DEC machines as possible. Assuming we can get 24 machines at once, total run time for one run will be 16.66 hours.

We expect the tree based genome of an individual to fairly directly represent the hardware for the value predictor. We plan to use global branch behavior, the history of local and global mispredictions, lookup tables, PC value, stride predictors, and various bit manipulations as the initial building block set.

Tasks

1. Comprehensive literature search for existing work
2. Decide on building blocks to include in genome
3. Implement GA
4. Extend GA to work in parallel mode
5. Learn how to modify GA to work on data value prediction
6. Determine how to collect simulation data with ATOM
7. Collect simulation data by hand for one predictor
8. Set up automatic collection of simulation data
9. Encode genome in GA
10. Formulate function to calculate data value prediction of individual given inputs
11. Modify crossover/mutation rules as needed to support genome
12. Determine tasks to be included in simulation benchmark
13. Formulate evaluation function based upon individual genome and simulation
14. First test run of GA with simulation
15. Progress report write-up
16. Modify structure of genome/GA/simulation to address problems
17. Final runs of GA with simulation
18. Final project report write-up
19. Prepare poster for poster session

Dependencies

A->B->I     
C->D         ->N->Y
C->E->I->K   ->N->P->Q->R
      I->J->M->N     Q->S
L->         M
F->G->H->   M  

Critical Path

F->G->H->M->N->P->Q->R

Schedule

Milestone

By November 8th, we plan to have the basic code base in place and debugged, and to conduct a test run of the GA using the simulator to perform the evaluation. Soon after, we hope to be fine tuning the GA and performing final tests.

Literature Search

Scope of papers:

• Genetic Algorithms (for general techniques)
• Branch Prediction methods (with and without GA solutions)
• Value Prediction methods (for basic building blocks)

Papers:

Steven J.Beaty. "Genetic Algorithms and Instruction Scheduling," in Proceedings of the 24th Annual International Symposium on Microarchitecture, 1991, pp. 206.

Kai Wang, and Manoj Franklin. "Highly Accurate Data Value Prediction using Hybrid Predictors," in Proceedings of the Thirtieth Annual IEEE/ACM International Symposium on Microarchitecture, 1997, pp. 281 – 290.

Resources Needed

Software

Genetic Algorithm

GAlib 2.4.4 developed at MIT (have copy, have compiled)

Parallel Virtual Machine

PVM to allow the the GA to run across several machines (freely available, not downloaded or installed yet)

Tracing/Simulation

ATOM code instrumentation interface (already installed on Alpha's)

Hardware

~400 hours of CPU time per run on DEC Alpha machines. We plan on doing this in a parallel manner, hopefully using ~25 machines for a ~16 hour run.

Getting Started: Work to date

• Reviewed branch prediction using GA to see constructs used
• Reviewed current value prediction schemes to find building blocks
• Located, downloaded, and compiled GAlib 2.4.4
• Beginning to explore ATOM simulation tool