CN103049398A - Filtering method capable of reducing useless prefetching - Google Patents
Filtering method capable of reducing useless prefetching Download PDFInfo
- Publication number
- CN103049398A CN103049398A CN2012105937967A CN201210593796A CN103049398A CN 103049398 A CN103049398 A CN 103049398A CN 2012105937967 A CN2012105937967 A CN 2012105937967A CN 201210593796 A CN201210593796 A CN 201210593796A CN 103049398 A CN103049398 A CN 103049398A
- Authority
- CN
- China
- Prior art keywords
- prefetching
- line
- address
- information
- replaced
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Images
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Memory System Of A Hierarchy Structure (AREA)
Abstract
Provided is a filtering method capable of reducing useless prefetching. The filtering method capable of reducing useless prefetching relates to the field of the performance optimization of the microprocessor memory access and is capable of reducing the useless prefetching with no data prefetching performance reduced so as to reduce the energy consumption of data prefetching and the bandwidth overhead and also improve energy efficiency of the data prefetching. The filtering method includes the steps of adding prefetching data read by some prefetching data into cache when the prefetching data is sent, taking a cache line of a cache group saved with the prefetching data as a prefetching line of the prefetching information, defining an effective cache line from the cache group to be a replacing line of the prefetching information so as to replace the cache group when all cache lines in the cache group are valid, and saving prefetching line addresses and replacing line addresses of the sent prefetching information to history prefetching information table. The filtering method is capable of effectively reducing the useless prefetching with smaller impact on useful prefetching, and effectively reducing the energy consumption of the data prefetching and the bandwidth overhead in the case of maintaining or improving the performance of the data prefetching, so energy efficiency of the data prefetching is improved.
Description
Technical field
The present invention relates to microprocessor memory access performance optimization field, relate in particular to a kind of adaptive useless filter method of looking ahead.
Background technology
Along with the continuous expansion of performance gap between processor and the storer, memory access latency becomes the key factor of restriction processor performance gradually.The data pre-fetching technology was predicted its memory access address and is sent access request to this memory access address in advance before processor to access data, to hide memory access latency.The data pre-fetching technology mainly can be divided into software prefetching technology and hardware prefetch technology.Wherein, the hardware prefetch technology by in the prefetcher prize procedure operational process repeatably memory access mode (Memory Access Pattern) predict follow-up memory access address and automatically initiate prefetch request.Prefetcher can produce useless looking ahead when the prediction to follow-up memory access address makes a mistake.The useless data of fetching of looking ahead can not used by processor, and it not only can cause the waste of bandwidth and energy consumption, and may have a negative impact because of the performance that causes buffer memory to pollute subprogram.Therefore, reducing useless looking ahead is the key that improves prefetching performance and efficiency.
Summary of the invention
Technical matters to be solved by this invention provides a kind of useless filter method of looking ahead, and can reduce useless looking ahead when not reducing data prefetching performance, to reduce energy consumption and the bandwidth cost of data pre-fetching, improves the efficiency of data pre-fetching.
In order to solve the problems of the technologies described above, the invention provides a kind of useless filter method of looking ahead, when certain prefetching information is issued, the prefetch data that described prefetching information is read adds in the buffer memory, to preserve the cache lines of buffer memory group of described prefetch data as the prefetched line of this prefetching information, if all cache lines of buffer memory group are all effective, determine from the buffer memory group that then an effective cache lines replaces out described buffer memory group as the line to be replaced of this prefetching information, prefetched line address and the line to be replaced address of described issued prefetching information is kept in the prefetching history information table.
Further, when certain prefetching information is filtered, the address information of the described prefetching information that is filtered is kept in the prefetching history information table as the prefetched line address.
The order of being accessed by processor according to prefetched line and line to be replaced further, judges whether to filter this prefetching information.
Further, whether judge with the prefetching information that is filtered whether described prefetching information is filtered according to processor.
Further, from the buffer memory group, determine an effective cache lines as an alternative the row method of replacing out described buffer memory group be:
First in first out replacement method, a kind of in replacement method and the least recently used replacement method at random.
Further, the prefetching history information table comprises following 4 territories:
The prefetched line address field is used for the prefetched line address of storing whole prefetching informations;
The prefetched line significance bit, whether the prefetched line that is used for each prefetched line address field of sign is effective;
The line to be replaced address field is for the line to be replaced address of storing the buffer memory group that all is replaced out because of prefetching information;
The line to be replaced significance bit, whether the line to be replaced that is used for each line to be replaced address field of sign is effective.
Further, described prefetching history information table adopts complete association or set associative structure.
Further, when processor or prefetcher access cache, the address search prefetching history information table of reference address or the cache lines that is replaced according to demand, and upgrade the value of corresponding list item in the filter counter according to following situation:
1) if the demand reference address is identical with the effective prefetched line address of arbitrary list item preservation in the prefetching history information table, then prefetched line is used by processor prior to line to be replaced, this prefetching information is not filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address subtracted 1;
2) if the demand reference address is identical with the effective line to be replaced address of arbitrary list item preservation in the prefetching history information table, then line to be replaced is used by processor prior to prefetched line, this prefetching information causes buffer memory to replace out a useful cache lines, this prefetching information is filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address added 1;
3) when buffer memory is replaced out a cache lines, if the address of this cache lines is identical with the effective prefetched line address of arbitrary list item preservation in the prefetching history information table, then this prefetching information data of fetching just were replaced out buffer memory before being used by processor, this prefetching information is filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address added 1.
Further, described filter counter is several counter arrays, the useless prefetching information filtration condition in the storage area of each counter sign in the described counter array.
Compared with prior art, prefetched line and line to be replaced address that the present invention uses prefetching history information table record to send prefetching information, first accessed to judge whether filter this prefetching information by processor according to its prefetched line or line to be replaced afterwards, and add up these historical informations in order to draw the conclusion of filtering or sending the prefetching information of new generation.Simultaneously, for fear of filtering mistakenly useful prefetching information, the present invention also records the address information of the prefetching information that is filtered in the prefetching history information table, whether judge with the prefetching information that is filtered whether it should be filtered according to processor afterwards, and add up these historical informations and filter feedback mechanism in order to make up.The present invention can effectively reduce useless looking ahead on the less situation of the useful impact of looking ahead, thereby effectively reduces energy consumption and the bandwidth cost of data pre-fetching in the situation of maintenance or raising data prefetching performance, improves the efficiency of data pre-fetching.
Description of drawings
Fig. 1 is the structural representation of the prefetching history information table of the embodiment of the invention.
Embodiment
For making the purpose, technical solutions and advantages of the present invention clearer, hereinafter in connection with accompanying drawing embodiments of the invention are elaborated.Need to prove that in the situation of not conflicting, the embodiment among the application and the feature among the embodiment be combination in any mutually.
The embodiment of the invention utilizes the prefetching history information table to preserve the address information of issued prefetching information and the prefetching information that is filtered.
Described prefetching history information table adopts complete association or set associative structure.
As shown in Figure 1, each list item of prefetching history information table is preserved the address information of a prefetching information that has sent or be filtered, and the prefetching history information table comprises following 4 territories:
Prefetched line address field (PAddr) is used for the prefetched line address of storing whole prefetching informations;
Prefetched line significance bit (PV), whether the prefetched line that is used for each prefetched line address field of sign is effective;
Line to be replaced address field (VAddr) is for the line to be replaced address of storing the buffer memory group that all is replaced out because of prefetching information;
Line to be replaced significance bit (VV), whether the line to be replaced that is used for each line to be replaced address field of sign is effective.
The embodiment of the invention is utilized the useless filtration condition of looking ahead of filter counter sign.Whether the concrete finger of the useless filtration condition of looking ahead filters described prefetching information.
Directly mapping, complete association and set associative are three kinds of typical buffer memorys (or storage) institutional frameworks.Under direct mapping structure, each data can only be stored in the fixed position (index is carried out by the address in this position) in the storage; Under the complete association structure, each data can leave any position (do not need to use the address to carry out index, need to relatively store the label of preserving all positions and find data) in the storage in; Under the set associative structure, storage is divided into several groups, each group comprises several row, each data can only be stored in some group of storage (this group is carried out index by the address), but in this group, can leave any one row (label that all row are preserved in needing more every group finds data) in.
Wherein, complete association structure also can be counted as only having the set associative structure of a group.
When data were more, directly mapping structure was because memory location of a plurality of data contentions can cause higher conflict to be lost efficacy; The conflict of complete association structure was lost efficacy minimum, but realized that cost is higher; The set associative structure then can lose efficacy and the realization cost in the balance conflict.
Described filter counter can be several counter arrays.Physical address space is being divided into the identical storage area (such as the storage area that physical address space can be divided into the 8MB size) of size, the useless filtration condition of looking ahead in the storage area of each counter sign in the counter array.When prefetcher produces new prefetching information, use prefetching information allocation index filter counter, the value (being the useless filtration condition of looking ahead) of reading corresponding list item is to determine to send or filter this prefetching information.
Can come the index filter counter with the most significant digit to 23 of physical address, with the value of upgrading or reading corresponding list item.
The embodiment of the invention has proposed a kind of adaptive useless filter method of looking ahead, and when certain prefetching information is issued or filters, the address information of the described prefetching information that has sent and be filtered is kept in the prefetching history information table.
For issued prefetching information, the prefetch data that described prefetching information is read adds in the buffer memory, to preserve the cache lines of buffer memory group of prefetch data as prefetched line, if all row of buffer memory group are all effective, then according to replace Algorithm, from the buffer memory group, determine as an alternative capable buffer memory group of replacing out of an effective cache lines, prefetched line address and the line to be replaced address of described issued prefetching information are kept in the prefetching history information table, and prefetched line significance bit and line to be replaced significance bit are all put 1.
Common replace Algorithm mainly contains three kinds: first in first out (FIFO, First In First Out), at random (Random) and least recently used (LRU, Least Recently Used).At present, most widely used is the LRU replace Algorithm, recording processor is to the operating position of each cache lines in the buffer memory group, select least-recently-used cache lines to replace away that (can realize the LRU replace Algorithm based on stack: each buffer memory group is safeguarded a stack, and the element of stack is each cache lines of this buffer memory group; When the processor access buffer memory hits, accessed cache lines is moved on to stack top; When the processor access buffer memory occur to lose efficacy, the cache lines that will be at the bottom of the stack was replaced away, and the cache lines that will deposit new data in moves on to stack top).
When judging issued prefetching information this being filtered, the order of being accessed by processor according to prefetched line and line to be replaced judges whether filter this prefetching information.
For the prefetching information that is filtered, because the prefetching information that is filtered can not send access request, can not add any data toward buffer memory yet, therefore, there is not line to be replaced in it, the address information of the described prefetching information that is filtered is kept in the prefetching history information table as the prefetched line address, and with prefetched line active position 1, simultaneously with the zero clearing of line to be replaced significance bit.
When judging the prefetching information be filtered whether this being filtered, whether judge with the prefetching information that is filtered whether it should be filtered according to processor.
When the useless filter method of looking ahead is looked ahead when filtering out useful because of prediction error, the address information that is filtered prefetching information is used for making up filters feedback mechanism, occurs with the situation of avoiding continuing filtering how useful prefetching information.The present invention adds up the above-mentioned historical information that whether should be filtered about the prefetching information that sends or be filtered, and is used for instructing the filtration to the prefetching information of follow-up new generation.
When processor or prefetcher access cache, the address search prefetching history information table of reference address or the cache lines that is replaced according to demand, and upgrade the value of corresponding list item in the filter counter according to following situation:
1) if the demand reference address is identical with the effective prefetched line address of arbitrary list item preservation in the prefetching history information table, then prefetched line is used by processor prior to line to be replaced, this prefetching information is useful prefetching information, this prefetching information should not be filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address subtracted 1;
2) if the demand reference address is identical with the effective line to be replaced address of arbitrary list item preservation in the prefetching history information table, then line to be replaced is used by processor prior to prefetched line, this prefetching information causes buffer memory to replace out a useful cache lines, the cache lines that this prefetching information should be filtered to avoid useful is replaced away the performance loss that causes, and this moment, the value with the corresponding filter counter list item in prefetching information address added 1;
3) when buffer memory is replaced out a cache lines, if the address of this cache lines is identical with the effective prefetched line address of arbitrary list item preservation in the prefetching history information table, then this prefetching information data of fetching just were replaced out buffer memory before being used by processor, this prefetching information should be filtered to avoid energy consumption and bandwidth waste, and this moment, the value with the corresponding filter counter list item in prefetching information address added 1.
For avoiding repeatedly upgrading filter counter according to some prefetching informations, when above-mentioned any one condition was satisfied, it is invalid that the present invention puts corresponding list item in the prefetching history information table.When prefetcher produced new prefetching information, the value that the present invention uses the prefetching information address of new generation to read corresponding list item in the filter counter as index if should be worth greater than 0, was then filtered this prefetching information; If should be worth less than or equal to 0, then send this prefetching information.
The embodiment of the invention uses the filter counter statistics to send the prefetched line of prefetching information or the information that line to be replaced is accessed by processor first, is used for drawing the conclusion of filtering or sending the prefetching information of new generation; A prefetching information that is filtered also may be useful prefetching information, and may be wrong to the filtration of this prefetching information this moment.Therefore, whether judge with the prefetching information that is filtered whether it should be filtered, and use this information updating counter according to processor, form and filter feedback mechanism, to avoid filtering mistakenly useful prefetching information.
Pass through said process, the present invention can effectively reduce useless prefetching information on the less situation of useful prefetching information impact, thereby in the situation of maintenance or raising data prefetching performance, effectively reduce energy consumption and the bandwidth cost of data pre-fetching, improve the efficiency of data pre-fetching.
Above embodiment is only unrestricted in order to technical scheme of the present invention to be described, only with reference to preferred embodiment the present invention is had been described in detail.Those of ordinary skill in the art should be appreciated that and can make amendment or be equal to replacement technical scheme of the present invention, and do not break away from the spirit and scope of technical solution of the present invention, all should be encompassed in the middle of the claim scope of the present invention.
Claims (9)
1. useless filter method of looking ahead is characterized in that:
When certain prefetching information is issued, the prefetch data that described prefetching information is read adds in the buffer memory, to preserve the cache lines of buffer memory group of described prefetch data as the prefetched line of this prefetching information, if all cache lines of buffer memory group are all effective, determine from the buffer memory group that then an effective cache lines replaces out described buffer memory group as the line to be replaced of this prefetching information, prefetched line address and the line to be replaced address of described issued prefetching information is kept in the prefetching history information table.
2. filter method as claimed in claim 1 is characterized in that: when certain prefetching information is filtered, the address information of the described prefetching information that is filtered is kept in the prefetching history information table as the prefetched line address.
3. filter method as claimed in claim 1 is characterized in that: the order of being accessed by processor according to prefetched line and line to be replaced judges whether to filter this prefetching information.
4. filter method as claimed in claim 2 is characterized in that: whether judge with the prefetching information that is filtered whether described prefetching information is filtered according to processor.
5. filter method as claimed in claim 1 is characterized in that: from the buffer memory group, determine an effective cache lines as an alternative the row method of replacing out described buffer memory group be:
First in first out replacement method, a kind of in replacement method and the least recently used replacement method at random.
6. filter method as claimed in claim 1, it is characterized in that: the prefetching history information table comprises following 4 territories:
The prefetched line address field is used for the prefetched line address of storing whole prefetching informations;
The prefetched line significance bit, whether the prefetched line that is used for each prefetched line address field of sign is effective;
The line to be replaced address field is for the line to be replaced address of storing the buffer memory group that all is replaced out because of prefetching information;
The line to be replaced significance bit, whether the line to be replaced that is used for each line to be replaced address field of sign is effective.
7. filter method as claimed in claim 6 is characterized in that: described prefetching history information table employing complete association or set associative structure.
8. filter method as claimed in claim 1, it is characterized in that: when processor or prefetcher access cache, the address search prefetching history information table of reference address or the cache lines that is replaced according to demand, and upgrade the value of corresponding list item in the filter counter according to following situation:
1) if the demand reference address is identical with the effective prefetched line address of arbitrary list item preservation in the prefetching history information table, then prefetched line is used by processor prior to line to be replaced, this prefetching information is not filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address subtracted 1;
2) if the demand reference address is identical with the effective line to be replaced address of arbitrary list item preservation in the prefetching history information table, then line to be replaced is used by processor prior to prefetched line, this prefetching information causes buffer memory to replace out a useful cache lines, this prefetching information is filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address added 1;
3) when buffer memory is replaced out a cache lines, if the address of this cache lines is identical with the effective prefetched line address of arbitrary list item preservation in the prefetching history information table, then this prefetching information data of fetching just were replaced out buffer memory before being used by processor, this prefetching information is filtered, and this moment, the value with the corresponding filter counter list item in prefetching information address added 1.
9. filter method as claimed in claim 8, it is characterized in that: described filter counter is several counter arrays, the useless prefetching information filtration condition in the storage area of each counter sign in the described counter array.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2012105937967A CN103049398A (en) | 2012-12-31 | 2012-12-31 | Filtering method capable of reducing useless prefetching |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2012105937967A CN103049398A (en) | 2012-12-31 | 2012-12-31 | Filtering method capable of reducing useless prefetching |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN103049398A true CN103049398A (en) | 2013-04-17 |
Family
ID=48062045
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2012105937967A Pending CN103049398A (en) | 2012-12-31 | 2012-12-31 | Filtering method capable of reducing useless prefetching |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103049398A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113392043A (en) * | 2021-07-06 | 2021-09-14 | 南京英锐创电子科技有限公司 | Cache data replacement method, device, equipment and storage medium |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5752045A (en) * | 1995-07-14 | 1998-05-12 | United Microelectronics Corporation | Power conservation in synchronous SRAM cache memory blocks of a computer system |
| US6560679B2 (en) * | 2000-06-05 | 2003-05-06 | Samsung Electronics Co., Ltd. | Method and apparatus for reducing power consumption by skipping second accesses to previously accessed cache lines |
| US20040153610A1 (en) * | 2003-01-31 | 2004-08-05 | Hua-Chang Chi | Cache controller unit architecture and applied method |
-
2012
- 2012-12-31 CN CN2012105937967A patent/CN103049398A/en active Pending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5752045A (en) * | 1995-07-14 | 1998-05-12 | United Microelectronics Corporation | Power conservation in synchronous SRAM cache memory blocks of a computer system |
| US6560679B2 (en) * | 2000-06-05 | 2003-05-06 | Samsung Electronics Co., Ltd. | Method and apparatus for reducing power consumption by skipping second accesses to previously accessed cache lines |
| US20040153610A1 (en) * | 2003-01-31 | 2004-08-05 | Hua-Chang Chi | Cache controller unit architecture and applied method |
Non-Patent Citations (1)
| Title |
|---|
| 党向磊等: "面向按序执行处理器的预执行指导的数据预取方法", 《电子学报》 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113392043A (en) * | 2021-07-06 | 2021-09-14 | 南京英锐创电子科技有限公司 | Cache data replacement method, device, equipment and storage medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11138121B2 (en) | Systems and methods for efficient cacheline handling based on predictions | |
| US8935484B2 (en) | Write-absorbing buffer for non-volatile memory | |
| CN104166634A (en) | Management method of mapping table caches in solid-state disk system | |
| CN103885728B (en) | A kind of disk buffering system based on solid-state disk | |
| US7793049B2 (en) | Mechanism for data cache replacement based on region policies | |
| CN109983536B (en) | Memory circuit responsive to tag match commands | |
| CN100541455C (en) | Reduce page or leaf in the system of use demand paging technique and replace a time method and an equipment | |
| US9582282B2 (en) | Prefetching using a prefetch lookup table identifying previously accessed cache lines | |
| CN103645859B (en) | A kind of magnetic disk array buffer storage method of virtual SSD and SSD isomery mirror image | |
| Park et al. | CFTL: A convertible flash translation layer adaptive to data access patterns | |
| CN1361887A (en) | Least recently used replacment method with protection | |
| CN103678169A (en) | Method and system for efficiently utilizing solid-state disk for caching | |
| CN101694640B (en) | Implementation method of the replacement strategy of the shared secondary cache under the multi-core architecture | |
| CN102314397B (en) | Method for processing cache data block | |
| US20190057035A1 (en) | Method of storage management, storage system and computer program product | |
| CN110297787B (en) | Method, device and equipment for accessing memory by I/O equipment | |
| CN109739780A (en) | Dynamic L2 Cache Flash Translation Layer Address Mapping Method Based on Page-Level Mapping | |
| CN104699627B (en) | A kind of caching system and method | |
| CN102768645A (en) | Solid state disk (SSD) prefetching method for mixed caching and SSD | |
| CN102110073B (en) | A replacement device and method for on-chip shared cache and corresponding processor | |
| WO2015004422A1 (en) | Data store and method of allocating data to the data store | |
| KR101180288B1 (en) | Method for managing the read and write cache in the system comprising hybrid memory and ssd | |
| CN110659305B (en) | High-performance relational database service system based on nonvolatile storage system | |
| CN102521161B (en) | Data caching method, device and server | |
| Wang et al. | ZFTL: A zone-based flash translation layer with a two-tier selective caching mechanism |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C02 | Deemed withdrawal of patent application after publication (patent law 2001) | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20130417 |