PUMTS: 一個針對 Prolog 設計之平行一致化多引線超純量處理機

Abstract

本論文的主旨在針對Prolog的平行一致化執行模式設計一有效能之處理機 架構-PUMTS(Parallel Unification Multi-threaded Superscalar ).由 於 Prolog 為人工智慧所常使用的語言之一,因此將需要一高效能的處理 機來處理 Prolog程式. 在整個 Prolog 程式執行的時間內, 一致化動作 佔了 55% 到 70%, 因此若能設計一能有效處理一致化動作的處機, 則整 體的效能將可提升. 我們是以 finegrained 的角度來設計此處理機架構, 此處理機結合了超純量(superscalar) 處理機及多引線(Multi- threaded) 處理機的特性. 我們利用超純量處理機的特性來開發指令間的 平行度, 並且利用多引線處理機的特性來平行執行一致化動作,每條引線 是以超純量處理機的我特性來執行指令.我們設計之處理機是承襲 LISCP- II(Linited Instruction Set Comp- er for Prolog,Versoin-II) 的指 令集. 暫存器組及記憶體等組識.LISCP- II為一個已設計完成且專為執 行 Prolog 的 RISC 型態的機器. 我們利用此基礎來探討 Prolog 在多引 線超純量處理機上執行平行一致化所遭遇之問題, 並提出解決之方法.在 模擬系統架構的結果上,我們發現 PUMTS 的效能為 LISCP-II 的3.6倍, 在處理一致化的動作上,其效能為具有相同硬體資源的超純量處理機的 1.4 倍, 而在整體的效能上仍為其1.07 倍. In this thesis, we design a high performance processor for parallel unification of Prolog - PUMTS (Parallel Unification Multi-Threaded Superscalar processor ). Prolog is the most used AI language, so a high performance Prolog processor is in great demand. The propotion of execution time spent on unification in a typical Prolog program vauges from 50% to 70%. If we can design a processor with high performance in processing unfication,the overall performance can be enhanced. We are to design such a processor based on fine-grained parallelism. This processor integrates the charateristics of superscalar processor and multi-threaded processor. We take the advantages of superscalar processing to exploit the instruction level parallelism, and multi-threaded peocessing to execute unification concurrently. PUMTS system accedes the instruction set, the register file and memory system of LISCP-II(Limited Instruction Set Computer for Prolog, Version II) . LISCP-II is a Prolog RISC processor. Based on LISCP-II,we discuss and propose the solutions to the problems encountered during executing the parallel unification on a superscalar processor. In the results of simulation, we observe that the performance of PUMTS is 3.6 times that of LISCP-II. We also compare PUMTS and the superscalar processor given the same amount of hardware resources. We observe that the performsce of PUMTS is 40% better than the superscalar processor in unification,and 7% better than superscalar processor for execution on the entir program.