к проблеме выбора алгоритмической модели

Во всем мне хочется дойти

До самой сути.

В работе, в поисках пути,

В сердечной смуте.



Б. Пастернак

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

Разработанные в последнее время языки программирования мало добавляют в теорию, да и в практику создания программ. Прогресс идет в основном за счет развития библиотек и сред разработки. Кроме того, присходит достаточно жесткая борьба между фирмами за продвигаемые ими стандарты, которые в вычислительную науку практически ничего не привносят.

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

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

А что нам скажет на это товарищ ... Мур?

Процессор ... приводит архитектуру фирмы Intel в новую эру совместимости и мощности.



Проспект фирмы Intel

Основатель корпорации Intel Д. Мур, объявив свой закон, не указал причин, по которым он будет выполняться. Но, странное дело, закон пока выполняется. Может быть, дело в том, что за его соблюдением следит фирма, основанная Муром? Как бы то ни было, в обществе то и дело возникают слухи о скором нарушении этого закона. Пока они слухами и остаются, но при нашем попустительстве, похоже, могут стать реальностью. Технологические ресурсы еще не исчерпаны, но о близости этого события говорят размеры кристаллов микропроцессоров. А в последнее время появился и еще один признак - применение в микропроцессорах кардинально новых архитектур. Но дадут ли они эффект?

Становится ясно, что в рамках существующей архитектуры фон Неймана фирме Intel сложно поддерживать свое реноме. Процессор Merced - попытка перейти к новым аппаратным решениям. Но несколько затянувшееся ожидание его выхода говорит о том, что проблемы существуют и в области новых архитектур. Да и просочившиеся о процессоре сведения вызывают определенные сомнения в том, что полностью сбудутся возлагаемые на него надежды. Основной источник таких сомнений - отсутствие формальной алгоритмической модели, лежащей в основе будущего параллельного процессора. Но это и отражение текущей ситуации в области параллельных систем: на данный момент нет признанной всеми базовой параллельной универсальной модели, которую можно было бы положить в основу архитектуры процессора.

Процессор Merced должен поддерживать множество функциональных устройств, понятие групп команд, новую концепцию управления последовательностью выполнения команд, параллелизм, вынесенный на уровень команд [1]. Все это хорошо по отдельности, но в сумме не объединяется в какую-либо модель. А отсюда и возможные проблемы в использовании данных решений. Вероятно, на уровне ассемблера они дадут эффект. А как насчет языка программирования высокого уровня?

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

В то же время некоторые из возможностей Merced хорошо подходят для автоматной модели [2]. Например, предикаты и действия автомата можно легко "разбросать" по функциональным блокам, используя понятие групп команд. И если при существующих подходах сложно в общем случае заставить эффективно работать вместе более 4-6 процессоров/функциональных устройств, то сетевая автоматная модель обладает в этом плане неограниченными возможностями.

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

Вести от Билла

Доверительные отношения могут быть либо двунаправленными, либо однонаправленными.



"Решения Microsoft"

Программное обеспечение смягчает несправедливость, навязываемую аппаратурой. Операционная среда - первый уровень, который скрывает особенности "железа" от пользователя. Известных операционных систем на платформе Intel несколько, но выбор, как оказывается, не так уж велик. На практике он сейчас сведен к одной Windows. И это только кажется, что мы выбираем ее. На самом деле Microsoft в лице Windows уже давно выбрала большинство из нас. Microsoft не столь регулярно, как Intel, выдает "на-гора" новые решения, но сказать, что она бездействует, тоже нельзя. Обработка сообщений, механизмы создания процессов на основе ветвей и нитей - ее "посильный" вклад в пропаганду и внедрение параллелизма "в массы". Но недостаток этих решений все в том же - в отсутствии в их основе формальной модели параллельных вычислений. Правда, кое-что исправляется, но при этом, как правило, суть самих решений не затрагивается.

Покажем это на примере механизма обработки сообщений. Неудачное исходное решение исправлено "косметическими средствами" библиотеки MFC (если говорить о решениях Microsoft) с помощью так называемых таблиц обработки сообщений (ТОС). Но и у этих таблиц имеются серьезные недостатки. Это легко увидеть, сравнив их с табличным представлением КА [2]. Любой ТОС соответствует модель КА с одним состоянием, имеющая множество входов-сообщений, но не имеющая выходов. Таким образом, видны как ограничения, так и пути совершенствования данного механизма работы с сообщениями.

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

Еще один пример - популярные ныне решения на базе модели COM. Перечислять недостатки COM означает повторять сказанное выше по поводу обработки сообщений. Наделение ее автоматными свойствами значительно расширит возможности не только самой модели, но и, как следствие, всего, что на ее базе создано, -- OLE, ActiveX и т. п. Это не фантазия и не утопия. Уже сейчас, используя механизмы наследования ООП [3], можно легко расширить возможности указанных средств. Но желательно, чтобы недостатки были устранены на системном (Windows) или модельном (СОМ) уровне. Не обязательно устранять их именно на базе КА (хотя на чем тогда?), но что это должно быть сделано, надеюсь, достаточно очевидно.

О выборе программистов

Купила мама коника...

Если аппаратура - нижний слой, то уровень языка программирования следует за операционной средой, и уж на нем-то, казалось бы, есть где разгуляться. Тут тебе и Бейсик, и Си с Си++, и Фортран, и Java в конце концов, - выбирай не хочу! Но на самом деле в основе всего этого разнообразия лежит одна и та же блок-схемная модель программ.

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

БС полностью соответствуют существующей архитектуре вычислительных машин и потому очень эффективны в смысле скорости исполнения. Кроме того, они даны нам "с рождения": как правило, программисты начинают свои "младенческие" опыты именно с БС. Поэтому перейти на другую программную модель достаточно сложно даже психологически: нужны веские причины и серьезный профессиональный опыт. Как это должно происходить и должно ли вообще, программист решает индивидуально. Его можно только в той или иной степени подтолкнуть, стимулировать, но не более того.

Конечно, "старый конь борозды не портит", но зато он обычно и "неглубоко пашет". Уже скоро - видимо, с выходом процессора Merced, программистам предстоит довольно серьезная "пахота". Несоответствие возможностей параллельного процессора и устаревшей последовательной математики создаст тяжелую "почву" для работы. Поговаривают, что задача распараллеливания должна быть переложена с аппаратуры на компилятор, а это уже совсем плохо [1]. Труднее всего придется программистам: эффективных параллельных компиляторов попросту нет (до сей поры почти все приходилось "параллелить" вручную), и маловероятно, что ситуация изменится, - ведь удобной универсальной параллельной модели не существует. Существуй она, программирование давно было бы параллельным. Но пока в наличии только такие его элементы, как нити, ветви и т. д., для создания параллельных систем в нашем распоряжении есть лишь запутанный клубок (или непроходимый лес?) проблем.

Имеется много способов уйти от БС к параллельному программированию. По своей сути они сводятся либо к применению программ-интерпретаторов для выбранной модели, либо к использованию на завершающем шаге разработки формальной процедуры перехода от выбранной модели к БС. Первый способ удобнее, второй актуален при повышенных требованиях, например, к быстродействию.

При разработке программ тоже применяется немало моделей, отличных от БС. Популярны, например, таблицы решений, переменные состояния (которые представляют собой автоматы, урезанные до одного состояния). Но по степени универсальности вряд ли какая-нибудь модель способна сравниться с КА. Они применяются при разработке игровых программ, систем управления реального времени (по играм см., например, [4], по управлению - [5]) и во многих других областях.

Модель КА - выбор, который может сделать осознанно сам программист, несмотря на навязываемую ему обстоятельствами модель БС. О том, почему этот выбор оправдан, и пойдет далее речь.

Есть такой математический аппарат!

Экспериментщик, чертова перечница,

Изобрел агрегат ядреный.



А. Вознесенский. "Оза";

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

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

Итак, КА вполне универсальны. Но насколько они мощнее, удобнее и практичнее БС? Вот перечень некоторых пунктов, в силу которых вполне можно забыть БС и перейти на КА.

  1. Модель конечных автоматов несравнимо мощнее теоретически и намного полезнее практически, чем модель БС.
  2. Уже в структурной модели КА на уровне входов/выходов имеется естественный параллелизм, который полностью отсутствует у БС.
  3. Отдельный автомат на уровне компонента и сетевая автоматная модель на уровне множества компонентов позволяют наглядно и просто описывать структуру любых систем. Модель БС на это не рассчитана, поэтому чем сложнее решаемые проблемы, тем удобнее использовать КА.
  4. Модель КА так же просто реализовать аппаратно, как и модель БС. КА может стать стержнем новой архитектуры. Аппаратная реализуемость - достоинство, выгодно отличающее КА от других известных формальных моделей. И потому автомат не менее практичен, чем БС.
  5. Непроцедурный характер и параллелизм компонентной и сетевой автоматной модели кардинальным образом влияют на мышление программиста, освобождая его от рутинной процедурной работы, характерной для БС. И в этом мощь, удобство и практичность автоматного подхода.

Объектное программирование уже во многом определяет мышление большинства программистов. Может ли такая судьба ожидать и автоматы? Может! Более того, к этому все и идет. Примеров тому множество. Где-то модель КА уже давно прочно держит первенство, а где-то ее только начинают внедрять. Но там, где ее применение ограничено, это обычно происходит из-за того, что в силу каких-то причин модель еще не успели обкатать.

Итого

Время легкий бисер нижет...

Час за часом, день ко дню:



В. Ходасевич

Проблема модели параллельных процессов - одна из главных при определении принципов построения вычислительных систем будущего [6, 8]). От того, как она будет решена, зависит и архитектура процессоров, и синтаксис языков программирования, и организация операционных систем... Процесс создания такой модели начался уже давно, но, к сожалению, протекает вяло. В существующих процессорах и операционных системах параллельные вычисления реализованы достаточно интуитивно и хаотично, без точной формулировки поставленных целей.

В связи с этим я не согласен с утверждением, что "не существует математического аппарата, пригодного на все случаи жизни". Есть такой аппарат, и есть такая модель - это теория и модель КА, дополненная модулями, эквивалентными соответствующим элементам машины Тьюринга - ленте и операциям с ней. В данном случае это память и множество функций, разделенных на предикаты и действия. Дополненные таким образом КА вполне смогут перенять эстафету от машин с неограниченными регистрами, теория которых лежит в основе блок-схемной модели и архитектуры фон Неймана [7]).

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

И последнее. Когда же мы перестанем наступать на одни и те же грабли? И долго ли будем закрывать глаза на проблемы, которые рано или поздно решать все равно придется? Для меня ответы на эти вопросы сосредоточены в одном - в поиске и формулировке модели параллельных процессов. И здесь я свой выбор сделал. Хорошо ли плохо ли (вот тема для дискуссии!), но сетевая автоматная модель свои функции выполняет. Я уверен, что хорошо. Если у кого-то на этот счет другое мнение - давайте обсудим.

Литература:

  1. Кузьминский М. Вышел Merced из тумана. - "ComputerWorld Россия", 1997, N 47, с. 31.
  2. Любченко В. С. Новые песни о главном (римейк для программистов). - "Мир ПК", 1998, N 6, с. 114.
  3. Буч Г. Объектно-ориентированное проектирование с примерами применения: Пер. с англ. - М.: "Конкорд", 1992. 519 с.
  4. Ла Мот А., Ратклиф Д., Тайлер Д. Секреты программирования игр. Пер. с англ. - СПб: "Питер", 1995. - 720 с.
  5. Шлеер С., Меллор С. Объектно-ориентированный анализ: моделирование мира в состояниях. Пер. с англ. - Киев: "Диалектика", 1993. - 240 с.
  6. В. А. Вальковский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков. Элементы параллельного программирования. Под ред. В. Е. Котова. - М.: "Радио и связь", 1983. - 240 с.
  7. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ. - М.: "Мир", 1983. - 256 с.
  8. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. - М.: "Наука", 1982, - 336 с.