A bijective code is a method for associating labeled n-trees to (n - 2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequenti...
详细信息
ISBN:
(纸本)9783642114397
A bijective code is a method for associating labeled n-trees to (n - 2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequential encoding and decoding algorithms are presented in literature, while parallel algorithms are investigated only for sonic of these codes. In this paper we focus our attention on the Blob code: a. code particularly considered in the field of Genetic algorithms. To the best of our knowledge, here we present the first parallel encoding and decoding algorithms for this code. The encoding algorithm implementation is optimal on an EREW PRAM, while the decoding algorithm requires O(log n) time and O(n) processors on CREW PRAM.
Given a trace of a distributed computation and a desired predicate, the predicate detection problem is to find a consistent global state that satisfies the given predicate. The predicate detection problem has many app...
详细信息
ISBN:
(纸本)9781450360944
Given a trace of a distributed computation and a desired predicate, the predicate detection problem is to find a consistent global state that satisfies the given predicate. The predicate detection problem has many applications in the testing and runtime verification of parallel and distributed systems. We show that many problems related to predicate detection are in the parallel complexity class NC, the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. Given a computation on n processes with at most m local states per process, our parallel algorithm to detect a given conjunctive predicate takes O(log mn) time and O(m(3)n(3) log mn) work. The sequential algorithm takes O(mn(2)) time. For data race detection, we give a parallel algorithm that takes O(logmn log n) time, also placing that problem in NC. This is the first work, to the best of our knowledge, that places the parallel complexity of such predicate detection problems in the class NC.
In this paper, based on the advantages of both optical transmission and electronic computation, we first provide an O(log log N) bus cycles parallel algorithm for weighted distance transforms of an NxN binary image on...
详细信息
ISBN:
(纸本)9783642030949
In this paper, based on the advantages of both optical transmission and electronic computation, we first provide an O(log log N) bus cycles parallel algorithm for weighted distance transforms of an NxN binary image on a linear array with a reconfigurable pipelined bus System using N-2 processors. By increasing the number of processors, the proposed algorithm can be run in O(loglog(q) N) and O(l) bus cycles using qN(2) and N2+1/epsilon processors respectively, where 2 <= q <= root N, epsilon is a constant and epsilon >= 1. These results improve on previously known algorithms developed on various parallel computation models.
In the last few years, molecular biology has produced a large amount of data, mainly in the form of sequences, that is, strings over am alphabet of four (DNA/RNA) or twenty symbols (proteins). For computational biolog...
详细信息
ISBN:
(纸本)3540425225
In the last few years, molecular biology has produced a large amount of data, mainly in the form of sequences, that is, strings over am alphabet of four (DNA/RNA) or twenty symbols (proteins). For computational biologists the main challenge now is to provide efficient tools for the analysis and the comparison of the sequences. In this paper, we introduce and briefly discuss some open problems, and present a parallel algorithm that finds repeated substrings in a DNA sequence or common substrings in a set of sequences. The occurrences of the substrings can be approximate, that is, can differ up to a maximum number of mismatches that depends on the length of the substring itself. The output of the algorithm is sorted according to different statistical measures of significance. The algorithm has been successfully implemented on a cluster of workstations.
We develop and evaluate parallel algorithms for a fundamental problem in numerical computing, namely the evaluation of a polynomial of a matrix. The algorithm consists of many building blocks that can be assembled in ...
详细信息
ISBN:
(纸本)9781450362955
We develop and evaluate parallel algorithms for a fundamental problem in numerical computing, namely the evaluation of a polynomial of a matrix. The algorithm consists of many building blocks that can be assembled in several ways. We investigate parallelism in individual building blocks, develop parallel implemenations, and assemble them into an overall parallel algorithm. We analyze the effects of both the dimension of the matrix and the degree of the polynomial on both arithmetic complexity and on parallelism, and we consequently propose which variants use in different cases. Our theoretical results indicate that one variant of the algorithm, based on applying the Paterson-Stockmeyer method to the entire matrix, parallelizes very effectively on virtually any matrix dimension and polynomial degree. However, it is not the most efficient from the arithmetic complexity viewpoint. Another algorithm, based on the Davies-Higham block recurrence is much more efficient from the arithmetic complexity viewpoint, but one of its building blocks is serial. Experimental results on a dual-socket 28-core server show that the first algorithm can effectively use all the cores, but that on high-degree polynomials the second algorithm is often faster, in spite of the sequential phase. This indicates that our parallel algorithms for the other phases are indeed effective.
parallel implementation of the implicit LU-SGS solver is considered. It leads to the graph coloring problem. A novel recursive graph coloring algorithm has been proposed that requires only three colors on 2: 1 balance...
详细信息
ISBN:
(纸本)9783319629322;9783319629315
parallel implementation of the implicit LU-SGS solver is considered. It leads to the graph coloring problem. A novel recursive graph coloring algorithm has been proposed that requires only three colors on 2: 1 balanced quadtree-based meshes. The algorithm has been shown to allow simple parallel implementations, including GPU architectures, and is fully coherent with local grid coarsing/refining procedures resulting in highly effective co-execution with local grid adaptation.
Multi-valued Decision Diagrams (MDDs) have been extensively studied in the last ten years. Recently, efficient algorithms implementing operators such as reduction, union, intersection, difference, etc., have been desi...
详细信息
ISBN:
(纸本)9781577358008
Multi-valued Decision Diagrams (MDDs) have been extensively studied in the last ten years. Recently, efficient algorithms implementing operators such as reduction, union, intersection, difference, etc., have been designed. They directly deal with the graph structure of the MDD and a time reduction of several orders of magnitude in comparison to other existing algorithms have been observed. These operators have permitted a new look at MDDs, because extremely large MDDs can finally be manipulated as shown by the models used to solve complex application in music generation. However, MDDs become so large (50GB) that minutes are sometimes required to perform some operations. In order to accelerate the manipulation of MDDs, parallel algorithms are required. In this paper, we introduce such algorithms. We carefully design them in order to overcome inherent difficulties of the parallelization of sequential algorithms such as data dependencies, software lock-out, false sharing, or load balancing. As a result, we observe a speed-up, i.e. ratio between parallel and sequential runtimes, growing linearly with the number of cores.
The first generation of transitive stereo-metric satellites in China, TH-1 Satellite, is able to gain stereo images of three-line-array with resolution of 5 meters, multispectral images of 10 meters, and panchromatic ...
详细信息
ISBN:
(纸本)9781628411768
The first generation of transitive stereo-metric satellites in China, TH-1 Satellite, is able to gain stereo images of three-line-array with resolution of 5 meters, multispectral images of 10 meters, and panchromatic high resolution images of 2 meters. The procedure between level 0 and level 1A of high resolution images is so called relative radiometric correction (RRC for short). The processing algorithm of high resolution images, with large volumes of data, is complicated and time consuming. In order to bring up the processing speed, people in industry commonly apply parallel processing techniques based on CPU or GPU. This article firstly introduces the whole process and each step of the algorithm - that is in application - of RRC for high resolution images in level 0;secondly, the theory and characteristics of MPI (Message Passing Interface) and OpenMP (Open Multi-Processing) parallel programming techniques is briefly described, as well as the superiority for parallel technique in image processing field;thirdly, aiming at each step of the algorithm in application and based on MPI+OpenMP hybrid paradigm, the parallelizability and the strategies of parallelism for three processing steps: Radiometric Correction, Splicing Pieces of TDICCD (Time Delay Integration Charge-Coupled Device) and Gray Level Adjustment among pieces of TDICCD are deeply discussed, and furthermore, deducts the theoretical acceleration rates of each step and the one of whole procedure, according to the processing styles and independence of calculation;for the step Splicing Pieces of TDICCD, two different strategies of parallelism are proposed, which are to be chosen with consideration of hardware capabilities;finally, series of experiments are carried out to verify the parallel algorithms by applying 2-meter panchromatic high resolution images of TH-1 Satellite, and the experimental results are analyzed. Strictly on the basis of former parallel algorithms, the programs in the experiments are wri
We present new parallel algorithms for testing pattern involvement for all length 4 permutations. Our algorithms have the complexity of O(log n) time with n/log n processors on the CREW PRAM model, O(log log log n) ti...
详细信息
ISBN:
(纸本)9781479938445
We present new parallel algorithms for testing pattern involvement for all length 4 permutations. Our algorithms have the complexity of O(log n) time with n/log n processors on the CREW PRAM model, O(log log log n) time with n/log log log n processors or constant time and n log 3 n processors on a CRCW PRAM model. parallel algorithms were not designed before for some of these patterns and for other patters the previous best algorithms require O(log n) time and n processors on the CREW PRAM model.
暂无评论