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

Architecture independent parallel algorithm design: theory vs practice

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2002年第5期18卷 573-593页

作者： Gerbessiotis, AV New Jersey Inst Technol Dept Comp & Informat Sci Newark NJ 07102 USA

We propose architecture independent parallel algorithm design as a framework for writing parallel code that is scalable, portable and reusable. Towards this end we study the performance of some dense matrix computations such as matrix multiplication, LU decomposition and matrix inversion. Although optimized algorithms for these problems have been extensively examined before, a systematic study of an architecture independent design and analysis of parallel algorithms and their performance (including matrix computations) has not been undertaken. Even though more refined algorithms and implementations (sequential or parallel) for the stated problems exist, the complexity and performance of the introduced algorithms is sufficient to raise the issues that are important in architecture independent parallel algorithm design. Two established distributions of an input matrix among the processors of a parallel machine are examined and the particular theoretical and practical merits of each one are also discussed. The algorithms we propose have been implemented and tested on a variety of parallel systems that include the SGI Power Challenge, the IBM SP2 and the Cray T3D. Our experimental results support our claims of efficiency, portability and reusability of the presented algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： architecture independent parallel algorithms parallel algorithm design parallel performance prediction dense matrix algorithms experimental parallel algorithmics

来源：评论

学校读者我要写书评

暂无评论

SOME COMBINATORIAL ASPECTS OF parallel algorithm design FOR MATRIX MULTIPLICATION

引用

IEEE TRANSACTIONS ON COMPUTERS 1992年第3期41卷 355-361页

作者： TSAY, JC SY, Y IND TECHNOL RES INST COMP & COMMUN RES LABSADV TECHNOL CTRHSINCHU 31015TAIWAN

In this paper, some combinatorial characteristics of matrix multiplication on regular two-dimensional arrays are studied. From the studies, we are able to design many efficient varieties of the cylindrical array and the two-layered mesh array for matrix multiplication. To design a cylindrical array for matrix multiplication, a systematic design procedure is proposed. In this design procedure, Latin square (a special type of matrix) plays an important role. To design a two-layered mesh array, we find that there is a transformation procedure to transform a cylindrical array to a two-layered mesh array.

关键词： CYLINDRICAL ARRAY LATIN SQUARE MATRIX MULTIPLICATION parallel algorithm design SYSTOLIC ARRAY 2-LAYERED MESH ARRAY

来源：评论

学校读者我要写书评

暂无评论

Emulations between QSM, BSP and LogP: a framework for general-purpose parallel algorithm design

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2003年第12期63卷 1175-1192页

作者： Ramachandran, V Grayson, B Dahlin, M Univ Texas Dept Comp Sci Austin TX 78712 USA Motorola Somerset Design Ctr Austin TX 78729 USA

We present work-preserving emulations with small slowdown between LogP and two other parallel models: BSP and QSM. In conjunction with earlier work-preserving emulations between QSM and BSP, these results establish a close correspondence between these three general-purpose parallel models. Our results also correct and improve on results reported earlier on emulations between BSP and LogP. In particular we shed new light on the relative power of stalling and non-stalling LogP models. The QSM is a shared-memory model with only two parameters-p, the number of processors, and g, a bandwidth parameter. The simplicity of the QSM parameters makes QSM a convenient model for parallel algorithm design, and simple work-preserving emulations of QSM on BSP and QSM on LogP show that algorithms designed for the QSM will also map quite well to these other models. The simplicity and generality of QSM present a strong case for the use of QSM as the model of choice for parallel algorithm design. We present QSM algorithms for three basic problems-prefix sums, sample sort and list ranking. We show that these algorithms are optimal in terms of both the total work performed and the number of 'phases' for input sizes of practical interest. For prefix sums, we present a matching lower bound that shows our algorithm to be optimal over the complete range of these parameters. We then examine the predicted and simulated performance of these algorithms. These results suggest that QSM analysis will predict algorithm performance quite accurately for problem sizes that arise in practice. (C) 2003 Elsevier Inc. All rights reserved.

关键词： emulations general-purpose parallel models BSP LogP QSM parallel algorithm design prefix sums sample sort list ranking

来源：评论

学校读者我要写书评

暂无评论

FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity

引用

BRIEFINGS IN BIOINFORMATICS 2025年第1期26卷 bbaf061页

作者： Wei, Yanming Zhou, Tong Zhai, Yixiao Yu, Liang Zou, Quan Xidian Univ Sch Comp Sci & Technol 266Xinglong Sect Xifeng RdChangan Zone Xian 710126 Peoples R China Univ Elect Sci & Technol China Inst Digital Hlth Yangtze Delta Reg Inst Quzhou 1Chengdian RdKecheng Zone Quzhou 324003 Peoples R China Univ Elect Sci & Technol China Inst Fundamental & Frontier Sci 2006Xiyuan AvePidu Zone Chengdu 610054 Peoples R China

Pairwise sequence alignment (PSA) serves as the cornerstone in computational bioinformatics, facilitating multiple sequence alignment and phylogenetic analysis. This paper introduces the FORAlign algorithm, leveraging the Four Russians algorithm with identical upper-bound time and space complexity as the Hirschberg divide-and-conquer PSA algorithm, aimed at accelerating Hirschberg PSA algorithm in parallel. Particularly notable is its capability to achieve up to 16.79 times speedup when aligning sequences with low sequence similarity, compared to the conventional Needleman-Wunsch PSA method using non-heuristic methods. Empirical evaluations underscore FORAlign's superiority over existing wavefront alignment (WFA) series software, especially in scenarios characterized by low sequence similarity during PSA tasks. Our method is capable of directly aligning monkeypox sequences with other sequences using non-heuristic methods. The algorithm was implemented within the FORAlign library, providing functionality for PSA and foundational support for multiple sequence alignment and phylogenetic trees. The FORAlign library is freely available at https://***/malabz/FORAlign.

关键词： sequence alignment four Russians speedup dynamic programming parallel algorithm design

来源：评论

学校读者我要写书评

暂无评论

The formal derivation of parallel triangular system solvers using a coordination-based design method

引用

parallel COMPUTING 1998年第7期24卷 1023-1046页

作者： Chaudron, MRV van Duin, ACN Leiden Univ Dept Comp Sci NL-2300 RA Leiden Netherlands

We present an application of a method for the design of parallel programs that addresses the functional aspects and the operational aspects in separate phases. In the first phase, the functional aspects are specified using the Gamma model, This model encourages a specification with a minimum of control and thereby provides insight into the potential parallelism inherent in the problem. Secondly, the operational aspects are specified separately by means of a coordination language. A formal theory of refinement of coordination supports the derivation of the operational aspects by a process of successive stepwise refinement. This separation facilitates formal reasoning and caters for the design of architecture-independent systems. We use this method to design algorithms for solving triangular systems of linear equations;i.e., finding the solution vector 'x' from 'Lx = b' where 'L' is a triangular NXN matrix. This problem arises in many application areas and many algorithms for solving it have been proposed. Among these algorithms are the parallel and sequential variants of the vector-update algorithm (or column-sweep solution method) and the inner-product algorithm (or row-sweep solution method). We formally derive these algorithms as different coordination strategies for the same Gamma program. We show how these strategies can be classified in terms of the BLAS hierarchy. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： parallel algorithm design stepwise refinement coordination formal methods taxonomy of triangular system solvers

来源：评论

学校读者我要写书评

暂无评论

Impact of platform heterogeneity on the design of parallel algorithms for morphological processing of high-dimensional image data

引用

JOURNAL OF SUPERCOMPUTING 2007年第1期40卷 81-107页

作者： Plaza, Antonio Plaza, Javier Valencia, David Univ Extremadura Polytech Inst Dept Comp Sci E-10071 Caceres Spain

The main objective of this paper is to describe a realistic framework to understand parallel performance of high-dimensional image processing algorithms in the context of heterogeneous networks of workstations (NOWs). As a case study, this paper explores techniques for mapping hyperspectral image analysis techniques onto fully heterogeneous NOWs. Hyperspectral imaging is a new technique in remote sensing that has gained tremendous popularity in many research areas, including satellite imaging and aerial reconnaissance. The automation of techniques able to transform massive amounts of hyperspectral data into scientific understanding in valid response times is critical for space-based Earth science and planetary exploration. Using an evaluation strategy which is based on comparing the efficiency achieved by an heterogeneous algorithm on a fully heterogeneous NOW with that evidenced by its homogeneous version on a homogeneous NOW with the same aggregate performance as the heterogeneous one, we develop a detailed analysis of parallel algorithms that integrate the spatial and spectral information in the image data through mathematical morphology concepts. For comparative purposes, performance data for the tested algorithms on Thunderhead (a large-scale Beowulf cluster at NASA's Goddard Space Flight Center) are also provided. Our detailed investigation of the parallel properties of the proposed morphological algorithms provides several intriguing findings that may help image analysts in selection of parallel techniques and strategies for specific applications.

关键词： heterogeneous computing parallel algorithm design cluster computing performance analysis hyperspectral imaging mathematical morphology

来源：评论

学校读者我要写书评

暂无评论

An experimental comparison of parallel algorithms for hyperspectral analysis using heterogeneous and homogeneous networks of workstations

引用

parallel COMPUTING 2008年第2期34卷 92-114页

作者： Plaza, Antonio Valencia, David Plaza, Javier Univ Extremadura Dept Comp Sci Comp Architecture & Technol Sect E-10071 Caceres Spain

Imaging spectroscopy, also known as hyperspectral imaging, is a new technique that has gained tremendous popularity in many research areas, including satellite imaging and aerial reconnaissance. In particular, NASA is continuously gathering high-dimensional image data from the surface of the earth with hyperspectral sensors such as the Jet Propulsion Laboratory's Airborne Visible-Infrared Imaging Spectrometer (AVIRIS) or the Hyperion hyperspectral imager aboard NASA's Earth Observing-1 (EO-I) spacecraft. Despite the massive volume of scientific data commonly involved in hyperspectral imaging applications, very few parallel strategies for hyperspectral analysis are currently available, and most of them have been designed in the context of homogeneous computing platforms. However, heterogeneous networks of workstations represent a very promising cost-effective solution that is expected to play a major role in the design of high-performance computing platforms for many on-going and planned remote sensing missions. Our main goal in this paper is to understand parallel performance of hyperspectral imaging algorithms comprising the standard hyperspectral data Processing chain (which includes pre-processing, selection of pure spectral components and linear spectral unmixing) in the context of fully heterogeneous computing platforms. For that purpose, we develop an exhaustive quantitative and comparative analysis of several available and new parallel hyperspectral imaging algorithms by comparing their efficiency on both a fully heterogeneous network of workstations and a massively parallel homogeneous cluster at NASA's Goddard Space Flight Center in Maryland. (c) 2008 Elsevier B.V. All rights reserved.

关键词： parallel algorithm design heterogeneous computing hyperspectral image analysis hyperspectral data processing chain load balance

来源：评论

学校读者我要写书评

暂无评论

Guest editor's introduction

引用

algorithmICA 2006年第3期45卷 263-267页

作者： Dehne, Frank Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

No abstract available

关键词： parallel algorithm Data Cube Processor Cluster parallel algorithm design Superior Scalability

来源：评论

学校读者我要写书评

暂无评论

On-the-Fly Runtime Adaptation for Efficient Execution of parallel Multi-algorithm Circuit Simulation

On-the-Fly Runtime Adaptation for Efficient Execution of Par...

引用

IEEE and ACM International Conference on Computer-Aided design

作者： Ye, Xiaoji Li, Peng Texas A&M Univ Dept ECE College Stn TX 77843 USA

ISBN: (纸本)9781424481927

The past several years have witnessed a significant interest in developing parallel CAD algorithms and implementations that exploit various multi-core and distributed computing hardware. In addition to fundamental parallel algorithm design, the ability in modeling parallel performance and facilitating runtime optimization is indispensable for achieving good efficiency for complex parallel CAD applications. Under the context of a recently developed hierarchical multi-algorithm parallel circuit simulation (HMAPS) framework, we demonstrate a runtime optimization approach that allows for automatic on-the-fly reconfiguration of the parallel simulation code. We show how the runtime information, collected as parallel simulation proceeds, can be combined with static parallel performance models to enable dynamic adaptation of parallel simulation execution for improved performance and robustness. Our results have shown that the proposed approach not only finds the near-optimal code configuration over a large configuration space, it also outperforms multi-algorithm circuit simulation assisted only with static pre-runtime parallel performance modeling.

关键词： automatic on-the-fly reconfiguration circuit CAD circuit simulation complex parallel CAD applications distributed computing hardware dynamic adaptation hierarchical multi-algorithm parallel circuit simulation logic CAD multialgorithm circuit simulation multicore computing hardware near-optimal code configuration on-the-fly runtime adaptation parallel CAD algorithms parallel algorithm design parallel algorithms parallel simulation code parallel simulation execution runtime information runtime optimization static parallel performance models static pre-runtime parallel performance modeling

来源：评论

学校读者我要写书评

暂无评论

GeoComputation in the grid computing age

引用

6th International Symposium on Web and Wireless Geographical Information Systems

作者： Guan, Qingfeng Zhang, Tong Clarke, Keith C. Univ Calif Santa Barbara Dept Geog Santa Barbara CA 93106 USA San Diego State Univ Dept Geog San Diego CA 92182 USA

ISBN: (纸本)9783540494669

This paper first discusses some challenges that current GeoComputation faces in terms of usability, feasibility, applicability and availability, and the opportunities that will arise when new computing technologies, especially Grid Computing, emerge and prevail. A Grid-based geospatial problem-solving architecture is proposed to provide a solution for building an easy-to-use, widely accessible and high-performance geospatial problem-solving environment that integrates multiple complicated GeoComputational processes at an acceptable cost. A parallel geographic cellular automata model is given as an example to address some distinguishing issues when designing and implementing parallel algorithms for GeoComputation to effectively and efficiently utilize the computational Grid.

关键词： GeoComputation grid computing web portals parallel algorithm design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：