Periodic Adaptive Branch Prediction and its Application in Superscalar Processing in Prolog

Branch instructions create barriers to instruction prefetching, greatly reducing the fine-grained parallelism of programs. Branch prediction is a common method for solving this problem. We first present four lemmata in this paper describing the relationships among branch prediction hit rate and system performance, hardware efficiency, and branch prediction overhead. We then propose a branch prediction method called PAM (Periodic Adaptive Method). An abstract model and detailed implementation of PAM are described. PAM's prediction hit rate as measured by 10 Prolog benchmark programs is 97%. When implemented in a superscalar Prolog system, PAM enhances the degree of system parallelism by 68.8%. PAM can be applied to languages and applications other then the Prolog system we used in this study.