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

System and Method for the design of the test-generation algorithm for Branch Indirect Address prediction hardware

IP.com Disclosure Number: IPCOM000237697D
Publication Date: 2014-Jul-02
Document File: 4 page(s) / 64K

Publishing Venue

The IP.com Prior Art Database


A system and method for the design of the test-generation algorithm for branch indirect address prediction hardware is disclosed.

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

Page 01 of 4

System and Method for the design of the test -generation algorithm for Branch Indirect Address prediction hardware

Disclosed is a system and method for the design of the test-generation algorithm for branch indirect address prediction hardware.

Modern superscalar speculative processors depend heavily on the branch prediction logic. Generally, every generation of processors improves the branch prediction logic. In the emerging workloads more of branch address prediction requirement are observed. This address prediction plays a key role in the languages including C++, scripting languages (which are current gaining lot of interest in the emerging workloads). Various performance study carried out over numerous emerging workloads and software brings out the importance of branch prediction requirements for the next generation workloads. More advanced Target address prediction algorithms (indirect address prediction) are put in the current generation processors to address the performance requirement for the emerging/next-generation workloads. There are very limited test generation algorithms available to generate effective test cases to stress the indirect address prediction hardware.

The disclosed algorithm addresses the gap of target address prediction to provide a complete coverage. Specifically, the problem of effective test-generation for the target address (indirect address prediction) by creating multi-node branch patterns to generate very interesting test scenarios for stressing any type of indirect address prediction hardware.

A set of instructions are built that are clearly delineated into a set of "nodes" where each "node" consists of a fixed number of instructions. The algorithm then interconnects the different nodes using a pseudo-random branch pattern generation methodology. At the end of this build process, a set of nodes is created where each node has a taken path and a not taken path. This path information is recorded in a Branch Information Structure. The self modifying code generation module uses the "Branch Information Structure" to actually build a couple of branch instructions in each node for the taken and not taken paths respectively. Each of these branches is built at fixed offsets from the start of a node.

The limitation of the above algorithm is that every "node" has a pair of direct/indirect branch instructions (that transfer control to the taken or not taken path) that always branch to a particular node irrespective of the execution pattern. Thus, although there can be multiple entry points into a node, there are always only two exits from a node. Moreover, the branches are ONLY direct branches (i.e. the displacement is part of the branch instruction itself) Although, this algorithm is useful to stress the branch direction prediction mechanism in modern processors, its inability to exercise the target address prediction hardware (which comes into t...