Branch prediction can be done in software, though that will take up memory. There are also ways to avoid branching, such as unrolling loops so that they are inline. The problem with this is you might need a lot of registers, which the SPEs do have.
I'm doing some reading up on it right now, so I'll be able to contribute a bit more in a bit.