DYNAMIC-PROGRAMMING ON A SHARED-MEMORY MULTIPROCESSOR

被引：8

作者：

EDMONDS, P

CHU, E

GEORGE, A

机构：

[1] UNIV WATERLOO,DEPT COMP SCI,WATERLOO N2L 3G1,ONTARIO,CANADA

[2] UNIV GUELPH,DEPT MATH & STAT,GUELPH N1G 2W1,ONTARIO,CANADA

[3] UNIV GUELPH,DEPT COMP & INFORMAT SCI,GUELPH N1G 2W1,ONTARIO,CANADA

[4] UNIV TORONTO,DEPT COMP SCI,TORONTO M5S 1A1,ONTARIO,CANADA

来源：

PARALLEL COMPUTING | 1993年 / 19卷 / 01期

基金：

美国国家航空航天局; 加拿大自然科学与工程研究理事会;

关键词：

DYNAMIC PROGRAMMING; SHARED-MEMORY MULTIPROCESSOR; PERFORMANCE EVALUATION; NUMERICAL EXPERIMENTS;

D O I：

10.1016/0167-8191(93)90102-Q

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Three new algorithms for solving dynamic programming problems on a shared-memory parallel computer are described. All three algorithms attempt to balance work load, while keeping synchronization cost low. In particular, for a multiprocessor having p processors, an analysis of the best algorithm shows that the arithmetic cost is O(n3/6p) and that the synchronization cost is O(\log(C) n\) if p much less than n, where C = (2p - 1)/(2p + 1) and n is the size of the problem. The low synchronization cost is important for machines where synchronization is expensive. Analysis and experiments show that the best algorithm is effective in balancing the work load and producing high efficiency.

引用

页码：9 / 22

页数：14