Patent Description:
<NPL>) suggests to re-purpose unused Block RAM resources to additionally support multiple contexts next to earlier-mentioned modes since the implementation of register file design still results in unused resources due to the coarseness of the BRAMs. The advantage of this is the reduction of interrupt latency and task switching latency, which are important in real-time and embedded systems.

<CIT> discloses a processor including an instruction fetch unit configured to issue instructions for execution, where the instructions are selected from a number of threads, where each given instruction has a corresponding thread identifier, and where at least some of the instructions specify operand(s) via register identifiers. A register file stores operands usable by the instructions, and may include several banks, each corresponding to a register identifiers and including several entries corresponding to the several threads, wherein the entries are configured to store data values.

Various embodiments include an instruction fetch mechanism within a processor system that has multiple hardware contexts by which the processor system executes instructions from multiple instruction threads in some interleaved fashion. The instruction fetch mechanism fetches an entire cache block from the instruction cache or instruction memory as one unit and stores it into one of a plurality of temporary storage locations, where the temporary storage locations are each associated with a particular thread of execution. To execute instructions from a particular thread, they are taken from the local storage associated with that thread. When an instruction to be executed is not present in the local storage then a fetch is initiated to fill the local storage.

Various embodiments include a processor system comprising: a logical register file set including a plurality of physical memory arrays, each of the memory arrays having an access time and plurality of access ports, each register file of the register file set being assigned to a different hardware context; a plurality of hardware contexts, each of the hardware contexts comprising: one of the logical register files and a row of a context unit, the context unit including a plurality of rows associated with different hardware contexts, the row of the context unit further including: a program counter storage, an instruction block storage configured to store a block of instructions, logic configured to fetch the block from a cache, and logic configured to indicate that an instruction is ready to be issued from the row; a plurality of pipelines each including at least one execution unit; and issue logic configured to select a row from among the plurality of rows and to issue an instruction from the selected row to one of the plurality of pipelines, wherein the selection of the row is based on a ready state of the selected row, wherein the issue logic is configured to select the row such that the logical register file set is accessed at a frequency greater than one divided by the access time of a single memory array, by requiring instructions from the same hardware context to be spaced apart in time by a minimum of the number of clock cycles required to access that memory array through that port.

Various embodiments include a processor system comprising: a pipeline including an execution unit; an instruction cache; a context unit including a plurality of rows, each of the plurality of rows being assigned to an independent thread, each of the plurality of rows including at least one program counter, each of the plurality of rows including storage configured to store one or more instructions, each of the plurality of rows including logic configured to fetch the one or more instructions from the instruction cache, and each of the plurality of rows including logic configured to determine when an instruction is ready to be issued to the pipeline from the respective row; and issue logic configured to select a row from among the plurality of rows and to issue an instruction from the selected row to the pipeline.

Various embodiments include a method of executing a set of computing instructions, the method comprising: moving instructions associated with an instruction thread from memory into a hardware context row that is associated with the same instruction thread, the row including a program counter and storage configured to store the moved instruction, wherein there is a plurality of rows, each associated with a different instruction thread and each row holding a portion of a hardware context, and including control logic whose behavior depends upon the history of past actions plus inputs to the system and having at least two functions, where such control logic is optionally embodied by finite state machines with a first finite state machine configured to indicate that an instruction is ready to be issued from the respective row, and each of the plurality of rows including a second finite state machine configured to control fetching of one or more next instructions to be executed by the hardware context, wherein moving the instructions is responsive to the issuing of an instruction from the row, and moving the instruction takes an access time; the first finite state machine in a row determining that an instruction is ready to be issued from the row to a pipeline, which involves avoiding conflicts over instructions in progress attempting to use the same single-use internal resource, for example more than one attempting to access the same port of a particular memory array that stores instruction register data; choosing a row from among those that are ready to issue an instruction, and issuing the ready instruction from that row, which involves moving the instruction to the pipeline; updating the program counter of the row that issued an instruction, to reflect the address of the next instruction to be issued from that row; and executing the instruction using the pipeline wherein instructions are issued to the pipeline at a rate faster than the physical memory arrays, which store the data indicated by register addresses within the instructions, can be accessed.

Various embodiments include an instruction fetch mechanism within a processor system that has multiple hardware contexts by which the processor system executes instructions from multiple instruction threads in some interleaved fashion. The instruction fetch mechanism fetches an entire cache block from the instruction cache or instruction memory as one unit and stores it into one of a plurality of temporary storage locations, where the temporary storage locations are each associated with a particular thread of execution. To execute instructions from a particular thread, they are taken from the local storage associated with that thread. When an instruction to be executed is not present in the local storage then a fetch is initiated to fill the local storage. Optionally, wherein instructions are issued to the plurality of pipelines at a frequency faster than one over an access time of the physical memory arrays, which store the data indicated by register addresses within the instructions. Optionally, wherein the state of the first finite state machine is responsive to progress of execution of an instruction through the pipeline. Optionally, further comprising partial decoding the instruction while the instruction is in the row and determining a number of clock cycles until it is safe to issue the next instruction from the row, wherein the state of the first finite state machine is responsive to the number of clock cycles.

As used herein the term "independent threads" is used to refer to sets of computer instructions whose respective instructions are not dependent on each other, although independent threads may share general purpose memory.

As used herein the term "hardware context" is used to refer to hardware dedicated to executing an independent thread. In various embodiments, a hardware context can include a logical register file, a program counter storage, metadata representing state of the hardware context, and/or one or more execution units. A hardware context may include parts of a row of a context unit as discussed further elsewhere herein.

As used herein the term "control status register" is used to refer to a logical mechanism by which an instruction can gain meta-information about the state of the system or affect the state of the system, where the system includes both the processor core and mechanisms outside of the processor core such as interrupt controller, peripherals in the system (e.g., on-chip network), and/or the like. Functions of the control status register include tracking knowledge about past instruction executions, such as the total count of the number of instructions previously executed in the instruction stream, knowledge about the presence of an interrupt request, the ability to clear such an interrupt request, and/or to change the mode of processing or to configure co-processors, and so on.

As used herein the term "finite state machine" is used to refer to control logic that chooses actions based on a particular sequence of previous activity within the system. Such control logic uses system state to differentiate between alternative possible preceding paths. A finite state machine is configured to represent a current state based on prior events. The represented state is one of a finite plurality of allowed states.

<FIG> illustrates a Processor <NUM>, according to various embodiments of the invention. Processor <NUM> includes circuits for executing software instructions. One or more of Processor <NUM> may be included in a computing device. In various embodiments, Processor <NUM> is implemented on a silicon chip, implemented in an FPGA, disposed within a single package or distributed among multiple packages. In some embodiments, more than one of Processor <NUM> is included in a single package.

In some embodiments, Processor <NUM> comprises a logical register file set <NUM>, a plurality of Pipelines <NUM>, a level <NUM> Instruction Cache <NUM>, a level <NUM> Data Cache <NUM>, System Control Logic <NUM>, and a Context Unit <NUM>. The logical Register File Set <NUM> is comprised of a plurality of logical Register Files 125A, 125B, 125C. The Pipelines <NUM> each contain an Execution Unit <NUM>. The Execution units 145A and 145B perform calculations such as addition, subtraction, comparison, logical AND, logical OR, and so on. Multiple types of execution unit can be included, such as Floating Point, Vector, and/or the like. A Floating Point execution unit operates on data that encodes a number in the form of a mantissa plus an exponent. A Vector execution unit operates on a group of datums as a single operand. The elements of the group can be floating point format, or integer format, or some other format such as representing graphical data or some custom format.

Processor <NUM> further includes an optional instruction Cache <NUM> configured to store computing instructions organized into sets. The computing instructions may be executed by two or more different independent threads. During execution, the computing instructions are typically copied to Instruction Cache <NUM> from memory external to Processor <NUM>.

Processor <NUM> further includes an optional Data Cache <NUM> configured to store data to be processed by the computing instructions stored in Instruction Cache <NUM>. The data stored in Data Cache <NUM> contains data that may be copied to and from memory external to Processor <NUM> and/or may be the result of instruction execution within Processor <NUM>.

Processor <NUM> further includes one, two or more Pipelines <NUM>, referenced individually as Pipeline 135A, 135B, etc. Pipelines <NUM> are configured to execution of software instructions. For example, Pipeline 135A may be configured to indicate it is ready for a new instruction, to receive an instruction, to decode the received instruction, obtain data on which the instruction will operate and then pass the instruction and data to Execution Unit 145A.

Each Pipeline <NUM> includes one or more dedicated Execution Units <NUM>, individually referenced as 145A, 145B, etc. Execution Units <NUM> can include an arithmetic logic unit configured to do integer arithmetic and logic, a floating-point logic unit configured to operate on floating point data, a vector logic unit configured to perform vector operations, and/or the like. In some embodiments one or more of Execution Units <NUM> are shared by Pipelines <NUM>.

Processor <NUM> further includes a register file set comprising two or more Register Files <NUM>, individually labeled 125A, 125B, etc. Each of Register Files <NUM> is included in a different hardware context. Register Files <NUM> are logical constructs that may be mapped to actual physical memory arrays in a variety of different ways. For example, particular hardware contexts may be mapped to particular physical memory arrays accessible through access ports of the physical memory. A physical memory array may have <NUM>, <NUM>, <NUM> or more access ports, which can be used independently. Register Files <NUM> are characterized by an "access time. " The access time is the time required to read or write data to or from the Register Files <NUM>. The access time may be measured in clock cycles or absolute time.

Processor <NUM> further includes a Context Unit <NUM>. Context Unit <NUM> includes a plurality of data structures, referred to herein as "rows", each associated with a different hardware context. A particular hardware context includes at least one logical register file, e.g., Register File 125A, and a row of Context Unit <NUM>.

Context Unit <NUM> is configured to hold instructions in the rows until the instructions are ready to be executed using one of Pipelines <NUM>. Issue Logic <NUM> is configured to control the issuance of instructions from the rows of Context Unit <NUM> to members of Pipelines <NUM>.

<FIG> illustrate further details of Context Unit <NUM>, according to various embodiments of the invention. Context Unit <NUM> includes a plurality of Rows <NUM>, individually identified as Row 310A, Row 310B, etc. Each of Rows <NUM> is associated with a different hardware context. As such, each of Rows <NUM> is assigned to execution of a different independent software thread. Context Unit <NUM> includes at least two Rows <NUM>, and can include, for example, <NUM>, <NUM>, <NUM>, <NUM> or <NUM> rows, or any number of rows between these values. In some embodiments, Context Unit <NUM> includes more than <NUM> rows. Rows <NUM> may be mapped to any configuration of physical memory and physical logic. In some embodiments, Rows <NUM> are disposed within Processor <NUM> to minimize time and/or power required to move instructions from Rows <NUM> to Pipelines <NUM>.

<FIG> illustrates further details of a Context Unit <NUM> including a plurality of Rows <NUM>. While the Rows <NUM> of Context Unit <NUM> are referred to as "rows," the contents thereof do not necessarily need to be disposed in a row physical structure. Each "Row" <NUM> may be a logical mapping to physical memory and physical logic in variety of alternative structures.

<FIG> illustrates further details of Row 310A of Context Unit <NUM>, as an example of a typical member of Rows <NUM>, according to various embodiments. A Row 310A contains an Instruction Block Storage <NUM>. Instruction Block Storage <NUM> can include, for example, memory configured to store <NUM>, <NUM>, <NUM>, <NUM>, <NUM> or other desired number of instructions. Instructions are transferred to Instruction Block Storage <NUM> from Instruction Cache <NUM> or instruction memory external to Processor <NUM>. The transfer of instruction blocks is limited by the access time of the Instruction Cache <NUM> or instruction memory external to processor <NUM>. Transfer from optional instruction Cache <NUM> or directly from external instruction memory to Instruction Block Storage <NUM> is controlled by history dependent control logic within each row that is optionally configured as a Fetch Finite State Machine <NUM>. When the next instruction to be issued from a context is not present in Instruction Block Storage <NUM> then Fetch Finite State Machine <NUM> issues a request to cache <NUM> to fetch a new block of instructions. Arbitration logic that is contained within System Control Logic <NUM> ensures that no greater number of accesses are presented to cache <NUM> in a given cycle than the maximum number that cache <NUM> can initiate each cycle. System Control Logic <NUM> is configured to manage the transfer of instruction blocks from Cache <NUM>. For example, System Control Logic <NUM> is configured to transfer blocks of instructions coming out of cache <NUM> to the appropriate row.

Ready Instruction Storage <NUM> is a logical element that may be a storage for one instruction expected to be issued next, or it may be an output of logic that selects an instruction from Instruction Block Storage <NUM>.

History dependent control logic within Row 310A that is configured as Fetch Finite State Machine <NUM> requests transfer of instructions from Cache <NUM>. Fetch Finite State Machine <NUM> is further configured to select the next instruction to issue out of Instruction Block Storage <NUM>. Fetch Finite State Machine <NUM> is further configured to signal to Ready Finite State Machine <NUM> when the next instruction to issue from the row is present in the row. Ready Finite State Machine <NUM> receives signals from the pipeline that indicate when a control flow instruction, e.g., an instruction that can control an order in which instructions are executed, from that row is being executed in the pipeline, and it receives notice when that control flow instruction has resolved, e.g., when the order of instruction execution is determined. If the control flow instruction has caused a change in flow then the address of the new instruction is sent from Pipeline 135A to Fetch Finite State Machine <NUM>. When the next instruction to issue from the row has an address that is not in Instruction Block Storage <NUM> then Fetch Finite State Machine <NUM> sends a request to Cache <NUM> to send a block of instructions that includes the next instruction to issue, and places these instructions into Instruction Block Storage <NUM>. It then notifies Ready Finite State Machine <NUM> that the next instruction is present.

History dependent control logic within Row 310A that is configured as Ready Finite State Machine <NUM> determines when the next instruction is ready to be issued from Row 310A. Ready Finite State Machine <NUM> is configured to prevent access to a particular physical memory array port within Register File <NUM> that is associated with the same hardware context as the Row <NUM> that contains Ready Finite State Machine <NUM> from happening more than once within the access time of the respective memory array. Specifically, if the access time of a particular physical memory Port 420A is X clock cycles, then Ready Finite State Machine <NUM> is configured to require a delay of at least X clock cycles between starts of instructions that would access the same memory Port 420A.

Using this requirement, Pipelines <NUM> can still be configured to access the logical Register File Set <NUM> more than one time during the access time of a particular physical memory array, i.e., at a frequency greater than one divided by the access time of a particular memory array. This is achieved because Ready Finite State Machine <NUM> is configured to only enable issue of instructions from its Row 310A that access different memory ports and/or different Register Files <NUM> of Registrar File Set <NUM> from ones that are already occupied in performing an access.

Typical embodiments include multiple memory arrays <NUM>, within Register File Set <NUM>, and employs control logic inside of Ready Finite State Machine <NUM> that ensures that no two instructions will attempt to use the same port of the same physical memory array in an overlapped fashion. Successive instructions that are issued from Context Unit <NUM> to Pipelines <NUM> are carefully chosen such that the particular register entries to which their reads and writes are mapped will access different Ports <NUM> than any read or write that they will overlap with in time.

<FIG> illustrates a timing diagram of memory port access, according to various embodiments of the invention. Horizontal lines indicate that time during which a particular port is accessed. The length of the lines represent the access times (X) for the respective ports. The ports shown, A-E, may be divided among multiple memory arrays. A memory port A is first accessed at a Time <NUM> and the access is completed at a Time <NUM>. Between Time <NUM> and Time <NUM>, access to Ports B-E are initiated but not necessarily completed. Under the control of Control Logic <NUM> another attempt to access Port A is not made until a Time <NUM>, after Time <NUM>. Memory port B may be accessed less than X clock cycles after a read operation is initiated at memory port A. This staggered approach to register access allows register read and write operations in parallel at a frequency greater than would be possible if only a single port was being accessed.

Processor <NUM> further includes Issue Logic <NUM>. Issue Logic <NUM> is configured to select a Row <NUM> from within Context Unit <NUM> and to issue an instruction from the selected row to one of Pipelines <NUM>. It also issues the value of Program Counter <NUM> and the number of the row from which the instruction comes. The number of the row that the instruction is taken from is also sent and serves as the identifier of the context to which the instruction belongs.

Issue Logic <NUM> is typically configured to make the selection in response to an indication from one of Pipelines <NUM> that The Pipeline <NUM> is ready for a next instruction. The selection is based on the selected row being in a "ready state. " As discussed further elsewhere herein, the ready state is optionally indicated by a "ready bit" or ready signal. When in the ready state a row is ready to issue the next instruction in an associated independent software thread. The position of that instruction within memory is indicated by Program Counter <NUM>.

The identifier of the hardware context that the instruction is issued from is also sent to the pipeline together with the instruction and the program counter value. In some embodiments, the identifier of the hardware context is an identifier of the row from which the instruction is issued.

In some embodiments, each of Pipelines <NUM> includes one specific type of Execution Unit <NUM>. In these embodiments, the selection of a Row <NUM> from which to issue an instruction is optionally further dependent on a match between the type of instruction that the Execution Unit <NUM> is configured to process and the type of instruction ready to be issued from particular members of Rows <NUM>. This approach typically requires that the instructions be at least partially decoded while in Rows <NUM>. In this approach either Ready Finite State Machine <NUM> performs the partial decode or Issue Logic <NUM> performs the partial decode.

In alternative embodiments Pipeline 135A, instructions may be issued to Pipeline 135A without regard to the type of Execution Unit(s) 145A associated with that particular pipeline. In this case, it may be discovered, after decoding an instruction, which the instruction is of the wrong type for Execution Unit 145A. As a result, Pipeline 135A will transfer the instruction after decode to a different member of the plurality of Pipelines <NUM>, which contains the appropriate type of Execution Unit <NUM> for the instruction.

In some embodiments, Processor <NUM> includes a different instance of Issue Logic <NUM> for each type of Pipeline <NUM>. In these embodiments, each instance of Issue Logic selects only instructions of the type appropriate for the pipeline(s) it is attached to. Optionally, each of Pipelines <NUM> is associated with its own instance of Issue Logic <NUM>.

Row310A further includes a Ready Bit <NUM>. Ready Bit <NUM> is configured to be used by issue logic <NUM> to select a row from among the plurality of Rows <NUM> and to issue an instruction from the selected Row <NUM> to one of a plurality of Pipelines <NUM>. On each clock cycle, Issue Logic <NUM> is configured to scan the Ready Bits <NUM> of rows <NUM>, and selects from among the ones that have their Ready Bit <NUM> asserted. The selected row has its ready instruction taken from its Ready Instruction Storage <NUM> and sent to one of Pipelines <NUM>. Thus, the issue logic <NUM> is responsive to a Ready Bit <NUM> asserted by Ready Finite State Machine <NUM> included in the selected row. If not all pipelines take the same format of operand, then Issue Logic <NUM> may optionally ensure that the instruction is of the correct format for the pipeline to which it is issued.

Each of Rows <NUM> further includes a Program Counter <NUM>. When an instruction is issued to a Pipeline <NUM>, it is accompanied by the address at which that instruction resides within the memory address space. Program Counter <NUM> is configured to hold this address. The control logic that exists inside of Finite State Machine <NUM> is configured to update the contents of Program Counter <NUM> to ensure that the contents are correct when an instruction is issued. The content of the respective Program Counter <NUM> (e.g., the memory address) is sent to Pipeline <NUM> together with each instruction issued from a member of Rows <NUM>.

Each of Rows <NUM> optionally further includes Control/Status Registers <NUM>. Control and Status Registers <NUM> can include memory configured to store data indicative of a status of Processor <NUM> and/or serve as a port to control operation of Processor. Control and status registers serve as an interface mechanism that allows instructions to access meta information about the system and to manipulate the system. Such meta information includes, for example, the presence of a request for an interrupt, the cause of such a request, status information such as the total number of instructions executed by the thread since the last reset. Performing a write operation on a Control and Status Registers <NUM> may be used for: clearing a request for interrupt, changing the operating mode of a pipeline or co-processor, and/or the like. Some of the Control and Status Registers <NUM> are shared between multiple Rows <NUM>, for example the control register that is used to access the real time clock, while other control and status Registers <NUM> are specific to individual members of Rows <NUM>, for example the status register that is used to access the total number of instructions that have been completed from that row's context.

Each of Rows <NUM> further includes a Fetch Finite State Machine <NUM>. Fetch Finite State Machine <NUM> is configured to manage blocks of instructions within Row 310A. This management includes, for example, issuing a request to fetch a new block of instructions from Cache <NUM>, storing a received block of instructions in Instruction Block Storage <NUM>, updating Program Counter <NUM> to ensure that holds the correct memory address when an instruction is issued from Row 310A, placing an instruction in Ready Instruction Storage <NUM>, and sends signals to Ready Finite State Machine <NUM> (discussed further elsewhere herein). Specifically, Fetch Finite State Machine <NUM> is configured to fetch a block of instructions from L1 Instruction Cache <NUM> whenever the next instruction to issue from the row is not present in Block Storage <NUM>. This condition can occur in many ways, including when all the instructions in Instruction Block Storage <NUM> have been processed or when a branch has been taken to an instruction not yet in Instruction Block Storage <NUM>. Fetch Finite State Machine <NUM> is configured to increment Program Counter <NUM> if the next instruction in the block of instructions is the next instruction to be executed, or if a control flow instruction has occurred in the instruction thread, to store the computed target address of a branch or jump into Program Counter.

Fetch Finite State Machine <NUM> is configured to place an instruction in Ready Instruction Storage <NUM>. Ready Instruction Storage <NUM> may be its own separate storage element, or it may be a system that selects one particular instruction out of Instruction Block Storage <NUM>. Ready Instruction Storage <NUM> serves as the portal from which instruction issue logic <NUM> takes the instruction when it is issued from the row. When a next instruction is placed in Ready Instruction Storage <NUM> this fact is communicated to Ready Finite State Machine <NUM>. Details of the requirements to place an instruction in Ready Instruction Storage <NUM>, and indicate that the instruction is present, are discussed elsewhere herein. See, for example, <FIG> and <FIG>.

Each of Rows <NUM> further includes Ready Finite State Machine <NUM>. Ready Finite State Machine <NUM> is configured to control the issuance of instructions from Row 310A to members of Pipelines 135A or 135B. Typically, the issued instruction is the one stored in Ready Instruction Storage <NUM> for the respective Row <NUM>. In some embodiments, Ready Finite State Machine <NUM> is configured to track the execution progress of previous instructions from the same thread or optionally from other threads and may optionally receive information regarding of the types of previous instructions and the type of the instruction to be issued next. Based on the type and progress of previous instructions Ready Finite State Machine <NUM> is configured to indicate when the instruction in Ready Instruction Storage <NUM> is ready to be issued to a pipeline for execution. One criterion for the instruction being ready to issue is that Fetch Finite State Machine <NUM> first indicates that the next instruction to issue is currently available in Ready Instruction Storage <NUM>. When Ready Finite State Machine <NUM> determines that instruction in Ready Instruction Storage <NUM> is ready, it signals this readiness by setting Ready Bit <NUM> accordingly. Note that in alternative embodiments, the functions of Fetch Finite State Machine <NUM> and Ready Finite State Machine <NUM> may be redistributed between these two elements of Row 310A.

Processor <NUM> further includes System Control Logic <NUM>. System Control Logic <NUM> manages system level control operations, including managing requests made to instruction Cache <NUM> and Data Cache <NUM>. System Control Logic <NUM> arbitrates among multiple requests made to the caches. System Control Logic <NUM> also tracks an identifier of the context from which an instruction was issued. System Control Logic <NUM> also manages sending signals between elements of Processor <NUM> that relate to the status of instruction execution. For example, System Control Logic <NUM> detects when a memory operation has completed access to Data Cache <NUM> and sends a signal indicating completion to the row that the instruction came from, and optionally an identifier of which instruction completed.

<FIG> illustrates two Memory Arrays 410A and 410B, which each have three Ports <NUM>, individually labeled 420A-420F, through which to access the contents of the Memory Array Rows 450A through <NUM>. Processor <NUM> further includes a plurality of Memory Arrays 410A, 410B and so on which are used to implement the Register Files <NUM> and are used within Instruction Cache <NUM> and Data Cache <NUM> and elsewhere. Memory Array <NUM> can be implemented as an SRAM array, an array of flip flops, an array of latches, or an array of specialized bit cells designed for use as register file memory. The arrays are optionally implemented with physical means to access the contents of Memory Array Rows <NUM>, which is generally termed a Port <NUM>. For example Memory Array 410A has two read Ports (420A & 420B) and one write Port 420C, which allows a read to be taking place at the same time as a write is taking place.

<FIG>, <FIG>, <FIG>, and <NUM> illustrate methods of executing multiple independent threads, according to various embodiments of the invention. The methods comprise multiple concurrent processes that interact. <FIG> illustrates the process of fetching instructions from the memory system into a Row <NUM>. <FIG> illustrates the process of ensuring that an instruction in a row is ready and then signaling its readiness. <FIG> illustrates the process of executing an instruction and signaling its progress and outcome. <NUM> illustrates the process of performing a memory operation and signaling its status.

<FIG> illustrates the process of fetching instructions form the memory system into a Row <NUM>. The process begins at an Attempt Advance Step <NUM> where Fetch Finite State Machine <NUM> attempts to advance to the next instruction in Instruction Block Storage <NUM>. This step fails if the next instruction to execute in the thread has an address that is outside the addresses of the instructions in Instruction Block Storage <NUM>.

In Present? Step <NUM> a next action is chosen based on whether the advance to the next instruction was successful. If not successful, then the next step is Issue Fetch <NUM> wherein a fetch request is issued.

Issue Fetch Step <NUM> occurs when the next instruction to execute in the thread is not present in the local Instruction Block Storage <NUM> of the respective Row <NUM>. In this case, Fetch Finite State Machine <NUM> issues a fetch request to Instruction Cache <NUM>. Many of Rows <NUM> may issue requests in overlapped fashion, however Instruction Cache <NUM> may only be able to process fewer requests than are issued. To handle this case, System Control Logic <NUM> includes arbitration logic that organizes the sequence of requests entering Instruction Cache <NUM>.

In a Wait Step <NUM> the system waits for the Instruction Cache <NUM> to retrieve/provide the indicated instructions. This may involve a cache miss, in which case the instruction must be fetched from memory outside of Processor <NUM>. A cache miss requires some amount of time to complete the request.

In a Receive Step <NUM> a block of instructions is received from Instruction Cache <NUM>.

In a Store Instructions Step <NUM> the received block of instructions is stored into Instruction Block Storage <NUM> of the respective Row <NUM>. Once Store Instructions Step <NUM> is complete, the method returns to Present? Step <NUM>.

At Present? Step <NUM>, if the answer is yes, then steps <NUM> and <NUM> are performed in parallel.

In an Adjust PC Step <NUM> the program counter is adjusted so that it has the correct address of the instruction that is present in Ready Instruction Storage <NUM>.

In A Move Step <NUM> the next instruction to be executed by the thread is made available in Ready Instruction Storage <NUM>, from which the instruction will be issued by Issue Logic <NUM> to a chosen Pipeline <NUM>.

In an Inform Ready Step <NUM> Fetch Finite State Machine <NUM> sends a signal to Ready Finite State Machine <NUM> that the instruction is present in Ready Instruction Storage <NUM>.

In a Wait Step <NUM> the process waits for a signal from Issue Logic <NUM> indicating that the row has been chosen to issue an instruction. Once this signal is received, Fetch Finite State Machine <NUM> loops to Step <NUM> to attempt to advance to making the next instruction in the instruction stream become present in Ready Instruction Storage <NUM>.

<FIG> illustrates the process of ensuring that an instruction in a row is ready to be issued and then signaling its readiness. This process optionally takes place in every Row <NUM> simultaneously and/or in parallel. Once started, the rows continue this process endlessly until the processor system is reset, or optionally some configuration is performed that disables one of Rows <NUM>, such as through the Control and Status Registers <NUM>.

The process begins at Present? Step <NUM> where a check is performed inside Ready Finite State Machine <NUM> to determine whether the next instruction to issue from the Row <NUM> is present in Ready Instruction Storage <NUM>.

If the instruction is not present, then in a Wait Step <NUM> Ready Finite State Machine <NUM> waits until Fetch Finite State Machine <NUM> signals that it is present. Then the process proceeds to an Interference? Step <NUM>.

If the instruction is present in Present? Step <NUM>, then the process proceeds directly to Interference? Step <NUM>.

Interference? Step <NUM> takes place within a single member of Rows <NUM>, and involves multiple elements from that Row <NUM>. Interference? Step <NUM> checks whether there may be interference between instruction in Ready Instruction Storage <NUM> and instructions that were previously issued from the same member of Rows <NUM>. Such interference can include conditions such as the port of the physical memory array accessed by the registers specified in the instruction present in Ready Instruction Storage <NUM> will be in use by a different instruction if instruction in Ready Instruction Storage <NUM> were to be issued on the next cycle. Another example is when the instruction in Ready Instruction Storage <NUM> is a memory access instruction, but there is a previous memory access instruction from the same Row <NUM> still being executed.

If there is interference, then the process proceeds to Wait Step <NUM>. In Wait Step <NUM>, Ready Finite State Machine <NUM> waits until all interference has resolved. Ready Finite State Machine <NUM> detects resolution by receiving signals from a plurality of other portions of Processor <NUM> where those signals indicate the status of instructions that were previously issued. Examples of such signals include the System Control Logic <NUM> sending a signal indicating completion of a memory access instruction to the Row <NUM> that issued the instruction upon completion of the access by the L1 Data Cache <NUM>. System Control Logic <NUM> tracks the context from which each instruction is issued and uses this information to deliver the signal to the correct Row <NUM>. The Ready Finite State Machine <NUM> in the row that received the signal then updates its state due to receipt of the signal. If receipt of that signal clears all interference associated to the instruction in Ready Instruction Storage <NUM> then Ready Finite State Machine <NUM> stops waiting and the process proceeds to A Signal Step <NUM>.

In Signal Step <NUM> Ready Bit <NUM> is asserted, which is the signal to Issue Logic <NUM> that informs Issue Logic <NUM> that the Row <NUM> that contains the Ready Bit <NUM> is ready to have its instruction held in Ready Instruction Storage <NUM> issue to the pipeline. The process then proceeds to A Wait Step <NUM>.

In Wait Step <NUM>, both Fetch Finite State Machine <NUM> and Ready Finite State Machine <NUM> wait for the member of Rows <NUM> that contains them to be selected by Issue Logic <NUM>. Issue Logic <NUM> provides a signal to both finite state machines when Issue Logic <NUM> selects the Row <NUM> that contains them. When the wait is over, the process loops back to Present? Step <NUM>.

<FIG> illustrates the process of executing an instruction and signaling its progress and outcome. This process begins at the start stage each cycle in each of Pipelines <NUM> when an instruction is issued to the pipeline.

In a Receive Instruction Step <NUM> a valid instruction is received into Pipeline 135A. The instruction is transferred from a selected member of Rows <NUM> by Issue Logic <NUM>. The process next goes to both an Extract Register Addresses Step <NUM> and a Decode Step <NUM>, optionally in parallel.

In Extract Register Addresses Step <NUM> bits are extracted from the received instruction. Most instructions of most instruction set architectures specify one or more registers that hold the inputs to the instruction. The extracted bits identify the logical registers that hold the data to use as input to the execution unit. The bits that indicate a register are sent to Register File Set <NUM> where they are used to access a particular location from a particular memory array through a particular memory port. The process then proceeds to a Receive Register Contents Step <NUM>.

In Decode Step <NUM> the received instruction is decoded, which determines the type of instruction, the kind of execution unit it requires, and/or the like. The type of instruction sometimes determines how many clock cycles the instruction will take and, thus, how soon the next instruction in the stream can be issued.

In a Conditionally Inform Row Step <NUM>, if the instruction is of a type that allows it to be followed closely then in this step the Pipeline 135A sends a signal to System Control Logic <NUM> which in turn delivers the signal to the member of Rows <NUM> from which the instruction was issued. In the member of Rows <NUM> that receives the signal, the Ready Finite State Machine <NUM> uses the signal in its determination of whether the next instruction from that row is ready to be issued. This step is optionally accomplished in other ways such as placing a partial decoder and counter in Ready Finite State Machine <NUM> that counts down the number of clock cycles it has to wait until interference with this type of instruction is no longer possible.

In a Receive Register Contents Step <NUM> the data to be operated upon is received by Pipeline 135A and is used as input to the Execution Unit 145A that is inside Pipeline 135A.

In a Perform Operation Step <NUM> the instruction executes in Execution Unit <NUM>.

A Flow Control Step <NUM> is a decision point in the process. If the instruction is not a control flow type then the next step is <NUM>. If it is a control flow type then the next step is <NUM>. A flow control type is a type of instruction that can control the order in which instructions are executed.

A MemOp? Step <NUM> is a decision point in the process. If the instruction type is not a memory operation such as a load instruction or a store instruction then the next step is a Send Result Step <NUM>. If it is a memory operation then the next step is a Send MemOp Step <NUM>.

Sent Result Step <NUM> is for a non-control flow and non-memory operation. For this type of instruction, a result of execution is normally generated by the Execution Unit <NUM>, and this result is sent to the Register File Set <NUM> by System Control Logic <NUM>. The next step is a Write Result Step <NUM>.

In Write Result Step <NUM> the result sent from Pipeline <NUM> is written into a physical memory. It is guaranteed that the port of the memory array that the result is written into is free because Ready Finite State Machine <NUM> is configured to only make instructions ready for issue to Pipelines <NUM> if there will be no conflicts during this step of writing the result. Alternatively, System Control Logic <NUM> can be configured to ensure that no two writes occupy the same port of the same physical memory array in an overlapped fashion.

Send MemOp Step <NUM> is for memory operation type of instructions. In this step, the memory operation to perform, the memory address, and optionally the data to write are made available to System Control Logic <NUM> which arbitrates among the many pipelines trying to access to the Data Cache <NUM>. Next is an Inform ctxt Unit Step <NUM>.

Inform ctxt Unit Step <NUM> takes an arbitrary amount of time, during which the memory system is accessed and the memory operation completes. Upon completion of the memory operation the System Control Logic <NUM> informs the Row <NUM> from which the instruction was issued that it has completed. The Ready Finite State Machine <NUM> in that row uses this information in its determination of whether that Row <NUM> is ready to issue its next instruction. Next is Store? Step <NUM>.

Store? Step <NUM> is a decision point in the process. If the completed memory operation is a load instruction then the next step is Write Result Step <NUM>. If it is not a load instruction then that is the end of execution of that instruction.

Write Result Step <NUM> is for load instructions. The result retrieved from the memory system is sent to the Register File Set <NUM> where the data is written into a physical memory array. This is the end of execution of this instruction.

Change Flow? Step <NUM> is for control flow instructions. It is a decision point in the process. Upon completion of processing on an instruction by Execution Unit <NUM> it is known whether the control flow instruction is taken or not. If it is not taken then the next step is an Inform ctxt Unit Step <NUM>. If it is taken then the next step is Send New Addr <NUM>.

Inform ctxt Unit Step <NUM> uses System Control Logic <NUM> to inform the Row <NUM> from which the instruction was issued that the branch was not taken. The Fetch Finite State Machine <NUM> uses this information to determine the instruction to place into Ready Instruction Storage <NUM>. This is the end of execution of this instruction.

Send New Addr Step <NUM> is for control flow instructions in which alteration of control flow does take place. An example of a control flow instruction is a taken branch instruction and another example is a jump instruction. In Send New Addr Step <NUM>, System Control Logic <NUM> is used to transfer the new instruction address to the row from which the control flow instruction was issued. This address is received by Fetch Finite State Machine <NUM> and determines what instruction is placed into Ready Instruction Storage <NUM>. This is the end of the execution of this instruction.

Several embodiments are specifically illustrated and/or described herein. However, it will be appreciated that modifications and variations are covered by the above teachings and within the scope of the appended claims.

For example, as used herein physical memory arrays can include an SRAM array, or an array of flip flops or latches or an array of transistors arranged as specialized register bit cells.

The embodiments discussed herein are illustrative of the present invention. As these embodiments of the present invention are described with reference to illustrations, various modifications or adaptations of the methods and or specific structures described may become apparent to those skilled in the art. All such modifications, adaptations, or variations that rely upon the teachings of the present invention, and through which these teachings have advanced the art, are considered to be within the scope of the present invention. Hence, these descriptions and drawings should not be considered in a limiting sense, as it is understood that the present invention is in no way limited to only the embodiments illustrated.

Computing systems referred to herein can comprise an integrated circuit, a microprocessor, a personal computer, a server, a distributed computing system, a communication device, a network device, or the like, and various combinations of the same. A computing system may also comprise volatile and/or non-volatile memory such as random access memory (RAM), dynamic random access memory (DRAM), static random access memory (SRAM), magnetic media, optical media, nano-media, a hard drive, a compact disk, a digital versatile disc (DVD), and/or other devices configured for storing analog or digital information, such as in a database. The various examples of logic noted above can comprise hardware, firmware, or software stored on a computer-readable medium, or combinations thereof. A computer-readable medium, as used herein, expressly excludes paper. Computer-implemented steps of the methods noted herein can comprise a set of instructions stored on a computer -readable medium that when executed cause the computing system to perform the steps. A computing system programmed to perform particular functions pursuant to instructions from program software is a special purpose computing system for performing those particular functions. Data that is manipulated by a special purpose computing system while performing those particular functions is at least electronically saved in buffers of the computing system, physically changing the special purpose computing system from one state to the next with each change to the stored data.

Claim 1:
A processor system (<NUM>) adapted to execute instructions from multiple instruction threads in interleaved fashion, the processor system comprising:
a plurality of pipelines (135A-C) each including an execution unit (<NUM> A-B);
an instruction cache (<NUM>);
a context unit (<NUM>) including a plurality of rows (<NUM> A-L), each of the plurality of rows:
- being assigned to an independent thread,
- including at least one program counter (<NUM>),
- including instruction block storage (<NUM>) configured to store one or more instructions,
- including logic (<NUM>) configured to fetch the one or more instructions from the instruction cache (<NUM>), and
- including logic (<NUM>) configured to determine when an instruction is ready to be issued to the pipeline (135A-C) from the respective row (<NUM> A-L); and
a logical register file set (<NUM>) comprised of a plurality of register files (<NUM> A-C) that are mapped to a plurality of physical memory arrays (<NUM>), each of the memory arrays (<NUM>) having an access time and a plurality of access ports, each register file (<NUM> A-C) of the register file set (<NUM>) being assigned to a different hardware context;
wherein each of the plurality of said hardware contexts being hardware dedicated to executing an independent thread and comprises:
one of the logical register files (<NUM> A-C) and
a row (<NUM> A-L) of said context unit (<NUM>), wherein the rows (<NUM> A-L) are associated with different hardware contexts; and
issue logic (<NUM>) configured to:
select a row (<NUM> A-L) from among the plurality of rows (<NUM> A-L),
wherein the selection of the row (<NUM> A-L) is based on a selected row (<NUM> A-L) being in a ready state, and
issue an instruction from the selected row (<NUM> A-L) to one of the plurality of pipelines (<NUM> A-B);
wherein the issue logic (<NUM>) is configured to alternatively select different rows (<NUM> A-L) of the plurality of rows (<NUM> A-L), such that a row (<NUM> A-L) of the same hardware context is not selected more than once within a time required to access one of the memory arrays (<NUM>).