Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-11-12
2004-03-30
Khatri, Anil (Department: 2121)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C712S023000, C712S234000, C712S235000
Reexamination Certificate
active
06714961
ABSTRACT:
BACKGROUND
The present invention generally relates to processing systems, and more particularly to a processing system having multiple processing units, and a method for handling job signals in such a processing system.
Many conventional central processing systems, such as the APZ processing system in the known AXE Digital Switching System from Telefonaktiebolaget LM Ericsson, are built around a single processing unit, referred to as an execution pipeline in the AXE system. However, central processing systems based on a single processing unit have limitations with regard to capacity.
One way of increasing the processing capacity is to build the processing system as a multiprocessor system, i.e. a processing system with multiple processors or processing units operating in parallel. In conventional multiprocessing systems, each processing unit processes an input signal to execute a corresponding sequence of instructions, one input signal being assigned to each processing unit at a time.
In a so-called superscalar processor, which explores fine grained parallelism found between neighboring instructions, the functional units within the processor are arranged to simultaneously execute several instructions in parallel.
However, there is still a general demand for even more efficient processing systems.
SUMMARY
The present invention constitutes a further development of the prior art multiprocessing system.
The invention is directed towards a multiprocessing system adapted for speculative execution of jobs. In a multiprocessing system, the processing units independently execute different jobs in parallel. However, at all times during parallel execution of jobs in a processing system adapted for speculative execution, only one processing unit has commit priority and is allowed to execute its current job non-speculatively, performing write back to the memory system and committing signal sendings. Jobs in the other processing units are executed speculatively and may be flushed if dependencies are detected.
During development of such a processing system, a particular problem was encountered: If the job with commit priority has a longer execution time than the other speculative jobs, the speculatively executing processing units have completed execution of their assigned jobs long before completion of the commit job. The speculatively executed jobs then have to wait until the commit job has been executed to completion so that one of the speculatively executed jobs can get commit priority. This generally means that the speculatively executing processing units simply wait for commit priority and valuable execution time is wasted, severely degrading the performance of the processing system.
Therefore, it is a general object of the present invention to provide a more flexible and efficient speculative multiprocessing system as well as a more efficient method for handling job signals in such a multiprocessing system.
It is another object of the invention to provide a job queue for use in a multiprocessing system.
These and other objects are met by the invention as defined by the accompanying patent claims.
The general idea according to the invention is based on assigning, for at least one processing unit in the multiprocessing system, a first job signal to the processing unit for speculative execution of a corresponding first job, assigning a further job signal to the processing unit for speculative execution of a corresponding further job, and initiating speculative execution of said further job when the processing unit has completed speculative execution of the first job. If desirable, even more job signals may be assigned to the processing unit for speculative execution, execution of the corresponding jobs being initiated as soon as the processing unit has completed speculative execution of the previously assigned job. The processing unit with commit priority may also be assigned a further job signal, the execution of which is initiated as soon as the commit job has been completed.
By assigning multiple job signals for speculative execution by the processing units, the effects of variations in execution time between jobs are neutralized or at least greatly reduced, and the overall performance of the processing system is substantially improved since the processing units are allowed to execute a plurality of jobs speculatively while waiting for commit priority.
In general, the protocol needed for assigning job signals to the processing units, keeping track of the job signals and handling the commit priority is managed by a job signal queue in combination with appropriate control software or hardware.
In order to identify a job signal, its corresponding job or the results thereof in the operation of the processing system, each job signal is associated with an identifier. The identifier may be in the form of a pointer to the storage position of the corresponding job signal in the job signal queue. Alternatively, the identifier comprises a unit label representing the identity of the processing unit to which the job signal is assigned, and a job-signal distinguishing label representing the identity the job signal is given in the processing unit. In a processing system adapted for speculative execution, the results of speculatively executed jobs are temporarily stored in a write queue arrangement, waiting to be committed. According to the invention, when a speculatively executed job gets commit priority the results of that job are retrieved by means of the identifier.
The invention offers the following advantages:
The overall performance of the processing system is substantially improved;
Flexible and efficient speculative execution is provided; and
The effects of variations in execution time between jobs are neutralized.
Other advantages offered by the present invention will be appreciated upon reading of the below description of the embodiments of the invention.
REFERENCES:
patent: 4466061 (1984-08-01), DeSantis et al.
patent: 5072364 (1991-12-01), Jardine et al.
patent: 5195181 (1993-03-01), Bryant et al.
patent: 5239539 (1993-08-01), Uchida et al.
patent: 5287467 (1994-02-01), Blaner et al.
patent: 5379428 (1995-01-01), Belo
patent: 5511172 (1996-04-01), Kimura et al.
patent: 5560029 (1996-09-01), Papadopoulos et al.
patent: 5740393 (1998-04-01), Vidwans et al.
patent: 5781753 (1998-07-01), McFarland et al.
patent: 5787300 (1998-07-01), Wijaya
patent: 5797025 (1998-08-01), Popescu et al.
patent: 5812839 (1998-09-01), Hoyt et al.
patent: 5832262 (1998-11-01), Johnson et al.
patent: 5848257 (1998-12-01), Angle et al.
patent: 5870597 (1999-02-01), Panwar et al.
patent: 5875326 (1999-02-01), Cheong et al.
patent: 230721 (1987-08-01), None
patent: 3263164 (1991-11-01), None
patent: 4100449 (1992-04-01), None
patent: 5274279 (1993-10-01), None
patent: 6276198 (1994-09-01), None
patent: 10143382 (1998-05-01), None
patent: 88/02513 (1988-04-01), None
patent: 99/31589 (1999-06-01), None
Multiscalar Processors, Computer Sciences Department, University of Wisconsin-Madison, Madison, WI 53706, Gurindar S. Sohi, et al.
The Effect of Speculative Execution on Cache Performance, University of Michigan, Jim Pierce, et al, 0-8186-5602-6/941994 IEEE.
Hardware for speculative Run-Time Parallelization in distributed Shared-Memory Multiprocessors, University of Illinois at Urbana-Champaign, IL 61801, Ye Zhang, et al, 0-8186-8323-6/98 1998 IEEE.
Operating System Concepts,Abraham Silberschatz, et al. Addison-Wesley Series in Computer Science, Jun., 1988, Chapter 4, pp. 149-185.
MAJC™Documentation, First MAJC™Implementation Presentation, MAJC-5200: A VLIW Convergent MPSOC by Marc Tremblay, Chief Architect, Microprocessor Forum, Oct. 1999; Introduction to the MAJC™ Architecture; MAJC Architecture Presentation; and MACK Architecture Tutorial, at http://wwwwseast.usec.sun.com/ microelectronics/ MAJC/documentation, Nov. 10, 1999.
Carlsson Magnus
Egeland Terje
Holmberg Per Anders
Linnermark Nils Ola
Strömbergson Karl Oscar Joachim
Khatri Anil
Pham Thomas
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Multiple job signals per processing unit in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple job signals per processing unit in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple job signals per processing unit in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205367