公开(公告)号：US20050235114A1

公开(公告)日：2005-10-20

申请号：US11151363

申请日：2005-06-13

申请人： Nimrod Megiddo ,  Dharmendra Modha

发明人： Nimrod Megiddo ,  Dharmendra Modha

IPC分类号： G06F12/00 ,  G06F12/12

CPC分类号： G06F12/123 ,  G06F12/122 ,  G06F12/127 ,  G06F2212/502

摘要： An adaptive replacement cache policy dynamically maintains two lists of pages, a recency list and a frequency list, in addition to a cache directory. The policy keeps these two lists to roughly the same size, the cache size c. Together, the two lists remember twice the number of pages that would fit in the cache. At any time, the policy selects a variable number of the most recent pages to exclude from the two lists. The policy adaptively decides in response to an evolving workload how many top pages from each list to maintain in the cache at any given time. It achieves such online, on-the-fly adaptation by using a learning rule that allows the policy to track a workload quickly and effectively.

摘要翻译： 自适应替换高速缓存策略除了缓存目录之外，还动态维护两个页面列表，新近度列表和频率列表。 该策略将这两个列表大致相同的大小，缓存大小c。 一起，两个列表记住了适合缓存的页面数量的两倍。 在任何时候，策略都会选择要从两个列表中排除的最新页面的可变数量。 该策略自适应地决定响应于不断变化的工作负载，在任何给定时间，来自每个列表的顶页数量将保持在高速缓存中。 它通过使用允许策略来快速有效地跟踪工作负载的学习规则来实现在线，即时的适应。

公开(公告)号：US20060080510A1

公开(公告)日：2006-04-13

申请号：US10964474

申请日：2004-10-12

申请人： Michael Benhase ,  Binny Gill ,  Thomas Jarvis ,  Dharmendra Modha

发明人： Michael Benhase ,  Binny Gill ,  Thomas Jarvis ,  Dharmendra Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/123 ,  G06F12/0866

摘要： A method is disclosed to manage a data cache. The method provides a data cache comprising a plurality of tracks, where each track comprises one or more segments. The method further maintains a first LRU list comprising one or more first tracks having a low reuse potential, maintains a second LRU list comprising one or more second tracks having a high reuse potential, and sets a target size for the first LRU list. The method then accesses a track, and determines if that accessed track comprises a first track. If the method determines that the accessed track comprises a first track, then the method increases the target size for said first LRU list. Alternatively, if the method determines that the accessed track comprises a second track, then the method decreases the target size for said first LRU list. The method demotes tracks from the first LRU list if its size exceeds the target size; otherwise, the method evicts tracks from the second LRU list.

摘要翻译： 公开了一种管理数据高速缓存的方法。 该方法提供包括多个轨道的数据高速缓存，其中每个轨道包括一个或多个段。 该方法还维护包括具有低再利用潜力的一个或多个第一轨道的第一LRU列表，维护包括具有高重用潜力的一个或多个第二轨道的第二LRU列表，并设置第一LRU列表的目标大小。 然后，该方法访问轨道，并且确定所访问的轨道是否包括第一轨道。 如果方法确定所访问的轨道包括第一轨道，则该方法增加所述第一LRU列表的目标大小。 或者，如果该方法确定所访问的轨道包括第二轨道，则该方法减小所述第一LRU列表的目标大小。 该方法如果其大小超过目标大小，则会从第一个LRU列表中降低轨道; 否则，该方法从第二LRU列表中逐出轨道。

公开(公告)号：US20070220201A1

公开(公告)日：2007-09-20

申请号：US11384939

申请日：2006-03-20

申请人： Binny Gill ,  Dharmendra Modha

发明人： Binny Gill ,  Dharmendra Modha

IPC分类号： G06F13/00 ,  G06F12/00

CPC分类号： G06F12/123 ,  G06F12/0804 ,  G06F12/0868 ,  G06F2212/1016 ,  G06F2212/262

摘要： A storage system has a storage controller for an array of storage disks, the array being ordered in an sequence of write groups. A write cache is shared by the disks. The storage controller temporarily stores write groups in the write cache, responsive to write groups being written, and lists the write groups in order of their sequence in the array and in circular fashion, so that a lowest is listed next to a highest one of the write groups. The storage controller selects the listed write groups in rotating sequence. Such a write group is destaged from the write cache to the disk responsive to i) the selecting of the write group and ii) a state of a recency indicator for the write group, wherein the recency indicator shows recency of writing to the write group.

摘要翻译： 存储系统具有用于存储盘阵列的存储控制器，阵列以写入组的顺序排序。 写缓存由磁盘共享。 存储控制器根据写入的组写入临时存储写入组中的写入组，并且按顺序在数组中以循环方式列出写入组，使得最低级别列在 写组。 存储控制器以旋转顺序选择列出的写入组。 响应于i）写入组的选择和ii）写入组的新近度指示符的状态，这样一个写入组从写入高速缓冲存储器移动到盘中，其中新近度指示符表示对写入组的写入的新近。

公开(公告)号：US20060129782A1

公开(公告)日：2006-06-15

申请号：US11014529

申请日：2004-12-15

申请人： Sorav Bansal ,  Paul McKenney ,  Dharmendra Modha

发明人： Sorav Bansal ,  Paul McKenney ,  Dharmendra Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/121 ,  G06F12/122 ,  G06F12/124 ,  G06F2212/502

摘要： An apparatus, system, and method are disclosed for dynamically allocating main memory among applications. The apparatus includes a cache memory module configured to maintain a first list and a second list, each list having a plurality of pages, and a resize module configured to resize the cache by adaptively selecting the first or second list and subtracting pages from or adding pages to the selected list. The system includes the apparatus and a cache replacement module configured to adaptively distribute a workload between the first list and the second list. The method includes maintaining a first list and a second list, each list having a plurality of pages, maintaining a cache memory module having a selected size, and resizing the selected size by adaptively selecting the first or second list and adding pages to the selected list to increase the selected size and subtracting pages from the selected list to decrease the selected size.

摘要翻译： 公开了用于在应用程序之间动态分配主存储器的装置，系统和方法。 该设备包括：高速缓存存储器模块，被配置为维护第一列表和第二列表，每个列表具有多个页面;以及调整大小模块，其被配置为通过自适应地选择第一列表或第二列表以及从页面中增加或添加页面来调整高速缓存大小 到所选列表。 该系统包括装置和配置成在第一列表和第二列表之间自适应地分配工作负载的高速缓存替换模块。 该方法包括维护第一列表和第二列表，每个列表具有多个页面，维护具有所选大小的高速缓存存储器模块，以及通过自适应地选择第一列表或第二列表以及将页面添加到所选列表来调整所选大小的大小 以增加所选的大小，并从所选列表中减去页面以减少所选的大小。

公开(公告)号：US20060069871A1

公开(公告)日：2006-03-30

申请号：US10954937

申请日：2004-09-30

申请人： Binny Gill ,  Dharmendra Modha

发明人： Binny Gill ,  Dharmendra Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/0862 ,  G06F12/0866 ,  G06F12/123

摘要： A self-tuning, low overhead, simple to implement, locally adaptive, novel cache management policy that dynamically and adaptively partitions the cache space amongst sequential and random streams so as to reduce read misses.

公开(公告)号：US20060069876A1

公开(公告)日：2006-03-30

申请号：US10955201

申请日：2004-09-30

申请人： Sorav Bansal ,  Dharmendra Modha

发明人： Sorav Bansal ,  Dharmendra Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/121 ,  G06F12/126 ,  G06F2212/502

摘要： A method and system of managing data retrieval in a computer comprising a cache memory and auxiliary memory comprises organizing pages in the cache memory into a first and second clock list, wherein the first clock list comprises pages with short-term utility and the second clock list comprises pages with long-term utility; requesting retrieval of a particular page in the computer; identifying requested pages located in the cache memory as a cache hit; transferring requested pages located in the auxiliary memory to the first clock list; relocating the transferred requested pages into the second clock list upon achieving at least two consecutive cache hits of the transferred requested page; logging a history of pages evicted from the cache memory; and adaptively varying a proportion of pages marked as short and long-term utility to increase a cache hit ratio of the cache memory by utilizing the logged history of evicted pages.

摘要翻译： 一种在包括高速缓冲存储器和辅助存储器的计算机中管理数据检索的方法和系统，包括将高速缓冲存储器中的页面组织成第一和第二时钟列表，其中第一时钟表包括具有短期效用的页面和第二时钟列表 包括具有长期效用的页面; 请求在计算机中检索特定页面; 将位于高速缓冲存储器中的请求页面识别为高速缓存命中; 将位于辅助存储器中的请求的页面传送到第一时钟列表; 在传送的请求页面的至少两个连续的缓存命中时，将传送的所请求的页面重定位到第二时钟列表中; 记录从高速缓存中排出的页面的历史记录; 并且自适应地改变标记为短期和长期效用的页面的比例，以通过利用所记录的被驱逐的页面的历史来增加缓存命中率。

公开(公告)号：US20050086436A1

公开(公告)日：2005-04-21

申请号：US10690303

申请日：2003-10-21

申请人： Dharmendra Modha

发明人： Dharmendra Modha

IPC分类号： G06F12/12 ,  G06F12/00

CPC分类号： G06F12/124 ,  G06F12/123 ,  G06F2212/502

摘要： A method for adaptively managing pages in a cache memory with a variable workload comprises defining a cache memory; organizing the cache into disjoint lists of pages, wherein the lists comprise lists T1, T2, B1, and B2; maintaining a bit that is set to either “S” or “L” for every page in the cache, which indicates whether the bit has short-term utility or long-term utility; ensuring that each member page of T1 is marked either as “S” or “L”, wherein each member page of T1 and B1 is marked as “S” and each member page of T2 and B2 is marked as “L”; and maintaining a temporal locality window parameter such that pages that are re-requested within a window are of short-term utility and pages that are re-requested outside the window are of long-term utility, wherein the cache comprises pages that are members of any of lists T1 and T2.

摘要翻译： 用于以可变工作负载自适应地管理高速缓冲存储器中的页面的方法包括定义高速缓冲存储器; 将缓存组织成不相交的页面列表，其中列表包括列表T 1，T 2，B 1和B 2 为缓存中的每个页面保留一个被设置为“S”或“L”的位，这表示该位是否具有短期效用或长期效用; 确保T＆lt; 1＆gt; 1的每个成员页面被标记为“S”或“L”，其中T 1＆lt; 1＆lt; 1＆lt; 1＆lt; 1＆lt; >标记为“S”，将T＆lt; 2＆lt; 2＆gt;和B＆gt; 2＆lt; 2＆gt;的每个成员页面标记为“L”; 并且维护时间局部性窗口参数，使得在窗口内重新请求的页面具有短期效用，并且在窗口之外重新请求的页面是长期有用的，其中，高速缓存包括作为 列表T 1和T 2中的任何一个。

公开(公告)号：US20070118695A1

公开(公告)日：2007-05-24

申请号：US11282157

申请日：2005-11-18

申请人： Steven Lowe ,  Dharmendra Modha ,  Binny Gill ,  Joseph Hyde

发明人： Steven Lowe ,  Dharmendra Modha ,  Binny Gill ,  Joseph Hyde

IPC分类号： G06F12/00 ,  G06F13/00

CPC分类号： G06F12/123 ,  G06F12/0866 ,  G06F12/127

摘要： In a data storage controller, accessed tracks are temporarily stored in a cache, with write data being stored in a first cache (such as a volatile cache) and a second cache and read data being stored in a second cache (such as a non-volatile cache). Corresponding least recently used (LRU) lists are maintained to hold entries identifying the tracks stored in the caches. When the list holding entries for the first cache (the A list) is full, the list is scanned to identify unmodified (read) data which can be discarded from the cache to make room for new data. Prior to or during the scan, modified (write) data entries are moved to the most recently used (MRU) end of the list, allowing the scans to proceed in an efficient manner and reducing the number of times the scan has to skip over modified entries Optionally, a status bit may be associated with each modified data entry. When the modified entry is moved to the MRU end of the A list without being requested to be read, its status bit is changed from an initial state (such as 0) to a second state (such as 1), indicating that it is a candidate to be discarded. If the status bit is already set to the second state (such as 1), then it is left unchanged. If a modified track is moved to the MRU end of the A list as a result of being requested to be read, the status bit of the corresponding A list entry is changed back to the first state, preventing the track from being discarded. Thus, write tracks are allowed to remain in the first cache only as long as necessary.

摘要翻译： 在数据存储控制器中，将访问的轨道临时存储在高速缓存中，其中写入数据被存储在第一高速缓存（例如易失性高速缓存）和第二高速缓存中，并且将读取的数据存储在第二高速缓存（例如， 易失性缓存）。 保持相应的最近使用的（LRU）列表来保存标识存储在高速缓存中的轨道的条目。 当保存第一个缓存（A列表）的条目的列表已满时，将扫描列表以识别可以从缓存中丢弃的未修改（读取）数据，为新数据腾出空间。 在扫描之前或期间，修改（写入）数据条目移动到列表的最近使用（MRU）端，允许扫描以有效的方式继续进行，并减少扫描必须跳过修改的次数 条目可选地，状态位可以与每个修改的数据条目相关联。 当修改的条目移动到A列表的MRU结尾而不被请求读取时，其状态位从初始状态（例如0）改变到第二状态（例如1），表示它是 候选人被丢弃。 如果状态位已经设置为第二个状态（如1），那么它将保持不变。 如果作为被请求读取的结果将经修改的轨道移动到A列表的MRU端，则相应的A列表条目的状态位被改回到第一状态，防止轨道被丢弃。 因此，仅在需要时才允许写轨迹保留在第一缓存中。

公开(公告)号：US20050071599A1

公开(公告)日：2005-03-31

申请号：US10676464

申请日：2003-09-30

申请人： Dharmendra Modha ,  Divyesh Jadav ,  Pawan Goyal ,  Renu Tewari

发明人： Dharmendra Modha ,  Divyesh Jadav ,  Pawan Goyal ,  Renu Tewari

IPC分类号： G06F9/50 ,  G06F12/12 ,  G06F12/00

CPC分类号： G06F9/5016 ,  G06F12/0871 ,  G06F12/12 ,  G06F2212/282 ,  G06F2212/6042

摘要： A method and system for dynamically allocating cache space in a storage system among multiple workload classes each having a unique set of quality-of-service (QoS) requirements. The invention dynamically adapts the space allocated to each class depending upon the observed response time for each class and the observed temporal locality in each class. The dynamic allocation is achieved by maintaining a history of recently evicted pages for each class, determining a future cache size for the class based on the history and the QoS requirements where the future cache size might be different than a current cache size for the class, determining whether the QoS requirements for the class are being met, and adjusting the future cache size to maximize the number of classes in which the QoS requirements are met. The future cache sizes are increased for the classes whose QoS requirements are not met while they are decreased for those whose QoS requirements are met.

摘要翻译： 一种用于在多个工作负载类别中动态地分配存储系统中的高速缓存空间的方法和系统，每个工作负载类别具有唯一的服务质量（QoS）要求。 本发明根据每个类的观察到的响应时间和每个类中观察到的时间局部性动态地适应分配给每个类的空间。 通过维护每个类别的最近被逐出的页面的历史来实现动态分配，基于历史和QoS要求确定将来的高速缓存大小，其中将来的高速缓存大小可能与该类的当前高速缓存大小不同， 确定是否满足该类的QoS要求，以及调整未来的高速缓存大小以最大化满足QoS要求的类的数量。 对于满足QoS要求的类，对于满足QoS要求的用户而言，对于不满足QoS要求的类，对于未来的高速缓存大小会有所增加。

公开(公告)号：US20070250660A1

公开(公告)日：2007-10-25

申请号：US11407797

申请日：2006-04-20

申请人： Binny Gill ,  Dharmendra Modha

发明人： Binny Gill ,  Dharmendra Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/0804 ,  G06F12/0866 ,  G06F2212/222

摘要： A technique for determining when to destage write data from a fast, NVS of a computer system from an upper level to a lower level of storage in the computer system comprises adaptively varying a destage rate of the NVS according to a current storage occupancy of the NVS; maintaining a high threshold level for the NVS; maintaining a low threshold level that is set to be a predetermined fixed amount below the high threshold; setting the destage rate of the NVS to zero when the NVS occupancy is below the low threshold; setting the destage rate of the NVS to be maximum when the NVS occupancy is above the high threshold; linearly increasing the destage rate of the NVS from zero to maximum as the NVS occupancy goes from the low to the high threshold; and adaptively varying the high threshold in response to a dynamic computer storage workload.

摘要翻译： 一种用于确定何时从计算机系统的快速NVS将计算机系统的写入数据从计算机系统中的较高级别存储到较低级别的存储装置的技术包括根据NVS的当前存储占用自适应地改变NVS的流率 ; 维持NVS的高门槛值; 保持低阈值水平，其被设置为低于高阈值的预定固定量; 当NVS占用率低于低阈值时，将NVS的流出率设置为零; 当NVS占用率高于高阈值时，将NVS的流出率设置为最大值; 随着NVS占用率从低到高的阈值，将NVS的流失率从零线性上升到最大值; 以及响应于动态计算机存储工作负载自适应地改变高阈值。