This paper addresses the problem of balancing the on-chip packet latencies in a chip multi-processor (CMP), which is simultaneously executing multiple applications. Specifically, this paper presents a balanced application-to-core mapping algorithm that aims to minimize the maximum on-chip packet latency of all running applications. The paper starts by formulating the balanced mapping problem for CMPs and proving its NP-completeness. Next it presents an efficient heuristic algorithm for solving the aforesaid problem, which utilizes the characteristics of on-chip cache and memory accesses in CMPs and takes into account the workload variations among applications. Simulation results on PARSEC benchmark suite show that the proposed algorithm lowers the maximum average packet latency of all applications by 11 percent while cutting the standard deviation of on-chip packet latencies by 99 percent. This is achieved by very little overhead in terms of the overall packet latency and power consumption averaged over all packets.

As chip designs penetrate further into the dark silicon era, innovative techniques are much needed to power off idle or under-utilized system components while having minimal impact on performance. On-chip network routers are potentially good targets for power-gating, but packets in the network can be significantly delayed as their paths may be blocked by powered-off routers. In this paper, we propose Power Punch, a novel performance-aware, power reduction scheme that aims to achieve non-blocking power-gating of on-chip network routers. Two mechanisms are proposed that not only allow power control signals to utilize existing slack at source nodes to wake up powered-off routers along the first few hops before packets are injected, but also allow these signals to utilize hop count slack by staying ahead of packets to "punch through " any blocked routers along the imminent path of packets, preventing packets from having to suffer router wakeup latency or packet detour latency. Full system evaluation on PARSEC benchmarks shows Power Punch saves more than 83% of router static energy while having an execution time penalty of less than 0.4%, effectively achieving near non-blocking power-gating of on-chip network routers.

Power-gating is a promising technique to mitigate the increasing static power of on-chip routers. Clos networks are potentially good targets for power-gating because of their path diversity and decoupling between processing elements and most of the routers. While power-gated Clos networks can perform better than power-gated direct networks such as meshes, a significant performance penalty exists when conventional power-gating techniques are used. In this paper, we propose an effective power-gating scheme, called MP3 (Minimal Performance Penalty Power-gating), which is able to achieve minimal (i.e., near-zero) performance penalty and save more static energy than conventional power-gating applied to Clos networks. MP3 is able to completely remove the wakeup latency from the critical path, reduce long-term and transient contention, and actively steer network traffic to create increased power-gating opportunities. Full system evaluation using PARSEC benchmarks shows that the proposed approach can significantly reduce the performance penalty to less than 1% (as opposed to 38% with conventional power-gating) while saving more than 47% of router static energy, with only 2.5% additional area overhead.

As the number of cores continues to grow in chip multiprocessors (CMPs), application-to-core mapping algorithms that leverage the non-uniform on-chip resource access time have been receiving increasing attention. However, existing mapping methods for reducing overall packet latency cannot meet the requirement of balanced on-chip latency when multiple applications are present. In this paper, we address the looming issue of balancing minimized on-chip packet latency with performance-awareness in the multi-application mapping of CMPs. Specifically, the proposed mapping problem is formulated, its NP-completeness is proven, and an efficient heuristic-based algorithm for solving the problem is presented. Simulation results show that the proposed algorithm is able to reduce the maximum average packet latency by 10.42% and the standard deviation of packet latency by 99.65% among concurrently running applications and, at the same time, incur little degradation in the overall performance.

While power gating is a promising technique to reduce the static power consumption of network-on-chip (NoC), its effectiveness is often hindered by the requirement of maintaining network connec-tivity and the limited knowledge of traffic behaviors. In this paper, we present Smart Butterfly, a core-state-aware NoC power-gating scheme based on flattened butterfly that utilizes the active/sleep state information of processing cores to improve power-gating effectiveness. Smart Butterfly exploits the rich connectivity of the flattened butterfly topology to allow more on-chip routers to be power-gated when their attached cores are asleep. We present two heuristic algorithms to determine the set of routers to be turned on to maintain connectivity and allow tradeoff between power consumption and average packet latency. Simulation results show an average of 42.85% and 60.48% power reduction of Smart Butterfly over prior art on 4x4 and 8x8 networks, respectively.

Multicore processors have the potential to deliver scalable performance by distributing computation across multiple cores. However, the communication cost of parallel application thread execution may significantly limit the performance achievable due to latency and contention on shared resources in the on-chip network of multicores experienced by packets from critical threads. We present PAIS, Parallelism-Aware Interconnect Scheduling, that bolsters performance and energy efficiency of parallel applications. PAIS dynamically detects thread execution progress based on communication latency and scheduling, and it accelerates communication for slowly executing threads by prioritizing packets from those threads with flow control and priority-based arbitration.

Deadlock-free flow control should be designed with minimal cost, particularly for on-chip designs where area and power resources are greatly constrained. While Bubble Flow Control, proposed a decade ago, can avoid deadlock in VCT-switched tori with only one virtual channel (VC), there has been no working solution for wormhole switching that achieves the similar objective. Wormhole switching allows the channel buffer size to be smaller than the packet size, thus is preferred by on-chip networks. However, wormhole packets can span multiple routers, thereby creating additional channel dependences and adding complexities in both deadlock and starvation avoidance. In this paper, we propose Worm-Bubble Flow Control (WBFC), a new flow control scheme that can avoid deadlock in wormhole-switched tori using minimally 1-flit-sized buffers per VC and one VC in total. Moreover, any wormhole-switched topology with embedded rings can use WBFC to avoid deadlock within each ring. Simulation results from synthetic traffic and PARSEC benchmarks show that the proposed approach can achieve significant throughput improvement and also area and energy savings compared to an optimized Dateline routing approach.

Handling routing- and protocol-induced deadlocks is a critical issue in designing a reliable communication system. Generally, to avoid these two types of deadlocks without losing routing freedom requires a large amount of virtual channels (VCs), which imposes significant negative effects on router power, energy and frequency. In this paper, we propose a virtual cut-through switched Bubble Coloring (BC) scheme, which can avoid both routing- and protocol-induced deadlocks and allow fully adaptive routing on any topology without the need for multiple virtual channels. Results from both synthetic and full-system simulation show that, compared to a conventional deadlock-free scheme with 4VCs (i.e., XY_adaptive_4VC), our BC scheme with the minimal 1VC (i.e., BC_1VC) can reduce router energy and area by up to 51.2% and 58.3%, respectively, and has comparable performance at the same time. As the proposed BC scheme does not require multiple virtual channels, it also reduces the complexity of router arbitration logic, which brings the opportunity to increase router frequency and further improve system performance.

With the advent of many-core systems capable of hosting multiple concurrently running applications, the traffic characteristics of networks-on-chip (NoCs) may exhibit new regional behaviors. By recognizing and exploiting these traffic behaviors, the effectiveness of NoC interference reduction techniques can be greatly improved. However, few works have investigated these regional behaviors and their potential impact on interference, leaving the opportunity largely unexplored. In this paper, we identify and characterize regional behavior in NoC and propose RAIR, a region-aware interference reduction technique that not only removes any restrictions on the inter-region traffic patterns, but also captures and exploits regional behavior throughout the design, thus improving the effectiveness of interference reduction. Evaluation using a cycle-accurate simulator shows that RAIR can improve the average packet latency by up to 17% on synthetic traffic patterns and up to 26% on PARSEC benchmarks compared to state-of-the-art interference reduction techniques.

With the emergence of multi-programmed workloads for Chip Multiprocessors (CMP), Quality of Service (QoS) of each co-scheduled application on the CMP is increasingly gaining importance. As more and more applications are consolidated into a single chip to compete for the limited off-chip memory bandwidth, off-chip memory bandwidth partitioning makes an increasing impact on system performance. Although various existing heuristic-based memory scheduling schemes have achieved significant system performance improvement by better partitioning the bandwidth, it is still not clear what are the best ways to partition off-chip bandwidth for improving different system performance objectives. The goal of this paper is to understand how off-chip memory bandwidth partitioning affects various system performance objectives. To achieve this goal, we propose an analytical model that is simple yet powerful enough to reveal the relationship between various memory bandwidth partitioning schemes and different system performance objectives. From our model, optimal memory bandwidth partitioning schemes for different system-level objectives are derived. Experimental results from a cycle-accurate full-system simulator show that, for heterogeneous workloads, performance improvements over No_partitioning/Equal_partitioning in terms of harmonic weighted speedup, minimum fairness, weighted speedup and sum of IPCs are 20.3%/2.1%, 49.8%/38.7%, 32.8%/7.6% and 64.2%/24%, on average, with our corresponding optimal partitioning schemes (i.e., Square_root, Proportional, Priority_APC, Priority_API), respectively.

While power-gating is a promising technique to mitigate the increasing static power of a chip, a fundamental requirement is for the idle periods to be sufficiently long to compensate for the power-gating and performance overhead. On-chip routers are potentially good targets for power optimizations, but few works have explored effective ways of power-gating them due to the intrinsic dependence between the node and router -- any packet (sent, received or forwarded) must wakeup the router before being transferred, thus breaking the potentially long idle period into fragmented intervals. Simulation shows that directly applying conventional power-gating techniques would cause frequent state-transitions and significant energy and performance overhead. In this paper, we propose NoRD (Node-Router Decoupling), a novel power-aware on-chip network approach that provides for power-gating bypass to decouple the node's ability for transferring packets from the powered-on/off status of the associated router, thereby maximizing the length of router idle periods. Full system evaluation using PARSEC benchmarks shows that the proposed approach can substantially reduce the number of state-transitions, completely hide wakeup latency from the critical path of packet transport and eliminate node-network disconnection problems. Compared to an optimized conventional power-gating technique applied to on-chip routers, NoRD can further reduce the router static energy by 29.9% and improve the average packet latency by 26.3%, with only 3% additional area overhead.

With continued Moore's law scaling, multicore-based architectures are becoming the de facto design paradigm for achieving low-cost and performance/power-efficient processing systems through effective exploitation of available parallelism in software and hardware. A crucial subsystem within multicores is the on-chip interconnection network that orchestrates high-bandwidth, low-latency, and low-power communication of data. Much previous work has focused on improving the design of on-chip networks but without more fully taking into consideration the on-chip communication behavior of application workloads that can be exploited by the network design. A significant portion of this paper analyzes and models on-chip network traffic characteristics of representative application workloads. Leveraged by this, the notion of globally coordinated on-chip networks is proposed in which application communication behavior-captured by traffic profiling-is utilized in the design and configuration of on-chip networks so as to support prevailing traffic flows well, in a globally coordinated manner. This is applied to the design of a hybrid network consisting of a mesh augmented with configurable multidrop (bus-like) spanning channels that serve as express paths for traffic flows benefiting from them, according to the characterized traffic profile. Evaluations reveal that network latency and energy consumption for a 64-core system running OpenMP benchmarks can be improved on average by 15 and 27 percent, respectively, with globally coordinated on-chip networks.

Network flow control mechanisms that are aware of global conditions potentially can achieve higher performance than flow control mechanisms that are only locally aware. Owing to high implementation overhead, globally-aware flow control mechanisms in their purest form are seldom adopted in practice, leading to less efficient simplified implementations. In this paper, we propose an efficient implementation of a globally-aware flow control mechanism, called Critical Bubble Scheme, and apply it successfully to k-ary n-cube networks for the general class of buffer occupancy-based network flow control techniques. Simulation results show that the proposed scheme can reduce the buffer access portion of packet latency by as much as 77%, leading to much lower average packet latency at medium and high network loads while sustaining 11% throughput improvement after network saturation.

As chip multiprocessors transition from multi-core to many-core, on-chip network power is increasingly becoming a key barrier to scalability. Studies have shown that on-chip networks can consume up to 36% of the total chip power, while analysis of network traffic reveals that for extended periods of execution time, network load is well below the network capacity in many applications. In recent studies, researchers have proposed to exploit this temporal variability in network traffic to dynamically turn off links, buffers and segments of the on-chip routers. In this work, we make the case for a polymorphic topology, called Cubic Ring (cRing), that allows dynamically turning off over 30% of resources in a 2D network (and more in higher dimensional networks), with less than 5% increase in average distance. As a result, cRing networks provide an elegant way to trade off network bandwidth for lower (static) power. A complete formalism for the proposed cRing topologies and the associated routing algorithm is presented, along with evaluation under synthetic workloads.

Microarchitectural redundancy has been proposed as a means of improving chip lifetime reliability. It is typically used in a reactive way, allowing chips to maintain operability in the presence of failures by detecting and isolating, correcting, and/or replacing components on a first-come, first-served basis only after they become faulty. In this paper, we explore an alternative, more preferred method of exploiting microarchitectural redundancy to enhance chip lifetime reliability. In our proposed approach, redundancy is used proactively to allow non-faulty microarchitecture components to be temporarily deactivated, on a rotating basis, to suspend and/or recover from certain wearout effects. This approach improves chip lifetime reliability by warding off the onset of wearout failures as opposed to reacting to them posteriorly. Applied to on-chip cache SRAM for combating NBTI-induced wearout failure, our proactive wearout recovery approach increases lifetime reliability (measured in mean-time-to-failure) of the cache by about a factor of seven relative to no use of microarchitectural redundancy and a factor of five relative to conventional reactive use of redundancy having similar area overhead.

Component failures and planned component replacements cause changes in the topology and routing paths supplied by the interconnection network of a parallel processor system over time. Such changes may require the network to be reconfigured such that the existing routing function is replaced by one that enables packets to reach their intended destinations amid the changes. Efficient reconfiguration methods are desired which allow the network to function uninterruptedly over the course of the reconfiguration process while remaining free from deadlocking behavior. In this paper, we propose, evaluate, and prove the deadlock freedom of a new network reconfiguration protocol that overlaps various phases of "static" reconfiguration processes traditionally used in commercial and research systems to provide performance efficiency on par with that of recently proposed "dynamic" reconfiguration processes but without their complexity. Simulation results show that the proposed Overlapping Static Reconfiguration protocol can reduce reconfiguration time by up to 50 percent, reduce packet latency by several orders of magnitude, reduce packet dropping by an order of magnitude, and provide unhalted packet injection as compared to traditional static reconfiguration while allowing network throughput similar to dynamic reconfiguration.

With the rise of multicore computing, the design of on-chip networks (or networks on chip) has become an increasingly important component of computer architecture. The cell broadband engine's element interconnect bus (EIB), with its four data rings and shared command bus for end-to-end control, supports twelve nodes - more than most mainstream on-chip networks, which makes it an interesting case study. As a first step toward understanding the design and performance of on-chip networks implemented within the context of a commercial multicore chip, this paper analytically evaluates the EIB network using conventional latency and throughput characterization methods as well as using a recently proposed 5-tuple latency characterization model for on-chip networks. These are used to identify the end-to-end control component of the EIB (i.e., the shared command bus) as being the main bottleneck to achieving minimal, single-cycle latency and maximal 307.2 GB/sec raw effective bandwidth provided natively by the EIB. This can be exacerbated by poorly designed cell software, which can have significant impact on the utilization of the EIB. The main findings from this study are that the end-to-end control of the EIB influenced by software running on the cell has inherent scaling problems and serves as the main limiter to overall network performance. Thus, end-to-end effects must not be overlooked when designing efficient networks on chip

As the level of chip-integration continues to advance at a fast pace, the desire for efficient interconnects - whether on-chip or off-chip - is rapidly increasing. Traditional interconnects like buses, point-to-point wires, and regular topologies may suffer from poor resource sharing in the time and space domains, leading to high contention or low resource utilization. In this paper, we propose a design methodology for constructing networks for special-purpose computer systems with well-behaved (known) communication characteristics. A temporal and spatial model is proposed to define the sufficient condition for contention-free communication. Based upon this model, a design methodology using a recursive bisection technique is applied to systematically partition a parallel system such that the required number of links and switches is minimized while achieving low contention. Results show that the design methodology can generate more optimized on-chip networks with up to 60 percent fewer resources than meshes or tori while providing blocking performance closer to that of a fully connected crossbar.

This paper develops theoretical support useful for determining deadlock properties of dynamic network reconfiguration techniques and also serves as a basis for the development of design methodologies useful for deriving deadlock-free reconfiguration techniques. It is applicable to interconnection networks typically used in multiprocessor servers, network-based computing clusters, and distributed storage systems, and also has potential application to system-on-chip networks. This theory builds on basic principles established by previous theories while pioneering new concepts fundamental to the case of dynamic network reconfiguration.

For pt.I see ibid., vol.16, no.5, p.412-427 (2005). Dynamic network reconfiguration is defined as the process of changing from one routing function to another while the network remains up and running. The main challenge is in avoiding deadlock anomalies while keeping restrictions on packet injection and forwarding minimal. Current approaches either require virtual channels in the network or they work only for a limited set of routing algorithms and/or fault patterns. In this paper, we present a methodology for devising deadlock free and dynamic transitions between old and new routing functions that is consistent with newly proposed theory [J. Duato et al., (2005)]. The methodology is independent of topology, can be applied to any deadlock-free routing function, and puts no restrictions on the routing function changes that can be supported. Furthermore, it does not require any virtual channels to guarantee deadlock freedom. This research is motivated by current trends toward using increasingly larger Internet and transaction processing servers based on clusters of PCs that have very high availability and dependability requirements, as well as other local, system, and storage area network-based computing systems.

AStechnology scaling enables the integration of billions of transistors ona chip, economiesof scale isprompting the move toward parallel chip architectures with both application-specific systems-on-a-chip (SoC) and general-purpose microprocessors leveraging multiple processing cores on a single chip for better performance at manageable design costs.As theseparallel chiparchitectures scale in size, on-chip networks are emerging as the de facto communication architecture, replacing dedicated interconnects and shared buses.At the same time, tightdesignconstraints in the formof ever-increasing chip-crossing interconnect delays and power consumption are reaching criticality. On-chip networks have todeliver good latency-throughputperformance in the faceof very tight power and area budgets. The interplay of these two trends makes on-chip network design one of the most challenging and significant design problems system designers are facing in the near term. New parallel chip architectures bring about unique delay and bandwidth requirements for on-chip networks that, in many ways, are substantially different from traditional multichip/multiboard interconnection networks found in multiprocessors and other “macro” system architectures. The exact requirements depend on the intended application, and need to be met with judicious use of precious silicon real-estate under a tight power budget capped by battery life, power delivery limits, and/or thermal characteristics. What’s more, the impact on design and verification effort as well as fault resilience must also be considered. While the computer industry within the past decade has begun introducing on-chip network architectures based on multiple buses (such as ARM’s AMBA, IBM’s CoreConnect, Sonic’s Smart Interconnect IP) and, more recently, point-to-point switch fabrics (such as CrossBow’s 2D mesh Xfabric and Fulcrum’s crossbar-centric Nexus), no standards have emerged and none are on the horizon. “Which on-chip network architecture best increases chip functionality while not negatively impacting achievable clock frequency, communication latency, bandwidth, flexibility, design/verification effort, and fault resiliency?” remains an open question. In this special section, we showcase several major research thrusts in the on-chip networks area. The selected papers can be classified by their targeted chip system: application-specific embedded SoCs versus general-purpose microprocessors. In the former, the availability of application knowledge makes it feasible and effective to tailor the on-chip network architecture toward the particular application(s) characteristics. In addition, as design time for embedded SoCs critically impacts time-to-market, streamlining and optimizing the design process of the onchip networks in such systems for flexibility, reuse, and speed is crucial. On the other hand, for general-purpose microprocessors, the break from traditional single-core architecture opens up the architectural design space, which spawns a different set of requirements (some more relaxed, others more restrictive) for on-chip networks, motivating new network architectures and studies. In both types of systems, on-chip network designers have to grapple with very tight area, power, and wire delay constraints. The first two papers target application-specific chip systems. “Joint Application Mapping/Interconnect Synthesis Techniques for Embedded Chip-Scale Multiprocessors,” by Neal K. Bambha and Shuvra S. Bhattacharyya focuses on a specific phase of the synthesis design flow of on-chip networks for application-specific SoCs: the topology mapping phase. Application knowledge is leveraged here for cooptimization of application mapping, along with topology selection, allowing for irregular topologies. The synthesis algorithm proposed is based on the metric of network hops. “NoC Synthesis Flow for Customized Domain Specific Multiprocessor Systems-on-Chip,” by Davide Bertozzi, Antoine Jalabert, Srinivasan Murali, Rutuparna Tamhankar, Stergios Stergio, Luca Benini, and Giovanni De Micheli proposes a design process that provides a complete synthesis flow of on-chip networks. It starts from application specifications, continues through the mapping of the application onto topologies and selection of a topology, and culminates with the synthesis of router microarchitectures and simulation of the final network design that allows for further design-space exploration. Area and power budgets given by users guide the synthesis process toward delay and reliability targets. The work demonstrates how the application-specific nature of a class of SoCs allows designers to optimize the on-chip network architecture for the application suites. In addition, automating the design process leads to the realization of flexible network architectures that can be parameterized and fine-tuned for a wide range of applications. Both papers demonstrate the IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 16, NO. 2, FEBRUARY 2005 97

Efficient and reliable communication is essential for achieving high performance in a networked computing environment. Finite network resources bring about unavoidable competition among in-flight network packets, resulting in network congestion and, possibly, deadlock. Many techniques have been proposed to improve network performance by efficiently handling network congestion and potential deadlock. However, none of them provide an efficient way of accelerating the movement of network packets in congestion toward their destinations. In this paper, we propose a new mechanism for detecting and resolving network congestion and potential deadlocks. The proposed mechanism is based on efficiently tracking paths of congestion and increasing the scheduling priority of packets along those paths. This acts to throttle other packets trying to enter those congested regions - in effect, locking out packets from congested regions until congestion has had the opportunity to disperse. Simulation results show that the proposed technique effectively disperses network congestion and is also applicable in helping to resolve potential deadlock.

InfiniBand is becoming an industry standard both for communication between processing nodes and I/O devices, and for interprocessor communication. Instead of using a shared bus, InfiniBand employs an arbitrary (possibly irregular) switched point-to-point network. InfiniBand specification defines a basic management infrastructure that is responsible for subnet configuration, activation, and fault tolerance. After the detection of a topology change, management entities collect the current subnet topology. The topology discovery algorithm is one of the management issues that are outside the scope of the current specification. Preliminary implementations obtain the entire topological information each time a change is detected. In this work, we present and analyze an optimized implementation, based on exploring only the region that has been affected by the change.

As the level of chip integration continues to advance at a fast pace, the desire for efficient interconnects - whether on-chip or off-chip - is rapidly increasing. Traditional interconnects like buses, point-to-point wires and regular topologies may suffer from poor resource sharing in the time and space domains, leading to high contention or low resource utilization. In this paper, we propose a design methodology for constructing networks for special-purpose computer systems with well-behaved (known) communication characteristics. A temporal and spatial model is proposed to define the sufficient condition for contention-free communication. Based upon this model, a design methodology using a recursive bisection technique is applied to systematically partition a parallel system such that the required number of links and switches is minimized while achieving low contention. Results show that the design methodology can generate more optimized on-chip networks with up to 60% fewer resources than meshes or tori while providing blocking performance closer to that of a fully connected crossbar.

The InfiniBand architecture is a high-performance network technology for the interconnection of processor nodes and I/O devices using a point-to-point switch-based fabric. The InfiniBand specification defines a basic management infrastructure that is responsible for subnet configuration, activation, and fault tolerance. Subnet management entities and functions are described, but the specifications do not impose any particular implementation. We present and analyze a complete subnet management mechanism for this architecture. We allow to anticipate future directions to obtain efficient management protocols

Dynamic network reconfiguration is defined as the change from one routing function to another while the network is up and running. The main challenge is avoidance of deadlocks, while keeping restrictions on packet injection and forwarding minimal. Current approaches either require virtual channels in the network, or they work only for a limited set of routing algorithms. We present a methodology for devising deadlock free and dynamic transitions between an old and a new routing function. The methodology is independent of topology and puts no restrictions on either routing function. Furthermore, it does not require any virtual channels to guarantee deadlock freedom. This research is motivated by the current trend toward using increasingly larger Internet servers based on clusters of PCs and the very high availability requirements of those as well as other local, system, and storage area network-based systems

Support for arbitrary topologies has become more popular for system-area networks but very little has been done in trying to characterize their behavior and performance. Traditional parameters like diameter and bisection width are not sufficient for characterizing the irregularities that abound in such networks and fail to give much insight into throughput performance. A clustering approach for partitioning a network into clusters of richly-connected regions is proposed as a means of defining two performance-correlated characterization metrics: intercluster bandwidth index and intercluster link-cost index. The two characterization metrics are shown to have a strong correlation to saturation throughput when link and load distribution of a network is imbalanced. Simulation results also show that the clustering algorithm can be applied to a variety of network configurations and traffic scenarios, particularly irregular ones. With the proposed characterization metrics that correlate more strongly with performance, it is possible to classify networks into categories having similar performance.

Network-based parallel computing systems often require the ability to reconfigure the routing algorithm to reflect changes in network topology if and when voluntary or involuntary changes occur. The process of reconfiguring a network's routing capabilities may be very inefficient and/or deadlock-prone if not handled properly. We propose efficient and deadlock-free dynamic reconfiguration schemes that are applicable to routing algorithms and networks which use wormhole, virtual cut-through, or store-and-forward switching, combined with hard link-level flow control. One requirement is that the network architecture use virtual channels or duplicate physical channels for deadlock-handling as well as performance purposes. The proposed schemes do not impede the injection, transmission, or delivery of user packets during the reconfiguration process. Instead, they provide uninterrupted service, increased availability/reliability, and improved overall quality-of-service support as compared to traditional techniques based on static reconfiguration.

Handling deadlocks is essential for providing reliable communication paths between processing nodes in parallel computer systems. The existence of multiple message types and associated inter-message dependencies may cause message-dependent deadlocks in networks that are designed to be free of routing deadlock. Most methods currently used for dealing with message-dependent deadlocks require more system resources than are necessary and/or do not use system resources efficiently. This may have an adverse effect on system performance if resources are scarce. In this paper, we characterize the frequency of message-dependent deadlocks in multiprocessor/multicomputer systems. We also propose a handling technique for message-dependent deadlocks based on progressive deadlock recovery and evaluate its performance with other approaches. Results show that message-dependent deadlocks occur very infrequently under typical circumstances thus, rendering approaches based on avoiding them overly restrictive in the common case. The proposed technique relaxes restrictions considerably, allowing the routing of packets and the handling of message-dependent deadlocks to be much more efficient-particularly when network resources are scarce.

Efficient and reliable communication is essential for achieving high performance in a networked computing environment. Limited network resources bring about unavoidable competition among in-flight packets, resulting in network congestion and possibly deadlock. Many techniques have been proposed to improve performance by efficiently handling network congestion and deadlock. However, none of them provide an efficient way of accelerating the movement of packets involved in congestion onward to their destinations. In this paper, we propose a new mechanism for the detection and resolution of network congestion and deadlocks. The proposed mechanism is based on increasing the scheduling priority of packets involved in congestion and providing necessary resources for those packets to make forward progress. Simulation results show that the proposed technique outperforms previously proposed techniques by effectively dispersing network congestion.

The existence of multiple message types and associated inter-message dependencies may cause message-dependent deadlock in networks that are designed to be free of routing deadlock. Most methods currently used for dealing with message-dependent deadlocks require more system resources than are necessary and/or do not use system resources efficiently. This may have an adverse effect on system performance if resources are scarce. In this paper, we evaluate different approaches for handling message-dependent deadlocks, and we propose an alternative technique based on progressive deadlock recovery. Results show that the proposed technique relaxes restrictions considerably, allowing the routing of packets and handling of message-dependent deadlocks to be much more efficient-particularly when network resources are scarce.

This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory. A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks.

Network-based computing systems often require the ability to reconfigure the routing algorithm to reflect changes in network topology if and when those changes occur. The process of reconfiguring a network's routing capabilities may lead to deadlock if not handled properly. In this paper we propose efficient and deadlock-free dynamic reconfiguration techniques that are generically applicable to distributed routing algorithms and networks, including those which use wormhole switching. The proposed techniques do not impede the transmission of packets during the reconfiguration process, thus providing increased network availability and quality-of-service (QoS) support as compared to traditional techniques based on static reconfiguration.

This paper presents a theoretical model of resource allocations and dependencies in wormhole and virtual cut-through interconnection networks. This model allows various types of message blocking to be described precisely, including deadlock. The model distinguishes between messages involved in deadlock and those simply dependent upon deadlock, thus establishing a framework for evaluating the accuracy and correctness of deadlock detection mechanisms. The paper also identifies the necessary and sufficient conditions for the occurrence and resolution of deadlock in interconnection networks, thus providing efficiency and correctness criteria for deadlock resolution mechanisms. Theorems derived from the model are related to various routing algorithms which are based on deadlock recovery.

This paper characterizes how various network parameters influence message blocking and deadlocks in irregular networks. Information on blocking behavior is provided that is useful in making design trade-offs between restricting routing freedom and allowing the possibility for deadlocks to form in irregular networks. This work also identifies ways in which a network's susceptibility to deadlock can be reduced and provides guidelines for designing irregular networks which maximize routing flexibility and resource utilization. Finally, a new empirical evaluation methodology for classifying irregular topologies and relating network behavior to various classes of network topologies is introduced.

The development of fully adaptive, cut-through (wormhole) networks is important for achieving high performance in communication-critical parallel processor systems. Increased flexibility in routing allows network bandwidth to be used efficiently, but also creates more opportunity for cyclic resource dependencies to form which can cause deadlock. If not guarded against, deadlocks in routing make packets block in the network indefinitely and, eventually, could result in the entire network coming to a complete standstill. The paper presents a simple, flexible, and efficient routing approach for multicomputer interconnection networks which is based on progressive deadlock recovery as proposed to deadlock avoidance or regressive deadlock recovery. Performance is optimized by allowing the maximum routing freedom provided by network resources to be exploited. True fully adaptive routing is supported in which all physical and virtual channels at each node in the network are available to packets without regard for deadlocks. Deadlock cycles, upon forming, are efficiently broken in finite time by progressively routing one of the blocked packets through a connected, deadlock-free recovery path. This routing approach enables the design of high-throughput networks that provide excellent performance. Simulations indicate that progressive deadlock recovery routing can improve throughput by as much as 45 percent and 25 percent over leading deadlock avoidance-based and regressive recovery-based routing schemes, respectively.

A spate of deadlock avoidance-based and deadlock recovery-based routing algorithms have been proposed in recent years without full understanding of the likelihood and characteristics of actual deadlocks in interconnection networks. This work models the interrelationships between routing freedom, message blocking, correlated resource dependencies, and deadlock formation. It is empirically shown that increasing routing freedom, as achieved by allowing unrestricted routing over multiple physical and virtual channels, reduces the probability of deadlocks and the likelihood of other types of correlated message blocking that can degrade performance. Moreover, when true fully adaptive routing is used in k-ary n-cube networks with two or more virtual channels (wormhole OF virtual cut-through switched), it is empirically shown that deadlocks are virtually eliminated in networks with n/spl ges/2. These results indicate that deadlocks are very infrequent when the network and routing algorithm inherently provide sufficient routing freedom, thus increasing the viability of deadlock recovery routing strategies.

Networks of workstations (NOW) have gained importance in recent years. The interconnection network of NOW systems often consist of generic switches connected in an irregular topology. Traditionally, interconnection networks are characterized by their topological properties, such as number of nodes, diameter, and bisection width. These parameters are not sufficient in characterizing irregular networks. This research puts forth a new approach that characterizes both regular and irregular networks. A partitioning algorithm is proposed to break down a network topology into groups or clusters of nodes such that there is higher bandwidth within clusters than between clusters. By doing so, the potential bottlenecks of a network are identified. Furthermore, a characterization scheme based on measurement of these clusters is defined. The new scheme uses two parameters, the intercluster bandwidth index and intercluster link cost index to describe a network topology. Simulation results show that these two indices have stronger correlation to performance than traditional topological properties.

In this paper, we take a different approach to handle deadlocks and performance degradation. We propose the use of an injection limitation mechanism that prevents performance degradation near the saturation point and reduces the probability of deadlock to negligible values even when fully adaptive routing is used. We also propose an improved deadlock detection mechanism that only uses local information, detects all the deadlocks, and considerably reduces the probability of false deadlock detection over previous proposals. In the rare case when impending deadlock is detected, our proposed recovery technique absorbs the deadlocked message at the current node and later re-injects it for continued routing towards its destination. Performance evaluation results show that our new approach to deadlock handling is more efficient than previously proposed techniques.

Deadlock avoidance-based and deadlock recovery-based routing algorithms have been proposed in recent years without full understanding of the likelihood and characteristics of actual deadlocks in interconnection networks. This work models the interrelationships between routing freedom, message blocking, correlated resource dependencies and deadlock formation. We empirically show that increasing routing freedom, as achieved by allowing unrestricted routing over multiple virtual channels, makes deadlocks highly improbable and reduces the likelihood of other types of correlated message blocking behavior that can degrade performance. Our results further substantiate that recovery-based routing algorithms have a higher potential performance advantage over deadlock avoidance-based routing algorithms which, inherently, allow less routing freedom.

This paper presents a simple, efficient and cost effective routing strategy that considers deadlock recovery as opposed to prevention. Performance is optimized in the absence of deadlocks by allowing maximum flexibility in routing. Disha supports true fully adaptive routing where all virtual channels at each node are available to packets without regard for deadlocks. Deadlock cycles, upon forming, are efficiently broken by progressively routing one of the blocked packets through a deadlock-free lane. This lane is implemented using a central floating deadlock buffer resource in routers which is accessible to all neighboring routers along the path. Simulations show that the Disha scheme results in superior performance and is extremely simple, ensuring quick recovery from deadlocks and enabling the design of fast routers.