Browse Prior Art Database

Method for stride-profile guided prefetching for irregular code

IP.com Disclosure Number: IPCOM000029128D
Publication Date: 2004-Jun-16
Document File: 7 page(s) / 118K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for stride-profile guided prefetching for irregular code. 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 20% of the total text.

Method for stride-profile guided prefetching for irregular code

Disclosed is a method for stride-profile guided prefetching for irregular code. Benefits include improved functionality and improved performance.

Background

              Irregular code in a program is difficult to prefetch because a compiler has difficulty anticipating the future address of a load. Examples of irregular code include pointer-chasing code and loops with paths that cannot be easily determined by a compiler due to changes during the execution of the loop. However, recent studies indicate that pointer-chasing code sometimes exhibits a near-constant stride. The difference between two successive load addresses is almost a constant for some pointer chasing code. However, conventional compiler techniques cannot easily discover the constant stride. If pointer-chasing code is always assumed to have a constant stride, many of the references without constant strides are penalized. For example, when irregular loops occur in a typical pointer-chasing program, the load instruction frequently causes data cache misses.

              Data prefetching and loading use the following terms:

•             Candidate load: Load that may miss cache and should be considered for profiling or prefetching

•             Profiled load: Candidate load that is selected for profiling

•             Prefetched load: Candidate load that is selected for prefetching

•             Stride: Difference between the successive load addresses in the current code iteration and the previous iteration

General description

              The disclosed method is a compiler technique to estimate stride values for memory references and insert prefetching instructions accordingly.                                                                    The key elements of the method include:

•             Identifying candidate loads

•             Grouping candidate loads and selecting loads for profiling

•             Inserting profiling instructions

•             Collecting a stride profile

•             Analyzing the stride profile

•             Inserting stride prefetching instructions

Advantages

              The disclosed method provides advantages, including:

•             Improved functionality due to providing a stride profile

•             Improved performance due to reduce the overhead by profiling a single load from a group of related loads with compiler analysis

•             Improved performance due to providing guidance to the compiler prefetching using the

stride profile

 

Detailed description

              The disclosed method is a compiler technique to estimate stride values for memory references and insert prefetching instructions accordingly. The compiler analyzes code whenever possible to group related loads to reduce the profiling overhead and reduce the prefetching overhead. If the stride is mostly a constant, the compiler recompiles the program and uses the stride information to...