Dynamic load balance in parallel merge sorting over homogeneous clusters
Material type:
ArticleSeries: ^p Datos electrónicos (1 archivo : 89 KB)Subject(s): Online resources: Summary: Sorting is one of the most usual and important operations carried out in a computer. The time required by the sequential sorting algorithms is an important problem when working with large sized sequences. As solution, we can consider parallelization and attaining a near optimal performance achieving a balance in the work to be done by processors. Notice that the work does not depend only on the amount of data but also on the sequence disordering, and on the relative computer power of processors. This paper develops a technique of redistributing dynamically the data load from the prediction of work to be carried out by each processor, balancing the load among the different processes. The method is proved to reach the theoretical optimum for the parallel algorithm performance. © 2005 IEEE. -- Keywords: Algorithm Parallelization; Dynamic Redistribution; Load Balancing; Performance Prediction; Sorting.
| Item type | Home library | Collection | Call number | URL | Status | Date due | Barcode | |
|---|---|---|---|---|---|---|---|---|
Capítulo de libro
|
Biblioteca de la Facultad de Informática | Biblioteca digital | A0068 (Browse shelf(Opens below)) | Link to resource | No corresponde |
Formato de archivo: PDF. -- Este documento es producción intelectual de la Facultad de Informática-UNLP (Colección BIPA / Biblioteca.) -- Disponible también en línea (Cons. 19/12/2008)
Sorting is one of the most usual and important operations carried out in a computer. The time required by the sequential sorting algorithms is an important problem when working with large sized sequences. As solution, we can consider parallelization and attaining a near optimal performance achieving a balance in the work to be done by processors. Notice that the work does not depend only on the amount of data but also on the sequence disordering, and on the relative computer power of processors. This paper develops a technique of redistributing dynamically the data load from the prediction of work to be carried out by each processor, balancing the load among the different processes. The method is proved to reach the theoretical optimum for the parallel algorithm performance. © 2005 IEEE. -- Keywords: Algorithm Parallelization; Dynamic Redistribution; Load Balancing; Performance Prediction; Sorting.
(2005) Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA, vol. 2, pp. 219-222.