TWI722438B - 用於進行中操作的指令排序的裝置及方法 - Google Patents

Abstract

記憶體指令的執行使用記憶體管理電路被管理，該記憶體管理電路包括第一快取記憶體和第二快取記憶體，第一快取記憶體在頁表中存儲多個映射，第二快取記憶體基於虛擬位址存儲條目。記憶體管理電路執行來自一個或者多個模組的操作，包括：響應於使得至少第一虛擬位址無效的第一操作，當第一操作由記憶體管理電路接收時，選擇性地對在進行中的多個進行中操作中的每個進行中操作排序，其中在特定進行中操作的排序中的位置取決於以下兩者之一或者兩者：(1)一個或者多個模組中的哪個模組發起特定進行中操作，或者(2)特定進行中操作是否向第一快取記憶體或者第二快取記憶體提供結果。

Description

用於進行中操作的指令排序的裝置及方法

本發明涉及用於進行中操作的指令排序。

許多計算系統利用虛擬記憶體系統以允許程式師訪問記憶體位址，而無需考慮記憶體位址駐留在計算系統的物理記憶體層次結構的何處。為了這樣做，虛擬記憶體系統維護由程式師使用的虛擬記憶體位址至物理記憶體位址的映射，該物理記憶體位址存儲由虛擬記憶體位址引用的實際資料。物理記憶體位址可以駐留在任何類型的存放裝置中(例如，SRAM、DRAM、磁片等)。

當程式訪問虛擬記憶體位址時，虛擬記憶體系統執行位址轉換以確定哪個物理記憶體位址由虛擬記憶體位址引用。在所確定的物理記憶體位址處存儲的資料從物理記憶體位址中被讀取，作為記憶體頁面內的偏移，並且由程式返回以供使用。虛擬到物理位址映射在“頁表”中被存儲。在一些情況下，虛擬記憶體位址可以位於大的虛擬位址空間中的頁面，該大的虛擬位址空間中的頁面轉換為當前未駐留在主記憶體中的物理記憶體的頁面(即，缺頁)，使得頁面然後被複製到主記憶體中。

現代計算系統包括其為用於頁面的快取記憶體的一個或者多個轉換後備緩衝器(TLB)，該一個或者多個轉換後備緩衝器由虛擬記憶體系統用來提高虛擬記憶體位址到物理記憶體位址轉換的速度。非常一般 地，TLB包括來自頁表的多個條目，每個條目包括從虛擬位址到物理位址的映射。每個TLB條目可以直接地快取記憶體頁表條目或者以產生從虛擬位址到物理位址轉換的這種方式組合頁表中的幾個條目。一般來說，TLB的條目僅覆蓋可用於計算系統的全部記憶體的一部分。在一些示例中，TLB的條目被維護，以使得由TLB覆蓋的全部可用記憶體的一部分包括全部可用記憶體的最近被訪問的、最常被訪問的或者最可能被訪問的部分。一般來說，每當虛擬記憶體位址改變虛擬記憶體位址與物理記憶體位址之間的映射時，TLB的條目需要被管理。該管理可以影響來自引用虛擬記憶體位址的指令的進行中的任何操作。在一些系統中，在由那些指令引用的虛擬記憶體位址被無效之前，具有進行中操作的任何指令被允許完成。

在一個方面，一般來說，一種裝置，包括：一個或者多個模組，該一個或者多個模組被配置為執行記憶體指令，該記憶體指令基於虛擬位址來訪問在物理記憶體中存儲的資料，該虛擬位址基於頁表中的映射被轉換為物理位址；以及記憶體管理電路，該記憶體管理電路被耦合到一個或者多個模組，該記憶體管理電路包括第一快取記憶體和第二快取記憶體，第一快取記憶體在頁表中存儲多個映射，第二快取記憶體基於虛擬位址存儲條目。記憶體管理電路被配置為執行來自一個或者多個模組的操作，執行包括：響應於使得至少第一虛擬位址無效的第一操作，當第一操作由記憶體管理電路接收時，選擇性對在進行中的多個進行中操作中的每個進行中操作排序，其中特定進行中操作在排序中的位置取決於以下兩者之一或者兩者：(1)一個或者多個模組中的哪個模組發起了特定進行中操作，或者(2)特定進行中操作是否向第一快取記憶體或者第二快取記憶體提供了結果。

方面可以包括以下特徵中的一個或者多個特徵。

第一操作被保證在有限數量的時鐘週期內開始執行。

特定進行中操作在排序中的位置被選擇為以下兩者之一：(1)在第一操作之前，或者(2)在第一操作之後。

排序對應於在其中操作的集合表現為已經被原子地執行而沒有排序中的相鄰的操作的重疊的排序。

特定進行中操作在排序中的位置取決於：一個或者多個模組中的哪個模組提供了特定進行中操作。

一個或者多個模組中的第一模組包括被配置為中央處理單元的核，以及一個或者多個模組中的第二模組被配置用於不需要核的直接記憶體訪問。

如果特定進行中操作由第二模組發起，則特定進行中操作在排序中的位置是在第一操作之前。

將特定進行中操作的位置選擇為在第一操作之前包括：允許特定進行中操作與第一操作併發地繼續執行，並且防止來自在第一操作由記憶體管理電路接收之後生成的特定進行中操作的任何結果被用來修改第一快取記憶體或者第二快取記憶體。

特定進行中操作在排序中的位置取決於：在特定進行中操作由第一模組發起時，特定進行中操作是否向第一快取記憶體或者第二快取記憶體提供了結果。

如果特定進行中操作沒有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之前，以及如果特定進行中操作有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之後。

特定進行中操作在排序中的位置取決於：進行中操作是否向第一快取記憶體或者第二快取記憶體提供了結果。

如果特定進行中操作沒有向第一快取記憶體或者第二快取 記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之前，以及如果特定進行中操作有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之後。

將特定進行中操作的位置選擇為在第一操作之前包括：允許特定進行中操作與第一操作併發地繼續執行。

將特定進行中操作的位置選擇為在第一操作之後包括：中止特定進行中操作並且在完成第一操作的執行之後，重新啟動特定進行中操作。

第一快取記憶體包括轉換後備緩衝器，該轉換後備緩衝器存儲由頁表中的少於全部的映射組成的子集。

第二快取記憶體包括資料快取記憶體，該資料快取記憶體存儲在物理記憶體中存儲的資料的副本。

第二快取記憶體包括頁表遍歷器快取記憶體，該頁表遍歷器快取記憶體存儲由頁表遍歷器提供的有限數量的中間結果，該頁表遍歷器遍歷具有多個級別的分層頁表的級別，其中每個級別存儲用於確定映射的中間結果。

第一操作包括使得包括第一虛擬位址的一定範圍的虛擬位址無效的操作。

在另一個方面，一般來說，一種方法，包括：使用一個或者多個模組執行記憶體指令，記憶體指令基於虛擬位址來訪問在物理記憶體中存儲的資料，虛擬位址基於頁表中的映射被轉換為物理位址；以及使用記憶體管理電路來管理記憶體指令的執行，記憶體管理電路被耦合到一個或者多個模組，記憶體管理電路包括第一快取記憶體和第二快取記憶體，第一快取記憶體在頁表中存儲多個映射，第二快取記憶體基於虛擬位址存儲條目。記憶體管理電路執行來自一個或者多個模組的操作，執行包括：響應於使得至少第一虛擬位址無效的第一操作，當第一操作由記憶體管理電路接收時，選擇性地對在進行中的多個進行中操作中的每個進行中操作排序，其 中特定進行中操作在排序中的位置取決於以下兩者之一或者兩者：(1)一個或者多個模組中的哪個模組發起了特定進行中操作，或者(2)特定進行中操作是否向第一快取記憶體或者第二快取記憶體提供了結果。

方面可以包括以下特徵中的一個或者多個特徵。

第一操作被保證在有限數量的時鐘週期內開始執行。

特定進行中操作在排序中的位置被選擇為以下兩者之一：(1)在第一操作之前，或者(2)在第一操作之後。

排序對應於在其中操作的集合表現為已經被原子地執行而沒有排序中的相鄰的操作的重疊的排序。

特定進行中操作的排序中的位置取決於：一個或者多個模組中的哪個模組提供了特定進行中操作。

一個或者多個模組中的第一模組包括被操作為中央處理單元的內，以及一個或者多個模組中的第二模組執行直接記憶體訪問而不需要核。

如果特定進行中操作由第二模組發起，則特定進行中操作在排序中的位置是在第一操作之前。

將特定進行中操作的位置選擇為在第一操作之前包括：允許特定進行中操作與第一操作併發地繼續執行，並且防止來自在第一操作由記憶體管理電路接收之後生成的特定進行中操作的任何結果被用來修改第一快取記憶體或者第二快取記憶體。

特定進行中操作在排序中的位置取決於：在特定進行中操作由第一模組發起時，特定進行中操作是否向第一快取記憶體或者第二快取記憶體提供了結果。

如果特定進行中操作沒有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之前，以及如果特定進行中操作有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之後。

特定進行中操作的排序中的位置取決於：進行中操作是否向第一快取記憶體或者第二快取記憶體提供了結果。

如果特定進行中操作沒有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之前，以及如果特定進行中操作有向第一快取記憶體或者第二快取記憶體提供結果，則特定進行中操作的位置被選擇為在第一操作之後。

將特定進行中操作的位置選擇為在第一操作之前包括：允許特定進行中操作與第一操作併發地繼續執行。

將特定進行中操作的位置選擇為在第一操作之後包括：中止特定進行中操作並且在完成第一操作的執行之後，重新啟動特定進行中操作。

第一快取記憶體包括轉換後備緩衝器，該轉換後備緩衝器存儲由頁表中的少於全部的映射組成的子集。

第二快取記憶體包括資料快取記憶體，該資料快取記憶體存儲在物理記憶體中存儲的資料的副本。

第二快取記憶體包括頁表遍歷器快取記憶體，該頁表遍歷器快取記憶體存儲由頁表遍歷器提供的有限數量的中間結果，該頁表遍歷器遍歷具有多個級別的分層頁表的級別，每個級別存儲用於確定映射的中間結果。

第一操作包括使得包括第一虛擬位址的一定範圍的虛擬位址無效的操作。

方面可以具有以下優點中的一個或者多個優點。

本文所描述的技術使得用於處理某些無效指令的有保證的確定性延遲。這種有保證的確定性延遲可以對於避免對用於限制未完成的無效指令的數量的反壓技術的需要是有用的。這樣的反壓技術可能增加系統的複雜性，以便於避免或者檢測鎖死情況。相反，有保證的確定性延遲是強加用於高效率地保證無效指令的轉發進度的有用的要求。

從下面的描述以及從權利要求書中，本發明的其他特徵和優點將變得顯而易見。

102:處理單元

104:L2快取記憶體

106:主記憶體

108:二級存儲

110:I/O設備

112:處理匯流排

114:記憶體匯流排

116:I/O匯流排

118:橋

202:處理單元

220:處理器核心

222:L1資料快取記憶體

224:L1指令快取記憶體

226:MMU

227:頁表遍歷器

228:匯流排界面

230:TLB

232:遍歷器快取記憶體

300:DMA模組

302:DMA模組

326:SMMU

327:遍歷器快取記憶體

328:匯流排界面

330:TLB

332:頁表遍歷器

第一圖是計算系統。

第二圖是被耦合至處理器匯流排的處理單元。

第三圖是直接記憶體訪問模組。

參考第一圖，，計算系統100包括多個處理單元102、二級(L2)快取記憶體104(例如，SRAM)、主記憶體106(例如，DRAM)、二級存放裝置(例如，磁片)108以及一個或者多個輸入/輸出(I/O)設備110(例如，鍵盤或者滑鼠)。處理單元102和L2快取記憶體104被連接到處理器匯流排112，主記憶體106被連接到記憶體匯流排114，以及I/O設備110和二級存放裝置108被連接到I/O匯流排116。處理器匯流排112、記憶體匯流排114以及I/O匯流排116經由橋118彼此連接。計算系統100還包括直接記憶體訪問(DMA)模組300，該直接記憶體訪問(DMA)模組300能夠通過記憶體匯流排114訪問主記憶體106，而不要求這些訪問要由處理單元102來處理。

一般來說，處理單元102執行一條或者多條電腦程式的指令，包括從被包括在計算系統100中的記憶體中讀取處理器指令和資料。如本領域所公知的，基於記憶體或者存放裝置的相對延遲，計算系統100中的各種記憶體或者存放裝置被組織成記憶體層次結構。這樣的記憶體層次結構的一個示例在頂部處具有處理器寄存器(未示出)，接著是1級(L1)快取記憶體(未示出)，接著是L2快取記憶體104，接著是主記憶體106， 以及最後接著是二級存放裝置108。當給定的處理單元102試圖訪問記憶體位址時，記憶體層次結構中的每個記憶體或者存放裝置以從記憶體層次結構的頂部向下的順序被檢查，以確定記憶體位址的資料是否被存儲在存放裝置或者記憶體設備中。

例如，對於訪問用於僅在二級存放裝置108中被存儲的資料的記憶體位址的處理單元102的第一處理單元，處理單元首先確定記憶體位址和資料是否被存儲在它的L1快取記憶體中。由於記憶體位址和資料沒有被存儲在它的L1快取記憶體中，快取記憶體未命中發生，使得處理器經由處理器匯流排112與L2快取記憶體140進行通信，以確定記憶體位址和資料是否被存儲在L2快取記憶體140中。由於記憶體位址和資料沒有被存儲在L2快取記憶體中，另一個快取記憶體未命中發生，使得處理器經由處理器匯流排112、橋118以及記憶體匯流排114與主記憶體106進行通信，以確定記憶體位址和資料是否被存儲在主記憶體106中。由於記憶體位址和資料沒有被存儲在主記憶體106中，另一個未命中發生(也被稱為“缺頁”)，使得處理器經由處理器匯流排114、橋118以及I/O匯流排116與二級存放裝置108進行通信，以確定記憶體位址和資料是否被存儲在二級存放裝置108中。由於記憶體位址和資料被存儲在二級存放裝置108中，資料從二級存放裝置108中被檢索並且經由I/O匯流排116、橋118以及處理器匯流排112被返回到處理單元。記憶體位址和資料可以被緩存在記憶體層級結構中的任何數量的記憶體或者存放裝置中，使得記憶體位址和資料在將來可以更容易地被訪問。

參考第二圖，第一圖的處理單元102的處理單元202的一個示例被連接到處理器匯流排112。處理單元202包括處理器核心220、L1資料快取記憶體222、L1指令快取記憶體224、記憶體管理單元(MMU)226以及匯流排界面228。處理器核心220(也被簡單稱為“核”)是與其他處理器核心一起協調形成多核處理器的單個處理器(也被稱為中央處理器(CPU))。MMU226包括頁表遍歷器227、轉換後備緩衝器(TLB)230、 以及遍歷器快取記憶體232，下面將對其中的每一個進行更詳細地描述。

非常一般地，處理器核心220執行在一些情況下要求訪問計算系統100的記憶體層次結構中的記憶體位址的指令。由第二圖的處理單元202執行的指令使用虛擬記憶體位址。記憶體層次結構的各種其他配置也是可能的。例如，TLB230可以位於每個處理單元的外面，或者可以有由多個核心共用的一個或者多個共用的TLB。

當處理器核心220要求訪問與資料關聯的虛擬記憶體位址時，處理器核心220向L1資料快取記憶體222發送針對虛擬記憶體位址的記憶體訪問請求。L1資料快取記憶體222存儲有限數量的最近或者經常被使用的資料值，這些資料值由它們的虛擬記憶體位址標記。如果L1資料快取記憶體222具有用於虛擬記憶體位址的條目(即，快取記憶體命中)，則與虛擬記憶體位址關聯的資料被返回到處理器核心220，而不需要記憶體層次結構中的任何進一步的記憶體訪問操作。備選地，在一些實現方式中，L1資料快取記憶體222通過條目的物理記憶體位址來標記條目，該L1資料快取記憶體222甚至要求針對快取記憶體命中的位址轉換。

如果L1資料快取記憶體222不具有用於虛擬記憶體位址的條目(即，快取記憶體未命中)，則記憶體訪問請求被發送到MMU 226。一般來說，MMU 226使用TLB 230來將虛擬記憶體位址轉換到對應的物理記憶體位址，並且經由匯流排界面228將針對物理記憶體位址的記憶體訪問請求發送出處理器202，並發送至記憶體層次結構的其他單元。頁表遍歷器227通過訪問在一個或多個級別的記憶體中被存儲(潛在地分層地)的整個頁表，處理沒有被存儲在TLB230中的映射的檢索。頁表遍歷器227可以為如在這個示例中所示出的硬體單元，或者在其他示例中，頁表遍歷器可以被實現在軟體中，而不需要MMU中的專用電路。頁表存儲虛擬記憶體位址與物理記憶體位址之間的整套映射，頁表遍歷器227訪問該整套映射以將虛擬記憶體位址轉換成對應的物理記憶體位址。

為了加快將虛擬記憶體位址轉換成物理記憶體位址的過程， TLB 230包括虛擬記憶體位址與物理記憶體位址之間的多個最近或者經常被使用的映射。如果TLB 230具有針對虛擬記憶體位址的映射，則針對與虛擬記憶體位址關聯的物理記憶體位址(如從在TLB 230中存儲的映射中所確定的)的記憶體訪問請求經由匯流排界面228從處理器202中被發出。

如果TLB230不具有針對虛擬記憶體位址的映射(即，TLB未命中)，頁表遍歷器227遍歷(或者“走查”)頁表的(多個)級別，以確定與虛擬記憶體位址關聯的物理記憶體位址，以及針對物理記憶體位址(如從在頁表中存儲的映射中所確定的)的記憶體請求經由匯流排界面228從處理器202中被發出。由頁表遍歷器227返回的中間結果被緩存在遍歷器快取記憶體232中以加快隨後的頁表遍歷。

在一些示例中，TLB 230和頁表被並行地訪問，以確保在TLB未命中發生時沒有造成附加的時間損失。

由於L1資料快取記憶體222和TLB 230僅可以存儲有限數量的條目，需要快取記憶體管理演算法以確保在L1資料快取記憶體222和TLB 230中所記憶體的條目是有可能被多次重複使用的那些。這樣的演算法基於準則、諸如最近最少使用準則逐出並且替換在L1資料快取記憶體222和TLB 230中所存儲的條目。

在一些示例中，計算系統的虛擬記憶體系統可以改變其虛擬記憶體位址與物理記憶體位址之間的映射。在這種情況下，(例如，通過作業系統或者通過硬體實體)向計算系統中的使用虛擬位址來標記條目的TLB或者其他實體(即，TLB 230和遍歷器快取記憶體232)發出用於虛擬記憶體位址的轉換後備緩衝器無效指令(TLBI)。一般來說，TLBI指令包括虛擬記憶體位址並且使得與虛擬記憶體位址關聯的任何TLB(或者遍歷器快取記憶體)條目的無效。也就是說，當TLB接收用於給定虛擬記憶體位址的TLBI時，存儲給定虛擬記憶體位址與物理記憶體位址之間的映射的TLB中的任何條目都被無效。

第三圖示出被連接到記憶體匯流排114的DMA模組300的 示例。DMA模組300包括DMA控制器302、系統MMU(SMMU)326以及匯流排界面328。SMMU 326包括TLB 330、多個頁表遍歷器332的集合以及遍歷器快取記憶體232。DMA控制器302使得計算系統100內除了處理單元102之外的多個不同實體能夠通過SMMU 326訪問主記憶體106。例如，這樣的訪問可以由I/O設備110發起。如果TLB 330中的轉換缺失，通過包括多個頁表遍歷器332(例如16個頁表遍歷器)，用於不同的請求實體的多個頁表遍歷操作可以並行地被執行。與那些頁表遍歷器332關聯的是存儲來自遍歷的中間結果的遍歷器快取記憶體327。如果TLBI指令在處理單元202中被發出，不僅本地TLB 230和遍歷器快取記憶體232需要被清除任何無效條目，而且其他處理單元102的TLB和遍歷器快取記憶體以及DMA模組300的TLB和遍歷器快取記憶體也需要被清除任何無效條目。DMA模組300而不是處理單元102可以回應於TLBI指令來執行不同的程式，但是二者可以執行需要確保TLBI指令適當處理的某些步驟。

在一些實施例中，MMU 226和SMMU 326包括TLBI處理器，該TLBI處理器被配置為保證用於處理TLBI指令的確定性延遲。例如，TLBI處理器立即或者在預先確定的最大數量的週期內啟動TLBI指令的執行。對於處理單元202，這可以包含將TLBI指令足夠快地插入到處理器核心220的流水線，以考慮可能需要通過流水線來傳播的週期P的最大數量(例如，9個週期)。如果TLBI指令不得不滿足在接收TLBI指令的TLBI處理器與TLBI指令完成執行之間的L個週期的最大延遲，TLBI處理器必須在L-P個週期內啟動執行。例如，TLBI指令的執行可能需要足夠的週期來從TLB中移除用於一定範圍的虛擬位址的條目。

TLBI處理器還需要確保由通過流水線執行的一系列指令執行的操作的排序對應於在其中那些動作表現為已經被原子地執行而沒有排序中的鄰近的操作的重疊的排序。關於已經被編譯成正在被執行的指令的軟體，維護原子的指令執行的這種表現對於保證正確性是有用的。這意味著當TLBI處理器將TLBI指令插入到流水線時，當TLBI指令被接收時，在 TLBI指令被接收但還沒有被提交之前發出的指令的任何進行中操作需要表現為完全地在TLBI指令之前它們被原子地執行，或者完全地在TLBI指令之後它們被原子地執行。TLBI處理器使用用於確保指令執行中的這種原子性的各種技術。

該技術中的一種技術是中止進行中操作並且在TLBI指令完成之後重新開機它。然而，由於可能存在與操作關聯的副作用，使得不可能中止操作而沒有將系統留在不一致的狀態中，這並不總是可能的。在一些情況下，即使不存在副作用，重新啟動可能是代價高的。例如，諸如I/O載入操作的操作可能花費相當大數量的週期來完成(例如，大約10,000個週期)。如果TLBI指令在相當大的一部分時間已經過去之後到達，則這將花費相當大數量的週期來中止並且重新啟動該操作。只要這些指令不使用正在被TLBI無效的虛擬位址來產生被存儲回到快取記憶體中的任何快取記憶體中的結果，允許它們與TLBI指令的執行併發地繼續是安全的。

如上面所描述的，對於充當TLBI處理器的MMU 226和SMMU 326二者，TLBI指令在預先確定的數量的週期內起作用。然而，進行中操作可以被不同地處理，這取決於是MMU226處理在處理單元202內發起的進行中操作，還是SMMU326處理在DMA模組300內發起的進行中操作。用於使用處理單元的MMU 226作為TLBI處理器來處理進行中操作的技術將首先被描述，接著是用於使用SMMU 326作為TLBI處理器來處理進行中操作的技術。

在MMU 226中處理具有進行中操作的指令(“進行中指令”)的一個方面包含確定指令的類型。一般來說，MMU 226將指令分類成在TLBI指令已經完成執行之後可以被中止並且然後被重新開機的指令，以及可以與TLBI指令的執行併發地繼續執行的指令。這種分類是基於指令是否能夠潛在地提供結果而做出的，該結果被存儲在由虛擬位址標記的快取記憶體(例如，TLB或者遍歷器快取記憶體)中，該虛擬位址正在被TLBI指令無效。下面是該分類可以如何被執行的示例。

如果指令沒有引用虛擬記憶體位址，則該指令將不會被TLBI影響，使得指令被允許與TLBI併發地繼續進行。在這種情況下，在操作的原子排序中，進行中指令在TLBI指令之前出現，即使進行中指令直到TLBI指令已經完成執行之後才完成執行。再次，因為進行中指令不被任何無效影響，該無效由TLBI指令產生，所以這種排序從軟體的觀點來看是正確的。

如果指令有引用參考虛擬記憶體位址，則MMU 226進一步地確定它是什麼類型的指令。由MMU 22轉換的一些虛擬位址被映射到為了與除了記憶體訪問操作之外的操作有關的指令而保留的一部分位址空間。例如，載入操作可以引用被映射到不是記憶體內的物理位址的值的虛擬位址，但是相反將載入操作標識為從I/O設備接收資料的I/O載入操作。在對於該虛擬位址的轉換被執行之前，可能不能確定載入操作是資料載入還是I/O載入。因此，在L1資料快取記憶體222中可以存在查找，該查找在該虛擬位址上與TLB 230中的查找並行地被執行。如果操作是記憶體載入，資料快取記憶體查找可以導致命中，該命中避免了針對由將被使用的轉換提供的映射的物理位址的需要。但是，如果操作是I/O載入，資料快取記憶體查找將導致未命中(用於在其中I/O載入沒有被快取記憶體的實現方式)。

如果在TLB 230中存在未命中並且在轉換過程期間TLBI指令到達，可能不是很明顯的是何種類型的進行中指令(例如，記憶體載入或者I/O載入)正在被執行。但是，在任何情況下，進行中指令可以被安全地中止並且從流水線中被刷出以及然後被重新啟動。這是因為將不存在將使得計算的狀態中的任何不一致性作為所中止的指令的結果的副作用。例如，記憶體載入指令不具有任何副作用，以及I/O載入的副作用直到其轉換完成並且確定指令是I/O載入之後才啟動。在這樣的情況下，在操作的原子性排序中，進行中指令(在被重新開機之後)在TLBI指令之後出現。

如果在TLB 230中存在命中，或者如果存在未命中並且TLBI指令在轉換過程之後到達，則MMU 226能夠將進行中指令分類為應 該繼續進行的指令，因為該指令不被TLBI指令(例如，I/O載入)影響，或者應該在TLBI指令之後被中止並且被重新開機的指令，因為該指令可能被TLBI指令(例如，記憶體載入)影響。

在SMMU 326中處理進行中操作不需要不同操作類型的分類。一般來說，當TLBI指令到達SMMU 326時將成為進行中的操作是頁表遍歷操作(或者簡單地“遍歷操作”)。由於可能存在許多頁表遍歷器332，可能存在許多這樣的進行中遍歷操作，並且每個遍歷操作可能花費許多週期(例如，1000個週期)。每個頁表遍歷器332被配置為檢測在進行中遍歷操作期間TLBI指令何時到達SMMU 326。遍歷操作被允許與TLBI指令的處理並行地繼續，但是在TLBI指令的所檢測的到達時間之後，由遍歷操作返回的任何中間結果被阻止添加到遍歷器快取記憶體327中，並且在TLBI指令的所檢測的到達時間之後，在遍歷操作的結尾處返回的任何最終結果被阻止添加到TLB 330中。

備選地，在一些實現方式中，頁表遍歷器332可以被配置為在TLBI指令的檢測之後輸入過濾模式。在過濾模式中，頁表遍歷器332將與結果關聯的虛擬位址與正在被TLBI指令無效的虛擬位址(或者虛擬位址的範圍)進行比較。如果存在匹配，則結果被阻塞。如果不存在匹配，結果被允許以被寫入到TLB 330或者遍歷器快取記憶體327中。當然，由於如果必要那些結果將被移除作為執行TLBI操作的一部分，在所檢測的到達時間之前，由進行中遍歷操作寫入到TLB 330或者遍歷器快取記憶體327中的結果不會造成問題。

因此，對於在SMMU 326中執行的任何進行中遍歷操作，在操作的原子性排序中，進行中遍歷操作在TLBI操作之前出現，即使進行中遍歷操作直到TLBI操作已經完成之後才完成執行。

其他實施例也在所附的發明申請專利範圍內。

114:記憶體匯流排

300:DMA模組

302:DMA控制器

326:SMMU

327:遍歷器快取記憶體

328:匯流排界面

330:TLB

332:頁表遍歷器

Claims (36)

1. 一種用於進行中操作的指令排序的裝置，包括：一個或者多個模組，所述一個或者多個模組被配置為執行記憶體指令，所述記憶體指令基於虛擬位址來訪問在物理記憶體中存儲的資料，所述虛擬位址基於頁表中的映射被轉換為物理位址；以及記憶體管理電路，所述記憶體管理電路被耦合到所述一個或者多個模組，所述記憶體管理電路包括第一快取記憶體和第二快取記憶體，所述第一快取記憶體在所述頁表中存儲多個所述映射，所述第二快取記憶體基於虛擬位址存儲條目；其中所述記憶體管理電路被配置為執行來自所述一個或者多個模組的操作，所述執行包括：當一第一操作由所述記憶體管理電路接收時，選擇性地對在一處理器流水線中進行中的多個進行中操作中的每個進行中操作排序，其中所述選擇性排序是關於在所述處理器流水線中完成執行，並被執行以回應該第一操作，其中該第一操作無效至少一第一虛擬位址，作為插入一指令至該流水線中的一結果，及其中一特定進行中操作在所述選擇性排序中的一位置取決於所述特定進行中操作是否向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供了結果。
2. 如請求項1所述的用於進行中操作的指令排序的裝置，其中所述第一操作被保證具有確定性延遲。
3. 如請求項1所述的用於進行中操作的指令排序的裝置，其中一特定進行中操作在所述選擇性排序中的一位置被選擇為以下兩者之一：(1)在所述第一操作之前，或者(2)在所述第一操作之後。
4. 如請求項3所述的用於進行中操作的指令排序的裝置，其中由該記憶體管理電路執行的一組操作包括於該第一操作的執行與該特定進行中操作的執行之重疊，但該組操作的執行的結果，關於其在由該記憶體管理電路執行的操作上的其他作用，係被原子地提供，而沒有該第一操作的結果的任何作用與該特定進行中操作的任何作用之重疊。
5. 如請求項1所述的用於進行中操作的指令排序的裝置，其中該第一操作無效至少該第一虛擬位址，作為於一預先確定的最大數量的週期內在該第一操作被接收後插入該指令至該流水線的一結果，其中該預先確定的最大數量的週期是至少部分基於(1)一保證的最大延遲及(2)讓該插入指令經由該流水線傳播所需的一最大週期數量所決定。
6. 如請求項3所述的用於進行中操作的指令排序的裝置，其中所述一個或者多個模組中的第一模組包括被配置為中央處理單元的核，以及所述一個或者多個模組中的第二模組被配置用於不需要所述核的直接記憶體訪問。
7. 如請求項6所述的用於進行中操作的指令排序的裝置，其中如果特定進行中操作由所述第二模組發起，則所述特定進行中操作在所述選擇性排序中的一位置是在所述第一操作之前。
8. 如請求項7所述的用於進行中操作的指令排序的裝置，其中將所述特定進行中操作的所述位置選擇為在所述第一操作之前包括：允 許所述特定進行中操作與所述第一操作併發地繼續執行，並且防止來自在所述第一操作由所述記憶體管理電路接收之後生成的所述特定進行中操作的任何結果被用來修改所述第一快取記憶體或者所述第二快取記憶體。
9. 如請求項7所述的用於進行中操作的指令排序的裝置，其中該特定進行中操作由所述第一模組發起。
10. 如請求項9所述的用於進行中操作的指令排序的裝置，其中如果所述特定進行中操作沒有向所述第一快取記憶體提供結果且沒有向所述第二快取記憶體提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之前，以及如果所述特定進行中操作有向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之後。
11. 如請求項3所述的用於進行中操作的指令排序的裝置，其中該特定進行中操作在所述選擇性排序中的位置取決於：所述進行中操作是否向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供了結果。
12. 如請求項11所述的用於進行中操作的指令排序的裝置，其中如果所述特定進行中操作沒有向所述第一快取記憶體提供結果且沒有向所述第二快取記憶體提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之前，以及如果所述特定進行中操作有向所述第一快取記憶體或者所述第二快取記憶體提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之後。
13. 如請求項12所述的用於進行中操作的指令排序的裝置，其中將所述特定進行中操作的所述位置選擇為在所述第一操作之前包括：允許所述特定進行中操作與所述第一操作併發地繼續執行。
14. 如請求項12所述的用於進行中操作的指令排序的裝置，其中將所述特定進行中操作的所述位置選擇為在所述第一操作之後包括：中止所述特定進行中操作並且在完成所述第一操作的執行之後重新啟動所述特定進行中操作。
15. 如請求項1所述的用於進行中操作的指令排序的裝置，其中所述第一快取記憶體包括轉換後備緩衝器，所述轉換後備緩衝器存儲由所述頁表中的少於全部的所述映射組成的子集。
16. 如請求項1所述的用於進行中操作的指令排序的裝置，其中所述第二快取記憶體包括資料快取記憶體，所述資料快取記憶體存儲在所述物理記憶體中存儲的資料的副本。
17. 如請求項1所述的用於進行中操作的指令排序的裝置，其中所述第二快取記憶體包括頁表遍歷器快取記憶體，所述頁表遍歷器快取記憶體存儲由頁表遍歷器提供的有限數量的中間結果，所述頁表遍歷器遍歷具有多個級別的分層頁表的級別，每個級別存儲用於確定所述映射的中間結果。
18. 如請求項1所述的用於進行中操作的指令排序的裝置，其中所述第一操作包括使得包括所述第一虛擬位址的一定範圍的虛擬位址無效的操作。
19. 一種用於進行中操作的指令排序的方法，包括： 使用一個或者多個模組執行記憶體指令，所述記憶體指令基於虛擬位址來訪問在物理記憶體中存儲的資料，所述虛擬位址基於頁表中的映射被轉換為物理位址；以及使用記憶體管理電路來管理所述記憶體指令的執行，所述記憶體管理電路被耦合到所述一個或者多個模組，所述記憶體管理電路包括第一快取記憶體和第二快取記憶體，所述第一快取記憶體在所述頁表中存儲多個所述映射，所述第二快取記憶體基於虛擬位址存儲條目；其中所述記憶體管理電路執行來自所述一個或者多個模組的操作，所述執行包括：當所述第一操作由所述記憶體管理電路接收時，選擇性地對在一處理器流水線中進行中的多個進行中操作中的每個進行中操作排序，其中所述選擇性排序是關於在所述處理器流水線中完成執行，並被執行以回應該第一操作，其中該第一操作無效至少一第一虛擬位址，作為插入一指令至該流水線中的一結果，及其中一特定進行中操作在所述選擇性排序中的一位置取決於所述特定進行中操作是否向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供了結果。
20. 如請求項19所述的用於進行中操作的指令排序的方法，其中所述第一操作被保證具有確定性延遲。
21. 如請求項19所述的用於進行中操作的指令排序的方法，其中該特定進行中操作在所述選擇性排序中的一位置被選擇為以下兩者之一：(1)在所述第一操作之前，或者(2)在所述第一操作之後。
22. 如請求項21所述的用於進行中操作的指令排序的方法，其中由該記憶體管理電路執行的一組操作包括於該第一操作的執行與該特定進行中操作的執行之重疊，但該組操作的執行的結果，關於其在由該記 憶體管理電路執行的操作上的其他作用，係被原子地提供，而沒有該第一操作的結果的任何作用與該特定進行中操作的任何作用之重疊。
23. 如請求項19所述的用於進行中操作的指令排序的方法，其中該第一操作無效至少該第一虛擬位址，作為於一預先確定的最大數量的週期內在該第一操作被接收後插入該指令至該流水線的一結果，其中該預先確定的最大數量的週期是至少部分基於(1)一保證的最大延遲及(2)讓該插入指令經由該流水線傳播所需的一最大週期數量所決定。
24. 如請求項21所述的用於進行中操作的指令排序的方法，其中所述一個或者多個模組中的第一模組包括操作為中央處理單元的核，以及所述一個或者多個模組中的第二模組執行直接記憶體訪問而不需要所述核。
25. 如請求項24所述的用於進行中操作的指令排序的方法，其中如果特定進行中操作由所述第二模組發起，則該特定進行中操作在所述選擇性排序中的位置是在所述第一操作之前。
26. 如請求項25所述的用於進行中操作的指令排序的方法，其中將所述特定進行中操作的所述位置選擇為在所述第一操作之前包括：允許所述特定進行中操作與所述第一操作併發地繼續執行，並且防止來自在所述第一操作由所述記憶體管理電路接收之後生成的所述特定進行中操作的任何結果被用來修改所述第一快取記憶體或者所述第二快取記憶體。
27. 如請求項25所述的用於進行中操作的指令排序的方法，其中該特定進行中操作由所述第一模組發起。
28. 如請求項27所述的用於進行中操作的指令排序的方法，其中如果所述特定進行中操作沒有向所述第一快取記憶體提供結果且沒有向所述第二快取記憶體提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之前，以及如果所述特定進行中操作有向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之後。
29. 如請求項21所述的用於進行中操作的指令排序的方法，其中該特定進行中操作的所述選擇性排序中的位置取決於：所述進行中操作是否向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供了結果。
30. 如請求項29所述的用於進行中操作的指令排序的方法，其中如果所述特定進行中操作沒有向所述第一快取記憶體提供結果且沒有向所述第二快取記憶體提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之前，以及如果所述特定進行中操作有向所述第一快取記憶體或者所述第二快取記憶體的至少一者提供結果，則所述特定進行中操作的所述位置被選擇為在所述第一操作之後。
31. 如請求項30所述的用於進行中操作的指令排序的方法，其中將所述特定進行中操作的所述位置選擇為在所述第一操作之前包括：允許所述特定進行中操作與所述第一操作併發地繼續執行。
32. 如請求項30所述的用於進行中操作的指令排序的方法，其中將所述特定進行中操作的所述位置選擇為在所述第一操作之後包括： 中止所述特定進行中操作並且在完成所述第一操作的執行之後重新啟動所述特定進行中操作。
33. 如請求項19所述的用於進行中操作的指令排序的方法，其中所述第一快取記憶體包括轉換後備緩衝器，所述轉換後備緩衝器存儲由所述頁表中的少於全部的所述映射組成的子集。
34. 如請求項19所述的用於進行中操作的指令排序的方法，其中所述第二快取記憶體包括資料快取記憶體，所述資料快取記憶體存儲在所述物理記憶體中存儲的資料的副本。
35. 如請求項19所述的用於進行中操作的指令排序的方法，其中所述第二快取記憶體包括頁表遍歷器快取記憶體，所述頁表遍歷器快取記憶體存儲由頁表遍歷器提供的有限數量的中間結果，所述頁表遍歷器遍歷具有多個級別的分層頁表的級別，每個級別存儲用於確定所述映射的中間結果。
36. 如請求項19所述的用於進行中操作的指令排序的方法，其中所述第一操作包括使得包括所述第一虛擬位址的一定範圍的虛擬位址無效的操作。

Images