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

Как-то все думал, стоит ли говорить то, что скажу. Нестандартно это очень...

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

>Во второй половине следующего года Intel намерена выпустить процессор с 16 аппаратными потокамию. И через 5 лет они собираются выпустить процессор с 80 ядрами! (Представть свои программы на 80 ядрах! Есть идеи как их использовать?)

А зададимся-ка таким вопросом. Представьте себе. что через 5 лет будет выпущен одноядерный процессор с быстродействием в 80 раз больше нынешнего. Вы его предпочтете или это многоядерное чудовище ?

Я в свое время голосование устроил

http://www.rsdn.ru/poll/1851.aspx

Автор: Pavel Dvorkin
Дата: 25.06.07
Вопрос: Какую машину бы Вы предпочли

Как видите, хоть и незначительное, но все же большинство предпочитает одноядерный процессор паре двухядерных с той же суммарной частотой. И это неудивительно — про распараллеливание много сказано, а попробуйте обратную задачу решить — заставить один поток исполняться на двух процессорах, дабы полностью использовать мощность компьютера. Именно так — на остальные процессы наплевать, им ничего не дадим (насколько сможем), а вот этому процессу — всю мощь PC. А он однопоточный по характеру самого алгоритма. Ну и как ?


Если же ситуация иная, и потоков много, то на этом жутком 80x скоростном процессоре время переключения потоков будет настолько ничтожным по сравнению с суммарным временем, что им просто можно будет пренебречь (разумеется, в предположении, что и скорость работы памяти увеличится так же) . И можете теперь рассматривать как один 80x скоростной процессор или , если хотите, как 80 1x-скоростных процессоров или как-то еще иначе.

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

Я уж не говорю о том. что при этом применяются решения, которые совсем не очевидны. Тут много о кэше памяти говорилось. А ведь кэш-память — это кэш ОП, а не процессора. И быть ей надо бы ИМХО именно кэш-памятью на самой ОП, а не у каждого процессора, тогда бы и проблем с синхронизацией кэша не было бы. Если процессор == поток, то получаем кэш у потока, вместо того, чтобы иметь его у процесса, отсюда и все проблемы. Но сделать иначе — технически невозможно, а точнее, не заложено в архитектуру.

Вот такие пироги...

Жить нам, конечно, с этими многоядерными монстрами придется, и проблемы решать — тоже. Но, похоже, многие из них не фундаментальные проблемы, а проблемы, которые на нас изготовители оборудования переложили.

P.S. Лично мое мнение о многопоточности очень простое. Если по характеру алгоритма распараллеливания нет — не надо ее насильно туда совать. Если оно может быть, но можно обойтись без него — тоже лучше не надо. Вот только если обойтись нельзя, то есть алгоритм по своей сути параллельный — тогда да.

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

PD>И это неудивительно — про распараллеливание много сказано, а попробуйте обратную задачу решить — заставить один поток исполняться на двух процессорах, дабы полностью использовать мощность компьютера. Именно так — на остальные процессы наплевать, им ничего не дадим (насколько сможем), а вот этому процессу — всю мощь PC. А он однопоточный по характеру самого алгоритма. Ну и как ?

Чего-то я запутался... Во-первых, занять одним потоком два процессора (если мы говорим о чем-то подобном threads в Windows) вроде как невозможно по определению. А если речь идет о процессе, а не о потоке, то это вроде и есть задача по распареллеливанию — замена "однопоточных" алгоритмов "многопоточными". Или я где-то ошибаюсь?

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

HB>Чего-то я запутался... Во-первых, занять одним потоком два процессора (если мы говорим о чем-то подобном threads в Windows) вроде как невозможно по определению.

Я именно об этом и говорю. Если программа однопоточная, то на двухядерном процессоре она может использовать только половину его мощности. В то время как на одноядерном процессоре — либо она все 100%, либо две программы по 50% — тоже все 100, либо четыре по 25% и т.д. А вот одна однопоточная 100% — не может.

У меня как раз задача — взять от процессора всю его мощность. А задача не является по своей сути распараллеливаемой, по крайней мере на первый взгляд. Так что придется ее распараллеливать искусственно...

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

PD>Я именно об этом и говорю. Если программа однопоточная, то на двухядерном процессоре она может использовать только половину его мощности. В то время как на одноядерном процессоре — либо она все 100%, либо две программы по 50% — тоже все 100, либо четыре по 25% и т.д. А вот одна однопоточная 100% — не может.

PD>У меня как раз задача — взять от процессора всю его мощность. А задача не является по своей сути распараллеливаемой, по крайней мере на первый взгляд. Так что придется ее распараллеливать искусственно...

А, ну так это, ИМХО, довольно общее место — то, что многоядерные системы хорошо подходят для распараллеливаемых задач, и плохо — для нераспараллеливаемых. Вряд ли кто-то с этим не согласится.

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

HB>А, ну так это, ИМХО, довольно общее место — то, что многоядерные системы хорошо подходят для распараллеливаемых задач, и плохо — для нераспараллеливаемых. Вряд ли кто-то с этим не согласится.

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

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

PD>Здравствуйте, Hobot Bobot, Вы писали:

HB>>А, ну так это, ИМХО, довольно общее место — то, что многоядерные системы хорошо подходят для распараллеливаемых задач, и плохо — для нераспараллеливаемых. Вряд ли кто-то с этим не согласится.

PD>А вот потенциальный одноядерный с быстродействием, равным сумме быстродействий ядер, хорошо бы подошел для задач обоих типов. Но с этим не уверен, что все согласятся

То-то и оно, что потенциальный. Если мы научились делать одно ядро в 80 раз быстрее, то мы вскоре сможем сделать 80-ядерник из таких в 80 раз более быстрых. Проблема же в том, что закон Мура вроде закончился. А быстродействия дополнительного хочется

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

HB>>А, ну так это, ИМХО, довольно общее место — то, что многоядерные системы хорошо подходят для распараллеливаемых задач, и плохо — для нераспараллеливаемых. Вряд ли кто-то с этим не согласится.

PD>А вот потенциальный одноядерный с быстродействием, равным сумме быстродействий ядер, хорошо бы подошел для задач обоих типов. Но с этим не уверен, что все согласятся

А вот если построить из этих "потенциальных и сверх-быстрых" ядер многоядерную систему...

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

HB>А вот если построить из этих "потенциальных и сверх-быстрых" ядер многоядерную систему...

А вот если заменить эту многоядерную систему из "потенциальных и сверх-быстрых" на один "потенциальный и сверх-сверх-быстрый"

Предлагаю рекурсию прекратить

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

PD>Жить нам, конечно, с этими многоядерными монстрами придется, и проблемы решать — тоже. Но, похоже, многие из них не фундаментальные проблемы, а проблемы, которые на нас изготовители оборудования переложили.

Железо последние годы развивалось значительно быстрее софта, и просто дошло до своего предела. Теперь оно пошло в другую сторону — туда, где еще свободно.

PD>P.S. Лично мое мнение о многопоточности очень простое. Если по характеру алгоритма распараллеливания нет — не надо ее насильно туда совать. Если оно может быть, но можно обойтись без него — тоже лучше не надо. Вот только если обойтись нельзя, то есть алгоритм по своей сути параллельный — тогда да.

Моё мнение о многопоточности: it sucks. Лучшая многопоточность — это множество однопоточных алгоритмов, взаимодействующих между собой в небольшом и явно выделенном числе точек соприкосновения. Чем меньше точек соприкосновения, тем лучше. Множество потоков не проблема, проблема — их взаимодействие.

Взгляните даже на реальный мир: реальная параллельность есть только там, где нет точек соприкосновения. В противном случае части начинают ждать или тормозить друг друга, становясь одной большой последовательной системой. Это естественно по самой природе параллельности: если взаимодействие незначительно для работы двух систем, эти системы автоматически параллельны; если они взаимодействуют ограниченное число времени, но их подсистемы затем работают независимо, они параллельны большую часть времени.

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

И ещё, далеко не всем алгоритмам для приемлемой скорости работы нужно хотя бы 50% мощности современных ядер. Так что наличие непараллелящихся алгоритмов не есть аргумент в пользу одноядерности. Сколько компьютеров в мире заняты обсчитыванием графов размером 4 Гб? Остальные 99.9999% обсчитывают данные размером 100 Кб, которые даже непараллелящимся алгоритмом приемлемо быстро выполнятся на одном 200 Мгц-ядре.

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

D>То-то и оно, что потенциальный. Если мы научились делать одно ядро в 80 раз быстрее, то мы вскоре сможем сделать 80-ядерник из таких в 80 раз более быстрых. Проблема же в том, что закон Мура вроде закончился.

Видимо, да.

>А быстродействия дополнительного хочется

Хочется. Но будет оно за счет нашей головной боли.

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

>>А быстродействия дополнительного хочется

PD>Хочется. Но будет оно за счет нашей головной боли.

Зато того, кто придумает лучшие таблетки, ждёт большой кусок пирога

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Для системных программистов никакого перегиба развития нету. Ядро полноценной ОС и все прибамбасы к нему должны быть SMP-совместимы, потому в системном программировании тестирование на SMP было обязательно и в 90ые годы.

Возможно разработчики ОС. Некоторых. Windows — нет.
Разработчики драйверов — нет.
Разработчики tcp-стеков и web-серверов — нет.


MSS>Только вот нити используются не только для задействования всех CPU, но и для той же отвязки от ожидания на вводе-выводе, к примеру.

Это отдельный разговор. Тут всё определяется тем, что и как предоставляет ОС. Windows, например, предоставляет очень хорошее API — IOCP. Linux — NBIO и AIO.


MSS>Мутексы должны быть "маленькими", под ними должны исполняться очень короткие пути кода.

Вот про это и я говорю. Подход "многопоточности на одном ядре". Короткие, не короткие, а пенальти в 500 тактов будь добр заплати. И насыщение шины когерентности кэшей.


MSS>Пачкание кэша — далеко не единственная причина тормозов на MT, есть еще и инверсии приоритетов, и голодания, и прочие радости.

Благодаря использованию хороших алгоритмов, меня, к счастью, такие проблемы не касаются

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

Кё>Железо последние годы развивалось значительно быстрее софта, и просто дошло до своего предела. Теперь оно пошло в другую сторону — туда, где еще свободно.

+1!

Кё>Моё мнение о многопоточности: it sucks.

Как и в случае с демократией, "это лучшее из того, что мы имеем на сей момент" (к)

Кё>Лучшая многопоточность — это множество однопоточных алгоритмов, взаимодействующих между собой в небольшом и явно выделенном числе точек соприкосновения. Чем меньше точек соприкосновения, тем лучше. Множество потоков не проблема, проблема — их взаимодействие.

+1!

Кё>Взгляните даже на реальный мир: реальная параллельность есть только там, где нет точек соприкосновения. В противном случае части начинают ждать или тормозить друг друга, становясь одной большой последовательной системой. Это естественно по самой природе параллельности: если взаимодействие незначительно для работы двух систем, эти системы автоматически параллельны; если они взаимодействуют ограниченное число времени, но их подсистемы затем работают независимо, они параллельны большую часть времени.

Реальный мир это уже прошел — равно аналогичный (имхо) этап развития в производстве: какое-то время тому назад всякий предмет делал один человек — ремесленник. Да, подмастерья были — банально потому что удобнее делать многие технологические операции "в четыре руки". Но потом данная технология производства совершенствовалась и достигла своего предела: один мастер просто физически не может делать больше. Выход напрашивается сам собой: посадить кучу мастеров и пусть они делают сразу много предметов — каждый свой — параллельно. А есть еще один, который был реализован исторически в современном промышленном производстве: разбить процесс производства предмета на отдельные составляющие и посадить кучу людей делать каждую отдельную составляющую, но параллельно — конвейер называется. Да, для реализации такого нужна дополнительная работа: разработка технологического процесса (читай: алгоритма?), подходящего для работы на конвейере. Для "железного", "материального" мира этот вопрос успешно решен.

Но тут действительно есть еще один вопрос...

Кё>И ещё, далеко не всем алгоритмам для приемлемой скорости работы нужно хотя бы 50% мощности современных ядер. Так что наличие непараллелящихся алгоритмов не есть аргумент в пользу одноядерности. Сколько компьютеров в мире заняты обсчитыванием графов размером 4 Гб? Остальные 99.9999% обсчитывают данные размером 100 Кб, которые даже непараллелящимся алгоритмом приемлемо быстро выполнятся на одном 200 Мгц-ядре.

Вот-вот. Однако же подобный "спор" я помню еще со времен классического "ни одной программе не понадобится более 640 килобайт ОЗУ" (к) (по памяти — возможно переврал), а потом еще один такой же этап на переходе с 16 бит разрядности на 32: "32 бита могут понадобиться лишь каким-то крайне требовательным к ресурсами приложениям, вроде СУБД и прочих, а рядовые вполне обойдуть 16-ю..." Но как-то вот сейчас по гигабайту памяти — обычный объем — а вопрос "почему я не могу 4 ГБ?" тоже перешел в разряд "боянов" — значит таки нужны?

Какие вообще исторические двигатели ИТ-прогресса произвотельности ПК имели место быть и есть сейчас? Игры. Сейчас — видео высокой четкости. Что еще?

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

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

PD>Как-то все думал, стоит ли говорить то, что скажу. Нестандартно это очень...

PD>А не кажется ли вам, господа, что многопоточность (а точнее, многоядерность) — не от хорошей жизни. Иными словами, это перекладывание проблем с аппаратуры на программистов ?

Именно так и есть!


>>Во второй половине следующего года Intel намерена выпустить процессор с 16 аппаратными потокамию. И через 5 лет они собираются выпустить процессор с 80 ядрами! (Представть свои программы на 80 ядрах! Есть идеи как их использовать?)

PD>А зададимся-ка таким вопросом. Представьте себе. что через 5 лет будет выпущен одноядерный процессор с быстродействием в 80 раз больше нынешнего. Вы его предпочтете или это многоядерное чудовище ?

К сожалению, мы перед таким выбором не стоим...



PD>Как видите, хоть и незначительное, но все же большинство предпочитает одноядерный процессор паре двухядерных с той же суммарной частотой. И это неудивительно — про распараллеливание много сказано, а попробуйте обратную задачу решить — заставить один поток исполняться на двух процессорах, дабы полностью использовать мощность компьютера. Именно так — на остальные процессы наплевать, им ничего не дадим (насколько сможем), а вот этому процессу — всю мощь PC. А он однопоточный по характеру самого алгоритма. Ну и как ?

Так же как и алгоритму, который упирается в пропускную способность памяти, или в пропускную способность сети. Они все не будут использовать процессор на полную мощность.



PD>Иными словами, не сумев решить задачу повышения быстродействия одного ядра, разработчики процессоров пошли по экстенсивному пути, начав наращивать число ядер. Возникающие проблемы при этом перекладываются на программистов, пусть они решают.

Так и есть.

PD>Я уж не говорю о том. что при этом применяются решения, которые совсем не очевидны. Тут много о кэше памяти говорилось. А ведь кэш-память — это кэш ОП, а не процессора. И быть ей надо бы ИМХО именно кэш-памятью на самой ОП, а не у каждого процессора, тогда бы и проблем с синхронизацией кэша не было бы. Если процессор == поток, то получаем кэш у потока, вместо того, чтобы иметь его у процесса, отсюда и все проблемы. Но сделать иначе — технически невозможно, а точнее, не заложено в архитектуру.


кэш-памятью на самой ОП — бессмысленно. ОП — и есть свой кэш.



PD>Жить нам, конечно, с этими многоядерными монстрами придется, и проблемы решать — тоже. Но, похоже, многие из них не фундаментальные проблемы, а проблемы, которые на нас изготовители оборудования переложили.

Так же как и IOCP, интерфейс которого переложили на нас изготовители ОС. Так же как и MMX/SSE/SSE2/SSE3/SSE4, которое на нас переложили изготовители процессора. И т.д. и т.п.


PD>P.S. Лично мое мнение о многопоточности очень простое. Если по характеру алгоритма распараллеливания нет — не надо ее насильно туда совать. Если оно может быть, но можно обойтись без него — тоже лучше не надо. Вот только если обойтись нельзя, то есть алгоритм по своей сути параллельный — тогда да.

Например, всё серверное ПО замечательно распараллеливается — на уровне транзацкий сам бог велел распараллеливать.
Что такое "по своей сути" — сложно сказать...

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

R>кэш-памятью на самой ОП — бессмысленно. ОП — и есть свой кэш.

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



R>Например, всё серверное ПО замечательно распараллеливается — на уровне транзацкий сам бог велел распараллеливать.

+1

R>Что такое "по своей сути" — сложно сказать...

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

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

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

R>>кэш-памятью на самой ОП — бессмысленно. ОП — и есть свой кэш.

PD>Я имел в виду, что та кэш-память, которая сейчас у процессора (и у каждого своя, откуда проблемы ее синхронизации), должна быть одной на все процессоры. Аналогично тому, что все потоки процесса иимеют программно-реализованный кэш (к примеру, данных из БД ), а не каждый поток имеет этот кэш.

Это не возможно, т.к. во-первых, всё равно нужна будет синхронизация при работе с этим кэшем. Ты же защищаешь мьютексом свой кэш, который общий на все потоки. Т.е. возвращаемся туда, откуда вышли. Во-вторых, кэш *обязан* быть близко к процессору, в этом его первостипенное предназначение. А как разместить общий кэш близко ко всем ядрам — не понятно.
В принципе, кэш второго уровня зачастую как раз и делают разделяемым между всеми ядрами. Но кэш первого уровня остаётся приватным для ядра.



R>>Что такое "по своей сути" — сложно сказать...

PD>Что такое компьютер — тоже сложно сказать , но когда мы его видим перед собой, мы сразу понимаем, что это он. Дать определение нераспараллеливаемому алгоритму я так сразу не берусь, но для конкретного алгоритма порой вполне ясно, что распараллелить его можно только с помощью грубой силы. Итерационные алгоритмы, к примеру...

А чем "грубая сила" плоха? Взяли матрицу и подели по строкам (по столбцам, по блокам, в шахматном порядке), и рассчитываем параллельно.
Итерационный — это алгоритм, а в конечном итоге нам всегда надо решить задачу, а не алгоритм. А у задачи может быть несколько алгоритмов решения. Например, есть алгоритмы сортировки, наиболее оптимальные для последовательного вычисления, но при распараллеливании обычно берут немного более плохой с т.з. вычислительной сложности алгоритм, но который зато легко и "естественно" разделяется на независимые подзадачи.

Кстати, если интересно, пример *задачи*, которая не поддаётся распараллеливанию (текущими математическими методами) — посчитать:
(2^(2^t)) (mod n*p)
где n и p — произвольные большие простые числа, t — произвольное число
(т.н. MIT LCS35 Time Capsule Crypto-Puzzle)

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

R>Ключевое слово, по которому надо искать — work stealing.
R>Так же ищи — Cilk, Java Fork/Join, C# TPL, Intel TBB. Как это ни удивительно, но все эти вещи используют идентичный механизм.

Неважно, когда нужно будет агрегировать результаты обработки частей — без разделяемой памяти все равно не обойтись.
Кстати, а когда TPL обещают в публичном доступе, неизвестно?

R>Если *всё*, что надо сделать твоей программе — это обработать 100 элементов, то я не думаю, что у тебя есть проблемы вообще.

Это просто упрощенный пример.

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

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

R>>Ключевое слово, по которому надо искать — work stealing.
R>>Так же ищи — Cilk, Java Fork/Join, C# TPL, Intel TBB. Как это ни удивительно, но все эти вещи используют идентичный механизм.

AF>Неважно, когда нужно будет агрегировать результаты обработки частей — без разделяемой памяти все равно не обойтись.

Агрегации либо вообще не бывает. Например, параллельная обработка транзакций на сервере, обработка изображений строго по частям.
Либо она на порядок меньше "основной работы". Например, "досортировка" массива. "Складывание" изображения из слоёв.


AF>Кстати, а когда TPL обещают в публичном доступе, неизвестно?

Вместе с .NET 4.0 видимо...



R>>Если *всё*, что надо сделать твоей программе — это обработать 100 элементов, то я не думаю, что у тебя есть проблемы вообще.

AF>Это просто упрощенный пример.

Значит, он не адекватный...

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

R>Либо она на порядок меньше "основной работы". Например, "досортировка" массива. "Складывание" изображения из слоёв.

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

R>Значит, он не адекватный...

Почему?

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

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

R>>Либо она на порядок меньше "основной работы". Например, "досортировка" массива. "Складывание" изображения из слоёв.

AF>Это если обработка каждой из частей занимает много времени. А если части маленькие, то все будет наоборот — накладные расходы будут на порядок больше выигрыша от распараллеливания.

При распараллеливании гранулярность должна быть не fine-grained, не coarse-grained, а right-grained

R>>Значит, он не адекватный...

AF>Почему?

Потому что предполагает тривиальное решение...