mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Real-Time Communication over Wormhole-Switched On-Chip Networks
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (Complex Real-Time Embedded Systems)ORCID iD: 0000-0001-9736-8490
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In a modern industrial system, the requirement on computational capacity has increased dramatically, in order to support a higher number of functionalities, to process a larger amount of data or to make faster and safer run-time decisions. Instead of using a traditional single-core processor where threads can only be executed sequentially, multi-core and many-core processors are gaining more and more attentions nowadays. In a multi-core processor, software programs can be executed in parallel, which can thus boost the computational performance. Many-core processors are specialized multi-core processors with a larger number of cores which are designed to achieve a higher degree of parallel processing. An on-chip communication bus is a central intersection used for data-exchange between cores, memory and I/O in most multi-core processors. As the number of cores increases, more contention can occur on the communication bus which raises a bottleneck of the overall performance. Therefore, in order to reduce contention incurred on the communication bus, a many-core processor typically employs a Network-on-Chip (NoC) to achieve data-exchange. Real-time embedded systems have been widely utilized for decades. In addition to the correctness of functionalities, timeliness is also an important factor in such systems. Violation of specific timing requirements can result in performance degradation or even fatal problems. While executing real-time applications on many-core processors, the timeliness of a NoC, as a communication subsystem, is essential as well. Unfortunately, many real-time system designs over-provision resources to guarantee the fulfillment of timing requirements, which can lead to significant resource waste. For example, analysis of a NoC design yields that the network is already saturated (i.e. accepting more traffic can incur requirement violation), however, in reality the network actually has the capacity to admit more traffic. In this thesis, we target such resource wasting problems related to design and analysis of NoCs that are used in real-time systems. We propose a number of solutions to improve the schedulability of real-time traffic over wormhole-switched NoCs in order to further improve the resource utilization of the whole system. The solutions focus mainly on two aspects: (1) providing more accurate and efficient time analyses; (2) proposing more cost-effective scheduling methods.

Place, publisher, year, edition, pages
Västerås: Malardalen University Press , 2017.
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 232
Keyword [en]
real-time system, network-on-chips
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-35316ISBN: 978-91-7485-332-2 (print)OAI: oai:DiVA.org:mdh-35316DiVA: diva2:1095357
Public defence
2017-06-20, Gamma, Västerås, 09:15 (English)
Opponent
Supervisors
Available from: 2017-05-15 Created: 2017-05-12 Last updated: 2017-07-10Bibliographically approved
List of papers
1. Tighter Time Analysis for Real-Time Traffic in On-Chip Networks with Shared Priorities
Open this publication in new window or tab >>Tighter Time Analysis for Real-Time Traffic in On-Chip Networks with Shared Priorities
2016 (English)In: 2016 10th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2016, 2016, 7579319Conference paper, Published paper (Refereed)
Abstract [en]

The Network-on-Chip (NoC) is the preferred inter- connection medium for massively parallel platforms. Targeting real-time applications, fixed-priority based NoCs with virtual- channels have been proposed as a promising solution. In order to verify if specific time requirements can be satisfied, scheduability tests are typically used. Several analysis approaches have been proposed targeting priority-based NoCs. However, due to the approximation considered in the analyses, the results may involve a large amount of pessimism. The applicability of the analyses is thus limited in practice. In this paper, we identify a number of properties of NoCs with shared priorities. An improved time analysis is proposed where pessimism can be significantly reduced for many cases. In order to evaluate the proposed analysis, a number of experiments have been generated along with a case study based on an automotive application. The improvement can be clearly observed from the evaluation results.

Keyword
Network-on-ChipMany-CoreReal-TimeTiming Analysis
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-32839 (URN)10.1109/NOCS.2016.7579319 (DOI)000392263800003 ()2-s2.0-84994652210 (Scopus ID)
Conference
10th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2016; Nara; Japan; 31 August 2016 through 2 September 2016; Category numberCFP16NOC-ART; Code 124142
Projects
PREMISE - Predictable Multicore SystemsDPAC - Dependable Platforms for Autonomous systems and Control
Available from: 2016-09-30 Created: 2016-08-24 Last updated: 2017-05-12Bibliographically approved
2. Improved Priority Assignment for Real-Time Communications in On-Chip Networks
Open this publication in new window or tab >>Improved Priority Assignment for Real-Time Communications in On-Chip Networks
2015 (English)In: ACM International Conference Proceeding SeriesVolume 04-06, 2015, 171-180 p.Conference paper, Published paper (Refereed)
Abstract [en]

The Network-on-Chip is the on-chip interconnection medium of choice for modern massively parallel processors and System-on-Chip in general. Fixed-priority based preemptive scheduling using virtual-channels is a solution to support real-time communications in on-chip networks. However, the different characteristics of the Network-on-Chip compared to the single processor scheduling problem prevents the usage of known optimal algorithms (e.g. the Audsley's algorithm) to assign priorities to messages. A heuristic search algorithm based approach (called the HSA) focusing on the priority assignment for on-chip communications has been presented in the literature. The HSA is much faster than an exhaustive search based solution, with a price of missing certain schedulable cases (i.e. non-optimal). In this paper, we present two undirected-graph based priority assignment algorithms, the GESA and the GHSA. In contrast to the previous work, we can decrease the search space significantly by taking the interference dependencies of different messages on the network into account. A number of experiments are generated, in order to evaluate the proposed algorithms. The results show that the GESA can always achieve higher schedulability ratios than the HSA, but may require longer processing time. On the other hand, the GHSA has the same performance as the HSA regarding the schedulability, but can significantly improve the efficiency.

Keyword
Network-on-ChipPriority assignmentMany-Core
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-30022 (URN)10.1145/2834848.2834867 (DOI)000380614800017 ()2-s2.0-84959481086 (Scopus ID)978-1-4503-3591-1 (ISBN)
Conference
The 23rd International Conference on Real-Time Networks and Systems RTNS'15, 4-6 Nov 2015, Lille, France
Projects
PREMISE - Predictable Multicore Systems
Available from: 2015-12-19 Created: 2015-12-18 Last updated: 2017-05-12Bibliographically approved
3. A dependency-graph based priority assignment algorithm for real-time traffic over NoCs with shared virtual-channels
Open this publication in new window or tab >>A dependency-graph based priority assignment algorithm for real-time traffic over NoCs with shared virtual-channels
2016 (English)In: IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS, 2016, Article number 7496504Conference paper, Published paper (Refereed)
Abstract [en]

The Network-on-Chip (NoC) is the on-chip interconnection medium of choice for modern massively parallel processors and System-on-Chip (SoC) in general. Fixed-priority based preemptive scheduling using virtual-channels is a solution to support real-time communications in on-chip networks. Targeting the priority assignment problem in the context of NoCs, heuristic based priority assignment algorithms are more practical, due to the exponentially increased search space as the number of flows goes up. In our previous work, we have proposed a graph-based heuristic priority assignment algorithm (called GHSA) for NoC communications, where we show that taking the dependencies between flows into account can significantly reduce the search space. However, GHSA only works for NoCs with distinct priorities. Routers in such type of platforms may have a large amount of buffer cost when the number of flows is high. The applicability can thus be limited in reality. One solution to reduce the buffer cost is to allow priority sharing of different flows. In this paper, we propose a dependency-graph based priority assignment algorithm (called eGHSA) targeting NoCs with shared virtual-channels. A number of experiments as well as a case study based on an automotive application are generated, which clearly show that eGHSA improves the efficiency compared to the existing solution in the literature. 

Keyword
Algorithms, Combinatorial optimization, Distributed computer systems, Flow graphs, Graphic methods, Heuristic algorithms, Program processors, Programmable logic controllers, Routers, System-on-chip, Automotive applications, Massively parallel processors, Network-on-chip(NoC), On-chip interconnection, Pre-emptive scheduling, Priority assignment, Real-time communication, System on chips (SoC), Network-on-chip
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-32521 (URN)10.1109/WFCS.2016.7496504 (DOI)000382857300010 ()2-s2.0-84980445834 (Scopus ID)9781509023394 (ISBN)
Conference
12th IEEE World Conference on Factory Communication Systems, WFCS 2016, 3 May 2016 through 6 May 2016
Available from: 2016-08-18 Created: 2016-08-18 Last updated: 2017-05-12Bibliographically approved
4. Scheduling Real-Time Packets with Non-preemptive Regions on Priority-Based NoCs
Open this publication in new window or tab >>Scheduling Real-Time Packets with Non-preemptive Regions on Priority-Based NoCs
2016 (English)In: Proceedings - 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016, 2016Conference paper, Published paper (Refereed)
Abstract [en]

Network-on-Chip (NoC) is a preferred communi- cation medium for massively parallel platforms. Fixed-priority based scheduling using virtual-channels is one of the promising solutions to support real-time traffic in on-chip networks. Most of the existing NoC implementations which can support fixed- priority based scheduling use a flit-level preemptive scheduling. Under such a mechanism, preemptions can happen between the transmissions of successive flits. In this paper, we present a modified framework where the non-preemptive region of each NoC packet increases from a single flit. Using the proposed approach, the response times of certain packet flows can be reduced, which can thus improve the schedulability of the whole network. As a result, the utilization of NoCs can be improved by admitting more real-time traffic. Schedulability tests regarding the proposed framework are presented along with the proof of the correctness. Moreover, a number of experiments as well as a case study based on an automotive application have been generated, where we can clearly observe the improvement of our solution compared to the original flit-level preemptive NoC.

Keyword
Network-on-ChipMany-CoreLimited Preemptive SchedulingPriority Arbitration
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-32855 (URN)10.1109/RTCSA.2016.36 (DOI)000387085600026 ()2-s2.0-84994515704 (Scopus ID)
Conference
22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016; Daegu; South Korea; 17 August 2016 through 19 August 2016; Category numberE5908; Code 124144
Projects
PREMISE - Predictable Multicore Systems
Available from: 2016-09-30 Created: 2016-08-24 Last updated: 2017-05-12Bibliographically approved
5. A Tighter Recursive Calculus to Compute the Worst-Case Traversal Time of Real-Time Traffic over NoCs
Open this publication in new window or tab >>A Tighter Recursive Calculus to Compute the Worst-Case Traversal Time of Real-Time Traffic over NoCs
2017 (English)In: 2017 22ND ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC), 2017, 275-282 p., 7858332Conference paper, Published paper (Refereed)
Abstract [en]

Network-on-Chip (NoC) is a communication subsystem which has been widely utilized in many-core processors and system-on-chips in general. In this paper, we focus on a Round-Robin Arbitration (RRA) based wormhole-switched NoC which is a common architecture used in most of the existing implementations. In order to execute real-time applications on such a NoC based platform, a number of given real-time requirements need to be fulfilled. One of the most typical requirements is schedulability which refers to if real-time packets can be delivered within the given time durations. Timing analysis is a common tool to verify the schedulability of a real-time system. Unfortunately, the existing timing analyses of RRA-based NoCs either provide too pessimistic estimates which results in overly allocated resources, or require a large amount of processing which limits the applicability in reality. Therefore, in this paper, we present an improved timing analysis, aiming to provide more accurate estimates along with acceptable computation time. From the evaluation results, we can clearly observe the improvement achieved by the proposed timing analysis.

Series
Asia and South Pacific Design Automation Conference Proceedings, ISSN 2153-6961
Keyword
Network-on-ChipRound-RobinAnalysisWorst-Case Traversal Time
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-33807 (URN)10.1109/ASPDAC.2017.7858332 (DOI)000403609600059 ()2-s2.0-85015318423 (Scopus ID)978-1-5090-1558-0 (ISBN)
Conference
22nd Asia and South Pacific Design Automation Conference ASP-DAC'17, 16-19 Jan 2017, Chiba / Tokyo, Japan
Projects
PREMISE - Predictable Multicore SystemsDPAC - Dependable Platforms for Autonomous systems and Control
Available from: 2016-11-21 Created: 2016-11-21 Last updated: 2017-07-06Bibliographically approved
6. Buffer-Aware Analysis for Worst-Case Traversal Time of Real-Time Traffic over RRA-based NoCs
Open this publication in new window or tab >>Buffer-Aware Analysis for Worst-Case Traversal Time of Real-Time Traffic over RRA-based NoCs
2017 (English)In: Proceedings - 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, 2017, 567-575 p., 7912705Conference paper, Published paper (Refereed)
Abstract [en]

Network-on-Chip (NoC) is a communication sub-system which has been widely utilized in many-core processors and system-on-chips in general. In order to execute time-critical applications on a NoC-based platform, the timing behavior of the network needs to be predicted during system design. One of the most important timing requirements is regarding schedulability, which refers to determining if a real-time packet can be delivered within a specific time duration. To verify the fulfillment of such timing requirement, a proper timing analysis is mandatory. Our work focuses on a Round-Robin Arbitration (RRA) based wormhole-switched NoC, which is a common architecture used in many of the existing implementations. Recursive Calculus (RC) is one of the existing analysis approaches for RRA-based NoCs which has been utilized in many research works. However, RC does not take buffer-effects into account. As a result, while performing RC on most of the existing RRA-based NoC designs, it can produce unsafe estimates which is not acceptable for time-critical systems. In this paper, we identify the optimistic problem of RC, and we propose a Revised Recursive Calculus (RRC) which extends RC by considering buffer-effects as well as supporting packetization.

Series
Euromicro Conference on Parallel Distributed and Network-Based Processing, ISSN 1066-6192
Keyword
Many-CoreNetwork-on-ChipBufferTiming Analysis
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-34101 (URN)10.1109/PDP.2017.37 (DOI)000403395100086 ()2-s2.0-85019596935 (Scopus ID)9781509060580 (ISBN)
Conference
25th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing PDP'17, 6-8 Mar 2017, Saint-Petersburg, Russian Federation
Projects
PREMISE - Predictable Multicore SystemsDPAC - Dependable Platforms for Autonomous systems and Control
Available from: 2016-12-14 Created: 2016-12-13 Last updated: 2017-07-06Bibliographically approved
7. Using Segmentation to Improve Schedulability of RRA-based NoCs with Mixed Traffic
Open this publication in new window or tab >>Using Segmentation to Improve Schedulability of RRA-based NoCs with Mixed Traffic
2017 (English)In: 2017 22ND ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC), 2017, 744-750 p., 7858413Conference paper, Published paper (Refereed)
Abstract [en]

Network-on-Chip (NoC) is the interconnect of choice for many- core processors and system-on-chips in general. Most of the exist- ing NoC designs focus on the performance with respect to average throughput, which makes them less applicable for real-time appli- cations especially when applications have hard timing requirements on the worst-case scenarios. In this paper, we focus on a Round- Robin Arbitration (RRA) based wormhole-switched NoC which is a common architecture used in most of the existing implementa- tions. We propose a novel segmentation algorithm targeting RRA- based NoCs in order to improve the schedulability of real-time traf- fic without modifying the hardware architecture. Additionally, we also address the problem of transmitting both real-time traffic and best-effort traffic in the same NoC. The proposed solutions aim to provide timing guarantees to real-time traffic and achieve low la- tency for best-effort traffic. According to the evaluation results, the proposed segmentation solution can significantly improve the schedulability of the whole network.

Series
Asia and South Pacific Design Automation Conference Proceedings, ISSN 2153-6961
Keyword
Network-on-ChipBest-EffortReal-Time Mixed-Traffic
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-33808 (URN)10.1109/ASPDAC.2017.7858413 (DOI)000403609600138 ()2-s2.0-85015315749 (Scopus ID)978-1-5090-1558-0 (ISBN)
Conference
22nd Asia and South Pacific Design Automation Conference ASP-DAC'17, 16-19 Jan 2017, Chiba / Tokyo, Japan
Projects
PREMISE - Predictable Multicore SystemsDPAC - Dependable Platforms for Autonomous systems and Control
Available from: 2016-11-21 Created: 2016-11-21 Last updated: 2017-07-06Bibliographically approved

Open Access in DiVA

fulltext(330 kB)9 downloads
File information
File name FULLTEXT02.pdfFile size 330 kBChecksum SHA-512
08d434b67c20e15bef6908e14217fc05bc5c4a156616554bd5fb97d1d9b2087e119d0f1f1eb92bf1abb79e06023c9118f79b6e877d14ffa714c9ac4673fda2f4
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Liu, Meng
By organisation
Embedded Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 9 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 175 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf