Authors A.E. Saak
Month, Year 06, 2015 @en
Index UDC 004.272.43
Abstract In the paper it is considered the further development of formal instruments for distribution management of computer and time resources of resource rectangles environment, as the base of the polynomial scheduling theory. In the previous works the author has introduced the operations of addition, multiplication, differentiation and dynamic integration of resource rectangles in the resource rectangles environment. Heuristic algorithms of polynomial complexity for resource distribution were suggested and studied. They have in their base the introduced operations above resource rectangles. The computer tasks with certain time of solution, in which the number of processors involved is defined by a user on the initial stage, are considered in the paper. It is suggested and developed a quadratic classification of a set of tasks simulated by resource rectangles. The polynomial algorithms were adapted under the appropriate quadratic type of tasks’ array. The purpose of the paper is new operations introduction in the resource rectangles environment, the development on their base new polynomial algorithms, which supposed to have better quality of scheduling measured by the non- Euclidean heuristic measure which takes into account both the square and the shape of the occupied area. In the paper there are defined operations of dynamic integration of the resource rectangles with an excess and minimal deviation. On the base of this operations there are developed a level algorithm with an excess and a wave level algorithm, adapted for the circular typed user tasks. On the simulation examples of a set of resource squares with the sides equal to successive natural numbers which begin with one we conduct scheduling and calculate the resource environments heuristic measures of the polynomial level algorithms. The comparative analysis shows an advantage of suggested polynomial algorithms and allows to recommend them to use in Grid systems with centralized structure when serving circle-typed task arrays.

Download PDF

Keywords The operation of resource rectangles dynamic integration on vertical with an excess; the operation of resource rectangles dynamic integration on vertical with minimal deviation; a Grid system; the centralized structure of scheduling system; a multi-site service mode; the non- Euclidean heuristic measure; a circle-typed tasks array; an algorithm of polynomial complexity; the level algorithm with an excess; the wave level 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 [The scheduling algorithms in Grid-based systems for 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, arrays applications users], Informatsionnye tekhnologii [Information Technologies], 2012, No. 4, pp. 32-36.
4. 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.
5. Saak A.E. Polinomial'nye algoritmy raspredeleniya resursov v Grid-sistemakh na osnove kvadratichnoy tipizatsii massivov zayavok [Polynomial algorithms for resource allocation in Grid-based systems for quadratic typing, arrays applications], Informatsionnye tekhnologii [Information Technologies], 2013, No. 7. Prilozhenie, 32 p.
6. 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, volume 1971 of Lecture Notes in Computer Science, Indiа, 2000. Springer, pp. 191-202.
7. Magoulиs F., Nguyen T., Yu L. Grid resource management: toward virtual and services compliant grid computing, Numerical analysis and scientific computing. CRC Press, UK, 2009.
8. Magoulиs F. (ed.). Fundamentals of grid computing: theory, algorithms and technologies, Numerical analysis and scientific computing. CRC Press, UK, 2010.
9. 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, USA, 2010.
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. 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.
12. Saak A.E. Upravlenie resursami i zayavkami pol'zovateley v Grid-sistemakh s tsentralizovannoy arkhitekturoy [The management of resources and applications users in Grid-systems with centralized architecture], Trudy KhII Vserossiyskogo soveshchaniya po problemam upravleniya VSPU-2014. Moskva, 16-19 iyunya 2014 g. [Proceedings of the XII all-Russian conference on control problems the EVERYTHING-2014. Moscow, 16-19 June 2014]. Moscow: Institut problem upravleniya im. V.A. Trapeznikova RAN, 2014, pp. 7489-7498.
13. Foster I., Kesselman C. The Grid in a nutshell. In: Nabrzyski J., Schopf J., Weglarz J. (eds.) Grid Resource Management: state of the art and future trends. Kluwer, 2003.
14. Jacob B., Brown M., Fukui K., Trivedi N. (2005) Introduction to grid computing. IBM Corp., USA. 15. Christodoulopoulos, K., Sourlas, V., Mpakolas, I., Varvarigos, E. A comparison of centralized and distributed meta-scheduling architectures for computation and communication tasks in Grid networks, Computer Communications, 2009, No. 32, pp. 1172-1184.
16. Feitelson, D., Rudolph, L. Toward convergence in job schedulers for parallel supercomputers. In Job Scheduling Strategies for Parallel Processing, Feitelson D., Rudolph L. (eds.). Springer-Verlag, 1996. Lecture Notes in Computer Science, Vol. 1162, pp. 1-26.
17. Ye D., Zhang G. On-Line Scheduling of Parallel Jobs. In R. Krбlovič and O. Sэkora, ed., SIROCCO 2004. Vol. LNCS 3104, pp. 279-290.
18. Caramia M., Giordani S., Iovanella A. Grid scheduling by on-line rectangle packing, Networks, 2004, Vol. 44, No. 2, pp. 106-119.
19. Korf R., Moffitt M., Pollack, M. Optimal rectangle packing, Annals of Operations Research, 2010, Vol. 179, No. 1, pp. 261-295.
20. Huang E., Korf R. Optimal rectangle packing: an absolute placement approach, Journal of Artificial Intelligence Research, 2012, No. 46, pp. 47-87.

Comments are closed.