CN1003680B - 可用实地址及虚地址寻址的高速缓冲存贮器 - Google Patents

Abstract

一种可由实地址及虚地址寻址的高速缓冲存贮器包括高速缓冲数据存贮器［６４］及标记存贮器［６６］。标记存贮器［６６］包括虚标记存贮器［６８］及实标记存贮器［７０］。实标记存贮器及虚标记存贮器都可用地址信号的最低有效位（ＬＳＢ）寻址以输出与存贮在高速缓冲数据存贮器［６４］内的数据相连系的地址的标记部分。开关［７８］在存贮器［６８］及［７０］的输出间选择，并由裁决单元［８８］控制。

Description

可用实地址及虚地址寻址的高速缓冲存贮器

本发明一般地与高速缓冲存贮器有关，且更具体地与高速缓冲存贮器（Cache）用实地址（Physical address）及虚地址（Virtual address）的可寻址性有关。

高速缓冲存贮器已用于现代计算机系统以便使该系统以主存贮器所能支持的大容量在更高的执行速度下工作。高速缓冲存贮器贮存有中央处理机容易存取的有限数目的指令或数据字。在从存贮器获得数据或指令时首先检查高速缓冲存贮器，以确定其中是否存有信息。如信息存于其中，则信息可以从高速缓冲存贮器中读出，否则，信息将从主存贮器读出。当信息必须从主存贮器读出时，然后将此新信息存于高速缓冲存贮器中并代替其中已存在的信息。为了决定在高速缓冲存贮器中要代替的信息，要作出有关决定，在高速缓冲存贮器内所存贮的数据及指令中哪些是最近最少存取的或“最近最少使用的”。这样做后，最常用的数据或指令将可在高速缓冲存贮器中统计地得到，因而增加给出系统的执行速度。

在利用最近最少使用系统时，需要在给出的高速缓冲存贮器内的不同的寄存器之间确定优先。为了完成这点，在过去已有不同的方法在应用，诸如颁发给张士哲（Shih-Jeh Chang）并转让给美国电话电报公司拜尔实验室的美国专利4，458，310号中所公开的内容。主要地是，需要应用附加存贮器来贮存对应于不同的数据寄存器的优先的信息。用指示字或类似物使这点很方便。然而实践证明，执行最近最少使用系统是困难的，并需要大量的电路及耗时的处理技术。

除去确定在高速缓冲存贮器中已知存贮位置的优先外，当在有多高速缓冲存贮器的多处理机的系统中使用时，高速缓冲存贮器的寻址也出现问题。在此形式的系统中，主存贮器及高速缓冲存贮器以实寻址方法工作，而多处理机以虚寻址方法工作。故为了访问其有关的高速缓冲存贮器，处理机必须将虚寻址翻译为实寻址。这样做的缺点是需要用预定数量的处理时间来完成翻译工作，因而降低了执行速度。故最好有能识别虚和实地址的高速缓冲存贮器，以便用一个高速缓冲存贮器就能直接利用任一种方式的地址，因而消除了将虚地址翻译为实地址的时间。

在制造高速缓冲存贮器时，必须是所有可存取的存贮器位置都是可用的以便当将存贮器合并入一系统时不致引进错误。虽然在N路相联组中可以允许有故障的位置，但是首先需要使该有故障位置不起作用，以便不要试图将数据存于其中或将数据从中读出。在已知技术中通过确定哪一个数据寄存器在系统加上电源后是有故障的，及将此信息存于存贮器内，使这一点很方便。然后利用电路来禁止访问高速缓冲存贮器的故障部分。这种方式的系统在1983年6月13～16日举行的第十届关于计算机总体设计的会议上帕特森（Patterson）等的“关于减少指令组计算机（RISC）的超大规模集成电路指令高速缓冲存贮器的总体设计”一文中作了说明。然而，这需要复杂电路且在启动系统之前扫描该系统。

鉴于以上缺点，需要一种总体设计能允许一系统直接通过实地址或虚地址与一高速缓冲存贮器通信，并以可靠及有效方式决定在给出的高速缓冲存贮器内那一个数据寄存器为最近最少存取数据的。

在此处公开并请求保护的本发明包括可以虚地址及实地址寻址的高速缓冲存贮器，在高速缓冲存贮器内寻址数据的地址分为最低有效位（Lsub）部分及标记部分（tag portion），最低有效位部分包括预定数目的最低有效位而最高有效位（Msub）部分则包括其余的或最高有效位。实地址及虚地址的最低有效位部分对于所有的寻址数据都是公共的。高速缓冲存贮器用来贮存选择数据，选择数据具有与该处有联系的虚地址及实地址。高速缓冲数据存贮器可用存贮在地址位置内的寻址数据所输出的收到地址的最低有效位部分寻址。提供的标记存贮器包括虚标记存贮器（Virtual tag memory）及实标记存贮器（Physical tag memory）。虚标记存贮器贮存与高速缓冲存贮器中所存贮的数据有关的虚地址的标记部分，实标记存贮器贮存与高速缓冲存贮器中所存的数据有关的实地址的标记部分。实标记存贮器及虚标记存贮器可用收到的地址的最低有效位部分寻址。提供有裁决单元（arbitration unit）用来决定收到的地址是虚地址还是实地址，且产生与决定相对应的控制信号。多路转换器（multiplexer）与虚标记存贮器及实标记存贮器的输出相连，并由裁决装置控制以选择标记存贮器中相对应的一个存贮器来输出虚标记部分或实标记部分。比较器将选出的虚标记部分或实标记部分与收到的标记部分相比较，以确定是否有匹配存在。如有匹配存在，则控制输出开关将高速缓冲存贮器的寻址数据输出。

在本发明的另一实施例中，与贮存的高速缓冲存贮器内的更新数据相联系的地址的虚标记部分及实标记部分有选择地贮存在虚标记存贮器及实标记存贮器内。多路转换器电路是双向的且响应输入到裁决装置的更新数据的虚地址或实地址产生虚标记部分及实标记部分。然后裁决装置控制多路转换器将实标记部分及虚标记部分分别存到虚标记存贮器及实标记存贮器中的适当位置。

为了更完整地理解本发明及其优点，现在结合附图作下列说明以作参考，其附图包括：

图1图示根据本发明的利用带高速缓冲存贮器的多处理机的多处理机系统的示意图;

图2图示对于给出的高速缓冲存贮器在标记存贮器中虚地址及实地址的变换;

图3图示识别虚地址及实地址用的高速缓冲存贮器的标记存贮器及数据存贮器;

图4图示高速缓冲存贮器的相联组的示意方块图;

图5图示最近最少使用（LRU）控制器的示意方块图;及

图6图示最近最少使用的控制器的一个方块的示意图。

现参见图1，其中图示有利用多个带有高速缓冲存贮器的微处理机单元的计算机系统的方块图。此系统通过其型式称为NU-总线的总线10通信。这是一载有32位实地址的32位总线。然而，也可以用任一种形式的系统总线。存贮器12通过总线14连到NU-总线10，且存贮器16也通过连接总线18连到总线10。在存贮器12及16之间的一串带点的线图示多个附加的存贮器。存贮器12及16中每个存贮器可以是任何形式的需要实地址来在其中存取的大容量存贮的存贮器。

高速缓冲存贮器20通过连接数据总线24连到总线接口22。总线接口22通过连接总线26与总线10相互连接。高速缓冲存贮器也通过连接总线30连到处理机28。包含在互连总线24上的地址为实地址而包括在互连总线30上的地址为虚地址，而处理机28仅与虚地址相连。

虚实地址翻译器（V/R翻译器）32中的实输入通过连接总线34连到连接总线24而其虚输入则通过连接总线36连到连接总线30。虚-实翻译器32使处理机28能通过总线接口电路22与数据总线10通信。

在运行时，处理机28的虚地址输出由高速缓冲存贮器20直接处理并与其相比较以便确定其中是否贮存有数据。如果高速缓冲存贮器20是从总线10来寻址、则实地址在连接总线24上输入到高速缓冲存贮器20并作出有关是否在高速缓冲存贮器20中存有此数据的决定。因而不必要在从处理机28中对高速缓冲存贮器20寻址之前查看虚-实地址翻译器。这就减少了处理时间，因为通常在主存贮器寻址以前在高速缓冲存贮器20内寻址。

虽然在高速缓冲存贮器20内寻址不需要虚-实翻译器32。但仍需要允许处理机28直接将实地址送到总线10。这在当高速缓冲存贮器20没有被寻址时诸如当处理机28完成其他外围操作时使用。

第二高速缓冲存贮器38通过连接总线42连到总线接口电路40以便通过连接总线44与总线10相连。高速缓冲存贮器38也通过连接总线48与处理机46相互连接，处理机46与处理机28相似。虚-实翻译器50的虚输入通过连接总线52连到连接总线48且其实输出通过连接总线54连到连接总线42以便将实地址送到该处。虚-实翻译器50与虚-实翻译器32相似，两者都使用常规电路来实现。

图1的系统可包括任何数目的主存贮器及任何数目的带有相联系的高速缓冲存贮器的处理机。当这种规模的系统工作时，高速缓冲存贮器20及38贮存从统计的观点看最常用的数据。因而，当从主存贮器12或16存取数据时，该数据贮存在各自的高速缓冲存贮器内供以后使用。其后，放在总线上作检索数据及/或指令用的地址首先输入到相联系的高速缓冲存贮器内以便确定是否其中存有数据。如没有，则由产生地址的微处理机从使用的主存贮器中检索数据，且此数据也贮存在相联系的高速缓冲存贮器内。存贮此数据时，重写在高速缓冲存贮器内的最近最少使用的数据寄存器。

当读数据时，问题发生在数据可能被包含在对面的高速缓冲存贮器及主存贮器之中。因而必须利用一些算法来保证存取正确数据。这通常包括检查系统中所有高速缓冲存贮器的内容。例如，如果处理机28从总线10读数据，则需确定读的数据是否贮存在高速缓冲存贮器38之中，这需要高速存贮器20及38对实地址进行响应以保证系统数据完整性。然而，利用虚寻址的处理机28或46的相联系的一个处理机也直接向高速缓冲存贮器寻址。为了提高系统性能，所利用的高速缓冲存贮器直接与虚地址或实地址相联而不用虚-实翻译器。

现在参见图2，图中示意表示了虚地址及实地址及用这些地址直接寻址的高速缓冲存贮器寻址系统的格式。虚地址可以有任何位数，并按照预定的模式安排在信息组内。此外，实地址也可用预定的顺序安排。数据安排在“页”中，它是存贮器单元。这允许将存贮器内的不同位置变换为存贮器内的其他位置。地址的前八位在虚存贮器及实存贮器中定义在一页中的位置。通过利用公共的图表，他们可以直接相互变换。例如八位导致存贮器每页256个字。然而，应懂得可使用其他页面大小。定义页长的八位是地址最低有效位（“Lsubs”）。最高有效位（Msubs）形成地址的其余部分。实地址及虚地址的最高有效位不一定要在长度上一样，因为虚存贮器可有较大的容量，尽管有些系统有相对较小的虚地址。页数由地址的最高有效位决定。

在常规的高速缓冲存贮器中，地址分为八位最低有效位信息组及剩余的最高有效位信息组。八位最低有效位信息组分为三位信息组56及五位信息组58。两信息组56及58定义高速缓冲存贮器的存贮块，而每块则分为预定数目的存贮位置。五位信息组58对应于高速缓冲存贮器内的各存贮块并定义32个分开的存贮块，而三位信息组56对应于在一给出的存贮块内的单个寄存器，并在每个存贮块中定义8个存贮器位置。在给出的存贮块中这些位置的每个位置都用来存贮数据。

在高速缓冲存贮器的地址内，最高有效位部分分为两种型式，第一型式60被定义为虚标记，而第二种型式62则被定义为实标记。型式60及62中每一种型式占据高速缓冲存贮器地址的同一部分;即，高速缓冲存贮器的最高有效位是从虚寻址单元或实寻址单元收到的。如下面参照图3所述的那样，在高速缓冲存贮器的数据部分内出现的高速缓冲存贮器地址的最高有效位存贮在分成32个分开的存贮器位置的标记存贮器。

现参见图3，其中图示了图1的高速缓冲存贮器20及38的示意方块图。每个高速缓冲存贮器分为数据存贮器64及标记存贮器66。数据存贮器分成32块并标号从“0”至“31”。每个存贮块分成8个分开的存贮位置，标号为“0”到“7”。因而，数据存贮器64包括256个数据字并贮存在存贮器的一页中。然而包括在数据存贮器64中的数据不一定对应于存贮器的一个特殊页。而是在数据存贮器64中每一存贮块可对应于从存贮器任一页来的八个字块。在数据存贮器64中的位置仅仅取决于八个最低有效位。如将在下面所述的那样，存贮在标记存贮器66的最高有效位仅对应于在数据存贮器64中一个数据字。然而，所有的与其有关的数据存在数据存贮器的同一块内，如由三位段56所定义的那样。

标记存贮器66分为两个不同的存贮器，虚标记存贮器68及实标记存贮器70，两存贮器68及70都有32个存贮位置并标为从“0”到“31”。存贮器的宽度等于在实标记部分62或虚标记部分60中最高有效位的宽度。例如，假如实地址是32位长，最高有效位为24位长则因而，实标记存贮器70是24位宽。在另一方面虚标记存贮器可有不同的长度，它决定于其中最高有效位的长度。

每个贮存在标记存贮器66中的最高有效位对应于给出的实地址或虚地址的最高有效位。位置决定于五位信息组58，反之五位信息组58也对应于数据存贮器64的块。因而五位信息组58确定存进对应数据的数据存贮块及在存有标记的最高有效位的标记存贮器66中的位置。此外，地址的三位信息组56确定在对应于该地址的数据存贮在已知块内的八个位置中的那一个位置。

为了对数据存贮器64及标记存贮器66寻址，从高速缓冲存贮器地址中抽出该地址的最低有效位并放在最低有效位地址总线72上。从最低有效位总线72中抽出高速缓冲存贮器地址的五位信息组58并放在五位总线74上。并被分支输入虚标记存贮器68及实标记存贮器70以便为其提供地址。虚标记存贮器68的输出在总线76上输出并输入到开关78，且实标记存贮器70在总线80上输出并输入到开关78的剩余输入处。开关78在两存贮器68及70的输出之间进行选择。

数据存贮器64通过构成高速缓冲存贮器地址的八位最低有效位进行寻址，这些位是从最低有效位地址总线72上接收的。对于每个最低有效位地址，选择数据存贮器64内的256个位置中的一个位置，并在数据总线82上输出并输入到开关84。开关84是常开的开关，其输出连到总线86以便输出到系统的其余部分。

开关78由裁决装置88控制，该装置在控制线90上输出控制信号并输入到开关78的控制输入端。裁决装置88有两个输入端，其中之一通过总线94连到虚地址机构92而其中另一输入则通过总线98与实地址机构96相连。裁决装置88的工作是在虚地址及实地址之间进行判别以便选定在标记存贮器68或70中应选择的一个存贮器。

开关78的输出通过总线102输入到比较电路100。比较电路的另一输入端连到最高有效位地址总线104，该总线载有高速缓冲存贮器地址（或为虚地址或为实地址）的最高有效位，如由图2的部分60及62所代表的那样。地址总线104与裁决装置88的输出相连。地址总线104还与连接总线102相联以便允许地址数据输入到开关78。比较器100将对其有最高有效位存贮在标记存贮器66中的虚地址单元92或实地址单元96所提供的地址之间的最高有效位进行比较。如果进行良好的比较，则有信号在控制线106上输出以便控制开关84将数据从总线82输出到总线86。例如，如虚地址输入到裁决装置88，开关78选择输出总线76。对于其中五位段58对应于逻辑“4”的地址，从虚标记存贮器68选出标为“4”的存贮位置，以便在总线102上输出。同时在该处，数据存贮器收到地址的八个最低有效位，并从中将256个数据中的一个数据输出到数据总线82。如在虚标记存贮器68的位置“4”中所存的地址最高有效位对应于从虚地址单元92所供应的最高有效位，则比较器100在线106上输出一控制信号使数据总线82上的数据与数据总线86相连，并进到系统的其余部分。然而，如未发现匹配，则在系统内到处指出“未命中”（“Miss”），此时通过寻址单元对主存贮器进行检索来取得数据，此外，该地址的最高有效位写进标记存贮器66，而与其有关的数据则写进数据存贮器64。然而安排在N路相联组内的高速缓冲存贮器需要一些型式的优先指示器来确定存贮位置，这将在下面说明。为了将数据写进标记存贮器68及70，最高有效位数据在总线102上输入，开关78对裁决装置作出响应，在存贮器68或70中选择适当的一个存贮器。裁决装置88的工作是将实地址的最高有效位部分及虚地址的最高有效位部分通过开关78写入各自的标记存贮器70或68。

现在参见图4，图中为用以确定其中最近最少使用的数据位置的附有相联系的电路的四路相联组的高速缓冲存贮器的示意方块图。为了简化，上述在虚地址及实地址之间进行判断的电路没有包括在内。数据存贮器包括四个数据存贮器108，110，112及114及标记存贮器（tag memory）包括四个标记存贮器116，118，120及122。数据存贮器108-114中的每一个存贮器与标记存贮器116-122中的一个存贮器相联系，他们分别标以数字“1”，“2”，“3”及“4”。

在地址总线124上载有高速缓冲存贮器用的地址，而数据则载在数据总线126上。数据总线126通过总线驱动器125连到数据存贮器108以便从中读出数据并通过总线驱动器128连到数据存贮器108以便从中接收数据。并以同样的方式分别通过总线驱动器130，132及134从数据总线将数据读入数据存贮器110，112及114。通过总线驱动器136，138及140分别将数据从存贮器110，112及114读入数据总线126。如上所述，数据存贮器108-114用的地址包括从地址总线124来的八个最低有效位，并通过最低有效位数据总线142在地址输入端接收。数据以常规的方式从存贮器108-114中写入或读出，以便用于高速缓冲存贮器

标记存贮器116，118，120及122与比较器144，146，148及150分别相连。比较器144-150中每一个都有两个输入端，其中一个输入端与标记存贮器116-120中的一个相连而其中另一个输入端则连到地址总线124上的地址的最高有效位。比较器144通过数据总线152与标记存贮器116相连并通过最高有效位数据总线154与地址总线124相连。比较器146，148，150以同样方式分别通过数据总线156，158及160连到有关的标记存贮器118，120及122，比较器146，148及150的其他输入端分别与最高有效位数据总线162，164及166相连，标记存贮器116-122的地址输入端连到最低有效位数据总线168，该总线连到高速缓冲存贮器地址的八位最低有效位段中的最高有效的五位。虽然没有画出，最高有效位数据总线154，162，164及166通过缓冲器连到标记存贮器116-122的数据输入端以便允许数据写入标记存贮器116-122。

比较器144-150的输出端连到四输入或非门170的各输入端。此外比较器144-150中的每个比较器的输出分别连到总线驱动器128，136，138及140的控制输入端以便能从数据存贮器108-114中检索数据。或非门170的输出确定关于在存贮器中的数据是否已完成“射中”（“hit”）或“未命中”（“miss”）。“射中”是指数据已从高速缓冲存贮器中被存取，而“未命中”是指数据没有存贮器在高速缓冲存贮器内，必须从主存贮器中存取。利用常规技术来从主存贮器中检索数据。然而，一旦已被检索到，则必须存贮在数据存贮器的最近最少使用存贮块内。如上所述，在对应于地址中的最低有效位的八个字的存贮块中检索数据。

为了确定存贮器的最近最少使用存贮块，比较器144-150的输出端通过线174输入到最近最少使用（简称LRU）控制器172。LRU控制器172通过双向数据总线178与LRU存贮器176相连。LRU存贮器176通过最低有效位（简称Lsub）数据总线180从地址总线124接收其地址，Lsub数据总线包括八位Lsub的五个最高有效位。

当没有存贮在数据存贮器108-114中的数据已被寻址时该数据必须从主存贮器中存取，且也被高速贮存（“cached”）。在高速贮存的数据（caching data）中，LRU控制器172首先检查LRU存贮器176以确定对于地址的给出的八位Lsub部分、数据存贮器108-114中那一个存贮器是最近最少使用的。一旦这被确定，就在线182上输出一个信号到数据存贮器108-114及标记存贮器116-122。这些线标有WE则表示写（Write）/允许（Enable）。将数据写入给出的数据存贮器及与高速缓冲存贮器相连系的标记存贮器所用的电路为常规线路。

除了从LRU存贮器176接收数据以便确定那一个高速缓冲存贮器是最近最少使用的，LRU控制器172也更新用于每个高速缓冲存贮器存取的LRU存贮器176。然而，这预先假设在有关的高速缓冲存贮器中的每个存贮位置是有效的，因而能从中读出数据并写入数据。如有一个存贮位置有故障，则错误可能引起不能存取所贮存的数据或取出错误的数据。虽然故障的存在并不有损于N路相连的高速缓冲存贮器，但需要确定哪一个存贮位置是有故障的，且防止数据写入此存贮位置或从中读出。在本发明中用一故障存贮器184就能很容易做到这一点，该故障存贮器的地址输入端通过Lsub数据总线186连到地址总线124，用来接收八位Lsub信息组的五个最高有效位，且其数据输出通过数据总线188连到LRU控制器172。故障存贮器184中已包括指示高速缓冲存贮器的每一存贮位置的故障情况的数据，因而阻止LRU控制器172指定该存贮位置为最近最少使用的高速缓冲存贮位置。此外，故障存贮器184的输出输入到每个比较器144-155，以其中一位相联以便使比较器输出被截止。如果向故障位置存取数据则在故障存贮器184中所存贮的数据阻止“命中”信号被寄存。

在最佳实施例中，故障存贮器184在工厂中预先编好程序以提供在高速缓冲存贮器内所有存贮位置的故障情况的永久记录。因而有可能籍助于LRU控制器172且不使用不适当的处理来控制在N路相联的高速缓冲存贮器中的数据的高速存贮。这将在下面说明。

进一步参见图3及图4，对系统的工作作更详细地说明。开始，一个处理机或寻址单元送一虚地址或实地址到裁决装置，同时也送到地址总线124。然后地址的最低有效位输入到标记存贮器116-122且存贮在其中的适当的最高有效位输出到比较电路144-150。在图3中的开关78确定是否有虚标记或实标记输出到比较器电路144-150。应明白比较器电路144-150与图3的比较器电路100是相同的。

在从选出的标记位置输出最高有效位的同时，数据在数据存贮器108-114中寻址，且此数据从中输出。在任一比较器144-150中进行很好的比较后，收发器128，136，138或140中适当的一个收发器由比较器144，146，148及150中的一个比较器分别启动，并将数据在数据总线126上输出。此外，驱动或非门170的输出为逻辑“低”来贮存“射中”（“hit”）信号。

如果在标记存贮器116-122中未发现对应于给出的八位Lsub信息组的最高有效位，则或非门170的输出为代表“未命中”（“miss”）的逻辑“高”。然后系统访问主存贮器以便获得存在该地址位置的所要的数据。此外此数据必须写进高速缓冲存贮器的适当位置。因为，如上所述，每个数据字与一数据块相连系，在高速缓冲存贮器地址中的五位信息组58所定义的存贮块与被寻址的字一起被检索与存贮。例如，如果五位信息组58为存贮块“31”的逻辑等同物，三位信息组56为在存贮块“31”中的第四段的逻辑等同物，然后所有的具有同样的最高有效位及同样的五位信息组58的数据都被放进存贮块“31”;即所有围绕第四段中的数据字的数据字都放进存贮块“31”。此外，地址的有关最高有效位信息组存贮在有关的标记存贮器内。将此数据及有关的标记存入数据存贮器108-114及标记存贮器116-122的方法是常规的。而且在写满现有高速缓冲存贮器数据之前，要检查确定是否在主存贮器中包括的有关数据必须更新。

在将数据写入数据存贮器108-114之前，必须对哪一个数据存贮器包括最近最少使用的数据作出决定。这通过使用LRU存贮器单元176及LRU控制器172来实现。在数据已被写入之后更新LRU存贮器176并可以将下一个地址供给高速缓冲存贮器。

现参见图5，本图为LRU控制器172的示意方块图，该控制器组成树状结构，树的分支与每个单个标记存贮器及有关的比较器相连。在两个图中同样的数字指示同样的部分。在相联组内的两个高速缓冲存贮器与控制电路190相连而其余两个高速缓冲存贮器则与控制电路192相连系。两控制电路190及192则与较高级控制电路194相连，此结构形式为等级结构，它的多个等级依赖于在N路相连组内的高速缓冲存贮器的数目。如果，例如，在相连组内有八个分开的高速缓冲存贮器则应利用四个较低等级的控制电路，两个中级控制电路及一个高级电路，总数为七个。故对于N路相连组，则有N-1个控制电路。每个控制电路应有一位存贮器与其相连以确定连于其上的分支中哪一个为最近最少使用的分支，因而N路相连组需要N-1位存贮器作为在标记存贮器中的每个可寻址位置以便确定最近最少使用的存贮位置。

每个较低等级的控制电路190及192在其输入端接收两个从线174来的由比较器144-150输出的两个存取信号（ACC）及从故障存贮器184来的两个故障信号。每个控制电路190及192也在标有“WE”的线182上输出最近最少使用（LRU）信号。此外，存取输出信号（ACC）及故障输出信号除从中接收在标有LRU的输入端上的LRU信号外还输出到下一个较高级的控制电路194。较高级控制电路194与较低级控制电路190及192相同。

数据总线178有通过收发器196，198及200分别连到每个控制电路190-194的位线。每个收发器196-200有一允许（Enable）输入（EN）来确定数据是从数据总线178读出还是写入数据总线178。收发器196-200的输出连到标有LRU MEM IN及LRU MEM OUT的输入端。

图5的最近最少使用接法及其总体设计通过提供关于确定最近最少使用成员的有效方法使在N路相连组内的大量高速缓冲存贮器方便地工作。当用可由虚地址及实地址直接寻址的高速缓冲存贮器构件时这一点变得更加重要。这是由于对相对于页面大小的单个大小限制。例如，如果页面大小是256个字，实地址及虚地址将有八位共同的信息组。这就防止增加单个高速缓冲存贮器构件的大小，如增加就需要用大的N路相连组。

现参见图6，图中为控制器190-194之一的示意图。输入标记LRU MEM IN连到结点202，加于其上的数据的状态或为逻辑“1”或为逻辑“0”。对于逻辑“1”，则在一个方向上导引电路来指出一个分支为最近最少使用的装置，而对于逻辑“0”，则在相反方向上导引电路来指出其他分支是最近最少使用的分支。或门204的一个输出端连到结点202而其另一输入则与故障输入端相连，为了说明，该输入端标为FI1。或门204的输出连到与门206的一个输入端，与门206的输出则连到与门208的一个输入端。与门206的其他输入通过反相器210连到其他故障输入端FI2。与门208的输出连到标为LRU2的输出，它连到标为WE的线182。与门208的其他输入端连到标为LRUI的从较高级控制电路来的LRU输入。

与门208的工作是当从LRUI输入及与门206的输出收到两个信号时触发LRU2线。此情况除来自从处在正确逻辑状态的LRU存贮器176（该逻辑状态在本方式中为逻辑“1”）接收的数据位外还来自于选择分支作为最近最少使用的分支的较高级控制电路。在或门204的输入端上的逻辑“1”加上由反相器210输出的逻辑“1”使得与门206输出逻辑“1”到与门208的输入端。当逻辑“1”在LRUI输入端上输入时则触发LRU2输出。

标为LRU1的其他LRU输出连到与门212的输出端，与门212的一个输入端连到LRUI信号而其另一个输入端则连到与门214的输出。与门214的一个输入端通过反相器216连到标为FI1的其他故障信号而其另一输入则连到或门218的输出。或门218的一个输入端通过反相器220连到结点202而其另一输入则连到其他故障信号FI2。为了触发与门212工作，从LRU存贮器176收到的数据位必须是逻辑“0”，可使反相器220的输出为逻辑“1”。

为了使贮存在LRU存贮器176中的数据导引LRU信号到LRUⅠ输出或LRUⅡ输出，故障输入FI1及FI2必须是逻辑“0”。然而，如果在对应于给出分支的故障存贮器186中存贮有故障信号，则此故障信号将LRU信号偏置到控制电路的对面。例如，如果在LRU1信号所控制的高速缓冲存贮器上存在故障，则将逻辑“1”信号输入到FI1输入。这在或门204的输出上置逻辑“1”而在反相器216的输出上置逻辑“0”。这就禁止与门212以防止LRU1信号出现且偏置与门208，因而只有LRU1信号对触发LRU2输入是需要的。

与LRU1信号相联系的存取信号标为ACC1且它和与门224的输入端相连，与门224的另一输入端则与反相器216的输出相连。与门224的输出端连到或门226的一个输入端，或门226的输出端则连到控制电路的LRU MEM OUT端。与LRU2输出相联系的其他存取信号则和与门228的一个输入端相连，与门228的另一个输入则连到反相器210的输出端。与门228的输出通过反相器232连到与门230的一个输入端。与门230的另一个输入端则连到LRUM EM IN输入而与门230的输出则连到或门226的另一输入端。与门224及228的输出端连到或门234的各自输入端，或门234的输出端连到从控制电路来的标为ACC的输出存取信号。

在工作中当在FI1及FI2上的故障信号在逻辑“0”状态时在ACC1或ACC2输入上的存取信号触发各自的与门224或228。如触发ACC1，或门226的输出端在逻辑“高”状态。如触发ACC2输入且故障信号FI2为逻辑“0”，则触发与门228在反相器232的输出端上置逻辑“0”，导致在LRU MEM OUT输出端上为逻辑“0”。应该明白只有一存取信号在ACC1或ACC2上出现，且在同一时间不会有两个输入都被触发。

当ACC1或ACC2都没有被触发时，与门224及228的输出为逻辑“0”状态。这导致从与门224来的逻辑“0”输入到或门226的一输入端而从反相器232来的逻辑“1”则输入到与门230。与门230的另一输入端连到LRU MEM IN输入因而其上的逻辑“0”来自从与门230来的逻辑“0”输出。当没有ACC2信号出现时其上的逻辑“1”输入来自与门230的输出端上的逻辑“1”。

存取信号的出现将改变存贮位的状态以导引电路到在相对的分支上的高速缓冲存贮器。例如，如果LRU MEM IN输入在逻辑“0”状态，则触发LRU1信号，因而指出这是两分支最近最少使用的分支。如果触发与ACC1信号相联系的分支则LRU MEM OUT输出必须变为逻辑“1”。然后此位存在LRU存贮器176内。这有效地使控制器偏向LRU2输出，这决定于从较高级控制电路来的LRU输入的状态。如果，在下一次存取时，存取与LRU2输入相联系的分支则触发ACC2信号，因而在反相器232的输出端上置逻辑“0”。这使得或门226的输出为逻辑“0”使控制电路偏向LRU1输出。

故障信号FI1及FI2两个都输入到与门236，其输出则连到FO输出。此输出输入到较高级控制电路的一个分支。如上所述，故障的出现压倒贮存在LRU存贮器176中的数据位并总是将LRU信号偏向已知控制器的相对的分支。由于此方式，具有与其相联系的故障的分支将总是出现为两个分支中最后存取的分支，因而防止将数据写入那个分支。

总之，本发明已提供一种可直接用虚地址或实地址寻址的高速缓冲存贮器。利用等级的树状结构在N路相连组中通过利用已贮存的存贮器的N-1位来确定最近最少使用的存贮位置。LRU算法是根据已存贮的存贮位来指出哪一个装置是最近最少使用的位，且也根据防止故障存贮位置被指定为最近最少使用的存贮位置的故障位，因而防止将数据写入其中。

虽然本发明的实施例已作了详细描述，应明白不偏离由附属权利要求所定义的发明的精神及范围就可在其中进行不同的变化，更换及取代。

Claims (6)

1、一种高速缓冲存贮装置包括：

接收所要数据的地址的总线装置，上述地址具有包含预定数目的最低有效位部分及包含剩下的或最高有效位的最高有效位部分，上述地址的最低有效位部分对所有被寻址的数据都是公共的;存贮有上述高速缓冲存贮装置的数据的数据存贮器;比较装置;标记存贮装置;及传送来自数据存贮器的数据的开关装置84;其特征包括：

上述标记存贮装置（66）贮存有与上述贮存的数据有关的虚地址及实地址的最高有效位部分，当上述收到的最低有效位部份对应于与贮存在上述数据存贮器中的数据有关的上述地址的最低有效位部分时上述存贮的虚最高有效位部分及实最高有效位部分可用从上述标记存贮装置（66）输出的上述收到的地址的最低有效位部分寻址;

地址选择装置，如上述收到的地址是虚地址则该选择装置选择上述贮存的虚最高有效位部分，如上述收到的地址是实地址则该选择装置选择上述贮存的实最高有效位部分;及

上述比较装置（100）对上述选择装置进行响应，并将上述选出的最高有效位部分与上述收到的地址的最高有效位部分进行比较，且提供对传送来自上述数据存贮器的上述选出的数据的上述开关装置84进行控制的输出信号。

2、如权利要求1所述的高速缓冲存贮装置，其特征还包括在上述数据存贮器内存贮更新数据的装置，上述更新数据的最低有效位部分决定存贮上述更新数据的上述数据存贮器中的地址位置，及

在由上述更新数据的有关地址的最低有效位部分所决定的上述标记存贮器（66）内的地址位置中贮存上述更新数据的有关实地址和虚地址的最高有效位部分的存贮装置。

3、如权利要求1所述的高速缓冲存贮装置，其特征在于上述地址选择装置包括：

从上述总线装置接收上述地址并决定上述地址是虚地址还是实地址的裁决装置（88），上述裁决装置（88）提供有识别上述收到地址是虚地址还是实地址的控制信号;及

与上述标记存贮装置（66）的输出相连并在由上述标记存贮装置（66）输出的上述虚最高有效位部分及上述实最高有效位部分之间进行选择的多路开关（78），上述多路开关（78）由从上述裁决装置来的上述控制信号进行控制，从而如上述收到的地址是虚地址时则输出上述虚最高有效位部分，如上述收到的地址为实地址则输出实最高有效位部分，且上述多路开关（78）的输出与上述比较装置（100）的输入相连。

4、如权利要求1所述的高速缓冲存贮装置，其特征在于上述比较装置包括接收上述收到的地址的最高有效位部分及由上述裁决装置输出的最高有效位部分的异或电路，当上述收到的地址的最高有效位部分与上述地址选择装置所选出的最高有效位部分相同时上述异或电路的输出对上述开关装置进行控制。

5、如权利要求1所述的高速缓冲存贮装置，其特征在于与数据有关的虚地址和实地址的最低有效位部分分成第一部分及第二部分，及上述标记存贮装置分成各数据块，上述第一部分定义上述数据块的地址位置，上述第二部分定义在每个数据块内的数据的位置，数据地址的最低有效位部分的上述第一部分定义在上述标记存贮装置（66）内存贮的上述数据的上述虚最高有效位部分及实最高有效位部分的位置。

6、如权利要求1所述的高速缓冲存贮装置，其特征在于上述标记存贮装置（66）包括第一和第二存贮部分（68），（70），每个部分都与上述总线装置（72）的最低有效位部分相连，并且其中具有多个存贮位置，每个都可用上述收到的地址的最低有效位部分寻址，从而在上述收到的地址的最低有效位部分已知时上述第一和第二存贮部分（68），（70）中的每个存贮部分都输出数据，上述第一存贮部分（68）贮存有与贮存在上述数据存贮器中的数据有关的虚地址的最高有效位部分，及上述第二存贮部分（70）贮存有与贮存在上述数据存贮器中的数据有关的实地址的最高有效位部分，在上述第一和第二存贮部分寻址的同时，输出对应于上述收到的地址的最低有效位部分的数据的虚最高有效位部分和实最高有效位部分。