Branch stall elimination in pipelined microprocessors

A system can include a microprocessor having a prefetch queue including a plurality of slots configured to store program counter values (PCVs) and instructions, a pipeline configured to receive instructions from the prefetch queue, and a select circuit coupled to the prefetch queue. The select circuit may selectively freeze a first slot of the plurality of slots and selectively output a frozen PCV and a frozen instruction from the first slot while frozen. The microprocessor can include write logic coupled to the prefetch queue and a comparator circuit coupled to the prefetch queue and the select circuit. The write logic may load data into unfrozen slots of the prefetch queue. The comparator circuit may compare a target PCV with the frozen PCV to determine a match. The select circuit indicates, to the pipeline, whether the frozen instruction is valid based on the comparing.

TECHNICAL FIELD

This disclosure relates to integrated circuits (ICs) and, more particularly, to elimination of branch stalls in pipelined microprocessors.

BACKGROUND

Microprocessors that utilize a Reduced Instruction Set Computer (RISC) architecture are characterized by execution of assembly language instructions that require one clock cycle per instruction. RISC microprocessors are also characterized by features such as having a larger number of registers compared to their Complex Instruction Set Computer (CISC) counterparts and the use of pipelining to facilitate simultaneous execution of instructions through a plurality of stages of pipeline circuitry.

RISC-V is an Instruction Set Architecture (ISA) for RISC microprocessors that does not provide jumps or branches with architecturally visible delay slots. A delay slot refers to an instruction slot within certain RISC and Digital Signal Processing (DSP) microprocessor architectures that is executed without the effects of a preceding instruction. An example of a delay slot is a single instruction located immediately after a branch or jump instruction that, in consequence of code reordering by the assembler, typically executes prior to the branch or jump instruction being executed. For example, a program instruction that is not dependent on the result of a branch or jump instruction may be executed in a delay slot while the branch or jump is taken as opposed to introducing a stall.

In many prior RISC microprocessor implementations, one or more delay slots were implemented to reduce pipeline stalls from branches and jumps. The RISC-V ISA omits delay slots to avoid complicating higher performance RISC-V based microprocessor implementations.

SUMMARY

In an example implementation, a system can include a microprocessor. The microprocessor can include a prefetch queue including a plurality of slots. The plurality of slots are configured to store program counter values and instructions. The microprocessor can include a pipeline configured to receive instructions from the prefetch queue. The microprocessor can include a select circuit coupled to the prefetch queue. The select circuit may be configured to selectively freeze a first slot of the plurality of slots and selectively output a frozen program counter value and a frozen instruction from the first slot while frozen. The microprocessor can include write logic coupled to the prefetch queue. The write logic may be configured to load program counter values and instructions into unfrozen slots of the prefetch queue. The microprocessor can include a comparator circuit coupled to the prefetch queue and the select circuit. The comparator circuit may be configured to compare a target program counter value with the frozen program counter value to determine a match. The select circuit indicates, to the pipeline, whether the frozen instruction is valid based on whether the target program counter value matches the frozen program counter value.

In another example implementation, a method can include freezing a first slot of a plurality of slots of a prefetch queue in response to detecting entry of a first control instruction into a pipeline of a microprocessor. The method can include outputting a frozen program counter value and a frozen instruction from the first slot while frozen in response to detecting entry of a second control instruction into the pipeline. The method can include comparing the frozen program counter value with a target program counter value using a comparator circuit to determine a match and providing the frozen instruction to the pipeline. The method can include indicating to the pipeline that the frozen instruction is valid in response to determining that the frozen instruction matches the target program counter value.

DETAILED DESCRIPTION

This disclosure relates to integrated circuits (ICs) and, more particularly, to elimination of branch stalls in pipelined microprocessors. A pipelined microprocessor uses a technique referred to as “instruction pipelining” for implementing instruction-level parallelism within the microprocessor. The microprocessor includes circuitry referred to as a “pipeline” having a plurality of sequential stages. In general, each stage of the pipeline may be responsible for performing a particular step or steps of instruction execution. For example, stages of a pipeline of a microprocessor may include instruction fetch, decode, execution, and write back. The number of stages of the pipeline of a microprocessor may vary depending on the complexity of the pipelining used.

Parallelism is achieved using instruction pipelining in that the microprocessor operates on multiple instructions concurrently in the different pipeline stages. For example, a pipeline having four stages allows a microprocessor to perform the following operations concurrently (e.g., in parallel): in the first stage an instruction is fetched, in the second stage a different instruction having already been processed through the first stage is decoded (e.g., operands are fetched), in the third stage yet a different instruction is executed having already been processed through the first and second stages, and in the fourth stage results are written for yet another instruction having already been processed through the first, second, and third stages.

Using pipelining, a microprocessor with a RISC architecture is capable of executing one instruction each clock cycle. Within some RISC processors that use a single-issue pipeline, the absence of delay slots, as proposed in the RISC-V ISA, can degrade performance of the microprocessor due to the occurrence of pipeline stalls. The term “single-issue pipeline” means a microprocessor architecture that uses a single pipeline. A single-issue pipeline is to be contrasted with other microprocessor architectures that use two or more pipelines in parallel, where each such pipeline can be used to process multiple instructions in parallel or different and alternative sequences of instructions.

One technique for addressing pipeline stalls in a RISC microprocessor having a single-issue pipeline architecture is to introduce a Branch Target Cache (BTC). While the BTC may avoid pipeline stalls, implementing a BTC requires a significant amount of circuit resources. The use of a BTC may also negatively affect the maximum achievable operating frequency of the microprocessor.

In accordance with the inventive arrangements described within this disclosure, a prefetch queue may be utilized to avoid pipeline stalls in a RISC-based, single-issue pipeline microprocessor. The prefetch queue is part of a circuit architecture that is already available in such microprocessors. The existing prefetch queue architecture may be modified to operate in a manner that is capable of eliminating pipeline stalls. Modifying the existing prefetch queue as described herein uses fewer additional circuit resources compared to implementing a BTC. Using a prefetch queue as described herein, a RISC-based, single-issue pipeline microprocessor is able to avoid situations where the next instruction for a pipeline following a control instruction is not available in the prefetch queue, thereby inducing a stall in the pipeline.

As defined within this disclosure, a control instruction is an instruction that causes a change in the sequence of instructions executed by a microprocessor such that the microprocessor executes a first instruction followed by a second instruction, in consequence of the control instruction, where the program counter value of the second instruction is non-sequential with the program counter value of the first instruction. Examples of control instructions include a jump instruction and a branch instruction.

FIG.1illustrates an example system100including a microprocessor102for use with the inventive arrangements described within this disclosure. System100may include, or be implemented as, an IC. In the example ofFIG.1, the IC is implemented as microprocessor102. For example, microprocessor102may be implemented as a standalone IC without other circuits and/or subsystems.

In another aspect, microprocessor102may be embedded within an IC along with one or more other components and/or subsystems forming system100. For example, microprocessor102may be included in an IC that includes other Application Specific ICs (ASICs) or hardwired circuit blocks, programmable circuitry, or any combination thereof. An example of an IC with an embedded microprocessor includes a Field Programmable Gate Array (FPGA) having one or more microprocessors therein or a System-on-Chip including one or more microprocessors therein.

Microprocessor102includes a prefetch queue architecture (PQ architecture)104and a pipeline106. Microprocessor102may be implemented as a RISC microprocessor. Further, microprocessor102may be implemented as a single-issue pipeline microprocessor. In this regard, microprocessor102may include a single pipeline106. In addition, microprocessor102may be implemented so as not to use delay slots. For example, microprocessor102may be implemented in accordance with the RISC-V ISA where no delay slots are visible.

Pipeline106may include a plurality of different stages. For purposes of illustration, the stages of pipeline106may include, but are not limited to, fetch, decode, execute, and write back. Pipeline106may include fewer or more stages depending on the particular implementation of pipeline106and microprocessor102.

PQ architecture104is configured to fetch instructions from a memory (not shown) in advance of the instructions being executed and store the fetched instructions in a prefetch queue. PQ architecture104is configured to feed those prefetched instructions stored in the prefetch queue to pipeline106. In general, PQ architecture104fetches instructions, in sequence, from a particular location in memory and loads the fetched instructions into the prefetch queue of PQ architecture104. The PQ architecture104may continue to fetch sequential instructions during operation. The instructions may be continually provided from the prefetch queue to pipeline106in sequence. When a control instruction is encountered by pipeline106, the sequence of instructions needed for execution deviates from the sequentially ordered instructions that have been prefetched into the prefetch queue of PQ architecture104.

In conventional single-issue pipeline microprocessors that operate without delay slots, the entire prefetch queue is cleared in response to encountering the control instruction since the instructions contained in the prefetch queue will not be executed. New sequential instructions are fetched into the prefetch queue, where the new sequential instructions start at the address to which program execution is branching or jumping, referred to herein as the “target program counter value” or “target address.” The new sequential instructions are loaded into the prefetch queue.

Fetching new data into the prefetch queue requires at least one clock cycle to complete. As such, in a conventional RISC-based microprocessor having a single-issue pipeline that does not use delay slots, the time needed to fetch new data into the prefetch queue causes a pipeline stall. No new instructions are available to load into the pipeline until the new data is fetched into the prefetch queue.

As the conventional microprocessor continues to operate, newly fetched data overwrites existing data in the prefetch queue. No data from prior fetch operations is preserved. In cases where the microprocessor is executing a loop, each loop back to the target address may result in a further clearing of the prefetch queue and subsequent overwrite of all data therein. This means that upon each iteration of the loop, in this case, the microprocessor will suffer a pipeline stall in consequence of the lack of delay slots thereby inhibiting performance of the microprocessor.

In accordance with the inventive arrangements described within this disclosure, PQ architecture104is capable of freezing certain data in the prefetch queue in response to a control instruction entering pipeline106. Upon detecting a further, or subsequent, control instruction entering pipeline106, PQ architecture104may provide all or a portion of the frozen data to pipeline106, as described hereinbelow, to avoid a pipeline stall. Concurrently with providing the frozen data, PQ architecture104fetches new data into portions of the prefetch queue that are not frozen. Such newly fetched data may then be fed into pipeline106in the next clock cycle and in subsequent clock cycles, while preserving the data in the frozen portion of the prefetch queue.

FIG.2illustrates an example implementation of PQ architecture104ofFIG.1. In the example ofFIG.2, PQ architecture104includes a prefetch queue202, a write circuit204, a select circuit206, and a comparator circuit208. Prefetch queue202includes a memory210and a multiplexer212. Memory210is organized into a plurality of slots214(e.g., memory locations). For purposes of illustration, memory210is shown to include 4 slots. It should be appreciated that memory210may include fewer or more slots than shown. In an example implementation, memory210is organized as and operates as a circular buffer.

Slots214are capable of storing program counter values220and instructions222. For example, each slot214is capable of storing a single program counter value and the instruction (e.g., opcode) located at the location in memory specified by that program counter value. Within this disclosure, the program counter value and instruction stored in the same slot may be referred to as “corresponding” to one another. Write circuit204is capable of fetching data, e.g., program counter values and corresponding instructions, and storing the fetched data within slots214.

In general, PQ architecture104is capable of selectively freezing and unfreezing one or more of slots214in response to certain conditions described hereinbelow in greater detail. As defined within this disclosure, the term “freeze” or “frozen,” as applied to a slot of the prefetch queue or data stored in a slot of a prefetch queue, means that the slot is in a state where the data stored in the slot may not be cleared or overwritten. To clear data from a frozen slot or write data to a frozen slot, the slot must first be unfrozen.

In one aspect, select circuit206is capable of performing the freezing and unfreezing of slots214. As noted, memory210may be organized as a circular buffer where select circuit206implements the pointer circuitry necessary to track reads, writes, and frozen and/or unfrozen slots of memory210. For example, select circuit206may include circuitry for tracking which of slots214is the “first” slot as new sequential data is fetched into memory210. Select circuit206may communicate with write circuit204to indicate which of slots214are frozen or unfrozen as the case may be. Accordingly, select circuit206is also capable of providing a select signal216to multiplexer212to specify the particular slot214from which data is output from multiplexer212to pipeline106and/or to comparator circuit208.

Write circuit204is capable of fetching data into memory210and writing the fetched data to slots214. Write circuit204may only write fetched data to those slots214that are unfrozen. That is, write circuit204is unable to write to a frozen slot, where the state of the slot as being frozen is specified by select circuit206.

Comparator circuit208is capable of receiving program counter values output from prefetch queue202and comparing the program counter values with a target program counter value. Comparator circuit208is capable of indicating, to select circuit206, by way of signal218, whether any given program counter value from multiplexer212matches the target program counter value. Further operative details relating toFIG.2are described below with reference toFIG.3.

FIG.3illustrates a method300of operation for PQ architecture104ofFIGS.1and2. Referring to bothFIGS.2and3, in block302, prefetch queue202begins operation with no frozen slots214. For purposes of illustration, memory210includes N different slots214, where N is an integer value greater than 1. PQ architecture104may operate such that write circuit204fetches enough data to fill the N slots214and writes the data to the N slots214. That is, write circuit204fetches N pairs of program counter values220and instructions222and stores each program counter value and corresponding instruction as a “data pair” in a slot214. The fetched data may be sequential in that write circuit204fetches the instructions from sequential addresses (e.g., program counter values) and stores the sequential data pairs in consecutive slots214(e.g., sequentially).

FIGS.4A,4B,4C,4D,4E, and4Fillustrate examples of data fetched into slots214of memory210of prefetch queue202. In the examples ofFIGS.4A-4F, the “first” slot is shown in bold. Any slots that are frozen are shaded.FIG.4Aillustrates an example where the prefetch queue includes slots 1, 2, 3, and 4.FIG.4Ais illustrative of block302in that no slot is frozen. Slot 1 is loaded with a first data pair depicted as “P1” in the figure. Slots 2, 3, and 4 are loaded with data pairs P2, P3, and P4, respectively.

In block304, entry of a control instruction into pipeline106may be detected. For example, select circuit206is capable of receiving a notification that a control instruction has entered pipeline106. In response to a control instruction entering a particular stage of pipeline106, pipeline106provides a notification to select circuit206by way of signal224. In one aspect, the particular stage of pipeline106that triggers the notification may be the first stage of pipeline106(e.g., a fetch stage). That is, the notification may be triggered in response to the control instruction entering the first stage of pipeline106. In another aspect, the particular stage of pipeline106that triggers the notification may be the decode stage of pipeline106. In another aspect, the particular stage of pipeline106that triggers the notification may be the execute stage of pipeline106. One or more of the noted stages, for example, may include circuitry that is capable of detecting a control instruction and/or determining that such instruction is valid and, in response, generating the notification. Select circuit206, in response to being notified of the first control instruction entering pipeline106, is capable of notifying write circuit204by way of signal228. In another aspect, write circuit204may receive signal224(not shown) in addition to select circuit206.

In block306, write circuit204is capable of fetching new data into prefetch queue202in response to the notification that a control instruction is entering pipeline106. In one aspect, the target address to which program execution will move (e.g., jump or branch) in consequence of the control instruction may be calculated by pipeline106and provided to PQ architecture104as the target program counter value. The target program counter value may be provided to comparator circuit208and, for example, to write circuit204. Accordingly, in response to the notification of the control instruction, write circuit204fetches new data pairs starting at the target program counter value and writes the new data pairs into prefetch queue202. That is, write circuit204fetches a N-sequential instructions (e.g., opcodes) starting from the target program counter value and loads target program counter values and corresponding instructions into the N slots214. With no slots frozen, and N slots being available, write circuit204fetches enough sequential data pairs to fill each of the N slots of prefetch queue202.

As discussed, with memory210being implemented as a circular buffer, select circuit206is capable of tracking which of slots214is the “first” slot. The “first slot” is the slot214of prefetch queue202that includes the first data pair of a sequence of such data pairs retrieved by write circuit204in the most recent fetch operation. Within this disclosure, only a first slot that stores the target program counter value in consequence of a control instruction may be frozen. Accordingly, in this example, the “first slot” is the slot214that stores the data pair that includes the target program counter value (e.g., as provided from pipeline106).

In block308, having detected a control instruction entering the pipeline and fetched new data into each of the N slots214of prefetch queue202(e.g., where no slot was frozen), the first slot214of prefetch queue202is frozen. Select circuit206is capable of freezing the first slot214of prefetch queue202.

FIG.4Billustrates an example state of memory210subsequent to block308. In the example ofFIG.4B, slots 1, 2, 3, and 4 store new data as data pairs P5, P6, P7, and P8, respectively. In this example, data pair P5 is not sequential with data pair P4. That is, the program counter value of data pair P5 is not sequential with the program counter value of data pair P4. Slot 1, being the “first slot,” is frozen where the frozen state of a slot is illustrated with shading.

In block310, the prefetch queue continues operation with the first slot frozen. That is, select circuit206, for example, may control multiplexer212to continue to output program counter values220and corresponding instructions222from slots214sequentially. Once the contents of the frozen first slot are output from multiplexer212one time, select circuit206does not output the contents of the frozen first slot again (e.g., while frozen) except in response to a detection of a further control instruction entering pipeline106. That is, select circuit206will continue to iterate by outputting data from the unfrozen slots214(e.g., slots 2, 3, and 4). Concurrently, write circuit204will continue to fetch new sequential data as needed into slots 2, 3, and 4. While the first slot is frozen, however, as indicated by signal228, write circuit fetches only enough data to fill N−1 slots214of prefetch queue202. As data pairs are fetched by write circuit204, the fetched data pairs are written to only the unfrozen slots214of prefetch queue202(e.g., to slots 2, 3, and 4).

FIG.4Cillustrates an example state of memory210subsequent to block310. In the example ofFIG.4C, the contents of the frozen first slot remain unchanged. Slot 1, for example, still stores data pair P5. The contents of unfrozen slots 2, 3, and 4 store new data in the form of data pairs P9, P10, and P11.

In block312, entry of a control instruction into pipeline106again may be detected. For example, select circuit206receives a notification that a control instruction has entered pipeline106. The control instruction detected in block312is the next control instruction to enter pipeline106following the control instruction of block304. That is, no other intervening control instruction has entered pipeline106between blocks304and312. In detecting a second control instruction entering pipeline106in block312, unlike in block304, prefetch queue202includes one (or more) frozen slots. It should be appreciated that the two control instructions need not be present within pipeline106concurrently.

In block314, prefetch queue202outputs the data stored in the frozen first slot. For example, in response to the notification of block312, select circuit206instructs multiplexer212, via select signal216, to output the program counter value and the instruction stored in the frozen first slot. For purposes of description, the program counter value and instruction stored in the frozen first slot may be referred to within this disclosure as the frozen program counter value and the frozen instruction. The frozen program counter value and the frozen instruction are output to the pipeline106. It should be appreciated that the frozen program counter value is the target program counter value from the control instruction detected in block304.

InFIG.4D, the contents of the frozen first slot again remain unchanged. Slot 1 continues to store P5. The contents of the unfrozen slots 2, 3, and 4 store new data in the form of data pairs P12, P13, and P14. In the case where a second control instruction is detected, select circuit206outputs the contents of the frozen first slot. Accordingly, data pair P5 is output from prefetch queue202.

In block316, the frozen program counter value is compared with a target program counter value. For example, comparator circuit208is capable of comparing the frozen program counter value with the target program counter value to determine a match. As discussed, the target program counter value may be provided to PQ architecture104from pipeline106. The target program counter value used for the comparison in block316is the target address calculated by pipeline106as determined from the (second) control instruction of block312.

In block318, a determination is made as to whether the target program counter value matches the frozen program counter value. In response to determining that the target program counter value matches the frozen program counter value, method300continues to block320. In response to determining that the target program counter value does not match the frozen program counter value, method300continues to block324.

In block320, in response to comparator circuit208determining that the target program counter value matches the frozen program counter value, comparator circuit208is capable of notifying select circuit206of the match via signal218. In response to being notified of the match, select circuit206is capable of notifying pipeline106that the data output from prefetch queue202is valid. For example, select circuit206is capable of asserting valid signal226to pipeline106thereby indicating that the data output from the frozen first slot is valid data. Pipeline106, for example, may not allow the frozen instruction and/or frozen program counter value to enter without receiving a valid indication from select circuit206. Further, in block320, the frozen first slot remains frozen.

In block322, the prefetch queue202continues to operate with the first slot frozen. That is, write circuit204may continue to fetch enough data to fill N−1 slots and write such data to only the unfrozen slots (e.g., slots 2, 3, and 4). It should be appreciated that concurrently with providing the frozen program counter value and/or the frozen instruction to pipeline106, write circuit204fetches new data into the unfrozen slots214of prefetch queue202. Accordingly, on a next clock cycle, prefetch queue202is capable of supplying further program counter values and instructions continuing from the target of the control instruction thereby avoiding a stall in pipeline106. As noted, select circuit206only provides the contents of the frozen first slot from multiplexer212in response to detection of control instructions entering pipeline106. In other cases, content from non-frozen slots is output. After block322, method300may loop back to block312to continue operation.

FIG.4Eis illustrative of an example state of prefetch queue202following block322. As shown, the frozen first slot again remains unchanged. Slot 1 continues to store data pair P5. The contents of the unfrozen slots 2, 3, and 4 store new data in the form of data pairs P15, P16, and P17. In the case where a second control instruction is detected as described in the example of block312, select circuit206outputs the contents of the frozen first slot. Accordingly, P5 is output from prefetch queue202.

In block324, in response to comparator circuit208determining that the target program counter value does not match the frozen program counter value, comparator circuit208is capable of notifying select circuit206of the mismatch via signal218. In response to being notified of the mismatch, select circuit206is capable of notifying pipeline106that the data output from prefetch queue202is invalid. For example, select circuit206is capable of de-asserting valid signal226to pipeline106thereby indicating that the data output from the frozen first slot is invalid data. The frozen program counter value does not match the target program counter value. In that case, pipeline106does not allow the frozen instruction and/or frozen program counter value to enter. The data is rejected by pipeline106.

Further, in block324, the first slot is unfrozen. Select circuit206is capable of unfreezing the first slot. Select circuit206may indicate that the first slot has been unfrozen to write circuit204by way of signal228. Continuing with block326, the prefetch queue continues operation with the first slot unfrozen. That is, write circuit204may continue to fetch enough data to fill N slots and write such data to only the unfrozen slots, which in this case is all slots of prefetch queue202. Following block326, method300may loop back to block304to continue operation.

FIG.4Fillustrates an example state of prefetch queue202following block326. As shown, the first slot is unfrozen. Further, write circuit204has fetched N different data pairs P18, P19, P20, and P21, that have been written to slots 1, 2, 3, and 4, respectively.

FIGS.2-4, taken collectively, illustrate how the first slot of prefetch queue202may be frozen following a data fetch performed responsive to a control instruction. Freezing the first slot following the data fetch as described ensures that the target program counter value for the control instruction is preserved in cases where the processor loops. Thus, each time the processor loops, the instruction corresponding to the target program counter value may be fed to pipeline106to avoid a pipeline stall.

While the examples described within this disclosure freeze and unfreeze the first slot of a prefetch queue, in other example implementations, more than one slot may be frozen. With freezing more than one slot, the architecture may be further modified to include additional comparator circuits. For example, for each slot that may be frozen in such an architecture, an additional comparator circuit may be added.

FIG.5is a method500illustrating certain operative features of the PQ architecture104ofFIGS.1and2. In block502, a first slot of a plurality of slots of the prefetch queue202is frozen in response to detecting entry of a first control instruction into a pipeline106of microprocessor102. For example, select circuit206is capable of freezing the first slot in response to receiving a notification that the first control instruction is entering or has entered the pipeline106.

In block504, a frozen program counter value and a frozen instruction are output from the first slot, while frozen, in response to detecting entry of a second control instruction into the pipeline. For example, select circuit206, in response to receiving a further notification as described that a subsequent control instruction has entered or is entering the pipeline106, is capable of instructing multiplexer212to output the contents or data pair (e.g., the frozen program counter value and the frozen instruction) of the frozen first slot.

In block506, the frozen program counter value is compared with a target program counter value using a comparator circuit to determine a match. Comparator circuit208is capable of comparing the program counter value output from the frozen first slot with the target program counter value received from pipeline106. Comparator circuit208determines whether, based on the comparison, the program counter value output from the frozen first slot matches the target program counter value.

In block508, the frozen instruction may be provided to a pipeline of the microprocessor. For example, the frozen instruction, as output by multiplexer212, is provided to pipeline106. In block510, an indication may be provided to the pipeline106of the microprocessor102that the frozen instruction is valid in response to determining that the frozen instruction matches a target program counter value. Comparator circuit208, for example, indicates to select circuit206via signal218that the frozen program counter value matches the target program counter value. In response, select circuit206indicates that the frozen instruction provided to pipeline106is valid via signal226. Pipeline106, in response to the indication that the frozen instruction is valid, admits the instruction into the pipeline106.

The foregoing and other implementations can each optionally include one or more of the following features, alone or in combination. Some example implementations include all the following features in combination.

The method can include fetching new data into prefetch queue202concurrently with the outputting the frozen program counter value and the frozen instruction from the first slot while frozen. That is, write circuit204may operate to continue to fetch new data into unfrozen slots of memory210while prefetch queue202operates and outputs data under control of select circuit206.

As discussed, only unfrozen slots of the plurality of slots are overwritten with new data in response to fetching the new data into the prefetch queue. Select circuit206, for example, is capable of indicating to write circuit204, via signal228, which slots are frozen at any given time. Write circuit204is capable of writing newly fetched data only into the slots of prefetch queue202that are not frozen.

The method can include unfreezing the first slot frozen in response to a mismatch between the target program counter value and the frozen program counter value. For example, in the case where the contents of the frozen first slot are output (e.g., block314and/or504), and the frozen program counter value does not match the target program counter, as determined by comparator circuit208, comparator circuit208indicates the mismatch to select circuit206. In response, select circuit206unfreezes the first slot. Once unfrozen, write circuit204may write newly fetched data into the first slot along with any other slots that are not frozen.

FIG.6illustrates an example architecture600for an IC. In one aspect, architecture600may be implemented within a programmable IC. For example, architecture600may be used to implement a field programmable gate array (FPGA). Architecture600may also be representative of a system-on-chip (SoC) type of IC. An SoC is an IC that includes a processor that executes program code and one or more other circuits. The other circuits may be implemented as hardwired circuitry, programmable circuitry, and/or a combination thereof. The circuits may operate cooperatively with one another and/or with the processor.

As shown, architecture600includes several different types of programmable circuit, e.g., logic, blocks. For example, architecture600may include a large number of different programmable tiles including multi-gigabit transceivers (MGTs)601, configurable logic blocks (CLBs)602, random-access memory blocks (BRAMs)603, input/output blocks (IOBs)604, configuration and clocking logic (CONFIG/CLOCKS)605, digital signal processing blocks (DSPs)606, specialized I/O blocks607(e.g., configuration ports and clock ports), and other programmable logic608such as digital clock managers, analog-to-digital converters, system monitoring logic, and so forth.

In some ICs, each programmable tile includes a programmable interconnect element (INT)611having standardized connections to and from a corresponding INT611in each adjacent tile. Therefore, INTs611, taken together, implement the programmable interconnect structure for the illustrated IC. Each INT611also includes the connections to and from the programmable logic element within the same tile, as shown by the examples included at the right ofFIG.6.

For example, a CLB602may include a configurable logic element (CLE)612that may be programmed to implement user logic plus a single INT611. A BRAM603may include a BRAM logic element (BRL)613in addition to one or more INTs611. Typically, the number of INTs611included in a tile depends on the height of the tile. As pictured, a BRAM tile has the same height as five CLBs, but other numbers (e.g., four) also may be used. A DSP tile606may include a DSP logic element (DSPL)614in addition to an appropriate number of INTs611. An10B604may include, for example, two instances of an I/O logic element (IOL)615in addition to one instance of an INT611. The actual I/O pads connected to IOL615may not be confined to the area of IOL615.

In the example pictured inFIG.6, the shaded area near the center of the die, e.g., formed of regions605,607, and608, may be used for configuration, clock, and other control logic. Shaded areas609may be used to distribute the clocks and configuration signals across the breadth of the programmable IC.

Some ICs utilizing the architecture illustrated inFIG.6include additional logic blocks that disrupt the regular columnar structure making up a large part of the IC. The additional logic blocks may be programmable blocks and/or dedicated circuitry. For example, a processor block depicted as PROC610spans several columns of CLBs and BRAMs. PROC610is an example of microprocessor102as described herein.

As such, PROC610may be implemented to include a PQ architecture104as described herein.FIG.6illustrates an example where a microprocessor (e.g., PROC610) is embedded in an IC. In the example ofFIG.6, the IC includes programmable logic. PROC610, for example, may be implemented using a RISC ISA. PROC610further may be implemented as a single-issue pipeline microprocessor.

In one aspect, PROC610may be implemented as dedicated circuitry, e.g., as a hardwired processor, that is fabricated as part of the die that implements the programmable circuitry of the IC. PROC610may represent any of a variety of different processor types and/or systems ranging in complexity from an individual processor, e.g., a single core capable of executing program code, to an entire processor system having one or more cores, modules, co-processors, interfaces, or the like. Still, PROC610and/or cores thereof are implemented using the RISC ISA and as a single-issue pipeline type of processor.

In another aspect, PROC610may be omitted from architecture600and replaced with one or more of the other varieties of the programmable blocks described. Further, such blocks may be utilized to form a “soft processor” in that the various blocks of programmable circuitry may be used to form a processor that can execute program code as is the case with PROC610.17. In that case, PROC610, being implemented programmable logic of the IC, still may be implemented using a RISC ISA and as a single-issue pipeline type of processor.

The phrase “programmable circuitry” refers to programmable circuit elements within an IC, e.g., the various programmable or configurable circuit blocks or tiles described herein, as well as the interconnect circuitry that selectively couples the various circuit blocks, tiles, and/or elements according to configuration data that is loaded into the IC. For example, circuit blocks shown inFIG.6that are external to PROC610such as CLBs602and BRAMs603are considered programmable circuitry of the IC.

In general, the functionality of programmable circuitry is not established until configuration data is loaded into the IC. A set of configuration bits may be used to program programmable circuitry of an IC such as an FPGA. The configuration bit(s) typically are referred to as a “configuration bitstream.” In general, programmable circuitry is not operational or functional without first loading a configuration bitstream into the IC. The configuration bitstream effectively implements a particular circuit design within the programmable circuitry. The circuit design specifies, for example, functional aspects of the programmable circuit blocks and physical connectivity among the various programmable circuit blocks.

Circuitry that is “hardwired” or “hardened,” i.e., not programmable, is manufactured as part of the IC. Unlike programmable circuitry, hardwired circuitry or circuit blocks are not implemented after the manufacture of the IC through the loading of a configuration bitstream. Hardwired circuitry is generally considered to have dedicated circuit blocks and interconnects, for example, that are functional without first loading a configuration bitstream into the IC, e.g., PROC610.

In some instances, hardwired circuitry may have one or more operational modes that can be set or selected according to register settings or values stored in one or more memory elements within the IC. The operational modes may be set, for example, through the loading of a configuration bitstream into the IC. Despite this ability, hardwired circuitry is not considered programmable circuitry as the hardwired circuitry is operable and has a particular function when manufactured as part of the IC.

In the case of an SoC, the configuration bitstream may specify the circuitry that is to be implemented within the programmable circuitry and the program code that is to be executed by PROC610or a soft processor. In some cases, architecture600includes a dedicated configuration processor that loads the configuration bitstream to the appropriate configuration memory and/or processor memory. The dedicated configuration processor does not execute user-specified program code. In other cases, architecture600may utilize PROC610to receive the configuration bitstream, load the configuration bitstream into appropriate configuration memory, and/or extract program code for execution.

FIG.6is intended to illustrate an example architecture that may be used to implement an IC that includes programmable circuitry, e.g., a programmable fabric. For example, the number of logic blocks in a column, the relative width of the columns, the number and order of columns, the types of logic blocks included in the columns, the relative sizes of the logic blocks, and the interconnect/logic implementations included at the right ofFIG.6are purely illustrative. In an actual IC, for example, more than one adjacent column of CLBs is typically included wherever the CLBs appear, to facilitate the efficient implementation of a user circuit design. The number of adjacent CLB columns, however, may vary with the overall size of the IC. Further, the size and/or positioning of blocks such as PROC610within the IC are for purposes of illustration only and are not intended as limitations.

As defined herein, the term “automatically” means without human intervention. As defined herein, the term “user” means a human being.

As defined herein, the term “responsive to” and similar language as described above, e.g., “if,” “when,” or “upon,” means responding or reacting readily to an action or event. The response or reaction is performed automatically. Thus, if a second action is performed “responsive to” a first action, there is a causal relationship between an occurrence of the first action and an occurrence of the second action. The term “responsive to” indicates the causal relationship.

As defined herein, the term “processor” and “microprocessor” mean at least one circuit capable of carrying out instructions contained in program code. The circuit may be an integrated circuit or embedded in an integrated circuit.

As defined herein, the term “soft” in reference to a circuit means that the circuit is implemented in programmable logic or programmable circuitry. Thus, a “soft processor” means at least one circuit implemented in programmable circuitry that is capable of carrying out instructions contained in program code.

As defined herein, the term “output” means storing in physical memory elements, e.g., devices, writing to display or other peripheral output device, sending or transmitting to another system, exporting, or the like.

The flowcharts and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems and methods according to various aspects of the inventive arrangements. In some alternative implementations, the operations noted in the blocks may occur out of the order noted in the figures. For example, two blocks shown in succession may be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. In other examples, blocks may be performed generally in increasing numeric order while in still other examples, one or more blocks may be performed in varying order with the results being stored and utilized in subsequent or other blocks that do not immediately follow. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, may be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.