?

Log in

No account? Create an account

Previous Entry Share Next Entry
Научно-популярная постановка задачи поиска разбиений граф-схем
evatutin

Однажды ко мне обратился один из кранчеров с предложением написать научно-популярную статью о проекте Gerasim@home, я написал. Коротко писать и говорить я не умел никогда, поэтому получилось около 5 страниц (и это по верхам, не вдаваясь в дебри!), написанное в дело не пошло, я про него забыл. А тут готовился к поездке на BOINC:FAST и случайно наткнулся. Перечитал, косметически обновил и решил выложить в блог — давно же хотел. За многабукаф прошу не пинать, я бы и еще местами мысль развернул бы :). Если кто-либо рискнет опубликовать, я за. Если кто-либо найдет ляпы, готов обсудить.



Современный мир сложно представить без использования разнообразных цифровых устройств – компьютеров, мобильных телефонов, различной бытовой техники и автомобильной электроники. Во многом этим мы обязаны стремительному прогрессу в области микроэлектроники, подчиняющемуся широко известному закону Мура. Удвоение числа транзисторов в микросхемах происходит примерно каждые два года, а вместе с ними растет число вычислительных ядер в процессорах и видеокартах, увеличиваются объемы кэш памяти и внутренних буферов, что в совокупности обеспечивает стремительный рост вычислительной мощности. Благодаря этому задачи, которые еще вчера считались вычислительно сложными (верстка текста, кодирование звука в формат mp3, трехмерная графика), сегодня выполняются в реальном времени. Основная часть транзисторов расходуется на реализацию в кремнии различных логических устройств (сумматоров, мультиплексоров, триггеров и т.д.), которые фактически выполняют простейшие операции по преобразованию или хранению поступающей на их входы информации. Совокупность подобных устройств-обработчиков называется операционной частью электронного устройства. Операционной частью обычно требуется управлять, т.е. в нужные моменты времени необходима выдача специальных управляющих сигналов, активирующих мультиплексор или разрешающих запись в ячейку памяти. (Исключение составляют т.н. комбинационные схемы, формирующие значение на выходе спустя некоторое время после поступления исходных данных на вход.) Подобная часть, как несложно догадаться, называется управляющей. Сигналы управления являются двоичными (принимают значения 0 или 1), а само управление называется логическим. (Его не следует путать с автоматическим управлением, которое осуществляется с использованием непрерывных сигналов и иных математических и схемотехнических приемов, выходящих за рамки повествования.)

Операционная часть во многом определяет организацию, микроархитектуру и, как следствие, быстродействие устройства. Например, среди исполнительных устройств современного процессора можно разместить 1 арифметико-логическое устройство (АЛУ) для выполнения сложений, можно 3, а можно и 10 (по крайней мере, теоретически). Какое количество оптимально? А по какому критерию (стоимость, быстродействие, степень загрузки)? Конкретное решение принимается по ряду факторов, к которым относятся целесообразность, возможность недорогой реализации в кремнии, тепловыделение, результаты численного моделирования в ходе структурно-параметрической оптимизации и т.д., однако общая тенденция увеличения числа исполнительных устройств имеет место.
Для первых несложных устройств, содержавших несколько сотен – тысяч транзисторов и малое количество различных схем в составе операционной части, построение устройств управления не вызывало особых затруднений, для чего был придуман и с успехом применяется математический аппарат теории конечных автоматов. Модель управляющего устройства представляется в виде автомата с набором состояний, между которыми он может переключаться (тут есть тонкость, связанная с построением автоматов Мили и Мура, но в контексте данного повествования она не играет решающей роли). При каждом переключении между состояниями конечным автоматом выдается набор микроопераций – те самые управляющие сигналы для операционной части, указывающие, что необходимо сделать на данном такте работы (например, записать результат сложения в регистр). Иногда переключения зависят от того, в каком состоянии находится операционная часть. Например, не имеет смысла выполнять сложение, если его операнды еще не прибыли из памяти. Для этого операционная часть сообщает управляющей в своем состоянии в виде набора сигналов логических условий. При этом можно говорить о том, что работа конечного автомата происходит по определенному алгоритму, называемому алгоритмом управления.

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

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

А вот при проектировании подобных управляющих систем начинается самое интересное. Как лучше представить (разбить) исходный алгоритм в виде маленьких кусочков? Какой из кусочков необходимо разместить в каком из контроллеров? Достаточным ли будет быстродействие полученной системы управления? Достаточно ли аппаратных ресурсов предоставляет выбранная аппаратная реализация системы управления? Как организовать коллективную работу контроллеров? Что делать в случае, если один из контроллеров перестал работать? Выбросить систему управления или попробовать заменить контроллер на заранее заготовленный резервный, не прерывая работы? Не нужно ли при этом изменить способ разбиения исходного алгоритма и переразместить фрагменты, чтобы добиться минимального падения быстродействия? Большинство представленных вопросов лежат в области математики, именуемой дискретной или комбинаторной оптимизацией, а получение ответов на них может потребовать существенных вычислительных ресурсов и времени на поиск наилучшего решения, называемого оптимальным. Обычно это связано с тем, что для получения оптимального решения требуется перебрать очень много решений и найти то единственное, которое является наилучшим. Именно поэтому задачи называются переборными (труднорешаемыми) или, как более строго говорят математики, относятся к классу NP. Например, поиск оптимального разбиения алгоритма управления из ста вершин (ромбиков и прямоугольников) потребует около ста тысяч лет счета на современном процессоре. Немало, не правда ли?

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

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

Многие задачи действительно упрощаются. Например, сложно точно оценить объем трафика, возникающий при координации работы контроллеров даже на модели, не говоря уже про реальную работающую систему, однако это можно сделать приближенно. И если полученное значение не будет сильно отличаться от точного (например, в пределах 5–10%), оно может быть использовано при проектировании (в этом случае говорят, что используемая математическая модель адекватна). Подобным образом и другие задачи могут быть решены не совсем точно с целью получить приближенное или эвристическое решение, а используемые при этом методы также называются эвристическими. Например, если группировать вершины алгоритма со схожими наборами сигналов микроопераций или логических условий, получится решение с малым дублированием сигналов на входах и выходах контроллеров, что упрощает разводку и более рационально использует имеющиеся аппаратные ресурсы (а их может и не хватить, тогда решение будет признано некорректным и потребуется искать другое). А если пытаться объединять наиболее часто взаимодействующие между собой вершины, получится быстродействующее решение с малым межконтроллерным трафиком. Подобные стратегии называются жадными, каждая из них в приведенном примере преследует попытку оптимизации одного из критериев качества и, следуя нашей обыденной логике, они должны давать неплохое качество решений. Для одних задач это действительно так, для других – нет. Ну и наконец, что делать, если невозможно одновременно обеспечить и малое дублирование, и малый трафик? Чем пожертвовать? Ответ на этот вопрос могут дать только эксперты при проектировании реальной системы, а раздел математики, решающий подобные вопросы с учетом их мнения, называется многокритериальной оптимизацией. В подобном случае обычно набор критериев каким-либо образом сводится в один и уже по нему производится оценка.

Однако как определить, насколько полученное решение «неплохо»? А нельзя ли найти решение лучше с использованием другого подхода? Оба вопроса правомерны. В первом случае математики говорят о степени «хорошести» решения как о суб- или квазиоптимальности (в первом случае точно известно, насколько мы проиграли оптимуму, для некоторых задач это удается оценить теоретически, во втором местонахождение оптимума неизвестно и приходится довольствоваться тем, что данное решение лучше других). Ответ на второй вопрос может дать только эксперимент, в котором будет произведено сравнение качества решений. При этом необходим анализ различных подходов и их практических реализаций на большом объеме исходных данных, т.к. при желании можно подобрать удобные или неудобные примеры практически для каждого из подходов.

Стратегии решения подобных труднорешаемых задач в общем-то известны, однако у большинства задач есть свои особенности, которые можно учесть с целью еще немного улучшить качество или снизить время поиска решения. Например, при отыскании разбиения можно не анализировать все множество вершин, а сперва разбить его на слои (т.н. ярусы или сечения), а при поиске фрагментов сечений (т.н. субсечений) можно не решать задачу изоморфизма «в лоб», а использовать ряд их особых свойств (для этого необходимы миллисекунды процессорного времени, а никакие не тысячи лет, т.к. комбинаторный перебор в подобном случае исключается).
Ну и наконец про суперкомпьютеры. Суперкомпьютеры – это здорово! Их производительность в сотни тысяч раз превосходит производительность обычных компьютеров и задачи, допускающие эффективное распараллеливание, могут быть решены на них довольно быстро. Однако суперкомпьютер – это дорогое удовольствие, которое могут себе позволить только крупные коммерческие организации или научные учреждения при поддержке государства, их вычислительное время стоит дорого. Обычно они не выделяются монопольно для решения одной задачи одним коллективом ученых, а решают параллельно сразу множество задач. Да и не всегда ученым необходимы именно подобные петафлопсные монстры в малым временем обмена между узлами, в некоторых случаях достаточным будет и вычислительной системы терафлопсного класса, все определяется решаемой задачей.

Одной из современных альтернатив суперкомпьютерам являются добровольные вычисления. В мире на данный момент существует более 60 проектов добровольных распределенных вычислений из различных областей науки с глобальным охватом участников в рамках всего земного шара. Многие из них решают различные оптимизационные задачи. В России до недавнего времени подобных проектов не было.

В июле 2010 года в рамках проекта Gerasim@home был реализован расчетный модуль separator, целью использования которого являлся ответ на один из приведенных выше вопросов: «Как лучше разбивать параллельные алгоритмы при проектировании систем логического управления?». В его составе исследовалось качество решений, получаемых двумя эвристическими методами – методом С.И. Баранова (был разработан в 80-е годы XX века для разбиения последовательных алгоритмов и впоследствии адаптирован для параллельных, использует жадную стратегию) и методом параллельно-последовательной декомпозиции (разработан в 1997 г. И.В. Зотовым на кафедре вычислительной техники тогда еще Курского государственного технического университета, реализован и уточнен в период 2003–2009 гг. мной, использует эквивалентные преобразования и особенности параллельных алгоритмов).

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

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

Мы не живем в идеальном мире с неограниченными ресурсами и это необходимо учитывать в том числе и при построении разбиений. При проектировании систем логического управления тоже есть определенные ограничения, накладываемые особенностями их организации и схемотехники. Так, конечный автомат в составе контроллера не может находиться в нескольких состояниях одновременно (параллельно), поэтому в составе подалгоритма, реализуемого контроллером, не может быть вершин из параллельных ветвей алгоритма (проверка того, параллельны вершины или нет – это отдельная интересная подзадача со своими особенностями). Логический контроллер имеет в своем составе ограниченную емкость памяти, в которую происходит запись вершин подалгоритма в виде микропрограммы. Если он будет содержать слишком много вершин, микропрограмма не поместится в памяти контроллера и система логического управления не сможет реализовать предложенный вариант разбиения. Также ограничены число сигналов, которые каждый контроллер может принимать и передавать (наиболее наглядно это можно представить в виде микросхемы с ножками на корпусе, сигнальные ножки объединяются в порты, портов обычно не хватает, сигналы приходится экономить). Сегодня подобные системы управления целесообразнее делать в виде программируемых логических интегральных схем (ПЛИС) или в заказном исполнении на кристалле вместе с операционной частью – в них проблема дублирования сигналов стоит менее остро, однако реализации на дискретных элементах тоже имеют место на практике (ввиду известных проблем с современной отечественной элементной базой), проблема минимизации дублирования управляющих сигналов (дорожек) остается, в большей или меньшей степени.

Ранние эксперименты в идеальных условиях (ограничения отсутствуют) показали незначительный, но все же проигрыш метода параллельно-последовательной декомпозиции методу С.И. Баранова. За этим последовал глубокий анализ, доработка некоторых частей метода и новые эксперименты, но уже не в идеальных условиях, а при наличии ограничений (например, емкость памяти – не ограничена, число сигналов на прием – 20, число сигналов на выдачу – не ограничено). Оказалось, что по мере усиления ограничений метод С.И. Баранова дает все большее ухудшение качества. Для систем логического управления это означает, что если проектировать их, отталкиваясь от жадного подхода, то это грозит избыточным числом контроллеров и связей между ними, увеличением массогабаритных характеристик и требований к питанию, более низким быстродействием и надежностью.

Проведенные эксперименты вроде бы ответили на поставленные вопросы о превосходстве методов, однако за полученными ответами возникли новые вопросы. Как поведут себя методы при наличии нескольких ограничений одновременно? Как повлияет на качество решений увеличение размера алгоритмов управления (точнее, числа вершин в их граф-схемах)? Не окажется ли, что рекомендации, сформулированные для сравнительно малого размера алгоритмов в 100 вершин окажутся неприменимыми для более сложных алгоритмов с бо́льшим числом вершин?

Выполненные ранее эксперименты требовали до нескольких часов процессорного времени, а для ответа на поставленные вопросы потребовались куда большие затраты. Ранние эксперименты были однопараметрическими (менялось одно из ограничений при постоянстве остальных), а для нового масштабного эксперимента требовалось как минимум одновременное изменение двух, что, с учетом увеличения размера алгоритмов, потребовало бы уже сотен лет вычислительного времени. В итоге эксперименты были поставлены с использованием функционала платформы BOINC силами более 1000 добровольцев из 61 страны на более чем 1000 компьютеров (что, по сравнению с более крупными проектами, сравнительно немного), расчеты длились чуть более года. За первым запуском последовал второй, за ним возможно будут и еще…
Полученные результаты в целом подтвердили сделанные ранее выводы, уточнив границы применимости методов и тенденции изменения показателей качества. Также было уточнено, на сколько в количественном выражении можно выиграть по тем или иным показателям при использовании параллельно-последовательной стратегии формирования разбиения. Например, при ограничениях средней силы число блоков в разбиении можно сократить на 10–12%. Соответственно, на 10–12% можно уменьшить число контроллеров в составе системы управления, либо оставить их в виде резерва на случай отказа.

Однако были получены и некоторые новые результаты, находящиеся в настоящее время в стадии опубликования. Так, например, были получены границы новой области пространства параметров, в которой дальнейшее ослабление значений ограничений не влияет на качество. Оказалось, что для метода параллельно-последовательной декомпозиции эта граница располагается ближе к началу координат, т.е. в большей области пространства ограничений он дает решения без ухудшения качества. А это, в свою очередь, может помочь при проектировании реальных систем управления в будущем. Выше был приведен пример с оптимальным числом АЛУ, необходимым процессору, для случая логических мультиконтроллеров задача оптимизации структуры может быть переформулирована по другому. Например, так: «На сколько улучшатся характеристики системы управления при увеличении емкости памяти на X%?». Или так: «Сколько ножек на прием сигналов логических условий является максимально необходимым для реализации алгоритмов управления из Z вершин?». Ответы на подобные вопросы дают полученные результаты моделирования. Например, для реализации алгоритмов управления из 200 вершин в среднем необходимо не более 64 выводов для приема сигналов логических условий и не более 84 ячеек памяти микрокоманд при параллельно-последовательной стратегии; и не более 92 выводов (на 43% больше) и 98 ячеек памяти (на 17% больше) при жадной. При этом достаточно 26 контроллеров в идеальных условиях и не более 37 контроллеров в условиях самых сильных ограничений. Полученные предельные ограничения на число принимаемых сигналов является существенными (представьте микросхему контроллера с 64–92 выводами только на прием сигналов), в то время как ограничения на емкость памяти – несущественными. Соответственно, емкость памяти можно экономить в меньшей степени, чем избыточные дублирующиеся проводники (говоря языком математики, можно изменить весовые коэффициенты функции, используемой для оценки качества решения).

На данный момент активных расчетов в рамках проекта Gerasim@home не ведется, но они планируются в ближайшее время. Существующие стратегии построения разбиений могут быть дополнены, а качество решений теоретически дополнительно улучшено. Модифицируя метод С.И. Баранова, можно попытаться синтезировать блоки параллельно, а не последовательно; можно формировать не одно, а несколько решений с последующим выбором наилучшего (подобные стратегии называются итерационными, в отличие от рассмотренных выше последовательных, в результате использования которых формируется единственное решение); можно попытаться использовать модификацию венгерского алгоритма при распределении субсечений по блокам и т.д. Все это может найти применение при создании системы автоматизированного проектирования (САПР) в области разработки систем логического управления.

Кроме того, полученные результаты имеют не только прикладное, но и фундаментальное значение. Граф-схемы алгоритмов как подкласс графов общего вида (наряду с деревьями, сетями, ациклическими, планарными и другими особыми видами графов) представляют особый теоретический интерес, т.к. обладают рядом особенностей, требующих внимательного изучения. (Проведенные эксперименты, в ходе которых в общей сложности было построено более 400 000 разбиений различных алгоритмов в различных условиях, подтвердили состоятельность ряда сформулированных ранее утверждений и теорем, на которых базируются алгоритмы промежуточных преобразований.) А полученные фундаментальные результаты могут найти применение при решении ряда смежных задач, связанных с проектированием не только управляющих, но и параллельных или реконфигурируемых вычислительных систем. Другие оптимизационные или переборные задачи из области теории графов или теории расписаний также могут быть решены с применением схожих подходов с использованием грид.

PS. Заметьте, ни одной формулы, в точности по Хокингу! :)