可选择性撤回预取的微处理器装置

1.一种微处理器，包括：
高速缓存；
预取缓冲器，该预取缓冲器耦接至该高速缓存，用以从一系统内存接收 一预取快取线；以及
控制逻辑器耦接至该预取缓冲器，该控制逻辑器是根据同时的存取该预 取快取线与预取该预取快取线至该预取缓冲器，以选择性的将该预取快取线 撤回到该高速缓存。
2.如权利要求1所述的微处理器，其中控制逻辑器选择性地将该预取快 取线撤回到该高速缓存，以响应一随后预取另一预取快取线至该预取缓冲器 的要求。
3.如权利要求1所述的微处理器，该微处理器还包括：
第一计数器，该计数器耦接至该控制逻辑器，以计算在该预取缓冲器内 的该预取快取线被存取的次数。
4.如权利要求3所述的微处理器，其中该控制逻辑器是根据被储存在该 计数器的表示对该预取快取线的存取次数的数值，以选择性的将该预取快取 线撤回到该高速缓存。
5.如权利要求4所述的微处理器，其中该高速缓存包括一N路径集合联 合方式高速缓存。
6.如权利要求5所述的微处理器，该微处理器还包括：
地址，该地址被输入至该N路径集合联合方式高速缓存，以用来在该高 速缓存内选取一N路径集合。
7.如权利要求6所述的微处理器，该微处理器还包括：
N个第二计数器，所述N个第二计数器耦接至该控制逻辑器，并且所述N 个第二计数器中的每一计数器，在该预取快取线被预取之后，分别的计算其 对应的该被选取集合的路径被存取的次数。
8.如权利要求7所述的微处理器，其中该控制逻辑器是根据与储存在所 述N个第二计数器的这些数值相对应的该第一存储器的数值，以选择性地将 该预取快取线撤回到该高速缓存。
9.如权利要求8所述的微处理器，该微处理器还包括：
选取逻辑器，该选取逻辑器耦接至该N个第二计数器，用以选取在该N 个第二计数器中存取次数的一最小数值。
10.如权利要求5所述的微处理器，其中该控制逻辑器将该预取快取线 撤回到该高速缓存，以作为使该被选取集合中N路径的一路径处于无效状态 的响应。
11.如权利要求10所述的微处理器，其中该控制逻辑器将该预取快取线 撤回到该高速缓存中该被选取集合中N路径的处于无效状态的路径。
12.如权利要求1所述的微处理器，该微处理器还包括：
缓存器，该缓存器耦接至该控制逻辑器，以储存该预取快取线的一地址。
13.如权利要求1所述的微处理器，其中该预取快取线是预取自该系统 内存，以作为快取未中该高速缓存的一地址的响应。
14.如权利要求1所述的微处理器，其中该预取快取线被同时存取的频 率至少相同于在高速缓存内的至少一个储备替代快取线的同时存取的频率 时，该控制逻辑器即将该预取快取线撤回到该高速缓存。
15.如权利要求1所述的微处理器，其中该预取快取线的被存取是先于 一新的预取要求预取另一快取线至该预取缓冲器，该控制逻辑器即将该预取 快取线撤回到该高速缓存。
16.一种在一微处理器内的装置，该装置是根据对一预取快取线的存取， 以选择性的将多个预取快取线撤回至该微处理器的一高速缓存，该装置包括：
一预取缓冲器，该预取缓冲器是用以储存一预取快取线；
一缓存器，该缓存器耦接至该预取缓冲器，以储存该预取快取线的一预 取地址；
控制逻辑器，该控制逻辑器耦接至该缓存器，以接收内存存取运算的一 存取地址，并且将该存取地址与该预取地址作一比较；
一计数器，该计数器耦接至该控制逻辑器，以储存存取该预取快取线的 一计数，其中该存取地址与该预取地址相同时，则该控制逻辑器即将该计数 器的计数增加。
其中，该控制逻辑器还根据该计数以选择性的将该预取快取线撤回至该 高速缓存。
17.如权利要求16所述的装置，其中内存存取运算包括加载运算，储存 运算，或窥视运算，以及包括加载运算、储存运算、和窥视运算中的至少两 种运算的组合。
18.如权利要求16所述的装置，该装置还包括：
一第二计数器，该第二计数器耦接至该控制逻辑器，以储存对在该高速 缓存内将会被该预取快取线所取代的一储备快取线的一第二计数。
19.如权利要求18所述的装置，其中该计数大于该第二计数时，该控制 逻辑器即将该预取快取线撤回到该高速缓存。
20.如权利要求19所述的装置，其中该计数不大于该第二计数时，该控 制逻辑器即用一新的预取快取线将在该预取缓冲器的该预取快取线覆盖重 写。
21.如权利要求20所述的装置，其中该储备快取线包括在该高速缓存内 被该预取地址所选取的一集合中多个快取线之一。
22.一种在一微处理器内的装置，该装置是可以选择性的将一预取快取 线撤回至该微处理器的一高速缓存，该装置包括：
一预取缓冲器，其是用以储存该预取快取线；
一计数器，该计数器耦接至该预取缓冲器，用以储存一存取在高速缓存 内的一储备快取线的计数；以及
控制逻辑器，该控制逻辑器耦接至该计数器，并且该控制逻辑器是根据 在该计数器内的该计数，以选择性的将该预取快取线撤回至该高速缓存。
23.如权利要求22所述的装置，该装置还包括：
一定限缓存器，该定限缓存器耦接至该控制逻辑器，以储存一定限数值。
24.如权利要求22所述的装置，该装置还包括：
一缓存器，该缓存器耦接至该控制逻辑器，以储存一数值，该数值具体 指定在该高速缓存内的一储备路径，并且该储备路径是储存该替代储备快取 线。

技术领域\n本发明涉及高速缓存(cache)的领域，尤指快取线(cache line)的预取运 算(prefetching)，即涉及可选择性撤回预取的微处理器装置。\n背景技术\n今天的计算机系统中均包括有一微处理器及一系统内存，该系统内存是 用以储存微处理器指令与为该微处理器指令所处理的数据。一般来说，从系 统内存读取数据所需的时间会远比微处理器执行一或多个指令所需的时间要 多-在某些情况下，甚至于是十倍或二十倍以上，因此，当从系统内存加载 数据时，微处理器常是处于闲置状态，此种情形是非常没有效率的，而且会 降低系统的性能。\n为缓和上述问题对系统的影响，通常会在微处理器内构建一高速缓存， 此高速缓存是内建在微处理器内，并且其记忆容量小于系统内存，用以储存 系统内存所存数据的一子集合。当处理器在执行一指令而须取用数据时，该 处理器首先会从一先前的数据加载中检查该所需数据是否存在于该高速缓存 中，此步骤一般称之为“快取命中”(cache hit)。如果在该先前的数据加载 中，所需数据“命中”  该高速缓存，换言之，即所需数据已被存入该高速缓 存，此时该指令可立即被执行，但若是在该先前的数据加载中，所需数据“快 取未中”(miss)该高速缓存，则再延缓该指令的执行，以等待从系统内存取 得所需数据到处理器内。\n微处理器的设计人员知道软件程序对数据与指令的存取常是连续性的， 因此，如果一数据加载未命中该高速缓存时，则紧接着该数据加载未命中地 址(load miss address)的内存地址上的数据很可能很快地会被该程序所需 求，所以一微处理器预期到未来对下一数据的需求，因此甚至在程序尚未要 求下一数据之前，常会预先将紧接着该未命中地址数据的随后的数据块加载 到其高速缓存中，此动作一般称之为预取(prefetch)。\n此被预取的数据块的大小通常是等同于一快取线的大小，高速缓存是将 数据储存快取线中，一般快取线的大小常是32字节或是64字节。快取线为 可在该高速缓存与该系统内存之间传输的数据的最小单位，换言之，当一微 处理器所欲读取的可被快取数据不存在于其高速缓存时，此微处理器即会从 系统内存读取包含该可被快取数据的整个快取线，并且将该快取线储存于其 高速缓存中，相似地，当需要将一新的快取线写入到其高速缓存时，即会导 致一被修改过的快取线的被取代，此时微处理器也将整个该被取代的快取线 写入到系统内存。\n传统上，该预取快取线均被视为等同于一普通快取线填充(line fill)。一 普通快取线填充为从系统内存提取的一快取线，因为一指令是从该快取线存 取数据，所以利用一普通快取线填充，该被提取的快取线可以无条件的被写 入或撤回到其高速缓存。无条件的撤回一先期预取快取线到其高速缓存会有 一缺点，此缺点为该被撤回的快取线可能会取代一正被使用或是即将被使用 的快取线，因而可能对高速缓存的效率有不利的影响。因此，欲改善高速缓 存的效率，必须要解决此缺点。\n发明内容\n在本发明的一第一具体实施例中，本发明可区别一预取快取线与一普通 快取线填充，并且基于对该预取快取线的同时存取(contemporaneous access)， 本发明可选择性的将该预取快取线撤回至其高速缓存。在本发明的一第二具 体实施例中，基于对该高速缓存内的一快取线的同时存取，并且该快取线为 将被该预取快取线所取代，该预取快取线是可选择性的撤回。因此，为达上 述目的，本发明提供一微处理器，该微处理器包括一高速缓存与一耦接至该 高速缓存的预取缓冲器，该预取缓冲器是用以接收来自一系统内存的一预取 快取线。该微处理器还包括耦接至该预取缓冲器的控制逻辑器，该控制逻辑 器是根据实质上同时的存取该预取快取线与预取该预取快取线至该预取缓 冲器，以将该预取快取线撤回到其高速缓存。\n另一方面，本发明提供一种在一微处理器内的装置，该装置是根据对一 预取快取线的存取，以选择性的将多个预取快取线撤回至该微处理器的一高 速缓存。该装置包括一预取缓冲器，该预取缓冲器是用以储存一预取快取线。 该装置还包括一耦接至该预取缓冲器的一缓存器，该缓存器是用以储存该预 取快取线的一预取地址。该装置也包括耦接至该缓存器的控制逻辑器，该控 制逻辑器接收一内存存取运算的存取地址，并且将该存取地址与该预取地址 作一比较。该装置也包括耦接至该控制逻辑器的一计数器，该计数器是用以 储存一存取该预取快取线的计数。如果该存取地址与该预取地址相同，则该 控制逻辑器将该计数器的计数增加。该控制逻辑器并且根据该计数以选择性 的将该预取快取线撤回至该高速缓存。\n又另一方面，本发明提供一种在一微处理器内的装置，该装置可以选择 性的将一预取快取线撤回至该微处理器的一高速缓存。该装置包括用以储存 该预取快取线的一预取缓冲器，与耦接至该预取缓冲器的一计数器，该计数 器用以储存一存取在高速缓存内的一储备快取线的计数。该装置也包括耦接 至该计数器的一控制逻辑器，该控制逻辑器根据该计数以选择性的将该预取 快取线撤回至该高速缓存。\n又另一方面，本发明提供一种方法，该方法是在一微处理器内，选择性 的从一预取缓冲器将一预取快取线撤回至一高速缓存。该方法的步骤包括保 存一存取该预取快取线的第一计数，与接收一要求以预取一新的快取线至该 预取缓冲器。该方法的步骤也包括判断在接收到该要求之前的存取在高速缓 存内的一储备快取线的一第二计数是否小于该第一计数，以做为接收该要求 的响应，并且如果该第二计数小于该第一计数，则将该新的快取线重写 (overwrite)到该预取缓冲器的该预取快取线上。\n又另一方面，本发明提供一种方法，该方法在一微处理器内，选择性的 从一预取缓冲器将一预取快取线撤回至一高速缓存。该方法的步骤包括预取 该预取快取线至该预取缓冲器，以做为该高速缓存的一快取未中与接收一要 求预取一新的快取线至该预取缓冲器的响应。该方法的步骤也包括判断在该 高速缓存内的一储备快取线是否为无效，如果该储备快取线为无效，则以该 预取快取线取代在该高速缓存内的该储备快取线。\n又另一方面，本发明提供一包含在一传输组件的一计算机数据信号，该 计算机数据信号包括计算机可辨识程序代码以供一微处理器所用。该程序代 码包括第一程序代码以供一高速缓存所用。该程序代码也包括第二程序代码 以供一预取缓冲器所用，该预取缓冲器耦接至该高速缓存，以从一系统内存 接收一预取快取线。该程序代码也包括第三程序代码以供一耦接至该预取缓 冲器的控制逻辑器所用，该控制逻辑器根据实质上同时的存取该预取快取线 与预取该预取快取线至该预取缓冲器，以将该预取快取线撤回到其高速缓 存。\n本发明的优点在于只要增加一些额外的硬件，本发明即可减低预取快取 线取代了还可能即将会被存取的快取线的不利可能性，从而增进高速缓存的 效率。\n本发明的其它目的及优点由随后的详细说明及随附的图表可更加清楚。\n附图说明\n图1为本发明的一方块图，其描述在一微处理器内的一装置，该装置是 用以选择性的撤回多数的预取快取线。\n图2为本发明的一流程图，其说明在图1所示的微处理器内，选择性的 从该预取缓冲器撤回一预取快取线至其高速缓存的作业。\n图3为本发明另一具体实施例的一方块图，其描述在一微处理器内的一 装置，该装置是用以选择性的撤回多数的预取快取线。\n图4为本发明的一流程图，其说明在图3所示的微处理器内，选择性的 从该预取缓冲器撤回一预取快取线至其高速缓存的作业。\n其中，附图标记说明如下：\n100微处理器                102控制逻辑器\n104高速缓存                106预取线缓冲器\n108预取地址缓存器(PAR)\n112A储备路径0存取计数缓存器(CWAC0)\n112B储备路径1存取计数缓存器(CWAC1)\n112C储备路径2存取计数缓存器(CWAC2)\n112D储备路径3存取计数缓存器(CWAC3)\n114最小选取逻辑器           116存取计数(PBAC)缓存器\n118比较器                   122min_AC\n124比较结果                 126min_way信号\n128预取缓冲存取计数(PBAC)   132加载/储存地址\n134状态信息       136预取快取线\n138预取地址       300微处理器\n302控制逻辑器     314储备快取线存取计数\n316存取定限缓存器 318储备路径缓存器\n具体实施方式\n请参阅图1，其是一方块图，其描述在一微处理器100内的一装置，该 装置是用以选择性的撤回多数的预取快取线。该微处理器100包括一彼此耦 接以构成一管线(pipeline)的多个阶段。一或多个该管线阶段包括一地址产生 器，该地址产生器用以产生一内存存取运算地址，如图1所示的加载/储存地 址132。该加载/储存地址132具体指定一加载或储存运算的地址。一加载运 算从内存读取数据至微处理器100，而储存运算将数据从微处理器100写入 到内存。在一具体实施例中，该加载/储存地址132为一物理内存地址。\n微处理器100也包括一高速缓存104，该高速缓存包括一N路径集合联 合方式的高速缓存。在一具体实施例中，该高速缓存104包括一4路径集合 联合方式(4-way set associative)的64KB高速缓存。在一具体实施例中，该高 速缓存104为一第一层数据高速缓存(level-1 data cache)；但是本发明并不局 限于应用在一数据高速缓存，而是可应用于一指令高速缓存，或是一联合数 据/指令高速缓存，并且本发明也不局限于只使用第一层数据高速缓存，而是 可使用在快取层级体系中任一层级的高速缓存。\n高速缓存104储存地址卷标及储存于其内的每一快取线的状态。该卷标 包括储存于高速缓存104内多个快取线的内存地址的上层部份。在一具体实 施例中，该状态包括MESI(修改，排他，共享，无效)(modified，exclusive， shared，invalid)协议信息。高速缓存104接收加载/储存地址132。该加载/ 储存地址132的一下层部份是用以在高速缓存104中做为选取一集合(set)， 或行(row)，或路径(ways)的索引。高速缓存104将该加载/储存地址132的上 层部份与该被选取集合中每一路径的地址卷标作一比较，以判断该加载/储存 地址132是否“命中”该高速缓存，换言之，即该加载/储存地址132是否与 任一存在于该高速缓存104内的卷标相符，并且为有效状态。高速缓存104 将状态信息134输出，该状态信息134包括被选取集合中每一路径的MESI 状态，以及表明该被选取集合中的任一卷标是否与加载/储存地址132相符的 一指示。如果加载/储存地址132源自一加载运算，并且“命中”高速缓存104， 则该命中的快取线数据将被提供给要求该快取线数据的该微处理器100的管 线阶段。\n微处理器100也包括耦接至高速缓存104的控制逻辑器102。该控制逻 辑器102接收源自高速缓存104的状态信息134及加载/储存地址132。控制 逻辑器102响应的产生多个控制信号以控制高速缓存104的运作。该控制逻 辑器的运作将会在下文中详述。\n微处理器100也包括耦接至高速缓存104的一预取线缓冲器106。预取 线缓冲器106是从一总线接口单元接收一预取快取线136，而该总线接口单 元是经由一处理器总线，以从一系统内存提取数据到该微处理器100。如下 所述，若加载/储存地址132快取未中该高速缓存104，则该控制逻辑器102 将会促使一快取线紧跟着该加载/储存地址132所指向的快取线，换言之，预 取快取线136被从系统内存预取至该预取线缓冲器106。因此，如下所述， 该控制逻辑器102即可有利的根据对该预取快取线136的同时存取，以选择 性的将该预取快取线136撤回至该高速缓存104。\n预取线缓冲器106将该预取快取线136提供给该高速缓存104，此外， 该预取线缓冲器106并且将预取快取线136提供给从该预取快取线136要求 数据的该微处理器100之一或多个管线阶段。就这一点而言，该预取线缓冲 器106可以视为是该高速缓存104的一延伸。即是，如果该控制逻辑器102 判定一加载运算具体指定的一加载/储存地址132快取未中该高速缓存104， 但是却命中该预取线缓冲器106，则该控制逻辑器102可将该预取快取线136 的数据提供给该微处理器100的管线阶段。\n微处理器100也包括耦接至控制逻辑器102的一预取地址缓存器 (prefetch address register，PAR)108。该预取地址缓存器108是储存在该预取 线缓冲器106内的预取快取线136的地址，此地址称之为预取地址138。当 控制逻辑器102促使该预取快取线136被预取至该预取线缓冲器106内，该 控制逻辑器102即将预取地址缓存器108更新为该预取快取线地址138。此 外，该控制逻辑器102将该预取地址缓存器108与该加载/储存地址132作一 比较，以侦测随后的对该预取快取线136的存取。\n微处理器100也包括耦接至控制逻辑器102的一预取缓冲存取计数 (prefetch buffer access count，PBAC)缓存器116。预取缓冲存取计数缓存器116 是储存对在该预取线缓冲器106内的该预取快取线136的存取次数，此存取 次数称之为预取缓冲存取计数(PBAC)128。当该控制逻辑器102侦测到对该 预取快取线136的一存取，则该控制逻辑器102即增加该PBAC缓存器116。 在一具体实施例中，一存取包括对该预取快取线136的一读取，但是，在其 它的具体实施例中，一对该预取快取线136的存取也包括写入及/或窥视 (snoop)运算。当一新的预取快取线136被预取到该预取线缓冲器106时，该 控制逻辑器102即清除该PBAC缓存器116。\n微处理器100也包括耦接至控制逻辑器102的多个储备路径存取计数 (candidate way access count，CWAC)缓存器112。N个第二计数器可耦接至该 控制逻辑器，在图1的具体实施例包括四个储备路径存取计数缓存器，分别 注记为CWAC0 112A，CWAC1 112B，CWAC2 112C，及CWAC3 112D，还 分别对应于4路径集合联合方式高速缓存104的每一路径。每一CWAC缓 存器112储存该储备集合中各自所对应的路径的存取次数。该储备集合为在 该高速缓存104中，由该预取地址138所选取的路径的集合。当该控制逻辑 器102侦测到对该高速缓存104中的该选取集合的一路径的存取时，则该控 制逻辑器102即增加相对应的一该CWAC缓存器112。当一新的预取快取线 136被预取到该预取线缓冲器106时，该控制逻辑器102即清除该CWAC缓 存器112。\n微处理器100也包括耦接至CWAC缓存器112的最小选取逻辑器 (minimum selection logic)114。该最小选取逻辑器114接收来自各CWAC缓 存器112的CWAC，并且输出其所接收的CWAC的最小值，该最小值可记 为min_AC 122。此外，该最小选取逻辑器114并且输出min_way信号126 至该控制逻辑器102，该min_way信号126具体指定该拥有从该CWAC缓 存器112接收到的最小值的路径编号。\n微处理器100也包括一比较器118，该比较器118是与该最小选取逻辑 器114与该PBAC缓存器116相耦接。该比较器118将该min_AC 122与该 PBAC 128作一比较，如果该PBAC 128大于该min_AC 122，则产生一逻辑 器真值(true value)以作为比较结果124输出，否则输出一逻辑器假值(false value)。在另一具体实施例中，该比较器118将该min_AC 122与该PBAC 128 作一比较，如果该PBAC 128大于或等于该min_AC 122，则产生一逻辑器真 值(true value)以作为比较结果124输出，否则输出一逻辑器假值(false value)。 该比较结果124然后被提供给该控制逻辑器102。\n请参阅图2，其为本发明的一流程图，说明在图1所示的微处理器100 内，选择性的从该预取缓冲器106撤回一预取快取线至其高速缓存104的作 业。流程开始于判断方块202。\n在判断方块202中，该控制逻辑器102将对图1的状态信号134进行检 查，用以判断该加载/储存地址132是否快取未中该高速缓存104。若答案为 是，则流程进行到方块204；若答案为否，则流程回到判断方块202。\n在方块204中，在开始从内存提取该快取未中快取线至该高速缓存104 之后，该控制逻辑器102指令其总线接口组件进行预取其下一个快取线至图 1的预取线缓冲器106，该下一个快取线为紧接着该快取未中加载/储存地址 132指向的预取快取线。在下一个快取线被预取至该预取线缓冲器106之前， 该控制逻辑器102核查该下一个快取线也为快取未中该高速缓存104。当该 预取快取线136已被预取至该预取线缓冲器106后，该控制逻辑器102即将 该预取地址缓存器108更新为图1的预取地址138，换言之，即将之更新为 该下一个快取线的地址。流程接着进行到判断方块206。\n在判断方块206中，控制逻辑器102向高速缓存104查询(query)预取地 址138，并且对图1的状态信息134进行一项检查用以判断在其储备集合中 是否有任何路径是处于无效(invalid)状态。若答案为是，则流程进行到方块 208；若答案为否，则流程进行到方块212。\n在方块208中，控制逻辑器102将该预取快取线136撤回到该处于无效 状态的路径，该路径在高速缓存104内的储备集合中。流程接着回到方块202。\n在方块212中，控制逻辑器102清除图1的PBAC缓存器116与CWAC 缓存器112，并将其值设定为0。流程接着进行到判断方块214。\n在判断方块214中，当加载/储存运算对高速缓存104进行存取时，控制 逻辑器102将进行一项检查用以判断是否有任一运算使得在其储备集合中的 任一路径变成无效状态。例如在储备集合中的一路径可以经一无效窥视存取 (invalidating snoop access)而变成无效状态。若有其储备集合中的任一路径被 变成无效状态，则流程从判断方块214回到方块208；若答案为否，则流程 进行到判断方块216。\n在判断方块216中，该控制逻辑器102将进行一项检查用以判断是否有 新的预取要求，换言之，该控制逻辑器102将进行一项检查用以判断一新的 加载/储存地址132是否快取未中该高速缓存104，因而导致需要该预取线缓 冲器106预取一新的快取线。若答案为是，则流程进行到判断方块218；若 答案为否，则流程进行到判断方块224。\n在判断方块218中，该控制逻辑器102将对图1的比较结果信号124进 行一项检查用以判断PBAC 128是否大于min_AC 122。若答案为是，则流程 进行到方块222；若答案为否，则流程回到方块204，以致储存于预取线缓 冲器106的该预取快取线136不会被撤回到该高速缓存104，而是被丢弃， 换言之，该预取快取线136被随后的新的预取快取线所覆盖重写。\n在方块222中，该控制逻辑器102将该预取快取线136撤回到由min_way 信号126所具体指定的路径，该路径在高速缓存104内的储备集合中。流程 接着从方块222回到方块204。\n在判断方块224中，该控制逻辑器102将状态信息134进行一项检查用 以判断在储备集合中的一路径是否已被存取。在一具体实施例中，一路径之 所以被存取，是因为该加载/储存地址132快取命中该高速缓存104，换言之， 是因为该路径为有效状态，并且该路径的卷标与该加载/储存地址132的卷标 部份相符。若该储备集合已被存取，则流程进行到判断方块226；若答案为 否，则流程进行到判断方块228。\n在判断方块226中，该控制逻辑器102响应于判断方块224所决定的存 取路径，以增加CWAC缓存器112。例如，若路径2被存取，则该控制逻辑 器102增加CWAC 112C。流程接着从方块226进行到判断方块228。\n在判断方块228中，该控制逻辑器102将比较该预取地址138与该加载 /储存地址132，以进行一项检查用以判断该预取快取线136是否已被存取。 若答案为是，则流程进行到方块232；若答案为否，则流程回到判断方块214。\n在方块232中，该控制逻辑器102增加PBAC缓存器116。流程接着从 方块232回到判断方块214。\n下列表格1所示的伪代码(pseudocode)也用以描述图2的微处理器100 的运算。\nIf(anyWayInCandidateSetInvalid){\nRetirePrefetchedLineToCache()；\n}else{    \nPBAC＝CWAC[0]＝CWAC[1]＝CWAC[2]＝＝CWAC[3]＝0；\nwhile(noNewPrefetchRequested&&noWayInCandidateSetInvalided){\nif(candidateSetAccessed)\nCWAC[accessedWay]++；\nif(PrefetchedLineAccessed)\nPBAC++；\n}\nif(newPrefetchRequested){\nif(PBAC＞min_AC)\nRetirePrefetchLineToCache()；\nelse/*throw away prefetched cache line*/\nOverwritePrefetchBufferWithNewPrefetchData()；\n}else{/*way in candidate set was invalidated*/\nRetirePrefetchedLineToCache()；\n}\n}\n表格1.\n如图1及图2所示，本发明的优点在于根据对应于该储存集合的路径的 被存取次数的该预取快取线136的被存取次数，可以选择性的将该预取快取 线136撤回至其高速缓存104，而不是不加选择的将该预取快取线136撤回 至其高速缓存104。\n请参阅图3，其为本发明另一具体实施例的一方块图，其描述在一微处 理器300内的一装置，该装置是用以选择性的撤回多数的预取快取线。\n如图1相同标号的组件，该微处理器300包括一高速缓存104，预取线 缓冲器106，预取地址缓存器(PAR)108，加载/储存地址132，状态信息134， 预取快取线136，以及预取地址138。\n微处理器300也包括耦接至该高速缓存104的控制逻辑器302，如同图 1的控制逻辑器102，与预取线缓冲器106；但是图3的控制逻辑器302是根 据多个数值以选择性的将该预取快取线136撤回至该高速缓存104，该多个 数值是储存在一储备快取线存取计数(candidate line access counter，CLAC)缓 存器314，一存取定限缓存器(access threshold register，ATR)316，及一储备路 径缓存器(candidate way register，CWR)318。上述的CLAC缓存器314，ATR 316及CWR 318均耦接至该控制逻辑器302。\nCWR 318储存一数值，该数值具体指定一储备路径，并且该路径为在该 储备集合中，将被预取快取线136所选择性取代的路径。在一具体实施例中， 该控制逻辑器302开始就将一在该储备集合中的最近使用过的路径进驻 CWR 318，该路径由状态信息134所决定。若前述的储备路径在一新的预取 被要求之前，即已被取代，则该控制逻辑器302将CWR 318更新为其一新 的最近使用过的路径。\nCLAC 314储存一数值，该数值为计算从预取快取线136被预取至预取 线缓冲器106之后，该被CWR 318所具体指定的储备快取线或是储备路径 被存取的次数。\nATR 316储存一定限数值，该定限数值被控制逻辑器302用以与储存在 CLAC 314的数值做比较，以选择性的撤回该预取快取线136，详述如下。 在一具体实施例中，储存在ATR 316的该数值为预定值。在一具体实施例中， 储存在ATR 316的该数值是可程控的。\n请参阅图4，其为本发明的一流程图，其说明在图3所示的微处理器300 内，选择性的从该预取缓冲器106撤回一预取快取线至其高速缓存104的作 业。流程开始于判断方块402。\n在判断方块402中，该控制逻辑器302将对图3的状态信号134进行检 查，用以判断该加载/储存地址132是否快取未中该高速缓存104。若答案为 是，则流程进行到方块404；若答案为否，则流程回到判断方块402。\n在方块404中，在开始从内存提取该快取未中快取线至该高速缓存104 之后，该控制逻辑器302即将具体指定该储备快取线的最近使用过路径 (LRU)的一数值进驻至CWR 318。并且，该控制逻辑器302指令其总线接 口组件进行预取其下一个快取线至图三的预取线缓冲器106，该下一个快取 线为紧接着该快取未中加载/储存地址132指向的预取快取线。在下一个快取 线被预取至该预取线缓冲器106之前，该控制逻辑器102查核该下一个快取 线也为快取未中该高速缓存104。此外，该控制逻辑器302即将该快取未中 快取线的下一个快取线的地址进驻至预取地址缓存器108。流程接着进行到 判断方块406。\n在判断方块406中，控制逻辑器302向高速缓存104查询(query)预取地 址138，并且对图3的状态信息134进行一项检查用以判断在其储备集合中 是否有任何路径是处于无效(invalid)状态。若答案为是，则流程进行到方块 408；若答案为否，则流程进行到方块412。\n在方块408中，控制逻辑器302将该预取快取线136撤回到被CWR 318 所具体指定的在高速缓存104的储备路径。流程接着回到判断方块402。\n在方块412中，控制逻辑器102清除图3的CLAC 314，并将其值设定 为0。流程接着进行到判断方块414。\n在判断方块414中，当加载/储存运算对高速缓存104进行存取时，控制 逻辑器302将进行一项检查用以判断是否有任一运算使得在其储备路径变成 无效状态。若答案为是，则流程从判断方块414回到方块408；若答案为否， 则流程进行到判断方块416。\n在判断方块416中，该控制逻辑器302将进行一项检查用以判断是否有 新的预取要求。若答案为是，则流程进行到判断方块418；若答案为否，则 流程进行到判断方块424。\n在判断方块418中，该控制逻辑器302将进行一项检查用以判断CLAC 314是否大于储存于图3的ATR 316内的数值。若答案为是，则流程进行到 方块422；若答案为否，则流程回到方块404，以致储存于预取线缓冲器106 的该预取快取线136不会被撤回到该高速缓存104，而是被丢弃，换言之， 该预取快取线136被随后的新的预取快取线所覆盖重写。\n在方块422中，该控制逻辑器302将该预取快取线136撤回到被CWR 318所具体指定的在高速缓存104的储备路径。流程接着从方块422回到方 块404。\n在判断方块424中，该控制逻辑器302将状态信息134进行一项检查用 以判断该储备路径是否已被存取。在一具体实施例中，该储备路径之所以被 存取，是因为该路径为有效状态，并且该路径的卷标与该加载/储存地址132 的卷标部分相符。若该储备集合已被存取，则流程进行到判断方块426；若 答案为否，则流程进行到判断方块428。\n在判断方块426中，该控制逻辑器302增加CLAC 314。流程接着从方 块426进行到判断方块428。\n在判断方块428中，该控制逻辑器302将进行一项检查用以判断储备路 径是否已被一储存运算所取代。若答案为是，则流程进行到方块432；若答 案为否，则流程回到判断方414。\n在方块432中，该控制逻辑器302将CWR 318更新为在其储备集合中 的一新的最近使用过的路径，并且清除CLAC 314，并将其值设定为0。流 程接着从方块432回到判断方块414。\n下列表格2所示的伪代码(pseudocode)也用以描述图4的微处理器300 的运算。\nIf(Cache[PrefetchIndex][CandidateWay].Valid＝＝0){\nRetirePrefetchedToCache()；\n}else{\n  CandidateLineAccessCount＝0；\n  while(！NewPrefetchRequest&&！CandidateLineInvalidated){\nif(CandidateLineAccessed){\n  CandidateLineAccessCount++；\n}else if(CandidateLineInvalidated){/*e.g.，by external snoop*/\n  RetirePrefetchToCache()；\n}else if(CandidateLineReplaced){/*i.e.，with valid miss data*/\n  UpdateCandidateWayRegister()；\n  CandidateLineAccessCount＝0；\n}\n}\nif((CandidateLineAccessCount＜AccessThreshold)&&\n(！CandidateLineInvalidate))\n   {\n    RetirePrefetchToCache()；\n   }else{\n  OverWritePrefetchBufferWithNewPrefetchData()；\n  /*i.e.，flush old prefetch data*/\n }\n}\n表格2.\n虽然本发明的具体实施例已叙述如前，但本发明并未受限于此。例如， 本发明可适用于一数据高速缓存，一指令高速缓存，或是一指令/数据高速缓 存。除此之外，虽然在一具体实施例中已详述在预取快取线已被预取至其预 取缓冲器中之后，如何追踪(track)该预取快取线的存取与储备快取线的取代， 但其它的同时存取也可被追踪，并且做为选择性的撤回该预取快取线的基 础，例如在该预取的需求被确定为与该预取快取线到达该预取缓冲器的时间 之间，对该预取快取线及/或储备快取线的存取。此外，读取、写入、窥视及 其它存取的组合也可被追踪，并且用之以选择性的撤回该预取快取线。换言 之，有各种各样的试误规则可以被具体实现以判断在高速缓存内的该预取快 取线，或是一储备快取线在未来有较大的被存取可能性，因此本发明比传统 的无条件将该预取快取线撤回至其高速缓存更为有利。最后，虽然本发明是 有关于由快取未中所产生的预取，本发明也可适用于任何型式的预取，例如 由预取程序指令所产生的预取。\n本发明不但可以硬件实现，也可以通过在一计算机可运用(例如，可辨识) 组件具体实现的计算机可辨识码(例如，计算机可辨识程序代码、数据等等) 来实现。该计算机程序码促成此处所揭示的本发明的功能，或制造，或两者 均有的实现。举例来说，本发明可以下列计算机程序码来实现之：一般的程 序语言(例如，C、C++、JAVA等等)；GDSII数据库；硬件描述语言(hardware description languages，HDL)，包括：Verilog HDL、VHDL、Altera HDL(AHDL) 等等；或是其它本技术领域中的编制程序及/或电路(即是，图标的)捕捉工具。 该计算机程序码可适用于任何已知的计算机可运用(例如，可辨识)组件，此 计算机可运用组件包括：半导体内存，磁盘片，光盘片(例如，CD-ROM、 DVD-ROM等等)，以及如同在一计算机可运用(例如，可辨识)传输组件(例如， 载波，或是包括数字、光学，或模拟式组件)具体实现的一计算机数据信号。 就其本身而论，该计算机程序码可以在通信网路上传输，该通信网路包括网 际网络与企业网络。可以理解的是本发明可以计算机程序码来实现(例如，一 知识产权(Intellectual property，IP)核心的一部分，如一微处理器核心，或是如 一系统层级的设计，例如一系统单芯片(System-on-Chip，SoC)，并且将之转 移至硬件以成为集成电路的一部分。本发明也可以一硬件与计算机程序码的 组合来实现。\n本发明的具体实施例已叙述如前，但本发明并未受限于此。上述仅为本 发明的较佳实施例，不能以之限制本发明的范围。凡依本发明权利要求所做 的均等变化及修改，仍属于本发明的保护范围，其并未脱离本发明的构思 和范围，所以都应视为本发明的进一步实施状况。