Research on synthesis of concurrent computing systems (Extended Abstract)

Publisher Website
Google Scholar
Abstract
The object of our research is the codification of programming knowledge for the synthesis of concurrent programs. We present sample rules and techniques that we show can be used to derive two concurrent algorithms: dynamic programming (for the class of problems that run in polynomial time on sequential machines) and array multiplication. For both derived concurrent versions the code runs in linear time. The concurrent versions are significant and complex algorithms, though they are not new and already have been reported in the literature. The synthesis knowledge for these derivations is embodied in seven synthesis rules. We expect these rules to generalize to other classes of algorithms. We have also discovered a pair of techniques called virtualization and aggregation. This pair of techniques (plus the seven rules) is shown to be powerful enough to synthesize Kung's systolic array architecture [Kung-76] from a specification of matrix multiplication.