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

A parallel algorithm for computing Voronoi diagram of a set of spheres using restricted lower envelope approach and topology matching

引用

COMPUTERS & GRAPHICS-UK 2022年 106卷 210-221页

作者： Mukundan, Manoj Kumar Thayyil, Safeer Babu Muthuganapathy, Ramanathan Indian Inst Technol Madras Dept Engn Design Adv Geometr Comp Lab Chennai India Govt Engn Coll Palakkad Dept Informat Technol Palakkad Kerala India Rajiv Gandhi Inst Technol Dept Mech Engn Kottayam Kerala India

We present a parallel algorithm for computing the Voronoi diagram of a set of spheres, S in R3. The spheres have varying radii and do not intersect. We compute each Voronoi cell independently using a two-stage iterative procedure, assuming the input spheres are in general position. In the first stage, an initial Voronoi cell for a sphere si is computed using an iterative lower envelope approach restricted to a subset of spheres Li subset of S. This helps to avoid defining the bisectors between all pairs of input spheres and develop a distributed memory parallel algorithm. We use the Delaunay graph of sample points from the input spheres to select the subset Li for computing each Voronoi cell. In the second stage, Voronoi cells obtained from the first stage are matched for updating the subsets. If additional spheres are added to a subset Li, the correctness of the computed vertices is verified with the bisectors of spheres newly added to Li. Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of spheres.

关键词： Voronoi diagram Topology matching Delaunay graph Touching sphere Lower envelope parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED parallel algorithm FOR CONSTRUCTING VORONOI DIAGRAM ON A MESH-CONNECTED COMPUTER

引用

parallel COMPUTING 1991年第4-5期17卷 505-514页

作者： JEONG, CS Department of Computer Science Pohang Institute of Science and Technology P.O. Box 125 Pohang Kyungbuk 680 Korea

While constructing a Voronoi diagram V(P) for a set of P of n points on a mesh-connected computer (MCC), it is necessary to find a set B of edges which are intersected by the dividing chain C during the merge process of two Voronoi diagrams V(L) and V(R), where L and R contain the leftmost [n/2] points and the rightmost [n/2] points of P respectively. The computation of B requires two operations: First decide for each edge e in V(L) and V(R) whether its end vertices are closer to L or R, and then from that information, determine whether e is intersected by C. However, in the previous parallel algorithm each of the former and latter operations requires planar point location which takes O(square-root n) time on square-root n x square-root n MCC, and in addition the former operation needs to compute convex hulls of L and R. In this paper, we shall show that the latter operation can be done in O(1) time without executing planar point location and the former operation can be executed without the computation of convex hulls. Therefore, the computation of B is reduced to only one planar point location.

关键词： parallel algorithm VORONOI DIAGRAM MESH-CONNECTED COMPUTER

来源：评论

学校读者我要写书评

暂无评论

Accelerating computed tomographic imaging spectrometer reconstruction using a parallel algorithm exploiting spatial shift-invariance

引用

OPTICAL ENGINEERING 2020年第5期59卷

作者： White, Larz Bell, W. Bryan Haygood, Ryan Lockheed Martin Aeronaut Ft Worth TX 76108 USA

Computed tomographic imaging spectrometers capture hyperspectral images in real-time. However, postprocessing the imagery can require enormous computational resources;thus, limiting its application to nonrealtime scenarios. To overcome these challenges, we developed a highly parallelizable algorithm that exploits spatial shift-invariance. To demonstrate the versatility of our algorithm, we developed implementations on a desktop and an embedded graphics processing unit. To our knowledge, our results show the fastest image reconstruction times reported. (C) 2020 Society of Photo-Optical Instrumentation Engineers (SPIE)

关键词： GPU CUDA CTIS computed tomography imaging spectrometer parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Hybrid swarm intelligent parallel algorithm research based on multi-core clusters

引用

MICROPROCESSORS AND MICROSYSTEMS 2016年 47卷 151-160页

作者： Li, Wenjing Bi, Yingzhou Zhu, Xiaofeng Yuan, Chang-an Zhang, Xiang-bo Guangxi Teachers Educ Univ Sci Comp & Intelligent Informat Proc GuangXi High Nanning 530023 Guangxi Peoples R China Guangxi Teachers Educ Univ Coll Comp & Informat Engn Nanning 530023 Guangxi Peoples R China Univ N Carolina Dept Radiol Chapel Hill NC USA Univ N Carolina BRIC Chapel Hill NC USA

In order to solve poor fine searching capacity of artificial fish swarm algorithm and artificial bee colony swarm algorithm in late state to result in insufficient local optimization, hybrid swarm intelligent parallel algorithm research based on multi-core clusters is proposed;Then, reverse learning mechanism is introduced in early stage of algorithm, initialized swarms are evenly distributed, and swarms are randomly divided into two groups to make interactive learning strategy accelerates rate of convergence, and basic artificial fish swarm algorithm and artificial bee colony swarm algorithm are used to make global searching. In late stage of algorithm, niches artificial fish swarm algorithm and Random Perturbation Artificial Bee Colony are used to make local fine searching to the solution obtained in early stage;On this basis, MPI+OpenMP+STM parallel programming model based on multi-core clusters is established for parallel design and analysis. Finally, stimulation experiment indicates optimizing efficiency of this algorithm is higher than single artificial fish swarm algorithm and artificial bee colony swarm algorithm. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Artificial fish swarm algorithm Artificial bee colony swarm algorithm Optimization Hybrid swarm intelligent algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm of Image Mean Filtering Based on OpenCL

引用

IEEE ACCESS 2021年 9卷 65001-65016页

作者： Xiao, Han Guo, Baoyun Zhang, Hongyan Li, Cailin Zhengzhou Normal Univ Sch Informat Sci & Technol Zhengzhou 450044 Peoples R China Shandong Univ Technol Sch Civil & Architectural Engn Zibo 255000 Peoples R China

The image will be contaminated by noise during the imaging process, which severely degrades the image quality. It is necessary to filter the collected image. With the increasing amount of image data, the traditional single-processor or multiprocessor computing equipment has been unable to meet the requirements of real-time data processing. In this paper, the computational model of weighted mean filtering and the characteristics of high performance computer architecture are studied. An efficient hierarchical image weighted mean filtering parallel algorithm for Open Computing Language (OpenCL) is designed and implemented, which can fully express the parallelism of the computing model. The parallel algorithm takes full account of the characteristics of image discrete convolution computing and the multi-layer logic architecture of high performance computer, deeply excavates the parallelism of the computing platform and computing model, and realizes the efficient task mapping from computing model to computing resources. The model is implemented in parallel with the two levels of work-group and work-item. The experimental results show that compared with the serial algorithm based on CPU, the parallel algorithm based on Open Multi-Processing (OpenMP) and the parallel algorithm based on Compute Unified Device Architecture (CUDA), the parallel algorithm of weighted mean filtering achieves 20.88 times, 18.52 times and 1.26 times acceleration ratio on the NVIDIA GPU computing platform based on OpenCL architecture, respectively. It realizes better computing performance and runs on different Graphic Processing Unit (GPU) computing platforms, and has good portability and scalability.

关键词： Graphics processing units Filtering parallel algorithms Filtering algorithms Computational modeling Acceleration Signal processing algorithms Weighted mean filtering Gaussian noise Graphic Processing Unit (GPU) Open Computing Language (OpenCL) parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast parallel algorithm for distance transform

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS 2003年第4期33卷 429-434页

作者： Datta, A Soundaralakshmi, S Univ Western Australia Sch Comp Sci & Software Engn Perth WA 6009 Australia

We present an O((log log N)(2)) -time algorithm for computing the distance transform of an N x N binary image. Our algorithm is designed for the common concurrent read concurrent write parallel random access machine (CRCW PRAM) and requires O(N2+epsilon / log log N) processors, for any epsilon such that 0 < E < 1. Our algorithm is based on a novel deterministic sampling scheme and can be used for computing distance transforms for a very general class of distance functions. We also present a scalable version of our algorithm when the number of processors is available p(2+epsilon) / log log p for some p < N. In this case, our algorithm runs in O((N-2/p(2)) + (N/p) log log p + (log log p)(2)) time. This scalable algorithm is more practical since usually the number of available processors is much less than the size of the image.

关键词： binary image CRCW PRAM deterministic sampling distance transform parallel algorithm pattern recognition scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

A new constant-time parallel algorithm for merging

引用

JOURNAL OF SUPERCOMPUTING 2019年第2期75卷 968-983页

作者： Bahig, Hazem M. Ain Shams Univ Fac Sci Dept Math Div Comp Sci Cairo 11566 Egypt Hail Univ Comp Sci & Engn Coll Hail Saudi Arabia

Merging is the process of constructing a sorted array C from two sorted arrays A and B of lengths nA and nB, respectively, such that array C contains the elements of arrays A and B. The problem is a fundamental subroutine in many applications such as tree reconstruction, database design, and sorting. In this paper, we present a constant-time integer merging algorithm on a shared memory model with a concurrent read operation. No constant-time algorithm for integer merging on this model was designed previously. The algorithm, which is based on cross-rank and address strategy, works when the elements of the inputs belong to the integer domain. The presented algorithm has the following advantages:- (1) running in constant time;(2) stable;(3) simple;(4) optimal when the domain of integers is less than or equal to the size of the inputs and the number of processors is equal to size of the inputs;and (5) deterministic.

关键词： Integer merging parallel algorithm Shared memory Concurrent read Constant-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Study on high speed parallel algorithm using PC grid environment for visualization measurements by Digital Holographic Particle Tracking Velocimetry

引用

COMPUTER PHYSICS COMMUNICATIONS 2008年第1期178卷 1-7页

作者： Satake, Shin-Ichi Anraku, Takafumi Kanamori, Hiroyuki Kunugi, Tomoaki Sato, Kazuho Ito, Tomoyoshi Tokyo Univ Sci Dept Appl Elect Noda Chiba 2788510 Japan Kyoto Univ Grad Sch Engn Dept Nucl Engn Kyoto 6068501 Japan Toyota Ind Corp Aichi 4488671 Japan Chiba Univ Japan Sci & Technol Agcy Inage Ku Chiba 2638522 Japan Chiba Univ Dept Elect & Mech Engn Inage Ku Chiba 2638522 Japan

A micro-digital holographic particle tracking velocimetry with high-speed system is constructed by a PC grid environment that employs Windows XP with AD-POWERs as parallel tool. Two algorithms for high-speed system are evaluated under the same PC grid environment. Both methods are based on a computer-generated hologram algorithm. One method is a division algorithm based on time development for the measurements, while the other is a division algorithm based on spatial reconstruction for the measurement. In case of the former, the performance is increased by a factor of 3.3 by using 4 PCs. The present system can compute huge hologram images and output them "on-site" at an experimental facility. (c) 2007 Elsevier B.V. All fights reserved.

关键词： parallel algorithm grid computing image processing digital holography particle tracking Velocimetry microflow

来源：评论

学校读者我要写书评

暂无评论

A FAST AND SIMPLE RANDOMIZED parallel algorithm FOR MAXIMAL MATCHING

引用

INFORMATION PROCESSING LETTERS 1986年第2期22卷 77-80页

作者： ISRAELI, A ITAI, A TECHNION ISRAEL INST TECHNOL DEPT COMP SCIIL-32000 HAIFAISRAEL

A parallel randomized algorithm to find a maximal matching is presented. Its expected running time on a CRCW-PRAM with vbEvb processors in O(logvbEvb). The expected time is independent of the structure of the input gr... 详细信息

关键词： Maximal matching parallel algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

引用

DISCRETE MATHEMATICS 2009年第6期309卷 1611-1622页

作者： Sarkozy, Gabor N. Worcester Polytech Inst Dept Comp Sci Worcester MA 01609 USA Hungarian Acad Sci Comp & Automat Res Inst H-1518 Budapest Hungary

Suppose than 0 = n - k. (Thus for eta = 0 we get the well-known Chvata graphs.) An NC(4)-algorithm is presented which accepts as input an eta-Chvatal graph and produces a Hamiltonian cycle in G as an output. This is a... 详细信息

Suppose than 0 < eta < 1 is given. We call a graph, G, on n vertices an eta-Chvatal graph if its degree sequences d(1) <= d(2) <= ... <= d(n) satisfies: for k < n/2, d(k) <= min {k + eta n. n/2} implies d(n-k-eta n) >= n - k. (Thus for eta = 0 we get the well-known Chvata graphs.) An NC(4)-algorithm is presented which accepts as input an eta-Chvatal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best NC-algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (delta(G) >= n/2 where delta(G) is the minimum degree in G). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Hamiltonian cycle parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：