Что такое «Hello World» параллельных программ?

Question

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

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

Я знаю о Обедающей философской проблеме , и это было бы приемлемо, но мне интересно, есть ли ещеубедительные, но не менее простые проблемы.

Answer 1

Производитель-потребитель проблема.

Answer 2

Я обычно использую простой сценарий "банковский перевод".Например, я опубликовал один такой тривиальный случай в этом вопросе о транзакциях .

Это хороший пример для изложения, потому что:

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

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

Answer 3

Раньше был пример Java-апплета (вполне возможно, до сих пор), который вы использовали для проверки того, какой алгоритм планирования использует ваша JVM и соответствующая ОС.Он анимировал две (или, может быть, больше, не помню) полосы, постепенно заполняющиеся, каждая из которых анимирована отдельным потоком с одинаковым приоритетом.

Эквивалент, который печатает:

red 1
red 2
green 1
red 3
green 2

и т. Д.на консоль, мне кажется, ближе всего по духу к природе «привет, мир».То есть «могу ли я заставить компьютер делать что-то бесполезное, но видимое?»

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

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

Answer 4

Я не думаю, что есть стандартная первая программа для демонстрации того, что параллелизм работает, как "Hello world" для последовательных программ.

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

Одной вещью, которая демонстрирует параллелизм и является относительно простой, является совместный подсчет: параллельные потоки (или что-то еще) имеют внутренний счетчик, который они отправляют друг другу, и устанавливают на то, что они получают, плюс один. (Я сделал это с помощью трех LEGO Mindstorms RCX по инфракрасному каналу несколько лет назад, сработал хорошо.)

Кстати: «Hello world» встроенного программиста - это мигающий светодиод.

Answer 5

Вы можете отслеживать трассировку "Hello" и "World" в отдельных потоках. Или оживите "Hello", пока "World" отслеживает лучи.