Software & Systems

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

К важному классу ограничений относятся булевы ограничения, представляемые в виде систем булевых уравнений. Постановка задачи формулируется следующим образом: для нахождения решения системы булевых уравнений, которую без потери общности можно представить в виде одного булева уравнения f(x1, …, xn)=0, где xiÎB2 для всех , B2={0, 1},  – заданная функция своих аргументов, требуется найти одно или все решения уравнения либо сделать вывод, что решений не существует. Такие задачи, как правило, имеют тяжелые комбинаторные характеристики с высокой оценкой сложности, что заставляет вести поиск методов, наиболее эффективно действующих для отдельных (интересных с практической точки зрения) классов булевых систем, и одновременно повышать производительность решения систем булевых уравнений путем использования многопроцессорной техники.

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

В статье рассматривается инструментальный комплекс (ИК) РЕБУС, применяющий технологию синтеза булевых ограничений по содержательному описанию дискретной задачи, технологию распараллеливания решения системы булевых уравнений как на уровне узлов кластера, так и на уровне процессорных ядер, содержащей методы и средства автоматизации представления, накопления, модификации и обработки знаний (в частности, алгоритмы полного поиска) для решения задач в булевых ограничениях, и ориентированной на использование в фундаментальных и прикладных исследованиях, где естественным образом возникают дискретные модели в виде систем булевых уравнений.

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

Технология решения комбинаторной задачи в ИК РЕБУС соответственно включает четыре этапа обработки информации: моделирование, декомпозиция булевой модели, параллельные вычисления и обработка результатов. Возможны три варианта проведения вычислений: ПЭВМ–кластер, только ПЭВМ, только кластер. В варианте ПЭВМ–клас­тер первый, второй и четвертый этапы выполняются на рабочей станции, на третьем этапе строится план решения задачи, генерируется задание для проведения параллельных вычислений, которое передается в систему управления заданиями (СУПЗ) на кластер. Вычисления проводятся в узлах кластера, после чего результаты передаются на рабочую станцию. Во втором и третьем вариантах все этапы выполняются соответственно на ПЭВМ или кластере.

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

Первый признак – зависимость булева вектора X от дискретного времени t=0, 1, 2, …, k. С этой точки зрения различаются статические (или одношаговые) задачи, вектор состояния которых не зависит от времени t, и динамические (или многошаговые) задачи, вектор состояния которых зависит от времени t. В первом случае булевы ограничения (в векторной форме) имеют вид F(X)=0, во втором рассматривается уравнение вида F(X0, X1, …, Xk)=0, где Xi=X(t) при t=i.

Второй признак – структуризация множества X булевых переменных задачи. Здесь рассматриваются варианты линейного упорядочения множества X (в данном случае X – вектор независимых переменных) и вариант упорядочения множества X в виде многомерного массива булевых переменных.

Приведенная классификация является в определенной степени условной, и существуют дискретные задачи, занимающие в ней промежуточное положение. В общем случае размерность динамических дискретных задач (при прочих равных условиях) существенно выше размерности статических задач, так как для динамической (многошаговой) задачи необходимо определить значение вектора состояния для каждого момента времени t=0, 1, 2, …, k.

Построение компьютерной модели включает следующие этапы:

1)    задание множества булевых переменных X={x1, x2, …, xn};

2)    задание системы булевых ограничений (множество C={C1, C2, …, Cm});

3)    представление системы ограничений в одном из форматов входных данных программ-решателей ИК РЕБУС.

Для автоматизации второго и третьего этапов была разработана специальная методика моделирования [2]. Методика булева моделирования предоставляет два различных способа построения компьютерной модели: автоматический синтез булевой модели в виде текста программ на языке программирования (Фортран, С++) и синтез системы булевых ограничений в международном формате DIMACS.

Для автоматического синтеза применяется генератор процедурного описания булевой модели – подсистема, разработанная с целью организации параллелизма на нижнем уровне и предназначенная для автоматического построения вычислителя булевой функции, использующегося решателем в процессе поиска в пространстве возможных решений [3]. Эта подсистема позволяет из формата представления булевой функции на языке математического редактора формул получить параллельный алгоритм ее вычисления на заданном наборе переменных.

При втором способе построения компьютерной модели применяется конструктор булевой модели – подсистема, обеспечивающая генерацию булевых ограничений по декларативным описаниям дискретных задач. Декларативное описание задачи задается при помощи специального языка содержательных формулировок (ЯСФОР) [2]. Встроенный в ИК РЕБУС конвертор осуществляет синтаксический анализ программ на данном языке и генерирует булевы уравнения во внутреннем формате, предусмотренном языком. Далее следует этап построения по полученной системе уравнений набора ограничений в DIMACS-формате.

Решение булева уравнения f(x1, …, xn)=0 на многоядерных процессорах с общей памятью дает возможность применять двухуровневое распараллеливание вычислительной нагрузки. На верхнем уровне, уровне узлов кластера, используется параллелизм по данным. На нижнем – уровне процессорных ядер – параллелизм по задачам.

Для распараллеливания булевой модели наиболее предпочтительным с точки зрения решения данного уравнения является метод расщепления, позволяющий выполнить декомпозицию этого уравнения на произвольное число независимых уравнений, объединение решений которых даст решение исходного уравнения. Каждое независимое уравнение может решаться в своем вычислительном узле. Анализатор булевой модели выбирает тактику расщепления и генерирует схему расщепления, используемую для последующей декомпозиции этой модели. Для проведения вычислений в узлах кластера используются решатели – вычислительные модули ИК РЕБУС. Три алгоритма решения булевых уравнений, лежащие в основе работы этих модулей, показали сравнительно высокую эффективность на ряде классических и практических дискретных задач. Специфика этих методов заключается в ориентации на решение больших разреженных систем булевых уравнений, а в качестве преимущества первых двух методов следует отметить возможность представления левой части булева уравнения в общем виде в отличие от существующих SAT-ре­шателей задач удовлетворения булевых ограничений, требующих соответствующего представления в конъюнктивной нормальной форме. Третий алгоритм предполагает знание структуры булевой формулы приведенного уравнения, которая должна быть представлена в дизъюнктивной нормальной форме. Этот алгоритм использует булево распространение ограничений и интеллектуальный возврат, а также специальную внутреннюю структуру данных для представления булевой функции, позволяющую особенно эффективно решать задачи, когда булева формула содержит только бинарные и p-арные конъюнкты с положительным или отрицательным вхождением булевых переменных соответственно.

Для распараллеливания на нижнем уровне разработана параллельная версия этого алгоритма, использующая стандарт OpenMP для работы с общей памятью.

Параллельный исполнитель – подсистема вычислительного эксперимента ИК РЕБУС – отвечает за проведение вычислений на кластере. ИК РЕБУС допускает две схемы проведения параллельных вычислений: 1) генерация параллельной программы, использующей библиотеку MPI с последующим сохранением, компиляцией и выполнением этой программы на кластере; 2) интеграция с ИК DISCOMP [4]. Обе схемы требуют средства интерактивного взаимодействия с кластером. В первом случае это взаимодействие обеспечивает ИК РЕБУС, использующий штатные средства СУПЗ кластера и утилиты удаленного доступа. Во втором случае взаимодействие с кластером осуществляется средствами доступа ИК РЕБУС к программному интерфейсу XML-RPC ИК DIS­COMP. При этом перед проведением вычислительного эксперимента требуется обеспечить формирование в рабочей области пользователя на кластере области расчетных данных, содержащей спецификации объектов предметной области и входные данные.

Затем средствами интерфейса XML-RPC производится запуск вычислительного процесса. Мониторинг выполнения этого процесса, выявление его завершения и считывание результатов вычислений из области расчетных данных кластера в ИК РЕБУС также отслеживаются при помощи средств доступа к XML-RPC-сервису. В этом случае на верхнем уровне абстракции вычислительная модель [5] ИК РЕБУС может быть представлена в виде двудольного графа áP, O, Eñ, где доля P содержит множество параметров, доля O – множество операций ИК РЕБУС, а множество ребер E – направленные связи между параметрами и операциями. Списки параметров, операций и модулей хранятся в БЗ ИК РЕБУС. В соответствии со спецификой решаемой задачи множество T допустимых типов параметров наряду с традиционными типами языков программирования дополнено специальным типом par – «параллельный список». Интерпретация операции f:x®y, где x, y – параметры типа par, выполняется следующим образом: 1) в БЗ осуществляется поиск всех вычислительных ресурсов (модуль + узел), реализующих операцию f; 2) организуется параллельное применение i-го параллельного ресурса к i-му элементу списка x; 3) результат применения присваивается i-му элементу.

В инструментальной среде ИК РЕБУС можно выделить следующие основные системы: моделирования, проведения вычислительного эксперимента и работы с БЗ. Система моделирования включает инструментальные средства автоматизации построения булевых ограничений и расщепления булевой модели. Система вычислительного эксперимента содержит инструментарий для построения плана решения задачи, организации процесса решения (последовательного или параллельного проведения вычислений), визуализации результатов. Информация, необходимая для работы этих систем, содержится в БЗ ИК РЕБУС. Система работы с БЗ включает три компонента: справочник (предоставление справочной информации по БЗ в соответствии с правами пользователя в результате выполнения запроса или составления отчета); администратор (администрирование пользователей, работа с нормативно-справочной информацией и мониторинг системы); пользователь (просмотр разрешенных таблиц БЗ и таблиц собственной БД, сохранение результатов).

Рассмотрим функциональные возможности компонентов ИК РЕБУС, обеспечивающих организацию параллельных вычислений, а именно: подсистемы моделирования, включающей модули конвертирования, анализа и расщепления модели; подсистемы параллельного исполнителя, организующего интерактивное взаимодействие с кластером; подсистемы обработки результатов решения, содержащей модули постпроцессора, слияния и визуализации результатов работы (см. рис.). Эти программные средства обеспечивают: анализ структуры булевой модели; выбор тактики расщепления; формирование схемы расщепления; генерацию спецификаций параметров и операций предметной области и схем решения задачи; генерацию паспорта задания для кластера; получение остаточной функции в узле в результате применения схемы расщепления к исходной функции; упрощение остаточной функции; параллельное решение полученных в результате расщепления подсистем булевых уравнений решателями вычислительного ядра ИК РЕБУС или внешними SAT-решателями, установленными в узлах кластера; слияние и визуализацию результатов решения; интерактивное взаимодействие с кластером.

Интерактивное взаимодействие ИК РЕБУС с кластером (см. рис.) в случае и генерации параллельной программы, и использования ИК DISCOMP требует, во-первых, предварительного сохранения в рабочей области пользователя либо текста параллельной программы, либо спецификаций параметров, операций и схемы решения задачи в области расчетных данных для первого и второго случаев соответственно; во-вторых, формирования паспорта задания, содержащего перечень исполняемых программ, названия файлов с исходными данными и результатами работы, инструкции по выполнению программ, требования к ресурсам. Средства, поддерживающие эти функциональные требования, реализованы в исполнителе, являющемся компонентом системы проведения вычислительного эксперимента ИК РЕБУС.

Представленная в данной статье инструментальная среда разработана на основе принципов создания многоплатформенных приложений, обеспечивающих переносимость на уровне исходного кода и использование приложений, разработанных для ОС Windows и Linux, в качестве модулей. Технология булева моделирования применялась для решения ряда дискретных задач, например, для поиска гамильтонова цикла, нахождения покрытия конечного множества системой его подмножеств, составления плана ремонта электропоездов при равномерной загрузке локомотивного депо, составления оперативного плана отправления локомотивных бригад в условиях жесткого расписания грузовых поездов, генерации туннельных маршрутов (подзадача задачи о равномерной загрузке каналов связи СПД), построения параллельного плана требуемой длины в распределенных вычислительных системах. Вычислительные эксперименты проводились в ИДСТУ СО РАН (г. Иркутск) на кластере выделенных рабочих станций с процессором Intel Core 2 Duo, на кластере Blackford Multicore, имеющем в каждом вычислительном узле два четырехъядерных процессора Intel Xeon 5345, и сервере NVidia Tesla, имеющем два шестиядерных процессора Intel Xeon X5670, под управлением соответственно ОС Windows и Linux и показали эффективность рассматриваемого подхода.

Дальнейшее направление исследований связано с разработкой решателя для графического ускорителя и проведением экспериментов на сервере NVidia Tesla, имеющем 4 GPU NVidia Tesla C1060 с общим числом ядер 960.

Литература

1.     Отпущенников И.В., Семенов А.А. Технология трансляции комбинаторных проблем в булевы уравнения // Прикладная дискретная математика. 2011. № 1. С. 96–115.

2.     Опарин Г.А., Богданова В.Г. РЕБУС – интеллектуальный решатель комбинаторных задач в булевых ограничениях // Вестн. НГУ. Сер. Информационные технологии. 2008. Т. 6. Вып. 1. С. 60–68.

3.     Богданова В.Г., Попов Е.В. Автоматизация параллельного вычисления булевой функции общего вида на многоядерных процессорах // Винеровские чтения: матер. IV Всерос. конф. Иркутск: Изд-во ИрГТУ, 2011. Т. 3. С. 5–10.

4.     Интеллектуальные технологии и инструментальные средства создания вычислительной инфраструктуры в сети Интернет / С.Н. Васильев [и др.] // Вычислительные технологии. 2006. Т. 11. С. 34–44 (Спец. вып.).

5.     Решение булевых уравнений большой размерности в распределенной вычислительной среде / Г.А. Опарин [и др.] // Распределенные вычисления и Грид-технологии в науке и образовании: тр. Междунар. конф. Дубна: ОИЯИ, 2004.