Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я имел в виду, что та кэш-память, которая сейчас у процессора (и у каждого своя, откуда проблемы ее синхронизации), должна быть одной на все процессоры. Аналогично тому, что все потоки процесса иимеют программно-реализованный кэш (к примеру, данных из БД ), а не каждый поток имеет этот кэш.
Эдак мы то совместных регистров дойдем. Иначе их придется синхронизировать между процессорами.
Здравствуйте, Andrei F., Вы писали:
AF>Здравствуйте, remark, Вы писали:
R>>
R>>При распараллеливании гранулярность должна быть не fine-grained, не coarse-grained, а right-grained
AF>right-grained — это понятие растяжимое, и очень зависит от величины накладных расходов
Так точно!
R>>Потому что предполагает тривиальное решение...
AF>Не понял мысли.
На таком примере нельзя ничего показать, и нельзя ничему научиться, т.к. я могу просто выдать ответ "делай всё в одном потоке", и это будет наилучшее решение для данной задачи. При приведении примеров надо отбрасывать второстипенные детали, а не существенные...
Здравствуйте, remark, Вы писали:
R>На таком примере нельзя ничего показать, и нельзя ничему научиться, т.к. я могу просто выдать ответ "делай всё в одном потоке", и это будет наилучшее решение для данной задачи. При приведении примеров надо отбрасывать второстипенные детали, а не существенные...
Ладно, давай тогда по другому. Это я правильно понял, что операция записи в разделяемую ячейку памяти стоит порядка 500-1000 тактов простоя, причем для каждого ядра, у которого в кэше загружена линия с этой ячейкой памяти?
Здравствуйте, Andrei F., Вы писали:
AF>Здравствуйте, remark, Вы писали:
R>>На таком примере нельзя ничего показать, и нельзя ничему научиться, т.к. я могу просто выдать ответ "делай всё в одном потоке", и это будет наилучшее решение для данной задачи. При приведении примеров надо отбрасывать второстипенные детали, а не существенные...
AF>Ладно, давай тогда по другому. Это я правильно понял, что операция записи в разделяемую ячейку памяти стоит порядка 500-1000 тактов простоя, причем для каждого ядра, у которого в кэше загружена линия с этой ячейкой памяти?
Ну не всё так плохо
Я думаю, ситуация всё же немного лучше. Но во-первых, надо понимать, что цифры в некоторой степени референсные. Во-вторых, цифры могут сильно зависеть от модели процессора (Pentium 4 vs Pentium Core), не говоря о производителе (Intel vs AMD).
По моим представлениям примерно так: захват/освобождение мьютекса стоит примерно 500 тактов. На Intel x86. При условии, что память, в которой расположен мьютекс находится в кэше другого ядра. Если память уже находится в кэше текущего ядра и другое ядро не пытается захватить мьютекс, то это может быть 200 тактов. Если это ещё спин-мьютекс, то это может быть 100 тактов.
То, что это пенальти для всех ядер, скорее мне кажется, что нет. Т.е. пенальти только для текущего ядра. Т.к. кэши и протокол когерентности работает асинхронно с вычислительным ядром. Хотя может наступить конкуренция или насыщение шины когерентности, тогда скорее всего будет неявное пенальти и для других ядер.
Но опять же, всё это достаточно сложно и архитектурно-зависимо. Поэтому единственный более-менее реалистичный способ судить об этом, это — просто измерять.
Если говорить о записе в разделяемую память. Тут зависит от состояния, в котором находится кэш линия (Modified, Owner, Shared, Invalidated). В хорошем случае это просто запись в кэш, т.е. несколько тактов. В плохом случае — 150-350 тактов. (Опять же это всё относится к Intel x86)
Здравствуйте, Кодёнок, Вы писали:
Кё>>>Сортировку вставками или пузырьком нельзя.
Зато сортировка Бэтчера (см. Кнут, том 3) — отлично параллелится. Многие исполнения внешней сортировки — тоже.
Кстати, почему это пузырёк по-Вашему не параллелится? При надлежащей синхронизации (следующая волна не может обогнать предыдущую) — полная;) параллельность (хотя у Бэтчера всё равно лучше).
Кё>>> Многие алгоритмы на графе нельзя. I>>Значит на многоядерных процессорах будут использоваться те алгоритмы, которые распараллелить можно. Кё>Не раньше чем появится «Исскусство программирования» для параллельного программирования :)
конечно, не Кнут, но основные подходы и теоретические зацепки есть. Это включая и плотносвязанные подходы вроде общей памяти, и обратные им — на сообщениях.
А кому надо чего-то менее современного — пусть читает Хоара:)
Кё> Проблема в том, что десятки ядер — уже здесь, а истинное (тру :) ) параллельное программирование — еще далеко-далеко «там». А то что сейчас под ним подразумевают (multithreading), на практике показывает немасштабируемость, даже на 8 ядер.
Я не думаю, что здесь народ настолько туп;), чтобы не заметить существование того же Erlang, у которого совсем не многопоточность и который освоит любое количество ядер (лишь бы работа была).
Вот промежуточных подходов практически нет, и это именно то, что вызывает резкий разрыв между двумя подходами. Или многонитевость на общей памяти — или полная независимость и обмен сообщениями (неважно, Erlang или MPI). Построения же в духе "вот тут 8 процессоров объединим на общей шине памяти, она может быть связана ещё с 15 такими же блоками, но уже через спецшины (получается NUMA), а такие блоки на 128 процессоров общаются между собой уже только сообщениями" — существуют только в узких нишах, снабжаемых 2-3 вендорами (типа Sun).
The God is real, unless declared integer.
Re[2]: Многопоточность сегодня - не от хорошей жизни
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А не кажется ли вам, господа, что многопоточность (а точнее, многоядерность) — не от хорошей жизни. Иными словами, это перекладывание проблем с аппаратуры на программистов ?
Какая альтернатива? Опровергнуть законы физики?
PD>Иными словами, не сумев решить задачу повышения быстродействия одного ядра, разработчики процессоров пошли по экстенсивному пути, начав наращивать число ядер. Возникающие проблемы при этом перекладываются на программистов, пусть они решают.
Только перекладывают проблемы не они. А те, кому нужна мощность несмотря на аппаратные проблемы.
The God is real, unless declared integer.
Re[7]: Многопоточность сегодня - не от хорошей жизни
Здравствуйте, deniok, Вы писали:
D>Проблема же в том, что закон Мура вроде закончился.
Закон Мура говорит об удвоении числа транзисторов на кристалле. О быстродействии он ничего не говорит.
Так что закон Мура будет еще действовать ближайшие 15-30 лет, пока современная технология производства чипов не упрется в физические пределы.
N>конечно, не Кнут, но основные подходы и теоретические зацепки есть. Это включая и плотносвязанные подходы вроде общей памяти, и обратные им — на сообщениях.
Вот именно, что *теоретические*. Очень много общих вещей, типа "Разделяемые данные нужно защищать критическими секциями бла-бла-бла бла-бла-бла ...". Материал в основном от второй половины 80 до второй половины 90.
Имхо, книга замечательно подходит для студента, который хочет вникнуть в тему. Но профессиональному разработчику, который хочет изучить что-то реальное, книга практически бесполезна...
Появилось бы что-нибудь с материалом хотя бы 2002-2004 годов...
Здравствуйте, Кодёнок, Вы писали:
Кё>Может ты хочешь невозможного — N ядер не могут дать N-кратного прироста скорости на взаимосвязанных процессах, предел скорости есть у всего.
Занятный момент — N ядер могут дать даже более чем N-кратный прирост скорости. Этот феномен называется Supra-linear scaling.
На 4-ёх ядерном процессоре авторы получили ускорение в 6,27 раза. Причём на вполне реалистичном приложении — сетевой сервер для фильтрации TCP соединений.
И в ряде других источников я встречался с упоминаниями этого феномена, правда с более скромными результатами (ссылки сейчас будет трудно найти).
Основная причина этого феномена — размер кэша первого и второго уровней. Если рабочий набор (и данных и команд) начинает не влезать в кэш первого уровня, то появляется скачкообразное падение производительности до 10-15 раз. И аналогично для не влезания в кэш второго уровня. На многоядерных процессорах кэши больше (пропорционально числу ядер), соотв. рабочий набор может начать влезать в кэш, в который он раньше не влезал. В этом и кроется причина Supra-linear scaling.
Хотя возможно тут есть и ещё какие-то менее очевидные факторы.
Конечно, цифра 6,27 достаточно большая, и, видимо, авторы, ну так скажем, создали благоприятные условия для проявления эффекта. На реальных приложениях такой цифры скорее всего добиться будет достаточно сложно. Однако, я думаю, что и можно создать искуственный пример, в котором добиться цифры 10.
MSS>>Для системных программистов никакого перегиба развития нету. Ядро полноценной ОС и все прибамбасы к нему должны быть SMP-совместимы, потому в системном программировании тестирование на SMP было обязательно и в 90ые годы.
R>Возможно разработчики ОС. Некоторых. Windows — нет.
SMP в Windows сделана полноценно с самого начала, в отличие от обоих популярных юниксов, где она была сделана как хак сбоку.
R>Разработчики драйверов — нет.
Разработчики драйверов — да.
R>Разработчики tcp-стеков и web-серверов — нет.
Разработчики tcp-стеков — да, web-серверов — нет, ибо в юзер моде нет разницы (кроме производительности в особо наворочанных местах) между многонитевостью на одном ядре и SMP.
R>Вот про это и я говорю. Подход "многопоточности на одном ядре". Короткие, не короткие, а пенальти в 500 тактов будь добр заплати. И насыщение шины когерентности кэшей.
500 тактов есть ерунда, например, для любой IO-bound задачи — IO все равно медленнее, да и послать IRP (и дождаться завершения) поболе 500 тактов стоит.
Что касается CPU-bound задач, то они как правило делятся на макро-операции, каждая из которых работает эдак с мегабайтом данных. Данные нарезаются на порции вот этого размера, потом на каждой порции бежит CPU-bound задача _уже без любых локов_. Снова 500 тактов — фигня по сравнению с переработкой мегабайта данных.
MSS>>Пачкание кэша — далеко не единственная причина тормозов на MT, есть еще и инверсии приоритетов, и голодания, и прочие радости.
R>Благодаря использованию хороших алгоритмов, меня, к счастью, такие проблемы не касаются
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>>>Для системных программистов никакого перегиба развития нету. Ядро полноценной ОС и все прибамбасы к нему должны быть SMP-совместимы, потому в системном программировании тестирование на SMP было обязательно и в 90ые годы.
R>>Возможно разработчики ОС. Некоторых. Windows — нет.
MSS>SMP в Windows сделана полноценно с самого начала, в отличие от обоих популярных юниксов, где она была сделана как хак сбоку.
Ну давай посмотрим.
Какие функции доступны с какой версии:
Обязательное условие сделать что-то стоящее — GetLogicalProcessorInformation() — Windows Vista or Windows XP Professional x64 Edition, Windows Server "Longhorn" or Windows Server 2003
Единственая возможность сделать что-то нормальное на NUMA и современных многоядерных процессорах — VirtualAllocExNuma() — Windows Vista, Windows Server "Longhorn"
Первый стоящий примитив синхронизации — InitializeSListHead() — Windows Vista or Windows XP, Windows Server "Longhorn" or Windows Server 2003
Второй стоящий примитив синхронизации — InitializeSRWLock() — Windows Vista, Windows Server "Longhorn".
Ну и так далее. Это говорит о том, когда они только *начали* задумываться об этом.
MSS>>>Пачкание кэша — далеко не единственная причина тормозов на MT, есть еще и инверсии приоритетов, и голодания, и прочие радости.
R>>Благодаря использованию хороших алгоритмов, меня, к счастью, такие проблемы не касаются
MSS>Я бы не зарекался вот именно вот тут.
Ну пожалуйста, не зарекайся.
Мои алгоритмы не подвержены инверсиям приоритетов, голоданиям, дедлокам и т.д.
MSS>>SMP в Windows сделана полноценно с самого начала, в отличие от обоих популярных юниксов, где она была сделана как хак сбоку.
R> R>Ну давай посмотрим.
А что там смотреть? код кернела изначально мог выполняться на многих процессорах, и для локинга всегда использовались fine-grained спинлоки (вплоть до того, что в каждом драйвере по нескольку), вместо одного могучего lock_kernel() в начале тела сисколла, как в линуксе.
Код кернела всегда был преемптивным, в отличие от почти всех юниксов, даже, кажется, от SunOS 5, которая ровесница Windows NT.
R>Какие функции доступны с какой версии: R>Обязательное условие сделать что-то стоящее — GetLogicalProcessorInformation() —
Да это просто пустяк. Все главное — см. выше.
R>Единственая возможность сделать что-то нормальное на NUMA и современных многоядерных процессорах — VirtualAllocExNuma() — Windows Vista, Windows Server "Longhorn"
При чем тут NUMA? мы про SMP, а не про NUMA.
NUMA да, совсем недавно стала поддерживаться вообще.
R>Первый стоящий примитив синхронизации — InitializeSListHead() — Windows Vista or Windows XP, Windows Server "Longhorn" or Windows Server 2003
Первые стоящие примитивы синхронизации — KeAcquireSpinLock, ExAcquireFastMutex, EnterCriticalSection — Windows NT 3.1
R>Ну и так далее. Это говорит о том, когда они только *начали* задумываться об этом.
В конце 80х и начали, сделав код ядра а) преемптивным б) способным выполняться на любом числе процессоров. Когда это в Линуксе появилось, к примеру? году в 2002?
Приведенные вами мелкие фенечки — это так, пустячки.
R>Ну пожалуйста, не зарекайся. R>Мои алгоритмы не подвержены инверсиям приоритетов, голоданиям, дедлокам и т.д.
Можно, я не поверю? в подфоруме по Си++ вы в коде "lock-free контейнера данных" сделали две смешные баги, говорящие о ваших навыках в многонитевом программировании.
Понимаете, человек, который допускает такое, не может быть авторитетом именно в данной предметной области, хотя может быть всячески достойным человеком и авторитетом в чем-то еще.
На этот скатывание во флейм можно остановить.
Занимайтесь LoveCraftом, а не WarCraftом!
Re[2]: Многопоточность сегодня - не от хорошей жизни
PD>А зададимся-ка таким вопросом. Представьте себе. что через 5 лет будет выпущен одноядерный процессор с быстродействием в 80 раз больше нынешнего. Вы его предпочтете или это многоядерное чудовище ?
Конечно же, однопроцессор лучше SMP при той же общей производительности. Лучше 1 процессор в 2 раза быстрее, чем SMP из двух.
Причин целый ряд: а) пачканье кэшей б) contention на общей шине в) выжимание максимума из SMP требует определенного программирования приложений, а максимум из однопроцессора выжмется и без этого.
Просто мощность однопроцессора ограничена технически (а когда около 2002 умер закон Мура, стало ясно, что и физикой тоже ограничена). Мощность же SMP может наращиваться примерно до 8 CPU на существующей технологической базе (у Сана были и 32процессорный СпаркЦентры, но они вроде как были NUMA).
Занимайтесь LoveCraftом, а не WarCraftом!
Re[3]: Многопоточность сегодня - не от хорошей жизни
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Просто мощность однопроцессора ограничена технически (а когда около 2002 умер закон Мура, стало ясно, что и физикой тоже ограничена). Мощность же SMP может наращиваться примерно до 8 CPU на существующей технологической базе (у Сана были и 32процессорный СпаркЦентры, но они вроде как были NUMA).
Не умер закон Мура!!
Hint: в нем ничего не сказано про тактовые частоты.
Sapienti sat!
Re[3]: Многопоточность сегодня - не от хорошей жизни
R>Например, всё серверное ПО замечательно распараллеливается — на уровне транзацкий сам бог велел распараллеливать.
...и даже на уровне микро-операций, из которых состоит транзакция — по крайней мере из них можно выделить IO bound и гонять CPU bound в параллель с IO bound.
Например, рендеринг трехмерной сцены. Экран режется на полосы по числу процессоров — и каждый процессор рендерит свое.
Вообще любые алгоритмы над независимыми друг от друга порциями данных легко параллелятся.
R>Что такое "по своей сути" — сложно сказать...
Занимайтесь LoveCraftом, а не WarCraftом!
Re[3]: Многопоточность сегодня - не от хорошей жизни
Кё>Моё мнение о многопоточности: it sucks. Лучшая многопоточность — это множество однопоточных алгоритмов, взаимодействующих между собой в небольшом и явно выделенном числе точек соприкосновения.
Именно так нормальную многопоточность и делают.
Кё>Взгляните даже на реальный мир: реальная параллельность есть только там, где нет точек соприкосновения. В противном случае части начинают ждать или тормозить друг друга, становясь одной большой последовательной системой.
Ага, и эти проблемы (голодания, инверсии приоритетов) — как правило, значительно хуже, чем то же загрязнение кэшей. Например, если CPU bound задача ждет завершения IO bound задачи, а процессор при этом стоит — то это может уменьшить общую производительность втрое. Загрязнение кэшей же... ну вряд ли втрое.
Про дедлоки я и не говорю — это просто баг. Обвинять в них многопоточность — это все равно что обвинять Windows в том, что при наличии на машине 30 наименований хренти какого софта она иногда показыает AV faults.
Кё>И ещё, далеко не всем алгоритмам для приемлемой скорости работы нужно хотя бы 50% мощности современных ядер. Так что наличие непараллелящихся алгоритмов не есть аргумент в пользу одноядерности. Сколько компьютеров в мире заняты обсчитыванием графов размером 4 Гб? Остальные 99.9999% обсчитывают данные размером 100 Кб, которые даже непараллелящимся алгоритмом приемлемо быстро выполнятся на одном 200 Мгц-ядре.
Ага. Значительная часть типовых современных задач прекрасно делается на компьютере 2000 года выпуска.
Занимайтесь LoveCraftом, а не WarCraftом!
Re[3]: Многопоточность сегодня - не от хорошей жизни
HB>Чего-то я запутался... Во-первых, занять одним потоком два процессора (если мы говорим о чем-то подобном threads в Windows) вроде как невозможно по определению. А если речь идет о процессе, а не о потоке, то это вроде и есть задача по распареллеливанию — замена "однопоточных" алгоритмов "многопоточными". Или я где-то ошибаюсь?
Забудьте о тредах. Это не более чем механизм ОС, предназначенный для задействования всех процессоров (а также для отвязки от блокирующего ожидания каких-то событий, IO completion в том числе).
Это не "железо".
А на уровне "железа" у нас вот что — исполнение задачи требует столько-то памяти, столько то операций ввода/вывода, и столько-то тактов процессора. И все равно, один это процессор или несколько.
Интересует — выполнить задачу быстрее. Число тактов процессора известно. Значит, есть только два выхода: а) повышать частоту б) поставить несколько независимых процессоров.
Так вот, подход б) хуже. Потому как процессора не есть 100% независимые, по чисто "железным" причинам. Потому как не все операции хорошо параллелятся. Скажем, компрессия фильма параллелится на ура — AVI файл все равно состоит из независимо закодированных фреймов (или групп фреймов), вот и выдать каждому процессору по фрейму, пусть кодирует. Но таковы не все задачи. Плохо параллелится то, где неизбежно есть крупные shared данные, для примера.
remark тут приводил в пример извратную ситуацию, когда 4 ядра дают выигрыш в 6 раз — но совершенно явно не мэйнстрим, и вообще похоже на интеловский маркетинг.
Правильный подход — это а).
Что же касается нитей, то они есть вспомогательная сущность, которая нужна для того, чтобы в рамках ОС задействовать процессор. Если процессор один — то просто отпадает нужда в нитях в некоторых случаев. Например, в предполагаемом компрессоре фильмов просто тупо компрессится кадр за кадром. Одной нитью (чтение и запись я оставляю за кадром). А на SMP надо будет — по нити на процессор (да еще и affinity раздать).
Занимайтесь LoveCraftом, а не WarCraftом!
Re[4]: Многопоточность сегодня - не от хорошей жизни
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>>>SMP в Windows сделана полноценно с самого начала, в отличие от обоих популярных юниксов, где она была сделана как хак сбоку.
R>> R>>Ну давай посмотрим.
MSS>А что там смотреть? код кернела изначально мог выполняться на многих процессорах, и для локинга всегда использовались fine-grained спинлоки (вплоть до того, что в каждом драйвере по нескольку), вместо одного могучего lock_kernel() в начале тела сисколла, как в линуксе.
MSS>Код кернела всегда был преемптивным, в отличие от почти всех юниксов, даже, кажется, от SunOS 5, которая ровесница Windows NT.
А ну если поддержкой многоядерности считать только возможность выполняться на нескольких аппаратных потоках и много локов, а не один. То пожалуйста. Я имел в виду, не теоритетическую возможность выполняться на нескольких аппаратных потоках, а *эффективную* работу.
R>>Первый стоящий примитив синхронизации — InitializeSListHead() — Windows Vista or Windows XP, Windows Server "Longhorn" or Windows Server 2003
MSS>Первые стоящие примитивы синхронизации — KeAcquireSpinLock, ExAcquireFastMutex, EnterCriticalSection — Windows NT 3.1
Этот треш из 70-ых годов меня не интересует. Хотя, да, он позволяет работать на нескольких аппаратных потоках.
R>>Ну пожалуйста, не зарекайся. R>>Мои алгоритмы не подвержены инверсиям приоритетов, голоданиям, дедлокам и т.д.
MSS>Можно, я не поверю? в подфоруме по Си++ вы в коде "lock-free контейнера данных" сделали две смешные баги, говорящие о ваших навыках в многонитевом программировании.
Я отвечу там.
MSS>Понимаете, человек, который допускает такое, не может быть авторитетом именно в данной предметной области, хотя может быть всячески достойным человеком и авторитетом в чем-то еще.
Автор(ы): Грегори Р. Эндрюс
