Search

CN-122019416-A - Distribution scheduling method for cache address labels

CN122019416ACN 122019416 ACN122019416 ACN 122019416ACN-122019416-A

Abstract

The invention discloses an allocation scheduling method for cache address labels, which relates to the technical field of computer cache management and is used for solving the problem of cache quota unbalance; according to the invention, an access home identifier driven tag view and a tag quota model are introduced into the final level cache, tag target quota, guaranteed bottom quota and limit quota of different tasks in each cache group are modeled and bound, a substitution candidate set is limited by combining underallocation, normal and overallocation states when a cache is missed, a substitution object is selected according to tag priority, multiplexing degree and short-lifetime tag mark, then closed-loop adjustment is carried out on quota parameters and tag priority through statistics of hit rate, substitution rate and response time in a period, so that cache address tag allocation is adaptively converged along with load change, and the overall hit rate and key service delay stability under multi-tenant and mixed load scenes are considered, and the utilization rate of the final level cache resources and the running reliability of the system are improved.

Inventors

  • LIN JIAQI

Assignees

  • 深圳市捷龙存储科技有限公司

Dates

Publication Date
20260512
Application Date
20260126

Claims (10)

  1. 1. The allocation scheduling method for the cache address labels is characterized by comprising the following specific steps: In the last level of cache controller, an access attribution identifier is added for each cache access, a cache group index and an address label are obtained according to an access address, a label view is maintained in each cache group, the address label, the attribution identifier and the access state of a cache line are recorded by the label view, and the label view is updated when hit or replacement is carried out; When the system is initialized or configured to be changed, a label quota model is established for each access attribution identifier in each cache group according to the task type and the service level, wherein the label quota model comprises a target quota, a guaranteed bottom quota, a limit quota and a label priority and is associated with the access attribution identifier and the cache group index; When the cache is not hit and a new label is needed to be inserted into the target cache group, comparing the occupied number of the labels in the cache group with a label quota model according to the current visit attribution counted by the label view, and dividing the current state into an underfit state, a normal state or an overfit state; Defining a replacement candidate set according to the state, preferentially reserving other attributive warranty quota labels in an undermatched state, preferentially selecting a replacement object in the current attributive label in an overmatched state, determining the replacement object in each attributive label by integrating the label priority and the multiplexing degree in a normal state, and writing a new label and an access attribution identifier into a label view; Summarizing the hit condition, the replacement condition and the corresponding response time of each access attribution in each cache group in a preset statistical period, adjusting the target quota, the guaranteed quota, the limit quota and the tag priority in the tag quota model according to a preset rule, and participating the adjusted tag quota model in cache access scheduling in the next statistical period.
  2. 2. The method for cache address tag allocation scheduling of claim 1, wherein maintaining a tag view for each cache set comprises: distributing a label record structure for each cache line in each cache group, and establishing a label view record table, wherein the label record structure at least comprises an address label value, an access attribution identifier, a latest access timestamp, an access count value, a multiplexing degree mark and a reserved mark field; When the cache access hits, updating the latest access time stamp in the tag record structure corresponding to the hit cache line according to the current time, increasing the access count value according to a preset rule, and updating the multiplexing degree mark according to the access count value and the time interval, wherein the multiplexing degree mark represents the multiplexing degree of the tag in a preset time window; When the cache is replaced or newly inserted into the cache line, updating an address tag value in a tag record structure corresponding to the replacement position to a new tag, updating an access attribution identifier to a current access attribution, initializing a latest access time stamp to a current time, initializing an access count value to a preset initial value, and resetting a multiplexing degree tag and a reservation tag to initial states; after hit updating and replacement updating are completed, counting the occupied number of the labels corresponding to each access attribution in each cache group according to the access attribution identification field in the label view.
  3. 3. The method for cache address tag allocation scheduling as recited in claim 1, wherein establishing a tag quota model for each access home identifier at each cache group upon system initialization or configuration change comprises: Calculating a basic quota proportion corresponding to each access attribution identifier according to the task type, the service grade parameter, hit rate statistics, average response time index and access strength index acquired in the historical operation process; determining a target quota according to the basic quota proportion and the total number of available tags in each cache group, wherein the target quota represents a tag number reference value of the access attribution in the cache group; setting an underlying quota on the basis of the target quota, wherein the underlying quota is not lower than the value obtained by subtracting the first quota offset from the target quota; setting a limiting quota on the basis of the target quota, wherein the limiting quota is not lower than the target quota and not higher than an upper limit value of the total number of available tags of the corresponding cache group; Generating a tag priority parameter for each access attribution identifier according to the service grade and the time delay sensitivity degree of the task type, combining the tag priority parameter with a target quota, a guaranteed quota and a limit quota into a tag quota model, and storing indexes according to the access attribution identifiers and the cache group indexes.
  4. 4. The method for allocating and scheduling cache address labels according to claim 1, wherein when a cache misses and a new label is needed to be inserted into a target cache set, the occupation amount of the labels in the cache set according to the current access attribution counted by a label view is compared with a label quota model, and the current state is divided into an underallocation state, a normal state or an overallocation state, and the method specifically comprises the following steps: Counting the occupied number of the tags of the current visit attribution in the target cache group according to the tag view, accumulating the tag insertion times and the tag hit times of the visit attribution in the cache group in a preset time window, and calculating the average occupied number of the tags in the time window; comparing the average tag occupation quantity with the guaranteed bottom quota, the target quota and the limit quota in the tag quota model, and dividing the state of the current access attribution in the cache group into an underallocated state when the average tag occupation quantity is smaller than the guaranteed bottom quota; When the average tag occupation quantity is larger than the limit quota, dividing the state of the current access attribution in the cache group into a super-allocation state; dividing the state of the current access attribution in the cache group into a normal state when the average tag occupation quantity is between the guaranteed bottom quota and the limited quota and the difference value between the average tag occupation quantity and the target quota falls into a preset tolerance range; and taking the underallocation state, the normal state and the overallocation state as state input in the label allocation and replacement scheduling process.
  5. 5. The allocation scheduling method for cache address tags of claim 1, wherein defining a replacement candidate set and determining a replacement object in an underfit state comprises: in the target cache group, acquiring the occupation quantity of the labels of all access attributions and the warranty quota value in the label quota model from the label view, and adding no replacement candidate set to the label records of the access attributions, the occupation quantity of the labels of which is smaller than or equal to the corresponding warranty quota value; Adding the label records of the visit attributions, the number of which is larger than the corresponding warranty quota value, into the replacement candidate set; In the replacement candidate set, a replacement ordering key is constructed according to the label priority parameter and the multiplexing degree mark in the label record, and the label record with the label priority parameter belonging to a preset low priority level and the multiplexing degree mark representing that the multiplexing degree is at the preset low multiplexing degree level is arranged at the front part of the replacement ordering key; And selecting a cache behavior replacement position corresponding to the label record with the front sequence according to the replacement sequence key, and writing a new label and a current access attribution identifier in the replacement position.
  6. 6. The allocation scheduling method for cache address tags of claim 1, wherein defining a replacement candidate set and determining a replacement object in the super-match state comprises: Selecting a replacement candidate object from a label record corresponding to the current visit attribution in the label view in the target cache group; Calculating an access interval index according to the multiplexing degree mark and the latest access time stamp for the label record corresponding to the current access attribution; When at least two replacement candidate objects exist, setting a first replacement priority for the label records marked as short lifetime labels in the replacement candidate objects, setting a second replacement priority for the label records not marked as short lifetime labels, wherein the first replacement priority is higher than the second replacement priority, and arranging the short lifetime label records corresponding to the first replacement priority at the forefront part of the replacement ordering key; And selecting a cache behavior replacement position corresponding to the label record with the front sequence according to the replacement sequence key, and writing a new label and a current access attribution identifier in the replacement position.
  7. 7. The method for cache address tag allocation scheduling of claim 6, wherein determining the replacement object by combining tag priority and multiplexing in a normal state comprises: collecting all label records corresponding to the access attribution from the label view in the target cache group, and removing the label records marked as valid reserved marks; Calculating the access frequency of unit time according to the access count value and the preset time window length for the residual label record, and writing the access frequency of unit time into a multiplexing degree mark as a multiplexing degree calculation result; constructing a replacement scoring function based on the label priority parameter and the multiplexing degree label, and combining the label priority weight and the multiplexing degree weight in the replacement scoring function according to a preset proportion to obtain a replacement scoring value corresponding to each label record; And sequencing the label records according to the replacement score value from high to low, arranging the replacement score value at a corresponding cache behavior replacement position of the leading label record, and writing a new label and a current access attribution identifier in the replacement position.
  8. 8. The method for cache address tag allocation scheduling of claim 7, wherein the short lifetime tag identification and restriction comprises: In each cache group, calculating the life cycle length and the hit proportion of the tags based on the insertion times, the hit times and the latest access time stamp of each tag record in the tag view, and marking the tag record with the life cycle length smaller than a preset access times threshold and the hit proportion lower than a preset hit threshold as a short lifetime tag; And maintaining a short-lifetime tag counter in each cache group, counting the number of short-lifetime tags in the current cache group according to the short-lifetime tags in the tag records, and selecting a replacement candidate object only in the short-lifetime tag records and not selecting the replacement candidate object in the non-short-lifetime tag records when the number of the short-lifetime tags reaches a preset short-lifetime tag upper limit value during tag allocation and replacement scheduling.
  9. 9. The method for allocating and scheduling cache address labels according to claim 8, wherein summarizing label hit, replacement and corresponding response time of each access attribute in each cache group in a preset statistical period comprises: Setting a statistics register for each access attribution in each cache group, wherein the statistics register records the hit times of the tags, the replacement times of the tags, the average value of the occupied number of the tags and the number of the access requests in a statistics period; When the statistics period is finished, calculating hit rate according to the number of times of hit of the tag and the number of access requests, calculating replacement rate according to the number of times of replacement of the tag and the number of access requests, comparing the hit rate, the replacement rate, the average value of the number of occupied tags and response time index of corresponding access attribution with a preset parameter threshold, and when the hit rate is lower than the lower limit of hit rate and the response time index is higher than the upper limit of response time, increasing target quota and guaranteed bottom quota of the access attribution in a cache group tag quota model and correspondingly reducing limit quota; When the average value of the occupied quantity of the labels is higher than the target quota and the hit rate is lower than a preset hit threshold, reducing the target quota and the guaranteed quota of the access attribution in the cache group label quota model, and correspondingly reducing the limit quota or the label priority parameter; writing the updated label quota model back to storage, and participating in label allocation and replacement scheduling in the next statistical period.
  10. 10. The method for allocating and scheduling cache address tags according to claim 9, wherein the hot spot cache set detection and tag subgroup redirection comprises: setting a hot spot monitoring counter for each cache group in each cache partition, wherein the hot spot monitoring counter records the label replacement times and the superconfiguration state duration time in a preset time window, and marks the corresponding cache group as a hot spot cache group when the label replacement times exceed a replacement times threshold and the superconfiguration state duration time exceeds a duration time threshold; Selecting a cache group with label replacement times lower than a preset threshold and average label occupation quantity lower than a target quota from other cache groups belonging to the same cache partition as the hot spot cache group as a sub-group, and establishing a label sub-group mapping table between the hot spot cache group and the sub-group, wherein the label sub-group mapping table records a hot spot cache group identifier, an access attribution identifier and a sub-group set; When the access attribution is accessed to the hot spot cache group currently and a new label is needed to be inserted, a target subgroup is selected from the subgroup set according to a label subgroup mapping table, the new label and the current access attribution identification are written into a corresponding cache line of the target subgroup, when the label searching is executed, the access attribution with the label subgroup mapping is carried out, the label matching is carried out on the hot spot cache group firstly, and then the label matching is carried out on each subgroup recorded in the label subgroup mapping table.

Description

Distribution scheduling method for cache address labels Technical Field The invention relates to the technical field of computer cache management, in particular to an allocation scheduling method for cache address labels. Background In the multi-core processor and the cloud computing platform, a plurality of processing cores, virtual machines and service instances share the last level of cache, and the cache address labels are used for realizing the quick hit of the main memory access. The prior art generally relies on traditional replacement strategies and static partitioning means to regulate cache resources, such as replacement algorithms based on access frequency or access time, cache partitioning mechanisms based on way count or address coloring, and based on overall hit rate and hardware structure constraints, cache space is uniformly scheduled to improve throughput capacity and average response performance under general load, and such schemes have formed more mature engineering practice under single application or load stabilization scenarios. However, in an actual running environment facing multi-tenant and mixed load, the prior cache management technology has obvious defects in address tag allocation and scheduling dimensions that on one hand, a tag occupation relationship is usually formed passively by a local replacement strategy, a tag quota model with access attribution identification as granularity is lacked, occupation boundaries among different tasks cannot be expressed on a cache group level, a problem that a certain burst access attribution intensively occupies tags in part of the cache group to cause frequent eviction of other critical task working sets easily occurs, on the other hand, statistics of the existing scheme on tag hit conditions, replacement conditions and response time stays in an integral or coarse granularity dimension, statistics results are difficult to be directly fed back to tag allocation and replacement decisions, tag quota and priority cannot be adaptively adjusted according to load changes, so that cache resource utilization efficiency and service level guarantee capability are insufficient, and technical problems of uncontrollable performance jitter and service delay easily occur under a scene of sharing the last level of cache are solved. Disclosure of Invention In order to overcome the above-mentioned defect of the prior art, there is the following scheme to solve the problem of cache quota unbalance in the above-mentioned background art. In order to achieve the above purpose, the present invention provides the following technical solutions: an allocation scheduling method for cache address labels comprises the following steps: In the last level of cache controller, an access attribution identifier is added for each cache access, a cache group index and an address label are obtained according to an access address, a label view is maintained in each cache group, the address label, the attribution identifier and the access state of a cache line are recorded by the label view, and the label view is updated when hit or replacement is carried out; When the system is initialized or configured to be changed, a label quota model is established for each access attribution identifier in each cache group according to the task type and the service level, wherein the label quota model comprises a target quota, a guaranteed bottom quota, a limit quota and a label priority and is associated with the access attribution identifier and the cache group index; When the cache is not hit and a new label is needed to be inserted into the target cache group, comparing the occupied number of the labels in the cache group with a label quota model according to the current visit attribution counted by the label view, and dividing the current state into an underfit state, a normal state or an overfit state; Defining a replacement candidate set according to the state, preferentially reserving other attributive warranty quota labels in an undermatched state, preferentially selecting a replacement object in the current attributive label in an overmatched state, determining the replacement object in each attributive label by integrating the label priority and the multiplexing degree in a normal state, and writing a new label and an access attribution identifier into a label view; Summarizing the hit condition, the replacement condition and the corresponding response time of each access attribution in each cache group in a preset statistical period, adjusting the target quota, the guaranteed quota, the limit quota and the tag priority in the tag quota model according to a preset rule, and participating the adjusted tag quota model in cache access scheduling in the next statistical period. Further, maintaining the tag view at each cache set includes: distributing a label record structure for each cache line in each cache group, and establishing a label view record table, wherein the label record