1. A computer implemented method for pipelined branch prediction of multiple threads, the method comprising: selecting, in a first pipeline stage, a first execution thread from a plurality of execution threads; prior to storage, allocating and thereby setting aside for future data storage, in a second pipeline stage, storage in a branch prediction output queue shared by the plurality of execution threads to be used to store a branch prediction at a later point in time, wherein the branch prediction is not generated within the second pipeline stage, said storage corresponding to a portion of the first execution thread and freeing, in said second pipeline stage, storage in the branch prediction output queue to be potentially used in a different pipeline stage; preventing progression of said first execution thread to said third pipeline stage unless the pre-allocating of storage in the branch prediction output queue succeeds in the second pipeline stage, wherein a second execution thread is permitted to bypass the first execution thread that is prevented from progressing; generating, in a third pipeline stage, a branch prediction corresponding to said portion of the first execution thread; and storing, in a fourth pipeline stage, the branch prediction at said allocated storage in the branch prediction output queue, wherein the first through fourth pipeline stages are distinct pipeline stages.