A branch cache (40) has a plurality of storage levels (120, 122, 140, and/or 142) wherein at least two write registers (114 and 116) are used to perform a parallel write operation to at least two of the storage levels in the plurality of storage levels (120, 122, 140, and/or 142). The two write registers (114 and 116) are provided due to the fact that the branch cache 40 is implemented as a multi-state (typically five state--see FIG. 5) branch prediction unit having instruction folding. Instruction folding, as taught herein, allows a branch instruction which is predicted as being taken to be executed along with an instruction that precedes the branch in execution flow. The instruction which directly precedes the branch in execution flow is usually the instruction which is used to "fold" the branch. Effectively, this instruction folding allows branches, which are predicted as being taken, to be executed in zero clock cycles.