откуда у параллелизма ноги
Dec. 5th, 2012 11:51 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfВ императивных языках учитывается модель памяти. Это такая вещь, которая приводит в соответствие program order и platform memory order.
Так вот. Это не функциональные программы хорошо параллелизуются, ибо иммутабельные данные. Это функциональные программы трудно писать с мутабельными данными, ибо в них остутствует этот самый program order.
Так вот. Это не функциональные программы хорошо параллелизуются, ибо иммутабельные данные. Это функциональные программы трудно писать с мутабельными данными, ибо в них остутствует этот самый program order.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-12-06 12:14 pm (UTC)Как-то так.
no subject
Date: 2012-12-06 01:33 pm (UTC)Чистота, чёрч-россеровость, ссылочная прозрачноть тоже попадалось в списке похвал функциональщине, но я пока не понял, как это сочетается с линеаризацией.
Я на академичность не претендую, но очень польщён просвещением.
no subject
Date: 2012-12-06 02:48 pm (UTC)Нельзя. Ленивость как таковая вообще не допускает reordering. Компилятор может слегка отклоняться от порядка, предписываемого ленивостью, из-за чистоты.
Пределом разрешения reordering является сильная нормализация, которой даже в хаскеле нет, но есть в агде2. В хаскеле есть всего лишь чёрч-россеровость, более слабая форма reordering. Императивные языки тоже допускают reordering, но в ещё более слабой форме.
Расширенные возможности по reordering - это свойство чистых программ, а не ленивых. Скажем, mapreduce допускает реордеринг.
Следствием из Чёрч-россеровости является возможность отклоняться от порядка редукций, предписываемого ленивостью, если при этом не происходит зацикливания. При сильной нормализации зацикливания произойти не может при любом порядке.
Исполнять редукции выгоднее всего в аппликативном ("неленивом"), а не в нормальном ("ленивом") порядке, поэтому компилятор хаскеля пробует заменять порядок редукции на аппликативный, где это увеличит скорость, не раздует потребление памяти и не приведёт к зацикливаниям. Все эти анализы неразрешимы (как следствие - неполны) и являются оптимизациями (не могут ухудшить потребление ресурсов по сравнению с нормальным порядком), так что для 99% практических нужд можно считать, что программы на хаскеле исполняются в фиксированном нормальном порядке.
Иммутабельность способствует чистоте (и реордерингу), но возможна чистота вместе с мутабельностью (IORef в хаскеле).
К паралеллизму всё вышесказанное имеет, однако, весьма косвенное отношение.
Для паралеллизма важно, чтобы все программы из threads interleaving space имели одну и ту же семантику. Этому как раз способствует immutability. Если вы будете в хаскеле использовать IORefs (чистота без immutability) многопоточно, то получите по голове теми же проблемами с изменением семантики в зависимости от интерливинга, что и в императивных программах.
Отправными точками в дизайне хаскеля являются нестрогость и тьюринг-полнота. Затем выбрали ленивый порядок как способ реализовать нестрогость. Затем решили, что человеку трудно думать в ленивом порядке, и решили, что нужно как-то писать программы, чтобы не было необходимости всегда думать в ленивом порядке. Затем поняли, что если разрешить думать в произвольном порядке - то пропадет тьюринг-полнота, поэтому сошлись на чёрч-россеровости как компромиссном варианте. Получилось иммутабельно, и пришлось думать, как добавить мутабельность, сохранив чёрч-россеровость и предыдущие фичи. Придумали монады. Затем поняли, что получился язык, на котором очень хорошо контролировать мутабельность, и эта возможность контроля мутабельности оказалась полезна в многопоточном программировании.
no subject
Date: 2012-12-06 03:42 pm (UTC)Допускает. Это вот normal order evaluation не допускает ("всегда внутренний левый"), а lazy evaluation (graph reduction) допускает.
no subject
Date: 2012-12-06 04:15 pm (UTC)Общепринято считать семантикой функциональной части хаскеля call by need lambda calculus with whnf (формально это другое исчисление по сравнению с call by need lambda calculus with nf), а семантикой императивной - семантику из tackling the squad.
Lazy evaluation и call by need lambda calculus - это одно и то же. "Normal order reduction" - это call by name lambda calculus.
Системы редукции графов могут быть использована как формализм (clean), так и как средство реализации call by need (haskell). Общепринято как раз считать редукцию графов деталью реализации ghc. Call by need прекрасно описывается через дырки (evaluation contexts) безо всяких графов или через interaction nets, которые, насколько мне известно, не являются TGRS в общепринятом смысле.
Т.е. это вопрос договорённости. Общепринято, что семантика хаскеля (включая потребление ресурсов) - это редукция в нормальном порядке, реализация всего лишь может её оптимизировать.
Но в принципе, можно считать и что семантика хаскеля - это редукция до whnf, а какую нормализирующую стратегию использовать - неспецифицированно.
Можно спросить в кафе, пусть нас рассудят :)
no subject
Date: 2012-12-06 04:04 pm (UTC)о. вот это и есть linearizability.
"Компилятор может слегка отклоняться от порядка, предписываемого ленивостью"
Хм, я думал, ленивость не предписывает порядок, ибо статьи о реализации рассуждают о возможности исполнять что-то спекулятивно, и что есть общая очередь спарков, которые должны сейчас выполняться, и что "агенты"=железные потоки выполняют любой спарк по одному, а потому о предписываемом порядке вычислений говорить сложно.
В частности, в разделе проблем обсуждаются вопросы "как не засорить память промежуточными данными, которые потребитель не успевает проглотить". Я это воспринял как отсутствие ограничения на порядок исполнения, и лишь как оптимизацию.
Или в каком смысле тогда порядок предписан?
А ещё вот такой вопрос. Blackholing - это, конечно, всего-лишь реализация концепции не-повторения вычислений. Я затрудняюсь решить, как это называется формально, но мне кажется, это вводит в код сериализацию. В императиве как раз один из трюков - до какой-то степени разрешить дублирование вычислений. Как-то можно этим управлять в, скажем, хаскелле?
"Пределом разрешения reordering является сильная нормализация, которой даже в хаскеле нет, но есть в агде2. В хаскеле есть всего лишь чёрч-россеровость, более слабая форма reordering. Императивные языки тоже допускают reordering, но в ещё более слабой форме."
Ага, хорошо. Агду пока страшно :)
Тогда этот пост о том, что я обнаружил, что reordering в хаскеле > reordering в императиве.
Ну, и спасибо за экскурс. Теперь понятно, почему никто не мог ответить "какая в хаскелле модель памяти?" - потому что на самом деле нужно искать литературу по чёрч-россеровости и сильным норальным формам.
no subject
Date: 2012-12-06 04:41 pm (UTC)> и сильным норальным формам.
Ищите литературу по strictness analysis - это часть оптимизатора, которая решает, что можно переставлять, а что нельзя. Возможно, там будет менее академическим языком описано то, что вы ищете.
no subject
Date: 2012-12-06 05:05 pm (UTC)> реализация концепции не-повторения вычислений.
Тут важно, что ленивостью предписано, в каких случаях вычисления повторяются, а в каких нет. Это не "автоматическая дедупликация всего", а жесткие и очень примитивные синтаксические правила, вроде того как в Си жестко задано, что longFunction в int x = longFunction(); for (;;) { }; вычисляется один раз если снаружи цикла, и столько раз сколько отрабатывает цикл, если внутри.
> В императиве как раз один из трюков - до какой-то
> степени разрешить дублирование вычислений.
> Как-то можно этим управлять в, скажем, хаскелле?
Да, для тонкого управления есть strictness annotations, и в высокопроизводительном коде приходится подсказывать компилятору.
no subject
Date: 2012-12-06 05:15 pm (UTC)> хаскеле > reordering в императиве.
Ага. Но не по той причине, и к паралеллизму не относится.
> Теперь понятно, почему никто не мог ответить
> "какая в хаскелле модель памяти?"
Система типов позволяет реализовывать произвольные модели памяти, и есть достаточно много разных библиотек с разными моделями:
http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_and_parallelism
Есть все традиционные и все экзотические модели :)
Наиболее интересные на мой взгляд - это
Cloud Haskell
Software Transactional Memory
CHP: Communicating Haskell Processes
Repa
no subject
Date: 2012-12-06 05:27 pm (UTC)Это называется serializability (of interleaving).
> Или в каком смысле тогда порядок предписан?
В таком же смысле, в каком он предписан в императивных языках. Если вы пишете
x = 5;
y = 6;
return x;
То предписано, что сначала делается x = 5, потом y = 6, потом return x.
Но если компилятор может доказать, что перестановка ничего не меняет - то он может всё попересталять:
return 5;
y = 6;
x = 5;
Но от этого никто не говорит, что в императивных программах порядок выполнения не определён :) И при написании программы рассуждает так, как будто порядок именно такой, как он написал и не рассматривает всевозможные эквивалентные порядки.
Отличия лишь в том, что в хаскеле у оптимизатора больше свободы и программист, привыкнув к чёрч-россеровости, освобожден от необходимости думать о порядке. Освобождение от размышлений о порядке - это один из столпов освоения функционального программирования. Для начала нужно заменить временные отношения на структурные - вместо "раньше" и "позже" применять "синтаксически снаружи" и "синтаксически внутри". В-общем, для эффективного использования нужно учиться думать по-особому.
При оценке потребления ресурсов конечно приходится думать о порядке, но в 99% случаев считаешь, что порядок нормальный, и только в 1% надо пускать профайлер или смотреть в генерируемый код, чтобы узнать реальный порядок.
no subject
Date: 2012-12-06 06:05 pm (UTC)здесь пересечение терминологии, по-видимому. Я о линеаризации в смысле как здесь: Linearizability: A Correctness Condition for Concurrent Objects, M. Herlihy and J.Wing, Proceedings of 14th ACM Symposium on Principles of Programming Languages, 1987
"Но от этого никто не говорит, что в императивных программах порядок выполнения не определён :) И при написании программы рассуждает так, как будто порядок именно такой, как он написал и не рассматривает всевозможные эквивалентные порядки."
Да, понятный пример. Тогда да, я думаю лишь о реализации, дающей результат, эквивалентный какому-то там каноническому, который я ещё не изучал.
no subject
Date: 2012-12-10 12:56 pm (UTC)no subject
Date: 2012-12-10 01:29 pm (UTC)Никаким. Я же так и писал - "весьма косвенное отношение".
"Отклоняться от порядка редукций" ничего не значит, т.к. это нестрогая формулировка, объяснение на пальцах. Ознакомьтесь со строгой версией.
http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting - 3 глава про системы перезаписи графов, и 5 глава про concurrency. У пиратов есть в пдф одним куском.
Но это очень маленький кусочек необходимых знаний, если хотите глубоко копать. Например, вам должна стать непонятной связь FGRS и лямбда-исчисления. Вас должно запутать, что G-machine - это не реализация FGRS.
См. также
- The Call-by-Need Lambda Calculus by John Maraist, Martin Odersky, Philip Wadler;
- http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/ (4 глава)
- http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3918
и т. д.
Ещё учтите, что Parallelism != Concurrency и tackling the squad посвящён concurrency, а вы говорите именно о паралеллизме. И MPI is all about parallelism, but Erlang is all about concurrency.
Отвечая непосредственно на ваш вопрос - есть теоремы о возможности параллельных редукций с сохранением семантики.
no subject
Date: 2012-12-10 01:59 pm (UTC)no subject
Date: 2012-12-10 02:13 pm (UTC)