Study on Parallelization Method for Sequential Processes Using Partial Evaluation

本课题研究了一种提高顺序进程并行化效率的方法，研究了并发进程的真正并发语义和等价关系，作为保证转换后的程序保留原程序的特征，从理论上提高并行性的基础研究。我们证实了使用展开的部分求值方法可以应用于使用之前报道的并发进程的部分求值框架的并行化。此外，我们还研究了Prolog程序的并行化，作为我们提出的并行化框架的实例。特别是在现有的许多语用Prolog程序中，其有效性取决于目标和/或子句的选择顺序，我们无法通过并行推导每个子目标来获得预期的答案。我们证明，通过转换子句，可以将这些程序转换为与原始程序等效并可以并行执行的程序。我们将注意力集中在pi-微积分理论上，主要是为了解决并发进程的真正并发语义问题。我们引入了DBS领域，该领域由具有过程分支结构和表示事件之间因果关系的事件偏序结构的结构组成。我们定义了一个从pi-微积分子集到DBS域的语义映射。我们证明了用语义映射同余关系定义的等价关系。利用DBS作为过程的测试者，对ACP的测试等价进行扩展，可以得到更抽象的等价关系。我们还展示了我们可以使用DBS的思想构建并发逻辑语言的语义。

This project investigated a parallelization method of sequential processes for improving the effeciency, and investigated truly concurrent semantics and equivalence relations of concurrent processes, as the basic research to guarantee that the transformed program preserves the feature of the original program and the parallelism is improved theoretically. We confirmed that partial evaluation methods using unfolding can be applied for parallelization using the framework of partial evaluation of concurrent processes that is reported before. Furthermore, we investigated the parallelization of Prolog programs as the instance of the framework of parallelization we presented. Especially, in many existing pragmatic Prolog programs of which validity depends on the order of the selection of goals and/or clauses, we cannot obtain the intended answers by deriving each subgoal in parallel. We showed that it is possible to transform those programs into the programs that work equivalently to the original programs and can be executed in parallel by transforming the clauses.We focused our attention on the theory of pi-calculus mainly for the truly concurrent semantics of concurrent processes. We introduced the domain of DBS that consists of structures which have branching structure of processes and partial order of events that represents the causality between the events. We defined a semantic mapping from a subset of pi-calculus to the domain of DBS.We showed that the equivalence relation that is defined using the semantic mapping congruent relation. We also showed that more abstract equivalence relation can be obtained by extending the testing equivalence of ACP using DBS's as testers of processes. We also showed that we can construct a semantics of concurrent logic languages using the idea of DBS.