Branch prediction for enhancing fine-grained parallelism in prolog

Ruey Liang Ma; Chung-Ping Chung

Branch prediction for enhancing fine-grained parallelism in prolog

Ruey Liang Ma^*, Chung-Ping Chung

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

Branch instructions create barriers to instruction fetching, thus greatly reducing the fine-grained parallelism of programs. One common method for solving this problem is branch prediction. In this paper, we first present four lemmas to clarify the relationship between the branch prediction hit rate and system performance, hardware efficiency, and branch prediction overhead. We then propose a new branch prediction method called PAM (Period Adaptive Method). An abstract model and detailed implementation of PAM are described. The prediction hit rate of this method was measured using ten Prolog benchmark programs and found to be 97%. When implemented in a superscalar Prolog system, PAM enhances the degree of system parallelism by 80%.

Original language	English
Pages	744-751
Number of pages	8
State	Published - 1 Dec 1994
Event	Proceedings of the 1994 International Conference on Parallel and Distributed Systems - Hsinchu, China Duration: 19 Dec 1994 → 21 Dec 1994

Conference

Conference	Proceedings of the 1994 International Conference on Parallel and Distributed Systems
City	Hsinchu, China
Period	19/12/94 → 21/12/94

Fingerprint Dive into the research topics of 'Branch prediction for enhancing fine-grained parallelism in prolog'. Together they form a unique fingerprint.

Cite this

@conference{57ad68563d4a43a08874dd2aed7c987a,

title = "Branch prediction for enhancing fine-grained parallelism in prolog",

abstract = "Branch instructions create barriers to instruction fetching, thus greatly reducing the fine-grained parallelism of programs. One common method for solving this problem is branch prediction. In this paper, we first present four lemmas to clarify the relationship between the branch prediction hit rate and system performance, hardware efficiency, and branch prediction overhead. We then propose a new branch prediction method called PAM (Period Adaptive Method). An abstract model and detailed implementation of PAM are described. The prediction hit rate of this method was measured using ten Prolog benchmark programs and found to be 97%. When implemented in a superscalar Prolog system, PAM enhances the degree of system parallelism by 80%.",

author = "Ma, {Ruey Liang} and Chung-Ping Chung",

year = "1994",

month = dec,

day = "1",

language = "English",

pages = "744--751",

note = "null ; Conference date: 19-12-1994 Through 21-12-1994",

}

TY - CONF

T1 - Branch prediction for enhancing fine-grained parallelism in prolog

AU - Ma, Ruey Liang

AU - Chung, Chung-Ping

PY - 1994/12/1

Y1 - 1994/12/1

N2 - Branch instructions create barriers to instruction fetching, thus greatly reducing the fine-grained parallelism of programs. One common method for solving this problem is branch prediction. In this paper, we first present four lemmas to clarify the relationship between the branch prediction hit rate and system performance, hardware efficiency, and branch prediction overhead. We then propose a new branch prediction method called PAM (Period Adaptive Method). An abstract model and detailed implementation of PAM are described. The prediction hit rate of this method was measured using ten Prolog benchmark programs and found to be 97%. When implemented in a superscalar Prolog system, PAM enhances the degree of system parallelism by 80%.

AB - Branch instructions create barriers to instruction fetching, thus greatly reducing the fine-grained parallelism of programs. One common method for solving this problem is branch prediction. In this paper, we first present four lemmas to clarify the relationship between the branch prediction hit rate and system performance, hardware efficiency, and branch prediction overhead. We then propose a new branch prediction method called PAM (Period Adaptive Method). An abstract model and detailed implementation of PAM are described. The prediction hit rate of this method was measured using ten Prolog benchmark programs and found to be 97%. When implemented in a superscalar Prolog system, PAM enhances the degree of system parallelism by 80%.

UR - http://www.scopus.com/inward/record.url?scp=0028749498&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0028749498

SP - 744

EP - 751

Y2 - 19 December 1994 through 21 December 1994

ER -