research-article

An ASIP Approach to Path Allocation in TDM NoCs using Adaptive Search Region

Authors:

Gerhard P. FettweisAuthors Info & Claims

GLSVLSI '20: Proceedings of the 2020 on Great Lakes Symposium on VLSI

Pages 463 - 468

https://doi.org/10.1145/3386263.3406936

Published: 07 September 2020 Publication History

Abstract

Dynamic connection allocation in time-division multiplexed network-on-chip(NoC) is a promising approach to provide a guaranteed service in NoC. Most recently, the trellis-search algorithm demonstrated using an application-specific instruction-set processor (ASIP). The processor achieved a considerable performance improvement for searching optimum paths. However, there is still a scalability issue. As network size increases, the path search time is rapidly increased. The purpose of this work is to introduce a relative search algorithm and to investigate its effect on NoC performance. Our proposed algorithm optimizes path search region and position according to the actual source-destination position on the network grid. Consequently, even though the network size is increased, the path search time of our proposed algorithm is gradually raised. The simulation results using 16x16 2D-mesh showed up to 10 thousand times and 3.5 times decreases in average execution cycles against 32bits RISC and ASIP, respectively.

Supplementary Material

MP4 File (3386263.3406936.mp4)

Presentation video

Download
9.07 MB

References

[1]

L. Benini and G. De Micheli. 2002. Networks on chips: a new SoC paradigm. Computer, Vol. 35, 1 (Jan 2002), 70--78. https://doi.org/10.1109/2.976921

Digital Library

[2]

Evgeny Bolotin, Israel Cidon, Ran Ginosar, and Avinoam Kolodny. 2004. QNoC: QoS architecture and design process for network on chip. Journal of Systems Architecture, Vol. 50, 2 (2004), 105 -- 128. https://doi.org/10.1016/j.sysarc.2003.07.004 Special issue on networks on chip.

Digital Library

[3]

Y. Chen, E. Matus, and G. P. Fettweis. 2016a. Centralized parallel multi-path multi-slot allocation approach for TDM NoCs. In 2016 IEEE Canadian Conference on Electrical and Computer Engineering (CCECE). 1--5.

[4]

Y. Chen, E. Matus, and G. P. Fettweis. 2016b. Trellis-search based dynamic multi-path connection allocation for TDM-NoCs. In 2016 International Great Lakes Symposium on VLSI (GLSVLSI). 323--328.

[5]

Y. Chen, E. Matus, and G. P. Fettweis. 2017a. Combined packet and TDM circuit switching NoCs with novel connection configuration mechanism. In 2017 IEEE International Symposium on Circuits and Systems (ISCAS). 1--4. https://doi.org/10.1109/ISCAS.2017.8050829

[6]

Y. Chen, E. Matus, and G. P. Fettweis. 2017b. Register-Exchange Based Connection Allocator for Circuit Switching NoCs. In 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP). 559--566.

[7]

Y. Chen, E. Matus, S. Moriam, and G. P. Fettweis. 2020. High Performance Dynamic Resource Allocation for Guaranteed Service in Network-on-Chips. IEEE Transactions on Emerging Topics in Computing, Vol. 8, 2 (2020), 503--516.

[8]

K. Goossens, J. Dielissen, and A. Radulescu. 2005. AEthereal network on chip: concepts, architectures, and implementations. IEEE Design Test of Computers, Vol. 22, 5 (2005), 414--421.

Digital Library

[9]

K. Goossens and A. Hansson. 2010. The aethereal network on chip after ten years: Goals, evolution, lessons, and future. In Design Automation Conference. 306--311.

[10]

Jan Heißwolf. 2014. A Scalable and Adaptive Network on Chip for Many-Core Architectures. Ph.D. Dissertation. Karlsruher Institut fur Technologie.

[11]

S. Liu, A. Jantsch, and Z. Lu. 2012. Parallel probing: Dynamic and constant time setup procedure in circuit switching NoC. In 2012 Design, Automation Test in Europe Conference Exhibition (DATE). 1289--1294.

[12]

S. Liu, A. Jantsch, and Z. Lu. 2014. Parallel probe based dynamic connection setup in TDM NoCs. In 2014 Design, Automation Test in Europe Conference Exhibition (DATE). 1--6.

[13]

Z. Lu and A. Jantsch. 2008. TDM Virtual-Circuit Configuration for Network-on-Chip. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 16, 8 (2008), 1021--1034.

Digital Library

[14]

A. K. Lusala and J. Legat. 2011. Combining sdm-based circuit switching with packet switching in a NoC for real-time applications. In 2011 IEEE International Symposium of Circuits and Systems (ISCAS). 2505--2508.

[15]

S. Nam, E. Matus, and G. P. Fettweis. 2019. Application Specific Instruction Processor for Dynamic Connection Allocation in TDM-NoCs. In 2019 32nd IEEE International System-on-Chip Conference (SOCC). 33--38.

[16]

J. Sparsø, E. Kasapaki, and M. Schoeberl. 2013. An area-efficient network interface for a TDM-based Network-on-Chip. In 2013 Design, Automation Test in Europe Conference Exhibition (DATE). 1044--1047.

[17]

R.A. Stefan. 2012. Resource Allocation in Time-Division-Multiplexed Networks on Chip. Ph.D. Dissertation. Delft University of Technology, Mekelweg 5, 2628 CD Delft, Niederlande. http://resolver.tudelft.nl/uuid:63251f1a-8c42--4153--94f4-c85c92a8e950

[18]

Radu Stefan, Ashkan Beyranvand Nejad, and Kees Goossens. 2012. Online Allocation for Contention-Free-Routing NoCs. In Proceedings of the 2012 Interconnection Network Architecture: On-Chip, Multi-Chip Workshop (INA-OCMC '12). Association for Computing Machinery, New York, NY, USA, 13--16. https://doi.org/10.1145/2107763.2107767

Digital Library

[19]

M. Winter and G. P. Fettweis. 2011. Guaranteed service virtual channel allocation in NoCs for run-time task scheduling. In 2011 Design, Automation Test in Europe. 1--6.

[20]

Steven Cameron Woo, Moriyoshi Ohara, Evan Torrie, Jaswinder Pal Singh, and Anoop Gupta. 1995. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22nd Annual International Symposium on Computer Architecture (ISCA '95). Association for Computing Machinery, New York, NY, USA, 24--36. https://doi.org/10.1145/223982.223990

Digital Library

Cited By

Nam SMatus EFettweis G(2021)Minimized Region of Path-search Algorithm for ASIP-based Connection Allocator in NoCs2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI51109.2021.00073(368-373)Online publication date: Jul-2021
https://doi.org/10.1109/ISVLSI51109.2021.00073

Index Terms

An ASIP Approach to Path Allocation in TDM NoCs using Adaptive Search Region
1. Hardware
  1. Very large scale integration design
    1. Design reuse and communication-based design
      1. Network on chip

Recommendations

P-NoC: Performance Evaluation and Design Space Exploration of NoCs for Chip Multiprocessor Architecture Using FPGA
Abstract
The network-on-chip (NoC) has emerged as an efficient and scalable communication fabric for chip multiprocessors (CMPs) and multiprocessor system on chips (MPSoCs). The NoC architecture, the routers micro-architecture and links influence the ...
Enhancing Butterfly Fat Tree NoCs for FPGAs with Lightweight Flow Control
FPGA '19: Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

FPGA overlay networks-on-chip (NoCs) based on Butterfly Fat Tree (BFT) topology and lightweight flow control can outperform state-of-the-art FPGA NoCs, such as Hoplite and others, on metrics such as throughput, latency, cost and power efficiency, and ...
A shortest path adaptive routing technique for minimizing path collisions in hybrid optical network-on-chip

Hybrid optical network-on-chip (HONoC) is a promising alternative to all-electrical NoC whose capability in the performance and the power consumption is facing ultimate physical limitation. However, the latency unfairness problem and the associated ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

GLSVLSI '20: Proceedings of the 2020 on Great Lakes Symposium on VLSI

September 2020

597 pages

ISBN:9781450379441

DOI:10.1145/3386263

General Chairs:
Tinoosh Mohsenin
University of Maryland, Baltimore County, USA
,
Weisheng Zhao
Beihang University, China
,
Program Chairs:
Yiran Chen
Duke University, USA
,
Onur Mutlu
ETH Zurich, Switzerland

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 September 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Federal Ministry of Education and Research of the Federal Republic of Germany (BMBF)

Conference

GLSVLSI '20

GLSVLSI '20: Great Lakes Symposium on VLSI 2020

September 7 - 9, 2020

Virtual Event, China

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
59
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nam SMatus EFettweis G(2021)Minimized Region of Path-search Algorithm for ASIP-based Connection Allocator in NoCs2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI51109.2021.00073(368-373)Online publication date: Jul-2021
https://doi.org/10.1109/ISVLSI51109.2021.00073

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents