It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system.A novel dynamic measurement method(DMM)was proposed to measure the task scheduling alg...It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system.A novel dynamic measurement method(DMM)was proposed to measure the task scheduling algorithm’s correctness and dependability.In a multi-processor system,task scheduling problem is represented by a combinatorial evaluation model,interactive Markov chain(IMC),and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic(aCSL).DMM derives a path by logging runtime scheduling actions and corresponding times.Through judging whether the derived path can be received by task scheduling IMC model,DMM analyses the correctness of algorithm.Through judging whether the actual values satisfy label function of the initial state,DMM analyses the dependability of algorithm.The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.展开更多
Thanks to the emerging 3D integration technology, The multiprocessor system on chips （MPSoCs） can now integrate more IP cores on chip with improved energy efficiency. However, several severe challenges also rise up ...Thanks to the emerging 3D integration technology, The multiprocessor system on chips （MPSoCs） can now integrate more IP cores on chip with improved energy efficiency. However, several severe challenges also rise up for 3D ICs due to the die-stacking architecture. Among them, power supply noise becomes a big concern. In the paper, we investigate power supply noise （PSN） interactions among different cores and tiers and show that PSN variations largely depend on task assignments. On the other hand, high integration density incurs a severe thermal issue on 3D ICs. In the paper, we propose a novel task scheduling framework considering both the PSN and the thermal issue. It mainly consists of three parts. First, we extract current stimuli of running tasks by analyzing their power traces derived from architecture level simulations. Second, we develop an efficient power delivery network （PDN） solver to evaluate PSN magnitudes efficiently. Third, we propose a heuristic algorithm to solve the formulated task scheduling problem. Compared with the state-of-the-art task assignment algorithm, the proposed method can reduce PSN by 12% on a 2 × 2 × 2 3D MPSoCs and by 14% on a 3 × 3 × 3 3D MPSoCs. The end-to-end task execution time also improves as much as 5.5% and 7.8% respectively due to the suppressed PSN.展开更多
Efficient program execution on massively parallel clusters is critical for fields like scientific computing and artificial intelligence.However,traditional task scheduling algorithms do not fully leverage platform cha...Efficient program execution on massively parallel clusters is critical for fields like scientific computing and artificial intelligence.However,traditional task scheduling algorithms do not fully leverage platform characteristics,resulting in inefficiency and long task execution times.We propose KANETAS,a reinforcement learning-based DAG(Directed Acyclic Graph)elastic task scheduling algorithm,designed to adapt to DAG tasks of various scales and structures.Kolmogorov-Arnold Network(KAN)was applied to the DAG scheduling problem.It enhances the efficiency of heterogeneous hardware by using Graph Convolutional Networks(GCN)and Actor-Critic Algorithm(A2C),recognizing hardware features and assigning tasks to appropriate computing units.We have conducted extensive experiments to evaluate the proposed solution with four strong baseline algorithms,including the state-of-the-art heuristics method and a variety of deep reinforcement learning based algorithms.The experimental results suggest that KANETAS can reduce the average makespan of the best baseline algorithm by 13.1%at most.Furthermore,compared to the MLP version,the KAN version showed superior performance.The proposed model demonstrates a clear advantage in load balancing.展开更多
基金the National Natural Science Foundation of China(Nos.11371003 and 11461006)the Special Fund for Scientific and Technological Bases and Talents of Guangxi(No.2016AD05050)+3 种基金the Special Fund for Bagui Scholars of Guangxithe Major Tendering Project of the National Social Science Foundation(No.17ZDA160)the Sichuan Science and Technology Project(No.19YYJC0038)the Fundamental Research Funds for the Central Universities,SWUN(No.2019NYB20)
文摘It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system.A novel dynamic measurement method(DMM)was proposed to measure the task scheduling algorithm’s correctness and dependability.In a multi-processor system,task scheduling problem is represented by a combinatorial evaluation model,interactive Markov chain(IMC),and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic(aCSL).DMM derives a path by logging runtime scheduling actions and corresponding times.Through judging whether the derived path can be received by task scheduling IMC model,DMM analyses the correctness of algorithm.Through judging whether the actual values satisfy label function of the initial state,DMM analyses the dependability of algorithm.The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.
基金This work was supported by the National Natural Science Foundation of China under Grant Nos. 61401008 and 61602022, and the State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, under Grant No. CARCH201602.
文摘Thanks to the emerging 3D integration technology, The multiprocessor system on chips （MPSoCs） can now integrate more IP cores on chip with improved energy efficiency. However, several severe challenges also rise up for 3D ICs due to the die-stacking architecture. Among them, power supply noise becomes a big concern. In the paper, we investigate power supply noise （PSN） interactions among different cores and tiers and show that PSN variations largely depend on task assignments. On the other hand, high integration density incurs a severe thermal issue on 3D ICs. In the paper, we propose a novel task scheduling framework considering both the PSN and the thermal issue. It mainly consists of three parts. First, we extract current stimuli of running tasks by analyzing their power traces derived from architecture level simulations. Second, we develop an efficient power delivery network （PDN） solver to evaluate PSN magnitudes efficiently. Third, we propose a heuristic algorithm to solve the formulated task scheduling problem. Compared with the state-of-the-art task assignment algorithm, the proposed method can reduce PSN by 12% on a 2 × 2 × 2 3D MPSoCs and by 14% on a 3 × 3 × 3 3D MPSoCs. The end-to-end task execution time also improves as much as 5.5% and 7.8% respectively due to the suppressed PSN.
基金Funding National Key Research and Development Program of China,2023YFB3001504.
文摘Efficient program execution on massively parallel clusters is critical for fields like scientific computing and artificial intelligence.However,traditional task scheduling algorithms do not fully leverage platform characteristics,resulting in inefficiency and long task execution times.We propose KANETAS,a reinforcement learning-based DAG(Directed Acyclic Graph)elastic task scheduling algorithm,designed to adapt to DAG tasks of various scales and structures.Kolmogorov-Arnold Network(KAN)was applied to the DAG scheduling problem.It enhances the efficiency of heterogeneous hardware by using Graph Convolutional Networks(GCN)and Actor-Critic Algorithm(A2C),recognizing hardware features and assigning tasks to appropriate computing units.We have conducted extensive experiments to evaluate the proposed solution with four strong baseline algorithms,including the state-of-the-art heuristics method and a variety of deep reinforcement learning based algorithms.The experimental results suggest that KANETAS can reduce the average makespan of the best baseline algorithm by 13.1%at most.Furthermore,compared to the MLP version,the KAN version showed superior performance.The proposed model demonstrates a clear advantage in load balancing.
