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

Решение на одном кристалле (chip-level multiprocessing, СМР) кажется привлекательным — это сейчас основное направление развития параллельных архитектур, однако в реальности это оборачивается переносом проблем, ранее известных лишь узкому кругу специалистов, в широкие массы программистов.

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

Что же нужно сделать, чтобы параллельное программирование стало более простым, надежным и качественным, да и собственно параллельным, а не его имитацией?

Модель параллельных вычислений

Сейчас архитектуре современного процессора соответствует модель вычислений, которая в графической форме может быть представлена блок-схемой, неизменной еще со времен эпохи ENIAC и первых работ фон Неймана, который, по воспоминаниям работавшего с ним Артура Беркса, придумал не только блок-схему, но предлагал использовать и кэш. Между прочим, «автомат Неймана», как множество параллельно работающих элементов Неймана, также до сих пор лежит в основе самых «передовых» аппаратных решений. И все пока работает, и, казалось бы, почему бы не работать так и дальше? Однако модель в виде блок-схем морально устарела, и, как ни покажется удивительным, по большему счету дело даже не в архитектуре фон Неймана, а в специфике ее применения. Более того, одно из направлений многоядерности — это ядра с минимальной неймановской архитектурой. Поневоле — «шаг вперед — два шага назад»!

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

У программистов накоплен богатый опыт использования разных моделей вычислений. Если говорить о потоках, то, рассматривая существующие параллельные модели, представляется логичным в основу их теории положить модель Хоара. Но эта модель удобна для описания протоколов, а не для детального описания алгоритмов. На примере предложенного Хоаром решения задачи о философах Дейкстры можно видеть, что в рамках его модели легко описать взаимодействие, но сложно понять поведение философов. И это причина того, что Хоар отказался сделать математически строгий анализ своего же решения.

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

Другой вариант сетевой модели — сеть на базе конечных автоматов. Еще фон Нейман рассматривал модель параллельных вычислений — автомат и/или разные варианты клеточных автоматов. Обладая не меньшей мощностью, чем сети Петри, автоматы отличаются в лучшую сторону простотой понимания, структурной ясностью, обширной и проверенной временем теорией. Сегодня, после некоторого охлаждения к автоматам, программисты вновь обратили на них свои взоры. Популярный язык моделирования UML базируется на автоматной модели, отечественные технологии проектирования программ SWITCH и КА также их используют (первая представлена на сайте СПбГУ ИТМО is.ifmo.ru, вторая — на сайте SoftCraft.ru).

Но не только программистов привлекают автоматы. Хороший пример их приложения — теоретические работы О. Л. Бандман о применении клеточных автоматов для моделирования пространственной динамики (Институт вычислительной математики и математической геофизики СО РАН). Перспективным является применение автоматов в нанотехнологиях — клеточные автоматы на квантовых точках (www.old.nanonewsnet.ru). На основе решения фон Неймана рассматриваются различные проблемы самовоспроизводства не только технических, но и общественных систем (П. О. Лукша, «Самовоспроизводство социально-экономических систем», www.luksha.ru/index_r.html) и т.д.

Адекватность физическим процессам

Практика подсказывает, что, создавая модель вычислений, необходимо руководствоваться связью с реальными процессами. Пока же, как утверждает Эдвард Ли, «базовой абстракцией параллельных вычислений была выбрана сущность, не имеющая даже приблизительного сходства с параллельностью в физическом мире» (см. перевод его статьи на сайте www.softcraft.ru/parallel/pwt/index.shtml и статью Сергея Кузнецова «Возвращение многоядерных систем», «Открытые системы», 2006, № 5). Нельзя с этим не согласиться.

Невозможно, глядя на программу как на «черный ящик», определить ее внутреннее устройство: оно может быть как параллельным, так и последовательным, как одноядерным, так и многоядерным. И удивительно, когда на примере задачи Дейкстры о разделении множеств доказывается отсутствие у параллельной программы свойства тотальной корректности. Такова уж ныне теория параллельных вычислений, не учитывающая «физический смысл», — если уж есть тотально корректный последовательный алгоритм, то должен быть с такими же качествами параллельный. При этом результат работы алгоритма или программы никак не должен быть связан с числом потоков или ядер процессора.

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

Чтобы следовать «физическому подходу», необходимы критерии, выявляющие несоответствие между миром абстрактных вычислений и миром реальным. Таких критериев может быть несколько — от образных до конкретных. К образным можно отнести критерий программной размерности, к конкретным — сравнение результатов работы известных параллельных задач с работой реальных аналогов. Среди таких задач: параллельное суммирование, философы Дейкстры, его же задача о разделении множеств, стрелки Майхилла, различные параллельные сортировки, задача о моделировании RS-триггера и т.д. Их реализация потребует от модели естественности в описании и высокой эффективности последующего исполнения. Необходимо также наличие формальных процедур анализа созданных алгоритмов.

Все упомянутые «физические качества» модели в полной мере в первую очередь присущи классическим автоматам. С незначительными дополнениями они — та модель, которая легко и естественно ложится на многоядерность. Здесь отдельное ядро — это автомат, множество ядер — автоматная сеть (в виртуальном режиме — одно ядро реализует автоматную сеть), а все вместе — аппаратно-виртуальная параллельная модель реального мира!

Реальное и модельное времена процессов

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

Корни недетерминизма многопоточного программирования в игнорировании свойств реального времени. Картина меняется существенно, если в модель вычислений ввести его модель. При этом изобретать почти ничего не надо — автоматные модели по определению работают в модельном дискретном времени. Поэтому в рамках автоматных процессов легко выполнить обмен данными, организовав, например, «встречу» в дискретном времени.

Но ключевой вопрос «физики» параллелизма — каким должно быть время параллельных процессов, единым для всех или у каждого процесса свое. В многопоточном программировании оно свое у каждого потока. И от этого все их проблемы, поскольку, как и в жизни, мало толку от «часов», идущих вразнобой. Исходя из структуры, связей и временной физики реальных параллельных процессов, построения их теории, мы должны иметь не только структурно параллельную модель, но модель, структурные блоки которой обладают единым временем.

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

Вопреки «здравому смыслу», например, теории и практике асинхронных процессов, единое время может увеличить скорость работы алгоритмов в разы. Так, параллельная сортировка, использующая протокол в едином времени, почти в три раза быстрее, чем сортировка с асинхронным протоколом. И видимо, в силу подобных фактов асинхронные решения так пока и не смогли воплотить в реальность декларативные утверждения по поводу повышенной скорости своей работы.

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

При наличии встроенного единого времени ничто не мешает отказаться от его «единственности». Все в руках разработчика. Но подход таков, что лучше иметь единое время, чем в последствии преодолевать проблемы, чтобы его ввести. Собственно об этом, но не столь конкретно, говорит и Ли, рассматривая проблему недетерминизма многопоточного программирования на многоядерных системах.

Выводы

Известно, что дешевле всего обходится устранение ошибок, обнаруженных на начальной стадии проектирования. В отношении новых архитектур это по большей части относится к правильному выбору алгоритмической модели, положенной в основу их функционирования вообще и параллельных алгоритмов в частности. «Никакой секатор не способен превратить дикий вьюн в надежную живую изгородь», — утверждает Эдвард Ли, рассматривая «достоинства» многопоточного (многоядерного) программирования. Истоки уже явно намечающегося кризиса многопоточных и многоядерных систем, когда имеющийся программный параллельный кризис переносится на новую аппаратную почву, в отсутствии прогресса в проектировании параллельных программ: потоки должны быть сосланы в машинное отделение программирования, как считает Ли. Этим сказано почти все.

Примета сегодняшнего дня в том, что даже «революционеры», понимая, что нынешнее параллельное программирование никуда не годится, не знают, каким ему быть. По заверениям Херба Саттера, «бесплатные завтраки» закончились (см. статью Леонида Черняка «Многоядерные системы и грядущая параллельная революция», «Открытые системы», 2007, № 4). Многоядерные системы «заставят проектировщиков переосмыслить фундаментальные начала», когда выяснится, что существующие «начала» уже не оправдывают ожиданий.

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

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

Вячеслав Любченко (sllubch@mail.ru), Юрий Тяжлов (armaguard@mail.ru) — сотрудники компании «ПараДип» (Москва).