Method and system for reissuing load requests in a multi-stream prefetch design

• US 6,317,811 B1
• Filed: 08/26/1999
• Issued: 11/13/2001
• Est. Priority Date: 08/26/1999
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mui, David, Deshpande, Sanjay Raghunath
• Primary Examiner(s): Ellis, Kevin L.
• Application Number:
  US09/383,737
• Time in Patent Office: 810 Days
• Field of Search: 711/129, 711/137, 711/213
• 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/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862

Abstract

A method and system for reissuing load requests in a multi-stream prefetch engine of a data processing system is provided. A read transaction is received from a transaction requester, and the read transaction has a base address and a prefetch stream identifier. The received read transaction is issued to a prefetch stream associated with a data prefetch buffer identified by the prefetch stream identifier as the prefetch stream is one of a set of prefetch streams, each of which has an associated prefetch buffer. The read transaction is issued to a prefetch stream associated with a data prefetch buffer, and a set of prefetch addresses are generated, each prefetch address in the set of prefetch addresses being proximate to the base address. A determination is made as to whether the data prefetch buffer has unallocated prefetch buffer entries, and a comparison is made between each prefetch address in the set of prefetch addresses and all prefetch addresses in each data prefetch buffer to determine whether a prefetch address in the set of prefetch addresses collides with a prefetch address in a data prefetch buffer. In response to a determination of an absence of an address collision and a determination that the data prefetch buffer does not have an unallocated prefetch buffer entry, the base address is held for data prefetch reissuance.

Claims

1. A method for prefetching data in a data processing system by using data prefetch transactions, the method comprising the steps of:

receiving a read transaction from a transaction requester, the read transaction comprising a base address;

generating a prefetch address proximate to the base address;

determining whether the prefetch address collides with an address in a prefetch buffer;

determining whether the prefetch buffer has an unallocated prefetch buffer entry; and

in response to a determination of an absence of an address collision and a determination that the prefetch buffer does not have an unallocated prefetch buffer entry, holding the base address to be reissued for data prefetch processing.

2. The method of claim 1 further comprising:

in response to a determination of an absence of an address collision and a determination that the prefetch buffer has an unallocated prefetch buffer entry, allocating the unallocated prefetch buffer entry to the prefetch address.

3. The method of claim 1 wherein the generated prefetch address is higher or lower than the base address according to a predetermined indicator.

4. The method of claim 1 further comprising:

reissuing the base address for data prefetch processing.

5. A method for prefetching data in a data processing system by using data prefetch transactions, the method comprising the steps of:

receiving a read transaction from a transaction requester, the read transaction comprising a base address and a prefetch stream identifier;

issuing the received read transaction to a prefetch stream associated with a first data prefetch buffer identified by the prefetch stream identifier, wherein the prefetch stream is one of a plurality of prefetch streams;

generating a first prefetch address proximate to the base address;

determining whether the first data prefetch buffer has an unallocated prefetch buffer entry;

determining whether the first prefetch address collides with a second prefetch address in a second data prefetch buffer; and

in response to a determination of an absence of an address collision and a determination that the first data prefetch buffer does not have an unallocated prefetch buffer entry, holding the base address for data prefetch reissuance.

6. The method of claim 5 further comprising:

in response to a determination of an absence of an address collision and a determination that the first data prefetch buffer has an unallocated prefetch buffer entry, allocating the unallocated prefetch buffer entry to the first prefetch address.

7. The method of claim 5 wherein the first prefetch address is higher or lower than the base address according to a predetermined indicator.

8. The method of claim 5 further comprising:

presenting the base address for data prefetch reissuance.

9. The method of claim 5 further comprising:

selecting a base address for data prefetch reissuance from a plurality of base addresses pending data prefetch reissuance.

10. The method of claim 9 wherein the base address for data prefetch reissuance is selected according to an arbitration scheme.

11. The method of claim 9 wherein each prefetch stream in the plurality of prefetch streams holds a base address for data prefetch reissuance.

12. The method of claim 5 further comprising:

generating a local comparison result for each prefetch stream by determining whether the first prefetch address collides with a prefetch address in any of the data prefetch buffers; and

combining local comparison results to generate a global comparison result that indicates whether the first prefetch address collides with any prefetch address in any of the plurality of data prefetch buffers.

13. A method for prefetching data in a data processing system by using data prefetch transactions, the method comprising the steps of:

receiving a read transaction from a transaction requestor, the read transaction comprising a base address and a prefetch stream identifier, wherein the prefetch identifier identifies a prefetch stream in a set of prefetch streams, wherein each prefetch stream in the set of prefetch streams is associated with a data prefetch buffer;

issuing the read transaction to a prefetch stream associated with a first data prefetch buffer;

generating a set of prefetch addresses, each prefetch address in the set of prefetch addresses being proximate to the base address;

determining whether the first data prefetch buffer has an unallocated prefetch buffer entry;

comparing each prefetch address in the set of prefetch addresses to all prefetch addresses in each data prefetch buffer to determine whether a prefetch address in the set of prefetch addresses collides with a prefetch address in a data prefetch buffer; and

in response to a determination of an address non-collision for one or more prefetch addresses in the set of prefetch addresses and a determination that the first data prefetch buffer does not have an unallocated prefetch buffer entry, holding the base address for data prefetch reissuance.

14. The method of claim 13 wherein each prefetch stream in the set of prefetch streams holds a base address for data prefetch reissuance.

15. A data processing system for prefetching data by using data prefetch transactions, the data processing system comprising:

receiving means for receiving a read transaction from a transaction requestor, the read transaction comprising a base address and a prefetch stream identifier;

issuing means for issuing the received read transaction to a prefetch stream associated with a first data prefetch buffer identified by the prefetch stream identifier, wherein the prefetch stream is one of a plurality of prefetch streams;

first generating means for generating a first prefetch address proximate to the base address;

first determining means for determining whether the first data prefetch buffer has an unallocated prefetch buffer entry;

second determining means for determining whether the first prefetch address collides with a second prefetch address in a second data prefetch buffer; and

holding means for holding, in response to a determination of an absence of an address collision and a determination that the first data prefetch buffer does not have an unallocated prefetch buffer entry, the base address for data prefetch reissuance.

16. The data processing system of claim 15 further comprising:

allocating means for allocating, in response to a determination of an absence of an address collision and a determination that the first data prefetch buffer has an unallocated prefetch buffer entry, the unallocated prefetch buffer entry to the first prefetch address.

17. The data processing system of claim 15 wherein the first prefetch address is higher or lower than the base address according to a predetermined indicator.

18. The data processing system of claim 15 further comprising:

presenting means for presenting the base address for data prefetch reissuance.

19. The data processing system of claim 15 further comprising:

selecting means for selecting a base address for data prefetch reissuance from a plurality of base addresses pending data prefetch reissuance.

20. The data processing system of claim 19 wherein the base address for data prefetch reissuance is selected according to an arbitration scheme.

21. The data processing system of claim 19 wherein each prefetch stream in the plurality of prefetch streams holds a base address for data prefetch reissuance.

22. The data processing system of claim 15 further comprising:

second generating means for generating a local comparison result for each prefetch stream by determining whether the first prefetch address collides with a prefetch address in any of the data prefetch buffers; and

combining means for combining local comparison results to generate a global comparison result that indicates whether the first prefetch address collides with any prefetch address in any of the plurality of data prefetch buffers.

23. A computer program product in a computer-readable medium for use in a distributed data processing system for prefetching data in a data processing system by using data prefetch transactions, the computer program product comprising the steps of:

first instructions for receiving a read transaction from a transaction requester, the read transaction comprising a base address and a prefetch stream identifier;

second instructions for issuing the received read transaction to a prefetch stream associated with a first data prefetch buffer identified by the prefetch stream identifier, wherein the prefetch stream is one of a plurality of prefetch streams;

third instructions for generating a first prefetch address proximate to the base address;

fourth instructions for determining whether the first data prefetch buffer has an unallocated prefetch buffer entry;

fifth instructions for determining whether the first prefetch address collides with a second prefetch address in a second data prefetch buffer; and

sixth instructions for in response to a determination of an absence of an address collision and a determination that the first data prefetch buffer does not have an unallocated prefetch buffer entry, holding the base address for data prefetch reissuance.

24. The computer program product of claim 23 further comprising:

instructions for selecting a base address for data prefetch reissuance from a plurality of base addresses pending data prefetch reissuance.

25. The computer program product of claim 24 wherein each prefetch stream in the plurality of prefetch streams holds a base address for data prefetch reissuance.