Connectivity of a network dictates the routability and survivability of a network. the paper investigates the edge connectivity problems in distributed environments. For a given network or graph G, one can distributiv...
详细信息
Connectivity of a network dictates the routability and survivability of a network. the paper investigates the edge connectivity problems in distributed environments. For a given network or graph G, one can distributively find bridges in the network first then find the 2-edge connected components. Both algorithms proposed, bridge finding and 2-edge connected component identifying, require only O(m) message complexity, where m is the number of edge in G. the paper also shows an efficient distributed 2-edge cutset algorithm that has O(n/sup 2/) message complexity, where n is the number of nodes in G.< >
Maekawa's algorithm is one of well-known distributed mutual exclusion algorithms and requires only O(/spl radic/N) messages per CS execution, where N is the number of sites in the system. However, Maekawa's al...
详细信息
Maekawa's algorithm is one of well-known distributed mutual exclusion algorithms and requires only O(/spl radic/N) messages per CS execution, where N is the number of sites in the system. However, Maekawa's algorithm can work well only if the pipelining property is satisfied (i.e., between any pair of sites, messages are delivered in the order in which they are sent). In this paper, we show how to modify Maekawa's algorithm to let it work well even when the pipelining property is no longer satisfied. Moreover, we discuss some interesting results of a simulation study of Maekawa'a algorithm which show that more than N messages may be needed in Maekawa's algorithm.< >
It is shown how to embed an x/sub 1/ /spl times/ 1/sub 1/ mesh M/sub 1/ into an s/sub 2/ /spl times/ t/sub 2/ mesh M/sub 2/, where s/sub 1/ /spl times/ t/sub 2/, s/sub 1/
It is shown how to embed an x/sub 1/ /spl times/ 1/sub 1/ mesh M/sub 1/ into an s/sub 2/ /spl times/ t/sub 2/ mesh M/sub 2/, where s/sub 1/ /spl times/ t/sub 2/, s/sub 1/ < t/sub i/ (i = 1,2) such that the dilation is minimized. It is assumed that load = 1 and expansion = 1. For each case there is shown a lower bound on the dilation and a corresponding embedding method. the dilations by these embedding algorithms either match a lower bound or are very close to a lower bound.< >
We present a parallel algorithm for solving the dual transshipment problem. the traditional dual simplex method does not offer much scope for parallelization, because it moves from one basic feasible solution to anoth...
详细信息
We present a parallel algorithm for solving the dual transshipment problem. the traditional dual simplex method does not offer much scope for parallelization, because it moves from one basic feasible solution to another, performing one pivot operation at a time. We present a new method called modified network dual simplex method which uses concurrent pivots. this departure from the traditional LP approach raises several issues such as the need to convert a non-basic feasible solution to a basic feasible solution. We present our strategies to handle these issues as well as the corresponding parallel algorithms. We also present results of testing this algorithm on large graphs to solve the integrated layout compaction and wire balancing problem.< >
In the context of parallel and distributed programming, program execution models are required to obtain a better understanding of the behavior, properties, and characteristics of parallel and distributed applications....
详细信息
In the context of parallel and distributed programming, program execution models are required to obtain a better understanding of the behavior, properties, and characteristics of parallel and distributed applications. One commonly adopted approach consists of representing an execution as a set of events and relations that capture the ordering of the events. the main disadvantages of most existing models are (1) the gap between the user's view of the execution and the program execution model, and (2) their inability to uniquely characterize an execution in terms of program behavior. the goal of this paper is to solve these two problems by first defining a new program execution model that enables more coarse-grained events to be considered, and then determining sufficient conditions for the model to uniquely identify the sequence of local states each process goes through.< >
We investigate the problem of broadcasting multiple messages in a message-passing system that supports simultaneous send and receive. the system consists of n processors, one of which has m messages to broadcast to th...
详细信息
We investigate the problem of broadcasting multiple messages in a message-passing system that supports simultaneous send and receive. the system consists of n processors, one of which has m messages to broadcast to the other n-1 processors. the processors communicate in rounds. In each round, a processor can simultaneously send a message to one processor and receive a message from another processor. the goal is to broadcast the m messages among the n processors in the minimal number of communication rounds. the lower bound on the number of rounds required is (m-1)+[log n]. We present an algorithm for this problem that requires at most m+[log n] communication rounds, for any values of m and n.< >
Quorum-based protocols can be formalized in terms of the data structures they use. these data structures, called quorum structures, include quorum sets, coteries, and bicoteries. In this paper, we present measures tha...
详细信息
Quorum-based protocols can be formalized in terms of the data structures they use. these data structures, called quorum structures, include quorum sets, coteries, and bicoteries. In this paper, we present measures that can be used to determine the relative importance of each node in a quorum structure. By knowing the relative importance of each node in the system, it is possible to improve the overall system reliability by investing more effort on improving the reliability of important nodes. Secondly, such measures can be used to accurately define symmetry in a distributed system. A quorum structure is symmetrical, if all nodes are equally important. Finally, since several well known protocols are based on composition, we present simple recursive methods to compute the importance of nodes in composite quorum structures.< >
this paper presents a solution to the (processor) group membership problem. the methodology followed in designing the algorithm is summarized by the option to optimize the performance of the algorithm under the assump...
详细信息
this paper presents a solution to the (processor) group membership problem. the methodology followed in designing the algorithm is summarized by the option to optimize the performance of the algorithm under the assumption that no failure occurs during its run, and adding the appropriate level of fault tolerance by implementing the algorithm as periodic and self-stabilizing. the performance indicators we consider are the number of message exchanges (between neighbor units) and the time needed to reach the agreement. the algorithm relies on the existence of three basic distributed services: clock synchronization, reliable diffusion, and local agreement between two neighbors. We do not assume the presence of a reliable datagram service, which is more complex to implement than the previous. the presence of a privileged unit (initiator) is avoided, so elections are not needed.< >
Some parallel applications do not require a precise imitation of the behavior of the physically shared memory programming model. Consequently, certain parallel machine architectures have elected to emphasize different...
详细信息
Some parallel applications do not require a precise imitation of the behavior of the physically shared memory programming model. Consequently, certain parallel machine architectures have elected to emphasize different required coherency properties because of possible efficiency gains. this has led to various definitions of models of store coherency. these definitions have not been amenable to detailed analysis and, consequently, inconsistencies have resulted. In this paper a unified framework is proposed in which different models of store coherency are developed systematically by progressively relaxing the constraints that they have to satisfy. A demonstration is given of how formal reasoning can be carried out to compare different models. Some real-life systems are considered and a definition of a version of weak coherency is found to be incomplete.< >
Nonlinear filters have been used in many signal processing applications, for example, to obtain optimum signal extraction or detection in the presence of random noise. the weighted median filter (WMF), of which the st...
详细信息
Nonlinear filters have been used in many signal processing applications, for example, to obtain optimum signal extraction or detection in the presence of random noise. the weighted median filter (WMF), of which the standard median is a special case, is a novel nonlinear technique designed for 2D image processing. A major advantage of the WMF is its flexibility in design to deal with a wide variety of properties. this paper describes a commonly used class W(4,4,1) of the WMF. AS with most nonlinear methods, the computational demands of this technique are high and require a non-trivial number of "expensive" operations. A data parallel approach for efficient implementation of the WMF is described and implemented on two architecturally dissimilar supercomputers, the Convex C3840 and the Connection Machine CM-200. An analysis of the performance obtained from these two high performance parallel platforms is presented.< >
暂无评论