CN1928841B - 高速缓冲存储器分析方法 - Google Patents

Abstract

所作的是从高速缓冲存储器中读取包含产生高速缓存未中的存储器地址的信息。对该信息中包含的每个高速缓存未中产生地址处所产生的高速缓存未中数进行总计。所产生的高速缓存未中数被总计的高速缓存未中产生地址按照每一集合分段。进一步，将所产生的高速缓存未中数一致或接近的地址组从被分为同一集合中的地址的多个高速缓存未中产生地址中提取出来。

Description

高速缓冲存储器分析方法

技术领域

本发明涉及一种高速缓冲存储器分析方法，该方法用于检测由于载有高速缓冲存储器的处理器中或仿真该处理器的仿真信息处理装置和类似装置中的存储器存取冲突而产生的高速缓存未中。

背景技术

在诸如处理器或仿真信息处理装置(仿真器)之类的系统中，由于请求数据时高速缓存未中而产生的等待时间是最严重的瓶颈之一。于是，为了改善在处理器和信息处理装置上工作的嵌入式系统中的执行性能，如何减少高速缓存未中是重要的。为了有效地减少高速缓存未中，有必要在上述系统中指定对减少高速缓存未中高度有效的存储器存取数据。

惯常地，有一种公知的用于指定对减少高速缓存未中高度有效的存储器存取数据的方法(1)。它是这样一种方法，即，计算每一存储器的存取地址中所产生的高速缓存未中数，并且将高速缓存未中数最大的地址检测为对减少高速缓存未中高度有效的存储器存取数据。

图11示出检测方法(1)的一个例子。图11示出高速缓冲存储器的存取状态。存取状态示于图11中的高速缓冲存储器是双路集合关联系统(setassociative system)。在图11中，横轴为高速缓冲存储器存取时间的流逝(lapse)，竖轴表示在同一集合中各地址处的数据。“集合”表示一个索引(表目)，它用存储器存取地址的若干低位与存储器的其它区域相区别，“路”则表示在高速缓冲存储器中有多少个块(高速缓存块)用于存储数据。在图11中，从a到e共五个数据在集合0中存取，从α到γ共三个数据在集合1中存取。由于高速缓存未中数最大的地址被视为对减少高速缓存未中高度有效的存储器存取数据，所以在图11中，集合0中产生六次高速缓存未中的数据a被检测为对减少高速缓存未中高度有效的存储器存取数据。

此外，美国专利No.5930507公开了一种用于指定可能具有冲突的存储器存取数据的方法(2)。该方法采集编译处理装置中高速缓冲存储器上的存储器存取数据，并对数据间产生的冲突关系进行分析，其中编译处理装置在具有高速缓冲存储器的计算器的基础上工作。

在方法(1)中，计算高速缓存未中数最大的地址是就已经产生高速缓存未中的每一存储器的存取地址进行的，而没有考虑高速缓冲存储器的存取冲突。因此，可能检测不到对减少高速缓存未中高度有效的地址。“冲突”意味着此种状态的重复，即高速缓冲存储器同一集合中的不同地址之一从高速缓冲存储器中“踢开”另一地址，或者，一个被另一个从高速缓冲存储器中“赶走”。

上述麻烦将参考图12A和图12B加以描述。这些图示出如图11所示的高速缓冲存储器的存取状态。图12A示出通过改变地址排列或诸如此类的方法，减少了图11中集合0的数据“a”中的高速缓存未中。图12B示出通过改变地址排列或诸如此类的方法，减少了图11中集合1的数据α中的高速缓存未中。

如图12A所示，通过改变高速缓存未中数最大(六)的数据“a”的地址排列，高速缓存未中的总数可由30次降至22次。

但是如图12B所示，通过改变高速缓存未中五次的数据α的地址排列，高速缓存未中的总数可由30次降至15次。这是因为集合1中的存储器存取冲突通过改变数据“α”的地址排列得到消除，并且因为存储器的存取冲突在集合1中的三个数据“α”、“β”、“γ”中间产生，所以集合1中高速缓存未中数变成0。在这种情况下可以认为，高速缓存未中五次的数据“α”对减少高速缓存未中而言，效率高于高速缓存未中六次的数据a。与此相似，存在着这样一种情况，即，即使所产生的高速缓存未中数很小，但是减少高速缓存未中的效率也很高。

方法(2)公开了一种仅用于对排列元素分析高速缓冲存储器的存取冲突的方法，其中编译时循环处理中的地址可由编译器统计识别。然而，由于在这种方法中高速缓冲存储器的存取冲突是在编译时进行统计分析的，所以实际操作中高速缓冲存储器的存取状态不得而知。

发明内容

因此，本发明的主要目的是提供一种高速缓冲存储器分析方法，用于检测对减少高速缓存未中高度有效的存储器存取地址，同时通过在编译后的实际操作中采集高速缓存存取信息来限定高速缓冲存储器的存取状态。

为了实现上述目的，根据本发明的高速缓冲存储器分析方法是一种用于分析处理器中高速缓冲存储器的占用状态的方法，该处理器包括集合关联系统的高速缓冲存储器和用于对该高速缓冲存储器执行记录控制的CPU，该集合关联系统的高速缓冲存储器的每一集合都具有多个数据存储块，并且每一集合用存储器存取地址的较低位与存取器的其它区域相区别。该方法包括以下步骤：

读取步骤，用于从所述高速缓冲存储器中读取其中产生高速缓存未中的存储器地址上的记录信息；

总计步骤，用于对包含在所述信息中的每个高速缓存未中产生地址处所产生的高速存取未中数进行总计；

分段步骤，用于按照每一集合根据所产生的高速缓存未中数的总计将高速缓存未中产生地址进行分段；

提取步骤，用于从被分为同一集合地址的多个高速缓存未中产生地址中，提取所产生的高速缓存未中数一致或接近的地址组；

指定步骤，用于指定每一集合的数据存储块数以作为所述提取步骤的预处理，其中，

在所述提取步骤中，当有多个被分在同一集合中的地址组时，通过将高优先级赋予在从包含在每个地址组中的地址数减去所述数据存储块数等于1或小于1的地址组，将所述多个地址组分开。

据此，极为可能的是，存储器存取冲突发生在被分为处于同一集合(表目)中产生高速缓存未中的多个地址处所产生的高速缓存未中数彼此一致或接近的地址中。基于这一判断，具有相同或类似的高速缓存未中产生数的高速缓存未中产生地址被视为对减少高速缓存未中高度有效的高速缓存未中产生地址。

当在属于地址组的一个地址处所产生的高速缓存未中通过改变地址排列或诸如此类的方法加以解决时，有可能同时解决集合中其它地址处所产生的高速缓存未中。在这种情况下，可以认为在集合关联系统中，当具有存储器存取冲突的地址数与每一集合中数据存储块数之差等于或小于1时，很有可能同时解决其它地址处的高速缓存未中。上述过程正是基于这种观点考虑的。按此过程，具有存储器存取冲突的地址数与每一集合中数据存储块数之差等于或小于1的地址组可被指定为可最有效地减少高速缓存未中的地址组。此过程对具有每一集合的数据存储块数可以改变的高速缓冲存储器的处理器或处理器的仿真信息处理装置也是有效的。

在提取步骤中，优选：设置一阈值，作为所产生的若干高速缓存未中数之差的上限；基于所述差是否落在范围内，将已分段成同一集合中的地址的高速缓存未中产生地址分开；并将所述范围内的高速缓存未中产生地址视为所产生的高速缓存未中数接近的地址组。

根据上述过程，有可能通过判断在所产生的高速缓存未中数不但一致而且落在近似阈值内的高速缓存未中产生地址之间具有存储器存取冲突，来指定对减少高速缓存未中高度有效的高速缓存未中产生地址。此外，有可能通过改变阈值来调整所指定的高速缓存未中产生地址数。

进一步，在提取步骤中，优选当提取同一集合内的多个地址组时，通过将它们以包含在地址组中的地址数的顺序并行排列来将多个地址组分段。

当在属于该地址组的地址中的一个地址处所产生的高速缓存未中通过改变地址排列或诸如此类的方法解决时，有可能同时解决集合中其它地址处的高速缓存未中。在这种情况下，可以认为，包含在相关地址组中的地址数越小，解决在其它地址处所产生的高速缓存未中的可能性就越大。上述过程正是基于该观点考虑的。按此过程，有可能将包含最少地址数的地址组指定为最有效地减少高速缓存未中的地址组。

进一步，在提取步骤中，优选当提取同一集合中包含相同地址数的多个地址组时，通过将它们按对包含在相关地址组中的地址处所产生的相应高速缓存未中数进行总计时的总值的顺序并行排列，来将具有相同地址数的地址组分段。

据此，每一地址组总计的包含在地址组的地址处所产生的高速缓存未中的总数最大的地址组可以被指定为最有效地减少高速缓存未中的地址组，即使在同一集合中有多个地址组包含相同的地址数也是如此。

此外，优选进一步包括显示步骤，用于将通过提取步骤所提取的地址组的结果显示为分析结果，其中，

在显示步骤中，优选将在提取步骤中被视为具有最少地址数的地址组着重显示为可高度有效地减少高速缓存未中的地址组。

据此，可高度有效地减少高速缓存未中的存储器存取数据可直观地加以判断。

此外，在提取步骤中，如果从包含在每个地址组中的地址数中减去所述数据存储块数时，有多个地址组具有小于或等于1的值，那么优选通过对它们按对每个地址组在地址处所产生的高速缓存未中数进行总计时的总值的顺序并行排列来将多个地址组分段。

据此，每个地址组总计的包含地址组中的地址处所产生的高速缓存未中的总数最大的地址组可被指定为可最有效地减少高速缓存未中的地址组，即使当数据存储块数从包含在同一集合中的地址数中减去时，有多个地址组具有小于或等于1的值时也是如此。

此外，优选进一步包括显示步骤，用于将提取步骤中提取出的地址组的提取结果显示为分析结果，其中，

在显示步骤中，在提取步骤中被分类为具有高优先级的地址组被着重显示为可高度有效地减少高速缓存未中的地址组。

本发明提供一种用于分析处理器中高速缓冲存储器的占用状态的高速缓冲存储器分析装置，该处理器包括集合关联系统的高速缓冲存储器和CPU，所述集合关联系统的高速缓冲存储器的每一集合都具有多个数据存储块，并且每一集合用存储器存取地址的较低位与存储器的其它区域相区别，CPU则用于对所述高速缓冲存储器进行记录控制，该装置包括：

读取装置，用于从所述高速缓冲存储器中读取对其中产生高速缓存未中的存储器地址进行记录的信息；

总计装置，用于对包含在所述信息中的每个高速缓存未中产生地址处所产生的高速缓存未中数进行总计；

分段装置，用于按照每一集合根据其中所产生的高速缓存未中数的总计将高速缓存未中产生地址进行分段；

提取装置，用于从被分段成为同一集合地址的高速缓存未中产生地址中提取所产生的高速缓存未中数一致或接近的地址组；

指定装置，用于指定每一集合的数据存储块数以作为所述提取装置所执行的提取动作的预处理，其中，

当有多个被分在同一集合中的地址组时，所述提取装置通过将高优先级赋予在从包含在每个地址组中的地址数减去所述数据存储块数等于1或小于1的地址组，将所述多个地址组分开。

此外，根据本发明的处理器和仿真信息处理装置包括：CPU；多路集合关联系统的高速缓冲存储器和高速缓存未中地址输出单元，该高速缓存未中地址输出单元用于当CPU请求数据而没有数据时，将数据地址作为高速缓存未中地址输出至处理器外或输出至文件系统。据此，有可能当产生高速缓存未中时，从处理器和仿真信息处理装置获得高速缓存未中地址。

根据本发明，有可能仅基于编译后的实际操作中的高速缓存存取信息，指定具有存储器存取冲突的地址，并检测出可高度有效地减少高速缓存未中的存储器存取数据。

只要在产生高速缓存未中时可以获得地址，那么本发明的技术就可以检测出可高度有效地减少高速缓存未中的存储器存取数据。因此，它在开发软件时，通过减少高速缓存未中来提高处理性能和类似性能很有效。

附图说明

本发明的其它目的可以因以下对优选实施例和所附权利要求的描述而变得显而易见。本领域的技术人员应该意识到，通过实施本发明，本发明还可能有许多其它优点。

图1为用于示出根据本发明实施例的处理器结构的框图，该处理器能输出高速缓存未中地址；

图2为用于示出用于仿真根据本发明实施例的处理器的仿真信息处理装置结构的框图；

图3为用于示出根据本发明实施例计算用于减少高速缓存未中的索引的数据流的流程图；

图4为用于分析根据本发明实施例的高速缓冲存储器的占用状态的流程图；

图5为用于示出根据本发明实施例的地址提取过程细节的流程图；

图6为示出根据本发明实施例的对所提取的地址组进行显示处理的流程图，同时顾及到提取地址组中的地址数；

图7为示出根据本发明实施例的对所提取的地址组进行显示处理的流程图，同时顾及到提取地址组中的地址数；

图8为用于描述从本发明实施例的处理器/仿真信息处理装置输出的高速缓存存取信息的图示；

图9为用于描述按本发明实施例中所产生的高速缓存未中数的降序进行分段处理的结果图；

图10为用于描述根据本发明实施例的地址提取处理的结果图；

图11为用于描述相关技术的高速缓存未中的存取状态图；

图12A为用于描述有关技术中高速缓存未中数减少时的结果图；

图12B为用于描述有关技术中高速缓存未中数减少时的结果图。

具体实施方式

下文中将参考附图描述本发明的优选实施例。

(第一实施例)

图1为根据本发明实施例的处理器10及其输出具有高速缓存未中地址记录的高速缓存存取信息的系统的示意图。

在图1中，处理器10包括CPU 11、高速缓冲存储器12和高速缓存未中地址输出单元13。高速缓冲存储器12具有多路集合关联系统的结构。当在向高速缓冲存储器12请求数据时产生高速缓存未中时，高速缓存未中地址输出单元13将产生未中的数据的地址作为高速缓存未中地址输出到处理器外。通过具有上述结构，处理器10仅利用产生高速缓存未中的地址就能分析高速缓冲存储器的占用状态。

图2示出仿真图1所示结构的仿真信息处理装置20。仿真信息处理装置20包括CPU 21、高速缓冲存储器22和高速缓存未中地址输出单元23。CPU 21、高速缓冲存储器22和高速缓存未中地址输出单元23包括与CPU11、高速缓冲存储器12和高速缓存未中地址输出单元13相同的结构。由此，上述处理器10可用仿真信息处理装置20代替。

图3示出用于计算用于减少高速缓存未中的索引的数据流。所准备的源程序31由编译器32转化为执行程序33，随后安装到执行执行程序33的程序执行装置34上。

程序执行设备34连接到处理器35上。在执行执行程序33时，CPU向位于所连接的处理器35中的高速缓冲存储器请求数据。当在这种状态下产生高速缓存未中时，高速缓存未中地址输出单元将发生高速缓存未中的数据的地址作为高速缓存存取信息36输出到处理器外。

图8示出从处理器35输出的高速缓存存取信息36。从处理器35输出的高速缓存存取信息36由用于高速缓冲存储器的占用状态分析器37分析，该分析器对高速缓冲存储器的占用状态进行分析。用于高速缓冲存储器的占用状态分析器37提取一组可高效减少高速缓存未中的存储器存取地址，并将所提取的地址组作为地址组提取结果38输出。

图4示出用于利用图3所示的用于高速缓冲存储器的占用状态分析器37分析高速缓冲存储器的占用状态的流程。在步骤S1中，读取高速缓存存取信息36，并在步骤S2中，总计每个地址中所产生的高速缓存未中数。在步骤S3中，将计数后的每个地址分段进每个相应的集合。在步骤S4中，相应的地址按步骤S2编译所产生的高速缓存未中数的降序分段。

图9示出步骤S4的分段结果。在图9中，地址按照每一集合分段，并且分段的地址以所产生的高速缓存未中数的降序排列。集合0中地址的两个最低数字为“00”，而集合1中地址的两个最低数字为“10”。

在步骤S5中，利用在步骤S4中所获得的分段结果提取地址组。也就是说，在每一集合中比较所产生的高速缓存未中数。如果所产生的高速缓存未中数之间的差在规定的阈值范围内，那么可以判定高速缓存未中是由存储器存取冲突导致的，因此提取该地址组。

在步骤S6中，步骤S5中所提取的地址组以优先级的顺序重新排列，并着重显示出来。在步骤S7中，结束高速缓冲存储器使用状态的分析处理，并且输出地址组提取结果38。

在执行上述处理的高速缓冲存储器使用状态分析器中，用于执行步骤S1的结构对应于读取装置，用于执行步骤S2的结构对应于汇总装置，用于执行步骤S3的结构对应于分段装置，用于执行步骤S5的结构对应于提取装置。基本上，这些结构包括计算机软件。

图5示出用于提取地址的步骤S5的细节。地址提取处理参照图9所示的结果进行描述。首先，在步骤11中设置阈值。此阈值为上述阈值，即所产生的高速缓存未中数之间的差的阈值。这里假定阈值设为“5”。在步骤S12中执行初始化，以便使步骤S14及其后续步骤的处理，能够执行与设立每个地址的集合的数量一样多的次数。“初始化”是一种用于重新设置连续数i(i＝0)的处理。连续数i表示地址提取处理业已完成的集合的数。重新设置连续数i后，在步骤S13中判断连续数i(业已提取的集合数)是否小于高速缓冲存储器12中的集合数(i＜集合数)。通常，在开始处理时，连续数i(业已提取的集合数)小于高速缓冲存储器12中的集合数(i＜集合数)，通过执行步骤S14及其后续的处理，所产生的高速缓存未中数在步骤S3中被分段的同一集合中的地址之间进行比较。

在步骤S14中，判断在作为处理目标(处理开始时图9中的集合0)的集合中是否有可获得的地址作为基准地址。当步骤S14判断出没有可获得的地址可在处理目标集合中作为基准地址时，就执行步骤S24。在步骤S24中，连续数i加“1”，并且再次执行上述步骤S13和步骤S14的处理。

同时，当在步骤S 14中判断出有可获得的地址作为基准地址时，就执行步骤S15以获得基准地址，并随后执行步骤S16。这里假设地址0x90000800可获得作为基准地址。

在步骤S16中，判断在所获得的基准地址处所产生的未中数是否为两次以上。假设基准地址为0x90000800，那么所产生的未中数为一百五十次，这在步骤16中判断为真。然后，执行步骤S17。

当在所获得的基准地址处产生的未中数为零或一，因此在步骤S16判断为假时，所获得的地址被视为不宜设置为用于检测存储器存取冲突的基准地址。这样，执行步骤S21。在步骤S21中，被获得的作为基准地址的地址从参考目标中删除，然后处理返回到步骤S14。

在步骤S16判断为真时所执行的步骤S17中，判断在作为处理目标的集合(处理开始时图9中的集合0)中是否有可获得的作为比较地址的地址。当在步骤S17中判断出没有地址可获得作为比较地址时，就执行步骤S21。因为步骤S21的处理在前面已经描述，所以这里省略对它的描述。

当在步骤S17中判断出有地址可获得作为比较地址时，就执行步骤S18以便获得比较地址，然后执行步骤S19。这里假设位置次于基准地址(0x90000800)的地址(0x90000000)被获得作为比较地址。

在步骤S19中，判断在所获得的比较地址处所产生的未中数是否为两次以上。这里假设比较地址为0x90000000，那么因为所产生的未中数为九十次，所以在步骤S19中判断为真。然后，进一步执行步骤S20。

当在所获得的比较地址处产生的未中数为零或一时，因此在步骤S19中判断为假时，所获得的未中数被视为不宜被设置为用于检测存储器存取冲突的比较地址。因此，执行步骤S21。因为步骤S21的处理在上面已经描述，所以这里省略对它的描述。

在步骤S20中，判断在两个地址处所产生的未中数之间的差是否处在阈值范围之内。阈值为预先在步骤S11中设置的值，在上述情况下为“5”。当假设0x90000800为基准地址，而0x90000000为比较地址时，两个地址处的高速缓存未中数之间的差为“60”。此时在两个地址处所产生的高速缓存未中之间的差“60”超出阈值“5”的范围。因此，判断出在基准地址与比较地址之间没有发生存储器存取冲突。

当在步骤S20中判断出没有存储器存取冲突时，就执行步骤S21。因为步骤S21的处理在上面已经描述，所以这里省略对它的描述。

其次，步骤S14的处理过程被描述为：当在步骤S16、S17、S19、S20中判断出所获得的作为基准地址和比较地址的地址不宜作为比较目标或者在所获得的基准地址与比较地址之间没有产生存储器存取冲突时，再次执行该过程。

当假设第一地址0x90000800在先前的步骤S14中被获得作为基准地址时，由于在集合0中有作为第二及其后续地址的地址可以被获得作为基准地址，所以此时在步骤S14中判断的结果为真。然后，执行步骤S15，其中位置次于第一地址0x90000800的第二地址0x90000000被获得作为基准地址。在步骤S16中，由于在此时基准地址(0x90000000)处所产生的高速缓存未中数为九十次，所以判断为真，然后继续执行步骤S17。在这种情况下，由于在集合0中存在可获得作为比较地址的地址，所以步骤S17中判断的结果为真。这样，继续执行步骤S18，其中位置次于第二地址0x90000000的第三地址0x90000C00被获得作为比较地址。

过程进一步执行到步骤S19，其中判断所获得的比较地址处产生的未中数是否为两次以上。假设比较地址为0x90000C00，由于所产生的未中数为五十次，所以在步骤S19中判断为真，然后继续执行步骤S20，其中在两个地址处产生的高速缓存未中数之间的差与阈值进行比较。基准地址0x90000000与比较地址0x90000C00处所产生的高速缓存未中数之间的差为“40”，这超出了在步骤S11中所设置的阈值“5”的范围。因此，此时判断出在基准地址与比较地址之间没有产生存储器存取冲突。

当在步骤S20中判断出没有存储器存取冲突时，在步骤S15中所获得的基准地址从基准目标中删去。然后，处理过程返回至步骤S14，并且重复上述处理过程。

在集合0中，例如，当第三地址0x90000C00被获得作为基准地址，而第四地址0x90000200被获得作为比较地址时，在那些地址处所产生的高速缓存未中数之间的差为“0”，其处于阈值“5”的范围之内。在这种情况下，判断出在基准地址与比较地址之间产生了存储器存取冲突，然后处理过程执行至步骤S22。在步骤S22中，提取当时的基准地址与比较地址作为具有存储器存取冲突的地址。然后，进一步执行步骤S23，将比较地址(上述情况中的地址0x90000200)从比较目标中删去，并返回到步骤S17以便继续一系列的处理过程。

上述处理过程一直继续，直到连续数i与构成高速缓冲存储器12的集合的数目相同为止(i＝集合数)。“连续数i与集合数相同”意味着在该集合的所有地址的地址提取处理过程都完成了。当在步骤S13中判断连续数i与集合数相同时，这一系列的处理过程结束。

通过此流程，有可能通过比较所产生的高速缓存未中数是否一致提取到具有存储器存取冲突的地址组。进一步，有可能计算出高效减少高速缓存未中的存储器存取地址。另外，有可能当比较所产生的高速缓存未中数时通过提供阈值，根据高速缓存未中的状态来改变阈值的设置。由此，有可能不但在所产生的高速缓存未中数一致时，而且在所产生的高速缓存未中数大体相同时，计算高效减少高速缓存未中的存储器存取地址。

图10示出图5所示的地址提取处理过程所提取的地址组的结果。集合0的地址组A由四个地址组成，地址组B由三个地址组成，地址组C由两个地址组成。所产生的高速缓存未中数相对彼此的差均为“5”或更小。在图9中的地址0x90000D00处，所产生的高速缓存未中数为“25”。在其前面的地址即0x90005300处，所产生的高速缓存未中数为“48”，在其后面的地址即0x90002400处，所产生的高速缓存未中数为“18”。如上所述，在地址0x90000D00处，所产生的高速缓存未中数相对就其顺序而言的相邻地址的差超过“5”。因此，它在图10上不被列为所提取出的地址组。

集合1中的地址组D由四个地址构成，地址组E由两个地址构成，地址组F也由两个地址构成。所产生的高速缓存未中数相对彼此的差均为“5”或更小。

图6和图7示出步骤S6的细节。步骤S6可用图6和图7所示的每个处理过程代替。首先，参考图10所示的结果，描述图6所示的所提取地址组的显示处理过程。

集合0和集合1结合在一起的第一地址组的顺序为A→B→C→D→E→F。在步骤S31中，初始化用在分类处理过程中的变量。此时，i表示计算地址组数时的统计数，j表示完成划分后的地址组数，k表示用于判断分段处理过程已完成的变量。将(地址组数-1)设置为变量k的初始值。每完成一次一系列处理过程，变量k就递减，当它为“0”时，分类处理过程就结束。这里，因为假设图10中地址组的总数为“6”，所以变量k的初始值设置为“5”。

然后，执行步骤S32，判断分类处理过程是否已完成。该判断通过核对变量k是否已达到0(k＞0)来实现。假设变量k的初始值为“5”，那么在处理过程刚开始时，步骤S32判断为真，并且过程继续执行至步骤S33。在步骤S33中，判断地址组的分类处理过程是否已基于统计数i与变量k之间的幅度关系到该组的最后一批地址时已经完成。具体的，如果i≥k，就判断为地址组的分类处理过程到该组的最后一批地址时已完成。否则，就判断为地址组的分类处理过程到该组的最后一批地址时还未完成。当假设变量k的初始值为“5”时，刚开始处理过程后，i＝0而k＝5。这样，在步骤S33中判断为假。当在步骤S33中判断为假时，执行步骤S34-步骤S38。

在步骤S34中，地址组i(在图10的情况下刚开始处理过程时的地址组A)中的地址数与下一地址组i+1(在图10的情况下刚开始处理过程时的地址组B)的地址数进行比较。在图10的情况下刚开始处理过程时，地址组A中的地址数为“4”，地址组B中的地址数为“3”，它们彼此不同。因此，在步骤S34中判断为假，处理过程执行步骤S35。在步骤S35中，地址组A中的地址数为“4”，其大于地址组B中的地址数“3”(i中的数＞i+1中的数)。因此，在步骤S35中判断为真，处理过程执行步骤S37。

在步骤S37中交换地址组i与地址组i+1的顺序。这样，继续执行步骤S38。具体的，作为地址组初始顺序的地址组i→地址组i+1的顺序改变为地址组i+1→地址组i。假设地址组i(地址组A)和地址组i+1(地址组B)，改变后的顺序变成地址组B→地址组A。

在步骤S38中，作为分类处理过程目标的那批地址组转变成下批地址组。随后，处理过程返回至步骤S33。具体的，步骤S38的处理过程为用于将统计数i加“1”的过程。此时，考虑到步骤S38的处理过程是在执行步骤S37的处理过程后进行的。在这种情况下，由于地址组的顺序变为B→A→C→D→E→F，所以当统计数“i”在步骤38中增加时，目标地址组变成地址组A和地址组C。

考虑到统计数i在步骤S38中由“0”递增到“1”。在这种情况下，由于实际上i＝1而k＝5，所以在步骤S38中判断为假，处理过程执行步骤S34。

在这种情况下，鉴于基于地址组A中的地址数“4”和地址组C中的地址数“2”对步骤S34与步骤S35中的地址数所作的比较，在步骤S34中判断为假，在步骤S35中判断为真。于是，执行步骤S37。

在步骤S37中交换地址组i与地址组i+1的顺序。然后，继续执行步骤S38。假设地址组i(地址组A)和地址组i+1(地址组A)，改变后的顺序为地址组C→地址组A。

在步骤S38中用于执行分类处理的那批地址组被转化为下批地址组。然后，返回到步骤S33。具体的，统计数i加“1”。在这种情况下，步骤S38的处理过程在执行步骤S37的处理过程后执行。因此，当统计数i在步骤38中递增时，目标地址组变成地址组A和地址组D。

考虑到统计数i在步骤S38中由“1”递增到“2”。在这种情况下，由于i＝2而k＝5，所以在步骤S33中判断为假，并且执行步骤S34。在这种情况下，鉴于基于地址组A中的地址数“4”和地址组D中的地址数“4”对步骤S34与步骤S35的地址数所作的比较，在步骤S34中判断为真。然后，执行步骤S36。如图10所示，组A中所产生的高速缓存未中总数为“198”，组D中所产生的高速缓存未中总数为“239”。因此，在步骤S36中判断为假，执行步骤S37。

在步骤S37中交换地址组i与地址组i+1的顺序。然后，执行步骤S38。假设地址组i(地址组A)和地址组i+1(地址组D)，改变后的顺序变成地址组D→地址组A。

在步骤S38中，作为分类处理的目标的那批地址组转换为下批地址组。然后，返回到步骤S33。具体的，统计数i加“1”。在这种情况下，步骤S38的处理过程在执行步骤S37的处理过程后执行。这样，当统计数i在步骤38中递增时，目标地址组变成地址组A和地址组E。

考虑到在步骤S38中所计算的数i由“2”递增到“3”。在这种情况下，i＝3而k＝5。因此，在步骤S33中判断为假，执行步骤S34。

在这种情况下，鉴于基于地址组A中的地址数“4”和地址组E中的地址数“2”对步骤S34与步骤S35中的地址数所作的比较，在步骤S34中判的断为假，在步骤S35中判断为真。然后，执行步骤S37。

在步骤S37中交换地址组i与地址组i+1的顺序。然后，执行步骤S38。假设地址组i(地址组A)和地址组i+1(地址组E)，改变后的顺序为地址组E→地址组A。

作为分类处理目标的那批地址组在步骤S38中转换为下批地址组。然后，返回到步骤S33。具体的，统计数i加“1”。在这种情况下，步骤S38的处理过程在执行步骤S37的处理过程后执行。因此，当统计数“i”在步骤38中递增时，目标地址组变成地址组A和地址组F。

通过进一步重复地执行这些处理过程，地址组A的顺序与地址组E和地址组F的顺序交换。因此，顺序成为B→C→D→E→F→A。在那种状态下，i＝5而j＝4。

再次返回步骤S33，由于i＝5而k＝5，所以在此步骤中判断为真。然后，执行步骤S39和步骤S40，以便执行这些步骤的处理，并且随后i＝0，j＝0，k＝4。由此，在执行过步骤S32和步骤S33后，继续执行步骤S34。在这种情况下，由于i回到0，划分处理过程返回到第一地址组。在这种情况下，第一地址组成为地址组B和地址组C。

在步骤S34中，比较地址组B中的地址数和地址组C中的地址数。由于下文的处理过程基于上述处理过程，所以这里省略对它的描述。

通过重复这种处理过程，地址组的顺序最后变成E→C→F→B→D→A。然后，继续执行步骤S41。如此一来，地址组E是可高度有效地减少高速缓存未中的地址组，即，具有最高优先级的地址组。

在步骤S41中，着重显示具有最高优先级的地址组E。地址组数与地址组E相同的地址组C和地址组F也可以着重显示。

补充说明了地址组的最后顺序(E→C→F→B→D→A)。被判断为具有最高优先级的地址组E中的地址数以及地址数与地址组E相同的地址组C和地址组F中的地址数均为“2”。地址组B中的地址数为“3”。地址组D和地址组A中的地址数为“4”。如此，在地址组的最后顺序中，各个组被分成具有相同地址数的组。然后，那些地址组按照升序排列为(E，C，F)→(B)→(D，A)。

分成地址数相同的组的地址组进一步按照所产生的高速缓存未中总数的降序排列。即，在带有“2”个地址的地址组E、C和F中，所产生的高速缓存未中总数依次分别为“60”(＝30+30)、“15”(＝8+7)和“7”(＝5+2)。这样，地址组E、C和F按所产生的高速缓存未中总数的降序排列为E→C→F的顺序。

同时，在带有“4”个地址的地址组D和A中，所产生的高速缓存未中总数依次分别为“239”(＝62+60+60+57)和“198”(＝50+50+50+48)。这样，地址组D和A按所产生的高速缓存未中总数的降序排列。

如上所述，地址数少被视为第一优先级，所产生的高速缓存未中总数大被视为第二优先级。有可能按此流程通过考虑属于地址组的地址组数多小和所产生的高速缓存未中总数多大，来检测可高度有效地减少高速缓存未中的地址组，即使当有多个具有存储器存取冲突的地址组时也是如此。

此外，有可能通过着重显示可高度有效地减少高速缓存未中的地址组来展示可高度有效地减少高速缓存未中的地址。在这里，分类处理就集合0和集合1而言一起执行。但是，分类处理可以按照每一集合进行，其结果可以着重显示。

如上所述，在通过参考图6描述的所提取地址组的显示处理过程的步骤S6中，步骤S31-步骤S40由用于高速缓冲存储器的占用状态分析器37的提取装置执行，步骤S41由用于高速缓冲存储器的占用状态分析器37的显示装置(未示出)执行。

接下来，参考图10所示的结果描述所提取地址组的显示处理过程，其中如图7所示考虑路数。路数表示高速缓冲存储器内有多少个块用于存储数据。图7中的处理过程为图6所示处理过程的修改。因此，在图7的流程图中存在着与图6的流程图相同的处理过程。也就是说，步骤S52(图7)与步骤S32(图6)相同，步骤S53(图7)与步骤S33(图6)相同，步骤S59(图7)与步骤S36(图6)相同，步骤S60(图7)与步骤S37(图6)相同，步骤S61(图7)与步骤S38(图6)相同，步骤S62(图7)与步骤S39(图6)相同，步骤S63(图7)与步骤S40(图6)相同，步骤S64(图7)与步骤S41(图6)相同。因此，图7所示的每个步骤的详述将省略。

首先，在步骤S51中执行分段处理时所使用的每个变量的初始化。在步骤S51的处理过程中，除了在图6的步骤S31中所设置的统计数i、地址组数j和变量k之外，还设置每组的路数w。这里假设它们被分别设置为i＝0，j＝0，k＝5和W＝2。

然后，在步骤S52和步骤S53的处理过程之后，继续执行步骤S54。在步骤S54中，分别计算N1和N2，它们分别为地址组i和地址组i+1中的地址数与路数w的差。在包括两集合的集合关联系统的高速缓冲存储器中，在每一集合中都存在与路数w一样多的高速缓存块。这样，如果地址数与路数w之间的差为“1”或更小，那么有以下情况。也就是说，在这种情况下，当在具有存储器存取冲突的地址中的一个地址处所产生的高速缓存未中通过改变地址排列或诸如此类的方法加以解决时，极有可能同时解决在具有存储器存取冲突的其它地址处的高速缓存未中。基于这样的观点，上述在步骤S54中的差N1和N2用作索引，用于确定所提取地址组的优先级。

下面根据刚开始处理过程时地址组i为地址组A，地址组i+1为地址组B这样的假设，描述处理过程。在处理过程中，N1＝2并且N2＝1。即，由于地址组A中的地址数为“4”，路数w为“2”，故N1＝4-2＝2。同时，由于地址组B中的地址数为“3”，路数w为“2”，故N2＝3-2＝1。

只有N2为“1”或更小，所以在步骤S56→步骤S57的处理过程之后，执行步骤S60。在步骤S60中，交换地址组A和地址组B的顺序。然后，执行步骤S61。在步骤S61中，那批用于分段处理的地址组变为下批地址组。然后，返回步骤S53并继续进行上述处理。

当到最后一批地址组时，分段处理过程完成，相应的地址组的顺序变成B→C→A→E→F→D。此时，i＝5，j＝4。

在地址组已为上述顺序的情况下，由于i＝5且k＝5，所以在其后执行的步骤S53中判断为真，并且执行步骤S62和步骤S63，用于执行各自的处理过程。作为步骤S62和步骤S63的处理过程的结果，i＝0，j＝0，k＝4，然后在步骤S52→步骤S53的处理过程之后，继续执行步骤S54→步骤S55。在步骤S54中，地址组i为地址组B，地址组i+1为地址组C，其中N1＝1和N2＝0。由于N1和N2都为“1”或更小，所以在步骤S55中判断为真，过程继续执行步骤S59。

由于在地址组B中所产生的高速缓存未中总数为“52”(＝18+18+16)，在地址组C中所产生的高速缓存未中总数为“15”(＝8+7)，所以在步骤S59中判断为真。然后，执行步骤S61。

通过重复上述处理过程，地址组的顺序最后变成E→B→C→F→A→D。也就是说，地址组E成为可最有效地减少高速缓存未中的地址组，即，具有最高优先级的地址组。因此，地址组E被着重显示为具有最高优先级的地址组。当有多个具有最高优先级的地址组时，多个地址组都可被着重显示。

通过图7所示的上述处理过程，通过考虑属于地址组的地址数、产生的高速缓存未中总数和路数，有可能检测可最有效地减少高速缓存未中的地址组，即使当有多个具有存储器存取冲突的地址组时也是如此。

此外，有可能通过着重显示可最有效地减少高速缓存未中的地址组来表示可最有效地减少高速缓存未中的地址。分类处理在集合0和集合1中一起进行，但是分类处理可以按照每一集合进行，并且划分结果可以着重显示。

已参考最优实施例详细描述了本发明。然而，不脱离所附权利要求的精神和宽阔范围，有可能对组成部分作出各种组合和修改。

Claims (10)

1.一种高速缓冲存储器分析方法，用于分析处理器中高速缓冲存储器的占用状态，该处理器包括集合关联系统的所述高速缓冲存储器，所述集合关联系统的高速缓冲存储器的每一集合都具有多个数据存储块，并且每一集合用存储器存取地址的较低位与存储器的其它区域相区别，该处理器还包括用于对所述高速缓冲存储器进行记录控制的CPU，该方法包括如下步骤：

读取步骤，用于从所述高速缓冲存储器中，读取包含其中产生高速缓存未中的存储器地址的信息；

总计步骤，用于对包含在所述信息中的每个高速缓存未中产生地址处所产生的高速缓存未中数进行总计；

分段步骤，用于按照每一集合根据所产生的高速缓存未中数的总计将高速缓存未中产生地址进行分段；

提取步骤，用于从被分段为同一集合地址的多个高速缓存未中产生地址中，提取所产生的高速缓存未中数一致或接近的地址组；

指定步骤，用于指定每一集合的数据存储块数以作为所述提取步骤的预处理，其中，

在所述提取步骤中，当有多个被分在同一集合中的地址组时，通过将高优先级赋予在从包含在每个地址组中的地址数减去所述数据存储块数等于1或小于1的地址组，将所述多个地址组分开。

2.根据权利要求1所述的高速缓冲存储器分析方法，进一步包括如下步骤：

显示步骤，用于将在所述提取步骤中所提取的地址组的提取结果显示为分析结果。

3.根据权利要求1所述的高速缓冲存储器分析方法，其中，在所述提取步骤中：

设置一阈值，作为所产生的若干高速缓存未中数之差的上限；基于所述差

是否落在阈值范围内，将已分段成同一集合中的高速缓存未中产生地址分开；并将所述阈值范围内的高速缓存未中产生地址视为所产生的高速缓存未中数接近的地址组。

4.根据权利要求3所述的高速缓冲存储器分析方法，其中，所述阈值被设置为边界值，该边界值用于识别是否将极有可能导致其中计算所述差值的高速缓存未中产生地址间的数据冲突。

5.根据权利要求1所述的高速缓冲存储器分析方法，其中，在所述提取步骤中，

当提取同一集合内的多个地址组时，所述多个地址组通过以包含在相关地址组中的地址数的顺序并行排列来分开。

6.根据权利要求5所述的高速缓冲存储器分析方法，其中，在所述提取步骤中，

当提取同一集合内包含相同地址数的多个地址组时，所述包含相同地址数的多个地址组通过以总值的顺序并行排列来分开，在每个地址组处，所述总值通过对包含在地址组中的地址处所产生的高速缓存未中数进行总计来获得。

7.根据权利要求5所述的高速缓冲存储器分析方法，进一步包括显示步骤，用于将在所述提取步骤中所提取的地址组的提取结果显示为分析结果，其中，

在该显示步骤中，被视为在所述提取步骤中具有最少地址数的地址组被着重显示为可高效减少高速缓存未中的地址组。

8.根据权利要求1所述的高速缓冲存储器分析方法，其中，在所述提取步骤中，

如果存在当从包含在每个地址组中的地址数减去所述数据存储块数等于1或小于1的多个地址组，则按照对每个地址组处的地址中所产生的高速缓存未中数进行总计而获得的总值的顺序并行排列，将所述多个地址组分开。

9.根据权利要求1所述的高速缓冲存储器分析方法，进一步包括显示步骤，用于将在所述提取步骤中所提取的地址组的提取结果显示为分析结果，其中，

在该显示步骤中，在所述提取步骤中被分段为具有高优先权的地址组被着重显示为可高效减少高速缓存未中的地址组。

10.一种用于分析处理器中高速缓冲存储器的占用状态的高速缓冲存储器分析装置，该处理器包括集合关联系统的高速缓冲存储器和CPU，所述集合关联系统的高速缓冲存储器的每一集合都具有多个数据存储块，并且每一集合用存储器存取地址的较低位与存储器的其它区域相区别，CPU则用于对所述高速缓冲存储器进行记录控制，该装置包括：

读取装置，用于从所述高速缓冲存储器中读取对其中产生高速缓存未中的存储器地址进行记录的信息；

总计装置，用于对包含在所述信息中的每个高速缓存未中产生地址处所产生的高速缓存未中数进行总计；

分段装置，用于按照每一集合根据其中所产生的高速缓存未中数的总计将高速缓存未中产生地址进行分段；

提取装置，用于从被分段成为同一集合地址的高速缓存未中产生地址中提取所产生的高速缓存未中数一致或接近的地址组；

指定装置，用于指定每一集合的数据存储块数以作为所述提取装置所执行的提取动作的预处理，其中，

当有多个被分在同一集合中的地址组时，所述提取装置通过将高优先级赋予在从包含在每个地址组中的地址数减去所述数据存储块数等于1或小于1的地址组，将所述多个地址组分开。

Images