Optimization of Mapping and Scheduling for NoC-based MPSoCs
Explore the contention-aware mapping and scheduling optimization strategies for Network-on-Chip based Multi-Processor Systems-on-Chip at the Institute of Software, Chinese Academy of Sciences. The research addresses motivation, problem formulation, hybrid algorithm development, experimentation, and conclusion, focusing on saving computation and communication, reducing makespan, and minimizing energy cost through problem-specific heuristics and multi-objective optimization.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Institute of Software,Chinese Academy of Sciences Contention-aware mapping and scheduling optimization for NoC-based MPSoCs Rongjie Yan1, Yupeng Zhou2, Anyu Cai3, Changwen Li3, Yige Yan2, Minghao Yin2 1 State Key Laboratory of Computer Science, ISCAS , China 2 School of Computer Science and Information Technology, NENU , China 3 College of Computer Science, BJUT, China
Institute of Software,Chinese Academy of Sciences Agenda Motivation Problem formulation Mapping and scheduling issues Optimization objectives The hybrid algorithm for multi-objective optimization Problem-specific heuristics The hybrid algorithm Experimentation Comparison with exact and heuristic-based methods Flexibility in design space exploration Conclusion 2
Institute of Software,Chinese Academy of Sciences Motivation (a) Saving computation (b) Saving communication task execution communication shared link task execution communication shared link P0,2 t1 P0,2 t1 t1->t2 t1->t3 t1->t2 t1->t3 P1,2 t2->t3 t2 P1,1 t2->t3 t2->t4 t2 t2->t4 P1,1 P0,1 t3 P0,0 P2,0 t3 t3->t4 t3->t4 53 t4 t4 3035 10 12 27 0 A scheduling for the mapping in (a) 51 61 89 99 63 0 97 10 77 41 A scheduling for the mapping in (b) Questions on design space exploration: 1. How to minimize communication contention 2. How to reduce makespan and minimize energy cost 3
Institute of Software,Chinese Academy of Sciences Problem formulation Comparison of related works Heter. = heterogeneous architecture Homo. = homogeneous architecture Map. = mapping Sch. = scheduling Cap. = capacity of PE 4
Institute of Software,Chinese Academy of Sciences Problem formulation Modeling Mapping tasks, processors Related objectives: computation and communication cost, energy cost, contention degree Scheduling Computation and communication Involved relations: non-overlapping relation, causality relation Related objectives: makespan, energy cost, contention degree Complex objectives To minimize Contention Makespan Energy consumption 5
Institute of Software,Chinese Academy of Sciences Solutions Multi-objective hybrid search algorithm (MOHA) Problem specific heuristics Task clustering (TC) To group tightly coupled tasks w.r.t their dependency relation Capacity constrained cluster refinement (CR) To achieve a balanced load between various PEs Spiral mapping (SM) To reduce the communication by considering the physical locations 6
Institute of Software,Chinese Academy of Sciences Solutions Multi-objective hybrid search algorithm (MOHA) Encoding Scheduled tasks in a gene Ordered genes Initialization Randomly generated Heuristic guided Genetic process Crossover Mutation 7
Institute of Software,Chinese Academy of Sciences Solutions Multi-objective hybrid search algorithm (MOHA) Local search 8
Institute of Software,Chinese Academy of Sciences Solutions Multi-objective hybrid search algorithm (MOHA) Task clustering Uniform crossover Genetic process Capacity constrained cluster refinement Heuristics Split-merge-based mutation Spiral mapping Pareto local search MOHA Local search -dominance 9
Institute of Software,Chinese Academy of Sciences Experimentation Considerations on evaluating MOHA The quality of solutions The flexibility in design space exploration Strategy verification Setup Z3, CPLEX as the baseline of exact methods NSGAII as the baseline of heuristic algorithms Randomly generated as well as real benchmarks Set coverage metric Hypervolume indicator Pareto front 10
Institute of Software,Chinese Academy of Sciences Experimentation- Comparison with both exact and meta-heuristic methods Comparison with both exact and meta-heuristic methods MOHA can achieve the same set of solutions as exact methods 11
Institute of Software,Chinese Academy of Sciences Experimentation- Heuristics comparison with various metrics (a) Local search (b) Initialization (c) MOHA and NSGAII Local search can always improve the performance Heuristic-based initialization outperforms random initialization By applying the heuristics in the hybrid algorithm, the performance of MOHA is better 12
Institute of Software,Chinese Academy of Sciences Experimentation-Design space exploration Design space exploration of H264 decoder (264 tasks) with 2x2, 3x3, 4x4, 5x5 NoC platforms The flexibility of MOHA facilitates design space exploration of large-scale applications 13
Institute of Software,Chinese Academy of Sciences Conclusion We propose to evaluate the contention degree in terms of overlapped communication paths, and regard it as an objective to be minimized We provide a hybrid evolutionary algorithm to optimize multiple objectives for mapping and scheduling NoC-based MPSoCs The extensive experimentation demonstrates the efficiency and effectiveness of the algorithm in finding optimized solutions 14
Institute of Software,Chinese Academy of Sciences Thanks! 15
