Abstract

We propose and evaluate a new processor allocation strategy in two-dimensional Multicomputers. The proposed strategy is comparatively evaluated against a set of well-known allocation strategies from the literature, namely; the 2D buddy System (Juang et al., 1997), the Multiple Buddy System and the Paging non-contiguous processor allocation strategies. Our experimental results show that the proposed allocation strategy has solved a number of flaws and drawbacks that have been observed in previously proposed strategies. Further, we observed that our proposed allocation strategy is scalable. We refer to the newly proposed strategy by the “Flexible 2D Buddy System” or F2DBS for short. In our experimental results, we also demonstrated that the F2DBS strategy is more flexible and applies to any 2D mesh of any shape and orientation.

Keywords:

Multicomputers, processor allocation, 2D buddy system , 2-D mesh , F2DBS,

References

1. Bani-Ahmad, S., 2011a. Bounded gradual-request-partitioning-based allocation strategies in 2D-mesh multicomputers. Int. J. Digital Content Technol. Appl., 5(1).
   
2. Bani-Ahmad, S., 2011b. Processor allocation with reduced internal and external fragmentation in 2D Mesh-based multicomputers. J. Appl. Sci., 11(6): 943-952.
   CrossRef    Direct Link
3. Bani-Ahmad, S., 2013. Submesh allocation in 2D-Mesh multicomputers: Partitioning at the longest dimension of requests. Int. Arab J. Inf. Techn., 10(3): 245.
   
4. Bani-Mohammad, S., M. Ould-Khaoua and I. Ababneh, 2007. A new processor allocation strategy with a high degree of contiguity in mesh-connected multicomputers. Simul. Model. Pract. Th., 15(4): 465-480.
   
5. Bunde, D.P., V.J. Leung and J. Mache, 2004. Communication patterns and allocation strategies. Proceeding of the 18th International Parallel and Distributed Processing Symposium.
   
6. De Rose, C.A.F., H.U. Heiss and B. Linnert, 2007. Distributed dynamic processor allocation for multicomputers. Parall. Comput., 33(3): 145-158.
   
7. Dhotre, I.A., 2009. Operating Systems. 7th Edn., Technical Publication Pune, India.
   PMid:19695102 PMCid:PMC2743715    
8. El-Rewini, H. and M. Abd-El-Barr, 2005. Advanced Computer Architecture and Parallel Processing. John Wiely and Sons Inc., Hoboken, N.J.
   
9. Feitelson, D.G. and L. Rudolph, 1996. Job scheduling strategies for parallel processing. Proceeding of the IPPS'96, Honolulu, Hawaii.
   CrossRef    
10. Grama, A., A. Gupta, G. Karypis and V. Kumar, 2003. Introduction to Parallel Computing. 2nd Edn., Addison Wesley, Boston, Massachusetts.
    PMid:12677330    
11. Juang, T.Y.T., Y.C. Tseng and Y.S. Chen, 1997. An enhanced 2D buddy strategy for submesh allocation in mesh networks. Proceeding of the 3rd International Conference on Algorithms and Architectures for Parallel Processing. Melbourne, Vic., pp: 345-352.
    
12. Li, K. and K.H. Cheng, 1990. A two dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system. Proceeding of the ACM Annual Conference on Cooperation (CSC '90). New York, pp: 22-27.
    
13. Liu, W., V. Lo, K. Windisch and B. Nitzberg, 1994. Non-contiguous processor allocation algorithms for distributed memory multicomputers. Proceeding of the ACM/IEEE Conference on Supercomputing (Supercomputing '94). New York, pp: 227-236.
    
14. Lo, V., K.J. Windisch, W. Liu and B. Nitzberg, 1997. Noncontiguous processor allocation algorithms for mesh-connected multicomputers. IEEE T. Parall. Distr., 8(7): 712-726.
    
15. Parhami, B., 2005. Computer Architecture: From Microprocessors to Supercomputers. Oxford University Press, New York, pp: 575.
    Direct Link
16. Penrose, D.E.M. and E. Wade, 2003. Interconnection Networks: An Engineer Approach. Elsevier Science, USA.
    
17. Rauber, T. and G. Rünger, 2010. Parallel Programming: For Multicore and Cluster Systems. Spring-Verlag, Berlin.
    
18. Sargunar, J., 2011. Introduction to Computer Science. 2nd Edn., Dorling Kindersley, India.
    
19. Windisch, K., J.V. Miller and V. Lo, 1995a. ProcSimity: An experimental tool for processor allocation and scheduling in highly parallel systems. Proceeding of the 5th Symposium on the Frontiers of Massively Parallel Computation. Washington, DC, USA.
    
20. Windisch, K., V. Lo and B. Bose, 1995b. Contiguous and non-contiguous processor allocation algorithms for k-ary n-cubes. IEEE T. Parall. Distr., 6: 414-421.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.