Apparatus and method for resolving dependencies among a plurality of instructions within a storage device

Claim 1

An apparatus for resolving dependencies among a plurality of instructions within a storage device, said storage device having a plurality of memory cells and sequentially storing said plurality of instructions in selected memory cells of said plurality of memory cells, said storage device having a read pointer indicating a next-empty memory cell of said plurality of memory cells, and a write pointer indicating an earliest-stored instruction of said plurality of instructions; each of said plurality of instructions effecting operational combination of a plurality of operands to determine a result, each of said plurality of operands being identified by a source indicator, said result being identified by a destination indicator; the apparatus generating an output signal, said output signal identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of a next-to-be-dispatched instruction, the apparatus comprising: a compare-hit means for comparing said source indicators with said destination indicators; said compare-hit means generating a compare-hit signal upon each concurrence of said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of an earlier-stored instruction of said plurality of instructions; a first enable means responsive to said read pointer and to said write pointer for generating a first enable signal for a first packet of instructions of said plurality of instructions, said first packet of instructions being defined by said read pointer and said write pointer; a first comparing means for generating a hit-enable signal for each concurrence of said compare-hit signal and said first enable signal; a second enable means responsive to said read pointer and to said hit-enable signal for generating a second enable signal for a second packet of instructions of said plurality of instructions, said second packet of instructions being defined by said read pointer and said hit-enable signal; and a second comparing means for generating said output signal for each concurrence of said second enable signal and said hit-enable signal.

Claim 2

An apparatus for resolving dependencies among a plurality of instructions within a storage device, said storage device having a plurality of memory cells and sequentially storing said plurality of instructions in selected memory cells of said plurality of memory cells, said storage device having a read pointer indicating a next-empty memory cell of said plurality of memory cells, and a write pointer indicating an earliest-stored instruction of said plurality of instructions; each of said plurality of instructions effecting operational combination of a plurality of operands to determine a result, each of said plurality of operands being identified by a source indicator, said result being identified by a destination indicator; the apparatus generating an output signal, said output signal identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of a next-to-be-dispatched instruction, the apparatus comprising: a compare-hit means for comparing said source indicators with said destination indicators; said compare-hit means generating a compare-hit signal upon each concurrence of said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of an earlier-stored instruction of said plurality of instructions; a first enable means responsive to said read pointer and to said write pointer for generating a first enable signal for a first packet of instructions of said plurality of instructions, said first packet of instructions being defined by said read pointer and said write pointer; a first comparing means for generating a hit-enable signal for each concurrence of said compare-hit signal and said first enable signal; a second enable means responsive to said read pointer and to said hit-enable signal for generating a second enable signal for a second packet of instructions of said plurality of instructions, said second packet of instructions being defined by said read pointer and said hit-enable signal; and a second comparing means for generating said output signal for each concurrence of said second enable signal and said hit-enable signal.

Claim 10

An apparatus for resolving dependencies among a plurality of instructions within a storage device, said storage device having a plurality of memory cells and sequentially storing said plurality of instructions in selected memory cells of said plurality of memory cells, each of said plurality of memory cells including a plurality of tags, each of said plurality of tags having a first value indicating enablement and a second value indicating non-enablement; said storage device having a read pointer indicating a next-empty memory cell of said plurality of memory cells, an a write pointer indicating an earliest-stored instruction of said plurality of instructions; each of said plurality of instructions effecting operational combination of a plurality of operands to determine a result, each of said plurality of operands being identified by a source indicator, said result being identified by a destination indicator; the apparatus setting an identification tag, said identification tag identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of a next-to-be-dispatched instruction, the apparatus comprising: a compare-hit means for comparing said source indicators with said destination indicators; said compare-hit means setting a compare-hit tag at said first value for a respective earlier-stored instruction of said plurality of instructions when there exists concurrence of said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of said respective earlier-stored instruction; a first enable means responsive to said read pointer and to said write pointer for setting a first enable tag at said first value for each instruction in a first packet of instructions of said plurality of instructions, said first packet of instructions comprising all instructions of said plurality of instructions stored intermediate said read pointer and said write pointer; a first comparing means for setting a hit-enable tag at said first value for each said instruction of said first packet of instructions for which said compare-hit tag and said first enable tag are set at said first value; a second enable means responsive to said read pointer and to said hit-enable tag for setting a second enable tag at said first value for each instruction in a second packet of instructions of said plurality of instructions, said second packet of instructions comprising all instructions of said first packet of instructions stored intermediate said read pointer and the earliest-stored instruction of said first packet of instructions having said hit-enable tag set at said first value; and a second comparing means for setting said identification tag for each instruction for which said second enable tag and said hit-enable tag are set at said first value.

Claim 11

An apparatus for resolving dependencies among a plurality of instructions within a storage device, said storage device having a plurality of memory cells and sequentially storing said plurality of instructions in selected memory cells of said plurality of memory cells, each of said plurality of memory cells including a plurality of tags, each of said plurality of tags having a first value indicating enablement and a second value indicating non-enablement; said storage device having a read pointer indicating a next-empty memory cell of said plurality of memory cells, an a write pointer indicating an earliest-stored instruction of said plurality of instructions; each of said plurality of instructions effecting operational combination of a plurality of operands to determine a result, each of said plurality of operands being identified by a source indicator, said result being identified by a destination indicator; the apparatus setting an identification tag, said identification tag identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of a next-to-be-dispatched instruction, the apparatus comprising: a compare-hit means for comparing said source indicators with said destination indicators; said compare-hit means setting a compare-hit tag at said first value for a respective earlier-stored instruction of said plurality of instructions when there exists concurrence of said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of said respective earlier-stored instruction; a first enable means responsive to said read pointer and to said write pointer for setting a first enable tag at said first value for each instruction in a first packet of instructions of said plurality of instructions, said first packet of instructions comprising all instructions of said plurality of instructions stored intermediate said read pointer and said write pointer; a first comparing means for setting a hit-enable tag at said first value for each said instruction of said first packet of instructions for which said compare-hit tag and said first enable tag are set at said first value; a second enable means responsive to said read pointer and to said hit-enable tag for setting a second enable tag at said first value for each instruction in a second packet of instructions of said plurality of instructions, said second packet of instructions comprising all instructions of said first packet of instructions stored intermediate said read pointer and the earliest-stored instruction of said first packet of instructions having said hit-enable tag set at said first value; and a second comparing means for setting said identification tag for each instruction for which said second enable tag and said hit-enable tag are set at said first value.

Claim 12

A method for resolving dependencies among a plurality of instructions within a storage device, said storage device having a plurality of memory cells and sequentially storing said plurality of instruction in selected memory cells of said plurality of memory cells, said storage device having a read pointer indicating a next-empty memory cell of said plurality of memory cells, and a write pointer indicating an earliest-stored instruction of said plurality of instructions; each of said plurality of instructions effecting operational combination of a plurality of operands to determine a result, each of said plurality of operands being identified by a source indicator, said result being identified by a destination indicator; the method identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of a next-to-be-dispatched instruction, the method comprising the steps of: (1) comparing each said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of each earlier-stored instruction of said plurality of instructions; (2) generating a compare-hit signal upon each concurrence of said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of an earlier-stored instruction of said plurality of instructions; (3) generating a first enable signal responsive to said read pointer and to said write pointer for a first packet of instructions of said plurality of instructions, said first packet of instructions being defined by said read pointer and said write pointer; (4) comparing said compare-hit signal with said first enable signal; (5) generating a hit-enable signal for each concurrence of said compare-hit signal and said first enable signal; (6) generating a second enable signal responsive to said read pointer and to said hit-enable signal for a second packet of instructions of said plurality of instructions, said second packet of instructions being defined by said read pointer and said hit-enable signal; (7) comparing said second enable signal with said hit-enable signal; and (8) generating an output signal for each concurrence of said second enable signal and said hit-enable signal, said output signal identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of said next-to-be-dispatched instruction.

Claim 13

A method for resolving dependencies among a plurality of instructions within a storage device, said storage device having a plurality of memory cells and sequentially storing said plurality of instruction in selected memory cells of said plurality of memory cells, said storage device having a read pointer indicating a next-empty memory cell of said plurality of memory cells, and a write pointer indicating an earliest-stored instruction of said plurality of instructions; each of said plurality of instructions effecting operational combination of a plurality of operands to determine a result, each of said plurality of operands being identified by a source indicator, said result being identified by a destination indicator; the method identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of a next-to-be-dispatched instruction, the method comprising the steps of: (1) comparing each said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of each earlier-stored instruction of said plurality of instructions; (2) generating a compare-hit signal upon each concurrence of said respective source indicator in said next-to-be-dispatched instruction with said destination indicator of an earlier-stored instruction of said plurality of instructions; (3) generating a first enable signal responsive to said read pointer and to said write pointer for a first packet of instructions of said plurality of instructions, said first packet of instructions being defined by said read pointer and said write pointer; (4) comparing said compare-hit signal with said first enable signal; (5) generating a hit-enable signal for each concurrence of said compare-hit signal and said first enable signal; (6) generating a second enable signal responsive to said read pointer and to said hit-enable signal for a second packet of instructions of said plurality of instructions, said second packet of instructions being defined by said read pointer and said hit-enable signal; (7) comparing said second enable signal with said hit-enable signal; and (8) generating an output signal for each concurrence of said second enable signal and said hit-enable signal, said output signal identifying the most-recently stored instruction of said plurality of instructions having said destination indicator matching a respective said source indicator of said next-to-be-dispatched instruction.