Method and apparatus for prefetching information and storing the information in a stream buffer
View Patent ↗A system for prefetching information from a computer storage includes a central processing unit operable to transmit to a transfer bus a memory transfer request containing a desired memory address. The system also includes a system controller operable to receive the memory transfer request from the transfer bus and to retrieve a prefetch block of data from the computer storage in response to determining that a stream buffer local to the system controller does not contain a copy of data stored at the desired memory address. The system controller is further operable to retrieve the data from the stream buffer and communicate the data to the central processing unit in response to determining that the stream buffer contains a copy of the data stored at the desired memory address.
1. A system for prefetching information from a computer storage comprising:
a central processing unit operable to transmit to a transfer bus a memory transfer request containing a desired memory address;
a system controller operable to receive the memory transfer request from the transfer bus and to retrieve a prefetch block of data from the computer storage in response to determining that a stream buffer local to the system controller does not contain a copy of data stored at the desired memory address, the system controller further operable to retrieve the data from the stream buffer and communicate the data to the central processing unit in response to determining that the stream buffer contains a copy of the data stored at the desired memory address; and
a tag table comprising a plurality of tags, each tag identifying a location in the stream buffer where a prefetch block is stored, wherein the tag table resides external to the stream buffer.
2. The system of claim 1 , wherein the central processing unit comprises a plurality of processors.
3. The system of claim 1 , wherein the stream buffer is located within the system controller.
4. The system of claim 1 , wherein each tag in the tag table is determined by truncating one or more least significant bits of each desired memory address.
5. The system of claim 4 , wherein each tag in the tag table identifies 2 n data values in the stream buffer, where n represents the number of least significant bits truncated from each desired memory address.
6. The system of claim 1 , wherein the tag table further comprises a plurality of validity markers operable to identify whether a tag in the tag table is valid, each tag having a corresponding validity marker.
7. The system of claim 1 , wherein the prefetch block comprises the data stored at the desired memory address and data stored at a plurality of addresses associated with the desired memory address.
8. The system of claim 1 , wherein the data comprising the prefetch block are located within a single logical page in a memory.
9. The system of claim 1 , wherein the data comprising the prefetch block are located between a first prefetch memory address and a second prefetch memory address, where the first prefetch memory address is defined by replacing one or more least significant bits of the desired memory address with zeroes, and the second prefetch memory address is defined by replacing one or more least significant bits of the desired memory address with ones.
10. The system of claim 1 , wherein the computer storage comprises a memory coupled to the system controller by a memory bus, the memory comprising the desired memory address.
11. The system of claim 10 , wherein the system controller transmits instructions to the memory on the memory bus at a faster rate than the central processing unit transmits memory transfer requests to the system controller on the transfer bus.
12. A system for prefetching information from a computer storage comprising:
a central processing unit operable to transmit to a transfer bus a memory transfer request containing a desired memory address;
a system controller operable to receive the memory transfer request from the transfer bus and to retrieve a prefetch block of data from the computer storage in response to determining that a stream buffer local to the system controller does not contain a copy of data stored at the desired memory address, the system controller further operable to retrieve the data from the stream buffer and communicate the data to the central processing unit in response to determining that the stream buffer contains a copy of the data stored at the desired memory address;
a tag table comprising a plurality of tags, each tag identifying a location in the stream buffer where a prefetch block is stored wherein the tag table resides external to the stream buffer;
wherein the computer storage comprises a memory coupled to the system controller by a memory bus, the memory comprising the desired memory address;
wherein the system controller transmits instructions to the memory on the memory bus at a faster rate than the central processing unit transmits memory transfer requests to the system controller on the transfer bus; and
wherein the prefetch block has a size determined by dividing a memory bus maximum request rate by a transfer bus maximum request rate.
13. A system controller for prefetching information from a computer storage comprising:
a stream buffer operable to store a prefetch block of data;
a stream buffer controller coupled to the stream buffer, the stream buffer controller operable to receive a memory transfer request containing a desired memory address and to retrieve a prefetch block of data from the computer storage in response to determining that the stream buffer does not contain a copy of data stored at the desired memory address, the stream buffer controller further operable to retrieve the data from the stream buffer and communicate the data to a central processing unit in response to determining that the stream buffer contains a copy of the data stored at the desired memory address; and
a tag table operable to identify a location of each prefetch block of data stored in the stream buffer, wherein the tag table resides external to the stream buffer.
14. The system controller of claim 13 , wherein the tag table comprises:
a plurality of tags, each tag identifying a location in the stream buffer where a prefetch block is stored; and
a plurality of validity markers defining when a tag in the tag table is valid, each tag having a corresponding validity marker.
15. The system controller of claim 14 , wherein each tag in the tag table comprises a desired memory address having one or more least significant bits truncated.
16. The system controller of claim 15 , wherein each prefetch block contains 2 n data values, where n represents the number of least significant bits truncated from the desired memory address.
17. The system controller of claim 14 , further comprising a plurality of comparators coupled to the controller and to the tag table, each comparator operable to compare a data value from the stream buffer controller with a tag from the tag table.
18. The system controller of claim 13 , wherein the prefetch block comprises the data stored at the desired memory address and data stored at a plurality of memory addresses associated with the desired memory address.
19. A method of prefetching information from a computer storage comprising:
receiving from a transfer bus a memory transfer request containing a desired memory address;
retrieving a prefetch block of data from the computer storage in response to determining that a stream buffer local to a system controller does not contain a copy of data stored at the desired memory address;
identifying based on a tag table a location in the stream buffer where the prefetch block is stored; and
retrieving data from the location in the stream buffer and communicating the data to the transfer bus in response to determining that the stream buffer contains a copy of the data stored at the desired memory address, wherein the tag table resides external to the stream buffer.
20. The method of claim 19 , further comprising the step of:
truncating at least one least significant bit of the desired memory address;
comparing one or more tags in the tag table with the truncated desired memory address, where each tag identifies a location in the stream buffer where a prefetch block of data is stored; and
determining if a tag is valid after locating a matching tag in the tag table.
21. The method of claim 20 , further comprising the step of invalidating a tag in the tag table in response to determining that the memory transfer request comprises a write operation.
22. The method of claim 19 , wherein the step of retrieving the prefetch block of data from the computer storage comprises retrieving from the computer storage the data stored at the desired memory address and data stored at a plurality of memory addresses associated with the desired memory address.
23. The method of claim 19 , further comprising the step of storing the prefetch block of data in the stream buffer.
24. The method of claim 23 , further comprising the step of transmitting the data stored at the desired memory address to the transfer bus.