?

Log in

No account? Create an account

elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Развернутый комментарий про теоретико-параллельный доклад на JPoint 2014
elizarov

На доклады на конференции JPoint 2014 в Москве было выделено по 45 минут. Что можно рассказать за 45 минут из теоретического курса параллельного программирования, который, по-хорошему, занимает целый семестр? Цель моего доклада заключалась в том, чтобы дать слушателям минимально необходимую теоретическую базу, которая позволит прочитать и понять 17-у главу спецификации языка Java (JLS), которая четко регламентирует допустимое поведение многопоточных программ на Java на любой архитектуре CPU. Это значит, что программисту на Java не обязательно разбираться в подробностях и деталях реализации кэшей, протоколов когерентности, параллелизма на уровне инструкций, специальных инструкций и барьеров, как и других особенностей различных архитектур. Это задача для тех, кто пишет JVM или хочет написать самый быстрый код. Программист на Java может писать корректные многопоточные программы, если он четко понимает, какие исполнения его многопоточного кода допустимы с точки зрения спецификации языка Java.

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

Слайды с доклада:

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

Я предпочитаю термин линеаризуемость. С точки зрения теории параллельного программирования, он является синонимом термина атомарность, но на практике термин атомарность часто используется нестрого, внося путаницу. Даже 17-ая глава JLS (JMM) допускает вольность в этом вопросе. Раздел 17.7 назван "Non-atomic Treatment of double and long" и содержит утверждение что "Writes to and reads of references are always atomic" в том смысле, что даже если ссылка занимает 64 бита, её чтение и запись не может происходить двумя операциями над её 32-битными частями. Там не имеется в виду линеаризуемость операций над ссылками.

Термин линеаризуемость вообще не используется в JMM, однако легко видеть, что JMM обещает линейную-упорядоченность всем операциям синхронизации (17.4.4), которыми являются, в том числе, операции чтения и записи volatile переменных (17.4.2). Из этого напрямую следует, что операции над volatile переменными в Java линеаризуемы просто по определению этого термина. В теории, такие переменные называют атомарными регистрами. В тоже время, возможным исполнениям над обычными разделяемыми переменными (не помеченными как volatile) JMM дает большую свободу. Время доклада было слишком ограничено, чтобы рассказать, что обычные разделяемые переменные в Java соответствуют тому, что в теории называют регулярными регистрами, за исключением long и double, про которые можно разве что сказать, что они являются безопасными регистрами.

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

V. Garg. Concurrent and Distributed Computing in Java. 2004. Этот учебник содержит основные элементы как параллельного так и распределенного программированию. Он не большой, поэтому собственно многопоточному (параллельному) программированию там посвящено не очень много. Однако он и не сложен в понимании и дает материал в понятной и логичной последовательности. Дело в том, что параллельное и распределенное программирование использует практически одинаковый формализм и несмотря на то, что в первом случае процессы общаются через разделяемы объекты, а во втором случае, через передачу сообщений, некоторые результаты и алгоритмы имеют прямые параллели для того и другого случая. Многие практически интересные вещи, такие как, например, Data Race Detector (DRD), разрабатываемый в нашей компании, можно осознать и создать только понимая концепции и алгоритмы из обеих областей одновременно.

M. Herlihy. The Art of Multiprocessor Programming. 2012. Это фундаментальный труд, название которого не случайно перекликается с классическим трудом Дональда Кнута. Там действительно освещены все фундаментальные теоретические достижения именно многопоточного программированиям. Автор не отвлекается на теорию распределенного программирования, а дает очень хороший обзор современных алгоритмов работающих с общей памятью.

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

L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. 1978. Несмотря на то, что в этой работе речь идет о распределенной системе, именно в ней впервые введено понятие произошло до.

L. Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. 1979. В этой работе впервые вводится понятие поледовательной согласованности именно для того, чтобы специфицировать среду исполнения многопоточных программ. Удивительно, но по прошествии более чем 30 лет, оно до сих пор именно так и используется.

L. Lamport. The Mutual Exclusion Problem. Part I: A Theory of Interprocess Communication. 1980. В этой работе рассматривается проблема взаимного исключения, которую я не затрагивал в своем докладе, однако именно в этой работе есть апелляция к СТО, как обоснование необходимости действительно параллельного формализма параллельных вычислений, в котором бывают фундаментально параллельные (не упорядоченные отношением произошло до) операции.

L. Lamport. On Interprocess Communication. 1985. В ней заложены основы теории параллельного программирования. Именно в этой работе вводится понятие атомарного регистра, как и других, более слабых регулярного и безопасного. Показано как более сильные регистры можно построить из более слабых.

M. Herlihy, J. Wing. Linearizability: A Correctness Condition for Concurrent Objects. 1990. В этой работе дается определение линеаризуемости, которое фактически обобщает понятие атомарности на произвольный класс общих объектов.

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


  • 1

Re: золотой век многопоточного программирования в разд

Я вас не понимаю. Обобществление жён какое-то. При чём тут многократное чтение? Откуда взялось про наращивание памяти? И отдельно, откуда взялось про ln(n)? Потрудитесь изложить свою мысль полнее.

P.S. А перед этим неплохо было бы за "ВАша риторика догоняет и перегоняет Путинскую, поэтому доверия нет ни вам, ни вашим собеседникам" извиниться, если вы хотите продолжать дискуссию в конструктивном ключе.

Re: золотой век многопоточного программирования в разд

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

Re: золотой век многопоточного программирования в разд

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

Потому что я не вижу, как от этого не спасают локальные кеши -- на первом доступе скешировали ту самую ячейку, и дёргаем потом значение из кеша. Массивно-параллельные системы давно имеют многоуровневые кеши, которые в т.ч. покрывают и несколько потоков исполнения сразу (бытовой пример: несколько ядер/гипертредов с разделяемым L3 на интеловских процах).

Ну и вообще-то bandwidth в основную память растёт не по дням, а по часам (посмотрите на эволюцию DDR) при мизерном увеличении latency (которая всё равно покрывается паралеллизмом).

Только я что-то не пойму, при чём тут модели памяти, если честно.

Re: золотой век многопоточного программирования в разд

Уважаемый Алексей. Согласитесь, что основная загрузка средств вичислительной техники в наши дни - обработка изображений. Типовый формат - FullHD. 2 миллиона мегапикселей. Для быстрой обработки нужны два миллиона нитей. В идеале - 2 млн процессоров. Для 8 ядер - да, кеши решают вопрос. Но для 2 млн?

Re: золотой век многопоточного программирования в разд

"Для быстрой обработки нужны два миллиона нитей." <--- почему?
а) Зачем дробить задачу на *очень* мелкие куски, вплоть до пикселя?
б) Зачем каждой задаче отводить отдельный поток/процессор?

Ну а про скалирование кешей есть всячески замечательная статья от хардварщиков:
http://acg.cis.upenn.edu/papers/cacm12_why_coherence.pdf

Re: золотой век многопоточного программирования в разд

Спасибо за ссылку, почитаем.
Зачем каждой задаче отводить отдельный поток/процессор?
Что бы в реал тайме распознавать лица, предметы и т.д.
Что бы в реал тайме просчитывать блики, трассировку лучей.

Re: золотой век многопоточного программирования в разд

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

Re: золотой век многопоточного программирования в разд

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

Re: золотой век многопоточного программирования в разд

Я вот и спрашиваю, зачем нам миллион процессоров, когда можно обойтись всего сотней, как это делают GPU :) Результат же достигнут за приемлемую цену? Получите, распишитесь.

Re: золотой век многопоточного программирования в разд

А где вы видели GPU, распознающие лицо в 200 мс?

Re: золотой век многопоточного программирования в разд

Ну вот недавно в КРОК-е видел на проходной систему распознавания, работающую в реальном времени. Может, там и не 200мс, но масштаб времён такой.

Re: золотой век многопоточного программирования в разд

Я уже с 2000 слышу про такую систему у полиции, для поиска футбольных хулиганов, но не верю. В моём кармане пока даже Сири не работает. Я пробовал работать вместо клавиатуры. Но ужасно неудобно.

Re:Куда ш ты пропал, сердешный?

Вот,например, люди просто не хотят понимать:
reddit . com / r / explainlikeimfive / comments / 1qgd0p / eli5why_are_there_no_128_bit_processors_or_256 /

Re: Куда ш ты пропал, сердешный?

Опять всё в кучу: при чём тут битность процессоров?

Re: Куда ш ты пропал, сердешный?

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

  • 1