A two dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system

ABSTRACT

The system partitioning problem in a partitionable mesh connected system (PMCS) is addressed. A two dimensional buddy system (2DBS) is proposed as a partitioning scheme for dynamic resource allocation in a PMCS. Allocation and reclamation algorithms and the method for locating buddies are designed. Internal fragmentation of our proposed 2DBS under various probability distributions of job sizes is analyzed. Experimental results on external and total fragmentations are also presented.

REFERENCES

• 1: B. S. Baker, E. G. Coffman, Jr., and R. L. Rivest, "Orthogonal packings in two dimensions," SIAM J. Computing, Nov. 1980, 846-855.
• 2: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 3: M.-S. Chen , K. G. Shin, Processor allocation in an N-cube multiprocessor using gray codes, IEEE Transactions on Computers, v.36 n.12, p.1396-1407, Dec. 1987 [doi>10.1109/TC.1987.5009493]
• 4: Daniel S. Hirschberg, A class of dynamic memory allocation algorithms, Communications of the ACM, v.16 n.10, p.615-618, Oct. 1973 [doi>10.1145/362375.362392]
• 5: M. Jeng and H. J. Siegel, "Dynamic partitioning in a class of parallel systems," Proc. 8th lnt'l Conf. Distributed Computing Sys., 1988, 33-40.
• 6: Kenneth C. Knowlton, A fast storage allocator, Communications of the ACM, v.8 n.10, p.623-624, Oct. 1965 [doi>10.1145/365628.365655]
• 7: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 8: W.H. Lee and M. Malek, "MOPAC: a partitionable and reconfigurable multicomputer array," Proc. 1983 lnt' l Conf. on Parallel Processing, 506.510.
• 9: K. Li and K. I-I. Cheng, "Complexity of resource allocation and job scheduling problems on partitionable mesh connected systems," Proc. }st Annual IEEE Symposium on Parallel and Distributed Processing, May 1989, 358-365.
• 10: K. Li and K. H. Cheng, "Job scheduling in partitionable mesh connected systems," Proc. 1989 lnt'l Conf. on Parallel Processing, Vol. 2, 65-72.
• 11: K. Li and K. H. Cheng, "A two dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system," TR #UH-CS-89-03, Dept. of Computer Science, Univ. of Houston, 1989.
• 12: I P Page , J Hagins, Improving the performance of buddy systems, IEEE Transactions on Computers, v.35 n.5, p.441-447, May 1986 [doi>10.1109/TC.1986.1676786]
• 13: James L. Peterson , Theodore A. Norman, Buddy systems, Communications of the ACM, v.20 n.6, p.421-431, June 1977 [doi>10.1145/359605.359626]
• 14: U. V. Premkumar , J. C. Browne, Resource allocation in rectangular SW banyans, Proceedings of the 9th annual symposium on Computer Architecture, p.326-333, April 26-29, 1982, Austin, Texas, United States
• 15: Kenneth K. Shen , James L. Peterson, A weighted buddy method for dynamic storage allocation, Communications of the ACM, v.17 n.10, p.558-562, Oct. 1974 [doi>10.1145/355620.361164]
• 16: H. J. Siegel, "The theory underlying the partitioning of permutation networks," IEEE Trans. on Computers, Sept. 1980, 791-801.
• 17: A. Silberschatz , J. L. Peterson, Operating systems concepts, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 18: S. Yalamanchili and L K. Aggarwal, "Reconfiguration strategies for parallel architectures," Computer, Dec. 1985, 44-61.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Main memory

General Terms:
Algorithms, Design, Experimentation