Примеры задач для параллельных вычислений
Существует множество парадигм и методов параллельного программирования, используемых сегодня. Программная транзакционная память, субъекты, параллелизм общего состояния, кортежные пространства и многое, многое другое.
Однако мне не хватает библиотеки интересных тестовых задач для параллелизма. Один хорошо известный пример - «Проблема обедающих философов», которая не является ни достаточно сложной, ни мотивирующей, ни реалистичной. Кроме того, существует множество параллельных алгоритмов (умножение матриц, рендеринг, общий параллелизм вложенных данных), которые просто требуют распределения работы, но не обеспечивают реального параллелизма при обмене данными между потоками выполнения.
Итак, кто-нибудь может указать мне на некоторые интересные наборы проблем которые требуют реального параллелизма в интерактивной, возможно даже распределенной среде, которые достаточно просты для использования в качестве примеров для парадигм параллелизма? В идеале я хочу найти ряд проблем, которые могли бы служить «тестом на недостаток» для парадигм параллелизма (или чтобы подчеркнуть их различия, поскольку каждая парадигма имеет свои сильные и слабые стороны).
Любая помощь очень ценится:)
1 ответ
Я ранее рассматривал именно эту проблему, ранее сам предлагая некоторые парадигмы параллельного программирования: p
Тогда я пришел к выводу, что такой набор тестов не кажется действительно существовать независимо от языка. Хотя его существование могло бы быть полезным, похоже, есть несколько довольно веских причин, по которым этого не происходит (насколько мне известно).
В рамках параллельного программирования основное внимание уделяется параллелизму данных , так что одна и та же операция применяется параллельно к разным частям одного и того же набора данных. Виды параллелизма на уровне задач (т. Е. Разные задачи, выполняемые параллельно, возможно, совместно использующие данные), о которых, я думаю, вы говорите, на самом деле выполняются не очень часто. Я думаю, это потому, что это довольно сложно. Но я думаю, что это также довольно сложно, потому что большинство проблем не очень хорошо поддаются такому виду параллелизма. Описание распределенной системы в терминах примитивов параллелизма может быть полезным, но эти системы имеют тенденцию быть разделенными, так что существует протокол (письменный или подразумеваемый), модерирующий их взаимодействие. Люди склонны не думать о таких системах как о явно "параллельных" ситуациях программирования, даже если они рассматриваются в правильном фрейме (т. Е.рассматривая «клиент» и «сервер» как агентов, работающих параллельно с синхронизацией в некоторых точках).
Я думаю, что источники вдохновения можно найти только в отдельных реализациях. Erlang, Occam (и Occam-pi), Alice, CML, Concurrent Haskell и т. Д., Вероятно, будут иметь небольшие корпуса тестов, но как проблемы, так и их реализации будут предвзято относиться к возможности реализации в рамках определенного языка (потому что они, очевидно, реализуемый на этом языке!). Возможно, вы также можете обратиться к сообществам, работающим над типами многосторонних сеансов и различными вычислениями процессов , такими как пи-исчисление, CCS и CSP, чтобы узнать, какие системы они используют. в качестве примеров моделей. Идея стандартного не зависящего от языка набора задач для описания параллельных взаимодействующих систем кажется привлекательной, но на данный момент, я думаю, несколько неуловима.