US 8,589,666 B2Granted

Elimination of stream consumer loop overshoot effects

AssigneeSRC Computers, Inc.

InventorJeffrey Hammes

Life of this patent

Estimating the term…

Loading patent…

Abstract

A reconfigurable processor invoking data stream pipelining is configured to associate a restore buffer with each incoming data stream. The buffer is configured to be of sufficient size to maintain data values dispatched to a loop so as to restore values fetched and lost due to loop overshoots. The restore buffer stores the values that were recently fetched from the buffer to the loop. To determine how many data values should be restored, the loop counts the number of the data values it takes from each data stream and the number of valid loop iterations that take place. Once a loop termination is detected, the loop halts the fetching of values from the restore buffer and compares, for each stream, the number of loop iterations with the number of values fetched. The difference is the number of extra values that were taken from the restore buffer and are restored.

Claims22

Dependent claims

A computer implemented method for eliminating loop overshoot effects in a reconfigurable processor, the method comprising:

configuring in a field programmable gate array a dataflow pipelined structure, wherein the dataflow pipelined structure includes a restore buffer in communication with, and interposed between, a First-In First-Out (FIFO) buffer and an iteration loop structure;
fetching a data value from the restore buffer to the iteration loop structure, wherein the restore buffer replaces the data value fetched from the restore buffer with another data value from the FIFO buffer and wherein the restore buffer is configured to continually maintain a number of data values, the number of data values continually maintained based on the iteration loop structure of the dataflow pipeline structure;
maintaining an accounting of how many data values are fetched from the restore buffer to the iteration loop structure;
executing an iterative computation process on the iteration loop structure wherein each iteration failing to terminate the iterative computation process is a valid loop iteration;
counting the valid loop iterations of the iterative computation process and preserving a total number of valid loop iterations;
identifying termination of the iterative computation process;
halting fetching data values from the restore buffer based on identification of termination of the iterative computational process;
and
restoring data values to the restore buffer that were fetched from the restore buffer between termination of the iterative computational process and halting fetching data values from the restore buffer based on identification of termination of the iterative computational process.

6 more elements

A reconfigurable computer system including a dataflow pipelined structure that eliminates loop overshoot effects, the system comprising:

a first buffer;
a second buffer;
a multi-adaptive processor, wherein the multi-adaptive processor includes field programmable gate arrays;
and
a multi-adaptive processor compiler capable of creating a plurality of code portions executable on the multi-adaptive processor, wherein one of the code portions is operable to create a pipelined data stream structure having at least one pipeline data stream, for each pipeline data stream the pipelined data stream structure comprising:
a data producer coupled to the first buffer, wherein the first buffer stores data values produced by the data producer;
a data consumer in communication with the first buffer, the data consumer having a loop structure, wherein the loop structure is configured to have a Synchronization node that determines a loop iteration value and a data fetch value, and a loop Terminate node that determines whether a loop termination condition has been reached, wherein execution of an iterative computation process on the loop structure that fails to terminate the iterative computation process is a valid loop iteration, and
wherein the second buffer is interposed between the first buffer and the loop structure of the data consumer and is configured to continually maintain a number of data values, the number of data values based on the loop structure, so as to restore data values from the at least one pipelined data stream mistakenly sent to the loop structure after the loop termination condition has been reached.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/456,466Filed 10 Jul 2006
Published: US 2008/0010444 A110 Jan 2008
Granted: 19 Nov 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 9/3863
Recovery, e.g. branch miss-prediction, exception handling: using multiple copies of the architectural state, e.g. shadow registers
G06F 8/456
Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions: parallelism detection
G06F 9/325
For non-sequential address: for loops, e.g. loop detection or loop counter
G06F 9/383
Operand accessing: operand prefetching