This article provides necessary and sufficient conditions for deadlock-free unicast and multicast routing with the path-based routing model in interconnection networks that use the wormhole switching technique. The theory is developed around three central concepts: channel waiting, False Resource Cycles , and valid destination sets . The first two concepts are suitable extensions to those developed for unicast routing by two authors of this article; the third concept has been developed by Lin and Ni. The necessary and sufficient conditions relax the requirements for deadlock-free routing, compared to techniques that provide only a sufficient condition. These necessary and sufficient conditions can be applied in a straightforward manner to prove deadlock freedom of newly developed adaptive routing algorithms for collective communication, which in turn will help in developing efficient and correct routing algorithms. The latter point is illustrated by developing two routing algorithms for multicast communication on 2D mesh architectures. The first algorithm uses fewer resources (channels) than an algorithm proposed in the literature but achieves the same adaptiveness. The second algorithm provides fully adaptive routing for both unicast and multicast messages.

Parallel algorithms for several common problems such as sorting and the FFT involve a personalized exchange of data among all the processors. Past approaches to doing complete exchange have taken one of two broad approaches: direct exchange or the indirect message-combining approaches. While combining approaches reduce the number of message startups, direct exchange minimizes the volume of data transmitted. This paper presents a family of hybrid algorithms for wormhole-routed 2D meshes that can effectively utilize the complementary strengths of these two approaches to complete exchange. The performance of hybrid algorithms using Cyclic Exchange and Scott's Direct Exchange are studied using analytical models, simulation, and implementation on a Cray T3D system. The results show that hybrids achieve lower completion times than either pure algorithm for a range of mesh sizes, data block sizes, and message startup costs. It is also demonstrated that barriers may be used to enhance performance by reducing message contention, whether or not the target system provides hardware support for barrier synchronization. The analytical models are shown useful in selecting the optimum hybrid for any given combination of system parameters (mesh size, message startup time, flit transfer time, and barrier cost) and the problem parameter (data block size).

The authors present efficient methods to determine the four usual branch conditions for a sum or difference, before the result of the addition or subtraction is available. The methods lead to the design of an early branch resolver which integrates well with a regular adder/subtracter, adding only a small amount of circuitry and almost no delay. The methods exploit the properties of half-adder form. Sums in half-adder form can be computed vary quickly (with the delay of a half adder), yet they have enough structure so that many of the properties of the final sum can be easily detected. The reduced latency for evaluating branch conditions means that an addition or subtraction and a dependent conditional instruction can execute in the same cycle with a consequent increase in instruction-level parallelism, and improved performance for both single-issue and superscalar processors.

Adaptive routing is widely regarded as a promising approach to improving interconnection network performance. Many designers of adaptive routing algorithms have used synthetic communication patterns, such as uniform and transpose traffic, to compare the performance of various adaptive routing algorithms with each other and with oblivious routing. These comparisons have shown that the average message latency is usually lower with adaptive routing. On the other hand, when a parallel program is executed on a multiprocessor the goal is to reduce the total execution time. We explain why improving the average message latency of a routing algorithm does not necessarily lead to a lower execution time for real applications. We support this observation by reporting simulation results for both adaptive and oblivious routing using communication derived from real applications. Specifically, we report the performance of various routing algorithms for directed acyclic graphs (DAGs) derived from the Cholesky factorization of sparse matrices. Our results show that there is little correlation between average message latency and the total execution time of a parallel program. Hence, average message latency does not seem to be a useful measure of the performance of a routing algorithm. This strongly suggests that current comparisons of routing algorithms do not provide a reliable indication of the performance improvements to be realized by executing programs on a multiprocessor with such a routing algorithm. We interpret these results and suggest several alternatives for further research.

We present an integrated adder/subtracter/zero-detector in which the zero detection completes well before the sum or difference is known. Previous zero detectors either required the sum to be available before they could complete, or were not well integrated with the ALU. We avoid these problems by exploiting the properties of half-adder form. Sums in half-adder form can be computed very quickly (with the delay of a half adder), yet they have enough structure so that many of the properties of the final sum can be easily detected. Our zero detector is faster than any previously described, requires only a small amount of additional circuitry in the ALU, and adds little or nothing to the overall delay of the ALU. We also examine some of the architectural implications of early zero detection: faster branching, more instruction-level parallelism, more powerful instructions, and reduced hardware needs for supporting speculative execution.

Parallel algorithms for several common problems such as sorting and the FFT involve a personalized exchange of data among all the processors. Past approaches to doing complete exchange have taken either the combining or the direct exchange approaches. While combining reduces the number of message startups, direct exchange minimizes the volume of data transmitted. This paper presents a family of hybrid algorithms for wormhole-routed 2D meshes that can effectively utilize the complementary strengths of these two approaches to complete exchange. The performance of hybrid algorithms using Cyclic Exchange [6] and Scott's Direct Exchange [5] are studied using analytical models as well as simulation. The results show that hybrids achieve lower completion times than either pure algorithm for a large range of mesh sizes, data block sizes and message startup costs. The analytical models may be used to select the optimum hybrid for any given combination of system parameters (mesh size, startup t...

Replicating sensors is desirable, not only to tolerate sensor failures, but to increase the average accuracy of the ensemble of replicated sensors beyond that obtainable with a single sensor. Such replication is used in a multi-sensor environment or in a distributed-sensor network. Following Marzullo (1990), the authors have modeled a continuous valued sensor as an interval of real numbers containing the physical value of interest. Given n sensors of which at most f can suffer arbitrary failures, this paper presents an efficient O(n/spl middot/log(n)) fault-tolerant algorithm (J/FTA) whose output is reliable (guaranteed to contain the correct value at all times) and is fairly accurate when f

We study the computational, communication, and scalability characteristics of a Computational Fluid Dynamics application, which solves the time accurate flow field of a jet using the compressible Navier-Stokes equations, on a variety of parallel architectural platforms. The platforms chosen for this study are a cluster of workstations (the LACE experimental testbed at NASA Lewis), a shared memory multiprocessor (the Cray YMP), distributed memory multiprocessors with different topologies - the IBM SP and the Cray T3D. We investigate the impact of various networks, connecting the cluster of workstations, on the performance of the application and the overheads induced by popular message passing libraries used for parallelization. The work also highlights the importance of matching the memory bandwidth to the processor speed for good single processor performance. By studying the performance of an application on a variety of architectures, we are able to point out the strengths and weaknesses of each of the example computing platforms

An important open problem in interconnection network routing has been to characterize the conditions under which routing algorithms are deadlock-free.Although this problem has been resolved for restricted classes of routing algorithms, no general solution has been found.In this paper, we solve this problem by proving a necessary and sufficient condition that can be used for any interconnection network routing algorithm, as long as only local information is required for routing.Our proof technique is universal: it can be used with any switching technique that is not inherently deadlock-free.This includes switching techniques such as wormhole routing, store-and-forward routing, and virtual cut-through.The proof technique for the necessary and sufficient condition introduces a new type of dependency graph, the buffer waiting graph, which omits most dependencies that cannot be used to create a deadlock configuration.Our methodology is illustrated by proving deadlock freedom for a store-and-forward routing algorithm for meshes and a wormhole routing algorithm for hypercubes.The hypercube routing algorithm requires only two virtual channels per physical channel and is more adaptive than any previously proposed wormhole routing algorithm for hypercubes.

Replicating sensors is desirable not only to tolerate sensor failures but also to increase the expected accuracy of the ensemble of replicated sensors beyond that obtainable with a single one. Such replication is used in a multisensor environment or in a distributed sensor network. We model a continuous valued sensor as an interval of real numbers containing the physical value of interest. Given n sensors of which at most f of them can suffer arbitrary failures, we present an efficient O(n log n) fault tolerant algorithm whose output is reliable when f>

Proposes a versatile architecture for a distributed sensor network which consists of a multilevel network with the nodes (processing element/sensor pairs) at each level interconnected as a deBruijn network. The authors show that this multilevel network has reasonable fault tolerance, admits simple and decentralized routing, and offers easy extensibility. They model information from sensors as real valued intervals and derive an interesting property related to information integration in the presence of faults. Using this property, the search for a fault is narrowed down to two potentially faulty sensors or communication links. In a distributed environment, information has to be integrated from "temporally close" signals in the presence of imperfect clocks in a distributed environment. The authors apply the results of past research in this area to state various relationships between the clocks of the processing elements in the network for proper information integration.>

Issues related ro cumpiling for shared memory multiprocessors with multilevel memory hierarchies are discussed. In particular, a method using simple and regular sections for parallelizing nested iterative loops with constant dependence distances is described.

A deadlock-free fully adaptive routing algorithm for 2D meshes which is optimal in the number of virtual channels required and in the number of restrictions placed on the use of these virtual channels is presented. The routing algorithm imposes less than half as many routing restrictions as any previous fully adaptive routing algorithm. It is also proved that, ignoring symmetry, this routing algorithm is the only fully adaptive routing algorithm that achieves both of these goals. The algorithm exploits the fact that for some adaptive routing algorithms, deadlock freedom is possible even when cycles are present in the channel dependency graph. The implementation of the routing algorithm requires relatively simple router control logic. The routing algorithm requires only the minimum number of virtual channels even when extended to arbitrary dimension meshes, yielding a dramatic reduction in the number of virtual channels needed to support fully adaptive routing. Compared to all previous algorithms which required an exponential number of virtual channels with the dimension of the mesh, the new algorithm requires only 4n - 2 virtual channels for an n-dimensional mesh.

The computational, i.e. architectural, algorithmic, and synchronization, issues related to competitive information integration in a distributed sensor network (DSN) are addressed. The proposed DSN architecture consists of a set of binary trees whose roots are fully connected. Each node of the tree has a processing element and one or more sensors associated with it. The information from each of the sensors has to be integrated in such a manner that the communication costs are low and that the real time needs are met. An information integration algorithm that has a low message cost (linear in the number of nodes of the network) and a low distributed computation cost is presented. The problems associated with synchronizing information to be integrated in the presence of imperfect clocks is considered. The fault tolerant features of the network and the integration algorithm are discussed.>