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
Analysis and Management of Communication in On-Chip Networks
KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Regarding the needs of low-power, high-performance embedded systems and the growing computation-intensive applications, the number of computing resources in a single chip has enormously increased. The current VLSI technology is able to support such an integration of transistors and add many computing resources such as CPU, DSP, specific IPs, etc to build a Systemon- Chip (SoC). However, interconnection between resources becomes another challenging issue which can be raised by using an on-chip interconnection network or Network-on-Chip (NoC). NoC-based communication which allows pipelined concurrent transmissions of transactions is becoming a dominate infrastructure for many core computing platforms.

This thesis analyzes and manages both Best Effort (BE) and Guaranteed Service (GS) communications using analytical performance approaches. As the first step, the present thesis focuses on the flow control for BE traffic in NoC. It models BE source rates as the solution to a utility-based optimization problem which is constrained with link capacities while preserving GS traffic requirements at the desired level. Towards this, several utility functions including proportionally-fair, rate-sum, and max-min fair scenarios are investigated. Moreover, it is worth looking into a scenario in which BE source rates are determined in favor of minimizing the delay of such traffics. The presented flow control algorithms solve the proposed optimization problems determining injection rate in each BE source node.

In the next step, real-time systems with guaranteed service are considered. Real-time applications require performance guarantees even under worst-case conditions, i.e. Quality of Service (QoS). Using network calculus, we present and prove the required theorems for deriving performance metrics and then apply them to propose formal approaches for the worst-case performance analysis. The proposed analytical model is used to minimize total cost in the networks in terms of buffer and delay. To this end, we address several optimization problems and solve them to consider the impact of various objective functions. We also develop a tool which derives performance metrics for a given NoC, formulates and solves the considerable optimization problems to provide an invaluable insight for NoC designers.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. , xxi, 59 p.
Series
TRITA-ICT-ECS AVH, ISSN 1653-6363 ; 15:01
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-161178ISBN: 978-91-7595-458-5 (print)OAI: oai:DiVA.org:kth-161178DiVA: diva2:793922
Public defence
2015-03-30, Sal/hall C, Elektrum , KTH-ICT, Isafjordsgatan, Kista, 13:00 (English)
Opponent
Supervisors
Note

QC 20150310

Available from: 2015-03-10 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
List of papers
1. A Novel Flow Control Scheme for Best Effort Traffic in NoC Based on Source Rate Utility Maximization
Open this publication in new window or tab >>A Novel Flow Control Scheme for Best Effort Traffic in NoC Based on Source Rate Utility Maximization
2007 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Advances in semiconductor technology, has enabled designers to put complex, massively parallel multiprocessor systems on a single chip. Network on chip (NoC) that supports high degree of reusability and scalablity, is a new paradigm for designing core based System-on-Chip. NoCs provide efficient communication services to IPs: communication services with guarantees on throughput and latency (GS) and communication services with no guarantees on them (BE). However, the run-time management of communication in NoC, especially congestion control mechanism is a challenging task. This paper considers a congestion control scenario which models flow control as a utility-based optimization problem. Since BE traffic is prone to congestion, we assume that GS traffic requirements are being preserved at the desired level and regulate BE source rates with the solution of the optimization problem. We propose an iterative algorithm to solve the optimization problem based on Newton's method. The proposed algorithm can be implemented by a centralized controller with low computation and communication overhead.

National Category
Embedded Systems
Identifiers
urn:nbn:se:kth:diva-161076 (URN)10.1109/MASCOTS.2007.3 (DOI)2-s2.0-57849115308 (Scopus ID)
Conference
the Modelling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
2. A Novel Congestion Control Scheme for Elastic Flows in Network-on-Chip Based on Sum-Rate Optimization
Open this publication in new window or tab >>A Novel Congestion Control Scheme for Elastic Flows in Network-on-Chip Based on Sum-Rate Optimization
2007 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Network-on-Chip (NoC) has been proposed as an attractive alternative to traditional dedicated busses in order to achieve modularity and high performance in the future System-on-Chip (SoC) designs. Recently, end-to-end congestion control has gained popularity in the design process of network-on-chip based SoCs. This paper addresses a congestion control scenario under traffic mixture which is comprised of Best Effort (BE) traffic or elastic flow and Guaranteed Service (GS) traffic or inelastic flow. We model the desired BE source rates as the solution to a rate-sum maximization problem which is constrained with link capacities while preserving GS traffic services requirements at the desired level. We proposed an iterative algorithm as the solution to the maximization problem which has the advantage of low complexity and fast convergence. The proposed algorithm may be implemented by a centralized controller with low computation and communication overhead.

Series
Lecture notes in computer science, 4704
National Category
Embedded Systems
Identifiers
urn:nbn:se:kth:diva-161077 (URN)10.1007/978-3-540-74484-9_35 (DOI)978-3-540-74482-5 (ISBN)
Conference
International Conference on Computational Science and its Applications (ICCSA)
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
3. Proportionally Fair Best Effort Flow Control in Network-on-Chip Architectures
Open this publication in new window or tab >>Proportionally Fair Best Effort Flow Control in Network-on-Chip Architectures
2008 (English)In: IPDPS Miami 2008: Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, 2008Conference paper, Published paper (Refereed)
Abstract [en]

The research community has recently witnessed the emergence of multi-processor system on chip (MPSoC) platforms consisting of a large set of embedded processors. Particularly, Interconnect networks methodology based on Network-on-Chip (NoC) in MP-SoC design is imminent to achieve high performance potential. More importantly, many well established schemes of networking and distributed systems inspire NoC design methodologies. Employing end-to-end congestion control is becoming more imminent in the design process of NoCs. This paper presents a centralized congestion scheme in the presence of both elastic and streaming flow traffic mixture. In this paper, we model the desired Best Effort (BE) source rates as the solution to a utility maximization problem which is constrained with link capacities while preserving Guaranteed Service (GS) traffics services requirements at the desired level. We proposed an iterative algorithm as the solution to the maximization problem which has the benefit of low complexity and fast convergence. The proposed algorithm may be implemented by a centralized controller with low computation and communication overhead.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161078 (URN)10.1109/IPDPS.2008.4536499 (DOI)2-s2.0-51049097478 (Scopus ID)978-1-4244-1694-3 (ISBN)
Conference
International Workshop on Performance Modeling, Evaluation, and Optimization of Ubiquitous Computing and Networked Systems ( PMEO UCNS)
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
4. A Novel Congestion Control Scheme in Network-on-Chip Based on Best Effort Delay-Sum Optimization
Open this publication in new window or tab >>A Novel Congestion Control Scheme in Network-on-Chip Based on Best Effort Delay-Sum Optimization
2008 (English)In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, 2008, 191-196 p.Conference paper, Published paper (Refereed)
Abstract [en]

With the advances of the semiconductor technology, the enormous number of transistors available on a single chip allows designers to integrate dozens of IP blocks together with large amounts of embedded memory. This has been led to the concept of network on a chip (NoC), in which different modules would be connected by a simple network of shared links and routers and is considered as a solution to replace traditional bus-based architectures to address the global communication challenges in nanoscale technologies. In NoC architectures, controlling congestion of the best effort traffic will continue to be an important design goal. Towards this, employing end-to-end congestion control is becoming more imminent in the design process of NoCs. In this paper, we introduce a centralized algorithm based on the delay minimization of best effort sources. The proposed algorithm can be used as a mechanism to control the flow of best effort source rates by which the sum of propagation delays of network is to be minimized.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161079 (URN)10.1109/I-SPAN.2008.45 (DOI)2-s2.0-49149097088 (Scopus ID)978-0-7695-3125-0 (ISBN)
Conference
International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN)
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
5. Max-Min-Fair Best Effort Flow Control in Network-on-Chip Architectures
Open this publication in new window or tab >>Max-Min-Fair Best Effort Flow Control in Network-on-Chip Architectures
2008 (English)In: Computational Science – ICCS 2008, 2008, 436-445 p.Conference paper, Published paper (Refereed)
Abstract [en]

Network-on-Chip (NoC) has been proposed as an attractive alternative to traditional dedicated busses in order to achieve modularity and high performance in the future System-on-Chip (SoC) designs. Recently, end to end flow control has gained popularity in the design process of network-on-chip based SoCs. Where flow control is employed, fairness issues need to be considered as well. In fact, one of most difficult aspects of flow control is that of treating all sources fairly when it is necessary to turn traffic away from the network. In this paper, we proposed a flow control scheme which admits Max-Min fairness criterion for all sources. In fact, we formulated Max-Min fairness criterion for the NoC architecture and presented implementation to be used as flow control mechanism.

Series
Lecture notes in computer science, ISSN 0302-9743 ; 5010
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161080 (URN)10.1007/978-3-540-69384-0_49 (DOI)2-s2.0-47749155242 (Scopus ID)978-354069383-3 (ISBN)
Conference
8th International Conference on Computational Science, ICCS 2008; Krakow; Poland
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
6. A Novel Flow Control Scheme for Best Effort Traffics in Network-on-Chip Based on Weighted Max-Min Fairness
Open this publication in new window or tab >>A Novel Flow Control Scheme for Best Effort Traffics in Network-on-Chip Based on Weighted Max-Min Fairness
2008 (English)In: 2008 International Symposium on Telecommunications, 2008, 458-463 p.Conference paper, Published paper (Refereed)
Abstract [en]

Network on chip (NoC) has been proposed as an attractive alternative to traditional dedicated busses in order to achieve modularity and high performance in the future system-on-chip (SoC) designs. Recently, end to end flow control has gained popularity in the design process of network-on-chip based SoCs. Where flow control is employed, fairness issues need to be considered as well. In fact, one of most difficult aspects of flow control is that of treating all sources fairly when it is necessary to turn traffic away from the network. In this paper, we propose a flow control scheme which admits max-min fairness criterion for all sources. In fact, we formulate weighted max-min fairness criterion for the NoC architecture and present implementation to be used as flow control mechanism.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161081 (URN)10.1109/ISTEL.2008.4651346 (DOI)000262259200085 ()2-s2.0-67650503521 (Scopus ID)978-1-4244-2750-5 (ISBN)
Conference
2008 International Symposium on Telecommunications, IST 2008; Tehran; Iran
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
7. Throughput-fairness tradeoff in Best Effort flow control for on-chip architectures
Open this publication in new window or tab >>Throughput-fairness tradeoff in Best Effort flow control for on-chip architectures
2009 (English)In: IPDPS 2009: Proceedings of the 2009 IEEE International Parallel and Distributed Processing Symposium, 2009Conference paper, Published paper (Refereed)
Abstract [en]

We consider two flow control schemes for Best Effort traffic in on-chip architectures, which can be deemed as the solutions to the boundary extremes of a class of utility maximization problem. At one extreme, we consider the so-called Rate-Sum flow control scheme, which aims at improving the performance of the underlying system by roughly maximizing throughput while satisfying capacity constraints. At the other extreme, we deem the Max-Min flow control, whose concern is to maintain Max-Min fairness in rate allocation by fairly sacrificing the throughput. We then elaborate our argument through a weighting mechanism in order to achieve a balance between the orthogonal goals of performance and fairness. Moreover, we investigate the implementation facets of the presented flow control schemes in on-chip architectures. Finally, we validate the proposed flow control schemes and the subsequent arguments through extensive simulation experiments.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161082 (URN)10.1109/IPDPS.2009.5161186 (DOI)2-s2.0-70449810244 (Scopus ID)978-1-4244-3750-4 (ISBN)
Conference
International Workshop on Performance Modeling, Evaluation, and Optimization of Ubiquitous Computing and Networked Systems (PMEO UCNS)
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved
8. Optimal Regulation of Traffic Flows in Networks-on-Chip
Open this publication in new window or tab >>Optimal Regulation of Traffic Flows in Networks-on-Chip
2010 (English)In: Proceedings of the Design Automation and Test Europe Conference (DATE), IEEE Computer Society, 2010, 1621-1624 p.Conference paper, Published paper (Refereed)
Abstract [en]

We have proposed (σ, ρ)-based flow regulation to reduce delay and backlog bounds in SoC architectures, where σ bounds the traffic burstiness and ρ the traffic rate. The regulation is conducted per-flow for its peak rate and traffic burstiness. In this paper, we optimize these regulation parameters in networks on chips where many flows may have conflicting regulation requirements. We formulate an optimization problem for minimizing total buffers under performance constraints. We solve the problem with the interior point method. Our case study results exhibit 48% reduction of total buffers and 16% reduction of total latency for the proposed problem. The optimization solution has low run-time complexity, enabling quick exploration of large design space.

Place, publisher, year, edition, pages
IEEE Computer Society, 2010
Series
Design, Automation, and Test in Europe Conference and Exhibition. Proceedings, ISSN 1530-1591
Keyword
Flow regulation, In-network, Interior point methods, Large designs, Optimization problems, Optimization solution, Performance constraints, Runtimes, SoC architecture, Traffic burstiness, Traffic flow, Traffic rate
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-63677 (URN)2-s2.0-77953098329 (Scopus ID)978-398108016-2 (ISBN)
Conference
DATE '10, Conference on Design, Automation and Test in Europe. Dresden, Germany. 8-12 March 2010
Note

QC 20120425

Available from: 2012-01-24 Created: 2012-01-24 Last updated: 2015-03-10Bibliographically approved
9. Output Process of Variable Bit-Rate Flows in On-Chip Networks Based on Aggregate Scheduling
Open this publication in new window or tab >>Output Process of Variable Bit-Rate Flows in On-Chip Networks Based on Aggregate Scheduling
2011 (English)In: Proceedings of the International Conference on Computer Design, 2011, 445-446 p.Conference paper, Published paper (Refereed)
Abstract [en]

 In NoCs often several flows are merged into one aggregate flow due to heavy resource sharing. For strengthening formal performance analysis, we propose an improved model for an output flow of a FIFO multiplexer under aggregate scheduling. The model of the aggregate flow is formally proven and can serve as the basis for a stringent worst case delay and buffer analysis.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-63676 (URN)10.1109/ICCD.2011.6081442 (DOI)000298257400076 ()2-s2.0-83455244341 (Scopus ID)978-1-4577-1952-3 (ISBN)
Conference
IEEE 29th International Conference on Computer Design (ICCD)
Note

Key: Nostrum. QC 20120201

Available from: 2012-01-24 Created: 2012-01-24 Last updated: 2015-03-10Bibliographically approved
10. Worst-Case Delay Analysis of Variable Bit-Rate Flows in Network-on-Chip with Aggregate Scheduling
Open this publication in new window or tab >>Worst-Case Delay Analysis of Variable Bit-Rate Flows in Network-on-Chip with Aggregate Scheduling
2012 (English)In: Proceedings of the Design and Test in Europe Conference (DATE), 2012, 538-541 p.Conference paper, Published paper (Refereed)
Abstract [en]

Aggregate scheduling in routers merges several flows into one aggregate flow. We propose an approach for computing the end-to-end delay bound of individual flows in a FIFO multiplexer under aggregate scheduling. A synthetic case study exhibits that the end-to-end delay bound is up to 33.6% tighter than the case without considering the traffic peak behavior.

Series
Design, Automation, and Test in Europe Conference and Exhibition. Proceedings, ISSN 1530-1591
Keyword
Delay analysis, End-to-end delay bounds, Network on chip, Variable bit rate
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-63611 (URN)2-s2.0-84862080160 (Scopus ID)978-398108018-6 (ISBN)
Conference
15th Design, Automation and Test in Europe Conference and Exhibition, DATE 2012; Dresden; Germany; 12 March 2012 through 16 March 2012
Note

QC 20130912

Available from: 2012-01-24 Created: 2012-01-24 Last updated: 2015-03-10Bibliographically approved
11. Proportionally fair flow control mechanism for best effort traffic in network-on-chip architectures
Open this publication in new window or tab >>Proportionally fair flow control mechanism for best effort traffic in network-on-chip architectures
2010 (English)In: International Journal of Parallel, Emergent and Distributed Systems, ISSN 1744-5760, E-ISSN 1744-5779, Vol. 25, no 4, 345-362 p.Article in journal (Refereed) Published
Abstract [en]

The research community has recently witnessed the emergence of multi-processor system on chip (MPSoC) platforms consisting of a large set of embedded processors. Particularly, Interconnect networks methodology based on network-on-chip (NoC) in MPSoC design is imminent to achieve high performance potential. More importantly, many well established schemes of networking and distributed systems inspire NoC design methodologies. Employing end-to-end congestion control is becoming more imminent in the design process of NoCs. This paper presents a centralised congestion control scheme in the presence of both elastic and streaming flow traffic mixture. We model the desired best effort source rates as the solution to an optimisation problem with weighted logarithmic objective which is known to admit proportional fairness criterion. The problem is constrained with link capacities while preserving guaranteed service traffics services requirements at the desired level. We propose an iterative algorithm as the solution to the optimisation problem which has the benefit of low complexity and fast convergence, and can be implemented by a controller unit with low computation and communication overhead.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161083 (URN)10.1080/17445760902894647 (DOI)2-s2.0-77954610437 (Scopus ID)
Note

QC 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2017-12-04Bibliographically approved
12. Buffer Optimization in Network-on-Chip Through Flow Regulation
Open this publication in new window or tab >>Buffer Optimization in Network-on-Chip Through Flow Regulation
2010 (English)In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, ISSN 0278-0070, E-ISSN 1937-4151, Vol. 29, no 12, 1973-1986 p.Article in journal (Refereed) Published
Abstract [en]

For network-on-chip (NoC) designs, optimizing buffers is an essential task since buffers are a major source of cost and power consumption. This paper proposes flow regulation and has defined a regulation spectrum as a means for system-on-chip architects to control delay and backlog bounds. The regulation is performed per flow for its peak rate and burstiness. However, many flows may have conflicting regulation requirements due to interferences with each other. Based on the regulation spectrum, this paper optimizes the regulation parameters aiming for buffer optimization. Three timing-constrained buffer optimization problems are formulated, namely, buffer size minimization, buffer variance minimization, and multiobjective optimization, which has both buffer size and variance as minimization objectives. Minimizing buffer variance is also important because it affects the modularity of routers and network interfaces. A realistic case study exhibits 62.8% reduction of total buffers, 84.3% reduction of total latency, and 94.4% reduction on the sum of variances of buffers. Likewise, the experimental results demonstrate similar improvements in the case of synthetic traffic patterns. The optimization algorithm has low run-time complexity, enabling quick exploration of large design spaces. This paper concludes that optimal flow regulation can be a highly valuable instrument for buffer optimization in NoC designs.

Keyword
Buffer size, buffer variance, interior point method, network-on-chip (NoC), optimization problem
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-27375 (URN)10.1109/TCAD.2010.2063130 (DOI)000284417400011 ()2-s2.0-78649341341 (Scopus ID)
Note
QC 20101213Available from: 2010-12-13 Created: 2010-12-13 Last updated: 2017-12-11Bibliographically approved
13. Least Upper Delay Bound for VBR Flows in Networks-on- Chip with Virtual Channels
Open this publication in new window or tab >>Least Upper Delay Bound for VBR Flows in Networks-on- Chip with Virtual Channels
(English)In: ACM Transactions on Design Automation of Electronic Systems, ISSN 1084-4309, E-ISSN 1557-7309Article in journal (Refereed) Accepted
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161084 (URN)
Note

QS 2015

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2017-12-04Bibliographically approved
14. Weighted Round Robin Configura- tion for Worst-Case Delay Optimization in Network-on-Chip
Open this publication in new window or tab >>Weighted Round Robin Configura- tion for Worst-Case Delay Optimization in Network-on-Chip
(English)Manuscript (preprint) (Other academic)
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-161172 (URN)
Note

QS 20150310

Available from: 2015-03-09 Created: 2015-03-09 Last updated: 2015-03-10Bibliographically approved

Open Access in DiVA

Thesis(16480 kB)3601 downloads
File information
File name FULLTEXT01.pdfFile size 16480 kBChecksum SHA-512
eea886449a5e9a0073ded12388089745da2585667219176fd2813ddb86a3d2b93fbc8b52013346cdef95c8c0f50c0b8de1d48c83e96be3a7bc7d85e3f5601daf
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Jafari, Fahimeh
By organisation
Electronics and Embedded Systems
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 3601 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1174 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