Hierarchical scheduling method for processing tasks having precedence constraints on a parallel processing system
US5392430A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Oct 30, 1992 |
| Grant date | Feb 21, 1995 |
| Priority date | — |
| Expiry date | Oct 30, 2012 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99933
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A plurality of queries (jobs) which consist of sets of tasks with precedence constraints between them are optimally scheduled in two stages of scheduling for processing on a parallel processing system. In a first stage of scheduling, multiple optimum schedules are created for each job, one optimum schedule for each possible number of processors which might be used to execute each job, and an estimated job execution time is determined for each of the optimum schedules created for each job, thereby producing a set of estimated job execution times for each job which are a function of the number of processors used for the job execution. Precedence constraints between tasks in each job are respected in creating all of these optimum schedules. Any known optimum scheduling method for parallel processing tasks that have precedence constraints among tasks may be used but a novel preferred method is also disclosed. The second stage of scheduling utilizes the estimated job execution times determined in the first stage of scheduling to create an overall optimum schedule for the jobs. The second stage of scheduling does not involve precedence constraints because the precedence constraints are b…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.