The Non-Contiguous Allocation Strategies Performance for k-ary n-cube Connected Multi Computers Using Smallest Job First Scheduling Strategy

Doreyed Muhammed Ahmed Awaad Al-Kerboly

doi:10.61841/aycx7619

Authors

Doreyed Muhammed Ahmed Awaad Al-Kerboly Mathematics Department, College of Education for Pure Science, University of Anbar, Anbar, Iraq Author

DOI:

https://doi.org/10.61841/aycx7619

Keywords:

Communication Patterns, k-ary n-cube Connected Multi Computers, Non-Contiguous Allocation, Fragmentation

Abstract

The performance of the famous non-contiguous allocation algorithms (Paging (0), Multiple Partner, and Random) proposed for k-ary n-cube connected multi-computers has been compared by wide simulation experiments. In the paper, the smallest job first scheduling strategy (SJF) and three communication patterns were measured; these are random, one-to-all, and all-to-all. The simulation results display that the performance of non-contiguous paging (0) is superior to that of wholly additional non-contiguous allocation algorithms (strategies) in our scenario due to their capability to reduce together (internal and external) fragmentation and reduce the dispute inside the network by preserving a huge contiguity degree through allocated processors.

Downloads

Download data is not yet available.

References

[1] Abdullah Al-Dhelaan, Processor Allocation & Communication in Networks, Ph.D. Thesis, Department of

Computer Science, Oregon State University, March 17, 1989.

[2] Abdullah Al-Dhelaan and B. Bose. A New Strategy for Processors Allocation in an N-Cube

Multiprocessor. In Proceedings of the International Phoenix Conference on Computers and

Communication, pp. 114-118, March, 1989.

[3] C.-Y. Chang and P. Mohapatra, Performance Improvement of Allocation Schemes for Mesh-Connected

Computers, Journal of Parallel and Distributed Computing, vol. 52, no. 1, pp. 40-68, 1998.

[4] Doreyed Muhammed Ahmed Awaad Al-kerboly, On the Execution of Different Job Scheduling Strategies

for Non-Contiguous Allocation Algorithm in k-ary ncube Connected Multi computers, Aus Journal

(Version on-line ISSN 0718-7262/Version impresa ISSN 0718-204x), p. 208-214, 2019.

[5] Hamid Mahini, and Hamid Sarbazi-Azad, Resource Placement in Three-Dimensional Tori, Institute for

Research in Fundamental Sciences (IPM), Tehran, Iran, vol. 35, No. 10-11, pp. 535-543, 2009.

[6] I. Foster, Designing and Building Parallel Programs, Concepts and Tools for Parallel Software Engineering,

Addison-Wesley, 3rd edition, 1995.

[7] J. Al-Sadi, K. DAY, and M. Ould-Khaoua, A New Fault-Tolerant Routing Algorithm for K-Ary N-Cube

Networks, International Journal of High Speed Computing, vol. 12, no. 1, pp. 29-54, 2004.

[8] Jacob Engel, Off-Chip Communications Architectures for High Throughput Network Processors, Ph.D.

Thesis, Department of Computer Engineering, College of Engineering and Computer Science, University

of Central Florida Orlando, Florida, 2005.

[9] José Duato , and Sudhakar Yalamanchili, Interconnection Networks: An Engineering Approach, Library of

Congress Control Number: 2002104300, ISBN: 1-55860-852-4 Revised Printing, by Elsevier Science

(USA), 2003.

[10] Kurt Windisch, Virginia and Bella Bosae, Contiguous and Non-Contiguous Processor Allocation

Algorithms for K-Ary N-Cubes, IEEE Transactions on Parallel and Distributed Systems, vol. 8, pp. 712-

726, 1995.

[11] M. Morris Mano, Computer System Architecture, Person Education Limited, 3rd edition, ISBN 0-13-

175563-3, 1993.

[12] Ming-Syan Chen and Kang G. Shin, Processor Allocation In an N-Cube Multiprocessor Using Grey Code,

IEEE Transactions on Computers, vol. C-36, no. 12, pp. 1396-1407, December 1987.

[13] ProcSimity V 4.3 User's Manual, University of Oregon, 1997.

[14] Qian Ping Gu and Jun Gu, Algorithms and Average Time Bounds of Sorting on a Mesh-Connected

Computer, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 3, pp. 308-315, March 1994.

[15] Raed Al Momani, and Ismail Ababneh, Communication Overhead in Non-Contiguous Processor Allocation

Policies for 3D Mesh--Connected Multicomputers, The International Arab Jordan of Information

Technology, vol. 9, no. 2, pp. 133-141, March 2012.

[16] S. Attari and A. Isazadeh, Processor Allocation In Mesh Multiprocessors Using a Hybrid Method, Proceedings of the Seventh International Conference on Parallel and Distributed Computing, Applications

and Technologies (PDCAT'06), 0-7695-2736-1/06, pp. 492-496, 2006.

[17] S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh and Lewis M. Mackenzie, An Efficient Turning Busy

List Sub-Mesh Allocation Strategy for 3D Mesh Connected multicomputers

Proceedings of the 7th Annual PostGraduate Symposium on the Convergence of Telecommunications,

Networking & Broadcasting, (PGNET 2006), Liverpool John Moores University, UK, pp. 37-43, 26-27

June 2006.

[18] S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh and Lewis M. Mackenzie, An Efficient Processor

Allocation Strategy that Maintains a High Degree of Contiguity Among Processors in 2D Mesh Connected

Multi computers, 2007 ACS/IEEE International Conference on Computer Systems and Applications

(AICCSA 2007 ), IEEE computer Society Press, Philadelphia university, Amman, Jordan, pp. 934-941, 13-

16 May 2007.

[19] S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh and Lewis M. Mackenzie, A Fast and Efficient Strategy

for Sub-Mesh Allocation with Minimal Allocation Overhead in 3D Mesh Connected Multicomputers,

Ubiquitous Computing and Communication Journal, vol. 1, no. 1, pp. 26-36, 2006.

[20] S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh, and Lewis M. Mackhenzie, Comparative Evaluation of

Contiguous Allocation Strategies on 3D Mesh Multicomputers, Journal of System and Software, vol. 82,

no. 2, pp. 307-318, 2009.

[21] S. Moghaddam and M. Naghibzadeh, A New Processor Allocation Strategy Using ESS (Expanding Square

Strategy), Proceedings of the 14th Euromicro International Conference on Parallel, Distributed, and

Network-Based Processing (PDP’06), 1066-6192/06, 2006.

[22] Saad Bani Mohammad, Ismail Ababneh, Mohamed Ould-Khaoua, A Comparative Study of Real Workload

Traces and Synthetic Workload Models for Non-Contiguous Allocation in 2D Meshes, International

Conference on Scalable Computing and Communications; The Eighth International Conference on

Embedded Computing, pp. 633-639, 2009.

[23] Saad Bani-Mohammad, Ismail Ababneh and Mazen Hamdan, Performance Evaluation of Noncontiguous

Allocation Algorithms for 2D Mesh Interconnection Networks, Journal of System and Software, vol. 84,

no. 12, pp. 2156-2170, 2011.

[24] Saad O. Bani Mohammad, Efficient Processor Allocation Strategies for Mesh Connected Multicomputers,

PhD. Thesis, Department of Computing Science, Faculty of Information and Mathematical Sciences,

University of Glasgow, February 2008.

[25] V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing, Person Education Limited, 2nd edition, ISBN 0-201-64865-2, 2003.

[26] Virginia Lo, Jens Mache, and Kurt Windisch, A Comparative Study of Real Workload Traces and Synthetic Workload Models for Parallel Job Scheduling, This research was sponsored by NSF grant MIP-9108528. Springer-Verlag Berlin Heidelberg, pp. 25-46, 1998.

[27] Virginia Lo, Kurt J. Windisch, Wanqian Liu, and Bill Nitzberg, Noncontiguous Processor Allocation Algorithms for Mesh-Connected Multicomputers, IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 7, pp. 712-726, July 1997.