Change search
Link to record
Permanent link

Direct link
BETA
Holsmark, Rickard
Publications (10 of 21) Show all publications
Holsmark, R., Kumar, S. & Palesi, M. (2010). A Multi-Level Routing Scheme and Router Architecture to support Hierarchical Routing in Large Network on Chip Platforms. In: 4th Workshop on Highly Parallel Processing on a Chip (HPPC 2010). Paper presented at 4th Workshop on Highly Parallel Processing on a Chip (HPPC 2010).
Open this publication in new window or tab >>A Multi-Level Routing Scheme and Router Architecture to support Hierarchical Routing in Large Network on Chip Platforms
2010 (English)In: 4th Workshop on Highly Parallel Processing on a Chip (HPPC 2010), 2010Conference paper, Published paper (Refereed)
Abstract [en]

The concept of hierarchical networks is useful for designing a large heterogeneous NoC by reusing predesigned small NoCs as subnets. It can also be helpful when analyzing and designing a large NoC as interconnection of subnets at a higher level of abstraction. Hierarchical deadlock-free routing is required to enable deadlock-free interconnection of sub-networks with different internal routing algorithms. In this paper we show that multi-level addressing is a cost-effective implementation option for hierarchical deadlock-free routing. We propose a two-level routing scheme, which is not only efficient, but also  enables co-existence of algorithmic and table-based implementation in one router. A hierarchical view of the network simplifies addressing of network nodes and address decoding in the router. Synthesis results show that a 2-level hierarchical router design for an 8x8 NoC, can reduce area and power requirements by  up to ~20%, as compared to a router for the flat network. This work also proposes a new possibility for increasing the number of nodes available for subnet-to-subnet interfaces, while keeping the properties of hierarchical deadlock-freedom. We evaluate and discuss the communication performance in a 2-level hierarchical network for various subnet interface set-ups and traffic situations. A cycle accurate simulator has been developed and used for this purpose.

Keywords
Networks on Chip, Hierarchical Networks, Deadlock Free Routing, Router Architecture
National Category
Computer Engineering Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:hj:diva-13124 (URN)
Conference
4th Workshop on Highly Parallel Processing on a Chip (HPPC 2010)
Available from: 2010-09-17 Created: 2010-09-14 Last updated: 2018-01-12Bibliographically approved
Palesi, M., Holsmark, R., Wang, X., Kumar, S., Yang, M., Jiang, Y. & Catania, V. (2010). A Novel Mechanism to Guarantee In-Order Packet Delivery with Adaptive Routing Algorithms in Networks on Chip. In:  13th Euromicro Conference On Digital System Design Architectures, Methods and Tools. Paper presented at 13th Euromicro Conference On Digital System Design Architectures, Methods and Tools Lille, France, 1-3 September, 2010.
Open this publication in new window or tab >>A Novel Mechanism to Guarantee In-Order Packet Delivery with Adaptive Routing Algorithms in Networks on Chip
Show others...
2010 (English)In:  13th Euromicro Conference On Digital System Design Architectures, Methods and Tools, 2010Conference paper, Published paper (Refereed)
Abstract [en]

Although adaptive routing algorithms promise higher communication performance, as compared to deterministic routing algorithms, they suffer from the out-of-order packet delivery problem. In the context of Network on Chip, the area and computational overhead of ordering packets at the destination is high and may reverse any gain achieved through the use of adaptivity of the routing algorithm. In this paper, we describe a novel scheme for ensuring in-order packet delivery while retaining the performance advantages of adaptive routing. The hardware architecture of a router that supports the proposed scheme is described. Although the basic idea in our proposal is topology independent we evaluate and compare the performance of our scheme with both deterministic as well as adaptive routing algorithms for 2D mesh NoC. As compared to the XY routing algorithm, our technique significantly reduces the packet delay and improves the saturation point. The impact on router area and power dissipation is also discussed. Although the power consumption of routers increase, the energy consumption per flit increases less than 2% on average, since the higher performance allows for draining more traffic during a certain time window.

Keywords
Keywords-Network on Chip, Routing Algorithm, Router Design, Performance Analysis, Adaptivity, In-order packet delivery
National Category
Computer Engineering Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:hj:diva-13127 (URN)
Conference
13th Euromicro Conference On Digital System Design Architectures, Methods and Tools Lille, France, 1-3 September, 2010
Available from: 2010-09-14 Created: 2010-09-14 Last updated: 2018-01-12
Palesi, M., Holsmark, R., Kumar, S. & Catania, V. (2009). Application Specific Routing Algorithms for Networks on Chip. IEEE Transactions on Parallel and Distributed Systems, 20(3), 316-330
Open this publication in new window or tab >>Application Specific Routing Algorithms for Networks on Chip
2009 (English)In: IEEE Transactions on Parallel and Distributed Systems, ISSN 1045-9219, E-ISSN 1558-2183, Vol. 20, no 3, p. 316-330Article in journal (Refereed) Published
Abstract [en]

In this paper we present a methodology to develop efficient and deadlock free routing algorithms for Network-on-Chip (NoC) platforms which are specialized for an application or a set of concurrent applications. The proposed methodology, called application specific routing algorithm (APSRA), exploits the application specific information regarding pairs of cores which communicate and other pairs which never communicate in the NoC platform to maximize communication adaptivity and performance. The methodology also exploits the known information regarding concurrency/non-concurrency of communication transactions among cores for the same purpose. We demonstrate, through analysis of adaptivity as well as simulation based evaluation of latency and throughput, that algorithms produced by the proposed methodology give significantly higher performance as compared to other deadlock free algorithms for both homogeneous as well as heterogeneous 2D mesh topology NoC systems. For example, for homogeneous mesh NoC, APSRA results in approximately 30% less average delay as compared to odd-even algorithm just below saturation load. Similarly the saturation load point for APSRA is significantly higher as compared to other adaptive routing algorithms for both homogeneous and non-homogeneous mesh networks.

Place, publisher, year, edition, pages
New York: IEEE Computer Society, 2009
Keywords
2D mesh topology, adaptive routing algorithms, application specific routing algorithms, deadlock free routing algorithms, network-on-chip platforms
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Computer Sciences
Identifiers
urn:nbn:se:hj:diva-10927 (URN)10.1109/TPDS.2008.106 (DOI)
Available from: 2009-11-26 Created: 2009-11-26 Last updated: 2018-01-12Bibliographically approved
Holsmark, R. (2009). Deadlock Free Routing in Mesh Networks on Chip with Regions. (Licentiate dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Deadlock Free Routing in Mesh Networks on Chip with Regions
2009 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

There is a seemingly endless miniaturization of electronic components, which has enabled designers to build sophisticated computing structureson silicon chips. Consequently, electronic systems are continuously improving with new and more advanced functionalities. Design complexity ofthese Systems on Chip (SoC) is reduced by the use of pre-designed cores. However, several problems related to the interconnection of coresremain. Network on Chip (NoC) is a new SoC design paradigm, which targets the interconnect problems using classical network concepts. Still,SoC cores show large variance in size and functionality, whereas several NoC benefits relate to regularity and homogeneity.

This thesis studies some network aspects which are characteristic to NoC systems. One is the issue of area wastage in NoC due to cores of varioussizes. We elaborate on using oversized regions in regular mesh NoC and identify several new design possibilities. Adverse effects of regions oncommunication are outlined and evaluated by simulation.

Deadlock freedom is an important region issue, since it affects both the usability and performance of routing algorithms. The concept of faultyblocks, used in deadlock free fault-tolerant routing algorithms has similarities with rectangular regions. We have improved and adopted one suchalgorithm to provide deadlock free routing in NoC with regions. This work also offers a methodology for designing topology agnostic, deadlockfree, highly adaptive application specific routing algorithms. The methodology exploits information about communication among tasks of anapplication. This is used in the analysis of deadlock freedom, such that fewer deadlock preventing routing restrictions are required.

A comparative study of the two proposed routing algorithms shows that the application specific algorithm gives significantly higher performance.But, the fault-tolerant algorithm may be preferred for systems requiring support for general communication. Several extensions to our work areproposed, for example in areas such as core mapping and efficient routing algorithms. The region concept can be extended for supporting reuse ofa pre-designed NoC as a component in a larger hierarchical NoC.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2009. p. 127
Series
Linköping Studies in Science and Technology, ISSN 0280-7971 ; 1410
Keywords
Networks on Chip, Mesh Topology, Routing Algorithms, Wormhole Switching, Deadlock, Application Specific Routing
National Category
Information Systems
Identifiers
urn:nbn:se:hj:diva-11602 (URN)9789173935593 (ISBN)
Presentation
2009-09-14, Tekniska Högskolan, Jönköping, 14:00 (English)
Opponent
Supervisors
Note
Preliminärgranskad av LaAd Available from: 2010-02-10 Created: 2010-02-10 Last updated: 2018-01-12Bibliographically approved
Holsmark, R., kumar, S., Palesi, M. & Mejia, A. (2009). HiRA: A methodology for deadlock free routing in hierarchical networks on chip. In: Networks-on-Chip, 2009. NoCS 2009. 3rd ACM/IEEE International Symposium on (pp. 2-11). IEEE Computer Society
Open this publication in new window or tab >>HiRA: A methodology for deadlock free routing in hierarchical networks on chip
2009 (English)In: Networks-on-Chip, 2009. NoCS 2009. 3rd ACM/IEEE International Symposium on, IEEE Computer Society , 2009, p. 2-11Conference paper, Published paper (Refereed)
Abstract [en]

Complexity of designing large and complex NoCs can be reduced/managed by using the concept of hierarchical networks. In this paper, we propose a methodology for design of deadlock free routing algorithms for hierarchical networks, by combining routing algorithms of component subnets. Specifically, our methodology ensures reachability and deadlock freedom for the complete network if routing algorithms for subnets are deadlock free. We evaluate and compare the performance of hierarchical routing algorithms designed using our methodology with routing algorithms for corresponding flat networks. We show that hierarchical routing, combining best routing algorithm for each subnet, has a potential for providing better performance than using any single routing algorithm. This is observed for both synthetic as well as traffic from real applications. We also demonstrate, by measuring jitter in throughput, that hierarchical routing algorithms leads to smoother flow of network traffic. A router architecture that supports scalable table-based routing is briefly outlined.

Place, publisher, year, edition, pages
IEEE Computer Society, 2009
Keywords
deadlock free routing, hierarchical networks, hierarchical routing algorithms, network-on-chip
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Computer Sciences
Identifiers
urn:nbn:se:hj:diva-10928 (URN)10.1109/NOCS.2009.5071439 (DOI)978-1-4244-4142-6 (ISBN)
Available from: 2009-11-26 Created: 2009-11-26 Last updated: 2018-01-12Bibliographically approved
Mejia, A., Palesi, M., Flich, J., Kumar, S., Lopez, P., Holsmark, R. & Duato, J. (2009). Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs. IEEE Transactions on Very Large Scale Integration (vlsi) Systems, 17(3), 356-369
Open this publication in new window or tab >>Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs
Show others...
2009 (English)In: IEEE Transactions on Very Large Scale Integration (vlsi) Systems, ISSN 1063-8210, E-ISSN 1557-9999, Vol. 17, no 3, p. 356-369Article in journal (Refereed) Published
Abstract [en]

An efficient routing algorithm is important for large on-chip networks [network-on-chip (NoC)] to provide the required communication performance to applications. Implementing NoC using table-based switches provide many advantages, including possibility of changing routing algorithms and fault tolerance, due to the option of table reconfigurations. However, table-based switches have been considered unsuitable for NoCs due to their perceived high area and power consumption. In this paper, we describe the region-based routing (RBR) mechanism which groups destinations into network regions allowing an efficient implementation with logic blocks. RBR can also be viewed as a mechanism to reduce the number of entries in routing tables. RBR is general and can be used in conjunction with any adaptive routing algorithm. In particular, we have evaluated the proposed scheme in conjunction with a general routing algorithm, namely segment-based routing (SR) and an application specific routing algorithm (APSRA) using regular and irregular mesh topologies. Our study shows that the number of entries in the table is significantly reduced, especially for large networks. Evaluation results show that RBR requires only four regions to support several routing algorithms in a 2-D mesh with no performance degradation. Considering link failures, our results indicate that RBR combined with SR is able to tolerate up to 7 link failures in an 8times8 mesh. RBR also reduces area and power dissipation of an equivalent table-based implementation by factors of 8 and 10, respectively. Moreover, the degradation in performance of the network is insignificant when using APSRA combined with RBR.

Keywords
adaptive routing algorithm, application specific routing algorithm, fault tolerance, large on-chip networks, network-on-chip, region-based routing mechanism, segment-based routing, table-based switches
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Computer Sciences
Identifiers
urn:nbn:se:hj:diva-10930 (URN)10.1109/TVLSI.2008.2012010 (DOI)
Available from: 2009-11-26 Created: 2009-11-26 Last updated: 2018-01-12Bibliographically approved
Holsmark, R., Palesi, M. & Kumar, S. (2008). Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions. Journal of systems architecture, 54(3-4), 427-440
Open this publication in new window or tab >>Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions
2008 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 54, no 3-4, p. 427-440Article in journal (Refereed) Published
Abstract [en]

The simplicity of regular mesh topology NoC architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology can not ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.

National Category
Information Systems
Identifiers
urn:nbn:se:hj:diva-3921 (URN)doi:10.1016/j.sysarc.2007.07.005 (DOI)
Available from: 2007-10-18 Created: 2007-10-18 Last updated: 2018-01-12Bibliographically approved
Palesi, M., Longo, G., Signorino, S., Holsmark, R., Kumar, S. & Catania, V. (2008). Design of bandwidth aware and congestion avoiding efficient routing algorithms for Network on Chip platforms. In: The 2nd IEEE International Symposium on Networks-on-Chip: Symposium on Networks-on-Chip (NOCS 2008) (pp. 97-106).
Open this publication in new window or tab >>Design of bandwidth aware and congestion avoiding efficient routing algorithms for Network on Chip platforms
Show others...
2008 (English)In: The 2nd IEEE International Symposium on Networks-on-Chip: Symposium on Networks-on-Chip (NOCS 2008), 2008, p. 97-106Conference paper, Published paper (Refereed)
Keywords
NoC, Routing, Application Specific
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:hj:diva-5945 (URN)978-0-7695-3098-7 (ISBN)
Available from: 2008-09-10 Created: 2008-09-10 Last updated: 2009-02-16Bibliographically approved
Holsmark, R. & Kumar, S. (2007). Corrections to Chen and Chui's Fault Tolerant Routing Algorithm for Mesh Networks. Journal of information science and engineering, 23(6), 1649-1662
Open this publication in new window or tab >>Corrections to Chen and Chui's Fault Tolerant Routing Algorithm for Mesh Networks
2007 (English)In: Journal of information science and engineering, ISSN 1016-2364, Vol. 23, no 6, p. 1649-1662Article in journal (Other (popular science, discussion, etc.)) Published
Abstract [en]

Chen and Chiu published a fault tolerant routing algorithm for mesh topology net-works which they claimed was deadlock free in the presence of multiple faults. In this paper we give a counter-example to show that their Message-Route algorithm fails to provide deadlock free routing in a 2 dimensional mesh network. We also point out certain cases where the algorithm fails to route messages to their destinations. We identify an error in the proof of the main theorem in their paper which was used for proving the property of deadlock freeness. Changes to their algorithm are proposed to make it deadlock free and complete. We also discuss a new application of fault tolerant routing algorithms for non-homogeneous 2-dimensional mesh topology networks for on-chip communication.

Keywords
deadlock, routing algorithms, wormhole routing, fault tolerance, mesh network, network on chip
Identifiers
urn:nbn:se:hj:diva-3655 (URN)
Available from: 2008-05-20 Created: 2008-05-20 Last updated: 2017-12-12Bibliographically approved
Palesi, M., Kumar, S., Holsmark, R. & Catania, V. (2007). Exploiting Communication Concurrency for Efficient Deadlock Free Routing in Reconfigurable NoC Platforms. In: Proceedins of 21st Internation Parallel and Distributed Symposium March 26-30, Long Beach, California, USA: 14th Reconfigurable Architectures Workshop.
Open this publication in new window or tab >>Exploiting Communication Concurrency for Efficient Deadlock Free Routing in Reconfigurable NoC Platforms
2007 (English)In: Proceedins of 21st Internation Parallel and Distributed Symposium March 26-30, Long Beach, California, USA: 14th Reconfigurable Architectures Workshop, 2007Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we make a case for the use of NoC

paradigm to develop future FPGAs in which large computational

blocks (cores) are connected to each other through

a packet switched communication network. We propose a

methodology to develop efficient and deadlock free routing

algorithms for such NoC platforms which can be specialized

for an application or a set of concurrent applications.

Application specific topology of communicating cores as

well as information about their communication concurrency

over time is exploited to maximize communication adaptivity

and performance. We demonstrate, both through analysis

of adaptivity as well as simulation based evaluation

of latency and throughput, that our algorithm gives significantly

higher performance as compared to general purpose

deadlock free algorithms like XY and Odd-Even.

Keywords
Network on Chip, Routing, Deadlock, Recongfiguration
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:hj:diva-4268 (URN)
Available from: 2007-10-05 Created: 2007-10-05
Organisations

Search in DiVA

Show all publications