共查询到20条相似文献,搜索用时 31 毫秒
1.
Unicast in hypercubes with large number of faulty nodes 总被引:1,自引:0,他引:1
Qian-Ping Gu Shietung Peng 《Parallel and Distributed Systems, IEEE Transactions on》1999,10(10):964-975
Unicast in computer/communication networks is a one-to-one communication between a source node s and a destination node t. We propose three algorithms which find a nonfaulty routing path between s and t for unicast in the hypercube with a large number of faulty nodes. Given the n-dimensional hypercube Hn and a set F of faulty nodes, node uϵ Hn is called k-safe if u has at least k nonfaulty neighbors. The Hn is called k-safe if every node of Hn is k-safe. It has been known that for 0⩽k⩽n/2, a k-safe Hn is connected if |F|⩽2k(n-k)-1. Our first algorithm finds a nonfaulty path of length at most d(s,t)+4 in O(n) time for unicast between 1-safe s and t in the Hn with |F|⩽2n-3, where d(s,t) is the distance between s and t. The second algorithm finds a nonfaulty path of length at most d(s,t)+6 in O(n) time for unicast in the 2-safe Hn with |F|⩽4n-9. The third algorithm finds a nonfaulty path of length at most d(s,t)+O(k2) in time O(|F|+n) for unicast in the k-safe Hn with |F|⩽2k(n-k)-1 (0⩽k⩽n/2). The time complexities of the algorithms are optimal. We show that in the worst case, the length of the nonfaulty path between s and t in a k-safe Hn with |F|⩽2k(n-k)-1 is at least d(s,t)+2(k+1) for 0⩽k⩽n/2. This implies that the path lengths found by the algorithms for unicast in the 1-safe and 2-safe hypercubes are optimal 相似文献
2.
It is shown that for a given p (1<p ⩽n ), the n -cube network can tolerate up to p 2(n-p)-1 processor failures and remains connected provided that at most p neighbors of any nonfaulty processor are allowed to fail. This generalizes the result for p =n-1, obtained by A.-M Esfahanian (1989). It is also shown that the n -cube network with n ⩾5 remains connected provided that at most two neighbors of any processor are allowed to fail 相似文献
3.
A hypercube algorithm to solve the list ranking problem is presented. Let n be the length of the list, and let p be the number of processors of the hypercube. The algorithm described runs in time O(n /p ) when n =Ω(p 1+ε) for any constant ε>0, and in time O(n log n /p +log3 p ) otherwise. This clearly attains a linear speedup when n =Ω(p 1+ε). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication 相似文献
4.
Jenq J.-F. Sahni S. 《IEEE transactions on pattern analysis and machine intelligence》1992,14(12):1218-1224
An O (n 2) time serial algorithm is developed for obtaining the medial axis transform (MAT) of an n ×n image. An O (log n ) time CREW PRAM algorithm and an O (log2 n ) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O (n 2) processors. Two problems associated with the MAT, the area and perimeter reporting problem, are studied. An O (log n ) time hypercube algorithm is developed for both of them, where n is the number of squares in the MAT, and the algorithms use O (n 2) processors 相似文献
5.
Parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing are presented. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles for any number p of processors satisfying 1⩽p ⩽n /((log3n )(loglog n )2), where n is the input size. The lower bound results are established under no restriction on how the input is mapped into the local memories of the different processors 相似文献
6.
Abali B. Ozguner F. Bataineh A. 《Parallel and Distributed Systems, IEEE Transactions on》1993,4(5):572-581
A parallel sorting algorithm for sorting n elements evenly distributed over 2d p nodes of a d -dimensional hypercube is presented. The average running time of the algorithm is O((n log n )/p +p log 2n ). The algorithm maintains a perfect load balance in the nodes by determining the (kn /p )th elements (k 1,. . ., (p -1)) of the final sorted list in advance. These p -1 keys are used to partition the sorted sublists in each node to redistribute data to the nodes to be merged in parallel. The nodes finish the sort with an equal number of elements (n / p ) regardless of the data distribution. A parallel selection algorithm for determining the balanced partition keys in O(p log2n ) time is presented. The speed of the sorting algorithm is further enhanced by the distance-d communication capability of the iPSC/2 hypercube computer and a novel conflict-free routing algorithm. Experimental results on a 16-node hypercube computer show that the sorting algorithm is competitive with the previous algorithms and faster for skewed data distributions 相似文献
7.
Properties and performance of folded hypercubes 总被引:3,自引:0,他引:3
A new hypercube-type structure, the folded hypercube (FHC), which is basically a standard hypercube with some extra links established between its nodes, is proposed and analyzed. The hardware overhead is almost 1/n , n being the dimensionality of the hypercube, which is negligible for large n . For this new design, optimal routing algorithms are developed and proven to be remarkably more efficient than those of the conventional n -cube. For one-to-one communication, each node can reach any other node in the network in at most [n /2] hops (each hop corresponds to the traversal of a single link), as opposed to n hops in the standard hypercube. One-to-all communication (broadcasting) can also be performed in only [n /2] steps, yielding a 50% improvement in broadcasting time over that of the standard hypercube. All routing algorithms are simple and easy to implement. Correctness proofs for the algorithms are given. For the proposed architecture, communication parameters such as average distance, message traffic density, and communication time delay are derived. In addition, some fault tolerance capabilities of this architecture are quantified and compared to those of the standard cube. It is shown that this structure offers substantial improvement over existing hypercube-type networks in terms of the above-mentioned network parameters 相似文献
8.
Let φ(s ,a )=φ0(s ,a )+ a 1φ1(s )+a 2 φ2(s )+ . . .+a kφ k(s )=φ0(s )-q(s , a ) be a family of real polynomials in s , with coefficients that depend linearly on parameters a i which are confined in a k -dimensional hypercube Ωa . Let φ0(s ) be stable of degree n and the φi(s ) polynomials (i ⩾1) of degree less than n . A Nyquist argument shows that the family φ(s ) is stable if and only if the complex number φ0(j ω) lies outside the set of complex points -q (j ω,Ωa) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q (j ω,Ωa ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k , 0(k 3), and these critical frequencies correspond to the real nonnegative roots of some polynomials 相似文献
9.
It is shown that there is a continuously parameterized family F of n -dimensional single-input single-output (SISO) stabilizable detectable linear system Σ(p ) which contains at least one realization of each reduced, strictly proper transfer function of McMillan degree not exceeding n . The parameterization map p →Σ(p ) is a polynomial function in 2n indeterminates from an open convex polyhedron in R 2n to the linear space of all SISO n -dimensional linear systems 相似文献
10.
A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k . Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n ⩾k ⩾1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Δ and diameter d , gossip can be completed under a proper Δ edge-coloring in time (Δ-1)d +1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined 相似文献
11.
Structural controllability of time-invariant and time-varying systems when the input control sequences have a restricted length k is compared. The dimensions of controllable space coincide in the following three special cases: the input sequences have length k =2; the input sequences have k =n , where n is the size of the system (i.e., the ultimate controllability is the same in both cases); and for every length of input sequences provided that the system has a single input only. It is proved that there may appear a gap for every input length k such that 2< k ⩽n /2. The case when n /2<k <n is left open 相似文献
12.
Pritchard D.J. Nicole D.A. 《Parallel and Distributed Systems, IEEE Transactions on》1993,4(1):111-117
The authors introduce a multiprocessor interconnection network, known as cube-connected Mobius ladders, which has an inherently deadlock-free routing strategy and hence has none of the buffering and computational overhead required by deadlock-avoidance message passing algorithms. The basic network has a diameter φ of 4n -1 for n 2n+2 nodes and has a fixed node degree of 4. The network can be interval routed in two stages and can be represented as a Cayley graph. This is the only practical fixed degree topology of size O (2φ) which has an inherently deadlock-free routing strategy, making it ideally suited for medium and large sized transputer networks 相似文献
13.
A unified analytical model for computing the task-based dependability (TDB) of hypercube architectures is presented. A hypercube is deemed operational as long as a task can be executed on the system. The technique can compute both reliability and availability for two types of task requirements-I -connected model and subcube model. The I -connected TBD assumes that a connected group of at least I working nodes is required for task execution. The subcube TBD needs at least an m -cube in an n -cube, m ⩽ n , for task execution. The dependability is computed by multiplying the probability that x nodes (x ⩾I or x ⩾2m) are working in an n -cube at time t by the conditional probability that the hypercube can satisfy any one of the two task requirements from x working nodes. Recursive models are proposed for the two types of task requirements to find the connection probability. The subcube requirement is extended to find multiple subcubes for analyzing multitask dependability. The analytical results are validated through extensive simulation 相似文献
14.
Itai A. Kutten S. Wolfstahl Y. Zaks S. 《IEEE transactions on pattern analysis and machine intelligence》1990,16(4):415-420
The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O (n log k +n +kt ) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t -resilient algorithm is not always higher than that of a nonresilient one. The t -resilient algorithm is a systematic modification of an existing algorithm for a fault-free network 相似文献
15.
Computing the width of a set 总被引:1,自引:0,他引:1
Houle M.E. Toussaint G.T. 《IEEE transactions on pattern analysis and machine intelligence》1988,10(5):761-765
For a set of points P in three-dimensional space, the width of P , W (P ), is defined as the minimum distance between parallel planes of support of P . It is shown that W (P ) can be computed in O(n log n +I ) time and O(n ) space, where I is the number of antipodal pairs of edges of the convex hull of P , and n is the number of vertices; in the worst case, I =O( n 2). For a convex polyhedra the time complexity becomes O(n +I ). If P is a set of points in the plane, the complexity can be reduced to O(n log n ). For simple polygons, linear time suffices 相似文献
16.
A distributed knot detection algorithm for general graphs is presented. The knot detection algorithm uses at most O (n log n +m ) messages and O (m +n log n ) bits of memory to detect all knots' nodes in the network (where n is the number of nodes and m is the number of links). This is compared to O (n 2) messages needed in the best algorithm previously published. The knot detection algorithm makes use of efficient cycle detection and clustering techniques. Various applications for the knot detection algorithms are presented. In particular, its importance to deadlock detection in store and forward communication networks and in transaction systems is demonstrated 相似文献
17.
The problem of finding an internally stabilizing controller that minimizes a mixed H 2/H ∞ performance measure subject to an inequality constraint on the H ∞ norm of another closed-loop transfer function is considered. This problem can be interpreted and motivated as a problem of optimal nominal performance subject to a robust stability constraint. Both the state-feedback and output-feedback problems are considered. It is shown that in the state-feedback case one can come arbitrarily close to the optimal (even over full information controllers) mixed H 2/H ∞ performance measure using constant gain state feedback. Moreover, the state-feedback problem can be converted into a convex optimization problem over a bounded subset of (n ×n and n ×q , where n and q are, respectively, the state and input dimensions) real matrices. Using the central H ∞ estimator, it is shown that the output feedback problem can be reduced to a state-feedback problem. In this case, the dimension of the resulting controller does not exceed the dimension of the generalized plant 相似文献
18.
Chang J.H. Ibarra O.H. Pong T.-C. Sohn S.M. 《IEEE transactions on pattern analysis and machine intelligence》1988,10(4):590-593
An algorithm for convolving a k ×k window of weighting coefficients with an n ×n image matrix on a pyramid computer of O (n 2) processors in time O (logn +k 2), excluding the time to load the image matrix, is presented. If k =Ω (√log n ), which is typical in practice, the algorithm has a processor-time product O (n 2 k 2) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k . Thus, for convolving two {0, 1}-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state 相似文献
19.
Varvarigos E.A. Bertsekas D.P. 《Parallel and Distributed Systems, IEEE Transactions on》1993,4(2):144-154
Multinode broadcast (MNB) in a hypercube and in a ring network of processors is considered. It is assumed that the lengths of the packets that are broadcast are not fixed, but are distributed according to some probabilistic rule, and the optimal times required to execute the MNB are compared for variable and for fixed packet lengths. For large hypercubes, it is shown, under very general probabilistic assumptions on the packet lengths, that the MNB is completed in essentially the same time as when the packet lengths are fixed. In particular, the MNB is completed by time (1+δ)T s with probability at least 1-ϵ, for any positive ϵ and δ, where T s is the optimal time required to execute the MNB when the packet lengths are fixed at their mean, provided that the size of the hypercube is large enough. In the case of the ring, it is proved that the average time required to execute a MNB when the packet lengths are exponentially distributed exceeds by a factor of ln n the corresponding time for the case there the packet lengths are fixed at their mean, where n is the number of nodes of the ring 相似文献
20.
An application-specific architecture for the parallel calculation of the decimation in time and radix 2 fast Hartley (FHT) and Fourier (FFT) transforms is presented. A real sequence with N =2n data items is considered as input. The system calculates the FHT and the FFT in n and n +1 stages. respectively. The modular and regular parallel architecture is based on a constant geometry algorithm using butterflies of four data items and the perfect unshuffle permutation. With this permutation, the mapping of the algorithm in VLSI technology is simplified and the communications among processors are minimized. Organization of the processor memory based on first-in, first-out (FIFO) queues facilitates a systolic data flow and permits the implementation in a direct way of the complex data movements and address sequences of the transforms. This is accomplished by means of simple multiplexing operations, using hardwired control. The total calculation time is (N log2N )/4Q cycles for the FHT and N (1+log2N )/4Q cycles for the FFT, where Q is the number of processors ( Q = 2q, Q ⩽N /4) 相似文献