Method and apparatus for queue issue pointer

[0002] The field of invention relates to processor technology generally; and more specifically, to methods and apparati that may be used for an instruction fetch unit.

[0003] Processors are used in computing systems and are implemented within a semiconductor chip. Processors execute instructions in order implement a software program. The instructions used to implement a software program are stored in a memory structure (e.g., an L1 cache, L2 cache and/or system memory) and fetched by the processor prior to their being executed. Each instruction has a corresponding address that is used to obtain the instruction from a particular memory structure location.

[0004] FIG. 1 shows a circuit 100 associated with the portion of a processor that fetches instructions. Array 108 has a series of locations 101₀₀through 101_nthat each store an instruction address (e.g., instruction addresses ADDRESS₁, ADDRESS₂or ADDRESS₃). Array 108 serves as a temporary holding place for up to n instruction addresses. The instruction addresses waiting in array 108 have been determined by other logic (not shown in FIG. 1) that determines or otherwise identifies which instructions (from the range of instructions supported by the processor) should be fetched by the processor.

[0005] Each instruction address within array 108 has a corresponding RABid value. The RABid value is data structure used to identify which array location 101₀₀through 101_na particular instruction address is stored in. For example, ADDRESS₁has a corresponding RABid value of “02” which reflects the fact that ADDRESS₁is stored in array location 101₀₂. Similarly, ADDRESS₂has a corresponding RABid value of “04” which reflects the fact that ADDRESS₂is stored in array location 101₀₄and ADDRESS₃has a corresponding RABid value of “00” which reflects the fact that ADDRESS₃is stored in array location 101₀₀.

[0006] For each address offered at input node 102b, the address's corresponding RABid value is used to control which array location 101₀₀through 101_nwill be used to store the address. For example, as seen in FIG. 1, the RABid value is used to select (via the select node 102a) which multiplexor 102 output is enabled for a particular address at input 102b. As another example (not shown in FIG. 1), the multiplexor 102 and its outputs 102ccould be respectively replaced with write logic and address/data buses. In this example, the RABid value is used to generate a write address that corresponds to the proper array location. The address is written into the proper array location via the address/data buses.

[0007] Eventually an address within array 108 “issues” as an instruction fetch. That is, when the proper moment arrives for an address within array 108 to be used as an instruction fetch from the processor, the proper address is read or otherwise received from its location within array 108 and directed to a memory structure address bus. Array control circuit 107 determines when a particular address is to be issued from the array 108. That is, array control circuit 107 controls: 1) which address is read from array 108; and 2) when the particular address is read from the array 108.

[0008] As a basic example, array control circuit 107 stores each “active” RABid (i.e., a RABid currently having an address in its corresponding array 108 location) in a first-in-first-out (FIFO) queue 103. The queue 103 typically has a depth 106 equal to the number “n” of array 108 locations. This allows the array control circuit 107 to successfully order the issuing of instruction addresses from array 108 in instances where array 108 is filled.

[0009] The RABids are stored in the queue 103 in the order in which they are used to store addresses in array 108. For example, if ADDRESS, was first to arrive at input 102bfollowed by ADDRESS₂and then ADDRESS₃, the queue 103 stores the RABids in the following order: RABid:02, RABid:04, RABid:00. Thus RABid:02 is serviced before RABid:04 and RABid:04 is serviced before RABid:00.

[0010] When a RABid is serviced from queue 103, its value is used to issue the RABid's corresponding instruction address. That is, RABid:02 will be used to issue ADDRESS₁from array location 101₂, RABid:04 will be used to issue ADDRESS₂from array location 101₀₄and RABid:00 will be used to issue ADDRESS₃from array location 101₀₀. This is accomplished by directing each RABid value from queue 103 to a unit that controls the issuing of address from array 108. For example, as seen in FIG. 1, the RABid is coupled to the selection control 104aof a multiplexor 104. Alternatively (not shown in FIG. 1), the multiplexor 104 and its inputs 104a, bcould be respectively replaced with read logic and address/data buses. In this example, the RABid value from queue 103 is used to generate a read address that corresponds to the proper array location. The address is read from the proper array location via the address/data buses. The number of outstanding issues are controlled by queue control circuit 105. When an instruction is successfully fetched, the RABid value used for its address is returned to array control circuit 107. Thus, if the current number of outstanding issues is at its maximum allowable value, the queue control circuit 105 can trigger the servicing of the next RABid in queue 103 upon the return of a previously serviced RABid value.

[0011] The present invention is illustrated by way of example, and not limitation, in the Figures of the accompanying drawings in which:

[0012] FIG. 1 shows an instruction fetch unit.

[0013] FIG. 2ashows an embodiment of an array control circuit 207 that may be used for the instruction fetch unit shown in FIG. 1.

[0014] FIG. 2bshows the state of the queue 203 shown in FIG. 2aat two different times t1 and t2.

[0015] FIG. 2cshows an embodiment of how the CAM 220 of FIG. 2afinds a match between a first input vector and the contents of the CAM 220.

[0016] FIG. 2dshows an embodiment of how the CAM 220 of FIG. 2afinds a match between a second input vector and the contents of the CAM 220.

[0017] FIG. 3ashows a method of cycling the array control circuit 207 of FIG. 2a.

[0018] FIG. 3bshows a methodology for the array control circuit of FIG. 2a.

[0019] FIG. 4 shows a methodology for determining a tail pointer for a queue.

[0020] FIG. 5ashows a methodology for determining an issue pointer for a queue.

[0021] FIG. 5bshows a methodology for determining a vector indicative of which data structures within a queue desire to be issued from the queue.

[0022] FIG. 5cshows an embodiment of an array control circuit configured to perform pre-emptive queuing.

[0023] FIG. 5dshows a methodology that may be used for another pre-emptive queuing embodiment.

[0024] FIG. 6 shows a transistor level design that may be used for the CAM 220 shown in FIG. 2a.

[0025] A method of generating an issue pointer for issuing data structures from a queue, comprising generating a signal that indicates where one or more of the data structures within the queue that desire to issue are located within the queue. Then, checking the signal at a queue location pointed to by an issue pointer. Then, incrementing the position of the issue pointer if a data structure has not shifted into the queue location since the previous issue and if the issue pointer is pointing to the location having issued on the previous queue issue or holding the issue pointer position if a data structure has shifted into the location since the previous issue and if the issue pointer is pointing to the location having issued on the previous queue issue.

[0026] These and other embodiments of the present invention may be realized in accordance with the following teachings and it should be evident that various modifications and changes may be made in the following teachings without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense and the invention measured only in terms of the claims.

[0027] FIG. 2ashows an embodiment of an array control circuit 207 that may be used for the array control circuit 107 of FIG. 1. Comparing the array control circuits 107, 207 of FIGS. 1 and 2a, the RABid input 210 to the array corresponds to RABid input 110 from the array. Also, the RABid output 204ato the array corresponds to the RABid output 104ato the array and the returned RABid 209 corresponds to the returned RABid 109.

[0028] Queue 203 corresponds to queue 103. Queue 203 is an arrangement of storage cells 203₀through 203₇such as register locations or memory locations. Note that in the particular example of FIG. 2a, queue 203 has eight cells 203₀through 203₇. Consistent with designer preference, however, other embodiments may have queue 203 depths greater than or less than eight cells.

[0029] As discussed in more detail ahead, array control circuit 207 may be configured to issue RABids according to methods more complicated than the simple FIFO method discussed with respect to the array control circuit 107 of FIG. 1. Because of this, RABids sent from the array (via input 210) for entry to the queue 203 are written into a particular cell according to the current value of a tail pointer. That is, the tail pointer “points” to the proper queue 203 cell that an incoming RABid from the array should be written into. The write address logic 211 accepts the tail pointer value from the tail pointer logic 213 in order to write the incoming RABid to the proper queue 203 cell along write data bus 215.

[0030] Furthermore, because array control circuit 207 may be configured to issue RABids according to methods more complicated than the simple FIFO method discussed with respect to the array control circuit 107 of FIG. 1, RABids are issued from queue 203 according to the value of an issue pointer that “points” to the cell holding the RABid to be issued. In order to issue a RABid from queue 203 to the array, read address logic 212 establishes the proper address on read address bus 214.

[0031] Note that the read address logic 212 accepts the current value of the issue pointer from the issue pointer logic 217 in order to determine the proper read address. When the proper address is established on read address bus 214, the RABid appears on the read data bus 234 and is directed toward the array at output 204a. Note that alternate architectural schemes may be employed such as a bi-directional data bus (i.e., read data bus 234 and write data bus 215 are merged together as a single data bus) or a multiplexor scheme similar to the multiplexor scheme used to write and read to/from array 108 of FIG. 1.

[0032] Consistent with the operation of a queue, queue 203 can “shift up” the contents of a cell when a RABid has successfully issued. Referring to FIGS. 2aand 2b, note that FIG. 2bshows at Table 1 a queue 203 state at a particular time t1. At time t1, the queue has already issued both RABid:05 and RABid:00. Note that RABid:00 has issued before RABid:03. This is possible since array control circuit 207 can issue RABids beyond a simple FIFO technique. For example, RABid:00 may correspond to a “high priority” instruction fetch that needs to issue before RABid:03.

[0033] The RABids within queue 203 that have not issued as of time t1 are indicated by the “don't want to issue” vector 240a. The “don't want to issue” vector (which is the logical inverse of “want to issue” wti) is a vector that records the status of those RABids that need to issue and those RABids that do not need to issue. RABids that have issued to the array no longer need to issue. Hence, it may be said that such RABids “don't want to issue”. As seen in the “don't want to issue” vector 240a, RABid:05 and RABid:00 are given logical high values to reflect the fact that both RABids issued as of time t1. Also, since RABid:01, RABid:02 and RABid:04 are currently not in use, these RABids do not need to issue either.

[0034] Thus, as seen in the “don't want to issue” vector 240a, the values for RABid:01, RABid:02 and RABid:04 also have a logical high value. The remaining RABids within the queue 203 still need to issue and may be said to “want to issue”. Hence, as seen in the “don't want to issue” vector 240a, RABid:03, RABid:07 and RABid:06 are each given logical low values. The “don't want to issue” vector, as described in more detail further ahead, is used to support sophisticated issuing techniques beyond a simple FIFO.

[0035] A RABid is deemed to have successfully issued when it returns to array control circuit 207 (which is reflected in the appearance of a signal at the RABid return vector bus 224). A RABid returns to the array control circuit 207 after it has been used to obtain an address from the array (108 of FIG. 1) that subsequently fetches an instruction from a memory structure (e.g., L1 cache, L2 cache or system memory).

[0036] When a RABid returns to the array control circuit 207 (i.e., when it is has been deemed successfully issued) it may be removed from queue 203. In the example of FIG. 2b, assume the issued RABid:00 returns to array control circuit 207 between times t1 and t2. The queue 203 state at time t2 is tabulated in Table 2. At time t2, the RABid:00 value is removed from the queue by “shifting up” all the RABids beneath it. That is, comparing the queue states of times t1 and t2, RABid:07 and RABid:06 have each shifted up one cell location. RABid:07 has shifted up from cell 203₃to 203₂and RABid:06 has shifted up from cell 203₄to 203₃. Referring to FIG. 2a, arrows 230₀through 230₆indicate the capability of the queue 203 to shift the contents of a cell into the cell just above it. For example, arrow 230₄indicates cell 203₅can shift its contents into cell 203₄just above it.

[0037] Thus, by way of the shifting up technique discussed above, the queue 203 may effectively rid itself of a RABid that has successfully issued to the array. As seen in FIG. 2a, cells 203₀through 203each have a corresponding shiftup input SHIFTUP0 through SHIFTUP6. In the example of FIG. 2a, when a logic high is presented at a particular shiftup input, the contents from the cell beneath the activated shiftup input are shifted into the cell having the activated input. For example, if SHIFTUP6 is logic high, the contents of cell 203₇are shifted into cell 203₆(i.e., the pathway represented by arrow 230₆is enabled).

[0038] In alternate embodiments, shiftup inputs may be used to shift the contents of an activated cell into the cell above it. For example, if SHIFTUP6 was logic high, the contents of cell 203₆would be shifted into cell 203₅. In such an alternate embodiment, the SHIFTUP0 input may be removed from cell 203₀and a SHIFTUP7 input should be added to cell 203₇.

[0039] The shiftup inputs SHIFTUP0 through SHIFTUP6, as shown in FIG. 2a, together form the shiftup bus 216. Shiftup bus 216 is the collection of shiftup inputs SHIFTUP0 through SHIFTUP6. The shiftup bus 216 is produced by logic structure 221 associated with queue control circuit 205. Queue control circuit 205 approximately corresponds to the queue control circuit 105 of FIG. 105. Queue control circuit 205 is different than queue control circuit 105 of FIG. 1, however, since queue control circuit 105 can only implement a simple FIFO.

[0040] Associated with queue control circuit 205 is a content addressable memory (CAM) 220. CAMs are used to identify a match between an input to a cell and a value stored in the cell. In an embodiment, CAM cells 220₀through 220₇are respectively coupled to queue cells 203₀through 203₇. Respectively coupled means: CAM cell 220₀is coupled to queue cell 203₀, CAM cell 220₁is coupled to queue 203₁, CAM cell 220₂is coupled to queue cell 203₂, etc.

[0041] In one embodiment, the CAM cells 220₀through 220₇are not distinguishable from the queue cells 203₀through 203₇. That is, queue 203 is physically merged with CAM 220 such that a single cell is able to perform both the RABid queuing associated with queue 203 and the match identification performed by CAM 220. In alternate embodiments, CAM cells 220₀through 220₇are distinguishable from the queue cells 203₀through 203₇. That is, the cells associated with CAM 220 are separate entities than the cells associated with queue 203. In these alternate “distinguishable” cell embodiments, in order to perform match identification, the CAM cells 220₀through 220₇may be configured to hold a duplicate copy (respectively) of the RABid values within queue 203; or the CAM cells 220₀through 220₇may be configured to sense or otherwise use (respectively) the RABid values within queue 203.

[0042] The coupling between the queue 203 cells and CAM 220 cells allows the CAM 220 to find matches between the inputs presented to the CAM 220 (such as the inputs associated with the “don't want to issue” vector bus 222 and the RABid return vector bus 224) and the contents within each of the queue cells 203₀through 203₇. FIG. 2cprovides an example.

[0043] Referring to Table 3 of FIG. 2c, note that each RABid value is presented with an embodiment of its binary representation. As seen in Table 3, RABid:00 is actually represented by “00000001”, RABid:01 is actually represented by “00000010”, etc. Table 4 shows the queue state displayed in Table 1 of FIG. 2bimplemented with the RABid binary values shown in Table 3 of FIG. 2c. Note that since each queue cell 203₀through 203₇is respectively coupled to each CAM cell 220₀through 220₇as discussed above, Table 4 lists the CAM 220 cell contents along with the queue 203 cell contents. Note that each queue/CAM cell is eight bits deep since, in this embodiment, each RABid is represented with eight bits.

[0044] Recall from FIG. 2bthat in between time t1 and time t2, the RABid:00 value was returned (causing the “shiftup” discussed above). Upon arrival of a returned RABid value, a RABid return vector is formed. The RABid vector 241 a formed after the arrival of the RABid:00 value is shown in FIG. 2c. The RABid return vector 241ais organized similar to the “don't want to issue” vector 240aof FIG. 2b. That is, each vector component corresponds to a RABid value (e.g., the rightmost vector component corresponds to RABid:00 while the leftmost vector component corresponds to RABid:07). Note that the particular RABid return vector 241ashown in FIG. 2ccorresponds to the return of the RABid:00 value since the vector component corresponding to RABid:00 (the rightmost) is a logic high.

[0045] The RABid return vector 241ais also shown at the bottom of Table 4 to indicate its use as an input to the CAM. Note that in FIG. 2a, the RABid return vector bus 224 presents the RABid return vector to each cell 220₀through 220₇. Each cell 220₀through 220₇in the CAM 220 checks to see if the RABid return vector 241 a matches the contents of the cell. Because each component of the RABid return vector 241 a corresponds to a RABid value (and because the RABid values are represented as shown in Table 3), each CAM cell only needs to check for a match of logic high values between the input vector 241 a and the contents of the cell. Such a match 242 is shown in FIG. 2cbetween the RABid return vector and the contents of CAM cell 220₂. Note the contents of CAM cell 220₂corresponds to RABid:00 which demonstrates the CAM 220 properly matched the input vector with the contents of the CAM 220.

[0046] Referring to FIG. 2a, a match between the RABid return vector (presented on the RABid return vector bus 224) and the content of a particular CAM 220 cell produces a match signal at the CAM output. In FIG. 2a, the “done” output of a CAM cell indicates a match. Note that in the particular embodiment of FIG. 2a, the “done” output from the CAM itself is active low. To correct for the active low, an inverter may be placed between the CAM output and logical structure 221.

[0047] Logical structure 221 is configured to indicate those queue 203 cells that should have present cell data written over by lower cell data. Referring to FIGS. 2a, 2band 2c, recall that the return of RABid:00 caused the shifting up activity of queue cells 203₂, 203₃and 203₄(comparing Tables 1 and 2 of FIG. 2b). Table 4 of FIG. 2cshows the CAM can properly identify that the returned RABid value (RABid:00) is located in queue/CAM cell 203₂/220₂. The “done” output from CAM cell 220₂will produce logic high values at the logical structure 221 outputs SHIFTUP2 through SHIFTUP6. These, in turn, properly rewrite the contents of each of the queue cells 203₂through 203₆with the data beneath each of the these cells.

[0048] Recall from the discussion FIG. 2bthat the RABids within queue 203 that need to issue at any time may be indicated by the “don't want to issue” vector 240a. As discussed, the “don't want to issue” vector (which is the logical inverse of “want to issue” wti) is a vector that records the status of those RABids that need to issue and those RABids that do not need to issue. Referring to FIG. 2a, the “don't want to issue” vector is presented on the “don't want to issue” vector bus 222 by the issue pointer logic 217.

[0049] The “don't want to issue” vector bus 222 couples the “don't want to issue” vector to each CAM cell 220₀through 220₇. Similar to the approach described just above with respect to the RABid return vector, each CAM cell 220₀through 220₇is configured to identify a match between the “don't want to issue” vector and the contents of the cell. An example is shown in FIG. 2d.

[0050] In the example of FIG. 2d, the queue 203 is full. That is, every queue 203 cell holds a RABid value. Because the queue 203 state is mirrored in the CAM 220, the CAM contents 220dof FIG. 2dare also full. FIG. 2dpresents the contents 270 of Table 3 (originally shown back in FIG. 3) so the reader can easily correlate the contents 220dof the CAM with the particular order of RABid values that the CAM holds in this example (i.e., RABid:06, RABid:03, RABid:00, etc.).

[0051] In the example of FIG. 2d, RABid:04 and RABid:07 do not want to issue. The “don't want to issue” vector, which is configured to indicate that RAB:04 and RAB:07 do not want to issue, is shown atop the CAM contents 220dso that the identification of a match is easily visualized. The CAM identifies which cells have the RABid values that do not want to issue. In the particular example of FIG. 2d, cells 220₃and 220₄hold RABid:04 and RABid:07. The CAM properly identifies matches 271 and 272 and presents the logical inverse of the “issue pointer issued” (ipi) vector. That is, the CAM cells 220₃, 220₄that identify a match produce an active low output while the all other CAM cells produce an active high output. This effectively produces an “issue pointer not issued” vector 223 as an output.

[0052] Note that the CAM embodiment discussed so far employs active low signaling for the input vectors and output vectors. This is due to a transistor level design used to identify a match within the CAM. The CAM's transistor level design for this CAM embodiment is discussed in more detail further ahead. It is important to note, however, that alternate embodiments may employ active high signaling at the CAM's inputs as well as the CAM's outputs.

[0053] Referring now to FIG. 2a, whether active high or active low signaling is used, the CAM output 223 that is generated by the comparison of the CAM's contents with the “don't want to issue” (or, alternatively, “want to issue”) vector will distinguish which queue cells have RABid values that have issued and which queue cells have RABid values that have not issued. This information is used by the issue pointer logic 217 to properly determine the next issue pointer value.

[0054] FIGS. 3aand 3bshow a methodology for the operation of the array control circuit. FIG. 3ashows an embodiment of the cycling for the array control circuit while FIG. 3bshows a method flow embodiment. Referring to FIGS. 2a, 3aand 3b, during a first cycle time 350: 1) new “don't want to issue” and RABid return vectors are presented to the CAM 220 on their respective bus 222, 224; and 2) a RABid from input 210 (if any) is written 323 into the queue 203 according to the position of the tail pointer.

[0055] During a second cycle time 351: 1) a RABid is read from the queue 203 and sent 326 from output 204ato the array; 2) the CAM 220 updates its outputs 302, 304 (in response to the new inputs presented during the first cycle 351) which may effect the signals on the “issue pointer not issued” bus 223 and the shiftup bus 216; and 3) a new RABid is accepted 325 at input 210 (if any).

[0056] During a third cycle time 352: 1) the issue pointer logic 217 calculates 303 a new issue pointer and a new “don't want to issue” vector in response to the new “issue pointer not issued” 223 and shiftup 216 bus information; 2) the queue 203 (and CAM 220) are shifted up 306 in response to the new shiftup bus 216 information (if any); and 3) the tail pointer logic 213 calculates 307 a new tail pointer in light of a new RABid input from the array (if any) and the updated shiftup bus 216 information (if any).

[0057] FIG. 4 shows a methodology for the operation of the tail pointer logic 213. The tail pointer should increment as the queue 203 becomes more populated with RABids and decrement as RABids are cleared from the queue 203 via the shiftup procedure. That is, the tail pointer is responsive to both the occurrence of a shiftup as well as the entry of another RABid at input 210.

[0058] The methodology of FIG. 4 indicates this responsiveness. In FIG. 4, the tail pointer decrements 401 (i.e., the tail pointer moves up toward queue cell 203₀) if a shiftup occurs. Furthermore, if an input RABid is presented at input 210 (also referred to as an “insert”) the tail pointer is incremented 403 (i.e., the tail pointer moves toward queue cell 203₇). The lack of a shiftup causes the tail pointer to hold its value 402 in response to the shiftup bus signal 216. Similarly, the lack of an insert cause the tail pointer to hold its value 404 in response to the insert signal.

[0059] Note that the tail pointer does not change (i.e., the new tail pointer value equals the old tail pointer value) if both a shiftup and an insert occurs. Similarly, the tail pointer does not change if neither a shiftup nor an insert occurs. The tail pointer's new value is decremented if a shiftup occurs and no insert occurs. Also, the tail pointer's new value is incremented if an insert occurs but no decrement occurs.

[0060] In the embodiment discussed above, the issue pointer logic 217 has two functions that are performed in the third cycle 352. A first function is to calculate the issue pointer that applies to the queue read 301 performed in the next cycle 350. A second function is to calculate the “don't want to issue” vector that is presented to the CAM 220 during the next cycle 350.

[0061] Recall that the issue pointer logic 217 is able to support issuing techniques more sophisticated than a simple FIFO technique. For example, the issue pointer logic 217 may be designed to implement a preemptive queuing technique. Pre-emptive queuing involves the prioritization of at least one RABid value over other RABid values. Before discussing pre-emptive queuing, however, simple FIFO servicing of queue 203 will be discussed.

[0062] As discussed, RABids are issued from queue 203 according to the value of an issue pointer that “points” to the cell holding the RABid to be issued. The issue pointer advances to the next location after the issuance of the RABid that is currently pointed to. To implement a simple FIFO, the next location corresponds to the RABid value that entered the array control circuit input 210 just after the RABid value that is currently pointed to.

[0063] A distinction should be drawn, however, between relative advancement and actual advancement. Relative advancement is advancement in light of the RABid values being pointed to. Actual advancement is advancement in light of the queue 203 cell that is being pointed to. Because of the shiftup capability of the queue 203, it is possible to have relative advancement without actual advancement as well as actual advancement without relative advancement.

[0064] An example of the former is if the issue pointer stays fixed upon a particular cell and the queue 203 shifts up into that cell. Here, the RABid value being pointed to has changed but the cell being pointed to has not changed. An example of the later is if the issue pointer shifts up along with the RABid value in the queue 203 cell being pointed to (i.e., both the queue 203 and the issue pointer shiftup simultaneously). Here, although the issue pointer has actually advanced to a higher cell, the issue pointer is still pointing to its original RABid value.

[0065] FIG. 5ashows a methodology 500 that may be used to determine the issue pointer for a simple FIFO queuing scheme. The methodology of FIG. 5aassumes the queue 203 and CAM 220 have already performed a shiftup (if any). The methodology of FIG. 5amay be modified, however, to account for a later rather than prior shiftup. For a simple FIFO, if the issue pointer points to a cell storing an issued RABid value, the issue pointer should exercise relative advancement. That is, the next RABid that has not issued should be pointed to. If the issue pointer points to a cell holding a RABid value that has not issued, the issue pointer should not exercise relative advancement and simply issue the RABid value being to. Frequently, the issue pointer is initially pointed at a cell holding an issued RABid because the issue pointer still points to the cell that just issued as the result of the pointer's present position.

[0066] The issue pointer logic 217 can determine 501 whether or not the pointed to cell has issued by comparing the “issue pointer not issued” vector against the issue pointer position. If the cell pointed to by the issue pointer has a logic low value in the “issue pointer not issued” vector, the cell corresponds to a RABid that has issued. If the cell pointed to by the issue pointer has a logic high value in the “issue pointer not issued” vector, the cell corresponds to a RABid that has not issued.

[0067] Whether or not the issue pointer actually advances (i.e., actually increments its position) will depend upon the presence of a shiftup for both relative advancement and no relative advancement. For relative advancement, the issue pointer should hold its position 502 if a shiftup occurred and actually increment 503 if no shiftup occurred. If relative advancement is not needed, the pointer value should hold its position 504 if no shiftup occurred and actually decrement 505 if a shiftup occurred.

[0068] Referring briefly to FIG. 2a, note that the shiftup signals SHIFTUP0 through SHIFTUP6 associated with the shiftup bus 216 are directed to the issue pointer logic 217. Whether or not a shiftup occurred for the methods discussed just above depends upon the position of the issue pointer in light of the status of the shiftup signals SHIFTUP0 through SHIFTUP6. It is possible that even though a shiftup occurred in the queue 203 and the CAM 220, the method 500 of FIG. 5aproperly executes according to a “no shiftup” condition (e.g., increment 503 or hold 504).

[0069] For example, if the issue pointer points to cell 203₂but a shiftup only occurred in cells 203₅and 203₆the shiftup has no relative effect on the RABid values pointed to by the issue pointer. As such, a shiftup condition arises for purposes of executing the method 500 of FIG. 5aonly if the cell being pointed by the issue pointer has lower data shifted into it by the shiftup. That is, for method 500, a shiftup is deemed to have occurred only if the issue pointer points to a cell having an active shiftup signal. As such, before making a determination as to whether or not a shiftup occurred, the issue pointer method 500 should check the shiftup signal of the cell being pointed to. If a shiftup occurred at that cell, then a “yes shiftup” condition arises. If a shiftup did not occur at that cell, a “no shiftup” condition arises.

[0070] Furthermore, regardless if relative advancement is necessary or if a shiftup condition arises, the issue pointer should be checked against the tail pointer to ensure that the issue pointer has not actually advanced beyond the tail pointer. In heavy traffic situations, the queue 203 begins to fill up with RABids which drives the tail pointer toward the lowest cell 203₇. Here, the issue pointer is typically higher than the tail pointer which reflects the delay experienced by the RABids while waiting in the queue 203.

[0071] In low traffic situations, the tail pointer and issue pointer may meet at the same cell (e.g.., when the queue is empty and waiting for the arrival of a RABid from the array). The issue pointer should not fall below the tail pointer, however, if proper ordering of issues is to be preserved. Thus, the position of the issue pointer is checked 506 against the position of the tail pointer. If the tail pointer is above the issue pointer, the issue pointer actually decrements 507 (bringing the issue pointer even with the tail pointer). If the issue pointer is not below the tail pointer, the issue pointer may keep 508 the position determined before the check 506 was made.

[0072] Referring to FIG. 2a, once the new issue pointer is forwarded to the read address logic 212, the corresponding RABid is read from the cell pointed to by the new issue pointer. The issue pointer logic 217 is coupled to the read data bus 234 so that the RABid value of the cell being read can be identified. Recall that the issue pointer logic 217 is also responsible for generating the “don't want to issue” vector. The RABid value of the cell being read is used to generate the “don't want to issue” vector.

[0073] FIG. 5bshows a methodology 510 that may be used to generate the “don't want to issue” vector. The “don't want to issue” vector may be formed by: 1) accounting for the arrival of new RABid values to the queue 203 from the array; and 2) accounting for the issuing of RABid values from the queue 203 to the array.

[0074] When a RABid value is sent from the array to the queue 203, the “don't want to issue” vector should reflect that the newly arrived RABid value wants to issue. That is, while a RABid value is not being used by the array control circuit (i.e., its value does not appear in the queue 203 or CAM 220) it has no desire to issue. As a result, the value of the “don't want to issue” vector component that corresponds to this RABid value is a logic high.

[0075] Once the RABid value is offered to the array control circuit 207 (via input 210) and subsequently written into the queue 203, its status changes from not desiring an issue to desiring an issue. The issue pointer logic 217 should therefore reflect this change of status by toggling the “don't want to issue” vector component bit from a logic high to a logic low for the new RABid value. Consistent with the above description, in the methodology 510 of FIG. 5b, it is first determined 550 whether or not a new RABid has arrived (e.g., via net 290 of FIG. 2a). If so, the status of the “don't want to issue” vector component that corresponds to the newly arrived RABid is changed 553. If not, the vector does not change 552.

[0076] When a RABid value is sent from the queue 203 to the array, the “don't want to issue” vector should reflect that the issued RABid value no longer wants to issue. That is, while a RABid value is waiting in the queue 203 it desires to issue to the array. As a result, while the RABid is waiting in the queue 203, the “don't want to issue” vector component that corresponds to this RABid value is a logic low.

[0077] Once the RABid value is issued to the array from the queue 203, its status changes from desiring an issue to not desiring an issue. The issue pointer logic 217 should therefore reflect this change of status by toggling the “don't want to issue” vector component bit from a logic low to a logic high for the issued RABid value. Consistent with the above description, in the methodology 510 of FIG. 5b, it is next determined 551 whether or not a RABid has issued (e.g., via net 291 of FIG. 2a). If so, the status of the “don't want to issue” vector component that corresponds to the newly arrived RABid is changed 555. If not, the vector does not change 554. The result of the process 510 is the new “don't want to issue” vector that will be forwarded to the CAM 220. Alternate embodiments may check 551 for an issued RABid before checking 550 for a newly arriving RABid.

[0078] The discussion so far supports mostly FIFO queuing techniques. However, as mentioned above, the array control circuit 207 of FIG. 2acan be used to support more complicated techniques such as pre-emptive queuing. Recall that pre-emptive queuing involves prioritizing at least one RABid over other RABids. For example, some instruction fetches may correspond to “demand” fetches while other instruction fetches may correspond to normal fetches. In an embodiment, demand fetches are used for instructions that will prevent or remove the processor from a condition where it is has to miss execution cycles because it is has not yet fetched a particular instruction (a condition commonly referred to as starvation).

[0079] Since the processor may soon reach a starve condition (or can't correct a starve condition) before the particular instruction is fetched, the processor “demands” the particular instruction and it is given higher priority over other instructions. The RABid that corresponds to the demanded instruction is labeled as a “demand” RABid. A demand RABid, being high priority, is issued to the array before other RABids even though other RABids were presented to the array control circuit input 210 prior to the arrival of the demand RABid.

[0080] FIG. 5cshows a modified version 590 of the array control circuit 207 that is configured to pre-emptively queue RABids given a “demand” status. The modifications include the addition of a demand register 523 and the addition of another CAM cell 520. Demand register 523 holds those RABids that are given demand status. Note that demand RABids enter input 210 having already been given demand status are identified in some manner as having demand status. In an embodiment, when a demand RABid enters the modified array control circuit 590, the write address logic 591 is configured to write the RABid in both the demand register 523 and the queue 203 cell being pointed to by the tail pointer.

[0081] This allows the logic that determines which RABids are demand RABids to change the status of a demand RABid to a normal RABid. For example, consider a case where a first demand RABid enters input 210 and is written in both the demand register 523 and a queue 203 cell. If the logic that determines RABid status decides that a subsequent RABid to be entered at input 210 should be given higher priority than the current demand RABid, the logic sends the subsequent RABid to input 210 as a demand RABid (i.e., a second demand RABid).

[0082] Following the procedure for demand RABids, write address logic 591 writes the second demand RABid into the demand register 523 and the queue 203 cell pointed to by the tail pointer. If the first demand RABid within the demand resister 523 has not yet issued to the array, the writing of the second RABid into the demand register 523 effectively erases the first demand RABid from the demand register. However, since the first RABids is also stored in the queue 203, the RABid value corresponding to the first demand RABid is still stored with the array control circuit queue 203 and CAM 220. This drops the status of the first demand RABid from a demand RABid to a normal RABid.

[0083] Another modification is the addition of multiplexor 521 that sends issued RABids to the array. Multiplexor 522 is configured to send a demand RABid from the demand register 523 to the array if the demand register 523 is populated; or send a normal RABid from the read data bus 224 to the array if the demand register is not populated. The signal 522 that controls whether the demand register 523 contents or read data bus 224 contents are sent to the array is determined by additional CAM cell 520.

[0084] Additional CAM cell 520 stores the value of the RABid that is within the demand register 523. Note that in the embodiment of FIG. 5c, the input to CAM cell 520 is the inverse of the “don't want to issue” vector. That is, CAM cell 520 is presented with the logical equivalent of a “want to issue” vector (wti). Recall the description above with respect to FIG. 5bregarding the methodology 510 used to determine the “don't want to issue” vector. When a newly entered RABid value arrives at input 210, the “don't want to issue” vector changes the value that corresponds to the new RABid value in such a manner that it reflects the new RABid value's desire to issue (e.g., the “don't want to issue” vector toggles the corresponding RABid value bit from a 1 to a 0).

[0085] When a RABid value that is written into the demand register is also written into queue 203, the “don't want to issue” vector is affected as described just above. By inverting the “don't want to issue” vector before presenting it to CAM cell 520, the new RABid value (which is also in demand register 523) component of the vector is a logic high at cell input 524. CAM cell 520 then positively identifies a match (similar to the manner described with respect to FIGS. 2cand 2d) which produces the “demand must issue” signal 522. By configuring multiplexor 522 to send the contents of the demand register 523 to the array when CAM cell 520 discovers a match, the RABid within the demand register 523 is pre-emptively queued over other RABid values.

[0086] In another pre-emptive embodiment, shown in FIG. 5d, a normal RABid already waiting in queue 203 may be instantaneously declared as a demand RABid. This changes the status of the particular RABid value from normal priority to high priority. In this embodiment, one may refer to the circuit 207 of FIG. 2a. This approach may also be used for RABids given a demand status before entering at input 210. Here, the issue pointer logic 217 is configured to direct its next issue pointer to the queue 203 cell holding the demanded RABid value. Note that, as seen in FIG. 2a, the processor may enter the demanded RABid value at input 250 (which may also be coupled to input 210).

[0087] Referring to FIG. 5d, when a particular RABid value 511 is demanded, the issue pointer logic 217 generates 510aa “don't want to issue” vector 561 according to the methodology 510 discussed with respect to FIG. 5b. The process 510awill generate a new “don't want to issue” vector 561 that reflects the demanded RABid value 511 desires to issue. Subsequently, the “issue pointer not issued” vector 562 generated from the new “don't want to issue” vector 561 will be different than the original “issue pointer not issued” vector 565.

[0088] The difference between the two vectors 562, 565 will be at the vector component corresponding to the cell location the demanded RABid has been stored in. Thus, the two vectors 562, 565 are compared 566 which produces the cell location 516 holding the demanded RABid value. The issue pointer logic 217 simply uses this cell location 516 to properly read the demanded RABid value from the queue. The demanded RABid value is pre-emptively queued as a result. New issue pointer 560 is suspended until the next issue pointer calculation sequence.

[0089] The RABid is then directed to the array and the demanded RABid value returns to the issue pointer logic. The issue pointer logic determines 510b(according to process 510 of FIG. 5b) the next “don't want to issue” vector 563 in light of the demanded RABid value and the new “don't want to issue” vector 561. The issue pointer logic also calculates 500b(according to process 500 of FIG. 5a) the next issue pointer 564 using the new issue pointer 560 that was previously suspended and the new “issue pointer issued” vector 562.

[0090] Note that the methodology 500 of FIG. 5ais robust enough to handle a shiftup that may occur while the pre-emptive queuing takes places. That is, a shiftup may cause the new issue pointer value 560 to point to a cell having a RABid value that has not issued. In this case, no relative advancement is needed. If two shiftups occurs in series (i.e., once before issue pointer 518 is determined and once before the next “don't want to issue” vector 563 is determined 510b), the second shiftup may be suspended or delayed (which may require queuing before input 210) so the next “don't want to issue” vector 563 points to the proper value.

[0091] FIG. 6 shows an embodiment of a CAM cell design that may be used to perform the CAM operations discussed above. Recall that in embodiments discussed above, CAM 220 finds a match between its cell contents and the input “don't want to issue” and RABid return vectors. Examples of the matching were shown in FIGS. 2cand 2d. Also note that both matches are performed simultaneously (referring briefly to cycle 351 in FIG. 3a).

[0092] In order to perform simultaneous matching, parallel circuits may be designed. A first parallel circuit can identify a match between the “don't want to issue” vector and the cell contents while a second parallel circuit can identify a match between the RABid return vector and the cell contents. FIG. 6 shows parallel circuits consistent with this approach. In FIG. 6, circuit 601 is the first parallel circuit (as defined above) while circuit 602 is the second parallel circuit (as defined above).

[0093] Recall that in the matching approaches discussed in FIGS. 2cand 2d, the CAM need only find a match of logic high values between the input vectors and the cell data. Circuits 601, 602 are configured to pull down their respective output nodes “issue pointer not issued”, and “not done” only if matching logical high values exist. The gate q of transistor 603 corresponds to a bit of the RABid value stored in the cell. The sources of transistors 603, 604 are coupled to a bit of the “don't want to issue” vector. In an embodiment having vector sizes and RABid value sizes of eight bits, the circuits 601, 602 are repeated eight times for each cell.

[0094] When the “don't want to issue” bit and q bits are high, transistor 604 is “on” and transistor 603 is “off”. If transistor 604 is “on”, the gate node of transistor 604 is low which turns “off” transistor 605. Also, if transistor 604 is “on”, the logic high value at the source of transistor 604 is observed at the drain of transistor 604. The combination of logic high voltage at the drain of transistor 604 and logic low voltage at transistor 605 provides the gate of transistor 606 with a logic high voltage. A logic high voltage at the gate of transistor 606 turns transistor 606 “on” which pulls down the output “issue pointer not issued” bit. In all cases other than logical high values at both the “don't want to issue” bit and the q bit, transistor 606 is “off”. Since the “issue pointer not issued” bit output is coupled to a pull up, the output will be logic high for all these cases. Circuit 602 operates similarly to circuit 601. As such both circuits 601, 602 help properly find a match of logic high between the input vectors and the cell data.