预取命令控制方法、预取命令控制装置以及高速缓冲存储器控制装置转让专利
申请号 : CN200480012681.8
文献号 : CN1849580B
文献日 : 2010-04-28
发明人 : 大场章男
申请人 : 索尼计算机娱乐公司
摘要 :
提供预取命令控制装置。当从CPU接收指定要预取的数据的使用时间的预取命令时，协议时隙产生单元根据使用时间产生协议时隙并将其注册在调度列表存储单元中。当接收常规访问命令时，协议时隙产生单元在常规协议队列存储单元中注册协议时隙。成本估算单元根据要预取的数据的高速缓存保留时间来估算预取命令的发布成本，并且根据资源占用成本估算常规访问命令的发布成本。协议发布单元根据这些发布成本的估算结果确定将要发布哪个命令，是预取命令还是常规访问命令。
权利要求 :
1.一种预取命令控制方法，包括：
产生具有指定数据使用时间的信息的用于数据的预取命令；
根据指定使用时间的信息调度预取命令的发布定时；以及
当发布预取命令时，根据预取的数据停留在高速缓存中的时期计算预取命令发布成本，其中根据发布成本调度预取命令的发布定时。
2.如权利要求1所述的方法，还在发布预取命令时，计算由于常规访问命令的发布延迟所造成的成本，以估算预取命令的发布成本。
3.如权利要求1-2中任意一个所述的方法，还依据由从当前时间到指定的使用时间的时期定义的预取时间限制估算风险，以估算预取命令的发布成本。
4.如权利要求1所述的方法，还包括当发布正规访问命令时，根据资源占用的时期计算用于数据的常规访问命令的发布成本，并且将预取命令的发布成本和常规访问命令的发布成本相比较，以决定将要发布预取命令或常规访问命令中的哪一个。
5.一种预取命令控制装置，包括：
存储单元，用于存储具有附加的指定数据使用时间的信息的、用于外部资源的预取命令；
成本估算单元，用于估算由于当发布所存储的预取命令时，预取的数据停留在高速缓存中指定的使用时间所造成的成本；和发布单元，用于根据成本估算单元的估算结果调节发布用于外部资源的、所存储的预取命令的定时。
6.如权利要求5所述的装置，其中成本估算单元将预取命令的发布成本与存储在访问请求队列中的用于外部资源的常规访问命令相比较，而发布单元根据成本估算单元的比较结果决定当前时间将要发布预取命令或常规访问命令中的哪一个。
7.如权利要求5所述的装置，其中当发布预取命令时，成本估算单元计算由于存储在访问请求队列中的、用于外部资源的常规访问命令的发布延迟所造成的成本，以估算预取命令的发布成本。
8.如权利要求5-7中任意一个所述的装置，其中成本估算单元依据由从当前时间到指定的使用时间的时期定义的预取时间限制估算风险，以估算预取命令的发布成本。
9.一种高速缓冲存储器控制装置，包括：
高速缓冲存储器，用于缓存从外部资源获得的数据，并且将缓存的数据提供给处理器；
调度器，用于调度从处理器接收的、用于外部资源的访问协议，并且在请求队列中建立用于外部资源的调度的访问协议；和外部资源控制器，用于从请求队列中读取访问协议，并且访问外部资源来提供数据给高速缓冲存储器，和其中调度器包括：
存储单元，用于存储具有附加的指定数据使用时间的信息的、用于外部资源的预取命令；
成本估算单元，用于估算由于当发布所存储的预取命令时，预取的数据停留在高速缓存中指定的使用时间所造成的成本；和发布单元，用于根据成本估算单元的估算结果调节发布用于外部资源的、所存储的预取命令的定时。
10.如权利要求9所述的装置，其中在发布预取命令后调度器根据指定数据使用时间的信息锁定高速缓冲存储器中的预取数据的高速缓存。
11.如权利要求9所述的装置，其中成本估算单元将预取命令的发布成本与存储在访问请求队列中的、用于外部资源的常规访问命令相比较，而发布单元根据成本估算单元的比较结果决定当前时间将要发布预取命令或常规访问命令中的哪一个。
12.如权利要求9所述的装置，其中当发布预取命令时，成本估算单元计算由于存储在访问请求队列中的、用于外部资源的常规访问命令的发布延迟所造成的成本，以估算预取命令的发布成本。
13.如权利要求9-12中任意一个所述的装置，其中成本估算单元根据由从当前时间到指定的使用时间的时期定义的预取时间限制估算风险，以估算预取命令的发布成本。
14.一种目标代码命令产生方法，该方法包括：
分析源代码并将源代码转换为中间代码；
根据中间代码确定要预取的数据，然后将用于数据的访问命令作为预取命令插入到原始执行序列位置之前的位置，并且将用于指定数据的使用时间的信息添加到预取命令中；和优化插入了预取命令的中间代码并产生目标代码。
15.如权利要求14所述的目标代码命令产生方法，其中指定使用时间的信息包括指定要预取的数据的使用开始时间，这是由离插入预取命令的位置的相对位置定义的。
16.如权利要求15所述的目标代码命令产生方法，其中指定使用时间的信息包括指定要预取的数据的使用结束时间，这是由离插入预取命令的位置的相对位置定义的。
说明书 :
技术领域
本发明涉及高速缓存控制技术，尤其涉及预取命令控制方法和装置以及高速缓冲存储器控制装置。
背景技术
由计算机处理器定位诸如I/O和DRAM之类的主存储器的一方面是位置(locality)。通过利用这种位置并将存储在主存储器中的频繁定位的数据复制到高速缓冲存储器(高速可访问小容量内部存储器)中，并且通过该高速缓冲存储器访问主存储器，可以降低存储器访问的等待时间。随着处理器性能的改善，在针对处理器的高速数据提供方面，高速缓冲存储器的重要性也变得越来越显著。
当高速缓存命中时，处理器可以以高速缓冲存储器的访问速度获得需要的数据。但在高速缓存缺失(cache miss)的情况下，在从主存储器向高速缓冲存储器传送数据时，处理器需要停止程序执行。由于因高速缓冲存储器容量不够而使已缓存(cached)数据退出缓存(cached out)，或者正在定位的数据是第一次访问，当在主存储器中的数据的副本不存在于高速缓冲存储器时，发生高速缓存缺失。在前一种情况下，通过增加高速缓冲存储器容量可以避免该问题。然而，当高速缓冲存储器容量增加时，成本也增加，因此很难显著增加容量。在后一种情况下，通过使用称为预取的方法可以避免该问题，通过该方法期望在将来使用的数据在执行前传输到高速缓冲存储器。
预取是进一步降低存储器访问时间的有效途径。然而，投机预取可能实际上降低高速缓冲存储器的效率。这是因为如果当高速缓冲存储器很小时过分经常使用预取，则预取的数据将使已缓存的(cached)数据退出缓存。由于没有明确的发布预取命令的情形和时间的准则，虽然许多处理器是与预取命令兼容的，但实际情况是，预取命令时常不被有效地使用。
当高速缓存命中时，处理器可以以高速缓冲存储器的访问速度获得需要的数据。但在高速缓存缺失(cache miss)的情况下，在从主存储器向高速缓冲存储器传送数据时，处理器需要停止程序执行。由于因高速缓冲存储器容量不够而使已缓存(cached)数据退出缓存(cached out)，或者正在定位的数据是第一次访问，当在主存储器中的数据的副本不存在于高速缓冲存储器时，发生高速缓存缺失。在前一种情况下，通过增加高速缓冲存储器容量可以避免该问题。然而，当高速缓冲存储器容量增加时，成本也增加，因此很难显著增加容量。在后一种情况下，通过使用称为预取的方法可以避免该问题，通过该方法期望在将来使用的数据在执行前传输到高速缓冲存储器。
预取是进一步降低存储器访问时间的有效途径。然而，投机预取可能实际上降低高速缓冲存储器的效率。这是因为如果当高速缓冲存储器很小时过分经常使用预取，则预取的数据将使已缓存的(cached)数据退出缓存。由于没有明确的发布预取命令的情形和时间的准则，虽然许多处理器是与预取命令兼容的，但实际情况是，预取命令时常不被有效地使用。
发明内容
本发明依据解决上述问题的观点作出的，其目的是提供使有效的存储器存取实现的预取命令控制方法和装置，以及高速缓冲存储器控制装置。
根据本发明一个方面，提供预取命令控制方法。该方法包括：产生具有指定数据使用时间的信息的用于数据的预取命令；根据指定使用时间的信息调度预取命令的发布定时(issuance timing)；以及当发布预取命令时，根据预取的数据停留在高速缓存中的时期计算预取命令发布成本，其中根据发布成本调度预取命令的发布定时。
在预取命令中指定使用时间的信息可以包括以相对时间或绝对时间指定数据使用开始时间或结束时间的信息。发布定时可以是当预取命令作为用于外部资源的实际协议而执行的时间。发布定时的调度可以调节将发布预取命令的时间，调节将逐个发布的多个预取命令的次序。发布定时可以被调节在预取命令和诸如加载命令或存储命令之类的常规访问命令之间。
根据本发明的另一方面，提供预取命令控制装置。该装置包括：存储单元，用于存储具有附加的指定数据使用时间的信息的、用于外部资源的预取命令；成本估算单元，用于估算由于当发布所存储的预取命令时，预取的数据停留在高速缓存中指定的使用时间所造成的成本；和发布单元，用于根据成本估算单元的估算结果调节发布用于外部资源的、所存储的预取命令的定时。
成本估算单元可以将预取命令的发布成本与存储在访问请求队列中的用于外部资源的常规访问命令相比较，而发布单元可以根据成本估算单元的比较结果，决定将要发布预取命令或常规访问命令中的哪一个。只要发布单元发布命令，成本估算单元就可以重新计算发布成本，由此更新当前发布成本值。
当估算预取命令的发布成本时，可以一起估算由于存储在访问请求队列中的、用于外部资源的常规访问命令的发布延迟造成的成本或要预取的数据没有按数据使用时间预取的风险。
根据本发明的另一方面，提供高速缓冲存储器控制装置。该装置包括：高速缓冲存储器，用于缓存从外部资源获得的数据，并且将缓存的数据提供到处理器；调度器，用于调度从处理器接收的、用于外部资源的访问协议，并且在请求队列中建立用于外部资源的经调度的访问协议；和外部资源控制器，用于从请求队列中读取访问协议，并且访问外部资源以提供数据到高速缓冲存储器。调度器是上述预取命令控制装置。
在发布了预取命令之后，调度器可以在根据包含在指定数据使用时间的信息中的预取的数据的使用开始时间和使用结束时间的时期内，锁定高速缓冲存储器中的预取数据的高速缓存。
根据本发明的另一方面，提供目标代码命令产生方法，该方法包括：分析源代码并将源代码转换为中间代码；根据中间代码确定要预取的数据，然后将用于数据的访问命令作为预取命令插入到原始执行序列位置之前的位置，并且将用于指定数据的使用时间的信息添加到预取命令中；和优化插入到预取命令的中间代码并产生目标代码。
此外，上述结构部件和步骤的任意替代和代替、方法和装置的表达部分代替或全部代替以及其添加，以及改变为系统、计算机程序、存储介质、发布介质等等的表达都是有效的，并且由本发明涵盖。
本发明的发明内容不需要描述所有必要特征，所以本发明可以使这些所述特征的子组合。
根据本发明一个方面，提供预取命令控制方法。该方法包括：产生具有指定数据使用时间的信息的用于数据的预取命令；根据指定使用时间的信息调度预取命令的发布定时(issuance timing)；以及当发布预取命令时，根据预取的数据停留在高速缓存中的时期计算预取命令发布成本，其中根据发布成本调度预取命令的发布定时。
在预取命令中指定使用时间的信息可以包括以相对时间或绝对时间指定数据使用开始时间或结束时间的信息。发布定时可以是当预取命令作为用于外部资源的实际协议而执行的时间。发布定时的调度可以调节将发布预取命令的时间，调节将逐个发布的多个预取命令的次序。发布定时可以被调节在预取命令和诸如加载命令或存储命令之类的常规访问命令之间。
根据本发明的另一方面，提供预取命令控制装置。该装置包括：存储单元，用于存储具有附加的指定数据使用时间的信息的、用于外部资源的预取命令；成本估算单元，用于估算由于当发布所存储的预取命令时，预取的数据停留在高速缓存中指定的使用时间所造成的成本；和发布单元，用于根据成本估算单元的估算结果调节发布用于外部资源的、所存储的预取命令的定时。
成本估算单元可以将预取命令的发布成本与存储在访问请求队列中的用于外部资源的常规访问命令相比较，而发布单元可以根据成本估算单元的比较结果，决定将要发布预取命令或常规访问命令中的哪一个。只要发布单元发布命令，成本估算单元就可以重新计算发布成本，由此更新当前发布成本值。
当估算预取命令的发布成本时，可以一起估算由于存储在访问请求队列中的、用于外部资源的常规访问命令的发布延迟造成的成本或要预取的数据没有按数据使用时间预取的风险。
根据本发明的另一方面，提供高速缓冲存储器控制装置。该装置包括：高速缓冲存储器，用于缓存从外部资源获得的数据，并且将缓存的数据提供到处理器；调度器，用于调度从处理器接收的、用于外部资源的访问协议，并且在请求队列中建立用于外部资源的经调度的访问协议；和外部资源控制器，用于从请求队列中读取访问协议，并且访问外部资源以提供数据到高速缓冲存储器。调度器是上述预取命令控制装置。
在发布了预取命令之后，调度器可以在根据包含在指定数据使用时间的信息中的预取的数据的使用开始时间和使用结束时间的时期内，锁定高速缓冲存储器中的预取数据的高速缓存。
根据本发明的另一方面，提供目标代码命令产生方法，该方法包括：分析源代码并将源代码转换为中间代码；根据中间代码确定要预取的数据，然后将用于数据的访问命令作为预取命令插入到原始执行序列位置之前的位置，并且将用于指定数据的使用时间的信息添加到预取命令中；和优化插入到预取命令的中间代码并产生目标代码。
此外，上述结构部件和步骤的任意替代和代替、方法和装置的表达部分代替或全部代替以及其添加，以及改变为系统、计算机程序、存储介质、发布介质等等的表达都是有效的，并且由本发明涵盖。
本发明的发明内容不需要描述所有必要特征，所以本发明可以使这些所述特征的子组合。
附图说明
图1是根据本发明实施例的处理器系统的方框图。
图2是根据本发明实施例的描述程序编译的流程图。
图3(a)到图3(d)是描述根据图2的编译处理其中插入了扩展预取命令的程序的图。
图4是描述怎样通过发布扩展预取命令来锁定图1的高速缓冲存储器的高速缓存的图。
图5是根据其功能显示图1的桥接模块的方框图。
图6是描述图5的协议间隙(slot)产生单元的协议间隙产生处理的流程图。
图7是描述存储在图5的调度列表存储单元中的即时协议(just-in-time)的调度列表的图。
图8是描述存储在图5的常规协议队列存储单元中的常规协议队列的图。
图9是显示图5的成本估算单元的用于发布访问协议的成本的估算处理的流程图。
图10是描述调度列表和常规协议队列中的协议间隙的注册状态的图。
图2是根据本发明实施例的描述程序编译的流程图。
图3(a)到图3(d)是描述根据图2的编译处理其中插入了扩展预取命令的程序的图。
图4是描述怎样通过发布扩展预取命令来锁定图1的高速缓冲存储器的高速缓存的图。
图5是根据其功能显示图1的桥接模块的方框图。
图6是描述图5的协议间隙(slot)产生单元的协议间隙产生处理的流程图。
图7是描述存储在图5的调度列表存储单元中的即时协议(just-in-time)的调度列表的图。
图8是描述存储在图5的常规协议队列存储单元中的常规协议队列的图。
图9是显示图5的成本估算单元的用于发布访问协议的成本的估算处理的流程图。
图10是描述调度列表和常规协议队列中的协议间隙的注册状态的图。
具体实施方式
将参照优选实施例描述本发明。不希望以此限制本发明的范围，而是对本发明的示例性描述。
图1是根据本发明实施例的处理器系统的方框图。该处理器系统包括处理器模块10、桥接模块20、I/O模块30和存储器模块40。处理器模块10连接到内部总线32；I/O模块30连接到I/O总线34；并且存储器模块40连接到存储器总线36。桥接模块20桥接内部总线32和I/O总线34，并且通过处理器模10块控制对I/O模块30的数据读取/写入。桥接模块20桥接内部总线32和存储器总线36，并且通过处理器模10块控制对存储器模块40的数据读取/写入。
处理器模块10包括CPU 12、高速缓冲存储器14和高速缓存控制器16。当CPU 12指定I/O或DRAM的资源ID和数据地址，并且发布诸如装载命令、存储命令或预取命令之类的访问协议时，桥接模块20的调度器22在缓冲存储器24中注册访问协议间隙。调度器22控制诸如每个资源的访问等待时间和访问速度之类的静态资源数据，以及诸如所注册的访问协议的等待状态之类的动态数据。根据这些数据，调度用于访问协议发布的定时，并且在每个资源的请求队列中建立访问协议。
I/O控制器26和存储器控制器28读取分别建立在它们的请求队列中的访问协议，并且分别访问I/O模块30和存储器模块40来读出特定的地址数据。所读出的数据经由内部总线32传送到存储器模块10的高速缓存控制器16。高速缓存控制器16缓存所述高速缓冲存储器14中的所述数据，并且同时向CPU 12提供所述数据。然后，当CPU 12使用相同的地址访问数据时，高速缓存控制器16将缓存的数据从高速缓冲存储器14传送到CPU 12。在未命中高速缓存的情况下，如上所述经由桥接模块20读出数据。
具有桥接模块20的处理器模块10是根据本发明的高速缓存控制器的一个例子，而桥接模块20的、具有缓冲存储器24的调度器22是根据本发明的预取控制器的一个例子。
CPU 12执行在存储器模块40中加载的编译器，并且编译程序的源代码并产生目标代码。在该目标代码的产生过程中，插入预取命令。
图2是描述程序编译的流程图。编译器分析程序的源代码并将其转换为中间代码(S10)。然后，编译器根据中间数据确定由加载命令访问的数据中的要预取的数据，并且计算该数据的地址(S12)。然后，编译器将该数据地址指定为参数(argument)的预取命令插入到加载命令的执行序列位置之前的位置，并且将指定数据使用时间的信息作为另一参数添加到预取命令，其显示从预取命令插入位置起，实际数据使用时间将会有多少步(S14)。因此，编译器优化具有指定数据使用时间的信息的预取命令(下面称为“扩展预取命令”)插入到的中间代码(步骤S16)，并且产生目标代码(S18)。还可以由仔细调节的(carefully tuned)汇编程序而不是编译器来插入扩展的预取命令。
图3(a)到图3(d)是描述根据图2的编译处理插入了扩展的预取命令的程序的实例的图。程序60包括诸如加载命令(LD)、存储命令(ST)和扩展预取命令(PreFetch)之类的访问协议。在图3(a)的实例中，用于预缓存数据区域yyy的扩展的预取命令62a被插入到加载命令64的执行序列位置之前n步的位置上，其中数据区域yyy包括要在加载命令64、66中使用的数据yyy-0和yyy-1。
对于扩展的预取命令62a的参数，指定要预取的数据区域yyy和使用开始时间n。利用使用开始时间n，可以知道在扩展的预取命令62a的插入位置n步后的位置访问数据区域yyy。然而，不知道在所述插入位置(n+1)步后的位置或之后是否存在对数据区域yyy的访问。对于正常排列的数据，同时访问在数据区域yyy中的相邻数据，以便会有在所述插入位置(n+1)步后的位置或之后对数据区域yyy中数据进行访问的可能性。因此，如斜线所标示的那样，从扩展的预取命令62a的使用开始时间n仅能判断出在所述插入位置n步后的位置或之后将存在某些对数据区域yyy的访问。
在图3(b)的实例中，对于扩展的预取命令62b的参数，作为指定使用时间的信息，指定要预取的数据区域yyy的使用开始时间n和使用结束时间m。由加载命令64在扩展的预取命令62b的插入位置n步之后首次访问数据区域，并且由存储命令68在所述插入位置m步之后最后访问数据区域。换句话说，将仅访问在斜线标记的部分中的数据区域yyy。因此，通过指定数据区域yyy的使用开始时间n和使用结束时间m，可以定义应该锁定数据区域yyy的高速缓存的时期。
在图3(c)的实例中，对于扩展的预取命令62c的参数，指定要预取的数据区域yyy的使用开始时间和优先级c。当注册了多个预取命令时，优先级c用于决定应该首先发布哪个预取命令。当预取的数据退出缓存(cached out)时，优先级c也用于决定应该首先将哪个高速缓存数据退出缓存。
在图3(d)的实例中，对于扩展的预取命令62b的参数，作为指定要预取的数据区域yyy的使用时间的信息，指定如上所述的使用开始时间n和使用结束时间m，并且还指定优先级c。
图4是描述怎样通过发布扩展预取命令来锁定高速缓冲存储器14的高速缓存的图。这里使用图3(d)中的扩展的预取命令62d作为实例来进行描述。当由CPU 12执行程序60，并且程序计数器PC到达图中所示的位置时，发布预取命令62d。在预取命令62d中使用下面的参数：数据区域yyy；使用开始时间n；使用结束时间m；优先权c；和程序计数器PC值pc，CPU 12发布即时(just-in-time)协议LoadtoCache(yyy，pc，n，m，c)到调度器22。
接收由CPU 12发布的即时协议的调度器22向高速缓存控制器16发出命令，作出保留以从当前程序计数器PC值pc开始锁定数据区域yyy的高速缓存直到(pc+m)步。根据诸如像要访问的DRAM和I/O的资源的等待时间和带宽之类的静态特征，以及资源请求队列的动态条件，调度器22调度预取命令62d的发布定时，并且在资源的请求协议队列中建立实际协议。当发布实际协议时，调度器22向高速缓存控制器16发出开始锁定数据区域yyy的高速缓存的命令。高速缓存控制16在从当接收到开始锁定的命令时的点到完成锁定的点的时期内锁定数据区域yyy的高速缓存，这是由做出保留的命令指定的。
图5是根据其功能显示图1中描述的桥接模块20的方框图。协议间隙产生单元50、成本估算单元52和协议发布单元54包含在图1的调度器22的功能配置中。调度列表存储单元56和常规协议队列存储单元58包含在图1的缓冲存储器24的功能配置中。
协议间隙(slot)产生单元50从CPU 12接收访问协议。对于访问协议，有根据扩展预取命令的即时协议和根据加载命令或存储命令的常规访问协议。
图6是描述协议间隙产生单元50的协议间隙产生处理的流程图。首先，协议间隙产生单元50识别从CPU 12接收的访问协议的类型是即时协议还是其它协议(S20)。如果是即时协议(S20为是)，则根据调度器22中的计数器的单位时间校正使用时间，该时间由扩展的预取命令指定为从程序计数器PC值pc开始的n步(S22)。接下来，产生协议间隙，用于根据该即时协议显示将占用资源的时间(S24)。在存储在调度列表存储单元56中的即时协议的调度列表70中注册所产生的协议间隙(S26)。
在步骤S20中，当从CPU 12接收的访问协议不是即时协议时(S20为“否”)，协议间隙产生单元50将该访问协议作为常规协议处理，并产生指示资源占用时间的协议间隙(S28)。所产生的协议间隙插入到存储在常规协议队列存储单元58中的常规协议队列90中(S30)。
图7是描述存储在图5的调度列表存储单元56中的即时协议(just-in-time)的调度列表70的图。通过在纵轴上设置根据调度器22的计数器的单元时间校正过的时间，用图解法显示了调度列表70的协议间隙的当前时间st上的注册状态。调度列表70划分为最小的时间单位以用于调度器22的计数器。如斜线标记的区域所示，即时协议的间隙72a、74和76分别存储在从当前时间st开始的2单位时间、4单位时间和8单位时间时期后。这意味着由这些协议间隙72a、74和76预取的数据的使用时间分别是(st+2)、(st+4)和(st+8)。然而，该图仅仅是通过根据每个协议间隙指定的使用开始时间来显示协议间隙的存储位置来帮助理解的模式图。在实际的实现中，将协议间隙与作为索引的使用时间scti和优先级ci的组合一起注册在调度列表70中，并且从最早使用时间scti开始的顺序存储它们，以形成如图中的指针所示连接的列表结构。
即时协议通常写成jtp(sct，rfrom，ptfrom，rto，ptto，c)。这里，第一参数sct是使用时间，而第六参数c是优先级。第二参数rfrom是数据传送源，而第四参数rto是数据接收源。第三参数ptfrom是占用数据传送源的时间，而第五参数ptto是占用数据接收源的时间。根据数据传送速度和资源的等待时间等确定资源占用时间。例如，对于资源，有DRAM、I/O、高速缓冲存储器等。可以使用该描述方法来描述从I/O传送到高速缓冲存储器的数据或从高速缓冲存储器到I/O的数据。
在图7的实例中，有四种要访问的资源r1到r4。即时协议jtpi是通过在占用时间pt3和pt1分别占用数据传送资源r3和数据接收资源r1来传送数据的访问协议。该协议可以写成jtpi(scti，r3，pt3，r1，pt1，ci)。如图所示，即时协议jtpi的协议间隙72a的数据结构72b将指定第一资源r1的占用时间pt1和第三资源r3的占用时间pt3。
这里，在四个资源r1到r4中，对于第一资源r1和第二资源r2，根据调度器22的计数器的最小单位时间计数它们的占用时间。同时，根据双倍单位时间计数第三资源r3的占用时间，并且根据四倍单位时间计数第四资源r4的占用时间。这是因为资源的访问占用时间的最小单位不同。在下面，为了使描述更简单，根据调度器22的计数器的最小单元表示占用时间，而不考虑每个资源的访问占用时间的最小单位。例如，在即时协议jtpi中，根据第三资源r3的访问占用时间的最小单位仅占用第三资源r3的1个单位时间。然而，这对应于调度器22的计数器的最小单元的三个单元的时间。因此，为了便于解释，根据调度器22的计数器的最小单元表示第三资源r3的占用时间pt3，其表示为3个单位时间。因此，即时协议jtpi可以写成jtpi(scti，r3，3，r1，2，ci)。这里，数据接收源r1的占用开始时间是比数据传送资源r3的占用开始时间晚一个单位时间的时间。这意味着在数据传送资源r3的访问开始后经过一个单位时间之前不开始数据接收源r1的数据传送。
图8是描述存储在图5的常规协议队列存储单元58中的常规协议队列90的图。在数据访问之前，按实际数据访问定时，从CPU 12发布与从CPU 12发布的即时协议不同的常规协议。协议间隙产生单元50以从CPU 12发布的第一个开始、到常规协议队列90中的最后一个的顺序逐个插入常规协议间隙。然而，协议间隙产生单元50可以通过改变顺序来优化注册在常规协议队列90中的协议间隙，因此没有空闲时间，或者根据优先级改变顺序。
常规协议通常可以写成np(rfrom，ptfrom，rto，ptto，c)。参数的定义与即时协议的情况相同。第五参数，即优先级c是可选项，并且在某些情况下不使用它。优先级c的使用方法与即时协议的情况相同。在图8的实例中，在当前时间st，从第i到第(i+3)(npi、npi+1、npi+2和npi+3)的常规协议的间隙注册在常规协议队列90中。从第i到第(i+3)的常规协议分别写成npi(r1，6，r2，6，ci)、npi+1(r3，3，r4，6，ci+1)、npi+2(r2，2，r3，3，ci+2)、npi+3(r4，6，r3，3，ci+3)。顺序取得并发布在位于常规协议队列90的头部的输出间隙中的常规协议。
再次参考图5的功能配置图，成本估算单元52估算常规协议队列90中处于等待状态的常规协议的发布成本，和注册在调度列表70中的即时协议的发布成本，并且比较这些发布成本。协议发布单元54发布具有较小发布成本的协议。根据资源ID，如果是用于I/O的命令，则将发布的协议发送到I/O控制器26，而如果是用于像DRAM的主存储器的命令，则发送到存储器控制器28，并执行它们。
图9是显示成本估算单元52的用于访问协议的发布成本的估算处理的流程图。图10是描述调度列表70和常规协议队列90中的协议间隙的注册状态的图。将参照这些图来进行解释。
成本估算单元52计算常规协议发布成本(S40)。常规协议发布成本Np通常是在常规协议队列90的输出间隙中的常规协议np和当前时间st的函数。这里，如下面的等式所示，当发布输出间隙中的常规协议np时，通过计算由于在时间t占用数据传送资源rfrom的成本Rcfrom(t)和由于在时间t占用数据接收资源rto的成本Rcto(t)的线性之和可以获得成本Np。Np＝np_cost_func(np，st)＝Rcfrom(st)+Rcto(st+α)。这里，常量α是数据传送资源的占用开始时间和数据接收资源的占用开始事件之间的时间差。
在图10中的常规协议队列90的实例中，常规协议np1存在于输出间隙中。如果在当前时间st发布该常规协议np1，则在当前时间st开始访问数据传送资源r3，并且仅占用数据传送资源r3三个单位时间。通过RC3(st)计算该时间内占用成本。同时，在2个单位时间后开始访问接收资源r2，并且仅占用接收资源r2一个单位时间。通过RC2(st+2)计算该时间内占用成本。因此，通过公式Np＝RC3(t)+RC2(t+2)计算常规协议发布成本Np。
接下来，成本估算单元52计算即时协议发布成本jtpcost(S42)。成本估算单元52估算关于调度列表70中注册的所有协议间隙的发布成本jtpcost。然而，可以仅仅估算具有最接近当前时间st的使用时间sct的协议间隙或具有最高优先级c的协议间隙的发布成本jtpcost。此外，可以以从最接近当前时间st的使用时间sct开始的顺序估算数个协议间隙发布成本jtpcost，或者以从具有最高优先级c的协议间隙开始的顺序估算数个协议间隙发布成本jtpcost。在图10中的实例，在调度列表70中，注册了用于两个即时协议jtp1(sct1，r1，pt1，r2，pt2，c1)和jtp2(sct2，r2，pt2，r4，pt4，c2)的间隙。成本估算单元52独立地计算相应协议间隙的发布成本jtpcost1和jtpcost2。
根据几个成本因素的组合计算即时协议发布成本jtpcost。第一成本因素是常规协议发布延迟成本LC。这是当发布即时协议时，由于在常规协议队列90中处于等待状态中的常规协议发布延迟造成的每个单元时间的成本。常规协议发布延迟成本通常是应用到存储在常规协议队列90中的所有常规协议的函数。这里，它是为各个常规协议npi计算的延迟成本LCs(npi)的线性和。在图10的实例中，在当前时间，五个常规协议np1到np5在常规协议队列90中处于等待状态，因此通过下面的公式计算常规协议发布延迟成本LC：
LC＝Lcfunc(np1，np2，np3，np4，np5)＝LC(np1)+LC(np2)+LC(np3)+LC(np4)+LC(np5)
这里，延迟成本LC(npi)是当常规协议npi具有仅仅一单位时间的延迟时间时造成的成本。
当在常规协议npi中指定优先级ci时，延迟成本写成LC(npi，ci)，并且可以设置其值，以使得它反映每个常规协议npi的优先级ci。例如，对于具有高优先级ci的常规协议npi可以将其延迟成本LC(pi，ci)估算得更高。
在图10的实例中，如该协议的间隙82所示，当发布第一即时协议jtp1(sct1，r1，pt1，r2，pt2，c1)时，从当前时间st起占用数据接收资源r25个单位时间，这与由常规协议队列90的输出间隙中的常规协议np1占用资源r2的时间重叠。因此，如图所示，为了执行即时协议jtp1，常规协议队列90的输出间隙86向后偏移时间1tc1，即3单位时间。通过使输出间隙86中的常规协议延迟3个单位时间，在常规协议队列90中处于等待状态的其它常规协议np2到np5也全部延迟3个单位时间。因此，总体上，通过发布即时协议jtp1，通过将常规协议发布延迟成本LC与输出间隙86的延迟时间1tc1相乘产生成本LC*1tc1。
以相同的方式，当发布第二即时协议jtp2时，可以根据该协议的间隙84和常规协议队列90中的协议间隙之间的资源占用时间的竞争关系计算延迟时间1tc2。通常，通过公式LC*1tci计算从发布即时协议jtpi产生的常规协议发布延迟成本。
即时协议发布成本jtpcost的第二成本因素是预取数据的高速缓存保留成本CacheRC。这是由于当发布即时协议时，预取的数据停留在高速缓冲存储器14中而产生的每单位时间的成本。当在当前时间st发布即时协议jtpi时，值cti＝(scti-st)，这是从要由即时协议jtpi预取的数据的使用时间scti减去当前时间st产生的，并且等于预取的数据在高速缓冲存储器14中保留的时间。因此，通过(scti-st)*CacheRC：每单位时间保留成本CacheRC乘以保留时间cti＝(scti-st)来计算由于在当前时间st发布即时协议jtpi产生的高速缓存成本。
第三成本因素是由于即时协议jtpi延迟导致在指定的使用时间内没有预取正在访问的数据的风险。使用即时协议jtpi和当前时间st作为函数的参数，通过Time_Limit_Func(jtpi，st)计算该成本。例如，该风险定义为如下的公式：
Time_Limit_Func(jtpi，st)＝(当scti-st＜max(ptfrom，ptto)+a时为Time_Limit，否则为0)。
当预取的数据高速缓存保留时间(scti-st)小于由于预取导致的数据传送资源rfrom的占用时间ptfrom或数据接收资源rto的占用时间ptto的最大值max(ptfrom，ptto)，使用时间scti不能完成数据预取。所以，高速缓存保留时间与通过相加常量a计算的值相比较，给出该常量来达到max(ptfrom，ptto)。当高速缓存保留时间(scti-st)小时，风险值将会是正常数Time_Limit，并且高速缓存保留时间(scti-st)大时，风险值将会是0。
根据以上三个成本因素计算当前时间st的即时协议jtpi发布成本jtpcosti：
jtpcosti＝jtp_cost-func(st，jtpi)
＝LC*1tci+(scti-st)*CacheRC-Time_Limit_Func(jtpi，st)
当情形处于不能完成预取时，第三项Time_Limit_Func(jtpi，st)为正数，并且从第一项LC*1tci和第二项(scti-st)*CacheRC减去它，所以总体上导致jtpcosti的值降低。因此，在好像很难保留即时协议的情形中，冲击在执行即时协议造成的成本和不执行即时协议所造成的风险之间的平衡。
返回到图9，当在当前时间st即时协议发布成本jtpcost小于常规协议发布成本Np时(S44的“是”)，协议发布单元54发布即时协议(S46)，如果即时协议发布成本jtpcost不小于常规协议发布成本(S44的“否”)，协则议发布单元54发布常规协议(S48)。一旦发布了两种协议之一，处理就返回到步骤S40。然后，在那个时间点进行新的成本计算，并且根据每个时间点的成本估算来选择并发布合适的协议。
在图10的例子中，将调度列表70中注册的第一即时协议jtp1发布成本jtpcost1、第二即时协议jtp2发布成本jtpcost2和常规协议队列90的输出间隙中的常规协议np1的发布成本NP相比较，并且由程序发布单元54发布最小的成本协议。这里，必须注意的是，因为在常规协议队列90中的协议的等待状态每次改变，每次需要重新计算即时协议发布成本，因此发布成本的计算公式的第一项的值LC*1tci改变。此外，存在与第一即时协议jtp1发布成本jtpcost1、第二即时协议jtp2发布成本jtpcost2相关的值由于以上相同原因而每次改变的可能性。所以，不保证具有与当前时间st接近的使用时间sct的即时协议将具有更小的发布成本。
此外，可以通过仅部分使用三个成本因素来估算即时协议发布成本jtpcosti。例如，通过仅使用高速缓存保留成本通过下面的公式可以得出估算：
jtpcosti＝(scti-st)*CacheRC
此外，下面的公式也可以用于估算，它还包括不能完成预取的风险因素：
jtpcosti＝(scti-st)*CacheRC-Time_Limit_Func(jtpi，st)
当使用上面的公式时，可以相对于常规协议队列90的协议间隙的条件独立地估算即时协议发布成本，这简化了成本计算。
如上所述，根据实施例，通过指定要在预取命令中预取的数据的使用时间，可以预测预取数据停留在高速缓存的时期，通过估算高速缓存保留成本这使得可以做出关于预取命令的发布定时的决定。此外，通过考虑资源占用时间之间的竞争关系做出成本估算，可以在冲击与其他访问命令的平衡时发布预取命令。结果，不会不必要地而是按计划执行预取命令，并且改善高速缓存可用性。
虽然通过示例性实施例的方式描述了本发明，但本领域内的普通技术人员将理解的是，可在不背离由所附权利要求书限定的本发明宗旨和范围的前提下对本发明进行各种形式和细节上的修改。在下面声明了某些这样的变型。
在上面的描述中，在扩展的预取命令中，根据从扩展的命令的插入位置开始计数的相对步数来指定预取的数据的使用开始点和结束点。然而，可以根据绝对时间指定预取的数据的使用开始点和结束点。
此外，在上面的描述中，计算并比较即时协议和常规协议的发布成本来决定将要发布哪个访问协议。然而，简单计算即时协议发布成本并且如果其值等于或低于预定值，则做出发布即时协议的决定也是可以接受的。
图1是根据本发明实施例的处理器系统的方框图。该处理器系统包括处理器模块10、桥接模块20、I/O模块30和存储器模块40。处理器模块10连接到内部总线32；I/O模块30连接到I/O总线34；并且存储器模块40连接到存储器总线36。桥接模块20桥接内部总线32和I/O总线34，并且通过处理器模10块控制对I/O模块30的数据读取/写入。桥接模块20桥接内部总线32和存储器总线36，并且通过处理器模10块控制对存储器模块40的数据读取/写入。
处理器模块10包括CPU 12、高速缓冲存储器14和高速缓存控制器16。当CPU 12指定I/O或DRAM的资源ID和数据地址，并且发布诸如装载命令、存储命令或预取命令之类的访问协议时，桥接模块20的调度器22在缓冲存储器24中注册访问协议间隙。调度器22控制诸如每个资源的访问等待时间和访问速度之类的静态资源数据，以及诸如所注册的访问协议的等待状态之类的动态数据。根据这些数据，调度用于访问协议发布的定时，并且在每个资源的请求队列中建立访问协议。
I/O控制器26和存储器控制器28读取分别建立在它们的请求队列中的访问协议，并且分别访问I/O模块30和存储器模块40来读出特定的地址数据。所读出的数据经由内部总线32传送到存储器模块10的高速缓存控制器16。高速缓存控制器16缓存所述高速缓冲存储器14中的所述数据，并且同时向CPU 12提供所述数据。然后，当CPU 12使用相同的地址访问数据时，高速缓存控制器16将缓存的数据从高速缓冲存储器14传送到CPU 12。在未命中高速缓存的情况下，如上所述经由桥接模块20读出数据。
具有桥接模块20的处理器模块10是根据本发明的高速缓存控制器的一个例子，而桥接模块20的、具有缓冲存储器24的调度器22是根据本发明的预取控制器的一个例子。
CPU 12执行在存储器模块40中加载的编译器，并且编译程序的源代码并产生目标代码。在该目标代码的产生过程中，插入预取命令。
图2是描述程序编译的流程图。编译器分析程序的源代码并将其转换为中间代码(S10)。然后，编译器根据中间数据确定由加载命令访问的数据中的要预取的数据，并且计算该数据的地址(S12)。然后，编译器将该数据地址指定为参数(argument)的预取命令插入到加载命令的执行序列位置之前的位置，并且将指定数据使用时间的信息作为另一参数添加到预取命令，其显示从预取命令插入位置起，实际数据使用时间将会有多少步(S14)。因此，编译器优化具有指定数据使用时间的信息的预取命令(下面称为“扩展预取命令”)插入到的中间代码(步骤S16)，并且产生目标代码(S18)。还可以由仔细调节的(carefully tuned)汇编程序而不是编译器来插入扩展的预取命令。
图3(a)到图3(d)是描述根据图2的编译处理插入了扩展的预取命令的程序的实例的图。程序60包括诸如加载命令(LD)、存储命令(ST)和扩展预取命令(PreFetch)之类的访问协议。在图3(a)的实例中，用于预缓存数据区域yyy的扩展的预取命令62a被插入到加载命令64的执行序列位置之前n步的位置上，其中数据区域yyy包括要在加载命令64、66中使用的数据yyy-0和yyy-1。
对于扩展的预取命令62a的参数，指定要预取的数据区域yyy和使用开始时间n。利用使用开始时间n，可以知道在扩展的预取命令62a的插入位置n步后的位置访问数据区域yyy。然而，不知道在所述插入位置(n+1)步后的位置或之后是否存在对数据区域yyy的访问。对于正常排列的数据，同时访问在数据区域yyy中的相邻数据，以便会有在所述插入位置(n+1)步后的位置或之后对数据区域yyy中数据进行访问的可能性。因此，如斜线所标示的那样，从扩展的预取命令62a的使用开始时间n仅能判断出在所述插入位置n步后的位置或之后将存在某些对数据区域yyy的访问。
在图3(b)的实例中，对于扩展的预取命令62b的参数，作为指定使用时间的信息，指定要预取的数据区域yyy的使用开始时间n和使用结束时间m。由加载命令64在扩展的预取命令62b的插入位置n步之后首次访问数据区域，并且由存储命令68在所述插入位置m步之后最后访问数据区域。换句话说，将仅访问在斜线标记的部分中的数据区域yyy。因此，通过指定数据区域yyy的使用开始时间n和使用结束时间m，可以定义应该锁定数据区域yyy的高速缓存的时期。
在图3(c)的实例中，对于扩展的预取命令62c的参数，指定要预取的数据区域yyy的使用开始时间和优先级c。当注册了多个预取命令时，优先级c用于决定应该首先发布哪个预取命令。当预取的数据退出缓存(cached out)时，优先级c也用于决定应该首先将哪个高速缓存数据退出缓存。
在图3(d)的实例中，对于扩展的预取命令62b的参数，作为指定要预取的数据区域yyy的使用时间的信息，指定如上所述的使用开始时间n和使用结束时间m，并且还指定优先级c。
图4是描述怎样通过发布扩展预取命令来锁定高速缓冲存储器14的高速缓存的图。这里使用图3(d)中的扩展的预取命令62d作为实例来进行描述。当由CPU 12执行程序60，并且程序计数器PC到达图中所示的位置时，发布预取命令62d。在预取命令62d中使用下面的参数：数据区域yyy；使用开始时间n；使用结束时间m；优先权c；和程序计数器PC值pc，CPU 12发布即时(just-in-time)协议LoadtoCache(yyy，pc，n，m，c)到调度器22。
接收由CPU 12发布的即时协议的调度器22向高速缓存控制器16发出命令，作出保留以从当前程序计数器PC值pc开始锁定数据区域yyy的高速缓存直到(pc+m)步。根据诸如像要访问的DRAM和I/O的资源的等待时间和带宽之类的静态特征，以及资源请求队列的动态条件，调度器22调度预取命令62d的发布定时，并且在资源的请求协议队列中建立实际协议。当发布实际协议时，调度器22向高速缓存控制器16发出开始锁定数据区域yyy的高速缓存的命令。高速缓存控制16在从当接收到开始锁定的命令时的点到完成锁定的点的时期内锁定数据区域yyy的高速缓存，这是由做出保留的命令指定的。
图5是根据其功能显示图1中描述的桥接模块20的方框图。协议间隙产生单元50、成本估算单元52和协议发布单元54包含在图1的调度器22的功能配置中。调度列表存储单元56和常规协议队列存储单元58包含在图1的缓冲存储器24的功能配置中。
协议间隙(slot)产生单元50从CPU 12接收访问协议。对于访问协议，有根据扩展预取命令的即时协议和根据加载命令或存储命令的常规访问协议。
图6是描述协议间隙产生单元50的协议间隙产生处理的流程图。首先，协议间隙产生单元50识别从CPU 12接收的访问协议的类型是即时协议还是其它协议(S20)。如果是即时协议(S20为是)，则根据调度器22中的计数器的单位时间校正使用时间，该时间由扩展的预取命令指定为从程序计数器PC值pc开始的n步(S22)。接下来，产生协议间隙，用于根据该即时协议显示将占用资源的时间(S24)。在存储在调度列表存储单元56中的即时协议的调度列表70中注册所产生的协议间隙(S26)。
在步骤S20中，当从CPU 12接收的访问协议不是即时协议时(S20为“否”)，协议间隙产生单元50将该访问协议作为常规协议处理，并产生指示资源占用时间的协议间隙(S28)。所产生的协议间隙插入到存储在常规协议队列存储单元58中的常规协议队列90中(S30)。
图7是描述存储在图5的调度列表存储单元56中的即时协议(just-in-time)的调度列表70的图。通过在纵轴上设置根据调度器22的计数器的单元时间校正过的时间，用图解法显示了调度列表70的协议间隙的当前时间st上的注册状态。调度列表70划分为最小的时间单位以用于调度器22的计数器。如斜线标记的区域所示，即时协议的间隙72a、74和76分别存储在从当前时间st开始的2单位时间、4单位时间和8单位时间时期后。这意味着由这些协议间隙72a、74和76预取的数据的使用时间分别是(st+2)、(st+4)和(st+8)。然而，该图仅仅是通过根据每个协议间隙指定的使用开始时间来显示协议间隙的存储位置来帮助理解的模式图。在实际的实现中，将协议间隙与作为索引的使用时间scti和优先级ci的组合一起注册在调度列表70中，并且从最早使用时间scti开始的顺序存储它们，以形成如图中的指针所示连接的列表结构。
即时协议通常写成jtp(sct，rfrom，ptfrom，rto，ptto，c)。这里，第一参数sct是使用时间，而第六参数c是优先级。第二参数rfrom是数据传送源，而第四参数rto是数据接收源。第三参数ptfrom是占用数据传送源的时间，而第五参数ptto是占用数据接收源的时间。根据数据传送速度和资源的等待时间等确定资源占用时间。例如，对于资源，有DRAM、I/O、高速缓冲存储器等。可以使用该描述方法来描述从I/O传送到高速缓冲存储器的数据或从高速缓冲存储器到I/O的数据。
在图7的实例中，有四种要访问的资源r1到r4。即时协议jtpi是通过在占用时间pt3和pt1分别占用数据传送资源r3和数据接收资源r1来传送数据的访问协议。该协议可以写成jtpi(scti，r3，pt3，r1，pt1，ci)。如图所示，即时协议jtpi的协议间隙72a的数据结构72b将指定第一资源r1的占用时间pt1和第三资源r3的占用时间pt3。
这里，在四个资源r1到r4中，对于第一资源r1和第二资源r2，根据调度器22的计数器的最小单位时间计数它们的占用时间。同时，根据双倍单位时间计数第三资源r3的占用时间，并且根据四倍单位时间计数第四资源r4的占用时间。这是因为资源的访问占用时间的最小单位不同。在下面，为了使描述更简单，根据调度器22的计数器的最小单元表示占用时间，而不考虑每个资源的访问占用时间的最小单位。例如，在即时协议jtpi中，根据第三资源r3的访问占用时间的最小单位仅占用第三资源r3的1个单位时间。然而，这对应于调度器22的计数器的最小单元的三个单元的时间。因此，为了便于解释，根据调度器22的计数器的最小单元表示第三资源r3的占用时间pt3，其表示为3个单位时间。因此，即时协议jtpi可以写成jtpi(scti，r3，3，r1，2，ci)。这里，数据接收源r1的占用开始时间是比数据传送资源r3的占用开始时间晚一个单位时间的时间。这意味着在数据传送资源r3的访问开始后经过一个单位时间之前不开始数据接收源r1的数据传送。
图8是描述存储在图5的常规协议队列存储单元58中的常规协议队列90的图。在数据访问之前，按实际数据访问定时，从CPU 12发布与从CPU 12发布的即时协议不同的常规协议。协议间隙产生单元50以从CPU 12发布的第一个开始、到常规协议队列90中的最后一个的顺序逐个插入常规协议间隙。然而，协议间隙产生单元50可以通过改变顺序来优化注册在常规协议队列90中的协议间隙，因此没有空闲时间，或者根据优先级改变顺序。
常规协议通常可以写成np(rfrom，ptfrom，rto，ptto，c)。参数的定义与即时协议的情况相同。第五参数，即优先级c是可选项，并且在某些情况下不使用它。优先级c的使用方法与即时协议的情况相同。在图8的实例中，在当前时间st，从第i到第(i+3)(npi、npi+1、npi+2和npi+3)的常规协议的间隙注册在常规协议队列90中。从第i到第(i+3)的常规协议分别写成npi(r1，6，r2，6，ci)、npi+1(r3，3，r4，6，ci+1)、npi+2(r2，2，r3，3，ci+2)、npi+3(r4，6，r3，3，ci+3)。顺序取得并发布在位于常规协议队列90的头部的输出间隙中的常规协议。
再次参考图5的功能配置图，成本估算单元52估算常规协议队列90中处于等待状态的常规协议的发布成本，和注册在调度列表70中的即时协议的发布成本，并且比较这些发布成本。协议发布单元54发布具有较小发布成本的协议。根据资源ID，如果是用于I/O的命令，则将发布的协议发送到I/O控制器26，而如果是用于像DRAM的主存储器的命令，则发送到存储器控制器28，并执行它们。
图9是显示成本估算单元52的用于访问协议的发布成本的估算处理的流程图。图10是描述调度列表70和常规协议队列90中的协议间隙的注册状态的图。将参照这些图来进行解释。
成本估算单元52计算常规协议发布成本(S40)。常规协议发布成本Np通常是在常规协议队列90的输出间隙中的常规协议np和当前时间st的函数。这里，如下面的等式所示，当发布输出间隙中的常规协议np时，通过计算由于在时间t占用数据传送资源rfrom的成本Rcfrom(t)和由于在时间t占用数据接收资源rto的成本Rcto(t)的线性之和可以获得成本Np。Np＝np_cost_func(np，st)＝Rcfrom(st)+Rcto(st+α)。这里，常量α是数据传送资源的占用开始时间和数据接收资源的占用开始事件之间的时间差。
在图10中的常规协议队列90的实例中，常规协议np1存在于输出间隙中。如果在当前时间st发布该常规协议np1，则在当前时间st开始访问数据传送资源r3，并且仅占用数据传送资源r3三个单位时间。通过RC3(st)计算该时间内占用成本。同时，在2个单位时间后开始访问接收资源r2，并且仅占用接收资源r2一个单位时间。通过RC2(st+2)计算该时间内占用成本。因此，通过公式Np＝RC3(t)+RC2(t+2)计算常规协议发布成本Np。
接下来，成本估算单元52计算即时协议发布成本jtpcost(S42)。成本估算单元52估算关于调度列表70中注册的所有协议间隙的发布成本jtpcost。然而，可以仅仅估算具有最接近当前时间st的使用时间sct的协议间隙或具有最高优先级c的协议间隙的发布成本jtpcost。此外，可以以从最接近当前时间st的使用时间sct开始的顺序估算数个协议间隙发布成本jtpcost，或者以从具有最高优先级c的协议间隙开始的顺序估算数个协议间隙发布成本jtpcost。在图10中的实例，在调度列表70中，注册了用于两个即时协议jtp1(sct1，r1，pt1，r2，pt2，c1)和jtp2(sct2，r2，pt2，r4，pt4，c2)的间隙。成本估算单元52独立地计算相应协议间隙的发布成本jtpcost1和jtpcost2。
根据几个成本因素的组合计算即时协议发布成本jtpcost。第一成本因素是常规协议发布延迟成本LC。这是当发布即时协议时，由于在常规协议队列90中处于等待状态中的常规协议发布延迟造成的每个单元时间的成本。常规协议发布延迟成本通常是应用到存储在常规协议队列90中的所有常规协议的函数。这里，它是为各个常规协议npi计算的延迟成本LCs(npi)的线性和。在图10的实例中，在当前时间，五个常规协议np1到np5在常规协议队列90中处于等待状态，因此通过下面的公式计算常规协议发布延迟成本LC：
LC＝Lcfunc(np1，np2，np3，np4，np5)＝LC(np1)+LC(np2)+LC(np3)+LC(np4)+LC(np5)
这里，延迟成本LC(npi)是当常规协议npi具有仅仅一单位时间的延迟时间时造成的成本。
当在常规协议npi中指定优先级ci时，延迟成本写成LC(npi，ci)，并且可以设置其值，以使得它反映每个常规协议npi的优先级ci。例如，对于具有高优先级ci的常规协议npi可以将其延迟成本LC(pi，ci)估算得更高。
在图10的实例中，如该协议的间隙82所示，当发布第一即时协议jtp1(sct1，r1，pt1，r2，pt2，c1)时，从当前时间st起占用数据接收资源r25个单位时间，这与由常规协议队列90的输出间隙中的常规协议np1占用资源r2的时间重叠。因此，如图所示，为了执行即时协议jtp1，常规协议队列90的输出间隙86向后偏移时间1tc1，即3单位时间。通过使输出间隙86中的常规协议延迟3个单位时间，在常规协议队列90中处于等待状态的其它常规协议np2到np5也全部延迟3个单位时间。因此，总体上，通过发布即时协议jtp1，通过将常规协议发布延迟成本LC与输出间隙86的延迟时间1tc1相乘产生成本LC*1tc1。
以相同的方式，当发布第二即时协议jtp2时，可以根据该协议的间隙84和常规协议队列90中的协议间隙之间的资源占用时间的竞争关系计算延迟时间1tc2。通常，通过公式LC*1tci计算从发布即时协议jtpi产生的常规协议发布延迟成本。
即时协议发布成本jtpcost的第二成本因素是预取数据的高速缓存保留成本CacheRC。这是由于当发布即时协议时，预取的数据停留在高速缓冲存储器14中而产生的每单位时间的成本。当在当前时间st发布即时协议jtpi时，值cti＝(scti-st)，这是从要由即时协议jtpi预取的数据的使用时间scti减去当前时间st产生的，并且等于预取的数据在高速缓冲存储器14中保留的时间。因此，通过(scti-st)*CacheRC：每单位时间保留成本CacheRC乘以保留时间cti＝(scti-st)来计算由于在当前时间st发布即时协议jtpi产生的高速缓存成本。
第三成本因素是由于即时协议jtpi延迟导致在指定的使用时间内没有预取正在访问的数据的风险。使用即时协议jtpi和当前时间st作为函数的参数，通过Time_Limit_Func(jtpi，st)计算该成本。例如，该风险定义为如下的公式：
Time_Limit_Func(jtpi，st)＝(当scti-st＜max(ptfrom，ptto)+a时为Time_Limit，否则为0)。
当预取的数据高速缓存保留时间(scti-st)小于由于预取导致的数据传送资源rfrom的占用时间ptfrom或数据接收资源rto的占用时间ptto的最大值max(ptfrom，ptto)，使用时间scti不能完成数据预取。所以，高速缓存保留时间与通过相加常量a计算的值相比较，给出该常量来达到max(ptfrom，ptto)。当高速缓存保留时间(scti-st)小时，风险值将会是正常数Time_Limit，并且高速缓存保留时间(scti-st)大时，风险值将会是0。
根据以上三个成本因素计算当前时间st的即时协议jtpi发布成本jtpcosti：
jtpcosti＝jtp_cost-func(st，jtpi)
＝LC*1tci+(scti-st)*CacheRC-Time_Limit_Func(jtpi，st)
当情形处于不能完成预取时，第三项Time_Limit_Func(jtpi，st)为正数，并且从第一项LC*1tci和第二项(scti-st)*CacheRC减去它，所以总体上导致jtpcosti的值降低。因此，在好像很难保留即时协议的情形中，冲击在执行即时协议造成的成本和不执行即时协议所造成的风险之间的平衡。
返回到图9，当在当前时间st即时协议发布成本jtpcost小于常规协议发布成本Np时(S44的“是”)，协议发布单元54发布即时协议(S46)，如果即时协议发布成本jtpcost不小于常规协议发布成本(S44的“否”)，协则议发布单元54发布常规协议(S48)。一旦发布了两种协议之一，处理就返回到步骤S40。然后，在那个时间点进行新的成本计算，并且根据每个时间点的成本估算来选择并发布合适的协议。
在图10的例子中，将调度列表70中注册的第一即时协议jtp1发布成本jtpcost1、第二即时协议jtp2发布成本jtpcost2和常规协议队列90的输出间隙中的常规协议np1的发布成本NP相比较，并且由程序发布单元54发布最小的成本协议。这里，必须注意的是，因为在常规协议队列90中的协议的等待状态每次改变，每次需要重新计算即时协议发布成本，因此发布成本的计算公式的第一项的值LC*1tci改变。此外，存在与第一即时协议jtp1发布成本jtpcost1、第二即时协议jtp2发布成本jtpcost2相关的值由于以上相同原因而每次改变的可能性。所以，不保证具有与当前时间st接近的使用时间sct的即时协议将具有更小的发布成本。
此外，可以通过仅部分使用三个成本因素来估算即时协议发布成本jtpcosti。例如，通过仅使用高速缓存保留成本通过下面的公式可以得出估算：
jtpcosti＝(scti-st)*CacheRC
此外，下面的公式也可以用于估算，它还包括不能完成预取的风险因素：
jtpcosti＝(scti-st)*CacheRC-Time_Limit_Func(jtpi，st)
当使用上面的公式时，可以相对于常规协议队列90的协议间隙的条件独立地估算即时协议发布成本，这简化了成本计算。
如上所述，根据实施例，通过指定要在预取命令中预取的数据的使用时间，可以预测预取数据停留在高速缓存的时期，通过估算高速缓存保留成本这使得可以做出关于预取命令的发布定时的决定。此外，通过考虑资源占用时间之间的竞争关系做出成本估算，可以在冲击与其他访问命令的平衡时发布预取命令。结果，不会不必要地而是按计划执行预取命令，并且改善高速缓存可用性。
虽然通过示例性实施例的方式描述了本发明，但本领域内的普通技术人员将理解的是，可在不背离由所附权利要求书限定的本发明宗旨和范围的前提下对本发明进行各种形式和细节上的修改。在下面声明了某些这样的变型。
在上面的描述中，在扩展的预取命令中，根据从扩展的命令的插入位置开始计数的相对步数来指定预取的数据的使用开始点和结束点。然而，可以根据绝对时间指定预取的数据的使用开始点和结束点。
此外，在上面的描述中，计算并比较即时协议和常规协议的发布成本来决定将要发布哪个访问协议。然而，简单计算即时协议发布成本并且如果其值等于或低于预定值，则做出发布即时协议的决定也是可以接受的。