Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-12-23
2004-08-17
Khatri, Anil (Department: 2121)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S102000, C718S103000, C718S104000
Reexamination Certificate
active
06779183
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to multiprocessors, and more particularly, to scheduling multidimensional tasks on multiple processors.
2. Description of the Related Art
The classical multiprocessor scheduling problem is to allocate a set of independent tasks on a collection of processors which may operate at different speeds, such that the entire set of tasks is completed in the least amount of time. The approximate processing time of each task is known. Typically, the number of tasks to be scheduled is larger than the number of available processors and thus multiple tasks may be assigned to each processor. The objective is to find a schedule for assigning tasks to the processors that minimizes the maximum time that any machine is scheduled.
Multiprocessor scheduling is a Nondeterministic Polynomial Time hard (NP-hard) optimization problem. No efficient solution method is known for NP hard problems and for known solution methods the execution time required to solve an instance of the problem is exponential in the number of given tasks. It is thus computationally intractable to compute exact or optimal solutions for large instances. A widely used approach to overcome this barrier is to settle for sub-optimal solutions. Approximation algorithms have been used to provide approximate solutions to scheduling problems which are NP-hard. A polynomial time approximation algorithm produces a solution of objective value which is at most (1+&egr;) times the optimal value for some &egr;>0, wherein &egr; is the relative error. The running time of the algorithm is polynomial in the size of the input instance and hence they are efficient. Such an algorithm is referred to as a (1+&egr;)-approximation algorithm. A problem is said to have a polynomial time approximation scheme (PTAS) if for any fixed &egr;>0, there exists a polynomial time (1+&egr;) approximation algorithm. Thus an arbitrary good approximation can be achieved in polynomial time for a problem with a PTAS.
When each given task is one-dimensional, a PTAS scheme is known for the multiprocessor scheduling problem. It is described in Hochbaum et al., “Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results.”, Journal of the Association for Computing Machinery, Vol. 34, No. 1, January 1987, pp. 144-162 hereby incorporated by reference. The PTAS uses a dual approximation algorithm in which the scheduling problem is viewed as a bin packing problem. In the bin packing problem we are given a set of items (jobs) of size at most 1 and the goal is to assign them to a given number of bins (processors) of height (load) 1 such that all items are assigned to bins without exceeding the height of 1. A feasible solution for the bin packing problem is an assignment which satisfies the above mentioned properties.
Hochbaum et al. describe a polynomial time algorithm which given a feasible bin packing instance finds a feasible solution for the same problem but with the bin height relaxed to (1+&egr;). This algorithm works for any fixed &egr;. The algorithm classifies jobs into large or small depending on whether the size of the job is greater than &egr; or not. Only a fixed number of large jobs (at most 1/&egr;) can be packed into any of the m bins, wherein m represents the number of given bins. The sizes of the large jobs are discretized into O(log 1/&egr;) classes and dynamic programming is used to pack all large jobs into the m bins such that no bin exceeds a height of (1+&egr;). Small jobs are packed on top of the packed large jobs in a greedy fashion. The Hochbaum et al. algorithm works only when the dimension of all jobs is one.
Other conventional techniques for multiprocessor scheduling include using optimal control theory to model tasks and the processing power applied to each task in graphs and hypergraphs. Scheduling algorithms are applied to graphs derived from an original task graph by conventional task expansion techniques. U.S. Pat. No. 5,742,821 discloses a multiprocessor scheduling and execution method in which a set of flow conservation equations and timing constraints are determined for signal processing tasks. Corrected gradient descents are performed using the determined flow conservation equations, timing constraints and an error criteria until substantial convergence to a processor schedule occurs. The signal processing tasks are defined as one dimensional and are executed according to the determined processor schedule.
Multiprocessor scheduling problems become more complex when multi-dimensional tasks are scheduled. A multi-dimensional task executes on a processor with a number of system resources that are time shareable, such as for example a central processing unit (CPU), one or more disks, and network controllers. One conventional type of multi-dimensional task is a database query in parallel database systems. See, Garofalakis et al., “Multi-dimensional Resource Scheduling For Parallel Queries.”, in the Proceedings of the 1996 ACM SIGMOD International Conference on Management Data, Montreal Canada, June 1996, pp. 365-376, hereby incorporated by reference. A need exists for a method for scheduling the execution of multi-dimensional tasks on a plurality of multiprocessor in order to minimize the maximum load on any dimension of the multiprocessor.
SUMMARY OF THE INVENTION
The invention is directed to a method and system of multiprocessor scheduling of multi-dimensional tasks for load sharing among multiprocessors to within any given error criteria, &egr;>0. The method comprises guessing the optimal load on the processors, partitioning the set of multi-dimensional tasks to be scheduled into a set of large tasks and a set of small tasks, guessing the interaction of the set of small tasks and the set of large tasks among the processors which are represented as multi-dimensional bins, packing a discretized set of large tasks in the guessed interaction, determining if the small tasks can be allocated into unallocated space of the multi-dimensional bins after packing of the discretized large tasks, and iteratively repeating the guessing steps until all the tasks can be allocated within the guessed load. The method establishes a schedule of the multi-dimensional tasks from the bin configuration of the set of discretized large tasks and the bin configuration of the set of small tasks. The established schedule provides an approximate value of the maximum load among the multiprocessors which is less than (1+&egr;) times the optimal load. For a pre-selected number of different resources accessed by the multi-dimensional tasks and error criteria, the method provides a schedule having polynomial time for the number of tasks and the number of multiprocessors. For a fixed number of different resources used by the multi-dimensional tasks and a fixed relative error target &egr;, the method provides a schedule with the above mentioned guarantee in time polynomial in the number of tasks and number of multi-processors.
Other features of the invention will become apparent from the following detailed description considered in conjunction with the accompanying drawings. It is to be understood, however, that the drawings are designed solely for purposes of illustration and do not serve to limit the invention, for which reference should be made to the appended claims.
REFERENCES:
patent: 4495559 (1985-01-01), Gelatt, Jr. et al.
patent: 5016503 (1991-05-01), Morton
patent: 5175692 (1992-12-01), Mazouz et al.
patent: 5493633 (1996-02-01), Obata
patent: 5617514 (1997-04-01), Dolby et al.
patent: 5742821 (1998-04-01), Prasanna
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5889989 (1999-03-01), Robertazzi et al.
patent: 6340560 (2002-01-01), Inaba et al.
Chandra Chekuri, Sanjeev Khanna. On multi-dimensional packing problems. Proceedings of the 10thannual ACM-SIAM symposium on Discrete algorithms. Jan. 1999.*
“Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results”, Dorit S. Hochbaum,Jour
Chekuri Chandra
Khanna Sanjeev
Khatri Anil
Pham Thomas
LandOfFree
Method and system for load scheduling multidimensional tasks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for load scheduling multidimensional tasks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for load scheduling multidimensional tasks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3297827