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

• Автор: Аль-Мараят Бакер Ибрахим
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Курск
• Количество страниц: 147 с. : ил.

Введение
1. Анализ известных методов и алгоритмов планирования размещения задач в кластерных вычислительных системах.

1.1. Коммуникационные задержки в кластерных системах.

1.2. Понятие о размещении задач по процессорам параллельной системы

1.3. Связь между топологиями вычислительных систем и методами размещения задач

1.4. Классификация методов размещения

1.5. Анализ алгоритмов размещения задач и целесообразность их аппаратной реализации.

1.6. Выводы

2. Метод планирования размещения задач в кластерных вычислительных системах. .

2.1. Постановка задачи минимизации коммуникационной задержки в кластерных вычислительных системах
2.2. Формализованная постановка задачи размещения в кластерных вычислительных системах
2.3. Метод минимизации коммуникационных задержек в матричных базовых кластерных блоках
2.3.1. Постановка задачи.
2.3.2. Поиск гипотетической нижней оценки величины коммуникационной задержки
2.4. Алгоритм планирования размещения задач в кластерных вычислительных системах.
2.4.1. Этапы поиска решения
2.4.2. Операция парной перестановки столбцов и строк матрицы обмена информации
2.5. Перестановочный алгоритм планирования размещения задач.
2.6. Метод ускорения сходимости алгоритма.
2.7. Ускоренный алгоритм планирования размещения задач
2.8. Методика ускоренного выполнения процедуры планирования размещения задач
2.9. Выводы.
3. Моделирование процедур планирования размещения задач в кластерных системах
3.1. Описание программной модели процедур планирования
3.2. Методы моделирования.
3.3. Результаты исследования на модели эффективности алгоритма планирования размещения
3.4. Выводы.
4. Организация двухуровневого микропроцессорного акселератора планирования размещения задач
4.1. Принципы аппаратной реализации процедур планирования размещения
4.2. Двухуровневая структурная организация микропроцессорного акселератора планирования размещения задач
4.3. Алгоритмы функционирования акселератора
4.4. Производительность акселератора и функциональные схемы узлов его нижнего уровня.
4.5. Методика и быстродействующее устройство проверки качества размещения задач
4.6. Выводы
Заключение.
Библиографический список.
Приложение
Приложение
Приложение
Введение


Методика ускоренного программноаппаратного выполнения процедур планирования размещения задач по процессорам матричного базового блока кластерной системы, отличающаяся вынесением на аппаратный уровень акселератора вычислительно сложного этапа нахождения максимума задержек, образующихся в результате поисковой перестановки, а на программный уровень выполнения очередной перестановки, выделения минимума из последовательности названных максимумов по результатам ряда перестановок, принятия решений о целесообразности инициализации поиска или о прекращении поиска и отбрасывании заключительных неэффективных перестановок, позволившая многократно повысить скорость поиска субоптимального варианта размещения. Алгоритмы и структурнофункциональная организация двухуровневого микропроцессорного акселератора планирования размещения задач, отличающегося аппаратной реализацией нижнего уровня нахождения максимума коммуникационных задержек в виде пятиступенчатого конвейерного вычислительного устройства, содержащего трехступенчатый матричноконвейерный блок умножения, и позволившего повысить производительность по сравнению с программной реализацией. Методика и быстродействующее устройство оперативной проверки качества размещения задач, позволяющие уменьшить вероятность возникновения потерь в степени снижения коммуникационных задержек в результате последующей маршрутизации. Области возможного использования. Результаты диссертационной работы могут быть использованы в кластерных системах высокой готовности, например, в случае отказа одного из процессорных модулей, когда необходимо оперативное переразмещение задач. Применение разработанного акселератора позволит дополнительно снизить затраты времени на планирование размещения задач и организовать оперативное переразмещение задач перед рестартом восстанавливаемой системы без существенного снижения ее коэффициента готовности, а также уменьшить сложность алгоритмов последующей маршрутизации параллельной передачи сообщений в матричных многопроцессорных системах. Коммуникационные задержки в кластерных системах Кластерную систему можно рассматривать как комплекс физических и логических компонентов, которые вместе выполняют вычислительные и коммуникационные задачи . Физические компоненты устройства сети передают перемещают данные между памятью хоста и коммуникационной средой. Логические компоненты обеспечивают услуги для сбора сообщений, буферизации, форматирования, определения направления передачи и проверки ошибок. Физические компоненты определяют тип сети, которую нужно использовать , , , тип топологии сети полностью связанная, шинная, древовидная, кольцевая, смешанная и случайная, и тип среды связи витая пара, коаксиальные кабели, оптоволоконная, радио или спутниковая 7,8. Физические компоненты также определяют, как хост получает доступ к ресурсам сети. Логические компоненты определяют тип услуг связи переключение пакетов, переключение сообщений, круговое переключение, тип информации данные, голос, факсимиле, изображение и видео, методы управления централизованный иили распределенный, и тип протоколов связи 4,5,8. Типичная архитектура кластерной системы показана на рис. Vi i. I
Vi . Рис. Кластерные узлы рис. Промежуточное соединение i, показанное на рис. Таким образом кластер это связанный набор полноценных компьютеров, ис
пользуемый в качестве единого ресурса 8. Под словосочетанием полноценный компьютер понимается завершенная компьютерная система, включающая процессоры, память, подсистему вводавывода, а также операционную подсистему, приложения и т. Обычно для этого годятся готовые компьютеры, которые могут обладать архитектурой и даже . Словосочетание единый ресурс означает наличие программного обеспечения, дающего возможность пользователям, администраторам и даже приложениям считать, что имеется только одна сущность кластер. Например, система пакетной обработки кластера позволяет послать задание на обработку кластеру, а не отдельному компьютеру. Более сложным примером являются иерархические многоуровневые системы баз данных. У всех ведущих поставщиков систем баз данных имеются версии, работающие в параллельном режиме на нескольких машинах кластера.