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

Polynomially fast parallel algorithms for some P-complete problems

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2001年第5期E84A卷 1244-1255页

作者： Castanho, CD Chen, W Wada, K Fujiwara, A Nagoya Inst Technol Dept Elect & Comp Engn Nagoya Aichi 4668555 Japan Kyushu Inst Technol Dept Comp Sci & Elect Iizuka Fukuoka 8208502 Japan

P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = U(t(n)(epsilon)) (epsilon < 1) using P(n) processors such that T(n) x P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an a,algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 < k < n(epsilon /2) (0 less than or equal to epsilon < 1) our algorithm runs in O(n log n/p) time using p processors, where 1 less than or equal to p less than or equal to n1-epsilon /2, and it is cost optimal, Next, we consider the envelope layers problem of a set S Of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 I k < n9 (O I E < l), Ne propose an algorithm for computing the envelope layers of S in O(n alpha (n) log(3) n/p) time using p processors, where 1 less than or equal to p less than or equal to n1-epsilon /2 and alpha (n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.

关键词： parallel algorithm P-complete problems convex layers problem envelope layers problem

来源：评论

学校读者我要写书评

暂无评论

parallel Rosenbrock methods for chemical systems

引用

COMPUTERS & CHEMISTRY 2001年第1期25卷 101-107页

作者： Voss, DA Khaliq, AQM Western Illinois Univ Dept Math Macomb IL 61455 USA

parallel Rosenbrock methods are developed for systems with stiff chemical reactions. Unlike classical Runge-Kutta methods, these linearly implicit schemes avoid the necessity to iterate at each time step. parallelism across the method allows for the solution of the linear algebraic systems in essentially Backward Euler-like solves on concurrent processors. In addition to possessing excellent stability properties, these methods are computationally efficient while preserving positivity of the solutions. Numerical results confirm these characteristics when applied to problems involving stiff chemistry, and enzyme kinetics. (C) 2001 Elsevier Science Ltd. All rights reserved.

关键词： Rosenbrock methods L-stable positivity adaptivity parallel algorithm method of lines

来源：评论

学校读者我要写书评

暂无评论

parallel implementation of a class of adaptive signal processing applications

引用

algorithmICA 2001年第4期30卷 645-684页

作者： Lee, M Liu, W Prasanna, VK Sun Microsyst Inc Syst Prod Grp Palo Alto CA 94303 USA Calif State Univ Los Angeles Dept Elect & Comp Engn Los Angeles CA 90032 USA Univ So Calif Dept EE Syst Los Angeles CA 90089 USA

Recently, High Performance Computing (HPC) platforms have bean employed to realize many computationally demanding applications in signal and image processing. These applications require real-time performance constraints to be met. These constraints include latency as well as throughput. In order to meet these performance requirements, efficient parallel algorithms are needed. These algorithms must be engineered to exploit the computational characteristics of such applications. In this paper we present a methodology for mapping a class of adaptive signal processing applications onto KPC platforms such that the throughput performance is optimized. We first define a new task model using the salient computational characteristics of a class of adaptive signal processing applications. Based on this task model, we propose a new execution model. In the earlier linear pipelined execution model, the task mapping choices were restricted. The new model permits flexible task mapping choices, leading to improved throughput performance compared with the previous model. Using the new model, a three-step task mapping methodology is developed. It consists of (1) a data remapping step, (2) a coarse resource allocation step, and (3) a fine performance tuning step. The methodology is demonstrated by designing parallel algorithms for modern radar and sonar signal processing applications. These are implemented on IBM SP2 and Cray T3E, state-of-the-art HPC platforms, to show the effectiveness of our approach. Experimental results show significant performance improvement over those obtained by previous approaches. Our code is written using C and the Message Passing Interface (MPI). Thus, it is portable across various HPC platforms.

关键词： adaptive signal processing parallel algorithm high performance computing latency throughput task model execution model task mapping data remapping

来源：评论

学校读者我要写书评

暂无评论

Improved parallel implementation of the two-dimensional Ising model

引用

COMPUTER PHYSICS COMMUNICATIONS 2001年第3期141卷 313-321页

作者： Knoll, P Mirzaei, S Univ Vienna Dept Expt Phys A-1010 Vienna Austria

Some simulations we would like to perform in computational physics require so much computation time that it is not possible to finish them in reasonable length of time on any nowadays available computer. If it is possible to decompose a compute intensive problem into smaller independent tasks one possibility is to shorten the calculation time is to apply a parallel algorithm. Java, a platform independent programming language changed the way of software design by using Jini and JavaSpaces. new technologies that have been introduced recently. By applying JavaSpaces, a virtual, network accessible space can be used to store Java objects but also for effective parallel processing. In this paper, we report a novel, parallel implementation of the two-dimensional Ising model using the JavaSpaces technology. Our new approach was implemented on standard computer equipment and results in significant improvement of computation time. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： parallel algorithm Ising model Jini JavaSpaces

来源：评论

学校读者我要写书评

暂无评论

parallel Ant Colonies for the quadratic assignment problem

引用

FUTURE GENERATION COMPUTER SYSTEMS 2001年第4期17卷 441-449页

作者： Talbi, EG Roux, O Fonlupt, C Robillard, D Univ Lille 1 LIFL CNRS URA 369 F-59655 Villeneuve Dascq France Univ Littoral LIL Calais France

Ant Colonies optimization take inspiration from the behavior of real ant colonies to solve optimization problems. This paper presents a parallel model for ant colonies to solve the quadratic assignment problem (QAP). The cooperation between simulated ants is provided by a pheromone matrix that plays the role of a global memory. The exploration of the search space is guided by the evolution of pheromones levels, while exploitation has been boosted by a tabu local search heuristic. Special care has also been taken in the design of a diversification phase, based on a frequency matrix. We give results that have been obtained on benchmarks from the QAP library. We show that they compare favorably with other algorithms dedicated for the QAP. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： metaheuristics Ant Colonies tabu search parallel algorithm quadratic assignment problem combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Multicanonical parallel simulations of proteins with continuous potentials

引用

JOURNAL OF COMPUTATIONAL CHEMISTRY 2001年第12期22卷 1287-1296页

作者： Hayryan, S Hu, CK Hu, SY Shang, RJ Acad Sinica Inst Phys Taipei 11529 Taiwan Natl Sun Yat Sen Univ Dept Informat Management Kaohsiung 804 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 106 Taiwan

The determination of the three-dimensional (3D) structure of a protein or peptide is a very important research problem in biological and medical sciences. Anfinsen's experiments (Science 1973, 181, 223) on renaturation of denatured proteins have shown that the native 3D structure of a (small) protein at low (room) temperatures is uniquely determined by its amino acid sequence, which suggests that it might be possible to determine the 3D structure of a protein from its amino acid sequence by pure computations. As a step toward that goal, in this article we present a simple approach for parallelization of multicanonical Monte Carlo simulations of proteins with continuous potentials. Our method is based on the parallel calculation of the protein energy function. The algorithm is tested by simulated annealing and multicanonical simulations of two small peptides, and known results are reproduced accurately. An acceptable degree of parallelization can be achieved in the simulation of Protein L using up to 30 PCs. (C) 2001 John Wiley & Sons, Inc.

关键词： multicanonical Monte Carlo energy parallelization method parallel algorithm Met enkephalin protein structure

来源：评论

学校读者我要写书评

暂无评论

Space-time tradeoffs for parallel 3D reconstruction algorithms for virus-structure determination

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2001年第12期13卷 1083-1106页

作者： Marinescu, DC Ji, YC Lynch, RE Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

The 3D electron-density determination of viruses, from experimental data provided by electron microscopy, is a data-intensive computation that requires the use of clusters of PCs or parallel computers. In this paper we report on three parallel algorithms used for 3D reconstruction of asymmetric objects from their 2D projections. We discuss their computational, communication, I/O, and space requirements and present some performance data. The algorithms are general and can be used for 3D reconstruction of asymmetric objects for applications other than structural biology. Copyright (C) 2001 John Wiley & Sons, Ltd.

关键词： 3D reconstruction electron microscopy parallel algorithm speedup

来源：评论

学校读者我要写书评

暂无评论

Local and parallel finite element algorithms based on two-grid discretizations for nonlinear problems

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2001年第4期14卷 293-327页

作者： Xu, JC Zhou, AH Penn State Univ Ctr Computat Math & Applicat University Pk PA 16802 USA Penn State Univ Dept Math University Pk PA 16802 USA Chinese Acad Sci Inst Computat Math & Sci Engn Comp Acad Math & Syst Sci Beijing 100080 Peoples R China

In this paper, some local and parallel discretizations and adaptive finite element algorithms are proposed and analyzed for nonlinear elliptic boundary value problems in both two and three dimensions. The main technique is to use a standard finite element discretization on a coarse grid to approximate low frequencies and then to apply some linearized discretization on a fine grid to correct the resulted residual (which contains mostly high frequencies) by some local/parallel procedures. The theoretical tools for analyzing these methods are some local a priori and a posteriori error estimates for finite element solutions on general shape-regular grids that are also obtained in this paper.

关键词： adaptive finite elements local a priori and a posteriori error estimates nonlinear parallel algorithm two-grid method

来源：评论

学校读者我要写书评

暂无评论

Entropy thresholding and its parallel algorithm on the reconfigurable array of processors with wider bus networks

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 1999年第9期8卷 1229-1242页

作者： Lee, SS Horng, SJ Tsai, HR Fu Shin Inst Technol & Commerce Dept Elect Engn Ilan Taiwan Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei Taiwan Overseas Chinese Coll Commerce Dept Informat Management Taichung Taiwan

Thresholding is the most commonly used technique in image segmentation. In this paper, we first propose an efficient sequential algorithm to improve the relative entropy-based thresholding technique, This algorithm combines the concepts of the relative entropy with that of the local entropy and also includes the quadtree hierarchical structure in it. Second, we derive a constant time parallel algorithm to solve this problem on the reconfigurable array of processors with wider bus networks (RAPWBN), The system bus bandwidth determines the capacity of data communication between processors, According to the results as shown in [15], [17], we know that the silicon area used by the switching control mechanism is far less than that used by the processor. Instead of increasing the number of processors, we extend the number of buses to increase the power of a parallel processing system, Such a strategy of utilizing the reconfigurable array of processors with wider bus networks not only has the advantage of saving silicon area but also increases the system power enormously. So, we use the RAPWBN to solve the entropy-based thresholding problem.

关键词： Hilbert's space-filling curve image segmentation local entropy parallel algorithm quadtree reconfigurable array of processors with wider bus networks relative entropy thresholding

来源：评论

学校读者我要写书评

暂无评论

parallel computing in interval mapping of quantitative trait loci

引用

JOURNAL OF HEREDITY 2001年第5期92卷 449-451页

作者： Carlborg, Ö Andersson-Eklund, L Andersson, L Swedish Univ Agr Sci Dept Anim Breeding & Genet Biomed Ctr S-75124 Uppsala Sweden

Linear regression analysis is considered the least computationally demanding method for mapping quantitative trait loci (QTL), However, simultaneous search for multiple QTL, the use of permutations to obtain empirical significance thresholds, and larger experimental studies significantly increase the computational demand, This report describes an easily implemented parallel algorithm, which significantly reduces the computing time in both QTL mapping and permutation testing. In the example provided, the analysis time was decreased to less than 15% of a single processor system by the use of 18 processors. We indicate how the efficiency of the analysis could be improved by distributing the computations more evenly to the processors and how other ways of distributing the data facilitate the use of more processors. The use of parallel computing in QTL mapping makes it possible to routinely use permutations to obtain empirical significance thresholds for multiple traits and multiple QTL models. It could also be of use to improve the computational efficiency of the more computationally demanding QTL analysis methods.

关键词： .QTL mapping interval mapping outbred obtain QTL analysis permutations processors multiple QTL parallel algorithm parallel computing cance Thresholds computational demand analysis time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：