Browse Prior Art Database

Method for a Q-phase boundary detection algorithm

IP.com Disclosure Number: IPCOM000130552D
Publication Date: 2005-Oct-26
Document File: 4 page(s) / 201K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a quantile phase (Q-phase) boundary detection algorithm. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Method for a Q-phase boundary detection algorithm

Disclosed is a method for a quantile phase (Q-phase) boundary detection algorithm. Benefits include improved functionality and improved performance.

Background

      The conventional approach of always building vectors with 100 million instructions will inevitably produce ambiguous vectors at phase boundaries that contain Extended Instruction Pointers (EIPs) from adjoining phases. The clustering algorithm either treats these vectors as part of a different phase, increasing the expected number of phases (k) value, or it places these vectors into one of the existing phases, increasing the error in code page information (CPI) estimation.

      One approach to achieve this goal is to minimize the number of phase changes for a given k.

General description

      The disclosed method is a quantile phase (Q-phase) boundary detection algorithm. The method is a simplified initial approach to split 100 million Extended Instruction Pointer Vector (EIPVs) at phase boundaries into smaller vectors that have no more than 100 million instructions each. The method generates multiple trace segments (one or more per phase), where each trace segment coincides with the EIPV representative selected by the tool. However, phase detection and trace collection are not performed at the same time and the two runs may not be identical. As a result, phases must be identified to be less sensitive to small run-time variations.

Advantages

              The disclosed method provides advantages, including:

•             Improved functionality due to providing a Q-phase boundary detection algorithm

•             Improved functionality due to providing trace collection

•             Improved performance due to reducing the amount of time that is spent simulating the behavior of an application when designing a new processor

Detailed description

      The disclosed method identifies phase changes by tracking the locus of execution - the average memory location in the application’s instruction space over a given period. For every EIP sample, the disclosed method computes the arithmetic average of the immediately preceding 100 EIP samples to compute the locus of execution. A similar locus is computed for the immediately following 100 EIP samples. The disclosed method computes the absolute value of the difference between the two loci (the derivative) and associates it with the current EIP sample. The derivatives at each EIP sample are sorted in descending order and the top 1% (or quantile) are marked as possible phase-change boundaries (Q99 phase detection).

      In experiments, 1% can be selected as the cut-off point, though an optimal value may be identified in the future. Specifying a 0% quantile (Q100) turns off the Q-phase algorithm.

      Phase change information can then be used to segregate the EIPs of one phase from the next by building a shortened vector that does not include any EIPs from the next...