We present efficient sequential and parallel algorithms for the maximum sum (MS) problem, which is to maximize the sum of some shape in the data array. We deal with two MS problems;the maximum subarray (MSA) problem a...
详细信息
We present efficient sequential and parallel algorithms for the maximum sum (MS) problem, which is to maximize the sum of some shape in the data array. We deal with two MS problems;the maximum subarray (MSA) problem and the maximum convex sum (MCS) problem. In the MSA problem, we find a rectangular part within the given data array that maximizes the sum in it. The MCS problem is to find a convex shape rather than a rectangular shape that maximizes the sum. Thus, MCS is a generalization of MSA. For the MSA problem, time parallel algorithms are already known on an 2D array of processors. We improve the communication steps from to n, which is optimal. For the MCS problem, we achieve the asymptotic time bound of 2D array of processors. We provide rigorous proofs for the correctness of our parallel algorithm based on Hoare logic and also provide some experimental results of our algorithm that are gathered from the Blue Gene/P super computer. Furthermore, we briefly describe how to compute the actual shape of the maximum convex sum.
This short paper presents a novel pipelining and processor allocation strategy for monoid computations on an unshuffle-exchange network. In the strategy, the processor utilization is near 1 and the communication is co...
详细信息
This short paper presents a novel pipelining and processor allocation strategy for monoid computations on an unshuffle-exchange network. In the strategy, the processor utilization is near 1 and the communication is collision-free. With the characteristics of constant connections to each processor and only a single output node on the network, the method given here can compete with the method of Barnard and Skillicorn based on a hypercube network with multiple output nodes.
The paper presents an application of a new parallel probabilistic algorithm for global optimization involving the transformation of the linear programming problem into a global optimization problem, using the basic id...
详细信息
The paper presents an application of a new parallel probabilistic algorithm for global optimization involving the transformation of the linear programming problem into a global optimization problem, using the basic idea of Lagrange. One incorporates the constraints of the linear programmingproblem into its objective function using an appropriate penalty function, and transforms the probleminto one of global optimization, solved subsequently by the probabilistic parallel algorithm. The two important aspects in its construction are: the use of a probabilistic mechanism for the search of the global optimum point, and its inherent parallel structure.
An algorithm for the distance transform of a binary image was presented in L. Boxer and R. Miller ( Comput. Vision Image Understand. 80 , 2000, 379–383). The algorithm was stated for the Euclidean metric. In this Cor...
详细信息
An algorithm for the distance transform of a binary image was presented in L. Boxer and R. Miller ( Comput. Vision Image Understand. 80 , 2000, 379–383). The algorithm was stated for the Euclidean metric. In this Corrigendum, we show that the algorithm of Boxer and Miller (2000) is correct for the L 1 “Manhattan” or “city block” metric; however, the algorithm is not correct for the general class of L p metrics, including the Enclidean metric.
In this paper, we present an algorithm for a generalization of list ranking called computation list evaluation . As a consequence of the generalization and the existence of this algorithm for computation list evaluati...
详细信息
In this paper, we present an algorithm for a generalization of list ranking called computation list evaluation . As a consequence of the generalization and the existence of this algorithm for computation list evaluation, we obtain a generalization of Euler Tour technique. Finally, we present several applications of the generalized Euler Tour technique. Of interest in the applications is the identification of a set of problem instances that are solvable using tree contraction and which can alternatively be solved using a simple algorithm based on the generalized Euler Tour technique.
In this paper we evaluate the potential for using an NVIDIA graphics processing unit (GPU) to accelerate high precision integer multiplication, addition, and subtraction. The reported peak vector performance for a typ...
详细信息
In this paper we evaluate the potential for using an NVIDIA graphics processing unit (GPU) to accelerate high precision integer multiplication, addition, and subtraction. The reported peak vector performance for a typical GPU appears to offer good potential for accelerating such a computation. Because of limitations in the on-chip memory, the high cost of kernel launches, and the nature of the architecture's support for parallelism, we used a hybrid algorithmic approach to obtain good performance on multiplication. On the GPU itself we adapt the Strassen FFT algorithm to multiply 32KB chunks, while on the CPU we adapt the Karatsuba divide-and-conquer approach to optimize application of the GPU's partial multiplies, which are viewed as "digits" by our implementation of Karatsuba. Even with this approach, the result is at best a factor of three increase in performance, compared with using the GMP package on a 64-bit CPU at a comparable technology node. Our implementations of addition and subtraction achieve up to a factor of eight improvement. We identify the issues that limit performance and discuss the likely impact of planned advances in GPU architecture.
A class of Adams-type parallel hybrid multistep algorithms is constructed. A-stable formula of 3-step 3rd order, A(α)-stable formula of 4-step 4th order with α = 89.99° and A(α)-stable formula of 5-step 5th or...
详细信息
A class of Adams-type parallel hybrid multistep algorithms is constructed. A-stable formula of 3-step 3rd order, A(α)-stable formula of 4-step 4th order with α = 89.99° and A(α)-stable formula of 5-step 5th order with α = 84.92° are obtained. The numerical example shows that these methods are efficient for solving stiff ordinary equations.
We present optimal parallel algorithms that run in time on mesh-connected computer for a number of fundamental problems concerning proximity and visibility in a simple polygon. These include computing shortest paths, ...
详细信息
We present optimal parallel algorithms that run in time on mesh-connected computer for a number of fundamental problems concerning proximity and visibility in a simple polygon. These include computing shortest paths, shortest path trees, shortest path partitions, all-farthest neighbors, the visibility polygon of a point, the weak visibility polygon of an edge, and the ray shooting problem.
In this paper, using the metric of iso--efficiency function [if. we analyze the scalability of PSRS (parallel. Sorting by Regular Sample) algorithm I2] on two popular architectures (Mesh and Hypercube) The Isoefficien...
详细信息
In this paper, using the metric of iso--efficiency function [if. we analyze the scalability of PSRS (parallel. Sorting by Regular Sample) algorithm I2] on two popular architectures (Mesh and Hypercube) The Isoefficiency function of PSRS on 2-dimensional mesh With p processors reaches the lower bound for that of sorting algorithms on this architecture. In nils sense, we say the scalabilify of PSRS is optimal on 2-dimensional mesh. The lso-efficiency function of PSRS on hypercube is equal to that of PSRS on 2-dimensional mesh. After changing the data exchanging scheme of PSRS, -cafe get a ne'v iso-efficiency function . which is better than that of PSRS on 2-dimensional mesh So we say that hypercube is more suitable for PSRS than 2--dimensional mesh.
暂无评论