Abstract
This paper concerns the problem of finding efficient task allocation algorithms in mesh structures. An allocation algorithm, called Window-Based-Best-Fit with Validated-Submeshes (WBBFVS), has been created. The core of this algorithm lays in the way of finding maximal submeshes what is an important part of the task allocation algorithms based on the stack approach. The new way of finding maximal submeshes avoids post-checking submeshes’ redundancy thanks to the proposed initial validation. The elimination of redundancy may increase the speed of the algorithms’ performance. The three considered algorithms have been evaluated on the basis of the results of simulation experiments made using the designed and implemented experimentation system. The obtained results of investigation show that the WBBFVS algorithm seems to be very promising.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Yoo, B.S., Das, C.R.: A fast and efficient processor allocation scheme for mesh-connected multicomputers. IEEE Transactions on Computers 51(1), 46–60 (2002)
Linkowski, T., Koszalka, L., Kasprzak, A.: Window-list-based best fit task allocation in mesh. In: Information Systems Architecture and Technology: System Analysis in Decision Aided Problems, OWPWr, pp. 379–388 (2009)
Sharma, D., Pradhan, D.K.: Submesh allocation in mesh multicomputers using busy-list: A best-fit approach with complete recognition capability. Journal of Parallel and Distributed Computing 36, 106–118 (1996)
Kaminski, R.T., Koszalka, L., Pozniak-Koszalka, I., Kasprzak, A.: Evaluation and comparison of task allocation algorithms for mesh networks. In: Proc. 9th International Conference on Networks, pp. 104–108. IEEE Computer Society Press (2010)
Koszalka, L.: Static and dynamic allocation algorithms in mesh structured networks. In: Madria, S.K., Claypool, K.T., Kannan, R., Uppuluri, P., Gore, M.M. (eds.) ICDCIT 2006. LNCS, vol. 4317, pp. 89–101. Springer, Heidelberg (2006)
Papadimitriou, C.: Calculation Complexity. WNT, Warsaw (2002)
Seong-Moo, Y., Hee, Y.Y., Hyun, S.C.: Fault-free maximal submeshes in faulty torus-connected multicomputers. Informatica 28(3), 289–296 (2004)
Bani-Mohammad, S., Ababneh, I., Hamdan, M.: Comparative performance evaluation of non-contiguous allocation algorithms in 2D mesh-connected multicomputers. In: CIT, pp. 2933–2939. IEEE Computer Society (2010)
Zydek, D., Selvaraj, H., Koszalka, L., Pozniak-Koszalka, I.: Evaluation scheme for NoC-based CMP with integrated processor management system. International Journal of Electronics and Telecommunications 56(2), 157–167 (2010)
Kmiecik, W., Wojcikowski, M., Koszalka, L., Kasprzak, A.: Task allocation in mesh connected processors with local search meta-heuristic algorithms. In: Nguyen, N.T., Le, M.T., Świątek, J. (eds.) Intelligent Information and Database Systems. LNCS (LNAI), vol. 5991, pp. 215–224. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Jarecki, R.J., Poźniak-Koszalka, I., Koszalka, L., Kasprzak, A. (2014). An Approach of Finding Maximal Submeshes for Task Allocation Algorithms in Mesh Structures. In: Nguyen, N.T., Attachoo, B., Trawiński, B., Somboonviwat, K. (eds) Intelligent Information and Database Systems. ACIIDS 2014. Lecture Notes in Computer Science(), vol 8397. Springer, Cham. https://doi.org/10.1007/978-3-319-05476-6_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-05476-6_34
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05475-9
Online ISBN: 978-3-319-05476-6
eBook Packages: Computer ScienceComputer Science (R0)