PFAST: A RISC processor for prolog

This dissertation presents the steps followed to define a specialized RISC architecture for fast execution of Prolog (PFAST). This research is based on the abstract Prolog machine description, known as the Warren Abstract Machine (WAM), defined by David H. D. Warren. The main goal of this research is to design a high performance single-task Prolog processor. The design of this special-purpose processor was accomplished by doing a comprehensive evaluation of multiple increasingly complex RISC architectures. This research draws on other RISC Prolog processors, providing a quantitative study of the design choices; all of which are not present in each architecture. The final PFAST design is a comprehensive architecture; 'better' in the sense that it is an optimal selection of previously proposed enhancements.;The main difference between the design of the PFAST and previous Prolog processors is that the PFAST is derived from the analysis of modifications to the instruction set or architecture and the impact of these modifications on its performance. Whereas, other studies of the WAM try to justify specialized hardware to speedup Prolog by only taking into account either the frequency of the instructions or empirical knowledge of bottlenecks, which normally result in good guesses, these studies do not give a realistic estimation of the execution cost of backtracking, dereferencing, nor unifying. This dissertation calculates the cost of each WAM instruction based on the execution frequency and number of cycles of the instruction.;The design of the PFAST is done in an evolutionary manner, starting with a semi-general-purpose RISC architecture and ending with a very specific-purpose Prolog RISC architecture. The first proposed PFAST has only one special Prolog feature: it handled tags. Further architectures proposed in this research have more specialized hardware to speedup the execution of Prolog programs. The design of this specialized hardware is accomplished by evaluating the performance contribution of each individual function.