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

Multi-mesh of trees with its parallel algorithms

JOURNAL OF SYSTEMS ARCHITECTURE 2004年第4期50卷 193-206页

作者： Jana, PK Indian Sch Mines Dept Comp Sci & Engn Dhanbad 826004 Bihar India

In recent years the multi-mesh network [Proceedings of the Ninth International Parallel Processing Symposium, Santa Barbara. CA, April 25-28, 1995, 17;IEEE Trans. on Comput. 68 (5) (1999) 536] has created a lot of interests among the researchers for its efficient topological properties. Several parallel algorithms for various trivial and nontrivial problems have been mapped on this network. However. because of its O(n) diameter, a large class of algorithms that involves frequent data broadcast in a row or in a column or between the diametrically opposite processors, requires O(n) time on an n x n multi-mesh. In search of faster algorithms, we introduce, in this paper, a new network topology. called multi-mesh of trees. This network is built around the multi-mesh network and the mesh of trees. As a result it can perform as efficiently as a multi-mesh network and also as efficiently as a mesh of trees. Several topological properties. including number of links, diameter, bisection width and decomposition are discussed. We present the parallel algorithms for finding sum of n(4) elements and the n(2)-point Lagrange interpolation both in O(log n)(1) time. The solution of n(2)-degree polynomial equation, n(2)-point DFT computation and sorting of n elements are all shown to run in O(log n) time too. The communication algorithms one-to-all, row broadcast and column broadcast are also described in O(log n) time. This can be compared with O(n) time algorithms on multi-mesh network for all these problems. (C) 2003 Elsevier B.V. All rights reserved.

关键词： mesh of trees multi-mesh bisection width decomposition communication algorithms Lagrange's interpolation Durand-Kerner method Ehrlich method matrix multiplication DFT computation sorting

来源：评论

学校读者我要写书评

暂无评论

Optimal routing algorithm on hexagonal networks based on a new addressing scheme

Optimal routing algorithm on hexagonal networks based on a n...

引用

International Conference on Parallel and Distributed Processing Techniques and Applications

作者： Decayeux, C Semé, D Univ Picardie CURI Lab Rech Informat Amiens F-80000 Amiens France

ISBN: (纸本)1892512459

In this paper, we propose a new addressing scheme for hexagonal interconnection networks. This is the first addressing system, using two coordinates, assuming both the unicity of the coordinates for each node and a distance formula between two nodes. Then, we present an optimal routing algorithm based on the distance formula in order to use shortest paths from the source to the destination node.

关键词： parallel Architectures interconnection networks hexagonal mesh routing communication algorithms

来源：评论

学校读者我要写书评

暂无评论

communication in the two-way listen-in vertex-disjoint paths mode

引用

THEORETICAL COMPUTER SCIENCE 2001年第1期264卷 65-90页

作者： Böckenhauer, HJ Rhein Westfal TH Aachen Lehrstuhl Informat 1 D-52056 Aachen Germany

A new communication mode for the dissemination of information among processors of interconnection networks via vertex-disjoint paths is introduced and investigated. In this communication mode, in one communication step two processors communicating via a path P send their pieces of information to all other processors on this path, too. The complexity of a communication algorithm is measured by the number of communication steps (rounds). In this paper we will design optimal broadcast, accumulation, and gossip algorithms for various classes of networks including paths, cycles, and hypercube-like networks. The main results are optimal accumulation and gossip algorithms for the two-dimensional grid. The technique used for the design of these algorithms is based on finding Hamiltonian paths in the grid with certain endpoints or center points. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： communication algorithms parallel computations

来源：评论

学校读者我要写书评

暂无评论

communication algorithms in k-ary n-cube interconnection networks

引用

INFORMATION PROCESSING LETTERS 1997年第1期61卷 43-48页

作者： Ashir, Y Stewart, IA Ahmed, A UNIV LEICESTER DEPT MATH & COMP SCILEICESTER LE1 7RHLEICSENGLAND UNIV BAHRAIN DEPT COMP SCIMANAMABAHRAIN

We consider several communication algorithms in the k-ary n-cube interconnection network;in particular, we develop and analyse routing, multi-node broadcasting, single-node scattering and total exchange algorithms, Al... 详细信息

关键词： interconnection networks parallel processing k-ary n-cubes communication algorithms

来源：评论

学校读者我要写书评

暂无评论

Attitude commands avoiding bright objects and maintaining communication with ground station

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 1999年第6期22卷 759-767页

作者： Hablani, HB Boeing Co Reusable Space Syst Flight Control Syst Avion Engn Downey CA 90242 USA

The objective of the paper is to develop attitude commands for slewing a vehicle such that the angle of its boresight with the centroid of a bright object is not less than a minimum angle and its antennae do not lose communication with the ground. These commands involve three angles: the required pitch/yaw slew angle, the bright object's exclusion angle normal to the slew angle, and a roll angle for maintaining communication. The location of the bright object's centroid is formulated in terms of an angle normal to the ideal slew plane. If the ideal, minimum-angle slew path enters the forbidden perimeter around the bright object, two alternative exclusion angles are determined so as to pass the object tangentially from either side. Between the two angles, that exclusion angle is selected, which steers the ground station trace, in the communication beam, toward beam axis and not away from it. communication links of the antennae are maintained by rolling the vehicle before, during, or after slewing. The three-axis attitude and rate commands are illustrated for a stressing scenario in which two bright objects are close by and hence pose special circumstances for the algorithm to tackle.

关键词： Ground Station Antennas Yaw Earth Telescopes Quaternions communication algorithms Hubble Space Telescope Interplanetary Spacecraft Monte Carlo Simulation

来源：评论

学校读者我要写书评

暂无评论

The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width

引用

DISCRETE APPLIED MATHEMATICS 1998年第1-3期83卷 229-246页

作者： Klasing, R Rhein Westfal TH Aachen Lehrstuhl Informat D-52074 Aachen Germany

The one-way and two-way communication modes used for sending messages to processors of interconnection networks via vertex-disjoint paths in one communication step are investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds), This paper reveals a direct relationship between the gossip complexity and the vertex bisection width. More precisely, the main results are the following: 1. We prove that for any 2-way gossip algorithm running on a graph G(n,k) of n nodes and vertex bisection width k, the lower bound on the number of rounds is 2log(2)n - log(2)k - log(2)log(2)k - 6. 2. We prove that there is a graph Gn,k Of n nodes and vertex bisection width k such that there exists a 2-way gossip algorithm for it running in 2 log(2)n - log(2)k - log(2)log(2)k + 7 rounds. 3. We prove that for any 1-way "well-structured" gossip algorithm running on a graph G(n,k) of n nodes and vertex bisection width k, the lower bound on the number of rounds is 2log(2)n - 0.56....(log(2)k + log(2)log(2)k) - O(1) (to the best of the authors' knowledge, to date all gossip algorithms designed in vertex-disjoint paths mode have been "well-structured"). 4. We prove that there is a graph G(n,k) of n nodes and vertex bisection width k such that there exists a I-way gossip algorithm for it running in 2log(2)n - 0.56....(log(2)k + log(2)log(2)k) + O(1) rounds. These results improve the previous results and prove their optimality with respect to the class of graphs G(n,k) Of n nodes and vertex bisection width k. Tight lower bounds on one-way "well-structured" gossip algorithms in d-dimensional grids, d greater than or equal to 3, several results for gossiping in graphs of constant degree and planar graphs, as well as similar results for the related edge-disjoint paths mode follow. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： communication algorithms parallel computations graph bisection hypercube graph grid graph

来源：评论

学校读者我要写书评

暂无评论

Generating an efficient broadcast sequence using reflected Gray codes

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第11期8卷 1117-1122页

作者： Moore, JA Quinn, MJ OREGON STATE UNIV DEPT COMP SCICORVALLISOR 97331

One-to-all broadcast is frequently implemented on multicomputers using a binomial tree communication pattern. The source processor, at the root of the broadcast tree, completes the broadcast before the processors at the leaves of the tree. This imbalance can degrade performance when a data-parallel algorithm requires a series of broadcasts from different source processors. In this paper, we show that using a reflected Gray code to order broadcasts minimizes the communication time.

关键词： broadcasting binomial trees communication algorithms multicomputers reflected Gray code parallel processing

来源：评论

学校读者我要写书评

暂无评论

Optimal information dissemination in star and pancake networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1996年第12期7卷 1292-1300页

作者： Berthome, P Ferreira, A Perennes, S CNRS I3SF-06560 VALBONNEFRANCE

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N = n! processors, our algorithms take less than inverted right perpendicular log N inverted left perpendicular + 1.5n steps.

关键词： interconnection networks parallel computing parallel architectures communication algorithms star graph pancake graph Cayley graphs broadcast gossip parallel prefix

来源：评论

学校读者我要写书评

暂无评论

Dissemination of information in vertex-disjoint paths mode

引用

COMPUTERS AND ARTIFICIAL INTELLIGENCE 1996年第4期15卷 295-318页

作者： Hromkovic, J Klasing, R Stohr, EA CHRISTIAN ALBRECHTS UNIV KIEL INST INFORMAT & PRAKT MATH D-24098 KIEL GERMANY UNIV MANCHESTER DEPT COMP SCI CTR NOVEL COMP MANCHESTER M13 9PL LANCS ENGLAND

The communication modes (one-way and two-way mode) used for disseminating information among processors of interconnection networks via vertex-disjoint paths in one communication step are investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). Since optimal broadcast and accumulation algorithms for these modes call be achieved in a straightforward way for almost all interconnection networks used, the paper concentrates on the gossip problem. The main results are listed below: 1. Optimal gossip algorithms for paths, complete graphs and flakes in both modes. 2. For hypercubes, cube-connected cycles, butterfly networks, etc., gossip algorithms which are only about O(log(2) log(2) n) rounds slower than the optimal gossip algorithms on complete graphs are designed. Note that the results achieved have also practical applications, because the vertex-disjoint paths mode carl be implemented in several hardware realisations of computing networks.

关键词： communication algorithms parallel computations

来源：评论

学校读者我要写书评

暂无评论

Using adaptive timeouts to achieve at-most-once message delivery

引用

DISTRIBUTED COMPUTING 1995年第3期9卷 109-117页

作者： Chaudhuri, S Coan, BA Welch, JL IOWA STATE UNIV SCI & TECHNOL AMESIA 50011 BELLCORE MORRISTOWNNJ 07960 TEXAS A&M UNIV DEPT COMP SCICOLLEGE STNTX 77843

We extend the at-most-once message delivery algorithm of Liskov, Shrira, and Wroclawski to adapt dynamically to changes in message transmission time and degree of clock synchronization. The performance of their algorithm depends on its being supplied with a good estimate of the maximum message lifetime - the sum of the message delivery time and the difference in processor clock values between sender and recipient. We present two algorithms that are suitable for use in a system where the message lifetime is unknown or may change, Our extensions allow the automatic and continuous determination of a suitable value for the maximum lifetime. We prove that whenever the actual message lifetime is bounded, then our adaptive algorithms converge to an accurate estimate of its true value. Our two algorithms differ in the behavior they require from the network and achieve different performance levels. Our formal statement of convergence is expressed in terms of the number of messages received, rather than time elapsed, We show that this formulation is necessary by proving that no method for estimating the lifetime can achieve convergence in a bounded amount of time.

关键词： at-most-once message delivery communication algorithms synchronized clocks adaptive algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：