713 Тем для обсуждения

6,530 Открытых обсуждений

Модель – для понта, язык – для дела?

vlubch (8 пост(а)) 15.10.2009 15:07

Перефразируя произнесенную в http://software.intel.com/ru-ru/blogs/2009/08/27/2001970/ фразу о ружьях и ножах из фильма «Карты, деньги, два ствола», давайте разберемся, действительно ли, как это часто преподносится, модель для наукообразия или, попросту, – для понта и только лишь язык программирования – для дела? На примере вычисления чисел ряда Фибоначчи мы рассмотрим параллельные идеи в рамках широко известных языков С# и С++ (подробнее см. соответственно [1] и [2]).

Имя Леонардо Фибоначчи (Леонардо Пизанского) часто упоминается в связи со следующей числовой последовательностью:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Данный ряд натуральных чисел, называемый рядом чисел Фибоначчи, записанный как
a0, a1, a2, a3, . . .
можно описать следующим образом:
a0 = 1, a1 = 1, и
ai = ai-1 + ai-2, для i >= 2.

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

Одна из тенденций реализации параллелизма состоит в расширении существующих языков программирования. Параллельная программа на языке MC# (он же – расширенный С#[1]), вычисляющая числа Фибоначчи, представлена листингом 1. Это известный последовательный рекурсивный алгоритм, в котором рекурсивные вызовы заменены на параллельно исполняемые. Введенный параллелизм несколько изменяет исходный последовательный алгоритм. Результат таких изменений в форме параллельной блок-схемы (БС) показан на рис. 1.

Приведенная блок-схема в явной форме отражает параллельные алгоритмические свойства решения. При этом на рис.1 переход (в терминах сети Петри), из которого исходят дуги, соответствует вызову параллельно исполняемых movable-методов MC#, а переход с входящими дугами – методу типа Get (см. листинг 1). При этом, например, у перехода с входящими дугами, их число соответствует числу каналов, по которым нужно одновременно принять данные от параллельно исполняемых методов.

Имея модель и зная процедуры ее эквивалентного преобразования, мы можем перейти к другой модели вычислений – автоматной[2]. В целях построения эквивалентного блок-схеме конечного автомата (КА) проведем процедуру разметки БС. Для этого нанесем на нее отметки внутренних состояний автомата, а элементы блок-схемы поименуем (см. рис.1). Именам функциональных блоков x1,…, xN в новой модели соответствуют методы - предикаты, возвращающие булевское значение. Им будут поставлены в соответствие входные сигналы автомата. Именам y1,…, yN соответствуют методы-действия, определяющие действия автоматной алгоритмической модели вычислений. Им соответствуют выходные сигналы автомата. Граф автомата, соответствующий разметке, показан на рис.2.

В терминах теории программ (точнее, - теории схем программ) рис.2 – это графическая форма так называемого управления программы. Но в модель программы кроме управления входит еще два множества - множество данных и множество операций (о моделях программ подробнее см. [3]). Поэтому рядом с графом управления автоматной программы приведено описание ее методов – предикатов и действий. Именно с их помощью выполняется анализ и преобразование данных в последовательности, определяемой управлением программы. Листинг 2 дает конкретное представление о выбранном подходе к реализации автоматной модели на языке С++.

Отметим, что в отличие от программ на языке MC# в автоматном С++ нет разделения на перемещаемые и неперемещаемые методы. Все методы потенциально параллельны. При этом на параллелизм предикатов ограничений нет, т.к. они не изменяют данных, а у параллельно исполняемых действий не должно быть пересечений по данным, к которым возможен одновременный доступ. Параллелизм методов отражают переходы автоматной модели, где параллелизм предикатов представляют конъюнкции входных сигналов, а параллелизм действий – набор выходных сигналов автомата.

Отвлечемся на мгновение от самого процесса вычисления чисел Фибоначчи… Можно ли утверждать, что модель вычислений определяет мышление программиста? Скорее да, чем нет. Сравнивая графы программ на рис.1 и 2, легко видеть, что автоматный язык лаконичнее языка блок-схем. Он несет больше информации, стимулирует на действия и мысли, которые вряд ли возникнут у того, кто пользуется языком блок-схем.

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

В автомате на рис.2 состояния-перекрестки программы можно трактовать следующим образом. Состояние автомата «f1» – начальное состояние алгоритма и одновременно состояние анализа текущего значения n – номера числа в ряду Фибоначчи; «f2» - состояние ожидания завершения вычисления предшествующих двух чисел ряда; «00» - заключительное состояние алгоритма, при переходе в которое мы знаем значение первого числа в ряду Фибоначчи или сумму предыдущих двух чисел ряда.
Анализируя управление автоматной программы, можно, опираясь на теорию конечных автоматов, оценить, например, его непротиворечивость и полноту. При этом в нашем случае полностью определенный автомат – это объединение его частичной формы, представленной явно (см. рис.2), и его дополнения – автоматом с теми же состояниями, что и частичный автомат, но с переходами по умолчанию - петлями, входные условия которых представлены отсутствующими на графе конъюнкциями входных сигналов.

Что толку от быстро полученного, но глупого совета!? Но, как бы там ни было, программу часто встречают «по одежке», т.е. скорости ее работы. А есть случаи – системы реального времени – когда скорость отклика имеет вообще решающее значение. Для них запоздало данный, хотя и правильный, совет не нужен. Поэтому весьма желательно, чтобы хорошему мышлению соответствовали быстрые и/или хотя бы оперативно данные правильные (!) ответы. Сравнение по скорости работы программы на MC# и автоматном С++ показало, что вычисление, например, 16-го числа на первом выполняется медленнее более чем в 20 раз, чем на втором…

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

Замечание. Можно впасть в крайность и вообще игнорировать общепризнанные этапы проектирования программ. Именно такое ощущение возникает от работы некоторых программ, когда возникает подозрение, что пропущен даже этап тестирования?!

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

И напоследок. Без ущерба для дела мы могли бы вообще не рассматривать программный код. Модель – основное, реализация – дело техники. Безусловно, качества программы зависят от языка программирования. Но это уже больше проблема выбора средства реализации, чем самой модели. Понимания пользы модели позволяет преодолеть любые сложности на пути ее эффективной реализации. Вплоть до создания языка программирования и аппаратной архитектуры для ее поддержки.
Литература
1. Гузев В., Сердюк Ю. Введение в параллельное программирование на языке MC#. Переславль Залесский/Москва. 2007. http://u.pereslavl.ru/~vadim/MCSharp/docs/pguide/pguide.doc
2. Любченко В.С. Конечно-автоматная технология программирования. http://www.softcraft.ru/design/katech.shtml
3. Наумов Н.А. О некоторых подходах к расширению языков программирования. http://eidos.kiam.ru/group/pod.html.

Листинг 1:

Листинг 2:

Категории: Параллельное программирование, Разработка софта

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

Комментарии (30)

Обратная ссылка (1)

• Блоги Intel® Software Network » Суров закон параллелизма, или «что за #@%&^ этот ваш параллелизм?»
  11.12.2009 04:31

Оставить комментарий  

Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*