Intel® Software Network

Какие методы существуют для анализа решаемой задачи. (для распаралеливания).
В каком виде можно представить алгоритм, многопоточной программы?
Ясно что любая распаралеливаемая задача требует, "математического" обоснования выбраного алгоритма. И изображения в виде графа.
Хочется узнать подробности таких представлений как:
- Ярусно-параллельная форма графа
- Модель вычислений в виде графа "операции – операнды"
Где можно почитать?

Если под задачами понимаются задачи повышения пиковой производительности системы (а это не единственный тип задач параллельного программирования, можно, например, отзывчивость повышать :) (как пример - встроенные системы) ), то рекомендую книгу "Системы параллельной обработки" под ред. Д.Ивенса, М.:Мир, 1985 г., а также курс лекций В.В.Воеводина "Вычислительная математика и структура алгоритмов" 2006 г (есть в электронном виде на parallel.ru)

Примерно то же порекомендовали наши спецы, прочитав ваш вопрос. Выяснилось, что они все "практики, а не теоретики", и что массу материалов можно найти на parallel.ru.

---

Дмитрий Оганезов
Intel® Software Network

Если говорить прямо, то "порекомендованное спецами" теорией можно назвать достаточно условно. Это лишь часть, причем далеко не самая основная, общей теории параллельных вычислений. К примеру, используя данную теорию, на упомянутом сайте (parallel.ru) так и не решили достаточно простую задачу (см. подробнее http://hp.parallel.ru/parBB/viewtopic.php?f=2&t=298&st=0&sk=t&sd=a).
Что это - недостатки теории или неумелое пользование ею?...
Поэтому, если ставить задачу параллельного программирования, как задачу автоматического распараллеливания существующего последовательного алгоритма, то можно воспользоваться упомянутыми "рекомендациями", но ... без особой надежды на успех (пример - предложенная на форуме задача).
Если же стоит задача создания, анализа и реализации параллельных алгоритмов в исходной - параллельной - постановке, то в "рекомендованных" источниках на эту тему мало что можно найти.
Иной подход представлен на сайте SoftCraft в разделе КА-технология (http://www.softcraft.ru/auto.shtml#ka, а теперь и на сайте http://www.deeplab.ru/). Сети Петри - в эту же тему...

Хорошая подборочка, статей спасибо!

Согласен, автоматическое распараллеливание несет много тайн и загадок, вот тут Алексей писал как раз об этом. Как и в жизни - 100% полагаться на автоматику можно, если хорошо представляешь, как она работает. Собственно, автоматические коробки передач прошли путь в несколько десятков лет прежде чем их стали ставить чуть ли на спорткары.

Честно признаюсь - я в этой теории мало понимаю, но на всякий случай ссылку нашим ребятам кину. Хотя, там тема аж 2005 года.

---

Дмитрий Оганезов
Intel® Software Network

Если говорить о статье Алексея, то насколько можно понять там дело отнюдь не в автоматическом распараллеливании, а в проблемах оптимизации кода. Сам параллельный алгоритм при этом фактически не изменяется, а уменьшается лишь число команд, реализующих операции алгоритма. Но подобные вещи только усложняют и уводят от сути процесс программирования.
Пример с коробкой автоматом представляется не очень удачным. И вот почему. Алгоритм можно выполнять ручками (на бумаге, например) или поручить его исполнение процессору. Коробка-автомат - это "процессорное" исполнение алгоритма переключения скоростей. Автоматическое распараллеливание - несколько иной процесс: нужно сунуть компилятору "последовательную коробку", а на выходе получить "параллельную" и ... поставить ее на спорткар. Только вот кто решится поехать на нем :) Да и сами процессы проектирования коробок передач пока еще не выполняются, думаю, автоматически...
И я тоже признаюсь, что в автоматическом распараллеливании я мало что понимаю :) Просто потому, что ... предпочитаю создавать и реализовывать параллельные алгоритмы сам. И считаю, что говорить, что автоматическое распараллеливание решит проблемы параллельного программирования - вводить людей в заблуждение. Пока об этом приходится только лишь мечтать. А, скорее всего, это несбыточная мечта. Особенно, если самой теории параллельного программирования пока еще нет. Есть некие решения для достаточно узкого класса задач/алгоритмов и не более того. Цельной теории - нет. Об этом нужно говорить прямо.

Кто-то разве говорил что автоматическое распараллеливание решит проблемы параллельного программирования? Хм, по-моему такого не было, по крайней мере тут у нас на ISN :)

Хотя, вы знаете, могу привести очень характерный пример когда автоматика дает очень неплохие результаты. Был тут у нас конкурс, Students Cup. Так вот, второе место занял парень, который просто грамотно подобрал ключи компилятора и использовал одну (если мне память не изменяет) библиотечную функцию. То есть по-полной включил автоматику. Выигрыш по скорости у него был где-то в 3 раза.

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

---

Дмитрий Оганезов
Intel® Software Network

Как известно, ничего бесплатного, кроме сыра в мышеловке, нет :)
Параллельным программированием следует заниматься, даже если нет выигрыша в скорости. Во-первых, потому, что увеличивается гибкость решения: отдельные параллельные блоки можно разрабатывать, заменять независимо друг от друга. Во-вторых, параллельное программирование – подход к уменьшению сложности решения: отдельный блок, как правило, меньше по сложности, чем соответствующее последовательное решение. В-третьих, при наличии соответствующей параллельной модели и ее теории – это еще один подход к анализу алгоритмов (думаю, что это даже «во-первых»). И лишь где-то там – на задворках параллельного программирования – увеличение скорости работы программ. Это, так сказать, побочный эффект параллельного программирования, который может быть, а может и не быть (здесь все определяется наличием/отсутствием аппаратной поддержки параллелизма).
Вот таким, как представляется, должен быть взгляд на параллельное программирование и его возможности. Мы же зачастую начинаем с конца – со скорости. Даже «тут у нас на ISN» :) Косвенным подтверждением справедливости сказанного является то, что современные проблемы программирования лежат не в плоскости повышения быстродействия, а в плоскости повышения надежности и уменьшения сложности. А автоматическое распараллеливание никак не решает эти задачи.
… Потому-то сейчас и сложно получить ответы на заданный изначально вопрос. «Математическое обоснование» появляется при наличии соответствующей теории, которой, как я уже сказал, фактически нет. Даже представив алгоритм в той или иной параллельной форме, вы на самом деле мало что можете сказать о его свойствах, доказать его корректность и т.д. и т.п. Сейчас все делается «на коленке»… Отсюда и все жалобы на сложность параллельного программирования.

vlubch:

...увеличение скорости работы программ. Это, так сказать, побочный эффект параллельного программирования, который может быть, а может и не быть (здесь все определяется наличием/отсутствием аппаратной поддержки параллелизма)...

Интересная мысль, и вот что я по этому поводу думаю: собственно, Интел и занимается "обеспечением наличия аппаратной поддержки параллелизма". Отличная формулировка, кстати! Таким образом, мы стараемся оказать помощь всем - и тем, кто "на коленке распараллеливает приложения" (как я понял вы так называете тех, кто использует библиотеки, ключики компилятора и прочие прагмы). И тем, кто занимается теоретическими и фундаментальными исследованиями.

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

И есть у меня подозрение, что многое делается в этом направлении... По крайней мере вот этот запрос дает более миллиона результатов :)

---

Дмитрий Оганезов
Intel® Software Network

Надеюсь, что когда-то количество перейдет в качество... :) Я почему так говорю? Не только я достаточно критически настроен в отношении многоядерного программирования. Например, есть очень интересные рассуждения на тему многоядерности и многопоточности Д.Кнута (см. http://webplanet.ru/interview/soft/2008/05/06/knuth.html). Сложно не учитывать мнение столь известного гуру в программировании. Могу лишь добавить, что все сказанное им доказуемо. Хотя бы на примере той же задачи о создании и тестировании модели RS-триггера.

vlubch:

Надеюсь, что когда-то количество перейдет в качество... 

Количество уже перешло в качество. Кнут: "Я знаю, что параллельные вычисления важны для рендеринга графики, взлома кодов, сканирования изображений, моделирования физических и биологических процессов, и так делее." Хотелось бы сделать ремарку по поводу следующего утверждения Кнута: "Но все эти приложения требуют специально заточенного кода и специфических алгоритмов, которые необходимо менять каждые несколько лет". Частично можно с этим согласиться. Но только частично. Есть такой пакет Goto BLAS. Появление быстрой команды pshufd в 45 нм. процессорах (в более ранних процессорах она была очень медленной) повлекло изменение алгоритмов для BLAS Level 3 для существенного увеличения скорости соответствующих алгоритмов. Но что объединяет старый и новый алгоритмы - это грамотное использование кэша. Попробуйте взять из пакета LAPACK subroutine dgemm и сделать на ее основе программу перемножения матриц. Она будет работать почти на порядок медленней, чем, например, dgemm Intel MKL. А все упирается в грамотное использование кэша. Если кэш эффективно использовать нельзя, то в моделях с общей памятью (каковыми являются большинство десктопных процессоров) от многоядерности мало смысла (см. тему "Ограничения в параллельном программировании в моделях с общей памятью" или мою страницу: http://www.thesa-store.com/products/ ).

YuriiSig:

Количество уже перешло в качество.

Пока категорическое - нет. Иначе бы процессоры были другими, с другой моделью вычислений - параллельной (о текущей модели - см. Кнута).

YuriiSig:

Частично можно с этим согласиться...

Думаю, нужно согласиться полностью. Насколько видно Ваши проблемы, хотя и важны, но это частные проблемы, а не общие проблемы параллельного программирования. Т.е. все по Кнуту :)

vlubch:

YuriiSig:

Количество уже перешло в качество.

Пока категорическое - нет. Иначе бы процессоры были другими, с другой моделью вычислений - параллельной (о текущей модели - см. Кнута).

YuriiSig:

Частично можно с этим согласиться...

Думаю, нужно согласиться полностью. Насколько видно Ваши проблемы, хотя и важны, но это частные проблемы, а не общие проблемы параллельного программирования. Т.е. все по Кнуту :)

Перед тем, как Вам отвечать, я внимательно прочитал, что Вы писали выше: "И я тоже признаюсь, что в автоматическом распараллеливании я мало что понимаю : Просто потому, что ... предпочитаю создавать и реализовывать параллельные алгоритмы сам." В этом ракурсе я Вам и отвечал. Ваш ответ на мой пост заставляет усомниться и в Вашем умении реализовывать параллельные алгоритмы. Вот Вам элементарная задачка: реализовать и распараллелить алгоритм умножения квадратных м-ц. У меня на q9450 при загрузке 4 ядер скорость умножения составляет 90% (на одном ядре 94%) от теоретически возможной скорости (для IA32). Максимальне скорости для q9450 на одном ядре: 96.2% для IA32 и 97.0% для EM64T.

 

 

Формально программа – S = (M, A, G). M - множество ячеек памяти, A - множество операторов программы, которые в свою очередь могут быть программами, G - управление. Управление может быть или последовательным или параллельным. Поскольку Вы закрыли свои алгоритмы, то Ваши алгоритмы нужно отнести к множеству операторов – операторов перемножения матриц. В силу сказанного на формальном уровне Ваше умножение матриц ничем не отличается от элементарного умножения. Это неделимые операции. Вот таковы «на пальцах» начала теории программ (подробнее см. http://www.softcraft.ru/auto/ka/ash/ash.shtml).
Просмотрев внимательно, как и Вы мои, некоторые Ваши материалы, я, к своему удивлению, даже не нашел в них слово «параллельно». Тогда какое отношение имеют Ваши алгоритмы к параллельному программированию и, тем более, к его теории?
Следите за материалами форума сайта DeepLab (http://www.deeplab.ru/), где я в ближайшее время постараюсь ответить, что же следует понимать (в моем, конечно, понимании) под параллельными алгоритмами. Хотя и на этом сайте и на сайте SoftCraft (http://www.softcraft.ru/auto.shtml#ka) подобных пояснений, думаю, более чем достаточно (жаль, что форум последнего сайта почил, так сказать).
Да. Вы можете рассеять мои сомнения по поводу автоматического распараллеливания, если все же решите упомянутую выше задачу (еще более элементарную, чем Ваша :) ), представленную на сайте PRALLERL.RU. Ну а уж если вместо перемножения матриц Вы расскажете, как перемножить два логических элемента И-НЕ, чтобы получить RS-триггер (а равно и любые другие параллельные процессы, чтобы получить их композицию), то я в уважении склоню перед Вами голову, признав Ваши познания в параллельном программировании. В том числе и в его теории.
И еще. Нужно меньше говорить о скорости работы алгоритмов, а больше о них самих. Это чтобы хорошо понять, что же такое параллельные алгоритмы, а не то, на чем они исполняются.

vlubch:

Формально программа – S = (M, A, G). M ...

Не надо мне приводить цитаты из учебников. Я умею читать. Еще раз привожу Ваш пассаж: "И я тоже признаюсь, что в автоматическом распараллеливании я мало что понимаю : Просто потому, что ... предпочитаю создавать и реализовывать параллельные алгоритмы сам." Ваш последний ответ говорит о том, что Вы имеете такое же отношение к программированию, как я к балету.