Примеры задач для параллельных вычислений - PullRequest
7 голосов
/ 18 августа 2010

В настоящее время используется множество парадигм и методов параллельного программирования. Программная транзакционная память, субъекты, параллелизм общего состояния, кортежные пространства и многое, многое другое.

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

Итак, кто-нибудь может указать мне на некоторые интересные наборы проблем, которые требуют реального параллелизма в интерактивной, возможно, даже распределенной среде, которые достаточно просты для использования в качестве примеров для парадигм параллелизма? В идеале я хочу найти ряд проблем, которые могли бы служить «тестом на недостаток» для парадигм параллелизма (или чтобы подчеркнуть их различия, поскольку каждая парадигма имеет свои сильные и слабые стороны).

Любая помощь очень ценится:)

1 Ответ

4 голосов
/ 19 августа 2010

Ранее я уже рассматривал эту точную проблему, предварительно предлагая некоторые парадигмы параллельного программирования: p

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

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

Единственные места, где, я думаю, вы могли бы найти источники вдохновения, были бы в отдельных реализациях.Erlang, Occam (и Occam-pi), Alice, CML, Concurrent Haskell и т. Д., Вероятно, имеют небольшие тестовые корпуса, но как проблемы, так и их реализации будут смещены в сторону их реализации на определенном языке (поскольку они, очевидно,реализуемо на этом языке!)Возможно, вы также можете обратиться к сообществам, работающим над типами многопартийных сеансов и различными исчислениями процесса , такими как pi-calculus, CCS и CSP, чтобы увидеть, какие системы они используютв качестве примера моделей.Идея стандартного, не зависящего от языка набора проблем для описания одновременных взаимодействующих систем привлекательна, но, на мой взгляд, несколько неуловима в данный момент.

...