Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-11-12
2003-12-09
Patel, Ramesh (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S207000
Reexamination Certificate
active
06662203
ABSTRACT:
BACKGROUND
The present invention generally relates to processing systems, and more particularly to multiprocessing systems having multiple processing units.
Many conventional central processing systems, such as the APZ processor 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 multiprocessing system, i.e. a processing system with multiple processing units operating in parallel. When having multiple processing units operating in parallel, the scheduling algorithm must offer high utilization of the processing units. In many multiprocessing systems, the scheduling is performed in order of the priority level of the jobs, tasks or processes to be executed. In this way, the available capacity may be directed towards jobs of high priority levels at first, and subsequently the capacity may be directed towards jobs of lower priority levels. However, each time a job of higher priority level arrives to the processing system, it will normally interrupt execution of a job of lower priority level. This will generally lead to a high number of priority level changes, and inefficient use of the execution capacity. In fact, it may be difficult to guarantee that any time at all is devoted to jobs of lower priority levels, even if a load regulation mechanism is used for limiting the total system load.
Furthermore, executing a single job or just a few jobs in the multiprocessing system is a waste of resources, since only one or a few of the multiple processing units are utilized. Consequently, whenever a high and stable flow of jobs to the multiple processing units can not be ensured, the parallel execution capacity of the multiple processing units is not fully utilized, thus degrading the performance of the processing system.
SUMMARY
The present invention overcomes these and other drawbacks of the prior art arrangements.
It is a general object of the present invention to provide a multiprocessing system in which the multiple processing units are enabled to operate in a more efficient manner than in multiprocessing systems of the prior art, and in which the number of priority level changes is minimized.
In particular, it is desirable to obtain a multiprocessing system in which the time available for execution of jobs, tasks or processes of lower priority levels is considerably increased at the same time as the multiprocessing system operates efficiently at all priority levels.
Yet another object of the invention is to provide a method for handling signals in a processing system having multiple processing units.
These and other objects are met by the invention as defined by the accompanying patent claims.
The present invention is mainly directed to a multiprocessing system in which signals or processes are scheduled in order of their priority level.
Briefly, the invention is based on batch-wise acceptance and scheduling of job signals. For this purpose, the invention utilizes at least one delay queue for temporarily storing job signals to the processing system before they are accepted for scheduling, and circuitry for batch-wise insertion of the temporarily stored job signals into the job scheduler of the multiprocessing system. In this way, the utilization of the parallel processing units is increased and the number of changes between different priority levels in the multiprocessing system is minimized or at least reduced, as will be explained in more detail in the description of embodiments.
As mentioned above, processing a single job, task or process in the multiprocessing system is a waste of resources. Delaying external signals in the delay queue and accepting a batch of the delayed signals for scheduling and subsequent processing by the multiple processing units makes it more likely that several signals are available for parallel processing at once.
Between the batch-wise insertions of job signals, new job signals that arrive to the processing system are collected and delayed in the delay queue. In this period of time, as soon as all the scheduled jobs of higher priority levels have been executed, the scheduler is free to start forwarding jobs of lower priority levels to the parallel processing units without the interference from job signals of higher priority levels arriving to the delay queue. Consequently, another purpose of the delay queue is to free time for execution of low priority jobs. In addition, system load can be estimated in a simple manner by measuring the amount of time left for execution of jobs of lower priority levels.
Preferably, the processing system comprises an individual delay queue for each priority level. Advantageously, each delay queue is associated with a corresponding job buffer in the job scheduler, and the job signals of each delay queue are transferred batch-wise to its corresponding job buffer.
The invention is not limited to the management of job signals that directly trigger the execution of corresponding jobs. Many commercial operating systems work with predefined processes. In such processing systems, each incoming signal is directed to its corresponding process, and the scheduling is performed on the processes and not based on the incoming signals. According to an alternative embodiment of the invention, the delay queue is utilized for temporarily storing process signals, and the process signals of the delay queue are inserted batch-wise into a process handler which directs the process signals to corresponding processes having different priority levels. Subsequently, the processes are scheduled for parallel execution by the multiple processing units in order of their priority level.
The invention offers the following advantages:
efficient utilization of the parallel execution capacity of the multiple processing units;
the number of changes between different priority levels is minimized or at least reduced;
the time available for execution of jobs, tasks or processes of lower priority levels is considerably increased at the same time as the multiprocessing system operates efficiently at all priority levels; and
system load can be measured in a simple manner.
Other advantages offered by the present invention will be appreciated upon reading of the below description of the embodiments of the invention.
REFERENCES:
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: 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
Egeland Terje
Holmberg Per Anders
Johnson Sten Edvard
Kling Lars-Örjan
Patel Ramesh
Pham Thomas
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Batch-wise handling of signals in a processing system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Batch-wise handling of signals in a processing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Batch-wise handling of signals in a processing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129473