Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-04-01
2002-08-13
Coleman, Eric (Department: 2783)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06434590
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods and means for scheduling tasks performed by parallel processors, and particularly to concurrent execution of operations in a number of functional units in cooperation with an assignment manager.
BACKGROUND OF THE INVENTION
Traditional data processing systems execute a sequence of instructions one at a time. To increase the execution speed of computers, multiple processors are used to perform parallel processing of primitive operations, or tasks. Such parallelism often requires substantially more space (memory) than sequential operations.
Many parallel programming languages allow for parallel processing in separate functional units. The goal of these languages is to have the user expose the full parallelism and have the language implementation schedule the parallelism onto processors. Costs of such operations can be measured abstractly in terms of the total number of operations executed by the program, i.e. the “work”, and the length of the longest sequence of dependencies, the i.e. the “depth”. Performance anomalies in such arrangements are often common. Heuristics used in the implementation often fail. Such systems do not necessarily offer good performance, both in terms of time and space.
The aforementioned application Ser. No. 08/502,625, filed Jul. 14, 1995, involved determining sequential ordering of tasks for processing, assigning priorities to the tasks available on the basis of the sequential ordering, selecting a number of tasks greater than a total number of available processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and processing the tasks in the parallel processing elements.
The processing elements in the latter application have buffers and operate in synchronism. An assignment manager pushes tasks into the buffers of each processing element.
SUMMARY OF THE INVENTION
In an embodiment of the invention, the assignment manager makes live tasks available and the processing elements extract the tasks and keep executing the tasks and upon reaching a criterion (time, memory etc.) each element feeds information back to the assignment manager and extracts more tasks. The assignment manager establishes the criterion and determines task priorities on the basis of a sequential schedule independent of the execution of the extracted tasks in the processing elements.
The various aspects of the invention are pointed out in the claims. Other objects and advantages of the invention will become evident when read in light of the accompanying drawings.
REFERENCES:
patent: 4521874 (1985-06-01), Rau
patent: 5155858 (1992-10-01), DeBruler
patent: 5241677 (1993-08-01), Naganuma
patent: 5325525 (1994-06-01), Shan
patent: 5325526 (1994-06-01), Cameron
patent: 5347654 (1994-09-01), Sabot
patent: 5349656 (1994-09-01), Kaneko
patent: 5392429 (1995-02-01), Agrawal
patent: 5442792 (1995-08-01), Chun
patent: 5481747 (1996-01-01), Kametani
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5889989 (1999-03-01), Robertazzi
Blelloch Guy E.
Gibbons Phillip B.
Matias Yossi
Narlikar Girija J.
Avaya Technology Corp.
Coleman Eric
LandOfFree
Methods and apparatus for scheduling parallel processors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for scheduling parallel processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for scheduling parallel processors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2887651