Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 08:00
Оценка:
Здравствуйте!

Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.
WBR — Yuriy
Re: Несколько потоков - быстрее вычичсление?
От: TfL  
Дата: 23.05.08 08:12
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте!


D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Конечно можно. Но есть лимит по кол потоков. Помниться даже рекоминдации были не более 4-6 потоков. Дальше система начинает деградировать.
Соотв и алгоритма может зависть, но это уж ваша математика.
Re[2]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 08:16
Оценка:
Здравствуйте, TfL, Вы писали:

...
TfL>Конечно можно.
Если можно в двух словах — за счет чего? Просто идею.
WBR — Yuriy
Re[3]: Несколько потоков - быстрее вычичсление?
От: TfL  
Дата: 23.05.08 08:44
Оценка: 3 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте, TfL, Вы писали:


D>...

TfL>>Конечно можно.
D>Если можно в двух словах — за счет чего? Просто идею.

Насколько я осведомлен, у основного потока есть приоритет и ОС выделяет определенный квант.. нето времени .. нето ресурса

Если мы разбиваем вычисление на несколько потоков, соотв получаем больше выч ресурса,

Но 1. есть лимит по кол потоков после чего выигрыш переростает в проигрыш ..
2. проблемы синхронизации + усложнение логики прогр
3. тонкости реализации многопоточности в ОС ..
Re: Несколько потоков - быстрее вычичсление?
От: tyger Россия  
Дата: 23.05.08 08:49
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте!


D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Конечно можно! Особенно если на системе многоядерный процессор или хотябы с технологией HyperThrading... Где-то здесь даже тест пробегал по производительности.

Если вычисления незвисимые или почти независимые, то на любой системе должен быть прирост. Если пользоваться потоками .NET, то они сами будут раскиданы по разным ядрам...
Re[4]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 08:49
Оценка:
Здравствуйте, TfL, Вы писали:
Спасибо TfL!
Идея понятна, спасибо!
WBR — Yuriy
Re[2]: Несколько потоков - быстрее вычичсление?
От: vasmann  
Дата: 23.05.08 08:58
Оценка:
Здравствуйте, tyger, Вы писали:

T>Если вычисления незвисимые или почти независимые, то на любой системе должен быть прирост. Если пользоваться потоками .NET, то они сами будут раскиданы по разным ядрам...


Всегда думал что ОС занимается распределнием нагрузки на ядра/процессоры ...
Re[3]: Несколько потоков - быстрее вычичсление?
От: vmpire Россия  
Дата: 23.05.08 09:06
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте, TfL, Вы писали:


D>...

TfL>>Конечно можно.
D>Если можно в двух словах — за счет чего? Просто идею.

Я думаю, за счёт того что почти все современные процессоры многопоточные — несколько ядер или, хотя бы, hyperthreading.
В этом случае потоки будут выполняться параллельно.

Плюс, даже на одном процессоре можно получить выигрыш в некоторых случаях. Например, если один поток ждёт окончания ввода/вывода, другой в это время может что-то считать.
Re: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 09:54
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Если есть возможность использовать .NET Framework 3.5, то рекомендую посмотрет на Parallel FX библиотеку от MS. Очень удобно быстро распараллелить всякие for циклы. Если .NET Framework 2.0, то могу сюда выложить аналог той библиотеки (мой велосипед ).
Re: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 10:07
Оценка: +3 -2
Здравствуйте, den123, Вы писали:

D>Здравствуйте!


D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.

Прямой зависимости больше потоков — быстрее вычисление не существует. Все зависит от множества условий. Вы можете получить выигрыш в производительности если:
— алгоритм хорошо распараллеливается (одному потоку не надо ждать результатов расчета в другом потоке)
— паралельные потоки не конкурируют за доступ к одному и тому же ресурсу (диск, порт, сеть, графическая подсистема, соединение с БД, и наконец процессор)
— аппаратная платформа поддерживает паралельное исполнение (это частный случай предыдущего пункта, когда ресурс — процессор)
— накладные расходы на обеспечение параллельного исполнения не велики по сравнению с общим временем расчета.
А теперь оцените по этим критериям свою задачу.
Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.
Если же можно отделить расчеты от графического вывода, графический вывод от работы с диском или сетью, и разнести это по разным потокам, то это даст прирост производительности даже на однопроцессорной системе. Просто за счет уменьшения простоев при работе с ресурсами.
Или например, распараллеливание алгоритма поэлементного сложения двух массивов в 1000 элементов каждый на тысячу потоков. Производительность упадет на несколько порядков по сравнению с выполнением в одном потоке, за счет накладных расходов на распараллеливание.
Понедельник начинается в субботу
Многопоточность
Re[2]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 10:08
Оценка:
Здравствуйте, Димчанский, Вы писали:

...

Д>Если есть возможность использовать .NET Framework 3.5, то рекомендую посмотрет на Parallel FX библиотеку от MS. Очень удобно быстро распараллелить всякие for циклы. Если .NET Framework 2.0, то могу сюда выложить аналог той библиотеки (мой велосипед ).


Спасибо! В библиотеке нет необходимости. Во всяком случае пока. На данном этапе мне важно было понять лишь возможность такого "ускорения" и идею.
WBR — Yuriy
Re[2]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 10:14
Оценка:
Здравствуйте, stump, Вы писали:

S>

Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

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

Может я не правильно понял предыдущих товарищей?
WBR — Yuriy
Re[3]: Несколько потоков - быстрее вычичсление?
От: TfL  
Дата: 23.05.08 10:19
Оценка: 2 (1) -2
Здравствуйте, den123, Вы писали:

D>Здравствуйте, stump, Вы писали:


S>>

D>

D>Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

D>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

D>Может я не правильно понял предыдущих товарищей?

все вы правильно поняли, в нескольких потоках будет работать быстрее, но есть верхняя граница по кол потоков и бла бла бла ..
Re[3]: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 10:29
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Спасибо! В библиотеке нет необходимости. Во всяком случае пока. На данном этапе мне важно было понять лишь возможность такого "ускорения" и идею.


Понял. На мой взгляд ускорение будет заметное (в зависимости от распараллелености алгоритма), если в процессоре не одно ядро или он гипертрединг поддерживает. Если там одно ядро без гипертрединга, то сомневаюсь, что в каких-то массивных вычисления будет ускорение, скорее наоборот некоторое падение производительности из-за оверхеда связанного с синхронизацией.
Re[3]: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 10:31
Оценка: 1 (1) +2
Здравствуйте, den123, Вы писали:

D>Здравствуйте, stump, Вы писали:


S>>

D>

D>Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

D>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

D>Может я не правильно понял предыдущих товарищей?


Мы берем абстрактный случай — чисто расчетный алгоритм, который работает только с данными в стеке и куче и не вызывает никаких внешних API, например, то-же суммирование массивов. И выполняем его паралельно в двух потоках.
В одонопроцессорной системе мы гарантированно получаем снижение производительности. Потоки последовательно получают кванты времени в течении которых выполняются, плюс каждое переключение контекста потоков занимает несколько тысяч процессорных тактов. Вот это переключение контекста и дает снижение производительности. Это может быть снижение на 10% или на 0.1%, но увеличения гарантировано не будет.
Есть еще один фактор — это кэширование данных. Для оптимизации часть данных с которыми работает поток подгужается в процессорный кэш. Если к этим данным (или даже не именно к этим, а к рядом лежащим) обращаются из другого потока, они выгружаются из кэша и обращение идет непосредственно к памяти. Это еще снижает производительность. Причем даже на многоядерных системах.
Из-за этого, распаралеливая расчетна два потока мы обычно вместо 100% прироста производительности получаем 30% — 60%.
Понедельник начинается в субботу
Re[4]: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 10:34
Оценка: +1
Здравствуйте, TfL, Вы писали:

TfL>Здравствуйте, den123, Вы писали:


D>>Здравствуйте, stump, Вы писали:


S>>>

D>>

D>>Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

D>>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

D>>Может я не правильно понял предыдущих товарищей?

TfL>все вы правильно поняли, в нескольких потоках будет работать быстрее, но есть верхняя граница по кол потоков и бла бла бла ..
Объясните откуда прирост берется. На пальцах. Без бла бла бла...
Понедельник начинается в субботу
Re: Несколько потоков - быстрее вычичсление?
От: TK Лес кывт.рф
Дата: 23.05.08 10:38
Оценка: +5
Здравствуйте, den123, Вы писали:

D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Увеличение производительности возможно только в том случае, если это подкрелено дополнительным hardware (несколько ядер процессора/процессоров)
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re[4]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 11:03
Оценка: -1
Здравствуйте, stump, Вы писали:


S>Мы берем абстрактный случай — чисто расчетный алгоритм, который работает только с данными в стеке и куче и не вызывает никаких внешних API, например, то-же суммирование массивов. И выполняем его паралельно в двух потоках.
S>В одонопроцессорной системе мы гарантированно получаем снижение производительности. Потоки последовательно получают кванты времени в течении которых выполняются, плюс каждое переключение контекста потоков занимает несколько тысяч процессорных тактов. Вот это переключение контекста и дает снижение производительности. Это может быть снижение на 10% или на 0.1%, но увеличения гарантировано не будет.
S>Есть еще один фактор — это кэширование данных. Для оптимизации часть данных с которыми работает поток подгужается в процессорный кэш. Если к этим данным (или даже не именно к этим, а к рядом лежащим) обращаются из другого потока, они выгружаются из кэша и обращение идет непосредственно к памяти. Это еще снижает производительность. Причем даже на многоядерных системах.
S>Из-за этого, распаралеливая расчетна два потока мы обычно вместо 100% прироста производительности получаем 30% — 60%.

Я думаю, что Вы абсолютно правы, если на машине НИЧЕГО ДРУГОГО не выполняется. Т.е. если есть только одна задача — моя, то любое разбиение чисто вычислительной задачи на потоки только вызовет потерю производительности из-за накладных расходов на переключения и т.п. Однако, если на машине выполняется много других задач, то можно получить выигрыш производительности. ОС все равно будет прерывать мою задачу/мой поток, чтобы дать очередной квант времени какой-то другой задаче. Если в число таких задач поставить другие мои потоки, то в целом моя задача получит бОльшее количество квантов времени на выполнение. Разумеется, что разбиение на N потоков не принесет увелечения производительности в N раз.
WBR — Yuriy
Re[3]: Несколько потоков - быстрее вычичсление?
От: Nonmanual Worker  
Дата: 23.05.08 11:03
Оценка: -1
Здравствуйте, den123, Вы писали:

D>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.


D>Может я не правильно понял предыдущих товарищей?


stump вам все четко и верно расписал.
На многопроцессорной системе будет выигрыш однозначно, в идеале во столько раз, сколько процессоров (но реально конечно немного меньше).
На однопроцессорной машине, для чисто расчетной задачи, будет падение суммарной производительности при распараллеривании, и чем больше потоков — тем сильнее падение. На сколько % — сказать не могу. Однако, гипотетически, если одновременно работает несколько процессороемких задач помимо вашей, то возможен небольшой прирост производительности за счет вытеснения других задач.
Поэтому определяйте сколько ядер — делайте столько же потоков — и вперед.
Re[5]: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 11:42
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Если в число таких задач поставить другие мои потоки, то в целом моя задача получит бОльшее количество квантов времени на выполнение.


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

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