Thaddeus P. Dobry

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-352

, 1987

Artificial intelligence is entering the mainstream of computer applications and as techniques are developed and integrated into a wide variety of areas they are beginning to tax the processing power of conventional architectures. To meet this demand, specialized architectures providing support for the unique features of symbolic processing languages are emerging. The goal of the research presented here is to show that an architecture specialized for Prolog can achieve a ten-fold improvement in performance over conventional, general-purpose architectures. This dissertation presents such an architecture for high performance execution of Prolog programs. <p> The architecture is based on the abstract machine description introduced by David H.D. Warren known as the Warren Abstract Machine (WAM). The execution model of the WAM is described and extended to provide a complete Instruction Set Architecture (ISA) for Prolog known as the PLM. This ISA is then realized in a microarchitecture and finally in a hardware design. <p> The design of the PLM is described at many levels. First, at the language level, some of the features of Prolog are discussed, particularly as they relate to their implementation at the ISA level. For Prolog, the unique fundamental operations of unification and backtracking provide the opportunity for specialized support to achieve high performance. The instruction set of the WAM provides for compiled unification in Prolog programs and provides a mechanism for backtracking. This dissertation proposes a variation on backtracking, called sidetracking, for more efficient implementation in many instances. The ISA enhancements to the WAM are then described. Next, the design of the microarchitecture is discussed with emphasis on those features providing special support for the ISA. These include parallel internal data paths, support for tagged data, and memory buffers and caches to support operations specified in the ISA. Finally, to complete the experiment fo the PLM, the microarchitecture was realized in physical hardware. This hardware validated the decisions made at each stage of the design. This important step in the experiment shows that the design features discussed here can indeed be realized in physical hardware and achieve the desired performance. In addition, simulators were written and utilized at each stage to measure and study the design with the hardware providing feedback to make the simulators more realistic. A quantitative analysis of the design features of the PLM is provided based on the results of these simulator studies. These results show that a ten-fold performance advantage is indeed achieved over the Prolog implementation proposed by Warren for a general-purpose processor. Directions for future study to further improve the performance of the PLM are also provided.

Advisors: Alvin M. Despain

---

BibTeX citation:

@phdthesis{Dobry:CSD-87-352,
    Author= {Dobry, Thaddeus P.},
    Title= {A High Performance Architecture for Prolog},
    School= {EECS Department, University of California, Berkeley},
    Year= {1987},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html},
    Number= {UCB/CSD-87-352},
    Abstract= {Artificial intelligence is entering the mainstream of computer applications and as techniques are developed and integrated into a wide variety of areas they are beginning to tax the processing power of conventional architectures. To meet this demand, specialized architectures providing support for the unique features of symbolic processing languages are emerging.  The goal of the research presented here is to show that an architecture specialized for Prolog can achieve a ten-fold improvement in performance over conventional, general-purpose architectures. This dissertation presents such an architecture for high performance execution of Prolog programs. <p> The architecture is based on the abstract machine description introduced by David H.D.  Warren known as the Warren Abstract Machine (WAM). The execution model of the WAM is described and extended to provide a complete Instruction Set Architecture (ISA) for Prolog known as the PLM. This ISA is then realized in a microarchitecture and finally in a hardware design. <p> The design of the PLM is described at many levels. First, at the language level, some of the features of Prolog are discussed, particularly as they relate to their implementation at the ISA level. For Prolog, the unique fundamental operations of unification and backtracking provide the opportunity for specialized support to achieve high performance. The instruction set of the WAM provides for compiled unification in Prolog programs and provides a mechanism for backtracking. This dissertation proposes a variation on backtracking, called sidetracking,  for more efficient implementation in many instances. The ISA enhancements to the WAM are then described. Next, the design of the microarchitecture is discussed with emphasis on those features providing special support for the ISA. These include parallel internal data paths,  support for tagged data, and memory buffers and caches to support operations specified in the ISA. Finally, to complete the experiment fo the PLM, the microarchitecture was realized in physical hardware. This hardware validated the decisions made at each stage of the design.  This important step in the experiment shows that the design features discussed here can indeed be realized in physical hardware and achieve the desired performance. In addition,  simulators were written and utilized at each stage to measure and study the design with the hardware providing feedback to make the simulators more realistic. A quantitative analysis of the design features of the PLM is provided based on the results of these simulator studies.  These results show that a ten-fold performance advantage is indeed achieved over the Prolog implementation proposed by Warren for a general-purpose processor. Directions for future study to further improve the performance of the PLM are also provided.},
}

EndNote citation:

%0 Thesis
%A Dobry, Thaddeus P. 
%T A High Performance Architecture for Prolog
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-352
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html
%F Dobry:CSD-87-352