mdh.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 22) Show all publications
Liu, M., Becker, M., Behnam, M. & Nolte, T. (2017). A Tighter Recursive Calculus to Compute the Worst-Case Traversal Time of Real-Time Traffic over NoCs. In: 2017 22ND ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC): . Paper presented at 22nd Asia and South Pacific Design Automation Conference ASP-DAC'17, 16-19 Jan 2017, Chiba / Tokyo, Japan (pp. 275-282). , Article ID 7858332.
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, p. 275-282, article id 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
Keywords
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
Liu, M., Becker, M., Behnam, M. & Nolte, T. (2017). Buffer-Aware Analysis for Worst-Case Traversal Time of Real-Time Traffic over RRA-based NoCs. In: Proceedings - 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017: . Paper presented at 25th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing PDP'17, 6-8 Mar 2017, Saint-Petersburg, Russian Federation (pp. 567-575). , Article ID 7912705.
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, p. 567-575, article id 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
Keywords
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
Liu, M. (2017). Real-Time Communication over Wormhole-Switched On-Chip Networks. (Doctoral dissertation). Västerås: Malardalen University Press
Open this publication in new window or tab >>Real-Time Communication over Wormhole-Switched On-Chip Networks
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
Keywords
real-time system, network-on-chips
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-35316 (URN)978-91-7485-332-2 (ISBN)
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
Liu, M., Becker, M., Behnam, M. & Nolte, T. (2017). Using Non-Preemptive Regions and Path Modification to Improve Schedulability of Real-Time Traffic over Priority-Based NoCs. Real-time systems (6), 886-915
Open this publication in new window or tab >>Using Non-Preemptive Regions and Path Modification to Improve Schedulability of Real-Time Traffic over Priority-Based NoCs
2017 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, no 6, p. 886-915Article in journal (Refereed) Published
Abstract [en]

Network-on-Chip (NoC) is a preferred communication 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 works regarding priority-based NoCs use a flit-level preemptive scheduling. Under such a mechanism, preemptions can only happen between the transmissions of successive flits but not during the transmission of a single flit. 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 traffic 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. Additionally, we also propose a path modification approach on top of the non-preemptive region based method to further improve schedulability. A number of experiments have been performed to evaluate the proposed solutions, where we can observe significant improvement on schedulability compared to the original flit-level preemptive NoCs. 

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-35665 (URN)10.1007/s11241-017-9276-5 (DOI)000412536700003 ()2-s2.0-85020737369 (Scopus ID)
Available from: 2017-06-09 Created: 2017-06-09 Last updated: 2017-10-31Bibliographically approved
Liu, M., Becker, M., Behnam, M. & Nolte, T. (2017). Using Segmentation to Improve Schedulability of RRA-based NoCs with Mixed Traffic. In: 2017 22ND ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC): . Paper presented at 22nd Asia and South Pacific Design Automation Conference ASP-DAC'17, 16-19 Jan 2017, Chiba / Tokyo, Japan (pp. 744-750). , Article ID 7858413.
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, p. 744-750, article id 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
Keywords
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
Liu, M., Becker, M., Behnam, M. & Nolte, T. (2016). A dependency-graph based priority assignment algorithm for real-time traffic over NoCs with shared virtual-channels. In: IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS: . Paper presented at 12th IEEE World Conference on Factory Communication Systems, WFCS 2016, 3 May 2016 through 6 May 2016. , Article ID Article number 7496504.
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 id 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. 

Keywords
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-84982854142 (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: 2019-01-28Bibliographically approved
Liu, M., Chiru, C., Behnam, M., Sandström, K. & Nolte, T. (2016). On providing real-time guarantees in cloud-based platforms. In: IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS: . Paper presented at 12th IEEE World Conference on Factory Communication Systems, WFCS 2016, 3 May 2016 through 6 May 2016. , Article ID Article number 7496534.
Open this publication in new window or tab >>On providing real-time guarantees in cloud-based platforms
Show others...
2016 (English)In: IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS, 2016, article id Article number 7496534Conference paper, Published paper (Refereed)
Abstract [en]

Cloud technologies are gaining more and more attentions in recent years. Cloud-based service brings benefits in cost, energy efficiency, sharing of resources, increased flexibility, adaptability and evolvability. However, there are a number of associated challenges that need to be properly addressed before applying the cloud technique generally in industries. Providing efficient and predictable computation and communication is one of the important challenges, since many industrial systems (e.g. a control system) have specific timing requirements. Our current work thus focuses on guaranteeing the predictability of a cloud-based service. Virtualization, as one of the key technologies in Cloud Computing, is used to abstract details of resources away from end-services which simplifies the resource sharing. It thus improves the resource utilization and saves budget for end-users. In this preliminary work, we have implemented a distributed system using virtualization techniques (including virtual machines and virtual switches). Additionally, we generate a number of experiments to investigate how QoS policies can help us to provide real-time communication guarantees. 

Keywords
Budget control, Energy efficiency, Systems analysis, Cloud based platforms, Distributed systems, Increased flexibility, Real time guarantees, Real-time communication, Resource utilizations, Timing requirements, Virtualization Techniques, Virtual reality
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-32522 (URN)10.1109/WFCS.2016.7496534 (DOI)000382857300040 ()2-s2.0-84982798199 (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: 2019-01-28Bibliographically approved
Liu, M., Behnam, M. & Nolte, T. (2015). A Stochastic Response Time Analysis for Communications in On-Chip Networks. In: : . Paper presented at 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA'15, 19-21 Aug 2015, Hong Kong, China (pp. 237-246).
Open this publication in new window or tab >>A Stochastic Response Time Analysis for Communications in On-Chip Networks
2015 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Priority-based wormhole-switching has been proposed as a solution to handle real-time traffic in on-chip networks. In order to support real-time traffic, the predictability of end-toend delays need to be guaranteed. Several deterministic schedulability analysis approaches for wormhole-switched networks have been proposed. These approaches calculate a single upper-bound of the response time of each Network-on-Chip (NoC) flow, which is suitable for hard real-time applications. However, for many soft real-time applications, the performance does not depend on the worst-case scenario, which means that the calculated single upper-bounds are not sufficient to represent the performance. Therefore, in this paper, we present a stochastic Response Time Analysis (RTA) which can calculate a distribution of the response times of a real-time NoC flow. The estimated distributions can be utilized for multiple purposes, such as calculating deadline miss ratios, and computing upper-bounds regarding different probabilities. A number of simulation-based experiments are generated in order to investigate the pessimism involved in the analysis. Moreover, the processing time of the analysis is also measured from the experiments in order to examine the scalability of the proposed approach.

Keywords
Stochastic Time AnalysisNetwork-on-ChipsReal-Time System
National Category
Embedded Systems
Identifiers
urn:nbn:se:mdh:diva-29256 (URN)10.1109/RTCSA.2015.25 (DOI)000378419800025 ()2-s2.0-84962835281 (Scopus ID)9781467378550 (ISBN)
Conference
21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA'15, 19-21 Aug 2015, Hong Kong, China
Projects
START - Stochastic Real-Time Analysis of Embedded Software Systems
Available from: 2015-10-06 Created: 2015-09-29 Last updated: 2016-10-31Bibliographically approved
Becker, M., Liu, M., Behnam, M. & Nolte, T. (2015). Adaptive Routing of Real-Time Traffic on a 2D-Mesh Based NoC. In: The 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, WiP RTCSA-wip'15: . Paper presented at The 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, WiP RTCSA-wip'15, 19 Aug 2015, Hong Kong, HongKong.
Open this publication in new window or tab >>Adaptive Routing of Real-Time Traffic on a 2D-Mesh Based NoC
2015 (English)In: The 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, WiP RTCSA-wip'15, 2015Conference paper, Published paper (Refereed)
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-29625 (URN)
Conference
The 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, WiP RTCSA-wip'15, 19 Aug 2015, Hong Kong, HongKong
Projects
START - Stochastic Real-Time Analysis of Embedded Software SystemsPREMISE - Predictable Multicore Systems
Available from: 2015-12-11 Created: 2015-11-26 Last updated: 2015-12-11Bibliographically approved
Liu, M., Becker, M., Behnam, M. & Nolte, T. (2015). Improved Priority Assignment for Real-Time Communications in On-Chip Networks. In: ACM International Conference Proceeding SeriesVolume 04-06: . Paper presented at The 23rd International Conference on Real-Time Networks and Systems RTNS'15, 4-6 Nov 2015, Lille, France (pp. 171-180).
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, p. 171-180Conference 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.

Keywords
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
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-9736-8490

Search in DiVA

Show all publications