Discrete controller synthesis based resource management method of heterogeneous multi-core processor system

doi:10.11772/j.issn.1001-9081.2019101865

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (6): 1698-1706.DOI: 10.11772/j.issn.1001-9081.2019101865

• Advanced computing • Previous Articles Next Articles

Discrete controller synthesis based resource management method of heterogeneous multi-core processor system

AN Xin^1,2, XIA Jinwei^1,2, YANG Haijiao^1,2, OUYANG Yiming¹, REN Fuji^1,2

1. School of Computer Science and Information Engineering, Hefei University of Technology, Hefei Anhui 230601, China
2. Anhui Province Key Laboratory of Affective Computing and Advanced Intelligent Machine (Hefei University of Technology), Hefei Anhui 230601, China

Received:2019-11-01 Revised:2019-12-17 Online:2020-06-10 Published:2020-06-18
Contact: AN Xin, born in 1987, Ph. D., associate professor. His research interests include embedded system design and validation, machine learning.
About author:XIA Jinwei, born in 1994, M. S. candidate. His research interests include embedded system design and validation.AN Xin, born in 1987, Ph. D., associate professor. His research interests include embedded system design and validation, machine learning.YANG Haijiao, born in 1995, M. S. candidate. Her research interests include embedded system and system-on-chip, machine learning.OUYANG Yiming, born in 1963, Ph. D., professor. His research interests include embedded system synthesis and testing, digital system design automation.REN Fuji, born in 1959, Ph. D., professor. His research interests include signal and information processing, affective computing, computer vision, pattern recognition.
Supported by:
Youth Program of National Natural Science Foundation of China (61502140), the Joint Fund of National Natural Science Foundation of China (U1613217), the Fundamental Research Funds for the Central Universities (JZ2020YYPY0092).

基于离散控制器合成的异构多核系统资源管理方法

安鑫^1,2, 夏近伟^1,2, 杨海娇^1,2, 欧阳一鸣¹, 任福继^1,2

1.合肥工业大学计算机与信息学院，合肥 230601
2.情感计算与先进智能机器安徽省重点实验室(合肥工业大学)，合肥 230601

通讯作者: 安鑫(1987—)
作者简介:安鑫（1987—），男，山东潍坊人，副教授，博士，CCF 会员，主要研究方向：嵌入式系统设计和验证、机器学习.夏近伟（1994—），男，安徽合肥人，硕士研究生，主要研究方向：嵌入式系统设计和验证.杨海娇（1995—），女，安徽六安人，硕士研究生，主要研究方向：嵌入式系统与片上系统、机器学习.欧阳一鸣（1963—），男，安徽合肥人，教授，博士，CCF会员，主要研究方向：嵌入式系统综合与测试、数字系统设计自动化.任福继（1959—），男，四川南充人，教授，博士，主要研究方向：信号与信息处理、情感计算、计算机视觉、模式识别。
基金资助:
国家自然科学基金青年基金资助项目(61502140)；国家自然科学基金联合基金资助项目（U1613217）；中央高校基本科研业务费专项资金资助项目(JZ2020YYPY0092)。

Abstract

Abstract: Nowadays, with the development of semiconductor technology and the requirement of the diversification of applications, heterogeneous multi-core processors have been widely used in high-performance embedded systems. How to manage and distribute the available resources (such as processing cores) during running in order to meet the requirements in performance and power consumption of the system and the applications that the system runs is a main challenge that the system focuses. However, although some mainstream resource management techniques have achieved good results in terms of performance and/or power consumption optimization, they lack the strict reliability guarantee for the resource management component. Therefore, a method based on Discrete Controller Synthesis (DCS) was proposed to automatically and reliably design the online resource management scheme for heterogeneous multi-core systems, which applies DCS (which is formal and can construct management control components automatically) to the design of online resource management components for heterogeneous multi-core systems. In this method, the heterogeneous system’s running behaviors (such as how to distribute the processing cores to the applications) were described by using the formal models, and the online resource management problem was transformed to a DCS problem aiming at one system management objective (such as maximizing system performance). On this basis, the existing DCS tools were used to illustrate and validate the proposed method, and the scalability of the DCS method was evaluated.

Key words: heterogeneous multi-core processor, resource management, formal method, Discrete Controller Synthesis (DCS), model-checking

摘要： 近年来，随着半导体技术的发展以及应用多样化的需求，异构多核处理器已被广泛应用于高性能嵌入式系统中。这类系统面临的一个主要挑战就是如何在运行时对系统的可用资源（包括处理核等）进行管理分配从而满足系统及其所运行应用在性能和功耗等方面的需求。然而，虽然目前一些主流的资源管理技术在性能和/或功耗优化等方面取得了良好表现，但却经常对所设计的资源管理部件缺乏严格的可靠性保证，因此提出了一种基于离散控制器合成（DCS）的方法来对异构多核系统的在线资源管理策略进行自动、可靠的设计，即将形式化的、能够自动构造管理控制部件的DCS应用到异构多核系统的在线资源管理部件设计中。该方法通过采用形式化模型来描述异构系统的运行行为（例如如何为应用分配处理核），并将在线资源管理问题转换为一个面向某个系统管理目标（例如最大化应用性能）的DCS问题。在此基础上，通过现有的DCS工具对提出的方法进行了示例演示和验证，并对所使用DCS方法的可扩展性进行了评估。

关键词: 异构多核处理器, 资源管理, 形式化方法, 离散控制器合成, 模型检测

CLC Number:

TP302.1

AN Xin, XIA Jinwei, YANG Haijiao, OUYANG Yiming, REN Fuji. Discrete controller synthesis based resource management method of heterogeneous multi-core processor system[J]. Journal of Computer Applications, 2020, 40(6): 1698-1706.

安鑫, 夏近伟, 杨海娇, 欧阳一鸣, 任福继. 基于离散控制器合成的异构多核系统资源管理方法[J]. 计算机应用, 2020, 40(6): 1698-1706.

References

1 BALSINIA, PANNOCCHIL, CUCINOTTAT. Modeling and simulation of power consumption and execution times for real-time tasks on embedded heterogeneous architectures [J] ACM SIGBED Review, 2019, 16(3): 51-56.
2 GREENHALGHP. BIG.LITTLE processing with ARM CortexTM-A15 & Cortex-A7 [EB/OL]. [2019-01-10].https://www.cl.cam.ac.uk/~rdm34/big.LITTLE.pdf.
3 PRAKASHA, AMROUCHH, SHAFIQUEM, et al. Improving mobile gaming performance through cooperative CPU-GPU thermal management [C]// Proceedings of the 53rd Annual Design Automation Conference. New York: ACM, 2016: 47.
4 DONYANAVARDB, MüCKT, SARMAS, et al. Sparta: runtime task allocation for energy efficient heterogeneous many-cores [C]// Proceedings of the 2016 International Conference on Hardware/Software Codesign and System Synthesis. Piscataway: IEEE, 2016: 1-10.
5 CHOIS, YEUNGD. Learning-based SMT processor resource distribution via hill-climbing [C]// Proceedings of the 33rd International Symposium on Computer Architecture. Piscataway: IEEE, 2006: 239-251.
6 COCHRANR, HANKENDIC, COSKUNA K, et al. Pack & Cap: adaptive DVFS and thread packing under power caps [C]// Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway: IEEE, 2011: 175-185.
7 RAGHAVENDRAR, RANGANATHANP, TALWARV, et al. No “power” struggles: coordinated multi-level power management for the data center [J]. ACM SIGOPS Operating Systems Review, 2008, 42(2): 48-59.
8 TEMBEYP, GAVRILOVSKAA, SCHWANK. A case for coordinated resource management in heterogeneous multicore platforms [C]// Proceedings of the 2010 International Symposium on Computer Architecture, LNCS 6161. Berlin: Springer, 2010: 341-356.
9 VEGAA, BUYUKTOSUNOGLUA, HANSONH, et al. Crank it up or dial it down: coordinated multiprocessor frequency and folding control [C]// Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway: IEEE, 2013: 210-221.
10 KESHANCHIB, SOURIA, NAVIMIPOURN J. An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing [J]. Journal of Systems and Software, 2017, 124: 1-21.
11 CAIH, WUH. An improved formalization analysis approach to determine schedulability of global multiprocessor scheduling based on symbolic safety analysis and statistical model checking in smartphone systems [J]. Cluster Computing, 2019, 22(2): 2543-2554.
12 REZAM F, ZHAOD, WUH. Task-resource co-allocation for hotspot minimization in heterogeneous many-core NoCs [C]// Proceedings of the 26th ACM International on Great Lakes Symposium on VLSI. New York: ACM, 2016: 137-140.
13 NEMIROVSKYD, ARKOSET, MARKOVICN, et al. A machine learning approach for performance prediction and scheduling on heterogeneous CPUs [C]// Proceedings of the 29th International Symposium on Computer Architecture and High Performance Computing. Piscataway: IEEE, 2017: 121-128.
14 ZHANGY, LAURENZANOM A, MARSJ, et al. SMiTe: precise QoS prediction on real-system SMT processors to improve utilization in warehouse scale computers [C]// Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway: IEEE, 2014: 406-418.
15 MICHALSKAM, CASALE-BRUNETS, BEZATIE, et al. High-precision performance estimation for the design space exploration of dynamic dataflow programs [J]. IEEE Transactions on Multi-Scale Computing Systems, 2018, 4(2): 127-140.
16 GUPTAU, CAMPBELLJ, OGRASU Y, et al. Adaptive performance prediction for integrated GPUs [C]// Proceedings of the 35th International Conference on Computer-Aided Design. New York: ACM, 2016: Article No.61.
17 SAYADIH, PATELN, SASANA, et al. Machine learning-based approaches for energy-efficiency prediction and scheduling in composite cores architectures [C]// Proceedings of the 2017 IEEE International Conference on Computer Design. Piscataway: IEEE, 2017: 129-136.
18 WANGL, LIUS, LUC, et al. Stable matching scheduler for single-ISA heterogeneous multi-core processors [C]// Proceedings of the 2015 International Workshop on Advanced Parallel Processing Technologies, LNCS 9231. Cham: Springer, 2015: 45-59.
19 BITIRGENR, IPEKE, MARTINEZJ F. Coordinated management of multiple interacting resources in chip multiprocessors: a machine learning approach [C]// Proceedings of the 41st IEEE/ACM International Symposium on Microarchitecture. Piscataway: IEEE, 2008: 318-329.
20 DUBACHC, JONEST M, BONILLAE V, et al. A predictive model for dynamic microarchitectural adaptivity control [C]// Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway: IEEE, 2010: 485-496.
21 ROTEME. Intel architecture, code name Skylake deep dive: a new architecture to manage power performance and energy efficiency [EB/OL] [2019-09-01]. https://en.wikichip.org/w/images/8/83/Intel_Architecture%2C_Code_Name_Skylake_Deep_Dive-_A_ New_Architecture_to_Manage_Power_Performance_and_Energy_ Efficiency.pdf.
22 BARTOLINIA, CACCIARIM, TILLIA, et al. A distributed and self-calibrating model-predictive controller for energy and thermal management of high-performance multicores [C]// Proceedings of the 2011 Design, Automation and Test in Europe Conference. Piscataway: IEEE, 2011: 1-6.
23 FUX, KABIRK, WANGX. Cache-aware utilization control for energy efficiency in multi-core real-time systems [C]// Proceedings of the 23rd Euromicro Conference on Real-Time Systems. Piscataway: IEEE, 2011: 102-111.
24 MAK, LIX, CHENM, et al. Scalable power control for many-core architectures running multi-threaded applications[C]// Proceedings of the 38th Annual International Symposium on Computer Architecture. New York: ACM, 2011: 449-460.
25 POTHUKUCHIR P, ANSARIA, VOULGARISP, et al. Using multiple input, multiple output formal control to maximize resource efficiency in architectures [C]// Proceedings of the ACM/IEEE 43rd Annual International Symposium on Computer Architecture. Piscataway: IEEE, 2016: 658-670.
26 RAHMANIA M, DONYANAVARDB, MüCKT, et al. SPECTR: formal supervisory control and coordination for many-core systems resource management [J]. ACM SIGPLAN Notices, 2018, 53(2): 169-183.
27 ANX, RUTTENE, DIGUETJ P, et al. Model-based design of correct controllers for dynamically reconfigurable architectures [J]. ACM Transactions on Embedded Computing Systems, 2016, 15(3): Article No.51.
28 ALTISENK, CLODICA, MARANINCHIF, et al. Using controller-synthesis techniques to build property-enforcing layers [C]// Proceedings of the 2003 European Symposium on Programming, LNCS 2618. Berlin: Springer, 2003: 174-188.
29 DUMITRESCUE, GIRAULTA, MARCHANDH, et al. Multicriteria optimal discrete controller synthesis for fault-tolerant tasks [C]// Proceedings of the 10th International Workshop on Discrete Event Systems. Berlin: Springer, 2010: 356-363.
30 RAMADGEP J G, WONHAMW M. The control of discrete event systems [J]. Proceedings of the IEEE, 1989, 77(1): 81-98.
31 DELAVALG, MARCHANDH, RUTTENE. Contracts for modular discrete controller synthesis [J]. ACM SIGPLAN Notices, 2010, 45(4): 57-66.
32 GAMATIéA, YUH, DELAVALG, et al. A case study on controller synthesis for data-intensive embedded systems [C]// Proceedings of the 2009 International Conference on Embedded Software and Systems. Piscataway: IEEE, 2009: 75-82.
33 MARCHANDH, SAMAANM. Incremental design of a power transformer station controller using a controller synthesis methodology [J]. IEEE Transactions on Software Engineering, 2000, 26(8): 729-741.
34 REDDYB K, SINGHA K, BISWASD, et al. Inter-cluster thread-to-core mapping and DVFS on heterogeneous multi-cores[J]. IEEE Transactions on Multi-Scale Computing Systems, 2018, 4(3): 369-382.
35 BENVENISTEA, CASPIP, EDWARDSS A, et al. The synchronous languages 12 years later [J]. Proceedings of the IEEE, 2003, 91(1):64-83.

[1]	WU Peng, WU Jinzhao. Reasoning method based on linear error assertion [J]. Journal of Computer Applications, 2021, 41(8): 2199-2204.
[2]	QIN Nan, MA Liang, HUANG Rui. Software safety requirement analysis and verification method based on system theoretic process analysis [J]. Journal of Computer Applications, 2020, 40(11): 3261-3266.
[3]	AN Xin, ZHANG Ying, KANG An, CHEN Tian, LI Jianhua. Machine learning based online mapping approach for heterogeneous multi-core processor system [J]. Journal of Computer Applications, 2019, 39(6): 1753-1759.
[4]	HAN Deshuai, XING Jianchun, YANG Qiliang, LI Juelong. Modeling and verification approach for temporal properties of self-adaptive software dynamic processes [J]. Journal of Computer Applications, 2018, 38(3): 799-805.
[5]	LU Jintian, YAO Lili, HE Xudong, MENG Bo. Improvement of OpenID Connect protocol and its security analysis [J]. Journal of Computer Applications, 2017, 37(5): 1347-1352.
[6]	GAO Xianming, WANG Baosheng, LI Tongbiao, XUE Huawei. Design and implementation of resource management plane in virtual router platform [J]. Journal of Computer Applications, 2017, 37(1): 1-5.
[7]	LU Haoyang, CHEN Shiping. Resource allocation framework based on cloud computing package cluster mapping [J]. Journal of Computer Applications, 2016, 36(10): 2704-2709.
[8]	MO Liping ZHOU Kaiqing. Formal description of dynamic construction method for square Hmong language characters [J]. Journal of Computer Applications, 2014, 34(3): 861-864.
[9]	YU Lizhen XU Zhongwei CHEN Zuxi ZHANG Shuqin. Formal verification of railway interlocking system based on ladder logic [J]. Journal of Computer Applications, 2013, 33(12): 3419-3422.
[10]	TIAN Bao-hua JIANG Ju-ping LI Bao-feng ZHANG Xiao-ming QU Wan-xia. Power saving scheme for supercomputing system based on unified resource management [J]. Journal of Computer Applications, 2012, 32(03): 835-838.
[11]	LI Jin ZHANG Hua WU Hao-xiong XIANG Jun. Formal description and analysis of conformance of composite Web service behavior [J]. Journal of Computer Applications, 2012, 32(02): 545-550.
[12]	. New grid resource management framework for mixed types of workloads [J]. Journal of Computer Applications, 2010, 30(8): 2197-2201.
[13]	. Game theory-based cooperative resource management for wireless broadband network [J]. Journal of Computer Applications, 2010, 30(3): 745-750.
[14]	. Epistemic Cord logic: verifying anonymous routing protocols in Ad Hoc network [J]. Journal of Computer Applications, 2009, 29(09): 2432-2434.
[15]	Jun LU . Multiple ant colony algorithm load balancing for network sessions [J]. Journal of Computer Applications, 2008, 28(3): 572-574.

Discrete controller synthesis based resource management method of heterogeneous multi-core processor system

基于离散控制器合成的异构多核系统资源管理方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics