[Home ]   [ فارسی ]  
Main Menu
Mission ::
Research Groups::
Contact Us::
Published Papers::
:: The impact of scheduling gangs with the shortest execution time on gang scheduling performance ::
The Impact of Scheduling Gangs with the Shortest
Execution Time on Gang Scheduling Performance
Maryam Sadat Mastoori
Iran University of Science and Technology
School of Electrical Engineering
Tehran, Iran
Hadi Shahriar Shahhoseini
Iran University of Science and Technology
School of Electrical Engineering
Tehran, Iran
PDF     │   Abstract   │  Keywords   │  References   │  Cite This 

Gang scheduling is an efficient scheduling approach that combines elements of space-sharing and time-sharing. The FillMatrix is the fourth phase in GS and plays the main role in accelerating the scheduling of more gangs. In this paper, a novel method is proposed to fill the matrix by a gang that has the smallest execution time (SET). By this method, this gang will be executed faster, and therefore more space of matrix will be freed to scheduling more larger gangs. The performance of the proposed algorithm is evaluated under different workload variability cases. The simulation results reveal the achievement improvement of SET-FillMatrix, especially in lighten workloads.

Keywords: Job scheduling, Parallel computing, Gang scheduling, Ousterhout Matrix, Simulation


[1] R.Tyagi, S.K. Gupta, "A Survey on Scheduling Algorithms for Parallel and Distributed Systems," In: Mishra A., Basu A., Tyagi V. (eds) Silicon Photonics & High Performance Computing. Advances in Intelligent Systems and Computing, vol 718. Springer, Singapore, 2018. https://doi.org/10.1007/978-981-10-7656-5_7     Google Scholar

[2] M.M. Bassiri, et.al. "A new approach in on-line task scheduling for reconfigurable computing systems," 2010  Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors, pp. 321-324. doi: 10.1109/ASAP.2010.5540975.   Google Scholar

[3] M.M. Bassiri, et.al., "On-line HW/SW partitioning and co-scheduling in reconfigurable computing systems," 2009 International Conference on Signal Processing Systems, ICSPS 2009, pp. 277-281. doi: 10.1109/ICCSIT.2009.5234664.    Google Scholar

[4] N. Nosrati,  et.al., "G-CARA: A global congestion-aware routing algorithm for traffic management in 3d networks-on-chip," 25th Iranian Conference on Electrical Engineering (ICEE2017), pp. 2188-2193, May 2017. doi: 10.1109/IranianCEE.2017.7985425.   Google Scholar

[5] H. J. Rad, et.al., "A new adaptive power optimization scheme for target tracking wireless sensor networks," Proceedings of 2009 IEEE Symposium on Industrial Electronics & Applications, Vol. 1, pp. 307-312, 2009.  doi: 10.1109/ISIEA.2009.5356452.    Google Scholar

[6] H.S. Shahhoseini, A. Naseri, and M. Naderi, "A new matrix method for pulse train identification," IEEE 11th  Mediterranean Electrotechnical Conference, pp. 183-187. Cairo, Egypt, 2002.    Google Scholar

[7] A. Omidvar, et.al., "Intelligent IP traffic matrix estimation by neural network and genetic algorithm," IEEE 7th nternational Symposium on Intelligent Signal Processing, pp. 1-6. IEEE, 2011. doi: 10.1109/WISP.2011.6051689.    Google Scholar

[8] F. Petrini, W. Feng, "Time-Sharing Parallel Jobs in the Presence of Multiple Resource Requirements," In: Feitelson D.G., Rudolph L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2000. Lecture Notes in Computer Science, vol 1911. Springer, Berlin, Heidelberg, 2000. https://doi.org/10.1007/3-540-39997-6_8.    Google Scholar

[9] Z. C. Papazachos and H. D. Karatza, "Performance evaluation of gang scheduling in a two-cluster system with migrations," 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome,  pp. 1-8, 2009. doi: 10.1109/IPDPS.2009.5161172.    Google Scholar

[10] C. Du, X. Sun and M. Wu, "Dynamic Scheduling with Process Migration," Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGrid '07), Rio De Janeiro, 2007, pp. 92-99. doi: 10.1109/CCGRID.2007.46.    Google Scholar

[11] A. Reuther, C. Byun, W. Arcand, D. Bestor, B. Bergeron, M. Hubbell, M. Jones, P. Michaleas, A. Prout, A. Rosa, J. Kepner, "Scalable system scheduling for HPC and big data," Journal of Parallel and Distributed Computing, Vol. 111, pp. 76-92, 2018. https://doi.org/10.1016/j.jpdc.2017.06.009.    Google Scholar

[12] G. L. Stavrinides and H. D. Karatza, "Scheduling techniques for complex workloads in distributed systems," In Proceedings of the 2nd International Conference on Future Networks and Distributed Systems (ICFNDS '18), ACM, New York, NY, USA, Article 34, 2018. https://doi.org/10.1145/3231053.3231087.    Google Scholar

[13] M.M. Bassiri, H.S. Shahhoseini, "Configuration reusing in on-line task scheduling for reconfigurable computing systems," Journal of Computer Science and Technology, 26(3), pp. 463-473, 2011. https://doi.org/10.1007/s11390-011-1147-2   Google Scholar

[14] M. Mollajafari, et.al., "An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph," Applied Intelligence, 45, no. 3 pp. 695-712, 2016.  https://doi.org/10.1007/s10489-016-0782-2<    Google Scholar

[15] M.M. Bassiri, H.S. Shahhoseini, "Mitigating reconfiguration overhead in on-line task scheduling for reconfigurable computing systems," 2010 International Conference on Computer Engineering and Technology (ICCET 2010),  pp. V4397-V4402. doi: 10.1109/ICCET.2010.5485509.    Google Scholar

[16] H. Naderi, et.al., "Evaluation MCDM multi-disjoint paths selection algorithms using fuzzy-copeland ranking method," International Journal of Communication Networks and Information Security, Vol. 5, No 1,  pp59-67,  April 2013.    Google Scholar

[17] M. Shemshaki, et.al., "Energy efficient clustering algorithm with multi-hop transmission," IEEE International Conference on Scalable Computing and Communications; 8th  International Conference on Embedded Computing, Dalian, China, pp. 459-462, Sept 2009. doi: 10.1109/EmbeddedCom-ScalCom.2009.88.   Google Scholar

[18] M. Saeed, and H.S. Shahhoseini, "APPMA-An anti-phishing protocol with mutual authentication," Proceedings of the IEEE Symposium on Computers and Communications, pp. 308-313, 2010. doi: 10.1109/ISCC.2010.5546794.   Google Scholar

[19] H.D. Karatza, "Scheduling Gangs in a Distributed System," International Journal of Simulation, Vol. 7, pp. 15-22, 2006.    Google Scholar

[20] H.D. Karatza, "The Impact of Critical Sporadic Jobs on Gang Scheduling Performance in  Distributed Systems," simulation, 84(2–3), 89–102, 2008. https://doi.org/10.1177/0037549708091640.    Google Scholar

[21] Z.C. Papazachos and H.D. Karatza, "Performance evaluation of gang scheduling in a two-cluster system with migrations," 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome, pp. 1-8, 2009. doi: 10.1109/IPDPS.2009.5161172.    Google Scholar

[22] Z.C. Papazachos, H.D. Karatza, "Gang scheduling in multi-core clusters implementing migrations," Future Generation Computer Systems, Vol. 27, pp. 1153-1165, 2011. https://doi.org/10.1016/j.future.2011.02.010    Google Scholar

[23] S.S. Priya, and W.A. Banu, "Fuzzy Resource Pre-processing and Compress and Join Gang Polling Evaluation Scheduling in Cloud Computing," International Journal of Intelligent Engineering and Systems. Vol. 10, pp. 371-380, 2017. doi: 10.22266/ijies2017.0630.42.    Google Scholar

[24] H.D. Karatza, "Performance of gang scheduling strategies in a parallel system," Simulation Modelling Practice and Theory, Vol. 17, pp. 430–441, 2009. https://doi.org/10.1016/j.simpat.2008.10.001    Google Scholar

[25] G.L. Stavrinides and H.D. Karatza, "Scheduling Different Types of Gang Jobs in Distributed Systems," 2019 International Conference on Computer, Information and Telecommunication Systems (CITS), Beijing, China, 2019, pp. 1-5. doi: 10.1109/CITS.2019.8862091.    Google Scholar

[26] F.A.B. Silva, E.P. Lopes, E.P.L. Aude, F. Mendes, J.T.C. Silveira, H. Serdeira, M. Martins, and W. Cirne, "Response time analysis of gang scheduling for real-time systems," Proceedings of the 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS02), San Diego, CA, pp. 297-301, 2002.    Google Scholar

[27] Y. Zhang, H. Franke, J. E. Moreira, and A. Sivasubramaniam, "Improving parallel job scheduling by combining gang scheduling and backfilling techniques," Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS2000, Cancun, pp. 133-142, 2000. doi: 10.1109/IPDPS.2000.845975.    Google Scholar

[28] Y. Wiseman, DG. Feitelson, "Paired gang scheduling," IEEE Trans Parallel Distributed System, 14:581–592,2003. doi: 10.1109/TPDS.2003.1206505.    Google Scholar

[29] S. Setia, "Trace-driven analysis of migration-based gang scheduling policies for parallel computers," Proceedings of Int Conf on Parallel Process, pp 489–492, 1997. doi: 10.1109/ICPP.1997.622685.     Google Scholar

[30] Y. Zhang, H. Frank, J. Moreira, and A. Sivasubramaniam, "An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration," IEEE Transactions on Parallel and Distributed Systems, vol. 14, pp. 236-247, 2003. doi: 10.1109/TPDS.2003.1189582.    Google Scholar

[31] Z. Papazachos, and H. Karatza, "Performance Evaluation of Bag of Gang Scheduling in a Heterogeneous Distributed System," Journal of Systems and Software, Vol. 83, pp. 1346-1354, 2010. https://doi.org/10.1016/j.jss.2010.01.009.    Google Scholar

[32] H. D. Karatza, "Gang scheduling performance under different distributions of gang size," Scalable Computing: Practice and Experience, 4(4):433–449, 2001.    Google Scholar

[33] H. Amir and H.S. Shahhoseini, "Improving CompactMatrix phase in gang scheduling by changing transference condition and utilizing exchange," The Journal of Supercomputing, Vol. 66, no. 3, pp. 1707-1728, 2013. https://doi.org/10.1007/s11227-013-0971-2.    Google Scholar

[34] H.S.Shahhoseini, M. Naderi, R. Buyya, "Shared memory multistage clustering structure, an efficient structure for massively parallel processing systems," Proceedings of the 4th IEEE International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, Vol. 1, pp. 22-27, 2000. doi: 10.1109/HPC.2000.846510.    Google Scholar

[35] Y. Zhang, H. Franke, J. Moreira, A. Sivasubramaniam, "The impact of migration on parallel job scheduling for distributed systems," Proc Europar, pp 242–251, 2000. https://doi.org/10.1007/3-540-44520-X_33.    Google Scholar

[36] G.L. Stavrinides, H.D. Karatza, “Scheduling Data-Intensive Workloads in Large-Scale Distributed Systems: Trends and Challenges,” Kołodziej J., Pop F., Dobre C. (eds) Modeling and Simulation in HPC and Cloud Systems. Studies in Big Data, vol. 36. Springer, Cham, 2018. https://doi.org/10.1007/978-3-319-73767-6_2.     Google Scholar


Cite this paper as:
M.S. Mastoori and H.S. Shahhoseini, "The Impact of Scheduling Gangs with the Shortest Execution Time on Gang Scheduling Performance," 20th International Symposium on Computer Architecture and Digital Systems (CADS 2020), Rasht, Iran, 2020.
View: 5444 Time(s)   |   Print: 4907 Time(s)   |   Email: 0 Time(s)   |   0 Comment(s)
All Rights reserved
Persian site map - English site map - Created in 0.09 seconds with 45 queries by YEKTAWEB 4657