ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 5, с. 58-73
КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 681.3.053:681.32.007.5
ИНТЕЛЛЕКТУАЛЬНОЕ УПРАВЛЕНИЕ ПРОЦЕССАМИ И ЗАГРУЖЕННОСТЬЮ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ*
© 2007 г. В. П. Кутепов
Москва, МЭИ Поступила в редакцию 21.03.07 г.
Рассматриваются методы и алгоритмы адаптивного управления процессами и загруженностью в компьютерных системах.
Введение. Большие перспективы, которые открывают вычислительные системы (ВС) в решении сложных научно-технических задач и управлении, наметившийся в последнее время качественный скачок в расширении их производства (см. TOP-500 http://www.top500.org) возвращают исследователей и разработчиков в этой области к старым хорошо известным и пока нерешенным проблемам [1]. Главные из них касаются поиска в некотором смысле универсальных языков, методов и сред параллельного и распределенного программирования и построения систем управления вычислительными системами.
Если для первой проблемы в настоящее время найдено более или менее приемлемое практическое решение (напомним о MPI для кластеров, о средствах нитевого программирования для SMP-сим-метричных мультипроцессорных систем [2], наших разработках систем параллельного программирования [3-5]), то задача управления вычислительными системами не имеет сколь-нибудь заметного продвижения в своем решении.
По сути, предполагается, что пользователь не только должен разработать программу, но и "отобразить" ее на конкретную ВС, чтобы достичь желаемого эффекта в части времени выполнения программы и использования вычислительных ресурсов. Например, разработчики суперсистемы фирмы IBM, состоящей из 8192 узлов и установленной в Ливермоской лаборатории, рекомендуют так организовать ее работу, чтобы на узлах были более или менее равные с точки зрения вычислений задачи, а обмены между узлами минимальны. Если для сеточных задач (например, численное решение уравнений в частных производных) это можно как-то сделать, то для задач, имитирующих процессы со сложными и непредсказуемыми взаимодействиями, эта рекомендация остается на уровне призыва.
Решение проблемы управления процессами в ВС наталкивается на принципиальную сложность,
* Работа выполнена при финансовой поддержке РФФИ (проект < 06-01-00817).
связанную с идентификацией их поведения. Один путь преодоления этой трудности состоит в рассмотрении поведения процессов как случайных стохастических процессов с определенными параметрами. Однако даже для последовательных программ наши знания об их поведении весьма ограниченны, в частности разработка опережающего устройства машин STRETCH, а затем БЭСМ-6 заставила ее создателей собрать необходимую статистику, показывающую, что при выполнении последовательных программ в среднем каждая десятая команда представляет команду перехода, из десяти команд три являются независимыми.
Другая возможность - построение в некотором смысле адаптивных схем управления, базирующихся на использовании качественных моделей поведения программ, известных общих законах, касающихся обслуживания процессов и полученных в рамках теории массового облуживания. Именно этому обязано появление в названии статьи прилагательного "интеллектуальное".
Известно, например, какую важную роль сыграли многоуровневые адаптивные схемы поквантово-го циклического облуживания процессов в многопользовательских системах с разделением времени. Задача состояла в том, чтобы обеспечить приоритет в обслуживании "коротких" по сложности процессов. Способность указанных схем облуживания процессов достаточно точно дифференцировать их по сложности, а также подбор соответствующих значений квантования для очередей разных уровней позволили успешно решить проблему. Эта организация облуживания процессов по-прежнему используется в компьютерах для того, чтобы достичь эффективного их взаимодействия с пользователем при решении задач.
Можно привести и другие примеры успешного применения адаптивных эвристик и общих знаний о поведении программ в решении задач управления многопрограммной работой в системах со страничной памятью [6-9]. В частности, достаточно точное прогнозирование поведения программы в процессе
ее выполнения может основываться на динамическом обнаружении циклически повторяющихся участков, что было успешно применено в управлении многопрограммной работой в системах со страничной памятью [8, 9]. Полученный эффект -уменьшение до 50% частоты обменов между оперативной и дисковой памятью и увеличение до 30% производительности многопрограммной работы (количества программ выполняемых в единицу времени).
Однако проблема эффективного управления процессами в больших компьютерных системах, насчитывающих десятки тысяч узлов (ВС ASCI WHITE, установленная в Ливермоской лаборатории, содержит 65536 узлов), настолько сложна, что помимо чисто управленческих решений она требует согласования архитектуры ВС и ее управления, учитывающего ограничения коммуникационных средств, возможность масштабирования, динамического реконфигурирования в процессе ее функционирования.
Цель статьи - изложить развиваемый нами подход к управлению большими компьютерными системами [1] и реализуемый в наших проектах создания систем параллельного программирования для кластерных систем [3-5].
1. Архитектурные особенности современных ВС. Сегодня мы имеем дело со следующими общими формами организации ВС:
многомашинной, предполагающей объединение посредством коммуникаций множества компьютеров, взаимодействующих друг с другом посредством обмена сообщениями,
многопроцессорной, ориентированной на использование общей памяти и множества процессоров, взаимодействующих друг с другом либо путем разделения общих переменных, либо путем обмена сообщениями через специально организуемые и защищенные семафорами так называемые почтовые ящики,
смешанной, когда в ВС присутствуют обе указанные выше организационные формы.
Типичными примерами современных многомашинных ВС с разделенной памятью являются системы фирмы IBM [10]. К этому типу организации относятся кластеры (сошлемся на примеры отечественных кластеров МВС 1000, СКИФ - производство России совместно с Республикой Беларусь). Различие между этими системами состоит в том, что в продуктах фирмы IBM используются более мощные коммуникации на уровне групп узлов (по 16 компьютеров), представляющие собой переключательные матрицы и позволяющие каждому компьютеру группы прямо связываться через линию связи с любым другим компьютером группы. У кластеров, как правило, подобная возможность отсутствует, все взаимодействия между компьютерами осуществляются по единому сценарию через
общие сетевые коммуникации. Ни у первой, ни у второй организационной структуры ВС не предусмотрены специальные технические решения, учитывающие особенности взаимодействия компьютеров ВС по управлению и данным и направленные на эффективную реализацию взаимодействий первого типа [1]. Считается, что для управляющих взаимодействий достаточна общая коммуникационная среда.
Важная проблема масштабирования для таких систем решается достаточно просто и единообразно путем подсоединения новых компьютеров на общие коммуникации (у кластеров) либо путем введения дополнительных переключательных схем связи (например, у систем SP). В любом случае увеличение масштаба системы означает увеличение в среднем времени взаимодействия между компьютерами ВС. Геометрия размещения стоек с компьютерами в пространстве, так же как и структура связей между компьютерами, могут сильно влиять на время межкомпьютерных взаимодействий (ограничения: длина линии связи и максимальная скорость передачи сигнала не более скорости света пока не преодолены).
Помимо того, что время взаимодействия между компьютерами зависит от расстояния между ними, остается еще задержка, которую называют латент-ностью (время на организацию передачи данных нулевой длины - пустого пакета) и которая сегодня даже у самых современных сетевых коммуникаций порядка нескольких микросекунд. Типичными примерами ВС с общей оперативной памятью являются системы фирмы Hewlett Packard и Convex SPP [11], у которых группа от 16 до 32 процессоров работает со своей общей памятью, используя высокоскоростной коммутатор, а масштабирование системы осуществляется путем объединения групп через более медленные тороидоидальные структуры коммуникации. При сравнении обеих организаций ВС очевидно, что ВС с раздельной памятью проще масштабировать, а у ВС с общей памятью больше возможностей поддерживать мелкозернистый параллелизм, по крайней мере, на уровне группы процессоров.
Многие известные фирмы (INTEL, SUN, IBM, AMD, др.) перешли в настоящее время к широкому производству так называемых многоядерных ВС с общей памятью. По сути, это многопроцессорные ВС (SMP) с общей памятью. Управление такими ВС осуществляет одна операционная система (ОС), поддерживающая нитевое (multithreading) программирование, представляющее ничто иное, как приукрашенные для пользователя средства ОС, предназначенные для порождения процессов, организации их взаимодействия и синхронизации. Ограниченная пропускная способность оперативной памяти является серьезным препятствием при их масштабировании.
Естественное объединение обоих вариантов построения ВС приводит к ВС с многопроцессорными узлами. При этом решаются проблемы масштабирования, объединения в рамках одной системы возможности поддерживать мелкозернистый параллелизм внутри узлов и крупнозернистый на уровне узлов. Очевидно, что по этому пути будет происходить развитие ВС в ближайшие годы.
2. Организационные формы управления и их связь с архитектурой ВС. Как мы уже говорили во Введении, проблема управления большими компьютерными системами сегодня далека от сколь-нибудь удовлетворительного практического решения [1]. По сложившейся традиции программист, разрабатывая параллельную программу, должен учитывать размер ВС (количество процессоров и компьютеров), регулировать зернистость параллелизма в программе и статически распределять ее фрагменты по компьютерам ВС. По сути, реально мы имеем дело с зависимым от архитектуры ВС программированием и "вручную" осуществляемым управлением. Иск
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.