Разработка и исследование алгоритмов управления очередями заданий при организации параллельных вычислений в кластерных вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Аль-хулайди Абдулмаджид Ахмед Галеб

• Аль-хулайди Абдулмаджид Ахмед Галеб
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Аль-хулайди Абдулмаджид Ахмед Галеб

СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ, МОДЕЛЕЙ И АЛГОРИТМОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ И ПАКЕТОВ, ОБЕСПЕЧИВАЮЩИХ ПАРАЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ В КЛАСТЕРНЫХ СИСТЕМАХ.

1.1. Методы распределения ресурсов при организации параллельных вычислений.

1.1.1. Метод FCFS (первый пришел, первый обслужен).

1.1.2 Метод Backfill (обратного заполнения).

1.1.3. Метод SJF (краткосрочного планирования).

1.2. Метод Gang scheduling (комплектного планирования).

1.3. Адаптивный метод управления потоком решения заданий в параллельной вычислительной среде.

1.4. Алгоритмы управления очередями при организации параллельных вычислений.

1.4.1. Традиционный алгоритм FIFO.

1.4.2. Алгоритм Priority Queing (приоритетного обслуживания).

1.4.3. Алгоритм WQ (взвешенных очередей).

1.4.4. Алгоритм WFQ (взвешенного справедливого обслуживания).

1.5. Распределённые вычисления (кластерные вычисления) с использованием пакета параллельного программирования MPI.

1.6. Анализ существующих программных пакетов в кластерных системах.

1.6.1. Кластеры высокой доступности.

1.6.2. Кластеры распределения нагрузки.

1.6.3. Вычислительные кластеры.

1.7. Анализ программного обеспечения и средства его установки на кластер.

1.8. Кластерные системы управления пакетной обработкой (СПО).

1.9. Интегрированные программные средства для кластеров.

1.10. Проблемы параллельных вычислений, возникающие при использовании кластерного пакета MPI/MPICH.

1.11. Выводы.

ГЛАВА 2. РАЗРАБОТКА МОДЕЛИ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ НА ОСНОВЕ СЕМАНТИЧЕСКОЙ СЕТИ И СТОХАСТИЧЕСКИЙ ПОДХОД К ОЦЕНКЕ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ В КЛАСТЕРНЫХ СИСТЕМАХ.

2.1. Модель кластера MPI/MPICH на основе семантической сети в планировщике Maui.

2.2. Управление очередями в кластерных системах.

2.2.1.Выбор критериев оценки алгоритмов управления очередями.

2.2.2.Схема организации вычислений.

2.2.3.Аппаратное обеспечение.

2.2.4.Менеджер ресурсов.

2.2.5. Планировщик задач к менеджерам ресурсов, работающий по методу backfill.

2.2.6.Конкретизация положений теории очередей для кластерной системы.

2.3. Основные положения теории Марковских процессов и стохастический подход к оценке управления очередями заданий.

2.4. Выводы.

ГАЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ И ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ПРОВЕРКИ ЭФФЕКТИВНОСТИ ПРЕДЛОЖЕННЫХ АЛГОРИТМОВ НА КЛАСТЕРНЫХ

СИСТЕМАХ.

3.1. Алгоритмы управления очередями заданий для параллельных вычислений

3.1.1. Алгоритм распределения ресурсов между процессами.

3.1.2 Алгоритм управления запуском заданий для кластерных систем.

4.2.2. Испытание и результаты экспериментальной проверки эффективности предложенной модели на основе транспортной задачи.

4.3. Испытания и результаты экспериментальной проверки эффективности предложенных алгоритмов на основе нахождения минимального остовного дерева.

4.3.1. Алгоритм управления на основе параллельного алгоритма нахождения минимального остовного дерева по методу Борувки.

4.3.2. Сравнительная характеристика экспериментальной и теоретической оценки эффективности параллельных алгоритмов нахождения минимального остовного дерева.

4.4. Испытания и результаты экспериментальной проверки эффективности предложенных алгоритмов управления на основе параллельного алгоритма решения транспортной задачи.

4.4.1. Экспериментальная проверка предложенных алгоритмов управления очередями заданий.

4.4.2. Сравнение экспериментального и теоретического времени работы параллельного алгоритма нахождения опорного плана транспортной задачи на основе метода Фогеля.

4.4.3. Экспериментальная проверка эффективности параллельного алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов.

4.5. Интерфейс программных стендов и работа с ними.

4.6.Вывод ы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов управления очередями заданий при организации параллельных вычислений в кластерных вычислительных системах»

Во введении обоснована актуальность темы, определены цель и задачи диссертационной работы, объект и предмет исследования, указаны методы исследования, научная новизна, основные положения, выносимые на защиту, приведены сведения о практической значимости, об использовании результатов работы, апробации диссертационной работы, дано краткое содержание основных разделов диссертации.

Первая глава посвящается анализу существующих методов, моделей и алгоритмов управления очередями заданий и пакетов, обеспечивающих

15 параллельные вычисления в кластерных системах, с целью повышения производительности кластерных систем при организации параллельных вычислений. Отмечены достоинство, недостатки и перспективы развития этих алгоритмов. По результатам проведенного анализа обосновывается необходимость разработки модели и алгоритмов, применяющихся в кластерных системах, для повышения производительности параллельных вычислений, обеспечения ускорения решения задач в кластерных системах и уменьшения времени ожиданий заданий в очереди.

Вторая глава посвящена разработке модели управления очередями на основе семантической сети и стохастического похода к оценке управления очередями заданий для параллельных вычислений на кластерах, с использованием Марковских процессов, с целью повышения производительности параллельных вычислений, обеспечения ускорения решения задач в кластерных системах и уменьшения времени ожидания заданий в очереди. В этой главе показано, как теоретические положения теории массового обслуживания (ТМО) - теории очередей - и семантическая сеть применяются к практическим задачам управления очередями заданий в кластерной системе.

Третья глава посвящена разработке алгоритмов управления очередями заданий для кластерных систем. Приводятся описания структурных схем алгоритма управления порядком запуска заданий и алгоритма распределения ресурсов между процессами. Кроме этого, посвящается разработке параллельного алгоритма и структурной схемы нахождения минимального остовного дерева, на основе метода Борувки, для проверки предложенных модели, подхода и алгоритмов управления очередями. Представлены разработанные алгоритмы решения транспортной задачи для параллельных систем: структурные схемы параллельного алгоритма нахождения опорного плана транспортной задачи, на основе метода Фогеля, и параллельного алгоритма нахождения оптимального решения транспортной задачи, на основе метода потенциалов, для проверки предложенных модели, подхода и

16 алгоритмов управления очередями заданий на кластерных системах. Выбираются основные классы задач, которые будут решаться на кластере, модель и алгоритмы управления очередями. Приводятся теоретические оценки оптимального количества вычислительных узлов кластерных систем, времени выполнения параллельных алгоритмов решения транспортной задачи на кластере, вычислительной сложности параллельного алгоритма нахождения минимального остовного дерева ,на основе метода Борувки, с целью повышения эффективности параллельной обработки на кластере.

В четвертой главе рассмотрены цель и средства экспериментальных исследований разработанных модели и алгоритмов управления очередями, для повышения эффективности производительности параллельных вычислений, обеспечения ускорения решения задач в кластерных системах и уменьшения времени ожидания заданий в очереди. Приведена экспериментальная проверка и испытание эффективности предложенных модели и алгоритмов управления очередями заданий на кластерном пакете MPI/MPICH и предложенного кластерного пакета MPI/MPI CHNEW, который содержит модель и алгоритмы управления очередями заданий, включающего параллельные алгоритмы решения транспортной задачи и нахождения минимального остовного дерева. Приводится сравнительная характеристика экспериментальных и теоретических оценок параллельных алгоритмов решения транспортной задачи, нахождения минимального остовного дерева для проверки эффективности алгоритмов управления очередями заданий в кластерных вычислениях. Приведен интерфейс программных стендов и работа с ними, которые применяются для подтверждения теоретических выводов.

В заключении представлены основные результаты и выводы по диссертационной работе.

В приложении приведены акты об использования результатов работы, свидетельства об официальной регистрации программ для ЭВМ.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Аль-хулайди Абдулмаджид Ахмед Галеб

4.6.Выводы

1. Разработан комплекс программ, для исследования алгоритмов управления очередями заданий в кластерных системах. А также разработаны параллельные программы для решения транспортной задачи и задачи нахождения минимального остовного дерева на кластерных системах, с помощью которых проведена проверка эффективности предложенной модели и алгоритмов управления очередями заданий в кластерных системах, реализация которых подтвердила их эффективность.

2. Проведены экспериментальные исследования, разработанной модели и алгоритмов управления очередями заданий, на основе транспортной задачи. Испытания эффективности модели и алгоритмов управления очередями заданий на кластерном пакете МР1/МР1СН и на улучшенном кластерном пакете МР1/МР1СНКЕ\¥, содержащем модель и алгоритм управления очередями заданий, на основе транспортной задачи показали, что при увеличении числа процессов от 20 до 40, производительность увеличивается в 1,24 раз, для размерности матрицы 1000x1 ООО,а на основе задачи нахождения минимального остовного дерева показали, что при увеличении числа процессов от 20 до 60, производительность увеличивается в 1,29 раз, при количестве вершин, равном 10000. Результаты проведенных экспериментов показали, что среднее время выполнения параллельного алгоритма решения транспортной задачи на МР1/МР1СН1Ч[Е\¥ меньше (по крайней мере, на 17,74%) нахождения минимального остовного дерева, на МР1/МР1СНТч[Е\У меньше (по крайней мере, на 15,65% ) по сравнению, с МР1/МР1СН. Это позволяет в совокупности получить более высокие показатели эффективности параллельных вычислений, обеспечить ускорение решения задач в кластерных системах и уменьшить время ожидания заданий в очереди.

3. Проведенное экспериментальное исследование, предложенной модели кластера МР1/МР1СН, для управления очередями заданий в

142 планировщике Maui показало, что при увеличении числа ядер от 30 до 40, производительность увеличивается в 1,37 раз при расчете матрицы размерности 1000x1000. Проведена сравнительная характеристика времени ожидания заданий, при модельном и реальном экспериментах. Экспериментальная проверка установила, что погрешность, полученная при использовании модели управления очередями заданий, для параллельного алгоритма решения транспортной задачи, не превышает 8,87% .

4. Проведена сравнительная характеристика экспериментальной и теоретической оценок параллельных алгоритмов, для решения транспортной задачи и задачи нахождения минимального остовного дерева, при проверки предложенных алгоритмов управления очередями. Экспериментальная проверка показала, что максимальное ускорение разработанного параллельного алгоритма, на основе метода Борувки, составляет 1,32 раз, по отношению к известному параллельному алгоритму Прима, ускорение которого составляет 1,29 раз. Кроме этого, эксперимент показал, что для больших размерностей транспортных задач(например ,размерность матрицы 1000x1000) получается значительный выигрыш вычислений: до 130%, при поиске опорного плана, и до 150%, при нахождении оптимального решения транспортной задачи. Проведено сравнение экспериментального и теоретического времени работы параллельного алгоритма, нахождения опорного плана транспортной задачи ,которое установило, что погрешность определения времени выполнения параллельного алгоритма поиска опорного плана не превышает 15% .

5. Предложенные модель и алгоритмы управления очередями заданий, для организации работы вычислительного кластера, позволяют достичь следующих улучшений в функционировании кластера: значительно снизить ресурсы, в ходе работы планировщика, за счёт применения специального алгоритма планирования запуска заданий; снизить расход

143 процессорного времени, при преждевременной остановке заданий за счёт постоянной корректировки резервирования ресурсов, исходя из обновлённой информации о занятости узлов; устранить проблемы старвации (зависания) заданий, требующих большого количества ресурсов в очереди, с помощью учёта времени задержки каждого из заданий в очереди и осуществления соответствующих перестановок; обеспечить равномерную загрузку узлов кластера путём мониторинга загрузки каждого из вычислительных узлов заданиями. В совокупности, данные преимущества позволяют достичь большей производительности вычислений на кластере, что было подтверждено в результате проведенного эксперимента.

Разработаны алгоритмы обслуживания очередями заданий, при параллельных вычислениях, в кластерных вычислительных системах: алгоритм распределения ресурсов между процессами и алгоритм управления порядком запуска заданий, которые позволяют значительно снизить ресурсы в ходе работы планировщика за счёт применения специального алгоритма планирования запуска заданий и снизить расход процессорного времени при преждевременной остановке заданий за счёт постоянной корректировки резервирования ресурсов и др. Испытания эффективности модели и алгоритмов управления очередями заданий, на кластерном пакете МР1/МР1СН и на улучшенном кластерном пакете

МР1/МР1СН1чПЕ\У, содержащем модель и алгоритм управления очередями заданий, на основе транспортной задачи, показали, что при увеличении числа процессов от 20 до 40, производительность увеличивается в 1,24 раз для размерности матрицы 1000x1 ООО,а на основе задачи нахождения минимального остовного дерева показали, что при увеличении числа процессов от 20 до 60, производительность увеличивается в 1,29 раз при количестве вершин равном 10000.

Результаты проведенных экспериментов показали, что среднее время выполнения параллельного алгоритма решения транспортной задачи на

МР1/МР1СНКЕ\¥ меньше (по крайней мере, на 17,74%), а нахождения минимального остовного дерева на МР1/МР1СНЫЕ\¥ меньше (по крайней мере, на 15,65% ) по сравнению с МР1/МР1СН.

Разработаны параллельные алгоритмы и их теоретические оценки нахождения минимального остовного дерева, на основе метода Борувки; опорного плана в транспортной задаче, на основе метода Фогеля; оптимального решения транспортной задачи, на основе метода потенциала, для проверки предложенных алгоритмов управления очередями заданий в кластерных системах и многопроцессорной среде, позволяющих достигать значительной величины ускорения, в том числе и при использовании нескольких тысяч процессоров. Теоретически

146 показано, что зависимость времени поиска штрафа, по методу Фогеля, от размерности задачи, близка к линейной. При большой размерности задачи от т=500,получаем увеличение времени поиска штрафа. При увеличении количества узлов от 1 до 7, время поиска штрафа, сокращается в 6 раз. Дальнейшее увеличение количества узлов не эффективно - при изменении от 7 до 20, получается только двукратный выигрыш производительности в 12 раз. Дальнейшее увеличение количества узлов приводит к увеличению затрат времени.

5. Получена теоретическая оценка вычислительной сложности параллельного алгоритма ,на основе метода Фогеля, которая составляет О(w2)- На основе данной оценки показано, что сокращение времени выполнения параллельного алгоритма для задач размерности т=500, при количестве узлов q=20, примерно в 2 раза меньше, чем при q= 10.Далее время расчета сокращается, не пропорционально количеству узлов. Это вызвано возрастанием количества пересылок между вычислительными узлами; время передачи данных (время пересылки) в кластерной локальной сети в 500 раз меньше, чем время передачи данных в GRID сети. Получена теоретическая оценка вычислительной сложности параллельного алгоритма нахождения минимального остовного дерева, на основе метода Борувки, в кластерных системах, 2 которая составляет, 0(").

Получена теоретическая оценка оптимального количества узлов в кластерных и GRID системах, через нахождение опорного плана транспортной задачи, в зависимости от количества строк(столбцов) и времени элементарной обработки. Полученная оценка позволяет определять не только оптимальное число узлов (процессоров), что сокращает используемые ресурсы, но и, решать задачу в оптимальные сроки.

Приведены сравнительные характеристики экспериментальных и полученных автором теоретических оценок, разработанных параллельных алгоритмов для решения транспортной задачи и задачи нахождения минимального остовного дерева, при проверки предложенных алгоритмов управления очередями. Максимальное ускорение разработанного параллельного алгоритма, на основе метода Борувки, составляет 1,32 раз, по отношению к известному, параллельному алгоритму Прима, ускорение которого составляет 1,29 раз. Кроме этого, для больших размерностей транспортных задач(например ,размерность матрицы 1000x1 ООО),получается значительный выигрыш вычислений до 130%, при поиске опорного плана, и до 150% , при нахождения оптимального решения транспортной задачи. Проведено сравнение экспериментального и теоретического времени работы параллельного алгоритма нахождения опорного плана транспортной задачи , которое установило, что погрешность определения времени выполнения параллельного алгоритма поиска опорного плана, не превышает 15% .

6. Разработан комплекс программ для исследования алгоритмов управления очередями заданий в кластерных системах. А также, разработаны параллельные программы для решения транспортной задачи и задачи нахождения минимального остовного дерева на кластерных системах, с помощью которых проведена проверка эффективности предложенной модели и алгоритмов управления очередями заданий, в кластерных системах, реализация которых подтвердила их эффективность. Полученные теоретические и экспериментальные результаты позволяют сделать вывод о достижении более высоких показателей эффективности производительности вычислений за счет распараллеливания вычислений, обеспечения ускорения решения задач и уменьшения времени ожидания заданий в очереди в кластерных системах.

Список литературы диссертационного исследования кандидат технических наук Аль-хулайди Абдулмаджид Ахмед Галеб, 2011 год

1. Norros I. A storage model with self-similar input /1. Norros //Queueing Systems AndTheir Applications. 1994. -N16. -P.369-387.

2. Kelly P.P. Analysis in Queueing Systems: Brownian models, cut constraints and resource pooling/ Kelly P.P. // Queueing Systems., 1993. N13. - P. 47-86.

3. Limic V. On the behavior of LIFO preemptive resume queues in Heavytraffic/ V. Limic // Elect. Comm. in Probab. 1999. - N4. -P. 13-27.

4. Kamp A. v., S. Schuster. Metatool 5.0: fast and flexible elementary modes analysis/A. v. Kamp , S. Schuster//Bioinformatics. 2006. -N22. -P. 1930-1931.

5. Chen L. Parallel simulation by multi-instruction, longest-path Algorithms/ L. Chen // Queueing Systems. 1997. -N 27. -P. 37-54.

6. Karatza H. D. A Simulation Model of Backfilling and I/O Scheduling in a Partitionable Parallel System/ Karatza H. D. //Proceedings of Winter Simulation Conference ACM, IEEE, SCS, Orlando,Florida, December,Orlando ,- 2000. -P. 496-505.

7. Flynn M. Some Computer Organisations and Their Effectiveness/ M. Flynn // IEEE Transactions on Computers. -1972. -N 9. -P.948-960.

8. Wang P., Dual-Direction Backfilling Algorithm for Job Scheduling/P. Wang, Xu Liu, Dan Meng, Jianfeng Zhan, Bibo Tu //HPC Asia conference. Kaohsiung, Taiwan. -2009. P.88-102.

9. Ward W., Scheduling Jobs on Parallel Systems Using a Relaxed Backfill Strategy/ W. Ward, L. Carrie //8th International Workshop on Job Scheduling Strategies for Parallel Processing, Spinger-Verlag. -2002. LNCS 2537. - P.88-102.

10. Hockney R. Parallel Computers: Architecture and Performance/ RHockney // Proc. Of Int. Conf. Parallel Computing. 1986. -N 85. - P.33-69.

11. Lifka D. The ANL/IBM SP scheduling system. In Job Scheduling Strategies for Parallel Processing / D. Lifka //Springer-Verlag, Lect. Notes Comput. -1995.-N. 949.-P. 295-303.

12. Mu'alem A. W Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling/ A. W. Mu'alem , D. G. Feitelson // IEEE Trans. Parallel Distributed Syst.-2001.-N12(6). -P. 529-543.

13. Maui scheduler. Cluster Resources Электронный pecypc.-2011. Режим доступа:http://www.supercluster.org/maui//, свободный.

14. Streit A. On Job Scheduling for HPC-Clusters and the Scheduler. /А. Streit //TR-00101, PC2 Paderborn Center for Parallel Computing, PaderbornUniversity. -2001. Электронный ресурс. - Режим доступа http://www.fz-iuelich.de/isc/vsgc/pub/strcit2001-QJS.pdf

15. Wiseman Y. Paired Gang Scheduling/ Y. Wiseman , D.G. Feitelson // Proc. Jerusalem Parallel Distributed Processing Symp., Nov. Jerusalem . -2001. -P. 218-222.

16. B. B Zhou .: Gang Scheduling with a Queue for Large Jobs/ Zhou B. B., Brent R. P.// IEEE International Parallel and Distributed ProcessingSymposium. -(2001).-N12.-P. 225-233.

17. Frachtenberg E. J.: Flexible CoScheduling: Mitigating Load Imbalance and Improvi Utilization of Heterogeneous Resources/ Frachtenberg E., Feitelson D.G. // 17th International Parallel andDistributed Processing Symposium. -2003.-39: 345-456.

18. Hockney R. Classification and Evaluation of Parallel Computer Systems /Hockney R.//lecture Notes in Computer Science. 1987.- N 295. - P. 13-25.

19. Chapin S.J. et all: Benchmarks and Standards for the Evaluation of Parallel Job Schedulers/ S.J. Chapin // Job Scheduling Strategiesfor Parallel Processing. -1999.-V.1234.-P. 67-90.

20. Goes L. F.: Proposal and Development of Reconfigurable Parallel Job Scheduling Algorithm/ L. F. Goes, W. Martins// Master' s Thesis. Belo Horizonte, Brazil(in Portuguese). 2004. -V.29.P. 345-456.

21. Low, Y.H. et al., Survey of Languages and Runtime Libraries for Parallel Discrete-Event Simulation//IEEEComputer Simulation. -1999.-N3. -P. 170-186.

22. Anderson, Cobb E. An experiment in public-resource computing / Anderson, Cobb E. // Comm. of the ACM. -2002. V. 45, No. 11. - P. 56-61.

23. Zhou B. B. An Efficient Resource Allocation Scheme for Gang Scheduling/ B.

24. B. Zhou, P. Mackerras, Johnson C. W., Walsh, D.//lst IEEE Computer Society International Workshop on Cluster Computing. Toqi 1999. - P. 18-194.

25. Martin R.D. Robust estimation via stochastic approximation/ R.D. Martin &

26. Анализ алгоритмов обслуживания очередей в сетях с поддержкой «Качества обслуживания» (QoS) / Е.Б.Фишман // Качество. Инновации. Образование. -2006. -№6. С.63- 71.

27. Федодеев Д. , Алгоритмы управления очередями / Д. Федодеев // Журнал сетевых решений/LAN. 2007. - Т. 13 (137). - С.26-31.

28. Климов, Г.П. Приоритетные системы обслуживания с ориентацией/ Г.П. Климов, Г.К.Мишкой.-М.: МГУ, 1979.-222 с.

29. Столлингс В. Современные компьютерные сети: Энциклопедия. - 2-е изд- СПб.: Питер. - 2003. - 782 с.

30. Таненбаум Э. Компьютерные сети. Классика computer science. 4-е / Э. Таненбаум. -4-е изд. -СПБ. Литер. 2008. - 992 с.

31. Меликов А.З. Приоритетное обслуживание в узлах коммутации сетей АТМ / А.З. Меликов, В.Ш. Фейзиев // Автоматика и вычислительная техника. -Харьков, 2005. Т.З. - С.79.

32. Kroner Н. Priority management in ATM switching nodes / H. Kroner, G. Hebuterne , P. Boyer, A. Gravey // IEEE J. Select. Areas Commun. 1991. -Vol.9, No.3.-P.418-427.

33. Антонов А. В. Оценка эффективности параллельных алгоритмов/ А. В. Антонов // Антикризисное управление в России в современных условиях: материалы VI Всерос. науч.-практ. Молодеж. конф. М.: Изд-во МГТУ им. Н. Э. Баумана, 2004. - С. 21- 22.

34. Гугель Ю.В. Характеристики параметров "Качество обслуживания" опорной инфраструктуры научно-образовательной сети / Ю.В. Гугель // Информатизация образования и науки. 2009. - Вып. 4. - С. 66-75.

35. Вегешна Ш. Качество обслуживания в сетях IP/ Ш. Вегешна. М.: Изд-во. Вильяме, 2003. -368с.

36. Коваленко В.Н. Методы и алгоритмы управления параллельными заданиями в гриде с ресурсами в форме кластеров/ В.Н. Коваленко, Д.А. Семячкин // Вестник Южного научного центра РАН. -2008. № 3(4). -С. 23-34.

37. Таненбаум Э. Компьютерные сети. Классика computer science/ Э. Таненбаум. 3-е изд. - СПБ.: Питер, 2002. - 829 с.

38. Аль-хулайди А. А. Распределенные вычисления (Кластерные вычисления) с использованием пакета параллельного программирования МР1/ А. А. Аль-хулайди //Современные наукоемкие технологии. (Электронный журнал). -2010.-№ 4-С. 82-83.

39. Аль-хулайди A.A. Разбиение кластерного пакета MPI/MPICH на классыфункций / А. А. Аль-хулайди // Российская Академия Естествознания

40. Научный электронный архив академии естествознания (Свидетельства от153

41. Кутепов В.П. Организация параллельных вычислений на системах / В.П. Кутепов. М.: Изд-во МЭИ, 1988. - 64 с.

42. Ластовецкий A.JI. Технологии параллельного программирования шрС Электронный ресурс. -Режим доступа: http://vvww.parallel.m/techympc/mpC-rus.html, свободный.

43. Johnston, W. Realtime Widely Distributed Instrumentation Systems. In Foster, I. and Kesselman, C. eds. //The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann. -1999. -P. 75-103.

44. Nick J.M. S/390 Cluster Technology: Parallel Sysplex/ J.M Nick , B.B. Moore //IBM Systems Journal. -1997. -36 (2). -P. 172-201.

45. Hockney R. Parallel Computers: Architecture and Performance/ R. Hockney // Proc. of Int. Conf. Parallel Computing'85. 1986. -P.33-69.

46. Livny M. High-Throughput Resource Management/ M. Livny, C. Kesselman //The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann. -1999.-P. 311-337.

47. Casanova H. A Network Server for Solving Computational Science Problems./ H. Casanova , J. Dongarra // International Journal of Supercomputer Applications and High Performance Computing. 1997. -N.ll (3). -P. 212223.

48. Foster I. Globus: A Metacomputing Infrastructure Toolkit /1. Foster., Kesselman // Intl J. Supercomputer Applications.-1997.-N.11.-P.115-128.

49. Robin Calkin. Portable programming with the parmacs message-passing library / Robin Calkin, Rolf Hempel, Hans-Christian Hoppe, Peter Wypior//Parallel Computing. -1994. 20(4). -P.615-632.

50. Maui scheduler: Электронный ресурс. Режим доступа: http://www.supercluster.org/maui Last Modified on 09/06/2003, last accessed in April 2009, свободный.

51. Foster I. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment /1. Foster, J. Geisler, W. Nickless, W.Smith// Proc. 5th IEEE Symposium on High Performance Distributed Computing. 1997. -P. 562-571.

52. Владимиров Д. Кластерная система Condor/ Д. Владимиров // Открытые системы — 2000. -№7-8. -С.20-26.

53. Ahmar Abbas. Grid Computing/ Ahmar Abbas //Charles River Media. 2004. -P.110-117.

54. Michael J. Brim How to install an OSCAR cluster / J. Brim Michael // The Open Cluster Group. -2001 Электронный ресурс. Режим доступа: http://www.csm.ornl.gov/oscar/papers.html, свободный.

55. Joseph D. Sloan, High Performance Linux Clusters With Oscar, Rocks, Open Mosix & Mpi/ D. Sloan Joseph // Fast results on terabytes of data. 2004. -P.368.

56. Robert L. Grossman, Compute and storage clouds using wide area high performance networks/ Robert L. Grossman, Yunhong Gu, Michal Sabala, Wanzhi Zhang //Future Generation Сотр. Syst. 2009 . -N.25(2). -P. 179-183.

57. Wunderlich, J.T. Functional verification of SMP, MPP, and vector-register supercomputers through controlled randomness/ J.T. Wunderlich//Computer Engineering Program . -2003. -P.l 17-122.

58. Buyya Rajkumar Buyya. High Performance Cluster Computing: Architecturesand Systems// Prentice Hall PTR. -NJ, (USA), 1999. V. 1. -P.227-233.

59. Al-khulaidi Abdulmajed Ahmed Parallel computing problems while using MPI / MPICH cluster package// Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симпозиума/-ДГТУ-Ростов н/Д: Издательский центр ДГТУ,2011.

60. Blumofe R. Scheduling multithreaded computations by work stealing/ R. Blumofe, C. Leiserson // 35th Annual IEEE Conf. on Foundations of Computer Science. FOCS'94. Santa Fe, (New Mexico). -1994. -P. 356-368.

61. Casavant T. A taxonomy of scheduling in generalpurpose distributed computing systems/ T. Casavant, J. Kuhl // IEEE Trans. О Software Engineering. -1988. -V. 14.-No 2.-P. 141-154.

62. Feitelson D.G. A Survey о Scheduling in Multiprogrammed Parallel Systems/ D.G. Feitelson // Research Report RC 19790 (87657). IBM T. J. Watson ResearchCenter. -1994. -P. 171.

63. Streit A. On Job Scheduling for HPC-Clusters and the dynP Scheduler / A. Streit // Lect. Notes Comput.Sci Berlin,- 2001. -V. 2228. - P. 58-67.

64. Brando T. J. Comparing DCE and CORBA / T. J. Brando // Technical Report MP,MITRE. -1995. -P.93-95.

65. Сайт проекта TORQUE. Электронный ресурс. Режим доступа : http://www.clusterresources.com/pages/products/torque-resource-manager.php, свободный.

66. Сайт проекта TORQUE Resource Manager^eKTpoHHbift ресурс.- Режим доступа: http://en.wikipedia.org/ wiki/TORQUE ResourceManager , свободный.

67. Bharucha-Reid А. Т., Elements of the theory of Markov processes and their applications/ A. T. Bharucha-Reid // New York, McGraw-Hill

68. Book Co. (РЖМат, 1961, 4B29 К). -I960,- XI. -1960. -N468. -P. 11-50.

69. Boyer R. H. An integro-differential equation for a Markov process.

70. R. H. Boyer //Industr. and Appl. Math-1959. V7, № 4. - P. 473^186.

71. Clarke A. B. Waiting line process of Markov type / A. B. Clarke // Ann. Math Statistics. 1956. - V. 27, № 2. - P. 452 -459.

72. Udagawa K. Note on a relation between the Markov chain and the birth and death process/ K. Udagawa // J. Operat. Res. Soc. 1арап(РЖМат, 1962, 7B21). 1961. - V. 4, №1.-P. 27-45.

73. Vere-Jones D., Geometric ergodicity in denumerable Markov chains// Quart. J. Math.- 1962,- V.13, №49. P.7-28.

74. Ивченко Г.И., Коваленко И.Н. Теория массового обслуживания/ Г.И. Ивченко, В.А. Каштанов. — М.:Высш. Шк., 1982. — 256 с.

75. Гнеденко Б.Б. Введение в теорию массового обслуживания/ Гнеденко Б.Б., И.Н. Коваленко. — М.: Наука, 1966.-255 с.

76. Сейфулин А.И. Ситуационное моделирование полиграфических процессов:дисс. Канд. Техн. Наук/ А.И. Сейфулин. — М., 2002.

77. Кофман А. Массовое обслуживание. Теория и приложения/ А. Кофман , Р. Крюон — М.:Мир, 1965. — 304 с.

78. Клименок В.И. Теорема Руше в задаче нахождения стационарного распределения квазитеплицевой цепи Маркова / В.И. Клименок // Автоматика и вычислительная техника. 1998. -№1. - С.23-29.

79. Дудин А.Н. Системы массового обслуживания с коррелированными потоками/ А.Н. Дудин, В.И. Клименок Минск: БГУ, 2000. - 175 с.

80. Климов Г.П. Стохастические системы обслуживания/ Г.П. Климов М.: Наука, 1966.-244 с.

81. Кормен Т. Алгоритмы: построение и анализ/ Т. Кормен, Ч. Лейзерсон, Р. РивестМ. :МЦНМО,2001.-960с.

82. Альфред Ахо Структуры данных и алгоритмы/ Ахо Альфред, Э. Джон, Д. Ульман М. - СПб - Киев: Вильяме, 2000 г. - 384 с.

83. Курейчик В.М. Дискретная математика. Ч.З. Оптимизационные задачи на графах/ В.М. Курейчик. Таганрог: Изд-во ТРТУ, 1998. - 296 с.

84. Кормен Т. X. Алгоритмы: построение и анализ/ Т. X. Кормен , Ч. И. Лейзерсон , Р. Л. Ривест, К. Штайн- 2-е изд.— М.: Вильяме, 2005. — 1296 с.

85. Graham. R. L. On the history of the minimum spanning tree problem. / R. L. Graham and P. Hell. // Annals of the History of Computing. 1985. - N 7(1).-P. 43-57.

86. Chung S. Parallel implementation of Boruvka's minimum spanning tree algorithm. / S. Chung, A. Condon // Parallel Processing Symp. (IPPS'96). -1996.-P. 302-315.

87. Chazelle. B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity / B. Chazelle// Journal of the ACM. 2000. -N47. - P. 10281047.

88. David R. Karger. A randomized linear-time algorithm to find minimum spanning trees/ David R. Karger, Philip N. Klein, and Robert E. Tarjan // Journal of the ACM. -1995. N.42 (2). -P. 321-328.

89. King V. A simpler minimum spanning tree verification algorithm/ V. King //Algorithmic. -1997. -18. -P. 263-270.

90. Ш.Бурков В.H. Прикладные задачи теории графов / В.Н. Бурков, И.А. Горгидзе, С.Е. Ловецкий Тбилиси: Мецниереба. - 1974. - 234 с.

91. Алексеев А.О. Транспортная задача по критерию времени при ограниченном количестве транспортных средств/ А.О. Алексеев // Математические методы оптимизации и управления в сложных системах /-КГУ. Калинин,- 1984. - с. 60- 65.

92. Математическое моделирование экономических процессов на железнодорожном транспорте / А.Б. Каплан, А.Д. Майданов, A.M. Макарочкин и др. М.: Транспорт. -1984. -256 с.

93. Кузнецов Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. М.: Высш. Шк,1976. -352с.

94. Высшая математика: Математическое программирование : Учеб. / A.B. Кузнецов, В.А.Сакович, Н.И. Холод. Минск.: Высш.шк., 1994. - 286 с.

95. Барский А. Б. Параллельное программирование/ А.Б. Барский СПб.: Бином, 2007. - 504 с.

96. Северин А. А. Исследование эффективности реализации численных методов на кластерах персональных ЭВМ/ А. А. Северин Минск, 2005.

97. Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации/ В. И. Хохлюк. М., 1987. - 224с.

98. Каныгин Т.П., Месхи Б.Ч., Соболь Б.В. Методы оптимизации / Г.И Каныгин., Б.Ч. Месхи , Б.В. Соболь — М.: Феникс, 2009 . — 384 с.

99. Аппроксимация Электронный ресурс. -Режим доступа: http://ru.wikipedia.org/wiki/AппpoкcимaцияПaдe (дата обращения 11.2.2011 г), свободный.

100. Грид Электронный ресурс. http://ru.wikipedia.org/wiki/rpHa (дата обращения 23.03.2011 ), свободный.

101. Аль-хулайди A.A. Использование метода формульного анализа масштабируемости в кластерных сетях/ A.A. Аль-хулайди // Математические методы в технике и технологиях-ММТТ-23: сб.тр. XXIII Междунар. науч. конф/ СГТУ.- Саратов, 2010. -Т.9. -С. 173-174.

102. Аль-хулайди A.A. Разработка алгоритмов управления заданиями при организаций параллельных вычислений в кластерных вычислительных системах/ A.A. Аль-хулайди , Ю.О. Чернышев// Вестник ДГТУ. -2011. -Т.11,№5(56) С.715 - 722.

103. Аль-хулайди A.A. Разработка параллельного алгоритма нахождения оптимального решения транспортной задачи для выполнения на кластере/ A.A. Аль-хулайди, Ю.О. Чернышев // Инженерный вестник Дона .

104. Электронный научно-инновационный журнал, 2011. №2. - № гос.161регистрации0421100096. Электронный журнал.: Режим доступа: http://ivdon.ru/magazine/latest/n2y2011/445/

105. Аль-хулайди Абдулмаджид Ахмед. Реализация функций кластерного пакета MPI/MPICH / Абдулмаджид Ахмед Аль-хулайди // Российская Академия Естествознания: Научный электронный архив академии естествознания (Свидетельства от российской

106. Академия Естествознания) -URL:http://econf.rae.ru/pdf/201 l/08/525.pdf

107. Коваленко В.Н. Метод опережающего планирования для грид/ .Н.Коваленко, Е.И.Коваленко, Д.А.Корягин, Э.З.Любимский // Ордена Ленина институт прикладной математикой имени М.В.Келдыша. Москва. -2005.-33с.

108. Al-khulaidi A. A. Algorithm development of resource allocation between processes for parallel systems/ A. A. Al-khulaidi //Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симп. /ДГТУ- Ростов н/Д,2011. С.234 - 237.