為 Prolog 語言設計一個有智慧型回溯功能之"或"平行執行模式

Abstract

在本論文中，我們為 Prolog 語言提出了一個有智慧型回溯功之〝或〞平行執行模式 ，此平行執行模式可被應用於一個我們所設計之多處理機系統- MIEP ( Multiple In ference Engine for Prolog ) ，其主要之核心處理機為一專為 Prolog 設計之精簡 指令型 ( RISC ) 處理機，LISCP 我們所採用之多處理機架構是多匯流排架構。 文中，我們提出了一個很有效率的智慧型回溯方法，此法可減少甚多不必要之回溯， 而且所付出之代價也不高。此法也被應用於我們所設計之〝或〞平行執行模式中，此 模式可以 Packet Passing 之方式實現之。並具有下列幾點特性﹕(1) 沒有環境資料 之複製；(2) 沒有程序管理之額外負擔；(3) 儘量減少 LISCP間之通訊；(4) 含智慧 型回溯之功能；(5) 能充分使用 LISCP記錄器窗；(6) 分散式執行及控制； 為了能將 Prolog 程式編譯為可平行執行之 LISCP目的碼，我們也設計並製作出第一 版之平行編譯器。此編譯器中應用了子句索引 ( Clause Indexing )及赫序( Hash ) 技巧。另外，我們也使用了較理想之記錄器配置法以節省計錄器之使用及不必要指令 之執行。 最後，針對我們的平行執行模式，我們設計出一個模擬器來評估我們的模式及系統。 結果顯示，此模式及系統極適於處理資料庫、專家系統、自然語言處理和定理證明等 〝不確定性〞高之應用。