| 摘要: |
| 针对众核处理器系统的核资源优化使用问题,提出了一种支持核资源动态分组的自适应调度算法CASM (core-partitioned adaptive scheduling for many-core systems).该算法通过对任务簇的拆分与合并,动态构建可弹性分区的核逻辑组,实现核资源的隔离优化访问.为了平衡核资源利用率及任务调度效率,CASM 算法针对任务簇间和簇内的不同特点,分别采用公平性较好的均衡调度算法和资源利用率较高的自适应调度算法.在线竞争理论分析表明,CASM 算法的任务执行时间在线竞争比为常数2,其性能可扩展性较好.实验结果表明,与WS(work-stealing),AGDEQ(adaptive greedy dynamic equi-partitioning)和EQUI?EQUI 算法相比,CASM算法使任务集运行时间分别减少了近46%,32%和15%.在相同能耗情况下,CASM 算法大幅度地提升了系统吞吐量. |
| 关键词: 众核处理器 分组调度 自适应调度 竞争分析 高效能计算 |
| DOI：10.3724/SP.J.1001.2012.04141 |
| 分类号: |
| 基金项目:国家自然科学基金(61073011, 61133004, 61173039); 国家高技术研究发展计划(863)(2008AA01A202, 2009AA01A131); 中意国际合作项目(2009DFA12110) |
|
| Adaptive Scheduling Algorithm Based on Dynamic Core-Resource Partitions for Many-Core Processor Systems |
|
CAO Yang-Jie1, QIAN De-Pei1,2, WU Wei-Guo1, DONG Xiao-She1
|
|
1.School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2.School of Computer Science and Engineering, BeiHang University, Beijing 100191, China
|
| Abstract: |
| With the aim to address the increasing difficulty of efficiently using large number of cores in many-core processors, a core-partitioned adaptive scheduling algorithm, named CASM (core-partitioned adaptive scheduling for many-core systems), is proposed. CASM dynamically aggregates cores into different partitions by splitting or merging task-clusters, which ensures the efficiency of isolated accessing in these core partitions. To improve the scheduling efficiency of CASM, equi-partitioning scheduling algorithm is adopted to reallocate the cores among task-clusters, and the feedback-driven adaptive scheduling algorithm is implemented within the task-clusters. Online competitive analysis shows that CASM achieves 2-competitiveness ratio with respect to the execution time of parallel jobs, which indicates that CASM has better performance and scalability. The experimental results demonstrate that compared with WS (work-stealing), AGDEQ (adaptive greedy dynamic equi-partitioning) and EQUI?EQUI, CASM reduces the execution time of the same workload by nearly 46%, 32% and 15% respectively. Under the same power consumption, CASM greatly enhances the system throughput. |
| Key words: many-core processor cluster-based scheduling adaptive scheduling competitive analysis powerefficient computing |
