Enhancing multiple-path speculative execution with predicate window shifting

Speculative execution has long been used as an approach to exploit instruct ion level parallelism across basic block boundaries. Most existing speculat ive execution techniques only support speculating along a single control pa th, and heavily rely on branch prediction to choose the right control path. In this paper, we review the existing approaches for speculative execution and propose an extended predicated execution mechanism, called predicate s hifting, to support speculating along multiple control paths. The predicate shifting mechanism maintains a condition/predicate window for each basic b lock. With the condition/predicate window, instructions can be guarded by p redicates related to current or future branch conditions. The predicate shi fting mechanism can reduce the number of required tag bits by shifting cond itions/predicates out of the condition/predicate window whenever they are n o longer in use. To incorporate the predicate shifting mechanism into a VLI W processor, a new result-buffering structure, called future buffer, is use d to buffer uncommitted results and to evaluate predicates. The FIFO struct ure of the future buffer not only simplifies exception handling but also al lows multiple uncommitted writes to the same register. Experimental results show that the predicate shifting mechanism can use predicate tag effective ly and achieve 24% performance improvement over the previous predicating me chanism (H. Ando, C. Nakanishi, T. Hara, M. Nakaya, Unconstrained speculati ve execution with predicated state buffering, in: Proceedings of the 22nd I nternational Symposium on Computer Architecture, 1995, PF 126-137) using a small predicate tag. (C) 1999 Elsevier Science B.V. All rights reserved.