ON THE PARALLEL-DECOMPOSABILITY OF GEOMETRIC PROBLEMS

作     者：ATALLAH, MJ TSAY, JJ 

作者机构：NATL CHUNG CHEN UNIVINST COMP SCI & INFORMAT ENGNCHIAYI 62107TAIWAN 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：1992年第8卷第3期

页      面：209-231页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：COMPUTATIONAL GEOMETRY MESH-CONNECTED ARRAYS OF PROCESSORS PARALLEL ALGORITHMS 

摘      要：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.