A recursive approach to parallel computation

Despite the advantages of recursive algorithms, they have not gained widespread acceptance because of their poor performance on conventional computers. In this work, we present, on the one hand, a mechanism to support the efficient parallel execution of a set of recursive functions. Each recursive function works on a mutually exclusive data domain and solves part of the problem. On the other hand, we describe a method to solve programs by means of data decomposition and a set of linear recursive functions. The machine model is called Parallel Recursive Evaluator (PRE). This machine can be used to solve problems that can be decomposed into a set of independent recursive functions and pipeline them into it. The PRE is based on two pipelines of n processors each, n being the maximum recursive depth level to be reached. One of the pipes is called the Call Down Pipe (CDP) and the other one is called the Return Up Pipe (RUP). In the CDP, recursive function calls are made, arguments are updated, and partial results are stored in the local memories. In the RUP, partial values are computed and returned. These two pipes communicate in two ways: via, local shared memory at each level of recursion and by message passing. Processors within each pipe only communicate by message passing with their two local neighbor processors. In this architecture, 2 * n recursive functions can be evaluated simultaneously. As case study, PRE is programmed to evaluate the factorial and the matrix-vector product. Finally, the Az = b problem is solved as a set of recursive functions and we describe how it is executed on the recursive mechanism proposed in 3n -1 steps.