Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-04-03
2001-12-11
Banankhah, Majid (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06330584
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
Not applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
The present invention relates to data processing, and more particularly to pipelined instruction execution, multi-tasking, and resource access techniques.
Pipelining and multi-tasking increase processor bandwidth. It is desirable to reduce the time and complexity associated with these techniques.
In particular, when instruction execution is pipelined, the processor may start executing an instruction before it is known whether the instruction should be executed. For example, suppose the processor starts executing an instruction I1, and then starts executing an instruction I2 before the I1 execution is finished. If the I1 execution cannot be completed, the instruction I2 should not be executed and has to be purged from the pipeline. In fact, at any given time, the processor may be executing more than one instruction that have to be purged from the pipeline. It is desirable to reduce the circuit complexity associated with pipeline purging.
It is also desirable to reduce the overhead associated with switching between different tasks in multi-tasking environments. To switch tasks, the operating system executed by the processor has to determine which task is to be executed next. The operating system also has to save register values used by one task and load the registers with values used by another task. These functions can involve a fair number of operating system instructions. It is desirable to reduce the number of instructions associated with these operations.
It is also desirable to improve access to resources which maybe unavailable. An example of such a resource is a FIFO which may be empty when a processor is trying to read it, or which may be full when the processor is trying to write the FIFO. Before accessing the FIFO, the processor polls a flag indicating whether the FIFO is available. It is desirable to improve the speed of accessing a resource which may be unavailable.
It is also desirable to provide simple synchronization methods to synchronize use of computer resources by multiple tasks to avoid errors that could be caused by a task accessing a resource when the resource is set for access by a different task.
SUMMARY
The present invention provides in some embodiments efficient pipeline processors, multi-tasking processors, and resource access techniques.
In some instruction execution pipeline embodiments, the pipeline purge overhead is reduced or eliminated by limiting the number of instructions that the processor can execute in a row for any given task. Thus, in some embodiments, consecutive instructions are executed by different tasks. Therefore, if an instruction cannot be executed, the next instruction still has to be executed because the next instruction belongs to a different task. Therefore, the next instruction is not purged from the pipeline.
In some embodiments, between any two instructions of the same task the processor executes a sufficient number of instructions from different tasks to eliminate any need for pipeline purging.
To reduce the overhead associated with task switching, some embodiments include separate registers for each task so that the register values do not have to be saved or restored in task switching operations. In particular, in some embodiments, each task has a separate program counter (PC) register and separate flags. In some embodiments, the task switching is performed by hardware in one clock cycle.
In some embodiments, a processor can access a resource without first checking whether the resource is available. If the resource is unavailable when the processor executes an instruction accessing the resource, the processor suspends the instruction, and the processor circuitry which was to execute the instruction becomes available to execute a different instruction, for example, an instruction of a different task.
Thus, in some embodiments, the processor keeps track of the state of all the resources (for example, FIFOs). (Unless specifically stated otherwise, the word “resource” as used herein means something that may or may not be available at any given time.) Signals are generated indicating the state of each resource, and in particular indicating which resource is available to which task. If a task attempts to access an unavailable resource, the task is suspended, and the processor can execute other tasks in the time slot that could otherwise be used by the suspended task. When the resource becomes available, the suspended task is resumed, and the instruction accessing the resource is re-executed.
To avoid synchronization errors when multiple tasks share one or more resources, in some embodiments after a task has finished accessing any one of the resources, the task does not get access to the same resource until after every other task sharing the resource has finished accessing the resource. Thus, in some network embodiments, different tasks share FIFO resources to process frames of data. Each task processes a separate frame of data. To process the frame, the task reads the frame address from a “request” FIFO. Then the task writes a command FIFO with commands to a channel processor to process the frame. A second task performs similar operations for a different frame. The first task again performs the same operations for a still different frame. If commands written for one frame get erroneously applied to another frame, the frames could be misprocessed.
To eliminate this possibility and to allow accurate matching between the frame addresses in the request FIFO and the commands in the command FIFO, the following technique is used. First one task (say, T1) is allowed to access both the request FIFO and the command FIFO, but no other task is allowed to access these resources. Once the task T1 has finished accessing any resource, the resource is allowed to be accessed by another task, and further the task T1 will not be allowed to access the resource again until every other task sharing the resource has finished accessing the resource. Therefore, the order of frame addresses in the request FIFO corresponds to the order of commands in the command FIFO, allowing the channel to accurately match the frame addresses with the commands. No special tag is needed to establish this match, and the match is established using FIFOs, which are simple data structures.
In some embodiments, a processor executes several tasks processing network data flows. The processor uses pipeline and task-switching techniques described above to provide high bandwidth.
Other embodiments and variations are described below. The invention is defined by the appended claims.
REFERENCES:
patent: 2686844 (1954-08-01), Brewer
patent: 4885744 (1989-12-01), Lespagnol et al.
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5062106 (1991-10-01), Yamazaki
patent: 5233606 (1993-08-01), Pashan et al.
patent: 5261062 (1993-11-01), Sato
patent: 5311509 (1994-05-01), Heddes et al.
patent: 5337308 (1994-08-01), Fan
patent: 5357617 (1994-10-01), Davis et al.
patent: 5457687 (1995-10-01), Newman
patent: 5517495 (1996-05-01), Lund et al.
patent: 5528588 (1996-06-01), Bennett et al.
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5546390 (1996-08-01), Stone
patent: 5555264 (1996-09-01), Sallberg et al.
patent: 5557611 (1996-09-01), Cappellari et al.
patent: 5583863 (1996-12-01), Darr, Jr. et al.
patent: 5592476 (1997-01-01), Calamvokis et al.
patent: 5629928 (1997-05-01), Calvignac et al.
patent: 5633859 (1997-05-01), Jain et al.
patent: 5633867 (1997-05-01), Ben-Num et al.
patent: 5689508 (1997-11-01), Lyles
patent: 5704047 (1997-12-01), Schneeberger
patent: 5715250 (1998-02-01), Watanabe
patent: 5719853 (1998-02-01), Ikeda
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5751951 (1998-05-01), Osborne et al.
patent: 5809024 (1998-09-01), Ferguson et al.
patent: 5983004 (1999-11-01), Shaw et al.
patent: 6018759 (2000-01-01), Doing et al.
patent: 6233590 (2001-05-01), Shaw et al.
patent: WO 95/20282 (1995-07-01), Non
Joffe Alexander
Vyshetsky Dmitry
Banankhah Majid
MMC Networks, Inc.
Shenker Michael
Skjerven Morrill & MacPherson LLP
LandOfFree
Systems and methods for multi-tasking, resource sharing and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for multi-tasking, resource sharing and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for multi-tasking, resource sharing and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2573870