New Communication Model for Network-On-Chip Schedulability Analysis

New Communication Model for Network-On-Chip Schedulability Analysis
Slide Note
Embed
Share

This study delves into the Exact Communication Time Model (ECTM) for analyzing schedulability of real-time systems over Network-On-Chip (NoC) architectures. The research addresses challenges in task and communication timing enforcement, introducing ECTM to evaluate the feasibility of periodic tasks in NoC-based parallel setups. Through ECTM, the study aims to improve accuracy and scalability while considering communication interferences and complexities caused by the network, offering potential enhancements to real-time scheduling solutions.

  • Communication Model
  • Network-On-Chip
  • Schedulability Analysis
  • Real-Time Systems
  • ECTM
sstea
sstea Follow

Uploaded on Apr 04, 2025 | 0 Views

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.

Download 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.

E N D

Presentation Transcript

  1. ECTM: A New Communication Model to Network-On-Chip SchedulabilityAnalysis MouradDridi*, St phaneRubini*,Frank Singhoff*, Jean-Philippe Diguet *Universit de Bretagne Occidentale, Lab-STICC, France Universit de Bretagne Sud,Lab-STICC, France 24th International Conference on Reliable Software Technologies Ada-Europe 2019 11-14 June 2019, Warsaw, Poland

  2. Outline 1. Introduction a. Context Network On Chip b. Problem Statement 2. Exact Communication Time Model (ECTM) a. ECTM for Store And Forward b. ECTM for Wormhole 3. Implementation and Evaluation a. Accuracy of ECTM b. Scalability of ECTM 4. Conclusion 2

  3. Context -Network On Chip (NoC) Introduction Communication infrastructure based on links and routers that interconnect cores providing packet-based data transfer PE3 PE2 PE1 Scalability Communication parallelism R1 R2 R3 Resource contentions between different flows in the network communication delays PE6 PE5 PE4 R4 R5 R6 PE9 PE8 PE7 3 R7 R8 R9

  4. Problem Statement - Real Time System over NoC Introduction Real Time System Timing constraints of tasks and communications (e.g. deadline) must be enforced during execution. Real Time System over NoC To analyze schedulability of periodic tasks in NoC-based parallel architectures, we have to : Analyze the task scheduling over processing elements Analyze the message communications scheduling over the network. NoC introduces new communication interferences types (Direct and Indirect interferences) Complicate the computation of communication time Classic multiprocessor real-time scheduling solutions consider worst case communication time instead of the actual delays introduced by the network Pessimistic analysis results. 4

  5. Outline 1. Introduction a. Context Network On Chip b. Context Real Time System c. Problem Statement 2. Exact Communication Time Model (ECTM) a. ECTM for Store And Forward b. ECTM for Wormhole 3. Implementation and Evaluation a. Accuracy of ECTM b. Scalability of ECTM 4. Conclusion 5

  6. 6 Exact Communication Time Model (ECTM) Architectural Model Task Mapping Task Model The main goal of ECTM is to assess the schedulability of dependent periodic tasks exchanging messages on NoC. NoC Model Flow Model Architectural Model A set of periodic tasks exchanging messages deployed over a NoC. ECTM eR1R2 eR3R2 R1 R2 R3 eR2R1 eR2R3 ePE3R3 ePE1R1 eR1PE1 eR3PE3 1 2 PE 3 PE 2 PE 1 R NoC Router Processing Element PE Message exy Task Physical link Schedulability Result (flow and tasks deadline)

  7. 7 Exact Communication Time Model (ECTM) Architectural Model Task Mapping Task Model The main goal of ECTM is to assess the schedulability of dependent periodic tasks exchanging messages on NoC. NoC Model Flow Model Architectural Model A set of periodic tasks exchanging messages deployed over a NoC. How to achieve ECTM schedulability analysis of the overall system ? eR1R2 eR3R2 R1 R2 R3 eR2R1 eR2R3 ePE3R3 ePE1R1 eR1PE1 eR3PE3 1 2 PE 3 PE 2 PE 1 R NoC Router Processing Element PE Message exy Task Physical link Schedulability Result (flow and tasks deadline)

  8. Exact Communication Time Model (ECTM) 8 Architectural Model ECTM Converts NoC flow of messages scheduling to periodic tasks scheduling. Each flow of message is transformed to a set of dependent periodic tasks. Task Mapping Task Model NoC Model Flow Model ECTM Analysis model A set of periodic task running on a multiprocessor execution platform. We assume a multiprocessor with identical processors and no shared resources. Scheduling analysis of such model can be performed with list scheduling algorithms Analysis Model Task Mapping Task Model Multiprocessors without shared resources List scheduling algorithms Simulation Simulation time according on feasibility intervals defined by Goossens Simulation Support Wormhole and SAF ECTM_Wormhole : Transformations rules for Wormhole NoC ECTM_SAF : Transformations rules for SAF NoC Schedulability Result (flow and tasks deadline)

  9. Transformations Rules of ECTM_SAF For the SAF mode, each router waits for a full packet to arrive before sending it to the next router For SAF NoC, ECTM_SAF applies the following rules: Rule 1 Each router of the architectural model will be removed in the analysis model while keeping all the processing elements. Rule 2 Each unidirectional link in the network between two routers and processing element of the architectural model will be replaced in the analysis model by a new processing element. Rule 3 Each flow of the architectural model will be replaced by a set of nb tasks. nb :number of links used by the flow. 9

  10. ECTM_SAF - Example The Architectural Model e12 e32 R1 R2 R3 e21 e23 ePE3R3 ePE1R1 eR1PE1 eR3PE3 1 2 PE 3 PE 2 PE 1 10

  11. ECTM_SAF - Example The Architectural Model e12 e32 R1 R2 R3 e21 e23 ePE3R3 ePE1R1 eR1PE1 eR3PE3 1 2 PE 3 PE 2 PE 1 ECTMSAF Rule 1 The Analysis Model 11 PE 1 PE 3 PE 2

  12. ECTM_SAF - Example The Architectural Model eR1R2 eR3R2 R1 R2 R3 eR2R1 eR2R3 ePE3R3 ePE1R1 eR1PE1 eR3PE3 1 2 PE 3 PE 2 PE 1 Rule 2 ECTMSAF The Analysis Model PE PE PE1R1 PE R1R2 PE PE2R2 PE R2R3 PE3R3 PE PE R3R2 PE R2PE2 PE R2R1 PE R1PE1 R3PE3 12 PE 1 PE 3 PE 2

  13. ECTM_SAF - Example The Architectural Model e12 e32 R1 R2 R3 e21 e23 ePE3R3 ePE1R1 eR1PE1 eR3PE3 1 2 PE 3 PE 2 PE 1 Rule 3 ECTMSAF The Analysis Model 1,1 1,2 1,3 PE PE PE1R1 PE R1R2 PE PE2R2 PE R2R3 PE3R3 PE PE R3R2 PE R2PE2 PE R2R1 PE R1PE1 R3PE3 1,4 13 PE 1 PE 3 PE 2 2 1

  14. Transformations Rules of ECTM_Wormhole For Wormhole mode, the packet is divided into a number of fixed size flits. The packet is transferred in a pipeline way and possibly span over multiple routers. For Wormhole NoC, ECTM applies the following rules: Rule 1 Each router of the architectural model will be removed in the analysis model while keeping all the processing elements. Rule 2 Each unidirectional link in the network between two routers and processing element of the architectural model will be replaced in the analysis model by a new processing element. Rule 3 Each flow of the architectural model will be replaced by a set of nb tasks. (nb = nblink X nbsize) nblink: number of links used by the flow nbsize: size of message of the flow 14

  15. Outline 1. Introduction a. Context Network On Chip b. Context Real Time System c. Problem Statement 2. Exact Communication Time Model (ECTM) a. ECTM for Store And Forward b. ECTM for Wormhole 3. Implementation and Evaluation a. Accuracy of ECTM b. Scalability of ECTM 4. Conclusion 15

  16. Implementation and Evaluation Implementation into a real-time scheduling simulator Cheddar Evaluation of Accuracy Scalability Comparison with Worst Case Communication Time Model (WCCTM) WCCTM : a NoC communication model based on worst case communication time analysis The scheduling analysis is performed with Highest Level First with Estimated Time (HLFET). 16

  17. Accuracy of ECTM Implementation and Evaluation Evaluate the rate of schedulable task sets found as schedulable by ECTM and WCCTM models. ECTM SAF WCCTM SAF ECTM Wormhole WCCTM Wormhole 100 90 80 Schedulability rate (%) 70 60 Generate randomly 100 sets of dependent periodic tasks using UuniFast. 50 40 30 20 10 Random task mapping 0 0 0.08 0.16 0.24 0.32 0.4 0.48 0.56 0.56 0.64 Traffic patterns: One-To-One. Processing Element Utilization For Wormhole NoCs, ECTM is more accurate than WCCTM with an improvement of 100%. 17 Packet size : 4 flits.

  18. Accuracy of ECTM Implementation and Evaluation ECTM SAF Evaluate the rate of schedulable task sets found as schedulable by ECTM and WCCTM models. 100 WCCTM SAF 90 ECTM Wormhole WCCTM Wormhole 80 Schedulability Rate (%) 70 60 Generate randomly 100 sets of dependent periodic tasks using UuniFast. 50 40 30 20 Random task mapping 10 0 Traffic patterns: All-To-One 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Processing Element Utilization ECTM is more accurate than WCCTM with an improvement of 30% for Store-And-Forward NoCs. 18 Packet size : 4 flits.

  19. Scalability of ECTM Implementation and Evaluation 9 Measure the computation time of the WCCTM and ECTM transformations. WCCTM ECTM SAF ECTM Wormhole (2 flits) ECTM Wormhole (3flits) 8 7 Computation Time (s) 6 5 4 3 2 Generate randomly sets of dependent periodic tasks using UuniFast. 1 0 15 30 45 60 75 90 105 120 Number of flow Random task mapping In terms of computation time, WCCTM has a shorter computation time comparing to ECTM with a reduction of 19 4x4 NoC 17% for Store-And-Forward NoCs 54% for Wormhole NoCs

  20. Conclusion Problem statement New communication delays introduced by the NoC complicate the communication time analysis. The communication schedulability is essential to analyze schedulability of periodic tasks deployed over NoC. Contribution ECTM: a NoC communication Model Assess the schedulability of dependent periodic tasks exchanging messages on NoC Converts NoC flow of messages scheduling to periodic tasks scheduling. Implementation available in the Cheddar tool http://beru.univ-brest.fr/svn/CHEDDAR/ Result ECTM is more accurate than WCCTM An improvement of 100% for Wormhole NoC An improvement of 30% for Store-And-Forward NoCs ECTM need more time to compute the analysis model than WCCTM 54% for Wormhole NoCs 20

Related


Medicaid and CHIP Coverage of New Treatments for Sickle Cell Disease

Medicaid and CHIP Coverage of New Treatments for Sickle Cell Disease

arun
OACES Chip Seal Workshop Highlights and Insights

OACES Chip Seal Workshop Highlights and Insights

tenlei
Digital Light Processing (DLP) Projectors

Digital Light Processing (DLP) Projectors

birc_676
Detection of Mutations in EGFR in Circulating Lung Cancer Cells: Study on SARMS Assay and CTC-Chip

Detection of Mutations in EGFR in Circulating Lung Cancer Cells: Study on SARMS Assay and CTC-Chip

fletc
ChIP-seq Data Analysis in Primate iPSCs

ChIP-seq Data Analysis in Primate iPSCs

whar
Enhancing NAND Flash Memory Chip-Off Forensic Analysis Reliability

Enhancing NAND Flash Memory Chip-Off Forensic Analysis Reliability

phi_gan
A Model for Application Slowdown Estimation in On-Chip Networks

A Model for Application Slowdown Estimation in On-Chip Networks

kyom_851
Investigating Chip-to-Chip Communication Performance on 2.5D Interposer

Investigating Chip-to-Chip Communication Performance on 2.5D Interposer

ron_kee
Parameterized Workload Adaptation for Fork-Join Tasks with Dynamic Workloads and Deadlines

Parameterized Workload Adaptation for Fork-Join Tasks with Dynamic Workloads and Deadlines

amirhe
Multi-Product Chip Multiprocessor Floorplan Optimization Framework

Multi-Product Chip Multiprocessor Floorplan Optimization Framework

ashmore_k
Control Chip Functionality Overview in Particle Detection Systems

Control Chip Functionality Overview in Particle Detection Systems

lcatt
Real-Time Analysis and Architectures for Automotive Systems

Real-Time Analysis and Architectures for Automotive Systems

tato_65
Networks-on-Chip (NoC) in Computer Engineering

Networks-on-Chip (NoC) in Computer Engineering

cad_eng
Network-on-Chip Communication and Optimization

Network-on-Chip Communication and Optimization

mode_nna
Challenges and Progress in Children's Health Coverage

Challenges and Progress in Children's Health Coverage

aun_koe
Best Chip Repair Services in Burnaby

Best Chip Repair Services in Burnaby

Jack3
Network Slicing in 5GC

Network Slicing in 5GC

harp_7
Performance Evaluation of On-Chip Sensor Network in MPSoC

Performance Evaluation of On-Chip Sensor Network in MPSoC

spat_taj
CMOS Chip Testing: Need, Principles, Strategies

CMOS Chip Testing: Need, Principles, Strategies

joli540
Efficient Timing Channel Protection for On-Chip Networks

Efficient Timing Channel Protection for On-Chip Networks

trer838
Optimizing JWST Observations: Target Visibility Tool Insights

Optimizing JWST Observations: Target Visibility Tool Insights

eka_cr
ESAC 2017 JWST Workshop General Target Visibility Tool

ESAC 2017 JWST Workshop General Target Visibility Tool

bcay

More Related Content