Karl Taht's Research Paper Blog

Authors:   Tim Sherwood, Erez Perelman, Brad Calder (UC San Diego) Venue:      PACT 2001 As the title states, the key problem this paper seeks to solve is finding simulation points. To do this, they come up with basic block vectors analysis (BBVA). BBVA uses BBV's, which can be collected in an environment more similar to running the default program than simulation, and as a result, is many orders of magnitude quicker than simulation. They use the BBV's to determine the relative sizes of each phase, i.e., how much duration of program execution they represent. Then using other tricks such as Fourier analysis, they are also able to analyze the cyclic behavior. Full Text

Authors:   Tim Sherwood, Erez Perelman, Greg Hamerly, Brad Calder (UC San Diego) Venue:      ASPLOS 2002 This paper introduces the concept of Basic Block Vectors (BBV). A basic block is defined as a piece of code with one entry and one exit. A basic block vector consists of an element for each basic block. The value in that block corresponds to the number of times the block was seen multiplied by the number of instructions in the block. Similar phases, or basic blocks, need not be temporally adjacent. One particularly interesting components is there phase detection algorithm. There basic block vectors are often millions of dimensions, and they use random linear projection to reduce the dimensionality 15. They use k-means multiples times and score the result using BIC - Bayesian Information Criterion. Full Text