Data processing system and method

• US 20020138700A1
• Filed: 04/24/2001
• Published: 09/26/2002
• Est. Priority Date: 04/28/2000
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Holmberg, Per Anders
• Granted Patent: US 6,539,458 B2
• Time in Patent Office: Days
• 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/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3814 Implementation provisions of instruction buffers, e.g. prefetch buffer; banks

Abstract

A data processing system and method involving a data requesting element and a first memory element from which said data requesting element requests data is described. An example of such a system is a processor and a first level cache memory, or two memories arranged in a hierarchy. A second memory element is provided between the first memory element and the requesting element. The second memory element stores data units read out of said first memory element, and performs a prefetch procedure, where said prefetch procedure contains both a sequential sub-procedure and a sub-procedure based on prefetch data identifiers associated with some of the data units.

Claims

1. A data processing system, comprising

a first memory element for storing data, from which data is read out in predetermined data units, each data unit being identified by a data identifier,

a second memory element for receiving data units from said first memory element, said second memory element being arranged to store a plurality of data units read from said first memory element,

a data requesting element that requests data from said second memory element, where said data requesting element comprises an element for establishing a sequence of data identifiers, each data identifier relating to data to be requested, and where the requesting procedure of said data requesting element is controlled in accordance with a program that proceeds according to said sequence, said data requesting element being operable to perform a request for data by providing said second memory element with a data identifier related to data being requested,

where said second memory element is operable to provide said data requesting element with data being requested if the data being requested is present in said second memory element, and is furthermore operable to perform a prefetch procedure for data units from said first memory element, said prefetch procedure comprising:

upon detecting a first predetermined change in status of said second memory element, determining a first given data unit in said second memory element associated with said first predetermined change in status, checking if said first given data unit fulfils a predetermined condition, said predetermined condition relating to a prefetch data identifier stored in association with said first given data unit, said prefetch data identifier identifying a different data unit than said first given data unit, and if said predetermined condition is fulfilled, giving to said first memory element a demand for at least a data unit identified by said prefetch data identifier stored in association with said first given data unit, and

upon detecting a second predetermined change in status of said second memory element, determining a second given data unit in said second memory element associated with said second predetermined change in status, and giving said first memory element a demand for at least a data unit identified by the data identifier that in said sequence follows the data identifier relating to the second given data unit.

2. The data processing system of claim 1, further comprising

a third memory element for storing data identifiers, said data identifiers identifying the data most recently requested by said data requesting element and being stored in the order of their last having been requested,

said data processing system being operable to perform a procedure such that if data identified by a data identifier provided by said data requesting element to said second memory element as a data request is not present in said second memory element, the data identifier for which no related data is present in said second memory element is associated with a data identifier belonging to a previous request stored in said third memory element, and then said data identifier for which no related data is present in said second memory element is stored as a prefetch data identifier in association with the data unit in said first memory element identified by said previous data identifier.

3. The data processing system of claim 2, wherein said data identifier belonging to a previous request, with which said data identifier for which no related data is present in said second memory element is associated, is determined as lying at a predetermined depth position in the order of stored data identifiers with respect to the data identifier most recently stored in said third memory element.

4. The data processing system of claim 3, wherein said depth position is variable.

5. The data processing system of claim 1, wherein a prefetch data identifier stored in association with a given data unit is stored together with said given data unit in the first memory element.

6. The data processing system of claim 5, wherein a prefetch data identifier stored in association with a given data unit is stored as a part of said given data unit.

7. The data processing system of claim 1, wherein a prefetch data identifier stored in association with a given data unit is stored separately from said given data unit in a designated table.

8. The data processing system of claim 7, wherein said designated table stores the data identifier identifying a given data unit together with the prefetch data identifier associated with the given data unit.

9. The data processing system of claim 1, wherein said first memory element comprises a cache memory.

10. The data processing system of claim 9, wherein said cache memory is an instruction cache.

11. The data processing system of claim 9, wherein said data units are one of data words and cache lines.

12. The data processing system of claim 1, wherein said second memory element comprises a stream buffer.

13. The data processing system of claim 12, wherein said second memory element comprises a multi-way stream buffer.

14. The data processing system of claim 1, wherein said data requesting element comprises a processor, and said element for establishing a sequence of data identifiers comprises a program counter.

15. The data processing system of claim 1, wherein said first predetermined change in status of said second memory element is the reading out of a data unit to said data requesting element, and said second memory element associated with said first predetermined change in status is the data unit read out.

16. The data processing system of claim 1, wherein said first predetermined change in status of said second memory element is the loading of a data unit into said second memory element, and said second memory element associated with said first predetermined change in status is the loaded data unit.

17. The data processing system of claim 1, wherein said checking of said predetermined condition relating to a prefetch data identifier comprises checking for the presence of said prefetch data identifier.

18. The data processing system of claim 1, wherein each data unit comprises a prefetch data identifier valid indicator, and said checking of said predetermined condition relating to a prefetch data identifier comprises checking the setting of said prefetch data identifier valid indicator.

19. The data processing system of claim 1, wherein detecting said second predetermined change in status of said second memory element comprises detecting said first predetermined change in status of said second memory element, and said second given data unit associated with said second predetermined change in status is identical with said first given data unit associated with said first predetermined change in status.

20. The data processing system of claim 19, wherein detecting said second predetermined change in status of said second memory element is identical with detecting said first predetermined change in status of said second memory element.

21. The data processing system of claim 19, wherein detecting said second predetermined change in status of said second memory element additionally comprises detecting that said first given data unit does not fulfil said predetermined condition.

22. The data processing system of claim 1, wherein said second predetermined change in status of said second memory element is associated with the degree of filling of said second memory element falling below a predetermined limit.

23. The data processing system of claim 1, wherein

said first memory element comprises an instruction cache memory,

said second memory element comprises a multi-way stream buffer,

said data requesting element comprises an execution pipeline belonging to a processor, the element for establishing a sequence of data identifiers being the program instruction counter,

a multiplexing element is provided between the multi-way stream buffer and the first memory element, said multiplexing element being operable to handle data demands from said plurality of multi-way stream buffers to said cache memory in such a way that data demands due to data requested by an execution pipeline not being present in said multi-way stream buffers have higher priority than data demands due to a prefetch operation on the basis of the data identifier that in the sequence follows the data identifier relating to the second given data unit, and data demands due to a prefetch operation on the basis of the data identifier that in the sequence follows the data identifier relating to the second given data unit have a higher priority than data demands due to a prefetch operation on the basis of a prefetch data identifier.

24. The data processing system of claim 1, wherein said second memory element comprises a plurality of multi-way stream buffers, said data requesting element comprises a plurality of execution pipelines, each respective execution pipeline being connected to a respective multi-way stream buffer of said second memory element, and where furthermore a plurality of multiplexing elements is provided between the plurality of multi-way stream buffers and the first memory element, such that all multi-way stream buffers of said plurality can access said instruction cache memory.

26. The method of claim 25, wherein a third memory element is provided for storing data identifiers, said data identifiers identifying the data most recently requested by said data requesting element and being stored in the order of their last having been requested,

said method furthermore comprising performing a procedure such that if data identified by a data identifier provided by said data requesting element to said second memory element as a data request is not present in said second memory element, the data identifier for which no related data is present in said second memory element is associated with a data identifier belonging to a previous request stored in said third memory element, and then said data identifier for which no related data is present in said second memory element is stored as a prefetch data identifier in association with the data unit in said first memory element identified by said previous data identifier.

27. The method of claim 26, wherein said data identifier belonging to a previous request, with which said data identifier for which no related data is present in said second memory element is associated, is determined as lying at a predetermined depth position in the order of stored data identifiers with respect to the data identifier most recently stored in said third memory element.

28. The method of claim 27, wherein said depth position is variable.

29. The method of claim 25, wherein a prefetch data identifier stored in association with a given data unit is stored together with said given data unit in the first memory element.

30. The method of claim 29, wherein a prefetch data identifier stored in association with a given data unit is stored as a part of said given data unit.

31. The method of claim 25, wherein a prefetch data identifier stored in association with a given data unit is stored separately from said given data unit in a designated table.

32. The method of claim 31, wherein said designated table stores the data identifier identifying a given data unit together with the prefetch data identifier associated with the given data unit.

33. The method of claim 25, wherein said first predetermined change in status of said second memory element is the reading out of a data unit to said data requesting element, and said second memory element associated with said first predetermined change in status is the data unit read out.

34. The method of claim 25, wherein said first predetermined change in status of said second memory element is the loading of a data unit into said second memory element, and said second memory element associated with said first predetermined change in status is the loaded data unit.

35. The method of claim 25, wherein said checking of said predetermined condition relating to a prefetch data identifier comprises checking for the presence of said prefetch data identifier.

36. The method of claim 25, wherein each data unit comprises a prefetch data identifier valid indicator, and said checking of said predetermined condition relating to a prefetch data identifier comprises checking the setting of said prefetch data identifier valid indicator.

37. The method of claim 25, wherein detecting said second predetermined change in status of said second memory element comprises detecting said first predetermined change in status of said second memory element, and said second given data unit associated with said second predetermined change in status is identical with said first given data unit associated with said first predetermined change in status.

38. The method of claim 37, wherein detecting said second predetermined change in status of said second memory element is identical with detecting said first predetermined change in status of said second memory element.

39. The method of claim 37, wherein detecting said second predetermined change in status of said second memory element additionally comprises detecting that said first given data unit does not fulfil said predetermined condition.

40. The method of claim 25, wherein said second predetermined change in status of said second memory element is associated with the degree of filling of said second memory element falling below a predetermined limit.

41. The method of claim 25, wherein said first memory element comprises an instruction cache memory, said second memory element comprises a multi-way stream buffer, said data requesting element comprises an execution pipeline belonging to a processor, the element for establishing a sequence of data identifiers being the program instruction counter, a multiplexing element is provided between the multi-way stream buffer and the first memory element,

wherein said method comprises that said multiplexing element is operated to handle data demands from said plurality of multi-way stream buffers to said cache memory in such a way that data demands due to data requested by an execution pipeline not being present in said multi-way stream buffers have higher priority than data demands due to a prefetch operation on the basis of the data identifier that in the sequence follows the data identifier relating to the second given data unit, and data demands due to a prefetch operation on the basis of the data identifier that in the sequence follows the data identifier relating to the second given data unit have a higher priority than data demands due to a prefetch operation on the basis of a prefetch data identifier.

25. A method of controlling a data processing system, said data processing system comprising a first memory element for storing data, from which data is read out in predetermined data units, each data unit being identified by a data identifier, a second memory element for receiving data units from said first memory element, said second memory element being arranged to store a plurality of data units read from said first memory element, a data requesting element that requests data from said second memory element, where said data requesting element comprises an element for establishing a sequence of data identifiers, each data identifier relating to data to be requested, and where the requesting procedure of said data requesting element is controlled in accordance with a program that proceeds according to said sequence, said data requesting element being operable to perform a request for data by providing said second memory element with a data identifier related to data being requested,

where said method comprises that second memory element is operated to provide said data requesting element with data being requested if the data being requested is present in said second memory element, and said method furthermore comprises that said second memory element is operated to perform a prefetch procedure for data units from said first memory element, said prefetch procedure comprising:

upon detecting a first predetermined change in status of said second memory element, determining a first given data unit in said second memory element associated with said first predetermined change in status, checking if said first given data unit fulfils a predetermined condition, said predetermined condition relating to a prefetch data identifier stored in association with said first given data unit, said prefetch data identifier identifying a different data unit than said first given data unit, and if said predetermined condition is fulfilled, giving to said first memory element a demand for at least a data unit identified by said prefetch data identifier stored in association with said first given data unit, and

upon detecting a second predetermined change in status of said second memory element, determining a second given data unit in said second memory element associated with said second predetermined change in status, and giving said first memory element a demand for at least a data unit identified by the data identifier that in said sequence follows the data identifier relating to the second given data unit.