1.一种分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,包括以下步骤:
(1)获取用户提交的视频流数据处理请求,该视频流数据处理请求包括视频流数据的来源信息、视频流数据的处理函数、视频流数据的分组函数和聚合函数、以及处理函数使用的视频流数据的初始值d,其中d为任意大于0的正整数;
(2)根据步骤(1)获取的视频流数据的函数中数据之间的依赖关系建立处理序列,并根据步骤(1)获取的视频流数据处理请求中视频流数据的函数的类型将该处理序列划分为多个处理阶段,所有的处理阶段构成处理阶段集合S={S1,S2...Sm},其中m表示处理阶段集合中的处理阶段总数;
(3)针对步骤(2)得到的处理阶段集合S中仅包括处理函数的每一个处理阶段而言,利用模拟退火启发式搜索算法获得该处理阶段内每个处理函数小于其最大时延L、最小准确度A并且使用系统资源价值最低的处理函数配置信息,所有的处理函数配置信息构成处理函数配置信息集合Q= 其中处理函数配置信息表示处理函数的配置信息是由处理阶段集合S中第x1个处理阶段Sx1中第x2个处理函数Px2产生,x1∈[1,m],x2∈[1,nx2],nm为处理阶段集合S中第m个处理阶段的处理函数总数,nx2为处理阶段集合S中第x2个处理阶段中处理函数的总数;
(4)针对步骤(2)得到的阶段集合中每个处理阶段中的每个处理函数而言,根据步骤(1)得到的处理函数的最大时延L以及步骤(3)得到的处理函数配置信息确定该处理函数的视频流窗口,将每个处理阶段的所有处理函数的视频流窗口中的最小视频流窗口作为该处理阶段对应的视频流窗口,所有处理阶段的视频流窗口构成集合NS={NS1,NS2,...,NSm};
(5)针对步骤(2)得到的处理阶段集合S中仅包括处理函数的每一个处理阶段而言,根据每个处理阶段内处理函数中数据之间的依赖关系建立该处理阶段对应的有向无环图,所有处理阶段对应的有向无环图构成有向无环图集合H;
(6)对于步骤(5)得到的处理阶段集合S对应的有向无环图集合中的每个有向无环图而言,使用广度优先遍历算法将该有向无环图划分为多个层次,所有层次构成该有向无环图对应的层次集合B={B1,B2,...Bnum4},其中Bcount表示有向无环图中的第count层,num4表示划分的层次总数,且count∈[1,num4];
(7)根据步骤(6)得到的每个有向无环图对应的层次集合B确定与该有向无环图对应的处理阶段的资源分配总量集合和并行通量,并从处理阶段集合S的所有资源分配总量集合和所有并行通量中选择最大资源分配总量集合Umax和最大并行通量kmax;
(8)向集群管理结点申请启动kmax个任务的进程,将最大资源分配总量集合Umax分配给每个进程,并从集群管理结点获取每个进程的网络地址,所有进程的网络地址组成集合(9)使用步骤(3)获取的处理函数配置信息集合Q中每个处理函数对应的可更改参数集合替换步骤(2)得到的处理阶段集合S中处理阶段内对应处理函数对应的可更改参数集合,并将处理阶段集合S中的每个处理阶段对应的视频流窗口设置为步骤(4)获取的对应处理阶段对应的视频流窗口,并将处理阶段集合S中的每个处理阶段封装成单个任务,所有任务构成任务集合E={E1,E2,...,Em},其中Enum5表示第num5个处理阶段封装成的任务,且num5∈[1,m];
(10)针对步骤(9)得到的任务集合中的每一个任务而言,将该任务复制kmax份,并根据步骤(8)得到的网络地址集合中的网络地址将复制后的kmax份任务发送给所有进程,并接收每个进程在执行任务过程中每隔周期T返回的进程执行信息PEt5,其中所有进程执行任务期间返回的任务执行情况构成进程执行信息集合PE={PE1,PE2,...,PEkmax},其中t5∈[1,kmax],T为任意大于零的自然数;
(11)根据步骤(10)获得的进程执行信息集合PE将所需转移剩余处理时间长的进程待处理的视频流数据转移到所需剩余处理时间短的进程。
2.根据权利要求1所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,
视频流数据的来源信息包括视频流数据的存储位置和存储速率r;
视频流数据的处理函数包括该视频流数据的并行通路数k、处理函数的最大时延L和最小准确度A、以及该处理函数对应的可更改参数集合V={G1,G2,...Gh},其中h表示可更改参数的总数。
3.根据权利要求2所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,
可更改参数集合V中的第num个可更改参数Gnum表示为五元组:Gnum={vnnum,vminnum,vmaxnum,vstepnum,voptimalnum}其中num∈[1,h],vnnum表示第num个可更改参数Gnum的变量名,vminnum表示第num个可更改参数Gnum的最小值,vmaxnum表示第num个可更改参数Gnum的最大值,vstepnum表示从vminnum到vmaxnum的步进值,voptimalnum表示能够使该处理函数获得最佳准确度的、第num个可更改参数的参考值,vminnum和vmaxnum为任意自然数,且vminnum<vmaxnum;
处理阶段集合S中第x1个处理阶段Sx1中第x2个处理函数Px2的配置信启、 表示为四元组:
其中 表示处理函数Px2对应的可更改参数集合, 表示将Px2的可更改参数替换为V后得到的处理函数P′x2的准确度, 表示视频流数据量为d时,处理函数P′k的执行时间, 表示处理函数P′x2执行时服务器的系统资源使用量集合。
4.根据权利要求1至3中任意一项所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,步骤(3)具体包括如下子步骤:(3‑1)设置计数器i=1;
(3‑2)判断i是否等于处理阶段集合S中处理阶段的总数m,如果是则过程结束,否则转入步骤(3‑3);
(3‑3)判断处理阶段集合S中处理阶段的第i阶段是否只包含处理函数,如果是转入步骤(3‑4),否则转入步骤(3‑12)(3‑4)设置计数器j=0;
(3‑5)获取处理阶段集合S中第i个处理阶段Si中第j个处理函数Pj对应的可更改参数集合Vj,获取可更改参数集合Vj中所有可更改参数的参考值组成的参考值集合Voptimal={voptimal1,voptimal2...voptimalh},将可更改参数集合Vj更新为参考值Voptimal,并获得此时参考值集合Voptimal对应的处理函数Poptimal,执行该处理函数Poptimal,以获得处理结果集合Toptimal,其中voptimalnum1表示参考值集合Voptimal中的第num1个可更改参数的参考值,且num1∈[1,h];
(3‑6)获取处理阶段集合S中第i个处理阶段Si中第j个处理函数Pj中的可更改参数集合Vj,从中随机选择多个可更改参数组成新的可更改参数集合Vj′={v1,v2,...,vh},其中vnum2表示新的可更改参数集合Vj′中的第num2个可更改参数,vnum∈[vminnum2,vmaxnum2],并且vnum2能被vstepnum2整除,num2∈[1,h];
(3‑7)将可更改参数集合Vj更新为新的可更改参数集合Vj′,并获得此时新的可更改参数集合Vj′对应的处理函数Pj′,执行该处理函数Pj′,以获得处理结果集合Tj′,根据处理结果集合Toptimal和Tj′计算处理函数Pj′的准确度aj′,并保存处理函数Pj′对视频流数据量为d的视频流数据的执行时间lj′;
(3‑8)获取处理函数Pj′执行时服务器的系统资源使用量集合U′j={u1,u2,u3...uf},并根据系统资源使用量U′j计算服务器消耗的系统资源价值rj;其中ux表示第x类系统资源的系统资源使用量,f表示系统资源类型的总数,且有x∈[1,f];
(3‑9)根据处理函数Pj′的准确度aj、执行时间lj以及服务器消耗的系统资源价值rj获取新的可更改参数集合Vj′对应的目标函数F(Vj′)=((aj‑A)*(L‑lj))/rj;
(3‑10)将步骤(3‑6)得到的新的可更改参数集合Vj′作为初始解,利用模拟退火启发式搜索算法搜索使目标函数F(Vj″)最大的可更改参数集合Vj″,并获得此时该可更改参数集合Vj″对应的处理函数Pj″,执行处理函数Pj″,得到处理函数P″j的准确度a″j、执行处理函数P″j的时间l″j、以及处理函数P″j执行时服务器的系统资源使用量集合U″j,将处理函数P″j的准确度a″j、执行时间l″j以及系统资源使用量集合U″j组装成处理阶段集合S中第i个处理阶段Si的第j个处理函数的配置信息四元组 并发送给应用处理结点;
(3‑11)判断计数器j是否小于等于处理阶段集合S中第i个处理阶段Si中处理函数的总数ni,如果是,则设置j=j+1,然后返回步骤(3‑5),否则转入步骤(3‑12);
(3‑12)设置i=i+1,并返回步骤(3‑2)。
5.根据权利要求4所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,
服务器消耗的系统资源价值等于:
其中we表示第e类系统资源对应的价值权重,并且 且e∈[1,f];
对于处理阶段集合S中第x1个处理阶段中的第x2个处理函数Pq而言,其视频流窗口大小为NPq=(L/lq)*d;
其中lq是从步骤(3)获得的第x1个处理阶段的第x2个处理函数信息集合中的 内的执行时间 。
6.根据权利要求5所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,
处理阶段集合S中第x3个处理阶段Sx3构建的有向无环图中第x层Bx的资源分配总量集合为 并行通量为 其中 表示从步骤(3)中获取的第x3个处理阶段的第b个处理函数中的配置信息四元组 中解析的执行时服务器的系统资源使用量集合,kb表示处理阶段集合S中第x3个处理阶段中第b个处理函数的并行通量,其中x3∈[1,m],j1∈[1,mb],jn∈[1,mb],mb为第d个处理阶段中处理函数的总数;
第x3个处理阶段Sx3对应的资源分配总量集合 第x3个处理阶段Sx3对应的并行通量
最大资源分配总量集合为Umax=max(Us1,Us2....Usm),最大并行通量kmax=max(ks1,ks2....ksm)。
7.根据权利要求6所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,第t3个进程的进程执行信息可以表示为三元组PEt3={nodet3,Sprocesst3,Dremaint3},Sprocesst3表示第t3个进程的实际处理速率,Dremaint3第t3个进程待处理的视频流数据量,nodet3表示第t3个进程的网络地址,均为任意自然数,t3∈[1,kmax]。
8.根据权利要求7所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,步骤(11)包括如下子步骤:
(11‑1)根据步骤(10)得到的所有进程执行信息对应进程所需剩余处理时间将步骤(10)得到的进程执行信息集合中的所有进程执行信息进行降序排序;
(11‑2)设置计数器i=1,j=kmax,index=1;
(11‑3)判断是否有i<j,如果是转入步骤(11‑4),否则过程结束;
(11‑4)判断如果将步骤(8)得到的所有进程中进程nodei的视频流数据转移到进程nodej后,对应视频流数据的执行时间的减少量 是否大于阈值DT,即是否有如果是则转入步骤(11‑6),否则转入步骤(11‑7);
(11‑5)根据步骤 (11‑4) 视频流数据转移前后的进程创建三元组并设置index=index+1,通知进程nodej从nodei中获取视频流数据量为 的视频流数据进行处理;
(11‑6)设置i=i+1,j=j‑1,并返回步骤(11‑3);
(11‑7)设置j=j‑1,并返回步骤(11‑3)。
9.根据权利要求7所述的分布式计算平台下基于QoS约束的视频流处理方法,其特征在于,
进程所需剩余处理时间等于该进程待处理的视频流数据量乘以进程的实际处理速率,即TRemaint3=(Sprocesst3*Dremaint3);
视频流数据的执行时间的减少量
其中 表示转移视频流数据量为 的视频流数据到进程nodej中所需的时间,且
其中 表示进程nodej处理完成之后,进程nodei剩余待处理的视频流数据量,且有:。
10.一种分布式计算平台下基于QoS约束的视频流处理系统,其特征在于,包括:第一模块,用于获取用户提交的视频流数据处理请求,该视频流数据处理请求包括视频流数据的来源信息、视频流数据的处理函数、视频流数据的分组函数和聚合函数、以及处理函数使用的视频流数据量的初始值d,其中d为任意大于0的正整数;
第二模块,用于根据第一模块获取的视频流数据的函数中数据之间的依赖关系建立处理序列,并根据第一模块获取的视频流数据处理请求中视频流数据的函数的类型将该处理序列划分为多个处理阶段,所有的处理阶段构成处理阶段集合S={S1,S2...Sm},其中m表示处理阶段集合中的处理阶段总数;
第三模块,用于针对第二模块得到的处理阶段集合S中仅包括处理函数的每一个处理阶段而言,利用模拟退火启发式搜索算法获得该处理阶段内每个处理函数小于其最大时延L、最小准确度A并且使用系统资源价值最低的处理函数配置信息,所有的处理函数配置信息构成处理函数配置信息集合 其中处理函数配置信息 表示处理函数的配置信息是由处理阶段集合S中第x1个处理阶段Sx1中第x2个处理函数Px2产生,x1∈[1,m],x2∈[1,nx2],nm为处理阶段集合S中第m个处理阶段的处理函数总数,nx2为处理阶段集合S中第x2个处理阶段中处理函数的总数;
第四模块,用于针对第二模块得到的阶段集合中每个处理阶段中的每个处理函数而言,根据第一模块得到的处理函数的最大时延L以及第三模块得到的处理函数配置信息确定该处理函数的视频流窗口,将每个处理阶段的所有处理函数的视频流窗口中的最小视频流窗口作为该处理阶段对应的视频流窗口,所有处理阶段的视频流窗口构成集合NS={NS1,NS2,...,NSm};
第五模块,用于针对第二模块得到的处理阶段集合S中仅包括处理函数的每一个处理阶段而言,根据每个处理阶段内处理函数中数据之间的依赖关系建立该处理阶段对应的有向无环图,所有处理阶段对应的有向无环图构成有向无环图集合H;
第六模块,用于对于第五模块得到的处理阶段集合S对应的有向无环图集合中的每个有向无环图而言,使用广度优先遍历算法将该有向无环图划分为多个层次,所有层次构成该有向无环图对应的层次集合B={B1,B2,...Bnum4},其中Bcount表示有向无环图中的第count层,num4表示划分的层次总数,且count∈[1,num4];
第七模块,用于根据第六模块得到的每个有向无环图对应的层次集合B确定与该有向无环图对应的处理阶段的资源分配总量集合和并行通量,并从处理阶段集合S的所有资源分配总量集合和所有并行通量中选择最大资源分配总量集合Umax和最大并行通量kmax;
第八模块,用于向集群管理结点申请启动kmax个任务的进程,将最大资源分配总量集合Umax分配给每个进程,并从集群管理结点获取每个进程的网络地址,所有进程的网络地址组成集合
第九模块,用于使用第三模块获取的处理函数配置信息集合Q中每个处理函数对应的可更改参数集合替换第二模块得到的处理阶段集合S中处理阶段内对应处理函数对应的可更改参数集合,并将处理阶段集合S中的每个处理阶段对应的视频流窗口设置为第四模块获取的对应处理阶段对应的视频流窗口,并将处理阶段集合S中的每个处理阶段封装成单个任务,所有任务构成任务集合E={E1,E2,...,Em},其中Enum5表示第num5个处理阶段封装成的任务,且num5∈[1,m];
第十模块,用于针对第九模块得到的任务集合中的每一个任务而言,将该任务复制kmax份,并根据第八模块得到的网络地址集合中的网络地址将复制后的kmax份任务发送给所有进程,并接收每个进程在执行任务过程中每隔周期T返回的进程执行信息PEt5,其中所有进程执行任务期间返回的任务执行情况构成进程执行信息集合PE={PE1,PE2,...,PEkmax},其中t5∈[1,kmax],T为任意大于零的自然数;
第十一模块,用于根据第十模块获得的进程执行信息集合PE将所需转移剩余处理时间长的进程待处理的视频流数据转移到所需剩余处理时间短的进程。