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

30

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

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

Николас Манкузо
источник

Ответы:

19

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

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

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

Суреш Венкат
источник
Мастерская DIMACs великолепна! Спасибо.
Николас Манкузо
3
В 2009 году был проведен более ранний семинар umiacs.umd.edu/conferences/tmc2009, который, как мне показалось, был еще более отточен, чем недавний DIMAC. Лесли Валиант представил там модель Multi-BSP (более подробно обсуждаемую на семинаре этого года), а Фил Гиббонс из Intel представил провокационную лекцию « Теория: спит при переходе на многоядерный процессор, на которую стоит взглянуть». Для меня семинар DIMAC был слишком сосредоточен на MapReduce, который Google больше не использует для создания своего веб-индекса.
Андрас Саламон
это правда. Я забыл о предыдущем.
Суреш Венкат
22

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

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

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

Дублирование только арифметики дает вам инструкции 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. Я широко использую термин «модель», охватывающий абстрактные машины как для формальных, так и для программных целей.

говяжий
источник
Я не понимаю, как mapreduce формирует дерево. Могли бы вы объяснить?
Рико Джейкоб
@Riko Jacob, допустим, вы сопоставляете «+» с (1 2 3 4), концептуально это создает дерево приложений с «+» в каждом узле и каждым числом в виде листьев. Снижать (или сворачивать, если вы из haskel) свернет каждый узел с данными его потомков.
Говядина
Гектометр Я понимаю, что поток данных может быть деревом. Почему это всегда дерево? Скажем, входные данные «a, b» преобразуются, a в (x, 1), (y, 2), b в (x, 2), (y, 5), а затем уменьшаются с помощью «+», так что результат является (х, 3) и (у, 7). В этом примере соединения между обоими входами с обоими выходами, который является который не является деревом. K2,2
Рико Джейкоб
Если вы не учитываете создание самого графа (например, сопоставление a, b с парами ключ / вейл), вы получите два дерева, выполняющих редукцию, с небольшим количеством доброй воли :) Возможно, это скорее k-связанный или решетчатый граф как вы сказали. Вы правы, что оно немного более общее, чем простое дерево. Я пытался провести различие с более общими структурами потока данных DAG.
Говядина
8

Для архитектур с передачей сообщений модель, которая очень похожа на 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 обычно имеют теоретический анализ сложности, очень близкий к фактическому времени, определенному экспериментально при их реализации и сравнительном анализе.

Массимо Кафаро
источник
4

Из того, что я знаю, модели 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), смоделированные как параллельные компьютеры, лично я думаю, что это очень интересная тема исследования. Кто знает, что в будущем процессоры будут созданы таким образом, как небольшие вычислительные пространства. У меня нет твердой ссылки на это, вы можете посмотреть в Интернете.

labotsirc
источник
3

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

Рико Джейкоб
источник
Не существует конкретной модели затрат, связанной с функциональным программированием, поэтому это не отвечает на вопрос. См. Cstheory.stackexchange.com/questions/376/…
Чарльз Стюарт
2
Механизмом оценки для таких языков, основанных на лямбда-исчислении, является редукция, которая на самом деле не имеет прямого сопоставления с реальным оборудованием. Вот почему Haskell по-прежнему должен вводить явные параллельные конструкции, такие как «par». ссылка: csg.csail.mit.edu/projects/languages/ph.shtml
Говядина
3

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

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

Чад Brewbaker
источник
-3

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

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

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

ВЗН
источник
опять таки. Я прошу модели или параллельные вычисления. Не инструменты. MapReduce является одной из таких моделей. Однако Hadoop и NoSQL нет. Hadoop - это Java-версия MapReduce. Насколько я могу судить, NoSQL - это модель для расслабленных хранилищ ключей.
Николас Манкузо
MapReduce начинал как инструмент и постепенно перешел к модели благодаря широкому использованию / внедрению. то же самое с другими. Hadoop не идентичен MapReduce, но, возможно, похож. да, я думаю, что я был сбит с толку ответом Suresh, который включал MapReduce ... люди, кажется, не очень заботятся или предпочитают не обсуждать реальные программные pkgs на этом сайте ... независимо от того, насколько широко они используются .. даже при условии , что они вдохновляют / crosspollinate / диск твердую позже теории как и MapReduce ... мои плохие = (
ВЗН
2
Дело в том, что вы не отвечаете на вопрос. политика здесь такова, что предложения, косвенно связанные с этим вопросом, не являются приемлемыми ответами. если вам не нравится эта политика, вы можете отказаться от участия. если бы у вас были реальные идеи о том, как смоделировать реальную параллельную систему, это было бы больше по теме (хотя это еще не ответ на заданный вопрос)
Сашо Николов
-3

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

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

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

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

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

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

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

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

ВЗН
источник
-6

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

возможно, лучшая связь связана с алгоритмом поиска Гроверса, который, как недавно было показано, является более общим в том смысле, что его можно использовать для ускорения в большинстве задач полного 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

ВЗН
источник
@vnz, это, кажется, в лучшем случае случайная мешанина понятий. Гуглить «параллельный квант» и перечислять результаты здесь бесполезно для меня и других читающих это. Я думаю, что было бы лучше, если бы сообщество на самом деле отвечало на ответы, которые вам удобны и хорошо осведомлены, а не просто делало безумный рывок за очки репутации. Это неконструктивно и возможно неискренне думать о квантовых вычислениях как о параллельном поиске. Квантовые вычисления, если использовать ваше описание, имеют «сильные аналогии / связи» с вероятностным поиском, а не параллельными.
Николас Манкузо
Я не знаю, чему учат в классах, но если кто-то действительно имеет ССЫЛКУ, а не просто БЕСПРОВОДНЫЕ УКАЗАНИЯ, которые указывают, почему до сих пор нет обоснованности до сих пор не обнаруженного соответствия QM, выполняющего параллельные классические вычисления ... Я ПРОЧИТАЮ ЭТО. QM-вычисления возвращают точные ответы ala / напр., Краткий факторинг, иначе это не фактическая система вычислений ..... есть и другие способы, чем я рисую, чтобы продемонстрировать, что QM-вычисления в некотором смысле должны быть эквивалентны параллельным классическим вычислениям ... возможно так как его нет в учебнике, это должно быть неправильно, да !!
vzn
Здесь есть целый бесплатный курс по квантовым вычислениям: coursera.org, он может прояснить для вас вещи.
Николас Манкузо
ps что касается "сборной солянки" ... попробуйте на самом деле ПРОЧИТАТЬ ССЫЛКИ ... или, может быть, просто просматривая их в вашем случае;) =)
vzn
1
(6.) Ваша ссылка. [5] описывает способы, которыми алгоритм Гровера может быть расширен, опять же без учета параллелизма, который вы ищете в квантовых вычислениях. Итак, ваша интерпретация того, что существуют связи между квантовыми и параллельными вычислениями, кажется, происходит из интерпретации многих миров QM. Хотя это и не является неясным, оно также не является неопровержимым и, конечно, не позволяет нам продуктивно описывать квантовые вычисления как «параллельные вычисления», за исключением того, что мы не видим эти вычисления ... что не является сильным аргументом для их присутствие.
Ниль де Бодрап