ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (4): 750-763.doi: 10.7544/issn1000-1239.2017.20160138

• 系统结构 • 上一篇    下一篇

基于数据流块的空间指令调度方法

刘炳涛1,2,3,王达1,叶笑春1,范东睿1,2,张志敏1,唐志敏1   

  1. 1(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190); 2(中国科学院大学计算机与控制学院 北京 100049); 3(杭州电子科技大学信息与控制研究所 310018) (liubingtao@ict.ac.cn)
  • 出版日期: 2017-04-01
  • 基金资助: 
    国家重点研发计划项目(2016YFB0200501);国家自然科学基金项目(61332009,61521092,61671196,61327902);数学工程与先进计算国家重点实验室开放基金项目(2016A04);北京市科委科技计划专项项目(Z15010101009)

The Data-Flow Block Based Spatial Instruction Scheduling Method

Liu Bingtao1,2,3, Wang Da1, Ye Xiaochun1, Fan Dongrui1,2, Zhang Zhimin1, Tang Zhimin1   

  1. 1(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190); 2(School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049); 3(Institute of Information and Control, Hangzhou Dianzi University, Hangzhou 310018)
  • Online: 2017-04-01

摘要: 分簇超标量处理器将硬件资源分区来避免大的单体部件导致的功耗与周期惩罚,动态多核处理器融合多个物理核的硬件资源提供适应程序需求的计算能力,这些结构合理使用空间分布的硬件资源实现高能效的计算.空间分区结构中指令负载不均衡和跨区操作数传递延迟等问题可导致性能惩罚,需要有效的指令调度方法将计算在分区间进行分布.提出了基于数据流块(data-flow block, DFB)的空间指令调度方法.DFB是动态构建、缓存并重用的一个或数个顺序执行的指令基本块的调度模式.DFB调度算法建模动态指令流中的数据流约束和硬件资源定义的调度空间,然后根据指令量化的相对关键性完成调度决策.介绍了DFB调度的微结构框架和算法.通过对分区数、分区间延迟和调度窗口容量等与调度方法密切相关的微结构参数的实验,证明了DFB调度的性能和稳定性优于负载均衡调度和基于依赖的调度.最后举例证明结合一种数据流块缓存实现的DFB调度达到的调度效果接近理想化的DFB调度.

关键词: 处理器微结构, 负载均衡, 指令调度, 数据流, 关键路径

Abstract: Clustered superscalar processors partition hardware resources to circumvent the energy and cycle time penalties incurred by large, monolithic structures. Dynamic multi-core processors fuse hardware resources of several physical cores to provide the computation capability adapting to applications. Energy-efficient computation is achieved in these architectures with a carefully orchestrated utilization of spatially distributed hardware resources. Problems such as instruction load imbalance and operand forwarding latency between partitions may cause performance penalties, so an effective spatial instruction scheduling method is needed to distribute the computation among the partitions of spatial architectures. We present the data-flow block(DFB) based spatial instruction scheduling method. DFBs are dynamically constructed, cached and reused schedule patterns for one or more sequentially executed instruction basic blocks. DFB scheduling algorithm models the data-flow constraints of dynamic instruction stream and the scheduling space defined by hardware resources, then makes the scheduling decision according to the relative criticality, which is the quantitative scheduling slack of instructions. We present the framework and algorithm related to DFB scheduling. Through experimenting with various microarchitecture parameters closely related to scheduling method such as partition count, inter-partition latency and schedule window capacity, we prove that ideal DFB scheduling performs better and stabler than round-robin and dependence-based scheduling. At last, we show that the scheduling performance with a DFB cache implementation example closes to ideal DFB scheduling.

Key words: processor microarchitecture, load balancing, instruction scheduling, data-flow, critical path

中图分类号: