PARALLEL.RU

В параллельном программировании сейчас проблем - хоть отбавляй! И одна из причин - нерешенные базовые проблемы параллельных вычислений. Эта тема обсуждалась и ранее, а сейчас приобрела особую актуальность, т.к. параллельные вычисления в связи с появлением многоядерных систем «пошли в массы». И если раньше они интересовали и беспокоили лишь достаточно узкий круг профессионалов, то теперь, как ни крути, они вынесены и их нужно решать на, так сказать, «бытовом уровне». А это требует кардинального пересмотра и даже переосмысливания существующих подходов в параллельных вычислениях…
Но ситуация такова, что сейчас идет простой перенос существующих «профессиональных решений» на современную основу. Это не годится, т.к. вне зависимости от желания «профессионалов» «массы» отвернут достаточно спорные, весьма ненадежные и сложные в использовании уже длительное время обкатываемые параллельные подходы. То, с чем мирился и мирится современный параллельный программист, не годится в приложении к универсальному применению. И собственно это и служит темой потока последних публикаций – какими быть параллельным вычислениям сейчас и в будущем.
Я упомяну лишь две публикации на эту тему – прошлогодний доклад В.В.Воеводина «Математические проблемы параллельных вычислений» (http://parallel.ru/info/voevodin.doc ) и достаточно свежий обзор С.Кузнецова в «Открытых системах», в котором представлена статья Эдварда Ли «Проблемы использования потоков управления».
В двух словах… Если отбросить всю ту «рекламную шелуху», которая сопровождает внедрение систем многоядерного типа, то все сводится к следующей фразе – нужна новая модель вычислений, которая будет принципиально отличаться от морально устаревшей модели многопоточных вычислений. А два-четыре-восемь и т.п. число ядер – это мало имеет значения. В любом случае – мало!
Современное параллельное программирование – это, образно говоря, уровень математики, когда уже есть понятие числа, но еще не определены операции над ними. Понятное дело, что такая ситуация не может длиться бесконечно (а она затянулась уже, пожалуй лет на пятьдесят-шестьдесят (см. http://www.citforum.ru/programming/digest/dejavu/ )!). Особенно когда подобную «математику» пытаются внедрить в массы. «Первобытный параллелизм» многопоточного типа (о его тестировании см. http://www.citforum.ru/programming/dige ... threading/ ) должен быть не просто усовершенствован, а кардинально изменен на иной вид/модель параллельных вычислений. Т.е. по существу еще только анонсируемые многоядерные системы являются, как ни печально, уже морально устаревшим продуктом…
Но ближе к теме…
В конце сентября в Абрау-Дюрсо состоится очередная конференция «Научный сервис в сети Интернет: технологии параллельного программирования». Одно из направлений конференций – «Технологии параллельного программирования». Я бы сказал – это основное направление, т.к. как о каком сервисе (Научный сервис в сети Интернет – второе ее направление) может идти речь, если не решены научные основы этого самого «сервиса»? А основное в «теории» - это собственно теория: модели, языки и технологии параллельного программирования (см. п.1.3. http://agora.guru.ru/display.php?conf=a ... 3eec82b15c ).
Если просмотреть тематику выступлений, то основной упор делается на практику, т.е. представление решений на существующей базе. И складывается впечатление, что проблем в теории как будто и нет…
С одной стороны, знакомиться с существующими решениями важно, но, с другой стороны, какой смысл в том, чтобы в очередной раз выслушать, как кто-то где-то преодолевал проблемы существующего параллелизма, о которых уже было сказано уже бессчетное число раз (в том числе на этой же конференции в предыдущие годы)?

Но в данном случае беспокоит даже не сама тематика предстоящих докладов. Все же решаем и представляем вниманию то, что можем решить и как умеем решать. Большинство, думаю, даже не задумывается над тем, что можно решать как-то иначе. И вот это и тревожит больше всего, т.к. знакомство с иными подходами затруднено даже на мероприятиях, как данная конференция, где рассмотрению этих вопросов должен быть дан казалось бы самый «зеленый свет»…
И вот тут я наконец-то подхожу к тому, что это делается не совсем так, как того требует сложившаяся ситуация. Сейчас намного важнее решить проблемы теории, чтобы в будущем было много меньше проблем с «сервисом». Этот вывод мною сделан на основании факта отношения организаторов к докладу, который был направлен мною на конференцию. Или, может, не организаторов, а тех рецензентов, которые были привлечены к анализу поступающих материалов. Но, с другой стороны, и мои попытки получить ответ на вопрос, почему же мой доклад не попал в секционные и даже не в стендовые, а только лишь в публикуемые (спасибо, хотя бы за это!) ,ни к чему не привели. Т.е. я попросту не получил ответ на заданный вопрос. А уж ответ на него в прямой компетенции организаторов: дать ответ о причинах помещения материала «на задворки» конференции (это без умаления значимости других материалов, которые аналогично моему будут размещены только в сборники).
Тем не менее, каких-то обид на организаторов конференции у меня нет. Есть лишь повод посмотреть на свой материал критически. Что я и сделал Хотя ответ, думаю, хотя бы по правилам вежливости все же должен быть дан…
Ну, а поскольку мне, видимо, не будет предоставлена возможность донесения своего материала до участников конференции в форме выступления, то в силу актуальности и важности материала я для знакомства с ним решил изыскать другие пути. Благо они есть… Во-первых, с этим материалом можно будет ознакомиться по ссылкам, которые я укажу. И это будет более детальное знакомство, чем тезисы, которые будут включены в сборник. Пока это ссылка на приложение к докладу, в котором я привожу свое решение алгоритма сдваивания (параллельного суммирования массива чисел), упомянутого в докладе В.В.Воеводина (см. ссылку на него выше). Ссылку на сам доклад я дам, но, наверное, чуть позже. Во-вторых, если будут желающие, то на конференции ничто не мешает организовать его «кулуарное обсуждение». Я готов провести своеобразный мастер-класс с демонстрацией на конкретных примерах той новой технологии параллельного программирования, которую я предлагаю, на смену «первобытному параллелизму» потоков/нитей.

Ну а пока … «для затравки»

Вот вполне серьезная несерьезная задачка «о птичках», которая не имеет естественного решения в рамках концепции многопоточного программирования

Есть несколько птичек, которые клюют в единицу времени то или иное число зерен (закон задан в условии и может быть любым). Дать ответ: сколько зерен они склюют через определенное число единиц времени? Смоделировать поведение пташек, отображая в динамике число зерен, которые были склеваны на текущий момент времени.

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

_________________
Лучшее - враг хорошего?

Забыл про ссылку
Вот ссылка на приложение к докладу, где рассмотрена автоматная реализация алгоритма сдваивания - http://www.writely.com/View.aspx?docid=dc5bbjgs_0gqrg8s

_________________
Лучшее - враг хорошего?

Все сходится к тому, что «параллельное сообщество» много говорит, но мало делает. Не в том смысле, что мало работает (тут, как раз, - пыхтят и очень пыхтят), а в том, чтобы что-то кардинально поменять. Или мы рассчитываем на то, что «нарыв» вскроется сам собой? Не будет этого! Не сделаем мы – сделают другие, ну а мы опять будем плестись в хвосте…
Спросите, - откуда такой пессимизм?
1) Если посмотреть курсы по параллельному программированию, то теории параллельных вычислений в них как таковой почти нет. У меня на памяти сейчас лишь курс Гергеля, где упоминаются сети Петри (но в каком объеме – не знаю), да лишь пособие Малышкина, где все те же сети Петри (СП). Причем, у Малышкина приводится пример, содержащий в себе ошибку. Может еще что-то и где-то есть, но примерно на этом же уровне. Но, главное, разговаривать с преподавателями подобных курсов на эту тему – тему теории параллельных вычислений – тоже почти «гиблое дело». Прямо сказать – обидишь и обижаются, а намеков … не понимают Так пока и ходим вокруг да около … в лучшем случае СП. Но и рассмотрение сетей Петри, это тоже скорее только лишь дань своеобразной «моде» (может, просто ничего другого нет/или не знают?), т.к. реально они редко применяются. Точнее я не припомню случаев, где бы в серьезных проектах говорилось бы серьезно о СП.
2) Если и можно говорить о какой-то теории, то это о теории автоматического распараллеливания. Но на эту тему проведено уже столько исследований и ею уже столько занимаются, а результатов – «пшик», если говорить прямо. Простейший пример распараллелить (см. здесь на сайте) – проблема!? О какой теории тогда можно говорить? Есть отдельные задачи/проблемы, которые решены в той или иной мере, но цельной теории не было и нет. Автоматическое распараллеливание - это тупик, о чем нужно прямо так и говорить. Точнее он будет тупиком пока не появится модель на базе котрой можно будет строить теорию. Об этом говорят многие и достаточно много, но что-то мало кто к этому прислушивается. Отсюда основной упор в обучении параллельному программированию – пространные разговоры на тему MPI и т.п. Но MPI – это параллельное программирование «на коленке». Теории в MPI нет. Есть только куча проблем, которые «муссируются» постоянно в статьях, да «кочуют» из одной конференции в другую.
3) Над теорией параллельных вычислений все же работают. Но такое впечатление, что это нужно больше энтузиастам. Тем же, кому этим должно заниматься по статусу, - все это «до спины». Пример тому – доклад В.В.Воеводина. Как в болото. Даже всплеска какого-то нет. Кинулся ли кто-то после знакомства с данным докладом реализовывать алгоритм сдваивания? Где такие? Не вижу, не слышу и не знаю… А надо бы, коль такая задача есть и поставлена, на сетях Петри, используя MPI и все что есть под рукой - применить, т.е. распараллелить, затем посмотреть, сравнить и т.д. и т.п. И подобных параллельных задач, на которых можно было бы обкатывать параллельные идеи множество. Но пока же – «бульк» и все… И если «большая наука» не заявляет, что СП, возможно, исчерпали себя, MPI и т.п. – это «наколеночное программирование», что другие параллельные модели - например, на базе функционального программирования – Haskell и т.п. – не дотягивают уже длительное время до нужного уровня, то все было и останется как есть. Тогда, может, нужно критически оценить нашу «большую науку». Т.е. нужен «критический взгляд» не только на саму теорию (см. доклад Воеводина), но и на тех, кто ею занимается уже длительное время?
4) В чем беда современного параллельного программирования? В том, что оно не учитывает свойств реального мира. Пока программирование было последовательным – это не было нужно. Став параллельным, программирование должно обрести черты и свойства реальных объектов. Прежде всего, с точки зрения поведения объектов и их взаимодействия между собой. Время, инерционность – вот качества реального мира и реальных параллельных объектов, на которые нужно обратить свое внимание в первую очередь. Параллельные модели, которые не учитываю этих свойств, нужно обследовать на их пригодность самым тщательным образом.
5) В чем беда современного «аппаратного параллелизма»? Тут можно сказать очень кратко – в том, что в его основе, как правило, нет все той же параллельной модели, о проблемах создания которой говорилось выше. Без хорошей теории все «железо» морально устаревает еще не родившись? Или «большой науке» это неведомо? А иначе, почему она погрязла в проблемах освоения MPI и т.п. «моделей»?
6) Нужны серьезные исследования и серьезное финансирование под него. Просто так и блохи не скачут. «Энтузиасты» могут подать лишь «параллельную идею», апробировать ее. Но довести ее до ума, до серьезного внедрения никакое «открытое сообщество» и «мелочные гранты» не смогут. Но это отдельный (за рамками теории), хотя и огромной важности разговор.

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

_________________
Лучшее - враг хорошего?

Я почти год не появлялся на этом форуме по той причине, что большинство обсуждений проистекают крайне вяло.
Вашу задачу надо отнести к разряду развлекательных и не относящуюся к моей настоящей деятельности. Это как олимпиадные задачи: найти решение интересно, но теорию построить вряд ли поможет. Я понимаю, что за год можно было бы найти время , но хоть я и держу эту задачу в голове, но не могу поставить ее в ранг приоритетных . О своем обещании помню, но если вам удобно считать, что я не способен ее решить, то это ваше дело.
Кстати, вы мне не доказали, что мое решение не верно А алгоритм сдваивания в докладе Воеводина В.В. как раз в том месте, где говориться что одну задачу можно решить разными способами. Ирония судьбы не правда ли?


Напомню, что в прошлом году ваша технология не позволяла распараллелить задачу сложения матриц . А эта задача практически более значима, чем "птички" или RS-тригер. Ваша технология усовершенствовалась?

_________________
Важно не слово, но дело!

> 3) Над теорией параллельных вычислений все же работают. Но такое впечатление, что это нужно больше энтузиастам. Тем же, кому этим должно заниматься по статусу, - все это «до спины».

Полностью согласен с этим пунктом. Большинство новаторских проектов делаются именно энтузиастами просто от любви к искуству... Те, кто занимаются этим по статусу - те лишь делают свою работу - ни плохо, ни хорошо... просто делают.

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

А вот здесь не совсем согласен. Обычно подобное "серьёзное финансирование" ничем хорошим не заканчивается - деньги освоют без проблем, но ничего революционного из этого освоения не получится, т.к. серьёзное финансирование подразумевает под собой лишь создание инструментов для создания прибыли в той или иной форме. Т.е. в данном случае владельцы бюджетов будут брать уже обкатанные технологии (пусть они даже и устарели вовсе) и будут пытаться собрать кластер, который хотя бы попадёт в Top 500, дабы потом можно было отчитаться как-то перед начальством. Минимизация рисков это называется... Ни о каких новшествах в языках программирования в подобных программах с серьёзным финансированием обычно речи не идёт, т.к. риски провала у подобных мероприятий довольно велики... IMHO лучше бы сделали 1000 грантов по 1000$, чем одну супер-финансируемую программу за 1000000$, выделенные деньги на которую всё-равно спустятся непонятно куда...

> Но … до встречи на конференции. И пока без мастер-класса Wink. А кому все же интересны проблемы параллельного программирования, то я готов просто поговорить, … загорая на камешках Абрау-Дюрсо Smile

Про связь параллельного мира с физическим: реальная история - в бакалавриате и магистратуре я занимался разработкой языка MC# (http://u.pereslavl.ru/~vadim/MCSharp/index.ru.php). В этом году меня взяли в аспирантуру на бюджет, при условии, что я найду себе подходящего научрука (хорошо хоть, что зав. кафедрой у меня мировой мужик и дал мне отсрочку на некоторое время). Подходящий человек (степень, звания ==> право быть науч.руком в аспирантуре) является ныне дефицитным ресурсом -- он имеет право руководить ТОЛЬКО 5 АСПИРАНТАМИ (а у нас в университете воообще это количество ограничено 3-мя) и обычно у него эти 5 человек уже заняты... а если учесть сколько человек сегодня заняты в России проблемами параллельных вычислений, можете себе представить насколько сложно найти такого человека... особенно простому студенту. Думал заняться дальнейшим развитием языка - сделать метакластерную и GRID-версию рантайма, поучаствовать в HPCChallenge, но сейчас вместо этого занимаюсь поиском подходящего человека на роль научрука. В общем, вместо того, чтобы заниматься поисками в "мире параллельных вычислений" занимаюсь поиском в "физическом мире"...

Напряженнейшую практическую работу по параллельным вычислениям веду Я !!!

Столько многа букафф, устал читать....

Вам нужно просто расслабиться от "напряженнейшей работы":) И потом просто нужно больше читать, чтобы была практика. Тогда не будете и уставать.

_________________
Лучшее - враг хорошего?

Привет ВЛ! Как поживаете? Чем занимаетесь? Как творческие успехи ?

Здравствуйте!
Я здесь человек новый, поэтому не совсем понимаю в чем сложность реализации алгоритма сдваивания. Или имеется некий критерий оптимальности решения и нижняя планка, выше которой нужно прыгнуть?

А Вы попробуйте его именно реализовать...
Т.е. пока речь идет о просто реализации... Когда же она есть, то можно уже делать анализ, давать оценки, сравнивать и т.д.

_________________
Лучшее - враг хорошего?

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

Еще интересно вот что. Почему все упоминают о СП, но не конкретизируют как именно и какие СП (ч/б и их разновидности или цветные; сейчас вот модно о Йенсене говорить, у него вообще огромное кол-во отличий от "классики") применять. Я в этой области дилетант, но из прочитанных книг и статей я так и не понял (может авторы и сами не понимают, а может я просто не те книги читаю) как применять СП применительно к паралл. прогр-ю:
а) Моделировать конкретные паралл. алгоритмы средствами СП "на бумаге", анализировать эти модели. А уже затем реализовывать алгоритмы в коде.
б) Или реализовать сам аппарат СП на кластере, подавать на вход различные сети и получать результаты (свойства ограниченности, безопасности... дерево разметок и т.д.)

Да. Модель реализации - Ваш выбор.

А Вы попросите "всех", кто упоминает, не "упоминать", а что-то реализовать конкретное... Упоминают многие, но делают далеко не все. Есть над чем задуматься, думаю
См. для информации по СП (раскрашенные СП) - http://www.softcraft.ru/theory/mrs/index.shtml

_________________
Лучшее - враг хорошего?

ВЛ, а чем вам не нравится теория изложенная у Воеводиных?

Давайте по пунктам:
1) Анализ структуры программ и алгоритмов с целью нахождения параллельных множеств операций. - Чем вам не нравится здесь работа Воеводина???

2) MPI - это технология параллельного программирования. То есть когда у вас уже есть параллельный алгоритм - это способ его запрограммировать. Причем это технология для систем с распределенной памятью. - Чем вам не нравится MPI?

3) Чем вам не угодило "многопоточное программирование"? Это тоже технология программирования, но для систем с общей памятью. Все современные операционные системы - многонитевые.

4) Сети Петри используются для моделирования асинхронных процессов, любых! - Чем вас эта модель не устраивает?

Спасибо за вопросы. Я постараюсь ответить в не столь "агрессивной" форме, которой они были заданы

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

MPI - не технология. MPI - протокол организации взаимодействия параллельных процессов. Но, если честно, мне не нравится, что его иногда выдают за технологию Технологию определяет алгоритмическая модель.

Не мне, а ... нам. См. ссылку. Многопоточное программирование - непредсказуемое, вероятностное програмирование. Это показать элементарно. Программирование должно быть, обязано быть предсказуемым, детерминированным. Это идет от определения понятия алгоритма.

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

_________________
Лучшее - враг хорошего?