Здравствуйте, Кодёнок, Вы писали:
Кё>Может это проблема алгоритмов, и того, как мы привыкли думать об алгоритмах (один исполнитель).
Наша привычка тут совершенно непричем. Возможность распараллеливания это объективная характеристика алгоритма. Если шаг Б зависит от результатов шага А, то никаким способом распараллелить их не удастся. Максимум, что тут можно сделать это выделить из алгоритма независимые части. Однако сам понимаешь, что таких независимых частей не бесконечно много и масштабируемость по количеству процессоров в общем случае невысока.
Кё>Например, любую классическую сортировку распараллелить трудно, но если разрабатывать алгоритм специально для такой архитектуры, то может получиться например, когда несколько процессоров сортируют части, а затем один или два занимаются слиянием.
Опять же далеко не факт что для некоторой задачи вобще существует такой алгоритм. И уж точно это не задача для компилятора.
Здравствуйте, Кодёнок, Вы писали:
Кё>Может это проблема алгоритмов, и того, как мы привыкли думать об алгоритмах (один исполнитель).
Кё>Например, любую классическую сортировку распараллелить трудно, но если разрабатывать алгоритм специально для такой архитектуры, то может получиться например, когда несколько процессоров сортируют части, а затем один или два занимаются слиянием.
Например, в третьем томе Кнута рассмотрен случай сортировки, когда доступно большое количество одновременно работающих компараторов. Если не ошибаюсь, алгоритм построения оптимального графа сравнений там нужно придумать в упражнении на 50 баллов.
По крайней мере, отсутствие решения этой задачи совершенно точно указывалось (у меня нет сабжа под рукой).
Конечно, сортировка слияниями легко поддается распараллеливанию. Вот только КПД у нее получится не слишком высокий.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, AndrewVK, Вы писали:
AVK>Опять же далеко не факт что для некоторой задачи вобще существует такой алгоритм. И уж точно это не задача для компилятора.
Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
Здравствуйте, Sinclair, Вы писали:
S>Конечно, сортировка слияниями легко поддается распараллеливанию. Вот только КПД у нее получится не слишком высокий.
Однако, у наращивания скорости процессора есть физический предел, а у наращивания их количества — нет.
Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
Здравствуйте, Кодёнок, Вы писали:
Кё>Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
Кодёнок,
Кё>Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
Ну если уж ты совсем опустился на юзерский уровень, вот тебе некоторые из них (может они принципиально и паралллелятся на каком-то низком уровне, но практически это последовательные):
1. Отображение html браузерами — пока не засосётся закрывающий тэг, браузер чаще всего вообще не может ничего показать.
2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
3. Вызовы типа prog1 | prog2 | prog3 ...
4. Авторизация в системе. Пока не произойдёт рукопожатие (по строго последовательному протоколу), дальнейшие действия невозможны.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Кодёнок, Вы писали:
Кё>>Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
AVK>Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
Вы это про задачи общего использования или про специфические?
Из общих приходят в голову цивилизации, где в условиях мира между несколькими странами, все шаги каждой из них можно считать параллельно. Думаю, во многих других задачах все аналогично.
Еще в голову приходят архиваторы, где, например, разбив файл на две части (ну или, если файлов несколько, скармливая каждому потоку по одному из них) можно также легко распараллелить алгоритм (хотя и вероятно снижение степени компрессии).
Ну а о специфических алгоритмах Вам лучше прикладные математики и ВМКашники расскажут...
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
Кё>>Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
LCR>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
LCR>3. Вызовы типа prog1 | prog2 | prog3 ...
Только если между программами есть зависимости (явные — по данным, или неявные — по косвенным эффектам выполнения).
mik1,
LCR>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
Да. Если бы пропускная способность файловой системы (а конкретно шины винчестера) была выше, то и копирование одного файла было бы быстрее А при копировании нескольких файлов одновременно будет наверное ещё хуже, потому что дёргание головки винчестеров тоже небесплатное.
Я говорю про копирование с одного каталога в другой на том же самом винчестере.
LCR>>3. Вызовы типа prog1 | prog2 | prog3 ...
M>Только если между программами есть зависимости (явные — по данным, или неявные — по косвенным эффектам выполнения).
Да, если каждая из программ будет в конце своей работы выводить неизвестное априори сообщение, то такая зависимость налицо.
Здравствуйте, mik1, Вы писали:
AVK>>Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
M>Вы это про задачи общего использования или про специфические?
Про первое.
M>Из общих приходят в голову цивилизации, где в условиях мира между несколькими странами, все шаги каждой из них можно считать параллельно. Думаю, во многих других задачах все аналогично.
Собственно лично я знаю всего несколько хорошо распараллеливающихся задач — моделирование, 3D, обработка сигнальных потоков. Первое вряд ли задача для десктопов, а для остального существуют аппаратные акселераторы и векторные сопроцессоры.
Евгений.
LCR>>3. Вызовы типа prog1 | prog2 | prog3 ...
E>А можно обосновать?
Напомню, что мы на юзерском уровне. Возможно prog1..n и параллелятся где-то в кишках, но сами программы должны выполняться последовательно, поскольку программа i+1 может требовать полностью вывод программы i.
Ну например, каждая из программ prog. выводит SUCCESS или FAILED, и это значение необходимо для следующей.
Если ты по-прежнему неудовлетворён ответом, возьми наконец ant, make etc. Уж здесь железно, если таск2 зависит от таска1, то пока таск1 не отработает, таск2 не начинается. Это просто прибито гвоздями в спецификации.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>1. Отображение html браузерами — пока не засосётся закрывающий тэг, браузер чаще всего вообще не может ничего показать.
Это проблема layout engine. Например, у Gecko родительский блок может "расти", удлиняться по мере того, как загружаются новые дочерние элементы. Хотя я не понимаю как это относится к распараллеливанию.
В этом случа можно как минимум распараллелить
1. Чтение из файла и парсинг.
2. Изменение DOM, пересчёт стилей.
3. Форматирование.
4. Посылка на экран.
Но это чисто фантазия, надо спросить у того, у кого есть опыт, например у c-smile.
LCR>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
Нересурсоемкий. Если это не скачка с FTP, где бывает целесообразно пускать несколько файлов одновременно, то всё упирается в скорость файловой системы, поэтому параллелить не нужно. А если это даст выигрыш, то каждый процессор может копировать по файлу.
Дополнительные процессоры могут заниматься распаковкой и расшифровкой файлов, если нужно.
LCR>3. Вызовы типа prog1 | prog2 | prog3 ...
-1, каждая программа может выполняться на отдельном процессоре (как минимум).
LCR>4. Авторизация в системе.
Нересурсоемкий. Те процессы, которые уже работают, будут работать как всегда. Те что еще не запущены, нас не интересуют Если на каком-нибудь сервере с громадным числом пользователей это важно, то некоторые сессии и оболочки могут быть предзагружены, опять же в разные процессоры, и по мере логинов (опять же каждый логин на своём процессоре) будут раздаваться.
LCR>Ещё продолжать?
Да, пожалуйста.
Я думаю, надо не гадать, а подумать. Если такие задачи есть, то в процессе их выполнение вы не работаете на компьютере, а ждете их выполнения. Пример: компиляция, архивания. Но в общем, на рабочей станции таких сложных вычислений нет, иначе смысл многозадачности сильно уменьшается (во время их выполнения вы не можете использовать компьютер на полную мощность).
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>>>3. Вызовы типа prog1 | prog2 | prog3 ...
E>>А можно обосновать?
LCR>Напомню, что мы на юзерском уровне.
Юзеру вообще совершенно фиолетово, как они исполняются. Поэтому вести разговор на этом уровне мне не интересно. Поэтому предлагаю перейти на уровень программистов
LCR>Возможно prog1..n и параллелятся где-то в кишках, но сами программы должны выполняться последовательно, поскольку программа i+1 может требовать полностью вывод программы i.
Не полностью, а только то, что ей сейчас необходимо на текущем вводе.
LCR>Ну например, каждая из программ prog. выводит SUCCESS или FAILED, и это значение необходимо для следующей.
Первый grep работает совешенно ни с кем не синхронизируясь (хотя синхронизация на уровне ввода-вывода, когда второй grep не успевает вычитывать свой входной поток). Второй grep должен засыпать только, если на его входе больше ничего нет. Если же на входе есть выход из первого grep-а, то второй grep берет очередную строку и обрабатывает ее (работая параллельно с первым grep-ом). А уж вывод второго grep-а вообще никак не нужно синхронизировать с первым grep-ом.
LCR>Если ты по-прежнему неудовлетворён ответом, возьми наконец ant, make etc. Уж здесь железно, если таск2 зависит от таска1, то пока таск1 не отработает, таск2 не начинается. Это просто прибито гвоздями в спецификации.
Это уже другой пример.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Да, если каждая из программ будет в конце своей работы выводить неизвестное априори сообщение, то такая зависимость налицо.
1. Если программы передают данные во время всего своего времени работы (канал), то они выполняются параллельно.
2. Если они передают данные только как результат, то вся работа алгоритма сводится к запуску нескольких процессов. При этом запуск 3 процессов одним быстрым процессором, или одним медленных и запуск трех процессов одновременно разными процессорами ничем особо не отличаются, т.к. всё равно обычно упираются в скорость чтения с диска. В крайнем слуае, если инициализация тяжелая, то распараллеливание не проиграет.
Исходный вопрос был о ситуациях, когда параллелить НУЖНО (имеет смысл).
Здравствуйте, Кодёнок, Вы писали:
Кё>Однако, у наращивания скорости процессора есть физический предел, а у наращивания их количества — нет.
Речь идет о том, что просто "разрабатывать алгоритм специально для такой архитектуры" недостаточно для получения реального выхлопа от роста количества процессоров.
Видишь ли, насколько мне известно, данной тематикой занимаются целые институты — всякие там раскрашенные сети петри и так далее — но результатов я в общем-то не знаю. Еще раз намекну про то, что решения для оптимальной загрузки процессоров сортировкой не существует. А очевидные решения быстро выходят на насыщение, и дальнейшее увеличение количества процессоров не приводит к росту производительности! Кё>Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
Экий ты быстрый. Вопрос про принципиальную параллелящесть сам по себе требует нехилого исследования для каждого конкретного случая. Что-то из области "перечислите все еще неоткрытые элементарные частицы. Объясните причины, препятствующие их открытию в настоящий момент".
Я всего лишь хотел несколько охладить оптимизм по поводу распараллеливания вычислений.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Да, тормоза 1-го и 2-го примеров связаны с тормозами на транспортном уровне. Я их привёл потому, что они последовательные с точки зрения пользователя (мы же здесь думаем про обычный, а не теоретически наилучший случай, не так ли?).
LCR>>3. Вызовы типа prog1 | prog2 | prog3 ... Кё>-1, каждая программа может выполняться на отдельном процессоре (как минимум).
Там я ответил eao где привёл ситуацию. Там пока будет выполняться prog1, остальные будут смиренно дожидаться своей очереди. Да. Зато каждая задача будет иметь свой собственный процессор, можно только порадоваться за задачи Но каждая задача — атом с точки зрения этой цепочки.
LCR>>4. Авторизация в системе. Кё>Нересурсоемкий. Те процессы, которые уже работают, будут работать как всегда. Те что еще не запущены, нас не интересуют Если на каком-нибудь сервере с громадным числом пользователей это важно, то некоторые сессии и оболочки могут быть предзагружены, опять же в разные процессоры, и по мере логинов (опять же каждый логин на своём процессоре) будут раздаваться.
Да нет, авторизация может выполняться очень долго. И это уже не связано с транспортом, а связано с вычислением хэшей. Хэши вычисляются последовательно, результат вычисления одного алгоритма хэширования является входом другого. То есть вычисление хэша — это атомарный вычислительный процесс.
Кё>Я думаю, надо не гадать, а подумать. Если такие задачи есть, то в процессе их выполнение вы не работаете на компьютере, а ждете их выполнения. Пример: компиляция, архивания. Но в общем, на рабочей станции таких сложных вычислений нет, иначе смысл многозадачности сильно уменьшается (во время их выполнения вы не можете использовать компьютер на полную мощность).
Именно!!! большинство тормозных десктопных задач софсем не связано с нагрузкой на процессор (а например, на сетку или диск). Здесь мы с тобой (да и не только) солидарны.
Поэтому любая десктопная непаралелящаяся задача будет "нересурсоёмкой", а любая тяжёлая непараллелящиеся задача — "специфической".
Вот я и гадаю, что бы ты хотел на "приведите мне десктопные ресурсоёмкие задачи"?
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>mik1,
LCR>>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
LCR>Да. Если бы пропускная способность файловой системы (а конкретно шины винчестера) была выше, то и копирование одного файла было бы быстрее А при копировании нескольких файлов одновременно будет наверное ещё хуже, потому что дёргание головки винчестеров тоже небесплатное.
LCR>Я говорю про копирование с одного каталога в другой на том же самом винчестере.
Ай-яй-яй. Какое правильное условие добавлено А мне как-то чаще приходится с CD/DVD или FTP копировать, чем между папками на одном винчестере. А винчестер может быть и не один (мы же помним один из советов Microsoft о том, что swap-файл, если есть возможность, надо размещать двумя частями на двух физических дисках. Чувствую, что они то параллельную запись тут реализовали).
LCR>>>3. Вызовы типа prog1 | prog2 | prog3 ...
M>>Только если между программами есть зависимости (явные — по данным, или неявные — по косвенным эффектам выполнения).
LCR>Да, если каждая из программ будет в конце своей работы выводить неизвестное априори сообщение, то такая зависимость налицо.
Команда "|" не подразумевает этого. Опять же в первоначальном сообщении об этом сказано не было
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Кодёнок, Вы писали:
Кё>>Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
AVK>Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
Забавная вещь. Работаю в банке. Казалось, что 99% работы составит либо рисование формочек, либо написание sql-запросов. Но вот частенько попадабтся задачи, которые иногда и не мешает распараллелить.
Например. Есть список ФИО сотрудников банка + кодов их подразделений. Есть списки пользователей различных информационных подсистем. Нужно сопоставить каждому пользователю из этих списков его код подразделения. Задача параллелится великолепно. А последовательно на 3 ГГц отрабатывает минут за 40...
Есть и другие задачи. Самый их главный критерий — их нельзя эффективно описать на SQL
А вот и с SQL пришло в голову. Длительная инициализация программы, состоящая в чтении данных из СУБД. Данные есть как зависящие от предыдущих считанных, так и не зависящие. Известно, что сервер недогружен. Почему бы не пустить инициализацию независимых блоков данных параллельно? Пользователю бы пришлось ждать меньше. Надеюсь, что задача для многих каждодневная и актуальная.
mik1,
M>Ай-яй-яй. Какое правильное условие добавлено А мне как-то чаще приходится с CD/DVD или FTP копировать, чем между папками на одном винчестере.
И тормоза сохраняются...
M> А винчестер может быть и не один (мы же помним один из советов Microsoft о том, что swap-файл, если есть возможность, надо размещать двумя частями на двух физических дисках. Чувствую, что они то параллельную запись тут реализовали).
Ну это уже детали, понимаешь. Опять же, для всех (даже для меня ) совершенно очевидно, что алгоритм "присваивание массива массиву" можно распараллелить.
M>Команда "|" не подразумевает этого. Опять же в первоначальном сообщении об этом сказано не было
Да, конечно.
Да, я потом вспомнил про ленивые потоки. Да вообще, я бы хотел от Кодёнка получить конкретизацию вопроса, какие такие непараллелящиеся задачи ему нужно, прежде чем продолжать искать. А то мои примеры сумбурные какие-то.
1.1.4 stable rev. 510
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
А при копировании нескольких файлов одновременно будет наверное ещё хуже, потому что дёргание головки винчестеров тоже небесплатное.
Но каждая задача — атом с точки зрения этой цепочки.
) совершенно очевидно, что алгоритм "присваивание массива массиву" можно распараллелить.