With the emergence of the network technologies, heterogeneous computing has become a wide accept paradigm for distributed and network computing. In this paper, we present different algorithms aiming to efficiently per...
详细信息
With the emergence of the network technologies, heterogeneous computing has become a wide accept paradigm for distributed and network computing. In this paper, we present different algorithms aiming to efficiently perform atomic one-to-all broadcast in a heterogeneous network with a one port model. The proposed algorithms are divided into graph-based and tree-based ones. In graph-based algorithms, we present Nearest Neighbor First and Maximum Degree Neighbor First schemes. A prescheduling strategy with constructing a message forwarding table for avoiding redundant transmissions is applied as runtime support. In the tree- based approaches, there are five heuristic algorithms: Nearest Neighbor First, Maximum Degree Neighbor First, Maximum Height Subtree First, Maximum Subtree First, and Maximum Weighted Subtree First, proposed based on different network characteristics. To evaluate the performance of the proposed techniques, we have developed a simulator that contains a parametric graph generator for generating network graphs with various characteristics. We have implemented all of the proposed scheduling algorithms on the simulator. The performance results show that the Maximum Weighted Subtree First performs best in high degree heterogeneous environments. On the contrary, with homogeneous-like environments, the graph-based Nearest Neighbor First will be the best choice. In summary, contribution of this study relies on informing significant suggestions for adapting proper broadcasting mechanism in different heterogeneous platforms.
Splitting extrapolation is an efficient technique for solving large scale scientific and engineering problems in parallel. This article discusses a finite element splitting extrapolation for second order hyperbolic eq...
详细信息
Splitting extrapolation is an efficient technique for solving large scale scientific and engineering problems in parallel. This article discusses a finite element splitting extrapolation for second order hyperbolic equations with time-dependent coefficients. This method possesses a higher degree of parallelism, less computational complexity, and more flexibility than Richardson extrapolation while achieving the same accuracy. By means of domain decomposition and isoparametric mapping, some grid parameters are chosen according to the problem. The multiparameter asymptotic expansion of the d-quadratic finite element error is also established. The splitting extrapolation formulas are developed from this expansion. An approximation with higher accuracy on a globally fine grid can be computed by solving a set of smaller discrete subproblems on different coarser grids in parallel. Some a posteriori error estimates are also provided. Numerical examples show that this method is efficient for solving discontinuous problems and nonlinear hyperbolic equations.
Let C be a closed convex subset of a real q-uniformly smooth Banach space and T-i : C -> C, i = 1, 2, ..., N be a finite family of mappings which are strictly pseudo-con tractive. Assume F := boolean AND(N)(i=1) F(...
详细信息
Let C be a closed convex subset of a real q-uniformly smooth Banach space and T-i : C -> C, i = 1, 2, ..., N be a finite family of mappings which are strictly pseudo-con tractive. Assume F := boolean AND(N)(i=1) F(T-i) not equal empty set. Let u, x(0) is an element of C be arbitrary fixed vectors in C. It is proved that the sequence {x(n)}(n >= 0) generated by {Y-n = (1 - alpha(n))x(n) + alpha(n) Sigma(N)(i=1) eta((n))(i) T(i)x(n), Xn+1 = beta(n)u + gamma(n)x(n) + delta(n)y(n), where {alpha(n)), {beta(n)}, {gamma(n)} and {sigma(n)} are sequences in (0, 1) satisfying appropriate conditions, converges strongly to an element of F. (c) 2008 Elsevier Ltd. All rights reserved.
A height-balanced tree is a rooted binary tree T in which for every vertex nu is an element of V(T), the heights of the subtrees, rooted at the left and right child of nu, differ by at most one;this difference is call...
详细信息
A height-balanced tree is a rooted binary tree T in which for every vertex nu is an element of V(T), the heights of the subtrees, rooted at the left and right child of nu, differ by at most one;this difference is called the balance factor of nu. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Q(h+1) under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation I or 2 according to whether it is balanced or not. (C) 2009 Elsevier Inc. All rights reserved.
Nonlinear elliptic partial differential equations are important to many large scale engineering and science problems. For this kind of equations, this article discusses a splitting extrapolation which possesses a high...
详细信息
Nonlinear elliptic partial differential equations are important to many large scale engineering and science problems. For this kind of equations, this article discusses a splitting extrapolation which possesses a high order of accuracy, a high degree of parallelism, less computational complexity and more flexibility than Richardson extrapolation. According to the problems, some domain decompositions are Constructed and some independent mesh parameters are designed. Multi-parameter asymptotic expansions are proved for the errors of approximations. Based on the expansions, splitting extrapolation formulas are developed to compute approximations with high order of accuracy on a globally fine grid. Because these formulas only require us to solve a set of smaller discrete subproblems on different coarser grids in parallel instead of on the globally fine grid, a large scale multidimensional problem is turned into a set of smaller discrete subproblems. Additionally, this method is efficient for solving interface problems. (C) 2008 Elsevier Inc. All rights reserved.
The block-based medial axis transform (BB_MAT, for short) of a 3D (2D) binary image, denoted 3D_BB_MAT (2D_BB_MAT). is defined as the problem to find a minimal set of upright 1-cubes (1-squares) whose union correspond...
详细信息
The block-based medial axis transform (BB_MAT, for short) of a 3D (2D) binary image, denoted 3D_BB_MAT (2D_BB_MAT). is defined as the problem to find a minimal set of upright 1-cubes (1-squares) whose union corresponds exactly to the 1-voxels (1-pixels) in the binary image. Many parallel algorithms have been proposed for computing the 2D_BB_MAT, almost all proposed approaches are unable to extend to a solution of the 3D_BB_MAT problem. In this paper, we first propose a novel 0(1) time algorithm for solving the 3D_BB_MAT (2D_BB_MAT) problem of a binary image of size N x N x N (N x N) on a linear array with a reconfigurable pipelined bus system (LARPBS, for short) by peeling the 3D (2D) corner shell of each 1-voxel (1-pixel) of the image and revealing some properties of the 3D_BB_MAT (2D_BB_MAT). The 3D (2D) chessboard distance transform problem, denoted 3D_CDT (2D_CDT), is the problem for each 0-voxel (0-pixel) of a 3D (2D) binary image to find its nearest 1-voxel (1-pixel) in the binary image based on chessboard distance metric. In this paper, we also solve the 3D_CDT (2D_CDT) based on the computed 3D_BB_MAT (2D_BB_MAT). All the proposed algorithms are very innovative although they look like "straightforward". To the best of our knowledge, the proposed 2D_BB_MAT (2D_CDT) algorithm is the first algorithm that can extend to a solution of the 3D_BB_MAT (3D_CDT) problem in parallel, and the 3D_BB_MAT (3D_CDT) algorithm is the first parallel
It is suggested here an algorithm based on stickers for the DNA Computing model [S. Roweis, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, L. Adleman, A sticker-based model for DNA Computation, Journ...
详细信息
It is suggested here an algorithm based on stickers for the DNA Computing model [S. Roweis, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, L. Adleman, A sticker-based model for DNA Computation, Journal of Computational Biology 5 (1998) 615-629] that solves the well known Bin-Packing Problem (BPP), that belongs to the class N P-Hard in the strong sense, in a time bounded by O(n(2)q), where n is the quantity of items and q the space requirements expressed in bits. To the best of the authors' knowledge, this is the first polynomial time algorithmic solution for the BPP in such a model. (C) 2009 Elsevier Inc. All rights reserved.
In this paper, some issues concerning the Chinese remaindering representation are discussed. A new converting method, which is an efficient probabilistic algorithm based on a recent result of von zur Gathen and Shparl...
详细信息
In this paper, some issues concerning the Chinese remaindering representation are discussed. A new converting method, which is an efficient probabilistic algorithm based on a recent result of von zur Gathen and Shparlinski [J. von zur Gathen, 1. Shparlinski, GCD of random linear forms, algorithmica 46 (2006) 137-148], is described. An efficient refinement of the NC1 division algorithm of Chiu, Davida and Litow [A. Chiu, G. Davida, B. Litow, Division in logspace-uniform NC1, Theoret. Informatics Appl. 35 (2001) 259-275] is given, where the number of moduli is reduced by a factor of log n. (C) 2009 Elsevier B.V. All rights reserved.
A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to fi...
详细信息
A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.
The ParaReal algorithm (CR. Acad. Sci. Paris 2001;332:1-6) is a parallel approach for solving numerically systems of ordinary differential equations by exploiting parallelism across the steps of the numerical integrat...
详细信息
The ParaReal algorithm (CR. Acad. Sci. Paris 2001;332:1-6) is a parallel approach for solving numerically systems of ordinary differential equations by exploiting parallelism across the steps of the numerical integrator. The method performs well for dissipative problems and problems of fluid-structure interaction (Int. J. Numer. Methods Engng 2003;58:1397-1434). We consider here a convergence analysis for the method and we report the performance achieved from the parallelization of a Stokes/Navier-Stokes code via the ParaReal algorithm. Copyright (C) 2009 John Wiley & Sons, Ltd.
暂无评论