Prolog遞迴圈串列結構的並行

Abstract

不管是邏輯（logic）或非邏輯（nonlogic）的程式語言中，遞迴（recursion）的程式結構都是使程式執行時間增長的主要原因之一。尤其在邏輯程式中（如Prolog），遞迴是主要的程式結構，其影響也就愈大。本論文討論，在Prolog中， 線狀結構（linear structure）的遞迴圈處理串列結構（list structure ）時，如何利用遞迴圈重複執行，串列分割運算以及Prolog的單一指定（single assignment）之特性，突破遞迴須循序呼叫的限制；使每一次的遞迴可提前執行，無須等到上一次的遞迴呼叫才後執行。這無異可減短遞圈完成處理的時間，增加Prolog執行的並行度。 於本論文中，我們提出如何在編譯時取得並行所須的資訊，包括找出處理串列的遞迴圈，分析遞迴圈內部的結構以求得每次遞迴輸入參數的變化。並且，提出如何利用編譯時所穫取的資訊，執行並行的方法。

Be it in logic or nonlogic programming languages, recursive loops are one of the reasons that increases the execution time of a program. In logic programs (like Prolog), since recursive loops are main programming structures, the effect that recursive loops cause is much stronger. If we can execute recursive loops in parallel, then the processing time of recursive loops should be decreased and the execution efficiency of a program should also be improved. This thesis illustrates how to parallelize loops of a recursive loop by using the properties of recursive loops that belong to linear structure type and process list structures in Prolog. These properties include repeated execution. list operation, and single assignment. There are three steps we propose at compile time to obtain information that helps the parallel execution of recursive loops. The first step is to find the recursive loops that can be parallelized, the second is to analyze the recursive loops, the third is the create the control process execution code which prepares inputs of loops. By using the information obtained at compile time, we also propose a execution-time control scheme for paralleizing recursive loops.