一种针对嵌入式多核系统的视频编码流水化并行方法

摘要

本发明提出了一种针对嵌入式多核系统的视频编码程序流水化并行方法，该方法基于视频编码原程序对基本数据单元处理的数据流图表示，对目标视频编码原程序进行模拟仿真，提取数据流图中各个节点运算量，分析数据流图中各个节点的依赖关系及流水化并行后处理基本数据单元时的数据依赖关系，根据得到的节点运算量及节点间依赖关系选择处理器负载均衡、核间通信量少的流水并行划分方案。得到划分方案后对任务节点按照指示器的接口标准进行对象化封装，将封装后的对象静态地映射到相应的处理器核上，配合各个处理器核上的指示器实现多核系统对视频编码原程序的流水化并行执行。本发明适用于各种数据流处理类型的程序的并行化。

说明书

技术领域

本发明涉及媒体应用程序的并行化编程，特别针对嵌入式多核系统提出了一种视频编码程序流水化并行方法。

背景技术

多处理器系统芯片(MPSoC：Multi-Processor System-on-Chip)在计算性能、功耗、芯片面积、以及实时性等方面的优势使得它在当今嵌入式领域应用越来越广泛。但是，如何方便地为MPSoC开发高效的并行程序，对应用程序开发者和系统设计者都是挑战。

媒体视频应用程序是嵌入式领域中应用较多且运算量较大的一类程序。媒体程序是一种典型的数据流处理程序，即依次对顺序输入的源数据进行若干处理阶段生成结果后输出。对媒体视频应用程序的并行化有两种策略：(1)数据性并行划分；即将处理过程中没有依赖关系的源数据分配到不同的处理器上进行处理，达到多核并行执行的目的。(2)任务性并行划分；即将基本单元宏块的处理过程分为若干阶段，每个处理器只负责特定阶段，且处理完当前宏块的被分配的处理阶段后，就把结果送至下一处理器使其开始计算，通过几个处理器的协同及流水化地处理宏块达到并行加速目的。

对于视频编码器来说，现存的一些任务性并行划分方法存在的限制主要包括：(1)没有一个理论上的确定任务流水并行划分方案的依据。(2)在任务流水划分方案的分析中没有明确提出处理不同源数据时的数据依赖关系对任务流水线的影响。(3)没有一个简单高效的任务同步及调度机制。本发明提出任务性并行化方法能避免上述限制，可以通过改变任务流水级的划分来均衡处理器负载，提高资源利用效率。

发明内容

本发明提供了一种针对嵌入式多核平台的视频编码器任务性流水化并行方法。该方法主要包括两方面的内容：(1)原始程序的并行化划分；(2)划分后的任务/线程的处理器映射及并行调度执行。

程序并行化划分的目标包括：提升并行化程序的加速比；挖掘串行程序的并行性，调度任务使得处理器等待开销最小，优化并行系统的资源利用率。

本发明提出的针对嵌入式多核平台的视频编码器任务性流水化并行方法具体包括以下步骤：

(1)针对目标视频编码原程序，根据要进行流水并行的基本数据单元级别得到程序的一种粗颗粒度数据流图表示；

根据原程序的流程选取的基本数据单元级别，对于视频编程序，可以选取宏块作为基本的数据处理单元。

(2)对目标视频编码原程序进行模拟仿真，提取数据流图中各个节点运算量；

在目标视频编码原程序并行划分之前，选择目标视频序列进行动态仿真，记录步骤(1)得到的数据流图中各个节点的运算量，作为确定并行划分方案的依据。

(3)分析数据流图中各个节点的依赖关系及流水化并行后处理基本数据单元时的数据依赖关系；

通过动态仿真确定数据流图中各个节点之间的数据依赖关系，统计因这些数据依赖关系导致的节点间所需的数据通信量大小，作为流水并行方案中额外数据通信开销的依据。

(4)根据核间任务的并行性及核间数据通信开销，得到流水并行划分方案，若该方案满足并行系统要求，进入步骤(5)，否则对原始数据流图中的节点进行分裂或合并，回到步骤(2)；

将步骤(2)和步骤(3)得到的数据流图中节点运算量统计和节点间数据通信量的统计标注到步骤(1)得到的数据流图中，得到原程序的一种同步数据流图表示。根据同步数据流图及目标多核平台的处理器数量选择并行划分方案。并行划分方案的选择包括以下两个指导原则：(1)各个流水级的运算量尽量相等，减少因处理器负载不均衡导致的并行效率下降；(2)根据数据流图中节点的数据依赖关系，将数据通信量大的节点分配到同一处理器上，减少因核间数据通信产生的开销；最终，以总的并行加速比和系统资源利用率最高为准则选取划分方案。

(5)根据步骤(4)得到的划分方案对任务节点按照指示器的接口标准进行对象化封装，封装后的对象静态地映射到相应的处理器核上，配合各个处理器核上的指示器实现多核系统对视频编码原程序的流水化并行执行；

每个封装后的对象(Object)包括行为函数和若干输入输出端口，每个输入输出端口对应一个输入输出缓冲区。每个端口都有一个相应的标志位表示端口的状态，所有的标志组成信号量条目(SemaEntry)，指示器通过对信号量条目的查询和更新来管理对象。当对象的所有输入输出端口都就绪时，指示器调度对象执行行为函数，行为函数从输入缓冲区取得数据进行处理后产生结果送到输出缓冲区。不同处理器间的数据通信由指示器完成。

本发明提出一种面向媒体应用的流水化并行方法，以视频编码器为实例来进行多核系统的程序并行化定量分析，具体的实施方法对于数据流处理类型的程序具有通用性。

附图说明

图1是本发明实施例的流程示意图；

图2是本发明实施例的粗颗粒度数据流示意图；

图3是本发明实施例的当前宏块与相邻宏块的关系示意图；

图4是本发明实施例的MPEG-4简单档次编码器编码流程示意图；

图5是本发明实施例的MPEG-4编码P型宏块数据流图；

图6是本发明实施例的多核系统平台结构示意图；

图7是本发明实施例的三核并行划分和映射方案示意图；

图8是本发明实施例的五核并行划分和映射方案示意图；

图9是本发明实施例的三核并行方案的流水线示意图；

图10是本发明实施例的五核并行方案的流水线示意图。

具体实施方式

下面结合附图，通过对MPEG-4简单档次编码器的任务性流水化并行划分实例来说明本发明一种面向媒体应用的多处理器流水化并行方法的实施方式。

本发明提出的针对嵌入式多核系统提出了一种视频编码程序流水化并行方法的流程如图1所示。

基于数据流图进行串行程序的并行性分析，如图2所示。典型的数据流图由若干节点及表示这些节点连接关系的有向弧组成，图中节点只要所有的输入都满足后成为就绪态，就可以被执行，执行后产生的结果作为后续节点的输入。节点可以是一段程序块或者一次函数调用，只要有足够的处理器数目和处于就绪态的节点，这些节点就可以同时被调度执行，因此数据流模型从本质上来讲能够用来开发程序的并行性。数据流图中的有向弧表示节点之间的数据依赖关系，存在数据依赖关系的节点不能同时执行，而数据依赖关系又可以分为两类：(1)处理同一个源数据时的数据依赖，本发明称之为前向依赖(FD：ForwardDependence)，图2中弧上的黑点即表示这种依赖关系。(2)处理不同源数据时的数据依赖，本发明称之为后向依赖(BD：Backward Dependence)，图2中M即表示这种依赖关系。

一般并行性开发考虑的是前向依赖产生的限制，如图2中节点F_B和F_C间没有前向依赖从而可以并行执行。但节点F_A和F_B在对同一源数据处理的时候有数据生产-消费依赖dAB而不能并行执行。若F_A和F_B对不同的源数据处理时不存在数据依赖，可以排成流水并行处理。在F_A处理当前输入数据的时候，F_B同时处理前一个时刻F_A处理完的输入数据，这样就可消除对同一源数据处理的前向依赖，从而实现了任务流水化并行。

任务流水化并行方案的确定应该尽量降低后向依赖引起的同步等待开销，提升系统性能。如图2中所示，若节点F_B与F_D处于不同的流水级，由于后向依赖M的存在，F_B在F_D处理完当前源数据之前不能进行下一个源数据的处理，导致流水线的停顿等待，降低了系统性能。

为了提高并行系统的资源利用效率，需要统计程序的数据流图表示中的各节点模块的运算量，分析节点间前向依赖和后向依赖关系，考察数据通信开销等因素，以探索一种使得多个处理器的负载均衡、流水线停顿等待开销最小的程序划分和任务映射方案。

并行化方案的确定过程中，任务节点颗粒度大小的选择至关重要。任务颗粒度小则在任务映射时更方便地实现处理器的负载均衡化，同时能更灵活地适应不同数量处理器核的情况，但是相应的通信开销、划分复杂度、以及程序代码量都会增加，因为每个任务都要进行对象化封装，对象内部需要额外的数据通信管理模块。

MPEG-4简单档次编码流程如图4所示。在MPEG-4编码程序中，原始图像的基本数据单元宏块(MB：MacroBlock)按照从上到下、从左到右的扫描顺序输入，经过若干任务处理后产生压缩码流。在对其并行化过程中，为了能够合理安排任务流水，不仅要考虑编码单个宏块时各个任务之间的数据依赖关系，还要考虑相邻宏块间的数据依赖关系即后向数据依赖关系。

如图4所示，I帧和P帧的编码流程不同，I帧宏块不用进行P帧宏块中的运动搜索部分。因此针对P帧的划分方案，在处理I帧数据时流水级会有较大的不均衡性。但是由于一般而言的编码模式为IPPP…IPPP…，每两个I帧之间间隔十几甚至几十个P帧，且两个I帧之间P帧越多这种不平衡造成的影响就越小，因此主要考虑P帧的均衡性进行流水级并行化。

通过对典型视频序列(foreman，news，mobile，bus)的模拟仿真，统计得到MPEG-4编码器编码P帧宏块时各主要模块的运算量比例如表1所示。

表1.MPEG-4编码P帧宏块时各主要模块运算量占总运算量比例

为了得到尽可能高的压缩率，MPEG-4编码器使用了各种预测技术，从而加重了宏块间的数据依赖性。无论是帧内编码帧(I frame)还是帧间编码帧(Pframe)，当前宏块与宏块A、宏块B、以及宏块C都存在数据依赖，如图3所示。I帧中当前宏块数据的预测值由宏块A、宏块B、以及及宏块C计算得到；P帧的最后编码的运动矢量残差(MVD：Motion Vector Difference)也是当前运动矢量与预测矢量相减计算得到；而预测矢量由宏块A、宏块C、以及宏块D计算得到，I帧和P帧的环路滤波都需要左边和上边宏块的值。熵编码的顺序要求严格按照宏块扫描顺序进行，即当前宏块熵编码未完成之前不能进行下一个宏块的熵编码。保证在处理当前宏块时上一行的宏块都已处理完毕，这样后向数据依赖存在于当前宏块与左边宏块间。但是这种有后向依赖的节点之间生产者所处的流水级阶段在消费者所处的流水级阶段之前，如图4中，系数预测模块处理当前宏块数据时需要上一个宏块编码完成之后的结果，而宏块编码模块在系数预测模块之前，执行当前宏块系数预测时上一个宏块的编码操作已经完成，因此不会对任务流水线产生停顿影响。

如表1所示，运算量比例不均衡。运动估计模块占去了大部分的运算时间。为了均衡处理器负载，必须重新分裂或合并节点，并根据具体硬件平台的资源确定划分策略。运动估计模块可分为整像素运动估计和半像素运动估计，其中运算量较大的半像素运动估计模块又可分为一次16×16块搜索和四次8×8块搜索。MPEG-4编码P帧宏块的数据流图如图5所示。图5中节点边上的数字表示该节点执行的指令条数，节点间数据通信量大小如表2所示。

表2.节点间数据通信量

本发明利用异构多核片上系统，包括1个精简指令集计算机(RISC：ReducedInstruction Set Computer)处理器和8个数字信号处理器(DSPs：DigitalSignal Processors)组成的多核RED平台进行三核和五核的并行方案实验，RED平台结构如图6所示。三核和五核的任务划分及映射方案如图7和图8所示。

图7中的映射方案为三级流水，其中数字信号处理器#1上的两个对象实际上处于不同的流水级，但是流水化执行一段时间后，可以把它们处理不同源数据的情况看成同一流水阶段。图8中的映射方案为五核四级流水，其中数字信号处理器#2和数字信号处理器#3上的对象彼此没有数据依赖而并行，它们处于同一流水级。相应的流水线状态分别如图9和图10所示。

上述两种方案提到的这些可并行模块占程序总运算量的比例约为96.3％，两种并行方案中这些模块理论上的加速比分别为2.92和4.28，根据阿姆达尔(Amdahl)定律，整个程序的理论加速比分别为2.72和3.82。

最后，还需要注意的是，以上列举的仅是本发明的具体实施例子。显然，本发明不限于以上实施例子，还可以有许多变形。本领域的普通技术人员能从本发明公开的内容直接导出或联想到的所有变形，均应认为是本发明的保护范围。