標題: ANDROR:一個PROLOG語言AND/OR平行執行模式的研究
作者: 吳坤榮
WU, KUN-RONG
鍾崇斌
ZHONG, CHONG-BIN
資訊科學與工程研究所
關鍵字: PROLOG語言;智慧型回溯;限制式OR平行執行;ANDROR;PROLOG-LANGUAGE;SUBGOAL;INTELLIGENT-BACKTRACKING;RESTRICTED-OR-PE;CARTESIAN-PRODUCT
公開日期: 1988
摘要: 本論文針對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 的問題及額外負擔。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT772394040
http://hdl.handle.net/11536/53793
顯示於類別:畢業論文