Efficient Implementations of the Min-Min Heuristic for HCSP on GPU

• Rafael F. Schmid UFMS
• Edson N. Cáceres UFMS

DOI: https://doi.org/10.5753/etc.2018.3156

Abstract

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.

References

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.