Текущие параллельные модели для расчетов

В 1980-х годах появились модели параллельных вычислений PRAM и BSP . Кажется, что расцвет обеих моделей был в конце 80-х и начале 90-х годов.

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

Есть несколько моделей, но некоторые из наиболее заметных:

1. Модели MUD и Mapreduce , которые в первую очередь предназначены для захвата среды MapReduce, но в более общем плане могут рассматриваться как модели вычислений с параллельным распределением
2. Различные многоядерные модели , которые были предложены (но ни в коем случае не являются стандартом)

В прошлом месяце в DIMACS был семинар на эту тему: просмотр тезисов даст вам больше советов.

Заранее извиняюсь за формат блога моего ответа. Я не мог не сделать небольшой обзор мира параллельных вычислений.

Вы можете классифицировать модели параллельного программирования примерно на две категории: модели потока управления и потока данных.

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

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

Дублирование ALU и ПК, но хранение секвенсора команд внутри блока управления дает вам выполнение вне очереди (OoO), которое приводит к некоторому конвейерному параллелизму. В этой категории у вас также есть техника очень длинных инструкций (VLWI) и методы прогнозирования ветвлений. Вы редко видите эту категорию на уровне программного обеспечения.

Пройдя немного дальше, вы продублируете все «ядро», но сохраняете общую память, это текущие многоядерные процессоры, которые обеспечивают параллелизм задач (или потоков). Совместное использование памяти в этом контексте дает вам очень, очень сложные и тонкие проблемы параллелизма . Параллельные вычисления на текущем многоядерном процессоре, таким образом, полностью вращаются вокруг проблем синхронизации / параллелизма, тщательного баланса производительности (без синхронизации) и желаемой семантики (полностью синхронизированная, семантика последовательного выполнения). Примером этого является PRAM или более популярный в наши дни Cilk ofshoots, такой как fork / join ( IntelTBB , Java.Utils.Concurrency). Модели CSP и Actor являются моделями параллелизма, но, как упоминалось выше, параллелизм и параллелизм размываются в среде с общей памятью. nb параллелизм для производительности, параллелизма для поддержания правильной семантики.

Дублирование памяти также дает вам либо сетевые компьютеры, которые запрограммированы на MPI и тому подобное, либо просто странные архитектуры, отличные от фон Неймана, такие как процессоры «сеть на кристалле» (облачный процессор, Transputer, Tilera). Модели памяти, такие как UMA или NUMA, пытаются поддерживать иллюзию совместной памяти и могут существовать как на программном, так и на аппаратном уровне. MPI поддерживает параллелизм на уровне программы и обменивается данными только через передачу сообщений. Передача сообщений также используется на аппаратном уровне для связи и параллелизма (Transputer).

Вторая категория - это модели потоков данных . Они были разработаны на заре компьютерной эры как способ записывать и выполнять параллельные вычисления, избегая дизайна фон Неймана. Они вышли из моды (для параллельных вычислений) к 80-м годам после того, как последовательная производительность выросла в геометрической прогрессии. Однако многие системы параллельного программирования, такие как Google MapReduce, Microsoft Dryad или Intel Concurrent Collections, на самом деле являются вычислительными моделями потоков данных. В какой-то момент они представляют вычисления в виде графика и используют его для руководства выполнением.

Указывая части моделей, вы получаете разные категории и семантику для модели потока данных. Что вы ограничиваете форму графика: DAG (CnC, Dryad), дерево (mapreduce), орграф? Есть ли строгая семантика синхронизации ( Luster, реактивное программирование]? Запрещаете ли вы рекурсию иметь статическое расписание (StreaMIT) или вы предоставляете более выразительные возможности, имея динамический планировщик (Intel CnC)? Есть ли ограничение на количество входящих или исходящих ребер? Позволяет ли семантика обжига запустить узел, когда доступно подмножество входящих данных? Являются ли ребра потоками данных (обработка потоков) или единичными токенами данных (статическое / динамическое одиночное назначение). Для связанной работы вы могли бы начать с изучения работы по исследованию потоков данных таких людей, как Арвинд, К. Кави, j. Шарп, В. Аккерман, Р. Джаганнатан и др.

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

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

Для архитектур с передачей сообщений модель, которая очень похожа на BSP, но с которой легче иметь дело, а анализ производительности, близкий к тому, что вы действительно получаете на реальной машине, - это, конечно, CGM или Coarse Grained Multicomputer. Это было предложено Фрэнком Дене, и вы найдете много интересных работ, представляющих алгоритмы, разработанные в этом контексте.

CGM подходит для крупнозернистых архитектур, предполагая, что имеется p процессоров, каждый из которых имеет O (n / p) локальную память и размер входного n намного больше (на несколько порядков друг от друга), чем p, то есть p≪n. Таким образом, модель отображается намного лучше, чем другие на современных архитектурах; это было тщательно изучено. Модель основана на следующих предположениях: (i) алгоритмы выполняют так называемые суперэтапы, которые состоят из одной фазы локальных вычислений и одной фазы межпроцессорного взаимодействия с синхронизацией промежуточного барьера, (ii) все p-процессоры имеют доступ к O (n / p) локальной памяти, (iii) на каждом супершаге процессор может отправлять и принимать не более O (n / p) элементов и (iv) сеть связи между процессорами может быть произвольной. В этой модели алгоритм оценивается по времени его вычисления и количеству раундов связи. Хотя модель проста, тем не менее, она обеспечивает разумный прогноз реальных характеристик параллельных алгоритмов; действительно, параллельные алгоритмы для CGM обычно имеют теоретический анализ сложности, очень близкий к фактическому времени, определенному экспериментально при их реализации и сравнительном анализе.

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

Из того, что я знаю, модели BSP и LogP используются сегодня для распределенных алгоритмов. Кроме того, начиная с вычислений на GPU, PRAM вновь становится популярным, однако в анализ следует включить иерархии памяти. Вы можете проверить модель UPMH (унифицированная параллельная иерархия памяти), которая хорошо дополняет PRAM.

B. Alpern, L. Carter, E. Feig и T. Selker. Модель иерархии единой памяти вычислений. Algorithmica, 12: 72–109, 1994. 10.1007 / BF01185206.

Боуэн Алперн, Ларри Картер и Жанна Ферранте. Моделирование параллельных компьютеров как иерархий памяти. В в процессе. Модели программирования для массивно параллельных компьютеров, стр. 116–123. IEEE Computer Society Press, 1993.

Также для вычислений на GPU было предложено теоретическое моделирование вычислений; К-модель:

Габриэле Капаннини, Фабрицио Сильвестри и Раньери Баралья. K-модель: новая вычислительная модель для потоковых процессоров. В материалах 12-й Международной конференции IEEE 2010 года по высокопроизводительным вычислениям и связи, HPCC '10, стр. 239–246, Вашингтон, округ Колумбия, США, 2010 г. IEEE Computer Society.

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

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

Я предпочитаю подход Bader-Jaja (см. Раздел 2.1). Вы моделируете сложность как проблему передачи сообщений. Для каждого отправленного сообщения есть как переменная задержки, чтобы инициировать связь, так и переменная пропускная способность.

Пусть будет задержкой, будет пропускной способностью, будет размером сообщения, а будет числом процессоров. Для большинства масштабируемых сетей стоимость вещания составляет O (( + * ) log ).у т р т у т $t$$u$$m$$p$$t$$u$$m$$p$

Вы упомянули облачные вычисления специально. наблюдается в течение всего несколько лет интенсивных инноваций в этой области с упругим вычислительным облаком Amazon, в Google App Engine и различными инструментами и связанные с ними «моделями» обработки концептуальных параллельно.

К специальным инструментам с открытым исходным кодом относятся базы данных Google Mapreduce , Apache Hadoop и NoSQL, которые становятся новыми, сильными, широко адаптированными стандартами в алгоритмах распараллеливания, «лучших практиках» и «шаблонах проектирования». Кроме того, memcacheD все чаще используется в качестве распределенной базы данных в памяти. Примером этого является использование в Facebook, описанное в недавней статье [1].

[1] Многие ключевые хранилища ключей-значений от Berezecki et al.

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

см., например, Параллельные вероятностные вычисления на кластере рабочих станций Radenski, Vann, Norris:

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

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

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

Рассуждение о вероятностных параллельных программах Рао:

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

конечно, QM-вычисления очень похожи на вероятностные вычисления (хорошая ссылка, в которой подчеркивается, что это взгляд Теоретика Сложности на Квантовые Вычисления от Fortnow ), и есть некоторый намек, что эти подходы могут быть расширены там, например, в работе по параллельному моделированию QM.

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

возможно, лучшая связь связана с алгоритмом поиска Гроверса, который, как недавно было показано, является более общим в том смысле, что его можно использовать для ускорения в большинстве задач полного NP в целом [5]. Алгоритм Гроверса, похоже, имеет сильную аналогию / связь с параллельными алгоритмами поиска в базе данных. лучшие классические последовательные алгоритмы не могут обеспечить одинаковую производительность, но по крайней мере один авторитет в последнее время утверждает, что подходы QM к поиску на самом деле не превосходят распараллеленные классические алгоритмы. [1]

Еще одним доказательством являются схемы, которые явно смотрят на параллелизм в квантовом поиске, например [2]. также были предложены квантовые симуляторы, которые основаны на параллельной / распределенной обработке [3] [4] и поскольку схема хорошо вписывается и приводит к эффективному и удобному моделированию (30 кубитов моделируются в [3]), это преобразование безусловно, не просто совпадение и указывает на более глубокий мост между параллельными классическими вычислениями и вычислениями QM, но, вероятно, до сих пор не раскрыт.

[1] Практичен ли квантовый поиск? Виамонтес и др.

[2] Точный квантовый поиск по параллельным унитарным схемам различения У / Диана

[3] Универсальный параллельный симулятор для квантовых вычислений . Авторы: Niwa, Matsumoto, Imai.

[4] эффективные распределенные квантовые вычисления , Beals et al 2012

[5] Решение NP полных задач с квантовым поиском по Furer 2008