一個為高效能RISC型態PROLOG處理機發展之動態智慧型迴溯技術

Abstract

本論文之主旨在於提出一個新的Prolog智慧型回溯技術, 並依此回溯演算法發展於一 部32位元的高效能RISC型態之Prolog理機–LISCPⅡ(Limited Instruction Set Comp uter for Prolog,Version-Ⅱ), 以提高單一LISCP-Ⅱ 的循序執行效益。 我們使用動態的方法來記錄、分析造一致化失敗的變數, 依此資訊來選擇回溯路徑, 而達到很好的回溯效能, 減少甚多不必要的搜尋和回溯, 提高Prolog的執行效率。本 篇所提出之回溯技術和其他相關研究比較具有下列特點: (一)、突破clause-level的 回溯, 使回溯能跨過一個子句達到更佳的效能。(二)、適合適用於單一Prolog處理機 上, 且所付出的額外負擔不大。(三)、利用回溯點堆詁(Back-tracking Point Stack ,BPS) 來記錄變數的generator 。(四)、分散式回溯點堆疊(distributed BPS) 之設 計, 透過Prolog 執行時擊結的追蹤及解除來管理BPS。(五)、能夠完全處理green cu t 和red cut 。(六)、方法簡單, 一般架構很容易支援。 我們修改LISCP-Ⅱ的編譯系統及模擬環境來驗證此回溯技術與量測評估效能, 確實達 到不錯之效果。最後, 對本篇論文研究之後的延績發展提出一些建議。