Analysis of ffp programs for parallel associative searching
Jr. Earl Hollins Williams · 1981
The formal functional programming (FFP) languages proposed by Backus are capable of expressing unbounded parallelism. Mago has designed a cellular computer that can efficiently execute FFP programs and, within limits of machine size, accommodate the unbounded parallelism. In this work, several analysis techniques are presented and used to predict the execution time and storage requirements of FFP associative searching algorithms on the Mago machine. Both decomposable searching and closest point problems are investigated. Brute force, semi-parallel, and cell methods are presented for solving the decomposable searching problems. If the initial program expression is suitably placed in memory, analysis of the brute force algorithms yields complexity results of O(k) time and O(kn) space. These bounds are shown to be asymptotically optimal with respect to the problem and the machine. Brute force, semi-parallel, and divide-and-conquer solutions are presented for solving the closest point problems. Analyses of the semi-parallel algorithms yield complexity results of O(kn) time and space, which are shown to be asymptotically optimal. Estimates of execution times of fast associative searching algorithms on a hypothetical sequential machine are compared to estimates of the execution times for the same problem on the Mago machine. The results indicate that the Mago machine will perform faster on files of moderate to large size. Suggestions are given for new operators that would reduce the execution time and storage requirements of FFP programs.