InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Trace Generation and Reduction Technique for Evaluation of Branch Prediction Algorithms

IP.com Disclosure Number: IPCOM000238432D
Publication Date: 2014-Aug-26
Document File: 4 page(s) / 72K

Publishing Venue

The IP.com Prior Art Database


Traditional trace generation methodology relies upon techniques like simpoints to capture the interesting phases of the benchmarks. But capturing the traces and reducing it with simpoint like techniques will result in missing out on some interesting branch behaviour patterns in the benchmark code though that section is not hot. So capturing the entire benchmark trace is important in evaluating the capacities of some of the key speculation related buffers in the hardware. But this kind of full blown trace will result in long running time and make the evaluation process more time consuming. Our proposed solution allow configurable thresholds of branch repetitive behaviour and branch history vector beyond which there is no change in branch behaviour information is recorded in the branch unit of the processor. While crossing these thresholds, the subsequent branches in the trace are skipped until the behaviour changes. This is very effective in studying long-running programs that typically consist of numerous loops that exhibits large iteration counts – each iteration involves a branch and the branch prediction data does not see a change beyond a threshold. This technique helps us to capture the interesting branch patterns and skip the unnecessary branch patterns where the branch prediction algorithm does not play a huge role.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 57% of the total text.

Page 01 of 4

Trace Generation and Reduction Technique for Evaluation of Branch Prediction Algorithms

The trace-driven or event-driven simulation are preferred methods for performance evaluation in microarchitecture design. A program binary is executed in a trace collection environment and the

program characteristics is recorded as a trace. Trace collection involves collection of information about each executed instruction and is hence a long process. The traces thus collected contain volumnous information and are huge files which pose a challenge in post-processing and storage. More importantly, cycle-accurate simulators that use these traces are extremely complex and take long periods of time(days to weeks) to complete simulation of a single industry-standard benchmark program trace. The long runtimes pose a hurdle in quick evaluation of microarchitecture changes and processor development process.

Different approaches exist that identify representative sections of hot, unique and interesting

phases of the program traces (Ex: Simpoints) and designers often use such an aggregation of such identified sections to study microarchitectural behaviour on cycle-accurate simulators.

During the branch prediction algorithms in hardware, a small change in branch pattern can heavily influence the behavior of branch prediction hardware and can end-up giving an inaccurate understanding about the prediction efficiency. For example, modern microprocessors use branch history for the particula...