We focus on the data models for storing the data generated by radio frequency identification (RFID) transactions and architectures for processing such data. We consider the supply chain comprised of the manufacturer, distributor, retailer, and the consumer. We discuss details of the data generated by RFID transactions and data models to store such data. Different organizations in the supply chain may use this data for different applications such as automatic product ordering, shelf replenishment, and product recall. We present models to anticipate the data requirements generated by RFID transactions and indicate how existing enterprise applications can be adapted to handle RFID data. The results presented in this paper will help a practitioner to 1) design and develop databases and applications for handling RFID data and 2) significantly reduce the storage requirements of RFID data. Using the data architectures, we discuss two supply chain applications-product recall and shelf replenishment-in detail. We present analytical models for the cost and time required for shelf replenishment in a retail store.

The current fault-tolerant routing methods require extensive changes to practical routers such as the Cray T3D's dimension-order router to handle faults. In this paper, we propose methods to handle faults in multicomputers with dimension-order routers with simple changes to router structure and logic. Our techniques can be applied to current implementations in which the router is partitioned into multiple modules and no centralized crossbar is used. We consider arbitrarily located faulty blocks and assume only local knowledge of faults. We apply our techniques for torus networks and show that, with as few as four virtual channels per physical channel, deadlock- and livelock-free routing can be provided even with multiple faults and multimodule implementation of routers. Our simulations of the proposed technique for 2D tori and mesh indicate that the performance degradation is similar to that seen in the case of cross-bar based designs previously proposed.

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of resource deadlocks has not been addressed in many previously proposed wormhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. We provide upper bounds for the number of consumption channels required to avoid deadlocks. In addition, we present a new multicast routing algorithm, column-path, which is based on the well-known dimension-order routing used in many multicomputers and multiprocessors. Therefore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multicast routing algorithms. Our results show that for multicast traffic, the column-path routing offers higher throughputs, while the multipath algorithm offers lower message latencies. Another result of our study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good performance provided the number of destinations is small.

Recent multiprocessors such as the Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate adaptivity into such routers with simple changes to the router structure and logic. We show that with as few as two virtual channels per physical channel, adaptivity can be provided to handle nonuniform traffic in multidimensional meshes.

In this paper, we first evaluate the performance degradation caused by unequal bandwidths on the execution of conventional parallel algorithms such as the fast Fourier transform on an ATM-based Network of Workstations. We then present a strategy based on dynamic redistribution of data points to reduce the bottlenecks caused by unequal bandwidths. We also extend this strategy to deal with processor heterogeneity. Using analysis and simulation we show that there is a considerable reduction in the runtime if the proposed redistribution strategy is adopted. The basic idea presented in this paper can also be used to improve the runtimes of parallel applications in connection-oriented environments.

The time-slot assignment (TSA) problem in a TDM switching system is to find a conflict-free assignment of traffic-units to slots such that the frame-length is minimized. In this paper, we develop a new parallel algorithm for the TSA problem in hierarchical switching systems (HSS). To design the parallel algorithm, we first reduce the TSA problem to the problem of routing permutations in three-stage Clos networks; we also show how this reduction can be achieved in polylogarithmic time using a polynomial number of processors on the EREW PRAM model. Once this reduction is achieved, we use existing parallel algorithms in literature to route permutations in Clos networks. The overall time-complexity of our parallel algorithm is O(log/sup 3/ X) using O(MX) processors, where X=max{M, L}, M is the number of inputs of the HSS, and L is the length of the time-slot assignment. This result is a significant improvement upon the earlier parallel algorithms, which require O(M/sup 2/ log M log L) time and O(ML) processors to solve the TSA problem.

A technique to enhance multicomputer routers for fault-tolerant routing with modest increase in routing complexity and resource requirements is described. This method handles solid faults in meshes, which includes all convex faults and many practical nonconvex faults, for example, faults in the shape of L or T. As examples of the proposed method, adaptive and nonadaptive fault-tolerant routing algorithms using four virtual channels per physical channel are described.

The current multiprocessors such as Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate fault-tolerance into such routers with simple changes to the router structure and logic. The previously known fault-tolerant routing methods assume centralized crossbar based routers and are not applicable to multiprocessors with PDRs. The proposed technique works for convex fault model, using only local knowledge of faults. Using the proposed techniques and as few as four virtual channels per physical channel, torus networks with PDRs can handle faults without compromising deadlock- and livelock-freedom. Simulations for 2-dimensional torus and mesh networks show that the resulting fault-tolerant PDRs have performances similar to those of the crossbar based routers.

We study the semi-rearrangeably nonblocking (SRN) operation of asymmetrical three-stage Clos (1953) switching networks in the multirate environment. We develop a basic algorithm that balances the established connections among middle-stage switches by performing a small number of rearrangements per disconnection. For this algorithm, we first derive general conditions under which rearranging from a single middle-stage switch is sufficient to achieve SRN operation. In the most general case, however, a sequence of rearrangements from several middle-stage switches may be required for SRN operation. An algorithm to achieve this sequence of rearrangements is presented and its correctness is proved. The minimum resource requirements to achieve SRN operation, in terms of the number of middle-stage switches, are derived for various cases.

This paper presents a framework to design fully-adaptive, deadlock-free wormhole algorithms for a variety of network topologies. The main theoretical contributions are: (a) design of new wormhole algorithms using store-and-forward algorithms, (b) a sufficient condition for deadlock free routing by the wormhole algorithms so designed, and (c) a sufficient condition for deadlock free routing by these wormhole algorithms with centralized flit buffers shared among multiple channels. To illustrate the theory, several wormhole algorithms based on store-and-forward hop schemes are designed. The hop-based wormhole algorithms can be applied to a variety of networks including torus, mesh, de Brujin, and a class of Cayley networks, with the best known bounds on virtual channels for minimal routing on the last two classes of networks. An analysis of the resource requirements and performances of a proposed algorithm, called negative-hop algorithm, with some of the previously proposed algorithms for torus and mesh networks is presented.

Power system transient stability analysis computes the response of the rapidly changing electrical components of a power system to a sequence of large disturbances followed by operations to protect the system against the disturbances. Transient stability analysis involves repeatedly solving large, very sparse, time varying non-linear systems over thousands of time steps. In this paper, we present parallel implementations of the transient stability problem in which we use direct methods to solve the linearized systems. One method uses factorization and forward and backward substitution to solve the linear systems. Another method, known as the W-Matrix method, uses factorization and partitioning to increase the amount of parallelism during the solution phase. The third method, the Repeated Substitution method, uses factorization and computations which can be done ahead of time to further increase the amount of parallelism during the solution phase. We discuss the performance of the different methods implemented on a loosely coupled, heterogeneous network of workstations (NOW) and the SP2 cluster of workstations.

We present simple methods to enhance the current minimal wormhole routing algorithms developed for high radix, low dimensional mesh networks for fault tolerant routing. We consider arbitrarily located faulty blocks and assume only local knowledge of faults. Messages are routed minimally when not blocked by faults and this constraint is relaxed to route around faults. The key concept we use is a fault ring consisting of fault free nodes and links can be formed around each fault region. Our fault tolerant techniques use these fault rings to route messages around fault regions. We show that, using just one extra virtual channel per physical channel, the well known e cube algorithm can be used to provide deadlock free routing in networks with nonoverlapping fault rings; there is no restriction on the number of faults. For the more complex faults with overlapping fault rings, four virtual channels are used. We also prove that at most four additional virtual channels are sufficient to make fully adaptive algorithms tolerant to multiple faulty blocks in n dimensional meshes. All these algorithms are deadlock and livelock free. Further, we present simulation results for the e cube and a fully adaptive algorithm fortified with our fault tolerant routing techniques and show that good performance may be obtained with as many as 10% links faulty.>

The problem of placing resources in a k-ary n-cube (k>2) is considered in this paper. For a given j/spl ges/1, resources are placed such that each nonresource node is adjacent to j resource nodes. We first prove that perfect j-adjacency placements are impossible in k-ary n-cubes if n>

Finding genes unequivocally in DNA sequences is one of the key goals of the Human Genome project. The human genome is a 3 billion character long DNA sequence and is estimated to contain about 100000 genes. It has been shown by several biologists that genes in a DNA sequence satisfy certain special properties. We use a combination of these properties to design a serial algorithm for gene-finding. To speed up the process of finding genes in long DNA sequences (of the order of /spl ges/100000 characters), we design a parallel algorithm for gene-finding. We have implemented the parallel gene-finding algorithm on the CM-5 multicomputer as well as on a network of HP Apollo workstations under Parallel Virtual Machine software package. Experimental results indicate that our algorithms predict genes with reasonable accuracy.>

In this paper, we study the nonblocking operation of asymmetrical three-stage Clos networks. We consider a control algorithm for operating the. asymmetrical Clos networks in the nonblocking mode. We derive sufficient conditions under which these networks are nonblocking for this control algorithm. Further, we provide results on the number of faults tolerated by the algorithm in the nonblocking mode of operation. We next design a different control algorithm for nonblocking operation of asymmetrical Clos networks. Using simulation results, the new control algorithm is shown to perform better than the previous one in terms of network utilization, blocking probability and fault-tolerance.

We present a method to enhance wormhole routing algorithms for deadlock-free fault-tolerant routing in tori. We consider arbitrarily-located faulty blocks and assume only local knowledge of faults. Messages are routed via shortest paths when there are no faults, and this constraint is only slightly relaxed to facilitate routing in the presence of faults. The key concept we use is that, for each fault region, a fault ring consisting of fault free nodes and physical channels can be formed around it. These fault rings can be used to route messages around fault regions. We prove that at most four additional virtual channels are sufficient to make any fully-adaptive algorithm tolerant to multiple faulty blocks in torus networks. As an example of this technique, we present simulation results for a fully-adaptive algorithm and show that good performance can be obtained with as many as 10% links faulty.

We present simple techniques to enhance the e-cube algorithm for fault-tolerant routing in mesh networks. These techniques are based on the concept of fault rings, which are formed using fault free nodes and links around each fault region. We use fault rings to enhance the e-cube to route messages in the presence of rectangular block faults. We show that if fault rings do not overlap with one another-the sets of links in fault rings are pairwise disjoint, then two virtual channels per physical channel are sufficient to make the e-cube tolerant to any number of faulty blocks. For more complex cases such as overlapping fault rings and faults on network boundaries, three or four virtual channels are used. In all cases, the routing guarantees livelock and deadlock free delivery of each and every message injected into the network. Our simulation results for isolated faults indicate that the proposed method provides acceptable performance with as many as 10 percent faulty links.>

In this paper, we present efficient sequential and parallel algorithms for computation of time-slot assignments in SS/TDMA (satellite-switched/time-division multiple-access) systems with variable-bandwidth beams. These algorithms are based on modeling the time-slot assignment (TSA) problem as a network-flow problem. Our sequential algorithm, in general, has a better time-complexity than a previous algorithm due to Gopal, et al. (1982) and generates fewer switching matrices. If M (N) is the number of uplink (downlink) beams, L is the length of any optimal TSA, and /spl alpha/ is the maximum bandwidth of an uplink or downlink beam, our sequential algorithm takes O((M+N)/sup 3/min(MN/spl alpha/,L)) time to compute an optimal TSA when the traffic-handling capacity of the satellite is of the same order as the total bandwidth of the links. Our parallel algorithm uses L/2 processors and has a time-complexity of O((M+N)/sup 3/logL) on a PRAM model of parallel computation. We then generalize this algorithm to P/spl les/L/2 processors and describe an efficient implementation of the algorithm on a hypercube multiprocessor with P processors. A massively-parallel version of the algorithm runs in O((M+N)/sup 2/log(M+N)logL) time on (M+N)L/2 processors.>

Improvement of message latency and network utilization in torus interconnection networks by increasing adaptivity in wormhole routing algorithms is studied. A recently proposed partially adaptive algorithm and four new fully-adaptive routing algorithms are compared with the well-known e-cube algorithm for uniform, hotspot, and local traffic patterns. Our simulations indicate that the partially adaptive north-last algorithm, which causes unbalanced traffic in the network, performs worse than the nonadaptive e-cube routing algorithm for all three traffic patterns. Another result of our study is that the performance does not necessarily improve with full-adaptivity. In particular, a commonly discussed fully-adaptive routing algorithm, which uses 2n virtual channels per physical channel of a k-ary n-cube, performs worse than e-cube for uniform and hotspot traffic patterns. The other three fully-adaptive algorithms, which give priority to messages based on distances traveled, perform much better than the e-cube and partially-adaptive algorithms for all three traffic patterns. One of the conclusions of this study is that adaptivity, full or partial, is not necessarily a benefit in wormhole routing.

Abstract In this paper, we study routing problems in a general class of asymmetrical three‐stage Clos networks. This class covers many asymmetrical three‐stage networks considered by earlier researchers. We derive necessary and sufficient conditions under which this class of networks is rearrangeable with respect to a set ofmulticonnections, i.e., connections between subsets of input and output terminals. We first model the routing problem in these networks as a network‐flow problem. If the number of switching elements in the first and last stages of the network isO(f)and the number of switching elements in the middle stage ism, then the network‐flow model yields a routing algorithm with running timeO(mf3). We then show that the problem of routing a set of multiconnections in an asymmetrical Clos network can be transformed into the well‐studied problem of routing a set of pairwise connections in a more symmetric form of the network. This approach results in a routing algorithm with complexityO(mK2), whereKis the aggregate capacity of the interstage links in the network. ©1993 by John Wiley & Sons, Inc.

It is shown that any hierarchical switching system can be modeled by a special class of flow networks called unit networks. Using the results available for finding maximum flow through a unit network, a time-slot assignment (TSA) algorithm that runs in O(min(L,M/sup 2/)*min(N, square root M)*M/sup 2/) time is presented. This is an O(max(M/N, square root M)) improvement over the TSA algorithm proposed by M.A. Bonucelli (1989).>

Presents parallel algorithms for computation of time-slot assignments in time-division multiplex (TDM) switching systems. The algorithms apply to a general class of TDM switching systems called hierarchical switching systems (HSS), which have a three-stage switching structure. The algorithms are based on modeling the time-slot assignment problem as a network-flow problem. Previous algorithms for finding an optimal time-slot assignment in these switching systems are inherently sequential and no parallel algorithms are known for this problem. If M is the number of users of the switching system, N is the switch-size, and L is the length of an optimal time-slot assignment, the best-known sequential TSA algorithm runs in O(M/sup 2/.min(N, square root M).min(L, M/sup 2/)) time. The authors first describe an algorithm using L/2 processors with running time O(M/sup 3/ log L) on a PRAM model of computation. They then generalize it to P>

The authors present an incremental algorithm for scheduling traffic in a general class of time-division multiplexed (TDM) switching systems used in satellite and terrestrial communication networks. Instead of recomputing the time slot assignment (TSA) for each frame of traffic, this algorithm computes a TSA for a new frame by modifying the known TSA of the previous frame. The algorithm takes O(M/sup 2/+cM) time for finding an optimal TSA in a hierarchical switching system, where M is the number of users and c is the number of changes between the traffic demands of two consecutive frames. The algorithm uses a two-step process. The first step transforms the TSA problem in the hierarchical switching system (HSS) into an equivalent TSA problem in a simple TDM switching system. The second step uses an incremental algorithm to find a TSA for the latter. The second step exploits the correspondence between the TSA problem and the rearrangement problem in a Clos three-stage network. When the traffic demands in consecutive frames overlap to a significant extent, the incremental algorithm provides considerable speedup over previous algorithms.>

The fault-tolerance capability of one-sided crosspoint networks is analyzed with respect to crosspoint faults. Because of the correspondence between one-sided crosspoint networks and multiple-bus interconnection networks, the analysis also applies to multiple-bus configurations, where M buses are used to interconnect N processors. Upper bounds are established on the size of a fault set to sustain a given level of connectivity. Two modes of operation are considered, namely, nonblocking and rearrangeable. A complete nonblocking switch matrix with N ports has N/sup 2//2 crosspoints. It is shown that at most N/2-1 faulty crosspoints can be tolerated in the case of nonblocking operation.>

The effect of nonuniform traffic patterns is studied based on simulation and analysis when two multistage networks are used in parallel to interconnect processors and memory modules in a shared-memory system. The networks considered are identical copies of buffered multi stage networks. The authors consider the following two strategies to distribute the total traffic between the two networks: distribute the traffic randomly among the networks, and route the nonuniform component of the traffic to one network and the uniform component to the other. To facilitate the implementation of these strategies in a system, a technique to detect nonuniformities in the network traffic at run-time and change the routing strategy dynamically is discussed. The authors compare this technique to an ideal scheme by means of analysis and simulation. The results show that the run-time detection scheme performs very close to the ideal case. The effectiveness of dual networks in tolerating short bursts of nonuniform traffic is also demonstrated.>

A set of routing criteria is proposed for circuit-switched hypercubes that exploit the flexibility provided by the hypercube. The routing criteria are provably deadlock-free and route messages along shortest paths. The number of shortest paths allowed by the routing criteria is more than one for most source-destination pairs. It is shown that the flexibility provided by the routing criteria can be used to limit the negative effects due to component-failures. The exact number of disrupted source-destination pairs are derived in the presence of a single faulty link or a single faulty node. It is shown that these numbers can be minimized using the relabeling techniques proposed. It is shown that the criteria, if used effectively, lead to a significant improvement in performance over the e-cube routing strategy for non-uniform traffic.>

The authors present efficient sequential and parallel algorithms for computation of time-slot assignments in SS/TDMA (satellite-switched/time-division multiple-access) systems with variable-bandwidth beams. These algorithms are based on modeling the time-slot assignment (TSA) problem as a network-flow problem. If M(N) is the number of uplink (downlink) beams, L is the length of any optimal TSA, and alpha is the maximum bandwidth of an uplink or downlink beam, the sequential algorithm takes O((M+N)/sup 3/ min (M N alpha , L)) time to compute an optimal TSA, when the traffic-handling capacity of the satellite is of the same order as the total bandwidth of the links. The parallel algorithm uses L/2 processors and has a time-complexity of O((M+N)/sup 3/ log L) on a probabilistic random access machine (PRAM) model of parallel computation. The authors then generalize this algorithm to P>

The authors study methods for routing data in supercomputers that use multistage interconnection networks (MINs) in the presence of faulty components in the network. These methods are applicable to existing multiprocessors such as the IBM GF11 and RP3. These methods are based on the concept of dynamic full-access (DFA) which refers to the ability of the network to route data from any processor in the system to any other processor in a finite number of passes through the network. The authors introduce a graph-model called the DFA graph of a MIN and show how it can be used to determine the DFA capability of the MIN under a given set of network faults. When the faults in the network satisfy certain special properties, algorithms for routing any arbitrary permutation in a faulty Benes network and any Omega permutation in a faulty Omega network are presented.>

The authors establish upper and lower bounds for the number of crosspoints required in a one-sided crosspoint switching network to provide a given level of connectivity. Two modes of operation are considered, namely, nonblocking and rearrangeable. A complete nonblocking switch matrix with N ports has N/sup 2//2 crosspoints. The authors show that this number can be reduced by at most N/2-1 crosspoints for nonblocking operation. If rearrangeable operation is allowed, however, as many as 25% of the crosspoints can be removed. An analysis is made of the relationship between the number of crosspoints removed and the maximum number of rearrangements of connections needed. Also introduced are algorithms for rearrangement of connections in both single-chip and partitioned implementations with reduced numbers of crosspoints.>