Computing the processor desires of jobs in an adaptively parallel scheduling environment
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/46
G06F-015/173
출원번호
US-0729176
(2007-03-28)
등록번호
US-8510741
(2013-08-13)
발명자
/ 주소
Leiserson, Charles E.
Agrawal, Kunal
Hsu, Wen-Jing
He, Yuxiong
출원인 / 주소
Massachusetts Institute of Technology
대리인 / 주소
Nields, Lemack & Frame, LLC
인용정보
피인용 횟수 :
4인용 특허 :
18
초록▼
The present invention describes a system and method for scheduling jobs on a multiprocessor system. The invention includes schedulers for use in both work-sharing and work-stealing environments. Each system utilizes a task scheduler using historical usage information, in conjunction with a job sched
The present invention describes a system and method for scheduling jobs on a multiprocessor system. The invention includes schedulers for use in both work-sharing and work-stealing environments. Each system utilizes a task scheduler using historical usage information, in conjunction with a job scheduler to achieve its results. In one embodiment, the task scheduler measures the time spent on various activities, in conjunction with its previous processor allocation or previous desire, to determine an indication of its current processor desire. In another embodiment of the present invention, the task scheduler measures the resources used by the job on various activities. Based on these measurements, the task scheduler determines the efficiency of the job and an indication of its current processor desire. In another embodiment, the task scheduler measures the resources consumed executing the job and determines its efficiency and an indication of its current processor desire.
대표청구항▼
1. A non-transitory computer-readable medium storing a plurality of computer executable instructions which, when executed, perform a method of generating an indication of a particular job's desired processor allocation, where said indication is to be used to allocate processing resources among a plu
1. A non-transitory computer-readable medium storing a plurality of computer executable instructions which, when executed, perform a method of generating an indication of a particular job's desired processor allocation, where said indication is to be used to allocate processing resources among a plurality of jobs in a multiprocessor computer system in a work-stealing environment, said method comprising: a. measuring the time spent by said particular job performing at least one of a plurality of activities, said activities selected from the group consisting of mugging cycles, steal cycles, unsuccessful steal cycles, successful steal cycles, and waste, andb. generating, responsive to said measurement, an indication of a desired processor allocation. 2. The non-transitory computer-readable medium of claim 1, wherein said step of measuring time comprises obtaining an indication of time when said particular job begins to perform at least one of said plurality of activities, obtaining a second indication of time when said particular job terminates performance of said at least one of said plurality of activities, and determining the difference between said two obtained indications of time. 3. The non-transitory computer-readable medium of claim 1, wherein said step of measuring time comprises starting a timer when said particular job begins to perform at least one of said plurality of activities, and stopping said timer when said particular job terminates performance of said at least one of said plurality of activities. 4. The non-transitory computer-readable medium of claim 1, wherein said step of measuring time comprises updating a counter during said performance of said at least one of said plurality of activities. 5. The non-transitory computer-readable medium of claim 1, wherein said step of measuring time comprises measuring the power consumed during said performance of at least one of said plurality of activities. 6. The non-transitory computer-readable medium of claim 1, wherein said activities comprise mugging cycles. 7. The non-transitory computer-readable medium of claim 1, wherein said activities comprise steal cycles. 8. The non-transitory computer-readable medium of claim 1, wherein said activities comprise unsuccessful steal cycles. 9. The non-transitory computer-readable medium of claim 1, wherein said activities comprise successful steal cycles. 10. The non-transitory computer-readable medium of claim 1, wherein said indication of a desired processor allocation comprises a number of desired processors. 11. The non-transitory computer-readable medium of claim 1, wherein said measuring and generating steps are performed on a recurring basis. 12. The non-transitory computer-readable medium of claim 11, wherein said indication of a desired processor allocation is relative to a previous processor allocation. 13. The non-transitory computer-readable medium of claim 11, wherein said indication of a desired processor allocation is relative to a previous desired indication of processor allocation. 14. A non-transitory computer-readable medium storing a plurality of computer executable instructions which, when executed, perform a method of generating an indication of a particular job's desired processor allocation, where said indication is to be used to allocate processing resources among a plurality of jobs in a multiprocessor computer system in a work-stealing environment, said method comprising: a. measuring the resources spent by said particular job performing at least one of a plurality of activities, said activities selected from the group consisting of mugging cycles, steal cycles, unsuccessful steal cycles, successful steal cycles, and waste,b. determining, responsive to said measurement, an efficiency of said particular job, where said efficiency is a measure of the useful work performed by said job, andc. generating an indication of a desired processor allocation for said particular job, responsive to said efficiency. 15. The non-transitory computer-readable medium of claim 14, wherein said resources comprise time. 16. The non-transitory computer-readable medium of claim 14, wherein said resources are selected from the group consisting of computer cycles, cache misses, I/O events, cache hits, and power consumption. 17. The non-transitory computer-readable medium of claim 14, wherein said activities comprise mugging cycles and said resources measured performing mugging cycles positively correlate to said efficiency. 18. The non-transitory computer-readable medium of claim 14, wherein said activities comprise mugging cycles and said resources measured performing mugging cycles negatively correlate to said efficiency. 19. The non-transitory computer-readable medium of claim 14, wherein said activities comprise steal cycles and said resources measured performing steal cycles positively correlate to said efficiency. 20. The non-transitory computer-readable medium of claim 14, wherein said activities comprise steal cycles and said resources measured performing steal cycles negatively correlate to said efficiency. 21. The non-transitory computer-readable medium of claim 14, wherein said activities comprise successful steal cycles and said resources measured performing successful steal cycles positively correlate to said efficiency. 22. The non-transitory computer-readable medium of claim 14, wherein said activities comprise successful steal cycles and said resources measured performing successful steal cycles negatively correlate to said efficiency. 23. The non-transitory computer-readable medium of claim 14, wherein said activities comprise unsuccessful steal cycles and said resources measured performing unsuccessful steal cycles positively correlate to said efficiency. 24. The non-transitory computer-readable medium of claim 14, wherein said activities comprise unsuccessful steal cycles and said resources measured performing steal cycles negatively correlate to said efficiency. 25. The non-transitory computer-readable medium of claim 14, wherein said indication of said desired allocation is generated on a recurring basis and said indication of desired allocation is responsive to a previous indication of desired allocation. 26. The non-transitory computer-readable medium of claim 25, wherein said indication of desired allocation is reduced from a previous indication of desired allocation if said efficiency is less than a first value. 27. The non-transitory computer-readable medium of claim 25, wherein said indication of desired allocation is increased from a previous indication of desired allocation if said efficiency is greater than a second value. 28. The non-transitory computer-readable medium of claim 14, wherein said indication of said desired allocation is generated on a recurring basis and said indication of desired allocation is responsive to a previous allocation. 29. The non-transitory computer-readable medium of claim 28, wherein said indication of desired allocation is reduced from a previous allocation if said efficiency is less than a first value. 30. The non-transitory computer-readable medium of claim 28, wherein said indication of desired allocation is increased from a previous allocation if said efficiency is greater than a second value. 31. The non-transitory computer-readable medium of claim 14, wherein said measuring is performed over a time period and said indication of desired allocation is generated at the end of said time period. 32. The non-transitory computer-readable medium claim 31, wherein said time period is of fixed duration. 33. The non-transitory computer-readable medium of claim 14, wherein said indication of desired processor allocation is adapted to be used with a job scheduler utilizing a dynamic equipartitioning algorithm.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (18)
Donald Edward Carmon ; Frank Edward Grieco ; Llewellyn Bradley Marshall, IV, Apparatus for pacing cycle steals from a data processor and methods for implementing the same.
Mullen David Clarence, Dynamically assigning priorities for the allocation of server resources to completing classes of work based upon achievement of server level goals.
Engelstad Steven L. (Lisle IL) Falck Keith F. (Naperville IL) Vandendorpe James E. (Naperville IL), Method for automatic memory reclamation for object-oriented systems with real-time constraints.
Boland Vernon K. ; Brasche Kevin R. ; Smith Kenneth A., Method for load balancing a per processor affinity scheduler wherein processes are strictly affinitized to processors an.
Jensen, Craig; Staffer, Andrew; Thomas, Basil, Method, system and apparatus for scheduling computer micro-jobs to execute at non-disruptive times and modifying a minimum wait time between the utilization windows for monitoring the resources.
Carmon Donald Edward ; Grieco Frank Edward ; Marshall ; IV Llewellyn Bradley, System for counting clock cycles stolen from a data processor and providing the count value to a second processor acces.
Suarez Gracia, Dario; Kumar, Tushar; Natarajan, Aravind; Hastantram, Ravish; Cascaval, Gheorghe Calin; Zhao, Han, Data management for multiple processing units using data transfer costs.
Balakrishnan, Ganesh; Peyravian, Mohammad; Ramani, Srinivasan; Rogers, Brian M.; Vu, Ken V., Processor power optimization with response time assurance.
Balakrishnan, Ganesh; Peyravian, Mohammad; Ramani, Srinivasan; Rogers, Brian M.; Vu, Ken V., Processor power optimization with response time assurance.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.