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

7th Euromicro Workshop on parallel and Distributed Processing (PDP 99)

作者： Casado, LG García, I Department of Computer Architecture and Electronics Almería University Spain

ISBN: (纸本)0769500595

Branch and Bound is a standard method for searching an optimal solution in the scope of continuous and discrete Global Optimization. It iteratively creates a search tree where each node represents a problem which is decomposed in several subproblems provided that a feasible solution can be found by solving this set of subproblems. The computational power needed to solved most of the Branch and Bound Global Optimization problems and their high degree of potential parallelism make them suitable candidates to be solved in a multiprocessing environment. With palallel processing in mind Branch and Bound techniques can be considered as irregular and dynamic problems. So, their parallel implementations are not straightforward and require the use of dynamic load balance methods where the workload of a subproblem is a crucial parameter. In this pn per. an efficient parallel approach to the Branch and Bound continuous Global Optimization problem is described. It is based on a centralized asynchronous parallel model and on the prediction of the work load of the set of subproblems containing a feasible solution. The proposed dynamic load balancing model obtains ar? almost perfect work load balance with lon communication overhead.

关键词： parallel algorithm distributed processing branch and bound global optimization interval arithmetic

来源：评论

学校读者我要写书评

暂无评论

Design of fast algorithms for projections through matrix decomposition

Design of fast algorithms for projections through matrix dec...

引用

Conference on parallel and Distributed Methods for Image Processing III

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

ISBN: (纸本)0819433039

Projection is a frequently used process in image processing and visualization. In volume graphics, projection is used to render the essential content of a 3D volume onto a 2D image plane. For Radon transform, projection is used to transform the image space into a parameter space. In this paper, we propose a matrix decomposition method called identity-plus-row decomposition for designing fast algorithms for projections. By applying this method, we solve the data redistributed problem due to the irregular data access patterns present in those applications on SIMD mesh-connected computers, developing fast algorithms for volume rendering and Radon transform an SIMD mesh-connected computers.

关键词： image processing matrix decomposition parallel algorithm mesh connected computers

来源：评论

学校读者我要写书评

暂无评论

parallel VERTEX COLOURING OF INTERVAL GRAPHS

引用

International Journal of Foundations of Computer Science 1999年第1期10卷 19-31页

作者： G. SAJITH SANJEEV SAXENA Computer Science and Engineering Indian Institute of Technology Guwahati 781 001 India Computer Science and Engineering Indian Institute of Technology Kanpur 208 016 India

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC 1 . This is done by showing that 3-colouring a linked list is NC 1 -reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC 1 . For the CRCW PRAM model, an o( log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o( log n) chromatic number and a known interval representation. In particular, when the chromatic number is O(( log n) 1-ε ), 0<ε<1, the algorithm runs in O( log n/ log log n) time. Also, an O( log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω( log n/ log log n) time, on a CRCW PRAM, with a polynomial number of processors.

关键词： parallel algorithm lower bounds graph algorithms CRCW model interval graphs graph coloring

来源：评论

学校读者我要写书评

暂无评论

動態批量平行演算法之探討

引用

Journal of Industrial and Production Engineering 1999年第2期16卷 173-182页

作者： Jr-Jung Lyu[a] Ming-Chang Lee[a] [a]Department Of Industrial Management National Cheng Kung Uniersity China

摘要摘要由於批量之決定影響生產系統之效率甚大，故在MRP架構中一直扮演著很重要的角色。雖然目前已有不少這方面之研究，大部份的最佳批量演算法卻受限於龐大之計算量而較不受實務界重視。隨著平行處理機的性能價格比日漸提昇，如何... 详细信息

摘要摘要由於批量之決定影響生產系統之效率甚大，故在MRP架構中一直扮演著很重要的角色。雖然目前已有不少這方面之研究，大部份的最佳批量演算法卻受限於龐大之計算量而較不受實務界重視。隨著平行處理機的性能價格比日漸提昇，如何運用平行演算法以求解如動態批量這樣計算繁雜的問題便是一値得重視的研究方向。本文提出了二個動態批量平行演算法，在問題大小爲n時，前者複雜度爲O(n{su2})（如果有n個處理器），後者則爲O(n{su3}/p+np{su2})（如果有P個處理器，且P<algorithms is hindered by the huge amount of computer resources required to solve the models, even for a modest problem. Since the powerful parallel computers are becoming cost-effective nowadays, it is necessary to explore paraIlel algorithms that can be used to solve these laborious computational problems. This paper presents two parallel algorithms for solving dynamic lot sizing problem using the cost path concept. Given n is the size of the problem. it is shown that the first proposed parallel algorithm is O(n2) with n processors and the second proposed parallel algorithm iswith p processors (p<parallel algorithms and some future research directions are also provided.

关键词：物料需求規劃平行演算法平行計算之複雜度 MRP parallel algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for high speed SAR processing

Parallel algorithms for high speed SAR processing

引用

Conference on SAR Image Analysis, Modeling, and Techniques

作者： Mallorquí, JJ Barà, M Broquetas, A Wis, M Martínez, A Nogueira, L Moreno, V Univ Politecn Catalunya ES-08034 Barcelona Spain

ISBN: (纸本)0819429562

The mass production of SAR products and its usage on monitoring emergency situations (oil spill detection, floods, etc.) requires high-speed SAR processors. Two different parallel strategies for near rear time SAR processing based on a multiblock version of the Chirp Scaling algorithm (CSA) have been studied. The first one is useful for small companies that would like to reduce computation times with no extra investment. It uses a cluster of heterogeneous UNIX workstations as a parallel computer. The second one is oriented to institutions, which have to process large amounts of data in short times and can afford the cost of large parallel computers. The parallel programming has reduced in both cases the computational times when compared with the sequential versions.

关键词： parallel algorithm SAR processor CSA real time high speed computing

来源：评论

学校读者我要写书评

暂无评论

A note on parallel algorithms for optimal h-v drawings of binary trees

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1998年第3期9卷 145-158页

作者： Metaxas, PT Pantziou, GE Symvonis, A Wellesley Coll Dept Comp Sci Wellesley MA 02181 USA Comp Technol Inst GR-26110 Patras Greece Univ Sydney Basser Dept Comp Sci Sydney NSW 2006 Australia

In this paper we present a method to obtain optimal h-v drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in O(log(2) n) parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings, Our work places the problem of obtaining optimal size h-v drawings in NC, presenting the first algorithm with polylogarithmic time complexity. (C) 1998 Elsevier Science B.V.

关键词： h-v drawing parallel algorithm parallel tree contraction tree layout

来源：评论

学校读者我要写书评

暂无评论

A parallel sort-balance mutual range-join algorithm on hypercube computers

引用

MICROPROCESSORS AND MICROSYSTEMS 1998年第3-4期22卷 209-215页

作者： Wong, R Topor, R Shen, H Griffith Univ Sch Comp & Informat Technol Nathan Qld 4111 Australia

This paper presents an efficient parallel algorithm for computing the mutual range-join of N sets of numbers on shared-nothing hypercube computers. The algorithm iteratively joins each set to the mutual range-join of the preceding sets. Each join is performed on all processors of the hypercube in parallel. The algorithm uses a global sorting method to distribute the elements of the first set evenly across all processors in increasing order, a new data balancing technique to distribute the elements of subsequent sets to match the intermediate set at each processor and to compensate for join skew, and a new efficient local range-join procedure. We analyse the performance of this algorithm and demonstrate that it improves on the previous result for this problem when the join selectivity factor is small and the restriction of SIMD operation is lifted. The method can also be applied to similar problems such as band-join and equi-join. (C) 1998 Elsevier Science B.V.

关键词： relational database query evaluation range-join hypercube parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Design and implementation of a systolic circuit dedicated to dynamic programming algorithm parallel calculation

Design and implementation of a systolic circuit dedicated to...

引用

Conference on Configurable Computing - Technology and Applications

作者： Pissaloux, EE Le Coat, F Bonnin, P Tissot, A Durbin, F Garie, T Univ Rouen PSI La3I F-76821 Mt St Aignan France

ISBN: (纸本)0819429872

This paper proposes a parallel systolic VLSI circuit which can support efficiently the implementation of a dynamic programming algorithm, a part of two aerial image matching procedure. A dynamic programming algorithm allows to estimate the dense field of local luminosity difference (distance) between images in O(N) steps (N x N being image size). The calculated field is a sampling of the projective transform which links two images. The transform parameter final values are obtained through pyramidal calculations (at different image resolutions) and least square approximations. Simulation temporal and quality results on Spare 20 (in C) and CM-5 (in C*) are presented.

关键词： optical flow image matching dynamic programming parallel algorithm movement estimation robotics computer vision

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for the simulation of temperature distribution in metal cutting

引用

ENGINEERING ANALYSIS WITH BOUNDARY ELEMENTS 1996年第3期18卷 245-250页

作者： Lai, CH School of Computing and Mathematical Sciences University of Greenwich Wellington Street Woolwich London UK SE18 6PF

Temperature distributions involved in some metal cutting or surface milling processes may be obtained by solving a nonlinear inverse problem. A simplified metal cutting process is considered in this paper. A problem partitioning concept is used to partition the original problem. We propose a distributed algorithm in relation to the choice of numerical schemes in order to simulate the temperature distribution of such problems. Numerical results are provided for three different materials. Efficiency analysis is provided to examine the algorithm when it is being run in a distributed computing environment. Possibilities are discussed of encapsulating the algorithm in a computer virtual design environment for metal cutting and extending the algorithm in a real time simulation system. (C) 1997 Elsevier Science Ltd.

关键词： parallel algorithm metal cutting boundary element methods

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for solving special tridiagonal systems on ring networks

引用

COMPUTING 1996年第4期56卷 385-395页

作者： Chung, KL Yan, WM Wu, JG NATL TAIWAN NORMAL UNIV DEPT INFORMAT & COMP EDUCTAIPEI 10610TAIWAN NATL TAIWAN UNIV DEPT COMP SCI & INFORMAT ENGNTAIPEI 10764TAIWAN

The solution of special linear, circulant-tridiagonal systems is considered. In this paper, a fast parallel algorithm for solving the special tridiagonal systems, which includes the skew-symmetric and tridiagonal-Toeplitz systems, is presented. Employing the diagonally dominant property, our parallel solver does need only local communications between adjacent processors on a ring network. An error analysis is also given. On the nCUBE/2E multiprocessors, some experimental results demonstrate the good performance of our stable parallel solver.

关键词： nCUBE/2E multiprocessors matrix perturbation parallel algorithm performance ring network tridiagonal Toeplitz linear systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：