一种基于任务窃取的任务调度方法及系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107220111A(43)申请公布日2017.09.29(21)申请号201710290460.6(22)申请日2017.04.28(71)申请人华中科技大学地址430074湖北省武汉市洪山区珞喻路1037号(72)发明人金海李陈希廖小飞石翔(74)专利代理机构华中科技大学专利中心42201代理人李智曹葆青(51)Int.Cl.G06F9/48(2006.01)G06F9/50(2006.01)权利要求书2页说明书7页附图3页(54)发明名称一种基于任务窃取的任务调度方法及系统(57)摘要本发明公开了一种基于任务窃取的任务调度方法及系统，该方法的实现包括：构造任务依赖图，将依赖节点作为回调函数注册至被依赖节点的回调容器中；为线程池中各线程分配一个无锁双端队列并置空，将根节点按照轮询方式放入各线程的无锁双端队列底部；若线程的无锁双端队列不为空，则从无锁双端队列底部取出节点并执行；若线程的无锁双端队列为空，则从其他线程的无锁双端队列顶部窃取节点，并将窃取的节点压入该线程的无锁双端队列底部，取出窃取的节点进行执行；在所有节点任务执行完成后，将任务依赖图中各节点的入度恢复到原始值，并结束对主线程的阻塞。本发明针对大型任务级并行应用程序，可以有效提高传统任务级并行应用程序的性能。CN107220111ACN107220111A权利要求书1/2页1.一种基于任务窃取的任务调度方法，其特征在于，包括：(1)将整体计算任务描述为由子任务节点与子任务节点间依赖边组成的任务依赖图，将依赖节点作为回调函数注册至被依赖节点的回调容器中；(2)获取所述任务依赖图中的根节点与叶子节点，为所有叶子节点添加一个虚拟依赖汇节点，所述虚拟依赖汇节点用于阻塞主线程；(3)为线程池中各线程分配一个无锁双端队列并置空，将所有根节点按照轮询方式放入各线程的无锁双端队列底部；(4)对于每个线程，若线程的无锁双端队列不为空，则从线程的无锁双端队列底部取出节点并执行节点中包含的任务，在任务执行结束后，执行节点中回调容器中的所有回调；若线程的无锁双端队列为空，则该线程尝试从其他线程的无锁双端队列顶部窃取节点，若窃取成功则将窃取的节点压入该线程的无锁双端队列底部，执行窃取节点中的任务以及窃取节点中回调容器中的所有回调；(5)在任务依赖图中所有节点中的任务均执行完成后，将任务依赖图中的各节点的入度恢复到原始值，并结束对主线程的阻塞。2.根据权利要求1所述的方法，其特征在于，步骤(1)具体包括以下步骤：(1.1)定义任务依赖图对象；(1.2)依据计算任务的属性将该计算任务划分成若干子任务，调用任务依赖图对象所提供的插入方法将各子任务添加进任务依赖图中并将各子任务封装为节点对象，返回各节点对象的指针；(1.3)通过各节点对象的指针构造各子任务间的依赖关系，将依赖节点视作回调函数注册至被依赖节点的回调容器中，将依赖节点的入度加1，将被依赖节点的出度加1。3.根据权利要求2所述的方法，其特征在于，步骤(2)具体包括以下步骤：(2.1)将任务依赖图中所有入度为0的节点加入根节点集合，将所有出度为0的节点加入叶子节点集合；(2.2)对于叶子节点集合L＝{L1，L2，…}，添加虚拟依赖汇节点virtual_sink_node，并调用virtual_sink_node->depends(L1,L2,…)，所述虚拟依赖汇节点用于阻塞主线程直到所有任务完成，防止主线程提前结束。4.根据权利要求2所述的方法，其特征在于，步骤(4)具体包括以下步骤：(4.1)对于每个线程，若线程的无锁双端队列不为空，则从线程的无锁双端队列底部取出节点并执行节点中包含的任务，在任务执行结束后，执行节点中回调容器中的所有回调，每执行一次回调，相对应的注册回调的节点的入度减1，若某一注册回调的节点的入度被减至0，则当前线程将该注册回调的节点压入当前线程的无锁双端队列底部；(4.2)若线程的无锁双端队列为空，则该线程尝试从其他线程的无锁双端队列顶部窃取节点，若窃取成功则将窃取的节点压入该线程无锁双端队列底部，并执行步骤(4.1)，否则放弃本轮CPU时间片；(4.3)重复执行步骤(4.1)～(4.2)直至任务依赖图中所有节点中的任务均执行完成。5.根据权利要求1至4任意一项所述的方法，其特征在于，所述线程池中的线程数目与CPU硬件核心的数目一致。6.一种基于任务窃取的任务调度系统，其特征在于，包括：2CN107220111A权利要求书2/2页任务依赖图构造模块，用于将整体计算任务描述为由子任务节点与子任务节点间依赖边组成的任务依赖图，将依赖节点作为回调函数注册至被依赖节点的回调容器中；预处理模块，用于获取所述任务依赖图中的根节点与叶子节点，为所有叶子节