Здравствуйте, remark, Вы писали:
R>Что и требовалось доказать.
Избирательно копаете. Почему 32 потока? Кто-то предлагал ограничиться этим числом?
>По моим подсчётам оверхед на переключения в нормальной программе должен быть ~0.01%. Считать ли его большим?
Такой — нет. Но я советую посмотреть на правую часть приведенного графика. Там всё не так весело.

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

S>Здравствуйте, remark, Вы писали:
R>>Что и требовалось доказать.
S>Избирательно копаете. Почему 32 потока? Кто-то предлагал ограничиться этим числом?

32 потока в смысле, что система держит 32*число_процессоров потоков, т.е. на 32 ядерной системе будет нормально держаться 1024 потока. 32*число_процессоров потоков — это вполне нормальное число для построения системы на основе преемптивных потоков. Число потоков в такой системе не должно зависеть от пользователя/нагрузки/и т.д, оно должно определяться как раз аппаратной платформой.

>>По моим подсчётам оверхед на переключения в нормальной программе должен быть ~0.01%. Считать ли его большим?

S>Такой — нет. Но я советую посмотреть на правую часть приведенного графика. Там всё не так весело.

Правую в смысле где Windows 98 SE? Туда не стоит сейчас смотреть. Наоборот в последних ОС шедулер только улучшается.

Здравствуйте, Кодёнок, Вы писали:

Кё>Здравствуйте, remark, Вы писали:

R>>Y — это что такое? Время под мьютексами? Если да, значит программа не распараллелена, надо её соотв. образом переписать.

Кё>Это принципиально непараллелящаяся часть. Вроде сведения сумм в примере с суммированием массива.

parallel machines will "just" be implementing "embarrassingly parallel" programs— because we will be shifting to scalable algorithms

Кстати, сведение сумм прекрасно распараллеливается. Это делается на "обратном фронте" fork/join (conquer/divide) алгоритма, т.е. на join фазе, т.е. получается иерархическая агрегация данных.

R>>Так же ты не учитываешь, что это 100% легально, что бы одновременно выполнялся код под одним мьютексом и под другим. Представь множество из 10^6 объектов, каждый защищён своим мьютексом. 10^3 потоков вполне могут параллельно работать с этими объектами и никогда не ждать друг друга.

Кё>Только это не ты выбираешь, сколько у тебя мьютексов будет. Это специфика алгоритма. К тому же даже в таком же соотношении, один объект может быть по своей роли оказаться востребованным сразу всеми.

Значит надо просто взять другой алгоритм. Параллелизация и "поддержка многоядерности" не сводится просто к "добавлению потоков", она может включать и применению другого алгоритма.
Например, в однопоточном окружении часто используют хитрые быстродействующие алгоритмы сортировки. Но к сожалению они обычно не распарарллеливаются (потому что слишком хитрые). Распараллеливание такой сортировки будет заключаться в применении, допустим, менее эффективного, но зато отлично распараллеливаемого quick sort (тоже O(N*lgN)), при этом quick sort можно применить только на "верхнем" уровне, а когда массив уже достаточно побит на части (допустим до кусков по 1000 элементов), можно применить изначальный хитрый однопоточный алгоритм.
Таким образом, получаем и отличное распараллеливание и отличную производительность, и это при том, что в изначальной программе у нас вроде как была только не распараллеливамая часть.

Один мьютекс, востребованный сразу всеми, — это специфика алгоритма, или даже точнее — реализации алгоритма. В том то и дело. Это не врожденная специфика той задачи, которую требуется решить.
Безусловно, можно применить такой алгоритм и так его реализовать, что и на 2 ядра распараллеливаться не будет, тут даже о "росте числа ядер" и говорить не надо.
Суть не в том, что можно сделать не распараллеливаемо, суть в том, что можно сделать распараллеливаемо.

S>>Избирательно копаете. Почему 32 потока? Кто-то предлагал ограничиться этим числом?

R>32 потока в смысле, что система держит 32*число_процессоров потоков, т.е. на 32 ядерной системе будет нормально держаться 1024 потока. 32*число_процессоров потоков — это вполне нормальное число для построения системы на основе преемптивных потоков. Число потоков в такой системе не должно зависеть от пользователя/нагрузки/и т.д, оно должно определяться как раз аппаратной платформой.

На одноядерной машине под виндой можно было и 256 потоков запустить без заметного влияния на быстродействие.
Поскольку ядро системы для таких машин вместо честного InterlockedXXX с префиксом LOCK использует обычные операции,
все мутексы, CS и т.д. тоже построены на том, что ядро проца _одно_.

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

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


S>>>Избирательно копаете. Почему 32 потока? Кто-то предлагал ограничиться этим числом?

R>>32 потока в смысле, что система держит 32*число_процессоров потоков, т.е. на 32 ядерной системе будет нормально держаться 1024 потока. 32*число_процессоров потоков — это вполне нормальное число для построения системы на основе преемптивных потоков. Число потоков в такой системе не должно зависеть от пользователя/нагрузки/и т.д, оно должно определяться как раз аппаратной платформой.

K13>На одноядерной машине под виндой можно было и 256 потоков запустить без заметного влияния на быстродействие.
K13>Поскольку ядро системы для таких машин вместо честного InterlockedXXX с префиксом LOCK использует обычные операции,
K13>все мутексы, CS и т.д. тоже построены на том, что ядро проца _одно_.

K13>Запустите 32 потока вместо одного на двухядерной машине, привязав все потоки к одному процессору -- это даст более реальный результат.

Я не думаю, что на современных ОС (Windows Vista, Windows Server 2003) это сильно повлияет на результат. Не в префиксе lock суть, суть в том, что шедулеры теперь распределенные. Тем более, что LOCK как таковой сильно подешевел на последних процессорах.

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

R>По моим подсчётам оверхед на переключения в нормальной программе должен быть ~0.01%. Считать ли его большим? Стоит ли гнаться за элиминацией этого оверхеда?
Дело не только в переключении контекста... У вытесняющей многозадачности есть куча побочных эффектов типа convoy phenomenon, особенно, когда начинается борьба за ресурсы между потоками, в этом-то и есть главная засада.

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

E>Здравствуйте, Кодёнок, Вы писали:

Кё>>Я правильно понимаю, что любой многопоточный код с ростом числа ядер достигнет числа, когда прирост остановится совсем, а при дальшейнем превышении — начнется замедление назад?

E>JFYI: Is the free lunch really over? Scalability in Many-core Systems: Part 1 in a Series
E>

E>Figure 1-1. Amdahl’s Law curves for 8 cores, varying degrees of parallelism.

E>Figure 1-2. Amdahl’s Law curves for 216 cores, varying degrees of parallelism.

Помимо графиков, построенных на основании закона Амдала, дальше в статье написано про корректировку, которую предложил Густафсон:

The key flaw in Amdahl’s Law was pointed out as early as 1988, by John Gustafson: it assumes either a fixed computational workload, or a fixed scaling of serial and parallel portions as the problem size is increased.
The alternative, often referred to as Scaled Speedup, looks instead at increasing the problem size for a given amount of time.

То бишь, с ростом вычислительных ресурсов обычно растёт и доступный для вычисления размер задачи, тогда как строго последовательный код остаётся ограниченным. Так что масштабируемость с ростом числа ядер — вопрос не только кода, но и объёма данных, которые код обрабатывает.