ANDROR：一個PROLOG語言AND/OR平行執行模式的研究

Abstract

本論文針對PROLOG語言，提出了一個融合AND 平行特性及OR平行特性的執行模式，稱 為ANDROR模式。在提出這個平行模式的過程中，我們審慎的考慮平行度與額外負擔（ OVERHEAD）之間的取捨。因此，這個模式可盡量發揚PROLOG程式所隱含的平行性，但 不會造成太大的額外負擔。 在偵測AND 平行性的做法上，採用了數種資料結構（DATA STRUCTURE）。針對每個子 句（CLAUSE）中的每個變數，我們列出所有用到這個變數的SUBGOAL 來構成GENERATO R LIST。針對每個子句中的所有SUBGOAL ，我們建立LOCK TABLE來記錄每個SUBGOAL 須等候幾個變數有值之後才能執行。同時在智慧型回溯（INTELLIGENT BACKTRACKING ）方面，我們針對每個子句建立一個BACKTRACK LIST來記錄所有可能的回溯路徑；這 個回溯方式將不會漏掉任何答案。 在OR平行性的展開上，我們採用限制式的OR平行執行（RESTRICTED OR-PARALLEL EXE CUTION）方式。這個方式將沒有非限制式平行執行（UNRESTRICTED OR-PARALLEL EXE CUTION）所有的CARTESIAN PRODUCT 的問題及額外負擔。