Patent ID: 6704856
Filing Date: 2004-03-09
Classification: G06F

Abstract:
A method of compacting an instruction queue in a processor, the queue comprising a plurality of rows for holding instructions and associated validity indicators, in which instructions may be removed from the queue out of sequence, the method comprising:for each row in the queue, responsive to validity indicators associated with rows below and including said row, determining a flat vector count of the number of invalid instructions below and including said row; determining a select value, by forming a diagonal from N counts corresponding to N rows above and including the present row, for a predetermined value N, wherein N is a maximum of new instructions which can enter the queue during any given cycle, limiting each count to N, and logically ANDing each diagonal bit with a set of validity indicators to form the present row's select value, each ANDed diagonal bit and corresponding validity indicator being associated with a common row, selecting one of the N rows responsive to the select value, and moving an instruction held in the selected row to the present row; and further comprising, for each row: determining a modified select value, responsive to counts for the Nâˆ’1 rows above and including the present row, and responsive to the validity indicators associated with the Nâˆ’1 rows, by forming a modified diagonal from the Nâˆ’1 counts corresponding to the Nâˆ’1 rows above and including the present row, and logically ANDing each diagonal bit, except for a most significant diagonal bit, with a set of validity indicators to form the present row's modified select value, each ANDed diagonal bit and validity indicator being associated with a common row; selecting one of the N rows responsive to the modified select value; and moving a validity indicator held in the selected row to the present row.