一种高速缓存失效的处理器访存指令处理方法

摘要

本发明公开了一种高速缓存失效的处理器访存指令处理方法，该方法包括：利用全修改Cache块节省访存带宽，通过预测失效的存数指令写高速缓存还是写低层存储系统，充分发挥两种处理方法的优点。本发明减少了失效存数指令造成的存储管理队列发生阻塞的频繁程度，避免了额外硬件开销，节省访存带宽，降低了Cache的失效率，实现存数指令对后面同一Cache块的取数指令的预取作用。

说明书

技术领域

本发明涉及微处理器体系结构技术领域，特别涉及一种高速缓冲存储器访问失效的处理器访存指令处理方法。

背景技术

随着微处理器设计和生产工艺的快速发展，存储系统的访问速度与处理器的运算速度的差距越来越显著，访存性能已成为处理器的瓶颈。目前的处理器普遍采用高速缓冲存储器(Cache，下文简称“高速缓存”)作为提高存储系统性能的有效方法和提高处理器处理能力的重要措施。高速缓存是一个容量小速度快的特殊存储器，存放处理器最近使用的指令和数据。受访问时间的限制，高速缓存的容量比较小。在处理器访问高速缓存，而数据不在高速缓存中，这时就会出现叫做访问失效的情况。设计高效的高速缓存失效的处理器访存指令处理方法，可以大幅度降低处理器的平均访存时间。

处理器的访存指令包括取数指令和存数指令。在实现高速缓存的处理器中，高速缓存失效的取数指令必须从低层存储系统中取回数据才能完成取数操作。存数指令与取数指令不同，它不需要对应块原来的值。目前，高速缓存访问失效(下文中简称“失效”)的存数指令的处理方法通常有两种：一种是写高速缓存，另一种是写低层存储系统。

存数指令失效后写高速缓存的方法，由于存数指令不会写满整个Cache块，因此需要把低层存储系统中的对应块读到高速缓存中再执行写操作。这种方法对一个块的多个存数指令都能够在Cache中完成，节省存储带宽，还会对后面同一地址的取数指令起到预取的作用。但把低层存储系统中的块取到Cache中再执行写操作，会延迟存数指令的执行。指令窗口和存储管理队列的大小是有限的，就会由于队列满引起流水线的阻塞。一种改进的写高速缓存方法是每个Cache块根据处理器的存数指令最小粒度设置有效位，失效的存数指令直接写高速缓存，置对应的有效位标志。这种改进方法的缺点是硬件代价大。因为处理器的存数指令最小粒度为字节写，一个Cache块一般为32字节或更大，这样每个Cache块就必须增加至少32比特的额外存储。而且不是每个Cache块都会被写满，要求低层存储系统要支持带屏蔽位的写回或分成多个写操作写回，这样就会牺牲存储带宽。总之，上述的高速缓存失效的存数指令写高速缓存的方法及其改进方法的不足是：如果存数指令被后面的取数指令用到，可以起到预取的作用；如果不会被后面的取数指令用到，会造成Cache的污染和填充Cache时对Cache端口的占用。

存数指令失效后写低层存储系统的方法，在失效时不需要从低层存储系统中取回Cache块，但每个存数指令都要执行一次对低层存储器的写操作，需要很大的存储带宽。一种改进的写低层存储系统的方法是设置写缓冲区，在写缓冲区满的情况下才执行写操作。这样就会把一些对同一个Cache块的写操作合并起来，减少写操作的次数。与设置有效位的失效后写高速缓存方法类似，不是每个Cache块都会被写满，要求低层存储系统要支持带屏蔽位的写或分成多个写操作写回。高速缓存失效的存数指令写低层存储系统的方法，不会造成Cache的污染和对Cache端口的额外占用，但存在的问题是：没有实现存数指令对后面同一Cache块的取数指令的预取作用；如果失效的存数指令被后面同一Cache块地址的取数指令用到，取数指令会失效，引起流水线的阻塞。

由于程序执行的空间局部性，一些Cache块会很快被连续的存数指令写满，这样的Cache块称为全修改Cache块，否则称为非全修改Cache块。对于全修改Cache块，整个Cache块都被写满，失效存数指令写高速缓存的方法在不设额外有效位标志情况下，不需要把低层存储系统中的对应块读到高速缓存中就可以执行写操作。全修改Cache块的失效存数指令采用写低层存储系统的方法，也不需要拆分成多个写或需要低层存储系统提供带屏蔽位的写支持。对于非全修改Cache块写高速缓存或是写低层存储系统，先从低层存储系统中取回对应块的值。因为非全修改Cache块写高速缓存必须取到对应块原来的值，写低层存储系统也可以通过取回对应块原来的值，避免拆分成多个写导致带宽的浪费，或需要低层存储系统提供带屏蔽位写的额外支持。

综上所述，现有技术的不足需要提供一种改进的高速缓存失效的处理器访存指令处理方法。

发明内容

本发明的目的在于减少失效存数指令造成的存储管理队列发生阻塞的频繁程度，避免额外的硬件开销，节省访存带宽，降低Cache的失效率，实现存数指令对后面同一Cache块的取数指令的预取作用，从而提供一种改进的高速缓存失效的处理器访存指令处理方法。

为了达到上述目的，本发明采取的技术方案如下：

一种高速缓存失效的处理器访存指令处理方法，该方法利用全修改Cache块节省访存带宽，预测失效的存数指令是写高速缓存还是写低层存储系统，具体包括如下步骤：

步骤1)：访存指令进入存储管理队列，将高速缓存是否命中的信息记录在存储管理队列对应项的命中域，判断命中域的值是否为1，如果是，存数指令直接写高速缓存，取数指令数据写到处理器的通用寄存器，如果否，执行步骤2)；

步骤2)：由存储管理队列向访存失效队列发出失效访问请求，存数指令在访存失效队列执行写操作，把数据写入所进入访存失效队列项的数据域，并退出存储管理队列，取数指令在存储管理队列中等待数据返回；

步骤3)：判断失效访存指令对应Cache块是否在写回队列中命中；如果是，从写回队列返回的数据与对应访存失效队列项的数据域中存数指令所写的数据拼成Cache块，执行步骤7)；如果否，执行步骤4)；

步骤4)判断是取数指令还是存数指令；

如果是取数指令，执行步骤5)；

如果是存数指令，判断是否收集为全修改Cache块；

如果收集为全修改Cache块，执行步骤7)；

如果没有收集为全修改Cache块，判断访存失效队列是否满；如果满，选择一个非全修改Cache块所在访存失效队列项，执行步骤5)，如果没有满，继续在访存失效队列中等待收集为全修改Cache块；

步骤5)：向低层存储系统发出访问请求；

步骤6)：等待低层存储系统数据返回，将返回的数据与对应访存失效队列项的数据域中存数指令所写的数据拼成Cache块；

步骤7)：访问预测装置，取数指令设置预测装置中预测表对应项的值为1，执行步骤8)；存数指令由预测装置预测是否写高速缓存，如果预测写高速缓存，执行步骤8)，如果预测写低层存储系统，执行步骤9)；

步骤8)：用访存失效队列对应项数据写高速缓存，同时取数指令置存储管理队列对应项命中域的值为1，执行步骤10)；

步骤9)：等待写回队列有空项，将访存失效队列中数据写到写回队列；

步骤10)：失效访存指令处理完成，从访存失效队列中退出。

在上述技术方案中，步骤4)中所述的非全修改Cache块所在访存失效队列项的选择，可以利用最近最少使用(LRU)策略和随机(Random)策略，但不限于这两种策略。

在上述技术方案中，访问低层存储系统的全修改Cache块的选择利用最近最少使用方法，通过在访存失效队列项中增加表示对应项没有存数指令进入的时间的域来实现。

在上述技术方案中，步骤7)中所述的预测装置根据指令执行的历史来预测存数指令对应Cache块是否会被后面的取数指令用到，从而确定写高速缓存还是写低层存储系统，具体步骤如下：

步骤71)：预测装置每隔n个处理器时钟周期进行一次初始化，初始化预测表各项为0；

步骤72)：判断访问预测装置的失效指令是存数指令还是取数指令，如果是存数指令，执行步骤74)，如果是取数指令，执行步骤73)；

步骤73)：设置取数指令预测表对应项的值为1，表示对应Cache块会被取数指令用到；

步骤74)：查询预测装置的预测结果，如果预测结果为1，表示写高速缓存，如果预测结果为0，表示写低层存储系统。

在上述技术方案中，所述n值的取值范围是100000到80000000000之间的整数；所述n值的取值以10000000为最佳。

与现有技术相比，本发明的优点在于：

1)失效存数指令发送到访存失效队列后，从存储管理队列中退出，减少失效存数指令造成的存储管理队列发生阻塞的频繁程度。

2)在访存失效队列中收集全修改Cache块，与设计独立的存数指令收集缓冲区相比，除避免了增加额外的硬件开销外，还避免了存数指令收集缓冲区与访存失效队列互相查询以保证数据一致性的开销。

3)在访存失效队列中收集满的全修改Cache块，不需要从低层存储系统中取回对应块原来的值，节省访存带宽。节省的访存带宽可以用来做预取等其他优化。

4)预测不会被后面的取数指令用到的失效存数指令对应的Cache块，直接写回到低层存储系统，避免Cache端口的占用和替换掉Cache中有用的Cache块而造成Cache污染，降低了Cache的失效率。

5)预测会被后面的取数指令用到的失效存数指令对应的Cache块，写回到Cache，实现存数指令对后面同一Cache块的取数指令的预取作用。

附图说明

图1是本发明访存微体系结构示意图；

图2是本发明访存失效队列项结构示意图图；

图3是本发明访存失效队列状态转换示意图图；

图4是本发明访存指令内部结构示意图；

图5是本发明失效访存指令处理流程图；

图6是本发明预测装置处理流程图。

具体实施方式

下面结合附图和实施例解释具体实施过程，对本发明作进一步详细描述。

如图1所示，为本发明访存模块微体系结构示意图。地址计算部件(MEM AddressCalculate)11用来进行访存指令的地址计算；高速缓存(Cache)12用来缓存最近使用的数据；虚实地址转换表(TLB)13用来将访存指令访问的虚地址转换成物理地址；标志位比较部件(Tag Compare)14进行标志位比较，判断高速缓存是否命中；存储管理队列(Load Store Queue)15记录高速缓存是否命中的信息，进行访存指令的管理；访存失效队列(Miss Queue)17处理高速缓存失效的访存指令；写回队列(Wtbk Queue)18是用来缓解对低层存储系统的读写冲突，将写低层存储系统的操作都先写到写回队列中，在低层存储系统访问通路空闲时再写到低层存储系统中；预测装置(Predict Table)16预测高速缓存失效的存数指令写高速缓存还是写低层存储系统；低层存储系统(Lower Memory Level)19是比高速缓存访问速度慢、容量大的存储系统。

访存指令的访问地址通过地址计算部件(MEM Address Calculate)11计算出来以后，用虚地址索引并行访问高速缓存(Cache)12和虚实地址转换表(TLB)13，标志位比较部件(Tag Compare)14进行标志位比较，确定是否高速缓存命中。访存指令进入存储管理队列(Load Store Queue)15，存储管理队列项的命中域记录高速缓存是否命中的信息，如果高速缓存命中置命中域的值为1，如果高速缓存失效置命中域的值为0。判断存储管理队列命中域的值是否为1，如果为1，表示命中，存数指令直接写高速缓存，取数指令数据写入处理器的通用寄存器，如果为0，表示失效，存储管理队列向访存失效队列(Miss Queue)17发送失效访问请求，存数指令将数据写入访存失效队列的数据域并从存储管理队列中退出，取数指令在存储管理队列中等待数据返回。访存失效队列向写回队列(Wtbk Queue)18查询失效访存指令对应高速缓存块是否在写回队列中。存数指令项在访存失效队列中收集全修改高速缓存块。取数指令项和访存失效队列满时非全修改高速缓存块对应的存数指令项向低层存储系统(Lower Memory Level)19发出访问请求。收集为全修改Cache块或失效Cache块在写回队列命中或低层存储系统数据返回，访问预测装置(Predict Table)16。取数指令修改预测装置中预测表对应项的值为1，存数指令由预测装置预测写高速缓存还是写低层存储系统。取数指令和预测写高速缓存的存数指令用访存失效队列对应项数据写高速缓存(Cache)12，同时取数指令置存储管理队列对应项命中域的值为1。预测写低层存储系统的存数指令将访存失效队列对应项数据写到写回队列(Wtbk Queue)18。失效访存指令处理完成，从访存失效队列中退出。

如图2所示，为访存失效队列项的结构示意图。其中，state域表示访存失效队列状态；op域表示访存指令的内部操作码；paddr域表示访存指令访问的物理地址；data域表示访存指令对应Cache行的数据；bytemask域表示data域的相应字节被存数指令写过，bytemask为全1表示该项为全修改Cache块；w域表示data域被存数指令写过；age域表示对应项没有存数指令进入的时间。

如图3所示，为访存失效队列状态转换示意图，其中，MQ_EMPTY表示该项为空；MQ_MISS表示该项接收失效请求等待查询写回队列；MQ_VCMISS表示在写回队列中没有对应块数据，等待收集为全修改Cache块或访问低层存储系统；MQ_MREF表示发出低层存储系统访问访问；MQ_RDY表示写回队列命中或收集满一个全修改Cache块或低层存储系统数据返回，数据已经准备好等待访问预测装置。数字101表示失效访问进入空项，数字102表示在写回队列中没有查询到对应Cache块，数字103表示在写回队列中得到对应Cache块的数据，数字104表示向低层存储系统发出访问请求，数字105表示低层存储系统数据返回，数字106表示收集为全修改Cache块，数字107表示预测写Cache的写回Cache、预测写低层存储系统的写到写回队列。

如图4所示，为发送到访存失效队列的访存指令内部格式示意图，op域表示内部操作码，标识是存数指令(store)或取数指令(load)，并标识操作模式是字节、半字、字或双字；paddr域表示访存指令访问的物理地址；value域表示存数指令所写的数据。

如图5所示，为本发明失效访存指令处理的流程图。参照图3和图5，一种高速缓存失效的处理器访存指令处理方法，具体实施步骤如下：

步骤1，判断访存指令访问高速缓存是否命中；如果是，存数指令直接写高速缓存，取数指令向处理器核返回数据，如果否，失效访存指令进入存储管理队列，执行步骤2；

步骤2，由存储管理队列向访存失效队列发出失效访问请求，失效的访存指令发送到访存失效队列，查询在访存失效队列中是否有相同块地址的失效访问，如果有命中项，则进入该项，否则进入一个状态为MQ_EMPTY的空项；失效访存指令进入访存失效队列空项(如101所示)，置对应项状态为MQ_MISS，置paddr域为失效指令的paddr，置op域为失效指令的操作码；如果是存数指令进入访存失效队列，访存失效队列根据操作模式和物理地址确定存数指令所写的Cache块的位置，用存数指令的value域填充data域的对应位置，并设置相应的bytemask域，置w域的值为1，用来在写高速缓存时置数据Cache的脏(dirty)位，将对应项的age域清零，表示新被存数指令使用过，其他失效存数指令项age域的值加1；如果是取数指令进入访存失效队列空项，置w域的值为0，bytemask域为0；如果取数指令进入非空项，置op为取数指令的op，表示不进行预测只用来修改预测表；因为取数指令必须填充Cache，并置存储管理队列对应项命中域的值为1。否则取数指令在存储管理队列中等待数据返回，会引起处理器的死锁；

步骤3，查询写回队列，如果在写回队列中查询到对应Cache块的数据(如103所示)，置对应项状态为MQ_RDY；根据bytemask域，将访存失效队列中失效存数指令所写数据与返回数据拼成Cache块，形成data域，执行步骤7；如果在写回队列中没有查询到对应Cache块(如102所示)，置成MQ_VCMISS状态，执行步骤4；

步骤4，判断op域是取数指令还是存数指令；如果是取数指令，执行步骤5；如果是存数指令，检查访存失效队列对应项的bytemask域，判断是否收集为全修改Cache块，如果收集为全修改Cache块(如106所示)，置为MQ_RDY状态，执行步骤7；如果没有收集为全修改Cache块，判断访存失效队列是否满；为了尽量多的收集到全修改Cache块，访存失效队列中存数指令的项在没有对相同Cache块的取数指令进入和队列不满的情况下，不向低层存储系统发送访问请求；如果访存失效队列满，按照LRU策略，选择age最大的非全修改Cache块所在访存失效队列项，执行步骤5，如果访存失效队列没有满，继续在访存失效队列中等待收集为全修改Cache块；

步骤5，向低层存储系统发出访问请求(如104所示)，置对应项状态为MQ_MREF；

步骤6，等待低层存储系统数据返回，低层存储系统数据返回(如105所示)，置对应项状态为MQ_RDY；根据bytemask域，将访存失效队列中失效存数指令所写数据与返回数据拼成Cache块，形成data域；

步骤7，访问预测装置，取数指令修改预测装置中预测表对应项的值为1，执行步骤8，存数指令由预测装置预测是否写高速缓存，如果预测写高速缓存，执行步骤8，如果预测写低层存储系统，执行步骤9；

步骤8，用访存失效队列对应项数据写高速缓存，同时取数指令置存储管理队列对应项命中域的值为1，执行步骤10；

步骤9，等待写回队列有空项，将访存失效队列中数据写到写回队列(如107所示)；

步骤10，失效访存指令处理完成，置对应项状态为MQ_EMPTY，从访存失效队列中退出。

本发明步骤7中所述的预测装置的预测方法，是根据指令执行的历史预测存数指令对应Cache块是否会被后面的取数指令用到，从而确定写高速缓存还是写低层存储系统。预测装置的预测策略利用程序访问的时间和空间局部性，建立访问历史表记录失效存数指令被后面取数指令用到的历史，根据历史表提供的信息进行预测。预测表用访存指令的地址进行索引，预测表中的每项的值表示对应的访存指令写高速缓存还是写低层存储系统，如果值为1表示写高速缓存，如果值为0表示写低层存储系统。如图6所示，为预测装置工作流程图。预测装置的预测方法，步骤如下：

步骤71，预测装置每隔n个处理器时钟周期进行一次初始化，初始化预测表各项为0；此处实施例中n取最佳值10000000，n值的取值范围可以是100000到80000000000之间的整数；

步骤72，判断访问的失效指令是存数指令还是取数指令，如果是存数指令，执行步骤74，如果是取数指令，执行步骤73；

步骤73，用块地址的低位索引访问预测表，设置取数指令预测表对应项的值为1，表示对应Cache块会被取数指令用到；

步骤74，用块地址的低位索引访问预测表，查询预测装置的预测结果，查询结果是对应项为1，则预测该存数指令会被后面的取数指令用到，预测结果为写高速缓存，如果对应项是0，则预测该存数指令不会被后面的取数指令用到，预测结果为写低层存储系统。

下面列举两个本发明对具体访存指令的处理的例子。通过两个失效存数指令处理的例子来具体说明如何通过本发明提到的高速缓存失效的处理器访存指令处理方法处理失效的访存指令。

例1.访存指令0x9a00000208b0801c3eb0(其中op域为0x9a、paddr域为0x00000208b0、value域为0x801c3eb0)，访问高速缓存失效。进入存储管理队列，置存储管理队列对应项命中域的值为0。从存储管理队列发送到访存失效队列，并从存储管理队列退出。该失效指令op域为0x9a的内部操作码表示是存数指令且访问模式为双字(8个字节)。数据Cache的Cache块大小为32字节，则Cache块地址(表示访问哪个Cache块)为paddr的高35位即0x000001045，Cache块内地址(表示从Cache块的哪个字节开始访问)为paddr的低5位即0x10。用失效的存数指令Cache块地址查询访存失效队列，查询结果是访存失效队列第2项与进入的失效存数指令的Cache块地址相同为0x000001045，该项处于MQ_VCIMSS状态，op域为存数指令操作码，bytemask域为0xff00ffff，data域为0x801c3ebc801c3eb8801c3eb4000000080a03eac80a03ea880a03ea480a03ea0，w域为1，age域为0x01。失效存数指令模式为双字、块内地址为0x10表示从Cache块的第16个字节开始存数存8个字节。存数指令进入后执行写操作，该项的bytemask域变为0x11111111表示收集为全修改Cache块，data域变为0x0x801c3ebc801c3eb8801c3eb4801c3eb080a03eac80a03ea880a03ea480a03ea0，age域置为0x00，其他存数指令项age域加1。由于该项处于MQ_VCMISS状态，表示写回队列没有相同Cache块的数据不需要再做查询。收集为全修改Cache块，置对应项状态为MQ_RDY。预测表大小为1K项，因此用块地址的低10位0x45索引访问预测表。预测表对应项为0，预测结果是写低层存储系统。此时写回队列有空项，把访存失效队列的块起始地址0x00000208a0(块地址35位0x000001045拼上块内地址5位0x00)和数据0x801c3ebc801c3eb8801c3eb4801c3eb080a03eac80a03ea880a03ea480a03ea0送到写回队列。该访存指令处理完成，置对应项状态为MQ_EMPTY，退出访存失效队列。

例2.失效的访存指令0x98000208b0801c3eb0(其中op域为0x98、paddr域为0x00000208b4、value域为0x801c3eb0)，访问高速缓存失效。进入存储管理队列，置存储管理队列对应项命中域的值为0。从存储管理队列送到访存失效队列，并从存储管理队列中退出。该失效指令op域为0x98的内部操作码表示是存数指令且访问模式为字(4个字节)。数据Cache的Cache块大小为32字节，则Cache块地址为paddr的高35位即0x000001045，Cache块内地址为paddr的低5位即0x14。用失效存数指令Cache块地址查询访存失效队列，查询结果是访存失效队列没有块地址为0x000001045的项。该失效存数指令进入空项第1项，对应项状态置为MQ_MISS，op域置为存数指令操作码，w域置为1，age域的值置为0x00。失效存数指令模式为双字、块内地址为0x14表示从Cache块的第20个字节开始存数存4个字节，存数指令进入后执行写操作，置bytemask域为0x00f00000，data域为0x000000000000000000000000801c000000000000000000000000000000000000。查询写回队列，在写回队列中没有相同块地址项，置第1项状态为MQ_VCMISS。经过7个时钟周期，访存失效队列又进入7条失效存数指令，都没有与第1项命中，每进入一条失效存数指令第1项的age域的值加1，此时第1项的age域为0x07，在访存失效队列中age最大。访存失效队列满，按照LRU策略选择第1项发出访问低层存储系统的请求，对应项状态置为MQ_MREF。从低层存储系统返回数据0x801c3ebc801c3eb8801c3eb400003eb080a03eac80a03ea880a03ea480a03ea0，该项状态置为MQ_RDY。在访存失效队列中把返回数据与访存失效队列中的存数指令所写数据进行拼合。访存失效队列中bytemask域是1的位置表示被存数指令写过，data域对应字节用存数指令数据，bytemask域是0的位置表示没有被存数指令写过，data域对应字节用低层存储系统返回的数据，拼好的data域数据为0x801c3ebc801c3eb8801c3eb4801c3eb080a03eac80a03ea880a03ea480a03ea0。预测表大小为1K项，因此用块地址的低10位0x45索引访问预测表。预测表对应项为1，预测结果是写高速缓存。完成写高速缓存操作，该访存指令处理完成，置对应项状态为MQ_EMPTY，退出访存失效队列。

最后应说明的是：以上实施例仅用以说明而非限制本发明的技术方案，尽管参照上述实施例对本发明进行了详细说明，本领域的普通技术人员应当理解：依然可以对本发明进行修改或者等同替换，而不脱离本发明的精神和范围的任何修改或局部替换，其均应涵盖在本发明的权利要求范围当中。