PARALLEL.RU

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

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




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
 Заголовок сообщения: скрытый параллелизм
СообщениеДобавлено: 2 фев 09 0:15 
Не в сети

Зарегистрирован: 31 янв 09 14:47
Сообщения: 2
Здравствуйте!
Подскажите пожайлуста, что такое скрытый параллелизм (и по возможности способы его выявления).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 2 фев 09 14:14 
Не в сети

Зарегистрирован: 18 ноя 02 16:40
Сообщения: 168
Откуда: Москва
Скорее всего, это потенциальный параллелизм последовательных программ. Способов выявления много, наиболее точные основываются на анализе графов информационных зависимостей.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 9 фев 09 15:59 
Не в сети

Зарегистрирован: 31 янв 09 14:47
Сообщения: 2
спасибо, что-то лучше, чем ничего


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 14 апр 10 1:29 
Не в сети

Зарегистрирован: 23 ноя 09 16:30
Сообщения: 19
GLaS писал(а):
Здравствуйте!
Подскажите пожайлуста, что такое скрытый параллелизм (и по возможности способы его выявления).

Термин сам по себе объёмный. Но в общем это значит, что алгоритм имеет возможности распараллеливания.
Например:
Код:
A[3][3];
B[3][3];
C[3][3];

for (i=0; i <3; i++)
for (j=0; j<3 j++)
 C[i][j] = A[i][j] + B[i][j];

На первый взгляд выглядит как C=A+B. Такой алгоритм не параллеливается, НО если присмотреться, то на самом деле каждая операция сложения делается независимо друг от друга, т.е. можно сделать распараллеливание, при котором каждый поток сделает одну операцию сложения и все. Это самый простой пример, ибо он сразу виден, как параллельный.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 14 апр 10 12:22 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Тут нет "скрытости". Скорее, "неочевидность". А её определения нету - это понятие субъективное...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 14 апр 10 12:49 
Не в сети

Зарегистрирован: 23 ноя 09 16:30
Сообщения: 19
Serg_Zhum писал(а):
Тут нет "скрытости". Скорее, "неочевидность". А её определения нету - это понятие субъективное...

Я же написал, что это простой пример. Понятное дело, что тут это видно. Но для примера подойдёт.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 15 апр 10 11:17 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Так каков критерий "скрытого" параллелизма? Параллелизм есть, если код можно выполнить параллельно. А скрытый - это как?
Я спрашиваю потому, что есть несколько возможных значений этого термина и хочу уточнить какой именно Вы подразумеваете.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 15 апр 10 12:54 
Не в сети

Зарегистрирован: 23 ноя 09 16:30
Сообщения: 19
Serg_Zhum писал(а):
Так каков критерий "скрытого" параллелизма? Параллелизм есть, если код можно выполнить параллельно. А скрытый - это как?
Я спрашиваю потому, что есть несколько возможных значений этого термина и хочу уточнить какой именно Вы подразумеваете.


Я понимаю ваш вопрос.
В данном случае это анализ циклов и особенности реализации алгоритма на вычислительной составляющей. Здесь 2 цикла и один из них вложенный. Для более опытного человека - это будет, как вы правильно заметили, неявный/неочевидный параллелизм (надо учитывать опыт выявления, и что сразу бросается в глаза), что, в принципе, тоже является частью термина скрытый, т.к. он не виден невооружённым глазом.

Например данный код может быть выполнен на GPU вообще без циклов, а просто по номерам тредов.
Можно распараллелить циклы при помощи OpenMP.
Можно привести к 2 циклам с меньшими границами индексов, которые будут выполняться в 2-х разных потоках на 2-х разных ядрах.

Опять же, я не просто так написал, что данная операция похожа на C=A+B, что в принципе нельзя распараллелить. Я понимаю, что это не то, чтобы не сложный, а практически элементарный пример, но он несколько показателен.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 4 май 10 23:48 
Не в сети

Зарегистрирован: 4 май 10 23:34
Сообщения: 2
Вообще выделяют такие виды параллелизма - естественный параллелизм и параллелизм множества объектов, параллелизм независимых ветвей и параллелизм смежных операций.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 5 май 10 10:41 
Не в сети

Зарегистрирован: 18 ноя 02 16:40
Сообщения: 168
Откуда: Москва
Alessyer писал(а):
Вообще выделяют такие виды параллелизма - естественный параллелизм и параллелизм множества объектов, параллелизм независимых ветвей и параллелизм смежных операций.

Интересно, это чья терминология? Можно какие-то ссылки?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 5 май 10 13:39 
Не в сети

Зарегистрирован: 4 май 10 23:34
Сообщения: 2
Ну тема параллелизма вряд-ли будет сильно смахивать на Закон Ньютона и в разных источниках можно найти разную информацию. Но вот эта классификация, которую я привела довольно старая. Например, см. Lawrie D.H., Layman T., Baer D. a.o. Glypnir-A programming Language for ILLIAC IV// Communications of the ACM. 1975.... ну и так далее. В советской литературе часто на него ссылались.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 1 фев 13 21:59 
Не в сети

Зарегистрирован: 1 фев 13 21:51
Сообщения: 1
Мне вообще думается, что имеется в виду параллелизм в работе одного процессора.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: скрытый параллелизм
СообщениеДобавлено: 13 фев 13 22:46 
Не в сети

Зарегистрирован: 2 ноя 11 19:40
Сообщения: 26
Откуда: Владивосток
Поддержку "вольную" формулировку скрытого параллелизма, как
"незадействованный потенциал ресурсов выч. системы, позволяющий ускорить работу алгоритма"

а скрытый, потому что далеко не каждый в состоянии знать/оценить/обнаружить этот потенциал даже с помощью отладчиков/анализаторов/профилировщиков

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


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

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


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

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


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

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