This paper presents BSR-parallel algorithms for three geometrical problems : point location, convex hull and smallest enclosing rectangle. These problems are solved in constant time using the BSR model introduced by S...
详细信息
ISBN:
(纸本)0769509886
This paper presents BSR-parallel algorithms for three geometrical problems : point location, convex hull and smallest enclosing rectangle. These problems are solved in constant time using the BSR model introduced by S. Akl in [2]. The first algorithm uses O(N) processors (N) is the number of edges of the polygon R). The second uses O(N'(2)) processors (N' is the number of points) and the third one uses O(N'2) processors (ir need the convex hull) to solve the smallest enclosing rectangle problem. These new results suggest that many other geometrical problems can be solved in constant rime using the BSR model.
We present a new BSP/CGM parallel algorithm for the transitive closure problem. Our algorithm uses O(n/sup 3//p/spl alpha/) local computation time with O(p//spl alpha/) communication rounds, where /spl alpha/ is the s...
详细信息
We present a new BSP/CGM parallel algorithm for the transitive closure problem. Our algorithm uses O(n/sup 3//p/spl alpha/) local computation time with O(p//spl alpha/) communication rounds, where /spl alpha/ is the size in bits that can be stored in a primitive data item. For all the randomly generated graphs that were used in the tests, the number of communication rounds was bounded by log p/spl bsol//spl alpha/+1. Our algorithm, even for the worst case, improves the previous results. The algorithm was implemented and the results show the efficiency and scalability of the presented algorithm and compare favorably with other parallel implementations.
Hashing is an important tool in randomized algorithms, with applications in such diverse fields including information retrieval, data mining, cryptology and parallel algorithms. However, the worst case behavior of a r...
详细信息
Hashing is an important tool in randomized algorithms, with applications in such diverse fields including information retrieval, data mining, cryptology and parallel algorithms. However, the worst case behavior of a regular hash-based searching is O(n). Perfect hashing is a solution to this problem that offers a worst case performance of O(1) only for the static key set. In this paper we have proposed an adaptive hashing scheme that works on dynamic key sets and still enables keys to be searched in constant time. It has been further established that, if the hash functions are carefully chosen, then the space requirement of the hash structure is O(n).
The concept of siphons plays an important role in the analysis of Petri nets. In particular, criteria for liveness and reachability of some subclasses of Petri nets can be stated in terms of siphons. However, the comp...
详细信息
ISBN:
(纸本)0780385675
The concept of siphons plays an important role in the analysis of Petri nets. In particular, criteria for liveness and reachability of some subclasses of Petri nets can be stated in terms of siphons. However, the computation of these structural components can be time consuming or even impossible. Recently, a variety of deadlock control policies that rely on partial siphon computation and enumeration have been developed. We propose a polynomial algorithm to find a set of elementary siphons in a class of Petri nets called systems of simple sequential processes with resources, S/sup 3/PR for short. Based on them, other siphons, called dependent ones, can be composed by simple set operations. Case studies show that the proposed algorithm is more computationally efficient than INA, integrated net analyzer, a widely used Petri net analysis tool.
This paper discusses the point covering problem solved by ant algorithm. Point covering problem is hard to solve with great actual value. Ant algorithm is a newly emerged stochastic searching optimization algorithm in...
详细信息
ISBN:
(纸本)0780384032
This paper discusses the point covering problem solved by ant algorithm. Point covering problem is hard to solve with great actual value. Ant algorithm is a newly emerged stochastic searching optimization algorithm in recent years. A distributed parallel algorithm of point covering is presented with ant algorithm. Experiment results demonstrate that the algorithm is effective.
The analysis of large amounts of data requires important computing resources that may not be available, even in current environment, and there are traditionally two main ways for solving this problem. The first is to ...
详细信息
The analysis of large amounts of data requires important computing resources that may not be available, even in current environment, and there are traditionally two main ways for solving this problem. The first is to use multiprocessor machines, and the second is to use computer clusters. The main drawbacks of these solutions are the expensive cost of machines and their specific utilization. In order to avoid these drawbacks, distributed algorithms for mining association rules have been proposed. However, these algorithms either run high-synchronous methods or lack flexibility to be adapted to machines with limited available resources. A distributed dichotomous algorithm (DDA) is proposed for association rule mining. The main features of DDA are that this algorithm does not require a high level of synchronization and that it does not process data replication and redundant calculations. In addition, DDA can partition recursively the tasks and the data set so as to be processed by machines with limited available resources.
Summary form only given. As scientific simulations are generating large amounts of data, analyzing this data to gain insights into scientific phenomenon is increasingly becoming a challenge. We present a case study on...
详细信息
Summary form only given. As scientific simulations are generating large amounts of data, analyzing this data to gain insights into scientific phenomenon is increasingly becoming a challenge. We present a case study on the use of a cluster middleware for rapidly creating a scalable and parallel implementation of a scientific data analysis application. Using FREERIDE (framework for rapid implementation of data mining engines), we parallelize as well as scale to disk-resident datasets a feature extraction algorithm. We have developed a parallel algorithm for this problem which matches the communication and computation structure supported by the FREERIDE system. The main observations from our experimental results are as follows: 1) the overhead of using the middleware is quite small in most cases, 2) there is an overhead associated with breaking the datasets into more partitions or chunks, and 3) if the dataset is partitioned into the same number of chunks, the execution time stays proportional to the size of the dataset and inversely proportional to the number of nodes, i.e. the overhead of communication or reading disk-resident datasets is very small.
In this work, we deal with the problem of minimizing the load redistribution cost in parallel implementations for cluster architectures. Due to the importance of the network latency in this kind of systems, the redist...
详细信息
In this work, we deal with the problem of minimizing the load redistribution cost in parallel implementations for cluster architectures. Due to the importance of the network latency in this kind of systems, the redistribution cost is primarily depending on the maximum number of messages sent or received by a processor. The load redistribution is a NP-hard problem similar to the multiple knapsack problems. Three heuristics are proposed to solve the problem in a global context, and a comparison is made to emphasize their characteristics. In a parallel application, it is important to decide whether it is efficient or not to carry out the workload redistribution. This decision is taken comparing the cost of the load imbalance and the communication overheads associated with the load balancing heuristic. Depending on these costs, a theoretic value of imbalance from which the redistribution is profitable is defined. Experimental results show the accuracy of our proposals.
A new parallel normalized explicit preconditioned conjugate gradient method in conjunction with normalized approximate inverse matrix techniques is presented for solving efficiently sparse linear systems on multi-comp...
详细信息
A new parallel normalized explicit preconditioned conjugate gradient method in conjunction with normalized approximate inverse matrix techniques is presented for solving efficiently sparse linear systems on multi-computer systems. Application of the proposed method on a three dimensional boundary value problem is discussed and numerical results are given. The implementation and performance on a distributed, memory MIMD machine, using message passing interface (MPI) is also investigated.
A new algorithm for modular multiplication for public key cryptography is presented. The algorithm is optimised with respect to area and time by use of a combination of adders and fast lookup tables. This leads to a m...
详细信息
A new algorithm for modular multiplication for public key cryptography is presented. The algorithm is optimised with respect to area and time by use of a combination of adders and fast lookup tables. This leads to a multiplication method that can significantly speed up exponentiation, because the values of the lookup table do not depend on the operands of the individual multiplication. The speedup is achieved by continuous modification of one operand.
暂无评论