Здравствуйте, Didro, Вы писали:

D>Я ошибся в названии второй задачи — не "Суммирование с использованием древовидной свертки", а "Суммирование с использованием древовидной свертки на базе асинхронных списков", возможно Вы имеено так меня и поняли. Собственно я эту задачу отнес к разряду интересных, поскольку в ней явно присутствует динамичность (зависимость от потока данных), что отличает её от стандартных типовых задач по параллельному программированию и придает оттенок задачи реального времени. Опыта у меня немного, и поэтому возможно я и ошибаюсь. Скажем тоже параллельное преобразование Фурье, оно, если говорить о не о задаче потокового преобразования Фурье, ближе к большим задачам и типовым задачам. Конечно это все непринципиально, просто решил уточнить. (вообще для меня 2-мя самыми частными премерами в параллельном программировании стали перемножение матриц и "параллельный Фурье").

Вы правы, я хотел подчеркнуть, что именно зависимость от потока данных является самым интересным местом в приведенной ссылке. Дело тут даже не в близости к задачам реального времени, а в иной модели (парадигме) параллельного программирования. То, что Вы называете типовыми задачами, по всей видимости, следует отнести к императивной модели программирования или, иначе говоря, стилю Фон-Неймана. В этой модели программа представляет собой запись некоторого алгоритма, т.е. четко заданной последовательности операций. В результате, при переходе к параллельным вычислениям алгоритмы, составленные для последовательных вычислений, становятся неэффективными и приходится развивать целую теорию эквивалентных преобразований программ на основе графа алгоритма, о чем очень подробно написано в известной книге В.В. Воеводин, Вл.В. Воеводин "Параллельные вычисления". Это, так сказать, классический подход.

Альтернативой является управление вычислениями на основе потока данных. В этом случае мы выделяем некоторые блоки вычислений, связанные между собой только по данным и говорим, что любой блок можно начать выполнять тогда, когда будут готовы все исходные данные. В результате можно построить параллельный вычислитель, отличный от машины Фон-Неймана, который сам решает, когда какие действия эффективнее всего выполнять, и распараллеливание происходит естественно и практически автоматически. Это дает стимул развития моделей программирования на основе потоков данных (Data Flow), в частности, модель Synchronous Data Flow (SDF) оказалась очень удобной для задач цифровой обработки сигналов. Модель потоков данных тесно связана с функциональным программированием. Ряд функциональных языков (напр. Haskell) позволяют т.н. ленивые вычисления, что также по сути управление на основе потока данных, только "наоборот": вычисление некоторых значений может быть отложено до того момента, пока данные не понадобятся. Этой темой как раз занимался SergH в своем дипломном проекте под моим руководством. Подобный подход может быть применен не только в задачах реального времени (с динамическим поступлением данных), но и в "больших" задачах со статически заданными исходными данными.