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
New circuit switching techniques in on-chip networks
KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.ORCID iD: 0000-0001-7966-6128
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Network on Chip (NoC) is proposed as a promising technology to address the communication challenges in deep sub-micron era. NoC brings network-based communication into the on-chip environment and tackles the problems like long wire complexities, bandwidth scaling and so on. After more than a decade's evolution and development, there are many NoC architectures and solutions available. Nevertheless, NoCs can be classi_ed into two categories: packet switched NoC and circuit switched NoC. In this thesis, targeting circuit switched NoC, we present our innovations and considerations on circuit switched NoCs in three areas, namely, connection setup method, time division multiplexing (TDM) technology and spatial division multiplexing (SDM) technology.

Connection setup technique deeply inuences the architecture and performance of a circuit switched NoC, since circuit switched NoC requires to set up connections before launching data transfer. We propose a novel parallel probe based method for dynamic distributed connection setup. This setup method on one hand searches all the possible minimal paths in parallel. On the other hand, it also has a mechanism to reduce resource occupation during the path search process by reclaiming redundant paths. With this setup method, connections are more likely to be established because of the exploration on the path diversity.

TDM based NoC constitutes a sub-category of circuit switched NoC. We propose a double time-wheel technique to facilitate a probe based connection setup in TDM NoCs. With this technique, path search algorithms used in connection setup are no longer limited to deterministic routing algorithms. Moreover, the hardware cost can be reduced, since setup requests and data flows can co-exist in one network. Apart from the double time-wheel technique for connection setup, we also propose a highway technique that can enhance the slot utilization during data transfer. This technique can accelerate the transfer of a data flow while maintaining the throughput guarantee and the packet order.

SDM based NoC constitutes another sub-category of circuit switched NoC. SDM NoC can benefit from high clock frequency and simple synchronization efforts. To better support the dynamic connection setup in SDM NoCs, we design a single cycle allocator for channel allocation inside each router. This allocator can guarantee both strong fairness and maximal matching quality. We also build up a circuit switched NoC, which can support multiple channels and multiple networks, to study different ways of organizing channels and setting up connections. Finally, we make a comparison between circuit switched NoC and packet switched NoC. We show the strengths and weaknesses on each of them by analysis and evaluation.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. , xvi, 82 p.
Series
TRITA-ICT-ECS AVH, ISSN 1653-6363 ; 2015:18
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-176624ISBN: 978-91-7595-727-2 (print)OAI: oai:DiVA.org:kth-176624DiVA: diva2:867998
Public defence
2015-12-04, Sal A, Elektrum, KTH-ICT, Kista, 09:00 (English)
Opponent
Supervisors
Note

QC 20151109

Available from: 2015-11-09 Created: 2015-11-09 Last updated: 2015-11-09Bibliographically approved
List of papers
1. Parallel Probing: Dynamic and constant time setup procedure in circuit switching NoC
Open this publication in new window or tab >>Parallel Probing: Dynamic and constant time setup procedure in circuit switching NoC
2012 (English)In: Design, Automation & Test in Europe Conference & Exhibition (DATE), 2012, IEEE Computer Society, 2012, 1289-1294 p.Conference paper, Published paper (Refereed)
Abstract [en]

We propose a circuit switching Network-on-chip with a parallel probe searching setup method, which can search the entire network in constant time, only dependent on the network size but independent of the network load. Under a specific search policy, the setup procedure is guaranteed to terminate in time 3D+6 cycles, where D is the geometric distance between source and destination. If a path can be found, the method succeeds in 3D+6 cycles; if a path cannot be found, it fails in maximum 3D+6 cycles. Compared to previous work, our method can reduce the setup time and enhance the success rate of setups. Our experiments show that compared with a sequential probe searching method, this method can reduce the search time by up to 20%. Compared with a centralized channel allocator method, this method can enhance the success rate by up to 20%.

Place, publisher, year, edition, pages
IEEE Computer Society, 2012
Series
Design, Automation, and Test in Europe Conference and Exhibition. Proceedings, ISSN 1530-1591
Keyword
Allocators, Circuit switching, Constant time, Geometric distances, Network load, Network on chip, Network size, Parallel probing, Search time, Searching methods, Set-up time
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-63610 (URN)10.1109/DATE.2012.6176691 (DOI)2-s2.0-84862111830 (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 20130114

Available from: 2012-01-24 Created: 2012-01-24 Last updated: 2015-11-09Bibliographically approved
2. Parallel probe based dynamic connection setup in TDM NoCs
Open this publication in new window or tab >>Parallel probe based dynamic connection setup in TDM NoCs
2014 (English)Conference paper, Published paper (Refereed)
Abstract [en]

We propose a Time-Division Multiplexing (TDM) based connection oriented NoC with a novel double time-wheel router architecture combined with a run-time parallel probing setup method. In comparison with traditional TDM connection setup methods, our design has the following advantages: (1) it allocates paths and time slots at run-time; (2) it is fast with predictable and bounded setup latency; (3) it avoids additional resources (no auxiliary network or central processor to find and manage connections); (4) it is fully distributed and therefore it scales nicely with network size. Compared to a packet based setup method, our probe based design can reduce path setup delay by 81% and increase network load by 110% in an 8×8 mesh, while avoiding the auxiliary network. Compared to a centralized method, our solution can double the success rate, while eliminating the central resource for path setup and reducing the wire overhead. Synthesis results suggest that our design is faster and smaller than all comparable solutions.

Series
Proceedings -Design, Automation and Test in Europe, DATE, ISSN 1530-1591 ; 6800453
Keyword
Design, Network architecture, Probes, Auxiliary network, Central processors, Connection oriented, Connection setup, Network size, Packet-based, Parallel probing, Router architecture, Network-on-chip
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-167563 (URN)10.7873/DATE2014.252 (DOI)000354965500239 ()2-s2.0-84903849861 (Scopus ID)9783981537024 (ISBN)
Conference
17th Design, Automation and Test in Europe, DATE 2014, 24 - 28 March 2014, Dresden
Note

QC 20150602. QC 20160208

Available from: 2015-06-02 Created: 2015-05-22 Last updated: 2016-02-08Bibliographically approved
3. Highway in TDM NoCs
Open this publication in new window or tab >>Highway in TDM NoCs
2015 (English)In: Proceedings of the Ninth ACM/IEEE International Symposium on Networks-on-Chip (NoCS'15), ACM Digital Library, 2015Conference paper, Published paper (Refereed)
Abstract [en]

TDM (Time Division Multiplexing) is a well-known technique to provide QoS guarantees in NoCs. However, unused time slots commonly exist in TDM NoCs. In the paper, we propose a TDM highway technique which can enhance the slot utilization of TDM NoCs. A TDM highway is an express TDM connection composed of special buffer queues, called highway channels (HWCs). It can enhance the throughput and reduce data transfer delay of the connection, while keeping the quality of service (QoS) guarantee on minimum bandwidth and in-order packet delivery. We have developed a dynamic and repetitive highway setup policy which has no dependency on particular TDM NoC techniques and no overhead on traffic flows. As a result, highways can be efficiently established and utilized in various TDM NoCs.

According to our experiments, compared to a traditional TDM NoC, adding one HWC with two buffers to every input port of routers in an 8×8 mesh can reduce data delay by up to 80% and increase the maximum throughput by up to 310%. More improvements can be achieved by adding more HWCs per input per router, or more buffers per HWC. We also use a set of MPSoC application benchmarks to evaluate our highway technique. The experiment results suggest that with highway, we can reduce application run time up to 51%.

Place, publisher, year, edition, pages
ACM Digital Library, 2015
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-176630 (URN)10.1145/2786572.2786577 (DOI)2-s2.0-84984653822 (Scopus ID)978-1-4503-3396-2 (ISBN)
Conference
the 9th International Symposium on Networks-on-Chip, Vancouver, Canada, 2015
Note

QC 20151109

Available from: 2015-11-09 Created: 2015-11-09 Last updated: 2016-11-22Bibliographically approved
4. A Fair and Maximal Allocator for Single-Cycle On-Chip Homogeneous Resource Allocation
Open this publication in new window or tab >>A Fair and Maximal Allocator for Single-Cycle On-Chip Homogeneous Resource Allocation
2014 (English)In: IEEE Transactions on Very Large Scale Integration (vlsi) Systems, ISSN 1063-8210, E-ISSN 1557-9999, Vol. 23, no 10, 2229-2233 p.Article in journal (Refereed) Published
Abstract [en]

Traditional allocators for network-on-chip (NoC) routers suffer from either poor-matching quality or limited fairness. We propose a waterfall (WTF) allocator targeting homogeneous resource allocation, which provides single-cycle maximal matching while guaranteeing strong fairness based on the round-robin principle. It can be implemented with a loop-free structure. In 90 nm technology, the allocator operates at about 1 GHz clock frequency. We compare WTF with wave-front, separable-input-first, and separable-output-first allocators and find that it is at least 10% smaller, has 50% less delay under high load, and uses 3% less power than any of these alternatives. Also, WTF is at least as fair or clearly fairer. We also find that in a 4 x 4 circuit switched NoC the use of WTF gives up to 20% higher network performance.

Keyword
Allocator, fairness, maximal matching, network-on-chip (NoC), round-robin
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-155469 (URN)10.1109/TVLSI.2013.2284563 (DOI)000343014100020 ()2-s2.0-84907660701 (Scopus ID)
Note

QC 20141112

Available from: 2014-11-12 Created: 2014-11-06 Last updated: 2017-12-05Bibliographically approved
5. MultiCS: Circuit switched NoC with multiple sub-networks and sub-channels
Open this publication in new window or tab >>MultiCS: Circuit switched NoC with multiple sub-networks and sub-channels
2015 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165Article in journal (Refereed) Published
Abstract [en]

We propose a multi-channel and multi-network circuit switched NoC (MultiCS) with a probe searching setup method to explore different channel partitioning and configuration policies. Our design has a variable number of channels which can be configured either as sub-channels (spatial division multiplexing channels) or sub-networks. Packets can be delivered on an established connection with one or multiple channels. An adaptive channel allocation scheme, which determines a connection width according to the dynamic use of channels, can greatly reduce the delay, compared to a deterministic allocation scheme. However, the latter can offer exact connection width as requested. The benefits and burden of using different number of channels and configurations are studied by analysis and experiments. Our experimental results show that sub-network configurations are superior to sub-channel configurations in delay and throughput, when working at the highest clock frequency of each configuration. Under reasonable channel partitioning, sub-networks with narrow channels can generally achieve higher throughput than the network using single wide channels.

Place, publisher, year, edition, pages
Elsevier, 2015
Keyword
Circuit switched, Multi-channel, NoC, SDM, Network-on-chip, Switching circuits, Adaptive channel allocation, Channel partitioning, Clock frequency, Multi channel, Multiple channels, Spatial Division Multiplexing, Space division multiple access
National Category
Computer Engineering
Identifiers
urn:nbn:se:kth:diva-175655 (URN)10.1016/j.sysarc.2015.07.013 (DOI)000364271900004 ()2-s2.0-84944148936 (Scopus ID)
Note

QC 20151023

Available from: 2015-10-23 Created: 2015-10-19 Last updated: 2017-12-01Bibliographically approved
6. Analysis and evaluation of circuit switched NoC and packet switched NoC
Open this publication in new window or tab >>Analysis and evaluation of circuit switched NoC and packet switched NoC
2013 (English)In: Proceedings - 16th Euromicro Conference on Digital System Design, DSD 2013, IEEE , 2013, 21-28 p.Conference paper, Published paper (Refereed)
Abstract [en]

Circuit switched NoC has, compared to packet switching, a longer setup time, guaranteed throughput and latency, higher clock frequency, lower HW complexity, and higher energy efficiency. Depending on packet size and throughput requirements they exhibit better or worse performance. In this paper we designed a circuit switched NoC and compared that with packet switched NoC. By speculation and analysis, we propose that, as packet size increases, performance decreases for packet switched NoC, while it increases for circuit switched NoC. By close examination on the router architecture, we suggest that circuit switched NoC can operate at a higher clock frequency than packet switched NoC, and thus at zero load above a certain packet size circuit switched NoC could be better than packet switched NoC in packet delay. Experiment results support our intuitions and analysis. We find the cross-over point, above which circuit switching has lower latency, is around 30 flits/packet under low load and 60-70 flits/packet under high network load.

Place, publisher, year, edition, pages
IEEE, 2013
Series
IEEE International Conference on Robotics and Automation, ISSN 1050-4729
Keyword
Analysis and evaluation, Circuit switching, Clock frequency, Guaranteed throughputs, Network load, Packet delay, Packet-switched, Router architecture
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-139421 (URN)10.1109/DSD.2013.13 (DOI)000337235200003 ()2-s2.0-84890067489 (Scopus ID)978-076955074-9 (ISBN)
Conference
16th Euromicro Conference on Digital System Design, DSD 2013; Santander; Spain; 4 September 2013 through 6 September 2013
Note

QC 20140116

Available from: 2014-01-16 Created: 2014-01-13 Last updated: 2015-11-09Bibliographically approved

Open Access in DiVA

Shaoteng_ICT_ESY(4604 kB)286 downloads
File information
File name FULLTEXT02.pdfFile size 4604 kBChecksum SHA-512
0b0e181aa281d4d691036b37de680ad6d31fa012eb0b8a44611157ec437b05d2a38f220aa95dd3b709ba97f7861bcca6506a8441cee142f31e9de7c999caf3dc
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Shaoteng, Liu
By organisation
Electronics and Embedded Systems
Computer Systems

Search outside of DiVA

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