This paper proposes two distributed algorithms for the heuristic solution of the Steiner Tree Problem in Network (SPN). The problem has a practical application in the construction of a minimum cost distribution tree f...
详细信息
ISBN:
(纸本)088986392X
This paper proposes two distributed algorithms for the heuristic solution of the Steiner Tree Problem in Network (SPN). The problem has a practical application in the construction of a minimum cost distribution tree for multicast transmission. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Currently, given the lack of efficient distributed methods, the existing protocols build the multicast distribution tree using some selected central node. The proposed distributed algorithms allow the construction of effective distribution trees using a coordination protocol among the network nodes. The algorithms have been implemented and tested both in simulation and on experimental active networks, and their performance values are presented.
Clusters have been used more and more has an alternative hardware platform for executing applications demanding high performance. Many new programming/execution environments have been proposed or adapted to better use...
详细信息
ISBN:
(纸本)088986392X
Clusters have been used more and more has an alternative hardware platform for executing applications demanding high performance. Many new programming/execution environments have been proposed or adapted to better use the resources of this type of platform. This paper presents a proposal of an environment called CLUX - Cluster Crux, in which the communication mechanism is based on a dynamic interconnection network. We describe the CLUX architecture and also the basic components of the communication mechanism, including their functionalities and programming interface.
To efficiently retrieve high-dimensional data in multimedia database and data warehousing applications, the VA-file and the CBF (Cell-based filtering) method have been proposed. But they show a linear decreasing on pe...
详细信息
ISBN:
(纸本)088986392X
To efficiently retrieve high-dimensional data in multimedia database and data warehousing applications, the VA-file and the CBF (Cell-based filtering) method have been proposed. But they show a linear decreasing on performance as the dimensionality. To cope with the problem, we, in this paper, propose a new parallel CBF method for shared-nothing (SN) cluster-based parallel architecture. In addition, we devise data insertion, range query processing, and k-NN query processing algorithms that are suitable for the SN parallel architecture. Finally, we show that our parallel CBF method achieves good retrieval performance in proportion to the number of servers in the SN parallel architecture, compared with the conventional CBF method.
In this paper, we consider the resource allocation problem for computing a large set of equal-sized independent tasks on heterogeneous computingsystems. This problem represents the computation paradigm for a wide ran...
详细信息
ISBN:
(纸本)088986392X
In this paper, we consider the resource allocation problem for computing a large set of equal-sized independent tasks on heterogeneous computingsystems. This problem represents the computation paradigm for a wide range of applications such as SETI@home and Monte Carlo simulations. Compute nodes in the system are heterogeneous and may communicate with each other at different speeds. We model such a system as a graph, which is capable of representing an arbitrary network topology. Our study focuses on the maximization of the steady state throughput of such systems. We show that, unlike the surprisingly difficult makespan minimization problem, the throughput maximization problem can be solved through a linear programming formulation. We also show that different operation scenarios of the compute nodes have intrinsic similarities. Our approach shows improved performance compared with the master/worker computation paradigm which assumes a tree-structured system topology.
This paper compares the performance of two parallelization strategies for a backpropagation neural network on a cluster computer: exemplar parallel and node parallel strategies. Equations for calculating the theorecti...
详细信息
ISBN:
(纸本)088986392X
This paper compares the performance of two parallelization strategies for a backpropagation neural network on a cluster computer: exemplar parallel and node parallel strategies. Equations for calculating the theorectial costs of these two strategies are proposed based on the implementation presented in the paper. Performance results are collated according to different sizes of neural network, different dataset sizes, and number of processors. The performance results show the advantages and disadvantages of the two strategies. More interestingly, we discover that the experimental results are very consistent with the theoretical costs. Therefore our cost equations can be used to predict which strategy is going to be better given a network size, a dataset size, and a number of processors.
The nearest-neighbor method can successfully be applied to correct possible errors induced into bit strings transmitted over noisy communication channels or to classify samples into a predefined set of categories. The...
详细信息
ISBN:
(纸本)088986392X
The nearest-neighbor method can successfully be applied to correct possible errors induced into bit strings transmitted over noisy communication channels or to classify samples into a predefined set of categories. These two applications are investigated under real-time constraints, when the deadlines imposed can dramatically alter the quality of the solution unless a parallel model of computation (in these cases, a linear array of processors) is used. We also study a class of real-time computations, referred to as reactive real-time systems, that are particularly sensitive to the first time constraint imposed.
Procedural languages like C and FORTRAN have historically been the languages of choice for implementing programs for high performance parallel computers. The inherent difficulties in writing efficient parallel codes w...
详细信息
ISBN:
(纸本)088986392X
Procedural languages like C and FORTRAN have historically been the languages of choice for implementing programs for high performance parallel computers. The inherent difficulties in writing efficient parallel codes with a procedural programming model are a motivation for pursing alternatives such as high-level parallel programming languages. SequenceL is a high-level parallel language that provides declarative constructs for non-scalar processing. Rather than specifying program control structures that, in turn, imply a data product, the problem solver specifies a data product and the control structures to produce or process the data product are implied, including the parallelisms. This paper focuses on the recent advances in the development of SequenceL as a parallel programming language.
A new algorithm for modular multiplication suitable for an optimal modular exponentiation is given. It is optimised with respect to time complexity. Each modular multiplication is computed with time complexity of O(lo...
详细信息
ISBN:
(纸本)088986392X
A new algorithm for modular multiplication suitable for an optimal modular exponentiation is given. It is optimised with respect to time complexity. Each modular multiplication is computed with time complexity of O(log n). The time complexity of modular exponentiation is O(n*log n). Before executing the first modular multiplication a lookup table is generated containing values that allow for an efficient reduction with respect to the modulus. These values can be used for all modular multiplications. The multiplication is calculated by parallel additions. It is shown how the new algorithm can be efficiently implemented in hardware using carry save adders and one carry lookahead adder.
One way of characterizing non-token-based mutual exclusion (m.e.) algorithms is in terms of the underlying information structure. The information structure for a given m.e. algorithm specifies which particular process...
详细信息
ISBN:
(纸本)088986392X
One way of characterizing non-token-based mutual exclusion (m.e.) algorithms is in terms of the underlying information structure. The information structure for a given m.e. algorithm specifies which particular processes interact with which other processes before entering their critical sections, and which processes they interact with when leaving their critical sections. By focusing on the information structure of an m.e. algorithm, we can compare different algorithms by comparing the respective information structures. Further, we can characterize the correctness of an m.e. algorithm in terms of conditions that its information structure must satisfy. In this paper, we propose a necessary and sufficient condition for ensuring the correctness of the m.e. algorithm and show that this condition is superior to the currently accepted condition.
In the context of e-commerce, execution atomicity is an important property for mobile agents. A mobile agent executes atomically, if either all its operations succeed, or none at all. This requires to solve an instanc...
详细信息
ISBN:
(纸本)088986392X
In the context of e-commerce, execution atomicity is an important property for mobile agents. A mobile agent executes atomically, if either all its operations succeed, or none at all. This requires to solve an instance of the atomic commitment problem. However, it is important that failures (e.g., of machines or agents) do not lead to blocking of transactional mobile agents, i.e., agents that execute as a transaction. In this paper, we give a novel specification of non-blocking atomic commitment in the context of mobile agent execution. We then show how transactional mobile agent execution can be built on top of earlier work on fault-tolerant mobile agent execution and give preliminary performance results.
暂无评论