Patent ID: 7409520
Filing Date: 2008-08-05
Classification: G06F

Abstract:
1. A method for thread allocation in multi-stage, multi-thread digital processing, comprising: circularly generating an address in a sequence of n addresses corresponding to threads i=1, 2 . . . n, each address in the sequence enabling access to the contents of a different memory location, each memory location containing an instruction for a different thread i, so that each address in the sequence corresponds to a different thread i in a sequence of threads in an n thread process; determining if execution of an ith thread corresponding to the generated address in the sequence of addresses is stalled; selecting the memory location corresponding to the generated ith address if execution of the ith thread is not stalled; determining and selecting a memory location corresponding to a complementary thread instruction if execution of the ith thread is stalled; wherein the complementary thread of a thread i is defined to be the thread (i+n/2) modulo(n), where is an even number greater than 3 and where n is the number of addresses in the sequence of addresses from which a thread is chosen; and submitting for execution the thread instruction from the selected memory location.