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

Mapping tree-structured computations onto mesh-connected arrays of processors

Parallel Algorithms and Applications 1993年第3期1卷 211-220页

作者： Tsay, Jyh-Jong National Chung Cheng University Institute of Computer Science and Information Engineering Chiayi 621 Taiwan

This paper shows how to parallelize tree-structured computations for d-dimensional (d > 1) mesh-connected arrays of processors. A tree-structured computation T consists of n computational tasks whose dependencies form a task tree T of n constant degree nodes. Each task can be executed in unit time, and sends one value to its parent task after it has executed. Let h be the height of T. We present linear time algorithms for partitioning and mapping the task tree T onto a p^1/d x x p^1/d mesh-connected array of processors so that we can schedule the processors to perform computation T in O(n)p) time, for p < min{n/h, n^d/(d+1)}. The O(max{h, n^1/(d+1)} time bound achieved when p = min{n/h, n^{d/d + 1})} is the best possible (upto a constant factor) over all p> 1. The best previous bound was 0((√n + h) log n) achieved on a linear array of min[n/h, n^1/2} processors, and could not be generalized to higher dimensional meshes. As a consequence, we obtain a mapping and schedule of an n-node expression tree of associative operators over a p^1/d x x p^1/d mesh-connected processor array, which evaluates the expression tree in O(n/p) time, for p < n^d/d+1). © 1993, Taylor & Francis Group, LLC. All rights reserved.

关键词： Mapping algorithms mesh-connected arrays of processors Tree partitioning

来源：评论

学校读者我要写书评

暂无评论

ON THE PARALLEL-DECOMPOSABILITY OF GEOMETRIC PROBLEMS

引用

ALGORITHMICA 1992年第3期8卷 209-231页

作者： ATALLAH, MJ TSAY, JJ NATL CHUNG CHEN UNIV INST COMP SCI & INFORMAT ENGNCHIAYI 62107TAIWAN

There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in time O(n1/d) on a d-dimensional n-processor array), and they all assume that the parallel machine is trying to solve a problem of size n on an n-processor array. Here we investigate the situation where we have a mesh of size p and we are interested in using it to solve a problem of size n > p. The goal we seek is to achieve, when solving a problem of size n > p, the same speed up as when solving a problem of size p. We show that for many geometric problems, the same speedup can be achieved when solving a problem of size n > p as when solving a problem of size p.

关键词： COMPUTATIONAL GEOMETRY mesh-connected arrays of processors PARALLEL ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：