IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0241720
(2005-09-29)
|
등록번호 |
US-8281313
(2012-10-02)
|
발명자
/ 주소 |
- Santos, Cipriano A.
- Beyer, Dirk
- Zhou, Yunhong
- Kelly, Terence P.
|
출원인 / 주소 |
- Hewlett-Packard Development Company, L.P.
|
인용정보 |
피인용 횟수 :
2 인용 특허 :
13 |
초록
▼
An embodiment of a method of scheduling computer processing begins with a first step of receiving job properties for a plurality of jobs to be processed in a multi-processor computing environment. At least some of the jobs each comprise a plurality of stages, one or more tasks for each stage, and pr
An embodiment of a method of scheduling computer processing begins with a first step of receiving job properties for a plurality of jobs to be processed in a multi-processor computing environment. At least some of the jobs each comprise a plurality of stages, one or more tasks for each stage, and precedence constraints among the stages. The method continues with a second step of determining a schedule for processing at least a subset of the plurality of jobs on processors within the multi-processor computing environment from a solution of a mathematical program that provides a near maximal completion reward. The schedule comprises a sequence of tasks for each processor. In a third step, the computer processing jobs are processed on the processors according to the sequence of tasks for each processor.
대표청구항
▼
1. A method of scheduling a plurality of computer processing jobs comprising: determining, by executing instructions on a scheduling processor, a schedule for processing the plurality of computer processing jobs on processors within a multi-processor computing environment, wherein each job has a plu
1. A method of scheduling a plurality of computer processing jobs comprising: determining, by executing instructions on a scheduling processor, a schedule for processing the plurality of computer processing jobs on processors within a multi-processor computing environment, wherein each job has a plurality of stages, at least one task for each stage, precedence constraints among the stages, and a job completion due time, wherein the precedence constraints include a particular precedence constraint between a first of the stages and a second of the stages, where each of the first and second stages has plural tasks, wherein a completion reward accrues for a job if the job completes by the corresponding job completion due time, and wherein the determined schedule assigns sequences of tasks to the processors in a manner that maximizes a sum of the completion rewards for the plurality of computer processing jobs; andprocessing the plurality of computer processing jobs on the processors within the multi-processor computing environment according to the determined schedule. 2. The method of claim 1 wherein the instructions executed by the scheduling processor comprise a mixed integer program. 3. The method of claim 2 wherein the mixed integer program comprises decision variables, state variables, input and derived parameters, constraints, and an objective. 4. The method of claim 3 wherein the decision variables comprise task-to-processor assignment decision variables, job selection decision variables, job-to-processor assignment decision variables, and stage sequence decision variables. 5. The method of claim 3 wherein the state variables comprise stage-at-processor completion time variables and job completion time variables. 6. The method of claim 5 wherein the state variables further comprise stage-at-cluster completion time variables. 7. The method of claim 3 wherein the constraints of the mixed integer program comprise tasks precedence constraints, job completion time constraints, job selection constraints, processor constraints, and sequence constraints. 8. The method of claim 3 wherein the objective comprises minimizing penalties. 9. The method of claim 8 wherein the penalties comprise fair share violation penalties. 10. The method of claim 8 wherein the penalties comprise due time violation penalties. 11. The method of claim 1, wherein the determining comprises finding a solution to a program that includes solving for decision variables of the program, wherein the decision variables include task-to-processor assignment variables, where each of the task-to-processor assignment variables represents a number of tasks assigned to a corresponding one of the processors. 12. The method of claim 11, wherein the decision variables further include job-to-processor assignment variables each indicating an assignment of at least one task of a corresponding one of the jobs to a corresponding one of the processors. 13. A non-transitory computer readable medium comprising computer code that upon execution cause a computer to: determine a schedule for processing a plurality of computer processing jobs on processors within a multi-processor computing environment, wherein each job has a plurality of stages, at least one task for each stage, precedence constraints among the stages, and a job completion due time, wherein the precedence constraints include a particular precedence constraint between a first of the stages and a second of the stages, where each of the first and second stages has plural tasks, wherein a completion reward accrues for a job if the job completes by the corresponding job completion due time, and wherein the determined schedule assigns sequences of tasks to the processors in a manner that maximizes a sum of the completion rewards for the plurality of computer processing jobs; andprocess the plurality of computer processing jobs on the processors within the multi-processor computing environment according to the determined schedule. 14. The computer readable medium of claim 13, wherein the determining comprises finding a solution to a program that includes solving for decision variables of the program, wherein the decision variables include task-to-processor assignment variables, where each of the task-to-processor assignment variables represents a number of tasks assigned to a corresponding one of the processors. 15. The computer readable medium of claim 14, wherein the decision variables further include job-to-processor assignment variables each indicating an assignment of at least one task of a corresponding one of the jobs to a corresponding one of the processors.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.