We have implemented sample sort and a parallel version of Quicksort on a cache-coherent shared address space multiprocessor: the SUN ENTERPRISE 10000. Our computational experiments show that parallel Quicksort outperf...
详细信息
ISBN:
(纸本)0769518753
We have implemented sample sort and a parallel version of Quicksort on a cache-coherent shared address space multiprocessor: the SUN ENTERPRISE 10000. Our computational experiments show that parallel Quicksort outperforms sample sort. Sample sort has been long thought to be the best, general parallel sorting algorithms, especially for larger data sets. On 32 processors of the ENTERPRISE 10000 the speedup of parallel Quicksort is more than six units higher than the speedup of sample sort, resulting in execution times that were more than 50% faster than sample sort. On one processor parallel quicksort achieved 15% percent faster execution times than sample sorting. Moreover because of its low memory requirements, parallel Quicksort could sort data sets twice the size that sample sort could under the same system memory restrictions.
Existing parallel association rule mining algorithms suffer from many problems when mining massive transactional datasets. One major problem is that most of the parallel algorithms for a shared nothing environment are...
详细信息
ISBN:
(纸本)0769519938
Existing parallel association rule mining algorithms suffer from many problems when mining massive transactional datasets. One major problem is that most of the parallel algorithms for a shared nothing environment are Apriori-based algorithms. Apriori-based algorithms are proven to be not scalable due to many reasons, mainly: (1) the repetitive 110 disk scans, (2) the huge computation and communication involved during the candidacy generation. This paper proposes a new disk-based parallel association rule mining algorithm called Inverted Matrix, which achieves its efficiency by applying three new ideas. First, transactional data is converted into a new database layout called Inverted Matrix that prevents multiple scanning of the database during the mining phase, in which finding globally frequent patterns could be achieved in less than a full scan with random access. This data structure is replicated among the parallel nodes. Second, for each frequent item assigned to a parallel node, a relatively small independent tree is built summarizing co-occurrences. Finally, a simple and non-recursive mining process reduces the memory requirements as minimum candidacy generation and counting is needed, and no communication between no-des is required to generate all globally frequent patterns.
The linear complementarity problem LCP(A, q) which consists of finding a vector z is an element of R-n such that Az + q greater than or equal to 0, z greater than or equal to 0, z(T) (Az + q) = 0, where A is an elemen...
详细信息
ISBN:
(纸本)1892512459
The linear complementarity problem LCP(A, q) which consists of finding a vector z is an element of R-n such that Az + q greater than or equal to 0, z greater than or equal to 0, z(T) (Az + q) = 0, where A is an element of R-nxn and q is an element of R-n are a given real matrix and an real vector, respectively. This paper proposes an O(n(2)) parallel algorithm (or O(n) parallel algorithm) by using n processors (or n(2) processors) for solving the LCP(A, q) with A is an M-matrix.
This paper introduces a natural implementation for broadcasting data on Ethernet based clusters used for parallel computing. Initially, it will be shown that libraries for Message Passing between processes such as PVM...
详细信息
ISBN:
(纸本)0769519067
This paper introduces a natural implementation for broadcasting data on Ethernet based clusters used for parallel computing. Initially, it will be shown that libraries for Message Passing between processes such as PVM and implementations of MPI do not implement efficiently this operation or there is no reliability in terms of its performance. An implementation for broadcast messages is presented, taking into account the Ethernet based hardware layer found in most of the clusters used for parallel computing. The proposed implementation for broadcasting data is compared with the broadcast message available in PVM and LAM/MPI. Also, some comments are made about the proposed broadcast messages when the hardware layer is not Ethernet based. Finally, it will be shown by experimentation how the proposed broadcast message is used in the context of parallel linear algebra operations, specifically for parallel matrix multiplication.
It has fundamental importance to reliably find numerical solutions for large-scale nonlinear global optimization problems. In this paper, we report an SPMD parallel algorithm that solves global optimization problem wi...
详细信息
ISBN:
(纸本)188084348X
It has fundamental importance to reliably find numerical solutions for large-scale nonlinear global optimization problems. In this paper, we report an SPMD parallel algorithm that solves global optimization problem with continuous nonlinear objective function and constraints. Interval branch-and-bound algorithms are the basic algorithms in this paper. Our coarse-grained SPMD algorithm has the advantages of less communication overhead, minor modification of sequential program, reduction of total number of computation, and balanced workload. Initial implementations of our parallel algorithm. have shown significant reductions of total number of computation and superlinear speedup.
The nonlinear Schrödinger equation is of tremendous interest in both theory and applications. Various regimes of pulse propagation in optical fibers are modeled by some form of the nonlinear Schrödinger equa...
详细信息
Data cube construction is a commonly used operation in data warehouses. Because of the volume of data that is stored and analyzed in a data warehouse and the amount of computation involved in data cube construction, i...
详细信息
ISBN:
(纸本)0769520170
Data cube construction is a commonly used operation in data warehouses. Because of the volume of data that is stored and analyzed in a data warehouse and the amount of computation involved in data cube construction, it is natural to consider parallel machines for this operation. This paper addresses a number of algorithmic issues in parallel data cube construction. First, we present an aggregation tree for sequential (and parallel) data cube construction, which has minimally bounded memory requirements. An aggregation tree is parameterized by the ordering of dimensions. We present a parallel algorithm based upon the aggregation tree. We analyze the interprocessor communication volume and construct a closed form expression for it. We prove that the same ordering of the dimensions minimizes both the computational and communication requirements. We also describe a method for partitioning the initial array and prove that it minimizes the communication volume. Experimental results from implementation of our algorithms on a cluster of workstations validate our theoretical results.
We present the first space and time optimal parallel algorithm for the pairwise sequence alignment problem, a fundamental problem in computational biology. This problem can be solved sequentially in O(mn) time and O(m...
详细信息
ISBN:
(纸本)0769520170
We present the first space and time optimal parallel algorithm for the pairwise sequence alignment problem, a fundamental problem in computational biology. This problem can be solved sequentially in O(mn) time and O(m + n) space, where m and n are the lengths of the sequences to be aligned. The fastest known parallel space-optimal algorithm for pairwise sequence alignment takes optimal O((m+n)/(p)) space but suboptimal O(((m+n)2)/(p)) time, where p is the number of processors. On the other hand, the most space economical time-optimal parallel algorithm takes O((mn)/(p)) time but O(m + (n)/(p)) space. We close this gap by presenting an algorithm that achieves both time and space optimality, i.e. requires only O((m+n)/(p)) space and O((mn)/(p)) time. We also present an experimental evaluation of the proposed algorithm on an IBM xSeries cluster.
,As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithm for circuit testing, logic minimization and simulation, HDL-based synth...
详细信息
ISBN:
(纸本)0769518753
,As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithm for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. In some of these applications the circuit partitioning problem occurs. That implies dividing a circuit into non-overlapping subcircuits while minimizing the number of cuts after the division and balancing the load associated to each one. Very effective heuristic algorithms have been developed in order to solve this problem, but it is unknown how good the partitions are since the problem is NP-complete. In these cases the use of parallel processing can be very useful. This paper describes a parallel evolutionary algorithm for circuit partitioning, where parallelism improves the solutions found by the corresponding sequential algorithm, which indeed is quite effective compared with other previously proposed procedures.
We propose a parallel and asynchronous approach to give near-optimal solutions to the non-fixed point-to-point connection problem. This problem is NP-hard and has practical applications in multicast routing. The techn...
详细信息
We propose a parallel and asynchronous approach to give near-optimal solutions to the non-fixed point-to-point connection problem. This problem is NP-hard and has practical applications in multicast routing. The technique adopted to solve the problem is an organization of heuristics that communicate with each other by means of a virtually shared memory. This technique is called A-Teams (for Asynchronous Teams). The virtual shared memory is implemented in a physically distributed memory system. Computational results comparing our approach with a branch-and-cut algorithm are presented. (C) 2003 Elsevier Science B.V. All rights reserved.
暂无评论