Dissertations / Theses on the topic 'Routing Deadlocks'

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 67-71).
Systems that can be integrated on a single silicon die have become larger and increasingly complex, and wire designs as communication mechanisms for these systems on chip (SoC) have shown to be a limiting factor in their performance. As an approach to remove the limitation of communication and to overcome wire delays, interconnection networks or Network-on-Chip (NoC) architectures have emerged. NoC architectures enable faster data communication between components and are more scalable. In designing NoC systems, there are three key issues; the topology, which directly depends on packaging technology and manufacturing costs, dictates the throughput and latency bounds of the network; the flit control protocol, which establishes how the network resources are allocated to packets exchanged between components; and finally, the routing algorithm, which aims at optimizing network performance for some topology and flow control protocol by selecting appropriate paths for those packets. Since the routing algorithm sits on top of the other layers of design, it is critical that routing is done in a matter that makes good usage of the resources of the network. Two main approaches to routing, oblivious and adaptive, have been followed in creating routing algorithms for these systems. Each approach has its pros and cons; oblivious routing, as opposite to adaptive routing, uses no network state information in determining routes at the cost of lower performance on certain applications, but has been widely used because of its simpler hardware requirements.
(cont.) This thesis examines oblivious routing schemes for NoC architectures. It introduces various non-minimal, oblivious routing algorithms that globally allocate network bandwidth for a given application when estimated bandwidths for data transfers are provided, while ensuring deadlock freedom with no significant additional hardware. The work presents and evaluates these oblivious routing algorithms which attempt to minimize the maximum channel load (MCL) across all network links in an effort to maximize application throughput. Simulation results from popular synthetic benchmarks and concrete applications, such as an H.264 decoder, show that it is possible to achieve better performance than traditional deterministic and oblivious routing schemes.
by Michel A. Kinsy.
S.M.

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.

In the pursuit for ever-increasing compute power, and with Moore's law slowly coming to an end, high-performance computing started to scale-out to larger systems. Alongside the increasing system size, the interconnection network is growing to accommodate and connect tens of thousands of compute nodes. These networks have a large influence on total cost, application performance, energy consumption, and overall system efficiency of the supercomputer. Unfortunately, state-of-the-art routing algorithms, which define the packet paths through the network, do not utilize this important resource efficiently. Topology-aware routing algorithms become increasingly inapplicable, due to irregular topologies, which either are irregular by design, or most often a result of hardware failures. Exchanging faulty network components potentially requires whole system downtime further increasing the cost of the failure. This management approach becomes more and more impractical due to the scale of today's networks and the accompanying steady decrease of the mean time between failures. Alternative methods of operating and maintaining these high-performance interconnects, both in terms of hardware- and software-management, are necessary to mitigate negative effects experienced by scientific applications executed on the supercomputer. However, existing topology-agnostic routing algorithms either suffer from poor load balancing or are not bounded in the number of virtual channels needed to resolve deadlocks in the routing tables. Using the fail-in-place strategy, a well-established method for storage systems to repair only critical component failures, is a feasible solution for current and future HPC interconnects as well as other large-scale installations such as data center networks. Although, an appropriate combination of topology and routing algorithm is required to minimize the throughput degradation for the entire system. This thesis contributes a network simulation toolchain to facilitate the process of finding a suitable combination, either during system design or while it is in operation. On top of this foundation, a key contribution is a novel scheduling-aware routing, which reduces fault-induced throughput degradation while improving overall network utilization. The scheduling-aware routing performs frequent property preserving routing updates to optimize the path balancing for simultaneously running batch jobs. The increased deployment of lossless interconnection networks, in conjunction with fail-in-place modes of operation and topology-agnostic, scheduling-aware routing algorithms, necessitates new solutions to solve the routing-deadlock problem. Therefore, this thesis further advances the state-of-the-art by introducing a novel concept of routing on the channel dependency graph, which allows the design of an universally applicable destination-based routing capable of optimizing the path balancing without exceeding a given number of virtual channels, which are a common hardware limitation. This disruptive innovation enables implicit deadlock-avoidance during path calculation, instead of solving both problems separately as all previous solutions.

O aumento da capacidade dos Sistemas sobre Silício (SoCs do inglês, Systemon-Chip) tem levado Redes Intrachip (NoCs do inglês, Network on-Chip) a serem utilizadas como interface de comunicação de Módulos de Processamento de sistemas complexos, e particularmente em Sistemas Dinamicamente Reconguráveis a serem implementados sobre FPGAs com capacidade de reconguração parcial. Algumas estratégias de reconguração geram cenários com NoCs irregulares e indiretas, fato que força o sistema a atualizar o seu algoritmo de roteamento afim de se evitar problemas de comunicação de dados, como deadlock e livelock. O presente trabalho apresenta uma NoC Dinamicamente Recongurável (DRNoC do inglês, Dynamically Recongurable Newtwork on-Chip) utilizando o Algoritmo de Roteamento Ordenado por Dimensão Flexibilizado (FDOR do inglês, Flexible Dimension Order Routing) que se caracteriza principalmente sua simplicidade, baixa complexidade e ser livre de deadlock. No presente trabalho, foi implementada a ferramenta DRSimGen, que gera código VHDL da arquitetura da NoC associada, para ser utilizado com aplicações específicas com reconfiguração parcial dinâmica que requeiram comunicações paralelas entre seus módulos de processamento. Esta ferramenta gera os roteadores, módulos de processamento, além de um Sistema de Controle de Reconguração Parcial Dinâmica que pode ser utilizado junto com o Sistema de Reconguração do algoritmo de roteamento baseado em FDOR, já desenvolvido por outros anteriormente. A ferramenta também gera componentes de testbench para a simulação do sistema, baseados na técnica de Chaveamento Dinâmico de Circuitos; são utilizadas chaves de isolação para emularos processos de reconguração parcial dinâmica. Os resultados destes experimentos ajudaram a determinar o comportamento desejado do sistema. Também foram feitas simulações da implementação do FDOR em descrição de alto nível, com a finalidade de determinar seu desempenho na transferência de dados que ajudarão a definir o posicionamento dos módulos de processamento sobre a estrutura da rede. Os resultados dos experimentos tem demonstrado a viabilidade desta estratégia, levando à conclusão que o algoritmo FDOR é uma solução adequada para DRNoCs.
The increased capacity of Systems on-Chip (SoCs) has led Networks on-Chip (NoC) to be used as communication interface for processing modules of complex systems, and particularly in Dynamically Recongurable Systems to be implemented over partially recongurable FPGAs. Some reconguration strategies work on irregular and indirect NoCs, fact that forces the system to update its routing algorithm in order to avoid data communication problems, such as deadlockandlivelock. ThispaperpresentsaDynamicallyRecongurableNoC(DRNoC)using Flexible Dimension Order Routing Algorithm (FDOR), mainly characterized by its simplicity, low complexity and deadlock freedom In this work, the DyAFNoC tool was implemented, to generate the VHDL code of the associated NoC architecture to be used with specic applications with dynamic partial reconguration that require parallel communications between their processing modules. This tool generates routers, processing modules, and also a Partial Dynamic Reconguration Control System that can be used with the FDOR-based Reconguration System, developed elsewhere. The tool also generates testbench components for the system simulation, based on the Dynamic Circuit Switching technique that uses isolation switches to emulate the dynamic partial reconguration processes. The results of these experiments have helped to determine the desired system behavior. Simulations of the FDOR implementation were also made in high level descriptioninordertodetermineitsdatatransferperformancethatwillhelptodeneplacement of the processing modules over the network structure. The experiments results have demonstrated the feasibility of this strategy, leading to the conclusion that the FDOR algorithm is a suitable solution for DRNoC.

碩士
國立臺灣科技大學
工程技術研究所
81
The communication latency between nodes of hypercube is a vital factor to the performance of the whole system. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. The deadlock-freeness and the performance improvement are the prin- cipal concern of routing algorithms. Since virtual channel is help to the expedition of message passing, this thesis employs the concept of virtual channel to avoid the deadlock and improve the performance. Deadlock-free multicast routing algorithm on path-like model is proposed. The simulation results indicate that one-path routing algo- rithm has lower traffic congestion than that of dual-path routing algorithm. Furthermore, it can also reduce the latency significantly, improving communication performance.

碩士
雲林科技大學
工業工程與管理研究所碩士班
98
In the automated production environment, it is important for the material transporting system to deliver the material to the right place at the right time. Generally, automated guided vehicle systems (AGVS) are widely used in transporting material. When a deadlock occurs, AGVs are unable to move forward and the partial delay may spread to the entire system and stop the operation of material handling. Therefore, deadlock avoidance in the AGV traffic control is an important issue. In this research, assuming that the environment layout and vehicle destinations are known, a deadlock -free and shortest path of AGV is generated. Using Colored Resource-Oriented Petri-net (CROPN), the AGV path model is established and analyzed to find the control strategy for deadlock avoidance.

博士
國立臺灣大學
電機工程學研究所
88
In direct multicomputer networks, tasks are executed by a set of intercommunicating nodes or processors. The communication is usually carried out by means of passing messages from one node to another over the interconnection network. Since direct networks utilize the locality of the message references more efficiently, most of the existing systems use direct networks such as k-ary n-cube or n-dimensional mesh. The performance of the interprocessor communication scheme depends largely on the network dimension, the switching technique, and the routing algorithm. Most contemporary systems have used two or three dimensions. Store and forward, virtual cut-though, and wormhole routing are the main switching techniques used for inter-processor communication. Due to the lower latency and smaller buffer requirements, wormhole routing is preferred and is widely used in recent multicomputers. Multicast is the delivery of the same message from one source node to an arbitrary number of destination nodes. Recently, wormhole routing has become one of the most popular switching techniques in new generation multicomputers. When designing communication algorithms for wormhole routed network topologies, the necessity to be deadlock-free due to the exclusive use of channels must be considered in the first place. Unfortunately, fault-tolerance properties of the routing networks would hurt under such restrictions. Previous researches have focused on fault-tolerant one-to-one routing algorithms for n-dimensional meshes. However, little research has been done on fault-tolerant one-to-many(multicast) routing algorithms due to the difficulty to achieving deadlock-free routing on faulty networks. We will develop such an algorithm for faulty hypercubes. Our approach is not based on adding physical or virtual channels to the network topology. Instead, we integrate several techniques such as partitioning of nodes, partitioning of channels, node label assignments, and path-like multicast to achieve fault tolerance. Both theoretical analysis and simulation are performed to demonstrate the effectiveness of the proposed algorithm. Routing is the delivery of a message from one source node to another destination node. Previous researches have focused on designing deadlock-free routing algorithms for an n-cube based on the Hamilton-path labeling. However, the labeling method widely employed in the literature is called the Gray-Code labeling. The Gray-Code labeling is a fixed approach and provides only one way to achieve routing. In contrast to this traditional way, a distributed Hamilton-path labeling algorithm is proposed in this thesis to provide up to ways of labeling. In addition, the proposed Hamilton-path labeling process can be completed for an n-cube in O(n) parallel steps. Finally, a heuristic algorithm to obtain an efficient way of labeling for our approach according to different system traffic distributions is also given. Therefore, the system performance can be improved significantly with such heuristic approach. In order to avoid deadlocks, prevention-based routing algorithms impose certain routing restrictions which lead to high hardware complexity or low adaptability. If deadlock occurrences are extremely rare, recovery-based routing algorithms become more attractive due to lower hardware complexity and better routing adaptivity. A simple architecture that each router is provided with an additional special flit buffer was developed to achieve deadlock recovery in the literature. Disha_SEQ and Disha_CON are two deadlock recovery schemes based on such architecture to accomplish sequential recovery and concurrent recovery, respectively. In this thesis, we propose a simple recovery scheme for a 2-dimensioal mesh with the same router architecture and eliminates the drawbacks in Disha_SEQ or Disha_CON such as hardwired token, finding the Hamilton cycle, Hamilton-path labeling for each node, and non-minimal path routing. Moreover, the simulation results show that the proposed scheme also outperforms Disha_SEQ and Disha_CON under various load distributions.

碩士
國立東華大學
資訊工程學系
104
With the rapid advance in chip manufacturing technology, more and more functions and modules can be integrated into a single chip. Today, tens or hundreds of silicon intellectual property (IP) cores can be placed on a single chip. Such a system-on-chip (SoC) design, however, requires a high-performance, low-power on-chip interconnect to provide effective communication. Recently, the network-on-chip (NoC) architecture has been proposed for the interconnection framework of SoC. Furthermore, as Moore's Law will not be as effective in the future, 3D chip have been proposed and studied for the future chip manufacturing. Hence, the on-chip interconnect with 3D technology will be more critical for the SoC design. This thesis presents the design of the NoC routing algorithms and architectures for future 3D VLSI chips. We focus on 3D mesh network routing with oversize IP cores in the NoC. In such a network, the network topology is no longer a conventional mesh. While some researchers have proposed their routing algorithms for 3D mesh NoC. Their designs focus on the regular 3D mesh with unit-size IP cores. Even though some researchers proposed the routing algorithms for 3D NoC with irregular topologies, they require costly routing tables with complex and slow routers. We modify our previously proposed train routing algorithm and propose the effective 3D NoC routing algorithm with oversize IP cores, which is called XY-Elevator TRAIN (XY-EBT). We show that XY-EBT is deadlock-free and requires no routing tables. It provides the 3D chip with high-performance and low-cost chip communication. We have run many simulations for the performance evaluation of XY-EBT by the Booksim 2.0 simulator, and compare it with other routing designs. The results show that the XY-EBT achieves superior performance to other designs, especially when the router has two virtual channels at each input port.

碩士
國立成功大學
電機工程學系碩博士班
101
Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing methods are either tree-based or path-based. The former may suffer from the problem of multicast deadlocks and the latter may require long routing paths. In this thesis, we propose a hybrid multicast routing approach that combines the advantages of both path-based and tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved due to an adaptive routing strategy according to the traffic load. We also investigate several variations of this hybrid approach and identify an algorithm that can achieve the best performance in general. Experimental results show that the saturation point (in terms of injection ratio) of this algorithm is significantly higher than those of the state-of-the-art tree- and path-based multicast routing algorithms. In fact experiments with different network dimensions, buffer sizes, packet sizes, and numbers of destinations per packet under various traffic injection rates have been carried out and the results show that the proposed algorithm outperforms the other two algorithms in all of these experiments.

碩士
國立東華大學
資訊工程學系
102
With the rapid advance of semiconductor technology, a single chip can accommodate more and more IP cores. Traditionally, we use dedicated wiring and shared buses for interconnecting IP cores on a chip. However, these approaches suffer from either extreme high cost or limited communication bandwidth for SoC. Therefore, network-on-chip (NoC) architectures are proposed to deal with the issues. A key problem with NoC design is how to map IP cores to the network in order to achieve effective communication. Several researchers have proposed algorithms to map from communication task graph to NoC architectures. However, in their evaluation, the communication cost is based on the shortest path. It means that they did not take potential deadlock into consideration. In this thesis, we use our proposed TRAIN routing algorithm for the IP mapping design. With our TRAIN, deadlock is guaranteed to be avoided. In our simulations, the real application cases include MPEG, MWD, and VOPD. Furthermore, we also use random synthesized cases for 4x4, 5x5, and 6x6 network topologies. The results show that the communication cost for TRAIN is close to that for the shortest path routing for various mapping algorithms. Furthermore, our proposed mapping algorithm outperforms the other mapping algorithms in most cases. Keywords: mapping, SoC, NoC, communication core graph.

碩士
國立清華大學
資訊工程學系
92
In this thesis, we proposed an efficient deadlock-free tree-based routing algorithm, the DOWN/UP routing, for irregular wormhole-routed networks based on the turn model. In a tree-based routing algorithm, hot spots around the root of a spanning tree and the uneven traffic distribution are the two main facts degrade the performance of the routing algorithm. To solve the hot spot and the uneven traffic distribution problems, in the DOWN/UP routing, it tries to push the traffic downward to the leaves of a spanning tree as much as possible and remove prohibited turn pairs with opposite directions in each node, respectively. Given an irregular network topology, the construction of the DOWN/UP routing consists of three phases. In the first phase, a communication graph based on the coordinated tree of the given topology is constructed. In a communication graph, tree links and cross links are considered as different links. This will make the prohibited turn selection more precisely. In this phase, we also proposed a better way to construct the coordinated tree such that a better throughput can be obtained when a routing algorithm is performed. In the second phase, based on the maximal direction graph and the turn model, we construct a maximal acyclic direction dependency graph to obtain the set of prohibited turns. In this phase, we careful select the set of prohibited turns such that the traffic can be pushed downward to leaves of a spanning tree as much as possible and a more even distribution of traffic load can be achieved. In the third phase, we apply the set of prohibited turns to each node in the communication graph and release unnecessary prohibited turns for each node. Then the DOWN/UP routing algorithm for the give irregular network can be derived based on the prohibited turns of each node. To evaluate the performance of DOWN/UP routing, the simulation is conducted. We have implemented the DOWN/UP routing along with the L-turn routing on the IRFlexSim0.5 simulator. Irregular networks that contain 128 switches with 4-port and 8-port configurations are simulated. The simulation results show that the proposed routing algorithm outperforms the L-turn routing for all test samples in terms of the degree of hot spots, the traffic load distribution, and throughput.

碩士
國立清華大學
資訊工程學系
93
The InfiniBand architecture (IBA) is an interconnect network standard designed for server I/O and inter-server communication. The IBA defines a switch-based network with point-to-point links to support arbitrary topology. Routing in an IBA network is based on the forwarding table stored in each switch. The forwarding table forwards packets to output ports by only considering the destination addresses of packets. However, the forwarding tables computed by many irregular routing algorithms consider both the input port and the destination address of the packet. Therefore, these irregular routing algorithms can not be used in IBA network because they do not conform to the IBA forwarding table format. There are two types of IBA forwarding table: Linear forwarding table (LFT) and Random forwarding table (RFT). In this thesis, we propose a two-phase method, partial renaming method, to construct the deadlock-free RFT according to the paths computed by any irregular deadlock-free routing algorithm which considers both the input port and the destination address. The partial renaming is an efficient and low overhead forwarding table construction method for IBA. The forwarding tables constructed by the partial renaming method do not modify the original paths computed by the routing algorithm before. This reserves the characteristic of the original routing algorithm. To evaluate the proposed method, we compare our method with the renaming scheme on a simulator. We evaluate the forwarding table overhead and the computation time of both methods in different network size and different switch settings. The simulation results show that the computation time and the size of forwarding table introduced by our method are much less than those introduced by the renaming scheme in all test cases