CN101833517A - 快取存储器系统及其存取方法 - Google Patents

Abstract

一种快取存储器系统及其存取方法，该快取存储器系统包括第一阵列，配置其每一储存元件以储存一快取列；对应于第一阵列的第二阵列，其每一储存元件被配置用以储存该第一阵列的对应储存元件中的该快取列的第一部分状态；及对应于第一阵列的第三阵列，其每一储存元件被配置用以储存该第一阵列的对应储存元件中的该快取列的第二部分状态。第二部分状态表示该快取列是否已被修改。当修改该快取列时，仅将第二部分状态写入第三阵列的对应储存元件中，但第一部分状态并未写入第二阵列的对应储存元件中。同时读取第一部分状态与第二部分状态，用以决定完整状态。本发明减少了微处理器内标签阵列的存取量，简化了标签阵列的平面规划。

Description

快取存储器系统及其存取方法

技术领域

本发明有关于微处理器内的快取存储器，特别是有关于其快取列的一致性状态结构。

背景技术

现今的微处理器包含快取存储器(cache memory)，用来减少存储器存取指令的延迟。快取存储器通常包括数据阵列以及标签阵列(tag array)；数据阵列为用以储存实际快取列(cacheline)数据的数据阵列，而标签阵列，用以储存与数据阵列内的快取列相关的地址标签。标签阵列所储存的每一项目(entry)也一并记录着快取列的状态。此外，快取列状态用来指示数据阵列内的对应快取列是否有效，以及该快取列自被分配后是否已被修改过。

另外，现今的微处理器，特别是超纯量(superscalar)处理器，包括多个功能单元可对快取存储器进行存取，例如不同的载入单元与储存单元。快取存储器的数据阵列与标签阵列通常具有多重端口，使得每一功能单元可以同时存取数据阵列与标签阵列，以将效能最佳化。然而，具有多重端口的阵列将大幅地增加面积与功率消耗。再者，在从事微处理器的平面规划(floor-planning)时，因为阵列面积通常已相对较大，若更大时将会更难以将其纳入。

针对这一问题的解决方式，即是复制标签阵列，使得每一功能单元拥有自己的标签阵列，进而使得标签阵列变成单一端口。虽然此解决方式需要集合微处理器上更多的空间，但因为每一标签阵列面积较小，便减轻了平面规划的负担，且由于每一标签阵列可进行单独的电源管理，从而额外地有利于电源管理。然而，使用此一解决方式的问题在于，当快取列的标签及/或状态需要更新时，必须存取所有标签阵列，用以更新每一个标签阵列所相应的快取列的标签及/或状态。这将消耗许多标签阵列的存取频宽，且进行更新时，所有标签阵列需要消耗功率。

因此，需要一种快取存储器结构，用以解决上述的问题。

发明内容

本发明提供一种快取存储器系统。该快取存储器系统包括由储存元件组成的一第一阵列，其每一储存元件系被配置用以储存一快取列。该快取存储器系统也包括由储存元件组成的一第二阵列，该第二阵列对应于由储存元件组成的该第一阵列，且该第二阵列的每一储存元件被配置用以储存一第一部分状态，该第一部分状态对应于该第一阵列的对应储存元件中的该快取列。该快取存储器系统也包括由储存元件组成的一第三阵列，该第三阵列对应于由储存元件组的该第一阵列，且该第三阵列的每一储存元件被配置用以储存一第二部分状态，该第二部分状态对应于该第一阵列的对应储存元件中的该快取列。该第二部分状态表示该快取列是否已被修改。当该快取存储器系统修改该第一阵列的一储存元件的该快取列时，该快取存储器系统仅将该第二部分状态写入至该第三阵列的对应储存元件中，以表示该快取列已被修改，但并没有将该第一部分状态写入至该第二阵列的对应储存元件中。该快取存储器系统自该第二阵列与第三阵列的对应储存元件分别读取该快取列的该第一部分状态与该第二部分状态，以决定该快取列的完整状态。

本发明提供一种快取存储器系统的存取方法。该方法包括将一快取列储存至由储存元件组成的一第一阵列的一储存元件中。该方法也包括于将该第一阵列的对应储存元件中的该快取列的一第一部分状态储存至由储存元件组成的一第二阵列的一储存元件中，由储存元件组成的该第二阵列对应于由储存元件组成的该第一阵列。该方法也包括将该第一阵列的对应储存元件中的该快取列的一第二部分状态储存至由储存元件组成的一第三阵列的一储存元件中，由储存元件组成的该第三阵列对应于由储存元件组成的该第一阵列，其中，该第二部分状态表示该快取列是否已被修改。该方法也包括，响应于该第一阵列的一储存元件的该快取列的修改，仅将该第二部分状态写入至该第三阵列的对应储存元件中，以表示该快取列已被修改，但并没有将该第一部分状态写入至该第二阵列的对应储存元件中。该方法也包括通过自该第二阵列与第三阵列的对应储存元件分别读取该快取列的该第一部分状态与第二部分状态，以决定该快取列的完整状态。

本发明提供一种计算机程序产品，用于一计算机装置，该计算机程序产品包括一计算机可使用的储存媒体，具有内建于该媒体的计算机可读取程序码，用以指定一快取存储器系统。该计算机可读取程序码包括第一程序码，用以指定由储存元件组成的一第一阵列，其每一储存元件被配置用以储存一快取列。该计算机可读取程序码也包括第二程序码，用以指定由储存元件组成的一第二阵列，对应于由储存元件组成的该第一阵列，其每一储存元件被配置用以储存该第一阵列的对应储存元件中，该快取列的一第一部分状态。该计算机可读取程序码也包括第三程序码，用以指定由储存元件组成的一第三阵列，对应于由储存元件组的该第一阵列，其每一储存元件被配置用以储存该第一阵列的对应储存元件中，该快取列的一第二部分状态。该第二部分状态表示该快取列是否已被修改。当该快取存储器系统修改该第一阵列的一储存元件的该快取列时，该快取存储器系统仅将该第二部分状态写入至该第三阵列的对应储存元件中，以表示该快取列已被修改，但并没有将该第一部分状态写入至该第二阵列的对应储存元件中。该快取存储器系统自该第二阵列与第三阵列的对应储存元件分别读取该快取列的该第一部分状态与该第二部分状态，以决定该快取列的完整状态。

本发明的优点在于快取列的修改需要对应地更新其状态，修改位阵列的存在减轻了存取标签阵列来更新快取列状态的需求，从而减少标签阵列的存取量。除此之外，于其他具有多重标签阵列的实施例中，修改位阵列的存在简化了微处理器内标签阵列的平面规划，使其具有较佳电源管理，且没有上述额外频宽消耗的问题。

附图说明

图1显示依据本发明的微处理器方块图。

图2显示依据本发明图1微处理器的执行单元与存储器子系统部分方块图。

图3a显示依据本发明图1的数据快取所使用的表格示意图，通过部分MESI快取列状态与一修改位，用以计算出完整MESI快取列状态。

图3b显示依据本发明另一实施例，说明图1的数据快取所使用的表格示意图，通过部分MESI快取列状态与一修改位，用以计算出完整MESI快取列状态。

图4显示依据本发明图1的微处理器的操作流程图，其中，微处理器具有图2实施例的执行单元与存储器子系统，用以执行一储存指令。

图5显示依据本发明图1的微处理器的操作流程图，其中，微处理器具有图2实施例的执行单元与存储器子系统，用以执行一无效窥探请求。

图6显示依据本发明另一实施例，说明于图1的微处理器中，执行单元与存储器子系统的部分方块图。

图7显示依据本发明图1的微处理器的操作流程图，其中，微处理器具有图6实施例的执行单元与存储器子系统，用以执行一储存指令。

图8显示依据本发明图1的微处理器的操作流程图，其中，微处理器具有图6实施例的执行单元与存储器子系统，用以执行一收回请求。

图9显示依据本发明另一实施例，说明于图1的微处理器中，执行单元与存储器子系统的部分方块图。

图10显示依据本发明图1的微处理器的操作流程图，其中，微处理器具有图9实施例的执行单元与存储器子系统，用以执行一储存指令。

图11显示依据本发明图1的微处理器的操作流程图，其中，微处理器具有图9实施例的执行单元与存储器子系统，用以执行一无效窥探请求。

图12显示依据本发明另一实施例，说明于图1的微处理器中，执行单元与存储器子系统的部分方块图。

图13显示依据本发明另一实施例，说明于图1的微处理器100中，执行单元与存储器子系统112的部分方块图。

具体实施方式

为使本发明的上述目的、特征和优点能更明显易懂，下文特举实施例，并配合所附图式，详细说明如下。

参考图1，显示依据本发明的微处理器100方块图。微处理器100包括指令快取(instruction cache)102，用以储存程序指令。这些程序指令是微处理器100自系统存储器(未图示)所取得且由微处理器100执行。举例而言，程序指令包括用以存取存储器的指令，像是x86 MOV、PUSH或POP指令，或者将导致微处理器100存取存储器的指令，像是若收到转译查询缓冲器不命中(translation lookaside buffer，TLB，missing)信号时执行页面表格查找(page table walk)。

微处理器100也包括指令转译器(instruction translator)104，用以由指令快取102接收指令，且将指令(也被称为宏指令)转译为一或多个微指令或微操作(micro-operations)。微操作是指微处理器100的执行单元与存储器子系统112实际执行的简化指令。特别地，微指令可包括载入微指令与储存微指令，或者包括载入指令与储存指令。载入指令，用以将存储器某位置的内容载入至微处理器100的结构化暂存器(architecturalregister)116中。储存指令，用以将微处理器100的结构化暂存器116的内容储存至存储器某位置。于其他的实施例中，载入指令与储存指令为微处理器100的原生指令集的一部分。

微处理器100也包括暂存器别名表(register alias table，RAT)106，用以接收来自指令转译器104的指令。暂存器别名表106依照程序顺序接收来自指令转译器104的转译指令，以及决定微处理器100内的其他未退出指令的每一指令的相依性。暂存器别名表106储存与微处理器100内的每一未退出指令相关的暂存器重命名信息。暂存器重命名信息包括程序顺序，则重排序缓冲器(reorder buffer，ROB)116借此依照程序顺序退出指令。在指令尚未分配至指令排序器108之前，暂存器别名表106为每一指令在重排序缓冲器116配置一笔项目。当指令来源运算自根据暂存器别名表106所产生的相依性信息判断为可使用时且当执行单元与存储器子系统112为可使用时，指令排序器108由暂存器别名表106接收指令，并将指令发送至执行单元与存储器子系统112。于一实施例中，微处理器100为一乱序执行微处理器(out-of-order execution microprocessor)。重排序缓冲器116耦接于暂存器别名表106、指令排序器108以及执行单元与存储器子系统112。

执行单元与存储器子系统112包括：数据快取128、载入单元122、储存单元124、储存队列(queue)126、二阶(level-2，L2)快取132与总线接口单元(bus interface unit，BIU)134，载入单元122、储存单元124、储存队列126、二阶快取132与总线接口单元134均耦接于数据快取128。于此，载入单元122、储存单元124与储存队列126，可被称为功能单元。载入单元122执行载入指令，以由数据快取128载入数据至结构化暂存器116。储存单元124与储存队列126执行储存指令，用以将结构化暂存器116的数据储存于数据快取128。总线接口单元134，作为微处理器100与微处理器100总线的接口，使得微处理器100传输数据至存储器与外围设备。进一步，总线接口单元134窥探(snoop)微处理器100总线，并且对应地执行针对数据快取128的窥探操作。除此之外，快取列将由数据快取128收回至二阶快取。于一实施例中，由于数据快取128的各种阵列(图2中的212、214、216及218)需要多个时脉周期来进行存取，因此，载入单元122、储存单元124及储存队列126均为多重阶层的管线结构。下文将详细说明数据快取128的结构，以及数据快取128与载入单元122、储存单元124、储存队列126、二阶快取132及总线接口单元134间的互动。

于一实施例中，微处理器100的宏结构为IA-32宏结构(也称为x86结构)。如果一个处理器能够正确地由执行大多数被设计用来于IA-32微处理器上执行的应用程序，则该微处理器被视为具有IA-32宏结构。而一个应用程序正确地被执行是指能得到该应用程序所预期的结果。然而，其他实施例中，微处理器的宏结构可有别于x86宏结构，不过仍包括数据快取128及修改位阵列216(于图2中)，用以实现其优点。

参考图2，显示依据本发明图1微处理器100的执行单元与存储器子系统112部分方块图。如图2所示，显示图1的执行单元与存储器子系统112的载入单元122、储存单元124与储存队列126。图1所示的数据快取128包含图2中的元件：载入标签阵列212、储存标签阵列214、修改位阵列216与数据阵列218。于图2的实施例中，载入标签阵列212包括耦接于载入单元122的单一读取/写入端口，而载入标签阵列212不包含另一读取/写入端口连接至储存单元124，供储存单元124更新载入标签阵列212中的项目；数据阵列218包括耦接于载入单元122的单一读取/写入端口；储存标签阵列214包括耦接于储存单元124的单一读取/写入端口，而储存标签阵列214不包含另一读取/写入端口连接至载入单元122，以供载入单元122更新储存标签阵列214中的项目；以及修改位阵列216包括耦接于载入单元122的写入端口及耦接于储存单元124的读取端口。于一实施例中，修改位阵列216为直接写入(write-through)阵列，也就是说，于一既定时脉周期中，当储存单元124读取修改位阵列216的位置与载入单元122写入修改位阵列216的位置相同时，则修改位阵列216将该位置新写入数值提供至储存单元124。于其他实施例中，数据快取128包括冲突检测与回复逻辑，用以检测上述的冲突，并且于下一时脉周期中，提供新写入数值。由于载入单元122与数据阵列218间具有单一读取/写入端口，储存队列126将执行一快取写入请求226，并提供至图2实施例的载入单元122。

载入标签阵列212、储存标签阵列214及修改位阵列216的结构方式与数据阵列218相同，且载入标签阵列212、储存标签阵列214及数据阵列218由多个储存元件所组成。举例来讲，于一实施例中，数据阵列218、载入标签阵列212、储存标签阵列214与修改位阵列216，各自为四集合关联存储器阵列(4-way setassociative cache memory array)，通过载入(load)、储存(store)、窥探(snoop)与收回(eviction)地址的索引部分(较低地址位)，用以编成索引，其中，该地址用以选择数据阵列218的一集合或一列，且每一集合具有四项目。于数据阵列218的某一被选中的集合的每一项目将储存一快取列。于载入标签阵列212与储存标签阵列214的该被选中的集合的每一项目将储存对应至数据阵列218的该快取列的一地址标签与快取列状态。于修改位阵列216的该被选中的集合的每一项目将储存一已修改位，用以指示数据阵列218的对应快取列是否被已修改。在另一实施例中，数据阵列218、载入标签阵列212、储存标签阵列214与修改位阵列216，各自为M集合关联存储器阵列(M-way setassociative cache memory array)，M是自然数，例如M＝2，即数据阵列218、载入标签阵列212、储存标签阵列214与修改位阵列216，各自为二集合关联存储器阵列，而每个阵列可包含N个集合。于一实施例中，根据现有的MESI快取一致性协议(coherencyprotocol)，快取状态为四种可能状态其中之一，该四种可能状态为：已修改(Modified)状态、独占(Exclusive)状态、共用(Shared)状态或无效(Invalid)状态。然而，其他实施例中，修改位阵列216用以储存已修改位，表示对应的快取列已修改，而且已修改位可用以计算其他快取一致性协议结构中的快取列完整状态。于一实施例中，当数据快取128分配一快取列至数据阵列218时，也同时将该快取列的完整MESI状态写入至载入标签阵列212以及储存标签阵列214，并清除修改位阵列216的对应已修改位。于另一实施例中，当数据快取128使快取列无效时，清除修改位阵列216的对应已修改位。

于图2的实施例中，除了快取写入请求226外，载入单元122也处理载入请求222与收回请求242。因为这些操作必须存取数据阵列218，而且载入单元122为耦接至数据阵列218的单一读取/写入端口的唯一单元。于图2的实施例中，储存单元124处理储存请求228与窥探请求224，各自配合图4与图5详细说明如下。

于图2的实施例中，数据快取128持续更新载入标签阵列212，用以反映数据阵列218的对应快取列的完整状态。然而，数据快取128并不会为了反映数据阵列218的对应快取列的完整状态而持续更新储存标签阵列214。具体地，当储存队列126执行一快取写入请求226来更新一快取列时，储存标签阵列214并未被更新为快取列的新MESI状态。相反地，载入单元122设定修改位阵列216的对应已修改位。因此，储存标签阵列214仅储存快取列的部分MESI状态，而修改位阵列216储存的已修改位，用来表示快取列已被修改。接着，当储存单元124需要知道快取列的完整的MESI状态时，储存单元124一起读取修改位阵列216的快取列的已修改位234与储存标签阵列214的快取列的部分MESI状态232，且储存单元124的组合逻辑208将使用图3a的表1或图3b的表2的任一示意图来计算快取列的完整MESI状态236(也提供给储存队列126)，其中，图3a与图3b将详细说明如下。

参考图3a，显示依据本发明图1的数据快取128所使用的表1示意图，通过部分MESI快取列状态与一已修改位，用以计算出完整MESI快取列状态。

表1包括三个栏位。第一栏位指定数据阵列218的对应快取列的部分MESI快取列状态，例如自图2的储存标签阵列214所读取的部分MESI状态232。第二栏位指定数据阵列218的对应快取列的已修改位，例如自修改位阵列216所读取的已修改位234。第三栏位指定数据阵列218的对应快取列的完整MESI状态，例如图2的组合逻辑208所产生的完整MESI状态236。

于第一行中，表1显示若部分MESI状态为已修改状态时，则不管已修改位的数值为何，所计算的完整MESI状态也为已修改状态。于第二行中，表1显示若部分MESI状态为独占状态且已修改位被设定时，所计算的完整MESI状态为已修改状态。于第三行中，表1显示若部分MESI状态为独占状态且已修改位被重置(reset)时，所计算的完整MESI状态为独占状态。于第四行中，表1显示若部分MESI状态为共用状态且已修改位被设定时，计算的完整MESI状态为已修改状态。此状况指示快取列正处于被升级至独占状态的过程中，且会发生早期储存合并。图3a的实施例具有此状况的优势，且将快取列升级至已修改状态。于第五行中，表1显示若部分MESI状态为共用状态且已修改位被重置时，所计算的完整MESI状态为共用状态。于第六行中，表1显示若部分MESI状态为无效状态，则不管已修改位的数值为何，所计算的完整MESI状态为无效状态。从以上的实施例中，可以理解部分MESI状态无法正确指出所对应的快取列是否已被修改，必须加上该快取列所对应的已修改位，计算得到完整MESI状态才能正确判断该快取列的状态是否为已修改状态。换句话说，该快取列的已修改位可以被视为另一个部分MESI状态，而该快取列的完整MESI状态可通过两个部分MESI状态加以计算得到。

参考图3b显示依据本发明另一实施例，说明图1的数据快取128所使用的表2示意图，通过部分MESI快取列状态与一已修改位，用以计算出完整MESI快取列状态。表2类似于图3a的表1。然而，于表2中，若部分MESI状态为共用状态，则不管已修改位的数值为何，所计算的完整MESI状态为共用状态。

参考图4，显示依据本发明图1的微处理器100的操作流程图，其中，微处理器100具有图2实施例的执行单元与存储器子系统112，用以执行一储存指令。流程始于步骤模块402。

于步骤模块402中，储存单元124接收储存请求228。接收储存请求228后，储存单元124针对与储存地址相关的快取列，执行储存询问操作。流程前进至步骤模块404。

于步骤模块404中，针对与储存指令的储存地址相关的快取列，储存询问操作从储存标签阵列214读取部分MESI状态232，并从图2的修改位阵列216读取已修改位234。流程前进至步骤模块406。

于步骤模块406中，根据图3a的表1或图3b的表2，储存单元124的组合逻辑208计算快取列的完整MESI状态236。流程前进至步骤模块408。

于步骤模块408中，储存单元124于储存队列126中分配一项目，并将由储存请求228所指定的储存数据及储存地址写入至分配项目。流程前进至步骤模块412。

于决定步骤模块412中，储存队列126判断步骤模块406所计算的完整MESI状态236是否为已修改状态或独占状态其中之一。若步骤模块406所计算的完整MESI状态236为已修改状态或独占状态其中之一，则流程前进至步骤模块416，否则，流程前进至步骤模块414。

于步骤模块414中，储存队列126命令总线接口单元134执行一总线写入无效操作，使得具有快取列备份的其他快取的快取列无效，并取得快取列的独占所有权。数据快取128响应地将载入标签阵列212与储存标签阵列214的MESI状态升级至独占状态。流程前进至步骤模块416。

于步骤模块416中，储存队列126执行一快取写入请求226，用以指定新MESI状态为已修改状态，并将该快取写入请求226提供至载入单元122。流程同时前进至步骤模块426与决定步骤模块418。

于步骤模块426中，载入单元122将与储存指令的储存地址相关的快取列的数据写入数据阵列128对应的项目。

另一方面，于决定步骤模块418中，载入单元122判断步骤模块406所计算的完整MESI状态236是否为已修改状态。若步骤模块406所计算的完整MESI状态236为已修改状态，则流程结束，否则，流程同时前进至步骤模块422与决定步骤模块424。

于步骤模块422中，针对与储存指令的储存地址相关的快取列，载入单元122将已修改状态写入至载入标签阵列212对应于该快取列的项目。流程结束于步骤模块422。

于步骤模块424中，针对与储存指令的储存地址相关的快取列，载入单元122设定修改位阵列216对应于该快取列的项目中的已修改位。尽管这时储存标签阵列214并未同时记录快取列的完整MESI状态(也就是说部分MESI状态232不是已修改状态)，这样的设计有助于之后储存单元124得以计算数据阵列218的对应快取列的完整MESI状态236。流程结束于步骤模块424。

由图4的流程图中可发现，当数据快取128执行快取写入请求226，用以修改数据阵列218的快取列时，数据快取128对具有已修改新状态的载入标签阵列212进行更新至最新的已修改状态(除非状态已经为已修改状态，如图4所示的相关步骤模块418、422与424)，并设定修改位阵列216的对应已修改位。这样设计的优点在于，数据快取128并没有对储存标签阵列214更新为已修改状态。不过，储存单元124可通过同时存取储存标签阵列214与修改位阵列216，如图4的相关步骤模块404(或者图5的步骤模块504)所示，用以计算快取列的全部完整MESI状态236，如图4的相关步骤模块406(或者图5的步骤模块506)所示。

参考图5，显示依据本发明图1的微处理器100的操作流程图，其中，微处理器100具有图2实施例的执行单元与存储器子系统112，用以执行一无效窥探请求。流程始于步骤模块502。

于步骤模块502中，储存单元124接收一无效窥探请求(invalidating snoop request)224，储存单元124针对与窥探地址相关的快取列，对自己执行一窥探询问操作。流程前进至步骤模块504。

于步骤模块504中，针对与窥探地址相关的快取列，窥探询问操作从储存标签阵列214读取部分MESI状态232，并从图2的修改位阵列216读取已修改位234。流程前进至步骤模块506。

于步骤模块506中，储存单元124的组合逻辑208根据图3a的表1或图3b的表2其中之一，用以计算快取列的完整MESI状态236。流程前进至决定步骤模块508。

于决定步骤模块508中，储存单元124判断步骤模块506所计算的完整MESI状态236是否为已修改状态。若是，流程前进至步骤模块512，否则，流程前进至步骤模块514。

于步骤模块512中，储存单元124命令总线接口单元134执行总线操作，用以将修改快取列写回至系统存储器。流程前进至步骤模块514。

于步骤模块514中，储存单元124对自己执行一状态更新操作，并对载入单元122执行一状态更新操作，每一更新用以指定新MESI状态为无效状态。流程同时前进至步骤模块516、518与522。

于步骤模块516中，针对与窥探地址相关的快取列，载入单元122将无效状态写入至载入标签阵列212对应该快取列的项目。流程结束于步骤模块516。

于步骤模块518中，针对与窥探地址相关的快取列，载入单元122清除修改位阵列216项目对应该快取列的已修改位。于一实施例中，当数据阵列218项目为无效时，数据快取128并不重置修改位阵列216的已修改位，而是等到对应快取列被分配至数据阵列218时重置该已修改位。流程结束于步骤模块518。

于步骤模块522中，针对与窥探地址相关的快取列，储存单元124将无效状态写入至储存标签阵列214对应该快取列的项目。流程结束于步骤模块522。

于图2的实施例中，由于储存单元124管线不像载入单元122管线繁忙，因此窥探询问操作由储存单元124管线来处理。然而，于另一实施例中，窥探询问操作由载入单元122而非储存单元124处理，因为载入标签阵列212也提供快取列的完整MESI状态。

于图2的实施例(以及图6、9及12的实施例)中，载入请求222与收回请求242由载入单元122处理，因为载入单元122可存取数据阵列218的单一读取端口。处理载入请求222仅需知道载入地址是否命中数据快取128，也就是说，是否有一快取线可表示载入地址存在于数据快取128中。(若载入地址的索引部分编成索引可指引至载入标签阵列212的一集合且载入地址的标签部分可与该集合中的其中一有效标签配对，则表示载入地址命中数据快取128。)然而，收回操作242(与窥探询问)需要知道快取列的完整MESI状态。收回操作242自图2实施例的载入标签阵列212中接收完整MESI状态。

进一步，最低限度上，储存操作仅需知道所指定快取列的状态是否至少为独占状态(也即，MESI状态为独占状态或已修改状态)，以便知道是否可立即写入快取列，或者，储存操作在进行步骤模块414时是否需要先取得快取列的独占所有权。然而，图4实施例包括对决定步骤模块418的进行最佳化设计，也就是当执行步骤模块418时，若所指定快取列的状态已经为已修改状态，且修改位阵列216的已修改位被设定时，则储存单元124放弃更新载入标签阵列212与修改位阵列216，进而达到消耗较少功率的优点。

一般而言，当需要知道快取列的完整ME SI状态时，才需要对修改位阵列216进行读取操作。因此，任一功能单元(载入单元122或者储存单元124)满足下列条件时，功能单元需对修改位阵列216进行读取，其条件是：(1)任一功能单元进行快取写入时并未更新其标签阵列212、214，以及(2)任一功能单元进行收回或窥探询问操作时(或者储存询问操作，具有图4及图7实施例所包含的最佳化)。

参考图6，显示依据本发明另一实施例，说明于图1的微处理器100中，执行单元与存储器子系统112的部分方块图。图6的实施例在许多方面类似于图2的实施例，且相同编号的元件为相似的。仅就不同处加以说明。

于图6的实施例中，修改位阵列216具有两个读取端口，其中之一用以将已修改位234提供至储存单元124，而另一端口则将已修改位634提供至载入单元122。除此之外，修改位阵列216的写入端口耦接于储存队列126，于执行快取写入请求226时，储存队列126借以更新修改位阵列216。

于图6的实施例中，载入单元122也包括组合逻辑608，用以从载入标签阵列212接收部分MESI状态632，并从修改位阵列216的第二读取端口接收修该已修改位634，并使用如图3a的表1或图3b的表2其中之一，用以计算完整MESI状态636。

于图6的实施例中，数据阵列218包括耦接于载入单元122的读取端口以及耦接于储存队列126的写入端口，用以致能储存队列126对数据阵列218执行快取写入请求226。也就是说，储存队列126直接对数据阵列218及修改位阵列216执行快取写入请求226，而非将其传送至图2的载入单元122。因此，载入标签阵列212与储存标签阵列214两者都不会因为处理快取写入请求226而被更新为已修改新状态。更确切地说，处理快取写入请求226仅设定修改位阵列216的对应已修改位。

参考图7，显示依据本发明图1的微处理器100的操作流程图，其中，微处理器100具有图6实施例的执行单元与存储器子系统112，用以执行一储存指令。图7的流程图与图4的流程图相似。然而，图7的步骤模块716取代图4的步骤模块416，其中，储存队列126执行直接针对数据阵列218的快取写入请求226，进而写入储存数据。除此之外，因为数据阵列218于步骤模块716中直接被写入，图7的流程图并不包括图4的步骤模块426。进一步，因为储存队列126并没有将新的修改快取列状态更新至储存标签阵列212(也没有更新至储存标签阵列214)，则于图7的流程图中，并无包括图4的步骤模块422。最后，假如于决定步骤模块418所判断完整MESI状态并非为已修改状态，则图7的步骤模块724取代图4的步骤模块424，使得储存队列126执行直接针对修改位阵列216的快取写入请求226，用以设定对应已修改位。

依据本发明图1实施例的微处理器100的操作，与图5所示的操作相似，其中，微处理器100具有图6实施例的执行单元与存储器子系统112，用以执行一无效窥探请求。

参考图8，显示依据本发明图1的微处理器100的操作流程图，其中，微处理器100具有图6实施例的执行单元与存储器子系统112，用以执行一收回请求242。流程开始于步骤模块802。

于步骤模块802中，载入单元122接收一收回请求242后，载入单元122针对与收回地址相关的快取列，执行一收回操作。流程前进至步骤模块804。

于步骤模块804中，针对与收回地址相关的快取列，收回操作从载入标签阵列212读取部分MESI状态632，并从图6的修改位阵列216读取已修改位634。流程前进至步骤模块806。

于步骤模块806中，载入单元122的组合逻辑208根据图3a的表1或第3b的表2，用以计算快取列的完整MESI状态636。流程前进至步骤模块808。

于步骤模块808中，载入单元122从数据阵列218读取收回地址所指定的快取列。流程前进至步骤模块812。

于步骤模块812中，载入单元122将步骤模块806所计算的完整MESI状态与步骤模块808所读取的快取列提供至图1的二阶快取132，用以执行收回操作。流程结束于步骤模块812。

参考图9，显示依据本发明另一实施例，说明于图1的微处理器100中，执行单元与存储器子系统112的部分方块图。图9的实施例在许多方面类似于图6的实施例，且相同编号的元件为相似的。仅就不同处加以说明。

于图9的实施例中，修改位阵列216包括单一读取端口，而非如图6的两个读取端口。因此，储存单元124并不包括组合逻辑208，而且不会产生完整MESI状态236。相反地，储存标签阵列214将部分MESI状态232直接提供至储存队列126。所以，图9的数据快取128所执行的储存请求228与先前实施例不同，其内容详述于下文图10相关的说明。最后，由载入单元122而非储存单元124接收窥探请求224。其结果是，图9的数据快取128所执行的窥探请求224也有不同，将于下文图11相关的说明。于图9的实施例中，修改位阵列216无需包括将已修改位提供至储存单元124的第二读取端口，这是因为窥探询问由载入单元122处理，且于图10中储存单元124并没有执行如图4与图7中储存单元124的最佳化的决定步骤模块418，也因此并不需要知道快取列的完整MESI状态，仅需知道MESI状态是否至少为独占状态(图10的步骤模块1012)，其可由储存标签阵列214的部分MESI状态232来加以判断。

参考图10，显示依据本发明图1的微处理器100的操作流程图，其中，微处理器100具有图9实施例的执行单元与存储器子系统112，用以执行一储存指令。图10的流程图与图7的流程图相似。然而，图10的步骤模块1004取代图7的步骤模块404，这仅仅将部分MESI状态232从储存标签阵列214被读取，而非如图7步骤模块404所示，需从修改位阵列216读取已修改位234。除此之外，图10并不存在步骤模块406，且流程直接由步骤模块1004前进至步骤模块408。更进一步，图10的决定步骤模块1012取代图7的步骤模块412，这使得储存队列126将判断在步骤模块1004所接收的部分MESI状态是否至少为独占状态(而非如图7的决定步骤模块412判断于其步骤模块406中所计算的完整MESI状态236是否为独占状态或已修改状态)。最后，由于储存队列126不需要存取快取列的完整MESI状态，因此，图10的流程图不包括图7的决定步骤模块418，不用进行图7的决定步骤模块418的最佳化；相反地，流程直接由步骤模块716前进至步骤模块724。

参考图11，显示依据本发明图1的微处理器100的操作流程图，其中，微处理器100具有图9实施例的执行单元与存储器子系统112，用以执行一无效窥探请求。流程开始于步骤模块1102。

于步骤模块1102中，载入单元122接收一无效窥探请求224。作为响应，针对与窥探地址相关的快取列，载入单元122对自己执行一窥探询问操作。流程前进至步骤模块1104。

于步骤模块1104中，针对与窥探地址相关的快取列，窥探询问操作从载入标签阵列212读取部分窥探请求632，并从图9的修改位阵列216读取已修改位634。流程前进至步骤模块1106。

于步骤模块1106中，载入单元122的组合逻辑608根据图3a的表1或图3b的表2其中之一，用以计算快取列的完整MESI状态636。流程前进至步骤模块1108。

于决定步骤模块1108中，载入单元112判断在步骤模块1106所计算的完整MESI状态636是否为已修改状态。若是，流程前进至步骤模块1112；否则，流程前进至步骤模块1114。

于步骤模块1112中，载入单元122命令总线接口单元134执行总线操作，将该快取列写回至系统存储器。流程前进至步骤模块1114。

于步骤模块1114中，载入单元122对自己执行一状态更新操作，以及对储存单元124执行一状态更新操作，其中，每一状态更新操作指定新MESI状态为无效状态。流程同时前进至步骤模块1116与步骤模块1122。

于步骤模块1116中，针对与窥探地址相关的快取列，载入单元122将无效状态写入至载入标签阵列212对应的项目。流程结束于步骤模块1116。

于步骤模块1122中，针对与窥探地址相关的快取列，储存单元124将无效状态写入储存标签阵列214对应的项目。流程结束于步骤模块1122。

值得注意的是，于图9的实施例中，当对应快取列被分配时，则重置修改位阵列216的已修改位，而非如图5的步骤模块518在收到窥探请求224就进行重置。

参考图12，显示依据本发明另一实施例，说明于图1的微处理器100中，执行单元与存储器子系统112的部分方块图。图12的实施例在许多方面类似于图9的实施例，且相同编号的元件为相似的。仅就不同处加以说明。

于图12的实施例中，储存队列126对储存单元124执行快取写入请求226(而非对图2的载入单元122，或者直接对图6与图9的数据阵列218与修改位阵列216)。数据阵列218的写入端口与修改位阵列216的写入端口均耦接于储存单元124，使得储存单元124(而非图9的数据队列126)将快取列写入至数据阵列218，并更新修改位阵列216的已修改位，用以响应于数据队列126的快取写入请求226。储存单元124将快取列的完整MESI状态更新至储存标签阵列214，使得储存单元124执行最佳化，其中，上述的最佳化，与图4与图7的决定步骤模块418中，载入单元122与储存队列126所分别执行的最佳化类似，而储存标签阵列214将完整MESI状态1232提供至储存队列126。

此外，由储存单元124而非载入单元122接收窥探请求224。因此，图12的储存单元124执行窥探请求224，此方式类似于图5相关的说明，除了储存单元124系直接由储存标签阵列214接收完整MESI状态1232(而非由图2的组合逻辑208)。然而，因为载入单元122也提供完整MESI状态636，于另一实施例中，载入单元122负责处理窥探请求224，流程如上述图11相关的说明。

最后，收回请求242由载入单元122处理，类似于上述图8的处理方式。

参考图13，显示依据本发明另一实施例，说明于图1的微处理器100中，执行单元与存储器子系统112的部分方块图。图13的实施例许多方面类似于图6的实施例，且相似数字的元件为相似的。仅将不同处说明如下。

图13的实施例包括单一的双端口标签阵列1314，也称为统一标签阵列1314，而非载入标签阵列212与储存标签阵列214。也就是说，统一标签阵列1314具有耦接于载入单元122的第一读取/写入端口，以及耦接于储存单元124的第二读取/写入端口。第一读取/写入端口将部分MESI状态1332提供至载入单元122的组合逻辑608，而第二读取/写入端口将部分MESI状态232提供至储存单元124的组合逻辑208。于图13的实施例中，当储存队列126执行快取写入请求226时，数据快取128并不将统一标签阵列1314以已修改新状态进行更新，此一优点在于，将减少统一标签阵列1314的拥塞状况。不过，通过同时存取统一标签阵列1314与修改位阵列216，储存单元124可计算快取列的完整MESI状态236，而载入单元122可计算快取列的完整MESI状态1332。

类似于上述图9的实施例，于图13的另一实施例中，载入单元122处理窥探请求224，且储存单元124不执行决定步骤模块418的最佳化，这使得储存单元124不用产生完整MESI状态236，而修改位阵列216可具有耦接于载入单元122的单一读取端口，而非两个读取端口。

于图13的实施例中，尽管并无享有独立载入标签阵列212与储存标签阵列214的实施例所带来的平面规划及电源管理的好处，图13的实施例仍可实现修改位阵列216的优势，意即，减少标签阵列的拥塞。进一步，图13的实施例有利于空间，其所具有的高效率双端口标签阵列设计，远小于两个单一端口标签阵列所消耗的总空间。

本发明虽以较佳实施例揭露如上，然其并非用以限定本发明的范围，本领域普通技术人员在不脱离本发明的精神和范围内，当可做些许的更动与润饰。举例来说，软件可以致能此处所述的装置及方法，如致能装置及方法的功能、制造、模型、模拟、性质及/或测试。例如，通过使用一般的程序语言(例如C或C++)、包括Verilog HDL、VHDL等硬件描述语言(hardwaredescription language，HDL)、或其它可使用的程序来完成。此类软件可被安装于任何已知计算机可用的介质中，例如半导体、磁盘或光盘(像是CD-ROM、DVD-ROM等)。此处所述装置及方法的实施例可被包含于一半导体知识产权核(semiconductorintellectual property core)中，如微处理器核(以HDL实现)，之后再以集成电路的制造转换成硬件。另外，此处所述的装置及方法可由硬件及软件来组合实现。故本发明不应局限于此处所述的具体实施例，而应以其所附的权利要求的保护范围为准。具体地，本发明可于通用型计算机所使用的微处理器装置中实现。最后，本领域普通技术人员应能在不脱离本发明范畴之前提下，以权利要求范围所揭露的概念及特定实施例为基础，设计或修改与本发明执行相同功能的其他结构。

附图中部分符号的说明如下：

100：微处理器；102：指令快取；104：指令转译器；106：暂存器别名表；108：指令排序器；112：执行单元与存储器子系统；116：重排序缓冲器(ROB)与结构化暂存器；122：载入单元；124：储存单元；126：储存队列；128：数据快取；132：二阶(L2)快取；134：总线接口单元(BIU)；208、608：组合逻辑；212：载入标签阵列；214：储存标签阵列；216：修改位阵列；218：数据阵列；222：载入请求；224：窥探请求；226：快取写入请求；228：储存请求；232、632、1332：部分MESI状态；234、634：已修改位；236、636、1232：完整MESI状态；242：收回请求。

Claims (32)

1.一种快取存储器系统，其特征在于，包括：

由储存元件组成的一第一阵列，其每一储存元件被配置用以储存一快取列；

由储存元件组成的一第二阵列，对应于由储存元件组成的该第一阵列，且该第二阵列的每一储存元件被配置用以储存一第一部分状态，该第一部分状态对应于该第一阵列的对应储存元件中的该快取列；及

由储存元件组成的一第三阵列，对应于由储存元件组成的该第一阵列，且该第三阵列的每一储存元件被配置用以储存一第二部分状态，该第二部分状态对应于该第一阵列的对应储存元件中的该快取列，其中，该第二部分状态表示该快取列是否已被修改，

其中，当该快取存储器系统修改该第一阵列的一储存元件的该快取列时，该快取存储器系统仅将该第二部分状态写入至该第三阵列的对应储存元件中，以表示该快取列已被修改，但并没有将该第一部分状态写入至该第二阵列的对应储存元件中，以及

其中，该快取存储器系统自该第二阵列与该第三阵列的对应储存元件分别读取该快取列的该第一部分状态与该第二部分状态，以决定该快取列的完整状态。

2.根据权利要求1所述的快取存储器系统，其特征在于，该第二阵列的每一储存元件被配置来储存该快取列的地址标签。

3.根据权利要求2所述的快取存储器系统，其特征在于，该第三阵列的每一储存元件并不被配置来储存该快取列的地址标签。

4.根据权利要求1所述的快取存储器系统，其特征在于，该第一部分状态表示该快取列是否有效、该快取列是否为该快取存储器系统所独占或该快取列是否为该快取存储器系统与其他快取存储器所共用。

5.根据权利要求1所述的快取存储器系统，其特征在于，当该快取存储器系统将该快取列配置于该第一阵列中时，该快取存储器系统将该快取列的完整状态写入至该第二阵列中对应的该第一部分状态。

6.根据权利要求5所述的快取存储器系统，其特征在于，当该快取存储器系统将该快取列配置于该第一阵列中时，该快取存储器系统也写入该第三阵列对应的该第二部分状态，以表示该快取列尚未被修改。

7.根据权利要求1所述的快取存储器系统，其特征在于，当该快取存储器系统将该第一阵列的该快取列设定为无效时，该快取存储器系统将该快取列的完整状态的写入至该第二阵列中对应的该第一部分状态。

8.根据权利要求7所述的快取存储器系统，其特征在于，当该快取存储器系统将该第一阵列的该快取列设定为无效时，该快取存储器系统也写入该第三阵列对应的该第二部分状态，以表示该快取列尚未被修改。

9.根据权利要求1所述的快取存储器系统，其特征在于，该完整状态为下列四种状态其中之一：已修改状态、独占状态、共用状态或无效状态。

10.根据权利要求1所述的快取存储器系统，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列尚未被修改时，该快取存储器系统决定该快取列的完整状态为自该第二阵列读取的该快取列的该第一部分状态。

11.根据权利要求1所述的快取存储器系统，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改时，该快取存储器系统决定该快取列的完整状态为已修改状态，除非自该第二阵列读取的该快取列的该第一部分状态为无效状态。

12.根据权利要求1所述的快取存储器系统，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改，且自该第二阵列读取的该快取列的该第一部分状态表示该快取列为该快取存储器系统与其它快取存储器所共用时，该快取存储器系统决定该快取列的完整状态为已修改状态。

13.根据权利要求1所述的快取存储器系统，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改，且自该第二阵列读取的该快取列的该第一部分状态表示该快取列为该快取存储器系统与其它快取存储器所共用时，该快取存储器系统决定该快取列的完整状态为该快取存储器系统与其它快取存储器所共用的状态。

14.根据权利要求1所述的快取存储器系统，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改，且自该第二阵列读取的该快取列的该第一部分状态表示该快取列为该快取存储器系统独占时，该快取存储器系统决定该快取列的完整状态为已修改状态。

15.根据权利要求1所述的快取存储器系统，其特征在于，该第一阵列、该第二阵列与该第三阵列各自具有N个集合，且各自被配置用以接收一存储器地址的一索引部分，以选择该N个集合其中之一，其中N为正整数。

16.根据权利要求15所述的快取存储器系统，其特征在于，于该N个集合中，每一集合具有多个项目，其中，该第三阵列被配置用以指定通过该索引部分对应于该第一阵列中该多个项目的每一该快取列的该第二部分状态。

17.一种快取存储器系统的存取方法，其特征在于，包括：

将一快取列储存至由储存元件组成的一第一阵列的一储存元件中；

将该第一阵列的对应储存元件中的该快取列的一第一部分状态储存至由储存元件组成的一第二阵列的一储存元件中，由储存元件组成的该第二阵列对应于由储存元件组成的该第一阵列；

将该第一阵列的对应储存元件中的该快取列的一第二部分状态储存至由储存元件组成的一第三阵列的一储存元件中，由储存元件组成的该第三阵列对应于由储存元件组成的该第一阵列，其中，该第二部分状态表示该快取列是否已被修改；

响应于该第一阵列的一储存元件的该快取列的修改，仅将该第二部分状态写入至该第三阵列的对应储存元件中，以表示该快取列已被修改，但并没有将该第一部分状态写入至该第二阵列的对应储存元件中；及

通过自该第二阵列与该第三阵列的对应储存元件分别读取该快取列的该第一部分状态与第二部分状态，决定该快取列的完整状态。

18.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，该第二阵列的对应储存元件被配置来储存该快取列的地址标签。

19.根据权利要求18所述的快取存储器系统的存取方法，其特征在于，该第三阵列的对应储存元件并不被配置来储存该快取列的地址标签。

20.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，该第一部分状态表示该快取列是否有效、该快取列是否为该快取存储器系统所独占或该快取列是否为该快取存储器系统与其他快取存储器所共用。

21.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当该快取存储器系统将该快取列配置于该第一阵列中时，该快取存储器系统将该快取列的完整状态写入至该第二阵列中对应的该第一部分状态。

22.根据权利要求21所述的快取存储器系统的存取方法，其特征在于，当该快取存储器系统将该快取列配置于该第一阵列中时，该快取存储器系统也写入至该第三阵列对应的该第二部分状态，以表示该快取列尚未被修改。

23.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当该快取存储器系统将该第一阵列的该快取列设定为无效时，该快取存储器系统将该快取列的完整状态写入至该第二阵列中对应的该第一部分状态。

24.根据权利要求23所述的快取存储器系统的存取方法，其特征在于，当该快取存储器系统将该第一阵列的该快取列设定为无效时，该快取存储器系统也写入该第三阵列对应的该第二部分状态，以表示该快取列尚未被修改。

25.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，该完整状态为下列四种状态其中之一：已修改状态、独占状态、共用状态或无效状态。

26.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列尚未被修改时，该快取存储器系统决定该快取列的完整状态为自该第二阵列读取的该快取列的该第一部分状态。

27.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改时，该快取存储器系统决定该快取列的完整状态为已修改状态，除非自该第二阵列读取的该快取列的该第一部分状态为无效状态。

28.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改，且自该第二阵列读取的该快取列的该第一部分状态表示该快取列为该快取存储器系统与其它快取存储器所共用时，该快取存储器系统决定该快取列的完整状态为已修改状态。

29.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改，且自该第二阵列读取的该快取列的该第一部分状态表示该快取列为该快取存储器系统与其它快取存储器所共用时，该快取存储器系统决定该快取列的完整状态为该快取存储器系统与其它快取存储器所共用的状态。

30.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，当自该第三阵列读取的该第二部分状态表示该快取列已被修改，且自该第二阵列读取的该快取列的该第一部分状态表示该快取列为该快取存储器系统独占时，该快取存储器系统决定该快取列的完整状态为已修改状态。

31.根据权利要求17所述的快取存储器系统的存取方法，其特征在于，该第一阵列、该第二阵列与该第三阵列各自具有N个集合，且各自被配置用以接收一存储器地址的一索引部分，以选择该N个集合其中之一，其中N为正整数。

32.根据权利要求31所述的快取存储器系统的存取方法，其特征在于，于该N个集合中，每一集合具有多个项目，其中，该第三阵列被配置用以指定通过该索引部分对应于该第一阵列中该多个项目的每一该快取列的该第二部分状态。

Images