×

zbMATH — the first resource for mathematics

A family of scheduling algorithms for hybrid parallel platforms. (English) Zbl 1387.68043

MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W25 Approximation algorithms
Software:
OmpSs; StarPU
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agullo, E.; Augonnet, C.; Dongarra, J.; Faverge, M.; Ltaief, H.; Thibault, S.; Tomov, S., QR factorization on a multicore node enhanced with multiple GPU accelerators, IEEE Int. Parallel and Distributed Processing Symposium (IPDPS), (2011)
[2] Augonnet, C.; Thibault, S.; Namyst, R.; Wacrenier, P. A., Starpu: A unified platform for task scheduling on heterogeneous multicore architectures, Concurrency and Computation: Practice and Experience, 23, 2, 187-198, (2011)
[3] Blazewicz, J.; Ecker, K.; Pesch, E.; Schmidt, G.; Weglarz, J., International Handbooks on Information Systems, Handbook on scheduling: from theory to applications, (2007), Springer
[4] Bleuse, R.; Kedad-Sidhoum, S.; Monna, F.; Mouni, G.; Trystram, D., Scheduling independent tasks on multi-cores with GPU accelerators, Concurrency and Computation: Practice and Experience, 27, 6, 1625-1638, (2015)
[5] V. Bonifaci and A. Wiese, Scheduling unrelated machines of few different types, CoRR abs/1205.0974 (2012).
[6] Boukerche, A.; Correa, J. M.; Melo, A.; Jacobi, R. P., A hardware accelerator for the fast retrieval of dialign biological sequence alignments in linear space, IEEE Trans. Comput., 59, 808-821, (2010) · Zbl 1366.92004
[7] Bueno, J.; Planas, J.; Duran, A.; Badia, R. M.; Martorell, X.; Ayguadé, E.; Labarta, J., Productive programming of gpu clusters with ompss, IPDPS, 557-568, (2012), IEEE Computer Society
[8] Chen, L.; Ye, D. S.; Zhang, G. C., Online scheduling of mixed CPU-GPU jobs, Int. J. Found. Comput. Sci., 25, 6, 745-762, (2014) · Zbl 1304.68023
[9] Friesen, D. K., Tighter bounds for lpt scheduling on uniform processors, SIAM J. Comput., 16, 3, 554-560, (1987) · Zbl 0654.68033
[10] Garey, M. R.; Grahams, R. L., Bounds for multiprocessor scheduling with resource constraints, SIAM J. Comput., 4, 187-200, (1975) · Zbl 0333.68041
[11] Gautier, T.; Ferreira, L.; Joao, V.; Maillard, N.; Raffin, B., Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures, Proc. of IEEE Int. Parallel and Distributed Processing Symposium (IPDPS), (2013)
[12] J. C. Gehrke, K. Jansen, S. E. J. Kraft and J. Schikowski, A PTAS for Scheduling Unrelated Machines of Few Different Types Technical report, Bericht Nr. 1506 ISSN 2192-6247 (2015). · Zbl 1442.90073
[13] Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17, 2, 416-429, (1969) · Zbl 0188.23101
[14] Hochbaum, D. S.; Shmoys, D. B., Using dual approximation algorithms for scheduling problems theoretical and practical results, J. ACM, 34, 1, 144-162, (1987)
[15] Hochbaum, D. S.; Shmoys, D. B., A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach, SIAM J. Comput., 17, 3, 539-551, (1988) · Zbl 0647.68040
[16] Imreh, C., Scheduling problems on two sets of identical machines, Computing, 70, 277-294, (2003) · Zbl 1033.90041
[17] Lee, V. W.; Kim, C.; Chhugani, J.; Deisher, M.; Kim, D.; Nguyen, A. D.; Satish, N.; Smelyanskiy, M.; Chennupaty, S.; Hammarlund, P.; Singhal, R.; Dubey, P., Debunking the 100x gpu vs. cpu myth: an evaluation of throughput computing on cpu and gpu, ACM SIGARCH Computer Architecture News ISCA’10, 38, 451-460, (2010)
[18] Lenstra, J. K.; Shmoys, D. B.; Tardos, E., Approximation algorithms for scheduling unrelated parallel machines, Math. Program., 46, 259-271, (1990) · Zbl 0715.90063
[19] Raravi, G.; Nélis, V., A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors, Real-Time Systems Symposium (RTSS), 117-126, (2012)
[20] Phillips, J. C.; Stone, J. E.; Schulten, K., Adapting a message-driven parallel application to gpu-accelerated clusters, High Performance Computing, Networking, Storage and Analysis, 1-9, (2008)
[21] 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)
[22] Shchepin, E. V.; Vakhania, N., An optimal rounding gives a better approximation for scheduling unrelated machines, Oper. Res. Lett., 33, 127-133, (2004) · Zbl 1099.90024
[23] Shmoys, D. B.; Tardos, E., An approximation algorithm for the generalized assignment problem, Math. Program., 62, 461-474, (1993) · Zbl 0804.90077
[24] Song, F.; Tomov, S.; Dongarra, J., Enabling and scaling matrix computations on heterogeneous multi-core and multi-gpu systems, 26th ACM International Conference on Supercomputing (ICS), (2012)
[25] Topcuoglu, H.; Hariri, S.; Wu, M. Y., Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Trans. Parallel Distrib. Syst., 13, 3, 260-274, (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.