Я правильно понимаю, что любой многопоточный код с ростом числа ядер достигнет числа, когда прирост остановится совсем, а при дальшейнем превышении — начнется замедление назад? Оцениваю так:
ВремяВыполнения = X + Y + Z = ВремяПараллелящегосяКода/ЧислоЯдер + ВремяПодМьютексами + ПереключениеКонтекстов*ЧислоЯдер
С ростом числа ядер, время X падает, Y — остается постоянным, а Z — растет.
Функция f(x) = a/x + b + cx при увеличении x рано или поздно начинает расти независимо от соотношения [положительных] констант a, b, c.
При соотношениях 0.98/x + 0.01 + 0.01*x где-то на сотне штук время сравнивается с одноядерником и неограниченно растет.
Может быть похуже, 0.88/x + 0.1 + 0.02*x — уже на 34.
Получается, что как не пыжься с оптимизацией, минимизируя время проведенное в мьютексах, затраты на конкуренцию все равно все погубят.
Интуитивно я согласен — для каждой задачи есть свой оптимум исполнителей, два человека забьют два гвоздя в 2 раза быстрее, чем один, но если это будут делать 16 человек — получится только замедление.
Выходит, идеально распараллеленый софт — не тот, который загрузит все ядра, а тот, который оценит нужное ему число и загрузит только их?
Здравствуйте, Кодёнок, Вы писали:
Кё>Я правильно понимаю, что любой многопоточный код с ростом числа ядер достигнет числа, когда прирост остановится совсем, а при дальшейнем превышении — начнется замедление назад? Оцениваю так:
Здравствуйте, Кодёнок, Вы писали: Кё>ВремяВыполнения = X + Y + Z = ВремяПараллелящегосяКода/ЧислоЯдер + ВремяПодМьютексами + ПереключениеКонтекстов*ЧислоЯдер Кё>С ростом числа ядер, время X падает, Y — остается постоянным, а Z — растет.
Совершенно непонятно, почему Z должно неограниченно расти.
АФАИК, если у "лишних" ядер нет работы, то никаких дополнительных переключений контекстов происходить не будет.
Далее, время под мьютексами вовсе не обязано оставаться постоянным. В предельном случае однопоточной программы Y очевидно строго равно нулю.
Нулю оно также равно в случае идеально распараллеленного алгоритма, которому не нужны общие данные (но это экзотика).
Представим себе менее тривиальный случай. Например, мы считаем сумму чисел в массиве.
Делим массив размером M на N фрагментов; каждый поток считает сумму по своему фрагменту и шарашит ее в общую сумму.
Очевидно, что всего понадобится N обращений к сумме, которые потребуют мьютекса (забудем пока про интерлокед инкремент), и время простоя в каждом из них будет примерно пропорционально (N-1). То есть Y ~ N^2.
В общем, модель вышла какая-то неубедительная.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Делим массив размером M на N фрагментов; каждый поток считает сумму по своему фрагменту и шарашит ее в общую сумму. S>Очевидно, что всего понадобится N обращений к сумме, которые потребуют мьютекса (забудем пока про интерлокед инкремент), и время простоя в каждом из них будет примерно пропорционально (N-1). То есть Y ~ N^2.
Верно, но тогда тенденция все равно сохраняется. По большому счету ведь интересует, пойдет N в числитель или в знаменатель.
Здравствуйте, Sinclair, Вы писали:
S>АФАИК, если у "лишних" ядер нет работы, то никаких дополнительных переключений контекстов происходить не будет.
Ну это если нет. Неинтересно. Если у всех ядер нет работы, то и переключаться некому, разве что потокам прочих процессов
S>Далее, время под мьютексами вовсе не обязано оставаться постоянным. В предельном случае однопоточной программы Y очевидно строго равно нулю.
Это тоже тривиальный случай.
S>Нулю оно также равно в случае идеально распараллеленного алгоритма, которому не нужны общие данные (но это экзотика).
Это не такая уж экзотика. Если брать твой пример с суммированием массива, то в нем общие данные есть. А вот если взять мой любимый пример с суммированием двумерного массива по строкам или столбцам, то он прекрасно параллелится без каких-либо общих данных. Каждый поток совершенно сам по себе, а поток-инициатор ждет, когда они все закончатся. Если потоков столько, сколько ядер — идеальная распараллеленность (естественно, я не учитываю потоки прочих процессов и дела в ядре).
А если CUDA взять (я с ней сейчас разбираюсь), то там параллится на N аппаратных тредов, каждый из них занимается свои кусочком, а потом, если им надо, то вызывается syncthreads(), что заставляет их сойтись в этой точке. Переключений контекста нет вообще. "На старт! Внимание! Марш!" — и все побежали по своей дорожке. А на финише их ждет судья — syncthreads(), и когда он последнего дождется, можно новый забег организовать. И на обычном процессоре такое можно смоделировать (что я и сделал
Например, суммирование двух линейных массивов сводится к тому, что каждый тред находит сумму своей пары x[i] и y[i] и пишет в z[i] (ну я немного упростил). А syncthread вызывается, чтобы быть уверенным, что все треды свое действие выполнили.
S>Представим себе менее тривиальный случай. Например, мы считаем сумму чисел в массиве. S>Делим массив размером M на N фрагментов; каждый поток считает сумму по своему фрагменту и шарашит ее в общую сумму. S>Очевидно, что всего понадобится N обращений к сумме, которые потребуют мьютекса (забудем пока про интерлокед инкремент), и время простоя в каждом из них будет примерно пропорционально (N-1). То есть Y ~ N^2.
S>В общем, модель вышла какая-то неубедительная.
+1. В этой модели неявно предполагается, что потоки постоянно переключаются. Между тем переключение потоков — совсем не обязательная ситуация. Вот на одном ядре им точно придется переключаться
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Это не такая уж экзотика. Если брать твой пример с суммированием массива, то в нем общие данные есть. А вот если взять мой любимый пример с суммированием двумерного массива по строкам или столбцам, то он прекрасно параллелится без каких-либо общих данных. Каждый поток совершенно сам по себе, а поток-инициатор ждет, когда они все закончатся. Если потоков столько, сколько ядер — идеальная распараллеленность (естественно, я не учитываю потоки прочих процессов и дела в ядре).
Да, именно про это я и говорил. К сожалению, в жизни крайне редко встречаются случаи, когда можно полностью divide & konquer.
Для них можно просто считать количество мьютексов равным нулю, и получать линейное увеличение шустродействия.
Естественно, при условии отсутствия конфликтов кэширования. В противном случае опять окажется, что раскидывание суммирования по дополнительным ядрам будет только портить cache locality и ухудшать общую производительность.
PD>+1. В этой модели неявно предполагается, что потоки постоянно переключаются. Между тем переключение потоков — совсем не обязательная ситуация. Вот на одном ядре им точно придется переключаться
Это если их больше одного
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Кодёнок, Вы писали:
Кё>Я правильно понимаю, что любой многопоточный код с ростом числа ядер достигнет числа, когда прирост остановится совсем, а при дальшейнем превышении — начнется замедление назад?
Здравствуйте, Sinclair, Вы писали:
S>Для них можно просто считать количество мьютексов равным нулю, и получать линейное увеличение шустродействия. S>Естественно, при условии отсутствия конфликтов кэширования. В противном случае опять окажется, что раскидывание суммирования по дополнительным ядрам будет только портить cache locality и ухудшать общую производительность.
Увы. Именно это у меня и имеет место быть. В пределах терпимого, но избавиться полностью пока не смог. Так что не линейное, но близкое к нему. Хотя пробовал на 2 ядрах и на 4 (заказчик пробовал). Вообще говоря, если опять-таки мое любимое суммирование матрицы взять, то по строкам — все будет идеально (при достаточно большой длине строки, а тем более при выровненности на длину линейки кеша они друг другу не конкуренты), а по столбцам — можно ведь и до абсурда довести, когда каждое ядро своим столбцом занимается, тут их (ядер) кеши передерутся все
Так что не такое уж простое это дело — распараллеливать алгоритмы
В CUDA это чистый кошмар. Стоит хоть где-то нарушить правила выравнивания, и вместо параллельной обработки будет последовательная.
PD>>+1. В этой модели неявно предполагается, что потоки постоянно переключаются. Между тем переключение потоков — совсем не обязательная ситуация. Вот на одном ядре им точно придется переключаться S>Это если их больше одного
Здравствуйте, Pavel Dvorkin, Вы писали:
S>>В общем, модель вышла какая-то неубедительная.
PD>+1. В этой модели неявно предполагается, что потоки постоянно переключаются. Между тем переключение потоков — совсем не обязательная ситуация. Вот на одном ядре им точно придется переключаться
Под X подразумевается параллелящийся код, под Y — последовательный, а под Z — издержки. Я конечно подразумеваю, что издержки всегда есть, и они зависят от числа ядер (и не сходятся к константе).
В Z так же входят затраты на конкуренцию, например, холостые обороты в спинлоках или переключение в kernel mode. Их может быть мало, но если начать прибавлять ядра не поштучно, а порядками, от 20 к 200, от 200 к 2000, то тенденция к деградации должна начаться именно из-за этого.
Еще другой процесс/модуль тоже может запустить свой тред-пул по числу ядер, и все, появились постоянные переключения.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Тебе в MS-DOS захотелось ?
При чем тут MS-DOS? Я констатирую медицинский факт: вытесняющая многозадачность — штука дорогостоящая. Кооперативная многозадачность для однопоточных приложений куда как лучше. Об этом, кстати, нам лично Вирт рассказывал десять лет назад Почтил, тскать, личным присутствием.
Конечно, вытесняющая многозадачность удобнее — нет риска повесить всю систему неосторожным зацикливанием.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Тебе в MS-DOS захотелось ? S>При чем тут MS-DOS? Я констатирую медицинский факт: вытесняющая многозадачность — штука дорогостоящая. Кооперативная многозадачность для однопоточных приложений куда как лучше. Об этом, кстати, нам лично Вирт рассказывал десять лет назад Почтил, тскать, личным присутствием. S>Конечно, вытесняющая многозадачность удобнее — нет риска повесить всю систему неосторожным зацикливанием.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Ты совсем шутки разучился понимать
Ты просто данную шутку часто повторять стал. Я и не могу понять — то ли ты шутишь, то ли до сих пор так и не понял, как высокопроизводительные сервера на одноядерных машинах работают.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Кодёнок, Вы писали:
Кё>Я правильно понимаю, что любой многопоточный код с ростом числа ядер достигнет числа, когда прирост остановится совсем, а при дальшейнем превышении — начнется замедление назад? Оцениваю так:
Кё>ВремяВыполнения = X + Y + Z = ВремяПараллелящегосяКода/ЧислоЯдер + ВремяПодМьютексами + ПереключениеКонтекстов*ЧислоЯдер
Кё>С ростом числа ядер, время X падает, Y — остается постоянным, а Z — растет.
Теоретически это действительно так. Т.е. при бесконечном росте числа ядер ты не получишь бесконечного уменьшения времени работы. НО! В тоже время при росте числа ядер можно добиться того, что бы время работы приложения (не какой-то отдельной его части, а именно всего приложения) снизилось, допустим, до 100 мкс. Да, 1 нс не получим. Но надо ли?
Т.е. вывод такой, что при бесконечном росте числа ядер мы можем получить для любой задачи sub-user-visible время выполнения. Мне кажется этого вполне достаточно.
По поводу необходимого кол-ва ядер. На практике это не составляет проблемы и решается тривиально — ограничением гранулярности "задач". Т.е. допустим ограничили гранулярность задачи 10 мкс. Имеем работы на 1 с. Значит бьём эту работу на 100 000 задач. Если у нас будет больше ядер — они автоматически не будут использоваться.
Здравствуйте, Sinclair, Вы писали:
S>При чем тут MS-DOS? Я констатирую медицинский факт: вытесняющая многозадачность — штука дорогостоящая.
Дорогостоящая? Насколько конкретно? Сколько процентов производительности она съедает (и соотв. сколько можно выгадать, если от неё избавиться)? Сколько занимает одно переключение?
Для контекста примем время кванта — 20мс, т.е. ~60 000 000 тактов.
Здравствуйте, eao197, Вы писали:
Кё>>Я правильно понимаю, что любой многопоточный код с ростом числа ядер достигнет числа, когда прирост остановится совсем, а при дальшейнем превышении — начнется замедление назад?
E>JFYI: Is the free lunch really over? Scalability in Many-core Systems: Part 1 in a Series E>[q] E>Figure 1-1. Amdahl’s Law curves for 8 cores, varying degrees of parallelism.
[красивые картинки поскипаны]
Ну если производительность остановится в такой точке, что любое приложение будет выполняться не более, допустим, 10 мкс. То меня бы это вполне устроило. Вас — нет?
Здравствуйте, remark, Вы писали:
R>Дорогостоящая? Насколько конкретно? Сколько процентов производительности она съедает (и соотв. сколько можно выгадать, если от неё избавиться)? Сколько занимает одно переключение?
Давай копнем архивы
Здравствуйте, remark, Вы писали:
R>Т.е. вывод такой, что при бесконечном росте числа ядер мы можем получить для любой задачи sub-user-visible время выполнения. Мне кажется этого вполне достаточно.
Почему оно обязательно будет sub-user-visible? Что если для комбинации алгоритм + данные минимум (Y) будет равняться 100 лет?
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, remark, Вы писали:
R>>Дорогостоящая? Насколько конкретно? Сколько процентов производительности она съедает (и соотв. сколько можно выгадать, если от неё избавиться)? Сколько занимает одно переключение?
S>Давай копнем архивы
Для двухпроцессорной системы два потока в программе дают оптимальную и максимально возможную производительность программы. Однако увеличение количества потоков приводит к постоянному увеличению времени выполнения программы на десять и более процентов. С другой стороны, на однопроцессорной системе увеличение количества потоков до 32 практически не сказывается на времени выполнения программы,
Что и требовалось доказать. И это определенно не лучший пример программы, ну точнее он лучший для вскрытия оверхедов на переключения, и даже он не смог их вскрыть. И так же учтём, что последние версии ОС (Vista, Server2008) существенно улучшают механизм планирования потоков.
По моим подсчётам оверхед на переключения в нормальной программе должен быть ~0.01%. Считать ли его большим? Стоит ли гнаться за элиминацией этого оверхеда?
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, remark, Вы писали:
R>>Т.е. вывод такой, что при бесконечном росте числа ядер мы можем получить для любой задачи sub-user-visible время выполнения. Мне кажется этого вполне достаточно.
Кё>Почему оно обязательно будет sub-user-visible? Что если для комбинации алгоритм + данные минимум (Y) будет равняться 100 лет?
Y — это что такое? Время под мьютексами? Если да, значит программа не распараллелена, надо её соотв. образом переписать.
Так же ты не учитываешь, что это 100% легально, что бы одновременно выполнялся код под одним мьютексом и под другим. Представь множество из 10^6 объектов, каждый защищён своим мьютексом. 10^3 потоков вполне могут параллельно работать с этими объектами и никогда не ждать друг друга.
When we look at those software houses, however, aren't they still mainly coding "embarrassingly parallel" applications?
Like many people, I dislike the term "embarrassingly parallel," but it is used so often there seems to be no way to avoid it. The term "embarrassingly parallel" really means anything that scales well. There is really nothing embarrassing about scaling well.
The term "embarrassingly parallel" has been mostly used to refer to algorithms where the best known solutions are able to scale well on supercomputers.
All algorithms are getting a second look, to see if there are equivalent or better algorithms that are "embarrassingly parallel."
For example, it turns out ray tracing is a superior rendering method for visualization, but we haven't had enough horsepower to do ray tracing. So we'll been using other less compute intensive methods despite the superiority of ray tracing. Parallelism makes ray-tracing work. We'll move to preferring ray-tracing in the future, not because it is "embarrassingly parallel," but because it is better and parallelism offers the horsepower to adopt it.
The shift to replacing algorithms that cannot scale will mean all programs try to be "embarrassingly parallel." This will make your question a self-fulfilling prophecy. Yes, parallel machines will "just" be implementing "embarrassingly parallel" programs— because we will be shifting to scalable algorithms.
Здравствуйте, remark, Вы писали:
R>Y — это что такое? Время под мьютексами? Если да, значит программа не распараллелена, надо её соотв. образом переписать.
Это принципиально непараллелящаяся часть. Вроде сведения сумм в примере с суммированием массива.
R>Так же ты не учитываешь, что это 100% легально, что бы одновременно выполнялся код под одним мьютексом и под другим. Представь множество из 10^6 объектов, каждый защищён своим мьютексом. 10^3 потоков вполне могут параллельно работать с этими объектами и никогда не ждать друг друга.
Только это не ты выбираешь, сколько у тебя мьютексов будет. Это специфика алгоритма. К тому же даже в таком же соотношении, один объект может быть по своей роли оказаться востребованным сразу всеми.
