Systematic Mapping of Higher-Order Functional Specifications

Zully Grant-Duff

The talk described a general method for mapping combinator (higher-order object-less functions) applications onto loosely-coupled multiprocessors. Programs in ACL, the source language where the combinators are a set of constant constructs, are represented as weighted task graphs. The weight associated with a node represents computation cost, while that associated with an arc representes communication cost. Analogously, the network is represented by a system graph whose nodes (processors) have an associated computation speed and whose arcs (communication links) have an associated communication bandwidth. The mapping algorithm clusters both graphs through identifying concurrency and connectivity respectively, and proceeds to match clusters according to demand and capacity. We showed experiments where the resulting mapping -and inherent scheduling- achieves a speed up which is approximately 66 % of the optimum.