Parallel multi-threaded processing

#This invention relates to a protocol for providing parallel, multi-threaded processors with high bandwidth access to shared resources.

#Parallel processing is an efficient form of computer information processing of concurrent events. Certain problems may be solved by applying parallel computer processing, which demands concurrent execution of many programs to do more than one thing at the same time. Unlike a serial paradigm where all tasks are performed sequentially at a single station, or a pipelined machine where tasks are performed at specialized stations, parallel processing requires that a plurality of stations have the capability to perform all tasks. In general, all or a plurality of the stations work simultaneously and independently on the same or common elements of a problem.

#Types of computer processing include single instruction stream, single data stream, which is the conventional serial von Neumann computer that includes a single stream of instructions. A second processing type is the single instruction stream, multiple data streams process (SIMD). This processing scheme may include multiple arithmetic-logic processors and a single control processor. Each of the arithmetic-logic processors performs operations on the data in lock step and are synchronized by the control processor. A third type is multiple instruction streams, single data stream (MISD) processing which involves processing the same data stream flows through a linear array of processors executing different instruction streams. A fourth processing type is multiple instruction streams, multiple data streams (MIMD) processing which uses multiple processors, each executing its own instruction stream to process a data stream fed to each of the processors. MIMD processors may have several instruction processing units and therefore several data streams.

#FIG. 1 is a block diagram of a communication system employing a hardware-based multithreaded processor.

#FIG. 2 is a simplified block diagram of a global arbitration system for a multithreaded process according to the invention.

#FIGS. 3A and 3B illustrate a flow chart of an implementation of a global command arbitration process according to the invention.

#FIG. 1 illustrates a communication system 10 that includes a parallel, hardware-based multithreaded processor 12. The system 10 is especially useful for tasks that can be broken into parallel subtasks or functions, and the hardware-based multithreaded processor 12 is particularly useful for tasks that are bandwidth oriented rather than latency oriented.

#The hardware-based multithreaded processor 12 may be an integrated circuit, and may be coupled to a bus such as a PCI bus 14, a memory system 16 and a second bus 18. In the illustrated implementation, the hardware-based multithreaded processor 12 has multiple microengines 22a to 22f that each includes multiple hardware-controlled threads that can be simultaneously active and that may independently work on a task. The multithreaded processor 12 also includes a central or core controller 20 that assists in loading microcode control for other resources and performs other general purpose computer-type functions such as handling protocols, handling exceptions, and providing extra support for packet processing, which may occur if the microengines pass the packets off for more detailed processing. In one embodiment, the core controller 20 is a Strong Arm® (Arm is a trademark of ARM Limited, United Kingdom) based architecture embedded general-purpose microprocessor, which includes an operating system. The operating system enables the core processor 20 to call functions to operate on the microengines 22a-22f. The core processor 20 can use any supported operating system but preferably utilizes a real time operating system. Suitable operating systems for a core processor implemented as a Strong Arm architecture microprocessor may include Microsoft NT real-time, VXWorks and μCUS, which is a freeware operating system available over the Internet.

#The plurality of functional microengines 22a-22f each maintain a plurality of program counters in hardware, and maintain states associated with the program counters. Each of the six microengines 22a-22f is capable of processing four independent hardware threads. Such processing allows one thread to start executing just after another thread issues a memory reference and then waits until that reference completes before doing more work. This behavior is critical to maintaining efficient hardware execution of the microegines because memory latency may be significant. Stated differently, if only a single thread execution was supported, the microengines would sit idle for a significant number of cycles waiting for references to return and thereby reduce overall computational throughput. Multi-threaded execution allows the microengines to mask memory latency by performing useful independent work across several threads. Effectively, a corresponding plurality of sets of threads can be simultaneously active on each of the microengines 22a-22f while only one is actually operating at any one time.