TWI684099B

TWI684099B - 剖析快取替代

Info

Publication number: TWI684099B
Application number: TW105141709A
Authority: TW
Inventors: 張治中
Original assignee: 美商谷歌有限責任公司
Priority date: 2016-02-10
Filing date: 2016-12-16
Publication date: 2020-02-01
Also published as: GB2547306B; JP2018537770A; CN107066397B; TW201732603A; EP3414665B1; US20170228322A1; GB201620880D0; DE202016107157U1; CN107066397A; EP3414665A1; GB2547306A; KR20180056736A; JP6613375B2; US10387329B2; WO2017139037A1; DE102016225545A1; KR102043886B1

Abstract

本發明揭示剖析快取替代。剖析快取替代係一種用於管理一主記憶體與一快取記憶體之間的資料遷移以改良總體系統性能之技術。不同於習知快取替代技術，剖析快取替代採用一剖析工具以維持計數器，計數器計數不僅存取維持在快取記憶體中之頁面亦存取維持在主記憶體中之頁面之記憶體請求。基於由該剖析工具收集之(例如關於記憶體存取請求之)資訊，一移動器移動主記憶體與快取記憶體之間的頁面。舉實例而言，移動器可交換主記憶體之高度請求頁面(諸如主記憶體之一最多請求頁面)與快取記憶體之較少請求頁面(諸如快取記憶體之一最少請求頁面)。移動器可在(例如)計數器指示主記憶體之高度請求頁面之頁面存取請求之數目大於快取記憶體之較少請求頁面之頁面存取請求之數目時實行該交換。移動器在背景中執行頁面交換以不阻礙記憶體使用者(例如客戶端應用程式)之操作。為此，移動器受限於依預定時間間隔(諸如每微秒(µs)一次)交換頁面。

Description

剖析快取替代

在計算中，一快取係用於頻繁存取之資料之暫時儲存之一記憶體塊，且允許快取資料之未來請求比非快取資料之請求服務更快。若請求資料含於快取中(稱為一「快取命中」之一方案)，則請求可僅由讀取快取服務，讀取快取相比而言比自主記憶體存取資料快。相反地，若請求資料未含於快取中(稱為一「快取未中」之一方案)，則重新計算資料或在習知技術中，將資料自其原始儲存位置填充至快取中，這比僅自快取讀取資料慢。因此，就速度而言，當資料請求之一較大部分自快取記憶體服務時改良總體系統性能。由於快取記憶體通常比主記憶體小，所以先前填充至快取中之資料可需要由最近使用之資料替代。藉此，採用快取替代演算法。習知快取替代演算法包含最近最少使用(LRU)演算法、最近最多使用(MRU)演算法、罕用(LFU)演算法、隨機替代演算法等等。一般而言，快取替代演算法係一電腦程式或一硬體維持結構實施用於管理快取記憶體之最佳化指令之一集合。特定言之，快取替代演算法選擇清除快取記憶體中的哪個資訊以為來自主記憶體之資訊騰出空間。諸多習知快取替代演算法不維持關於當前未在快取記憶體中之資料區塊中之資訊。因此，當資料之一工作集之一大小超過快取記憶體之一大小時，可產生過量填充及清除訊務。此過量填充及清除訊務可引起稱為「顛簸」之一條件，其中若干快取未中急劇增加且執行快取填充及清除所花費之時間因未中而可超過執行資料之該工作集之原始請求計算操作所花費之時間。相應地，習知快取替代演算法具有能夠妨礙計算操作之缺點。

本發明描述一種剖析快取替代。剖析快取替代係一種用於管理一主記憶體與一快取記憶體之間的資料遷移以改良總體系統性能之技術。快取記憶體及主記憶體兩者經組態以儲存資料之頁面—該快取記憶體比該主記憶體小且因此能夠維持比該主記憶體少之頁面。然而，相較於該主記憶體，該快取記憶體具有較低延遲、較高頻寬或較低電力使用之至少一者。因此，系統性能在可自該快取記憶體服務資料存取請求之一較大部分時改良。剖析快取替代快取該快取記憶體中之高度請求頁面且遷移該主記憶體中之較少請求頁面(或將較少請求頁面留在該主記憶體中)以增加自該快取記憶體服務之資料存取請求之部分。不同於習知快取替代技術，剖析快取替代採用一剖析工具以維持計數器，計數器計數不僅存取維持在快取記憶體中之頁面亦存取維持在主記憶體中之頁面之記憶體請求。基於由該剖析工具收集之(例如關於記憶體存取請求之)資訊，一移動器移動主記憶體與快取記憶體之間的頁面。舉實例而言，移動器可交換主記憶體之高度請求頁面(諸如主記憶體之一最多請求頁面)與快取記憶體之較少請求頁面(諸如快取記憶體之一最少請求頁面)。移動器可在(例如)計數器指示主記憶體之高度請求頁面之頁面存取請求之數目大於快取記憶體之較少請求頁面之頁面存取請求之數目時實行該交換。由記憶體使用者執行之請求不因快取未中而被阻擋以不阻礙記憶體使用者(例如客戶端應用程式)之操作，且移動器在背景中執行頁面交換。就非阻擋行為而言，當一頁面存取請求導致一快取未中時，所請求之頁面未立即載入至快取記憶體中使得可自快取記憶體服務該請求。相反，直接自主記憶體服務該請求。就在背景中執行頁面交換而言，優先經由移動器執行之頁面交換服務由記憶體使用者執行之請求。藉此，移動器受限於依預定時間間隔(諸如每微秒(µs)一次)交換頁面。在一預定時間間隔下，移動器判定主記憶體中之一高度請求頁面之頁面存取請求之數目是否超過快取記憶體之一較少請求頁面之頁面存取請求之數目。若主記憶體中之一高度請求頁面之頁面存取請求之數目超過快取記憶體之一較少請求頁面之頁面存取請求之數目，則移動器交換主記憶體之高度請求頁面與快取記憶體之較少請求頁面。藉此，剖析快取替代最佳化快取記憶體填充之頁面，且在不會干擾記憶體使用者之操作之情況下執行該最佳化，結果係改良系統性能。提供本「發明內容」以引入關於在以下「實施方式」中進一步描述之技術之簡化概念。本「發明內容」不意欲識別所主張之標的之基本特徵，亦不意欲用於判定所主張之標的之範疇。

相關申請案 本申請案根據35 U.S.C. § 119規定主張名稱為「Profiling Cache Replacement」之2016年2月10日申請之臨時申請案第62/293,688號之優先權，其全部內容以引用的方式併入本文中。概述本發明描述使用剖析快取替代之技術及啟用剖析快取替代之裝置。通過使用此等技術及裝置，依一經由習知快取替代技術(諸如最近最少使用(LRU)演算法、最近最多使用(MRU)演算法、罕用(LFU)演算法、隨機替代演算法等等)改良系統性能之方式來管理一主記憶體與一快取記憶體之間的資料遷移。相對於習知技術，改良性能至少部分地由與使資料在該主記憶體與該快取記憶體之間遷移同時發生之減少「顛簸」之量造成。術語「顛簸」指稱由可在資料之一工作集之一大小超過該快取記憶體之一大小時產生之過量填充及清除訊務引起之一條件。顛簸可導致若干快取未中急劇增加，其引起系統比執行執行資料之該工作集之原始請求計算操作花費更多時間用於執行所得未中之快取填充及清除。通過應用剖析快取替代，可依一減少顛簸且改良總體系統性能之方式來管理快取記憶體及主記憶體中之資料。舉實例而言，一記憶體使用者(諸如一客戶端應用程式)可請求存取載入在記憶體中之一特定頁面。在此實例中，假定該客戶端應用程式自記憶體存取該特定頁面作為一初始化程序之部分。在該初始化程序期間，該客戶端應用程式可請求多次存取該特定頁面。為了最高效地服務該客戶端應用程式之請求，該特定頁面可載入至快取記憶體中(例如)使得該特定頁面之請求可比自主記憶體服務時快。在完成該初始化程序之後，該客戶端應用程式可不需要存取該特定頁面，或可相對於其他頁面較少存取該特定頁面。在正常操作期間，該客戶端應用程式可代以請求存取更多存取其他頁面，使得用於存取其他頁面之請求最終超過用於該特定頁面之請求—此係由於已完成該初始化程序且不再請求該特定頁面。因此，由於(例如)儘管快取記憶體在大小上比主記憶體小，但其具有比主記憶體低之延遲、比主記憶體高之頻寬或比主記憶體低之電力使用，所以可藉由服務來自快取記憶體之其他頁面之請求而改良該客戶端應用程式之正常操作之效率。換言之，可藉由交換其他頁面之一者與該特定頁面而改良效率。「交換」(如本文所使用)指稱使對應於另一頁面之資料能夠填充至快取記憶體中且清除對應於來自快取記憶體之該特定頁面之資料之一動作或一系列動作。在一些方案中，對應於另一頁面之資料僅與對應於該特定頁面之資料交換，使得另一頁面之資料替代快取記憶體中之特定頁面之資料且該特定頁面之資料替代主記憶體中之另一頁面之資料。在此等方案中，當快取一頁面時，頁面之資料僅駐留在快取記憶體中而不是主記憶體中。然而，在其他方案中，記憶體中之各頁面之至少一些資料存在於主記憶體中，不管是否存取對應於資料之一頁面。在此等方案中，當快取一頁面時，快取記憶體中之一頁面及主記憶體中之一頁面一起提供頁面之有效資料。然而，在一些例項中，因為快取記憶體中之一些頁面未填充，所以該等頁面可不含有效資料。主記憶體中之一些頁面在(諸如)該等頁面之全部資料已在快取記憶體中修改時亦可不含有效資料。在此等方案中，交換特定頁面之資料與對應於另一頁面之資料不僅係如所描述之第一方案中之資料之一交換。確切而言，交換涉及清除對應於來自快取記憶體之特定頁面之資料至主記憶體中之一各自頁面。在各自頁面中，在快取記憶體中時修改之資料之部分複製到主記憶體中之各自頁面—由於各自頁面仍維持未修改之區塊之相同資料，所以複製受限於所修改之區塊。在清除之後，快取記憶體(資料自快取記憶體清除)之頁面填充來自主記憶體之另一頁面之資料。然而，各自頁面(例如被清除之資料放置於其中之頁面)及另一頁面(例如用以填充可用快取記憶體頁面之主記憶體資料)不對應於相同頁面。無論主記憶體及快取記憶體組態之方式及因此主記憶體及快取記憶體之頁面交換之方式如何，在交換之後可自快取記憶體服務另一頁面。為判定何時交換主記憶體與快取記憶體之間的頁面及在主記憶體與快取記憶體之間交換哪些頁面，剖析快取替代計數存取維持在主記憶體及快取記憶體中之資料之頁面。特定言之，使用計數器來追蹤「可定址記憶體」中之頁面之存取。術語「可定址記憶體」指稱由記憶體使用者辨識之記憶體之部分。在恰在上文描述之第一方案中，可定址記憶體之大小對應於主記憶體之一大小加上快取記憶體之大小。然而，在其他方案中，可定址記憶體之大小僅對應於主記憶體之大小。因此，若干計數器維持對應於主記憶體中之若干頁面。藉此，一剖析工具可維持可定址記憶體中之頁面之各者之計數器且當請求存取該等頁面之一者時，增量頁面之計數器。在上文所討論之其他記憶體組態及交換方案中，針對可定址記憶體中之各頁面維持一計數器，(例如)針對主記憶體中之各頁面維持一計數器，此係由於所快取之頁面亦由主記憶體中之資料表示。返回至討論在初始化期間多次存取特定頁面之客戶端應用程式，在初始化之後不請求存取或請求較少存取特定頁面且請求在正常操作期間更多存取其他頁面。由剖析工具在某刻維持之計數器指示請求存取其他頁面之至少一者已比請求存取特定頁面多。一旦如此，經組態以將頁面自主記憶體移動至快取記憶體(且反之亦然)之一移動器可交換比特定頁面請求更多之其他頁面之一者與特定頁面。特定言之，該移動器可將最多請求頁面自主記憶體移動至快取記憶體中，且可將特定頁面自快取記憶體移動至主記憶體中。為防止客戶端應用程式之操作中斷，未阻擋由客戶端應用程式執行之請求，且在背景中執行交換頁面以最佳化維持在快取記憶體中之資料之行為。特定言之，當一頁面存取請求導致一快取未中時，所請求之頁面未立即載入至快取記憶體中使得可自快取記憶體服務該請求。相反，直接自主記憶體服務該請求。此外，移動器受限於依預定時間間隔(諸如每微秒(μs)一次)啟動頁面交換。因此，移動器不與用於在其他時間存取主記憶體或快取記憶體之客戶端應用程式競爭。使用此等技術，可避免計算操作之中斷及減少顛簸，藉此改良系統之總體性能。此僅係其中可執行剖析快取替代之方式之一簡單實例，下文提供其他實例及細節。本發明現轉至一實例性環境，該環境參考展示頁面計數器值之圖，在參考之後，描述裝置及方法及一實例性計算系統。實例性環境 圖1係其中可採用剖析快取替代之一實例性環境100之一圖式。環境100繪示具有剖析記憶體104之一記憶體剖析計算裝置102。在圖1之特定實例中，記憶體剖析計算裝置102組態為一智慧型電話，然而，可設想其他組態。後續圖式中繪示能夠使用剖析快取替代最佳化記憶體之記憶體剖析計算裝置102之其他組態。環境100亦繪示剖析記憶體104之組件。剖析記憶體104包含快取記憶體106及主記憶體108。快取記憶體106及主記憶體108能夠儲存用於由記憶體使用者(諸如由一操作系統、客戶端應用程式等等)存取之資料。例如，快取記憶體106及主記憶體108能夠儲存資料之頁面。術語「頁面」(如本文所使用)指稱相同大小之資料之區塊(例如4千位元組(KB)之資料之區塊)。相對於主記憶體108，快取記憶體106較小—其具有比主記憶體108小之儲存且因此能夠儲存比主記憶體108少之資料之頁面。儘管就儲存而言比主記憶體108小，但快取記憶體具有比主記憶體108低之延遲、比主記憶體108高之頻寬或比主記憶體108低之電力使用之至少一者。歸因於快取記憶體106之此等特性，就速度、電力或系統效率之一些其他量測而言，服務資料存取請求之一較大部分及快取資料而不是未快取資料導致記憶體剖析計算裝置102之更有效請求服務。剖析記憶體104亦包含映射器110、剖析工具112及移動器114。射器110、剖析工具112及移動器114表示藉由快取高度使用頁面且將較少使用頁面留在主記憶體108中而最佳化剖析記憶體104之性能之功能。映射器110用於各記憶體存取。映射器110將一輸入位址映射至快取記憶體106中之一位址(例如一快取命中)或映射至主記憶體108中之一位址(例如一快取未中)。相比於習知技術，當一頁面存取請求導致一快取未中時，所請求之頁面未立即載入至快取記憶體106中使得可自快取記憶體106服務該請求。相反，直接自主記憶體108服務該請求，例如，將所請求之頁面提供至請求直接自主記憶體108存取頁面之一記憶體使用者。剖析工具112表示收集關於記憶體存取之資訊之功能。舉實例而言，剖析工具112追蹤頁面存取之數目，諸如用於存取剖析記憶體104中之頁面之請求之一數目。儘管本文使用其中追蹤存取各頁面之請求之數目之實例來描述技術，但剖析工具112可在不會背離本文描述之技術之精神或範疇之情況下以不同方式追蹤記憶體存取。當請求之大小在各請求上不一致時，例如(諸如)當一些請求用於64 B而其他請求用於128 B時，剖析工具112可計數位元組替代請求之數目。替代地，剖析工具112可將記憶體中之存取頁面之較大請求視為多個請求。在其他實例中，可在無需計數存取一頁面之各請求之情況下追蹤記憶體存取。確切而言，可追蹤一頁面之讀取請求但不追蹤寫入請求。同樣地，可追蹤一頁面之寫入請求而不追蹤讀取請求。無論用以追蹤存取頁面之記憶體之單元如何，剖析工具112可針對快取記憶體106中之各頁面及主記憶體108中之各頁面維持一計數器。當請求存取一頁面時，剖析工具112可增量該頁面之計數器，藉此追蹤頁面存取。然而，在一或多個實施方案中，剖析工具112維持記憶體之各頁面一個以下計數器。藉此，剖析工具112可減少用以儲存追蹤資訊之記憶體之量，追蹤資訊描述剖析記憶體104之頁面存取。下文描述其中剖析工具112針對記憶體之各頁面使用一個以下計數器之方式之細節。移動器114表示在快取記憶體106與主記憶體108之間移動頁面之功能。例如，移動器114能夠交換主記憶體108之高度請求頁面與快取記憶體106之較少請求頁面。術語「高度」請求頁面或若干頁面(如本文所使用)指稱比考慮記憶體之部分中之其他頁面請求更多之頁面，且可對應於考慮部分中之一最多請求頁面、該部分中之前10%請求頁面等等。例如，主記憶體108中之一高度請求頁面可為請求之數目在主記憶體108之頁面中排名前10%之一頁面，或其可為主記憶體108中之最多請求頁面。類似地，術語「較少」請求頁面或若干頁面指稱比考慮記憶體之部分中之其他頁面請求更少之頁面，且可對應於考慮部分中之一最少請求頁面、該部分中之後10%請求頁面等等。舉實例而言，快取記憶體106中之一較少請求頁面可為請求之數目在快取記憶體106之頁面中排名後10%之一頁面，或其可為快取記憶體106中之最少請求頁面。然而，應注意「高度」及「較少」結合對應於頁面之記憶體之部分使用。因此，主記憶體108中之一高度請求頁面可具有比快取記憶體108中之一較少請求頁面少之存取請求之一數目，或可具有一類似數目之請求。然而，主記憶體108中之一高度請求頁面具有比主記憶體108中之一較少請求頁面大之存取請求之一數目。另外，剖析記憶體104中之一高度請求頁面(例如主記憶體108及快取記憶體106中之頁面中)具有比剖析記憶體104中之較少請求頁面大之存取請求之一數目。無論如何，移動器114可回應於主記憶體108之高度請求頁面之存取請求比快取記憶體106之較少請求頁面多之一判定而交換主記憶體108之高度請求頁面與快取記憶體106之較少請求頁面。除在快取記憶體106與主記憶體108之間移動頁面之外，移動器114亦表示判定主記憶體108中之頁面之存取是否比快取記憶體106中之頁面多。移動器114可藉由檢查由剖析工具112 (例如計數器)收集之資訊而作出該判定。一旦移動器114移動頁面(例如交換快取記憶體106中之一頁面與主記憶體108中之一頁面)，移動器114將更新由映射器110使用之位址資訊，使得未來記憶體存取請求映射至快取記憶體106或主記憶體108中正確位址。應注意回應於主記憶體108之高度請求頁面之存取請求不比快取記憶體106之較少請求頁面多之一判定，移動器114不交換頁面。對於上下文，考量圖2及圖3，其等繪示主記憶體及快取記憶體之實例性頁面計數器值之圖。圖2之圖200展示一第一時間處之主記憶體及快取記憶體之實例性頁面計數器值，而圖3之圖300展示第一時間之後的一第二時間處之主記憶體及快取記憶體之實例性頁面計數器值。如下文所更詳細討論，移動器114檢查關於所請求之頁面存取之資訊。移動器114亦依一預定時間間隔(例如每微秒(µs)一次)啟動頁面交換。參考該預定時間間隔，對應於圖200之該第一時間可在發生此一特定預定時間間隔之前而對應於圖200之該第二時間在發生該特定時間間隔之後。圖200包含對應於指示頁面存取之數目之計數器值之一第一軸202。圖200之一第二軸204表示維持在記憶體中之頁面。圖200亦包含分界線206。繪示於分界線206左邊之條表示該第一時間處之快取記憶體106中之頁面之計數器值，而繪示於分界線右邊之條表示該第一時間處之主記憶體108中之頁面之計數器值。在由圖2及圖3繪示之特定實例中，快取記憶體106係128兆位元組(128 MB)，主記憶體108係4吉位元組(4 GB)，且資料之各頁面係4千位元組(4 KB)。因此，分界線206左邊之條表示4-KB頁面之128 MB值，而分界線206右邊之條表示4-KB頁面之4 GB值(1百萬頁面)。應瞭解此等僅為示例性大小且快取記憶體106、主記憶體108及維持在記憶體中之頁面之大小可在不會背離本文描述之技術之精神或範疇之情況下隨實例中使用之大小變化。為更易於理解所闡釋之概念，圖2及圖3已經繪示以表示上述方案，其中對應於主記憶體108中之頁面之資料僅與對應於快取記憶體106中之頁面之資料交換，使得當快取一頁面時，頁面之資料在快取記憶體106中而不在主記憶體108中。在此等方案中，記憶體使用者將可定址記憶體辨識為4 GB及128 MB之組合(例如主記憶體108及快取記憶體106之一組合)。然而，在實施方案中，當快取記憶體106相對於主記憶體108而較小時(128 MB相對於4 GB)，主記憶體108及快取記憶體106可根據上述其他記憶體組態及交換方案而組態。在上述其他記憶體組態及交換方案，快取記憶體106中之一頁面及主記憶體108中之一頁面一起提供一快取頁面之有效資料。在此等其他方案中，當快取頁面時，對應於所快取之頁面之至少一些資料可在快取記憶體106中且對應於所快取之頁面之至少一些資料亦可在主記憶體108中。然而，在一些例項中，因為快取記憶體106中之一些頁面未填充，所以該等頁面可不含有效資料。主記憶體108中之一些頁面在(諸如)該等頁面之全部資料已在快取記憶體106中修改時亦可不含有效資料。根據此等其他組態及交換方案，且鑑於其中主記憶體108係4 GB且快取記憶體係128 MB之實例，記憶體使用者將可定址記憶體辨識為僅4 GB (例如僅主記憶體108)。當將來自主記憶體108之一4-KB頁面之資料填充至快取記憶體106中時，移動器114可不將該頁面之4-KB之資料之各部分填充至快取記憶體106中。例如，移動器114可代以將1 KB之頁面之資料填充至快取記憶體106中。移動器可(諸如)在就是否將使用另3 KB而言存在某些不確定性時填充接近一請求位址之該1 KB之資料。當預期一頁面之大多數請求為寫入請求時，移動器114可不填充將重寫至快取記憶體106中之頁面之資料。確切而言，移動器114可將用於指示尋找該頁面之各64位元組部分之位置之資訊填充至快取記憶體106中。返回至圖2及圖3之所繪示之實例，表示頁面之條可依下降計數器值順序自左至右排序，且亦在快取記憶體106及主記憶體108之邊界內。因此，表示快取記憶體106中之最多存取頁面之頁面存取之數目之條208對應於比表示快取記憶體106中之第二多存取頁面之頁面存取之數目之條210大之一計數器值。類似地，表示主記憶體108中之第二少存取頁面之頁面存取之數目之條212對應於比表示主記憶體108中之最少存取頁面之頁面存取之數目之條214大之一計數器值。特別注意條216、218，條216、218分別表示第一時間處之快取記憶體106中之一最少請求頁面及主記憶體108中之一最多請求頁面。在繪示之實例中，條216比條218小，且因此表示在第一時間處，存取快取記憶體106中之該最少請求頁面之請求比存取主記憶體108中之該最多請求頁面之請求少。圖300類似於圖200，其包含表示計數器值及維持在記憶體中之頁面、維持在快取記憶體106及主記憶體108中之頁面之間的分界線等等。然而，在一顯著方面，圖300不同於圖200。在圖300中，交換條216、218，表示快取記憶體106與主記憶體108之間的對應頁面之一交換。換言之，圖300繪示一方案，其中由條216表示之頁面(例如由移動器114)移動至主記憶體108中且由條218表示之頁面(例如由移動器114)移動至快取記憶體106中。如上文所提及，圖200對應於一第二時間而圖300對應於該第一時間之後的一第二時間。為了闡明，可假定在圖2及圖3中尚未在第一時間與第二時間之間執行存取由所繪示之條表示之頁面之請求。換言之，圖200、300中表示之頁面之計數器值在兩個時間中相同。然而，在第一時間與第二時間之間，假定出現一移動時間，在此時間期間移動器114交換快取記憶體106與主記憶體108之間的頁面。因此，第一時間及第二時間可分別表示就在該移動時間之前及就在該移動時間之後之時間片段。因此，在第一時間與第二時間之間，剖析快取替代技術由移動器114應用以最佳化記憶體剖析計算裝置102之所快取之頁面。關於圖1之實例性記憶體剖析計算裝置102，考量圖4中之一詳細繪示。記憶體剖析計算裝置102可為各種裝置之一者或一組合，此處繪示六個實例：一智慧型電話102-1、一計算手錶102-2、一數位相機102-3、一膝上型電腦102-4、一平板電腦102-5及一桌上型電腦102-6，儘管亦可使用諸如一隨身型易網機、一遊戲控制台或一機上盒之其他計算裝置及系統。如上文所提示，在一些實施例中至少部分地透過一遠端計算裝置操作此等技術。該遠端計算裝置可組態為(例如)一伺服器。在此等情況中，可(例如)藉由傳達透過具有有限計算操作之一通信裝置啟用計算之資料或甚至將啟用計算之資料自記憶體剖析計算裝置102直接傳達至伺服器而本地(locally)放棄一些計算。記憶體剖析計算裝置102包含一顯示器402 (圖4中展示五個顯示器)、一收發器404、一或多個處理器406及電腦可讀儲存媒體408 (CRM 408)或能夠與一顯示器402 (圖4中展示五個顯示器)、一收發器404、一或多個處理器406及電腦可讀儲存媒體408 (CRM 408)通信。收發器404能夠直接或通過一通信網路發送及接收資料，諸如通過一區域網路、廣域網路、個人區域網路、蜂巢式或近場網路自裝置102接收客戶端應用程式資料。在一或多個實施方案中，快取記憶體106、主記憶體108、剖析工具112、映射器110及移動器114體現在CRM 408上。快取記憶體106包含快取頁面410且主記憶體包含主記憶體載入頁面412 (MM載入頁面412)。剖析工具112包含由剖析工具112收集之關於記憶體存取之記憶體存取資訊414。舉實例而言，記憶體存取資訊414包含指示存取快取頁面410及MM載入頁面412之請求之數目之計數器。CRM 408亦包含將輸入位址(諸如由一記憶體使用者提供以存取快取記憶體或主記憶體中之資訊之頁面之位址)映射至快取記憶體106中之快取頁面410之一者之一位址(一快取命中)或主記憶體108中之MM載入頁面412之一者(一快取未中)之輸入位址映射416。如上文所討論，映射器110用於各記憶體存取，且表示將一輸入位址映射至快取記憶體106或主記憶體108中之一位址之功能。當映射器110接收(例如用於請求存取來自記憶體之資料之一頁面之)一輸入位址時，映射器110可引用輸入位址映射416且回覆快取記憶體106或主記憶體108之一對應位址。剖析工具112亦採用各記憶體存取。特定言之，剖析工具追蹤存取快取頁面410及MM載入頁面412之數目。在一或多個實施方案中，剖析工具112維持快取頁面410之各者及MM載入頁面412之各者之各自計數器作為記憶體存取資訊414之部分。在此方案中，當存取快取頁面410之一者及MM載入頁面412之一者時，剖析工具112增量用於指示存取之各自計數器。然而，在一些實施方案中，維持快取頁面410之各者及MM載入頁面412之各者之一可增量計數器可消耗太多儲存空間。若(例如)剖析工具112使用8位元計數器，主記憶體係4 GB，且MM載入頁面412之各者係4 KB，則1 MB之記憶體僅用於儲存一百萬頁面之計數器—其在(例如)記憶體存取資訊414儲存在靜態隨機存取記憶體(SRAM)中時之一些實施方案中不適合。相應地，剖析工具112可依利用較少儲存之方式追蹤及維持記憶體存取資訊414。剖析工具112可(例如)實施計數器以通過計數器之一範圍之動態擴展減少總計數器儲存或使得記憶體之各頁面存在一個以下計數器。就通過動態擴展減少總計數器儲存而言，在一或多個预设實施方案中剖析工具112使用8位元計數器，且在一或多個其他實施方案中使用動態擴展計數器。可使用浮點表示法以實施範圍動態擴展之計數器。一般而言，快取記憶體106及主記憶體108中之頁面之存取計數具有一高動態範圍，例如高度存取頁面之存取明顯比較少存取頁面之存取多，且高度存取頁面之存取之數目可在系統操作期間繼續增加。在一或多個實施方案(包含其中採用動態擴展計數器之實施方案)中，記憶體中之資料可分成若干集合。換言之，快取頁面410及MM載入頁面412可分成頁面之集合，使得各集合包含一些快取頁面410及一些MM載入頁面412。在其中(例如)快取記憶體106係128 MB、主記憶體108係4 GB且各頁面係4 KB之下一實例中，頁面可分成若干集合使得各集合包含512個MM載入頁面412及16個快取頁面410。當記憶體中資料分成若干集合時，移動器114可交換一集合中之快取頁面410與亦在該集合中之MM載入頁面412。因此，在此實例中，當檢查計數器時，移動器114可檢查512個計數器以判定最多請求頁面及最少請求頁面。然而，移動器114不交換該集合中之快取頁面410與來自其他集合之MM載入頁面412。在動態擴展計數器實施方案中，剖析工具112可對於頁面之各集合保持一公制S，且對於一集合中之各頁面保持一N位元計數器C。舉實例而言，剖析工具可針對使用6個位元之頁面之一集合實施公制S。一般而言，因為計數器值在一集合內比較，例如由於僅交換一相同集合中之快取記憶體106及主記憶體108中之頁面，所以剖析工具112可在頁面分成若干集合時使用一公制。由於具有公制S及N位元計數器C，所以剖析工具112可維持計數器使得計數器之值等於C×2^S 。相比於其中對於一頁面之各存取，剖析工具112增量計數器值達1之剖析快取替代之預設實施方案，在其中使用動態擴展計數器之實施方案中，剖析工具112增加頁面之計數器C達

之一機率。這允許剖析工具112產生S個隨機位元，且接著，僅當S個位元之各者為零時增加計數器。當一頁面之計數器C溢出時(例如當先前N個位元不足以表示頁面存取時)，剖析工具112可增加頁面之設定之公制S達一，且將引起溢出之特定頁面以及集合之其他頁面之計數器值之各者除以2。考量其中採用此用於動態擴展計數器之方案之一情況。剖析工具112可以多種不同方式儲存各計數器值。例如，剖析工具112可儲存等於C之一計數器值，其中C僅係一二進位整數。剖析工具112亦可儲存等於C×2^S 之一計數器值，其中C再次係一二進位整數。剖析工具112亦可使用C之一簡單浮點表示法增加個別計數器之一動態範圍。由剖析工具112儲存之計數器值仍可等於C×2^S ，然而，剖析工具112可按如下編碼C：

此處，項K表示一有效數字，其係由有效數字之有效數位組成之一浮點數字之一部分，且項E表示基數之指數(2為基底)。鑑於此，最終計數器值係：

在此方案中，若假定剖析工具112使用一4位元有效數字K (使得K之值可在0至15之範圍內)且指數係3位元(使得指數之值可在0至7之範圍內)，一7位元計數器C可表示[0,15×2⁷ ]之一範圍內之頁面存取值。考量用於採用動態擴展計數器之一替代方案。在此替代方案中，剖析工具112依一不同方式編碼一個別計數器C。特定言之，編碼取決於針對有效數字K分配之若干位元(在本文中表示為nK)及針對指數E分配之若干位元(在本文中表示為nE)。若指數E等於零，則剖析工具112僅編碼計數器C之值使得計數器C之值等於有效數字K，使得C=K。然而，若指數E大於零，則剖析工具112按如下編碼計數器C之值：

在此替代方案中，若假定針對有效數字nK分配之位元之數目係4位元且針對指數nE分配之位元之數目係3位元，則一計數器可儲存在[0,1984]之一範圍內之值。如上文所提及，除減小個別計數器之一大小(就位元之數目而言)，亦可在一些儲存敏感實施方案中減少若干計數器，例如自記憶體之每頁面一個計數器至記憶體之各頁面之一個以下計數器。就使用記憶體之每頁面一個以下計數器而言，如此為之係基於一觀察：由記憶體使用者(例如客戶端應用程式)使用之資料之工作集結合共同工作負荷不可能等於或超過主記憶體108之一大小。此外，由於剖析快取替代僅因為請求存取該等頁面而涉及將主記憶體108之高度請求頁面快取至快取記憶體106而不是僅將頁面快取至快取記憶體106，所以主記憶體108中之罕有請求頁面之存取之數目針對本文描述之技術而基本無關。相應地，剖析工具112可維持更頻繁存取之頁面之計數器。標籤可用以識別計數器之各者與之相關聯之一頁面以減少用以追蹤快取記憶體106及主記憶體108中之頁面之計數器之數目。當請求存取與一計數器相關聯之一頁面時，剖析工具112依上文描述之方式之一者更新計數器以指示存取。然而，當請求存取不與一計數器相關聯之一頁面(例如其存取當前未由一計數器追蹤之一頁面)時，已用以追蹤一不同頁面之存取之計數器之一者可與不同頁面失去關聯且與經請求但先前未關聯之頁面相關聯。用於使計數器與所追蹤之頁面失去關聯且使計數器與經請求但先前未關聯之頁面相關聯之一些習知技術可引起顛簸。在一或多個實施方案中，剖析快取替代涉及應用一或多個經修改之計數器觸發技術以使計數器與所追蹤之頁面失去關聯且使計數器與經請求但先前未關聯之頁面相關聯。此等經修改之計數器標記技術可相較於習知技術而減少顛簸。剖析工具112藉由維持計數器之一數目N作為記憶體存取資訊414之部分而應用經修改之計數器標記技術。各計數器包括表示呈(例如) {頁面、計數}形式之一資料對，資料對表示識別計數器與之相關聯之一頁面之一頁面標籤及與該頁面相關聯之一計數。當請求存取一特定頁面X時，剖析工具112檢查是否存在與特定頁面X相關聯之一計數器{X、C}。若存在與特定頁面X相關聯之一計數器(例如{X、C})，則剖析工具112增量計數C達1。若無與特定頁面X相關聯之計數器，則剖析工具112發現具有一最小計數C之一頁面Y之一計數器{Y、C}。接著，剖析工具112替代計數器之值使得其與特定頁面X相關聯且指示特定頁面X之一存取，例如剖析工具將{Y、C}之值之對調整為{X、1}。此不同於繼承一先前計數之習知技術。換言之，習知技術可將C替代為C+1，而不是如經修改之計數器標記技術般將C替代為1。藉由使用經修改之計數器標記技術計數頁面存取，具有最大計數之計數器之一數目N對應於前n個頁面。無論如何實施計數器，移動器114表示檢查維持在記憶體存取資訊414中之計數器以判定是否交換主記憶體108與快取記憶體106之間的頁面之功能。如上文所提及，移動器114執行此等檢查以作出該判定以依一預定時間間隔(諸如每微秒(1 µs))啟動頁面交換。儘管本文所討論之實例指稱時間間隔經預定且對應於1 µs，但時間間隔可在不會背離本文所描述之技術之精神或範疇之情況下不同。舉實例而言，亦可基於如下文所更詳細討論之存取之一數目(例如請求存取來自剖析記憶體104之頁面之一總數)等等而隨機判定預定間隔。在預定時間間隔(各微秒)下，移動器114可依據本文所描述之技術作出判定。移動器114可替代地判定每頁面之集合每N個記憶體存取而不使用一絕對時間(例如預定時間間隔)。依此方式，本文所描述之技術可控制所使用之背景頻寬之一百分比替代所使用之背景頻寬之一絕對值。無論頻率如何，在移動時間期間，移動器114經組態以判定主記憶體108之高度請求頁面是否之請求是否比快取記憶體106中之較少請求頁面之請求多。主記憶體108之高度請求頁面相對於MM載入頁面412而高度請求，且快取記憶體106中之較少請求頁面相對於快取頁面410而較少請求。然而，高度請求之主記憶體頁面之請求之數目可實質上類似於較少請求之快取記憶體頁面之請求之數目。若主記憶體108中之高度請求頁面之請求比快取記憶體106中之較少請求頁面之請求多，則移動器114交換主記憶體108中之高度請求頁面與快取記憶體106之較少請求頁面。藉此，移動器114自快取記憶體106清除較少請求頁面且將主記憶體之高度請求頁面填充至快取記憶體106中。由於移動器114之操作與來自記憶體使用者(例如客戶端應用程式)之需求請求競爭，所以使移動器114之判定及交換操作之性能受限於移動時間減小移動器114對記憶體使用者之影響—減少記憶體剖析計算裝置102之記憶體存取之延遲。因此，當記憶體使用者存取來自快取記憶體106及主記憶體108之資料之頁面時移動器114在背景中操作。除使移動器114之操作受限於背景之外，由記憶體使用者執行之頁面存取請求優先於為最佳化記憶體而作出之頁面存取請求(例如由移動器114請求之頁面交換)。存取來自快取記憶體106及主記憶體108之資料之頁面之請求通常可分成兩個類型—需求請求及背景請求。術語「需求請求」指稱由一記憶體使用者(諸如一客戶端應用程式)針對來自快取記憶體106或主記憶體108之資料之一頁面執行之一請求。術語「背景請求」指稱由需求請求間接觸發之一填充或清除請求，諸如由移動器114結合交換主記憶體108與快取記憶體106之間的頁面執行之填充及清除請求。本文所描述之技術以數種方式滿足需求請求優於滿足背景請求。首先，技術可允許(諸如)藉由維持在經組態以保持有限數目個待定背景請求之一佇列中允許有限數目個待定背景請求。若在執行一背景請求時佇列已滿，則僅放棄請求(例如請求未添加至該佇列)。實際上，其他背景請求未添加至佇列直至服務全佇列中之待定背景請求之至少一者。其中本文所描述之技術滿足需求請求優於滿足背景請求之第二方式涉及一實施方案，其中使用一動態隨機存取記憶體(DRAM)請求佇列，且其中允許背景請求填充該DRAM請求佇列之一有限量(例如一半)。若(例如) DRAM請求佇列之一填充位準大於佇列之最大填充位準之一半，則本文所描述之技術使進入請求受限於需求請求。此處，可在DRAM請求佇列之填充位準大於佇列之最大填充位準之一半時延滯背景請求。例如，若太多移動器請求之背景請求待定，則放棄由移動器114啟動之一背景請求。然而，未放棄之由移動器114啟動之背景請求分解為DRAM請求且發送至DRAM請求佇列。若DRAM請求佇列超過一特定臨限值(例如佇列之最大填充位準之一半)，指示DRAM請求佇列太忙而當前無法處置進入DRAM請求，則不將進一步背景請求發送至DRAM請求佇列。相反，保持背景DRAM請求直至DRAM請求佇列位準低於臨限值。一旦DRAM請求佇列能夠再次處置背景DRAM請求，則將所保持之請求發送至DRAM請求佇列。在操作期間，記憶體使用者施加於剖析記憶體104上之工作負荷可隨時間改變。結合改變工作負荷，高度請求頁面亦可改變。換言之，當一客戶端應用程式操作時主記憶體108中快取及高度請求之頁面可不相同於當另一客戶端應用程式操作時主記憶體108中快取及高度請求之頁面。剖析工具112可使頁面計數器之值衰減以確保快取記憶體106填充對應於記憶體剖析計算裝置102之當前操作之頁面。藉由使計數器值在某一衰減間隔下自動衰減，曾大幅存取之頁面可在頁面之用途衰退時自快取記憶體106清除。在一或多個實施方案中，剖析工具112可在衰減間隔下僅將一集合之計數器值之各者分為兩半。考量一實例，其中衰減間隔對應於針對一集合中之頁面請求之存取之一總數之一預定義臨限值(例如2¹⁴ 個存取)。在此實例中，當一集合中之頁面之存取之總數超過2¹⁴ 個存取時，剖析工具112將該集合之計數器值除以2。返回參考使用公制S之實施方案，剖析工具112藉由在一集合之公制S大於零時減小該集合之公制S達1而使計數器衰減。然而，若集合之公制S已為零，則剖析工具112將集合之計數器之各者除以2。在其他實施方案中，衰減間隔對應於某一預定絕對時間而不是存取之預定義數目。應瞭解可在不會背離本文所描述之技術之精神或範疇之情況下依除將計數器除以2之外之方式使計數器衰減。舉實例而言，計數器可乘以諸如三分之二(⅔)之一因數而不是除以2。進一步就在記憶體剖析計算裝置102之操作期間出現之進一步方案而言，在一些情況中快取記憶體106之較少請求頁面及主記憶體108之高度請求頁面之計數器可具有相同或非常相似之值。參考頁面之一集合，該集合之較少請求(相較於其他快取頁面)之快取頁面及主記憶體108之該集合之高度請求頁面可具有相同或非常相似之值。當移動器114判定在快取頁面具有類似於候選以待快取之頁面之計數器值時快取哪些頁面時可產生困難。考量其中一集合之一第一頁面之存取比該集合之其他頁面之存取稍多之一實例。由於具有更多存取，所以移動器114可快取該第一頁面。然而，亦考量稍後該集合之一第二頁面之存取比該第一頁面稍多。歸因於後續存取，移動器114將該第一頁面替代為該第二頁面，藉此將該第一頁面自快取記憶體106清除。在循環引用之頁面之一集合中，該第一頁面之稍多存取可再次引起移動器114替代快取記憶體中之該第二頁面，等等。本方案可引起此等頁面之顛簸，且可在使用衰減計數器且衰減間隔較短時尤其成問題。為防止此顛簸，移動器114可在決定交換主記憶體108中高度請求頁面與快取記憶體106中之較少請求頁面之前新增入口之一障壁。因此，移動器114可代以在高度請求之主記憶體頁面之請求存取之數目大於較少請求之快取頁面之請求存取之數目時決定交換頁面而不是每當高度請求之主記憶體頁面之請求存取之一數目大於較少請求之快取頁面之請求存取之數目時交換主記憶體108之高度請求頁面與快取記憶體106之較少請求頁面。舉實例而言，移動器114可在以下為真時決定交換頁面：

在此表達式中，Δ表示入口障壁且可對應於一預定整數，諸如偏移一資源成本(例如時間、電力等等)以交換頁面之一整數。仍可在不會背離本文所描述之技術之精神或範疇之情況下以其他方式實施剖析快取替代。一替代實施方案之一實例係使用時間多工計數器。替代僅針對最多存取之頁面維持計數器，剖析工具112可針對頁面之各者維持計數器。然而，在任何給定時間，剖析工具112可存取有限數目個計數器。考量其中十六分之一個計數器維持在SRAM中且另十六分之十五個計數器維持在DRAM中之一方案。當請求存取計數器在SRAM中之一頁面時，剖析工具112僅增量計數器。然而，當請求存取計數器在DRAM中之一頁面時，剖析工具112忽略該請求。此等時間多工計數器技術週期性地將SRAM中之計數器清除回DRAM，且將另十六分之一個計數器自DRAM載入至SRAM。假定藉此在一些時段後各計數器將具有約十六分之一個實際存取計數器值。移動器114可經組態以在DRAM及SRAM兩者中檢查計數器。一替代實施例之另一實例係在一頁表資料結構中集束計數器。因此，剖析工具112可在一頁表資料結構中集束計數器替代維持單獨計數器。藉此，計數器之管理可遵循相同於該頁表及一轉換旁看緩衝器(TLB)之一流程。在一替代實施例之另一實例中，可藉由逐漸減少公制S而實施計數器衰減，導致一分率S。所表示之計數器值可藉由逐漸減少公制S而衰減而不是在預定衰減間隔下使各計數器值衰減。下文更詳細闡述此等及其他能力以及其中圖1及圖4之實體起作用及交互之方式。此等實體可經進一步劃分、組合等等。圖1之環境100及圖4之詳細圖解繪示能夠採用所描述之技術之諸多可能環境之一些環境。實例性方法 圖5至圖7描繪啟用或使用剖析快取替代之方法。此等方法展示為指定所執行之操作但不必要受限於經展示用於由各自區塊執行操作之順序或組合。在以下討論之部分中，可參考圖1之環境100及圖4中詳述之實體，參考僅為實例。技術不受限於由在一裝置上操作之一實體或多個實體執行。圖5描繪方法500，其描述根據用於管理快取記憶體與一主記憶體之間的資料遷移之一剖析演算法來替代快取記憶體中之頁面之方式。在502中，更新維持與維持在主記憶體及快取記憶體中之資料之頁面相關聯之計數器。計數器經組態以指示存取維持在主記憶體及快取記憶體中之頁面之請求之一數目。舉實例而言，剖析工具112將計數器維持在記憶體存取資訊414中。此等計數器指示存取快取頁面410及MM載入頁面412之請求之一數目。回應於存取快取頁面410之一者或MM載入頁面412之一者之請求，剖析工具112 (例如)增量記憶體存取資訊414中之對應計數器。在服務由維持在快取記憶體106及主記憶體108中之頁面之記憶體執行之請求之一背景中執行剖析記憶體替代以不干擾記憶體使用者(諸如客戶端應用程式)之存取。藉此，方法步驟504及506之性能可受限於依一預定時間間隔(諸如每微秒(μs))執行。在504中，在該預定時間間隔下，依據計數器而判定主記憶體中之一高度請求頁面之頁面存取請求之一數目是否大於快取記憶體中之一較少請求頁面之頁面存取請求之一數目。主記憶體之高度請求頁面相對於載入在主記憶體中之頁面係高度請求，而快取記憶體之較少請求頁面相對於載入在快取記憶體中之頁面而較少請求。然而，高度請求之主記憶體頁面之請求之數目可實質上類似於較少請求之快取記憶體頁面之請求之數目。舉實例而言，移動器114檢查由記憶體存取資訊414中之剖析工具112維持之計數器。例如，每微秒，移動器114依據計數器而判定(例如請求少於快取記憶體106中之其他頁面之)一較少請求之快取頁面410及(例如請求多於主記憶體108中之其他頁面之)一高度請求之MM載入頁面412。移動器114比較各自計數器值以判定主記憶體108之高度請求頁面之請求是否比快取記憶體106之較少請求頁面之請求多。在506中，回應於高度請求之主記憶體頁面之頁面存取請求之數目大於較少請求之快取記憶體頁面之頁面存取請求之數目之一判定，交換高度請求之主記憶體頁面與較少請求之快取記憶體頁面。舉實例而言，步驟504中之移動器114判定來自主記憶體108之高度請求頁面之請求壁快取記憶體106之較少請求頁面之請求多。回應於此判定，移動器114交換來自主記憶體108之高度請求頁面與快取記憶體106之較少請求頁面。換言之，移動器114自快取記憶體106清除較少請求之快取記憶體頁面且將該頁面載入至主記憶體108。移動器114亦快取高度請求之主記憶體頁面。圖6描繪方法600，其描述其中使用減少空間計數器來計數用於剖析快取替代之頁面存取之方式。在602中，維持記憶體中之頁面之集合之公制。舉實例而言，維持在剖析記憶體104中之資料分成頁面之集合，使得各集合包含來自快取記憶體106之複數個頁面及來自主記憶體108之複數個頁面。特定言之，頁面可分成若干集合，如上文所更詳細描述。對於各集合之資料，剖析工具112維持一公制S，其指示集合之頁面之存取之一基數計數或基數。在一或多個實施方案中，剖析工具112針對各集合之頁面維持4位元公制。應瞭解可在不會背離本文所描述之技術之精神或範疇之情況下使用不同大小之公制(就位元之數目而言)。在604中，維持一集合中之頁面之各者之一計數器且指示相對於該集合中之其他頁面之頁面存取之一數目。舉實例而言，剖析工具112針對一集合中之各頁面維持一N位元計數器，如上文所更詳細描述。一頁面之N位元計數器與該頁面之集合之公制S一起指示該頁面之存取之數目。在606中，回應於存取一頁面之一請求，根據存取更新一對應計數器及公制。舉實例而言，回應於存取一頁面之一請求，剖析工具112更新與所請求之頁面相關聯之一N位元計數器且亦更新與所請求之頁面之集合相關聯之公制S。剖析工具112更新N位元計數器及公制S，如上文所更詳細描述。應瞭解本文所描述之技術可在一或多個儲存敏感實施方案(例如當記憶體存取資訊414儲存在SRAM中時)中利用方法600。圖7描繪方法700，其描述其中使用記憶體之每頁面一個以下計數器來計數用於剖析快取替代之頁面存取之方式。如同方法600，方法700亦可用於一或多個儲存敏感實施方案。在702中，n數目個計數器與記憶體中之前n個存取頁面相關聯。舉實例而言，剖析工具112使n個計數器與剖析記憶體104中之前n個存取頁面相關聯。特定言之，計數器與所快取之剖析記憶體104之頁面相關聯，使其餘計數器與主記憶體108中之下一最多存取頁面相關聯。在704中，接收用以存取維持在記憶體中之一頁面之一請求。舉實例而言，接收用以存取維持在剖析記憶體104中之一頁面(諸如用於存取快取頁面410之一者或MM記載頁面412之一者)之一請求。在706中，判定所請求之頁面是否與計數器之一者相關聯，例如計數器之一者是否具有識別所請求之頁面之一屬性。舉實例而言，剖析工具112判定所請求之頁面是否與經維持作為記憶體存取資訊414之部分之計數器之一者相關聯。若判定所請求之頁面與計數器之一者相關聯(例如在706中為「是」)，則在708中，更新與所請求之頁面相關聯之計數器。舉實例而言，剖析工具112使與所請求之頁面相關聯之一計數器之一計數器值C自C增量至C+1。然而，若判定所請求之頁面不與計數器之一者相關聯(例如在706中為「否」)，則在710中，判定與一計數器相關聯之最少存取頁面。舉實例而言，剖析工具112判定相同於所請求之頁面之頁面之一集合中之一計數器相關聯之一最少存取頁面。替代地，剖析工具112僅判定與計數器相關聯之頁面之最少存取頁面。剖析工具112可藉由及檢查計數器之計數器值而判定最少存取頁面。在712中，最少存取頁面之計數器與所請求之頁面相關聯。舉實例而言，剖析工具112使最少存取頁面與所請求之頁面失去關聯且接著(例如)藉由改變用於識別所請求之頁面之計數器之一標籤使計數器與所請求之頁面相關聯。在714中，調整計數器之一計數器值以反映存取請求。舉實例而言，剖析工具112藉由將計數器值設定為1而調整一計數器值C (其指示先前與計數器相關聯之頁面之存取之一數目)。將計數器值設定為1與涉及將計數器值C設定為C+1之一些習知技術截然不同。藉此，方法700可減少顛簸。先前討論描述與剖析快取替代有關之方法。此等方法之態樣可在硬體(例如固定邏輯電路)、韌體、軟體、手動處理、或其任何組合中實施。此等技術可體現在圖1、圖4及圖8 (計算系統800在下文之圖8中描述)中所展示之實體之一或多者上，實體可進一步劃分、組合等等。因此，此等圖式繪示能夠採用所描述之技術之許多可能系統或設備之一些系統或設備。此等圖式之實體通常表示軟體、韌體、硬體、整個裝置或網路或其等之一組合。實例性計算系統 圖8繪示可實施為如參考先前圖1至圖7所描述之客戶端、伺服器及/或計算裝置之任何類型以實施剖析快取替代之實例性計算系統800之各種組件。在實施例中，計算系統800可實施為之一有線及/或無線可佩戴裝置、晶片系統(SoC)之一者或一組合及/或實施為另一類型之裝置或裝置之部分。計算系統800亦可與一使用者(例如一個人)及/或操作裝置使得一裝置描述包含使用者、軟體、韌體及/或裝置之一組合之邏輯裝置之一實體相關聯。計算系統800包含啟用裝置資料804 (例如所接收之資料、正被接收之資料、經排定用於廣播之資料、資料之資料包等等)之有線及/或無線通信的通信裝置802。裝置資料804或其他裝置內容可包含裝置之組態設定、儲存在裝置上之媒體內容及/或與裝置之一使用者相關聯之資訊。儲存在計算系統800上之媒體內容可包含任何類型之音訊、視訊及/或影像資料，包含剖析快取替代行為之複雜或詳細結果。計算系統800包含一或多個資料輸入806，可經由資料輸入806接收任何類型之資料、媒體內容及/或輸入，諸如人類話語、使用者可選擇輸入(顯式或隱式)、訊息、音樂、電視媒體內容、所記錄之視訊內容及字任何內容及/或資料源接收之任何其他類型之音訊、視訊及/或影像資料。計算系統800亦包含通信介面808，其可實施為一串列及/或平行介面、一無線介面、任何類型之網路介面、一数据機之任一或多者及實施為任何其他類型之通信介面。通信介面808在計算系統800與其他電子裝置、計算裝置及通信裝置藉此與計算系統800傳達資料之一通信網路之間提供一連接及/或通信鏈路。計算系統800包含一或多個處理器810 (例如微處理器、控制器及其類似者之任何者)，處理器810處理各種電腦可執行指令以控制計算系統800之操作且實現剖析快取替代之技術或其中剖析快取替代可體現之技術。替代地或另外，可使用硬體、韌體或連同通常在812處識別之處理及控制電路一起實施之固定邏輯電路之任一者或任何組合來實施計算系統800。儘管圖中未展示，但計算系統800可包含將各種組件耦合於裝置內之一系統匯流排或資料傳送系統。一系統匯流排可包含不同匯流排結構(諸如一記憶體匯流排或記憶體控制器、一周邊匯流排、一通用串列匯流排及/或利用多種匯流排架構之任何者之一處理器或區域匯流排)之任一者或任何組合。計算系統800亦包含電腦可讀媒體814，諸如除實現持續及/或非暫時資料儲存(即相比於單純信號傳輸而言)之剖析記憶體104之外之一或多個記憶體裝置，記憶體裝置之實例包含隨機存取記憶體(RAM)、非揮發性記憶體(例如一唯讀記憶體(ROM)、快閃記憶體、EPROM、EEPROM等等之任一或多者)及一磁碟儲存裝置。一磁碟儲存裝置可實施為任何類型之磁性儲存裝置或光學儲存裝置，諸如一硬磁碟驅動機、一可錄式及/或可覆寫光碟(CD)、任何類型之一多樣化數位光碟(DVD)及其類似者。計算系統800亦可包含一大量儲存媒體裝置816。在此實例中，電腦可讀裝媒體814亦包含一剖析記憶體104。電腦可讀媒體814提供用於儲存裝置資料804之資料儲存機構以及各種裝置應用程式818及與計算系統800之操作態樣有關之任何其他類型之資訊及/或資料。例如，一操作系統820可維持為具有電腦可讀媒體814且在處理器810上執行之一電腦應用。裝置應用818可包含一裝置管理器，諸如任何形式之一控制應用、軟體應用、信號處理及控制模組、源於一特定裝置之程式碼、一特地裝置之一硬體抽象層等等。裝置應用818亦包含用於實施技術之任何系統組件、引擎或管理器。結論儘管已使用特定於特徵及/或方法之語言描述使用剖析快取替代之技術及啟用剖析快取替代之設備之實施例，但應瞭解隨附申請專利範圍之主旨不必要受限於所描述之具體特徵或方法。確切而言，具體特徵及方法揭示為此等技術之實例性實施方案。

100‧‧‧環境102‧‧‧記憶體剖析(MP)計算裝置102-1‧‧‧智慧型電話102-2‧‧‧計算手錶102-3‧‧‧數位相機102-4‧‧‧膝上型電腦102-5‧‧‧平板電腦102-6‧‧‧桌上型電腦104‧‧‧剖析記憶體106‧‧‧快取記憶體108‧‧‧主記憶體110‧‧‧映射器112‧‧‧剖析工具114‧‧‧移動器200‧‧‧圖202‧‧‧第一軸204‧‧‧第二軸206‧‧‧分界線208‧‧‧條210‧‧‧條212‧‧‧條214‧‧‧條216‧‧‧條218‧‧‧條300‧‧‧圖402‧‧‧顯示器404‧‧‧收發器406‧‧‧處理器408‧‧‧電腦可讀儲存媒體(CRM)410‧‧‧快取頁面412‧‧‧主記憶體(MM)載入頁面414‧‧‧記憶體存取資訊416‧‧‧輸入位址映射500‧‧‧方法502‧‧‧步驟504‧‧‧步驟506‧‧‧步驟600‧‧‧方法602‧‧‧步驟604‧‧‧步驟606‧‧‧步驟700‧‧‧方法702‧‧‧步驟704‧‧‧步驟706‧‧‧步驟708‧‧‧步驟710‧‧‧步驟712‧‧‧步驟714‧‧‧步驟800‧‧‧計算系統802‧‧‧通信裝置804‧‧‧裝置資料806‧‧‧資料輸入808‧‧‧通信介面810‧‧‧處理器812‧‧‧處理及控制電路814‧‧‧電腦可讀媒體816‧‧‧大量儲存媒體裝置818‧‧‧裝置應用820‧‧‧操作系統

參考以下圖式描述剖析快取替代之技術及裝置之實施例。圖式中之相同數字用以指稱相同特徵及組件：圖1繪示其中可實施技術之一實例性環境。圖2繪示展示一第一時間處之主記憶體及快取記憶體之實例性頁面計數器值的一圖。圖3繪示展示第一時間之後的一第二時間處之主記憶體及快取記憶體之實例性頁面計數器值的一圖。圖4繪示圖1之一實例性記憶體剖析計算裝置。圖5繪示依據一剖析演算法之替代快取記憶體中之頁面之一方法。圖6繪示使用減少空間計數器計數剖析快取替代之頁面存取之一方法。圖7繪示使用每記憶體頁面一個以下計數器計數剖析快取替代之頁面存取之一方法。圖8繪示體現或其中可實施能夠使用剖析快取替代之技術之一實例性計算系統。

500‧‧‧方法

502‧‧‧步驟

504‧‧‧步驟

506‧‧‧步驟

Claims

一種用於管理一主記憶體與一快取記憶體之間的資料遷移之方法，該方法包括：使計數器維持與維持在該主記憶體及該快取記憶體中之資料之頁面相關聯，該等計數器指示用於存取該等頁面之請求之數目，維持在該主記憶體及該快取記憶體中之該資料之該等頁面被分成數個頁面集合，各頁面集合包含來自該快取記憶體之複數個頁面及來自該主記憶體之複數個頁面；基於該維持而動態地擴展可藉由該等計數器表示之值的範圍；及且在一預定時間間隔下：依據該等計數器而判定在一給定集合中該主記憶體中之一頻繁(frequently)請求頁面之頁面存取請求之一數目是否大於在該給定集合中該快取記憶體中之一不常(infrequently)請求頁面之頁面存取請求之一數目，該判定係在該預定時間間隔下於比所有該等頁面集合少之頁面上執行；及回應於在該給定集合中該主記憶體中之該頻繁請求頁面之頁面存取請求之數目大於在該給定集合中該快取記憶體之該不常請求頁面之頁面存取請求之數目之一判定，在該給定集合內交換該主記憶體之該頻繁請求頁面與該快取記憶體之該不常請求頁面。
如請求項1之方法，其中該快取記憶體之該不常請求頁面對應於該快取記憶體之一最少請求頁面，且該主記憶體之該頻繁請求頁面對應於該主記憶體之一最多請求頁面。
如請求項1之方法，其中在服務由記憶體使用者執行之請求之一背景中執行該判定及該交換以存取維持在該主記憶體及該快取記憶體中該資料之該等頁面。
如請求項1之方法，其進一步包括：接收用於存取維持在該主記憶體中該資料之該等頁面之至少一者之一請求；及在未先將維持在該主記憶體中該資料之該等頁面之該至少一者填充至該快取記憶體之情況下，服務維持在該主記憶體中該資料之該等頁面之該至少一者之該請求。
如請求項1之方法，其中在不同集合中維持在該主記憶體中該資料之該等頁面未與維持在該快取記憶體中該資料之該等頁面交換。
如請求項1之方法，其中該預定時間間隔包含對應於1微秒(1μs)之一預定時間間隔。
如請求項1之方法，其中該動態地擴展包括使用一浮點表示法或一公制(common scale)之至少一者來實施該等計數器。
一種系統，其包括：主記憶體及快取記憶體，其等經組態以維持資料之頁面，該快取記憶體經組態以維持比該主記憶體少之頁面，且具有比該主記憶體低之延遲、比該主記憶體高之頻寬或比該主記憶體低之電力使用之至少一者，維持在該主記憶體及該快取記憶體中之該資料之該等頁面被分成數個頁面集合，各頁面集合包含來自該快取記憶體之複數個頁面及來自該主記憶體之複數個頁面；一剖析工具，其經組態以：使計數器維持與維持在該主記憶體及該快取記憶體中之該等頁面相關聯，該等計數器經組態以指示用於存取該等頁面之請求之數目；及基於該維持而動態地擴展可藉由該等計數器表示之值的範圍；及一移動器，其經組態以：在一預定時間間隔下就根據該計數器判斷在一給定集合中該主記憶體之一頻繁請求頁面之頁面存取請求之一數目是否大於在該給定集合中該快取記憶體之一不常請求頁面之頁面存取請求之一數目，其包含經組態以在該預定時間間隔下比所有該等頁面集合少之頁面上檢查；且回應於在該給定集合中該主記憶體中之該頻繁請求頁面之頁面存取請求之該數目大於在該給定集合中該快取記憶體中之該不常請求頁面之頁面存取請求之該數目之一判定，在該給定集合內交換該主記憶體中之該頻繁請求頁面與該快取記憶體中之該不常請求頁面。
如請求項8之系統，其中該剖析工具經進一步組態以維持該主記憶體中之該等頁面之各者之一各自計數器。
如請求項8之系統，其中該剖析工具經進一步組態以維持在該主記憶體中之每頁資料維持一個以下計數器。
如請求項8之系統，其中該預定時間間隔包含1微秒(1μs)。
如請求項8之系統，其進一步包括一映射器，該映射器經組態以將與一記憶體存取請求相關聯之一輸入位址映射至對服務該記憶體存取請求有效之該主記憶體或該快取記憶體中之一對應頁面。
如請求項8之系統，其中該剖析工具經組態以藉由使用一浮點表示法或一公制之至少一者來實施該等計數器而動態地擴展該等值的範圍。
一或多個電腦可讀儲存媒體，其包括：主記憶體及快取記憶體，其等經組態以維持資料之頁面，該快取記憶體經組態以維持比該主記憶體少之頁面，且具有比該主記憶體低之延遲、比該主記憶體高之頻寬或比該主記憶體低之電力使用之至少一者；以及指令，藉由包含以下之操作而回應於一或多個處理器之執行，以依據一剖析快取替代技術而填充頁面至該快取：使計數器維持與該主記憶體及該快取記憶體之該等頁面相關聯以指示用於存取該等頁面之請求之數目；基於該維持而動態地擴展可藉由該等計數器表示之值的範圍；在一預定時間間隔下依據該等計數器而就該主記憶體之一頻繁請求頁面之頁面存取請求之一數目是否大於該快取記憶體之一不常請求頁面之頁面存取請求之一數目進行一判定；回應於該主記憶體之該頻繁請求頁面之頁面存取請求之該數目大於該快取記憶體之該不常請求頁面之頁面存取請求之該數目之一判定，交換該主記憶體之該頻繁請求頁面與該快取記憶體之該不常請求頁面。
如請求項14之一或多個電腦可讀儲存媒體，其中該快取記憶體具有至少128兆位元組(MB)之一大小。
如請求項14之一或多個電腦可讀儲存媒體，其中該主記憶體具有至少4吉位元組(GB)之一大小。
如請求項14之一或多個電腦可讀儲存媒體，其中該動態擴展包含使用一浮點表示法或一公制之至少一者以實施該等計數器。
如請求項14之一或多個電腦可讀儲存媒體，其中該維持計數器包含實施計數器的數量少於該資料之該等頁面的每頁面皆配置一個計數器。
如請求項18之一或多個電腦可讀儲存媒體，其中該維持計數器包含使用一標籤以識別與該等計數器之各計數器相關聯之一頁面。
如請求項14之一或多個電腦可讀儲存媒體，其中該等操作進一步包括回應於該交換而更新該等計數器。