Boots – shoes – and leggings
Patent
1992-10-30
1995-02-21
Heckler, Thomas M.
Boots, shoes, and leggings
364DIG1, 3642818, 3642816, 3642283, G06F 946
Patent
active
053924304
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 between tasks within the same job and not between tasks in separate jobs, so jobs may be scheduled without observing any precedence constraints. Any known optimum scheduling method for the parallel processing of jobs that have no precedence constraints may be used, but a novel preferred method is also disclosed.
REFERENCES:
patent: 3648253 (1972-03-01), Mullery et al.
patent: 3916383 (1975-10-01), Malcolm
patent: 4642756 (1987-02-01), Sherrod
"An Approximation Algorithm For Scheduling Tasks On Varying Partition Sizes In Partitionable Multipocessor Systems", R. Krishnamurti and E. Ma, Research Report, RC 15900 (#70682) Jul. 3, 1990.
"An Effective Algorithm For Parallelizing Sort Merge Joins In The Presence Of Data Skew", IEEE, Proceedings of the Second International Symposium On Databases In Parallel and Distributed Systems, Dublin, Ireland, Jul. 2-4, 1990. (J. Wolf, D. Dias and P. Yu).
"An Effective Algorithm For Parallelizing Hash Joins In The Presence Of Data Skew", J. Wolf, D. Dias, P. Yu and J. Turek, Proceedings Of The Seventh International Conference On Data Engineering, Kobe, Japan, Apr. 8-12, 1991.
"Percentile Finding Algorithm For Multiple Sorted Runs", B. Iyer, G. Ricard, P. Varman, Proceedings Of The Fifteenth International Conference On Very Large Data Bases, Amsterdam, Netherlands, Aug. 1989.
"Complexity of Scheduling Parallel Task Systems", SIAM Journal Of Discrete Mathematics, J. Du and Y. T. Leung (1989).
"Scheduling And Processor Allocation For Parallel Execution Of Multi-Join Queries", M. S. Chen, P. S. Yu, K. L. Wu, Proceddings of the IEEE Conference On Data Engineering (1992).
"Approximate Algorithms For Scheduling Parallelizable Tasks", J. J. Turek, J. L. Wolf, P. S. Yu, Proceedings On the Symposium On Parallel Algorithms and Architectures, 1992.
"Scheduling Parallelizable Tasks: Putting It all On The Shelf", J. J. Turek, J. L. Wolf, K. Pattipati and P. S. Yu, Proceedings of the ACM Sigmetrics Conference, 1992.
Chen Ming-Syan
Turek John J. E.
Wolf Joel L.
Yu Philip S.
Drumheller Ronald L.
Heckler Thomas M.
International Business Machines
Ludwin Richard M.
LandOfFree
Hierarchical scheduling method for processing tasks having prece does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical scheduling method for processing tasks having prece, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical scheduling method for processing tasks having prece will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1941131