• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 7
    • 下载费用:30 金币  

    重庆时时彩开奖官方: 基于多核DSP的自适应任务调度方法.pdf

    关 键 词:
    基于 多核 DSP 自适应 任务 调度 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410185521.9

    申请日:

    2014.05.04

    公开号:

    CN103942109A

    公开日:

    2014.07.23

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 专利权的转移IPC(主分类):G06F 9/50登记生效日:20180213变更事项:专利权人变更前权利人:江苏物联网研究发展中心变更后权利人:中科微至智能制造科技江苏有限公司变更事项:地址变更前权利人:214135 江苏省无锡市新区菱湖大道200号中国传感网国际创新园C座变更后权利人:214105 江苏省无锡市锡山区大成路299号|||授权|||实质审查的生效IPC(主分类):G06F 9/50申请日:20140504|||公开
    IPC分类号: G06F9/50; G06F9/38 主分类号: G06F9/50
    申请人: 江苏物联网研究发展中心
    发明人: 王丰; 李功燕
    地址: 214135 江苏省无锡市新区菱湖大道200号中国传感网国际创新园C座
    优先权:
    专利代理机构: 无锡市大为专利商标事务所(普通合伙) 32104 代理人: 曹祖良;韩凤
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410185521.9

    授权公告号:

    |||||||||

    法律状态公告日:

    2018.03.09|||2017.02.15|||2014.08.20|||2014.07.23

    法律状态类型:

    专利申请权、专利权的转移|||授权|||实质审查的生效|||公开

    摘要

    本发明涉及一种基于多核DSP的自适应任务调度方法,首先需要在多核DSP系统内建立公共的任务池,所有参与运算的核通过算法调度,从公共的任务池中取走相应的任务分别进行计算。将任务分为:均等任务,递增任务,递减任务和无规则随机任务。自适应调度过程分三个步骤实现:1.先将整个任务的前一部分平均分配给多个处理器核进行处理,计算每个核所负责的任务的平均处理时间,推测任务类型。2.依据推测出任务的类型,选取对应的调度策略,直到任务池中的任务都被取走。3.先完成任务的核将找到当前剩余任务最多的核的任务池中,分担工作量。此方法能够根据不同任务的特点进行自适应调度,尽可能使得任务均衡地分配给多个处理器核,提高整体的计算性能。

    权利要求书

    权利要求书
    1.  基于多核DSP的自适应任务调度方法,其特征是:在多核DSP系统内建立一个公共的任务池,所有参与运算的处理器核通过算法调度从公共任务池中取走相应的任务分别进行计算,同时每个处理器核中都有一个共享的任务池,存放当前需要执行的任务;将任务分为4种类型:
    (1)均等任务,每个任务的计算量基本相同;
    (2)递增任务,每个任务的计算量随着任务的进行而递增;
    (3)递减任务,每个任务的计算量随着任务的进行而减少;
    (4)无规则随机任务,每个任务的计算量无明显规律;
    整个自适应调度过程分三个步骤实现:
    a.先将整个任务的前一部分平均分配给多个处理器核进行处理,这个过程中由任务计数器与计时器对任务的运行状况进行跟踪监测;当其中有一个处理器核完成分配到的任务之后,则开始对当前所有处理器核中的结果进行分析:计算每个处理器核所负责的任务的平均处理时间n为参与任务运算的处理器核的个数,再根据计算出来的平均时间,推测任务的类型;
    b.对接下来还未开始计算的任务,依据推测出任务的类型,选取对应的调度策略进行相应的动态分配,直到公共任务池中的任务都被取走为止:对均等任务类型,每个处理器核分配相同的数量的任务;对递增任务类型,为每个处理器核分配的任务数量满足递减的趋势;对递减任务类型,为每个处理器核分配的任务数量满足递增的趋势;对随机任务类型,为每个处理器核分配均等大小的小块的任务;
    c.先完成任务的处理器核将找到当前剩余任务最多处理器核的任务池中,进行任务窃取,帮助未完成任务的处理器核分担工作量,以实现平衡;如此反复直到最终所有任务都被完成为止。

    2.  如权利要求1所述基于多核DSP的自适应任务调度方法,其特征是,步骤a中先将整个任务的前50%平均分配给多个处理器核进行处理。

    3.  如权利要求1所述基于多核DSP的自适应任务调度方法,其特征是,步骤c所述任务窃取将剩余任务最多处理器核的任务池中的1/3任务取走进行处理。

    4.  如权利要求1所述基于多核DSP的自适应任务调度方法,其特征是,步骤b中,对均等任务类型,每个处理器核分配到的任务数均为对递增任务类型,对递减任务类型,对随机任务类型,其中,k=Σi=2nT‾iT‾i-1(n-1);]]>s:总的任务数量,l:剩余未被执行的任务数量,r:调度的次数,w(r,i):第r轮调度,第i个处理器核当前分配到的任务数量。

    说明书

    说明书基于多核DSP的自适应任务调度方法
    技术领域
    本发明涉及一种多核DSP中的任务调度方法,属于信息技术领域。
    背景技术
    自动并行化研究始于20世纪70年代,历经自动向量化、循环级自动并行化、过程级自动并行化等几个阶段,每个阶段的发展都体现了人们对程序并行特性理解的不断深入。通过对向量化编程规律的发现,人们提出了依赖关系分析理论,从而完成了串行程序的自动向量化。随着自动向量化技术的成功应用,研究人员把注意力转向共享内存体系结构的自动化并行化,并取得了一定的成功。但是,如何把数据分发到多个处理器上去以充分发掘程序的并行性、减少通信成本,是一个较为复杂的问题。
    在多核DSP的任务并行中,最困难的问题之一是在保持所有节点或处理器负载均衡的同时最小化通信和同步的开销。在共享内存体系中,所有处理机对主存拥有相同的访问延迟和贷款,不存在因处理器访问不同位置的数据带来的通信开销。任务调度对于负载均衡和额外开销具有非常重要的影响。其调度策略直接影响着系统资源的利用率和并行效率。
    任务调度的研究包括平衡负载、同步开销和通信开销。在很多共享内存多处理器系统中,一个单独的准备队列是处理调度常用机制。负载平衡是该单独准备队列处理机制的焦点,且单个准备队列容易造成竞争和同步开销,成为性能瓶颈。为并行任务选择合适的调度策略能够获得很大的性能收益。
    常见的负载均衡调度有两种方法——静态调度与动态调度。
    静态调度是在编译时,将任务平均分配到各个线程上。而动态调度是在运行时动态地将任务分配给空闲线程,但是,这将会花费一定的调度开销。
    现有的大多数任务调度算法,都需要在编码的过程中就确认任务的调度策略,一旦确定不能修改,这将直接导致任务调度的策略死板,不灵活。并且在讨论任务调度方法时,许多方法都是默认为所有任务的计算量都是相同的进行调度,鲜有对任务的计算量不同时的情况进行探讨,对任务计算量不同时的解决方案也只是简单地采取通过某些算法将任务递减地分配给处理器。
    发明内容
    为了克服现有调度方法的不足,本发明提供了一种自适应的任务调度方法,采用良好的调度策略对并行任务进行合理的划分,在调度开销以及负载均衡方面获得更好的权衡,以提高多核的并行计算性能。
    为了实现这个目的,本方法在多核DSP系统内建立一个公共的任务池,所有参与运算的处理器核通过算法调度从公共任务池中取走相应的任务分别 进行计算,同时每个处理器核中都有一个共享的任务池,存放当前需要执行的任务;将任务分为4种类型:
    (1)均等任务,每个任务的计算量基本相同;
    (2)递增任务,每个任务的计算量随着任务的进行而递增;
    (3)递减任务,每个任务的计算量随着任务的进行而减少;
    (4)无规则随机任务,每个任务的计算量无明显规律;
    整个自适应调度过程分三个步骤实现:
    a.先将整个任务的前一部分(如任务的前50%)平均分配给多个处理器核进行处理,这个过程中由任务计数器与计时器对任务的运行状况进行跟踪监测;当其中有一个处理器核完成分配到的任务之后,则开始对当前所有处理器核中的结果进行分析:计算每个处理器核所负责的任务的平均处理时间n为参与任务运算的处理器核的个数,再根据计算出来的平均时间,推测任务的类型;
    b.对接下来还未开始计算的任务,依据推测出任务的类型,选取对应的调度策略进行相应的动态分配,直到公共任务池中的任务都被取走为止:对均等任务类型,每个处理器核分配相同的数量的任务;对递增任务类型,为每个处理器核分配的任务数量满足递减的趋势;对递减任务类型,为每个处理器核分配的任务数量满足递增的趋势;对随机任务类型,为每个处理器核分配均等大小的小块的任务;
    c.先完成任务的处理器核将找到当前剩余任务最多处理器核的任务池中,进行任务窃取(比如取走1/3任务),帮助未完成任务的处理器核分担工作量,以实现平衡;如此反复直到最终所有任务都被完成为止。
    具体的,步骤b中,对均等任务类型,每个处理器核分配到的任务数均为对递增任务类型,对递减任务类型,对随机任务类型,其中,s:总的任务数量,l:剩余未被执行的任务数量,r:调度的次数,w(r,i):第r轮调度,第i个处理器当前分配到的任务数量。
    本发明的优点是:此方法能够根据不同任务的特点进行自适应调度,尽可能使得任务均衡地分配给多个处理器,提高整体的计算性能。
    附图说明
    图1是自适应任务调度方法流程图。
    具体实施方式
    本发明需要在多核DSP系统内建立一个公共的任务池,将任务放入公共的任务池中,所有参与运算的核通过算法调度,从公共的任务池中取走相应 的任务分别进行计算,同时每个核中都有一个共享的任务池,存放当前需要执行的任务。
    首先,在本发明中将任务分为5种类型:
    (1)均等任务,每个任务的计算量基本相同;
    (2)递增任务,每个任务的计算量随着任务的进行而递增;
    (3)递减任务,每个任务的计算量随着任务的进行而减少;
    (4)无规则随机任务,每个任务的计算量无明显规律。
    如图1所示,整个自适应调度过程分三个步骤实现:
    1.试探
    先将整个任务的前一部分平均分配给多个处理器核进行处理,这个过程中有任务计数器与计时器对任务的运行状况进行跟踪监测。
    当其中有一个处理器核完成分配到的任务之后,则开始对当前所有处理器核中的结果进行分析——计算每个核所负责的任务的平均处理时间,再根据计算出来的平均时间,推测任务的类型。
    2.应用策略
    对接下来还未开始计算的任务,依据推测出任务的类型,选取对应的调度策略,进行相应的动态分配;直到任务池中的任务都被取走为止。
    3.收尾
    先完成任务的处理器核将找到当前剩余任务最多处理器核的任务池中,进行任务窃取,帮助未完成任务的核分担工作量,尽可能实现平衡。
    如此反复直到最终所有任务都被完成为止。
    以下结合实施例对本发明做进一步说明。
    主要的符号说明如下:
    n:参与任务运算的处理器核的个数,
    s:总的任务数量,
    l:剩余未被执行的任务数量,
    r:调度的次数,
    w(r,i):第r轮调度,第i个处理器核当前分配到的任务数量。
    为了在调度开销以及负载均衡方面获得更好的权衡,需要采用良好的调度策略对并行任务进行合理的划分,以提高多核的运行性能。
    整个自适应调度过程分三个步骤实现:
    1.试探。
    先将整个任务的前50%平均分配给多个处理器核进行处理,这个过程中有任务计数器与计时器对任务的运行状况进行跟踪监测。计时器计算每个处理器核中每个任务的平均处理时间。即在这个阶段中每个处理器核分配到的任务数量皆为:

    表示向上取整。当其中有一个处理器核完成分配到的任务之后,则开始对 当前所有处理器核中的结果,根据任务计数器与计时器进行分析,将每个处理器核的已执行任务数除以当前的运行时间,可以得到每个处理器核所负责任务的平均时间
    (1)如果平均时间几乎相同,则推测当前任务是均等任务类型;
    (2)如果平均时间呈递增趋势,则推测当前任务是递增任务类型,计算出趋势因子k;
    k=Σi=2nT‾iT‾i-1(n-1);]]>
    (3)如果平均时间呈递减趋势,则推测当前任务是递减任务类型,计算出趋势因子k;
    k=Σi=2nT‾iT‾i-1(n-1);]]>
    (4)否则,推测当前任务为无规则随机任务类型。
    2.对整个任务剩下的50%部分应用相应的调度策略。
    (1)均等任务类型。
    每个处理器核分配相同的数量的任务,每个处理器核分配到的任务数均为
    (2)递增任务类型。
    为每个处理器核分配的任务数量满足递减的趋势。

    (3)递减任务类型。
    为每个处理器核分配的任务数量满足递增的趋势。

    (4)随机任务类型。
    为每个处理器核分配均等大小的小块的任务。

    3.先完成任务的处理器核将找到当前剩余任务最多处理器核的任务池中,进行任务窃取——将其任务池中的1/3任务取走进行处理,尽可能实现平衡。按照这个步骤一直进行,直到所有任务都被完成为止。

    关于本文
    本文标题:基于多核DSP的自适应任务调度方法.pdf
    链接地址://www.4mum.com.cn/p-6143346.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 极速赛车冠军3码计划 幸运飞艇固定345678 设胆是什么意思 福彩3d组六6码多少钱 吉利分分彩计划软件 海南七星彩包头尾 时时彩热号变冷前奏 免费时时彩龙虎计划 排列三稳赚的投注技巧 七星彩开奖号码结果 双色球走势图综合版 双色球开奖查询结果 上海时时票开奖结果查询 pk10杀号技巧大全 pk10免费手机版苹果 北京时时软件怎么样