Synthesis of Tree-Structured Computing Systems through Use of Closures

摘要

During this past year we have concerned ourselves with the synthesis of tree structures. These structures offer, in our opinion, the best hope of achieving subpolynomial running times for typical problems without a degree of interconnection that makes physical implementation difficult. One would like to be able to synthesize trees using divide & conquer. Divide & conquer is an appealing technique for tree synthesis because of the isomorphism between the shape of the desired synthesized system and the recursive descent implicit in divide & conquer. Additionally, the technique makes good use of theorem proving techniques which are rapidly being developed for other purposes. Certain problems arise, however, when one tries to use divide & conquer to synthesize a tree-structured computing system. The basic difficulty is that nodes that are high in the tree are required to either compute or communicate large amounts of data. Our primary solution to this problem is to replace the original specification, which in general declares the existence of an output array that depends on various elements of the input array, into an equivalent specification; which declares the existence of a certain closure, or specialized functional object, together with a declaration that it be applied.