Implementações Eficientes da Heurística Min-Min para o HCSP em GPU
Resumo
Min-min heuristic is one of the most indicated algorithm to solve HCSP, when we are looking for performance. A previous result presented an efficient implementation to this problem with assymptotic complexity O(t log(t)m). In this work, we implement this problem with linear complexity. Our implementation is competitive with the previous results.
Referências
Braun, T. D., Siegel, H. J., Beck, N., Bölöni, L. L., Maheswaran, M., Reuther, A. I., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D., and Freund, R. F. (2001). A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810 – 837.
Ezzatti, P., Pedemonte, M., and Martín, Á. (2013). An efficient implementation of the min-min heuristic. Computers & Operations Research, 40(11):2670–2676.
Nesmachnow, S. and Canabé, M. (2011). Gpu implementations of scheduling heuristics for heterogeneous computing environments. In XVII Congreso Argentino de Ciencias de la Computación.
Pedemonte, M., Ezzatti, P., and Martín, Á. (2016). Accelerating the min-min heuristic. In Parallel Processing and Applied Mathematics, pages 101–110. Springer.
Schmid, R., Pisani, F., Borin, E., and Cáceres, E. (2016). An evaluation of segmented sorting strategies on gpus. In IEEE 18th International Conference on High Performance Computing and Communications (HPCC), pages 1123–1130. IEEE.
Wu, M.-Y., Shu, W., and Zhang, H. (2000). Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems. In Heterogeneous Computing Workshop, 2000.(HCW 2000) Proceedings. 9th, pages 375–385. IEEE.
Ezzatti, P., Pedemonte, M., and Martín, Á. (2013). An efficient implementation of the min-min heuristic. Computers & Operations Research, 40(11):2670–2676.
Nesmachnow, S. and Canabé, M. (2011). Gpu implementations of scheduling heuristics for heterogeneous computing environments. In XVII Congreso Argentino de Ciencias de la Computación.
Pedemonte, M., Ezzatti, P., and Martín, Á. (2016). Accelerating the min-min heuristic. In Parallel Processing and Applied Mathematics, pages 101–110. Springer.
Schmid, R., Pisani, F., Borin, E., and Cáceres, E. (2016). An evaluation of segmented sorting strategies on gpus. In IEEE 18th International Conference on High Performance Computing and Communications (HPCC), pages 1123–1130. IEEE.
Wu, M.-Y., Shu, W., and Zhang, H. (2000). Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems. In Heterogeneous Computing Workshop, 2000.(HCW 2000) Proceedings. 9th, pages 375–385. IEEE.
Publicado
26/07/2018
Como Citar
SCHMID, Rafael F.; CÁCERES, Edson N..
Implementações Eficientes da Heurística Min-Min para o HCSP em GPU. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 81-84.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3156.
