The paper presents a topology-agnostic greedy protocol for network-on-chip routing. The proposed routing algorithm can tolerate any number of permanent faults, and is proven to be deadlock-free. We introduce a specialized variant of the algorithm, which is optimized for 2D mesh networks, both flat and wireless. The adaptiveness and minimality of several variants this algorithm are analyzed through graph-based simulations.
A subcategory of routing schemes in which the full graph topology is processed employs spanning trees to ensure that the routing process remains deadlock free. An overview of these methods is given by @cite_18 . The fundamental algorithm in this category is up* down* routing @cite_9 . In this method, a spanning tree is constructed over the network, and the up' or down' direction is assigned to each arc in the network (including the ones that are not part of the spanning tree). The directions are assigned in such a way that there is no cycle containing exclusively up' or exclusively down' arcs. To guarantee deadlock freeness, shortest paths between a source and destination vertex are searched under the restriction that no up edge can follow after a down edge (i.e. the down-up' turn is forbidden). These path constraints were relaxed in @cite_2 , which uses uses a more fine grained categorization of edges, in which only few specific turns are prohibited.
@cite_9 @cite_18 @cite_2
2124906592 2025879446 2142007322
Autonet is a self-configuring local area network composed of switches interconnected by 100 Mb s, full-duplex, point-to-point links. The switches contain 12 ports that are internally connected by a full crossbar. Switches use cut-through to achieve a packet forwarding latency as low as 2 ms switch. Any switch port can be cabled to any other switch port or to a host network controller. A processor in each switch monitors the network's physical configuration. A distributed algorithm running on the switch processor computes the routes packets are to follow and fills in the packet forwarding table in each switch. With Autonet, distinct paths through the set of network links can carry packets in parallel, allowing many pairs of hosts to communicate simultaneously at full link bandwidth. A 30-switch network with more than 100 hosts has been the service network for Digital's Systems Research Center since February 1990. > Most standard cluster interconnect technologies are flexible with respect to network topology. This has spawned a substantial amount of research on topology-agnostic routing algorithms, which make no assumption about the network structure, thus providing the flexibility needed to route on irregular networks. Actually, such an irregularity should be often interpreted as minor modifications of some regular interconnection pattern, such as those induced by faults. In fact, topology-agnostic routing algorithms are also becoming increasingly useful for networks on chip (NoCs), where faults may make the preferred 2D mesh topology irregular. Existing topology-agnostic routing algorithms were developed for varying purposes, giving them different and not always comparable properties. Details are scattered among many papers, each with distinct conditions, making comparison difficult. This paper presents a comprehensive overview of the known topology-agnostic routing algorithms. We classify these algorithms by their most important properties, and evaluate them consistently. This provides significant insight into the algorithms and their appropriateness for different on- and off-chip environments. System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up* down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up* down*-based routings, and also reduce latency