# US 2013/0212334 A1 · Determining Optimal Preload Distance at Runtime

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0212334 A1
- Document ID: US20130212334A1
- Status: Published application
- Kind: A1
- Application number: 13/369,548
- Filed: 2012-02-09
- Published: 2013-08-15
- Earliest claimed: 2012-02-09
- Assignees: QUALCOMM Incorporated
- Inventors: Gerald Paul Michalak; Gregory Allan Reid
- Web page: https://patentgrep.com/patent/US20130212334A1

## CPC

- G06F 12/0862: with prefetch
- G06F 9/38: Concurrent instruction execution, e.g. pipeline or look ahead
- G06F 9/3854: {Instruction completion, e.g. retiring, committing or graduating}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A run-time delay of a memory is measured, a run-time duration of a routine is determined, and an optimal run-time preload distance for the routine is determined based on the measured run-time memory delay and the determined run-time duration of the routine. Optionally, the run-time duration of the routine can be determined by measuring a run-time duration, and optionally the run-time duration can be determined based on a database of run-time delay for operations of the routine. Optionally, the optimal run-time preload distance is used in performing a loop of the routines.

## Claims

### Claim 1

A method for optimizing a preloading of a processor from a memory, at run time, comprising:
measuring a run-time memory latency of the memory and generating, as a result, a measured run-time memory latency;
determining a run-time duration of a routine on the processor and generating, as a result, a determined run-time duration;
determining a run-time optimal preloading distance based on the measured run-time memory latency and the determined run-time duration of the routine on the processor.

### Claim 2 (depends on 1)

The method of claim 1, wherein determining the run-time optimal preloading distance includes dividing the measured run-time memory latency by the determined run-time duration to generate a quotient, and rounding the quotient to an integer.

### Claim 3 (depends on 1)

The method of claim 1, wherein determining the run-time duration of the routine on the processor includes warming a cache associated with the routine to obtain a warmed cache, performing the routine a plurality of times using the warmed cache, and measuring a time span required for performing the routine a plurality of times.

### Claim 4 (depends on 1)

The method of claim 1, wherein measuring the run-time memory latency includes:
identifying a memory loading start time;
performing a loading from the memory, starting at a start time associated with said memory loading start time;
detecting a termination of the loading;
identifying a memory loading termination time associated with the termination of the loading; and
calculating the measured run-time memory latency based on said memory loading start time and the memory loading end time.

### Claim 5 (depends on 4)

The method of claim 4, wherein identifying the memory loading start time includes reading a start value on a central processing unit (CPU) cycle counter, identifying the memory loading termination time includes reading an end value on the CPU cycle counter, and wherein calculating the measured run-time memory latency includes calculating a difference between the end value and the start value.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
providing a processing system overhead for said reading of the CPU cycle counter;
adjusting the measured run-time memory latency based on the processing system overhead.

### Claim 7 (depends on 4)

The method of claim 4, wherein identifying the memory loading start time includes reading a system timer, identifying the memory loading termination time includes reading the system timer.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
providing a processing system overhead for said reading of the system timer;
adjusting the measured run-time memory latency based on the processing system overhead.

### Claim 9 (depends on 1)

The method of claim 1, wherein measuring the run-time memory latency includes:
storing a plurality of pointers comprising a last pointer and a plurality of interim pointers in the memory, each of the interim pointers pointing to a location in the memory of another of the pointers;
reading the pointers, the reading comprising
setting a pointer access location based on one of the interim pointers,
accessing another of the pointers based on the pointer access location,
updating the pointer access location based on an another accessed pointer resulting from accessing another of the pointers,
repeating the accessing of another of the pointers and updating the pointer access location until detecting an accessing of the last pointer;
measuring a time elapsed in reading the pointers; and
dividing the time elapsed by a quantity of the pointers read to obtain an estimated run-time memory latency as the measured run-time memory latency.

### Claim 10 (depends on 9)

The method of claim 9, further comprising
initializing an access counter in association with a start of reading the pointers;
incrementing the access counter in association with accessing another of the pointers; and comparing the access counter to a termination count,
wherein detecting the accessing of the last pointer is based on a result of the comparing.

### Claim 11 (depends on 9)

The method of claim 9, wherein the last pointer has a last pointer value, and
wherein detecting the accessing of the last pointer is based on detecting another accessed pointer matching the last pointer value.

### Claim 12 (depends on 1)

The method of claim 1, further comprising providing a database of run-time duration for each of a plurality of processor operations, and wherein determining the run-time duration of the routine on the processor is based on the database of run-time duration.

### Claim 13 (depends on 1)

The method of claim 1, further comprising performing N iterations of the routine and, during the performing, preloading a cache of the processor using the run-time optimal preloading distance.

### Claim 14 (depends on 13)

The method of claim 13, wherein preloading the cache includes preloading the cache with data and instructions for a number of iterations of the routine corresponding to the run-time optimal preloading distance.

### Claim 15 (depends on 14)

The method of claim 14, wherein performing the N iterations of the routine includes a preloading of the cache at each iteration of the routine, and counting a number of instances of the preloading.

### Claim 16 (depends on 13)

The method of claim 13, wherein performing the N iterations of the routine comprises:
performing prologue iterations, each prologue iteration including one preloading without execution of the routine;
performing body iterations, each body iteration including one preloading and one execution of the routine; and
performing epilogue iterations, each epilogue iteration including one execution of the routine without preloading.

### Claim 17 (depends on 16)

The method of claim 16, wherein the prologue iterations fill the cache with data or instructions for a quantity of iterations of the routine equal to the run-time optimal preloading distance.

### Claim 18 (depends on 17)

The method of claim 17, wherein the body iterations perform a quantity of iterations equal to the run-time optimal preloading distance subtracted from N.

### Claim 19 (depends on 13)

The method of claim 13, wherein determining the run-time duration of the routine includes measuring a time span of performing the N iterations of the routine, generating a corresponding measured time span, and dividing the measured time span by N.

### Claim 20

An apparatus for optimizing a preloading of a processor from a memory, at run time, comprising:
means for measuring run-time memory latency of the memory and generating, as a result of the measuring, a measured run-time memory latency;
means for determining a run-time duration of a routine on the processor and generating, as a result, a determined run-time duration; and
means for determining a run-time optimal preloading distance based on the measured run-time memory latency and the run-time duration of the routine on the processor.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein determining the run-time optimal preloading distance includes quotient the measured run-time memory latency by the run-time duration to generate a quotient, and rounding the quotient up to an integer.

### Claim 22 (depends on 20)

The apparatus of claim 20, wherein determining the run-time duration of the routine on the processor includes warming a cache associated with the routine to obtain a warmed cache, performing the routine a plurality of times using the warmed cache, and measuring a time span required for performing the routine a plurality of times.

### Claim 23 (depends on 20)

The apparatus of claim 20, wherein the means for measuring the run-time memory latency includes:
means for identifying a memory loading start time;
means for performing a loading from the memory, starting at a start time associated with said memory loading start time;
means for detecting the termination of the loading;
means for identifying a memory loading termination time associated with the termination of the loading; and
means for calculating the measured run-time memory latency based on said memory loading start time and memory loading end time.

### Claim 24 (depends on 23)

The apparatus of claim 23, wherein identifying the memory loading start time includes reading a start value on a central processing unit (CPU) cycle counter, identifying the memory loading termination time includes reading an end value on the CPU cycle counter, and wherein calculating the measured run-time memory latency includes calculating a difference between the end value and the start value.

### Claim 25 (depends on 23)

The apparatus of claim 23, further comprising:
means for adjusting the measured run-time memory latency based on a processing system overhead for said reading of the CPU cycle counter.

### Claim 26 (depends on 23)

The apparatus of claim 23 wherein identifying the memory loading start time includes reading a system timer, and identifying the memory loading termination time includes reading the system timer.

### Claim 27 (depends on 26)

The apparatus of claim 26, further comprising:
means for providing a processing system overhead for said reading of the system timer; and
means for adjusting the measured run-time memory latency based on the processing system overhead.

### Claim 28 (depends on 20)

The apparatus of claim 20, wherein the means for measuring the run-time memory latency includes
means for storing a plurality of pointers comprising a last pointer and a plurality of interim pointers in the memory, each of the interim pointers pointing to a location in the memory of another of the pointers;
means for reading the pointers;
means for measuring a time elapsed in reading the pointers; and
means for dividing the time elapsed by a quantity of the pointers read to obtain an estimated run-time memory latency as the measured run-time memory latency.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein reading the pointers includes:
setting a pointer access location based on one of the interim pointers,
accessing another of the pointers based on the pointer access location to provide another accessed pointer,
updating the pointer access location based on the accessed another pointer, and
repeating the accessing of another of the pointers and updating the pointer access location until detecting an accessing of the last pointer.

### Claim 30 (depends on 29)

The apparatus of claim 29, wherein reading the pointers further comprises:
initializing an access counter in association with a start of reading the pointers;
incrementing the access counter in association with accessing another of the pointers; and comparing the access counter to a termination count,
wherein detecting the accessing of the last pointer is based on a result of the comparing.

### Claim 31 (depends on 28)

The apparatus of claim 28, wherein identifying the memory loading start time includes reading a system timer, wherein identifying the memory loading termination time includes reading the system timer,
wherein the last pointer has a last pointer value, and
wherein detecting the accessing of the last pointer is based on detecting the accessed another pointer matching the last pointer value.

### Claim 32 (depends on 28)

The apparatus of claim 28, further comprising:
means for providing a processing system overhead for said reading of the system timer; and
means for adjusting the measured run-time memory latency based on the processing system overhead.

### Claim 33 (depends on 20)

The apparatus of claim 20 further comprising means for preloading a cache of the processor with data and instructions for a number of iterations of the routine corresponding to the run-time optimal preloading distance.

### Claim 34 (depends on 20)

The apparatus of claim 20, wherein determining the run-time duration of the routine includes measuring a time span of performing the N iterations of the routine and generating, in response, a measured time span, and dividing the measured time span by N.

### Claim 35 (depends on 20)

The apparatus of claim 20, wherein the apparatus is integrated in at least one semiconductor die.

### Claim 36 (depends on 20)

The apparatus of claim 20, further comprising a device, selected from the group consisting of a set top box, music player, video player, entertainment unit, navigation device, communications device, personal digital assistant (PDA), fixed location data unit, and a computer, into which the apparatus is integrated.

### Claim 37

A computer product having a computer readable medium comprising instructions that, when read and executed by a processor, cause the processor to perform operations for optimizing a preloading of a processor from a memory, at run time, the instructions comprising:
instructions that cause the processor to measure run-time memory latency of the memory to generate a measured run-time memory latency;
instructions that cause the processor to determine a run-time duration of a routine on the processor and to generate a resulting determined run-time duration;
instructions that cause the processor to determine a run-time optimal preloading distance based on the measured run-time memory latency and the determined run-time duration of the routine on the processor.

### Claim 38 (depends on 37)

The computer product of claim 37, wherein instructions that cause the processor to determine the run-time optimal preloading distance includes instructions that cause the processor to divide the measured run-time memory latency by the determined run-time duration to generate a quotient, and round the quotient to an integer.

### Claim 39 (depends on 37)

The computer product of claim 37, wherein instruction that cause the processor to determine the run-time duration of the routine on the processor include instructions that cause the processor to warm a cache associated with the routine to obtain a warmed cache, perform the routine a plurality of times using the warmed cache, and measure a time span required for performing the routine a plurality of times.

### Claim 40 (depends on 37)

The computer product of claim 37, wherein instructions that cause the processor to determine the run-time duration of the routine on the processor include instruction that the cause the processor to measure a time span of performing N iterations of the routine, and divide the time span of performing the routine N times by N.

### Claim 41 (depends on 37)

The computer product of claim 37, wherein instructions that cause the processor to measure the run-time memory latency include:
instructions that cause the processor to identify a memory loading start time;
instructions that cause the processor to perform a loading from the memory, starting at a start time associated with said memory loading start time;
instructions that cause the processor to detect a termination of the loading;
instructions that cause the processor to identify a memory loading termination time associated with the termination of the loading; and
instructions that cause the processor to calculate, based on said memory loading start time and memory loading end time, the measured run-time memory latency.

### Claim 42 (depends on 41)

The method of claim 41, wherein identifying the memory loading start time includes reading a start value on a central processing unit (CPU) cycle counter, identifying the memory loading termination time includes reading an end value on the CPU cycle counter, and wherein calculating the measured run-time memory latency includes calculating a difference between the end value and the start value.

### Claim 43 (depends on 42)

The computer product of claim 42, further comprising:
instructions that cause the processor to provide a processing system overhead for said reading of the CPU cycle counter;
instructions that cause the processor to adjust the measured run-time memory latency based on the processing system overhead.

### Claim 44 (depends on 41)

The computer product of claim 41, wherein instructions that cause the processor to identify the memory loading start time includes instructions that cause the processor to read a system timer, and wherein instructions that cause the processor to identify the memory loading termination time include instructions that cause the processor to read the system timer.

### Claim 45 (depends on 44)

The method of claim 44, further comprising:
providing a processing system overhead for said reading of the system timer;
adjusting the measured memory latency based on the processing system overhead.

### Claim 46 (depends on 37)

The computer product of claim 37, further comprising instructions that cause the processor to determine the run-time duration of the routine on the processor based on a given database of run-time duration for each of a plurality of processor operations.

### Claim 47 (depends on 37)

The computer product of claim 37, further comprising instructions that cause the processor to perform N iterations of the routine and, during the performing, to preload a cache of the processor using the run-time optimal preloading distance.

### Claim 48 (depends on 47)

The computer product of claim 47, wherein instructions that cause the processor to perform the N iterations include instructions that cause the processor to preload the cache at each iteration of the routine, and to count a number of instances of the preloading.

### Claim 49 (depends on 47)

The computer product of claim 47, wherein instructions that cause the processor to perform the N iterations comprises:
instructions that cause the processor to perform prologue iterations, each prologue iteration including one preloading without execution of the routine;
instructions that cause the processor to perform body iterations, each body iteration including one preloading and one execution of the routine; and
instructions that cause the processor to perform epilogue iterations, each epilogue iteration including one execution of the routine without preloading.

### Claim 50 (depends on 49)

The computer product of claim 49, wherein the prologue iterations fill the cache with data or instructions for a quantity of iterations of the routine equal to the run-time optimal preloading distance.

### Claim 51 (depends on 50)

The computer product of claim 50, wherein the body iterations perform a quantity of iterations equal the run-time optimal preloading distance subtracted from N.
