Abstract
Min-Min is a classical heuristic for scheduling tasks to heterogeneous computational resources, which has been applied either directly or as part of more sophisticated heuristics. The time complexity of the direct implementation of Min-Min is \(O(mn^2)\) for scheduling n tasks on m machines. This has motivated the use of simpler heuristics and parallel implementations of Min-Min for the sake of acceptable runtimes in large scenarios. Recently, we have proposed an efficient algorithm for computing Min-Min, whose time complexity is O(mn). In this work, we study mult-many core versions of this new algorithm. The experimental evaluation of our proposal shows important runtime reductions compared to the sequential version.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The time complexity is O(mn) for fixed numeric precision implementations.
- 2.
The real available free memory is 4.92 GB.
References
Baxter, S.: Modern gpu. http://nvlabs.github.io/moderngpu/. Accessed April 2015
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., Freund, R.F.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 61(6), 810–837 (2001)
Canabé, M., Nesmachnow, S.: Parallel implementations of the MinMin heterogeneous computing scheduler in GPU. In: V Latin American Symposium on High Performance Computing. HPCLatam (2012). www.clei.cl/cleiej/papers/v15i3p8.pdf
Diaz, C.O., Guzek, M., Pecero, J.E., Danoy, G., Bouvry, P., Khan, S.U.: Energy-aware fast scheduling heuristics in heterogeneous computing systems. In: Proceedings of the 2011 International Conference on High Performance Computing & Simulation (HPCS 2011), pp. 478–484 (2011)
Ezzatti, P., Pedemonte, M., Martín, A.: An efficient implementation of the min-min heuristic. Comput. Oper. Res. 40(11), 2670–2676 (2013)
Fernandez-Baca, D.: Allocating modules to processors in a distributed system. IEEE Trans. Softw. Eng. 15(11), 1427–1436 (1989)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Giersch, A., Robert, Y., Vivien, F.: Scheduling tasks sharing files on heterogeneous master-slave platforms. J. Syst. Archit. 52(2), 88–104 (2006)
Herf, M.: Radix tricks. http://stereopsis.com/radix.html. Accessed April 2015
Hildebrandt, P., Isbitz, H.: Radix exchange-an internal sorting method for digital computers. J. ACM 6(2), 156–163 (1959)
Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24(2), 280–289 (1977)
Knuth, D.E.: The Art of Computer Programming, Sorting and Searching, vol. 3, 2nd edn. Addison Wesley Longman Publishing Co., Inc., Redwood City (1998)
Luo, P., Lü, K., Shi, Z.: A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems. J. Parallel Distrib. Comput. 67(6), 695–714 (2007)
Mathworks: Multicore matlab. http://www.mathworks.com/discovery/multicore-matlab.html. Accessed April 2015
McCool, M.D., Robison, A.D., Reinders, J.: Structured Parallel Programming: Patterns for Efficient Computation. Morgan Kaufmann, Burlington (2012)
Haberman, N.: Parallel neighbor sort (or the glory of the induction principle). Technical report 2087, Computer Science Department, Carnegie Mellon University (1972)
Nvidia Corporation: CUDA C Programming Guide Version 5.5. Nvidia Corporation (2013)
Pinel, F., Dorronsoro, B., Pecero, J., Bouvry, P., Khan, S.: A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids. Cluster Comput. 16, 1–13 (2012)
Pinel, F., Dorronsoro, B., Bouvry, P.: Solving very large instances of the scheduling of independent tasks problem on the GPU. J. Parallel Distrib. Comput. 73(1), 101–110 (2013)
Ritchie, G., Levine, J.: A fast, effective local search for scheduling independent jobs in heterogeneous computing environments. In: PLANSIG 2003: Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group, pp. 178–183, December 2003
Tabak, E., Cambazoglu, B., Aykanat, C.: Improving the performance of independent task assignment heuristics minmin, maxmin and sufferage. IEEE Trans. Parallel Distrib. Syst. 25(5), 1244–1256 (2013)
Valiant, L.G.: Parallelism in comparison problems. SIAM J. Comput. 4(3), 348–355 (1975)
Wu, M.Y., Shu, W., Zhang, H.: Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems. In: Proceedings of the 9th Heterogeneous Computing Workshop, HCW 2000, pp. 375–385. IEEE Computer Society, Washington, DC (2000)
Xhafa, F., Abraham, A.: Computational models and heuristic methods for grid scheduling problems. Future Gener. Comput. Syst. 26(4), 608–621 (2010)
Xhafa, F., Alba, E., Dorronsoro, B., Duran, B.: Efficient batch job scheduling in grids using cellular memetic algorithms. J. Math. Model. Algorithms 7, 217–236 (2008)
Xhafa, F., Barolli, L., Durresi, A.: Batch mode scheduling in grid systems. Int. J. Web Grid Serv. 3(1), 19–37 (2007)
Xhafa, F., Carretero, J., Dorronsoro, B., Alba, E.: A TABU search algorithm for scheduling independent jobs in computational grids. Comput. Artif. Intell. 28(2), 237–250 (2009)
Acknowledgment
The authors acknowledge support from Programa de Desarrollo de las Ciencias Básicas, Uruguay, and Sistema Nacional de Investigadores, Uruguay.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Pedemonte, M., Ezzatti, P., Martín, Á. (2016). Accelerating the Min-Min Heuristic. In: Wyrzykowski, R., Deelman, E., Dongarra, J., Karczewski, K., Kitowski, J., Wiatr, K. (eds) Parallel Processing and Applied Mathematics. Lecture Notes in Computer Science(), vol 9574. Springer, Cham. https://doi.org/10.1007/978-3-319-32152-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-32152-3_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-32151-6
Online ISBN: 978-3-319-32152-3
eBook Packages: Computer ScienceComputer Science (R0)