PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 24 авг 19 18:49

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 12 ] 
Автор Сообщение
 Заголовок сообщения: Поговорим о теории
СообщениеДобавлено: 25 ноя 02 15:13 
Здравствуйте. Я интересуюсь теорией параллельных вычислений. Как я понимаю, существует несколько теоретических подходов к изучению параллельных программ. Какой подход является сейчас наиболее популярным, и какие практические задачи успешно решаются с его помощью?


Вернуться к началу
  
 
 Заголовок сообщения: Теория параллельных вычислений
СообщениеДобавлено: 24 дек 02 10:13 
:shock:
Все определяется формальной моделью параллельных процессов. С них надо начинать :D Среди них, пожалуй, самая известная - сети Петри. Или, например, из "наших" - модель А-схем программ (В.Котов и др.) Но их практические достижения (в отличие от теоретических :? достаточно скромны.
Другие модели менее известны.
Пока сосуществуют множество моделей. Выбор их определяется практическими соображениями. Универсальной модели пока нет. Точнее нет общепризнанной такой модели.


Вернуться к началу
  
 
 Заголовок сообщения: о моделях параллельных программ
СообщениеДобавлено: 25 дек 02 19:50 
О сетях Петри много говорят, но когда я использовать их для анализа простейших параллельных программ, то имел абсолютеный неуспех. Как например построить сеть Петри, моделирующую простейшую параллельную программу вычисления определителя матрицы, или например параллельную программу численного решения дифференциального уравнения? По-моему это невозможно, и надо использовать совсем другие модели. Не мог бы кто-либо написать, какие модели годятся для анализа параллельных программ решения перечисленных выше задач вычислительной матетматики? В.В.Воеводин, интересует Ваше мнение по данному вопросу.


Вернуться к началу
  
 
 Заголовок сообщения: Поговорим о теории
СообщениеДобавлено: 31 дек 02 16:10 
Вообще-то сложно представить такой "абсолютный неуспех" ;)
Шлите "мылом" свой алгоритм (для конкретности, например, вычисления определителя матрицы) и попробую Вам помочь. Не обещаю, что это будут сети Петри (скорее, нет), но параллельно, надеюсь, будет :)
Мой e-mail: sllubch@mail.ru


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 9 янв 03 13:19 
Проблема была не в том, чтобы проанализировать конкретный алгоритм вычисления определителя матрицы. Вопрос звучал так: какие математические модели параллельных программ наиболее часто используются для анализа параллельных алгоритмов решения типичных задач вычислительной математики, в частности вычислительных задач линейной алгебры и задач численного решения дифференциальных уравнений в частных производных (В.В.Воеводин, интересует Ваше мнение по данному вопросу!)


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 4 мар 03 12:35 
Для решения задач математической физики на статических структурированных сетках предлагаю использовать спец. язык Норма :oops: . Информацию можно почерпнуть на сайте http://www.keldysh.ru/pages/norma.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 4 мар 03 12:36 
Для решения задач математической физики на статических структурированных сетках предлагаю использовать спец. язык Норма :oops: . Информацию можно почерпнуть на сайте http://www.keldysh.ru/pages/norma.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 10 окт 03 18:44 
Пожалуй, лучшая книга по теории параллельных вычислений - http://www-unix.mcs.anl.gov/dbpp/. Базовы принципов по распараллеливанию можно выделить два: распараллеливание по данным (наиболее популярный метод) и распараллеливание по задачам (часто единственно возможный), а построение всяких сетей Петри и т.п. не видится особенно целесообразным из-за своей неуниверсальности. Ещё более сомнительным видится применение параллельных компиляторов и языков программирования из-за их низкой эффективности.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 29 апр 04 15:38 
Rasparallelivanie po zadacham(ili vernee - po podzdacaham) est sledstvie
rasparallelivania po dannym.
Naprimer - pasparallelivanie po ciklam proizvoditsia na baze analiza
parametrov (dannyh) cikla. S drugoj storony cikl mojno rassmatrivat i
kak podzadach.

Metodika rasparallellivania - analiz Tablic Nezavisimosti Ciklov.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 31 май 04 10:53 
Случайно заглянул и был и… как мне кажется, эта тема все еще кому-то интересна :-) А потому…
Пожалуй, самое лучшее еще не издано… Став же изданным, оно автоматически переходит в разряд хорошего, ну, может быть, лучшего, но на текущий момент… ;)
Так вот. Сети Петри – модель универсальная. Это почти как аксиома. Хотя бы потому, что ее можно применить к описанию структурных моделей задач распараллеленных как по данным, так и по задачам (подзадачам, процессам, подпроцессам и т.д. и т.п.). Как всякий универсальный инструмент он может быть удобным в той или иной мере, но, даже будучи не очень удобным для отдельной задачи или даже целого их класса, он не становится от этого менее универсальным…
Я могу предложить достаточно простую на структурном уровне _параллельную_ задачу, которая в какой те мере может служить пояснением сказанных выше слов.

1. Пусть имеем два параллельных процесса/подпроцесса (задачи/подзадачи, но далее – просто процессы). На структурном уровне пусть это будут ЧЯ («черные ящики»), имеющие по два входных и одному выходному каналу.
2. При этом каждый из выходных каналов процессов соединен с одним из входных каналов соседнего процесса.
3. Информация, циркулирующая в системе (по ее каналам), представлена в двоичной форме – 0,1 (внутри ЧЯ она может быть любой).
4. На оставшиеся свободные каналы процессов поступает также двоичная информация.
5. Оба процесса выполняют одинаковую работу – вычисляют логическую функцию И-НЕ y=!(x1&&x2), где x1,x2 – входные каналы процесса, у – выходной канал процесса.
Нужно. Используя любую (универсальную или даже не очень ;) модель параллельных вычислений, создать модель (параллельную) описанных выше процессов и определить их поведение.

Примечание1. В общем случае работа процессов может быть любой, а не только одинаковой и не только вычислением логических функций.

Примечание 2. В качестве «каналов» в программе могут выступать , например, переменные, а доступ к этим переменным моделирует информационные связи между процессами. Но это могут быть и сообщения. Т.е. понятие канала определяется моделью вычислений.

Примечание 3. В общем случае двоичная информация может быть представлена в потенциальной форме, т.е. сохраняющей во времени то или иное свое значение (подобно значению переменной в программе). Но ее можно представить и в «импульсной форме», т.е. в форме генерации порций «ноликов» и/или «единиц». Т.е. и в данном случае нет каких-то ограничений на форму представления информации. Хотя нужно понимать, что для сопряжения подсистем разного типа – потенциальной и импульсной - нужно уметь преобразовывать информацию к нужному виду.

Итак. Нужно составить модель, описать, а еще лучше - рассчитать ее поведение, ну и соответственно реализовать созданную модель.

Примечание 4. Я могу представить модель данной задачи, как модель в определенном смысле распараллеленную по данным или по задачам, могу ее представить и в форме сетей Петри, в виде А-схем программ и т.д. и т.п. Могу даже предложить свою модель универсальных параллельных вычислений… Но как применить в данном случае «универсальную» методику распараллеливания по циклам? На это было бы интересно посмотреть. В том числе и на реализацию в рамках MPI и т.п.

Мне кажется, что обсуждение конкретных решений и есть обсуждение возможностей и универсализма той или иной теории параллельных процессов. Или, если уж быть точным, то теории некоторой универсальной модели параллельных процессов. И одна из таких задач предложена выше. Проще ее сложно что-то придумать.

Хотелось бы, чтобы участники форума попробовали решить предложенную задачу и тем самым продемонстрировали возможности той или иной «своей» модели параллельных вычислений.

PS
Заглянул на «лучшую» ссылку. Первое впечатление – некая заброшенность. Неужели все лучшее создали до 1995 г и на том успокоились?
И еще одно замечание по поводу универсальности сетей Петри. Современная, а потому можно считать наиболее совершенная на текущий момент универсальная программная технология - UML ориентирована также на параллельное проектирование. Базируется в основном на модели сетей Петри. По крайней мере, в части реализации параллелизма. Хотя это и не означает, что она лучшая ;)


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 7 июл 04 15:16 
to ВЛ:
на счёт сетей Петри вы, скорее всего, правы. Просто нужно точнее (с моей стороны) разделять теорию и практику параллельных вычислений. Для меня неочевиден результат теоретических исследований анализа представления параллельных программ. Такое ощущение, что в сфере параллельных вычислений практика порождает теорию, а не наоборот.

to Antonov:
позволю не согласиться (точнее, согласится не вполне) с несколькими вашими высказываниями.
Параллелизм по задачам отюдь не всегда является следствием параллелизма по данным. Например, в методах Монте-Карло (а это очень ширный класс задач), зачастую входные данные просто реплицируются по узлам + во многих задачах, связанных с генерацией новых данных, паралелизм можно организовать за счёт правильного разбиения пространства обработки данных (например, сетки) и явное разбиение даных так же будет отсутсвовать.
А на счёт того, что методика распаралелливания - это только анализ таблиц независимости циклов, есть ещё больше сомнений.
Во-первых стратегия распараллеливания сильно (причём очень) зависит от объёмов входных данных (ососбенно если это не один параметр, а несколько). И, во-вторых, попробуйте только одним анализом независимости циклов эффективно (а не абы как) распараллелить самый тривиальный метод исключения Гаусса. :twisted:

PS
А по поводу заброшенности темы с 95 года. Так похоже оно так и есть. Причём, боюсь, не с 95-го, а ещё раньше, ведь книга Фостера - некое обощение ещё более раннего опыта. Причём это касается именно алгоритмической (математической) части параллельных вычислений. Могие работы Донгарры 80-х и сейчас не потеряли актуальности. С точки же зрения информатики, soft, hard и т.д. всё развивается очень даже не плохо.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 8 июл 04 1:36 
Zarva писал(а):
to ВЛ:
Для меня неочевиден результат теоретических исследований анализа представления параллельных программ.

А вообще есть ли такой анализ? Я предложил конкретную задачу. С помощью какой известной Вам теории можно сделать ее анализ?
Zarva писал(а):
Такое ощущение, что в сфере параллельных вычислений практика порождает теорию, а не наоборот.

А так оно и есть. Практика породила многопоточное программирование, а это издевательство над теорией ;)
Вы сможете реализовать предложенную выше задачу на множестве потоков. Но какая "многопоточная теория" сможет предсказать результаты ее работы? Может кто знает?
Zarva писал(а):
... Причём, боюсь, не с 95-го, а ещё раньше ...

Согласен полностью. Можно смело еще лет 10-15 сбросить ;)


Вернуться к началу
  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Часовой пояс: UTC + 4 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB