Authors A.E. Saak, V.V. Kureichik
Month, Year 04, 2015 @en
Index UDC 004.272.43
Abstract For Grid system’ time and computing resources scheduling as the theoretical base of the algorithmic supply of scheduling with polynomial complexity the resource rectangle environment is defined, in which arrays of user tasks are classified to circular, hyperbolic and parabolic square types. The Grid systems of centralized architecture with multisite scheduling are considered. The Non-Euclidean heuristic measure which considers both the square and the shape of occupied resource area is used for heuristic algorithms quality assessment. The possible minimum of the heuristic measure is reached through packing into a square enclosure without emptiness. The heuristic polynomial algorithm’ adaptability was showed for linear polyedrals of circular type which were optimally packed into the comprehensive minimum square with emptiness. In the paper the linear polyedrals of resource rectangles are defined for which the square resource enclosure without emptiness exists. The polyedrals are denoted as the ones of precise shape. Also the notion of circular-type linear polyedrals is extended in the paper. The aim of the paper is to study adaptability of polynomial algorithms for the class of linear polyedrals with square resource en-closure which dosen’t have any empty spaces. The linear polyedrals induced by the elements of perfect square squaring are analyzed. A minimal degree of perfect simple square squaring and perfect complex square squaring induces two linear polyedrals. A minimal size of a square of perfect simple squaring induces three linear polyedrals. The linear polyedrals are scheduled then and the heuristic measure indicators for the resource enclosures created by an initial ring algorithm, level algorithm, angular-level algorithm and successive approximation algorithm are calculated. In the paper we prove that considered polynomial algorithms retain their adaptedness characteristic when used for precisely-formed circular-type linear polyedrals.

Download PDF

Keywords Precisely-formed linear polyedrals; circular-type linear polyedrals; Grid system; scheduling; Non-Euclidean heuristic measure; polynomial complexity of an algorithm; square squaring; initial ring algorithm; level algorithm; angular-level algorithm; successive approximation algorithm.
References 1. Saak A.E. Lokal'no-optimal'nye resursnye raspredeleniya [Locally optimal resource allocation], Informatsionnye tekhnologii [Information Technologies], 2011, No.2, pp. 28-34.
2. Saak A.E. Algoritmy dispetcherizatsii v Grid-sistemakh na osnove kvadratichnoy tipizatsii massivov zayavok [Algorithms for scheduling in Grid systems based on the quadratic typing arrays applications], Informatsionnye tekhnologii [Information Technologies], 2011, No. 11, pp. 9-13.
3. Saak A.E. Dispetcherizatsiya v Grid-sistemakh na osnove odnorodnoy kvadratichnoy tipizatsii massivov zayavok pol'zovateley [Scheduling in Grid systems based on homogeneous quadratic typing of arrays of user requests], Informatsionnye tekhnologii [Information Technologies], 2012, No. 4, pp. 32-36.
4. Saak A.E. Polinomial'nye algoritmy raspredeleniya resursov v Grid-sistemakh na osnove kvadratichnoy tipizatsii massivov zayavok // Informatsionnye tekhnologii [Information Technologies], 2013, No. 7. Application, 32 p.
5. Magoulиs F., Nguyen T., Yu L. (2009). Grid resource management: toward virtual and services compliant grid computing, Numerical analysis and scientific computing. CRC Press, UK. 6. Magoulиs F. (ed.). (2010) Fundamentals of grid computing: theory, algorithms and technologies, Numerical analysis and scientific computing. CRC Press, UK.
7. Antonopoulos N., Exarchakos G., Li M., Liotta A. (eds.). (2010). Handbook of research on p2p and grid systems for service-oriented computing: models, methodologies and applications. IGI Global publisher, USA.
8. Li M., Baker M. (2005). The grid: core technologies. John Wiley & Sons Ltd, England. 9. Hamscher V., Schwiegelshohn U., Streit A., Yahyapour R. Evaluation of job-scheduling strategies for grid computing // In Proceedings of the 7th International Conference on High Performance Computing, HiPC-2000. Vol. 1971 of Lecture Notes in Computer Science, Indiа, Springer, 2000, pp. 191-202.
10. Rahman M., Ranjan R., Buyya R., Benatallah B. A taxonomy and survey on autonomic management of applications in grid computing environments, Concurrency Computat.: Pract. Exper., 2011, No. 23, pp. 1990-2019.
11. Krauter K., Buyya R., Maheswaran M. A taxonomy and survey of Grid resource management systems for distributed computing, Softw. Pract. Exper., 2002, Vol. 32, No. 2, pp. 135-164.
12. Iosup A., Epema D.H.J., Tannenbaum T., Farrellee M., Livny M. Inter-operating Grids through delegated matchmaking, In 2007 ACM/IEEE Conference on Supercomputing (SC 2007). New York: ACM Press, 2007, pp. 1-12.
13. Patel S. Survey Report of Job Scheduler on Grids, International Journal of Emerging Research in Management &Technology, 2013, Vol. 2, No. 4, pp. 115-125.
14. Assunзгo M., Buyya R. Architectural elements of resource sharing networks. In Li K., Hsu C., Yang L., Dongarra J., Zima H. (eds.), Handbook of research on scalable computing technologies, 2010, Vol. 2, pp. 517-550.
15. Netto M., Buyya R. Resource Co-allocation in Grid Computing Environments. In Antonopoulos, N., Exarchakos G., Li,M., Liotta A. (eds.), Handbook of research on p2p and grid systems for service-oriented computing: models, methodologies and applications. – IGI Global publisher, 2010, Vol. 1, pp. 476-494.
16. Saak A.E. Upravlenie resursami i zayavkami pol'zovateley v Grid-sistemakh s tsentrali-zovannoy arkhitekturoy [The management of resources and applications users in Grid systems with a centralized architecture], Trudy XII Vserossiyskogo soveshchaniya po problemam upravleniya VSPU-2014. Moskva, 16-19 iyunya 2014 g [Proceedings of the XII all-Russian conference on the problems of management in the Everything-2014. Moscow, 16-19 June 2014]. Moscow: Institut problem upravleniya im. V.A. Trapeznikova RAN, 2014, pp. 7489-7498.
17. Saak A.E. Sravnitel'nyy analiz polinomial'nykh algoritmov dispetcherizatsii v Grid-sistemakh [Comparative analysis of polynomial algorithms for scheduling in Grid systems], Informatsionnye tekhnologii [Information Technologies], 2012, No. 9, pp. 28-32.
18. Korf R. Optimal rectangle packing: New results, In Proceedings of the fourteenth international conference on automated planning and scheduling (ICAPS 2004). Whistler, British Columbia, Canada, June 3-7, 2004, pp. 142-149.
19. Korf R., Moffitt M., Pollack M. Optimal rectangle packing, Annals of Operations Research, 2010, Vol. 179, No. 1, pp. 261-295.
20. Caramia M., Giordani S., Iovanella A. Grid scheduling by on-line rectangle packing, Networks, 2004, Vol. 44, No. 2, pp. 106-119.
21. Duijvestijn A.J.W. Simple perfect squared square of lowest order, J. Combin. Theory, 1978. Ser. B, No. 25, pp. 240-243.
22. Duijvestijn A.J.W., Federico P.J., Leeuw P. Compound perfect squares. Amer. Math. Monthly, 1982, No. 89, pp. 15-32.
23. Gambini I. A method for cutting squares into distinct squares, Discrete Applied Math, 1999, No. 98, pp. 65-80.

Comments are closed.