Parallel solution of recurrences on a tree machine |
| |
Authors: | Roy P Pargas |
| |
Affiliation: | (1) Department of Computer Science, Clemson University, 29631 Clemson, South Carolina |
| |
Abstract: | The recurrencex
o =a
o
x
i =a
i+b
i
x
i–1,i = 1, 2,...,n–1 requiresO(n) operations on a sequential computer. Elegant parallel solutions exist, however, that reduce the complexity toO(logN) usingNn processors. This paper discusses one such solution, designed for a tree-structured network of processors.A tree structure is ideal for solving recurrences. It takes exactly one sweep up and down the tree to solve any of several classes of recurrences, thus guaranteeing a solution inO(logN) time for a tree withNn leaf nodes. Ifn exceedsN, the algorithm efficiently pipelines the operation and solves the recurrence inO(n/N + logN) time. |
| |
Keywords: | Tree machine parallel computation recurrences |
本文献已被 SpringerLink 等数据库收录! |
|