DocumentCode :
1317098
Title :
Branch merging for scheduling concurrent executions of branch operations
Author :
Chen, Chih-Ming ; King, Chung-Ta ; Chen, Y.Y. ; Debnath, Depanwita ; Sasao, T.
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Volume :
143
Issue :
6
fYear :
1996
fDate :
11/1/1996 12:00:00 AM
Firstpage :
369
Lastpage :
375
Abstract :
Branches are a major limiting factor to instruction-level parallelism. One solution is to execute several branches simultaneously using multiway branching architectures. Such architectures are especially important when the instruction issue width becomes large. The authors study the problem of compile-time scheduling of branch operations on such architectures: an optimisation called branch merging. The scheduling attempts to bring profitable branches together for concurrent execution. It is shown that finding the optimal solution to the branch merging problem is NP-hard. A heuristic is then proposed, which relies on a cost model to direct the merging of branches and their associated basic blocks. Merged branches are then scheduled together for concurrent execution. The authors used simulation to evaluate the effectiveness of the proposed algorithm. Experiments on selected benchmark programs show that the heuristic achieves roughly a 10% performance improvement on multiway branching architectures
Keywords :
computational complexity; instruction sets; optimising compilers; parallel algorithms; parallel architectures; scheduling; software performance evaluation; trees (mathematics); NP-hard; branch merging; branch operations; compile-time scheduling; concurrent execution scheduling; cost model; decision trees; directed graphs; heuristic; instruction issue width; instruction-level parallelism; multiway branching architectures; optimal solution; optimisation; performance; simulation;
fLanguage :
English
Journal_Title :
Computers and Digital Techniques, IEE Proceedings -
Publisher :
iet
ISSN :
1350-2387
Type :
jour
Filename :
556708
Link To Document :
بازگشت