A characterization of Prolog execution
Mark A. Friedman · Minds at UW (University of Wisconsin) · 1992
We analyze the execution of a new suite of medium-sized and realistic benchmarks through simulations on a general-purpose, register-oriented architecture at the abstract machine and architectural levels to identify the most critical characteristics of Prolog for efficient execution. We propose improvements through modest enhancements to the architecture and to the Warren abstract machine to add significant support for the identified issues. Architectural support for tag-handling operations through an architecture which distinguishes between the tag and value fields of an object leads to a twelve percent decrease in static code and a seven percent decrease in executed instructions. The addition of orthogonal tag instructions reduces code size by an additional nine percent and reduces dynamic instructions by eleven percent. The introduction of push and pop instructions decreases code size by seven percent and the number of instructions executed by eight percent. Static code is reduced by forty percent and the number of instructions executed decreases by nine percent by utilizing procedure argument mode information at compile time within compiled unification operations. Knowledge of dereferencing characteristics reduces static code by six percent and reduces instructions executed by six percent by eliminating dereferencing for objects which are directly referenced and when previously dereferenced values may be substituted for non-dereferenced objects. Optimization of arithmetic expression evaluation eliminates six percent of the executed instructions which create arithmetic expressions and eliminates seven percent of the executed instructions which evaluate these structures and decreases the static code size by ten percent. A modified WAM-database execution model is proposed which reduces static code by twenty percent with a modest four percent increase in executed instructions. We find Prolog to attain only modest speedups through simple pipelined and multiple-operation-issue machine implementations and propose new directions to explore to allow Prolog to better exploit the increasing levels of instruction-level parallelism attainable in modern architectures.