计算机科学 ›› 2020, Vol. 47 ›› Issue (8): 41-48.doi: 10.11896/jsjkx.191000148

所属专题: 高性能计算

• 高性能计算 • 上一篇    下一篇

负载均衡的处理器运算资源分配方法

王国澎, 杨剑新, 尹飞, 蒋生健   

  1. 上海高性能集成电路设计中心 上海 201204
  • 出版日期:2020-08-15 发布日期:2020-08-10
  • 通讯作者: 王国澎(wgp.sun@163.com)
  • 基金资助:
    “核高基”重大专项课题(2018ZX01029101)

Computing Resources Allocation with Load Balance in Modern Processor

WANG Guo-peng, YANG Jian-xin, YIN Fei, JIANG Sheng-jian   

  1. Shanghai High Performance IC Design Center, Shanghai 201204, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:WANG Guo-peng, born in 1988, MSc, engineer.His main research interests include computer architecture, microprocessor design.
  • Supported by:
    This work was supported by the Natonal Science and Technology Major Project(2018ZX01029101).

摘要: 现代超标量处理器通常设置有多套计算部件支持指令并行执行, 以提高程序的运行效率。运算资源分配策略在很大程度上决定了处理器能否充分利用计算部件并行加速计算, 具有重要作用。就指令调度以及运算资源分配问题而言, 当前的研究以软件编译优化方法居多。但编译优化是一种静态方法, 优化排布的指令无法再次改变次序, 且缺乏运行时信息, 灵活性不够。为了降低因运算资源分配不当导致的指令阻塞, 充分释放其运算能力, 从硬件自动调度和实现的角度分析了这个问题, 研究了对称情形和非对称情形下运算资源的细粒度自动分配方法, 进而提出了负载均衡的贪心分配策略。实验结果表明, 提出的运算资源分配方法可以有效减弱现代超标量处理器中指令发射不公平所带来的负面影响, 能更好地利用片上缓冲资源和计算资源, 且处理器中运算资源越多, 发射缓冲深度越大, 负载均衡方法获得的性能提升就越明显。

关键词: 负载均衡, 流水线, 指令调度, 指令发射, 资源分配

Abstract: To improve the efficiency of program, it is used to arrange multiple function units in modern superscalar processor, supporting to execute instructions in parallel.The allocation policy of computing resources plays an important role in taking full advantage of multiple function units.Although the policy of how to allocate computing resources and schedule instruction has been well studied in literature, the proposed solutions almost concentrate on optimization methods at compile time, which is mostlystatic, inflexible and inefficient because of lack of computing pipeline information at run time.To mitigate the negative impacts of improper computing resource allocation and maximize the power of multiple function units, this paper abstracts the mathematical model of resource allocation problem at run time and makes a study of hardware fine-grained automatic method based on symmetric and asymmetric configuration of function units, in order to make dynamic and wise computing resource allocating decision when instructions are issued in general situation.As a result, a load-balanced greedy resource allocation strategy is proposed and evaluated.The experimental results show that our policy is efficient to minimize blocking time caused by unfair allocation of computing resources.Furthermore, the more computing resources are provided, the better performance our policy can yield.

Key words: Instruction issue, Instruction scheduling, Load balance, Pipeline, Resource allocation

中图分类号: 

  • TP302
[1] DAI J, DAI G L, ZHANG S Q, et al.Integration of instruction scheduling and register allocation[J].Journal of Tsinghua University(Sci &Tech), 2004, 44(1):69-73.
[2] LIAN R Q, WU C Y, ZHANG Z Q.Integrating code optimization and instruction scheduling[J].Chinese Journal of Computer, 2001, 24(7):694-701.
[3] QU Q W, LIANG L P.Instruction parallel scheduling and im-plementation based on LLVM[J].Microelectronics & Computer, 2013(11):60-63.
[4] LAM M.Software pipelining:an effective scheduling technique for VLIW machines[J].Acm Sigplan Notices, 1988, 23(7):318-328.
[5] STOTZER E J, LEISS E L.Modulo scheduling without over-lapped lifetimes[C]∥ACM Sigplan/sigbed Conference on Languages, Compilers, and TOOLS for Embedded Systems.ACM, 2009:1-10.
[6] LLOSA J.Swing Modulo Scheduling:A Lifetime-Sensitive Approach[C]∥Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, 1996.IEEE, 1996:80-86.
[7] TAN M X, LIU X H, ZHANG J Y, et al.Non-overlapped modulo scheduling with optimized backtracking model[J].Acta Electronica Sinica, 2012, 40(8):1681-1686.
[8] UPTON M, HUFF T, MUDGE T, et al.Resource allocation in a high clock rate microprocessor[C]∥International Conference on Architectural Support for Programming Languages and Operating Systems.ACM, 1994:98-109.
[9] BUYUKTOSUNOGLU A, KARKHANIS T, ALBONESI D H, et al.Energy efficient co-adaptive instruction fetch and issue[C]∥International Symposium on Computer Architecture, 2003.IEEE, 2003:147-156.
[10]VILLAVIEJA C, JOAO J, MIFTAKHUTDINOV R, et al.AHybrid Dynamic VLIW/OoO Processor:Technical Report:TR-HPS-2014-001[R].2014.
[11]PERELMAN E, HAMERLY G, VAN BIESBROUCK M, et al.Using SimPoint for accurate and efficient simulation[J].ACM SIGMETRICS Performance Evaluation Review, 2003, 31(1):318.
[1] 于滨, 李学华, 潘春雨, 李娜.
基于深度强化学习的边云协同资源分配算法
Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning
计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219
[2] 唐枫, 冯翔, 虞慧群.
基于自适应知识迁移与资源分配的多任务协同优化算法
Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation
计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184
[3] 李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳.
基于深度确定性策略梯度的服务器可靠性任务卸载策略
Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient
计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040
[4] 田真真, 蒋维, 郑炳旭, 孟利民.
基于服务器集群的负载均衡优化调度算法
Load Balancing Optimization Scheduling Algorithm Based on Server Cluster
计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[5] 周天清, 岳亚莉.
超密集物联网络中多任务多步计算卸载算法研究
Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks
计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147
[6] 邱旭, 卞浩卜, 吴铭骁, 朱晓荣.
基于5G毫米波通信的高速公路车联网任务卸载算法研究
Study on Task Offloading Algorithm for Internet of Vehicles on Highway Based on 5G MillimeterWave Communication
计算机科学, 2022, 49(6): 25-31. https://doi.org/10.11896/jsjkx.211100198
[7] 胥昊, 曹桂均, 闫璐, 李科, 王振宏.
面向铁路集装箱的高可靠低时延无线资源分配算法
Wireless Resource Allocation Algorithm with High Reliability and Low Delay for Railway Container
计算机科学, 2022, 49(6): 39-43. https://doi.org/10.11896/jsjkx.211200143
[8] 傅思清, 黎铁军, 张建民.
面向粒子输运程序加速的体系结构设计
Architecture Design for Particle Transport Code Acceleration
计算机科学, 2022, 49(6): 81-88. https://doi.org/10.11896/jsjkx.210600179
[9] 高捷, 刘沙, 黄则强, 郑天宇, 刘鑫, 漆锋滨.
基于国产众核处理器的深度神经网络算子加速库优化
Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor
计算机科学, 2022, 49(5): 355-362. https://doi.org/10.11896/jsjkx.210500226
[10] 沈家芳, 钱丽萍, 杨超.
面向集能型中继窄带物联网的非正交多址接入和多维网络资源优化
Non-orthogonal Multiple Access and Multi-dimension Resource Optimization in EH Relay NB-IoT Networks
计算机科学, 2022, 49(5): 279-286. https://doi.org/10.11896/jsjkx.210400239
[11] 谭双杰, 林宝军, 刘迎春, 赵帅.
基于机器学习的分布式星载RTs系统负载调度算法
Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning
计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[12] 潘燕娜, 冯翔, 虞慧群.
基于自适应资源分配池的竞争合作群协同优化算法
Competitive-Cooperative Coevolution for Large Scale Optimization with Computation Resource Allocation Pool
计算机科学, 2022, 49(2): 182-190. https://doi.org/10.11896/jsjkx.201200012
[13] 夏中, 向敏, 黄春梅.
基于CHBL的P2P视频监控网络分层管理机制
Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL
计算机科学, 2021, 48(9): 278-285. https://doi.org/10.11896/jsjkx.201200056
[14] 宋海宁, 焦健, 刘永.
高速公路中的移动边缘计算研究
Research on Mobile Edge Computing in Expressway
计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212
[15] 王政, 姜春茂.
一种基于三支决策的云任务调度优化算法
Cloud Task Scheduling Algorithm Based on Three-way Decisions
计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!