Apparatus and method for entry allocation for a buffer resource utilizing an internal two cycle pipeline

Claim 2

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource to instruction information relating to instructions for storage into said buffer resource of a pipelined superscalar microprocessor, said instructions received during cycle n of said pipelined superscalar microprocessor, said apparatus comprising: allocation circuitry for generating, during a cycle n-1, a first list of vacant entries available for allocation to said instructions received during cycle n; a preliminary deallocation vector received during said cycle n and indicating vacant entries within said buffer resource; circuitry for receiving, during said cycle n, said first list of vacant entries available for allocation to said instructions received during cycle n; and mask circuitry for masking those entries of said preliminary deallocation vector that correspond to entries of said first list of vacant entries actually allocated to said instructions received during cycle n, so as to generate a modified deallocation vector; wherein said allocation circuitry, responsive to said modified deallocation vector, is also for generating, during said cycle n, a second list of vacant entries for instructions received during a cycle n+1.

Claim 3

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 1 wherein said buffer resource is a reservation station for containing instruction information pending execution within said pipelined superscalar microprocessor.

Claim 4

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 1 further comprising speculative stall circuitry operable during said cycle n-1 for generating a speculative stall signal responsive to said first list of vacant entries, said speculative stall signal indicating if said allocation circuitry failed to locate enough vacant entries to allocate to a maximum number of expected instructions to be received for said cycle n.

Claim 5

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 1 further comprising logic circuitry for determining which of said instructions received during said cycle n actually require allocation of an entry of said first list of vacant entries.

Claim 6

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 4 further comprising circuitry which stores instruction information into said buffer resource for those instructions received during said cycle n that actually require allocation of an entry of said first list of vacant entries available for allocation to said instructions received during said cycle n.

Claim 7

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 3 further comprising: logic circuitry for determining which of said instructions received during said cycle n actually require allocation of an entry of said first list of vacant entries; and stall circuitry for generating an allocation stall signal provided said logic circuitry and said speculative stall circuitry both indicate that an instruction of said cycle n requires allocation of a vacant entry and such entry is not available for allocation to said instruction.

Claim 8

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 6 further comprising a multiplexing circuit coupled to receive said preliminary deallocation vector and coupled to receive said modified deallocation vector and responsive to said allocation stall signal for supplying said allocation circuitry with said modified deallocation vector when said allocation stall signal is not asserted.

Claim 9

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 7 wherein said multiplexing circuit is for supplying said allocation circuitry with said preliminary deallocation vector when said allocation stall signal is asserted and wherein said allocation circuitry is responsive to said preliminary deallocation vector when said allocation stall signal is asserted.

Claim 10

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 2 wherein said preliminary deallocation vector is formulated based on instruction information validly stored within or dispatched from said reservation station just before said cycle n.

Claim 11

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource to instruction information relating to instructions for storage into said buffer resource of a pipelined superscalar microprocessor, said instructions received during cycle n of said pipelined superscalar microprocessor, said apparatus comprising: allocation circuitry for generating during a cycle n-1, a first list of vacant entries available for allocation to said instructions received during cycle n; a circuit for containing a preliminary deallocation vector received during cycle n, said preliminary deallocation vector indicating vacant entries within said buffer resource; and mask circuitry for receiving, during said cycle n, a second list of vacant entries actually allocated to said instructions received during said cycle n, said second list of vacant entries being derived from said first list of vacant entries; wherein said mask circuitry is also for masking those entries of said preliminary deallocation vector that correspond to entries of said second list of vacant entries actually allocated to said instructions received during said cycle n, so as to generate a modified deallocation vector; and wherein said allocation circuitry, responsive to a selected deallocation vector comprising either said modified deallocation vector or said preliminary deallocation vector, is also for generating a third list of vacant entries, during said cycle n, available for allocation to instructions received during a cycle n+1, said allocation circuitry comprising: (a) processing logic circuitry for examining bit sections of said selected deallocation vector for vacant entries and for each of said bit sections examined, generating a plurality of bitmaps associated with each of said bit sections; and (b) multiplexing logic circuitry coupled to receive said bitmaps and for multiplexing each of said bitmaps of said selected deallocation vector and generating therefrom said third list of vacant entries for instructions received during cycle n+1.

Claim 12

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource to instruction information relating to instructions for storage into said buffer resource of a pipelined superscalar microprocessor, said instructions received during cycle n of said pipelined superscalar microprocessor, said apparatus comprising: allocation circuitry for generating during a cycle n-1, a first list of vacant entries available for allocation to said instructions received during cycle n; a circuit for containing a preliminary deallocation vector received during cycle n, said preliminary deallocation vector indicating vacant entries within said buffer resource; and mask circuitry for receiving, during said cycle n, a second list of vacant entries actually allocated to said instructions received during said cycle n, said second list of vacant entries being derived from said first list of vacant entries; wherein said mask circuitry is also for masking those entries of said preliminary deallocation vector that correspond to entries of said second list of vacant entries actually allocated to said instructions received during said cycle n, so as to generate a modified deallocation vector; and wherein said allocation circuitry, responsive to a selected deallocation vector comprising either said modified deallocation vector or said preliminary deallocation vector, is also for generating a third list of vacant entries, during said cycle n, available for allocation to instructions received during a cycle n+1, said allocation circuitry comprising: (a) processing logic circuitry for examining bit sections of said selected deallocation vector for vacant entries and for each of said bit sections examined, generating a plurality of bitmaps associated with each of said bit sections; and (b) multiplexing logic circuitry coupled to receive said bitmaps and for multiplexing each of said bitmaps of said selected deallocation vector and generating therefrom said third list of vacant entries for instructions received during cycle n+1.

Claim 13

A two cycle pipeline apparatus for allocating vacant entries as described in claim 10 wherein each of said plurality of bitmaps contains not more than one bit set.

Claim 14

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 11 wherein said buffer resource is a reservation station for containing instruction information pending execution.

Claim 15

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 11 further comprising speculative stall circuitry operable during said cycle n-1 for generating a speculative stall signal responsive to said first list of vacant entries available for allocation to said instructions received during said cycle n that is generated by said allocation circuitry during said cycle n-1, said speculative stall signal indicating if said allocation circuitry failed to locate enough vacant entries for allocation to a maximum number of expected instructions received for said cycle n.

Claim 16

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 11 further comprising logic circuitry for determining which of said instructions received during cycle n actually require allocation of a vacant entry of said buffer resource.

Claim 17

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 13 further comprising: logic circuitry for determining which of said instructions received during said cycle n actually require allocation of a vacant entry of said buffer resource; and stall circuitry for generating an allocation stall signal provided said logic circuitry and said speculative stall circuitry both indicate that an instruction of said cycle n requires allocation of a vacant entry and said vacant entry is not available for allocation to said instruction.

Claim 18

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 15 further comprising a multiplexing circuit coupled to receive said preliminary deallocation vector and coupled to receive said modified deallocation vector and responsive to said allocation stall signal for supplying said allocation circuitry with said modified deallocation vector when said allocation stall signal is not asserted.

Claim 19

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 16 wherein said multiplexing circuit is for supplying said allocation circuitry with said preliminary deallocation vector when said allocation stall signal is asserted and wherein said allocation circuitry is responsive to said preliminary deallocation vector when said allocation stall signal is asserted.

Claim 20

A two cycle pipeline apparatus for allocating vacant entries of a buffer resource as described in claim 12 wherein said preliminary deallocation vector is formulated based on instruction information validly stored within or dispatched from said reservation station just before said cycle n.

Claim 21

A computer system comprising: a bus for providing a communication pathway; a memory coupled to said bus for storing instructions and program information; a user interface coupled to said bus for receiving information and for communicating information; and a pipelined superscalar processor coupled to said bus for executing instructions and processing data, said processor comprising a two cycle allocation circuit for allocating entries of a buffer resource for storing instruction information relating to instructions received during a cycle n into said buffer resource, said two cycle allocation circuit comprising: circuitry for generating, during cycle n-1, a first list of vacant entries available for allocation to said instructions received during cycle n; circuitry for receiving a preliminary deallocation vector during said cycle n, said preliminary deallocation vector for indicating vacant entries within said buffer resource; and mask circuitry for receiving, during said cycle n, a second list of vacant entries actually allocated to said instructions received during cycle n, said second list of vacant entries being derived from said first list of vacant entries; wherein said mask circuitry is also for masking those entries of said preliminary deallocation vector that correspond to entries of said second list of vacant entries actually allocated to said instructions received during said cycle n, so as to generate a modified deallocation vector; and wherein said circuitry for generating, responsive to said modified deallocation vector, is also for generating, during said cycle n, a third list of vacant entries available for allocation to instructions received during a cycle n+1.

Claim 22

A computer system comprising: a bus for providing a communication pathway; a memory coupled to said bus for storing instructions and program information; a user interface coupled to said bus for receiving information and for communicating information; and a pipelined superscalar processor coupled to said bus for executing instructions and processing data, said processor comprising a two cycle allocation circuit for allocating entries of a buffer resource for storing instruction information relating to instructions received during a cycle n into said buffer resource, said two cycle allocation circuit comprising: circuitry for generating, during cycle n-1, a first list of vacant entries available for allocation to said instructions received during cycle n; circuitry for receiving a preliminary deallocation vector during said cycle n, said preliminary deallocation vector for indicating vacant entries within said buffer resource; and mask circuitry for receiving, during said cycle n, a second list of vacant entries actually allocated to said instructions received during cycle n, said second list of vacant entries being derived from said first list of vacant entries; wherein said mask circuitry is also for masking those entries of said preliminary deallocation vector that correspond to entries of said second list of vacant entries actually allocated to said instructions received during said cycle n, so as to generate a modified deallocation vector; and wherein said circuitry for generating, responsive to said modified deallocation vector, is also for generating, during said cycle n, a third list of vacant entries available for allocation to instructions received during a cycle n+1.

Claim 23

A computer system as described in claim 19 wherein said buffer resource is a reservation station for containing instruction information pending execution.

Claim 24

A computer system as described in claim 19 further comprising speculative stall circuitry operable during said cycle n-1 for generating a speculative stall signal responsive to said first list of vacant entries available for allocation to instructions received during said cycle n that is generated by said circuitry for generating, said speculative stall signal indicating if said circuitry for generating failed to locate enough vacant entries to allocate to a maximum number of expected instructions to be received for said cycle n.

Claim 25

A computer system as described in claim 19 further comprising logic circuitry for determining which of said instructions received during said cycle n actually require allocation of a vacant entry of said buffer resource.

Claim 26

A computer system as described in claim 21 further comprising: logic circuitry for determining which of said instructions received during said cycle n actually require allocation of a vacant entry of said buffer resource; and stall circuitry for generating an allocation stall signal provided said logic circuitry and said speculative stall circuitry both indicate that an instruction of said cycle n requires a vacant entry and such entry is not available for said instruction.

Claim 27

A computer system as described in claim 23 further comprising a multiplexing circuit coupled to receive said preliminary deallocation vector and coupled to receive said modified deallocation vector and responsive to said allocation stall signal for supplying said allocation circuitry with said modified deallocation vector when said allocation stall signal is not asserted.

Claim 28

A computer system as described in claim 24 wherein said multiplexing circuit is for supplying said allocation circuitry with said preliminary deallocation vector when said allocation stall signal is asserted and wherein said allocation circuitry is responsive to said preliminary deallocation vector when said allocation stall signal is asserted.

Claim 29

A computer system as described in claim 20 wherein said preliminary deallocation vector is based on instruction information validly stored within or dispatched from said reservation station just before said cycle n.

Claim 30

In a pipeline superscalar processor, a two cycle pipeline method for allocating vacant entries of a buffer resource to instruction information relating to instructions received during a cycle n of said processor, said two cycle pipeline method comprising the steps of: generating a first list of vacant entries during a cycle n-1 available for allocation to instructions received during said cycle n; receiving a preliminary deallocation vector during said cycle n, said preliminary deallocation vector indicating vacant entries within said buffer resource; generating, during said cycle n, a second list of vacant entries actually allocated to said instructions received during said cycle n, said second list of vacant entries being derived from said first list of vacant entries; masking those entries of said preliminary deallocation vector that correspond to entries of said second list of vacant entries actually allocated to said instructions received during said cycle n, so as to generate a modified deallocation vector; and generating a third list of vacant entries during said cycle n available for allocation to instructions received during a cycle n+1 in response to a selected deallocation vector comprising either said preliminary deallocation vector or said modified deallocation vector.

Claim 31

In a pipeline superscalar processor, a two cycle pipeline method for allocating vacant entries of a buffer resource to instruction information relating to instructions received during a cycle n of said processor, said two cycle pipeline method comprising the steps of: generating a first list of vacant entries during a cycle n-1 available for allocation to instructions received during said cycle n; receiving a preliminary deallocation vector during said cycle n, said preliminary deallocation vector indicating vacant entries within said buffer resource; generating, during said cycle n, a second list of vacant entries actually allocated to said instructions received during said cycle n, said second list of vacant entries being derived from said first list of vacant entries; masking those entries of said preliminary deallocation vector that correspond to entries of said second list of vacant entries actually allocated to said instructions received during said cycle n, so as to generate a modified deallocation vector; and generating a third list of vacant entries during said cycle n available for allocation to instructions received during a cycle n+1 in response to a selected deallocation vector comprising either said preliminary deallocation vector or said modified deallocation vector.

Claim 32

A two cycle method of allocating vacant entries of a buffer resource as described in claim 27 wherein said buffer resource is a reservation station for containing instruction information pending execution.

Claim 33

A two cycle method of allocating vacant entries of a buffer resource as described in claim 27 further comprising the step of generating a speculative stall signal during said cycle n-1 responsive to said first list of vacant entries, said speculative stall signal indicating if said said first list of vacant entries contains less vacant entries than a maximum number of expected instructions to be received for said cycle n.

Claim 34

A two cycle method of allocating vacant entries of a buffer resource as described in claim 27 further comprising the step of determining which of said instructions received during said cycle n actually require allocation of a vacant entry of said buffer resource.

Claim 35

A two cycle method of allocating vacant entries of a buffer resource as described in claim 30 further comprising the step of storing instruction information into said buffer resource for those instructions received during said cycle n that actually require allocation of an entry of said first list of vacant entries available for allocated to said instructions received during said cycle n.

Claim 36

A two cycle method of allocating vacant entries of a buffer resource as described in claim 29 further comprising the steps of: determining which of said instructions received during said cycle n actually require allocation of a vacant entry of said buffer resource; and generating an allocation stall signal provided said step of determining which of said instructions received during said cycle n actually require allocation of a vacant entry of said buffer resource and said step of generating a speculative stall signal both indicate that an instruction of said cycle n requires allocation of a vacant entry and such a vacant entry is not available for allocation to said instruction.

Claim 37

A two cycle method of allocating vacant entries of a buffer resource as described in claim 32 wherein said step of generating said third list of vacant entries includes the step of multiplexing said preliminary deallocation vector and said modified deallocation vector so that said selected deallocation vector comprises said modified deallocation vector when said allocation stall signal is not asserted.

Claim 38

A two cycle method of allocating vacant entries of a buffer resource as described in claim 33 wherein said selected deallocation vector comprises said preliminary allocation vector when said allocation stall signal is asserted.

Claim 39

A two cycle method of allocating vacant entries of a buffer resource as described in claim 28 wherein said preliminary deallocation vector is based on instruction information validly stored within or dispatched from said reservation station just before said cycle n.