USRE44129E1 - System and method for instruction-level parallelism in a programmable multiple network processor environment - Google Patents

Abstract

A system and method process data elements with instruction-level parallelism. An instruction buffer holds a first instruction and a second instruction, the first instruction being associated with a first thread, and the second instruction being associated with a second thread. A dependency counter counts satisfaction of dependencies of instructions of the second thread on instructions of the first thread. An instruction control unit is coupled to the instruction buffer and the dependency counter, the instruction control unit increments and decrements the dependency counter according to dependency information included in instructions. An execution switch is coupled to the instruction control unit and the instruction buffer, and the execution switch routes instructions to instruction execution units.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

The present invention is related to patent applications “System And Method For Processing Overlapping Tasks In A Programmable Network Processor Environment” (Ser. No. 09/833,581) and “System and Method for Data Forwarding in a Programmable Multiple Network Processor Environment” (Ser. No. 09/833,578), both of which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to digital computing. More specifically, the present invention relates to network processors for processing network data elements.

2. Discussion of the Related Art

Network switches and routers, or network switch elements, form the backbone of digital networks, such as the Internet. Network switch elements connect network segments by receiving network data from ingress network segments and transferring the network data to egress network segments. Because large telecommunications switching facilities and central offices aggregate network traffic from extensive networks and many network segments, they require high-speed and high-availability switches and routers.

Network switch elements select the egress network segment by processing the address or destination included in the network data according to network data processing program logic. Traditionally, network switch elements included Application Specific Integrated Circuits (ASICs) that provided the program logic. Because ASICs are “hard-coded” with program logic for handling network traffic, they provide the high speed necessary to process a large volume of network data. ASICs, however, make it difficult to upgrade or reconfigure a network switch element, and it is expensive to design and fabricate a new ASIC for each new type of network rig switch element.

In response to these drawbacks, manufacturers of network switch elements are turning to programmable network processors to enable network switch elements to process network data. Programmable network processors process network data according to program instructions, or software, stored in a memory. The software allows manufacturers and users to define the functionality of the network switch elements-functionality that can be altered and changed as needed. With programmable network processors, manufacturers and users can change the software to respond to new services quickly, without costly system upgrades, as well as implement new designs quickly.

To the extent that there is a drawback to the use of programmable network processors in network switch elements, that drawback relates to speed. Because programmable network processors process network data using software, they are usually slower than a comparable hard-coded ASIC. One of the major design challenges, therefore, is developing programmable network processors fast enough to process the large volume of network data at large telecommunications switching facilities.

One technique used to increase speed in traditional processor design is “instruction-level parallelism,” or processing multiple threads of instructions on a processing element in parallel. However, traditional instruction-level parallelism techniques are either highly complex, or would introduce unacceptable delays and timing problems into the processing of network data, which must be processed on a time critical basis.

SUMMARY OF THE INVENTION

The present invention provides a system and method for processing information using instruction-level parallelism. In the system, an instruction buffer holds a first instruction and a second instruction, the first instruction being associated with a first thread, and the second instruction being associated with a second thread. In this system, one or more instructions from the second thread may be dependent on the execution of one or more instructions in the first thread. A dependency counter is used to record dependencies of instructions between the first thread and the second thread. An instruction control unit is coupled to the instruction buffer and the dependency counter, the instruction control unit increments and decrements the dependency counter on the basis of information in the instructions. An execution switch is coupled to the instruction control unit and the instruction buffer, the execution switch sends instructions to an execution unit.

In the method, a first instruction associated with a first thread is loaded on a processing element. The processing element determines that execution of a second instruction depends on the execution of the first instruction, where the second instruction is associated with a second thread. A dependency counter associated with the second thread is incremented if the processing element determines that execution of a second instruction depends on the execution of the first instruction.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is described with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.

FIG. 1 illustrates a system block diagram of a data communications system.

FIG. 2 illustrates a system block diagram of a programmable network processor.

FIG. 3 illustrates a system block diagram of a multiprocessor core.

FIG. 4 illustrates a system block diagram of an exemplary processing element.

FIG. 5 is a diagram illustrating concurrent processing of three threads of instructions.

FIG. 6 illustrates concurrent processing of two threads of instructions.

FIG. 7 illustrates dependency counter groups.

FIG. 8 illustrates an exemplary instruction.

FIG. 9 illustrates an exemplary process for executing instructions.

FIG. 10 illustrates an exemplary process for executing instructions

DETAILED DESCRIPTION

Exemplary embodiments of the invention are discussed in detail below. While specific implementations are discussed, it should be understood that this is done for illustrative purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without parting from the spirit and scope of the invention.

Programmable network processors offer a number of advantages including flexibility, low cost, maintenance ease, decreased time to market, and increased service life. It is difficult, however, to develop a programmable network processor capable of meeting the demand for ever-increasing speed. One technique for increasing the speed of a programmable network processor is instruction-level parallelism. In instruction-level parallelism, threads of parallel programs can execute concurrently on a single processing element. Instruction-level parallelism allows a processing element to continue processing instructions, even if one or more threads are waiting for long-latency operations to complete.

One problem with instruction-level parallelism is maintaining synchronization of dependent instructions between the threads running on a processing element. Often, an instruction in one thread is dependent on the execution of instructions in another thread. Examples of instruction dependency are control dependency (i.e., the execution of one instruction is conditioned on the execution of another) and data dependency (i.e., one instruction uses the results of the execution of another instruction). Unfortunately, conventional techniques for synchronizing the execution of instructions among multiple threads do not lend themselves to programmable network processor applications. Conventional techniques introduce significant delays to processing, delays that are unsuitable for processing time critical network data elements.

The present invention is directed to a system and method for synchronizing the execution of multiple threads of instructions on a single processing element at high speed. An instruction in a first thread can include dependence indicators, such as a bit or bits, that indicate dependence of the instruction on the execution of a second thread. When a processing element encounters an instruction that includes dependence indicators that indicate dependence between threads, the processing element checks, decrements, or increments one or more dependency counters that record satisfaction of dependencies between instructions and threads. If a dependency indicator indicates that an instruction in a first thread is dependent upon the execution of a second thread, a dependency counter is checked. If the dependency counter is not above a threshold, the processing element suspends the execution of the first thread until the dependency counter is incremented by a second thread to above the threshold. This allows the processing element to maintain synchronized execution of dependent instructions between threads in a highly efficient manner. It should be recognized that the concepts described below are not restricted to processing network data elements but are extensible to a generic form of data processing. Prior to discussing the features of the present invention, a brief description of a data communications system is provided.

FIG. 1 illustrates a block diagram of a network data communications system, according to an embodiment of the present invention.Data communications system100 can be, for example, of the type used by network service providers and telecommunication carriers to provide voice and data communications services to consumers.Data communications system100 includesnetwork102,network line modules104₁–104_N, and switchfabric106. Note that a subscript “N” in the figures denotes a plurality of elements generally, and not a specific number or equality of number between different elements with a subscript “N.”

Network102 is connected to networkline modules104₁–104_Nwhich, in turn, are connected to switchfabric106. Althoughdata communications system100 is shown as including physical connections between the various components, other configurations are possible, such as wireless connections. Connections betweennetwork102,network line modules104₁–104_N, and switchfabric106 can be, for example, wireless data connections, data over copper, fiber optic connections (e.g., OC-48, OC-192, OC-768), or other data communications connections as would be apparent.

Network line modules104₁–104_Nsend and receive network data elements to (from)network102.Network line modules104₁–104_Nprocess the network data elements and communicate the process network data elements withswitch fabric106. Network data elements are signals carrying information including communications information. Examples of network data elements are asynchronous transfer mode (“ATM”) cells, Frame Relay frames, Internet Protocol (“IP”) packets, etc., and portions (segments) of these. Processing includes the concepts of performing a calculation or manipulation involving a network data element. Processing can include, for example, determining the next hop or egress port to which the network data element Star should be routed, network management, such as traffic shaping or policing, network monitoring, etc.Network102 is a network for communicating network data elements.Network102 can be, for example, the Internet, a telecommunications data network, an intranet, an extranet, a voice over data communications network, etc., and combinations thereof.

For descriptive clarity, operation ofdata communication system100 is described in terms ofnetwork line module104₁.Network line module104, includes network linemodule ingress port108, network linemodule egress port110, andprogrammable network processors112₁–112₂. Note that the configuration ofnetwork line modules104₁–104_Nis shown for illustrative purposes only, and alternate configurations fornetwork line modules104₁–104_Nare possible. Alternate configurations include, for example, single or additional programmable network processors per network line module, additional network line module ingress ports, multiple egress ports, additional connections to network102, etc.

Network line module1041 104₁receives network data elements fromnetwork102 at network linemodule ingress port108.Programmable network processor112₁receives network data elements from network linemodule ingress port108.Programmable network processor112 enables network line module1041 104₁to process the received network data elements.Programmable network processor112₁provides the network data elements to switchfabric106 after processing.

Switch fabric106 includes switchfabric ingress ports114₁–114_Nand switchfabric egress ports116₁–116_N. Switchfabric ingress ports114₁–114_Nreceive data fromnetwork line modules104₁–104_Nand switchfabric egress ports116₁–116_Nports provide data to networkline modules104₁–104_N.Switch fabric106 outputs network data elements received fromnetwork processor112₁on the desired switchfabric egress port116₁–116_N.Network line module104₁receives processed network data elements from switchfabric egress port116₁and performs additional processing, as required, and transmits the network data element to network102 via network linemodule egress port110. Note that network linemodule ingress port108, networkelement egress port110, switchfabric ingress ports114₁–114_N, and switchfabric egress ports116₁–116_Nare logical representations of physical devices, and other combinations, such as single ports that transmit and receive network data elements, are possible.

FIG. 2 illustrates a system block diagram of a programmable network processor, according to an embodiment of the present invention.Programmable network processor200 can be considered an exemplary embodiment of both ingress and egressprogrammable network processors112₁–112_N, as described above.Programmable network processor200 includesmemory controller204,input interface206,multiprocessor core202, andoutput interface208.Multiprocessor core202 is connected to inputinterface206,output interface208, andmemory controller204. Note that the particular configuration, number, and type of elements ofprogrammable processor200 are shown for illustrative purposes only and other configurations ofprogrammable network processor200 are possible as would be apparent.

For the purposes of this description, it is presumed that theprogrammable network processor200 ofFIG. 2 corresponds toprogrammable network processor112₁. In operation, such aprogrammable network processor200 receives network data elements from network linemodule ingress port108 viainput interface206.Input interface206 receives the network data elements and provides them tomultiprocessor core202 for processing as described above.Multiprocessor core202 processes the network data elements and provides the result tooutput interface208.Output interface208 receives processed network data elements frommultiprocessor core202 and forwards them to switchfabric106 for routing.Multiprocessor core202 accesses storage located offprogrammable network processor200 viamemory controller204.

Multiprocessor core202 is connected to hostcontrol processor210.Host control processor210 provides network management logic and information forprogrammable network processor200. Such network management logic and information includes, for example, generating and receiving network data elements for controllingswitch fabric106,network line modules104₁–104_Nand other network components.Host control processor210 performs other functions, such as generating network data elements for switch fabric control, setting up network connections and loading programs intomultiprocessor core202 for operation.

FIG. 3 illustrates a system block diagram of a multiprocessor core, according to an embodiment of the present invention.Multiprocessor core300 is an exemplary embodiment ofmultiprocessor core202, as described above. Althoughmultiprocessor core300 can be used for a generic form of data processing,multiprocessor core300 can also be of the type employed indata communications system100.Multiprocessor core300 includes processing elements (PE)302₁–302_N, data memories (DM)304₁–304_N, program memories (PM)306₁–306_N,intraswitch314, andhost control interface308.Processing elements302₁–302_Nare connected to programmemories306₁–306_N, andintraswitch314.Data memories304₁–304_Nare connected to intraswitch314.Program memories306₁–306_Nare connected to processingelements302₁–302_Nandintraswitch314.Host control interface308 is connected to intraswitch314.Intraswitch314 is connected to on-chipperipheral units310 and312. Examples of on-chipperipheral units310 and312 areinput interface206,output interface208, andmemory controller204 ofFIG. 2.

Processing elements302₁–302_Nprocess network data elements, thereby providing the processing functionality formultiprocessor core300.Processing elements302₁–302_Nexecute program instructions fromprogram memories306₁–306_N, and load and store data indata memories304₁–304_N. Each of processingelements302₁–302_Ncan process multiple threads of instructions concurrently, according to an embodiment of the present invention.

Program memories306₁–306_Nanddata memories304₁–304_Nprovide data storage functionality for the various elements ofmultiprocessor core300.Program memories306₁–306_Nstore program instructions for the processing of network data elements by processingelements302₁–302_N. AlthoughFIG. 3 depicts groups of four processing elements directly connected to one ofprogram memories306₁–306_N, other configurations connecting program memory to processing elements are possible, including for example, additional processing elements or program memories as would be apparent.Data memories304₁–304_Nprovide on-chip storage for data, such as intermediate-results data from processing network data elements, for the operation of processingelements302₁–302_N.

Intraswitch314 enables communication between the various components ofmultiprocessor core300. For example, processingelements302₁–302_Naccess data memories304₁–304_Nthroughintraswitch314.Intraswitch314 can be, for example, a switching fabric inmultiprocessor core300, or individual trace connections inmultiprocessor core300.Host control interface308 connectsmultiprocessor core300 to hostcontrol processor210.Multiprocessor core300 is connected to on-chipperipheral units310 and312 viaintraswitch314.

In operation,multiprocessor core300 receives network data elements from on-chipperipheral units310 and312.Processing elements302₁–302_Nreceive the network data elements and process them according to the programs stored as instructions inprogram memories306₁–306_N. The intermediate results and final results of the processing operations are stored indata memories304₁–304_N. After a network data element has been processed, it is sent to on-chipperipheral unit310 and312.

FIG. 4 illustrates a system block diagram of an exemplary processing element, according to an embodiment of the present invention.Processing element400 is an example of one of the processing elements shown inFIG. 3, and can be employed in a generic form of data processing or can be of the type that is employed indata communications system100.

Moreover,exemplary processing element400 is an instruction-level parallel processing element, in which two or more threads of parallel programs execute concurrently.Processing element400 can, therefore, maintain a high utilization under conditions where the processing element would otherwise idle waiting for long-latency operations to complete. Note thatprocessing element400 is provided for illustrative purposes only and that other processing element configurations are possible.

Processing element400 includes instruction fetchunit402,instruction buffers404A,404B,404C, and404D.Processing element400 also includes function decode andexecution switch406, dependency counters410,instruction issue control408, memory/peripheral interface unit4;2 412,primary function unit414,auxiliary function unit416, and registerfile418. Note that although dependency counters410 are shown as being part ofinstruction issue control408, other configurations are possible. For example, dependency counters410 can also be connected to, but not part of,instruction issue control408.

Instruction fetchunit402 is connected to each ofinstruction buffers404A–404D. Each of the connections between fetchunit402 andinstruction buffers404A–404D provides a path for instructions from a program thread. Instruction buffers404A–404D are, in turn, connected to function decode andexecution switch406. Instruction buffers404A–404D are also connected toinstruction issue control408.Instruction issue control408 is connected to function decode andexecution switch406. Function decode andexecution switch406 is connected to memoryperipheral interface unit412,primary function unit414, andauxiliary function unit416. Memoryperipheral interface unit412,primary function unit414, andauxiliary function unit416 are also referred to herein asexecution units412–416. Memory peripheral interface unit is connected to intraswitch314, and registerfile418.Primary function unit414 is connected to registerfile418.Auxiliary function unit416 is connected to registerfile418.

Register file418 includes readports420 and writeport422. Readports420 allowexecution units412–416 to read data from the various registers inregister file418. Writeport422 allowsexecution units412–416 to write data to registerfile418.

Exemplary processing element400 is shown as supporting four concurrent threads of instructions. Instruction fetchunit402 fetches instructions fromprogram memory306. The instructions are entered in the fourinstruction buffers404A–404D according to the program thread they belong to. Each ofinstruction buffers404A–404D is associated with one of four threads. For descriptive clarity, the convention of associating thread0 (T0) withinstruction buffer404A, thread1 (T1) withinstruction buffer404B, thread2 (T2) withinstruction buffer404C, and thread3 (T3) withinstruction buffer404D is adopted.

Function decode andexecution switch406 receives the instructions associated with the four threads frominstruction buffers404A–404D. Function decode andexecution switch406 provides the instructions toexecution units412–416.

FIG. 5 is a diagram illustrating concurrent processing of three threads of instructions. Instruction processing diagram500 illustrates the problem of instruction synchronization between multiple threads. The instructions of one thread can be dependent on the results of instructions in another thread. For example, the contents of a register that is set by a first instruction in one thread can be used by a second instruction in another thread. In such a case, if the first instruction is not executed before the second instruction, the register will not include data valid for the execution of the first second instruction. These types of problems are referred to as synchronization problems, and may result in a program execution error.

Instruction processing diagram500 shows three threads of instructions,thread502,thread504, andthread506.Threads502–506 can be of the type employed in a generic form of data processing or can be of the type that are employed indata communications system100. Note that three threads are shown for descriptive clarity only, and other configurations are possible. A processing element can process as few as two threads, and as many threads as is accommodated by a processing element architecture. For example,processing element400 accommodates four concurrent threads of instructions.

Each ofthreads502–506 is shown including two instructions.Thread502 includes instruction508 (i1) and instruction510 (i2).Thread504 includes instruction512 (i3) and instruction514 (i4).Thread506 includes instruction516 (i5) and instruction518 (i6). Note that instruction processing diagram500 shows two instructions per thread for descriptive clarity only, and other configurations are possible. For example, each ofthreads502–506 can include additional instructions (not shown) before the first instruction (e.g.,instruction508 in thread502), between the first and second instruction (e.g.,instructions508 and510 in thread502), and after the second instruction (e.g.,instruction510 in thread502).Threads502–506 can include as many instructions as are required to perform generic data processing or perform processing fordata communications system100.

Generally, a processing element processes the three threads by executing their respective instructions. Instruction processing diagram500 shows instruction execution proceeding from left to right, and the relative spacing of instructions indicates when an instruction is being executed. For example, instruction processing diagram500 showsinstruction508 is executed beforeinstruction510 ofthread502. Note also the chronological relationships between instructions of different threads. For example, the processing element executesinstruction508 ofthread502 beforeinstruction512 ofthread504, andinstruction512 beforeinstruction516 ofthread506.

Additionally, instruction processing diagram500 shows the dependency between the instructions ofthreads502–506. Dependency is when the execution of a second instruction is conditional on the execution of a first instruction. Consider, for example, a situation in which a first instruction in a first thread writes a value to a register file, such asregister file418, and a second instruction in a second thread subsequently reads the value from the register file and uses the value as an operand in a calculation. In this situation, the first instruction is referred to as the dependee instruction, and the second instruction is referred to as the dependent instruction. A dependent instruction is an instruction that must not be executed before the instruction on which it depends. A dependee instruction is an instruction on which a dependent instruction depends. As long as the dependee instruction is executed before the dependent instruction, the register file includes the correct value for the execution of the dependent instruction.

Dependsindicators520–526 are used to show dependencies between the instructions ofthreads502–506. Depends indicators are drawn from a dependent instruction to a dependee instruction (i.e., the arrow of the depends indicator points to the dependee instruction). Dependsindicator520 indicates that the execution ofinstruction512 depends on the execution ofinstruction508. Dependsindicator522 indicates that the execution of instruction of510 depends on the execution ofinstruction514. Dependsindicator524 indicates that the execution ofinstruction516 depends on the execution ofinstruction510. Dependsindicator526 indicates that the execution ofinstruction518 is dependent on the execution ofinstruction514.

As described above, if a first instruction depends on a second, earlier executed, instruction, processing may proceed normally. Instruction processing diagram500 showsinstruction512 andinstruction516 dependent on earlier executed instructions. Program errors may occur, however, if a first instruction depends on a later executed instruction. Instruction processing diagram500 shows the synchronization problem asinstruction510 depending on a later executed instruction. As such, it is important for a processing element to synchronize the execution order of dependent and dependee instructions between threads to avoid such program errors.

The present invention provides a system and method that maintains the order of instruction execution between threads. Generally, a processing element processes multiple threads of instructions. Instructions in the threads can include dependence indicators that indicate dependencies between instructions and threads. When the processing element encounters instructions that include dependence indicators identifying a dependent instruction or thread, it checks, decrements, or increments one or more dependency counters. If the dependency counter is not above a threshold, it indicates that a dependency has not been satisfied, and the processing element can suspend the execution of a thread until the dependency counter is incremented to above the threshold. This allows the processing element to maintain a form of synchronized execution of dependent instructions between threads.

In one embodiment, instructions can include the dependence indicators as bits, called “depends” bits and “tells” bits. A depends bit is an indicator in a dependent instruction that a particular other thread includes an instruction on which this one depends. A tells bit is an indicator in a dependee instruction that a particular other thread includes an instruction dependent on this one. The additional bits can be included with the instruction in a number of ways. For example, a compiler for instruction-level parallel processors can include the bits at compile time based on dependencies, or a programmer may specify the instruction execution order by including “depends” and “tells” bits when coding, etc.

An exemplary embodiment is described herein to provide context for discussion, and the present invention encompasses other embodiments, as are described further below. Consider an exemplary processing element processing four threads of instructions. Each of the instructions in the four threads can include depends bits and tells bits. In an exemplary embodiment each instruction in a thread can include three depends bits, each of which indicates that the instruction is dependent on one of the other three threads. Similarly, each instruction in a thread can include three tells bits, each of which indicates that one of the other three threads depends on the execution of the instruction.

In the exemplary embodiment, the processing element can include four groups of dependency counters, each of which is associated with one of the four threads. Each of the groups of dependency counters includes three individual dependency counters, each of which is associated with one of the other three threads. For instance, consider four exemplary threads,thread0,thread1,thread2, andthread3, each having an associated group of dependency counters. The exemplary group of dependency counters associated withthread0 includes three individual dependency counters, each of which is associated with one ofthread1,thread2, orthread3.

In operation, the exemplary processing element processes the instructions of the four threads. When the exemplary processing element encounters an instruction in a first thread that includes a tells bit identifying a second thread (i.e., one of the other three threads), the exemplary processing element increments the dependency counter associated with the first thread of the group of dependency counters associated with the second thread.

When the exemplary processing element processes an instruction in a first thread that includes a depends bit identifying a second thread, the processing element checks the dependency counter associated with the second thread of the group of dependency counters associated with the first thread to determine whether the instruction can be executed. If the value of the exemplary dependency counter is above a threshold (e.g., non-zero), the processing element executes the instruction. If, on the other hand, the value of the exemplary dependency counter is below a threshold, processing of the first thread is inhibited. The processing element increments the dependency counter when instructions including tells bits in the second thread are executed, and processing the first thread is resumed once the dependency counter is above the threshold. Note that an instruction can include multiple dependency indicators, such as one or more tells bits in combination with one or more depends bits. When an instruction includes more than one depends bit, the associated dependency counters must be above the threshold before the instruction is executed.

The threshold is a dependency counter value chosen to ensure that dependent instructions are not executed before the instructions in other threads on which they depend. The threshold value can be set to ensure correct instruction level synchronization. For example, the threshold can be chosen to be zero, so that a dependency counter must be incremented before a dependent instruction can be executed, as is described in further detail, below. Network data element processing is often repetitive and predictable. As such, a programmer, or compiler, can determine that value at which the threshold can be set. Note that although one embodiment of the present invention is explained in terms of a “threshold,” “above a threshold,” and “not above a threshold,” other configurations that record dependency between instructions and threads are possible. For example, in an alternate embodiment, the processing element can suspend processing a thread if a dependency counter falls below a threshold.

According to an embodiment of the present invention, depends bits, tells bits, and dependency counters are used to record the satisfaction of dependencies between instructions in a first thread and the processing of a second thread. This is in contrast to instruction processing diagram500 ofFIG. 5 that shows dependencies between individual instructions. It is sufficient to record dependency at this level because the present invention provides a system and method that ensures that dependent instructions are executed after the instructions on which they depend.

Consider, for example, the application of “depends” bits and “tells” bits to instruction processing diagram500 ofFIG. 5. In this example,instruction512 would include a dependsbit identifying instruction512 as dependent upon instructions inthread502. In one embodiment, the depends bit identifies the thread that includes the instruction on whichinstruction512 is dependent, which is, in this case,thread502. In another embodiment, the depends bits can identify the type or particular one of the instructions inthread502. For example, the instruction can include more bits (i.e., more information) that identify instruction characteristics (such as type, priority, etc.). For descriptive clarity, however, depends bits and tells bits are described herein as identifying threads, and not instructions. As such,instruction508 would include a tells bit that identifiesthread504 as including an instruction or instructions that are dependent upon the execution ofinstruction508.

Similarly,instruction510 would include a tellsbit identifying thread506 as including instructions dependent upon the execution ofinstruction510.Instruction510 would also include a dependsbit identifying instruction510 as dependent on the execution of instructions inthread504.Instruction514 would include a tellsbit identifying thread502 as including instructions that are dependent on the execution ofinstruction514.Instruction514 also would include a tellsbit identifying thread506 as including instructions dependent on the execution ofinstruction514.Instruction516 would include abit identifying instruction516 as dependent on instructions inthread502.Instruction518 would include a dependsbit identifying instruction518 as dependent on the execution of instructions inthread504.

FIG. 8 illustrates an exemplary instruction, according to an embodiment of the present invention.Instruction800 includesopcode802, source0804 0 804, source1806 1 806,result808, dependsbit810, dependsbit812, dependsbit814, tellsbit816, tellsbit818, and tellsbit820.Opcode802 is the operator forinstruction800. Source0804 0 804 specifies a first operand operated upon byopcode802. Source1806 1 806 specifies a second operand operated upon byopcode802.Result808 identifies a register to which the results of opcode1302 are stored.

Dependsbits810–814 indicate thatinstruction800 depends upon the execution of instructions in other threads.Instruction800 is configured for a processing element that supports the operation of four threads. Note that althoughinstruction800 includes three depends bits which identify three other threads, and three tells bits, which also identify three other threads, other configurations are possible. By adding additional bits or changing how the bits are used,instruction800 can be configured for a processing element that supports more than four threads. Consider, for example, binary coding of dependsbits810–814, and tellsbits816–818 816-820. In such an example, dependsbits810–814 can represent up to eight other threads, extendinginstruction800 to a processing element supporting nine threads. Similarly, additional depends and tells bits can be added as is necessary for a given processing element architecture.

Consider, for example, the case in whichinstruction800 is executing inthread1. Ifinstruction800 is executing inthread1, the other three threads on which the execution ofinstruction800 may depend arethread0,thread2, andthread3. In this case, dependsbit810 can identifyinstruction800 as dependent onthread0, dependsbit812 can identifyinstruction800 as dependent onthread2, and depends bid814 can identifyinstruction800 as dependent onthread3. Likewise, tellsbit816 can identifythread0 as dependent oninstruction800. Tellsbit818 can identifythread2 as dependent oninstruction800. Tellsbit820 can identifythread3 as dependent oninstruction800.

As suggested by the relationships described above, dependency counter groups are a set of dependency counters associated with each thread. Each ofthreads502–506 of instruction processing diagram500, for example, would have, or be associated with, a dependency counter group. Each dependency counter group could include a number of individual dependency counters, each of which is associated with one of the other threads executing on the processing element. For example, the dependency counter group associated withthread502 of instruction processing diagram500 would include two dependency counters, one related to, or associated with,thread504, and one related to, or associated with,thread506.

FIG. 7 illustrates exemplary dependency counter groups, according to an embodiment of the present invention.FIG. 7 shows four dependency counter groups, each of which is associated with one of four threads. Dependency counter group702 (T0) is associated withthread0, dependency counter group704 (T1) is associated withthread1, dependency counter group706 (T2) is associated withthread2, and dependency counter group708 (T3) is associated withthread3. Each ofdependency counter groups702–708 includes three dependency counters, each of which is associated with one of the other three threads.Dependency counter group702 includes dependency counter T0₁, dependency counter T0₂, and dependency counter T0₃. Dependency counter T0₁is that dependency counter ofthread0 that is related to, or associated with,thread1. Similarly, dependency counter T0₂and dependency counter T0₃arethread0 dependency counters associated with, or related to,threads2 and3, respectively. In the same manner,dependency counter group704 includes dependency counter T1₀, dependency counter T1₂, and dependency counter T1₃. Dependency counter T1₀is associated withthread0, dependency counter T1₂is associated withthread2, and dependency counter T1₃is associated withthread3. Also,dependency counter group706 includes dependency counter T2₀, dependency counter T2₁, and dependency counter T2₃. Dependency counter T2₀is associated withthread0, dependency counter T2₁is associated withthread1, and dependency counter T1₃is associated withthread3.Dependency counter group708 includes dependency counter T3₀, dependency counter T3₁, and dependency counter T3₂. Dependency counter T3₀is associated withthread0, dependency counter T3₁is associated withthread1, and dependency counter T3₂is associated withthread2.

Note that although four dependency counter groups are shown (as are implemented in one embodiment to support four threads), and the dependency counter groups include three dependency counters each, other configurations are possible. For example, greater or fewer than four dependency counter groups can be used according to the number of threads a processing element can execute concurrently. Additionally,dependency counter groups702–708 can include more or fewer dependency counters, depending on the processing element architecture.

Moreover, although the invention and illustrative examples are described in terms of dependency counter groups, and dependency counters, other configurations are possible. Consider, for example, bi-state, or tri-state elements substituted for dependency counters702–708. A bi-state element associated with a first thread can be set when a corresponding dependee instruction in a second thread is executed, and reset when the dependent instruction is executed. In this example, a processing element suspends processing the first thread when it encounters an instruction including a depends bit if the bi-state element is not set. Similarly, tri-state elements, and other state retaining elements can be set and reset by the processing element. In this embodiment, however, care should be taken to avoid overflowing the state elements. For example, a bi-state element may be incremented, or changed, only once in response to an instruction that includes a tells bit.

Similarly, the implementation of the present invention should account for the size of the dependency counters to avoid overflow. Consider, for example, the case in which multiple instructions including tells bits identifying one thread are executed. In such a case, it is possible to overflow the dependency counter. Dependency counters, therefore, should be specified large enough to ensure that overflow will never occur, or limits should be set on the number of times a dependency counter can be incremented. For example, a first thread that includes many instructions that include tells bits identifying a second thread can be suspended once the dependency counter associated with the second thread has reached a limit. The limit can ensure that the dependency counter does not overflow, and can also ensure that a dependee thread does not get too far ahead of a dependent thread.

In operation, a tells bit affects one or more dependency counters of the threads other than the one on which the tells bit appears. By contrast, a depends bit affects one or more dependency counters of the thread on which the depends bit appears. Thus, when the processing element detects a first instruction in a first thread as including a tells bit that identifies a second thread, the processing element increments one of the dependency counters in the dependency counter group of the second thread. In particular, it increments that dependency counter of the second thread that is associated with the first thread. Consider, for example, the case in whichthread1 is executing a stream of instructions. One of the instructions inthread1 includes a tells bit that identifiesthread0. In response to the tells bit, the processing element increments the particular dependency counter independency counter group702 associated withthread1. In the example ofdependency counter group702, dependency counter T0₁, is associated withthread1. The processing element, therefore, increments T0₁ofdependency counter group704 when thethread1 instruction tells bit is detected. Similarly, when the processing element detects an instruction in a thread that includes a depends bit, the dependency counters are checked, and the processing element either suspends the dependent thread or executes the instruction and decrements the associated dependency counter.

For example,thread1 can include an instruction that includes a depends bit that identifies the instruction as depending on the execution ofthread0. In this case, when the processing element detects the depends bit, the dependency counter associated withthread0 of the dependency counter group associated with thethread1 is checked. In this case, dependency counter T1₀ofdependency counter group704 is associated with thread T0. Depending on the value of dependency counter T1₀, the processing element either suspendsprocessing thread1 or both decrements T1₀and continues processing thethread1, thereby executing the instruction. Once suspended, the processing element resumesprocessing thread1 when dependency counter T1₀is incremented by the processing element (i.e., when an instruction inthread0 with a tells bit is executed).

FIG. 6 illustrates concurrent processing of two threads of instructions, according to an embodiment of the present invention. Thread synchronization diagram600 showsthread602 andthread604 as a series of processing steps. A processing step is an action or actions performed by a processing element in the implementation of one embodiment of the present invention. A processing step can be, for example, the execution of an instruction, incrementing a dependency counter, decrementing a dependency counter, etc.Thread602 includesprocessing step606, processingstep608, processingstep610, processingstep612, processingstep614, andprocessing step616.Thread604 includesprocessing step618, processingstep620, andprocessing step622. Although synchronization diagram600 only shows two threads of instructions, other configurations are possible. For example, the system and method of the present invention can be extended to three, four, and more than four threads, as described above.

For the purpose of descriptive clarity, the instructions of thread synchronization diagram600 are referred to as instruction508 (i1), instruction510 (i2), instruction512 (i3), and instruction514 (i4). Note, however, that instruction processing diagram500 showsinstruction512 as dependent oninstruction508, and showsinstruction510 as dependent oninstruction514. Thread synchronization diagram600, on the other hand, shows the instructions ofthread602 dependent on the execution of instructions inthread604 generally, and the instructions ofthread604 dependent on the execution of instructions inthread602 generally. The dependencies betweeninstructions508–514 shown in instruction processing diagram500 are implemented in the operation of one embodiment of the present invention through the general dependency of instructions within one thread on the processing of another thread (i.e., rather than particular instructions). This concept is illustrated in further detail below.

Additionally, thread synchronization diagram600 shows tellsbits624 and630 and dependsbit626 and628 as arrows pointing from processing steps to the threads that the bits identify. The arrows are shown to indicate that an instruction being processed in a processing step includes a tells bit or depends bit, and identifies the thread to which the bit points. Either the thread pointed to depends on the instruction (i.e., tells bit), or the instruction depends on the thread (i.e., depends bit). For example, tellsbit624 identifiesthread604 as dependent oninstruction508 ofprocessing step606. Similarly, dependsbit626 identifiesinstruction512 ofprocessing step618 as dependent onthread602.

Processing ofthread602 andthread604 begins when the processing element executesinstruction508, in processingstep606.Instruction508 includes tellsbit624 that identifiesthread604 as dependent oninstruction508. The processing element detects tellsbit624 and increments a dependency counter in adependency counter group704 associated with thread T1,604.

As described above, a dependency counter group is associated with a thread, and the dependency counter group includes dependency counters, each of which is associated with one of the other threads executing on the processing element. Thread synchronization diagram600 is described in terms of dependency counter group702 (associated with thread602) and dependency counter group704 (associated with thread604). Dependency counter T₁₀ T1₀ofdependency counter group704 is associated withthread602, and dependency counter T0, is associated withthread602.

After processingstep606, the processing element receivesinstruction512, in processingstep618.Instruction512 includes dependsbit626 identifyinginstruction512 as dependent on the execution of instructions inthread602. The processing element determines if dependency counter T1₀is above a predefined threshold. For the purposes of explanation, dependency counter T1₀is assumed to have been above, or at the threshold, so that it is above the threshold after being incremented. Since the processing element has incremented dependency counter T1₀, when the dependency counter is checked in response toinstruction512, the processing element determines that dependency counter T1₀is above the threshold.

Since dependency counter T1₀is above the threshold, the processing element continuesprocessing instruction512, at processingstep620. Inprocessing step620, the processing element executesinstruction512 and decrements dependency counter T1₀.

Meanwhile, the processing element processesthread602 inprocessing step608. Inprocessing step608, the processing element receivesinstruction510 from program memory.Instruction510 includes dependsbit628, which identifiesinstruction510 as dependent on the execution of instructions inthread604. The processing element checks the dependency counter group ofthread602, particularly the dependency counter related tothread604, in response to detecting dependsbit628. This corresponds to dependency counter T0₁. The value can be, for example, zero, or some other number representing a predetermined threshold. For exemplary purposes, however, dependency counter T0₁is defined as having a value of the predetermined threshold. In any case, the value of dependency counter T0₁indicates that instructions inthread604 upon whichinstruction510 depends, have not yet been executed. In response to detecting that dependency counter T0₁is not above a threshold, the processing element suspends execution ofthread602 inprocessing step610.

Meanwhile, the processing element continuesprocessing thread604. The processing element receivesinstruction514 inprocessing step622.Instruction514 includes tellsbit630 that identifiesthread602 as including instructions dependent oninstruction514. The processing element increments that dependency counter of thethread602 dependency counter group that is related to thread604 (namely, dependency counter T0₁) in response to detecting tellsbit630, and executesinstruction514, in processingstep622. Note that the order of executing the instruction and incrementing or decrementing dependency counters is chosen for illustrative purposes only, and the same outcome can be achieved with reversed order.

After processingstep622, the processing element detects that dependency counter T0₁has been incremented to above the threshold, in processingstep612. As such, the processing element resumesprocessing thread602 atinstruction510 inprocessing step614. After resumingprocessing thread602, the processing element executesinstruction510, decrements dependency counter T0₁, and continues processing the instructions ofthread602, instep616. Note that in the example ofFIG. 6, dependency counter T0₁is now equal to the threshold value, and any additional instructions inthread602 that include dependsbits identifying thread604 will cause the processing element to suspend execution of the thread (absent prior instructions inthread604 with tells bits identifying thread602).

The operation of thread synchronization diagram600 is now described with reference to the elements ofexemplary processing element400. The execution ofthread602 begins in processingstep606. For descriptive clarity,thread602 is associated withinstruction buffer404A, andthread604 is associated withinstruction buffer404B. In general, instruction fetchunit402 fetches program instructions fromprogram memory306. Instruction fetchunit402 distributes the instructions associated with the four threads to one ofinstruction buffers404A,404B,404C, or404D. In one embodiment, each ofinstruction buffers404A–404D is associated with a particular thread.

Instruction issue control408 detects the presence of depends bits such as dependsbits810–814 or the presence of tells bits, such as tellsbits816–820 included in instructions ininstruction buffers404A–404D. Based on presence or absence of depends bits and tells bits in the instruction,instruction issue control408 controls function decode andexecution switch406. Based on signals frominstruction issue control408, function decode andexecution switch406 issues instructions frominstruction buffers404A–404D to one ofexecution units412–416 (i.e., memoryperipheral interface unit412,primary function unit414, or auxiliary function unit416).

Inprocessing step606,instruction508 is received ininstruction buffer404A.Instruction issue control408 detects the presence of tellsbit624 ininstruction508. In response to detecting the presence of tellsbit624, instruction issue control increments one of the dependency counters in dependency counters410. As described above,instruction issue control408 increments dependency counter T1₀.Instruction issue control408 then causes function decode andexecution switch406 to provideinstruction508 to one ofexecution units412–416 for execution. Meanwhile,processing element400 is also processingthread604.Instruction buffer404B receivesinstruction512, in processingstep618.Instruction issue control408 detects the existence of dependsbit626 ininstruction512. Dependsbit626 identifiesinstruction512 as dependent on instructions inthread602. In response to detecting dependsbit626,instruction issue control408 checks dependency counter T1₀in processingstep618. Since dependency counter T1₀is above the threshold (as described above),instruction issue control408 enables function decode andexecution switch406 to provideinstruction512 to one ofexecution units412–416 for execution. Additionally, instruction issue control decrements dependency counter T1₀in dependency counters410.

Meanwhile,processing element400 receivesinstruction510 inprocessing step608.Instruction issue control408 detects the existence of dependsbit628 ininstruction buffer404A. Dependsbit628 identifiesinstruction510 as dependent on instructions inthread604. In response to detecting dependsbit628,instruction issue control408 checks dependency counter T0₁in dependency counters410. In this particular example, dependency counter T0₁is equal to the threshold necessary to continue processinginstruction510. Since dependency counter T0₁is not above the threshold,instruction issue control408 suspends execution ofthread602 by holdinginstruction510 in function decode andexecution switch406.

Processing element400 continuesprocessing thread604, and receivesinstruction514 inprocessing step622.Instruction514 includes tellsbit630 identifyingthread602 as dependent on the execution ofinstruction514.Instruction issue control408 increments dependency counter T0₁in response to detecting tellsbit630, in processingstep622.Instruction issue control408 causes function decode andexecution switch406 to sendinstruction514 to one ofexecution units412–416 for execution. After dependency counter T0₁has been incremented in processingstep622,instruction issue control408 detects that dependency counter T0₁has been incremented.Instruction issue control408 checks dependency counter T0₁to determine if it is above the threshold. In the example of thread synchronization diagram600,instruction issue control408 determines that dependency counter T0₁is above the threshold, in processingstep612. In response to detecting dependency counter T0₁above the threshold,instruction issue control408 resumesprocessing thread602 by issuinginstruction510 to one ofexecution units412–416, in processingstep614.Instruction510 is executed, andinstruction issue control408 decrements dependency counter T0₁in processingstep616.

FIG. 9 illustrates a process for executing instructions, according to an embodiment of the present invention. Aftermethod900 starts instep902, a processing element receives an instruction in a first thread, instep904. Instep906, the processing element determines if the execution of the instruction in the first thread is dependent on the execution of instructions in a second thread.

If the processing element determines that the execution of the instruction in the first thread is not dependent on the execution of instructions in a second thread,method900 ends instep916.

If, on the other hand, the processing element determines that the execution of the instruction in the first thread is dependent on the execution of instructions in a second thread, the process ofmethod900 continues instep908. Instep908, the processing element examines a dependency counter group that includes a dependency counter associated with the second thread.

Instep910, the processing element determines whether the dependency counter includes a value above a threshold. If the dependency counter includes a value above a threshold,method900 continues instep914. Instep914, the processing element executes the first thread instruction and decrements the dependency counter.

If, on the other hand, the processing element determines that the dependency counter does not include a value above a threshold,method900 continues instep912. Instep912, the processing element suspends execution of the first thread until the dependency counter is incremented to above a threshold. Once the dependency counter is incremented to above a threshold, processing the first thread resumes,method900 continues instep914. Instep914, the processing element executes the first thread instruction.

FIG. 10 illustrates an exemplary process for executing instructions, according to an embodiment of the present invention. Aftermethod1000 starts instep1002, a processing element receives a first thread instruction, instep1004. After the first thread instruction has been received, the processing element determines whether a second thread is dependent on the first thread instruction, instep1006.

If a second thread is dependent on the execution of the first thread instruction,method1000 continues instep1008. Instep1008, the processing element increments a dependency counter included in a dependency counter group associated with the second thread. After the dependency counter is incremented, the processing element executes the first thread instruction, instep1010.

If, on the other hand, the processing element determines that a second thread is not dependent on the first thread instruction, the process ofmethod1000 continues instep1010. Instep1010, the processing element executes the first thread instruction.

Afterstep1010,method1000 ends instep1012.

The present invention provides a system and method for high speed processing of network data elements. A network line module, such asnetwork line module104₁, receives network data elements from a network or switch fabric via a network line module ingress port. The network line module provides the network data elements to a multiprocessor core. The received network data elements are distributed to multiple processing elements within the multiprocessor core for processing according to a program.

The processing elements process the network data elements according to program instructions stored in program memory. Each of the processing elements uses instruction-level parallelism to process multiple threads of instructions concurrently. Instruction execution is synchronized by recording dependencies between instructions and threads. Instructions in the threads can include dependence indicators identifying dependencies between instructions and threads. When a processing element encounters an instruction that includes dependence indicators identifying a dependent instruction or thread, the processing element checks, decrements, or increments one or more dependency counters that records dependency between instructions and threads. If an instruction in a first thread is dependent upon the execution of instructions in a second thread, a dependency counter is checked. If the dependency counter is not above a predetermined threshold, the processing element suspends the execution of the first thread until the dependency counter is incremented by the second thread to above the threshold.

After processing, the multiprocessor core provides processed network data elements to the network line module. The network line module provides the processed network data element to an egress port connected to a network or switch fabric.

It will be apparent to one skilled in the art that various changes and modifications can be made therein without departing from the spirit and scope thereof. Thus, it is intended that the present invention cover the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.

Claims (26)

What is claimed is:

1. An apparatus for instruction-level parallelism in a processing element, comprising: an instruction control unit; The apparatus of claim 7, wherein the instruction buffer comprises:

a first instruction buffer coupled to said instruction control unit, the first instruction buffer configured to hold a the first instructionincluding a dependency indicator and being associated with a first thread;, and

a second instruction buffer coupled to said instruction control unit, the second instruction buffer configured to hold a the second instructionincluding a dependency indicator and being associated with a second thread; a dependency counter coupled to said instruction control unit;; and wherein

anthe execution switch is coupled to said instruction control unit, said first instruction buffer, and said second instruction buffer; and

an execution unit coupled to said execution switch;

said instruction control unit configured to detect the dependency indicators and change the value of said dependency counter in response to detecting the dependency indicators and configured to disallow execution of the first instruction if said dependency counter includes a value less than a threshold value.

2. The apparatus ofclaim 1, wherein said dependency counter includes a first counter associated with the first instruction buffer and a second counter associated with the second instruction buffer.

3. The apparatus ofclaim 1, wherein said instruction control unit identifies instruction dependency bits in said first instruction buffer, the instruction dependency bits being associated with instructions.

4. The apparatus ofclaim 1, said instruction control unit generating control signals based on the dependency bits and values included in said dependency counter.

5. The apparatus ofclaim 4, said execution switch providing instructions from said first instruction buffer to said execution unit based on control signals from said instruction control unit.

6. The apparatus ofclaim 1, said execution switch providing instructions from said first instruction buffer to said execution unit based on control signals from said instruction control unit.

7. An apparatus for processing instructions in multiple threads in an execution unit, comprising:

an instruction buffer holding configured to hold a first instruction and a second instruction, the first instruction being associated with a first thread, and the second instruction being associated with a second thread, the first instruction and the second instruction including one or more instruction dependency bits;

a dependency counter,

an instruction control unit coupled to said instruction buffer and said dependency counter, said instruction control unit detecting configured to detect the instruction dependency bits and incrementing and decrementing to increment and decrement said dependency counter in response to detecting the instruction dependence bits, said instruction control unit configured to disallow execution of the first instruction if in response to said dependency counter includes including a value less than a threshold value; and

an execution switch coupled to said instruction control unit and said instruction buffer, said execution switch sending configured to send instructions to the execution unit.

8. The apparatus ofclaim 7, wherein said dependency counter includes a first counter associated with the first thread and a second counter associated with the second thread.

9. The apparatus ofclaim 7, wherein said instruction buffer includes the instruction dependency bits, the instruction dependency bits being associated with instructions.

10. The apparatus ofclaim 7, wherein said instruction control detects dependency between the first instruction and the second thread based on dependency bits in said instruction buffer and a value of said dependency counter.

11. A method for processing instructions in multiple threads, comprising:

receiving a first instruction associated with a first thread;

determining whether execution of the first instruction depends on execution of a second instruction, the second instruction being associated with a second thread;

examining a counter logic element associated with the first thread if in response to said determining indicates indicating that the first instruction depends on the execution of the second instruction, wherein the logic element comprises a single bi-state element or a tri-state element;

decrementing the counter ifmodifying the logic element in response to said examining indicatesindicating that the second instruction has already been executed; and

executing the first instruction; and

suspending the processing of the first thread until said examining indicates that the second instruction has already been executed and then resuming processing.

12. The method ofclaim 11, further comprising suspending the processing of the first thread until said examining indicates that the second instruction has already been executed.

13. A method for processing instructions in multiple threads, comprising:

receiving a first instruction associated with a first thread;

determining whether execution of a second instruction depends on the execution of the first instruction, the second instruction being associated with a second thread;

incrementing a counter associated with the second thread if in response to said determining indicates indicating that execution of a second instruction depends on the execution of the first instruction; and

executing the first instruction; and

suspending the processing of the second thread in response to the counter associated with the second thread not exceeding a threshold and resuming the processing of the second thread in response to the counter associated with the second thread exceeding the threshold;

wherein the first instruction and the second instruction include one or more instruction dependency bits.

14. The method ofclaim 13, further comprising suspending the processing of the second thread if the counter associated with the second thread does not exceed a threshold.

15. A method for processing instructions in multiple threads, comprising:

receiving a first instruction associated with a first thread, the first instruction including one or more instruction dependency bits;

determining whether a second thread depends on said first instruction;

incrementing a counter associated with the second thread if in response to the second thread depends depending on said first instruction;

loading a second instruction associated with a second thread; and

processing the second instruction in a manner related to the value of the counter associated with the second thread; and

suspending, the processing of the second thread in response to the counter not exceeding a threshold and resuming the processing of the second thread in response to the counter exceeding said threshold.

16. The method ofclaim 15, further comprising suspending the processing the second thread if the counter indicates that a dependent thread has not been executed.

17. The method ofclaim 15, further comprising executing the second instruction if the counter indicates that said first instruction has been executed.

18. An apparatus for processing instructions in multiple threads, comprising:

an instruction buffer configured to hold a first instruction and a second instruction, the first instruction including a dependency indicator and being associated with a first thread, and the second instruction including a dependency indicator and being associated with a second thread;

an instruction control unit coupled to said instruction buffer;

a dependency counter coupled to said instruction control unit, said dependency counter associated with the first thread;

said instruction control unit configured to detect the dependency indicators and change the value of increment and decrement said dependency counter in response to detecting the dependency indicators; and

said instruction control unit configured to disallow execution of the first instruction if in response to said dependency counter includes including a value less than a threshold value.

19. The apparatus ofclaim 18, wherein said instruction control unit is configured to determine that the dependency indicator included in the first instruction indicates that the second thread includes an instruction on which the first instruction depends.

20. The apparatus ofclaim 18, wherein the dependency indicator included in the first instruction is a depends bit.

21. The apparatus ofclaim 18, wherein said instruction control unit is configured to determine that the dependency indicator included in the second instruction indicates that the first thread includes an instruction that is dependent on the second instruction.

22. The apparatus ofclaim 18, wherein the dependency indicator included in the second instruction is a tells bit.

23. The apparatus of claim18 25, wherein said instruction control unit is configured to increment said dependency counter in response to detecting the dependency indicator included in the second instruction.

24. The apparatus of claim18 25, wherein said instruction control unit is configured to decrement said dependency counter in response to detecting the dependency indicator included in the first instruction.

25. The apparatus according to claim 18, wherein said dependency counter is coupled to said instruction control unit and associated with the first thread.

26. A method for processing instructions in multiple threads, comprising:

receiving a first instruction associated with a first thread;

determining that execution of the first instruction depends on execution of a second instruction, the second instruction being associated with a second thread;

examining a dependency counter associated with the first thread to determine whether the second instruction has already been executed;

incrementing the dependency counter in response to said determining indicating that execution of the first instruction depends on execution of the second instruction; and

suspending the processing of the first thread when examining indicates that the dependency counter does not exceed a threshold and resuming the processing after the dependency counter exceeds said threshold,

wherein the first instruction and the second instruction include one or more instruction dependency bits.

Images