Value Prediction for Java Programs
Project Description
In Java, method return values can often be predicted using simple techniques. Such predictions are useful for speculative threading on multi-core architectures. This project is about analysing some typical Java programs to determine how and when their method return values can be predicted.
Project aims:
- adapt and extend the Sable Speculative Multi-threading tool for return value prediction in Java programs
- evaluate the accuracy and computational cost of existing return value prediction algorithms
- devise new and innovative prediction techniques
Project Progress
10 Apr 08
Developed Java code to implement three predictors:
- last value prediction
- stride value prediction
- context prediction
Familiarization with Jikes RVM and DaCapo benchmarks
Objectives
10 Apr 08
- (s) Change context predictor to work for any length of context (use array instead of hard-coded variables) (done 15 Apr 08)
- (j) fix Jikes RVM so we can extract method return value traces (done 15 Apr 08)
- (j) find Compilers info for background reading (done 15 Apr 08)
Objectives
15 Apr 08
- (s) Use retval rvm with DaCapo benchmarks to get set of files with return values (done 22 Apr 08)
- (s) Test all predictors (lvp,svp,contexts) on these return value files - for global prediction (done 22 Apr 08)
- (s) Split context predictor into separate context tables based on actual return values (treat 0,1 specially) (carry forward)
Summary
22 Apr 08
- Extracted all return values for global prediction, however some benchmark files are so big that the context predictor runs out of memory when the key length larger than 3.
Actions to take
- (s) Recode context predictor to mask bottom N bits of key integers, to reduce context table size (although we know this may reduce accuracy). Trading off space and precision. (carry forward)
- (s) Evaluate how accuracy changes for a length-4 context predictor when we vary the size of the key mask. Draw graphs for jython, luindex and chart, since these seem to be interesting benchmarks for prediction. (carry forward)
- (s) Draft out a rough plan for the Project Background Research Report. (done)
Idea
24 Apr 08
Jeremy's idea - maybe try to implement a Jimenez-style neural predictor for return values??? How would we implement this?
Project Summary
6 May 08
- written up first draft of background report (due 9 May). Jeremy suggested alterations, Swanand to redraft within next 24 hours. (done)
- Jeremy's idea - maybe try to implement a meta-predictor - predict when another predictor is wrong...
Project Meeting
6 Jun 08
Use a mask, something like:
public class Mask {
public static int NUM_BITS_IN_MASK = 3;
public static int MASK = (1<<NUM_BITS_IN_MASK) - 1;
public static void main(String [] args) {
int i;
for (i = 0; i < 1000; i++) {
int maskedI = i & MASK;
System.out.println(""+i + " " + maskedI);
}
}
}
You need to use the masked versions of the return values when creating your key String (still include the commas to separate the numbers).
But - don't use the masked value for the return value to store with the key - use the full 32 bit value instead :-)
You can trade-off space and accuracy for your context predictor by varying the number of bits in the mask. (NUM_BITS_IN_MASK in above code)
Low NUM_BITS_IN_MASK is good for space, high is good for accuracy.
(Draw graphs to see if this is true.)
---
Short-term objectives
- implement masking in hash table key construction (to avoid out-of-memory errors) (done)
Long-term objectives
- analyse predictor performance on per-method value streams rather than global value stream
- implement novel prediction algorithms (split predictors based on values, other hybrid predictors, or meta-predictors)
---
Project Objectives
17 Jun 08
- implement per-method predictor using hash-table based on method ids (done)
- first implement method-specific last value predictor (done)
- then implement method-specific context predictor (two-level hash table) (done)
- try to generate some line graphs in excel
---
Project Objectives
24 Jun 08
- implement method-specific stride value predictor (done)
- implement method-specific context predictor with global context history for keys (done)
---
Project Objectives
1 Jul 08
There are four weeks left for software development, then four weeks for thesis writing.
- try to use the default DaCapo inputs instead of small, to generate bigger trace files (done)
- try to explain why some predictors work well for some benchmarks, understand why trends occur in graphs (e.g. lusearch with increasing key size for method specific context predictor...)
- implement global value sensitive hybrid predictor (0,1 -> one predictor, everything else to another). Try context and LVP. (done, well done!!!)
- dissertation preparation work (jeremy - done)
---
Dissertation Outline
8 Jul 08
- introduction - short, interesting description of problem (speculation, value prediction)
- background - existing prediction algorithms
- infrastructure - Jikes RVM, capturing return value trace files, benchmarks we used, how we implemented predictors using Java data structures (hash tables, etc). Put some simple algorithmic descriptions (pseudo code or flow charts ) in here
- Value Prediction Investigations - confirm existing knowledge about LVP, SVP, CVP. Lots of graphs, comparing accuracy of each predictor on each benchmark. Show how changes in parameters (mask size, context length) affects accuracy and space overhead.
- New Prediction Algorithms - value-sensitive hybrid predictor. Evaluate how well this works in relation to existing predictors.
- Related work - summarise other papers in this area
- Conclusions - summarise what this project has achieved, pointers for future work.
80-100 pages. 10-20 Kwords.
Aiming to finish by 25 August?
---
Objectives
* Jul 08
- get started with latex editor on windows, using muthesis outline (started)
- sort out chapters, and rough idea of contents for each thesis chapter (to do)
- finish off experiments on default size inputs for DaCapo (done)
- try more experiments with hybrid predictor - 2 CVPs - one for 0,1, one for all other values (discussed problems with hybrid predictor, can't look at actual values until we have decided which predictor to use...)
- sort out graphs for chapter 4. (jeremy think about this too) (to do)
---
Objectives
15 Jul 08
- implement new hybrid predictor, with a meta-predictor to choose between various value predictors (look at papers on hybrid value prediction)
- test different hybrid configurations
Objectives
12 Aug 08
- expand bg report into chapters 1 and 2
- revise chapter 3, draw diagrams for various predictor algorithms, and explain how these can be implemented using Java data structures.
- first draft of chapter 4, results and commentary for the various predictors on the DaCapo benchmarks.
- aim to email PDF of these 4 chapters by Mon 18 Aug, meet again to discuss on Tue 19.
