Детерминированное параллельное программирование: декларативный параллелизм
Предыдущая серия со ссылками на ранние:
Декларативный параллелизм -- это первая и простейшая форма детерминированного параллелизма. Декларативный параллелизм характеризуется главным плюсом функционального программирования в параллельной модели: все вычисления чистые, они всегда дают один и тот же результат с одними и теми же входными данными. Другими словами, отсутствует race condition.
К функциональной парадигме добавляются две концепции: нити и переменные dataflow (см. предыдущие серии).
Нить -- это последовательность инструкций, которая исполняется независимо от других нитей (рекурсивное определение :). Нити по сути выполняют всего одну операцию: получают некоторую функцию как аргумент и исполняют её внутри себя.
Переменная dataflow -- это переменная с однократным присваиванием, которая используется для синхронизации. Переменные dataflow поддерживают три операции:
- создать новую переменную dataflow с заданным идентификатором X;
- связать X со значением (например, взять значение из другой существующей переменной dataflow);
- сообщить текущей нити, когда X будет связана со значением.
Например, функция сложения двух чисел X и Y -- Add(X,Y,Z) (результат в декларативной модели возвращается через отдельный параметр Z, передающийся «по ссылке») -- может работать так:
- ждать связывания X;
- ждать связывания Y;
- рассчитать сумму X+Y;
- связать Z с рассчитанной суммой.
В качестве операции ожидания связывания может быть задействован классический оператор IF, и в итоге мы получаем полноценный декларативный dataflow язык.
Приведу более наглядный пример по этой теме из моего курса по парадигмам программирования на Julia:
"В целом, парадигма Dataflow отличается, во-первых, независимыми корректными вычислениями независимо от того, как они распределяются по параллельным процессам.
Например, имеются три функции, первая из которых возводит глобальную переменную X в квадрат, как только она будет определена. Вторая функция задаёт переменной X значение 9, и третья функция выполняет задержку работы всей программы на 10 секунд. В каком бы порядке мы не стали вызывать эти функции, как бы мы не распределили их по нитям, итог всегда будет один и тот же: программа замирает на 10 секунд и выдаёт значение 81.
И во-вторых, сами вычисления скромны и терпеливы: они не посылают никаких сигналов, а просто ждут, когда активизируются нужные им данные".
Ленивый декларативный параллелизм
В ленивом исполнении решение о том, надо ли выполнять некоторое вычисление, принимает не поставщик результата, а его потребитель. То есть в петле обратной связи условие завершения вычисления контролируется пользователем этого вычисления, а не "поставщиком", который вообще может быть представлен (запрограммирован) как бесконечный цикл.
Ленивое исполнение подразумевает наименьшее количество вычислений, необходимое для получения результата. Мы делаем декларативный параллелизм ленивым, добавляя всего одну концепцию -- синхронизацию по необходимости, которая реализуется одной операцией: текущая нить ожидает, когда какая-нибудь другая нить запросит ожидание связывания некоторой ячейки X (не само связывание, а именно пока только его ожидание).
Идея в том, что пока X никому не понадобилась, её и не надо вычислять.
Ленивая версия функции Add(X,Y,Z) запишется так:
- ожидать, когда запросится связывание Z;
- рассчитать сумму X+Y;
- связать Z с рассчитанной суммой.
Откуда, понятно, потянется ленивая цепочка связывания X и Y, и т. д.
Резюме
С массовым распространением многоядерных процессоров актуальность параллельных вычислений резко выросла, однако массовые языки программирования поддерживают её и по сей день усложнённо, непрозрачно и весьма невыразительно. Идеального решения здесь нету, а главный путь -- это повышение наглядности и выразительности механизмов параллельных вычислений с акцентом на повышении детерминистичности системы. Например, неплохая модель параллельного программирования -- это организация независимо действующих агентов, связанных потоками сообщений. Такие программы легко распараллеливаются, например, распределением агентов по ядрам процессора.
Декларативный параллелизм в данном случае очень хорошая парадигма, потому что в ней активно применяются сильные идеи функционального программирования. В ней отсутствуют race conditions: любая часть программы может быть выполнена независимо, без влияния на результат. Проблемы возникают, как только начинают использоваться парадигмы с именованными состояниями (переменными), подразумевающими последовательности значений, растянутые во времени.
= = =
В заключение познакомимся с программированием в ограничениях. Это, так сказать, "самая декларативная" парадигма во всей таксономии, самая её первоначальная, родная версия: сказать компьютеру, что нужно сделать, вместо того, чтобы подробно объяснять, как это рассчитать. Эта парадигма обеспечивает высокий уровень абстракции для решения задач с глобальными целями. Программирование в ограничениях, начав своё развитие в 1970-х, сегодня достигло высокой степени зрелости, и например такие системы, как SMT-солверы, эффективно находят весьма и весьма сложные решения задач и доказывают серьёзные теоремы.
Высшая школа программирования Сергея Бобровского
