LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Bani-Mohammad, S.; Ould-Khaoua, M.; Abaneh, I.; Mackenzie, L.M. (2007)
Publisher: Institute of Electrical and Electronics Engineers
Languages: English
Types: Other
Subjects: QA75
Two strategies are used for the allocation of jobs to processors connected by mesh topologies: contiguous allocation and non-contiguous allocation. In non-contiguous allocation, a job request can be split into smaller parts that are allocated to non-adjacent free sub-meshes rather than always waiting until a single sub-mesh of the requested size and shape is available. Lifting the contiguity condition is expected to reduce processor fragmentation and increase system utilization. However, the distances traversed by messages can be long, and as a result the communication overhead, especially contention, is increased. The extra communication overhead depends on how the allocation request is partitioned and assigned to free sub-meshes. This paper presents a new Non-contiguous allocation algorithm, referred to as Greedy-Available-Busy-List (GABL for short), which can decrease the communication overhead among processors allocated to a given job. The simulation results show that the new strategy can reduce the communication overhead and substantially improve performance in terms of parameters such as job turnaround time and system utilization. Moreover, the results reveal that the Shortest-Service-Demand-First (SSD) scheduling strategy is much better than the First-Come-First-Served (FCFS) scheduling strategy.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • B.-S.Yoo, C.-R. Das, “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.
    • C.-Y. Chang, P. Mohapatra, “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.
    • G.-M. Chiu, S.-K. Chen, “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.
    • 79, no. 8, Elsevier Science Inc., New York, NY, USA, August 2006, pp. 1168-1179.
    • I. Ismail, J. Davis, “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.
    • Intel Corporation, A Touchstone DELTA system description, 1991.
    • K. Li, K.-H. Cheng, “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.
    • Connelly, and M. Tsukamoto, “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.
    • K. Windisch, J. V. Miller, and V. Lo, “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.
    • K.-H. Seo, “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.
    • Giampapa, P. Heidelberger, S. Singh, B. SteinmacherBurow, T. Takken and P. Vranas, “Design and Analysis of the BlueGene/L Torus Interconnection Network”, IBM Research Report RC23025, IBM Research Division, Thomas J. Watson Research Center, Dec. 3, 2003.
    • P. Krueger, T. Lai, V. A. Radiya, “Job scheduling is more important than processor allocation for hypercube [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] computers”, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 5, IEEE Press, Piscataway, NJ, USA, May 1994, pp. 488-497.
    • P.-J. Chuang, N.-F. Tzeng, “Allocating precise submeshes in mesh connected systems”, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 2, IEEE Press, USA, February 1994, pp. 211-217.
    • ProcSimity V4.3 User's Manual, University of Oregon, 1997.
    • S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh, and L. Machenzie, “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.
    • S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh, and L. Machenzie, “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.
    • Jonathan, “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.
    • V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction To Parallel Computing, The Benjamin/Cummings publishing Company, Inc., Redwood City, California, 2003.
    • V. Lo, K. Windisch, W. Liu, and B. Nitzberg, “Noncontiguous processor allocation algorithms for meshconnected multicomputers”, IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 7, IEEE Press, Piscataway, NJ, USA, July 1997, pp. 712-726.
    • W. Mao, J. Chen, W. Watson, “Efficient Subtorus Processor Allocation in a Multi-Dimensional Torus”, Proceedings of the 8th International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA'05), IEEE Computer Society, Washington, DC, USA, 30 November - 3 December, 2005, pp. 53-60.
    • Moreira, and E. Shmueli, “Open Job Management Architecture for the Blue gene/L Supercomputer”, Proceedings of the 11th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP'05), Springer Berlin / Heidelberg, Cambridge, MA, June 19, 2005, pp.
    • Y. Zhu, “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.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article