检索结果-内蒙古大学图书馆

3D block-based medial axis transform and chessboard distance transform based on dominance

IMAGE AND VISION COMPUTING 2011年第4期29卷 272-285页

作者： Lin, Shih-Ying Horng, Shi-Jinn Kao, Tzong-Wann Fahn, Chin-Shyurng Fan, Pingzhi Chen, Yuan-Hsin Khan, Muhammad Khurram Bourgeois, Anu Terano, Takao Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei Taiwan Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei Taiwan Natl United Univ Dept Elect Engn Miaoli Taiwan Technol & Sci Inst No Taiwan Dept Elect Engn Taipei Taiwan SW Jiaotong Univ Inst Mobile Commun Chengdu 610031 Peoples R China King Saud Univ Ctr Excellence Informat Assurance Riyadh 11451 Saudi Arabia Georgia State Univ Dept Comp Sci Atlanta GA 30302 USA Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Tokyo Japan

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N-3, our parallel algorithm can be run in O(logN) time using N3 processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size. (C) 2010 Elsevier BM. All rights reserved.

关键词： parallel algorithm Image processing CREW PRAM model Block-based medial axis transform Chessboard distance transform Euclidean distance transform

来源：评论

学校读者我要写书评

暂无评论

Simulation of 1+1 dimensional surface growth and lattices gases using GPUs

引用

COMPUTER PHYSICS COMMUNICATIONS 2011年第7期182卷 1467-1476页

作者： Schulz, Henrik Odor, Geza Odor, Gergely Nagy, Mate Ferenc Helmholtz Zentrum Dresden Rossendorf D-01314 Dresden Germany Res Inst Tech Phys & Mat Sci H-1525 Budapest Hungary Res Inst Particle & Nucl Phys H-1525 Budapest Hungary ELTE TTK H-1117 Budapest Hungary

Restricted solid on solid surface growth models can be mapped onto binary lattice gases. We show that efficient simulation algorithms can be realized on CPUs either by CUDA or by OpenCL programming. We consider a deposition/evaporation model following Kardar-Parisi-Zhang growth in 1 + 1 dimensions related to the Asymmetric Simple Exclusion Process and show that for sizes, that fit into the shared memory of CPUs one can achieve the maximum parallelization speedup (similar to x 100 for a Quadro FX 5800 graphics card with respect to a single CPU of 2.67 GHz). This permits us to study the effect of quenched columnar disorder, requiring extremely long simulation times. We compare the CUDA realization with an OpenCL implementation designed for processor clusters via MPI. A two-lane traffic model with randomized turning points is also realized and the dynamical behavior has been investigated. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Surface growth Lattice gases GPU parallel algorithm KPZ equation

来源：评论

学校读者我要写书评

暂无评论

Constructing independent spanning trees for locally twisted cubes

引用

THEORETICAL COMPUTER SCIENCE 2011年第22期412卷 2237-2252页

作者： Liu, Yi-Jiun Lan, James K. Chou, Well Y. Chen, Chiuyuan Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ(n). The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ(n). However, we find out that LTQ(n) is not vertex-transitive when n >= 4;therefore Hsieh and Tu's result does not solve the Edge Conjecture for LTQ(n),,. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ(n);consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ(n),. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Independent spanning trees Data broadcasting Design and analysis of algorithms Locally twisted cubes Hypercubes Hypercube variants parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Spatial-Temporal Coverage Optimization in Wireless Sensor Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2011年第4期10卷 465-478页

作者： Liu, Changlei Cao, Guohong Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA

Mission-driven sensor networks usually have special lifetime requirements. However, the density of the sensors may not be large enough to satisfy the coverage requirement while meeting the lifetime constraint at the same time. Sometimes, coverage has to be traded for network lifetime. In this paper, we study how to schedule sensors to maximize their coverage during a specified network lifetime. Unlike sensor deployment, where the goal is to maximize the spatial coverage, our objective is to maximize the spatial-temporal coverage by scheduling sensors' activity after they have been deployed. Since the optimization problem is NP-hard, we first present a centralized heuristic whose approximation factor is proved to be 1 2, and then, propose a distributed parallel optimization protocol (POP). In POP, nodes optimize their schedules on their own but converge to local optimality without conflict with one another. Theoretical and simulation results show that POP substantially outperforms other schemes in terms of network lifetime, coverage redundancy, convergence time, and event detection probability.

关键词： Wireless sensor network coverage sensor scheduling distributed protocol parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for Automatic Database Normalization

Parallel Algorithms for Automatic Database Normalization

引用

2nd International Conference on Computer and Automation Engineering (ICCAE)

作者： Bahmani, Amir-H. Shekofteh, S. Kazem Naghibzadeh, Mahmoud Deldari, Hossein Islamic Azad Univ Dept Comp Engn Young Researchers Club Mashhad Iran Ferdowsi Univ Mashhad Fac Engn Dept Comp Engn Mashhad Iran

ISBN: (纸本)9781424455690

As processing power becomes cheaper and more available by using cluster of computers, the needs for parallel algorithms, which can harness these computing potentials, are increasing. Automatic database normalization is an application of parallel algorithms. Normalization is the most exercised technique for the analysis of relational databases. It aims at creating a set of relational tables with minimum data redundancy that preserve consistency and facilitate correct insertion, deletion, and modification. While existing sequential algorithms are usually much time consuming, especially the process of transforming relations into 3NF, in this paper, we have proposed parallel algorithms for automatic database normalization. The proposed algorithms have been examined with MPI and its implementation results on EDM showed that parallel approach reduces the time, efficiently. Exploiting p processors has reduced the time of Automatic Database Normalization to n(2).m/p+c in which c is the communication overhead between the processors, m is the number of simple keys, and n is the number of determinant keys.

关键词： automaic database normalization parallel algorithm mpi

来源：评论

学校读者我要写书评

暂无评论

A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network

引用

DIGITAL SIGNAL PROCESSING 2011年第4期21卷 517-521页

作者： Zhang, Yudong Wu, Lenan Wei, Geng Wang, Shuihua Southeast Univ Sch Informat Sci & Engn Nanjing Peoples R China

All pairs shortest path (APSP) is a classical problem with diverse applications. Traditional algorithms are not suitable for real time applications, so it is necessary to investigate parallel algorithms. This paper presents an improved matrix multiplication method to solve the APSO problem. Afterwards, the pulse coupled neural network (PCNN) is employed to realize the parallel computation. The time complexity of our strategy is only O (log(2) n), where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods. (C) 2011 Elsevier Inc. All rights reserved.

关键词： All pairs shortest path Pulse coupled neural network Matrix multiplication parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction

引用

JOURNAL OF CRYPTOGRAPHIC ENGINEERING 2011年第3期1卷 187-199页

作者： Taverne, Jonathan Faz-Hernandez, Armando Aranha, Diego F. Rodriguez-Henriquez, Francisco Hankerson, Darrel Lopez, Julio Univ Lyon Univ Lyon 1 ISFA Lyon France CINVESTAV IPN Dept Comp Sci Mexico City DF Mexico Univ Estadual Campinas Inst Comp Campinas SP Brazil Auburn Univ Auburn AL 36849 USA

The availability of a newcarry-lessmultiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112-and 192-bit security levels and a newspeed record for side-channel-resistant scalar multiplication in a random curve at the 128-bit security level. The algorithms presented in this work were implemented on Westmere and Sandy Bridge processors, the latest generation Intel microarchitectures.

关键词： Elliptic curve cryptography Finite field arithmetic parallel algorithm Efficient software implementation

来源：评论

学校读者我要写书评

暂无评论

The orbit problem is in the GapL hierarchy

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第1期21卷 124-137页

作者： Arvind, V. Vijayaraghavan, T. C. Inst Math Sci Madras 600113 Tamil Nadu India Chennai Math Inst Siruseri 603103 India

The Orbit problem is defined as follows: Given a matrix A is an element of Q(nxn) and vectors x, y is an element of Q(n), does there exist a non-negative integer i such that A(i)x = y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4): 808-821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C(=)L with respect to logspace many-one reductions.

关键词： Orbit problem Linear algebra parallel complexity Logspace counting classes parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A new VLSI algorithm and architecture for the hardware implementation of type IV discrete cosine transform using a pseudo-band correlation structure

引用

OPEN COMPUTER SCIENCE 2011年第2期1卷 243-250页

作者： Chiper, Doru Florin Tech Univ Gh Asachi Iasi Dept Appl Elect B Dul Carol 111 RO-6600 Iasi Romania

A new VLSI algorithm and its associated systolic array architecture for a prime length type IV discrete cosine transform is presented. They represent the basis of an efficient design approach for deriving a linear systolic array architecture for type IV DCT. The proposed algorithm uses a regular computational structure called pseudoband correlation structure that is appropriate for a VLSI implementation. The proposed algorithm is then mapped onto a linear systolic array with a small number of I/O channels and low I/O bandwidth. The proposed architecture can be unified with that obtained for type IV DST due to a similar kernel. A highly efficient VLSI chip can be thus obtained with good performance in the architectural topology, computing parallelism, processing speed, hardware complexity and I/O costs similar to those obtained for circular correlation and cyclic convolution computational structures.

关键词： parallel algorithm parallel architecture systolic arrays

来源：评论

学校读者我要写书评

暂无评论

parallel finite element algorithm based on full domain partition for stationary Stokes equations

引用

Applied Mathematics and Mechanics(English Edition) 2010年第5期31卷 643-650页

作者：尚月强何银年 School of Mathematics and Computer Science Guizhou Normal University Faculty of Science Xi'an Jiaotong University

Based on the full domain partition, a parallel finite element algorithm for the stationary Stokes equations is proposed and analyzed. In this algorithm, each subproblem is defined in the entire domain. Majority of the degrees of freedom are associated with the relevant subdomain. Therefore, it can be solved in parallel with other subproblems using an existing sequential solver without extensive recoding. This allows the algorithm to be implemented easily with low communication costs. Numerical results are given showing the high efficiency of the parallel algorithm.

关键词： Stokes equations finite element parallel algorithm full domain partition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：