Formal derivation of efficient parallel programs by construction of list homomorphisms
Formal derivation of efficient parallel programs by construction of list homomorphisms
复制标题
通过构建列表同态形式化推导高效并行程序
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
M. Takeichi
中科院分区：
文献类型：
--
作者：
Zhenjiang Hu;H. Iwasaki;M. Takeichi
由于列表同态非常适合分而治之的并行范式，因此在并行编程中使用列表同态一直备受关注。然而，在高效并行程序的开发过程中，它们通常被非正式地临时处理。更糟糕的是，一些有趣的函数，如最大分段和问题，基本上不是列表同态的。在本文中，我们提出了一种系统而正式的方法，为给定问题构建列表同态，从而导出高效的并行程序。我们通过几个众所周知但并不复杂的问题，展示了如何将一个简单明了、"显然 "正确但相当低效的问题解决方案成功转化为语义等价的 "近似列表同态"。这一推导基于两种变换，即 tupling 和 fusion，它们是根据列表同态的特定递归结构定义的。
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. What is worse is that some interesting functions, e.g., the maximum segment sum problem, are basically not list homomorphisms. In this article, we propose a systematic and formal way for the construction of a list homomorphism for a given problem so that an efficient parallel program is derived. We show, with several well-known but nontrivial problems, how a straightforward, and “obviously” correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent “almost list homomorphism.” The derivation is based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.