English | 中文 | Русский | Français

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

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

“Параллельное программирование – это просто” 2, или “The most general definition of beauty”

yuryserdyuk (8 пост(а)) 23.12.2008 19:42

В заголовок этого поста вынесено начало эпиграфа к книге K.Mani Chandy, Jayadev Misra “Parallel Program Design: A Foundation”. Полностью этот эпиграф выглядит так:

“The most general definition of beauty … Multeity in Unity”

(Samuel Taylor Coleridge, “On the Principles of Genial Criticism”, 1814).

К чему это?

Хотелось бы еще на одном примере показать, как грамотно выбранная система обозначений (читай, язык программирования) позволяет очень просто сформулировать алгоритм решения задачи, который в другой бы нотации записывался очень сложно, или, вообще бы казался нереализуемым.

 

Начнем чуть издалека. Многим хорошо известен язык логического программирования Prolog, программирование на котором в чистом виде состоит в том, что мы, в основном, выписываем правила того, ЧТО должно быть сделано для решения задачи, оставляя вопрос КАК это делать интерпретатору этого языка. Т.е., интерпретатор языка Prolog выполняет любую программу единым образом – пытается сделать истинными предложения, из которых составлена программа, используя, возможно, откаты назад (так называемый бектрекинг). 

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

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

Язык программирования Unity понять очень легко – мы его продемонстрируем на примере записи программы нахождения наибольшего общего делителя двух целых чисел: 

Program gcd

            declare x, y : integer

            initially x, y = X, Y

            assign

                        x, y := x – y, y  if x > y

                      | x, y := x, y – x  if y > x

end { gcd } 

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

Теперь реализуем с помощью Unity модель некоторой системы, которая обсуждалась в комментариях к моим двум предыдущим постам. А именно, требуется реализовать в виде двух параллельных процессов модели логических элементов И-НЕ, связанных между собой перекрестными связями. А именно, выход y1 первого элемента вычисляется как

y1 =  NOT  ( x1  AND y2 ),

а выход y2 второго элемента вычисляется как

y2 = NOT ( x2 AND y1 ).

Как работает данная система – было проанализировано “на бумажке” в комментариях к предыдущим постам. Чтобы получить аналогичное поведение, мы просто напросто переносим определение системы в формализм Unity: 

Program Model

            declare x1, x2, y1, y2 : integer

            initially x1, x2, y1, y2 = 0, 0, 0, 0

            assign

                        y1, y2 = 1- ( x1 & y2 ), 1 - ( x2 & y1 )                     

end { Model } 

Программа (причем, параллельная) получена!

И как вам это? 

PS

Всех с наступающим Новым годом !

И в качестве альбома для прослушивания на Новый год рекомендую

один из лучших дисков 2007 года – Burial “Untrue”

 

 

 

 

 

 

 

 

 

 

Категории: Intel Software Network

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

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

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

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

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

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


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