PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 20 июн 18 8:18

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




Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: 28 окт 05 23:09 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
coctic писал(а):
ВЛ писал(а):
Граф зависимостей это тоже не модель алгоритма/программы...


Это еще почему граф алгоритма не модель алгоритма? Вполне себе модель, позволяет исследовать некоторые свойства алгоритма.

Свойства алгоритма - не есть сам алгоритм. "Свойства" отражают какие-то характеристики, но не "побуждают" к действию. Также как, например, рост и вест человека никак не определяют поведение субъекта.
Собственно в предыдущем сообщении во многом ответ и на Ваш вопрос.
coctic писал(а):
Если точнее, граф алгоритма - модель даже не алгоритма, а его конкретной реализации (при конкретных входных данных).

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

Да и я так считаю в отношении того что я сказал по поводу графа алгоритма

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 31 окт 05 12:42 
"В нем отражены связи между данными, но не реальный порядок выполнения каких-то команд/операторов программы, работающей с этими данными. Да и где в нем сами операторы программы?"

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

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

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


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 31 окт 05 14:34 
Не в сети

Зарегистрирован: 5 мар 05 14:01
Сообщения: 74
ВЛ писал(а):
Свойства алгоритма - не есть сам алгоритм. "Свойства" отражают какие-то характеристики, но не "побуждают" к действию. Также как, например, рост и вест человека никак не определяют поведение субъекта.

Это конечно. Но ведь в том и смысл любой модели, что вместо того, чтобы изучать весь объект во всей его сложности, мы берем его упрощенное представление, которое и называем моделью, и которое в нужной нам мере отражает поведение исходного объекта. Например, если мы исследуем вопрос падения человека с высокой башни и как он повредит автомобиль, на который упадет, то знание характера человека нам не нужно совершенно, а вот рост и вес пригодятся.
ВЛ писал(а):
coctic писал(а):
Если точнее, граф алгоритма - модель даже не алгоритма, а его конкретной реализации (при конкретных входных данных).

В нем отражены связи между данными, но не реальный порядок выполнения каких-то команд/операторов программы, работающей с этими данными. Да и где в нем сами операторы программы?

Во-первых, вершинами графа алгоритма являются именно операторы программы. Так что в каком-то виде они там есть. А более подробного их знания для некоторых применений может оказаться и не нужно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 1 ноя 05 1:22 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
Igor A. писал(а):
- Напомните текст исходной, последовательной, программы.

http://hp.parallel.ru/parBB/viewtopic.php?p=1052#1052
Это в теме "О параллельной программе разделения двух множеств" в сообщении от 30 марта.
И если бы на этом примере вы (здесь я имею в виду не только Вас Igor) показали что такое модель программ, о которой вы все говорите, то это бы сняло многие вопросы.
Я, например, могу сразу сказать, что блок-схема данной программы и есть ее модель. Я могу сделать модель данной программы в форме конечного автомата и даже форме машины Тьюринга ;) И все это будут модели данной программы. Разные модели, интерпретируя которые я могу получить исходную программу. Вот это и есть как бы "на пальцах" понимание программной модели с точки зрения теории программ.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Граф алгоритма?
СообщениеДобавлено: 3 ноя 05 13:24 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
Что-то долго «рисуется» граф алгоритма для моей программы? Это так сложно? Или это невозможно?...

...По сути детализацией идей ВВ можно считать статью А.Легалова «Стратегии управления в вычислительных системах и языках программирования» (см. http://www.softcraft.ru/parallel/strat/strat.shtml ).
Там даже есть фраза: «Информационный граф задает связи между данными, обрабатываемыми в ходе вычислений. Он полностью определяет алгоритм решаемой задачи при заданном наборе операций обработки и не изменяется при любых способах организации управления вычислениями.»
Собственно в том, что «полностью» и есть основные сомнения. Более того, в статье чуть ниже упоминается управляющий граф. И здесь же говорится, что «в целом именно управляющий граф определяет порядок выполнения операций и корректность проводимых вычислений».
Так кто из них и что определяет?

Попробую привести пример. Есть кирпичи (данные), из которых нужно построить здание (алгоритм). Информационные связи между кирпичами - это кто, где и над кем (или под кем) и как лежит и т.д. и т.п. Казалось бы все, что нужно для постройки здания есть: правильно по связям лежат кирпичи – имеем правильное здание, неправильно – развалы.
Но если подумать, то информационные связи – это лишь статическая информация об уже имеющемся алгоритме/здании. Возможно, что даже одного из алгоритмов. Мне почему-то кажется, что только в сказке можно подойти к куче кирпичей с перечнем информационных связей между ними, дав команду которым – строиться!, можно сразу пойти курить. Хотя, пожалуй, именно такие цели преследует так называемое непроцедурное программирование.
Но как нельзя построить здание, дав команду «куче кирпичей», так, видимо, не всесильно и непроцедурное программирование. Иначе бы мы уже давно стройки шли бы именно таким образом, а программирование было бы только непроцедурным.
Так вот, должен быть еще некий управляющих граф (УГ), который позволил бы корректно растащить кучу кирпичей, превратив ее в здание. Более того, если есть такой УГ, то не нужен граф информационный (ИГ). Зачем ИГ, если все расписано в УГ, который как раз и определяет в какой последовательности и куда класть кирпичи.
Но процесс «непроцедурной постройки» привлекателен и в общем-то используется тоже. Так, если следовать лишь «процедурному строительству», то мы должны указать куда и в какой последовательности положить каждый камешек в машине щебня. Но зачем, когда достаточно вывалить его и затем разровнять грейдером. Вот вам и две непроцедурные операции в строительстве ;)
Вывод. Мы должны согласиться, что в общем случае информационного графа явно недостаточно. Должен быть еще и управляющий. Более того, наличие ИГ по сути не определяет алгоритм, а вот УГ определяет его даже без ИГ.
Такие или подобные рассуждения, видимо, и приводят нас к следующему понятию модели программы. Модель программы можно рассматривать как тройку S = <M,A,G> (см. подробнее http://www.softcraft.ru/auto/ka/ash/ash.shtml). И здесь именно управление G определяет параллелизм программы, т.к. в общем случае оно может быть любым – последовательным, параллельным, непроцедурным и т.д. и т.п.
Конечно, хотелось бы лежа на печи, построив информационный граф, отдавать команды типа: &laquo;По щучьему велению, по моему хотению! Стройся параллельная программа!&raquo;. Но, похоже, в ближайшем будущем на это рассчитывать не приходится. И хотя управляющий граф создать сложнее, чем информационный, может, лучше сосредоточить свои усилия именно на совершенствовании этого процесса – построение управляющего графа? Автоматная модель параллельных вычислений/алгоритмов, которой занимаюсь я, это движение по этому пути (один из путей). Кстати для нее характерна и непроцедурность (не надо думать над каждым кирпичом, если есть определенная свобода его перемещения).
Ну и последнее. То, что пока так и нет информационного графа для моего примера, тоже, видимо, о чем-то да говорит. Его или сложно построить или … в нем просто нет смысла. По крайней мере, в данном конкретном случае. Но этот случай не есть аномалия, а есть обычная и очень простая программа. Кстати построить для нее управляющий граф не проблема. Но вот построить эквивалентный параллельный управляющий граф – проблема, которую так пока и не решил здесь на сайте RS. Хотя насколько мне известно информационный графы он может строить &laquo;одной левой&raquo; ;)
И все же очень хочется посмотреть на информационный граф как формальную модель предложенной реальной программы…

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 6 ноя 05 2:11 
Я посмотрел программу.
Во-первых, она всегда зацикливается. То есть программа не рабочая.
Во-вторых, она не принадлежит к линейному классу, так как там в циклах while переход зависит от входных данных. Так что для этих циклов теория Воеводина не работает. А вообще такие циклы последовательны, а число итераций случайно.
Во-третьих, если не смотреть на ее неработоспособность и считать, что значения х там появляются чудесным образом, то самый внешний цикл представляет собой цикл ParDO. То есть ни одна переменная в программе не пересчитывается и все итерации этого цикла независимы. Так что каждое срабатывание тела этого цикла может выполняться параллельно.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 7 ноя 05 23:48 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
Igor A. писал(а):
Я посмотрел программу.
Во-первых, она всегда зацикливается. То есть программа не рабочая.

Вы не правы. Просто посмотрите, что мы на эту тему говорили с RS. Он тоже сначала утверждал что-то подобное.
Igor A. писал(а):
Во-вторых, она не принадлежит к линейному классу, так как там в циклах while переход зависит от входных данных. Так что для этих циклов теория Воеводина не работает. А вообще такие циклы последовательны, а число итераций случайно.

Значит теория ВВ работает только для очень узкого класса программ? Или, говоря другими словами, - она не универсальна, а специализирована?
Igor A. писал(а):
Во-третьих, если не смотреть на ее неработоспособность и считать, что значения х там появляются чудесным образом, то самый внешний цикл представляет собой цикл ParDO. То есть ни одна переменная в программе не пересчитывается и все итерации этого цикла независимы. Так что каждое срабатывание тела этого цикла может выполняться параллельно.

Чудес нет. Опять же смотрите тему, где все это обсуждается (как появляются значения и как снимаются). Там же приведены и рассуждения, что в ней параллельно и сколько может быть параллельных процессов. Правда, при этом не привлекается теория ВВ, но, может, действительно, тут она и не применима. Хотя и здесь бы я не был столь категоричен. Мне кажется, что и здесь ей можно было бы найти применение (но это лишь предположение).
Кратко. Ваш ответет не верен. Во-первых, это нормальная программа. Более того она получена формальным путем из некоторого множества параллельных программ (отсюда следует, что, вероятно, возможена и обратная операция). Во-вторых, и отказ от применения теории ВВ может быть поспешным. Ну, ... хотя бы в силу неверных начальных выводов (о неработоспособности программы)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 8 ноя 05 12:05 
"Вы не правы."
Имейте совесть, хоть чуть-чуть. Прежде чем кого-то о чем-то просить проверте ее на своем компьютере.

"Значит теория ВВ работает только для очень узкого класса программ?"
- Для очень широкого.

"Правда, при этом не привлекается теория ВВ, но, может, действительно, тут она и не применима."
- Потрудитесь хотя бы до конца дочитать. Самый внешний цикл распараллеливается. Но теорию там и применять-то не к чему, так как это самый простой случай - цикл ParDo.

В общем, я делаю вывод, что вы не способны к конструктивному диалогу, а просто разводите демагогию. Мне от этого разговора вряд ли можно что-нибудь полезное почерпнуть. А вас я обучать не собираюсь, все равно благодарности никакой.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 8 ноя 05 12:52 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
Igor A. писал(а):
"Вы не правы."
Имейте совесть, хоть чуть-чуть. Прежде чем кого-то о чем-то просить проверте ее на своем компьютере.

У нас разные, видимо, понятия о совести. Прежде чем кого-то "совестить" нужно быть в чем-то уверенным. Ваша "совесть", видимо, ждет когда ей разжуют и положат... Вам бы спросить, если лень читать... Все проверено. Или, как Вы думаете, зачем я привел два варианта программы - на С и VB? Так что в данном случае моя совесть просто кристально чиста. Может, подумаете о своей? ;)
Igor A. писал(а):
"Значит теория ВВ работает только для очень узкого класса программ?"
- Для очень широкого.

Ну, понятие "ширины" оно относительно... Иногда просто завит от ... длины рук ;)
Igor A. писал(а):
"Правда, при этом не привлекается теория ВВ, но, может, действительно, тут она и не применима."
- Потрудитесь хотя бы до конца дочитать. Самый внешний цикл распараллеливается. Но теорию там и применять-то не к чему, так как это самый простой случай - цикл ParDo.

Я "трудюсь"... Была поставлена задача - распараллелить. Я "дочитал", но ... решения не увидел.
Igor A. писал(а):
В общем, я делаю вывод, что вы не способны к конструктивному диалогу, а просто разводите демагогию. Мне от этого разговора вряд ли можно что-нибудь полезное почерпнуть. А вас я обучать не собираюсь, все равно благодарности никакой.

Все зависит только от Вас. Я готов Вам выслать проект на VB, но моя "совесть"- вот, наглая! - требует компенсации за ее ущемленное достоинство в виде какой-либо ... благодарности. Только вот теперь ее требования к размеру этой самой благодарности будут, боюсь, очень высоки...
Мне же (дела "моей совести" - это ее дела ;) вместо демагогии хотелось бы увидеть просто параллельный вариант предложенной программы. Пусть к этому процессу ее получения подключится и Ваша "совесть". Вдвоем оно, думаю, будет сподручнее ...
...
Прошу прощения, если что не так, но ... это все она - моя "совесть" ;) Мне же, если честно, нужно только одно - решение поставленной задачи. Лучше без демагогии, и лучше, может, даже без участия какой-либо "совести". Когда решение сделано формально, строго математически (хотя бы в виде просто какой-то работающей программы), то и "демагогия" и "совесть" обычно где-то в стороне.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 9 ноя 05 22:03 
ВЛ
По-моему вы зависли...
Повторяю, для наиболее трудных товарищей.
Операции этой программы независимы по графу алгоритма, однако операции зависимы по входу. Это означает, что каждую выходную преременную можно вычислять на отдельном процессоре в многопроцессорной системе с общей памятью. При дублировании входных данных - и на системе с распределенной памятью.

И не надо больше всем плакаться, что вам не могут распараллелить программу. Лучше лишний раз прочитайте написанное, или "чукча не читатель однака, чукча - писатель"???


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 10 ноя 05 14:05 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
Igor A. писал(а):
ВЛ
По-моему вы зависли...
Повторяю, для наиболее трудных товарищей.
...

Хоть это иногда и трудно, но я постараюсь быть терпеливым.
1. Есть ЧЯ, имеющий два входа x1,x2 и два выхода - y1, y2.
2. Есть последовательный алгоритм его работы (см. мои программы).
3. Известно, что алгоритм его работы может быть параллельным.
4. Найти параллельный алгоритм/алгоритмы работы, зная, например, последовательный.
Задача поставлена ВСЕМ - от сантехника до ... академика ;)
Нужны не рассказы о том, что там и как это может "зужжать" "внутре" ящика, а дать описание параллельного алгоритма в форме формальной модели, можно программы.
Igor A. писал(а):
И не надо больше всем плакаться, что вам не могут распараллелить программу. Лучше лишний раз прочитайте написанное, или "чукча не читатель однака, чукча - писатель"???

Может, впору плакать нам всем, если так сложно, долго и нудно решаются такие небольшие задачи? А, ведь, я могу предложить и посложнее ;)
Я же - "Нет, я не плачу..." (см. подробнее http://www.nsu.ru/library/olga/songs/Kim_kino2.htm)
Замечу, что мне решение известно. Вам - его еще нужно будет найти. Если, конечно, оно "по зубам"... Вам, но не мне.
Реально плачет тот, кто плачет последним. Мне бы хотелось "порыдать" над Вашим решением, но ... суждено ли? ;)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: модель ГРИД
СообщениеДобавлено: 27 ноя 10 19:01 
Не в сети

Зарегистрирован: 27 ноя 10 15:42
Сообщения: 2
Добрый день.

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу Пред.  1, 2

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


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

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


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

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