350 rub
Journal Achievements of Modern Radioelectronics №8 for 2011 г.
Article in number:
Task Allocation Problem in Parallel Programs of Conducting a Database of Space Debris Elements
Authors:
V. A. Goryuchkin
Abstract:
In the article «Task allocation problem in parallel programs of conducting a database of space debris elements» a task allocation problem is discussed. The major factors on which the decision process for this problem depends are considered. For formal representation of these factors the concept of an Abstract resource is defined. The concept of an abstract resource plays a key role in construction of model of planning procedure. The model also includes a parameter of current utilization of computing system U, and restrictions on this parameter, which determine minimal and maximal values of utilization of the computing system. The equivalence of the examined task allocation problem and the problem of integer programming for m-Dimensional Vector Packing Problem is shown on the basis of the entered model. This equivalence entails NP-completeness of task allocation problem. For the decision of the problem it is proposed to use heuristic algorithms. For simplification of algorithm the special procedure «the reinterpretaion» is offered . One-passage heuristic algorithm of task allocation is developed. This algorithm provides uniform distribution of processes and minimizes number of computing nodes. In the article the analysis of other works devoted to the given theme is carried out. In the conclusion of the article the brief review of the received results is given and the further directions of researches are defined.
Pages: 67-71
References
  1. Горючкин В.А. Определение орбит элементов космического мусора на вычислительной системе с параллельной архитектурой // Успехи современной радиоэлектроники. 2009. № 4. С. 73-80.
  2. Garey. M.R., Graham. R.L., Johnson. D.S., and Yao. A.C.C. Resource constrained scheduling as generalized bin packing // Journal of Combinatorial Theory (Series A). 1976. № 21. Р. 257-298.
  3. Sorawit Yaoyuenyong A Search-Based Algorithm for the Multi-Dimensional Vector Packing Problem // Asia Pacific Industrial Engineering & Management Systems Conference (APIEMC 2009). 14-16 December 2009. Р. 81-85.
  4. Беллман Р., Дрейфус Р. Прикладные задачи динамического программирования: пер. с англ. М.: Наука. 1965.
  5. Beck. J. and Siewiorek. D. Modeling multicomputer task allocation as a vector packing problem // In Proceedings of the 9thInternational Symposium on System Synthesis. San Diego, CA. Nov. 1996. Р. 115-121
  6. Fisher N., Anderson J.H., Baruah S. Task partitioning upon memory-constrained multiprocessors // 11thIEEE International Conference of Embedded and Real-Time Computing Systems and Applications (RTCSA 2005). 17-19 August 2005. Honk Kong, China. Р. 416-421 // IEEE Computer Society. 2005.