Knowledge-Based Transformational Synthesis of Efficient Structures for Concurrent Computation

摘要

The object of our research is the codification of programming knowledge for the synthesis of concurrent programs. This is important because concurrency is a way of securing better performance on amenable problems than is available on non-concurrent computers. We divide this knowledge into two sections: knowledge for the synthesis of arrays of processors that could be connected in a geometrically regular manner (crystalline concurrency), and knowledge for the synthesis of tree structure (tree concurrency). We divide synthesis of crystalline concurrency, in turn into several subsections: synthesis of declarations of multiple processors and the wires implied by the dependencies among the values they contain reduction of this wire network to a smaller wire network creation of subnetworks to replace an overly-broad fanout network, virtualization which is the creation of additional array elements and processors to reflect the internal enumerations that comprise the computation of a datum and aggregation which is the merging of several processors into one. We use a transformational approach. The transformational system has rules each of which contains two predicates: an antecendent and a consequent. If the antecedent of a rule is true of a given object, the rule applies and the object is modified to make the consequent true. (Author)