PARALLEL.RU

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

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




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
СообщениеДобавлено: 3 мар 04 20:56 
Здравствуйте.

Возник вопрос (спор):

Пусть имеется однопроцессорная машина (например, обычный Pentium)
Разработан последовательный алгоритм. Возможно ли распараллелив данный алгоритм добится повышеня производительности (скорости счёта) на этой же однопроцесорной машине.

Мне кажется нет т.к. вычислительной устройство одно + затраты на коммуникации м/у задачами может привести лишь к замедлению.
Прав ли я ? Если нет пожалуйста приведите примеры.

С уважением, Михаил.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 3 мар 04 21:03 
Вы абсолютно правы. Выигрыш может быть лишь косвенным - за счёт распараллеливания вычислений Вы можете более оптимально использовать кэш-мапять, что возможно приведёт к ускорению.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 3 мар 04 21:12 
Что вы имеете в виду под "более оптимально использовать кэш-мапять" - оптимизация работы с памятью ?


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 3 мар 04 21:19 
За счёт того, что при распараллеливании вероятно блоки данных будут меньше, они будут чаще попадать в кеш. Это совсем не обязательно произойдёт и для этого программу не обязательно параллелить.
Однако, переписав программу так, что она может работать в параллельном режиме в т.ч. и на одном процессоре (как частный случай), Вы сделаете "задел" на перспективу. Кроме того, возможно ускорение по вышеприведённой причине.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 5 мар 04 1:08 
Не в сети

Зарегистрирован: 24 июл 03 22:36
Сообщения: 23
Откуда: Химки (почти Москва)
Mikhail писал(а):
Здравствуйте.
Пусть имеется однопроцессорная машина (например, обычный Pentium)
Разработан последовательный алгоритм. Возможно ли распараллелив данный алгоритм добится повышеня производительности (скорости счёта) на этой же однопроцесорной машине.


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

Пример: надо посчитать (1000 000!) и скопировать мегабайтный файл. Это независимые задачи, и они легко могут идти параллельно - 1-я грузит проц, вторая винт.

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


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

Зарегистрирован: 24 июл 03 22:36
Сообщения: 23
Откуда: Химки (почти Москва)
Anonymous писал(а):
За счёт того, что при распараллеливании вероятно блоки данных будут меньше, они будут чаще попадать в кеш.

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

Вообще оптимизация строк данных под кэш конкретного процессора и распараллеливание - это совсем разные вещи, одно другому не мешает.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 5 мар 04 15:09 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
PavelS писал(а):
Ну уж нет. Скорее всего что данные, которые нужны одному потоку исполнения, совершенно не нужны другому.


Запускать пару (или более) потоков на одном процессоре, конечно же смысла не имеет. Но написание параллельной программы и её запуск на одном процессоре (когда ветвь будет одна, т.е. вырожденный случай) может дать положительный результат.

А уж когда появится возможность пустить её на 2-х и более процессорах - тем более :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 1 июн 04 12:31 
А по-моему, многопоточная программа будет работать быстрее.
1) на оди процесс будет выделяться больше процессорного времени
2) потоки для того и нужны, чтобы ускорить выполнение программы


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 1 июн 04 12:38 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
1. Одному процессу(потоку) не может быть выделено больше, чем 100% процессорного времени. Если активен один процесс, то ему будет отдано 100%. Простаивать процессор не будет. А вот 2 потока потребуют накладных расходов в виде переключений контекста, будут портить друг другу кэш и, возможно, "подерутся" за оперативную память (приватную).
2. Потоки действительно нужны для ускорения работы - на SMP-машинах. Или для логического деления работы, при этом один из потоков активен, а другие выполняют нетрудоёмкие задачи (опрос пользовательского ввода, запись на диск, и т.п.)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 2 июн 04 10:38 
Во-первых, и, может, это самое примечательное, распараллеливание нужно не только для ускорения процесса вычислений. Гораздо важнее то, что параллельные алгоритмы позволяют решить задачи, которые сложно решить последовательным – однопроцессорным - путем. Вот об этом часто забывают. Т.е. только скорость – узкий взгляд на параллельное программирование.

Но, безусловно, моделирование параллелизма замедляет процесс решения. Но, прежде всего, по отношению к своему же, но _немодельному_ решению. Если же рассматривать подобное параллельное решение в сравнении с эквивалентным последовательным решением, то не все так просто. Могу поделиться своими экспериментами при сравнении параллельных и последовательных решений на однопроцессорных системах.

Итак. Возьмем задачу сортировки данных и сравним быстродействие самого быстрого последовательного алгоритма сортировки – быстрой сортировки Хоара с параллельной сортировкой. Мне удалось создать алгоритм параллельной сортировки, который по формальным параметрам (дискретным шагам, где шаг это, например, абстрактная операции пересылки/сравнении данных и т.д. и т.п.) быстрее примерно в 15 раз быстрой сортировки.

В _реальных шагах_ созданный параллельный алгоритм, безусловно, медленнее: реальный шаг параллельной программы - особенно в режиме моделирования параллелизма – по времени длиннее, чем шаг обычной последовательной программы. Но число шагов-то все равно меньше! А потому в определенной ситуации реальное время параллельной сортировки может быть меньше, чем реальное время последовательной сортировки. Например, если нужно выводить, запоминать и/или выполнять какие-то действия с текущими данными сортируемого массива на каждом «шаге» процесса сортировки. При этом даже простейший вывод данных в окно приложения – тот же процесс отладки - _съедает_ все быстродействие более быстрой последовательной сортировки.

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

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


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 2 июн 04 10:43 
Да. Мне кажется, что привел достаточно убедительный пример, дающий отрицательный ответ на изначально заданный вопрос (но в пользу параллельных решений). Т.е. Вы, Михаил, не совсем правы :-)


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 7 июл 04 18:30 
Хотел бы заметить, что чаще всего при оценке суперкомпютерной техники обращают внимание на мощность и количество процессооров. Хотя наличие огромного количества оперативки и дискового пространства - фактор, открыающий возможнтсти решения задач совершенно нового масштаба. Задачи, оперирующие огромными данными, просто не уместятся в памяти однопроцессорной машины.
Но всё же, на мой взгляд, параллельные вычисления - это не самоцель, а применительно к однопроцессорной технике - это вообще нечто чужеродное (особенно с учётом закона Амдаля). Для однороцессорных машин гораздо важнее многопотчность (многозадачность ОС, клиент-серевер и т.п.), но применительно к вычислительными задачам от неё толку немного.
Что касается сортировки, то насколько показали мои эксперименты объём данных, для которых время сортровки становится критичным и требует распарллеливания имеет порядок, превшающий размеры оперативки современных ПК и измеряется как мимнимиум сотнями миллионов элементов. Если есть необходимость отсортировать большие объёмы данных, то (это тоже моё личное мнение) наиболее оптимальный алгоритм:
1. Разбить массив на подмассивы и отсортировать каждый на своём процессоре быстрой сортировкой.
2. Собрать подмассивы на одном узле и отсортировать сортировкой слиянием.
Обе сортровки имеют одинаковый порядок сложности и итоговая эффективность должа быть дастаточно высокой (для SMP уж точно).

Если это можно сделать эффективнее - буду рад ознакомться с такими работами.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: 8 июл 04 1:54 
Zarva писал(а):
Но всё же, на мой взгляд, параллельные вычисления - это не самоцель, а применительно к однопроцессорной технике - это вообще нечто чужеродное (особенно с учётом закона Амдаля).

Это Вы не правы ;) Дела не в числе процессов, а в потребностях параллелизма. На РС параллельных вычислений еще больше, чем на суперкомпьютерах, кластерах и т.п.
Zarva писал(а):
... время сортровки становится критичным и требует распарллеливания имеет порядок, превшающий размеры оперативки современных ПК...

И опять не соглашусь. Мои эксперименты показали, что быстрая сортировка на P2.4 100000 элементов целых чисел - это 0.3 сек, а еще на порядок - уже 3.6 сек. И первое, а второе тем более, для невытесняющей многозадачности непозволительная роскошь, т.к. сразу возникнут "висюки" в приложении.
Так что какие там сотни миллионов! А в остальном Вы, наверное, правы. Хотя все же можно что-то придумать и эффективнее ;)


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

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


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

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


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

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