Formal derivation of parallel program for 2-dimensional maximum segment sum problem
説明
It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm. However, they have been usually treated rather informally and ad-hoc in the development of efficient parallel programs. This paper reports a case study on systematic and formal development of a new parallel program for the 2-dimensional maximum segment problem. We show how a straightforward, and“obviously” correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent “almost list homomorphism” based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.
