Load balancing on hetrogenous processing cluster based on exceeded load imbalance factor threshold determined by total completion time of multiple processing phases
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-001/12
G06F-009/46
G06F-009/50
G06F-009/52
출원번호
US-0409872
(2012-03-01)
등록번호
US-9038088
(2015-05-19)
발명자
/ 주소
Phull, Rajat
Cadambi, Srihari
Ravi, Nishkam
Chakradhar, Srimat
출원인 / 주소
NEC Laboratories America, Inc.
대리인 / 주소
Kolodka, Joseph
인용정보
피인용 횟수 :
2인용 특허 :
3
초록▼
Methods and systems for managing data loads on a cluster of processors that implement an iterative procedure through parallel processing of data for the procedure are disclosed. One method includes monitoring, for at least one iteration of the procedure, completion times of a plurality of different
Methods and systems for managing data loads on a cluster of processors that implement an iterative procedure through parallel processing of data for the procedure are disclosed. One method includes monitoring, for at least one iteration of the procedure, completion times of a plurality of different processing phases that are undergone by each of the processors in a given iteration. The method further includes determining whether a load imbalance factor threshold is exceeded in the given iteration based on the completion times for the given iteration. In addition, the data is repartitioned by reassigning the data to the processors based on predicted dependencies between assigned data units of the data and completion times of a plurality of the processers for at least two of the phases. Further, the parallel processing is implemented on the cluster of processors in accordance with the reassignment.
대표청구항▼
1. A method for managing data loads on a cluster of processors that implement an iterative procedure through parallel processing of data for the procedure, the method comprising: for at least one iteration of the procedure, monitoring completion times of a plurality of different processing phases th
1. A method for managing data loads on a cluster of processors that implement an iterative procedure through parallel processing of data for the procedure, the method comprising: for at least one iteration of the procedure, monitoring completion times of a plurality of different processing phases that are undergone by each of the processors in a given iteration;determining whether a load imbalance factor threshold is exceeded in the given iteration based on the completion times of each phase for the given iteration;if the load imbalance factor threshold is exceeded, repartitioning the original data load by reassigning the data to the processors based on predicted dependencies between assigned data units of the data and completion times of a plurality of the processers for at least two of the phases; andimplementing the parallel processing on the cluster of processors in accordance with the reassigning;wherein the cluster of processors includes at least one processor with heterogeneous processing capability and processing speed, and at least one processor with heterogeneous communication capability and communication speed;wherein the determining further comprises computing an imbalance factor for the given iteration that is normalized by a total iteration time for the given iteration that includes each of the plurality of different processing phases;wherein the plurality of different processing phases are successive phases and include a computation phase, a data transfer phase, a synchronization phase and a convergence check phase; andwherein the imbalance factor is WmaxK-WminKTK*WmaxK, where K is the given iteration, WmaxK is a maximum completion time for the synchronization phase among the completion times monitored by the monitoring for the synchronization phase for the given iteration, WminK is a minimum completion time for the synchronization phase among the completion times monitored by the monitoring for the synchronization phase for the given iteration and TK is the total iteration time for the given iteration. 2. The method of claim 1, wherein the plurality of different processing phases includes a synchronization phase and wherein the repartitioning further comprises determining which of the processors has a highest completion time for the synchronization phase for the given iteration and which of the processors has a lowest completion time for the synchronization phase for the given iteration. 3. The method of claim 2, wherein the processor that has the highest completion time for the synchronization phase for the given iteration is a first processor, wherein the processor that has the lowest completion time for the synchronization phase for the given iteration is a second processor and wherein the repartitioning further comprises reassigning a given number of data units of said data from the first processor to the second processor based on said predicted dependencies. 4. The method of claim 3, wherein the at least two of the phases includes the computation phase and the data transfer phase. 5. The method of claim 4, wherein the dependencies include a first dependency that is a dependency between data units and the completion time of the computation phase and a second dependency that is a dependency between the data units and the completion time of the data transfer phase. 6. The method of claim 5, wherein the repartitioning further comprises computing, based on said first dependency, a first number of data units, the reassignment of which from the first processor to the second processor renders the computation phase of the first processor equal to the computation phase of the second processor, computing, based on said second dependency, a second number of data units, the reassignment of which from the first processor to the second processor renders a data transfer phase of the first processor equal to a data transfer phase of the second processor, and selecting a lesser of the first number of data units and the second number of data units as the given number of data units for repartioning. 7. The method of claim 1, wherein the method further comprises: predicting said dependencies based on the completion times monitored by the monitoring for a plurality of iterations of the procedure using a time estimation model. 8. A non-transitory computer readable storage medium comprising a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform a method for managing data loads on a cluster of processors that implement an iterative procedure through parallel processing of data for the procedure, the method comprising: for at least one iteration of the procedure, monitoring completion times of a plurality of different processing phases that are undergone by each of the processors in a given iteration;determining whether a load imbalance factor threshold is exceeded in the given iteration based on the completion times of each phase for the given iteration; andif the load imbalance factor threshold is exceeded, repartitioning the data load by reassigning the data to the processors based on predicted dependencies between assigned data units of the data and completion times of a plurality of the processers for at least two of the phases;wherein the cluster of processors includes at least one processor with heterogeneous processing capability and processing speed, and at least one processor with heterogeneous communication capability and communication speed;wherein the determining further comprises computing an imbalance factor for the given iteration that is normalized by a total iteration time for the given iteration that includes each of the plurality of different processing phases;wherein the plurality of different processing phases are successive phases and include a computation phase, a data transfer phase, a synchronization phase and a convergence check phase; andwherein the imbalance factor is WmaxK-WminKTK*WmaxK, where K is the given iteration, WmaxK is a maximum completion time for the synchronization phase among the completion times monitored by the monitoring for the synchronization phase for the given iteration, WminK is a minimum completion time for the synchronization phase among the completion times monitored by the monitoring for the synchronization phase for the given iteration and TK is the total iteration time for the given iteration. 9. A system for managing data loads comprising: a cluster of processors, including at least one processor with heterogeneous processing capability and processing speed, and at least one processor with heterogeneous communication capability and communication speed, configured to implement an iterative procedure through parallel processing of data for the procedure;a data repartitioner module configured to partition and assign the data to the processors for the parallel processing; anda balancer module configured to, for at least one iteration of the procedure, monitor completion times of a plurality of different processing phases that are undergone by each of the processors in a given iteration, to determine whether a load imbalance factor threshold is exceeded in the given iteration based on the completion times of each phase for the given iteration, and, if the load imbalance factor threshold is exceeded, to direct the data repartitioner module to reparation the data by reassigning the data to the processors based on predicted dependencies between assigned data units of the data and completion times of a plurality of the processers for at least two of the phases;wherein the balancer module is further configured to compute an imbalance factor for the given iteration that is normalized by a total iteration time for the given iteration that includes each of the plurality of different processing phaseswherein the plurality of different processing phases are successive phases and include a computation phase, a data transfer phase, a synchronization phase and a convergence check phase; andwherein the imbalance factor is WmaxK-WminKTK*WmaxK, where K is the given iteration, WmaxK is a maximum completion time for the synchronization phase among the monitored completion times monitored for the synchronization phase for the given iteration, WminK is a minimum completion time for the synchronization phase among the monitored completion times for the synchronization phase for the given iteration and TK is the total iteration time for the given iteration. 10. The system of claim 9, wherein the plurality of different processing phases includes a synchronization phase and wherein the balancer module is further configured to determine which of the processors has a highest completion time for the synchronization phase for the given iteration and which of the processors has a lowest completion time for the synchronization phase for the given iteration. 11. The system of claim 10, wherein the processor that has the highest completion time for the synchronization phase for the given iteration is a first processor, wherein the processor that has the lowest completion time for the synchronization phase for the given iteration is a second processor and wherein the balancer module is further configured to direct the data repartitioner module to reassign a given number of data units of said data from the first processor to the second processor based on said predicted dependencies. 12. The system of claim 11, wherein the at least two of the phases includes the computation phase and the data transfer phase, wherein the dependencies include a first dependency that is a dependency between data units and the completion time of the computation phase and a second dependency that is a dependency between the data units and the completion time of the data transfer phase. 13. The system of claim 12, wherein the balancer module is further configured to compute, based on said first dependency, a first number of data units, the reassignment of which from the first processor to the second processor renders the computation phase of the first processor equal to the computation phase of the second processor, to compute, based on said second dependency, a second number of data units, the reassignment of which from the first processor to the second processor renders a data transfer phase of the first processor equal to a data transfer phase of the second processor, and to select a lesser of the first number of data units and the second number of data units as the given number of data units. 14. The system of claim 9, wherein the balancer module is further configured to predict said dependencies based on completion times monitored for a plurality of iterations of the procedure using a time estimation model.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (3)
Hardwick Jonathan C.,GBX, Dynamic load balancing among processors in a parallel computer.
Brokenshire, Daniel Alan; Hofstee, Harm Peter; Minor, Barry L; Nutter, Mark Richard, Dynamically partitioning processing across a plurality of heterogeneous processors.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.