Reducing branch costs via branch alignment

Publisher Website
Google Scholar
Abstract
Several researchers have proposed algorithms for basic block re - ordering We call these branch alignment algorithms The primary emphasis of these algorithms has been on improving instruction cache locality, and the few studies concerned with branch predic - tion reported small or minimal improvements As wide - issue archi - tectures become increasingly popular the importance of reducing branch costs will increase, and branch alignment is one mechanism which can effectively reduce these costs In this paper, we propose an improved branch alignment algo - rithm that takes into consideration the architectural cost model and the branch prediction architecture when performing the basic block reordering We show that branch alignment algorithms can improve a broad range of static and dynamic branch prediction architectures We also show that a programs performance can be improved by ap - proximately 5% even when using recently proposed, highly accurate branch prediction architectures The programs are compiled by any existing compiler and then transformed via binary transformations When implementing these algorithms on a Alpha AXP 21604 up to a 16% reduction in total execution time is achieved

This publication has 20 references indexed in Scilit: