Параллельное программирование в функциональном стиле

© 2003 Глебов А.Н.

В этой статье рассказывается о создании модели для параллельного программирования (ПП).

Дополнительные материалы, содержащие текстовые документы, системы программирования и программы
можно найти на сайте автора: http://lisp2d.crimeastar.net

1. Введение

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

Чтобы программировать стало реально нужно поменять стиль программирования и научиться программировать заново. Взять трехтомник Кнута, просмотреть, закрыть и забыть. ;)

Какими свойствами должен обладать такой язык?

1. Многоплатформенность: сейчас параллельных вычислительных систем большое множество, так как идет поиск самых удобных систем, и этот поиск далек от завершения. Этот язык должен быть абстрактным, не касаться особенностей определенных систем. Таким же абстрактным как блок схемы алгоритмов отличаются от ассемблера.
2. Структуризованность: в процедурном программировании уже перешли к этому стилю , меньше используют операторы перехода goto и больше структуры while,for. Когда программа хорошо структуризована в ней проще разобраться, так как известно что данная часть программы при изменении повлияет только на малую часть всего проекта. При переходе на объектно-ориентированное программирование появилась возможность писать сервисные функции (методы) для работы с объектами (а объекты - это части проекта). И при изменении работы одного объекта отпадает необходимость в пересмотре работы других. Для ПП структуризованность очень важна так как сейчас это камень преткновения для перехода на ПП.
3. Очевидность: программист должен иметь возможность контролировать поведение всего вычислительного процесса в целом. При отсутствии этого механизма, отдельные куски программы не могут однозначно определить как функционируют другие процессы. Введение семафоров и других механизмов синхронизации не приводят к желаемому результату, так как сама идея семафоров пришла из привычки думать последовательно и наказание не заставило себя ждать - появились ситуации остановки, когда несколько процессов по кругу закрывают доступ с одной стороны и ждут доступ с другой.
4. Эффективность: способность максимально загрузить все вычислительные ресурсы (полезным делом, конечно). Эффективность работы программы на конкретной платформе оценивается временем, затрачиваемым на ее выполнение. При добавлении к платформе еще одного вычислительного ресурса (блока к кластерной системе) должно происходить повышение быстродействия программы. По достижению определенной мощности системы программа больше не сможет загружать задачами дополнительные ресурсы, так как играет роль необходимость последовательности некоторых действий в алгоритме. Назовем эффективностью языка возможность для программиста максимально распараллелить алгоритм, при наличии неограниченных вычислительных ресурсов.

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

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

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

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

Таким образом встал вопрос о кандидате - языке, который бы больше всего подходил для расширения до ПП. Перепробовав различные стили программирования стало ясно, что к вышеозначенным требованиям идеально подходит функциональный стиль, а именно язык Лисп.

2. Лисп

Лисп (Lisp) - также известный как (((Lots of (Idiotic (Silly (Parentheses)))))) (множество идиотских вложенных скобок) начал свое применение лишь как експериментальная модель для теории лямбда-исчисления. Чтобы на этом языке можно было запрограммировать все обще-рекурсивные функции по Черчу (а этот класс совпадает с классом всех алгоритмов, которые можно задать с помощью машины Тьюринга) в него достаточно задать возможность к рекурсии, проверке на нуль-объект и элементарными операциями над объектами в области которых будут действовать функции. Так появился Чистый Лисп (Pure Lisp).

Объекты Лиспа задаются как либо атомы, либо структуры атомов. Атом - по определению неделимый объект. Конкретно в Лиспе единой структурой атомов был выбран список и язык получил свое название LISt Processing (обработка списков).

Функция - это отображение из поля объектов в поле объектов. Сложные функции получаются из элементарных с помощью конкатенации, которая необходима в теории лямбда-исчислении.

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

Более полно введение в Лисп можно прочитать в других источниках:

• Ассоциация пользователей Лиспа - www.elwoodcorp.com/alu
• Вторая редакция стандарта Common Lisp - http://gauss.upf.es/www-storage/cltl/clm/clm.html

Почему был выбран Лисп? Рассмотрим его свойства.

Многоплатформенность: в связи с тем что он чисто теоретический, то и создавался не опираясь на конкретную архитектуру.

Структуризованность: что может быть более структуризованным? Программа в Лиспе - это вызов одной функции с аргументами (в Чистом Лиспе с одним аргументом). Сначала вычисляются значения аргументов, затем над значениями производится соотвествующая обработка и возвращается одно значение - результат функции. Причем в Чистом Лиспе процесс вычисления аргументов независим от вычисления других аргументов (а значит поддается параллелизации!) и независим от того каким способом будет обрабатываться результат вызываемой функцией.

Очевидность - это результат хорошей структуры. При перепрограммировании одной функции достаточно пересмотреть обработку функций которые ее вызывают и фунций, которых вызывает она.

Эффективность: в теории обще-рекурсивных функций заложен механизм распараллеливания задач. А именно сложная функция, созданная с помощью конкатенации f(g(x)) обязана вычисляться последовательно, а вычисление аргументов функции f(x,y,...,z) могут и должны вычисляться параллельно. Заданная с помощью Чистого Лиспа функция не может быть распараллелена больше, чем это задано ее структурой.

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

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

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

Таким образом встал вопрос - как в смешении всех стилей создать механизм, который бы эффективно задавал условия на возможность распараллеливания вычислений.

3. Расширение Лиспа для параллельных вычислений

Определение функции в Common Lisp-е выглядит так:

(defun fname arglist body)

где arglist представляет собой список из формальных имен аргументов и ключевых слов. Ключевые слова выглядят так: &rest, &optional, &environment, ... Все эти ключевые слова используются для интерпретации: какую часть фактических параметров функции присваивать каким формальным параметрам. Так как способ вычислений аргументов является составляющей функции и при другом порядке вычислений это был бы уже другой алгоритм, то логичным было бы добавить ключевые слова, например &concurrent и &parallel, затем заключить соответствующие параметры в скобки.

Например, функция func от трех аргументов x, y, z требует, чтобы они вычислялись в таком порядке: (z параллельно (x затем y) ). Это можно записать так:

(defun func (&parallel (z &concurrent (x y))) body)

Теперь рассмотрим как можно записать вычисление параллельно нескольких функций, часть которых выполняется последовательно. Для последовательного выполнения в Лиспе существует функция progn:

(progn func1...funcn) ,

которая вычисляет все функции func_i последовательно и как результат возвращает значение последнего выражения. Соответсвенно определяем форму parallelprogn , которая вычисляет подфункции в параллельном режиме, а результат возвращает nil.

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

Берем в Лиспе функцию apply, которая вычисляет применение некоторой функции к списку аргументов и создаем параллельный аналог parallelapply, который выполняет вычисления вышеописанным способом. Здесь появляется одна ловушка.

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

Значит и этот порядок вычислений нужно задавать на уровне определения функции. Например так:

Нормальная функция - (defun func args body) ,
и безымянная - (lambda args body) .

Instant (моментальная) функция - (paralleldefun func args body) ,
и безымянная - (parallellambda args body).

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

Теперь пришла пора вспомнить о Чистом Лиспе, где тип вычислений очевидно определялся структурой программы - красиво и естественно.

Убедившись в том, что использовать уже написанные программы на каком-либо языке для усовершенствования к параллельному исполнению невозможно, я окончательно отказался от идеи расширения языков.

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

4. Lisp2D

Lisp2D - это экспериментальный функциональный язык, созданный для изучения техники параллельного программирования.

Функции в этом языке - это отображения из поля объектов в поле объектов.

Объект - либо атом либо структура объектов.

Атом - неделимый объект, может быть разных типов: числа, символы, строки, массивы, функции, лексические замыкания. Также есть типы, состоящие из одного объекта: t - логическая правда (true), ui - неопределенность (unidentified).

Структура - это пара ссылок на другие объекты. Первый (головной) элемент обозначается car, второй (хвостовой) - cdr. В отличие от классического Лиспа эта пара имеет ориентацию в задачно-временном пространстве. Пара, ориентированная вдоль временной оси называется последовательной и обозначается (car . cdr), ориентированная же вдоль задачной оси называется параллельной и обозначается [car . cdr].

Список - это пары, соединенные специальным образом: (a . (b . (... . ( z . nil))...), в зависимости от ориентации пар списки бывают последовательные и параллельные, и обозначаются соответственно: (a b ... z) или [a b ... z].

Интерпретатор принимает объект с консоли или из файла, вычисляет его и возвращает результат.

Результатом атома будет само значение атома, за исключением символов. Если с символом связано какое либо значение в текущем окружении, то возвращается это значение, иначе возникает ошибка интерпретатора и возвращается ui.

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

(function arg1 arg2 … argn)

Порядок вычисления функции и самих аргументов зависит от вызываемой функции и задается во время ее определения

На месте function может стоять символ, функция, лексическое замыкание или структура функций.

Если function - символ то берется функциональное значение символа из текущего функционального окружения и это значение применяется к окружению. При отсутствии функционального значения происходит ошибка интерпретатора и возвращается ui.

Определить функциональное значение для символа можно функцией defun.

(defun name arglist body) или [defun name arglist body]

Функция может быть откомпилированной или лямбда-вызовом. Лямда-вызов - это определение функции без имени.

(lambda arglist body) или [lambda arglist body]

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

arglist - список формальных имен аргументов, которые связываются с фактическими значениями и имеют действие только во время выполнения тела body. Извне этой формы значения формальных параметров недоступны.

Ориентация списка определяет порядок вычисления аргументов, также этот список может состоять из подсписков другой ориентации. Например:

(x [y (z t)] a) - определяет, что t должен вычислятся после z, а a - после всех аргументов в этой форме, y же должен вычисляться после x, и независимо от z и t. Порядок подачи аргументов для функции должен соответсвовать порядку в arglist:

(name x1 y1 z1 t1 a1)

Лексическое замыкание - это объект, являющийся функцией и одновременно имеющий несколько объектов, которые описывают его состояние. Введен в Лисп специально для удобства программирования в объектно-ориентированном стиле, также может применяться и при определении автоматов.

Структура функций на месте головной части формы реализует концепцию одно данное-много функций. Последовательный список функций (f g h) интерпретируется как конкатенация функций (f (g (h args))). Точнее, правило преобразования выглядит так:

((f g h) .arglist) <=> (f (g (h (nil .arglist))))

Пустой список nil на месте функции определен как функция идентичности и возвращает свои аргументы:

(nil 'a 'b 'c) -> [a b c]

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

(sincos x) -> [(sin x) (cos x)] ,

, тогда:

(+ (sincos x)) -> (+ (sin x) (cos x))

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

Также на месте функции может стоять параллельный список [f g h], вычисление формы ([f g h] .arglist) приводит к параллельному исполнению нескольких форм:

(f .arglist) (g .arglist) (h .arglist)

Результатом вызова будет параллельный список соответствующих результатов:

[ (f .arglist) (g .arglist) (h .arglist) ]

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

((+ [sin (cos 1+)]) x) -> (+ (sin x) (cos (1+ x)))

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

Естественно, что на практике ресурсы ограничены, и для того чтобы аргумент формы ([f g h] (z x)) вычислялся один раз, нужно это задать явно: (([f g h] z) x),или (apply '[f g h] (z x)) или использовать дополнительную переменную.

5. Преимущества специального языка для ПП

С помощью описанного метода регулировки порядка вычислений программисту существенно проще программировать параллельные программы, так как большую часть синхронизации берет на себя интерпретатор. Например параллельное вычисление аргументов функции с последующим присваиванием значений формальным параметрам функции скрывает в себе точку синхронизации окончания вычисления всех аргументов. Автоматическое приостановка процесса для ожидания значения аргумента в случае моментальных функций (определенных [defun name arglist body]) скрывает в себе весь процесс проверки готовности результата и остановка/запуск процесса. В большинстве случаев при практическом программировании можно обойтись без специальных системных функций таких как (wait x) - остановка процесса до определения значения x, (lock x) (unlock x) - дополнительные функции для доступа к разделяемым данным. Их использование засоряет текст программы и затрудняет понимание работы всего процесса.

Программирование с непосредственным управлением синхронизацией процессов и совместным пользованием данными требует такого же искоренения как в свое время был искоренен принцип управления последовательностью работы программы с помощью goto. Появились структуры while, for, do, until, которые по сути скрывали в себе необходимые команды управления.

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

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

6. Примеры программ на Lisp2D

Задача: найти наибольшее значение в массиве элементов.

Делим массив на две части, для каждой части в отдельности решаем задачу рекурсивно. Результат возвращаем как максимум двух решений для половин массива. Для Common Lisp-а программа выглядит так:

(defun max2 (a b)  ;вспомогательная функция для двух аргументов
   (if (< a b) b a))

(defun find-max (arr begin n)
  (if (= n 1)
    (aref arr begin)) ;если элемент один – то его и возвращаем
    (max2              ;берем максимум
      (find-max arr begin (div n 2)) ;первая половина
      (find-max arr (+ begin (div n 2)) (- n (div n 2)))))) ;вторая половина

;запускаем функцию
(find-max arr 0 (length arr))

Для того, чтобы рекурсии для разный частей массива выполнялись параллельно, достаточно, чтобы функция max2 вычисляла свои аргументы параллельно. Соответсвующая программа на Lisp2D будет выглядеть так:

(defun max2 [a b]  ;здесь любые аргументы будут вычисляться параллельно
   (if (< a b) b a))

(defun find-max [arr begin n] ;маленькая оптимизация не помешает
  (if (= n 1)
    (aref arr begin)) ;если элемент один – то его и возвращаем
      (max2              ;берем максимум
        (find-max arr begin (div n 2)) ;первая половина – параллельно с …
        (find-max arr (+ begin (div n 2)) (- n (div n 2)))))) ;второй половиной

;запускаем функцию
(find-max arr 0 (length arr))

Пример использования моментального запуска функции:

[defun fast* [a b] ;функция запускается не дожидаясь значений аргументов
  (if (= a 0)      ;здесь остановка до получения значения a
    0              ;возвращает очевидный результат и процесс вычисления
                   ;второго аргумента прекращается автоматически
    (* a b))]      ;обычная функция

;попробуем
(fast* (- 1 1) (loop)) ->
0

Несмотря на то, что второй аргумент для функции никогда не вычислится, результат формы будет определен.

Пример использования составных и многозначных функций:

;выполнение sin(x) и cos(x) – параллельное,f(x) – вычисляется 2 раза параллельно
([sin cos] (f x)) -> [sin(f(x)) cos(f(x))]

(defun distance (x y)
  (sqrt (+ (* x x) (* y y))))

(distance ([sin cos] (f x))) ->
1

(defun sqrt2 (x)
   (if (< x 0)
       ([+ -] #C(0 (sqrt (- x))))
       (sqrt x)))

(sqrt2 1) ->
1

(sqrt2 -1) -> [#C(0 1) #C(0 -1)]

Вычисление составной функции Distance(sin(f(x)),cos(f(x))):

((distance [sin cos] f) x) ->
1

Краткая сводка встроенных функций

(- a b) – вычитание
(+ a ... b) – сложение
(* a ... b) – умножение
(= a b) – сравнение
(aref  arr i) – взятие i-го элемента массива
(defun name arglist body) – определение функции
(div x y) – целая часть деления x/y
(if test body-true body-false) – разветвление алгоритма:
    если test<>nil выполняется body-true, иначе body-false
(length arr) – длина массива
(loop body) – бесконечное циклическое выполнение body