数据存储器高速缓存装置及数据存储器高速缓存系统

摘要

一种数据存储器高速缓存装置，其高速缓存单元(117)，以16字节宽的行单位对主存储装置(131)进行数据的读写，以各行所含的4字节宽的小区域单位对MPU(113)进行数据的读写。在MPU(113)执行push命令时，若包含保持应向MPU(113)输入的数据之小区域的行中产生高速缓存错误(S1中为“否”)，则高速缓存单元(117)释放该行(S301)。在应写入从MPU(113)送来的数据的小区域与地址大的侧即写入早侧的行边界相邻时(S56中为“是”)，则高速缓存单元(117)不进行回填，在该小区域与行边界不相邻时(S56中为“否”)，则进行回填(S21)。这样，可以使存储器存取速度提高。

说明书

技术领域

本发明涉及一种以在CPU对主存储装置存取时避免由于主存储装置的存取速度慢而导致的额外开销，提高性能为目的的数据存储器高速缓存装置及系统。

本发明特别涉及一种存储数据的数据存储器的高速缓冲，更涉及所谓堆栈式存储器，即根据压入弹出命令对地址连续存取(数据的读出或写入)的数据存储器的高速缓存。

背景技术

以往，在为了减少压入弹出(push·pop)命令所需时间，在高速缓存中不保持压入弹出后不需要数据的堆栈式(stack)高速缓存的控制方式及堆栈式高速缓存中，例如提出了一种堆栈式高速缓存的控制方式，是在包括作为主存储装置上的数据结构支持最后输入的数据最先输出的堆栈结构、以向堆栈的数据输入作为压入、从上述堆栈的数据输出作为弹出、区别于其他的数据写入/读出而进行数据处理的微计算机的微计算机系统中，所具有的特征是：上述微计算机在压入时，取代上述主存储装置而保持该地址与数据的数组，将未被压入到上述主存储装置的保持数据，瞄准上述微计算机未向外部存取时压入到上述主存储装置中；上述微计算机在弹出时如果保持有该数据，则取代上述主存储装置将该数据向上述微计算机输出，由于将上述微计算机的弹出后不需要的数据置换为后来有弹出可能性的堆栈底部的数据，瞄准上述微计算机未向外部存取时，而从上述主存储装置中弹出(例如，参照专利文献1)。

然而，在上述以往的堆栈式高速缓存系统及堆栈式高速缓存控制方法中，丝毫没有改变以针对通常的数据存储器的随机存取为前提的存储器存取高速化方法，不能活用具有所谓堆栈式存储器的规则性的存取特征，在达到高速化的方面存在问题。

该情况尤其在适合近年普时计算(Ubiquitous Computing)等的需求正在增大的Java(注册商标)系统等堆栈式存取的比重大的存储器系统中，成为特别大的问题。接下来对具体问题进行说明。

(第1问题)

例如，假设针对堆栈的数据压入在主存储装置上的存储器地址的增加方向进行，再有假设该堆栈已被高速缓存到于高速缓冲存储器内。而且假设由某数据A的压入导致高速缓存错误发生。在该条件下，从主存储装置向高速缓冲存储器读入由发生了高速缓存错误的存储器地址构成的1个高速缓存单位量的新数据存储器的内容。

在图35中表示该状态。图35表示地址90的存储区域内有堆栈指针913，并已将数据A压入该地址90的存储区域内的状态。此时，如图35所示，利用数据A的压入，堆栈指针913自地址89的存储区域向地址90的存储区域移动。

而且，再如同图35所示，地址90、91、92、93的存储区域为1个高速缓存单位，由于该1个高速缓存单位的地址90的存储区域首次被存取，故由该地址90、91、92、93的存储区域构成的1个高速缓存单位被从主存储装置读入到高速缓冲存储器内。

然而，读入该高速缓冲存储器内的1高速缓存单位量的新数据存储器的内容，只要遵从堆栈存取的规则性，则是根据接下来进行的数据压入而进行改写的内容，而决不是没有读出过的数据。而且，这样将决不是没有读出过的数据从主存储装置读入高速缓冲存储器内，成为实现高速化的障碍。

(第2问题)

与上述情况相反，假设针对堆栈的数据弹出在主存储装置上的存储器地址的减少方向上进行，再有假设该堆栈已被高速缓存于高速缓冲存储器内。而且假设由某数据A的弹出导致高速缓存错误发生。在该条件下，从高速缓冲存储器向主存储装置回写(write back)由比发生了高速缓存错误的存储器地址还大的存储器地址构成的1个高速缓存单位量的数据存储器的内容。

在图36中表示该状态。如图36所示，通过数据B的弹出，堆栈指针923从地址90的存储区域向地址89的存储区域移动。而且，又如同图36所示，地址90、91、92、93的存储区域为1个高速缓存单位，由于堆栈指针向该1个高速缓存单位以外的地址89的存储区域移动，故由该地址90、91、92、93的存储区域构成的1个高速缓存单位被从高速缓冲存储器回写到主存储装置内，释放高速缓冲存储器。

然而，回写到该主存储装置内的1高速缓存单位量的数据存储器的内容，只要遵从堆栈存取的规则性，为通过已进行的数据弹出而读出的内容，决不会再被读出。而且将这种决不会读出的数据从高速缓冲存储器回写到主存储装置的操作，成为实现高速化的障碍。

(第3问题)

另外，假设针对堆栈的数据压入在主存储装置上的存储器地址的增加方向进行，再有假设该堆栈已被高速缓存于高速缓冲存储器内。而且，假设某数据C、D、··、E的压入连续执行。在该条件下，在作为针对目前的堆栈进行压入·弹出的区域的比堆栈指针所表示的地址还低的存储区域内，存储有大量的被堆栈压入的数据，在本例中为C或D，该低地址的存储区域内存储的数据在短暂的时间内利用弹出而被读出的可能性非常低。

在图37中表示该状态。图37表示地址194的存储区域内有堆栈指针933，从远在下方的例如地址80的存储区域到该地址194的存储区域，连续压入C、D、··、E等数据的状态。此时如图37所示，通常从地址80到地址83的1个高速缓存单位只要高速缓冲存储器未满，就直接占据高速缓冲存储器区域，不回写到主存储装置内。而且，当高速缓冲存储器满了时才开始向主存储装置回写，为了其他的存储区域而将高速缓冲存储器腾出。

这样，高速缓冲存储器为零，产生对新的高速缓冲存储器的要求之后才进行回写，成为实现高速化的障碍。

例如，如图37所示，比作为目前堆栈指针933位置的地址194的存储区域远在下方的存储区域，例如地址80～83的存储区域暂时由弹出而被读出的可能性非常低。因此，与专利文献1所揭示的以往技术不同，例如可以将作为地址80～83的存储区域的1个高速缓存单位的高速缓冲存储器的内容预先回写到主存储装置内的操作，可以设想作为一种解决方法。由此，比在高速缓冲存储器没有余量的阶段，匆忙将高速缓冲存储器的内容写入到主存储装置中，以在高速缓冲存储器内形成空余区域的方法可以期待提高存储器的存取速度。

(第4问题)

假设针对堆栈的数据弹出在主存储装置上的存储器地址的减少方向上进行，再有假设该堆栈已被高速缓存于高速缓冲存储器内。而且，假设某数据F、G、··、H的弹出连续执行。在该条件下，被堆栈压入作为针对目前的堆栈进行压入·弹出的区域的比堆栈指针所表示的地址还低的存储区域，例如在本例中为84～87的存储区域内的数据，连续通过弹出而马上被读出的可能性非常高。

在图38中表示该状态。图38表示地址91的存储区域内有堆栈指针943，从较上面例如地址196的存储区域到该地址91的存储区域，连续弹出F、G、··、H等数据的状态。此时如图38所示，通常从地址84到地址87为止的1个高速缓存单位只要属于该区域的1个存储器，例如地址87的存储区域只要没有通过弹出的执行进行存取，就不从主存储装置向高速缓冲存储器区域读入。而且，例如在该地址87的存储区域通过弹出的执行进行存取时才开始从主存储装置向高速缓冲存储器上读出的操作。

这样，在属于1个新的高速缓存单位的区域开始存取，发生了针对1个新的高速缓存区域的数据要求之后，从存储区域向高速缓冲存储区域进行数据的读入，成为实现高速化的障碍。

例如，如图38所示，作为紧接目前堆栈指针943的位置的地址91的存储区域之下的存储区域，例如占据地址84～87的存储区域的1个高速缓存单位，利用连续弹出而被马上读出的可能性非常高。因此，与专利文献1所揭示的以往技术不同，例如可以将作为这种地址84～87的存储区域的1个高速缓存单位的数据预先从主存储装置读入高速缓冲存储器内的操作，设想为一种解决方法。由此，比在针对高速缓冲存储器上没有的存储区域进行存取的阶段，匆忙将主存储装置的内容读入高速缓冲存储器中的方法，可期待提高存储器的存取速度。

专利文献1：特开平5-143330号公报

发明内容

本发明鉴于上述问题点，其目的在于提供一种可以提高存储器存取速度的数据存储器高速缓存装置及数据存储器高速缓存系统。

为了解决上述问题，本发明之一是一种数据存储器高速缓存装置，其介于运算单元与该运算单元存取的主存储装置之间使用，包括：数据保持部，其具有用于保持数据的多个数据区域，上述多个数据区域每一个所保持的数据对上述主存储装置临时读写，上述多个数据区域每一个被分割成多个小区域，上述多个小区域每一个所保持的数据对上述运算单元临时读写；和控制部，在有来自上述运算单元的、对上述主存储装置的连续地址进行数据写入的连续写入请求，且作为与上述运算单元输出的地址对应的数据区域的对象数据区域中产生高速缓存错误时，释放上述对象数据区域之后，在作为上述对象数据区域中的与上述运算单元输出的地址对应的小区域之对象小区域，与作为按照地址的顺序位于上述连续写入的先写方向的上述对象数据区域的边界的数据区域边界相邻时，不进行从上述主存储装置向上述对象数据区域的数据读入，将上述运算单元输出的数据写入上述对象小区域，而在上述对象小区域与上述数据区域边界不相邻时，进行从上述主存储装置向上述对象数据区域的数据读入，并将上述运算单元输出的数据写入上述对象小区域。

根据该发明，由于控制部在从运算单元向连续地址进行连续写入时发生了高速缓存错误的情况下，对要进行写入的数据区域，在该数据区域的释放后不进行来自主存储装置的无用数据的读入，故提高存储器存取速度。再有，控制部根据应进行写入的小区域是否与数据区域边界相邻，来选择是否在释放后的数据区域中省略数据的读入。即，控制部在应进行写入的小区域不是数据区域边界的情况下发生了高速缓存错误时，在释放后的数据区域中进行来自主存储装置的数据读入。因此，运算单元不仅可以从对应于与数据区域边界相邻的小区域的地址开始，也可以从对应于与数据区域边界不相邻的小区域的地址开始连续写入。

本发明之二是在本发明之一所述的数据存储器高速缓存装置中，上述控制部具备：压入存取检测部，其检测来自上述运算单元的上述连续写入请求；高速缓存错误判定部，其在上述压入存取检测部检测出上述连续写入请求时，对上述对象数据区域判定高速缓存错误的有无；边界判定部，其在上述压入存取检测部检测出上述连续写入请求时，判定上述对象小区域是否与上述数据区域边界相邻；数据区域释放部，其在上述高速缓存错误判定部判定了上述高速缓存错误发生时，释放上述对象数据区域；回填部，其在上述数据区域释放部释放了上述对象数据区域的情况下上述边界判定部的判定为否定时，从上述主存储装置向上述数据区域释放部已释放的上述对象数据区域读入数据，在上述边界判定部的判定为肯定时，不从上述主存储装置向上述数据区域释放部已释放的上述对象数据区域读入数据；和数据写入部，其在上述压入存取检测部检测出上述连续写入请求时，将上述运算单元输出的数据写入上述对象小区域内。

根据该发明，压入存取检测部检测出连续写入的要求，高速缓存错误判定部对对象数据区域判定高速缓存错误的有无，边界判定部判定对象小区域与数据区域边界是否相邻，数据区域释放部根据高速缓存错误判定部的判定释放对象数据区域，回填部根据边界判定部的判定，进行向已被释放的对象数据区域的数据写入，数据写入部将来自运算单元的数据写入对象小区域内。因此，控制部根据应进行数据写入的小区域与数据区域边界是否相邻，可以容易地实现省略向释放后的数据区域中写入数据的处理。

本发明之三是在本发明之二所述的数据存储器高速缓存装置中，上述数据保持部还具备多个有效标志保持部，其保持分别表示上述多个数据区域的释放或未释放的多个有效标志；上述回填部即使在对应于上述对象数据区域的有效标志设于表示释放一侧的情况下，也在上述边界判定部的判定为否定时，从上述主存储装置向上述对象数据区域读入数据，在上述边界判定部的判定为肯定时不从上述主存储装置向上述对象数据区域读入数据。

根据该发明，数据保持部具备有效标志保持部，回填部不只是在对象数据区域未释放的情况下，即使在对应于对象数据区域的有效标志表示对象数据区域释放的情况下，也根据对象小区域的位置来选择是否进行从上述主存储装置向上述对象数据区域的数据读入。因此，即使在对象数据区域正释放的情况下，也可以回避无用的读入，由此进一步提高存储器存取速度。另外，由于回填部在对象小区域和数据区域边界不相邻时进行从上述主存储装置向上述对象数据区域的数据读入，故运算单元不仅可以从对应于与数据区域边界相邻的小区域的地址开始，也可以从对应于与数据区域边界不相邻的小区域的地址开始连续写入。

本发明之四是在本发明之二或三所述的数据存储器高速缓存装置中，上述数据保持部还具备多个堆栈标志保持部，其保持分别表示上述多个数据区域使用于连续写入或连续读出中哪一个的多个堆栈标志；上述控制部还具备堆栈标志设定部，其当上述边界判定部的判定为肯定时，上述数据写入部结束上述数据的写入后将与上述对象数据区域对应的堆栈标志设定在肯定侧，当上述边界判定部的判定为否定时，上述数据写入部结束上述数据的写入后不变更与上述对象数据区域对应的堆栈标志。

根据该发明，数据保持部具备堆栈标志保持部，控制部具备在数据写入后根据对象小区域的位置操作堆栈标志的堆栈标志设定部。因此，控制部在连续写入的过程中，采用在由高速缓存错误发生导致该数据区域释放之前，利用数据总线的不使用期间将结束了写入的数据区域的数据预先回写到主存储装置中的构成时，通过利用堆栈标志，可以避免对未分配为堆栈的数据区域的数据进行无用回写。再有，控制部即使在连续读出的过程中，采用预先从主存储区域向读出前的数据区域读入数据的构成时，也通过利用堆栈标志，可以避免对未分配为堆栈的数据区域的数据进行无用回写。

本发明之五是在本发明之二～四中任一项所述的数据存储器高速缓存装置中，上述多个数据区域与上述主存储装置的地址中位部分对应，上述多个小区域每一个与上述主存储装置的地址的下位部分对应，上述主存储装置的地址的上述中位部分的同一值对应于1个以上的数据区域；上述数据保持部还具备多个标签保持部，其保持分别表示保持上述多个数据区域的数据地址的上位部分的多个标签；上述控制部还具备地址抽出部，其从上述运算单元输出的地址中抽出上述上位部分、上述中位部分与上述下位部分；上述高速缓存错误判定部分别将与对应于上述地址抽出部抽出的上述中位部分的上述1个以上数据区域每一个建立了关联的标签所表示的值、和上述地址抽出部抽出的上述上位部分进行比较，在都不一致的情况下判定为发生了上述高速缓存错误；上述边界判定部通过判定上述多个小区域中与上述地址抽出部抽出的上述下位部分对应的小区域是否与按照地址顺序而位于该小区域所属的数据区域的上述连续写入的先写方向的边界相邻，来判定上述对象小区域是否与上述数据区域边界相邻；上述数据区域释放部在上述压入存取检测部检测出上述连续写入请求且上述高速缓存错误判定部判定出上述高速缓存错误发生时，通过释放与上述地址抽出部抽出的上述中位部分对应的上述1个以上数据区域的任意一个，来释放上述对象数据区域；上述控制部还具备标签更新部，其将与上述数据区域释放部释放的上述数据区域对应的标签更新为上述地址抽出部抽出的上述上位部分；上述数据写入部，作为上述对象小区域，采用与上述地址抽出部抽出的上述中位部分对应的、并且在保持上述地址抽出部抽出的上述上位部分的标签所对应的数据区域中与上述地址抽出部抽出的上述下位部分对应的小区域，并向该对象小区域写入上述运算单元输出的数据。

根据该发明，数据保持部具备多个标签保持部，地址抽出部从运算单元输出的地址中抽出各地址部分，高速缓存错误判定部根据地址抽出部抽出的地址部分和对应于数据区域的标签来进行高速缓存错误的判定，边界判定部根据抽出的地址部分判定对象小区域与数据区域边界是否相邻，数据区域释放部根据地址抽出部抽出的地址部分进行数据区域的释放，标签更新部更新与释放后的数据区域对应的标签，数据写入部根据地址抽出部抽出的地址部分和标签进行运算单元输出的数据的写入。因此，控制部根据应进行写入的小区域与数据区域边界是否相邻，可以更容易且适宜地实现在释放后的数据区域中省略数据的读入的处理及数据的写入处理。

而且，在本发明中，作为主存储装置的地址的下位部分，如在实施方式中各小区域表示从地址的最下位位数除去第1及第2位后的与第3及第4位对应的示例那样，是中位部分的与下位侧相邻的部分，并不一定包含到最下位。

本发明之六是一种数据存储器高速缓存装置，其介于运算单元与该运算单元存取的主存储装置之间使用，包括：数据保持部，其具有与上述主存储装置的地址对应的、并用于保持对应地址的数据的多个数据区域；和控制部，在施行从上述主存储装置的连续地址向上述运算单元进行数据读出的连续读出时，释放上述数据保持部中上述连续读出已结束的数据区域，而不将上述连续读出已结束的数据区域所保持的数据向上述主存储装置回写。

根据该发明，控制部在由运算单元从连续地址进行连续读出时，在不将该数据区域保持的数据向主存储装置回写的情况下，将进行过读出的数据区域释放。保持由连续读出也不会再次读出的数据之数据区域，是即使释放也没有妨碍的区域，且该数据区域所保持的数据为无用的数据，是没有写回主存储装置的必要。这样，由于控制部不进行数据的回写就释放保持无用数据的数据区域，故对运算单元的动作不产生障碍，可以提高存储器存取速度。

本发明之七是在本发明之六所述的数据存储器高速缓存装置中，上述多个数据区域每一个所保持的数据对上述主存储装置临时读写，上述多个数据区域每一个被分割成多个小区域，上述多个小区域每一个所保持的数据对上述运算单元临时读写；上述控制部在有从上述运算单元向上述主存储装置的连续地址进行数据写入的连续写入请求时，从在作为从与上述运算单元输出的地址对应的数据区域的对象数据区域中与上述运算单元输出的上述地址对应的小区域的对象小区域，向上述运算单元进行数据读出，同时在对象小区域与按照地址的顺序位于上述连续写入的后写方向的上述对象数据区域的边界的数据区域边界相邻时，在不进行从上述对象数据区域向上述主存储装置的数据回写的情况下释放上述对象数据区域，在上述对象小区域与上述数据区域边界不相邻时，不释放上述对象数据区域。

根据该发明，控制部根据读出对象即小区域与数据区域边界是否相邻来选择是否进行对象数据区域的释放。即，控制部在读出对象即小区域位于数据区域边界时进行对象数据区域的释放，在不位于数据区域边界时不进行释放。因此，运算单元不仅可以从对应于与数据区域边界相邻的小区域的地址开始，也可以从对应于与数据区域边界不相邻的小区域的地址开始连续写入。

本发明之八是在本发明之七所述的数据存储器高速缓存装置中，上述数据保持部还具备多个有效标志保持部，其保持分别表示上述多个数据区域的释放或未释放的多个有效标志；上述控制部通过在表示释放一侧设定与上述对象数据区域对应的有效标志，来释放上述对象数据区域。

根据该发明，由于控制部通过在给定侧设定有效标志来进行对象数据区域的释放，故可以容易进行对象数据区域的释放。

本发明之九是在本发明之八所述的数据存储器高速缓存装置中，上述控制部具备：弹出存取检测部，其检测来自上述运算单元的上述连续读出请求；边界判定部，其在上述弹出存取检测部检测出上述连续读出请求时，判定上述对象小区域与上述数据区域边界是否相邻；数据读出部，其在上述弹出存取检测部检测出上述连续读出请求时，向上述运算单元读出上述对象小区域的数据；有效标志设定部，其当上述边界判定部的判定为肯定时，由上述数据读出部读出了上述数据后，不进行从上述对象数据区域向上述主存储装置的数据回写，并将与上述对象数据区域对应的上述有效标志设定于表示释放一侧，在上述对象小区域与上述数据区域边界不相邻时，不变更与上述对象数据区域对应的上述有效标志。

根据该发明，弹出存取检测部检测连续读出的要求，边界判定部判定对象小区域和数据区域边界是否相邻，数据读出部向运算单元读出对象小区域的数据，有效标志设定部根据边界判定部的判定进行有效标志的设定。因此，控制部根据作为读出对象的小区域和数据区域边界是否相邻，可以容易实现释放对象数据区域的处理。

本发明之十是一种数据存储器高速缓存装置，其介于运算单元与该运算单元存取的主存储装置之间使用，包括：数据保持部，其具有用于保持数据的多个数据区域，上述多个数据区域每一个保持的数据对上述主存储装置临时读写，上述多个数据区域每一个被分割成多个小区域，上述多个小区域每一个所保持的数据对上述运算单元临时读写；和控制部，在有从上述运算单元向上述主存储装置的连续地址进行数据写入的连续写入请求时，从在作为与上述运算单元输出的地址对应的数据区域的对象数据区域中与上述运算单元输出的上述地址对应的小区域的对象小区域，进行向上述运算单元的数据读出，同时在上述对象小区域与按照地址顺序位于上述连续写入的后写方向的上述对象数据区域的边界的数据区域边界相邻时，在之后释放上述对象数据区域时进行禁止从上述对象数据区域向上述主存储装置的数据回写的设定，在上述对象小区域和上述数据区域边界不相邻时不进行上述设定。

根据该发明，由于控制部在由运算单元从连续地址进行连续读出时，对进行过读出的数据区域，进行为禁止伴随该数据区域的释放而向主存储装置回写数据的设定，故提高存储器存取速度。再有，控制部根据作为读出对象的小区域和数据区域边界是否相邻来选择是否进行禁止回写的设定。即，控制部在作为读出对象的小区域位于数据区域边界时进行禁止回写的设定，在不位于数据区域边界时不进行设定。因此，运算单元不仅可以从对应于与数据区域边界相邻的小区域的地址开始，也可以从对应于与数据区域边界不相邻的小区域的地址开始连续写入。

本发明之十一是在本发明之十所述的数据存储器高速缓存装置中，上述数据保持部还具备多个改动标志保持部，其保持分别表示上述多个数据区域所保持的数据和上述主存储装置对应的地址所保持的数据之间的一致及不一致的多个改动标志；上述控制部通过将与上述对象数据区域对应的改动标志设定于表示上述一致一侧来进行上述设定。

根据该发明，数据保持部具备改动标志保持部，控制部通过将改动标志设定在给定侧，来进行用于禁止回写的设定。因此，控制部可以容易进行禁止回写用的设定。

本发明之十二是在本发明之十一所述的数据存储器高速缓存装置中，上述控制部具备：弹出存取检测部，其检测来自上述运算单元的上述连续读出请求；边界判定部，其在上述弹出存取检测部检测出上述连续读出请求时，判定上述对象小区域与上述数据区域边界是否相邻；数据读出部，其在上述弹出存取检测部检测出上述连续读出请求时，向上述运算单元读出上述对象小区域的数据；和改动标志设定部，其当上述边界判定部的判定为肯定时，由上述数据读出部读出了上述数据后，将与上述对象数据区域对应的上述改动标志设定于表示上述一致一侧，当上述边界判定部的判定为否定时，不变更与上述对象数据区域对应的上述改动标志。

根据该发明，弹出存取检测部检测连续读出的要求，边界判定部判定对象小区域和数据区域边界是否相邻，数据读出部向运算单元读出对象小区域的数据，改动标志设定部根据边界判定部的判定进行改动标志的设定。因此，控制部根据作为读出对象的小区域和数据区域边界是否相邻，可以容易地实现设定回写禁止的处理。

本发明之十三是在本发明之九或十二所述的数据存储器高速缓存装置中，上述数据保持部还具备多个堆栈标志保持部，其保持分别表示上述多个数据区域使用于连续写入或连续读出中哪一个的多个堆栈标志；上述控制部还具备堆栈标志设定部，其当上述边界判定部的判定为肯定时，上述数据读出部结束上述数据的读出后将与上述对象数据区域对应的堆栈标志设定在肯定侧，当上述边界判定部的判定为否定时，上述数据读出部结束上述数据的读出后不变更与上述对象数据区域对应的堆栈标志。

根据该发明，数据保持部具备堆栈标志保持部，控制部具备在数据写入后根据对象小区域的位置操作堆栈标志的堆栈标志设定部。因此，控制部在连续读出的过程中，采用在由高速缓存错误发生导致该数据区域释放之前，利用数据总线的不使用期间将结束了写入的数据区域的数据预先返写回主存储装置中的构成时，通过利用堆栈标志，可以避免对未分配为堆栈的数据区域的数据进行无用的回写的情况。

本发明之十四是在本发明之九、十二或十三所述的数据存储器高速缓存装置中，上述多个数据区域与上述主存储装置的地址中位部分对应，上述多个小区域每一个与上述主存储装置的地址的下位部分对应，上述主存储装置的地址的上述中位部分的同一值对应于1个以上的数据区域；上述数据保持部还具备多个标签保持部，其保持分别表示保持上述多个数据区域的数据地址的上位部分的多个标签；上述控制部还具备地址抽出部，其从上述运算单元输出的地址中抽出上述上位部分、上述中位部分与上述下位部分；上述边界判定部通过判定上述多个小区域中与上述地址抽出部抽出的上述下位部分对应的小区域、和按照地址顺序位于该小区域所属的数据区域的上述连续读出的后读方向之边界是否相邻，来判定上述对象小区域与上述数据区域边界是否相邻；上述数据读出部，作为上述对象小区域，采用与上述地址抽出部抽出的上述中位部分对应的、并且和对应于表示上述地址抽出部抽出的上述上位部分的标签之数据区域中与上述地址抽出部抽出的上述下位部分对应的小区域，并向上述运算单元读出该对象小区域的数据。

根据该发明，数据保持部具备多个标签保持部，地址抽出部从运算单元数据的地址中抽出各地址部分，边界判定部根据抽出的地址部分判定对象小区域和数据区域边界是否相邻，数据读出部根据地址抽出部抽出的地址部分及标签，进行向运算单元的数据读出。因此，控制部可以更容易实现连续读出结束的无用数据区域的无回写的释放，或伴随该无用数据区域的释放之回写的禁止设定。

本发明之十五是一种数据存储器高速缓存装置，其介于运算单元与该运算单元存取的主存储装置之间使用，包括：数据保持部，其具有与上述主存储装置对应的、并用于保持对应地址的数据的多个数据区域；和控制部，在执行从上述运算单元向上述主存储装置的连续地址的数据写入即连续写入的期间，并且不使用在上述数据保持部与上述主存储装置之间转移数据用的数据总线的期间，进行从按照地址顺序比目前正进行的连续写入还位于连续写入早的方向上的上述数据保持部中的数据区域向上述主存储装置的数据回写。

根据该发明，控制部在执行连续写入期间内，将按照地址顺序比目前正进行的连续写入还位于连续写入早的方向的数据区域之数据，在释放该数据区域之前利用数据总线的不使用期间(即空置时间)，预先向主存储装置回写。由此，控制部对于已结束连续写入的可能性高，而立即进行读出的可能性低的数据区域，在之后释放时没有进行回写的必要，故提高存储器存取速度。

本发明之十六是在本发明之十五所述的数据存储器高速缓存装置中，上述控制部具备：压入存取检测部，其检测来自上述运算单元的上述连续写入请求；偏置计算部，在上述压入存取检测部检测出上述连续写入请求时，计算从上述运算单元输出的地址向上述连续写入的先写方向偏离给定间隔的地址即偏置地址；高速缓存错误判定部，其对上述偏置地址判定高速缓存错误的有无；转送忙判定部，其判定上述数据总线是否在使用中；和回写部，其当上述高速缓存错误判定部判定为无上述高速缓存错误，且上述转送忙判定部判定为上述数据总线不使用时，进行从上述偏置地址对应的数据区域向上述主存储装置的数据回写。

根据该发明，压入存取检测部检测连续写入请求，偏置计算部计算偏置地址，高速缓存错误判定部对偏置地址判定高速缓存错误的有无，转送忙判定部判定数据总线是否在使用中，回写部根据高速缓存错误判定部的判定与转送忙判定部的判定，进行从对应于偏置地址的数据区域向主存储装置的数据回写。因此，控制部可以容易且适当地实现将连续写入已结束的数据区域的可能性高的数据区域的数据在释放该数据区域之前，利用数据总线的不使用期间，预先向主存储装置回写。

本发明之十七是在本发明之十六所述的数据存储器高速缓存装置中，上述多个数据区域与上述主存储装置的地址中位部分对应，且上述中位部分的同一值对应于1个以上的数据区域；上述多个数据区域每一个被分割为与上述地址的下位部分对应的多个小区域；上述多个数据区域每一个保持的数据对上述主存储装置临时读写，上述多个小区域每一个保持的数据对上述运算单元临时读写；上述数据保持部还具备多个标签保持部，其保持分别表示保持上述多个数据区域的数据地址的上位部分的多个标签；上述控制部还具备地址抽出部，其从上述运算单元输出的地址中抽出上述上位部分、上述中位部分与上述下位部分；上述偏置计算部在上述压入存取检测部检测出上述连续写入请求时，将从由上述地址抽出部抽出的上述中位部分与上述上位部分所表现的地址向上述连续写入的先写方向偏离给定间隔的地址作为上述偏置地址进行计算；上述高速缓存错误判定部将与对应于上述偏置地址的上述中位部分的上述1个以上区域每一个对应的标签所表示的值、和上述偏置地址的上述上位部分进行比较，在都不一致的情况下判定为产生了高速缓存错误。    

根据该发明，数据保持部具备多个标签保持部，地址抽出部从运算单元数据的地址中抽出各地址部分，偏置计算部根据地址抽出部抽出的地址部分计算偏置地址，高速缓存错误判定部根据地址抽出部抽出的地址部分和对应于数据区域的标签来进行高速缓存错误的判定。因此，控制部可以容易地进行偏置地址的计算及高速缓存错误的判定。

本发明之十八是一种数据存储器高速缓存装置，其介于运算单元与该运算单元存取的主存储装置之间使用，包括：数据保持部，其具有与上述主存储装置的地址对应的、并用来保持对应地址的数据的多个数据区域；和控制部，其在执行从上述主存储装置的连续地址向上述运算单元进行数据读出的连续读出期间，且在上述数据保持部与上述主存储装置之间不使用转移数据用的数据总线期间，进行从按照地址顺序比目前正进行的连续读出还位于连续读出早的方向之上的上述数据保持部中的数据区域向上述主存储装置的数据回写。

根据该发明，控制部在执行连续读出期间内，将从按照地址顺序比目前正进行的连续读出还位于连续读出早的方向之上的数据区域的数据在释放该数据区域之前，利用数据总线的不使用期间(即空置时间)，预先向主存储装置回写。由此，控制部对于已结束连续读出的可能性高、进行再次读出的可能性低的数据区域，在之后释放时没有进行回写的必要，故提高存储器存取速度。

本发明之十九是在本发明之十八所述的数据存储器高速缓存装置中，上述控制部具备：弹出存取检测部，检测来自上述运算单元的上述连续读出请求；偏置计算部，在上述弹出存取检测部检测出上述连续读出请求时，计算从上述运算单元输出的地址向上述连续读出的先读方向偏离给定间隔的地址即偏置地址；高速缓存错误判定部，其对上述偏置地址判定高速缓存错误的有无；转送忙判定部，其判定上述数据总线是否在使用中的；和回写部，其在上述高速缓存错误判定部判定为无上述高速缓存错误，且上述转送忙判定部判定为上述数据总线不使用时，进行从上述偏置地址对应的数据区域向上述主存储装置的数据回写。

根据该发明，弹出存取检测部检测连续读出请求，偏置计算部计算偏置地址，高速缓存错误判定部对偏置地址判定高速缓存错误的有无，转送忙判定部判定数据总线是否在使用中，回写部根据高速缓存错误判定部的判定与转送忙判定部的判定，进行从对应于偏置地址的数据区域向主存储装置的数据回写。因此，控制部可以容易且适当地实现将连续读出已结束的数据区域即可能性高的数据区域的数据在释放该数据区域之前，利用数据总线的不使用期间，预先向主存储装置回写。

本发明之二十是在本发明之十九所述的数据存储器高速缓存装置中，上述多个数据区域与上述主存储装置的地址中位部分对应，且上述中位部分的同一值对应于1个以上的数据区域；上述多个数据区域每一个被分割为与上述地址的下位部分对应的多个小区域；上述多个数据区域每一个保持的数据对上述主存储装置临时读写，上述多个小区域每一个保持的数据对上述运算单元临时读写；上述数据保持部还具备多个标签保持部，其保持分别表示保持上述多个数据区域的数据地址的上位部分的多个标签；上述控制部还具备地址抽出部。其从上述运算单元输出的地址中抽出上述上位部分、上述中位部分与上述下位部分；上述偏置计算部在上述弹出存取检测部检测出上述连续读出请求时，将从由上述地址抽出部抽出的上述中位部分与上述上位部分所表现的地址向上述连续读出的先读方向偏离给定间隔的地址作为上述偏置地址进行计算；上述高速缓存错误判定部将与对应于上述偏置地址的上述中位部分的上述1个以上区域每一个对应的标签所表示的值、和上述偏置地址的上述上位部分进行比较，在都不一致的情况下判定为产生了高速缓存错误。    

根据该发明，数据保持部具备多个标签保持部，地址抽出部从运算单元数据的地址中抽出各地址部分，偏置计算部根据地址抽出部抽出的地址部分计算偏置地址，高速缓存错误判定部根据地址抽出部抽出的地址部分和对应于数据区域的标签来进行高速缓存错误的判定。因此，控制部可以容易进行偏置地址的计算及高速缓存错误的判定。

本发明之二十一是在本发明之十六、十七、十九或二十所述的数据存储器高速缓存装置中，上述数据保持部还具备多个堆栈标志保持部，其保持分别表示上述多个数据区域是否使用于连续写入或连续读出的任一种的多个堆栈标志；上述回写部在上述高速缓存错误判定部判定无上述高速缓存错误，且上述转送忙判定部判定上述数据总线不使用的情况下，只要将与对应于上述偏置地址的数据区域对应的上述堆栈标志设于肯定侧，就进行从与上述偏置地址对应的数据区域向上述主存储装置的数据的回写。

根据该发明，数据保持部具备堆栈标志保持部，回写部也参照堆栈标志来选择是否进行数据的回写。由此，可以避免回写部对有连续写入以外的写入之数据区域或有连续读出以外的读出之数据区域进行无用的回写的情况。

本发明之二十二是在本发明之十六、十七、十九、二十或二十一所述的数据存储器高速缓存装置中，上述数据保持部还具备多个有效标志保持部，其保持分别表示上述多个数据区域的释放或未释放之多个有效标志；上述回写部在上述高速缓存错误判定部判定无上述高速缓存错误，且上述转送忙判定部判定上述数据总线不使用的情况下，只要将与对应于上述偏置地址的数据区域对应的上述有效标志设于表示未释放一侧，就进行从与上述偏置地址对应的数据区域向上述主存储装置的数据的回写。

根据该发明，数据保持部具备有效标志保持部，回写部也参照有效标志来选择是否进行数据的回写。由此，可以避免回写部对已释放的数据区域进行无用的回写之情况。

本发明之二十三是一种数据存储器高速缓存装置，其介于运算单元与该运算单元存取的主存储装置之间使用，包括：数据保持部，其具有与上述主存储装置的地址对应的、并用来保持对应地址的数据的多个数据区域；和控制部，在执行从上述主存储装置的连续地址中读出向上述运算单元传送的数据的连续读出的期间，且在上述数据保持部与上述主存储装置之间不使用转移数据用的数据总线期间，进行从上述主存储装置向按照地址顺序比目前正进行的连续读出还位于连续读出晚的方向之上的上述数据保持部中的数据区域的数据回写。

根据该发明，控制部在执行连续读出期间内，利用数据总线的不使用期间(即空置时间)，预先从主存储装置向期望在以后能进行读出的数据区域进行数据的读出。由此，控制部可以节省从主存储装置向应读出数据的数据区域读入数据的时间。结果，提高存储器存取速度。

本发明之二十四是在本发明之二十三所述的数据存储器高速缓存装置中，上述控制部具备：弹出存取检测部，其检测来自上述运算单元的上述连续读出要求；偏置计算部，其在上述弹出存取检测部检测出上述连续读出请求时，计算从上述运算单元输出的地址向上述连续读出的后读方向偏离给定间隔的地址即偏置地址；转送忙判定部，其判定上述数据总线是否为使用中；和回填部，在上述转送忙判定部判定为上述数据总线不使用时，从上述主存储装置向对应于上述偏置地址的数据区域进行数据的读入。

根据该发明，弹出存取检测部检测连续读入的要求，偏置计算部计算偏置地址，转移执行部判定数据总线是否在使用中，回填部根据转送忙判定部的判定，将数据从主存储装置读入对应于偏置地址的数据区域。因此，控制部可以容易实现利用数据总线的不使用期间，预先将数据从主存储装置读入期望能进行读出的数据区域之处理。

本发明之二十五是在本发明之二十四所述的数据存储器高速缓存装置中，上述数据保持部还具备多个堆栈标志保持部，其保持分别表示上述多个数据区域是否使用于连续写入或连续读出的任一种之多个堆栈标志；上述回填部在上述转送忙判定部判定上述数据总线不使用的情况下，只要将与对应于上述偏置地址的数据区域对应的上述堆栈标志设于肯定侧，就进行从上述主存储装置向与上述偏置地址对应的数据区域的数据的读入。

根据该发明，数据保持部具备堆栈标志保持部，回填部也参照堆栈标志来选择是否进行数据的读入。由此，可以避免回填部对未成为连续读出对象的数据区域即没有成为连续读入对象的数据区域进行无用的读入之情况。

本发明之二十六是在本发明之二十四或二十五所述的数据存储器高速缓存装置中，上述数据保持部还具备多个有效标志保持部，其保持分别表示上述多个数据区域的释放或未释放之多个有效标志；上述回填部在上述转送忙判定部判定上述数据总线不使用的情况下，只要将与对应于上述偏置地址的数据区域对应的上述有效标志设于表示释放一侧，就进行从上述主存储装置向与上述偏置地址对应的数据区域的数据读入。

根据该发明，数据保持部具备有效标志保持部，回填部也参照有效标志来选择是否进行数据的读入。由此，可以避免回填部对未释放的数据区域进行无用的读入之情况。

本发明之二十七是在本发明之二十四至二十六中任一项所述的数据存储器高速缓存装置中，上述多个数据区域与上述主存储装置的地址中位部分对应，且上述中位部分的同一值对应于1个以上的数据区域；上述多个数据区域每一个被分割为与上述地址的下位部分对应的多个小区域；上述多个数据区域每一个保持的数据对上述主存储装置临时读写，上述多个小区域每一个保持的数据对上述运算单元临时读写；上述数据保持部还具备多个标签保持部，其保持分别表示保持上述多个数据区域的数据地址的上位部分的多个标签；上述控制部还具备地址抽出部，其从上述运算单元输出的地址中抽出上述上位部分、上述中位部分与上述下位部分；上述偏置计算部在上述弹出存取检测部检测出上述连续读出请求时，将从由上述地址抽出部抽出的上述中位部分与上述上位部分表现的地址向上述连续读出的后读方向偏离给定间隔的地址作为上述偏置地址进行计算。

根据该发明，数据保持部具备多个标签保持部，地址抽出部从运算单元输出的地址中抽出各地址部分，偏置计算部根据地址抽出部抽出的地址部分计算偏置地址。由此，控制部可以容易进行偏置地址的计算。

本发明之二十八是在本发明之二十七所述的数据存储器高速缓存装置中，上述控制部还具备：高速缓存错误判定部，其将对应于与上述偏置地址的上述中位部分所对应的上述1个以上数据区域每一个的标签表示的值、和上述偏置地址的上述上位部分进行比较，在都不一致的情况下对上述偏置地址判定高速缓存错误产生；数据区域释放部，其在上述高速缓存错误判定部判定上述高速缓存错误产生时，释放与上述偏置地址的上述中位部分对应的上述1个以上的数据区域的任一个；和标签更新部，其将上述数据区域释放部释放了的上述数据区域对应的标签更新为上述偏置地址的上述上位部分。

根据该发明，高速缓存错误判定部根据偏置地址计算部算出的偏置地址及对应于该偏置地址所对应的数据区域之标签，针对偏置地址进行高速缓存错误的判定，数据区域释放部根据偏置地址计算部算出的偏置地址进行数据区域的释放，标签更新部更新与释放后的数据区域对应的标签。因此，控制部即使在偏置地址存在高速缓存错误，也可以进行从主存储装置向对应于偏置地址的数据区域之数据读入。

本发明之二十九是一种数据存储器高速缓存系统，包括：本发明之一至二十八中任一项所述的数据存储器高速缓存装置；与上述数据存储器高速缓存装置连接的运算单元；及与上述数据存储器高速缓存装置连接且由上述运算单元进行存取的主存储装置。

根据该发明，由于数据存储器高速缓存系统具备本发明的数据存储器高速缓存装置、与该装置连接的运算单元及与该装置连接且由运算单元进行存取的主存储装置，故可以提高存储器存取速度。

如上所述，根据本发明的数据存储器高速缓存装置及数据存储器高速缓存系统，可以提高存储器存取速度。

附图说明

图1是表示本发明的实施方式之数据存储器高速缓存系统的构成框图。

图2是表示push、pop、load、store命令的各命令形式与动作的说明图。

图3是表示由MPU执行的命令与各控制线的状态的关系说明图。

图4是表示相当于本发明的实施方式之数据存储器高速缓存装置的图1的高速缓存单元的构成框图。

图5是表示图4的高速缓存单元的数据保持部的构成框图。

图6是表示图5的数据保持部的行的构成之说明图。

图7是表示valid标志、dirty标志、stack标志的取得组合及其所意味的行的状态的图。

图8是MPU执行随机读出命令时的图1之高速缓存系统的动作顺序图。

图9是表示与随机读·随机写入命令执行时的各行的状态对应的动作内容的说明图。

图10是表示执行行的释放·SP向上方移动时的各行的状态所对应的动作内容之说明图。

图11是MPU执行随机写入命令时的图1之高速缓存系统的动作顺序图。

图12是MPU执行SP相对读出命令时的图1之高速缓存系统的动作顺序图。

图13是表示与SP相对读·SP相对写入命令执行时的各行的状态所对应的动作内容的说明图。

图14是MPU执行SP相对读出命令时的图1的高速缓存系统的动作顺序图。

图15是MPU执行pop命令时的图1之高速缓存系统的动作顺序图。

图16是表示pop命令执行时的各行状态所对应的动作内容的说明图。

图17是表示在MPU执行pop命令时，与图15的处理并行进行的其他处理的动作顺序图。

图18是表示SP远离下方·SP从下方靠近执行时的各行的状态所对应的动作内容的图。

图19是表示在MPU执行pop命令时，与图15的处理并行进行的其他处理的动作顺序图。

图20是MPU执行push命令时的图1之高速缓存系统的动作顺序图。

图21是表示push命令执行时的各行状态所对应的动作内容的说明图。

图22是表示在MPU执行push命令时，与图21的处理并行进行的其他处理的动作顺序图。

图23是表示C语言的堆栈结构图。

图24是表示调用参数刚生成后的堆栈结构图。

图25是表示函数调用刚进行后的堆栈结构图。

图26是表示寄存器保存刚进行后的堆栈结构图。

图27是表示堆栈帧生成刚进行后的堆栈结构图。

图28是表示堆栈帧生成刚进行后的高速缓存行的状态图。

图29是表示随机存取后的高速缓存行的状态图。

图30是表示Java(注册商标)的堆栈结构图。

图31是调用参数生成刚进行后的Java(注册商标)的堆栈结构图。

图32是表示局部变量区域生成刚进行后的Java(注册商标)的堆栈结构图。

图33是表示函数处理中的Java(注册商标)的堆栈结构图。

图34是表示函数处理中的高速缓存行的状态图。

图35是表示在以往的堆栈式高速缓存系统中，在产生了高速缓存错误时采用push将1单位的内容从主存储装置读入高速缓冲存储器内的状态图。

图36是表示在以往的堆栈式高速缓存系统中，在产生了高速缓存错误时采用pop将1单位的内容从主存储装置读入高速缓冲存储器内的状态图。

图37是表示低地址的存储区域内存储的数据暂时通过弹出而读出的可能性非常低的状态图。

图38是表示比堆栈指针表示的地址还低的地址区域马上通过弹出而读出的可能性非常高的状态图。

具体实施方式

以下，参照附图说明有关本专利申请的发明(以后适当称为“本发明”)的实施方式。

(1、系统的构成)

在图1中表示本发明的第1实施方式的数据存储器高速缓存装置及包含该装置的数据存储器高速缓存系统(以后，除了应特别区分的情况，都单称为“高速缓存装置”及“高速缓存系统”)的构成框图。由于命令存储器高速缓存装置及命令存储器高速缓存系统与本发明无直接关系，故省略其说明。

本实施方式的高速缓存系统100主要包括：运算单元113、存储器管理单元115(以后适当称为“MMU115”)、堆栈对应数据高速缓存单元117(以后除了应特别区分的情况外，适当简称为“高速缓存单元117”)、转移控制单元119、主存储装置131。高速缓存单元117相当于本发明的数据存储器高速缓存装置的一实施方式。

运算单元113通常为MPU或(狭义的)CPU或者称为处理器的机构，从命令存储器取出各种运算命令、数据移动命令、控制命令等其他命令，并执行。以后，作为运算单元113的一例，采用MPU，适当称为“MPU113”。当然本发明的运算单元并未限于MPU。

MPU113特别是具有将存储器地址存储的专用寄存器SP(堆栈指针)。将该堆栈指针表示的存储器地址(memory address)称为栈顶(stack top)。另外，作为该堆栈指针，除了专用的SP以外，也可以使用通用的寄存器Rm(寄存器m)。这种安装在将通用CPU作为Java(注册商标)虚拟机使用等情况下是特别有效的。

以后只要不特别产生混淆，就不特别将(堆栈指针(SP))或(堆栈指针(SP)存取)等用语区分为使用专用的SP寄存器的情况与使用通用的寄存器(例如记为Rm或Rn)的情况，用于包含两者的含义。

MPU113，作为数据移动命令的一部分准备push命令(压入命令)、pop命令(弹出命令)、load命令(取出命令)、store命令(存入命令)及其他命令。push命令是让SP的内容减4(即只缩减4)，在该栈顶写4字节数据(从MPU113向存储器写入)的命令。pop命令是从堆栈读例如4字节数据(从存储器向MPU113读出)，并使SP的内容加4的命令。load命令是在距栈顶的相对地址处执行存储器读出的命令。store命令是在距栈顶的相对地址处执行存储器写入的命令。MPU113，作为其他数据移动命令例如准备在直接地址、寄存器间接地址、寄存器相对地址等以各种方法指定的任意地址直接随机进行存储器存取的命令。

图2(a)、(b)、(c)、(d)的左侧“命令”栏中表示这些数据移动命令中代表性的push、pop、load、store命令的各命令形式。push命令是向主存储装置131的连续地址写入数据的命令的具体例。另外，pop命令是从主存储装置131的连续地址读出数据的命令的具体例。图2中示例的命令形式，将通用寄存器Rm或通用寄存器Rn作为堆栈指针使用。再有，在该说明中，令这些命令的存储器存取的单位为4字节，虽然用push/pop命令使在数据移动前后进行堆栈指针的增减的单位值为4，但这是其中一例，也可以为任意值。

图2(a)左侧的“命令”栏中表示push命令的命令形式。在该形式中，MPU113将Rm寄存器作为堆栈指针使用。图2(a)右侧的“动作”栏表示由该命令的执行而进行的动作。

若执行该push命令，则首先，将Rm的内容减4。接着以Rm间接地址指定将Rn寄存器的内容写入到存储器。即，Rn寄存器的内容写入到Rm寄存器内容表示的地址的存储器内。而且，push/pop修饰位置位。该push/pop修饰位的内容，如图1所示，使用于通过控制线从MPU113向高速缓存单元117通知执行push/pop命令。

图2(b)左侧的“命令”栏表示pop命令的命令形式。在该形式中MPU113将Rn寄存器作为堆栈指针使用。图2(b)右侧的“动作”栏表示由执行该命令而进行的动作。

若执行该pop命令，则首先将push/pop修饰位置位。与上述同样，push/pop修饰位的内容用于通过控制线从MPU113向高速缓存单元117通知执行push/pop命令。接着，以Rn间接地址指定将存储器的内容读入Rm寄存器内。即，Rn寄存器的内容所表示地址的存储器的内容被读入Rm寄存器内。而且，Rn的内容加4(即，只增加4)。

图2(c)左侧的“命令”栏表示load命令的命令形式。在该形式中MPU113将Rn寄存器作为堆栈指针使用。图2(c)右侧的“动作”栏表示由该命令的执行而进行的动作。

若执行该load命令，则首先将SP相对修饰位置位。该SP相对修饰位的内容，如图1所示，用于通过控制线从MPU113向高速缓存单元117通知以SP相对地址指定执行load/storepop命令。接着，以在Rn寄存器的内容上相加偏置值的间接地址指定来将存储器的内容读入Rm寄存器内。即，将Rn寄存器的内容加上偏置值后的值所表示的地址的存储器内容读入Rm寄存器内。作为SP使用的Rn的内容不会被增减。

图2(d)左侧的“命令”栏表示store命令的命令形式。在该形式中MPU113将Rm寄存器作为堆栈指针使用。图2(d)右侧的“动作”栏表示由该命令的执行而进行的动作。

若执行该store命令，则以Rm寄存器的内容加上偏置值的间接地址指定来将Rn寄存器的内容写入存储器内。即，在将Rm寄存器的内容加上偏置值后的值所表示的地址的存储器中写入Rn寄存器内容。而且，SP相对修饰位置位。与上述同样，SP相对修饰位的内容，用于通过控制线从MPU113向高速缓存单元117通知以SP相对地址指定执行load/storepop命令。作为SP使用的Rm的内容不被增减的情况与上述相同。

若由MPU113执行包含这些命令的数据移动命令，则只要该数据移动命令向外部存储器存取，MPU113就将存取对象即外部存储器的逻辑地址向虚拟地址总线输出，根据数据存取为从存储器开始的数据读出还是写入，来分别接通高速缓存读出请求或高速缓存写入请求位信号线。若数据存取为向存储器的数据写入，则MPU113也同时将成为写入对象的数据向32位宽的数据总线输出。输出到虚拟数据总线的逻辑地址由MMU115变换为物理地址，向实际数据总线输出。接受这些数据的高速缓存单元117判定作为数据存取对象的存储器在高速缓存上是否存在。

如上所说明的，使用于从本实施方式中使用的MPU进行存储器存取的控制信号线为传输push/pop修饰、SP相对修饰、高速缓存读出请求及高速缓存写入请求的4根(4位)。在图3中表示由MPU113执行的命令及动作与各控制线的状态的可能的组合。

图3(a)表示高速缓存读出请求与高速缓存写入请求都断开(0)的情况。在这种情况下，无论push/pop修饰、SP相对修饰状态如何，也不进行与高速缓冲存储器的读写相关的任何动作。

图3(b)表示高速缓存读出请求断开(0)，高速缓存写入请求接通(1)，push/pop修饰与SP相对修饰都断开(0)的情况。即，图3(b)表示对存储器执行随机写入命令时的动作与此时的控制信号线的状态。

图3(c)表示高速缓存读出请求断开(0)，高速缓存写入请求接通(1)，push/pop修饰断开(0)，SP相对修饰接通(1)的情况。即，图3(c)表示对存储器执行SP相对写入(store)命令时的动作与此时的控制信号线的状态。

图3(d)表示高速缓存读出请求断开(0)，高速缓存写入请求接通(1)，push/pop修饰接通(1)，SP相对修饰断开(0)的情况。即，图3(d)表示对存储器执行push命令时的动作与此时的控制信号线的状态。

图3(e)表示高速缓存读出请求断开(0)，高速缓存写入请求接通(1)，push/pop修饰与SP相对修饰都接通(1)的情况。通常不设想这种状态。即，通常不发生这种状态。

图3(f)表示高速缓存读出请求接通(1)，高速缓存写入请求断开(0)，push/pop修饰与SP相对修饰都断开(0)的情况。即，图3(f)表示对存储器执行随机读出命令时的动作与此时的控制信号线的状态。

图3(g)表示高速缓存读出请求接通(1)，高速缓存写入请求断开(0)，push/pop修饰断开(0)，SP相对修饰接通(1)的情况。即，图3(g)表示对存储器执行SP相对读出(load)命令时的动作与此时的控制信号线的状态。

图3(h)表示高速缓存读出请求接通(1)，高速缓存写入请求断开(0)，push/pop修饰接通(1)，SP相对修饰断开(0)的情况。即，图3(h)表示对存储器执行pop命令时的动作与此时的控制信号线的状态。

图3(i)表示高速缓存读出请求接通(1)，高速缓存写入请求断开(0)，push/pop修饰与SP相对修饰都接通(1)的情况。通常不设想这种状态。即，通常不发生这种状态。

图3(j)表示高速缓存读出请求与高速缓存写入请求都接通(1)的情况。无论push/pop修饰、SP相对修饰状态如何，通常不设想这种状态。即，通常不发生这种状态。

图4是表示高速缓存单元117的构成框图。高速缓存单元117具备数据保持部300及控制部200。数据保持部300的构成在图5中描述。本实施方式的高速缓存单元117的数据保持部300具有256组(set)、4路线(way)的构成。然而，本发明的数据存储器高速缓存装置并未限于该构成，可以采用其他任意构成。

图6是表示图5所示的数据保持部300中所含的行的构成之构成图。如图6所示，各行具有保持数据用的数据区域、保持控制中使用的3种控制位(标志)的标志保持部和保持标签用的标签保持部。

各数据区域是保持对主存储装置131临时读写的16字节(4字、128位)单位的数据的区域，具有16字节的存储容量。另外，各数据区域被分割为保持对MPU113同时读写的1字(4字节)单位的数据用的4个小区域。各标签保持部保持20位宽的标签。各标志保持部具有保持每1位的valid标志(有效标志)的有效标志保持部、保持dirty标志(改动标志)的改动标志保持部及保持stack标志(堆栈标志)的堆栈标志保持部。图7表示这3种标志的取得组合及这些组合所表示的含义。图7在后述的高速缓存系统100的动作说明中参照。

返回图4，控制部200用于对数据保持部300进行控制。作为主要的构成要素，控制部200具备随机写入检测部5、随机读出检测部6、SP相对写入检测部7、SP相对读出检测部8、压入存取检测部11、弹出存取检测部12、地址抽出部13、偏置计算部14、转送忙判定部15、数据写入部21、数据读出部22、边界判定部23、高速缓存错误判定部24、行释放部25、标签更新部26、标志设定部27、回填部28及回写部29。

随机写入检测部5检测来自MPU113的伴随随机写入命令执行的数据写入请求。更特定地讲，随机写入检测部5在对push/pop修饰与SP相对修饰否定，声明(assert)高速缓存写入请求时，判断为有伴随随机写入命令执行的数据写入请求。

随机读出检测部6检测来自MPU113的伴随随机读出命令执行的数据读出请求。更特定地讲，随机读出检测部6在对push/pop修饰与SP相对修饰否定，声明高速缓存读出请求时，判断为有伴随随机读出命令执行的数据读出请求。

SP相对写入检测部7检测来自MPU113的伴随SP相对写入命令执行的数据写入请求。更特定地讲，SP相对写入检测部7在声明SP相对修饰与高速缓存写入请求双方时，判断为有伴随SP相对写入命令执行的数据写入请求。SP相对读出检测部8检测来自MPU113的伴随SP相对读出命令执行的数据读出请求。更特定地讲，SP相对读出检测部8在声明SP相对修饰与高速缓存读出请求双方时，判断为有伴随SP相对读出命令执行的数据读出请求。

压入存取检测部11检测来自MPU113的伴随push命令执行的数据写入请求。更特定地讲，压入存取检测部11在声明push/pop修饰与高速缓存写入请求双方时，判断为有伴随push命令执行的数据写入请求。弹出存取检测部12检测来自MPU113的伴随pop命令执行的数据读出请求。更特定地讲，弹出存取检测部12在声明push/pop修饰与高速缓存读出请求时，判断为有伴随pop命令执行的数据读出请求。

控制部200内的以下各要素根据上述随机写入检测部5、随机读出检测部6、SP相对写入检测部7、SP相对读出检测部8、压入存取检测部11及弹出存取检测部12的检测结果，进行与各命令对应的动作。

地址抽出部13从MPU113输出的32位地址中抽出与各组(图5)对应的地址的中位8位、应与标签对比的地址的上位20位、与各小区域(图6)对应的下位2位。在这里，下位2位是与地址的中位8位的下位侧相邻的2位，换言之是与从最下位开始的第3及第4位相当的部分。

偏置计算部14用于在MPU113执行push命令或pop命令时，计算从MPU113输出的地址偏离预定间隔的地址即偏置地址。关于偏置地址将在后面阐述。

转送忙判定部15判定在高速缓存单元117与主存储装置131之间转移数据用的数据总线是否在使用中。更特定地讲，转送忙判定部15在声明转移控制单元119输出的转送忙应答时判断为数据总线使用中。在这里，数据总线相当于插入转移控制单元119的图1的示例中的转移数据总线。

数据写入部21在有来自MPU113的数据写入请求时，将MPU113输出的数据写入与MPU113输出的地址对应的小区域内。数据读出部22在有来自MPU113的数据读出请求时，从与MPU113输出的地址对应的小区域向MPU113读出数据。

边界判定部23在MPU113执行push命令时，判定与MPU113输出的地址对应的小区域是否与该小区域所属的数据区域的边界中地址前进方向的相反侧的边界(以下适当地称为“行边界”)相邻。另外，边界判定部23在MPU113执行pop命令时，判定与MPU113输出的地址对应的小区域是否与该小区域所属的数据区域的边界中地址前进方向的边界(以下适当地称为“行边界”)相邻。

在图6中，越到下方地址越上升，在伴随push命令的执行MPU113输出的地址下降的情况下，即在图6中地址向上方移动的情况下，行边界位于数据区域的地址高的一方(图6中的下方)。这种情况下，如图6右端上附加阴影线所示，属于数据区域的4个小区域中与行边界相邻的小区域，相当于地址最高的小区域(在图6位于最下方的小区域)。在伴随pop命令的执行MPU113的输出的地址上升时，即在图6中地址向下方移动时，行边界位于数据区域的地址高的一方(图6中的下方)。这种情况下，如图6右端上附加剖面线所示，属于数据区域的4个小区域中与行边界相邻的小区域相当于地址最高的小区域(图6位于最下方的小区域)。即，行边界及与行边界相邻的小区域在push命令与pop命令之间通用。

高速缓存错误判定部24针对与MPU113输出的数据对应的数据区域判定是否正产生高速缓存错误。MPU113在偏置计算部14计算偏置地址时，即使对于与所算出的偏置地址对应的数据区域也判定是否正发生高速缓存错误。行释放部25释放已判定了高速缓存错误的数据区域。以下将数据区域的释放按照该领域的惯例适当地称为“行的释放”。另外，由于数据区域在每个行内各设置1个，故将数据区域适当地称为“行”。而且，行释放部25相当于本发明的数据区域释放部的具体例。

标志设定部27将3种标志设定于肯定侧或否定侧。标志设定部27如图4中用符号v、d、s所示，具有对应于3种标志的3种标志设定部，即有效标志设定部、改动标志设定部及堆栈标志设定部。另外，标志设定部27也可以设置于每个对应的行上。

回写部29是在与MPU113输出的地址对应的数据区域内产生高速缓存错误，导致该数据区域被释放等时，进行从数据区域向主存储装置131的数据返写(回写)的机构。回填部28是在与MPU113输出的地址对应的数据区域内产生高速缓存错误，导致该数据区域被释放之后，进行从主存储装置131向数据区域的数据读入(回填)的机构。标签更新部26是以新的地址将对应于已释放的数据区域的标签更新的机构。

(2、系统的动作)

以下，也参照已引用的图1～图7，对本实施方式的高速缓存系统100进行的高速缓存控制进行说明。

(2-1.随机读出)

图8是表示MPU113执行随机读出命令时的高速缓存系统100的动作的顺序图。图8以下的顺序图为了也同时表示高速缓存单元117的动作的详细内容，组成流程图。在以下的顺序图中，带箭头的虚线表示在高速缓存单元117及主存储装置131之间交换的信号。

若MPU113开始执行随机读出命令，则图1所示的MPU113接通(即声明)高速缓存读出请求，同时将表示想读的存储区域的逻辑地址向虚拟地址总线输出。另外，MPU113将SP相对修饰及push/pop修饰保持为断开状态(即否定后的状态)。高速缓存单元117的随机读出检测部6通过接收这些信号，检测出MPU113在执行随机读出命令的同时进行数据读出请求。与此同时，高速缓存单元117的控制部200接通高速缓存忙应答。MPU113确认高速缓存忙应答接通，断开(即否定)高速缓存读出请求。而且，在本说明书中，将声明控制信号适当地表现为“接通”，将否定适当地表现为“断开”。

MMU115将虚拟地址总线的上位20位变换为物理地址的上位20位，向实际地址总线输出。虚拟地址总线的下位12位直接输出到实际地址总线。

如上所述，若控制部200接收高速缓存读出请求信号，则首先接通高速缓存忙应答信号。接着，在步骤S1中，高速缓存单元117的高速缓存错误判定部24，将地址抽出部13抽出的实际地址的中位8位作为关键词，选择各路线中的1组，读出所选择的组的标签值。

如图5所示，假设本实施方式的高速缓存单元117具有256组、4路线的构成。因此，例如地址总线的上位20位用二进制数表现则为“00011001 1100 0000 1111(用16进制数表现0x19C0F)”，例如地址总线的中位8位用二进制数表现则为“0010 1000(用16进制数表现0x28，10进制数表现“40”)”。这种情况下，高速缓存错误判定部24，将包含在“组40”中的4个行的任一行，作为可以在高速缓存中使用的行进行选择

然后，高速缓存错误判定部24比较实际地址总线的上位20位与已读出的标签的值(20位)，若一致则高速缓存选中，即判断没有发生高速缓存错误(S1中为“是”)。在上述的示例中，由于地址总线的上位20位为(0x19C0F)，故只要组40所含的行中包含的标志的任何值都与其相同，为(0x19C0F)，高速缓存错误判定部24就判定高速缓存选中。

将判断为该高速缓存选中时(S1中为“是”)的动作(S2～S4、S21、S24)在图9(b)～(g)“动作”的左栏“随机读出”中表示。另外，将高速缓存选中(S1中为“是”)且该行的valid标志为1时(S2中为“是”)的动作(S21、S24)在图9(b)～(e)中表示。此时的状态相当于图7(e)～(h)。由于此时的行的内容与主存储装置131的内容一致或比主存储装置131的内容还新，故数据读出部22从该行所含的全16字节中读出相当于实际地址总线的下位4位的数据，向32位宽的数据总线输出(S3)。然后，控制部200断开高速缓存忙应答信号。

另外，此时若stack标志为1，则动作状态相当于图7(f)、(h)的状态，如图9(c)、(e)所示，标志设定部27令stack标志为0(S3)。MPU113检测出高速缓存忙应答信号已断开，读入向数据总线送出的数据(S10)。

在图9(f)、(g)中表示虽然高速缓存选中但valid标志为0时(S2中为“否”)的动作(S21、S24)。此时的状态相当于图7(a)、(b)。该状态相当于虽然地址总线的上位20位的值偶然与标签的内容一致，但行已释放，实际上并未进行高速缓存的状态。即，在该状态中，由于主存储装置131的内容比行的内容还新，故控制部200必须进行将对应的主存储装置131的内容读入高速缓冲存储器中的回填动作(S21)。回填部28进行过回填(S21)后，标志设定部27将valid标志置为0(S24)，若stack标志为1则置为0(S3)。

根据以上的动作，由于称为与图9(b)相同的状态，故以后与图9(b)同样，数据读出部22从该行所含的全16字节中读出相当于实际地址总线的下位4位的数据(S4)，向32位宽的数据总线输出。然后，控制部200断开高速缓存忙应答信号。而且，回填动作(S21)的详细内容将在以下的高速缓存错误的说明中进行说明。

另一方面，高速缓存错误判定部24，比较实际地址总线的上位20位与读出的标签的值(20位)，结果若选择过的组所含的任何一路线都不一致，则高速缓存未选中，即判断为产生高速缓存错误(S1)。在图9(a)“动作”的左栏“随机读出”中表示此时的动作(S300、S21～S23、S3)。

若判定为高速缓存错误产生，则首先行释放部25从位于同一组中的4个行中选择1个，进行行的释放(S300)。在释放行的选择(S31)中，例如使用LRU算法(Least Recently Used algorithm)。执行这些的是图5的各组所含的“LRU式取换工具(replacer)”。即，行释放部25使用LRU式取换工具进行行的选择。该算法如名字那样，是释放最近最不经常使用的即使用频率少的部分的方法。由于其内容与本发明的本质部分无直接关系，故省略说明。另外，不一定限于该算法，也可以用其他的算法来决定释放的行。

接着，如此进行选择完的行的释放。释放行的动作根据各行的状态，即此时由该行的各标志的值所表示的状态的不同而不同，其内容在图10“动作”的右栏中表示。

图10(a)的状态意味着该行并未作为主存储装置131的高速缓存分配，即正释放着。因此，行释放部25没有重新释放该行的必要(S31中为“否”)该状态通常表示valid标志为0的情况。

在图10(b)、(c)的状态中，如图7(e)、(f)所示，行的内容与主存储装置131的内容一致(S32中为“是”、S33中为“否”)。因此，行释放部25不需回写，为了表示只释放该行，只要将valid标志置为0(S36)即可。行释放部25例如可以利用标志设定部27进行各种标志的设定。另外，如图10(c)所示，stack标志成为1，若表示分配给stack(堆栈)的状态，则行释放部25在释放该行时将stack标志也置为0(S36)。

在图10(d)、(e)的状态中，dirty标志为1(S33中为“是”)，如图7(g)、(h)所示，该行的内容更新为比主存储装置131的内容还新。因此，行释放部25必须将行的内容回写到主存储装置131。行释放部25例如可以起动回写部29来执行回写动作。该回写是通过使用图1所示的转移控制单元119，借助转移数据总线与外部数据总线而高速且自动地进行的。然而，对于该方法，也由于与本发明的本质无直接关系，故省略说明。行释放部25为了表示在进行回写后，一旦该行已释放的情况，将valid标志与dirty标志置为0(S36)。

图10(e)所示的valid标志为1(S32中为“是”)，dirty标志为1(S33中为“是”)，stack标志也为1的状态，相当于图7(h)的状态。该状态意味着该行被分配给堆栈。因此，这种情况与上述相同，行释放部25在释放行时，解除向堆栈的分配，同时将stack标志也置为0(S36)

图10(f)、(g)所示的valid标志为0的状态相当于图7(a)～(f)的状态。在该状态中，虽然标签的置偶然一致，但由于该行已经不作为高速缓存使用即正释放着，故行释放部25没有进行回写的必要。若stack标志为1，则行释放部25在行的释放时只执行将stack标志置为0的动作(S36)。

以上1个行的释放结束，接着，为了将该已释放的行作为高速缓存利用，回填部28将含有要求的地址的16字节的主存储装置131的内容回填到该行中。该回填动作虽然也是使用图1所示的转移控制单元119，借助转移数据总线与外部数据总线而高速且自动地进行的，但由于该方法也与本发明的本质无直接关系，故省略说明。

标签更新部26向与已进行过回填的行对应的标签写入实际地址的上位20位(S22)。接着，标志设定部27将valid标志置为1，dirty标志置为0，stack标志置为0，即设置为图7(e)的状态(S23)。

由于结束了步骤S23的状态和图9(b)的状态相同，故控制部200之后进行与图9(b)相同的动作(S2～S4)。即，  数据读出部22从已进行过标签更新的行所含的全16字节中读出相当于实际地址总线的下位4位的小区域数据，向32位宽的数据总线输出(S3)。然后，控制部200断开高速缓存忙应答信号。MPU113检测到高速缓存忙应答信号已断开，读入通过数据总线传送的数据的内容(S10)。

(2-2.随机写入)

图11是表示MPU113执行随机写入命令时的高速缓存系统100的动作的顺序图。若MPU113开始执行随机写入命令，则图1所示的MPU113接通高速缓存写入请求，同时向虚拟地址总线输出表示想写的存储区域的逻辑地址，再将想写的数据向32位宽的数据总线输出。另外，MPU113直接断开SP相对修饰及push/pop修饰。高速缓存单元117的随机写入检测部5通过接收这些信号，而检测出MPU113伴随随机写入命令的执行，进行数据写入请求的情况。与此同时，控制部200接通高速缓存忙应答。MPU113一确认高速缓存忙应答已接通，就断开高速缓存写入请求。

接着，与随机读出同样，高速缓存错误判定部24进行组与路线的选择及高速缓存选中或高速缓存错误的判断(S1)。对于该情况，由于选中已经说明，故省略。

将判断为高速缓存选中时(S1中为“是”)的动作(S2、S11、S12)在图9(b)～(g)“动作”的右栏“随机写入”中表示。另外，高速缓存选中(S1中为“是”)且该行的valid标志为1时(S2中为“是”)的动作(S11、S12)在图9(b)～(e)中表示。此时的状态相当于图7(e)～(h)。由于此时的行内容与主存储装置131的内容一致或比主存储装置131的内容还新，故数据写入部21将数据总线的内容即通过数据总线送来的数据写入与该行的实际地址总线下位4位相当的区域内(S11)。接着，若dirty标志还不为1，则如图9(b)、(c)所示，标志设定部27将dirty标志置为1(S12)。然后，控制部200断开高速缓存忙应答信号。

另外，此时若stack标志为1，则动作状态相当于图7(f)、(h)的状态。此时，如图9(c)、(e)所示，标志设定部27将stack标志置为0。MPU113一检测到高速缓存忙应答信号已断开，就知道随机写入已结束。

在图9(f)、(g)中表示虽然高速缓存选中但valid标志为0时(S2中为“否”)的动作(S21、S24)。此时的状态相当于图7(a)、(b)。该状态相当于虽然地址总线的上位20位偶然与标签的内容一致，但行已释放，实际上没有进行高速缓存的状态。即，在该状态中，由于主存储装置131的内容比行的内容还新，故必须进行将对应的主存储装置131的内容读入高速缓冲存储器内的回填动作(S21)。回填部28进行过回填(S21)之后，标志设定部27将valid标志置为1(S24)。接着，数据写入部21将数据总线的内容写入与该行的实际地址总线下位4位相当的区域内(S11)。然后，标志设定部27将dirty标志置为1(S12)。

若动作状态相当于图7(b)的状态，将stack标志置为1，则如图9(g)所示，控制部200解除向行的堆栈的分配。即，标志设定部27将stack标志置为0(S12)。

另一方面，将在步骤S1中判断为高速缓存错误时(S1中为“否”)的动作在图9(a)“动作”的右栏“随机写入”中表示。行释放部25，为了确保新高速缓存中使用的行而从以地址总线的中位8位选择的组中决定LRU式取换工具释放的行，释放已决定的行(S30)，为了将释放了的行作为新的高速缓存使用，进行回填动作(S21)。由于该动作与已说明的随机读出中的行释放相同，故在此省略其说明。

由于利用这些动作，行的数据内容与主存储装置131的内容一致，动作状态成为图9(b)的状态，故控制部200以后进行与图9(b)相同的动作。即，数据写入部21将数据总线的内容写入相当于已回填的行的实际地址总线下位4位的小区域内。接着，控制部200断开高速缓存忙应答信号。MPU113一检测出高速缓存忙应答信号断开的情况，就知道随机写入已结束。

(2-3.SP相对读出)

图12是表示MPU113执行SP相对读出命令时的高速缓存系统100的动作的顺序图。若MPU113开始执行SP相对读出命令，则MPU113接通高速缓存读出请求，同时向虚拟地址总线输出表示想读的存储区域的逻辑地址。同时MPU113接通SP相对修饰信号。高速缓存单元117的SP相对读出检测部8通过接收这些信号，检测出MPU113伴随SP相对读出命令的执行进行数据读出请求的情况。在这一点上，SP相对读出与上述随机读出的动作不同。与此同时，高速缓存单元117的控制部200接通高速缓存忙应答。MPU113一确认高速缓存忙应答已接通，就断开高速缓存读出请求。

MMU115将虚拟地址总线的上位20位变换为物理地址的上位20位，向实际地址总线输出。虚拟地址总线的下位12位直接向实际地址总线输出。

如上所述，若控制部200接收高速缓存读出请求信号，则首先接通高速缓存忙应答信号。接着，在步骤S1中，高速缓存错误判定部24将地址抽出部13抽出的实际地址的中位8位作为关键词，选择各路线中的1个组，并读出所选择的组的标签的值。高速缓存错误判定部24进一步判断高速缓存的选中与错误。这些动作与随机读出中的动作相同。

若高速缓存选中(S1中为“是”)，且该行的valid标志为1(S2中为“是”)则数据读出部22从该行中读出相当于实际地址总线的下位4位的数据，并向32位宽的数据总线输出。然后，控制部200断开高速缓存忙应答信号。在图13(b)～(e)“动作”的左栏“SP相对读出”中表示以上动作。MPU113一检测出高速缓存忙应答信号已断开，就读入数据总线的内容(S10)。

若高速缓存虽然选中(S1中为“是”)，但valid标志为0(S2中为“否”)，则意味着如上所述，虽然地址总线的上位20位的值偶然与某行的标签内容一致，但该行已释放，且并未进行高速缓存。因此，这种情况下，回填部28进行过回填(S21)之后，标志设定部27将valid标志置为1(S24)。然后，控制部200进行与图13(b)相同的动作。在图13(f)、(g)的左栏“SP相对读出”中表示此时的动作。

另外，高速缓存错误判定部24比较实际地址总线的上位20位和已读出的标签的值(20位)，若结果是和由地址总线的中位8位的值选择的组中的任何路线都不一致，则判断为高速缓存未选中(高速缓存错误)，从位于同一组内的4个行中选择1个，进行行的释放(S301)。在步骤S301中，与步骤S300不同的是，标志设定部27不将stack标志置为0(S36)，而只将valid标志置为0(S37)。步骤S301的其他处理与步骤S300同样。

然后，回填部28针对已释放的行，从该主存储装置131的存储区域回填其内容(S21)。接着，标签更新部26更新对应于已回填的行的标签(S22)。接下来，标志设定部27将valid标志置为1(S24)。然后，控制部200进行与图13(b)相同的动作。在图13(f)、(g)的左栏“SP相对读出”中表示此时的动作。

由于在图13(a)～(g)所示的任何状态中都不进行stack标志的设定，故stack标志的状态维持原来的状态。在这一点上，SP相对读出也与随机读的动作不同。

(2-4.SP相对写入)

图14是表示MPU113执行SP相对写入命令时的高速缓存系统100的动作的顺序图。若MPU113开始执行SP相对写入命令，则MPU113接通高速缓存写入请求，同时向虚拟地址总线输出表示想读的存储区域的逻辑地址，并向32位宽数据总线输出想写的数据。同时MPU113接通SP相对修饰信号。高速缓存单元117的SP相对写入检测部7通过接收这些信号，检测出MPU113伴随SP相对写入命令的执行进行数据写入请求的情况。在这一点上，与上述随机写的动作不同。与此同时，高速缓存单元117的控制部200接通高速缓存忙应答。MPU113一确认高速缓存忙应答已接通，就断开高速缓存读出请求。

接着，高速缓存错误判定部24利用与SP相对读出中步骤S1同样的动作，进行组与路线的选择及高速缓存选中或高速缓存错误的判断(S1)。在图13(b)～(g)“动作”的右栏“SP相对写入”中表示判断为高速缓存已选中时(S1中为“否”)的动作。

若高速缓存选中(S1中为“是”)，且该行的valid标志为1(S2中为“是”)则数据写入部21将数据总线的内容写入相当于实际地址总线的下位4位的区域内(S11)。然后，若dirty标志仍为1，则如图13(b)、(c)所示，标志设定部27将dirty标志置为1(S13)。控制部200断开高速缓存忙应答信号。在图13(b)～(e)“动作”的右栏“SP相对写入”中表示以上动作。MPU113一检测出高速缓存忙应答信号已断开，就知道SP相对写入已结束。

若高速缓存虽然选中(S1中为“是”)，但valid标志为0(S2中为“否”)，则意味着如上所述，虽然地址总线的上位20位的值偶然与某行的标签内容一致，但该行已释放，且并未进行高速缓存。因此，这种情况下，回填部28进行过回填(S21)之后，标志设定部27将valid标志置为1(S24)。然后，控制部200进行与图13(b)相同的动作。在图13(f)、(g)的右栏“SP相对写入”中表示此时的动作。

另一方面，高速缓存错误判定部24比较实际地址总线的上位20位和已读出的标签的值(20位)，若结果是和由地址总线的中位8位的值选择的组中的任何路线都不一致，则判断为高速缓存未选中(高速缓存错误)，从位于同一组内的4个行中选择1个，进行行的释放(S301)。

然后，回填部28针对已释放的行，从该主存储装置131的存储区域回填其内容(S21)。接着，标签更新部26更新对应于已回填的行的标签(S22)。接下来，标志设定部27将valid标志置为1(S24)。然后，控制部200进行与图13(b)相同的动作。在图13(f)、(g)的右栏“SP相对写入”中表示此时的动作。

由于在图13(a)～(g)所示的任何状态中都不进行stack标志的设定，故stack标志的状态维持原来的状态。在这一点上，SP相对写入也与随机写入的动作不同，而与上述SP相对读出相同。

(2-5.pop)

图15是表示MPU113执行pop命令时的高速缓存系统100的动作的顺序图。若MPU113开始执行pop命令，则MPU113接通高速缓存读出请求，同时向虚拟地址总线输出表示想pop的存储区域的逻辑地址。同时MPU113接通push/pop修饰信号。高速缓存单元117的弹出存取检测部12通过接收这些信号，检测出MPU113伴随pop命令的执行进行数据读出请求的情况。在这一点上，pop与上述随机读出及SP相对读出的动作不同。与此同时，高速缓存单元117的控制部200接通高速缓存忙应答。MPU113一确认高速缓存忙应答已接通，就断开push/pop修饰信号。

MMU115将虚拟地址总线的上位20位变换为物理地址的上位20位，向实际地址总线输出。虚拟地址总线的下位12位直接向实际地址总线输出。

如上所述，若控制部200接收高速缓存读出请求信号，则首先接通高速缓存忙应答信号。接着，在步骤S1中，高速缓存错误判定部24将地址抽出部13抽出的实际地址的中位8位作为关键词，选择各路线中的1个组，并读出所选择的组的标签的值，判断高速缓存的选中或者错误。由于这些动作与随机读出或SP相对读出中的动作相同，故省略说明。

若实际地址总线的上位20位与所选择的组中的某行的标签内容一致(S1中为“是”，即高速缓存选中)，且该行的valid标志为1(S2中为“是”)，则控制部200进行图16(b)～(e)的动作。此时，利用边界判定部23的判定(S51)，若实际地址总线的第3位(从下面的位数开始第4个位，即表示2的3次方的位数的位，以后同样)与第2位(从下面的位数开始第3位，即表示2的2次方的位数的位，以后同样)双方都为1(S51中为“是”)，则控制部200进行图16(b)～(e)的动作左栏“从最上位地址pop”的动作。即，数据读出部22从该行读出与实际地址总线的下位4位相当的数据，并输出到32位宽的数据总线(S4)。然后，控制部200断开高速缓存忙应答信号。

接着，标志设定部27将该行的valid标志置为0(S52)，释放该行。这是因为通过从最上位地址数据被pop，来空置该堆栈的缘故。标志设定部27虽然将valid标志置为0，释放行，但此时回写部29不进行回写。这是因为该行的内容不再被参照，没有必要回写并保存在主存储装置内的缘故。

另外，如图16(b)、(d)的动作左栏“从最上位地址pop”所示，若该行的stack标志断开，则标志设定部27接通stack标志(S52)。这是因为存储该行作为堆栈使用情况的缘故。

再有，如图16(d)、(e)的动作左栏“从最上位地址pop”所示，若该行的dirty标志接通，则标志设定部27断开dirty标志(S52)。由于该行被释放，故dirty标志没有意义。还有，标志设定部27在步骤S52中，可以不断开valid标志即不进行行的释放，只断开dirty标志。由此，利用步骤S300或S301，在以后必须释放对应的行时可以将回写(S34)禁止(S33中为“否”)。

若实际地址总线的第3位与第2位的至少一方为0(S51中为“否”)，则控制部200进行图16(b)～(e)的动作右栏“从最上位地址以外pop”的动作。即，数据读出部22从该行读出与实际地址总线的下位4位相当的数据，并输出到32位宽的数据总线(S4)。然后，控制部200断开高速缓存忙应答信号。MPU113一检测出高速缓存忙应答信号已断开，就读入32位宽数据总线的内容即数据(S10)。此时，标志设定部27不进行标志的操作等。

若虽然实际地址总线的上位20位与所选择的组中的某行的标签内容一致(S1中为“是”)，但该行的valid标志为0(S2中为“否”)，则控制部200进行图16(f)、(g)的动作。此时，虽然所选择的组中的某行的内容与实际地址总线的上位20位的值偶然一致，但由于相当于该行已释放，故回填部28进行回填(S21)。利用边界判定部23的判定(S55)，若实际地址总线的第3位与第2位双方都为1(S55中为“是”)，则控制部200进行图16(f)、(g)的动作左栏“从最上位地址pop”的动作。

即，回填部28针对该行，从主存储装置进行存储于该地址的信息的回填，标志设定部27将valid标志置为1(S25)。而且，数据读出部22从该行向实际地址总线的下位4位读出该数据，并输出到32位宽的数据总线(S4)。然后，控制部200断开高速缓存忙应答信号。

若此时stack标志为0，则标志设定部27将stack标志置为1(图16(f)动作左栏“从最上位地址pop”；S53)。再有，标志设定部27将valid标志恢复到0(图16(f)(g)动作左栏“从最上位地址pop”；S53)。这是因为利用从最上位地址的pop来释放该行的缘故。

若实际地址总线的第3位与第2位的至少一方为0(S55中为“否”)，则控制部200进行图16(f)、(g)的动作右栏“从最上位地址以外pop”的动作。即，即使在这种情况下，标志设定部27也针对该行从主存储装置执行该地址所存储信息的回填(S21)，标志设定部27将valid标志置为1(S25)。而且，数据读出部22从该行读出与实际地址总线的下位4位相当的数据，并向32位宽的数据总线输出(S4)。然后，控制部200断开高速缓存忙应答信号。之后标志设定部27不进行标志的操作等。而且，在图15中虽然描述了步骤S21及S25的处理在步骤S55的判定之前执行的示例，但也可以不管该判定的结果，在步骤S55之后进行步骤S21及S25的处理。

若实际地址总线的上位20位的值与所选择的组中的行的标签内容不一致(S1中为“否”)，则高速缓存错误判定部24判断高速缓存错误，控制部200根据此进行图16(a)的动作。即，行释放部25从该组利用LRU算法释放1个行(S30)，回填部28针对该行，从主存储装置执行存储于该地址的信息的回填。然后，标签更新部26更新已回填过的行对应的标签。接着，标志设定部27将该行对应的valid标志置为1，dirty标志置为0(S25)。接下来，数据读出部22从该行读出与实际地址总线的下位4位相当的数据，并向32位宽的数据总线输出(S4)。然后，控制部200断开高速缓存忙应答信号(以上如图16(a))。

再有，若利用边界判定部23的判定(S56)，实际地址总线的第3位与第2位都为1(S56中为“是”)，则标志设定部27将stack标志置为1(图16(a)动作左栏“从最上位地址pop”；S54)。还有，此时标志设定部27将valid标志恢复到0(图16(a)动作左栏“从最上位地址pop”；S54)。这是因为利用从最上位地址的pop来释放该行的缘故。

如上所述，在MPU113执行pop命令的情况下，数据读出对象即小区域位于行边界(S51、S55、S56中为“是”)时，控制部200并不向主存储装置131回写该行所保持的数据，而是释放该行(即，S52、S53、S54中设定v＝0)。保持利用pop命令的读出，也不再读出的数据的行是即使释放也没有故障的部分，且该行保持的数据是无用的数据，没有向主存储装置131回写的必要。这样，由于控制部200以无数据的回写的方式释放保持无用数据的行，故对MPU113的动作不影响，可以提高存储器存取速度。

另外，控制部200在读出对象即小区域不位于行边界时(S51、S55、S56中为“否”)不进行行释放。因此，MPU113不仅可以使pop命令的数据读出在与行边界相邻的小区域所对应的地址中结束，也使其在与行边界不相邻的小区域所对应的地址中结束。

另外，如上所述，在步骤S52中，可以不将valid标志设定为0，而将dirty标志设定为0。由此，在MPU113执行其他命令时，控制部200在进行伴随高速缓存错误的行释放(S300、S301)时，跳过该行的数据向主存储装置131的回写(S34)。结果，存储器存取速度提高。

如图17所示，在以上动作之后或之中内，若转送忙应答信号断开，则由于转移数据总线空置，故控制部200针对可能马上有成为必须的存储器执行预回填。由此，可以更进一步提高存储器存取速度。具体地讲，若转送忙判定部15检测出转送忙应答信号断开(S61中为“是”)，则控制部200找到1个包含在行中的标签值与由包含该行的组所示实际地址的上位28位比目前的SP的实际地址的上位28位还大1或2的地址即偏置地址对应的行，进行图18的动作右栏“SP从下方趋近”所示的动作。即，偏置计算部14计算上述偏置地址，高速缓存错误判定部24针对与偏置地址对应的行判定是否产生高速缓存错误(S65)。

高速缓存错误判定部24可以找到这种行(S65中为“是”)，且若该行的valid标志为1(S67中为“是”)，则控制部200什么都不进行(图18动作右栏(b)～(e))。

高速缓存错误判定部24虽然可以找到这种行(S65中为“是”)，但若该行的valid标志为0(S67中为“否”)，且该行被分配给堆栈(S69中为“是”)，则回填部28进行该行的回填(S21)。之后，标志设定部27将valid标志置为1(S70)(以上是图18的动作右栏(g))。

高速缓存错误判定部24虽然可以找到这种行(S65中为“是”)，但该行的valid标志为0(S67中为“否”)，且该行未被分配给堆栈(S69中为“否”)，则控制部200什么都不进行(图18动作右栏(f))。

另外，若高速缓存错误判定部24不能找到这种行(S65中为“否”)，则按照地址的顺序，位于目前的堆栈指针SP之上且马上由pop读出的可能性高的主存储装置的存储区域未被高速缓存。因此，控制部200针对实际地址的上位28位比目前的SP的实际地址的上位28位还大，下位4位为0的主存储装置的区域，在高速缓存上执行回填(图18动作右栏(a)，S21)。

具体地讲，行释放部25在比目前的堆栈指针SP的实际地址的上位28位还大的地址所对应的则中，决定由LRU释放的行，进行决定完的行的释放(S301)。之后，标签更新部26进行标签更新(S22)，标志设定部27将stack标志设定为1(S26)。接着，回填部28执行该行的实际地址的上位28位比目前的SP的实际地址的上位28位还大1，下位4位为0的主存储装置的存储区域的回填(S21)。接下来，标志设定部27将该行的valid标志设定为1(S70)。

另外，同时如图19所示，在转送忙应答断开时(S61)，偏置计算部14计算包含在行中的标签值与由包含该行的组所示实际地址的上位28位比目前的SP的实际地址的上位28位还小的地址即其他偏置地址。高速缓存错误判定部24检索与该偏置地址对应的行(以上为S71)。高速缓存错误判定部24若能找到这种行(S71中为“是”)，则控制部200进行图10的动作左栏“SP向上方移动”所示的动作。

即，若高速缓存错误判定部24可以找到这种行(S71中为“是”)，且该行的valid标志、dirty标志、stack标志都为1(S73中为“是”)，则回写部29进行该行的回写(S75)，标志设定部27将dirty标志设为0(S77)(以上，图10的动作左栏(e))。

若高速缓存错误判定部24不能找到这种行(S71中为“否”)，或者即使能找到但valid标志、dirty标志、stack标志都为0(S73中为“否”)，则控制部200什么也不执行(图10动作左栏(a)～(d)(f)(g))。

如上所述，控制部200由于将根据pop命令结束读出的行的数据即不能再次读出的数据回写(S75)，故在释放该行时(S300、S301)，不必进行回写(S34)。由此，存储器存取速度提高。

(2-6.push)

图20是表示MPU113执行push命令时的高速缓存系统100的动作的顺序图。若MPU113开始执行push命令，则MPU113接通高速缓存写入请求，同时向虚拟地址总线输出表示想读的存储区域的逻辑地址，且向32位宽的数据总线输出想写的字数据。同时MPU113接通push/pop修饰信号。高速缓存单元117的压入存取检测部11通过接收这些信号，检测出MPU113伴随push命令的执行进行数据写入请求的情况。在这一点上，压入与上述随机写入及SP相对写入的动作不同。与此同时，高速缓存单元117的控制部200接通高速缓存忙应答。MPU113一确认高速缓存忙应答已接通，就断开push/pop修饰信号。

接着，高速缓存错误判定部24利用与pop的步骤S1同样的动作，进行组与路线的选择及判断高速缓存选中或高速缓存错误(S1)。由于这些动作与随机写入或SP相对写入中的对应动作同样，故省略说明。

若实际地址总线的上位20位与所选择的组中的某行的标签内容一致(S1中为“是”，即高速缓存选中)，且该行的valid标志为1(S2中为“是”)，则控制部200在该行中进行图21(b)～(e)的动作左栏“向最上位地址push”或动作右栏“向最上位地址以外push”的动作。此时，利用边界判定部23的判定(S51)，若实际地址总线的第3位与第2位双方都为1(S51中为“是”)，则控制部200进行图16(b)～(e)的动作左栏“向最上位地址push”的动作。即，数据写入部21从32位宽的数据总线读入应写的字数据，并写入与该行的实际地址总线的下位4位相当的区域内(S11)。然后，控制部200断开高速缓存忙应答信号(以上，图21(b)～(e)动作右栏(压入最上位地址))。

接下来，若该行的dirty标志为0，则标志设定部27将dirty标志置为1(图21(b)(c)动作左栏“向最上位地址push”；S15)。另外，若该行的stack标志为0，则标志设定部27将stack标志置为1(图21(b)(d)动作左栏“向最上位地址push”；S15)。然后，MPU113一检测出高速缓存忙应答信号已断开，就知道push命令的处理已经结束。

若实际地址总线的第3位与第2位的至少一方为0(S51中为“否”)，则控制部200进行图21(b)～(e)的动作右栏“向最上位地址以外push”的动作。即，数据写入部21从32位宽的数据总线读入想写的字数据，并写入与该行的实际地址总线的下位4位相当的区域内(S11)。然后，控制部200断开高速缓存忙应答信号(以上，图21(b)～(e)动作右栏“压入最上位地址以外”；S13)。若该行的dirty标志为0，则标志设定部27将dirty标志置为1(图21(b)(c)动作右栏“向最上位地址以外push”；S13)。标志设定部27不进行其他标志的操作。MPU113一检测出高速缓存忙应答信号已断开，就知道push命令的处理已经结束。

若虽然实际地址总线的上位20位与所选择的组中的某行的标签内容一致(S1中为“是”)，但该行的valid标志为0(S2中为“否”)，则控制部200进行图21(f)、(g)的动作。此时，虽然所选择的组中的某行的内容与实际地址总线的上位20位的值偶然一致，但相当于该行已释放。

利用边界判定部23的判定(S55)，若实际地址总线的第3位与第2位双方都为1(S55中为“是”)，则控制部200进行图21(f)、(g)的动作左栏“向最上位地址push”的动作。即，回填部28针对该行，不进行从主存储装置回填存储于该地址的信息，标志设定部27将valid标志置为1(S24)。

而且，数据写入部21从32位宽的数据总线读入想写的字数据，并写入该行的实际地址总线的下位4位相当的区域内(S11)。接着，控制部200断开高速缓存忙应答信号(以上，图21(f)(g)动作左栏“向最上位地址push”)。MPU113一检测出高速缓存忙应答信号已断开，就知道push命令的处理已经结束。标志设定部27将dirty标志置为1(图21(f)(g)动作左栏“向最上位地址push”；S15)。若此时stack标志为0，则标志设定部27将stack标志置为1(图21(f)动作左栏“向最上位地址push”；S15)。

在步骤S55的判定中，若实际地址总线的第3位与第2位的至少一方为0(S55中为“否”)，控制部200进行图21(f)(g)动作右栏“向最上位地址以外push”的动作。即，回填部28针对该行执行从主存储装置回填存储于该地址的信息(S21)。接着标志设定部27将valid标志置为1(S24)。接下来，数据写入部21从32位宽的数据总线读入想写的字数据，并写入该行的实际地址总线的下位4位相当的区域内(S11)。然后，控制部200断开高速缓存忙应答信号。与此同时，标志设定部27将dirty标志置为1。

在步骤S1的判定中，若实际地址总线的上位20位的值与所选择的组中的行的标签内容不一致(S1中为“否”)，则高速缓存错误判定部24判断高速缓存未选中。与此同时，控制部200进行图21(a)的动作。即，行释放部25从该组利用LRU算法释放1个行(S301)。根据边界判定部23的判定(S56)，若实际地址总线的第3位与第2位均为1(S56中为“是”)，则回填部28针对该行，不进行从主存储装置回填存储于该地址内的信息。然后，标签更新部26更新已释放的行对应的标签(S22)。接着，标志设定部27将该行对应的valid标志置为1，dirty标志置为0，stack标志置为0(S27)。由于成为和图21(b)相同的状态，故以后控制部执行图21(b)的动作。

在步骤S56的判定中，若实际地址总线的第3位与第2位的至少一方为0(S56中为“否”)，则回填部28针对该行执行从主存储装置回填存储于该地址的信息(S21)。之后，控制部200与步骤S56的判定为“是”的情况相同，执行步骤S22以下的处理。

如上所述，在MPU113执行push命令的情况下，应写入数据的小区域位于行边界(S56中为“是”)时，控制部200在伴随高速缓存错误的行释放(S301)之后不进行无用的回填(S21)。因此，提高存储器存取速度。另外，控制部200在应写入数据的小区域不位于行边界时(S56中为“否”)，进行回填(S21)。因此，MPU113不仅可以使伴随push命令的数据连续写入在与行边界相邻的小区域所对应的地址中开始，也可以使其在与行边界不相邻的小区域所对应的地址中开始。

再有，不仅在行已被释放的情况下(S301)，而且在valid标志为表示行的释放的0的情况下(S2中为“否”)控制部200根据应写入数据的小区域的位置(S55)，来选择是否进行回填(S21)。因此，在行已经释放时，可以回避无用的回填，由此可以更进一步提高存储器存取速度。

如图22所示，在以上动作之后或之中内，若转送忙应答信号断开，则由于转移数据总线空置，故控制部200针对可能马上成为必须的存储器执行预回填。具体地讲，若转送忙判定部15检测出转送忙应答信号断开(S61中为“是”)，则控制部200找到1个作为MMU115的地址变换单元的、包含在行中的标签值比目前的SP的实际地址的上位20位还大的地址即偏置地址对应的行，或包含在行中的标签值与由包含该行的组所示实际地址的上位28位比目前的SP实际地址的上位28位还大3个以上的地址(同样称为“偏置地址”)所对应的行，并进行图18的动作左栏“SP向下方远离”所示的动作。即，偏置计算部14计算上述偏置地址，高速缓存错误判定部24针对与偏置地址对应的行判定是否产生高速缓存错误(S81)。

即使在高速缓存错误判定部24能找到这种行时(S81中为“是”)，但若该行的valid标志、dirty标志、stack标志中至少一个为1(S73中为“否”)，则控制部200不进行任何动作(图18动作左栏(b)～(d)(f)(g))。若高速缓存错误判定部24能找到这种行(S81中为“是”)，且该行的valid标志、dirty标志、stack标志都为1(S73中为“是”)，则回写部29进行该行的回写(S75)。接着，标志设定部27将dirty设为0(S77)(以上，图18动作左栏(e))。由此，之后在利用LRU算法释放该行时，不需重新进行回写，可以高速化处理。

若高速缓存错误判定部24不能找到这种行(S81中为“否”)，则控制部200不进行任何动作(图18动作左栏(a))。

(3、动作例1)

对于本发明的实施方式的数据存储器高速缓存系统的动作例，以作为MPU113采用执行用C语言编写的程序之通用CPU的情况为例，使用图23～图29进行详细说明。

用C语言编写的程序，例如使用从上位地址向下位地址方向成长的堆栈结构。该程序使用通用CPU内存在的专用堆栈指针(SP)，将该通用CPU内存在的通用寄存器作为帧指针(FP)使用，在该堆栈结构中执行存取。在图23中表示此时的堆栈结构的一例。在该例中只表示1个函数的执行中相关的堆栈结构。实际上，与已经执行的函数调用的数对应的堆栈结构做成堆积在下方的结构。

接着，说明用C语言进行的新函数调用使该结构如何生成(变化)。在C语言的函数调用时首先调用函数侧在栈顶使用push命令，生成函数侧的处理中必需的调用数。这是因为将该调用数传递给函数的缘故。在图24中表示生成了该调用数之后的堆栈结构。

接下来，执行函数调用。此时，执行push命令，来自函数的返回地址保存到堆栈内。在图25中表示该函数调用执行后的堆栈结构。

然后，程序的执行向调用的函数侧移动。在调用的函数侧最初执行push命令，将也含有帧指针的函数内部使用的寄存器保存到堆栈内。在图26中表示该寄存器保存后的堆栈结构。

接着，在调用的函数中，将堆栈指针的值设定为帧指针，为了生成堆栈帧，从堆栈指针减法运算堆栈帧的尺寸。由此，堆栈指针向更下位地址侧移动，在该堆栈指针与帧指针之间生成堆栈帧。在图27中表示堆栈帧生成后的堆栈结构。

在调用的函数侧，接着执行帧指针相对读出·写入命令、堆栈指针相对读出·写入命令、随机读出写入命令等，对调用数存取或对堆栈帧存取，对必要的信息存取后，执行函数的处理。另外有必要的话，有时也执行其他函数调用。

在调用的函数侧，若结束函数的处理，则由于将使用着的堆栈帧废弃，故在堆栈指针上加法运算堆栈帧的尺寸。而且，执行pop命令。将保存的寄存器复原。此时的堆栈结构复原为与函数调用后的堆栈结构完全相同的状态，如图25所示。

接下来执行pop命令，取出用于向调用侧的函数返回的地址，根据返回命令，使程序执行从被调用的函数向已调用的函数恢复。此时的堆栈结构与生成向函数传递的调用数后堆栈结构完全相同，如图24所示。在复原的调用函数侧，由于废弃调用数列，故在堆栈指针上加法运算调用数列的大小。例如，在图24的示例中是相当于2乘以字尺寸的值。

根据以上处理，堆栈结构恢复到开始函数调用处理前的结构。此时的堆栈结构如图23所示。

在图28中表示以上的函数调用相关的一行处理中堆栈帧生成之后的高速缓存行的状态。如图28所示，堆栈帧以外的部分作为堆栈使用，由此行的stack标志设定为1。由于高速缓存行的单位是16字节，堆栈结构的单位是4字节，故不限于堆栈帧与寄存器保存堆栈的边界和高速缓存行的边界一致。

根据本发明，在寄存器保存堆栈与堆栈帧共存的行中，将stack标志设定为1。另外，在堆栈帧与调用数列共存的行中将stack标志设定为0。在函数处理执行中，若执行对调用数列或堆栈帧的存取，则通常因为这些存取利用随机读出·写入命令来进行，故引起设定为1的stack标志也变化成0的情况。因此，在寄存器保存堆栈与堆栈帧共存的行或调用数列与返回地址共存的行中，stack标志也变化成0。在图29中表示此时各行的标志的状态。

(4、动作例2)

针对本发明的实施方式的数据存储器高速缓存系统的其他动作例，以作为MPU113使用的是执行用Java(注册商标)语言编写的程序的通用CPU的情况为例，并利用图29～图34详细进行说明。    

用C语言编写的程序例如由C语言所编写的解释程序(interpreter)来执行。该解释程序除了用来执行C语言所编写的程序的程序计数器(program counter)以外，还有为了安装Java(注册商标)虚拟机所必需的Java(注册商标)程序计数器。另外，在堆栈结构中，也是除了用于执行C语言所编写的程序的堆栈结构以外，还有为了安装Java(注册商标)虚拟机所必需的Java(注册商标)堆栈结构。

Java(注册商标)堆栈结构例如也可以使用从上位地址向下位地址方向成长的堆栈结构。在该Java(注册商标)堆栈结构中，例如将通用CPU内存在的通用寄存器作为堆栈指针(SP)使用，在Java(注册商标)堆栈结构中执行存取。

在图30中表示Java(注册商标)堆栈结构的一例。图30中，表示1个方法(method)(相当于C语言中的函数)的处理相对应的Java(注册商标)堆栈结构。实际上，与至此产生的程序调用(引用call)相当数量的堆栈结构形成为堆积在下方的结构。

接着，说明该堆栈结构根据Java(注册商标)语言进行的新方法调用如何生成(变化)。最初，调出新方法的方法调用侧通过在栈顶执行push命令来设定方法内的处理中使用的调用数。在图31中表示该调用数列生成之后的Java(注册商标)堆栈结构。该调用数列用于将调出的方法侧的处理中所必需的值从方法调用侧传递给调出方法侧。

接下来执行方法调用。来自方法的返回Java(注册商标)地址保存到C语言堆栈内。由于该地址的保存与Java(注册商标)堆栈结构无直接关系，故省略说明。利用该方法调用，Java(注册商标)程序的控制向调出的方法侧移动。在调出的Java(注册商标)方法侧，若使用的寄存器的保存是必要的，则将这些寄存器的值保存于C语言堆栈内。由于该寄存器的保存也与Java(注册商标)堆栈结构无直接关系，故省略说明。

接着，在调出的方法侧，为了生成自身执行的处理中所必需的局部变量用的区域，从Java(注册商标)堆栈指针的值减法运算相当于局部变量的区域尺寸的值。在图32中表示该局部变量区域生成之后的Java(注册商标)堆栈结构。

在调出的方法侧，之后利用作为Java(注册商标)堆栈指针相对地址指定的SP相对读出·写入命令，对调用数或局部变量内存取，执行方法的处理。

由于Java(注册商标)语言是堆栈指向语言，故Java(注册商标)命令中的操作数必需作为Java(注册商标)堆栈指针相对而被指定。例如，加法运算(add)命令中并不明确指定，而是自动地设定为Java(注册商标)堆栈的顶层或第二层(second)。因此，Java(注册商标)解释方法在执行加法运算命令中，通过执行2次pop命令，从Java(注册商标)堆栈中的操作数堆栈内读出2个值，执行加法运算，通过执行push命令，而将其结果存储于Java(注册商标)堆栈的操作数堆栈的顶层内。在图33中表示执行该处理中的Java(注册商标)堆栈结构。

在调出的方法中，有时也根据需要调用其他的方法。在调出的方法中的处理结束时，Java(注册商标)堆栈中的操作数堆栈成为空的。而且由于废弃局部变量区域和调用数列，故在Java(注册商标)堆栈指针上加法运算与这些的合计尺寸相当的值。此时的Java(注册商标)堆栈结构恢复到开始Java(注册商标)方法调用处理前的Java(注册商标)堆栈结构。在图30中表示此时的Java(注册商标)堆栈结构。

在图34中表示以上的Java(注册商标)方法调用处理的执行中，处理执行的高速缓存行的状态。如图34所示，该方法调用处理所生成的行的stack标志设定为1。另外，也在图34中表示通过使Java(注册商标)堆栈指针自堆栈底部(stack bottom)远离，从而在从堆栈指针离开的行中，在转送忙应答信号断开的时间内执行回写，将该行的dirty标志设定为0的状态。

由于本发明的数据存储器高速缓存装置及数据存储器高速缓存系统可以提高存储器存取速度，故在产业上有用。