We consider the class of Dandelion-like codes, i.e., a class of bijective codes for coding labeled trees by means of strings of node labels. In the literature it is possible to find optimal sequential algorithm,,;for ...
详细信息
ISBN:
(纸本)9783642019692
We consider the class of Dandelion-like codes, i.e., a class of bijective codes for coding labeled trees by means of strings of node labels. In the literature it is possible to find optimal sequential algorithm,,;for codes belonging to this class, but, for the best of our knowledge, no parallel algorithm is reported. In this paper we present the first encoding and decoding parallel algorithms for Dandelion-like codes. Namely, we design a. unique encoding algorithm and a unique decoding algorithm that, properly parametrized, can be used for all Dandelion-like codes. These algorithms are optimal in the sequential setting. The encoding algorithm implementation oil all EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading.
Given an unweighted planar graph G together with nets of terminals, our problem is to find a Steiner forest, i.e., vertex-disjoint trees, each of which interconnects all the terminals of a net. This paper presents fou...
详细信息
In this paper we face the inexact graph matching problem from the parallel algorithms viewpoint. After a brief introduction of both graph matching and parallel computing contexts, we discuss a specific method of perfo...
详细信息
ISBN:
(纸本)9781467314909
In this paper we face the inexact graph matching problem from the parallel algorithms viewpoint. After a brief introduction of both graph matching and parallel computing contexts, we discuss a specific method of performing inexact graph matching based on the well known tensor product operator. We analyze the problem using two parallel computing models, following different algorithmic strategies, and performing also an experimental evaluation. The aim of this paper is to provide modeling and algorithmic strategies to extend inexact graph matching methods to graphs of high order and size, conceiving the computational problem in the more wider context of graph-based Pattern Recognition and Soft Computing systems. As a whole, the obtained results encourage more effort on this direction.
parallelization of Marchuk's method for solution of inverse problems based on adjoint equations and dual representation of contaminant concentration functional is considered here. There are N individual adjoint eq...
详细信息
ISBN:
(纸本)9783642148217
parallelization of Marchuk's method for solution of inverse problems based on adjoint equations and dual representation of contaminant concentration functional is considered here. There are N individual adjoint equations independently solved at each time step. Such conditions of numerical investigation allow application of high performance computations. For this purpose the following ways of parallelization are used: geometrical decomposition, functional decomposition and combination of geometrical and functional decompositions.
Jaccard similarity between a pair of vertices in a graph measures the relative overlap among their adjacent vertices. This metric is used to estimate the strength of existing edges and predict new edges between pairs ...
详细信息
ISBN:
(纸本)9798350308600
Jaccard similarity between a pair of vertices in a graph measures the relative overlap among their adjacent vertices. This metric is used to estimate the strength of existing edges and predict new edges between pairs of disconnected vertices. Computing Jaccard similarity for all pairs of vertices or for all edges is computationally expensive. Existing sequential and parallel algorithms are either too slow or do not scale well for large scale graphs. We present a shared-memory parallel algorithm for computing Jaccard weights. Our algorithm relies on sparse linear algebraic operations that utilize masking, semirings, vector iterators, and other GraphBLAS features for performance. Our implementation, albeit simple, outperforms recent state-of-the-art implementations by a factor of up to 20x and exhibits an average speedup of 9x.
With small device features in sub-micron technologies, interconnection delays play a dominant part in cycle time. Hence, it is important to consider the impact of physical design during high level synthesis. In compar...
详细信息
ISBN:
(纸本)0780344553
With small device features in sub-micron technologies, interconnection delays play a dominant part in cycle time. Hence, it is important to consider the impact of physical design during high level synthesis. In comparison to a traditional approach which separates high-level synthesis from physical design, an algorithm which is able to make these stages interact very closely, would result in solutions with lower latency and area. However, such an approach could result in increased runtimes. parallel processing is an attractive way of reducing the runtimes. In this paper, two parallel algorithms for simultaneous scheduling, binding and floorplanning algorithm are presented. A detailed hardware model is considered, taking into account multiplexor and register areas and delays. Experimental results are reported on an IBM SP-2 multicomputer, with close to linear speedups for a set of benchmark circuits.
This paper aims to develop effective parallel processing techniques for 3-dimensional (3D) multi-level median filtering (3DMMF) with motion compensation on video sequences. Due to the nature of unbalanced load of the ...
详细信息
ISBN:
(纸本)0780331222
This paper aims to develop effective parallel processing techniques for 3-dimensional (3D) multi-level median filtering (3DMMF) with motion compensation on video sequences. Due to the nature of unbalanced load of the filtering algorithm and the objective for the parallel approach, two methods of dynamic load balancing have been proposed and compared. They are sender-initiated-load-balancing (SILB) and receiver-initiated-load-balancing (RILB) algorithms. We propose a SILB algorithm which utilises the spatial-temporal characteristics of the processed sequences for load prediction to achieve dynamic load balancing. Both theoretical analysis and experimental results on the IBM SP2 computing surface have been presented in this paper.
Lyapunov vectors and exponents are of great importance for understanding the dynamics of many-particle systems. We present results of performance tests on different processor architectures of several parallel implemen...
详细信息
ISBN:
(纸本)3540290672
Lyapunov vectors and exponents are of great importance for understanding the dynamics of many-particle systems. We present results of performance tests on different processor architectures of several parallel implementations for the calculation of all Lyapunov characteristics. For the most time consuming reorthogonalization steps, which have to be combined with molecular dynamics simulations. we tested different parallel versions of the Gram-Schmidt algorithm and of QR-decomposition. The latter gave the best results with respect to runtime and stability. For large systems the blockwise parallel Gram-Schmidt, algorithm yields comparable runtime results.
Novel high throughput sequencing technologies have redefined the way genome sequencing is performed. They are able to produce millions of short sequences in a single experiment and with a muck lower cost than previous...
详细信息
ISBN:
(纸本)9788001044032
Novel high throughput sequencing technologies have redefined the way genome sequencing is performed. They are able to produce millions of short sequences in a single experiment and with a muck lower cost than previous methods. In this paper, we address the problem of efficiently mapping and classifying millions of degenerate and weighted sequences to a reference genome, based on whether they occur exactly once in the get rot ire or not, and by taking into consideration probability scores. in particular, we design parallel algorithms for Massive Exact and Approximate Unique Pattern Matching for degenerate and weighted sequences derived from high throughput sequencing technologies.
The most important geophysical problems are inverse gravimetry and magnetometry problems. Among them are the structural gravimetry and magnetometry problems of finding interfaces between layers with different densitie...
详细信息
ISBN:
(纸本)9786197105100
The most important geophysical problems are inverse gravimetry and magnetometry problems. Among them are the structural gravimetry and magnetometry problems of finding interfaces between layers with different densities or magnetizations using known gravitational or magnetic data [1], [2], [3]. The gravimetry and magnetometry problems are described by nonlinear integral Fredholm equations of the first kind;they are ill-posed problems. After the discretization of integral operators, the problems are reduced to systems of nonlinear equations with dense matrices. The real gravity and magnetic measurements are carried out over a large area producing large-scale grids. Processing of gravity and magnetic data is time consuming and requires a lot of memory. In this paper, for solving the structural inverse magnetometry problem in a multilayer medium, efficient stable parallel algorithms based on iteratively regularized gradient methods with variable weight factors are proposed. The algorithms were implemented numerically with using new computing technologies on the parallel computing system Uran at the Institute of Mathematics and Mechanics of the UB RAS. The structural magnetometry problem with "quasi-model" data was solved.
暂无评论