Apparatus for predicting memory access and method thereof

A method for predicting memory access, where each data processing procedure is performed in a plurality of stages with segment processing, and the plurality of stages include at least a first stage and a second stage, includes: dividing a memory into a plurality of memory blocks, generating a predicting value of a second position information according to a correct value of a first position information at the first stage, accessing the memory blocks of the corresponding position in the memory according to the predicting value of the second position information, and identifying whether the predicting value of the second position information is correct or not for determining whether the memory is re-accessed, where the first stage occurs before the second stage in a same data processing procedure.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a memory access mechanism, and more particularly, to a method and apparatus for predicting memory access.

2. Description of the Prior Art

FIG. 1is a diagram of a prior art data processing system10. As shown inFIG. 1, the data processing system10comprises a core processor101, a memory102, a cache memory103, an outer memory interface104and an outer memory105. The core processor101is for processing calculation information; the memory102is coupled to the core processor101, and is for storing instructions or data that needs to be processed by the core processor101; the cache memory103is a memory apparatus of low storage capacity but high access speed, and is also coupled to the core processor101for temporarily storing instructions or data that needs to be processed by the core processor101; the outer memory interface104is coupled to the core processor101, for being the communication channel of the outer memory105and internal components; and the outer memory105is coupled to the outer memory interface104, and is a memory apparatus of high storage capacity but low access speed.

Generally speaking, the core processor101first retrieves instructions and data from the cache memory103. When the required instructions and data are unable to be found in the cache memory103, the core processor101retrieves the instructions and data from the memory102. Similarly, when the required instructions and data are unable to be found in the memory102, the core processor101retrieves the instructions and data from the outer memory105.

Within the procedure of retrieving instructions and data, a memory management unit (MMU) and an address calculation unit (not illustrated inFIG. 1) are set depending on the needs of the system, where the address calculation unit generates a virtual address/logic address according to the tasks of the system, and the MMU is for converting the virtual address/logic address to a physical address, and then searching the overall memory according to the physical address to retrieve the required instructions or data.

The procedure of searching instructions and data from layers of memories is not only time consuming, but also power consuming, and significantly reduces the overall efficiency and performance of the system. Therefore, how to improve the access efficiency of the memory and also reduce the power consumption are important topics to be considered.

SUMMARY OF THE INVENTION

Accordingly, it is therefore one of the objectives of the present invention to provide a method and apparatus of predicting memory access in order to solve the problems faced by the conventional art, in order to improve the prediction accuracy and reduce the power consumption of the memory system.

According to an embodiment of the present invention, a method of predicting memory access is disclosed, where each data processing procedure is performed in a plurality of stages with segment processing, and the plurality of stages comprises at least a first stage and a second stage. The method comprises: dividing a memory into a plurality of memory blocks; generating a predicting value of a second position information according to a correct value of a first position information at the first stage; accessing the memory blocks of the corresponding position in the memory according to the predicting value of the second position information; and identifying whether the predicting value of the second position information is correct or not for determining whether the memory is re-accessed; where the first stage occurs before the second stage in a same data processing procedure.

According to another embodiment, the present invention discloses an apparatus for predicting memory access, where each data processing procedure is performed in a plurality of stages with segment processing, and the plurality of stages comprises at least a first stage and a second stage. The apparatus comprises: a memory, comprising a plurality of memory blocks; a prediction unit, coupled to the memory, for generating a predicting value of a second position information according to a correct value of a first position information at the first stage to access the memory blocks of the corresponding position in the memory; and a determining unit, coupled to the prediction unit, for identifying whether the correct value of a second position information is the same as the predicting value of the second position information at the second stage or not; where the first stage occurs before the second stage in a same data processing procedure.

DETAILED DESCRIPTION

For improving the efficiency of data accessing and reducing power consumption, the present invention provides a method and apparatus for predicting memory access in the system mentioned above, for solving the problems associated with the prior art in order to improve overall efficiency and performance.

Please refer toFIG. 2.FIG. 2is a diagram illustrating an exemplary embodiment of a predicting memory access apparatus20. The apparatus20comprises: an access history queue (AHQ)200, a prediction table202, a determining unit204and a memory unit206.

In an embodiment, the memory unit206is divided into a plurality of memory blocks. It is assumed here that the memory unit206is divided into four memory blocks, which are memory block1, memory block2, memory block3and memory block4. As the memory unit206is divided into four memory blocks, the physical address of the memory block received each time by the AHQ200is capable of being represented by 2 bits only, and a 6-bit first in first out (FIFO) register is adopted to implement the AHQ200; that is, only three physical addresses of the memory blocks are stored. The prediction table202is divided into 64 (26=64) entries according to the bit numbers of the AHQ200, and each entry is for storing a physical address of a memory block.

For better understanding, the physical address of the memory block to be accessed here is represented as PHYADD_NEXT, and the predicting value of the physical address of the memory block to be accessed is represented as PHYADD_NEXT_PREDICTION. Please refer toFIG. 3.FIG. 3is a flowchart illustrating an exemplary embodiment of a predicting memory access according to the present invention. The steps are as follows:

STEP310: Before the AHQ200receives the physical address PHYADD_NEXT of the memory block to be accessed, a 6-bit data of the AHQ200is used as an index to retrieve the content of the entry corresponding to the index from the prediction table202for being the predicting value PHYADD_NEXT_PREDICTION of the physical address of the memory block to be accessed.

STEP320: According to the predicting value PHYADD_NEXT_PREDICTION of the physical address of the memory block, corresponding memory blocks from the memory unit206are accessed for retrieving required instructions and data. At the same time, the AHQ200receives the physical address PHYADD_NEXT of the memory block to be accessed and stores the physical address PHYADD_NEXT in the FIFO method.

STEP330: The determining unit204compares the physical address PHYADD_NEXT of the memory block with the predicting value PHYADD_NEXT_PREDICTION of the physical address of the memory block. If the two addresses are the same, then the prediction is correct; if the two addresses are different, the prediction is wrong, and the flow proceeds to STEP340.

STEP340: According to the physical address PHYADD_NEXT of the memory block, corresponding memory blocks of the memory unit206are accessed for retrieving required instructions and data.

In another embodiment, the apparatus20further comprises an address generation module, for generating the physical address PHYADD_NEXT of the memory block in the AHQ200. This is for illustration purposes only and is not intended as a limitation of the present invention.

Please refer toFIG. 4.FIG. 4is a diagram illustrating an exemplary embodiment of a predicting memory access apparatus20operated in the data processing system10. In an embodiment, the apparatus20further comprises: an address calculation module208applied to a system having a pipeline mechanism. For each data processing procedure, the pipeline mechanism is performed in the following stages: Instruction fetch (I), Decode (D), Execution (E), Memory access (M), Write back (W) etc. Five stages are shown here, but this is for illustration purposes only and is not intended as a limitation of the present invention. The number of stages can be altered according to practical applications.

The pipeline mechanism is further outlined here for better illustration and understanding. It is assumed that the data processing system10has five tasks that need to be processed: task1, task2, task3, task4and task5. During the execution of task1, the corresponding instructions are retrieved in the I stage; then, when task1performs decoding of instructions at the D stage, task2derives the corresponding instructions at the I stage at the same time; then, task1performs corresponding operations according to the result derived from the I stage at the E stage, and task2performs decoding of instructions at the D stage, task3derives the instructions needed at the I stage at the same time; then, task1derives the data needed from memories at the M stage, task2performs corresponding operations according to the result derived from the D stage at the E stage; task3performs decoding of the instructions at the D stage, task4derives the corresponding instructions needed at the I stage at the same time; then, task1stores the data to the memories at the W stage, task2derives the data needed from memories at the M stage, task3performs corresponding operations according to the result derived from the D stage at the E stage; task4performs decoding of the instructions at the D stage, task5derives the corresponding instructions at the I stage at the same time; others and so forth according to the pipeline process. Please refer toFIG. 5for a clearer illustration of the entire process.

Further illustration of an exemplary embodiment of a predicting memory access apparatus mentioned above is detailed herein. At the E stage, the address calculation module208generates a virtual address according to the task of the system, and converts the virtual address to a physical address. At the same time, the predicting memory access apparatus20of this invention performs accessing in advance of the memory blocks to be accessed according to AHQ200and prediction table202. At the M stage, it is determined whether a prediction hit occurs or a prediction miss occurs, then the method of predicting memory access mentioned inFIG. 3is performed. The related operations of other stages are omitted herein for brevity.

When memory blocks are accessed as described above, corresponding memory blocks of the memory206are started only according to the physical address, and other memory blocks are all closed. Therefore, when a prediction hit occurs, the memory block corresponding to the predicting value PHYADD_NEXT_PREDICTION of the physical address of the memory block is started; when a prediction miss occurs, the two memory blocks corresponding to the predicting value PHYADD_NEXT_PREDICTION and the physical address PHYADD_NEXT of the memory blocks are started only. Thus, the present invention not only reduces the power consumption but also improves the overall performance of the present invention. Please note that this example is for illustration purposes only and is not intended as a limitation of the present invention.

It should be noted that, in the embodiment mentioned above, the memory206is implemented by a tightly coupled memory (TCM), but this is for illustration purposes only and is not intended as a limitation of the present invention. The prediction mechanism mentioned above is capable of being applied to other kinds of memories, but corresponding descriptions are omitted herein for brevity.

Please refer toFIG. 2andFIGS. 6 to 12.FIG. 6is a diagram illustrating an exemplary embodiment of predicting memory access andFIG. 7toFIG. 12are diagrams illustrating a prediction table of an exemplary embodiment of predicting memory access. Please refer toFIG. 6andFIG. 7first. The content of the AHQ200and the content of the prediction table202are all default values, where the bit sequence is “B5B4B3B2B1B0” representing that the physical addresses of the memory blocks accessed in sequence are “B1B0”, “B3B2” and “B5B4”. In the record501, the AHQ200is the combination of the access sequence “000000”, and the prediction value PHYADD_NEXT_PREDICTION of the physical address of the memory block is derived from the index address “000000” and the default value “00” of the index address “000000” of the prediction table202ofFIG. 7, then accessing in advance of the memory block of the physical address “00” is performed. Here, the physical address PHYADD_NEXT of the memory block to be accessed is also “00” (please refer toFIG. 6), so it represents a prediction hit occurs. Additionally, the physical address PHYADD_NEXT “00” of the memory block uploads “B5B4” to the AHQ200in the FIFO, and the default content of the index address “000000” of the prediction table202is set to be “00” (please refer toFIG. 8); then, the second memory access is performed (please refer toFIG. 6andFIG. 8), as shown in the record502. The AHQ200is still “000000”, and accessing of the prediction table202is still performed according to the content of the AQH200, where the content of the AQH200is the index, and the default content of the index address “000000” of the prediction table202of theFIG. 8is “00”, so the prediction value PHYADD_NEXT_PREDICTION of the physical address of the memory block this time is “00”, and accessing in advance of the physical address being “00” of the memory block is performed, but the physical address PHYADD_NEXT of the memory block to be accessed is “01” (please refer toFIG. 6), which represents a prediction miss occurs. Therefore, accessing of the physical address “01” of the memory block should be performed to derive correct instructions and data. Additionally, “B5B4” is uploaded to the AHQ300in the FIFO method, and the default content of the index address “000000” of the prediction table202is set to be “01” (please refer toFIG. 9); then, the third memory accessing is performed (please refer toFIG. 6andFIG. 9), as shown in the record503, the AHQ200is “010000”, and accessing of the prediction table202is still performed according to the content of the AQH200, where the content of the AQH200is the index, and the default content of the index “010000” of the prediction table202of theFIG. 9is “00”, so the prediction value PHYADD_NEXT_PREDICTION of the physical address of the memory block this time is “00”, and therefore accessing in advance of the physical address being “00” of the memory block is performed, which represents a prediction miss occurs, therefore, accessing of the physical address “11” of the memory block should be performed to derive correct instructions and data. Additionally, the physical address PHYADD_NEXT “11” of the memory block is uploaded to the “B5B4” of the AHQ200in the FIFO method, and the content of the AHQ200is “110100”, and the content of the default value of the prediction table202is set to be “11” (please refer toFIG. 10); then, the third memory accessing is performed (please refer toFIG. 10). As shown in the record504, the AHQ200is “110100”, and still performs accessing of the prediction table202according to the content of the AQH200, where the content of the AQH200is the index, and the content of the default value “110100” of the prediction table202of theFIG. 9is “00”, so the prediction value PHYADD_NEXT_PREDICTION of the physical address of the memory block this time is “00”, so accessing in advance of the physical address “00” of the memory block is performed, and the physical address PHYADD_NEXT of the memory block to be accessed this time is “00” (please refer toFIG. 6), which represents a prediction hit occurs. Additionally, the physical address PHYADD_NEXT “00” of the memory block uploads the “B5B4” of the AHQ200in the FIFO method, and the content of the AHQ200now is “001101”, and the content of the default value of the index address “110100” is set to be “00” (please refer toFIG. 11; here, the record505shows that the content of the AHQ200is “001101”, and still accessing of the prediction table202according to the content of the AQH200is still performed, where the content of the AQH200is the index, and the content of the index address “001101” of the prediction table202of theFIG. 11is “01”, so the prediction value PHYADD_NEXT_PREDICTION of the physical address of the memory block this time is “01”, so accessing in advance of the physical address “01” of the memory block is performed. The physical address PHYADD_NEXT of the memory block to be accessed this time is “01” (please refer toFIG. 6), which represents a prediction hit occurs, additionally, the physical address PHYADD_NEXT “01” of the memory block uploads the “B5B4” of the AHQ200in the FIFO method, and the content of the AHQ200now is “010011”, but the content of the index address “001101” is already set to be “01” (please refer toFIG. 12), so does not need to be set again.

From the above it can be seen that the next memory block to be accessed is capable of being predicted precisely through proper procedures to construct the prediction table202. Please note that, in this embodiment, the AQH200only records three continuous physical addresses of the memory block, but this is for illustration purposes only and is not intended as a limitation of the implement method of the prediction table202.

Those skilled in the art will readily observe that numerous modifications and alterations of the apparatus and method may be made while retaining the teachings of the invention.