Написание псевдокода для параллельного программирования

Псевдокод - это просто английский. Итак, вы можете использовать все, что ясно и недвусмысленно. Это не язык программирования, поэтому вам не нужно представлять такие операции, как «разброс» ... вы можете просто сказать «разброс».

Для псевдокода нет стандартов, но хороший псевдокод прост и понятен.

Я нашел как минимум один псевдоязык для параллельного программирования: Peril-L. Это формально, но, на мой вкус, слишком низко.

Попробуйте «написать диаграммы» здесь: http://www.websequencediagrams.com/

Вы получите лучшее из обоих миров, довольно простые английские утверждения («псевдокод») и чистые диаграммы. С помощью этих диаграмм я смог объяснить своим менеджерам и коллегам довольно сложное параллельное программирование. И последнее, но не менее важное: можно проверить "источник" диаграммы в системе управления версиями.

Короткий ответ на ваш вопрос: не существует традиционного способа написания псевдокода для параллельного программирования.

Это связано с тем, что существует множество способов параллельного программирования с точки зрения различных параллельных архитектур (например, SMP, графические процессоры, кластеры и другие экзотические системы) и подходов к параллельному программированию. Я имею в виду «подходы к программированию», потому что, как правило, большинство из них представляют собой библиотеки или аннотации, а не языки (см. MPI, OpenMP, TBB и т. Д.). Таким образом, даже если вы можете выбрать архитектуру и язык, вам будет сложно определить семантику библиотеки или системы аннотаций.

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

Вот два предложения:

• PRAM. Программирование с общей памятью тесно связано с моделью вычислений с параллельной машиной с произвольным доступом (PRAM). Это было широко изучено, и в нем разработано множество алгоритмов. Быстрый поиск литературы поможет найти подходящие обозначения PRAM.
• CSP. Связь последовательных процессов (CSP) - это формализм (алгебра) для выражения и рассуждения о системах передачи сообщений. Он оказал влияние на дизайн многих языков, особенно occam.

Модель PRAM очень проста и должна использоваться в качестве основы для обозначений программирования с общей памятью. Сам CSP может быть слишком математическим для псевдокода, а нотация оккама может быть слишком многословной. Так считал Бринч Хансен (великий специалист по параллельному программированию), который разработал свой родственный язык SuperPascal. , который будет использоваться в качестве обозначения для объяснения параллельных алгоритмов в публикациях.

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

Проведя некоторое исследование в Интернете, я понял, что своего рода стандарт все еще не существует. Как говорит @Larry Watanabe, псевдокод - это в значительной степени английский язык. Итак, вы можете использовать все, что ясно и недвусмысленно. Это не язык программирования, поэтому вам не нужно представлять такие операции, как scatter ... вы можете просто сказать scatter.

Итак, вот мое личное решение с использованием algorithm2e: не так много деталей о разделяемой памяти, локальной переменной и т. Д., Но с той же стратегией вы можете найти способ описать свою идею:

\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
...
\begin{algorithm}
    \DontPrintSemicolon 
    \SetKwBlock{DoParallel}{do in parallel}{end}
    \KwIn{Some inputs}
    \KwOut{The ouput}
    \DoParallel{
        Compute a \;
        Compute b \;
        Compute c \;
    }
    \DoParallel{
        a1\;
        b1\;
        c1\;
    }
    \Return{the solution}\;
    \caption{Parallel Algo}
    \label{algo:parallelAlgorithm}
\end{algorithm}

Результат:

Он основан на определении новой команды с использованием выражения \SetKwBlock. Руководство по использованию пакета можно найти здесь. Первоначально я разместил ответ на этот вопрос также здесь.

Использование стратегии определения ваших ключевых слов для описания вашего алгоритма с деталями, которые вы предпочитаете, всегда должно быть возможным. Учтите, что:

1. подробнее → подробнее вы будете ближе к своим языкам программирования.
2. меньше деталей → больше это можно рассматривать как псевдокод.

Заключение: это всегда вопрос компромиссов: вы сами решаете, где находится предел (с учетом целевых людей, на которых вы ссылаетесь).

Та же стратегия использовалась в журнальных статьях (например, см. Алгоритмы 3 и 4 в Документ IEEE).

Это эссе Мэтью Адамса, вероятно, лучшее введение, которое я видно, как пройти через многопоточный процесс с использованием псевдокода.

Рассматривали ли вы подход к разработке, основанной на поведении? Недавно я собрал довольно сложный многопроцессорный / многоядерный фрагмент кода, используя подход BDD, и нашел его очень полезным. Лучшая часть подхода заключалась в том, что я мог описать все простым английским языком и сосредоточиться на проблеме, а не на деталях реализации. Мои первые несколько итераций были однопоточными, чтобы гарантировать, что код прошел все тесты и решил проблему. Я повысил производительность системы, используя многопроцессорность в выбранных местах, убедившись, что она не нарушит тесты, которые прошла однопоточная система. Рефакторинг был намного проще, потому что код и без того был значительно проще, чем если бы я спроектировал вещи вокруг деталей оптимизации заранее, и я мог бы сосредоточиться на мониторинге времени обработки реформированных систем, поскольку я получал точно такие же результаты, как и предыдущие итерации.

Взгляните на книгу Разработка через тестирование для встроенного C по некоторым идеям. Я использовал эту книгу во время разработки и сделал ее постоянной частью моей библиотеки.