We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
An Efficient Restoration Method for the Faint Dot Matrix Images

Ao Zhu Peng Cao
Random Articles
Reseach Article

Comparative Evaluation of Request-Partitioning-based Processor Allocation Strategies in 2D Mesh-based Multicomputers

by Sulieman Bani-Ahmad
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 26 - Number 7
Year of Publication: 2011
Authors: Sulieman Bani-Ahmad
10.5120/3113-4275

Sulieman Bani-Ahmad . Comparative Evaluation of Request-Partitioning-based Processor Allocation Strategies in 2D Mesh-based Multicomputers. International Journal of Computer Applications. 26, 7 ( July 2011), 40-48. DOI=10.5120/3113-4275

@article{ 10.5120/3113-4275,
author = { Sulieman Bani-Ahmad },
title = { Comparative Evaluation of Request-Partitioning-based Processor Allocation Strategies in 2D Mesh-based Multicomputers },
journal = { International Journal of Computer Applications },
issue_date = { July 2011 },
volume = { 26 },
number = { 7 },
month = { July },
year = { 2011 },
issn = { 0975-8887 },
pages = { 40-48 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume26/number7/3113-4275/ },
doi = { 10.5120/3113-4275 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:12:12.883616+05:30
%A Sulieman Bani-Ahmad
%T Comparative Evaluation of Request-Partitioning-based Processor Allocation Strategies in 2D Mesh-based Multicomputers
%J International Journal of Computer Applications
%@ 0975-8887
%V 26
%N 7
%P 40-48
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Request-Partitioning-Based (RPB) allocation schemes remedy the problem of fragmentation by allowing parallel requests to be allocated non-contiguously in case contiguous allocation fails. Two RPB allocation schemes are proposed in literature; the Adaptive Non-Contiguous Allocation (ANCA) and the Bounded-Gradual-Partitioning (BGP) allocation. In ANCA, the frame requested by the parallel job is subdivided into two subframes of equal sizes at the longest dimension of the request. In BGP, requests are gradually partitioned into one large and another small subframe of multicomputers. In this paper, ANCA and BGP based allocation strategies are comparatively evaluated through exhaustive simulation-based experiments. Our experimental results also showed that the ANCA scheme can sustain higher system and communication loads compared to BGP in terms of major system performance metrics. We also observed that, in the BGP approach, increasing the partitioning bound value can slightly improve the performance of the parallel system. Comparatively, increasing the partitioning bound in the ANCA approach could significantly improve the performance of the parallel system.

References
  1. Ababneh, I. (2006), “An efficient free-list submesh allocation scheme for two-dimensional mesh-connected multicomputers”, Journal of Systems and Software, vol. 79, no. 8, Elsevier Science Inc., New York, NY, USA, August 2006, pp. 1168-1179.
  2. Ababneh, I. and Davis, J. (1995), “Program-based static allocation policies for highly parallel computers”, Proc. IPCCC 95, IEEE Computer Society Press, Scottsdale, AZ, USA, 28-31 Mar 1995, pp. 61-68.
  3. S. Bani-Ahmad. “Bounded Gradual-Request-Partitioning-Based Allocation Strategies in 2D-Mesh Multicomputers”. International Journal of Digital Content Technology and its Applications (JDCTA). Volume 5, Number 1, January 2011.
  4. Bani-Ahmad, S. (2010b), “Submesh Allocation in 2D-Mesh Multicomputer: Partitioning at the Longest Dimension of Requests”. Proceedings of the Fourth International Conference on Advanced Engineering Computing and Applications in Sciences (ADVCOMP 2010). October 25-30, 2010, Florence, Italy.
  5. S. Bani-Ahmad. “Processor Allocation with Reduced Internal and External Fragmentation in 2D Mesh-based Multicomputers”. Journal of Applied Sciences. Volume 11, Issue: 6, 2011, pp 943-952.
  6. Bani-Mohammad, S.; Ould-Khaoua , M.; Ababneh, I., and Machenzie, L. (2006), “Non-contiguous Processor Allocation Strategy for 2D Mesh Connected Multicomputers Based on Sub-meshes Available for Allocation”, Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS’06), vol. 2, IEEE Computer Society Press, USA, 2006, pp. 41-48.
  7. Bani-Mohammad, S.; Ould-Khaoua, M.; Ababneh, I.; and Machenzie, L. (2007), “A Fast and Efficient Processor Allocation Strategy which Combines a Contiguous and Non-contiguous Processor Allocation Algorithms”, Technical Report; TR-2007-229, DCS Technical Report Series, Department of Computing Science, University of Glasgow, January 2007.
  8. Chang, C. Y. and Mohapatra, P. (1998), “Performance improvement of allocation schemes for mesh-connected computers”, Journal of Parallel and Distributed Computing, vol. 52, no. 1, Academic Press, Inc. Orlando, FL, USA, July 1998, pp. 40-68.
  9. Chiu, G. M. and Chen, S.K. (1999), “An efficient submesh allocation scheme for two-dimensional meshes with little overhead”, IEEE Transactions on Parallel & Distributed Systems, vol. 10, no. 5, IEEE Press, Piscataway, NJ, USA, May 1999, pp. 471-486.
  10. Chuang, P. J. and Tzeng, N. F. (1994), Allocating precise submesh in mesh-connected systems, IEEE Transactions Parallel and Distributed Systems (Feb. 1994), 211217.
  11. Ding, J. and Bhuyan, L. N. (1993), An adaptive submesh allocation strategy for two-dimensional mesh connected systems, Proc. Int. Conf. Parallel Process. II (Aug. 1993), 193200.
  12. Krueger, P.; Lai, T.; and Radiya, V. A. (1994), “Job scheduling is more important than processor allocation for hypercube computers”, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 5, IEEE Press, Piscataway, NJ, USA, May 1994, pp. 488-497.
  13. Kumar, V.; Grama, A.; Gupta, A.; and Karypis, G. (2003), Introduction To Parallel Computing, The Benjamin/Cummings publishing Company, Inc., Redwood City, California, 2003.
  14. Li, K. and Cheng, K. H. (1991), “A Two-Dimensional Buddy System for Dynamic Resource Allocation in a Partitionable Mesh Connected System”, Journal of Parallel and Distributed Computing, vol. 12, no. 1, Elsevier Science, CA, USA, May 1991, pp. 79-83.
  15. Lin, X.; Mckinly, P.; and Esfahanina, A. (1993). “Adaptive Multicast wormhole Routing in 2D-mesh multicomputers”. Proceeding of Parallel Architecture and Language conference (PARLE), pp 228-241.
  16. Liu, T.; W. Huang, K.; Lombardi, F. and Bhuyan, L. N. (1995), A submesh allocation scheme for mesh-connected multiprocessor systems, Proc. Int. Conf. Parallel Process. II (Aug. 1995), 159163.
  17. Lo, V.; Windisch, K.; Liu, W.; and Nitzberg, B. (1997), “Non-contiguous processor allocation algorithms for mesh-connected multicomputers”, IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 7, IEEE Press, Piscataway, NJ, USA, July 1997, pp. 712-726.
  18. Min, D. and Mutka, M. W. (1995), Effect of job interactions due to scattered processor allocations in 2-D wormhole networks, in ``Proc. of Int. Conf. on Parallel and Distributed Computing Systems,'' (Sept. 1995), pp. 262267.
  19. Moore, S. Q. and Ni, L. M. (1996), The effect of network contention on processor allocation strategies, in ``Proc. of the 1996 International Parallel Processing Symposium,'' (April 1996).
  20. Ni, L. M. and McKinley, P. K. (1993), “A Survey of Wormhole Routing Techniques in Direct Networks”. Computer 26, 2 (Feb. 1993), pp 62-76. DOI= http://dx.doi.org/10.1109/2.191995.
  21. Niedermeier, R.; K. Reinhardt; and P. Sanders (1997). Towards optimal locality in mesh indexings. In Proc. 11th Intl Symp on Fund. Computation Theory, volume 1279 of LNCS, pages 364-375, 1997.
  22. ProcSimity V4.3 User’s Manual, University of Oregon, 1997.
  23. Seo, K. H. (2005), “Fragmentation-Efficient Node Allocation Algorithm in 2D Mesh-Connected Systems”, Proceedings of the 8th International Symposium on Parallel Architecture, Algorithms and Networks (ISPAN’05), IEEE Computer Society Press, Washington, DC, USA, 7-9 December, 2005, pp. 318-323.
  24. Srinivasan, T.; Seshadri, J.; Chandrasekhar, A.; and Jonathan, J. (2004), “A Minimal Fragmentation Algorithm for Task Allocation in Mesh-Connected Multicomputers”, Proceedings of IEEE International Conference on Advances in Intelligent Systems – Theory and Applications – AISTA 2004 in conjunction with IEEE Computer Society, ISBN 2-9599-7768-8, IEEE Press, Luxembourg, Western Europe, 15-18 Nov 2004.
  25. Suzaki, K.; Tanuma, H.; Hirano, S.; Ichisugi, Y.; Connelly, C.; and Tsukamoto, M. (1996), “Multi-tasking Method on Parallel Computers which Combines a Contiguous and Non-contiguous Processor Partitioning Algorithm”, Proceedings of the Third International Workshop on Applied Parallel Computing, Industrial Computation and Optimization, Springer-Verlag, UK, 1996, pp. 641-650.
  26. Windisch, K.; Miller, J. V.; and Lo, V. (1995), “ProcSimity: an experimental tool for processor allocation and scheduling in highly parallel systems”, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), IEEE Computer Society Press, Washington, USA, 6-9 Feb 1995, pp. 414-421.
  27. Yoo , B. S. and Das, C. R. (2002), “A Fast and Efficient Processor Allocation Scheme for Mesh-Connected Multicomputers”, IEEE Transactions on Parallel & Distributed Systems, vol. 51, no. 1, IEEE Computer Society, Washington, USA, January 2002, pp. 46-60.
  28. Yoo, B. S.; Das, C. R.; and Yu, C (1995), Yu, Processor management techniques for mesh-connected multiprocessors, Proc. Int. Conf. Parallel Process. II (Aug. 1995), 105112.
  29. Yu, C.; Das, C. R. (1994), “Limit allocation: An efficient processor management scheme for hypercubes”, International Conference on Parallel Processing (1994), DOI: 10.1109/ICPP.1994.124 .
  30. Zhu, Y. (1992), “Efficient processor allocation strategies for mesh-connected parallel computers”, Journal of Parallel and Distributed Computing, vol. 16, no. 4, Elsevier, San Diego, CA, 1992, pp. 328-337.
Index Terms

Computer Science
Information Sciences

Keywords

Non-contiguous allocation 2D-Mesh Multicomputers Request-Partitioning ANCA BGP

Powered by PhDFocusTM