Data processing system for processing vector data and method therefor

• US 6,202,130 B1
• Filed: 04/17/1998
• Issued: 03/13/2001
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.), International Business Machines Corporation, NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Olsson, Brett, Diefendorff, Keith Everett, Beavers, Bradford Byron, May, Cathy, Silha, Edward John, Burgess, Bradley G., Dubey, Pradeep Kumar, Hochsprung, Ronald Ray, Snyder, Michael Dean, Scales, Hunter Ledbetter III
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): Vital, Pierre M.
• Application Number:
  US09/061,975
• Time in Patent Office: 1,061 Days
• Field of Search: 711/137, 712/6
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30101 Special purpose registers

Abstract

A data processing system includes a data processor (10) coupled to a memory system having a first memory, such as an L1 data cache (16), arranged with a second memory (such as an L2 cache) at a lower hierarchical level. The data processor (10) prefetches data elements of a vector into the first memory prior to processing such data elements. If a requested data element is not present in the first memory, a load request is issued to the second memory and to lower levels of the memory hierarchy until the requested data element is finally retrieved and stored in the first memory. The data processor (10) continues to prefetch subsequent data elements of the vector by considering the length of the data element and the stride of the vector. In one embodiment, the data processor (10) prefetches the vector into the first memory in response to a single data stream touch load (DST) instruction (100).

Claims

1. In a data processing system having a first memory and a second memory at a lower hierarchical level than the first memory, a data processor for prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba+(s*i)), and i is an index having a value from 0 to (n−

1), the data processor comprising;

a first register for storing n;

a second register for storing s;

a third register for storing ea;

an arithmetic unit having a first input coupled to the second register, a second input coupled to the third register, and an output terminal, for calculating the effective address ea of each unit i of the n units of the vector and for providing a fetch address to the output terminal thereof corresponding to the effective address ea when enabled;

a load unit coupled to the first memory and to the second memory and having an input terminal for receiving the fetch address, for prefetching a data element located at the fetch address from the second memory into the first memory; and

a state machine having an input coupled to the first register, for enabling the arithmetic unit in response to the data processor receiving a predetermined instruction, and for enabling the arithmetic unit repetitively until an nth unit of the vector has been prefetched.

2. The data processor of claim 1 wherein the load unit determines if an ith unit is already stored in the first memory, and, if not, prefetches the ith unit of the vector from the second memory into the first memory.

3. The data processor of claim 1 wherein the data processing system operates in a selected one of a first mode and a second mode, and wherein, if, when operating in the first mode, the second mode is selected, an operation of the data processor is suspended until the first mode is next selected.

4. The data processor of claim 3 wherein the state machine, when operating in the first mode, further terminates the operation of the data processor before all of the n units are prefetched into the first memory in response to a second predetermined instruction.

5. The data processor of claim 1 further including means for selectively terminating an operation of the data processor before all of the n units are prefetched into the first memory.

6. The data processor of claim 1 wherein:

each of the n units has a length l;

the data processor further comprises a fourth register for storing l; and

the arithmetic unit further has a third input for receiving the length l, and enables the arithmetic unit a plurality of times corresponding to the length l to provide a corresponding plurality of fetch addresses for each unit i of the n units.

7. The data processor of claim 6 further comprising a register for storing the fetch address.

9. The method of claim 1 wherein the step of prefetching comprises the steps of:

determining if the cth unit is already stored in the first memory; and

if not, prefetching the cth unit of the vector from the second memory into the first memory.

10. The method of claim 1 further comprising the step of selectively terminating the method before all of the n units are prefetched into the first memory.

11. The method of claim 1 further comprising the step of:

receiving a predetermined instruction and performing all previous steps in response to an execution of the predetermined instruction.

12. The method of claim 1 wherein the step of stepping the count is further characterized as:

stepping the count c and selectively modifying the stride s.

22. The method of claim 9 further comprising the step of:

receiving a predetermined instruction and performing all previous steps in response to an execution of the predetermined instruction.

8. In a data processing system having a plurality of architectural registers adapted for storing a like plurality of vectors, a first, non-architected memory and a second memory at a lower hierarchical level than the first memory, a method for explicitly prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba+(s*i)), and i is an index having a value from 0 to (n−

1), the method comprising the steps of;

receiving a predetermined instruction, wherein said predetermined instruction does not cause the data processing system to affect the plurality of architectural registers;

executing said predetermined instruction by performing the steps of;

initializing a count c;

calculating the effective address ea of a cth unit of the vector;

prefetching the cth unit of the vector from the second memory into the first memory;

stepping the count c; and

if the count c is a predetermined value with respect to n, returning to the step of calculating.

13. In a data processing system having a first memory and a second memory at a lower hierarchical level than the first memory, a method for prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba +(s*i)), and i is an index having a value from 0 to (n−

1), the method comprising the steps of;

initializing a count c;

calculating the effective address ea of a cth unit of the vector;

prefetching the cth unit of the vector from the second memory into the first memory;

stepping the count c; and

if the count c is a predetermined value with respect to n, returning to the step of calculating;

wherein the data processing system operates in a selected one of a first mode and a second mode, and wherein, if, when operating in the first mode, the second mode is selected, the method is suspended until the first mode is next selected.

14. The method of claim 13 further comprising, when operating in the first mode, the step of selectively terminating the method before all of the n units are prefetched into the first memory.

15. The method of claim 13 wherein the step of stepping the count is further characterized as:

stepping the count c and selectively modifying the stride s.

16. In a data processing system having a first memory and a second memory at a lower hierarchical level than the first memory, a method for prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba+(s*i)), and i is an index having a value from 0 to (n−

1), the method comprising the steps of;

initializing a count c;

calculating the effective address ea of a cth unit of the vector;

prefetching the cth unit of the vector from the second memory into the first memory;

stepping the count c; and

if the count c is a predetermined value with respect to n, returning to the step of calculating;

wherein the step of prefetching comprises the step of changing a cache state of the cth unit of the vector in the first memory.

17. The method of claim 16 further comprising the step of:

receiving a predetermined instruction and performing all previous steps in response to an execution of the predetermined instruction.

18. The method of claim 16 wherein the step of stepping the count is further characterized as:

stepping the count c and selectively modifying the stride s.

19. In a data processing system having a plurality of architectural registers adapted for storing a like plurality of vectors, a first, non-architected memory and a second memory at a lower hierarchical level than the first memory, a method for explicitly prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba+(s*i)), and i is an index having a value from 0 to (n−

1), the method comprising the steps of;

receiving a predetermined instruction, wherein said predetermined instruction does not cause the data processing system to affect the plurality of architectural registers;

executing said predetermined instruction by performing the steps of;

for each unit i of the n units;

calculating the effective address ea of the ith unit of the vector; and

prefetching the ith unit of the vector from the second memory into the first memory.

20. The method of claim 19 wherein the step of prefetching comprises the steps of:

determining if the ith unit is already stored in the first memory; and

if not, prefetching the ith unit of the vector from the second memory into the first memory.

21. The method of claim 19 further comprising the step of selectively terminating the method before all of the n units are prefetched into the first memory.

23. The method of claim 19 further comprising, after the step of prefetching, the step of:

selectively modifying the stride s.

24. In a data processing system having a first memory and a second memory at a lower hierarchical level than the first memory, a method for prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba +(s*i)), and i is an index having a value from 0 to (n−

1), the method comprising the steps of;

for each unit i of the n units;

calculating the effective address ea of the ith unit of the vector; and

prefetching the ith unit of the vector from the second memory into the first memory;

wherein the data processing system operates in a selected one of a first mode and a second mode, and wherein, if, when operating in the first mode, the second mode is selected, the method is suspended until the first mode is next selected.

25. The method of claim 24 further comprising, when operating in the first mode, the step of selectively terminating the method before all of the n units are prefetched into the first memory.

26. The method of claim 24 further comprising, after the step of prefetching, the step of:

selectively modifying the stride s.

27. In a data processing system having a first memory and a second memory at a lower hierarchical level than the first memory, a method for prefetching into the first memory a vector stored in the second memory, the vector comprising n units distributed in the second memory at a stride s relative to a base address ba with an ith unit of the vector stored in the second memory at an effective address ea, where ea=(ba +(s*i)), and i is an index having a value from 0 to (n−

1), the method comprising the steps of;

for each unit i of the n units;

calculating the effective address ea of the ith unit of the vector; and

prefetching the ith unit of the vector from the second memory into the first memory;

wherein the step of prefetching comprises the step of changing a cache state of the ith unit of the vector in the first memory.

28. The method of claim 27 further comprising the step of:

receiving a predetermined instruction and performing all previous steps in response to an execution of the predetermined instruction.

29. The method of claim 27 further comprising, after the step of prefetching, the step of:

selectively modifying the stride s.