一种动态可重构处理器的任务级并行调度方法与系统

摘要

本发明提出一种动态可重构处理器的任务级并行调度方法与系统，其中该系统包括主控制器、多个可重构处理单元、主存储器、直接存储访问和系统总线，其中，所述每个可重构处理单元由协控制器、多个负责可重构计算的可重构处理单元阵列和多个用于数据存储的共享存储器组成，其中所述可重构处理单元阵列和共享存储器相邻排列，所述共享存储器可被周围相连的两个可重构处理单元阵列所读写。本发明提出的动态可重构处理器的任务级并行调度方法与系统，通过调节调度方法能够针对不同的任务进行不同的调度方式，基本所有并行任务均能在这种可重构处理器上得到好的并行加速。

权利要求

1.一种动态可重构处理器的任务级并行调度方法，其特征在于，包括下列步骤：

将应用程序中的计算密集的可并行代码封装为内核函数；

将串行部分代码和并行部分代码分别编译生成适合主控制器和可重构处理单元的可执行代码；

所述主控制器执行串行部分代码；

当执行到内核函数部分代码时，所述主控制器对可重构处理单元进行调度分配处理所述内核函数部分代码；

其中，当所述内核函数指令较多，不能一次性的执行完内核函数的所有语句时，将内核函数分为多个长度相同的子任务，分别将子任务的配置信息按顺序分配给多个可重构处理单元阵列，由于每个可重构处理单元阵列可以读写相邻的上层共享存储器和下层共享存储器，将每个共享存储器分为等大小的A块和B块，在任务流水过程中，每个可重构处理单元阵列先从上层共享存储器的A块读取数据，并将结果写入下层共享存储器的B块，处理结束之后，每个可重构处理单元阵列再从上层共享存储器的B块读取数据，并将结果写入下层共享存储器的A块，在这两个过程的同时，对首末共享存储器没有参与计算的部分进行数据到主内存的搬运。

2.根据权利要求1所述的动态可重构处理器的任务级并行调度方法，其特征在于，所述主控制器对可重构处理单元进行调度分为同步调用和异步调用两种并行方式：若为同步调用，则由主控制器寻找未在运行中的可重构处理单元，并且载入可执行代码和配置信息，与此同时，主控制器挂起，同步调用中，将多个可重构处理单元同时调用，处理不同数据块的内容，在所有的可重构处理单元处理结束之后，通过同步函数返回值来更新处理结果，并且继续主控制器的串行代码执行；

若为异步调用，则由主控制器寻找未在运行中的可重构处理单元，与此同时在不中断主控制器的前提下将可执行代码和配置信息载入，启动可重构处理单元，主控制器继续运行至需要可重构处理单元返回数据时，再中止等待可重构处理单元计算完成并返回数据。

3.根据权利要求1所述的动态可重构处理器的任务级并行调度方法，其特征在于，当所述内核函数指令较少，一个可重构处理单元可以单独完成整个内核函数的计算任务时，其内部的多个可重构处理单元阵列并行执行相同的配置信息，每个可重构处理单元阵列负责自己的共享存储器的数据计算。

说明书

一种动态可重构处理器的任务级并行调度方法与系统

技术领域

[0001] 本发明涉及计算机领域，且特别涉及一种动态可重构处理器的任务级并行调度方法与系统。

背景技术

[0002] 在以往的处理器计算模式中，通常分为以下两类。传统的以冯·诺依曼处理器为基础的通用计算具有极强的灵活性，但是其指令流驱动的执行方式、有限的运算单元和存储带宽使其整体性能和功耗并不理想。专用计算可以针对特定的应用优化结构和电路，无需指令集，其执行速度快，功耗低。但专用计算系统存在着致命的缺陷，灵活性和扩展性很差，对不断演化的更加复杂的应用往往不能通过简单的扩展来完成。针对不同的应用，必须设计不同的专用计算系统，因此硬件的设计往往无法跟上应用的更新速度。同时，专用计算系统的设计周期长，一次性工程投入成本过高。可重构计算正是在这种背景下出现的一种将软件的灵活性和硬件的高效性结合在一起的计算方式，可重构计算技术结合了通用处理器和ASIC两者的优点，既能够提供硬件的高效率又具有软件的可编程性。其在性能、功耗和灵活性等关键指标之间取得更好的平衡，填补了通用计算和专用计算之间的空白。

[0003] 现阶段计算机中的处理器主流是拥有2～8个核心的多核CPU以及众核GPU，而这种设计也使得并行处理成为了热门课题，并行算法和并行编程也成为了程序员必须了解和掌握的内容。2007年6月，NVIDIA推出了CUDA，这是一种将GPU作为数据并行计算设备的软硬件体系。CUDA变成模型将CPU作为主机，GPU作为协处理器其中运行在GPU上的CUDA并行计算函数被称为kernal(内核)。一个kenerl函数并不是一个完整的程序，而是整个CUDA程序中可以被并行执行的步骤。这样很好的对CPU和GPU进行分工从而实现各种层次的并行。

[0004] 但是，对于本发明所针对的通用可重构处理器却没有一个统一的并行处理规范。典型的可重构处理器架构中包含了一个通用处理器和一个或多个可重构处理单元(Reconfigurable Processing Unit,RPU)，对于多任务应用如何在这种粗粒度可重构处理器上进行任务分配，本发明提出了一套RPU分配和任务调度方法和系统。

发明内容

[0005] 本发明提出一种动态可重构处理器的任务级并行调度方法与系统，通过调节调度方法能够针对不同的任务进行不同的调度方式，基本所有并行任务均能在这种可重构处理器上得到好的并行加速。

[0006] 为了达到上述目的，本发明提出一种动态可重构处理器的任务级并行调度系统，包括主控制器、多个可重构处理单元、主存储器、直接存储访问和系统总线，[0007] 其中，所述每个可重构处理单元由协控制器、多个负责可重构计算的可重构处理单元阵列和多个用于数据存储的共享存储器组成，其中所述可重构处理单元阵列和共享存储器相邻排列，所述共享存储器可被周围相连的两个可重构处理单元阵列所读写。

[0008] 进一步的，所述主控制器用于执行程序中不适合可重构处理单元处理的串行代码，并负责多个可重构处理单元的调度、启动与运行。

[0009] 进一步的，所述可重构处理单元负责计算程序中计算密集的可并行代码。

[0010] 进一步的，所述协控制器用于搬运多个可重构处理单元阵列计算所需的数据与配置信息，控制多个可重构处理单元阵列的启动、运行与终止。

[0011] 为了达到上述目的，本发明还提出一种动态可重构处理器的任务级并行调度方法，包括下列步骤：

[0012] 将应用程序中的计算密集的可并行代码封装为内核函数；

[0013] 将串行部分代码和并行部分代码分别编译生成适合主控制器和可重构处理单元的可执行代码；

[0014] 所述主控制器执行串行部分代码；

[0015] 当执行到内核函数部分代码时，所述主控制器对可重构处理单元进行调度分配处理所述内核函数部分代码。

[0016] 进一步的，所述主控制器对可重构处理单元进行调度分为同步调用和异步调用两种并行方式：

[0017] 若为同步调用，则由主控制器寻找未在运行中的可重构处理单元，并且载入可执行代码和配置信息，与此同时，主控制器挂起，同步调用中，将多个可重构处理单元同时调用，处理不同数据块的内容，在所有的可重构处理单元处理结束之后，通过同步函数返回值来更新处理结果，并且继续主控制器的串行代码执行；

[0018] 若为异步调用，则由主控制器寻找未在运行中的可重构处理单元，与此同时在不中断主控制器的前提下将可执行代码和配置信息载入，启动可重构处理单元，主控制器继续运行至需要可重构处理单元返回数据时，再中止等待可重构处理单元计算完成并返回数据。

[0019] 进一步的，当所述内核函数指令较少，一个可重构处理单元可以单独完成整个内核函数的计算任务时，其内部的多个可重构处理单元阵列并行执行相同的配置信息，每个可重构处理单元阵列负责自己的共享存储器的数据计算。

[0020] 进一步的，当所述内核函数指令较多，不能一次性的执行完内核函数的所有语句时，将内核函数分为多个长度相同的子任务，分别将子任务的配置信息按顺序分配给多个可重构处理单元阵列，由于每个可重构处理单元阵列可以读写相邻的上层共享存储器和下层共享存储器，将每个共享存储器分为等大小的A块和B块，在任务流水过程中，每个可重构处理单元阵列先从上层共享存储器的A块读取数据，并将结果写入下层共享存储器的B块，处理结束之后，每个可重构处理单元阵列再从上层共享存储器的B块读取数据，并将结果写入下层共享存储器的A块，在这两个过程的同时，对首末共享存储器没有参与计算的部分进行数据到主内存的搬运。

[0021] 与现有技术相比，上述技术方案包括以下创新点及有益效果(优点)：

[0022] 1、本发明的任务级并行调度方法是面向特定的三层次的异构粗粒度可重构处理器来进行设计实现的，将应用程序的数据密集和计算密集的部分用内核函数的方法打包出来，主控制器负责串行代码的处理和可重构处理单元的分配，内核函数交由并行计算能力较强的可重构处理单元进行处理，可重构处理单元中在灵活分配其中的可重构阵列来进行计算处理。用这种方式能够充分的发挥多层次异构粗粒度可重构处理器的并行计算能力，再配合特定的编译器能够充分并行加速计算密集型的应用程序。

[0023] 2、本发明在GPU并行运算工具CUDA的基础上，将其并行调度方法移植到了多层次异构粗粒度可重构处理器上，并且提出了新的流水化的调度方式，扩展了对不同种类任务的调度方法。

[0024] 3、本发明实现了多任务多可重构处理单元调度的过程，通过调节调度方法能够针对不同的任务进行不同的调度方式，避免了单一的调度方式对任务的要求，基本所有并行任务均能在这种可重构处理器上得到好的并行加速。

附图说明

[0025] 图1所示为本发明较佳实施例的动态可重构处理器的任务级并行调度系统结构示意图。

[0026] 图2所示为本发明较佳实施例的动态可重构处理器的任务级并行调度方法流程图。

[0027] 图3和图4所示为当所述内核函数指令较少时的同步调度方法示意图。

[0028] 图5所示为当所述内核函数指令较多时的异步调度方法示意图。

具体实施方式

[0029] 以下结合附图给出本发明的具体实施方式，但本发明不限于以下的实施方式。根据下面说明和权利要求书，本发明的优点和特征将更清楚。需说明的是，附图均采用非常简化的形式且均使用非精准的比率，仅用于方便、明晰地辅助说明本发明实施例的目的。

[0030] 请参考图1，图1所示为本发明较佳实施例的动态可重构处理器的任务级并行调度系统结构示意图，其中右侧方框边上RPU1的放大图，以便显示其内部功能结构。本发明提出一种动态可重构处理器的任务级并行调度系统，包括主控制器ARM11、多个可重构处理单元(Reconfigurable Process Unit,RPU)、主存储器DDR、直接存储访问(Direct Memory Access,DMA)和系统总线AHB，其中，所述每个可重构处理单元RPU由协控制器ARM7、多个负责可重构计算的可重构处理单元阵列(Processing Element Array,PEA)和多个用于数据存储的共享存储器(Shared Memory,SM)组成，其中所述可重构处理单元阵列PEA和共享存储器SM相邻排列，所述共享存储器SM可被周围相连的两个可重构处理单元阵列PEA所读写。

[0031] 根据本发明较佳实施例，所述主控制器ARM11用于执行程序中不适合可重构处理单元RPU处理的串行代码，并负责多个可重构处理单元RPU的调度、启动与运行。所述可重构处理单元RPU负责计算程序中计算密集的可并行代码。进一步的，所述协控制器ARM7用于搬运多个可重构处理单元阵列PEA计算所需的数据与配置信息，控制多个可重构处理单元阵列PEA的启动、运行与终止。

[0032] 根据本发明较佳实施例，每个可重构处理单元RPU包括4个可重构处理单元阵列PEA和4个共享存储器SM。

[0033] 在请参考图2，图2所示为本发明较佳实施例的动态可重构处理器的任务级并行调度方法流程图。本发明还提出一种动态可重构处理器的任务级并行调度方法，包括下列步骤：

[0034] 步骤S100：将应用程序中的计算密集的可并行代码封装为内核函数；

[0035] 步骤S200：将串行部分代码和并行部分代码分别编译生成适合主控制器和可重构处理单元的可执行代码；

[0036] 步骤S300：所述主控制器执行串行部分代码；

[0037] 步骤S400：当执行到内核函数部分代码时，所述主控制器对可重构处理单元进行调度分配处理所述内核函数部分代码。

[0038] 对于一般的可重构处理器，并行过程大多仅仅是利用可重构部件的高速运算来处理大量重复性的计算密集型的运算，而对于本发明针对的多层次的比较复杂的异构可重构处理器，它包含了三个层次的计算模块，分别为主控制器、协控制器和PEA，它们三者之间内存独立，共同构成了一个三层次的可重构异构架构。在对应用程序进行处理的过程中，任务级并行的方法不仅仅包括了可重构单元的并行，还包括了多RPU的分配和调度。

[0039] 对于一个应用的C代码程序，我们将其中计算密集的可并行代码封装为kernal(内核)函数，在一个应用中，可以存在多个功能和复杂程度不同的kernal函数。在编译过程中，将串行部分和并行部分分别编译生成适合主控制器部分和可重构处理单元RPU部分的可执行代码。kernal函数存在两个层次的并行，分别为不同RPU之间的同步异步的并行以及RPU内部4个PEA上的代码并行。

[0040] 对于一个多任务的应用程序，在可重构架构上执行时，先由主控制器执行串行部分代码，在执行到kernal部分时，会由主控制器的RPU调度器对RPU进行分配，并且分为同步调用和异步调用两种并行方式：

[0041] 若为同步调用，则由主控制器寻找未在运行中的可重构处理单元，并且载入可执行代码和配置信息，与此同时，主控制器挂起，同步调用中，将多个可重构处理单元同时调用，处理不同数据块的内容，在所有的可重构处理单元处理结束之后，通过同步函数返回值来更新处理结果，并且继续主控制器的串行代码执行；

[0042] 若为异步调用，则由主控制器寻找未在运行中的可重构处理单元，与此同时在不中断主控制器的前提下将可执行代码和配置信息载入，启动可重构处理单元，主控制器继续运行至需要可重构处理单元返回数据时，再中止等待可重构处理单元计算完成并返回数据。同步调用方式可以将数据量大的kernal函数通过多RPU并行计算来处理，而异步调用可以将不同的没有依赖关系的kernal进行并行。

[0043] 在对执行kernal函数的RPU进行分配和调度后，在RPU内部同样的存在任务并行，也就是第二个层次的并行计算。在本发明依赖的硬件架构中，每个RPU中包含了4个PEA和相对应的SM，其中SM可以被周围相连的两个PEA所读写，这样我们就可以针对这种架构完成针对kernal种类的两种方式的并行计算方法。

[0044] 请参考图3和图4，图3和图4所示为当所述内核函数指令较少时的同步调度方法示意图。当所述内核函数指令较少，一个可重构处理单元可以单独完成整个内核函数的计算任务时，其内部的多个可重构处理单元阵列并行执行相同的配置信息，每个可重构处理单元阵列负责自己的共享存储器的数据计算，这样便可以将kernal执行时间缩短到最多四分之一。其中第一排方框block1～4表示协控制器将数据从DDR拷贝到SM的左半部分，圆圈表示PEA执行，第二排方框block1～4表示PEA将计算完的数据输出到SM的右半部分，第三排方框block1～4表示协控制器将数据从SM右半部分输出到DDR中，以上为程序当中的循环体。

[0045] 当所述内核函数指令较多，不能一次性的执行完内核函数的所有语句时，对这种情况，我们需要采取流水的方式进行任务并行，具体方案为将kernal函数分为不多于4个的子任务，每个子任务长度尽量相同，分别将子任务的配置信息按顺序分给4个PEA，由于每个可重构处理单元阵列可以读写相邻的上层共享存储器和下层共享存储器，将每个共享存储器分为等大小的A块和B块，在任务流水过程中，每个可重构处理单元阵列先从上层共享存储器的A块读取数据，并将结果写入下层共享存储器的B块，处理结束之后，每个可重构处理单元阵列再从上层共享存储器的B块读取数据，并将结果写入下层共享存储器的A块，在这两个过程的同时，对首末共享存储器没有参与计算的部分进行数据到主内存的搬运。这样，整个过程中没有额外的数据搬运时间，能够很好的无间断的流水执行kernal函数。

[0046] 请参考图5，图5所示为当所述内核函数指令较多时的异步调度方法示意图。如图5所示，程序员将循环中的所有命令按照一定的方法分为几个部分，在编译器处理GR-C的过程中，会将这些命令分别编译成不同的PEA配置包，由4个PEA顺序调用，在时钟周期上分别延后一个周期在进行运作，达到流水的效果，第一个周期，PEA1将SM1中A部分的数据进行运算，结果放入SM2的B块中，第二个周期PEA1将SM1中B部分的数据进行运算，同时PEA2将SM2的B块数据进行运算，分别放入SM2和SM3的A块中，以此类推形成流水的过程，在PEA4计算完数据后直接将数据copy到主存中，直到所有的数据处理完毕。RPU内部按任务划分完整的执行流程，其中block1～block5表示不同的数据流，最右侧方框表示数据从SM3中输出到DDR中。

[0047] 虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明。本发明所属技术领域中具有通常知识者，在不脱离本发明的精神和范围内，当可作各种的更动与润饰。因此，本发明的保护范围当视权利要求书所界定者为准。