Здравствуйте, Gaperton, Вы писали:
G>Фундаментальная истина, не поспоришь, особенно для процов x86 . Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль.
А если не работают?
Подумай о nccNUMA
Sapienti sat!
Re: Immutable data structures are the way of the future in C
Здравствуйте, nikov, Вы писали:
N>Eric Lippert, один из разработчиков C#, пишет в своем блоге.
N>
N>Immutable data structures are the way of the future in C#.
Типа Америку открыл, блин... И пример у него надуманный. Вот вполне реальная задачка: есть два потока, один пишет данные в очередь, другой их изымает из этой очереди. Запросто все делается без синхронизаций, и по нашим замерам получали итоговое ускорение более чем в 5 раз.
Re[13]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
G>>Фундаментальная истина, не поспоришь, особенно для процов x86 . Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль. C>А если не работают?
Ну, кстати, я оказался не совсем прав. Картину несколько портят раздельные кэша L1 для каждого из ядер — в них надо убить значения счетчика. Вторая проблема — в разделяемом кэше L2 у нас данные хранятся широкими строками. Все это — источник тормозов. Вот как оно на самом деле:
Xbox 360 Performance
The performance of synchronization instructions and functions on Xbox 360 will vary depending on what other code is running. Acquiring locks will take much longer if another thread currently owns the lock. InterlockedIncrement and critical section operations will take much longer if other threads are writing to the same cache line. The contents of the store queues can also affect performance. Therefore, all of these numbers are just approximations, generated from very simple tests:
lwsync was measured as taking 33-48 cycles.
InterlockedIncrement was measured as taking 225-260 cycles. (казалось бы, медленно, но дело в том, что в PowerPC на это уходит три инструкции, и в этот момент проц не простаивает, а моментально переключается на другой аппаратный тред, так что на практике все хорошо)
Acquiring or releasing a critical section was measured as taking about 345 cycles.
Acquiring or releasing a mutex was measured as taking about 2350 cycles.
Windows Performance
The performance of synchronization instructions and functions on Windows vary widely depending on the processor type and configuration, and on what other code is running. Multi-core and multi-socket systems often take longer to execute synchronizing instructions. Acquiring locks take much longer if another thread currently owns the lock. However, even some measurements generated from very simple tests are helpful:
MemoryBarrier was measured as taking 20-90 cycles. InterlockedIncrement was measured as taking 36-90 cycles. (Wintel рулит! Реально быстрый интерлокед инеремент, на который наложатся следующие инструкции, так как Core Duo — суперскалярный проц)
Acquiring or releasing a critical section was measured as taking 40-100 cycles.
Acquiring or releasing a mutex was measured as taking about 750-2500 cycles.
C>Подумай о nccNUMA
Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру.
Кстати, о неблокирющих структурах и микро-параллелизме на С++. Программерам на С++ ничего руками делать не надо. Все укадено до нас. http://threadingbuildingblocks.org/
Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. http://www.devx.com/go-parallel/Article/34951
Re[14]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
C>>Подумай о nccNUMA G>Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру.
Ну... Если посмотреть под определенным углом и Cell можно считать nccNUMA. И вообще, я тебе гарантирую, что nccNUMA обязательно будет — так как барьеры и полная когенертность кэшей будет непомерно дорогой на процессорах с 80 ядрами.
Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах
G>Кстати, о неблокирющих структурах и микро-параллелизме на С++. Программерам на С++ ничего руками делать не надо. Все укадено до нас. G>http://threadingbuildingblocks.org/ G>Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор.
Аллокатор там отстойный HOARD лучше, смотрел я TBB уже. Вообще, в Java есть подобный аналог (в стандартной библиотеке с JDK1.5) — набор классов в java.util.concurrent.
Sapienti sat!
Re[14]: Immutable data structures are the way of the future
> http://threadingbuildingblocks.org/ > Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. > http://www.devx.com/go-parallel/Article/34951
А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re[15]: Immutable data structures are the way of the future
Здравствуйте, Sergey, Вы писали: S>А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать.
Ну, вообще народ говорит, что шансов на дальнейшее расслабление модели не так уж и много. В следующей версии CLR планируют ужесточить модель памяти, т.к. в настоящем виде она слишком relaxed и требует, вообще говоря, параноидального стиля программирования.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Immutable data structures are the way of the future i
Ты то ли плохо понимашь чем отличаются неизменяемые струтуры данных от полного не использования состояния в программах, то ли не понимаешь, что наличие неизменяемых струтур не отменяет наличие изменяемых.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Immutable data structures are the way of the future
> S>А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать. > Ну, вообще народ говорит, что шансов на дальнейшее расслабление модели не так уж и много.
А что за народ, из интел или из амд?
> В следующей версии CLR планируют ужесточить модель памяти, т.к. в настоящем виде она слишком relaxed и требует, вообще говоря, параноидального стиля программирования.
А CLR то тут причем? Мы ж конкретно за Intel® Threading Building Blocks перетираем.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re[15]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
C>>>Подумай о nccNUMA G>>Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру. C>Ну... Если посмотреть под определенным углом и Cell можно считать nccNUMA. И вообще, я тебе гарантирую, что nccNUMA обязательно будет — так как барьеры и полная когенертность кэшей будет непомерно дорогой на процессорах с 80 ядрами.
Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. Каждый отдельный поток протормозит, но вместе они нагрузят одно ядро на процентов 70-80. При поддержке аппаратной многопоточности вполне реально сделать объединенный кэш L2 — пусть он будет высоколатентный — это не важно, с латентностью и задержками эффективно борется аппаратная многопоточность.
Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
C>Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах
Зачем так делать, если можно увеличить количество аппаратных потоков, и сделать высоколатентный, но централизованный кэш L2.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
C>>>Подумай о nccNUMA G>>Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру. C>Ну... Если посмотреть под определенным углом и Cell можно считать nccNUMA. И вообще, я тебе гарантирую, что nccNUMA обязательно будет — так как барьеры и полная когенертность кэшей будет непомерно дорогой на процессорах с 80 ядрами.
Кроме того. Если ты глянешь на архитектуру UltraSPARC T1 (а это первый из сильно многоядерных процов), то можно обратить внимание, что он не выполняет переупорядочивания записей (из-за которого возникает недетский геморрой и тормоза при синхронизации). Total Store Order там — это кроме прочего еще и снижает количество требуемых инструкций для синхронизации. И один кэш L2 на 8 ядер, зацепленный за коммутатор кроссбар. Это все в сумме означает мегадешевый interlocked increment (он из-за Relaxed Store Order такой дорогой у intel и ibm, собственно), и удешевление остальных примитивов синхронизации.
UltraSPARC T1 has two varieties of instructions for synchronization: memory
barriers and flush. The following memory barrier instructions ensure that any load,
store, or atomic memory operation issued after it take effect after all memory
operations issued before it:
■ MEMBAR with mmask{1} = 1 (MEMBAR #StoreLoad)
■ MEMBAR with cmask{1} = 1 (MEMBAR #MemIssue)
■ MEMBAR with cmask{2} = 1 MEMBAR #Sync)
All other types of membar instructions are treated as NOPs, since they are implied
by the TSO memory ordering protocol followed by UltraSPARC T1.
Кроме того, он выполняет переключение потока при синхронизации, накладывая на нее выполнение другого потока — о чем я и говорил. Поэтому задержка на синхронизации вобще не важна — throughput процессорного ядра она не уменьшит.
Multithreading
In UltraSPARC T1, execution is switched in round-robin fashion every cycle among
the strands that are ready to issue another instruction. Context switching is built into
the UltraSPARC T1 pipeline and takes place during the SWITCH stage, thus contexts
are switched each cycle with no pipeline stall penalty.
The following instructions change a strand from a ready-to-issue state to a not-
ready-to-issue state, until hardware determines that their input/execution
requirements can be satisfied:
■ All branches (including CALL, JMPL, etc.)
■ All VIS instructions
■ All floating point (FPops)
■ All WRPR, WR, WRHPR
■ All RDPR, RD, RDHPR
■ SAVE(D), RESTORE(D), RETURN, FLUSHW (all register management)
■ All MUL and DIV
■ MULSCC
■ MEMBAR #Sync, MEMBAR #StoreLoad, MEMBAR #MemIssue
■ FLUSH
■ All loads
■ All floating-point memory operations
■ All memory operations to alternate space
■ All atomics load-store operations
■ Prefetch
Здравствуйте, Sergey, Вы писали:
>> http://threadingbuildingblocks.org/ >> Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. >> http://www.devx.com/go-parallel/Article/34951
S>А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать.
Не окажется. Должно быть нормально. Эта либа, кстати, портирована и на PowerPC. На AMD она, естественно, тоже работает.
И как правильно говорит товарищ Синклер, в будущем, при росте количества ядер, модель памяти будет скорее строже, чем наоборот. В Ниагаре сановской вообще TSO.
Re[4]: Immutable data structures are the way of the future i
VD>Случаем — нет.
VD>Ты то ли плохо понимашь чем отличаются неизменяемые струтуры данных от полного не использования состояния в программах, то ли не понимаешь, что наличие неизменяемых струтур не отменяет наличие изменяемых.
Э-э-э... Это сложно как-то очень. Это типа как "пчелы против меда" штоли?
Здравствуйте, Gaperton, Вы писали:
G>Кроме того. Если ты глянешь на архитектуру UltraSPARC T1 (а это первый из сильно многоядерных процов), то можно обратить внимание, что он не выполняет переупорядочивания записей (из-за которого возникает недетский геморрой и тормоза при синхронизации). Total Store Order там — это кроме прочего еще и снижает количество требуемых инструкций для синхронизации. И один кэш L2 на 8 ядер, зацепленный за коммутатор кроссбар. Это все в сумме означает мегадешевый interlocked increment (он из-за Relaxed Store Order такой дорогой у intel и ibm, собственно), и удешевление остальных примитивов синхронизации.
Так вот только сами по себе ядра в SPARC'ах никогда особым быстродейтвием не отличались. Для массивно-параллельных задач типа жуткого сервера с кучей потоков — оно рулит, но вот матетематика с числодробилками на нем часто сосет.
Я сейчас как раз работаю (удаленно) с машинкой с UltraSparc T1 (на днях должны UltraSparc T2 привезти — жду с нетерпением). Сервера на нем вообще просто великолепно работают, а та же перекомпиляция ядра — медленнее, чем на моей скромной домашней Core 2 Duo машине.
G>Кроме того, он выполняет переключение потока при синхронизации, накладывая на нее выполнение другого потока — о чем я и говорил. Поэтому задержка на синхронизации вобще не важна — throughput процессорного ядра она не уменьшит.
Ну это сказки — на практике будет cache thrashing, уже наблюдали такое с HyperThreading. Хотя как оптимизация — действительно работает неплохо.
G>Именно таким образом будут выглядеть процы ближайшего будущего, дружище. Вот оно, будущее. Все просто, и никаких извратов. G>http://opensparc-t1.sunsource.net/specs/UST1-UASuppl-current-draft-HP-EXT.pdf
Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться.
Sapienti sat!
Re[16]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. Каждый отдельный поток протормозит, но вместе они нагрузят одно ядро на процентов 70-80. При поддержке аппаратной многопоточности вполне реально сделать объединенный кэш L2 — пусть он будет высоколатентный — это не важно, с латентностью и задержками эффективно борется аппаратная многопоточность.
Только вот куча задач у нас реально однопоточна — поэтому жуткие замедления на синхронизации будут убивать производительность. А если выкидывать все примитивы синхронизации — то тогда получаем и полную невозможность использовать многопоточность.
Причем, это не теория — а вполне себе реальная практика с HyperThreading'овыми CPU. Там как раз та же ситуация, но по другой причине — длинный pipeline делал синхронизацию очень дорогой, и в качестве метода борьбы использовали переключение потоков. В результате, очень часто получали ЗАМЕДЛЕНИЕ вместо ускорения.
G>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
Ок, против моей любимой валюты — отсканированых $100
C>>Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах G>Зачем так делать, если можно увеличить количество аппаратных потоков, и сделать высоколатентный, но централизованный кэш L2.
См. выше.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
G>>Именно таким образом будут выглядеть процы ближайшего будущего, дружище. Вот оно, будущее. Все просто, и никаких извратов. G>>http://opensparc-t1.sunsource.net/specs/UST1-UASuppl-current-draft-HP-EXT.pdf C>Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться.
Здравствуйте, Курилка, Вы писали:
C>>Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться. К>Было бы интересно посмотреть пдфку http://crtc.wm.edu/paper/eorm07.pdf и еще одна есть, сейчас постараюсь найти.
Sapienti sat!
Re[16]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток.
Погоди, тут я чего-то не понимаю. Мы говорим про thread context switch или про что?
Переключение потока, вроде бы, тоже не сахар. Поскольку у потока как минимум свой стек, переключение нарушит локальность и с высокой вероятностью приведет к сбросу кэша. А это опять сбегать в основную память.
G>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу.
Чего-то я фундаментально не понимаю.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[17]: Immutable data structures are the way of the future
Здравствуйте, Sinclair, Вы писали:
G>>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. S>Погоди, тут я чего-то не понимаю. Мы говорим про thread context switch или про что?
Ага.
S>Переключение потока, вроде бы, тоже не сахар. Поскольку у потока как минимум свой стек, переключение нарушит локальность и с высокой вероятностью приведет к сбросу кэша. А это опять сбегать в основную память.
Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался.
Sapienti sat!
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали: C>Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался.
8-0 Это как? У нас в системе живет несколько тысяч (если не десятков тысяч) потоков. Сколько-сколько кэшей мы собираемся создать???
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[19]: Immutable data structures are the way of the future
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Cyberax, Вы писали: C>>Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался. S>8-0 Это как? У нас в системе живет несколько тысяч (если не десятков тысяч) потоков. Сколько-сколько кэшей мы собираемся создать???
Два на одно вычислительное ядро Для ОС одно физическое ядро будет видно как два логических CPU.
. Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль.
Это типа как "пчелы против меда" штоли?
