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...
详细信息
ISBN:
(纸本)081864222X
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.
In this paper, we propose a new parallel genetic algorithm (GA), called Extended distributed Genetic Algorithm (EDGA), for channel routing problem. the EDGA combines the advantages of previous parallel GA models, viz....
详细信息
ISBN:
(纸本)081864222X
In this paper, we propose a new parallel genetic algorithm (GA), called Extended distributed Genetic Algorithm (EDGA), for channel routing problem. the EDGA combines the advantages of previous parallel GA models, viz., master/slave GA model and distributed GA model. In EDGA, the root processor executes the conventional genetic algorithm with global selection on total population and the remaining processors execute conventional genetic algorithm with local selection on subpopulations. After certain number of generations, the total population on the root processor and the subpopulations on the remaining processors are interchanged, and the process is repeated till terminating conditions are reached. this incorporates features of both global and local selection in the proposed EDGA. the EDGA is designed to obtain good speedup, global optimal solution, and full utilization of the parallel system. We have implemented master/slave GA, distributed GA, and the proposed EDGA in C on a transputer-based parallel MIMD machine and compared their performance. It is found that the EDGA achieves higher speedup than both master/slave GA, and distributed GA.
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...
详细信息
ISBN:
(纸本)081864222X
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.
We consider parallel triangular solver on a distributed memory MIMD computer. three task partitioning methods will be discussed with both task assignation and task schedule. their estimated times will be provided by u...
详细信息
We consider parallel triangular solver on a distributed memory MIMD computer. three task partitioning methods will be discussed with both task assignation and task schedule. their estimated times will be provided by using a performance model and a methodology of parallel performance evaluation. the optimal task granularities will be deduced by their performance analysis. Experiences on a transputer-based multicomputer will be given.
distributed C++ (DC++) is a language for writing parallel applications on loosely coupled distributed systems in C++. Its key idea is to extend the C++ class into 3 categories: gateway classes which act as communicati...
详细信息
ISBN:
(纸本)081864222X
distributed C++ (DC++) is a language for writing parallel applications on loosely coupled distributed systems in C++. Its key idea is to extend the C++ class into 3 categories: gateway classes which act as communication and synchronization entry points between abstract processors, classes whose instances may be passed by value between abstract processors via gateways, and vanilla C++ classes. DC++ code is compiled to C++ code with calls to the DC++ runtime system. the DC++ compiler wraps gateway classes with handle classes so that remote procedure calls are transparent. It adds static variables to value classes and produces code which is used to marshal and unmarshal arguments when these value classes are used in remote procedure calls. Value classes are deep copied and preserve structure sharing. this paper shows DC++ compilation and performance.
distributed program reliability has been proposed as a reliability index for distributed computing systems to analyze the probability of the successful execution of a program, task, or mission in the system. However, ...
详细信息
ISBN:
(纸本)081864222X
distributed program reliability has been proposed as a reliability index for distributed computing systems to analyze the probability of the successful execution of a program, task, or mission in the system. However, current reliability models proposed for distributed program reliability evaluation do not capture the effects of real-time constraints. In this paper, we propose an approach to the reliability analysis of distributed programs that addresses real-time constraints. Our approach is based on a model for evaluating transmission time, which allow us to find the time needed to complete execution of the program, task, or mission under evaluation. With information on time-constraints, the corresponding Markov state space can then be defined for reliability computation. To speed up the evaluation process and reduce the size of the Markov state space, several dynamic reliability-preserving reductions are developed. A simple distributed real-time system is used as an example to illustrate the feasibility and uniqueness of the proposed approach.
Consider a message-passing system of n processors each holds one piece of data initially. the goal is to compute an associative and commutative reduction function on the n distributed pieces of data and to make the re...
详细信息
ISBN:
(纸本)081864222X
Consider a message-passing system of n processors each holds one piece of data initially. the goal is to compute an associative and commutative reduction function on the n distributed pieces of data and to make the result known to all the processors. We model the message-passing system using the parameter k for the k-port model and the parameter λ for the communication latency in the postal model. In this general model, each processor during each round r can send messages to any set of k processors and receive messages from any other set of k processors, which were sent out during round r-λ+1, provided r-λ+1≥1. We describe an optimal algorithm that requires the least number of communication rounds and minimizes the time spent by each processor in sending and receiving messages.
A new approach for dynamic submesh allocation in mesh-connected multiprocessor system, which supports a multi-user environment, is proposed. the proposed strategy effectively prunes the search space by searching for f...
详细信息
ISBN:
(纸本)081864222X
A new approach for dynamic submesh allocation in mesh-connected multiprocessor system, which supports a multi-user environment, is proposed. the proposed strategy effectively prunes the search space by searching for free submeshes on the corners of allocated submeshes along withthe corners of the mesh system. A submesh is selected withthe potential of causing the least amount of fragmentation in the system. the proposed strategy possesses complete submesh recognition capability;it is a best-fit strategy, as well. Existing strategies do not provide this combination of capabilities. the deallocation time and memory overhead is shown to be constant in that it does not grow withthe size of the mesh. Simulation results indicate that the proposed strategy outperforms the existing ones in terms of parameters such as average delay in honoring a request, standard deviation of the delays, average allocation time, average deallocation time and the amount of memory required.
this paper presents efficient techniques for identifying opportunities to increase parallelism when the asynchronous remote procedure call (ARPC) model of parallel execution is applied to programs constructed from abs...
详细信息
ISBN:
(纸本)081864222X
this paper presents efficient techniques for identifying opportunities to increase parallelism when the asynchronous remote procedure call (ARPC) model of parallel execution is applied to programs constructed from abstract data type (ADT) modules. Frequently, an ADT module is needed simultaneously by multiple clients, thus causing contention. To decrease queueing delays to execute module operations, cloning of modules is often useful. the main contribution of this work is a heuristic to efficiently determine, for each module used in a program, an upper bound on the number of clones of that module that can be used concurrently. the results include transformation rules for conditionals, so that the clone analysis algorithm avoids considering an exponential number of paths through the program. Additionally, a technique is presented to determine the number of clones required each time a loop is unrolled. Furthermore, analysis is given to consider the effects of intermodule dependence relationships on the sharing of clones.
Recent advancements in VLSI and packaging technologies demonstrate attractiveness in building scalable parallel systems using clustered configurations while exploiting communication locality. Clustered architectures u...
详细信息
ISBN:
(纸本)081864222X
Recent advancements in VLSI and packaging technologies demonstrate attractiveness in building scalable parallel systems using clustered configurations while exploiting communication locality. Clustered architectures using buses or MINs as the inter-cluster interconnection do not satisfy boththe above objectives. this paper proposes a new class of k-ary n-cube cluster-c scalable architectures by combining the scalability of k-ary n-cube wormhole-routed networks withthe cost-effectiveness of processor cluster designs. this paper focuses on direct cluster interconnection. the interplay between various system parameters and routing schemes are analyzed to determine optimal configurations under the constant bisection bandwidth constraint. Our analysis indicates that small sized clusters with a ring intra-cluster topology and a 2D/3D/4D inter-cluster network connecting these clusters offer best system performance.
暂无评论