用于多处理器系统的探听过滤器以及相关探听过滤方法

摘要

本发明提供种位于多处理器系统中的探听过滤器包含储存装置以及控制电路,其中该控制电路管理储存在该储存装置的至少第型态条目以及至少第二型态条目,设定该第型态条目以储存该多处理器系统的多个快取条列状态信息,此多个快取条列仅存在于高速缓存中,且在存储器地址上有相互间的关联性。而设定该第二型态条目以记录该多处理器系统的至少快取条列状态信息,此快取条列存在于多个高速缓存中,且在存储器地址上有相互间的关联性。

权利要求

1.一种用于多处理器系统的探听过滤器，包含:

储存装置；以及

控制电路，用以管理储存在该储存装置中的至少一第一型态条目以及至少一第二型态条目；

其中该第一型态条目被设定用以记录指出该多处理器系统的第一快取以及与多个第一快取列相关的第一需求存储器地址的信息，其中该多个第一快取列的每一个皆仅存在于该第一快取中；以及该第二型态条目被设定用以记录指出该多处理器系统的多个第二快取以及与第二快取列相关的至少一第二需求存储器地址，其中该第二快取列存在于该多个第二快取中。

2.如权利要求1所述的探听过滤器，其特征在于，该第一型态条目具有第一数据结构，而该第二型态条目具有第二数据结构，其中该第二数据结构不同于该第一数据结构。

3.如权利要求2所述的探听过滤器，其特征在于，具有该第一数据结构的该第一型态条目包含:地址栏，用以储存K个存储器地址的共同部分，其中该K个存储器地址包含该第一需求存储器地址，且K为大于一的正整数；

向量栏，用以储存K个指示位，其中该K个指示位用以分别指示该第一快取中K个快取列的存在与否，且该K个快取列包含该多个第一快取列；以及快取标示栏，用以指示该第一快取。

4.如权利要求2所述的探听过滤器，其特征在于，该多处理器系统包含N个快取，且具有该第二数据结构的该第二型态条目包含:地址栏，用以储存M个存储器地址的共同部分，其中该M个存储器地址至少包含该第二需求存储器位置，其中N为大于一的正整数而M为大于或等于一的正整数；

M个向量栏，分别对应该M个存储器地址，其中M个向量栏中的每一向量栏包含分别指示N个快取中的相同快取列的N个指示位。

5.如权利要求1所述的探听过滤器，其特征在于，该储存装置包含多个可组态条目，且每一可组态条目具有相同位长度；而该控制电路另用以动态地设定第一可组态条目以作为该第一型态条目以及动态地设定第二可组态条目以作为该第二型态条目。

6.如权利要求1所述的探听过滤器，其特征在于，该储存装置包含至少一第一子储存装置以及第二子储存装置，该第一子储存装置包含具有第一位长度的条目，而该第二子储存装置包含具有第二位长度的条目，其中该第二位长度不同或相同于该第一位长度；以及该控制电路另用以在该第一子储存装置中储存第一型态条目以及在该第二子储存装置中储存第二型态条目。

7.如权利要求1所述的探听过滤器，其特征在于，该控制电路另用以在储存装置中将该第一型态条目的至少一部分转换为至少另一第二型态条目。

8.如权利要求1所述的探听过滤器，其特征在于，该控制电路另用以在储存装置中转换该第二型态条目的至少一部分到至少另一第一型态条目中。

9.如权利要求1所述的探听过滤器，其特征在于，该第一型态条目系根据直接对映条目配置、集合关连式条目配置及完全关连式条目配置中的其中之一以储存至该储存装置。

10.如权利要求1所述的探听过滤器，其特征在于，该第二型态条目系根据直接对映条目配置、集合关连式条目配置以及完全关连式条目配置中的其中之一以储存至该储存装置。

11.一种用于多处理器系统的探听过滤器，包含:

储存装置，其中该储存装置包含多个可组态条目；以及

控制电路，用以动态地设定至少一可组态条目以作为具有第一数据结构的至少一第一型态条目，以及动态地设定至少一可组态条目以作为具有第二数据结构的至少一第二型态条目，其中该第二数据结构不同于该第一数据结构，且该至少一第一型态条目以及该至少一第二型态条目系用以记录存在于该多处理器系统的快取中的快取列的状态。

12.一种用于多处理器系统的探听过滤器，包含:

储存装置；以及

控制电路，用以管理储存在该储存装置的多个条目，其中该多个条目系用以记录存在于该多处理器系统的快取中的快取列的状态，该多个条目包含至少一第一条目以及第二条目，其中该第一条目根据第一条目配置储存在该储存装置中，而该第二条目根据第二条目配置储存在该储存装置中，且该第一条目配置以及该第二条目配置具有相同或不同的条目配置方式。

13.一种应用于多处理器系统的探听过滤方法，包含:

在储存装置中记录至少一第一型态条目，其中该第一型态条目被设定用以记录指出该多处理器统的第一快取以及与多个第一快取列相关的第一需求存储器地址的信息，其中该多个第一快取列的每一个皆仅存在于该第一快取中；以及在该储存装置中记录至少一第二型态条目，其中该第二型态条目被设定用以记录指出该多处理器系统的多个第二快取以及与一第二快取列相关的至少一第二需求存储器地址的信息，其中该第二快取列存在于该多个第二快取中。

14.如权利要求13所述的探听过滤方法，其特征在于，该第一型态条目具有第一数据结构，而该第二型态条目具有第二数据结构，其中该第二数据结构不同于该第一数据结构。

15.如权利要求14所述的探听过滤方法，其特征在于，具有该第一数据结构的该第一型态条目包含:地址栏，用以储存K个存储器地址的一共同部分，其中该K个存储器地址包含该第一需求存储器地址，且K为大于一的正整数；

向量栏，用以储存K个指示位，其中该K个指示位用以分别指示该第一快取中K个快取列的存在与否，且K个快取列包含该多个第一快取列；以及快取标示栏，用以指示该第一快取。

16.如权利要求14所述的探听过滤方法，其特征在于，该多处理器系统包含N个快取，且具有该第二数据结构的该第二型态条目包含:地址栏，用以储存M个存储器地址的共同部分，其中该M个存储器地址至少包含该第二需求存储器位置，其中N为大于一的正整数而M为大于或等于一的正整数；

M个向量栏，分别对应该M个存储器地址，其中M个向量栏中的每一向量栏包含分别指示N个快取中的相同快取列的N个指示位。

17.如权利要求13所述的探听过滤方法，其特征在于，该储存装置包含多个可组态条目，且每一可组态条目具有相同的位长度；且该探听过滤方法另包含:动态地设定第一组态条目以作为该第一型态条目；以及

动态地设定第二组态条目以作为该第二型态条目。

18.如权利要求13所述的探听过滤方法，其特征在于，该储存装置包含至少一第一子储存装置以及第二子储存装置，该第一子储存装置包含具有第一位长度的条目，而该第二子储存装置包含具有第二位长度的条目，其中该第二位长度不同或相同于该第一位长度；以及该至少一第一型态条目被储存在该至少一第一子储存装置中，该至少一第二型态条目被储存在该至少一第二形态条目中。

19.如权利要求13所述的探听过滤方法，其特征在于，另包含:

在储存装置中转换该第一型态条目的至少一部分至至少另一第二型态条目。

20.如权利要求13所述的探听过滤方法，其特征在于，另包含:

在储存装置中转换该第二型态条目的至少一部分至至少另一第一型态条目。

21.如权利要求13所述的探听过滤方法，其特征在于，该第一型态条目系根据直接对映条目配置、集合关连式条目配置以及完全关连式条目配置中的其中之一以储存至该储存装置。

22.如权利要求13所述的探听过滤方法，其特征在于，该第二型态条目系根据直接对映条目配置、集合关连式条目配置以及完全关连式条目配置中的其中之一以储存至该储存装置。

23.一种用于多处理器系统的探听过滤方法，包含:

利用储存装置，其中该储存装置包含多个可组态条目；

动态地设定至少一可组态条目以作为具有第一数据结构的至少一第一型态条目；

动态地设定至少一可组态条目以作为具有第二数据结构的至少一第二型态条目，其中该第二数据结构不同于该第一数据结构；

其中该至少一第一型态条目以及该至少一第二型态条目系用以储存存在于该多处理器系统的快取中的快取列的状态。

24.一种用于多处理器系统的一探听过滤方法，包含:

在储存装置中记录多个条目，其中该多个条目系用以记录存在于该多处理器系统的快取中的快取列的状态，且该多个条目包含至少一第一条目以及第二条目，其中根据第一条目将该第一条目储存至该储存装置，根据第二条目配置将该第二条目储存至该储存装置，且该第一条目配置以及该第二条目配置具有相同或不同的条目配置方式。

说明书

用于多处理器系统的探听过滤器以及相关探听过滤方法

技术领域

[0001] 本发明有关于多处理器系统，尤指用于多处理器系统的探听过滤器以及相关探听过滤方法。

背景技术

[0002] 由于计算性能的需求，近年来多处理器系统愈受欢迎。一般来说，多处理器系统中的每一处理器具有其专属的快取以改良存取存储器的存取效率，为了让多个处理器共享存储器空间，可在该多处理器系统中实现快取一致互联(cache coherency interconnect)以管理不同处理器专属的快取之间的缓存一致性。而基于缓存一致性的窥探是一致互联中广泛使用的机制，举例来说，若快取未命中(cache miss)发生在快取中，窥探机制将窥探其他快取以确认其是否拥有所需要的快取列(cache line)。然而，大部分的应用皆无共享数据，亦即，大部分的窥探是不必要的，而不必要的窥探将会干扰被窥探的快取的操作，进而导致整体系统效能的降低。另外，不必要的窥探将导致额外的功率消耗。

[0003] 为了避免不必要的窥探，可在快取一致互联中采用一探听过滤器，举例来说，可使用传统的目录式(directory-based)探听过滤器以维持所共享的存储器快取的所有快取列的目录。换句话说，通过询问该探听过滤器，不必要的窥探操作将会被过滤，因此可改善系统性能并且减少功率消耗。然而，传统的目录式探听过滤器需要大尺寸的存储器来记录在共享存储器快取中的所有快取列，此将造成更高的制造成本。因此，需要设计一种不需要如此大尺寸之存储器的新式探听过滤器来降低制造成本。

发明内容

[0004] 本发明的目的之一在于提供用于多处理器系统的探听过滤器以及相关探听过滤方法。

[0005] 根据本发明的第一观点，揭露多处理器系统的探听过滤器。该探听过滤器包含储存装置以及控制电路。该控制电路系用以管理储存在该储存装置中的至少一第一型态条目以及至少一第二型态条目。其中，该第一型态条目记录用以指示该多处理器系统的第一快取以及第一需求存储器地址的信息，其中该第一需求存储器地址对应多个第一快取列，且每一快取列仅存在于该第一快取中；且该第二型态条目记录用以指示该多处理器系统的多个第二快取以及至少一第二需求存储器地址的信息，其中该至少第二需求存储器地址对应第二快取列，且该第二快取列存在于该多个第二快取中。

[0006] 根据本发明的第二观点，揭露多处理器系统的探听过滤器。其中，该探听过滤器包含储存装置以及控制电路。该储存装置包含多个可组态条目。该控制电路系用以可动态地将至少一可组态条目(如具有一第一数据结构的至少一第一型态条目)进行设定并且可动态地将至少一可组态条目(如具有第二数据结构的至少一第二型态条目)进行设定。其中，该第二数据结构不同于该第一数据结构，且该至少一第一型态条目与该至少一第二型态条目用以记录在该多处理器系统的快取中所存有的快取列的状态。

[0007] 根据本发明的第三观点，揭露多处理器系统的探听过滤器，其中该探听过滤器包含储存装置以及控制电路。该控制电路系用以管理储存在该储存装置中的多个条目。该多个条目系用以记录在该多处理器系统的多个快取中所存有的多个快取列的状态，且该多个条目包含至少一第一条目以及第二条目。该第一条目根据第一条目配置储存在该储存装置中，该第二条目根据第二条目配置储存在该储存装置中。且该第一条目配置以及该第二条目配置具有相同或不同的条目配置方式。

[0008] 根据本发明的第四观点，揭露应用于多处理器系统的探听过滤方法，其中该探听过滤方法包含:在储存装置中记录至少一第一型态条目，其中该第一型态条目记录用以指示该多处理器系统的第一快取以及第一需求存储器地址的信息，其中该第一需求存储器地址对应多个第一快取列，且每一快取列仅存在于该第一快取中；以及在该储存装置中记录至少一第二型态条目，其中该第二型态条目记录用以指示该多处理器系统的多个第二快取以及至少一第二需求存储器地址的信息，其中该至少第二需求存储器地址对应第二快取列，且该第二快取列存在于该多个第二快取中。

[0009] 根据本发明的第五观点，揭露应用于多处理器系统的探听过滤方法，其中该探听过滤方法包含:利用包含多个可组态条目的储存装置；可动态地将至少一可组态条目(如具有第一数据结构的至少一第一型态条目)进行设定；以及可动态地将至少一可组态条目(如具有第二数据结构的至少一第二型态条目)进行设定，其中该第二数据结构不同于该第一数据结构。该至少一第一型态条目与该至少一第二型态条目系用以记录在该多处理器系统的快取中所存有的快取列的状态。

[0010] 据本发明的第六观点，揭露应用于多处理器系统的一探听过滤方法，其中该探听过滤方法包含:在储存装置中记录多个条目，其中该多个条目系用以记录在该多处理器系统的多个快取中所存有的多个快取列的状态。该多个条目包含至少一第一条目以及第二条目。其中该第一条目根据第一条目配置储存在该储存装置中，该第二条目根据第二条目配置储存在该储存装置中，且该第一条目配置以及该第二条目配置具有相同或不同的条目配置方式。

附图说明

[0011] 图1是根据本发明实施例的多处理器系统的示意图。

[0012] 图2是根据本发明实施例的第一型态条目(如独有表项目)的第一数据结构的示意图。

[0013] 图3是根据本发明实施例的第二型态条目(如共有表项目)的第二数据结构的示意图。

[0014] 图4是由探听过滤器所管理的第一型态条目以及第二型态条目的范例示意图。

[0015] 图5是根据本发明实施例的具有可组态条目的储存装置的示意图。

[0016] 图6是根据本发明一实施例的与该独有表项目以及该共有表项目相关的需求存储器地址的地址分割示意图。

[0017] 图7是根据本发明一实施例的独有表项目的八路集合关系型条目配置以及共有表项目的四路集合关系型条目配置的示意图。

[0018] 图8是根据本发明一实施例的独有表项目的四路集合关系型条目配置以及共有表项目的四路集合关系型条目配置的示意图。

[0019] 图9-13为创造并更新第一型态条目以及第二型态条目的范例示意图。

[0020] 图14是根据本发明一实施例的在多处理器系统的正常操作中动态地创造并更新第一型态条目以及第二型态条目的流程图。

[0021] 图15是根据本发明具有至少两个子储存装置的储存装置示意图。

具体实施方式

[0022] 在说明书及后续的权利要求当中使用了某些词汇来指称特定的组件。所属领域中具有通常知识者应可理解，硬件制造商可能会用不同的名词来称呼同一个组件。本说明书及后续的权利要求并不以名称的差异来作为区分组件的方式，而是以组件在功能上的差异来作为区分的准则。在通篇说明书及后续的请求项当中所提及的「包含」为开放式的用语，故应解释成「包含但不限定于」。此外，「耦接」一词在此包含任何直接及间接的电气连接手段，因此，若文中描述第一装置耦接于第二装置，则代表该第一装置可直接电气连接于该第二装置，或者透过其他装置或连接手段间接地电气连接至该第二装置。

[0023] 图1是根据本发明实施例的多处理器系统的示意图。多处理器系统100可实现于携带式装置如移动电话、平板计算机、穿戴式装置之中。然而，此并非本发明的限制，亦即，任何使用本发明所提出的探听过滤器(snoop filter)的电子装置皆应隶属于本发明的范畴。在此实施例中，多处理器系统100可具有多个集群(cluster)112_1-112_N，其中N为一正整数且可根据实际设计考虑调整。亦即，本发明并不限制多处理器系统100中集群的数量。

[0024] 针对集群112_1-112_N，每一集群可为一组处理器(或称为处理器核心)。举例来说，集群112_1可包含一个或多个处理器117，而集群112_N可包含一个或多个处理器118。需注意的是，集群112_1-112_N中的处理器数量可根据实际设计考虑作调整。举例来说，集群112_1中的处理器核心117的数量可能与集群112_N中的处理器核心118的数量相同或不同。

[0025] 集群112_1-112_N可能具有其专属快取。在此实施例中，每一集群可配置专属快取(例如，L2快取)。如图1所示，多处理器系统100可具有多个快取114_1-114_N。因此，集群112_1可使用快取114_1，而集群112_N可使用另一快取114_N。除此之外，可使用快取一致互联116来个别管理集群112_1-112_N所存取的快取114_1-114_N的一致性。如图1所示，集群
112_1-112_N中的处理器117与118共享主存储器119，其中主存储器119透过快取一致互联
116耦接至快取114_1-114_N。被指派给特定集群的特定快取中的一快取列(cache line)可根据需求存储器地址被存取，其中该需求存储器地址包含在由该特定集群的处理器所发出的读取/写入要求中。当该特定快取发生快取未命中时，可自其他快取中或自主存储器119中取回该需求数据。举例来说，若该需求数据存在于另一快取中，可自该另一快取读取该需求数据并储存进该特定快取中。以另一例子而言，若该需求数据不存在于其他快取中，则自主存储器119中读取该需求数据并储存进该特定快取中。当该特定快取发生快取命中(cache hit)时，可自该特定快取中取回该需求数据。亦即，当该特定快取发生快取命中时，其代表该需求数据存在于该特定快取中，因此不需存取主存储器119以及其他快取。

[0026] 窥探(snooping)是个别快取侦测是否具有该需求数据的过程。然而，如上所述，由于其他快取通常不具有该需求快取列，因此大多数的窥探为非必要的。在此实施例中，快取一致互联116包含探听过滤器120，并通过过滤不需要的窥探操作以节省快取一致传输量。探听过滤器120包含控制电路122以及储存装置124。举例来说，储存装置124可利用内部存储器(如一静态随机存取存储器(static random access memory,SRAM))来实现。控制电路
122则系用以管理储存在储存装置124中的一个或多个第一型态条目(entry)(例如，独有表项目(unique table entries))E1以及一个或多个第二型态条目(例如，共有表项目(shared table entries))E2。第一型态条目E1记录用以指示多处理器系统100的第一快取以及第一需求存储器(requested memory)地址的信息。其中，该第一需求存储器地址对应多个第一快取列，且每一快取列仅存在于该第一快取中。该第二型态条目E2记录用以指示多处理器系统100的多个第二快取以及至少一第二需求存储器地址的信息。其中，该至少第二需求存储器地址对应第二快取列，且该第二快取列存在于该多个第二快取中。

[0027] 许多程序具有局部性，因此，程序所需求的数据通常储存在连续的存储器地址中。除此之外，大部分的快取列是具有独特性的。因此，程序所需求的数据通常仅缓存在单一快取中。根据这些观察，本发明提出具有第一数据结构的第一型态条目(如独有表项目)E1以及具有第二数据结构的第二型态条目(如共有表项目)。其中，该第二数据结构不同于该第一数据结构。该第一数据结构适用于记录仅位于快取中的快取列的存在信息，该第二数据结构适用于记录位于多个快取中的快取列的存在信息。搭配第一型态条目E1及/或第二型态条目E2的使用，探听过滤器120可为一目录式探听过滤器，其中该目录式探听过滤器具有较传统目录式探听过滤器更为紧密的(compact)目录。关于第一型态条目E1及第二型态条目E2的进一步说明如下所述。

[0028] 图2是根据本发明实施例的第一型态条目(如独有表项目)E1的第一数据结构的示意图。如图2所示，第一型态条目E1包含地址栏(address field)202、向量栏(vector field)204以及快取标示栏(cache index field)206。其中，地址栏202用以储存K个存储器地址的共同部分(common part)(标记为“K列对齐地址”(K-line aligned addr))，其中K为大于1的正整数。举例来说，K个存储器地址中的每一地址包含最高有效位(Most Significant Bit,MSB)、中央有效位(Central Significant Bit,CSB)以及最低有效位(Least Significant Bit,LSB)。在设计中，K个存储器地址可以为连续的存储器地址。举例来说，该K个存储器地址的最高有效位部分都相同、该K存储器地址的中央有效位部分都相同、但该K存储器地址的最低有效位部分则不相同。因此，地址栏202可用以储存于连续的存储器地址中相同的最高有效位部分以及相同的中央有效位部分。然而，此仅为范例说明，并非本发明的限制。在另一实施例中，K个存储器地址可为均匀分布的不连续存储器地址。举例来说，该K个存储器地址的最高有效位部分都相同、中央有效位部分不相同、最低有效位部分都相同。因此，地址栏202可用以储存于不连续的存储器地址中相同的最高有效位部分以及相同的最低有效位部分。在另一实施例中，该K个存储器地址的最高有效位部分不相同、中央有效位部分都相同、最低有效位部分都相同。因此，地址栏202可用以储存于不连续的存储器地址中相同的中央有效位部分以及相同的最低有效位部分。

[0029] 向量栏204用以储存K个指示位A1-AK，其中K个指示位A1-AK用以分别指示在相同快取中K个快取列的存在与否。快取标示栏206用以储存数值Cn，且此数值Cn用以指示具有该K个快取列的该快取。举例来说，当Ai＝1(其中i在{1,K}的范围中)且Cn＝j(其中j在{1,N}的范围中)时，即代表在该K个存储器地址中与第i个存储器地址相关的快取列存在，且其存在于N个快取114_1-114_N里的第j个快取中。

[0030] 举例来说，但非本发明的限制，K可为4。因此，储存在储存装置124中的每一个第一型态条目E1皆可记录指示出对单一快取而言，最多4个特殊的快取列的信息。然而，此并非本发明的限制。在实作上，K的值可以根据实际设计考虑作调整。

[0031] 图3是根据本发明实施例的第二型态条目(如共有表项目)的第二数据结构的示意图。如图3所示，第二型态条目E2包含地址栏302以及多个向量栏304_1-304-M，其中M为正整数且可等于或大于1。地址栏302用以储存M个存储器地址的共同部分(标记为”M列对齐地址”)。举例来说，M个存储器地址中的每一地址包含最高有效位、中央有效位以及最低有效位。在设计中，M个存储器地址可以为连续的存储器地址。举例来说，该M个存储器地址的最高有效位部分都相同、该M个存储器地址的中央有效位部分都相同、但该M个存储器地址的最低有效位部分则不相同。因此，地址栏302可用以储存于连续的存储器地址中相同的最高有效位部分以及相同的中央有效位部分。，然而，此仅为范例说明，并非本发明的限制。在另一实施例中，M个存储器地址可为均匀分布的不连续存储器地址。举例来说，该M个存储器地址的最高有效位部分都相同、中央有效位部分不相同、最低有效位部分都相同。因此，地址栏302可用以储存于不连续的存储器地址中相同的最高有效位部分以及相同的最低有效位部分。在另一实施例中，该M个存储器地址的最高有效位部分不相同、中央有效位部分都相同、最低有效位部分都相同。因此，地址栏302可用以储存于不连续的存储器地址中相同的中央有效位部分以及相同的最低有效位部分。

[0032] M个向量栏304_1-304_M分别对应至M个存储器地址。M个向量栏304_1-304_M中的每一向量栏皆包含分别用以指示N个快取114_1-114_N中的相同快取列之存在的N个指示位B1-BN。举例来说，当向量栏304_j(其中j在{1,M}的范围中)的指示位Bi＝1(其中i在{1,N}的范围中)时，其代表与M个存储器地址中的第j个存储器地址相关的一快取列存在于N个快取114_1-114_N里的第i个快取中。

[0033] 举例来说，但非本发明的限制，M可为2。因此，储存在储存装置124中的每一个第二型态条目E2皆可记录最多指示出2个快取列的信息，其中所记录的每一快取列皆由多个快取所共享。然而，此并非本发明的限制。在实作上，M的值可以根据实际设计考虑作调整。举例来说，K的值可能与M的值相同或不同。需注意的是，每一快取列(不管是特殊快取列或共享快取列)的存在状态，仅会存在于该独有表及该共有表中的其中之一。

[0034] 图4示范一实施例以更好理解本发明所提出的第一型态条目(如独有表项目)E1以及第二型态条目(如共有表项目)E2的技术特征。在此实施例中，假设N＝4、K＝4以及M＝2。因此，多处理器系统可设定为包含4个快取Cache1-Cache4，且此4个快取Cache1-Cache4分别指派给4个处理器CPU1-CPU4。如图4所示，第一处理器CPU1已发出包含需求存储器地址
9000与9001的读取/写入要求，第二处理器CPU2已发出包含需求存储器地址8000、8001、
8002与9000的读取/写入要求，第三处理器CPU3已发出包含需求存储器地址7000、7002、
7003、9001的读取/写入要求，且第四处理器CPU4已发出包含需求存储器地址A000、A0003的读取/写入要求。此时，探听过滤器(如探听过滤器120)具有独有表以及共有表，其中该独有表具有三个第一型态条目而该共有表具有第二型态条目。

[0035] 如图4所示，需求存储器地址8000、8001(即8000+1)以及8002(即8000+2)分别仅存在于第二快取Cache2中。因此，第一型态条目的地址栏被设定为共同的地址值(common address value)”8000”、其向量栏被设定为位串(bit string)”1110”以及其快取标示栏被设定为代表第二快取Cache2的”C2”。需求存储器地址7000、7002(即7000+2)以及7003(即7000+3)仅存在于第三快取Cache3中。因此，另一第一型态条目的地址栏被设定为共同的地址值”7000”、其向量栏被设定为位串”1011”以及其快取标示栏被设定为代表第三快取Cache3的”C3”。此外，需求存储器地址A000以及A003(即A000+3)仅存在于第四快取Cache4中。因此，其余的第一型态条目的地址栏被设定为共同的地址值”A000”、向量栏被设定为位串”1001”以及快取标示栏被设定为代表第四快取Cache4的”C4”。

[0036] 如图4所示，需求存储器地址9000同时存在于第一快取Cache1以及第二快取Cache2中，且需求存储器地址9001(即9000+1)与同时存在于第一快取Cache1以及第三快取Cache3中的相同快取列相关。因此，该第二型态条目的一地址栏被设定为共同的地址值”9000”、与需求存储器地址9000相关的一共享快取列的一第一向量栏被设定为位串”1100”，以及与需求存储器地址9001相关的另一共享快取列的一第二向量栏被设定为位串”1010”。

[0037] 如上所述，第一型态条目E1所使用的该第一数据结构不同于第二型态条目E2所使用的第二数据结构。在一实施例中，该独有表的尺寸以及该共有表的尺寸可在设计时即被固定。若应用包含大量的共享快取列，则最糟的情况为该共有表是满的而该独有表是空的。若应用包含大量的特殊快取列，则最糟的情况为该独有表示满的而该共有表是空的。因此，该固定尺寸的独有表以及该固定尺寸的共有表的设定可能仅仅适用于某些应用。因而造成此类使用固定尺寸的独有表以及固定尺寸的共有表的探听过滤器在使用上较无弹性。因此，本发明另外提出使用具有可组态条目的整合型(unified)存储器的探听过滤器设计。

[0038] 若记录在第一型态条目E1中的特殊快取列的最大数量等同于记录在第二型态条目E2的共享快取列的最大数量(即K＝M)，则第一型态条目E1中的地址栏的位长度等于第二型态条目E2中的地址栏的位长度。若记录在第一型态条目E1中的特殊快取列的最大数量与记录在第二型态条目E2中的共享快取列的最大数量仅有些许不同(即K≠M)，则第一型态条目E1中的地址栏的位长度与第二型态条目E2中的地址栏的位长度亦只有些许不同。举例来说，假设快取列的尺寸为64字节(byte)、使用的是32位的地址空间、记录在第一型态条目E1中的4列对齐地址需要24位，记录在第二型态条目E2中的2列对齐地址则需要25位。根据以上观察，本发明提出供该独有表以及该共有表的一整合型存储器来实现储存装置124，藉此增加探听过滤器120的弹性。

[0039] 图5是根据本发明一实施例的具有可组态条目的储存装置的示意图。在一实施例中，可使用图5所示的储存装置500实现图1所示的储存装置124。在储存装置500中设置有多个可组态条目，其中每一可组态条目具有相同的位长度BL。当多处理器系统100正常启动时，可动态地设定每一可组态条目为第一型态条目(如独有表项目)E1或是第二型态条目(如共有表项目)E2。因此，可以在多处理器系统100正常操作的过程中动态地调整该独有表的尺寸以及该共有表的尺寸，藉此可适用更广泛的应用。

[0040] 如图5所示，可组态条目502可作为第一型态条目E1，而可组态条目504可作为第二型态条目E2。除了上述提及的地址栏、向量栏以及快取标示栏，额外的位S被包含在第一型态条目E1的该第一数据结构中，此额外的位S用以说明可组态条目502的型态。同样地，除了上述提及的地址栏以及向量栏，额外的位S被包含在第二型态条目E2的该第二数据结构中，此额外的位S用以说明可组态条目504的型态。举例来说，当可组态条目被设定为独有表项目时，位于可组态条目的最后的额外位S则被设定为”0”；而当该可组态条目被设定为共有表项目时，位于该可组态条目的最后的该额外位S则被设定为”1”。然而，此仅为范例说明，并非本发明的限制。

[0041] 由于每一可组态条目具有相同的位长度，并且第一型态条目E1所使用的该第一数据结构不同于第二型态条目E2所使用的该第二数据结构，因此在一可组态条目中可能有一个或多个被设定为第一型态条目E1(若K>M)或被设定为第二型态条目E2(若K

[0042] 在图5所示的实施例中，独有表以及一共有表可用相同位长度储存在具有表项目的相同储存装置中。然而，此仅为范例说明，并非本发明的限制。图15是根据本发明具有至少两个子储存装置的储存装置示意图。在另一实施例中，可使用图15的储存装置1500实现图1所示的储存装置124。其中，储存装置1500可包含至少两个子储存装置1512与1514。子储存装置1512存有具第一位长度BL1的条目1502，子储存装置1512存有具第二位长度BL2的条目1504。根据实际设计考虑，第二位长度BL2可与第一位长度BL1相同或相异。在图15所示的实施例中，第一位长度BL1大于第二位长度BL2。然而，第一位长度BL1亦可小于或等于第二位长度BL2。在子储存装置1512中的每一条目1502可为一第一型态条目(独有表项目)E1，而在子储存装置1514中的每一条目1504可为一第二型态条目(共有表项目)E2。换句话说，一独有表仅被创建并仅储存于子储存装置1512中，且一共有表仅被创建并储存于子储存装置1514中。简单来说，该独有表或该共有表可使用相同位长度或不同的位长度的表项目，分别储存在不同的子储存装置，此变化应同样隶属于本发明的范畴。

[0043] 探听过滤器120的控制电路122系用以管理储存在探听过滤器120的储存装置124中的多个条目，该多个条目包含一个或多个的第一型态条目E1及/或一个或多个的第二型态条目E2。其中，该多个条目系用以记录存在于多处理器系统100的快取114_1-114_N中的快取列的状态。在实施例中，第一条目(例如，第一型态条目E1)可根据具有第一关联性(associativity)的第一条目配置(entry placement)以储存在储存装置124中，而第二条目(如第二型态条目)可根据具有第二关联性的第二条目配置以储存在相同的储存装置124中。该第一条目配置以及该第二条目配置可拥有相同或不同的关联性。亦即，根据实际设计考虑，该第一关联性可能等同或不同于该第二关联性。举例来说，第一型态条目E1可根据直接对映条目配置(direct-mapped entry placement)、集合关系型条目配置(set associative entry placement)以及完全关系型条目配置(fully associative entry placement)中的其中之一储存在储存装置124中。以另一例子而言，第二型态条目E2可根据直接对映条目配置(direct-mapped entry placement)、集合关系型条目配置(set associative entry placement)以及完全关系型条目配置(fully associative entry placement)中的其中之一储存在储存装置124中。详细来说，控制电路122可于储存装置124中使用相同快取关联性的概念，以储存及存取第一型态条目E1与第二型态条目E2。在快取关联性设计领域中具有通常知识者应能理解”直接对映(关联性＝1)”、”集合关系型(关联性＝n)”以及”完全关系型(关联性＝表项目的编号)”等关联性种类，进一步解释在此省略以省篇幅。

[0044] 图6是根据本发明实施例的与该独有表项目以及该共有表项目相关的需求存储器地址的地址分割示意图。在本实施例中，假设K＝4，M＝2，快取列的尺寸为64字节并且使用32位的地址空间。当该独有表以及该共有表使用完全关系型条目配置时，利用32位的需求存储器地址的第8-31位为卷标(tag)并储存于第一型态条目(独有表项目)的地址栏，而第
0-7位作为4个64字节快取列的区块偏移(block offset)；利用32位的需求存储器地址的第
7-31位为卷标并储存于第二型态条目(共有表项目)的地址栏，而第0-6位作为2个64字节快取列的区块偏移。当该独有表以及该共有表使用集何关系型条目配置时，如图6所示，利用
32位的需求存储器地址的第21-31位为卷标并储存于第一型态条目(独有表项目)的地址栏，而该相同的32位需求存储器地址的第8-20位作为标示值，且第0-7位做为4个64字节快取列的区块偏移；利用32位的需求存储器地址的第21-31位为卷标并储存于第二型态条目(共有表项目)的地址栏，而该相同的32位需求存储器地址的第8-20位作为标示值，该相同的32位需求存储器地址的第7位作为另一标示值(标记为index2)，且第0-6位作为两个64字节快取列的区块偏移。该标示值可被用以定位(locate)储存装置124中表项目的集合，而该卷标可被用以确认是否命中该集合中的一表项目。

[0045] 图7是根据本发明实施例的用于独有表项目的八路(8-way)集合关系型条目配置以及用于共有表项目的四路(4-way)集合关系型条目配置的示意图。八个独有表项目(如Way0-Way7)可属于由标示值Bit[20:8]所标示的相同集合，并将卷标值Bit[31:21]与储存在独有表项目(如Way0-Way7)的地址栏的地址值做比较，以确认是否命中独有表项目(如Way0-Way7)中的任何项目。除此之外，四个共有表项目(如Way0-Way3或Way4-Way7)可属于由标示值Bit[20:8]以及Bit[7]所标示的相同集合，并将卷标值Bit[31:21]与储存在共有表项目(如Way0-Way3或Way4-Way7)的地址栏的地址值做比较，以确认是否命中共有表项目(如Way0-Way3或Way4-Way7)中的任何项目。

[0046] 需注意的是，根据实际设计考虑，在相同的储存装置124中的该独有表以及该共有表可使用相同或不同的关联性。举例来说，图8绘示根据本发明在K＝M的实施例中，用于该独有表项目的四路集合关系型条目配置以及用于该共有表项目的四路集合关系型条目配置。

[0047] 另外，可在多处理器系统100正常操作下，动态地创建与更新第一型态条目E1以及第二型态条目E2。参考第9-13图，其绘示创建与更新第一型态条目E1以及第二型态条目E2的实施例。假设N＝4、K＝4以及M＝2，多处理器系统可包含4个快取Cache1-Cache4，此4个快取Cache1-Cache4分别配置予4个处理器CPU1-CPU4。此外，采用所提出的整合型存储器。因此，可使用该整合型存储器以储存多个可组态条目，每一可组态条目具有相同位长度。开始时，并无任何读取/写入要求由处理器CPU1-CPU4发出。因此，在图9所示的初始状态，快取Cache1-Cache4并未储存任何快取列，且该整合型存储器并未储存第一型态条目E1以及第二型态条目E2。为清楚说明，图9绘示透过设定该整合型存储器中的可组态条目来设定的第一型态条目E1的该第一数据结构以及透过设定该整合型存储器中的可组态条目来设定的第二型态条目E2的该第二数据结构。

[0048] 如图10所示，第一处理器CPU1发出包含需求存储器地址9000的读取/写入要求，第二处理器CPU2发出包含需求存储器地址8000的读取/写入要求，第三处理器CPU3发出包含需求存储器地址7000的读取/写入要求，以及第四处理器CPU4发出包含需求存储器地址A000的读取/写入要求。该需求存储器地址9000与仅存在于第一快取Cache1中的快取列相关，该需求存储器地址8000与仅存在于第二快取Cache2中的快取列相关，该需求存储器地址7000与仅存在于第三快取Cache3中的快取列相关，并且该需求存储器地址A000与仅存在于第四快取Cache4中的快取列相关。因此，第一可组态条目(其为在该整合型存储器中所找到的一新的可组态条目)被设为第一型态条目，其地址栏被设定为具有共同地址值”9000”，其向量栏被设定为位串(bit string)”1000”且其快取标示栏被设定为代表第一快取Cache1的”C1”；第二可组态条目(其为在该整合型存储器中所找到的一新的可组态条目)被设为第一型态条目，其地址栏被设定为共同的地址值”8000”，其向量栏被设定为位串”1000”且其快取标示栏被设定为代表第二快取Cache2”C2”；第三可组态条目(其为在该整合型存储器中所找到的新的可组态条目)被设为第一型态条目，其地址栏被设定为共同的地址值”7000”，其向量栏被设定为位串”1000”且其快取标示栏被设定为代表第三快取Cache3的”C3”；以及第四可组态条目(其为在该整合型存储器中所找到的一新的可组态条目)被设为第一型态条目，其地址栏被设定为共同的地址值”A000”，其向量栏被设定为位串”1000”且其快取标示栏被设定为代表第四快取Cache4的”C4”。

[0049] 如图11所示，第一处理器CPU1另发出包含需求存储器地址9001(即9000+1)的读取/写入要求，第二处理器CPU2另发出包含求存储器地址8001(即8000+1)以及8002(即8000+2)的两个读取/写入要求，第三处理器CPU3另发出包含求存储器地址7002(即7000+2)以及7003(即7000+3)的两个读取/写入要求，以及第四处理器CPU4另发出包含求存储器地址A003(即A000+3)的读取/写入要求。需求存储器地址9000以及9001与仅存在于第一快取Cache1中的快取列相关，需求存储器地址8000、8001以及8002与仅存在于第二快取Cache2中的快取列相关，需求存储器地址7000、7002以及7003与仅存在于第三快取Cache3中的快取列相关，而需求存储器地址A000以及A003与仅存在于第四快取Cache4中的快取列相关。
因此，将该第一可组态条目(其被设定为第一快取Cache1的一第一型态条目)中所设定的向量栏更新以储存一位串”1100”、将该第二可组态条目(其被设定为第二快取Cache2的一第一型态条目)中所设定的向量栏更新以储存位串”1110”、将该第三可组态条目(其被设定为第三快取Cache3的第一型态条目)中所设定的向量栏更新以储存位串”1011”以及将该第四可组态条目(其被设定为第四快取Cache4的第一型态条目)中所设定的向量栏更新以储存位串”1001”。

[0050] 如图12所示，第二处理器CPU2另发出包含需求存储器地址9000的读取/写入要求，其中该需求存储器地址9000与存在于第一快取Cache1以及第二快取Cache2中的相同快取列相关。在此实施例中，在该探听过滤器的该控制单元可将该第一可组态条目(其被设定为第一快取Cache1的第一型态条目)转换(transfer)至另一可组态条目(其为在该整合型存储器中所找到的一新的可组态条目并且被设定做为两个快取列的第二型态条目)。如图12所示，移除该第一可组态条目，并选择且设定第五可组态条目，其地址栏被设定为共同地址值”9000”、其第一向量栏被设定为与需求存储器地址9000的快取列相关的位串”1100”，且其第二向量栏被设定为与需求存储器地址9001的另一快取列相关的位串”1000”的另一快取列的第二向量栏。

[0051] 如图13所示，第三处理器CPU3另外发出包含需求存储器地址9001的读取/写入要求。其中，该需求存储器地址9001与存在于第一快取Cache1以及第三快取Cache3中的相同快取列相关。在此实施例中，更新该第五可组态条目(其被设定为两个需求存储器地址的第二型态条目)的该第二向量栏以储存一位串”1010”。

[0052] 在探听过滤器120的储存装置124中动态地创建并更新第一型态条目E1以及第二型态条目E2的操作系由探听过滤器120的控制电路122所控制。举例来说，可使用图14所示的控制流程以在多处理器系统100的正常操作中动态地创建并更新第一型态条目E1以及第二型态条目E2。针对由具有一快取(X)的一处理器所发出的需求存储器地址(A)，可确认在一个或多个独有表项目中的该地址栏(对齐地址)、向量栏(A1-Ak)以及快取标示栏(Cn)，及/或可确认在一个或多个共有表项目中的该地址栏(对齐地址)、向量栏(B1-Bn)，因此，该控制电路可参考一确认结果以寻找并使用一新的独有表项目、更新一已存在的独有表项目、寻找并使用一新的共有表项目或更新一已存在的共有表项目。需注意的是图14所示的步骤仅为范例说明，并非本发明的一限制，在实作中，可以使用不同的控制流程以在多处理器系统100的正常操作中动态地产生并更新第一型态条目E1以及第二型态条目E2。

[0053] 当满足第一转换条件(transition condition)时，可通过控制探听过滤器120的控制电路122来执行第一过渡操作，以转换已存在的第一型态条目的至少一部份(即部分或全部)至储存装置124中的至少一新的第二型态条目。举例来说，若创建第一型态条目以储存指出相同快取的多个快取列以及包含在将会成为存在于多个快取中的共享快取列的快取列中的一个或多个特定快取列的信息，控制电路122可在未移除该第一型态条目的情况下自该第一型态条目转换该特定快取列的存在信息至至少一新的第二型态条目，并可据此相应更新该第一型态条目的该向量栏。在另一实施例中，若创建一第一型态条目以记录指出相同快取的多个快取列以及包含在将会成为存在于多个快取中的共享快取列的快取列中的一个或多个特定快取列的信息，控制电路122可自该第一型态条目转换所有快取列的存在信息至至少一新的第二型态条目，并可移除该第一型态条目。

[0054] 当满足第二转换条件时，可通过控制探听过滤器120的控制电路122来执行第二过渡操作以转换已存在的第二型态条目的至少一部份(即部分或全部)至储存装置124中的至少一新的第一型态条目。举例来说，若创建第二型态条目以记录指出存在于多个快取中的至少一快取列且包含在将会成为存在于单一个快取中的特殊快取列的至少一快取列中的一个或多个特定快取列的信息，控制电路122可在未移除该第二型态条目的情况下自该第二型态条目转换该特定快取列的存在信息至至少一新的第一型态条目，并可据此相应更新该第二型态条目的向量栏。在另一实施例中，若产生第二型态条目以记录指出存在于多个快取中的至少一快取列以及包含在将会成为存在于单一个快取中的特殊快取列的至少一快取列中的一个或多个特定快取列的信息，控制电路122可自该第二型态条目转换该至少一快取的所有快取的存在信息至至少一新的第一型态条目并可移除该第二型态条目。

[0055] 以上所述仅为本发明之较佳实施例，凡依本发明权利要求所做之均等变化与修饰，皆应属本发明之涵盖范围。