用以任务调度与分配的处理系统及其加速方法

摘要

本发明公开一种用以任务调度与分配的处理系统处理系统及其加速方法，该处理系统包括至少一处理器内核、多个硬件加速器以及一微控制器。处理器内核用以运行多个进程，并且对应每一上述进程建立至少一任务队列。处理器内核产生多个命令封包并将其压入对应的上述任务队列。多个硬件加速器执行上述命令封包。微控制器配置在上述硬件加速器与处理器内核之间，用以调度上述命令封包至对应的上述硬件加速器执行。当上述硬件加速器的任何一个执行属于上述进程其中的一个的上述命令封包时，微控制器指派硬件加速器优先执行属于进程的上述任务队列的其他上述命令封包。

权利要求

1.一种用以任务调度与分配的处理系统，包括：

至少一处理器内核，用以运行多个进程，并且对应每一所述进程建立至少一任务队列，该处理器内核产生多个命令封包并将其压入对应的所述任务队列；

至少一硬件加速器，用以执行所述命令封包；以及

微控制器，配置在该硬件加速器与该处理器内核之间，用以调度所述命令封包至该硬件加速器执行，其中当该硬件加速器执行属于所述进程其中之一的个的所述命令封包时，该微控制器指派该硬件加速器优先执行属于该进程的所述任务队列的其他所述命令封包。

2.如权利要求1所述的处理系统，其中：

该至少一硬件加速器包括多个硬件加速器，该微控制器为每一所述硬件加速器对应每一所述任务队列分别配置时间片，藉由轮询方式分配所述命令封包之一至所述硬件加速器中对应于该命令封包所属的任务队列的该时间片不为零的硬件加速器执行，其中在该硬件加速器执行该命令封包之后，该微控制器将该硬件加速器对应于该命令封包所属的该任务队列的该时间片减一。

3.如权利要求2所述的处理系统，其中：

当该时间片的该数值递减为零、或是已执行的所述命令封包所属的该任务队列尚无新的命令封包压入，该微控制器查询已执行的所述命令封包所属的该进程，并且指派该硬件加速器执行该进程对应的其它任务队列的该命令封包。

4.如权利要求3所述的处理系统，其中：

该进程的信息存储在每一所述任务队列的每一标头。

5.如权利要求1所述的处理系统，其中：

当该硬件加速器所执行的所述命令封包具有关联性时，该微控制器指派该硬件加速器优先执行具有该关联性的其它所述命令封包。

6.如权利要求5所述的处理系统，其中：

当命令封包与在前的所述命令封包对应相同的上下文信息时，该命令封包具有该关联性，其中该硬件加速器使用该上下文信息执行具有该关联性的所述命令封包。

7.如权利要求6所述的处理系统，其中：

该上下文信息暂存在该硬件加速器的内部随机存取存储器。

8.如权利要求5所述的处理系统，其中：

当所述命令封包不具有该关联性时，该微控制器存取该处理系统之一系统存储器以执行上下文保留操作或上下文再存储操作。

9.如权利要求5所述的处理系统，其中：

所述命令封包还包括相依起始标示与相依结束标示，分别指示该关联性的起始与结束。

10.如权利要求5所述的处理系统，其中：

该至少一硬件加速器包括多个硬件加速器，该微控制器为每一所述硬件加速器对应每一所述任务队列分别配置时间片，藉由轮询方式分配所述命令封包之一至所述硬件加速器中对应于该命令封包所属的任务队列的该时间片不为零的硬件加速器执行，其中在该硬件加速器执行该命令封包之后，该微控制器将该硬件加速器对应于该命令封包所属的该任务队列的该时间片减一，其中当该时间片的该数值递减为零但所述命令封包的该关联性尚未结束时，该微控制器将该时间片的该数值加N，其中N为自然数。

11.一种用以任务调度与分配的方法，适用于至少一处理器内核、至少一硬件加速器、以及微控制器，该处理器内核用以运行多个进程，该访存方法包括：对应每一所述进程建立至少一任务队列；

产生多个命令封包并将其压入对应的所述任务队列；以及藉由该微控制器调度所述命令封包至对应的该硬件加速器执行，其中当该硬件加速器执行属于所述进程其中之一的个的所述命令封包时，指派该硬件加速器优先执行属于该进程的所述任务队列的其他所述命令封包。

12.如权利要求11所述的方法，其中该至少一硬件加速器包括多个硬件加速器，该方法还包括：为每一所述硬件加速器对应每一所述任务队列分别配置时间片；

藉由轮询方式分配所述命令封包之一至所述硬件加速器中对应于该命令封包所属的任务队列的该时间片不为零的硬件加速器执行；以及在该硬件加速器执行该命令封包之后，将该硬件加速器对应于该命令封包所属的该任务队列的该时间片减一。

13.如权利要求12所述的方法，其中：

当该时间片的该数值递减为零、或是已执行的所述命令封包所属的该任务队列尚无新的命令封包压入，查询已执行的所述命令封包所属的该进程，并且指派该硬件加速器执行该进程对应的其它任务队列的该命令封包。

14.如权利要求13所述的方法，其中：

该进程的信息存储在每一所述任务队列的每一标头。

15.如权利要求11所述的方法，其中：

当该硬件加速器所执行的所述命令封包具有关联性时，指派该硬件加速器优先执行具有该关联性的其它所述命令封包。

16.如权利要求15所述的方法，其中：

当命令封包与在前的所述命令封包对应相同的上下文信息时，该命令封包具有该关联性，并且该硬件加速器使用该上下文信息执行具有该关联性的所述命令封包。

17.如权利要求16所述的方法，其中：

该上下文信息暂存在该硬件加速器的内部随机存取存储器。

18.如权利要求15所述的方法，还包括：

当所述命令封包不具有该关联性时，存取该处理系统之一系统存储器以执行上下文保留操作或上下文再存储操作。

19.如权利要求15所述的方法，其中：

所述命令封包还包括相依起始标示与相依结束标示，分别指示该关联性的起始与结束。

20.如权利要求15所述的方法，其中该至少一硬件加速器包括多个硬件加速器，还包括：为每一所述硬件加速器对应每一所述任务队列分别配置时间片；

藉由轮询方式分配所述命令封包之一至所述硬件加速器中对应于该命令封包所属的任务队列的该时间片不为零的硬件加速器执行；

在该硬件加速器执行该命令封包之后，将该硬件加速器对应于该命令封包所属的该任务队列的该时间片减一；以及当该时间片的该数值递减为零但所述命令封包的该关联性尚未结束时，将该时间片的该数值加N，其中N为自然数。

说明书

用以任务调度与分配的处理系统及其加速方法

技术领域

[0001] 本发明涉及一种处理系统与访存方法，特别涉及一种异构处理器的处理系统、加速方法与访存方法。

背景技术

[0002] 硬件加速器，如加速功能单元(accelerator function unit，AFU)，主要用于加速一些特定的计算任务，这些计算任务如果由中央处理器内核的软件进行运算，将使得效率低下。而硬件加速器通过分析计算过程，设计专门的硬件逻辑处理计算的任务，以达到加速效果。硬件加速器与中央处理器之间的接口实现将特定的加速任务指派给硬件加速器执行，已知技术中的硬件加速器通常是以设备(device)的形式直接连接于总线及系统存储器，导致产生两个问题：首先，硬件加速器所能使用的系统存储器的空间是固定的；其次，任务通常是中央处理器在用户模式下(user mode)建立但需要在内核模式下(kernel mode)将其分指派给硬件加速器执行，因此这些任务往往需要从用户空间(user space)拷贝到内核空间(kernel space)，这需要进行较为耗费资源的上下文切换(context switch)操作。

[0003] 此外，在当前多用户多任务并行的操作系统平台下，存在着多个应用程序或执行流皆有硬件加速的需求。如何调度多任务给硬件加速器执行亦为该接口设计的一大难点。

[0004] 为了满足多个应用程序或执行流共用硬件加速器的需求，往往在一颗芯片中放置多个硬件加速器。然而若是多个硬件加速器之间没有协同调度，将使得硬件加速器的任务分配不平均，则多个硬件加速器的能力将无法充分发挥。

[0005] 因此，我们有需要设计一种全新的异构计算处理系统以克服现有技术中硬件加速器与中央处理器在任务指派、调度与分配上存在的上述技术问题。

发明内容

[0006] 为了解决上述问题，本发明提出一种任务调度与分配的处理系统及其加速方法，依据任务队列所属的进程来调度与分配命令封包，并且藉由配置多个任务队列的时间片以及轮询机制的执行，能够平均调度与分配多个任务队列的命令封包，避免发生过度集中分配与执行一部分的任务队列、却忽略与闲置另一部分的任务队列的情况。

[0007] 本发明的一实施例提供了一种处理系统，包括至少一处理器内核、至少一硬件加速器以及一微控制器。处理器内核用以运行多个进程(process)，并且对应每一上述进程建立至少一任务队列。处理器内核产生多个命令封包(command packet)并将其压入对应的上述任务队列。至少一硬件加速器执行上述命令封包。微控制器配置在上述硬件加速器与处理器内核之间，用以调度上述命令封包至硬件加速器执行。当上述硬件加速器执行属于上述进程其中的一个的上述命令封包时，微控制器指派硬件加速器优先执行属于进程的上述任务队列的其他上述命令封包。

[0008] 本发明的另一实施例提供了一种用以任务调度与分配的方法，适用于至少一处理器内核、至少一硬件加速器以及一微控制器。处理器内核用以运行多个进程。上述访存方法包括：对应每一上述进程建立至少一任务队列；产生多个命令封包并将其压入对应的上述任务队列；藉由微控制器调度上述命令封包至对应的上述硬件加速器执行；以及当上述硬件加速器执行属于上述进程其中的一个的上述命令封包时，指派硬件加速器优先执行属于进程的上述任务队列的其他上述命令封包。

[0009] 关于本发明其他附加的特征与优点，本领域技术人员在不脱离本发明的精神和范围内，当可根据本申请实施方法中所公开的处理系统与访存方法而加以实施。

附图说明

[0010] 根据以下的详细说明并配合附图做完整公开。应注意的是，根据本产业的一般操作，图示并未必按照比例绘制。事实上，可能任意的放大或缩小元件的尺寸，以做清楚的说明。

[0011] 图1是显示根据本发明一实施例所述的处理系统的示意图；

[0012] 图2是显示根据本发明另一实施例所述的处理系统的示意图；

[0013] 图3A是显示根据本发明一实施例所述的处理器内核、处理器非内核、与加速器接口前端的示意图；

[0014] 图3B是显示根据本发明一实施例所述的处理器非内核、加速器接口前端、与加速器接口后端的示意图；

[0015] 图4是显示根据本发明一实施例所述的位映射表与微控制器表格的示意图；

[0016] 图5是显示根据本发明一实施例所述的硬件加速器、微控制器与访存单元的示意图；

[0017] 图6是显示根据本发明一实施例所述的调度器与内存重排序缓冲区的示意图；

[0018] 图7A是显示根据本发明一实施例所述的将命令封包压入任务队列的示意图；

[0019] 图7B是显示根据本发明一实施例所述的硬件加速器依序执行命令封包的示意图；

[0020] 图8A是显示根据本发明一实施例所述的执行不同任务队列的命令封包的示意图；

[0021] 图8B是显示根据本发明另一实施例所述的执行不同任务队列的命令封包的示意图；

[0022] 图9是显示根据本发明另一实施例所述的执行不同任务队列的命令封包的示意图；

[0023] 图10是显示根据本发明另一实施例所述的执行不同任务队列的命令封包的示意图；

[0024] 图11A是显示根据本发明一实施例所述的再排序缓冲区及其相关的发布指标、返送指标与完成标志的示意图；

[0025] 图11B是显示根据本发明一实施例所述的再排序缓冲区及其相关的发布指标、返送指标与完成标志的示意图；

[0026] 图11C是显示根据本发明一实施例所述的再排序缓冲区及其相关的发布指标、返送指标与完成标志的示意图；

[0027] 图11D是显示根据本发明一实施例所述的再排序缓冲区及其相关的发布指标、返送指标与完成标志的示意图；

[0028] 图12A与12B是显示根据本发明一实施例所述的异构处理器加速方法；

[0029] 图13是显示根据本发明另一实施例所述的异构处理器加速方法；

[0030] 图14是显示根据本发明一实施例所述的用以分配任务的处理系统的访存方法；

[0031] 图15是显示根据本发明一实施例所述的使用轮询机制的访存方法；

[0032] 图16是显示根据本发明另一实施例所述的使用轮询机制的访存方法；

[0033] 图17是显示根据本发明一实施例所述的用于调度的处理系统的访存方法；

[0034] 图18是显示根据本发明一实施例所述的用以任务调度与分配的处理器加速方法；

[0035] 图19是显示根据本发明另一实施例所述的用以任务调度与分配的处理器加速方法；

[0036] 图20A与20B是显示根据本发明另一实施例所述的用以任务调度与分配的处理器加速方法；

[0037] 图21是显示根据本发明一实施例所述的用以任务调度的处理器加速方法；

[0038] 图22是显示根据本发明另一实施例所述的用以任务调度的处理器加速方法。

[0039] 【符号说明】

[0040] 10～处理系统

[0041] 110、110A、110B….110N～硬件加速器

[0042] 116～内部随机存取存储器

[0043] 120、120A、120B….120N～处理器内核

[0044] 130～加速器接口

[0045] 130_BE～加速器接口后端

[0046] 130_FE～加速器接口前端

[0047] 131～命令寄存器

[0048] 132～解码器

[0049] 134～权限列表

[0050] 136～寄存器

[0051] 137～位映射表

[0052] 140～控制器

[0053] 142～静态随机存取存储器

[0054] 147～活跃列表

[0055] 150～访存单元

[0056] 160～系统存储器

[0057] 180～处理器非内核

[0058] 181～非内核仲裁器

[0059] 182～非内核量程器

[0060] 209A、209B…209E～寻访引擎

[0061] 210A、210B…210E～调度器

[0062] 250～内存重排序缓冲区

[0063] 281～仲裁器

[0064] 282～流水线资源

[0065] 282A～第一流水线资源

[0066] 282B～第二流水线资源

[0067] 283～总线接口

[0068] C00、C01…C05～完成标志

[0069] P10、P11….P31～命令封包

[0070] PIN～发布指标

[0071] PRT～返送指标

[0072] PS1、PS2…PS4～进程

[0073] ROB～再排序缓冲器

[0074] S1201、S1202…S2212～步骤

[0075] TQ1、TQ2…TQ9～任务队列

具体实施方式

[0076] 以下的公开内容提供许多不同的实施例或范例以实施本申请的不同特征。以下的公开内容叙述各个构件及其排列方式的特定范例，以简化说明。当然，这些特定的范例并非用以限定。例如，若是本说明书叙述了一第一特征形成在一第二特征之上或上方，即表示其可能包含上述第一特征与上述第二特征是直接接触的实施例，也可能包含了有附加特征形成在上述第一特征与上述第二特征之间，而使上述第一特征与第二特征可能未直接接触的实施例。另外，以下说明书不同范例可能重复使用相同的参考符号和/或标记。这些重复是为了简化与清晰的目的，并非用以限定所讨论的不同实施例和/或结构之间有特定的关系。

[0077] 图1是显示根据本发明一实施例所述的处理系统10的示意图。处理系统10包括至少一个硬件加速器(AFU，accelerator function unit)110A～110N、至少一个处理器内核(core)120A～120N、加速器接口130以及系统存储器160。值得注意的是，处理器内核及硬件加速器的数量可以是任意个数，且二者并不一定数量相等。如图所示，加速器接口130耦接在多个硬件加速器110A～110N以及多个处理器内核120A～120N之间。在一实施例中，处理系统10还包括处理器非内核180，其耦接在加速器接口130与多个处理器内核120A～120N之间。处理系统10可为构成一电子装置的部分组成。上述电子装置为手机、平板计算机、笔记型计算机或是PDA等移动电子装置，或是桌上型计算机、服务器等电子装置。

[0078] 在一实施例中，至少一处理器内核120A～120N建立至少一任务(task)，硬件加速器110A～110N则用以执行上述任务。硬件加速器110A～110N主要用于加速一些特定的计算任务，这些计算任务如果由处理器内核120A～120N及其软件进行运算，将使得效率低下。硬件加速器110A～110N通过分析计算过程，设计专门的硬件逻辑处理计算的任务，以达到加速效果。

[0079] 举例而言，处理器内核120A～120N和硬件加速器110A～110N可包含数字信号处理器(digital signal processing，DSP)、微处理器(microcontroller，MCU)、一单一中央处理单元(central-processing unit，CPU)或者是关联于并行运算环境(parallel processing environment)的多个并行处理单元，用以执行操作系统、模块以及应用程序。值得注意的是，经由本发明的加速器接口130，处理器内核120A～120N可通过特殊的指令指示硬件加速器110A～110N进行加速操作，而不必在用户模式和内核模式之间频繁切换。

[0080] 在一实施例中，处理器内核120A～120N对应其上运行的至少一进程(process)在系统存储器160中建立关于上述任务的至少一任务队列。举例而言，这些任务队列具体可由硬件加速器110A～110N的驱动程序(driver)根据对应的进程而创建，每个进程可创建多个任务队列，不同的进程对应不同的任务队列。该进程，例如为压缩应用，当其运行到需要压缩大量数据的位置时，可以调用本发明特别定义的加速器指令以通知加速器接口130指派相应的硬件加速器110A～110N执行加速任务。详细而言，任务队列包括一标头(header)以及至少一命令封包(command packet)。上述任务是以命令封包为单位实现的，举例而言，命令封包包括该任务对应的一类型、一长度、至少一源地址及至少一目标地址。每个命令封包描述一个需要加速的任务，以加速任务为压缩解压数据为例，每个命令封包可指定压缩一定大小的源数据。上述标头用以存储关于该任务队列所隶属的进程的信息。

[0081] 此外，加速器接口130配置在处理器内核120A～120N与硬件加速器110A～110N之间，用以接收处理器内核120A～120N传送的关于上述任务的一加速器接口指令(instruction)。然后，加速器接口130依据加速器接口指令指示硬件加速器110A～110N，使得硬件加速器110A～110N执行上述任务。该特殊定义的加速器指令格式根据处理器内核120A～120N的指令集的不同而不同，可以是X86指令也可以是RISC指令。关于前述加速器指令的具体功能和实现后面会有详述。详细而言，加速器接口130解析该任务，并且依据上述任务的性质将此任务分配给对应的硬件加速器110A～110N。在一实施例中，加速器接口130可依据上述命令封包所包含的类型、长度、源地址及目标地址等信息，将此任务队列的命令封包分配给硬件加速器110A～110N的其中一个。值得注意的是，后会详述如何将任务分配给多个硬件加速器110A～110N的其中一个使得整体执行效率最高的算法，这里先描述包含多个硬件加速器110A～110N及仅包含一个硬件加速器的处理器系统10均普遍适用的内容。

[0082] 图2是显示根据本发明另一实施例所述的处理系统10的示意图。加速器接口130包括加速器接口前端130_FE与加速器接口后端130_BE，分别用以连接处理器内核120(在一实施例中，例如如图2所示是连接处理器非内核180)与硬件加速器110。在一实施例中，加速器接口前端130_FE包括一解码器132，加速器接口后端130_BE包括一微控制器140。处理系统10还包括一访存单元150耦接在硬件加速器110以及加速器接口130的微控制器140之间。

[0083] 要注意的是，硬件加速器110与处理器内核120共同使用多个虚拟地址以进行访存。在一实施例中，处理器内核120建立一任务并将此任务存储在上述虚拟地址的其中一个。详细而言，该任务由处理器内核120上运行的进程在用户模式下(user mode)根据自身的加速需求而创建，具体通过向该进程对应的任务队列中压入描述该任务的一命令封包(command packet)而创建；当然，如果该进程在系统存储器160中不存在对应的任务队列或者对应的任务队列已满，则应首先创建对应该进程的一任务队列(后面描述的都是需先创建一任务队列的情形)。详细而言，处理器内核120传送关于该任务的一加速器接口指令ACCIF_CMD至微控制器140，微控制器140依据该加速器接口指令ACCIF_CMD指示硬件加速器110使其执行该任务(例如该命令封包command packet)。在一实施例中，加速器接口指令ACCIF_CMD的第一子指令(sub-command，又称为第一微指令μop)ACCIF_CMD_Creat_QI包括该任务所存储的虚拟地址，例如包含该任务所存储的任务队列的基地址(task queue base address)，其当处理器内核120创建对应的任务队列时发出；加速器接口指令ACCIF_CMD的第二微指令ACCIF_CMD_New_Packet包括关于该任务(例如该命令封包command packet)对应的页目录表(page directory)基地址，其当处理器内核120将产生的命令封包压入对应的任务队列中时发出。

[0084] 然后，加速器接口130的解码器120解码该加速器接口指令ACCIF_CMD得到其所携带的页目录表基地址，从而确认该任务是否建权成功，微控制器140解析此该加速器接口指令ACCIF_CMD得到该任务(即命令封包)所存储的虚拟地址(如所存储的任务队列的基地址task queue base address)，并且将该任务分配给对应的硬件加速器110。值得注意的是在一实施例中，该任务所存储的任务队列的虚拟地址是处理器内核120在系统存储器160中创建该任务队列时藉由加速器接口指令ACCIF_CMD(例如其第一微指令ACCIF_CMD_Creat_QI)存储在微控制器140内部，后续当该任务队列有新的任务压入时，可从微控制器140直接查询到相应的虚拟地址。硬件加速器110藉由访存单元150访存该任务所存储的虚拟地址、并且通过读取该任务所包含的任务描述(例如包括待加速的目标数据的源地址/目标地址/长度等)以执行该任务。

[0085] 在一实施例中，微控制器140在解析任务后，将该任务所存储的虚拟地址传送给硬件加速器110。硬件加速器110依据该虚拟地址从系统存储器160读取用以执行任务所需的数据。在另一实施例中，微控制器140解析任务、并且依据解析结果从系统存储器160取得关于该任务的任务队列的命令封包，然后将上述命令封包传送给硬件加速器110使硬件加速器110执行任务。

[0086] 图3A是显示根据本发明一实施例所述的处理器内核120、处理器非内核180、与加速器接口前端130_FE的示意图。处理器非内核180包括非内核仲裁器181以及非内核量程器182，分别连接处理器内核120以及加速器接口前端130_FE。

[0087] 当多个任务同时被至少一处理器内核120所建立时，非内核仲裁器181将调度与仲裁上述多个任务，依序处理来自处理器内核120的多个任务，避免造成处理系统10的效能低落与速度延迟。再者，非内核量程器182用以根据上述任务的虚拟地址或性质判断该任务是否应由硬件加速器110处理，以决定是否传送上述任务至加速器接口前端130_FE，使加速器接口130进行任务解析、以及后续的任务派遣与调度。

[0088] 图3B是显示根据本发明一实施例所述的处理器非内核180、加速器接口前端130_FE、与加速器接口后端130_BE的示意图。加速器接口前端130_FE包括命令寄存器131、解码器132、权限列表134、寄存器136以及位映射表137。加速器接口后端130_BE包括微控制器140以及活跃列表147。其中，微控制器140还包括静态随机存取存储器142，用以存取权限列表134、位映射表137以及活跃列表147。

[0089] 在一实施例中，加速器接口130的命令寄存器131用以存储处理器内核120经由处理器非内核180所传送的加速器接口指令。在一实施例中，当处理器内核120创建一新的任务队列时，发出加速器接口指令的第一微操作(micro operation)，其包括任务在系统存储器160中所存储的虚拟地址。处理器内核120经由第一微操作将任务所存储的虚拟地址传送至加速器接口前端130_FE。处理器内核120经由加速器接口130存储该虚拟地址至微控制器140内部的一微控制器表格。然后，当处理器内核120在该任务队列中建立一任务(例如在该任务队列中压入一命令封包)时，发出加速器接口指令的第二微操作通知加速器接口130，如果该任务建权(后面图5会详述如何藉由第二微操作建权)成功，则微控制器140解析该任务并且分析其对应的任务的性质与内容，将该任务分配给多个硬件加速器110A～110N的其中一个。

[0090] 在另一实施例中，加速器接口指令的第二微操作ACCIF_CMD_New_Packet包括关于该任务的一页目录表(page directory)基地址，上述页目录表基地址用以索引一页表(page table)。详细而言，页表包括多个用以存储系统存储器160中的每一虚拟地址与每一物理地址之间的映射的页表条目。前述页表又包括多级(后面以两级为例说明，但本发明并不局限于此)，前述页目录表基地址指向第一级页表(又称为页目录page directory)的存储位置。系统存储器160中的物理地址空间是以页(page)为单位划分的，举例而言，每个物理页包含4K个字节，每个字节对应的虚拟地址包括32位(bit)，其中每个虚拟地址的高位(例如高10位)用于索引第一级页表，而第一级页表的每个表项指向对应的第二级页表所存储的位置；每个虚拟地址的中间位(例如中间10位)用于索引第二级页表，而第二级页表的每个表项指向系统存储器160的物理地址空间对应的页(page)，每个虚拟地址的低位(例如为低12位)为在对应页中的页内偏移，通过前述的二级页表的查表过程可将一虚拟地址转换为一物理地址。通常而言，处理器内核120上的进程不切换，其对应在系统存储器160中分配的页目录表基地址就不变，该页目录表基地址通常会存储在处理器内核120内部的页目录基地址寄存器(Page-Directory Base address Register，PDBR)中，该寄存器又叫做CR3控制寄存器。

[0091] 加速器接口130将第二微指令ACCIF_CMD_New_Packet所携带的该页目录表基地址与一预存页目录表基地址进行比对，以确认该任务是否建权成功(后面图5会详述)。如果页目录表基地址与预存页目录表基地址是符合的，则表示建权成功；如果两者不符合，则表示建权失败。要注意的是，上述预存页目录表基地址在一内核模式(kernel mode)下由该处理器内核120存储在该加速器接口130的一权限列表(privilege table)134中，其中权限列表(privilege table)134可同时存储多个进程的预存页目录表基地址，以供各进程后续有任务需要调度给硬件加速器110执行时建权使用。在其它实施例中，上述预存页目录表基地址也可存储在该加速器接口130的一微控制器表格、或是存储在处理系统10的系统存储器160中、或是存储在加速器接口前端130_FE的寄存器136中，本发明并不加以限制。

[0092] 当页目录表基地址与预存页目录表基地址的比对符合时，加速器接口130将建权成功的信息通知处理器内核120，以及更新关于该任务的一位映射表(bitmap)137。上述位映射表137用以指示该任务所对应的任务队列。然后，微控制器140依据更新后的位映射表137，控制所对应的硬件加速器110从系统存储器160中所对应的该任务队列中读取对应的任务。在硬件加速器110包含多个硬件加速器(例如图1的硬件加速器110A～110N)的实施例中，加速器接口130还根据该页目录表基地址辨识该任务所对应的进程，从而根据一定规则决定将其分配给多个硬件加速器110中对应的一个(后面会详述)。当加速器接口130从系统存储器160中读取任务后，则调度硬件加速器110执行所读取的该任务。

[0093] 在另一实施例中，当硬件加速器110执行该任务之后，硬件加速器110藉由中断(interrupt)或内存访问监控机制(memory access monitor mechanism)通知处理器内核110上述任务已执行完成。详细而言，在任务执行完成后，硬件加速器110或微控制器140可将任务完成标志(command complete flag)写入系统存储器160的特定地址，此即为内存访问监控机制的通知。此外，硬件加速器110或微控制器140也可发出中断通知，即时通知处理器内核120任务已执行完成。

[0094] 再者，在一实施例中，加速器接口指令还包括一第三微操作，用以删除关于该任务的任务队列。在另一实施例中，加速器接口指令还包括一第四微操作，用以建立或配置位于加速器接口前端130_FE的寄存器136。寄存器136用以存储权限列表134、位映射表137、加速器接口指令或其他数据与指令等，本发明并不加以限制。

[0095] 以下将详细说明位映射表137的功能与操作方式。图4是显示根据本发明一实施例所述的位映射表137与活跃列表147的示意图。当一新任务产生、以及加速器接口130比对新任务的页目录表基地址与预存页目录表基地址并且建权成功，则更新关于该新任务的位映射表137。上述位映射表137用以指示新任务所对应的任务队列。

[0096] 如图4所示，活跃列表147记录了多个任务队列的队列编号TQ1～TQ4及其对应的进程PS1～PS4。例如位映射表137的第3个位为1，表示关于新任务的任务队列为队列编号TQ3的任务队列。微控制器140可经由活跃列表147查询队列编号TQ3的任务队列对应进程PS3。因此，使用位映射表137能够提升加速器接口130查询任务队列与进程的速度，有效管理各种新任务以及调度分配给适当的硬件加速器110。

[0097] 上述活跃列表147可存储在微控制器140的静态随机存取存储器142、或是存储在寄存器136等。要注意的是，上述活跃列表147仅作为例示之用，而非用以限制本发明。举例而言，微控制器140可使用其他方式记录与管理任务队列及其对应的进程。再者，进程与任务队列可以是一对一、或者一对多的对应关系。换句话说，一个进程可包括一个任务队列或是两个以上的任务队列。

[0098] 图5是显示根据本发明一实施例所述的硬件加速器110A～110D、微控制器140与访存单元150的示意图。访存单元150包括多个调度器210A～210E以及一内存重排序缓冲区(Memory Reorder Buffer，MOB)250。其中，4个调度器210A～210D分别对应4个硬件加速器110A～110D，并且调度器210E对应微控制器140。硬件加速器110A～110D和/或微控制器140与至少一处理器内核藉由访存单元150共同使用处理系统10的多个虚拟地址访存。换句话说，硬件加速器110A～110D及微控制器140皆分别有其专属且对应的调度器210A～210E。上述多个调度器210A～210E和硬件加速器110A～110D的数量用以说明之用，而非用以限制本发明。

[0099] 在一实施例中，每一硬件加速器110A～110D用以对应执行多个任务中的至少一任务，并且该任务被解析后对应多个访存请求，具体而言，通常一个任务需藉由多个访存请求从系统存储器160中存取该任务相关的数据，例如该任务为压缩4M大小的数据，则需要藉由多个访存请求分批从系统存储器160读出待压缩数据，待硬件加速器110A～110D完成压缩操作后，再藉由多个访存请求分批将压缩结果写回系统存储器160。因此，当硬件加速器110A～110D被分配执行某个任务时，硬件加速器110A～110D基于该任务产生多个访存请求，并且上述访存请求对应的数据存储在上述多个虚拟地址中。此外，微控制器140在分配任务给硬件加速器110A～110D中对应的一个时，也需要产生多个访存请求以从系统存储器
160存取该任务本身(其中该任务本身在系统存储器160中的虚拟地址由前述第一微指令所包含的任务队列基地址决定)。调度器210A～210E分别耦接硬件加速器110A～110D及微控制器140，用以分别对硬件加速器110A～110D及微控制器140产生的多个访存请求进行排序，并且依序将该等访存请求的结果传送至硬件加速器110A～110D及微控制器140。要注意的是，上述访存请求相关的数据以及该任务本身都存储在处理器内核120、硬件加速器110A～110D及微处理器140三者共享的虚拟地址空间的上述虚拟地址中。值得注意的是，这里所谓的共享虚拟地址空间所映射的物理地址空间属于系统存储器160，系统存储器160也可包括多级缓存(cache)，例如第一级缓存(L1 cache)及第二级缓存(L2 cache)等，本发明并不以此为限。

[0100] 此外，访存单元150使用一转译查询缓冲器(TLB，translation look aside buffer，图未绘示)以暂时存储一页表中多个硬件加速器110A～110D访存时最有可能使用的多个页表条目。其中，每一该页表条目用以存储一虚拟地址与一物理地址之间的映射。由于硬件加速器110A～110D及微处理器140共享虚拟地址空间，即不同的硬件加速器110A～110D和/或微处理器140的任务数据对应相同虚拟地址空间(例如4G)，但不同的硬件加速器
110A～110D和/或微处理器140相同的这4G虚拟地址空间所映射(mapping)的物理地址是不同的，为了区分硬件加速器110A～110D和/或微处理器140相同的虚拟地址，本发明的转译查询缓冲器中暂时存储的每一该页表条目具有一第一辨识码，该第一辨识码用以表征该页表条目对应硬件加速器110A～110D和/或微处理器140中的哪个。上述多个访存请求的每一个亦分别具有一第二辨识码以表征该访存请求对应硬件加速器110A～110D和/或微处理器
140中的哪个。访存请求可藉由其第二辨识码与页表条目的第一辨识码是否匹配来判断该页表条目是否是属于自己对应的硬件加速器110A～110D和/或微处理器140的4G虚拟地址空间的映射关系，以决定是否使用该页表条目访存。此外，如果访存单元150没有成功经由对应的页表条目执行对应的访存请求(TLB miss)时，访存单元150依据该第二辨识码至硬件加速器110A～110D和/或微处理器140相应的寻访引擎进行寻访操作以从系统存储器160中将对应的页表条目载入该转译查询缓冲器。因此，本发明的一实施例藉由在每个页表条目及访存请求中均配置辨识码，除了能够辨识一页表条目是否是属于自己对应的虚拟地址空间的映射关系之外，还能够便于在访存单元150没有成功执行访存请求时执行寻访(tablewalk)操作，关于该寻访操作后面图6会详述。

[0101] 再者，如果访存单元150成功执行访存请求且产生对应的访存结果时，调度器210A～210E依照从硬件加速器110A～110D和/或微处理器140接收多个任务对应的多个访存请求的顺序，对上述多个访存请求进行排序。然后，访存单元150依照该顺序将上述访存请求的结果传送至对应的硬件加速器110A～110D和/或微处理器140。由此可知，即使在任务数量众多与繁复的情况下，调度器210A～210E的排序与调度功能能够让各个任务的访存结果依序传送至对应的硬件加速器110A～110D和/或微处理器140。

[0102] 图6是显示根据本发明一实施例所述的调度器210A～210E与内存重排序缓冲区250的示意图。内存重排序缓冲区250包括仲裁器281、流水线资源282、总线接口283以及多个寻访引擎(tablewalk engine)209A～209E。每一寻访引擎209A～209E分别对应每一调度器210A～210E。

[0103] 其中，流水线资源282包括第一流水线资源282A以及第二流水线资源282B用以轮流执行不同的访存请求。仲裁器281耦接在调度器210A～210E与流水线资源282之间，用以仲裁与决定多个访存请求被执行的顺序，然后依序将多个访存请求传送至第一流水线资源282A或第二流水线资源282B。

[0104] 详细而言，仲裁器281在每个时钟周期(clock)以轮询(round-robin)方式选定多个硬件加速器110A～110D及微处理器140(微处理器140也有对应的访存请求，例如需要读取任务本身)的调度器210A～210E的其中一个，将选定的该调度器对应的多个访存请求之一传送至流水线资源282，使仲裁器281所选定的该硬件加速器藉由第一流水线资源282A或第二流水线资源282B执行该访存请求以读写其任务相关的数据。换句话说，仲裁器281在每个时钟周期中，依照一定规则选定调度器210A～210E其中的一个的访存请求送至流水线资源282执行。

[0105] 在一实施例中，仲裁器281以轮询方式、亦即依序轮流询问与指派每一调度器210A～210E将其所对应的硬件加速器和/或微处理器140的一访存请求的传送至该流水线资源282，并且藉由第一流水线资源282A或第二流水线资源282B执行该访存请求以读写其任务相关的数据。因此，每一调度器210A～210E都能平均获得相同的机会进行其所对应的调度请求。

[0106] 然后，流水线资源282接收并执行调度器210A～210E所传送的多个访存请求，并且在该等访存请求执行结束后，经由每一调度器210A～210E依据该等访存请求的原始顺序将上述访存请求的执行结果传送至所对应的硬件加速器110A～110D和/或微处理器140。硬件加速器110A～110D也可依据访存结果(例如藉由访存读取的待压缩数据)执行对应的任务。

[0107] 如前所述，每一访存请求分别具有一第二辨识码。在一实施例中，仲裁器281还可依据上述第二辨识码为奇数或偶数，将所对应的每一访存请求传送至第一流水线资源282A或第二流水线资源282B。在其它实施例中，仲裁器281还可依据访存请求在各自调度器210A～201E中的排序号为奇数或偶数，将所对应的每一访存请求传送至第一流水线资源282A或第二流水线资源282B，本发明并不以此为限。当访存请求的数量增加时，也可对应配置三个以上的流水线资源以避免产生延迟或降低运算效能。

[0108] 在另一实施例中，访存单元150使用转译查询缓冲器以暂时存储硬件加速器访存时最有可能使用的页表条目。如果访存单元150没有成功经由对应的页表条目执行对应的访存请求(即TLB未命中，TLB miss)时，由于寻访引擎209A～209E与硬件加速器110A～110D及微处理器140一一对应，因此访存请求所携带的第二辨识码也可用以辨识与之对应的寻访引擎209A～209E，访存单元150可直接依据该访存请求所携带的第二辨识码至寻访引擎209A～209E中与其第二辨识码对应的一个执行寻访(table walk)操作；寻访引擎209A～
209E中对应的一个依据前述的页目录表(page directory)基地址及该访存请求所包含的虚拟地址(即virtual address)经由一多级页表寻址以从处理系统10的系统存储器160中载入对应的页表条目。

[0109] 再者，当对应的寻访引擎209A～209E从系统存储器160中载入对应的该页表条目时，对应的寻访引擎209A～209E在载入的页表条目中填入访存请求的第二辨识码作为该页表条目之前述第一辨识码，以表征该页表条目所对应的调度器210A～210E(即对应的硬件加速器110A～110D和/或微处理器140)，以表征该页表条目是属于硬件加速器110A～110D和/或微处理器140中哪个的虚拟地址空间(例如都是4G的虚拟地址空间)的映射关系。要注意的是，每一硬件加速器110A～110D和/或微处理器140、及其所对应的每一调度器210A～210E、以及其所对应的每一寻访引擎209A～209E具有相同的页目录表(page directory)基地址。

[0110] 以下将详细说明如何调度与分配多个命令封包至硬件加速器110以执行命令封包。现在返回参考图1，在硬件加速器110包含多个硬件加速器110A～110N的实施例中，加速器接口130(或图2的微控制器140)配置在该硬件加速器110与处理器内核120之间，用以调度多个命令封包至对应的硬件加速器110A～110N的其中一个执行。当硬件加速器110A～110N的任何一个执行属于多个进程其中的一个的至少一命令封包时，加速器接口130(或微控制器140)指派该硬件加速器110优先执行属于该进程的该等任务队列的其他该等命令封包。

[0111] 详细而言，加速器接口130(或微控制器140)为每一硬件加速器110A～110N对应每一任务队列分别配置一时间片(time slice)，并且藉由轮询(round-robin)方式分配该等命令封包的一至多个硬件加速器110A～110N中对应于该命令封包所属的任务队列的该时间片不为零的一个硬件加速器执行。在该硬件加速器执行命令封包之后，加速器接口130(或微控制器140)将该硬件加速器110对应于该命令封包所属的任务队列的时间片减一。

[0112] 当时间片的数值递减为零、或是已执行的命令封包所属的任务队列尚无新的命令封包压入，则微控制器140查询已执行的命令封包所属的进程，并且指派硬件加速器110执行该进程对应的其它任务队列的命令封包。换句话说，微控制器140优先执行相同进程的任务队列的多个命令封包，减少切换到其他不同进程的次数，以避免产生处理时间的延宕。其中一个任务(即命令封包)所隶属的进程的信息存储在其所存储的任务队列的标头(header)中。

[0113] 要注意的是，每个硬件加速器110A～110N对应为每一个任务队列配置时间片，并且每个任务队列的时间片都是各自独立的。因此，一个硬件加速器110可同时具有属于不同任务队列的多个时间片。藉由配置多个任务队列的时间片以及轮询机制的执行，能够平均调度与分配多个任务队列的命令封包，避免发生过度集中分配与执行一部分的任务队列、却忽略与闲置另一部分的任务队列的情况。值得注意的是，本发明前述配置多个任务队列的时间片以及轮询机制适用于包含多个硬件加速器110A～110D的处理系统10，但本发明并不局限于此，仅包含一个硬件加速器110的处理系统10在调度多个任务队列(或进程)的命令封包时同样适用。

[0114] 在另一实施例中，硬件加速器110A～110D的任何一个所执行的多个命令封包具有关联性时，微控制器140指派该硬件加速器优先执行具有关联性的其它命令封包。例如，连续几个命令封包压缩同一个文件(file)的数据，则这几个命令封包就具备关联性。详细而言，当一命令封包与在前的命令封包对应相同的上下文(context)信息时，则表示该命令封包具有关联性。然后，硬件加速器110使用该上下文信息执行具有关联性的命令封包。其中，上下文信息可暂存在硬件加速器110的内部随机存取存储器(internal RAM)116。

[0115] 此外，当上述命令封包不具有关联性时，微控制器140存取处理系统10的系统存储器160以执行上下文保留(context save)操作或上下文再存储(context restore)操作。换句话说。微控制器140取得对应的上下文信息并将其暂存在系统存储器160或内部随机存取存储器116。此外，上述命令封包还包括一相依起始标示与一相依结束标示，分别用以指示关联性的起始与结束。

[0116] 因此，微控制器140能够依据上述相依起始标示与相依结束标示，判断多个命令封包之间的关联性是否结束。在一实施例中，当时间片的该数值递减为零、但命令封包的关联性尚未结束时，微控制器140将时间片的数值加N，其中N为大于1的正整数。换句话说，微控制器140将继续分配具有上述关联性的命令封包直到关联性结束。

[0117] 以下将以具体案例说明分配多个命令封包至硬件加速器以执行命令封包的方法。图7A是显示根据本发明一实施例所述的将命令封包P11～P31压入任务队列TQ1～TQ3的示意图；图7B是显示根据本发明一实施例所述的2个硬件加速器110A与110B依序执行命令封包P11～P31的示意图。

[0118] 如图7A所示，任务队列TQ1包括4个命令封包P10～P13，任务队列TQ2包括4个命令封包P20～P23，任务队列TQ3包括2个命令封包P30～P31。此外，3个任务队列TQ1～TQ3属于不同的进程，并且时间片的初始数值为3。首先，微控制器140分别逐一分配命令封包任务队列TQ1与TQ2的命令封包P10～P13、P20～P23至硬件加速器110A与110B。硬件加速器110A与110B每执行一命令封包时，就会分别递减任务队列TQ1与TQ2的时间片的数值。

[0119] 因为时间片的初始数值为3，当硬件加速器110A执行3个命令封包P10～P12时，其对应任务队列TQ1的时间片的数值为0。因此，微控制器140将指派与任务队列TQ1命令隶属于相同进程的其他命令队列的命令封包给硬件加速器110A。同样地，当硬件加速器110B执行3个命令封包P20～P22时，其对应任务队列TQ2的时间片的数值为0。因此，微控制器140将指派与任务队列TQ2命令隶属于相同进程的其他命令队列的命令封包给硬件加速器110A。

[0120] 对于硬件加速器110A而言，任务队列TQ2与TQ3的进程都和任务队列TQ1的进程不相同，因此微控制器140可以指派任务队列TQ2或TQ3的命令封包给硬件加速器110A。然而，由于硬件加速器110B对应于任务队列TQ2的时间片已经减为0，微控制器140依据轮询机制指派任务队列TQ3的命令封包给硬件加速器110A，而不指派任务队列TQ2的命令封包给硬件加速器110A。

[0121] 同样地，对于硬件加速器110B而言，由于硬件加速器110A对应于任务队列TQ1的时间片已经减为0，微控制器140依据轮询机制指派任务队列TQ3的命令封包给硬件加速器110B，而不指派任务队列TQ1的命令封包给硬件加速器110B。因此如图7B所示，硬件加速器
110A依序执行4个命令封包P10～P12以及P30，硬件加速器110B则依序执行4个命令封包P20～P22以及P31。

[0122] 图8A是显示根据本发明一实施例所述的执行不同任务队列TQ1～TQ3的命令封包的示意图。在此实施例中，2个任务队列TQ1与TQ2属于进程A，任务队列TQ3属于不同于进程A的另一进程B。如图所示，微控制器140依序指派任务队列TQ1的命令封包P10与P11，然后任务队列TQ1所对应的时间片已经递减为0。因此，微控制器140调度同一进程A的另一任务队列TQ2的任务封包P20～P22。

[0123] 然后，任务队列TQ2所对应的时间片已经递减为0。此时，因为任务队列TQ3对应的进程B不同于进程A，因此微控制器140将分配进程A的任务队列TQ1的命令封包P12。详细而言，由于任务队列TQ1所对应的时间片已经递减为0，微控制器140将任务队列TQ1所对应的时间片增加1(亦即剩余尚未分配的命令封包的数量)，以指派进程A的任务队列TQ1的命令封包P12。此外，在另一实施例中，如果命令封包P10～P12的关联性尚未结束，微控制器140也可将任务队列TQ1所对应的时间片增加1(亦即关联性尚未结束的命令封包的数量)，以指派进程A的任务队列TQ1的命令封包P12。

[0124] 图8B是显示根据本发明另一实施例所述的执行不同任务队列TQ1～TQ3的命令封包的示意图。此实施例类似于图8A的实施例，其差异在于3个命令队列都是属于进程A。因此，当微控制器140调度进程A的任务队列TQ2的任务封包P20～P22之后，可依据轮询原则调度同属进程A的另一任务队列TQ3的任务封包P30，以避免任务队列TQ3被闲置太久。

[0125] 图9是显示根据本发明另一实施例所述的执行不同任务队列TQ1～TQ3的命令封包的示意图。在此实施例中，进程A包括任务队列TQ2，另一进程B包括任务队列TQ1与TQ3，任务队列TQ1的命令封包P10～P12具有关联性，任务队列TQ2的命令封包P20～P22则不具有关联性。因为任务队列TQ2所对应的进程A不同于另外2个任务队列TQ1与TQ3所对应的进程B，如果任务队列TQ2的时间片没有被递减为0，微控制器140会指派任务队列TQ2的全部命令封包，再去指派其他进程的任务队列。

[0126] 当微控制器140指派任务队列TQ2的命令封包P20～P22之后，将指派另一进程B的任务队列TQ1的命令封包P10～P12。要注意的是，因为任务队列TQ1的命令封包P10～P12具有关联性，当相互关联的命令封包P10～P12指派完成后，微控制器140再指派相同进程A的另一任务队列TQ3的不具有关联性的命令封包P30～P32。

[0127] 图10是显示根据本发明另一实施例所述的执行不同任务队列TQ1～TQ3的命令封包的示意图。此实施例类似于图9的实施例，其差异在于任务队列TQ1的命令封包P10～P12不具有关联性。因此，当微控制器140指派任务队列TQ1的命令封包P10之后，可指派相同进程但是不具有关联性的其他命令封包。因此，微控制器140基于轮询机制指派同属于进程B的任务队列TQ3的命令封包P30，而不是指派任务队列TQ1的命令封包P11。然后，微控制器140再基于轮询机制指派同属于进程B的任务队列TQ1的命令封包P11，以此类推。

[0128] 以下将详细说明如何藉由再排序缓冲区(reorder buffer)搭配位映射表137与活跃列表147以进行命令封包的指派与调度。在一实施例中，加速器前端130_FE接收并解码加速器接口指令以设置位映射表137。详细而言，加速度接口指令第二微指令ACCIF_CMD_New_Packet，其由处理器内核120在产生新的命令封包并将其压入对应的任务队列后发出。

[0129] 然后，加速器后端130_BE依据位映射表137更新活跃列表147，以及依据活跃列表147从多个任务队列之一选择多个命令封包的其中一个，并且调度所选择的命令封包至对应的硬件加速器110执行。要注意的是，位映射表137用以指示有上述命令封包产生的该任务队列。活跃列表147用以指示存在上述命令封包的该任务队列，即不为空的任务队列。此外，如图4的活跃列表147所示，活跃列表147可用以指示存在上述命令封包的该任务队列所对应的进程，亦即该进程的该任务队列并非空的(empty)，而是具有至少一个命令封包。

[0130] 由于前述所选择的命令封包被调度至对应的硬件加速器110后并不会立即被执行，即便是立即被执行，硬件加速器110执行每一命令封包的时间是不相同的，因此先被调度的命令封包也可能较晚完成。在另一实施例中，为每一任务队列再配置一再排序缓冲器(reorder buffer)ROB(图未绘示)，用以依照每一任务队列中的多个命令封包在每一任务队列中的一原始排列顺序排序该等命令封包。然后，加速器接口130依据上述原始排列顺序将硬件加速器110执行完成后的多个命令封包返回处理器内核120。硬件加速器110执行每一命令封包的时间是不相同的，利用再排序缓冲器ROB可将每一命令封包的执行结果依照原始排列顺序返回给处理器内核120，避免因为返送顺序不一致而发生错误。此外，该再排序缓冲器存储在加速器接口130的静态随机存取存储器142。

[0131] 由此可知，当加速器接口130一次性调度多个命令封包至多个硬件加速器110执行时，加速器接口130依据任务队列中封包的原始排列顺序，一次性将执行完成后的多个命令封包返回处理器内核120。详细而言，再排序缓冲器ROB还包括一发布指标以及一返送指标。发布指标用以指向下一个要被调度至硬件加速器110执行的命令封包，返送指标用以指向下一个要被返回处理器内核120的命令封包。再者，再排序缓冲器ROB更对应每一命令封包存储一个完成标志，用以指示对应的每一命令封包是否执行完成。

[0132] 图11A～11D依顺序显示根据本发明一实施例所述的再排序缓冲器ROB及其相关的发布指标PIN、返送指标PRT与完成标志C00～C05的示意图。在此实施例中，再排序缓冲器ROB的多个表项具有多个完成标志C00～C05，分别用以指示对应的命令封包P00～P05是否执行完成。位0表示对应的命令封包尚未执行完成，位1表示对应的命令封包已经执行完成。

[0133] 首先在图11A中，全部命令封包P00～P05都还没被指派也还没被执行，因此其对应的完成标志C00～C05都为0，并且发布指标PIN与返送指标PRT都指向再排序缓冲器ROB的第1个表项，即命令封包P00对应的表项。

[0134] 接着，在图11B中，微控制器140指派命令封包P00～P03至硬件加速器110，但是硬件加速器110尚未执行完成。因此完成标志C00～C03仍为0，但是发布指标PIN指向命令封包P04对应的表项，表示下一个要被调度至硬件加速器110执行的是命令封包P04。

[0135] 接着，在图11C中，命令封包P01与P02执行完成，因此其对应的完成标志C01与C02为1，其他完成标志仍维持为0。要注意的是，由于再排序缓冲器ROB的第1个表项(即命令封包P00对应的表项)完成标志C00为0，故此时微控制器140仍无法依照原始排列顺序返送已执行完成的命令封包P01与P02给处理器内核120。

[0136] 接着，在图11D中，命令封包P00执行完成，因此其对应的完成标志C00为1。由于再排序缓冲器ROB的第1个完成标志C00为1，故此时微控制器140依照原始排列顺序返送已执行完成的命令封包P01～P02给处理器内核120。此外，返送指标PRT指向命令封包P03对应的表项，表示下一个要被返回处理器内核120的是命令封包P03。

[0137] 以下将详细说明本发明所述的各种处理系统以及异构处理器的加速、调度与访存方法。图12A与12B是显示根据本发明一实施例所述的异构处理器加速方法，该流程主要由处理器内核120执行。首先，在步骤S1201，处理器内核120启动硬件加速器110，具体而言处理器内核120会先判断处理系统10中是否存在硬件加速器110可供其使用，若是则启动硬件加速器110，若否则结束。在步骤S1202，处理器内核120在内核模式下预先存储关于该任务的预存页目录表基地址至权限列表134。在步骤S1203，处理器内核120在用户模式下在系统存储器160中建立对应该任务的一任务队列。

[0138] 接着，在步骤S1204，处理器内核120准备并且将关于该任务的加速器接口指令的第一微操作通过处理器非内核180传送至加速器接口130。上述加速器接口指令包括存储该任务队列的虚拟地址。

[0139] 在步骤S1208，处理器非内核180藉由虚拟地址判断该任务是否应该由该硬件加速器110执行。如果判断该任务不应该由该硬件加速器110执行，则再次执行步骤S1204；如果判断该任务应该由该硬件加速器110执行，则执行步骤S1210，经由该加速器接口130存储该虚拟地址至微控制器表格。在步骤S1211，在用户模式下在该任务队列中建立至少一任务(例如压入至少一命令封包)时，并且将关于该任务的加速器接口指令的第二微操作通过处理器非内核180传送至加速器接口130。上述第二微操作包括一页目录表基地址[0140] 在步骤S1212，藉由加速器接口130比较该页目录表基地址与该预存页目录表基地址以确定该任务是否建权成功。如果建权不成功，则再次执行步骤S1204；如果建权成功，则执行步骤S1214，处理器内核120接收加速器接口130所传送的任务建权成功的信息。然后在步骤S1216，处理器内核120执行该任务之外的其他任务。在步骤S1218，处理器内核120接收硬件加速器110所传送的该任务完成的信息。

[0141] 图13是显示根据本发明另一实施例所述的异构处理器加速方法，该流程主要由加速器接口130执行。在步骤S1302，在处理器内核120与硬件加速器110之间配置一加速器接口130。在步骤S1304，接收用以使硬件加速器130执行一任务的加速器接口指令，其包含一页目录表基地址以索引一页表。在步骤S1306，藉由加速器接口130解码加速器接口命令以产生对应的微操作。

[0142] 然后在步骤S1310，比对该页目录表基地址与一预存页目录表基地址，以确定该任务是否建权成功。如果没有建权成功，则再次执行步骤S1304；如果建权成功，则执行步骤S1312，将建权成功的信息通知处理器内核120。接着在步骤S1314，更新关于该任务之一位映射137表、读取所对应的该任务队列、并调度所对应的硬件加速器110依据系统存储器160中的该任务队列执行该任务。

[0143] 图14是显示根据本发明一实施例所述的用以分配任务的处理系统的访存方法。在步骤S1402，配置多个硬件加速器110与处理器内核120共同使用多个虚拟地址以进行访存。在步骤S1404，处理器内核120建立一任务，并将该任务存储在其中一虚拟地址，如前图12A所述，建立该任务即在以某个虚拟地址为队列基地址(queue base address)的任务队列中压入一命令封包。在步骤S1406，微控制器140解析该任务，并且依据该任务的性质分配给其中一硬件加速器110。然后在步骤S1408，硬件加速器110藉由访存单元150访存该任务所存储的虚拟地址。在步骤S1410，硬件加速器110执行该任务。

[0144] 要注意的是，如果硬件加速器110与处理器内核120没有共同使用多个虚拟地址以进行访存，硬件加速器110在完成任务后只能先将数据写入硬盘或系统存储器160，然后处理器内核120再去读取，需要两次从硬盘或系统存储器160移动数据的过程。相较之下，本发明配置硬件加速器110与处理器内核120共同使用多个虚拟地址以进行访存，能够简化数据移动的过程而达到加速的目的。

[0145] 图15是显示根据本发明一实施例所述的使用轮询机制的访存方法。在步骤S1502，依据多个任务的性质将任务分配给多个硬件加速器110的其中一个。在步骤S1504，被指派的硬件加速器110依据对应的任务产生多个访存请求。在步骤S1506，在每个时钟周期以轮询方式指派上述硬件加速器110的其中一个，将其对应的任务对应的多个访存请求之一传送至流水线资源282。

[0146] 然后在步骤S1508，被指派的硬件加速器110藉由流水线资源282执行该访存请求以以从系统存储器160读写该任务相关的数据。在步骤S1510，将访存请求的执行结果传送至仲裁器281所指派的硬件加速器110。上述仲裁器281、流水线资源282的配置方式如图6所示，故此处不再赘述。

[0147] 图16是显示根据本发明另一实施例所述的使用轮询机制的访存方法。在步骤S1602，配置多个硬件加速器110与处理器内核120共同使用多个虚拟地址以进行访存，且在任务的每一访存请求配置一辨识码，以表征其页表条目对应的该等硬件加速器110和/或微处理器140的其中一个。换句话说，每个访存请求就具有其专属的辨识码，以快速查询所对应的访存请求主体(硬件加速器110和/或微处理器140)。

[0148] 在步骤S1606，暂时存储一页表中多个硬件加速器110和/或微处理器140访存时最有可能使用的多个页表条目在一转译查询缓冲器(TLB，translation look aside buffer)。详细而言，每一页表条目存储一虚拟地址与一物理地址之间的映射。在步骤S1608，当访存请求没有成功经由暂时存储的页表条目访存时，流水线资源282依据该辨识码将访存请求传送至对应的寻访引擎209A～209E以从系统存储器160中载入对应的页表条目。换句话说，如图5及图6所示，硬件加速器110A～110D及微处理器140皆分别有其专属且对应的调度器210A～210E以及寻访引擎209A～209E。

[0149] 接着在步骤S1609，对应的寻访引擎209A～209E依据一页目录表基地址及访存请求所包含的虚拟地址，寻址一多级页表以载入对应的页表条目至转译查询缓冲器TLB。在步骤S1610，对应的寻访引擎209A～209E从系统存储器160中载入对应页表条目时，其在载入的页表条目中填入该访存请求的辨识码。在步骤S1611，依据该辨识码为奇数或偶数，将所对应的每一访存请求传送至第一流水线资源282A或第二流水线资源282B。因此，藉由上述辨识码以及配合第一流水线资源282A和第二流水线资源282B的分流配置，能够加速访存请求的处理速度。除此之外，从系统存储器160中载入的页表条目由于被填入了该辨识码，因此访存请求可藉由该辨识码判断被载入的该页表条目是否与之对应。

[0150] 图17是显示根据本发明一实施例所述的用于调度的处理系统的访存方法。在步骤S1702，配置多个调度器210A～210E，其中每一调度器对应多个硬件加速器110及微处理器140的每一个。在步骤S1704，依照以对应的硬件加速器110及微处理器140接收多个访存请求的顺序对上述访存请求进行排序。在步骤S1706，以轮询方式指派每一调度器210A～210E将其所对应的硬件加速器110及微处理器140的访存请求传送至流水线资源282。在步骤S1708，流水线资源282接收并执行调度器210A～210E所传送的访存请求。在步骤S1710，每一调度器210A～210E依据步骤S1704的排序顺序将多个访存请求的执行结果传送至所对应的硬件加速器110。

[0151] 图18是显示根据本发明一实施例所述的用以任务调度与分配的处理器加速方法。在步骤S1801，配置一微控制器140在至少一硬件加速器110与处理器内核120之间。在步骤S1802，经由处理器内核120对其运行的多个进程(process)之一建立至少一任务队列。

[0152] 然后在步骤S1803，经由处理器内核120产生多个命令封包并将其压入对应的任务队列。在步骤S1804，经由微控制器140调度该等命令封包至对应的硬件加速器110执行。在步骤S1806，当任一硬件加速器110所执行的命令封包属于该等进程其中的一个时，微控制器140指派硬件加速器110优先执行属于该进程的任务队列的其他命令封包。值得注意的是，图18的方法流程并不限制硬件加速器110的个数，包含一个或多个硬件加速器110的处理系统10均可适用本发明的任务调度与分配的处理器加速方法。

[0153] 图19是显示根据本发明另一实施例所述的用以任务调度与分配的处理器加速方法。在步骤S1902，在每一硬件加速器110对应每一任务队列分别配置一时间片。在步骤S1904，藉由轮询方式分配多个命令封包的一个至该等硬件加速110器中对应于该命令封包所属的任务队列的时间片不为0的一硬件加速器110执行。在步骤S1906中，在执行该等命令封包之后，将硬件加速器110对应于命令封包所属的任务队列的时间片的数值减1。

[0154] 在步骤S1908，判断该数值是否递减为零、或是已执行的该等命令封包所属的任务队列尚无新的命令封包压入。如果该数值并未递减为零、或是已执行的该等命令封包所属的任务队具有新的命令封包压入，则再次执行步骤S1906。如果该数值递减为零、或是已执行的该等命令封包所属的任务队没有新的命令封包压入，则执行步骤S1910。在步骤S1910，查询已执行的命令封包所属的进程。在步骤S1912，指派该硬件加速器执行该进程对应的其他任务队列的命令封包。值得注意的是，图19的方法流程并不限制硬件加速器110的个数，包含一个或多个硬件加速器110的处理系统10均可适用本发明的任务调度与分配的处理器加速方法。

[0155] 图20A与20B是显示根据本发明另一实施例所述的用以任务调度与分配的处理器加速方法。在步骤S2002，处理器内核120运行多个进程，对应每一该等进程建立至少一任务队列，产生多个命令封包并将其压入对应的该等任务队列。在步骤S2004，微控制器140调度多个命令封包至对应的硬件加速器110执行。

[0156] 接着在步骤S2006，判断硬件加速器110是否执行属于该等进程其中的一个的命令封包。如果硬件加速器110并未执行属于该等进程其中的一个的命令封包，则再次执行步骤S2004。如果硬件加速器110执行属于该等进程其中的一个的命令封包，则执行步骤S2008，微控制器140指派该硬件加速器110优先执行属于该进程的该等任务队列的其他命令封包。

[0157] 在步骤S2010，判断硬件加速器110所执行的命令封包是否具有一关联性。如果硬件加速器110所执行的命令封包具有关联性，则执行步骤S2012，微控制器140指派硬件加速器110优先执行具有该关联性的其它命令封包。如果硬件加速器110所执行的命令封包不具有关联性，则执行步骤S2018，微控制器140存取一系统存储器160以执行上下文保留(context save)操作或上下文再存储(context restore)操作。

[0158] 然后，在步骤S2014，判断上述命令封包的其中一个与在前的其他命令封包是否对应相同的上下文信息。如果该命令封包与在前的其他命令封包没有对应相同的上下文信息，则再次执行步骤S2012。如果该命令封包与在前的其他命令封包具有对应相同的上下文信息，则执行步骤S2016，硬件加速器120使用该上下文信息执行具有该关联性的该等命令封包。其中前述上下文信息可暂存在硬件加速器110的内部随机存取存储器116。值得注意的是，

[0159] 图20的方法流程并不限制硬件加速器110的个数，包含一个或多个硬件加速器110的处理系统10均可适用本发明的任务调度与分配的处理器加速方法。

[0160] 图21是显示根据本发明一实施例所述的用以任务调度的处理器加速方法。在步骤S2100，经由至少一处理器内核运行多个进程，并且对应每一进程建立至少一任务队列。在步骤S2101，经由处理器内核120产生多个命令封包，并将其压入对应的任务队列，以及传送关于该任务队列的一加速器接口指令。在步骤S2102，配置一加速器接口130在硬件加速器110与处理器内核120之间，用以接收该加速器接口指令。

[0161] 然后在步骤S2104，依据该加速器接口命令设置一位映射表137，用以指示有该等命令封包产生的该等任务队列。在步骤S2108，加速器接口130依据位映射表137更新一活跃列表147，并且加速器接口130依据活跃列表137从上述任务队列之一选择该等命令封包的其中一个。然后在步骤S2110，加速器接口130依据该等命令封包的关联性将所选择的该命令封包指派至硬件加速器110执行。

[0162] 图22是显示根据本发明另一实施例所述的用以任务调度的处理器加速方法。在步骤S2202，在每一该等任务队列配置一再排序缓冲器，以依照该等命令封包在每一任务队列中一原始排列顺序排序多个命令封包。在步骤S2204在再排序缓冲器配置一发布指标，以指向再排序缓冲器中的下一个要被调度至硬件加速器110执行的命令封包。在步骤S2206，在再排序缓冲器配置一返送指标，以指向再排序缓冲器中的下一个要被返回处理器内核120的命令封包。

[0163] 在步骤S2208，经由硬件加速器110执行上述命令封包。在步骤S2210，依据再排序缓冲器中为每一命令封包配置的一完成标志判断上述命令封包是否执行完毕。如果上述命令封包尚未执行完毕，则再次执行步骤S2208，经由硬件加速器110执行上述命令封包。如果上述命令封包已执行完毕，则执行步骤S2211，依据上述命令封包的原始顺序将已执行的命令封包返回处理器内核120。然后在步骤S2212，修改返回指标以指向上述完成并返回的所有命令封包之后的下一命令封包。

[0164] 在本说明书以及权利要求书中的序数，例如“第一”、“第二”、“第三”等等，彼此之间并没有顺序上的先后关系，其仅用于标示区分两个具有相同名字的不同元件。本发明说明书中“耦接”一词泛指各种直接或间接的电性连接方式。本说明书以及权利要求书中的术语“访存”为“访问存储器(memory access)”的简称，其包括从系统存储器中加载(load)数据和/或存储(store)数据到系统存储器，此外，“系统存储器”在其它实施例中也可以是“内存”。

[0165] 本发明虽以优选实施例公开如上，然其并非用以限定本发明的范围，本领域技术人员，在不脱离本发明的精神和范围内，当可做些许的更动与润饰，因此本发明的保护范围当视所附权利要求书界定范围为准。