Study on Parallelization Method for Sequential Processes Using Partial Evaluation

本课题研究了一种提高顺序进程并行化效率的方法，研究了并发进程的真正并发语义和等价关系，为保证转换后的程序保持原程序的特征，提高并行性提供了理论基础。我们证实，使用展开的部分评估方法可以应用于并行化使用的框架，部分评估的并发进程之前报道。此外，我们研究了Prolog程序的并行化作为我们提出的并行化框架的实例。特别是，在许多现有的实用的Prolog程序的有效性取决于目标和/或子句的选择的顺序，我们不能得到预期的答案，并行派生每个子目标。我们证明了通过子句的转换可以将这些程序转换成与原程序等价的程序，并且可以并行执行.我们着重研究了并发进程的真正并发语义的π演算理论.我们介绍了DBS的域，它由具有过程的分支结构和表示事件之间因果关系的事件的偏序的结构组成。我们定义了一个从π-演算子集到DBS论域的语义映射，并证明了用这个语义映射定义的等价关系是全等关系。我们还表明，更抽象的等价关系，可以通过扩展的测试等价的ACP使用DBS的过程的测试。我们还表明，我们可以使用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.