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

Independent and cooperative parallel search methods for the generalized assignment problem

OPTIMIZATION METHODS & SOFTWARE 2003年第2期18卷 129-141页

作者： Asahiro, Y Ishibashi, M Yamashita, M Kyushu Sangyo Univ Dept Social Informat Syst Fac Informat Sci Higashi Ku Fukuoka 8138503 Japan Kyushu Univ Dept Comp Sci & Commun Engn Grad Sch Informat Sci & Elect Engn Higashi Ku Fukuoka 8128581 Japan

The generalized assignment problem is a representative NP-hard problem, for which many heuristic algorithms are known. In this article, two parallel heuristic algorithms are proposed, which are based on the ejection chain local search (EC) proposed by Yagiura et al. One is a simple parallelization called multistart parallel EC (MPEC) and the other is cooperative parallel EC (CPEC). In MPEC each search process independently explores search space while in CPEC search processes share partial information to cooperate with each other. The experimental results with 9 computers for large benchmark instances show that (1) MPEC and CPEC, respectively, run twice and 4 times faster than EC, and (2) compared to EC, the difference in quality between obtained solutions and theoretical lower bounds is reduced to 3/4 and 2/3 by MPEC and CPEC, respectively. It is said that these methods give us full benefit of parallelization, speedup and improvement for quality of solutions.

关键词： generalized assignment problem heuristics local search parallel algorithm PC cluster

来源：评论

学校读者我要写书评

暂无评论

parallel Computation of the 3-D Euclidean Distance Transform on the SIMD Hypercube Computer

Parallel Computation of the 3-D Euclidean Distance Transform...

引用

The Fourth International Conference on parallel and Distributed Computing, Applications and Technologies

作者： Yu-Hua Lee Shi-Jinn Horng Department of Computer Science and Information Engineering Ching Yun Instutute of Technology Department of Computer Science and Information Engineering National Taiwan University of Science and Technology

The processing of three-dimensional（3-D） objects from 3-D digital image data is an important task in the image processing and the computer vision *** distance transform（DT） is extensively applied in the image processing and computer vision areas as a key operation. In a two or three-dimensional image array,the computation of distance transform（DT） is an important task. With the increasing application of 3D voxel images,it is useful to consider the distance transform of a 3D digital image *** order to provide the efficient transform computations, parallelism is *** develop parallel algorithms for the three-dimensional Euclidean distance transform （3D-EDT） on the SIMD hypercube *** time complexity of our parallel algorithm is O（log N） for an N×JV×N image array using JV3 processors.A generalized parallel algorithm for the 3D-EDT is also proposed and it runs O(（N/p） log（N） +（N/p） log p) time for an N×N×N binary image array on the SIMD hypercube computer using p PE's,where 1≤p≤N.

关键词： Computer Vision Distance Transform Image Processing parallel algorithm SIMD Hypercube Computer

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for volume projections on SIMD mesh-connected computers

引用

JOURNAL OF SUPERCOMPUTING 2000年第1期17卷 5-22页

作者： Li, HZ Shi, HC Univ Missouri Dept Comp Engn & Comp Sci Columbia MO 65211 USA

Projections are widely used in machine vision, volume rendering, and computer graphics. For applications with 3D volume data, we design a parallel projection algorithm on SIMD mesh-connected computers and implement the algorithm on the parallel Algebraic Logic (PAL) computer. The algorithm is a parallel ray casting algorithm for both orthographic and perspective projections. It decomposes a volume projection into two transformations that can be implemented in the SIMD fashion to solve the data distribution and redistribution problem caused by non-regular data access patterns in volume projections.

关键词： volume projection matrix decomposition parallel algorithm mesh-connected computer data distribution and redistribution

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for minimum spanning tree problem

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2002年第4期79卷 441-448页

作者： Ahrabian, H Nowzari-Dalini, A Univ Tehran Fac Sci Dept Math & Comp Sci Tehran Iran Univ Tehran Fac Sci Dept Math & Comp Sci Tehran Iran

Two parallel algorithms are presented for solving the minimum cost spanning tree problem in any undirected graph. These algorithms are parallel formulations of DHEA algorithm using Depth-First Search of the graph, The... 详细信息

关键词： graph minimum spanning tree parallel algorithm cost-optimality

来源：评论

学校读者我要写书评

暂无评论

The Non-eye Typhoon Center Locating with parallel Computing

The Non-eye Typhoon Center Locating with Parallel Computing

引用

Proceedings of The Fourth International Conference on parallel and Distribyted Computing,Applications and Technologies(第四届并行与分布式计算应用与技术国际会议)

作者： Juntao Xue Zhengguang Liu Bing Wu Huanzhu Liu School of Engineering Electrical and Automation Tianjin University 300072 China National Meteorological Center Beijing 100081 China

ISBN: (纸本)0780378407

A new mathematical morphology-based algorithm is proposed to achieve automatic center location of non-eye typhoon. The center of a non-eye typhoon is near the geometric center of the cloud system and has higher temperature. For each infrared satellite cloud image, the locating procedures are as follows: a) noises filtering, b) main cloud systems segmenting, c) center locating and d) multispectral image verification. The algorithms are based on operations of mathematical morphology, and designed in IBM SP2 massively parallel computer. The experiment results show that the algorithm locates the centers of most non-eye typhoons successfully and achieves faster, more precise and non-human interactive non-eye typhoon center positioning.

关键词： Satellite cloud image Non-eye typhoon locating parallel algorithm Mathematical morphology

来源：评论

学校读者我要写书评

暂无评论

The Non-eye Typhoon Center Locating with parallel Computing

The Non-eye Typhoon Center Locating with Parallel Computing

引用

The Fourth International Conference on parallel and Distributed Computing, Applications and Technologies

作者： Zhengguang Liu Bing Wu Juntao Xue Huanzhu Liu School of Engineering Electrical and Automation Tianjin University National Meteorological Center

A new mathematical morphology-based algorithm is proposed to achieve automatic center location of non-eye *** center of a non-eye typhoon is near the geometric center of the cloud system and has higher *** each infrared satellite cloud image,the locating procedures are as follows:a) noises filtering,b) main cloud systems segmenting,c) center locating and d) multispectral image *** algorithms are based on operations of mathematical morphology,and designed in IBM SP2 massively parallel *** experiment results show that the algorithm locates the centers of most non-eye typhoons successfully and achieves faster,more precise and non-human interactive non-eye typhoon center positioning.

关键词： Satellite cloud image Non-eye typhoon locating parallel algorithm Mathematical morphology

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel algorithms for solvent accessible surface area of proteins

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2002年第6期13卷 544-555页

作者： Futamura, N Aluru, S Ranjan, D Hariharan, B Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA Iowa State Univ Laurence H Baker Ctr Bioinformat & Biol Stat Ames IA 50011 USA New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA

We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules. The ASA is computed by finding the exposed surface areas of the spheres obtained by increasing the van der Waals radii of the atoms with the van der Waals radius of the solvent. Using domain specific knowledge, we show that the number of sphere intersections is only O(n), where n is the number of atoms in the protein molecule. For computing sphere intersections, we present hash-based algorithms that run in O(n) expected sequential time and O(n/p) expected parallel time and sort-based algorithms that run in worst-case O(n log n) sequential time and O(n log n/p) parallel time. These are significant improvements over previously known algorithms which take O(n(2)) time sequentially and O(n(2)/p) time in parallel. We present a Monte Carlo algorithm for computing the solvent accessible surface area. The basic idea is to generate points uniformly at random on the surface of spheres obtained by increasing the van der Waals radii of the atoms with the van der Waals radius of the solvent molecule and to test the points for accessibility. We also provide error bounds as a function of the sample size. Experimental verification of the algorithms is carried out using an IBM SP-2.

关键词： computational biology accessible surface area protein folding parallel algorithm Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

Some Massively parallel algorithms from Nature

引用

Wuhan University Journal of Natural Sciences 2002年第1期7卷 37-46页

作者： Li Yan, Kang Li-shan, Chen Yu-ping, Liu Pu, Cao Hong-qing, Pan Zheng-jun The State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, Hubei, China Wuhan University The State Key Laboratory of Software Engineering Wuhan Hubei China (GRID:grid.49470.3e) (ISNI:***)

We introduced the work on parallel problem solvers from physics and biology being developed by the research team at the State Key Laboratory of Software Engineering, Wuhan University. Results on parallel solvers include the following areas: Evolutionary algorithms based on imitating the evolution processes of nature for parallel problem solving, especially for parallel optimization and model-building; Asynchronous parallel algorithms based on domain decomposition which are inspired by physical analogies such as elastic relaxation process and annealing process, for scientific computations, especially for solving nonlinear mathematical physics problems. All these algorithms have the following common characteristics: inherent parallelism, self-adaptation and self-organization, because the basic ideas of these solvers are from imitating the natural evolutionary processes.

关键词： evolutionary computation parallel algorithm imitating nature domain decomposition knowledge discovery in databases

来源：评论

学校读者我要写书评

暂无评论

Comments on parallel algorithms for the knapsack problem

引用

parallel COMPUTING 2002年第10期28卷 1501-1505页

作者： Sanches, CAA Soma, NY Yanasse, HH Inst Tecnol Aeronaut CTA ITA IEC BR-12228900 Sao Jose Dos Campos SP Brazil Inst Nacl Pesquisas Espaciais LAC BR-12227010 Sao Jose Dos Campos SP Brazil

Chang et al. [parallel Comput. (1994) 233) introduced a parallel algorithm based on a shared memory SIMD architecture for the generation phase of the classic Horowitz and Sahni [J. ACM 21(2) (1974) 277] two-list serial algorithm for the knapsack problem. They claimed that their parallel generation phase could be accomplished in time O((n/8)(2)) and in space O(2(n/4)) with O(2(n/8)) processors. We prove that their results are not correct, i.e., that the suggested scheme time and space complexity should be bounded, instead, by O(n2(n/2)) and O(2(n/2)), respectively. These results also invalidate the performance analysis of the more recent Lou and Chang [parallel Comput. (1997) 1985] algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： knapsack problem parallel algorithm shared memory multiprocessor SIMD machine

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel algorithms for distance maps of 2-D binary images using an optical bus

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS 2002年第2期32卷 228-236页

作者： Pan, Y Li, YM Li, J Li, KQ Zheng, SQ Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Hosei Univ Fac Comp & Informat Sci Tokyo 1848584 Japan Univ Tsukuba Inst Informat Sci & Elect Tsukuba Ibaraki 3058573 Japan SUNY Albany Dept Math & Comp Sci New Paltz NY 12561 USA Univ Texas Dept Comp Sci Richardson TX 75083 USA

Computing a distance map (distance transform) is an operation that converts a two-dimensional (2-D) image consisting of black and white pixels to an image where each pixel has a value or a pair of coordinates that represents the distance to or location of the nearest black pixel. It is a basic operation in image processing and computer vision fields, and is used for expanding, shrinking, thinning, segmentation, clustering, computing shape, object reconstruction, etc. This paper examines the possibility of implementing, the problem of finding a distance map for an image efficiently using an optical bus. The computational model considered is the linear array with a reconfigurable pipelined bus system (LARPBS), which has been introduced recently based on current electronic and optical technologies. It is shown that the problem for an n x n, image can be implemented in O(log n log log n) bus cycles deterministically or in O(log n) bus cycles with high probability on an LARPBS with n(2) processors. By high probability, we mean a probability of greater than or equal to(1 - n(-alpha)) for any constant a greater than or equal to 1. We also show that the problem can be solved in O (log log n) bus cycles deterministically or in O(1) bus cycles with high probability on an LARPBS with n(3) processors. Scalability of the algorithms is also discussed briefly. The same problem can be solved using an LARPBS of P < n processors in O((n(2)/P) log n log log n) time deterministically or in O((n(2)/P) log n) time with high probability for any practical machine size of P. For processor arrays with practical sizes, a bus cycle is roughly the time of an arithmetic operation. Hence, the algorithm compares favorably to the best known parallel algorithms for the same problem in the literature.

关键词： distance map Euclidean distance transform (ETD) image analysis parallel algorithm reconfigurable optical bus time complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：