Automatically Deriving Cost Models for Structured Parallel Processes(…) – Kevin Hammond – YouTube
Structured parallelism using nested algorithmic skeletons can greatly ease the task of writing parallel software, since common, but hard-to-debug prob- lems such as race conditions are eliminated by design. However, choosing the right combination of algorithmic skeletons to yield good parallel speedups for a specific program on a specific parallel architecture is still a difficult prob- lem. This work uses the unifying notion of hylomorphisms, a general recursion pattern, to make it possible to reason about both functional correctness prop- erties and extra-functional timing properties of structured parallel programs. We have previously used hylomorphisms to provide a denotational semantics for skeletons, and proved that a given parallel structure for a program sat- isfies functional correctness. This paper expands on this theme, providing a simple operational semantics for algorithmic skeletons, and a cost semantics that can be automatically derived from that operational semantics. We prove both semantics sound with respect to the previous denotational semantics. This means that we can now automatically and statically choose the prov- ably optimal parallel structure for a given program with respect to a parallel architecture or a class of architectures. We are also able to predict speedups using an automatic amortised analysis.