Нужна ли особая оптимизация под Core2Duo?
Попробовать icc.
Найти профайлером самые горячие места, и переписать на sse (там где это возможно).
Найти профайлером самые горячие места, и переписать на sse (там где это возможно).
Не надо ничего переписывать.
Надо положиться на оптимизатор. Если уж он не сможет соптимизировать, то с огромнейшей вероятностью и вручную не удастся.
Да, icc, скорее всего справится с задачей лучше чем любой другой.
Надо положиться на оптимизатор. Если уж он не сможет соптимизировать, то с огромнейшей вероятностью и вручную не удастся.
Да, icc, скорее всего справится с задачей лучше чем любой другой.
Почему именно icc?
чтобы на корке работало на 5% быстрее, а на атлонах вдвое медленее
Из своего опыта, как минимум. Писал код для обработки изображений. Потом замерял для icc, gcc и ms-овского (запускал как на интеловских, так и на амд-шных процах). icc всех делал, но все равно приемущество было маленьким. Правда это было два года назад, но не думаю, что что-то изменилось. Разве что остальные подтянулись к icc. Плюс, можно в инете бенчмарки нарыть наверняка.
спасибо
2Бишоп: мне по барабану, будет ли моя программа работать под атлонами и с какой скоростью. Она один раз запустится на коре, прогоняется на ней пару недель и больше никогда использоваться не будет. А если будет, я просто откомпилирую ее заново, попросив совета касательно оптимизации под атлон.
2Бишоп: мне по барабану, будет ли моя программа работать под атлонами и с какой скоростью. Она один раз запустится на коре, прогоняется на ней пару недель и больше никогда использоваться не будет. А если будет, я просто откомпилирую ее заново, попросив совета касательно оптимизации под атлон.
Разве что остальные подтянулись к icc.Есть мнение (и не только мое что gcc с каждой версией генерит все более медленный код. Не знаю, что там у микрософта.
И вообще говорить о преимуществе "в целом" - бесполезно. SIMD, если задача позволяет, в разы быстрее обычного кода. Поэтому, если icc зарюхает, он всех порвет. Если нет - пиши вручную и тоже всех порвешь.
что gcc с каждой версией генерит все более медленный код.не совсем правда, 4.0, конечно, медленее 3.3. Но 4.1 быстрее 4.0, а 4.2 быстрее 4.1
Из моего опыта измерения производительности на спеках, gcc в большинстве случаев просасывает просто жутко (в 1.2 - 1.5 раза) по сравнению с icc на ксеонах.
Да, кстати, распараллелить на 2 ядра очень не помешало бы. В принципе, если написано удачно, то icc с опцией -parallel сам все сделает.
> распараллелить на 2 ядра очень не помешало бы
достаточно ли просто разбить вычисления на два потока или требуется что-то специфичное именно для ядер?
достаточно ли просто разбить вычисления на два потока или требуется что-то специфичное именно для ядер?
Не, двух потоков достаточно будет. ОС сама догадается.
сенкс 
Да, кстати, распараллелить на 2 ядра очень не помешало бы.Ага, иначе загрузка будет процентов 50 всего. Это хорошо видно, когда в MSVS что-нибудь компилишь - если компилится только один проект, то загрузка 50, если одновременно два - то 100%.
Не, двух потоков достаточно будет.Гонево.
Надо положиться на оптимизатор. Если уж он не сможет соптимизировать, то с огромнейшей вероятностью и вручную не удастся.Классическое заблуждение тех, кто ни разу не программировал на ассемблере и не видел сгенерированного компилятором кода.
Аргументировать будем или оставим это как пустой набор слов, к тому же не имеющий ничего общего с реальностью?
ты сначала свою фразу аргументируй. тем более, что речь в треде вообще о конкретном проце.
Код не приведу, ибо далеко он и впадлу. И с учетом того, что прога будет юзаться один раз и проработает пару недель, время, которое надо будет затратить на ручную оптимизацию скорее всего окажется на несколько порядков больше, чем разница во времени выполнении оптимизированного icc и руками кода. Тривиальный код оптимизиатор сам разрюхает, а код, где куча всего понапихано, что оптимизатор не разберет, руками переписывать на асме, плюс отладка выйдет далеко не в тридцать минут.
А поконкретнее?
Контексты тредов не переносятся по межпроцессорному транспорту на десктопных системах без софтверных ухищрений.
ну это да, теперь согласен
> Контексты тредов не переносятся по межпроцессорному транспорту на десктопных системах без софтверных ухищрений.
А можешь раскрыть эту мысль - как это отражается на поведении многопоточной проги или какие нужны ухищрения? Потому что когда я делаю несколько независимых потоков, они отлично распределяются сами на несколько ядер и несколько процессоров, винда сама все делает. Проверял на Core2Duo и двухпроцессорной системе из двухядерных Оптеронов.
А можешь раскрыть эту мысль - как это отражается на поведении многопоточной проги или какие нужны ухищрения? Потому что когда я делаю несколько независимых потоков, они отлично распределяются сами на несколько ядер и несколько процессоров, винда сама все делает. Проверял на Core2Duo и двухпроцессорной системе из двухядерных Оптеронов.
А зачем C2D будет переносить контексты тредов, если память полностью разделяемая? На системах с неразделяемой памятью такая проблема может и есть.
Ты чото путаешь. Коре2дуо не является SMT-процессором.
SMT поддерживается четвертым пнём в виде хипер трединга, но только в районе одного едра.
SMT поддерживается четвертым пнём в виде хипер трединга, но только в районе одного едра.
с этим вопросом к интеловским архитекторам, а не ко мне
Ну что, кто прогонит тестик простой, чтобы развеять все сомнения?
#include <windows.h>
#include <process.h>
#include <iostream>
#define N 100000
unsigned __stdcall threadFunc ( void *args);
using namespace std;
int main ( )
{
int *m, i, j;
uintptr_t m_thread;
unsigned int m_id;
m = new int[ 2 * N];
m_thread = _beginthreadex( 0, 0, threadFunc, static_cast < void *>( m 0, &m_id);
for ( i = 0; i < N; i++)
{
for ( j = 0; j < N * 2; j++)
{
m[ i] += 2 * j - i;
}
}
WaitForSingleObject( reinterpret_cast < HANDLE >( m_thread INFINITE);
delete [] m;
return 0;
}
unsigned __stdcall threadFunc ( void *args)
{
int i, j;
int *m = static_cast < int* >( args);
for ( i = N; i < N * 2; i++)
{
for ( j = 0; j < N * 2; j++)
{
m[ i] += 2 * j - i;
}
}
return 0;
}
Реинтерпрет-касты жгут
Естественно 
тут по другому особо и не сделаешь
тут по другому особо и не сделаешь
По просьбам общественности изменил касты. Лучше бы потестили, как на коре работает.
То же самое для омп:
То же самое для омп:
#include <iostream>
#include <omp.h>
#define N 50000
using namespace std;
int main ( )
{
int *m, i, j;
uintptr_t m_thread;
unsigned int m_id;
m = new int[ 2 * N];
#pragma omp parallel for private (i, j)
for ( i = 0; i < N * 2; i++)
{
for ( j = 0; j < N * 2; j++)
{
m[ i] += 2 * j - i;
}
}
delete [] m;
return 0;
}
Посмотрел на QX6850 под VS2005.
Ну что, кто прогонит тестик простой, чтобы развеять все сомнения?
Время работы в один поток, в два, в четыре одинаково (ну может несколько процентов разница). Занимает соответственно 25, 50, 100% процессора.
PS (добавлено)
Имеется ввиду, что за то же время с помощью потоков сделано в 4 раза больше "работы".
Кстати, ни у кого не завалялось mpCC или xlC? Проверил бы на POWER5
Запустил в двух вариантах - исходном и однопоточном.
Процессор - Core 2 Duo T7200 2.00 GHz на ноуте.
Время работы однопоточного варианта - почти 59 секунд. Загрузка 50% (хотя вначале показывает 100).
Время работы двухпоточного варианта - 30 секунд, загрузка 100%.
http://stuff.thedeemon.com/1thread.png
http://stuff.thedeemon.com/2threads.png
, что я теперь напутал?
Процессор - Core 2 Duo T7200 2.00 GHz на ноуте.
Время работы однопоточного варианта - почти 59 секунд. Загрузка 50% (хотя вначале показывает 100).
Время работы двухпоточного варианта - 30 секунд, загрузка 100%.
http://stuff.thedeemon.com/1thread.png
http://stuff.thedeemon.com/2threads.png
, что я теперь напутал?
Ну я в общем то и не проверяя был уверен, что так и получится. Вот мне больше интересен "дополняющий" эффект, когда 100% загрузки 1 ядра расползается на 2. Каково его происхождение? Я так понимаю система регулярно переключает интерфейс потока с ядра на ядро для равномерного прогрева. На системе из двух двухядерных ксеонов под управлением CentOS однопоточная задача занимала 100% но переползала время от времени с одного ядра на другое.
, что я теперь напутал?Два раза процесс запустил?
тебя плющит
Несколько раз запускал с повторяемым результатом. Время работы прога выводит. Может, тебе на видео процесс снять?
>Я так понимаю система регулярно переключает интерфейс потока с ядра на ядро
это очень дорого
>для равномерного прогрева
бессмысленно
>На системе из двух двухядерных ксеонов под управлением CentOS однопоточная задача занимала 100% но переползала время от времени с одного ядра на другое.
откуда данные?
это очень дорого
>для равномерного прогрева
бессмысленно
>На системе из двух двухядерных ксеонов под управлением CentOS однопоточная задача занимала 100% но переползала время от времени с одного ядра на другое.
откуда данные?
>На системе из двух двухядерных ксеонов под управлением CentOS однопоточная задача занимала 100% но переползала время от времени с одного ядра на другое.о. может ты что-нибудь скажешь?
откуда данные?
по идее оно из этого следует. и blind там отмечал, что "изредка будут переключения между ядрами для равномерного нагрева".
Не понял, о каком нагреве идет речь, но тоже наблюдал переключения между процессорами на SMP. Редкие, раз в 5-10 секунд.
про нагрев — шутка наверное. =)
>>На системе из двух двухядерных ксеонов под управлением CentOS однопоточная задача занимала 100% но переползала время от времени с одного ядра на другое.
>откуда данные?
Данные типа "смотри".
>>Я так понимаю система регулярно переключает интерфейс потока с ядра на ядро
>это очень дорого
>>для равномерного прогрева
>бессмысленно
Возможно, поэтому мне и интересно объяснение этого эффекта.
>откуда данные?
Данные типа "смотри".
>>Я так понимаю система регулярно переключает интерфейс потока с ядра на ядро
>это очень дорого
>>для равномерного прогрева
>бессмысленно
Возможно, поэтому мне и интересно объяснение этого эффекта.
чето я ниче не понял вопрос
у прожорливого процесса (который расходует всё выделенное время) приоритет же ниже чем у интерактивных, то он буде выполняться после всех интерактивных задач и к тому времени ядро уже может посчитать, что задача не в кеше и смело её двинет, если возникла разбалансировка очередей. но это не будет происходить чаще чем 0.2с
раз в 5с это совсем мизерная плата за интерактивность, вытесняемость
думаю, что при загрузке всех ядер такая миграция будет происходить реже, чем одна задача на нескольких ядрах.
у прожорливого процесса (который расходует всё выделенное время) приоритет же ниже чем у интерактивных, то он буде выполняться после всех интерактивных задач и к тому времени ядро уже может посчитать, что задача не в кеше и смело её двинет, если возникла разбалансировка очередей. но это не будет происходить чаще чем 0.2с
раз в 5с это совсем мизерная плата за интерактивность, вытесняемость
думаю, что при загрузке всех ядер такая миграция будет происходить реже, чем одна задача на нескольких ядрах.
мне просто удивительно как однопоточное приложение может занимать 4 ядра. и что значит в этом случае значит "переползала время от времени с одного ядра на другое"
у прожорливого процесса (который расходует всё выделенное время) приоритет же ниже чем у интерактивных, то он буде выполняться после всех интерактивных задач и к тому времени ядро уже может посчитать, что задача не в кеше и смело её двинет, если возникла разбалансировка очередей. но это не будет происходить чаще чем 0.2ся предполагал, что интерактивные выполняет одно ядро, а прожорливые — другое.
и тогда из запощенных мной там условий выходит, что будут частые переключения.
а на деле — раз в 5 с.
думаю, что при загрузке всех ядер такая миграция будет происходить реже, чем одна задача на нескольких ядрах.ну это-то понятно, у меня вопрос скорее теоретический. =)
Она не занимала 4 ядра, но занимало 1 ядро на 100% иногда переключаясь между ядрами.
не, оно балансирует кол-во задач в очередях, с учётом того как они тратят время
дисбаланс это когда в одной очереди задач больше на 25% чем в другой
дисбаланс это когда в одной очереди задач больше на 25% чем в другой
ты абсолютно прав! я забыл про это.
теперь стало более-менее понятно.
теперь стало более-менее понятно.
Чувак, ты попутал.
Я сейчас почитал википедию, то, о чём ты говоришь (SMT в виде, например, HT (я, кстати, не знал, что оно так работает, спасибо в некотором смысле относится к исполнению разных тредов на одном ядре. Способность делать SMT ортогональна способности исполнять разные треды на разных ядрах или процессорах. Я ничуть не удивлён, что второе реализуется вне зависимости от наличия первого. Память-то uniform accessible, причём с точки зрения процессора разницы между процессом и тредом как бы нет (ну, типа).
Я сейчас почитал википедию, то, о чём ты говоришь (SMT в виде, например, HT (я, кстати, не знал, что оно так работает, спасибо в некотором смысле относится к исполнению разных тредов на одном ядре. Способность делать SMT ортогональна способности исполнять разные треды на разных ядрах или процессорах. Я ничуть не удивлён, что второе реализуется вне зависимости от наличия первого. Память-то uniform accessible, причём с точки зрения процессора разницы между процессом и тредом как бы нет (ну, типа).
По ходу, ты прав.
Мы тоже поботали и выяснили, что работа нескольких потоков на разных процессорах понижает эффективность кэша, но, в принципе, возможна. Хотя это и не подтверждает правоту высказывания, что, дескать, "достаточно просто двух потоков".
А вот те софтверные ухищрения, о которых я говорил.
Мы тоже поботали и выяснили, что работа нескольких потоков на разных процессорах понижает эффективность кэша, но, в принципе, возможна. Хотя это и не подтверждает правоту высказывания, что, дескать, "достаточно просто двух потоков".
А вот те софтверные ухищрения, о которых я говорил.
Чем тебя мой пример не устроил? Чего недостает?
На висте шедулер новый походу, похоже на кэш тупо зобили
Примерчег соображу как-нить, наверное.
Примерчег соображу как-нить, наверное.
Это ухищрение позволяет ПРИНУДИТЕЛЬНО исполнять потоки на желаемых ядрах, хоть оба на одном, хоть на разных. Читай что написано:
Setting an affinity mask for a process or thread can result in threads receiving less processor time, as the system is restricted from running the threads on certain processors. In most cases, it is better to let the system select an available processor.
If the new thread affinity mask does not specify the processor that is currently running the thread, the thread is rescheduled on one of the allowable processors.
>На висте шедулер новый походу
На XP наблюдал такое же точно поведение.
Edit: ..для двух потоков. Один поток сидел на одном и том же ядре, а не растекался по двум как в висте.
На XP наблюдал такое же точно поведение.
Edit: ..для двух потоков. Один поток сидел на одном и том же ядре, а не растекался по двум как в висте.
Память-то uniform accessible, причём с точки зрения процессора разницы между процессом и тредом как бы нет (ну, типаНу вот, советую почитать на досуге - http://en.wikipedia.org/wiki/Cache_coherency
Если воспринимать изначальный вопрос автора как "достаточно ли тупо создать два треда, чтоб на 100% загрузить кор2дуо", то ответ "да" исчерпывающ.
Если его воспринмать как "нужно ли заботиться при многопоточном программировании о чем то, кроме создания двух тредов", то вот тут уже надо принимать как минимум во внимание ссылку про когерентность кешей, что привел , и еще пачку других вещей.
Из-за разницы этих двух воприятий и ко и не понимают 'а.
В любом случае, 'а продолжает плющить.
Ибо проблема когерентности кешей - не единственная проблема, возникающая при переходе на мультитрединговое программирование.
И решение этих проблем никогда не возлагалось на скедулер, ни в ХР, ни в Виста. Выполнять все треды, которые могут затронуть одни и те же данные исключительно на одном процессоре(судя по ссылке на SetThreadAffinityMаsk что ты привел, предлагается именно это) - не решение, а выливание воды из чайника.
Достаточно подумать, как организована например процессорно нагруженная реляционная БД.
Она малтитредовая, ее треды живут на всех доступных системе процессорах (думаю, в этом сомнений нет).
То есть потенциально у нее куча вышеобозначенных проблем. И они все там как-то решаются.
Если его воспринмать как "нужно ли заботиться при многопоточном программировании о чем то, кроме создания двух тредов", то вот тут уже надо принимать как минимум во внимание ссылку про когерентность кешей, что привел , и еще пачку других вещей.
Из-за разницы этих двух воприятий и ко и не понимают 'а.
В любом случае, 'а продолжает плющить.
Ибо проблема когерентности кешей - не единственная проблема, возникающая при переходе на мультитрединговое программирование.
И решение этих проблем никогда не возлагалось на скедулер, ни в ХР, ни в Виста. Выполнять все треды, которые могут затронуть одни и те же данные исключительно на одном процессоре(судя по ссылке на SetThreadAffinityMаsk что ты привел, предлагается именно это) - не решение, а выливание воды из чайника.
Достаточно подумать, как организована например процессорно нагруженная реляционная БД.
Она малтитредовая, ее треды живут на всех доступных системе процессорах (думаю, в этом сомнений нет).
То есть потенциально у нее куча вышеобозначенных проблем. И они все там как-то решаются.
Если его воспринмать как "нужно ли заботиться при многопоточном программировании о чем то, кроме создания двух тредов", то вот тут уже надо принимать как минимум во внимание ссылку про когерентность кешей, что привел , и еще пачку других вещей.
Когерентность кэшей и пр. заморочки хардварного уровня программиста как раз касаться не должны, как и где оно реализовано это черный ящик.
А вопрос стоял такой:
достаточно ли просто разбить вычисления на два потока или требуется что-то специфичное именно для ядер?Такая постановка вопроса имхо гораздо ближе к первой формулировке, чем ко второй. Про синхронизацию потоков речь тут не шла.
Когерентность кэшей и пр. заморочки хардварного уровня программиста как раз касаться не должны, как и где оно реализовано это черный ящик.Проблема в том, что когерентности кешей в процессорах как раз нет, и заботиться о ее сохранении тебе придется руками, в коде.
Насколько просто будет проходить эта "забота" - вопрос конкретного яп.
А должны эти заморочки там или не должны касаться программиста - вопрос пока исключительно философский.
А как же бедные кэши будут писать в одну ячейку памяти, если такая оказия случится?
Проблема в том, что когерентности кешей в процессорах как раз нетТы что?! Как раз есть. Или поясни, что ты имеешь в виду.
> А как же бедные кэши будут писать в одну ячейку памяти, если такая оказия случится?
для этого вообще-то критические секции используются вместе с WriteBarrier-ом
для этого вообще-то критические секции используются вместе с WriteBarrier-ом
WriteBarrierЭто что, такая функция в виндах ? В известных мне реализациях wb делается внутрях мьютексов, локов и т.д. и программисту он в целом не интересен.
Внутри процессора?
Внутри процессора?Критические секции ?
о том и речь, что на большинстве задач ставят локи/семафоры и не парятся с кэшами
и только в редких случаях, заморачиваются на write barrier
ps
и в винде, и в *nix-е
и только в редких случаях, заморачиваются на write barrier
ps
и в винде, и в *nix-е
> Внутри процессора?
внутри кода.
или о чем сейчас идет речь?
внутри кода.
или о чем сейчас идет речь?
Не стоял лок на ресурсе, 2 потока захотели записать в одну ячейку. Процессор скажет фу и откажется работать? Или все же такие коллизии разрешает на хардварном уровне?
Чочо?
Последний раз, когда я употребил выражение "абортивный материал в моих интернетах" я оказался дико неправ и мне было стыдно. Но вы тут все такую хуйню написали, что я прям даже не могу представить, как я могу ошибаться с её интерпретацией.
SetAffininityMask, как было справедливо замечено выше, не является необходимым условием перекидывания тредов на другие процессоры. Более того, это низкоуровневый хак, оверрайдящий нормальное поведение ОС, и использовать его надлежит с опаской.
Многопроцессорные системы сами поддерживают когерентность кешей. Всегда. Правильно написанное многотредовое приложение всегда исполняется так, как если бы оно исполнялось на одном процессоре. Нет, бывают специфические исключительные случаи, когда хардварь мануфакчуреры делают деструктивную оптимизацию, например, самомодифицирующийся код на современных процах должен в явном виде ресетить instruction cache, но это редкие случаи и данный к ним не относится.
Рекомендую всем потратить часов эдак восемь личного времени на прочтение http://people.redhat.com/drepper/cpumemory.pdf (What every programmer should know about memory от главного чувака из редхата)
Теперь наиболее поразившее меня утверждение (хотя я даже не знаю, утверждение о том, что процессоры не поддерживают когерентность, тоже меня убило, хотя и по-другому , солнышко, ты ж знаешь, наверное, слова MergeSort, HeapSort и QuickSort? А ты слышал, что HeapSort дико клёвый, но используется только в тех случаях, когда квиксорт явно целится в квадратичное время? А знаешь, почему? Потому что, блджад, по данным чувака из редхата на топовых позапрошлогодних процессорах обращение к памяти жрало 240 тактов, а обращение к L1 кэшу — 3 (три). При этом если ты подряд читаешь память, но на обработку очередной cache line (64 байта обычно) тратишь больше 240 тактов, то обращение к следующей порции памяти тебе выдают со стопроцентной скидкой, то есть бесплатно, потому что префетч. Это, если ты вдруг забыл арифметику, получается менее четырёх тактов на байт, что не так уж мало. А если ты ещё и возвращаешься обратно периодически, то большой L2 кэш существенно уменьшает твои шансы хоть когда-нибудь встретиться с реальной латентностью памяти (а она с тех пор нифига не уменьшилась, в отличие от возросших тактовых частот и числа ядер).
Это для тебя, как для программиста, означает буквально следующее: если ты сортируешь двадцатимегабайтный массив квиксортом или мерджсортом, то кэш тебя любит, поэтому затраты на сравнение двух элементов (а также обмен етс) пропорциональны числу 3. А если ты вдруг решаешь посортировать тот же массив HeapSort'ом, который выносит все мыслимые и немыслимые кэши сразу, то у тебя те же затраты пропорциональны числу 240. Поэтому производительность двух программ, написанных с использованием квиксорта и хипсорта, будет отличаться в восемьдесят раз. То есть меньше, конечно, там ведь ещё и другие действия производятся (хотя и им от постоянного рефреша кэша очень плохо так что я бы уверенно поставил на двадцать раз или больше.
Ты понимаешь, что такое "в 20 раз медленнее"? Ты готов сказать, что это неважно, но при этом считаешь себя программистом? Ты готов сказать то же самое и о затратах на межпроцессорную синхронизацию кэшей (которая весьма сложна сама по себе и в случае write-write дефолтится на запись текущей линии в память и далее обращении напрямую к памяти без использования кэша whatsoever пока конфликт не разрешится)?
Последний раз, когда я употребил выражение "абортивный материал в моих интернетах" я оказался дико неправ и мне было стыдно. Но вы тут все такую хуйню написали, что я прям даже не могу представить, как я могу ошибаться с её интерпретацией.
SetAffininityMask, как было справедливо замечено выше, не является необходимым условием перекидывания тредов на другие процессоры. Более того, это низкоуровневый хак, оверрайдящий нормальное поведение ОС, и использовать его надлежит с опаской.
Многопроцессорные системы сами поддерживают когерентность кешей. Всегда. Правильно написанное многотредовое приложение всегда исполняется так, как если бы оно исполнялось на одном процессоре. Нет, бывают специфические исключительные случаи, когда хардварь мануфакчуреры делают деструктивную оптимизацию, например, самомодифицирующийся код на современных процах должен в явном виде ресетить instruction cache, но это редкие случаи и данный к ним не относится.
Рекомендую всем потратить часов эдак восемь личного времени на прочтение http://people.redhat.com/drepper/cpumemory.pdf (What every programmer should know about memory от главного чувака из редхата)
Теперь наиболее поразившее меня утверждение (хотя я даже не знаю, утверждение о том, что процессоры не поддерживают когерентность, тоже меня убило, хотя и по-другому , солнышко, ты ж знаешь, наверное, слова MergeSort, HeapSort и QuickSort? А ты слышал, что HeapSort дико клёвый, но используется только в тех случаях, когда квиксорт явно целится в квадратичное время? А знаешь, почему? Потому что, блджад, по данным чувака из редхата на топовых позапрошлогодних процессорах обращение к памяти жрало 240 тактов, а обращение к L1 кэшу — 3 (три). При этом если ты подряд читаешь память, но на обработку очередной cache line (64 байта обычно) тратишь больше 240 тактов, то обращение к следующей порции памяти тебе выдают со стопроцентной скидкой, то есть бесплатно, потому что префетч. Это, если ты вдруг забыл арифметику, получается менее четырёх тактов на байт, что не так уж мало. А если ты ещё и возвращаешься обратно периодически, то большой L2 кэш существенно уменьшает твои шансы хоть когда-нибудь встретиться с реальной латентностью памяти (а она с тех пор нифига не уменьшилась, в отличие от возросших тактовых частот и числа ядер).
Это для тебя, как для программиста, означает буквально следующее: если ты сортируешь двадцатимегабайтный массив квиксортом или мерджсортом, то кэш тебя любит, поэтому затраты на сравнение двух элементов (а также обмен етс) пропорциональны числу 3. А если ты вдруг решаешь посортировать тот же массив HeapSort'ом, который выносит все мыслимые и немыслимые кэши сразу, то у тебя те же затраты пропорциональны числу 240. Поэтому производительность двух программ, написанных с использованием квиксорта и хипсорта, будет отличаться в восемьдесят раз. То есть меньше, конечно, там ведь ещё и другие действия производятся (хотя и им от постоянного рефреша кэша очень плохо так что я бы уверенно поставил на двадцать раз или больше.
Ты понимаешь, что такое "в 20 раз медленнее"? Ты готов сказать, что это неважно, но при этом считаешь себя программистом? Ты готов сказать то же самое и о затратах на межпроцессорную синхронизацию кэшей (которая весьма сложна сама по себе и в случае write-write дефолтится на запись текущей линии в память и далее обращении напрямую к памяти без использования кэша whatsoever пока конфликт не разрешится)?
На практике, heap-sort работает не так уж медленно. Построение исходного дерева - O(n) и не убивает хэш на верхних уровнях дерева (на нижних убивает, но они уже не такие большие). Далее на каждый элемент приходится O(ln(кэш операций с кэш-попаданием (нижние уровни дерева) и O(ln(n)-ln(кэш операций с кэш-промахом(верхние уровни дерева). ln(n) редко значительно превосходит ln(кэш поэтому все не так плохо.
радость моя, как тут уже было замечено, это глубокий философский вопрос. Я раскрою свою идею поподробнее.
Расскажи мне, когда ты пишешь свою программу, и перед тобой встает вопрос какую сортировку выбрать, думаешь ли ты как движется каждый электрон в процессоре, как отрабатывает каждый из нескольких миллионов транзисторов в нем, как при запросе чтения по адресу процессор просматривает L1 кэш, L2 кэш, не находит там нужного значения и, всплакнув, выкладывает нужный адрес на шину с запросом на чтение, как контроллер памяти шлет этот запрос к памяти, как сигнал бежит по проводочкам, выбирается нужный банк памяти, как срабатывают транзисторы, разряжая конденсаторы, как заново записывается значение по адресу, как это значение отсылается обратно контроллеру, это не считая задержек, которые делает память для ожидания стабильного уровня сигнала и т. д.
Нет? Странно, но из этого как раз и складывается знание о том что на все про все уйдет 240 тактов. Так вскрывая слой за слоем хардварного представления можно узнать, почему происходит так, а не иначе. Почему же ты остановился на уровне принципов работы кэша и не пошел копать глубже? Ты посчитал что здесь остановится достаточно. Я с тем же успехом остановился на софтварном слое.
К чему это я? Все к тому, что для того чтобы использовать следствие не обязательно знать причину. Нет-нет, несомненно знать причину очень полезно и увлекательно, но с тем же успехом можно начать читать википедию от корки до корки. Где-то надо остановиться.
Дык вот, выбор метода сортировки ты будешь делать на основании "используется только в тех случаях, когда квиксорт явно целится в квадратичное время". Это можно сделать на основании этого утверждения не вдаваясь глубже в причины утверждения. И я уверен, что ты используешь именно это знание при выборе метода, не вспоминая как при этом будут вести кэши и прочие хардварные элементы. Dixi.
PS Кстати, на почти упорядоченных массивах HeapSort не такой уж замечательный.
Расскажи мне, когда ты пишешь свою программу, и перед тобой встает вопрос какую сортировку выбрать, думаешь ли ты как движется каждый электрон в процессоре, как отрабатывает каждый из нескольких миллионов транзисторов в нем, как при запросе чтения по адресу процессор просматривает L1 кэш, L2 кэш, не находит там нужного значения и, всплакнув, выкладывает нужный адрес на шину с запросом на чтение, как контроллер памяти шлет этот запрос к памяти, как сигнал бежит по проводочкам, выбирается нужный банк памяти, как срабатывают транзисторы, разряжая конденсаторы, как заново записывается значение по адресу, как это значение отсылается обратно контроллеру, это не считая задержек, которые делает память для ожидания стабильного уровня сигнала и т. д.
Нет? Странно, но из этого как раз и складывается знание о том что на все про все уйдет 240 тактов. Так вскрывая слой за слоем хардварного представления можно узнать, почему происходит так, а не иначе. Почему же ты остановился на уровне принципов работы кэша и не пошел копать глубже? Ты посчитал что здесь остановится достаточно. Я с тем же успехом остановился на софтварном слое.
К чему это я? Все к тому, что для того чтобы использовать следствие не обязательно знать причину. Нет-нет, несомненно знать причину очень полезно и увлекательно, но с тем же успехом можно начать читать википедию от корки до корки. Где-то надо остановиться.
Дык вот, выбор метода сортировки ты будешь делать на основании "используется только в тех случаях, когда квиксорт явно целится в квадратичное время". Это можно сделать на основании этого утверждения не вдаваясь глубже в причины утверждения. И я уверен, что ты используешь именно это знание при выборе метода, не вспоминая как при этом будут вести кэши и прочие хардварные элементы. Dixi.
PS Кстати, на почти упорядоченных массивах HeapSort не такой уж замечательный.
Разумеется, доказав один раз, что 2+2=4, не нужно передаказывать это снова каждый раз, когда это потребуется. При разработке же нового алгоритма лично я о кэше и ассемблере вспоминаю довольно часто.
Ты писал:
Если ты заводишь структурку из двух интов, причём первый тред постоянно читает и пишет первый инт, а второй — второй, то каждая запись/чтение будет не только пролетать мимо кэша, но и вызывать неслабые дополнительные затраты. У меня под рукой нет двухпроцессорной системы, чтобы проверить, но по-моему так. Причём в таком случае ты ещё сразу увидишь, что что-то пошло не так, а если, например, ты выделяешь кусочки памяти маллоком, то попадать в одну и ту же линию они будут случайно и непредсказуемо, причём поведение программы начнёт зависеть от кучи разных причин.
И вот ЭТО программиста должно касаться наиболее непосредственным образом. В самом деле, он собирается параллелить прогу под два процессора надеясь всего лишь на двукратное ускорение, ему эта константа "2" важна, его именно она волнует, а не асимптотика какая-нибудь. Было бы, наверное, очень грустно наблюдать, как после распараллеливания производительность программы наоборот падает раз в десять, не правда ли?
Когерентность кэшей и пр. заморочки хардварного уровня программиста как раз касаться не должны, как и где оно реализовано это черный ящик.Я, естественно, не требую в ответе на вопрос детально разбирать протокол поддержки когерентности кэшей. Это действительно программиста касаться не должно. Вполне достаточно некоего высокоуровнего представления о принципах работы Чёрного Ящика. Сформулированного, например, так: треды должны писать и читать разную память, желательно действительно разную, то есть находящуюся в физически разделённых участках (а чтобы гарантировать это, было бы неплохо выделять память специальными АПИ, помечать глобальные переменные специальными директивами етс).
А вопрос стоял такой:
достаточно ли просто разбить вычисления на два потока или требуется что-то специфичное именно для ядер?
Если ты заводишь структурку из двух интов, причём первый тред постоянно читает и пишет первый инт, а второй — второй, то каждая запись/чтение будет не только пролетать мимо кэша, но и вызывать неслабые дополнительные затраты. У меня под рукой нет двухпроцессорной системы, чтобы проверить, но по-моему так. Причём в таком случае ты ещё сразу увидишь, что что-то пошло не так, а если, например, ты выделяешь кусочки памяти маллоком, то попадать в одну и ту же линию они будут случайно и непредсказуемо, причём поведение программы начнёт зависеть от кучи разных причин.
И вот ЭТО программиста должно касаться наиболее непосредственным образом. В самом деле, он собирается параллелить прогу под два процессора надеясь всего лишь на двукратное ускорение, ему эта константа "2" важна, его именно она волнует, а не асимптотика какая-нибудь. Было бы, наверное, очень грустно наблюдать, как после распараллеливания производительность программы наоборот падает раз в десять, не правда ли?
Сформулированного, например, так: треды должны писать и читать разную память, желательно действительно разную, то есть находящуюся в физически разделённых участках (а чтобы гарантировать это, было бы неплохо выделять память специальными АПИ, помечать глобальные переменные специальными директивами етс).
Вот вот вот, об этом я и говорю. Важно знать что хорошо и что плохо, почему же так, знать хорошо, но необязательно. Ты в общем то и подтвердил эту идею своими примерами. В принципе теоритически не совсем ясно, что будет происходить в твоих примерах, знание принципов работы кэша не дает прямых ответов на эти вопросы, но при этом ты знаешь, что так делать не хорошо.
Если ты заводишь структурку из двух интов, причём первый тред постоянно читает и пишет первый инт, а второй — второй, то каждая запись/чтение будет не только пролетать мимо кэша, но и вызывать неслабые дополнительные затраты.А ты сейчас про какой кэш?
Просто L2 у Core2 один на оба ядра.
по моему мнению лучшая оптимизация это впервую очередь разделить программу на различные потоки
вычислительная задача, вещественные числа. Что бы сделать, чтобы получить максимум преимуществ проца? Как программить, как оптимизировать компиляцию?
Она один раз запустится на коре, прогоняется на ней пару недель и больше никогда использоваться не будет.На фиг тогда тебе её оптимизировать ? Один фиг ты в разы скорость не увеличишь, тогда зачем заморачиваться оптимизацией ?
Чукча не читатель?
Ты бы сначала тред осилил, умник, прежде чем такие комментарии писать.
Ты бы сначала тред осилил, умник, прежде чем такие комментарии писать.
Раз уж тред подняли, попробую реабилитироваться после нового года =)
В своем посте, где я говорил про некогерентность кешей в процессоре, я действительно облажался. На самом деле я имел ввиду не L1\L2, а более высокоуровневые "кеши".
Например, в джаве в JSL'е для переменных есть понятие уровня visibility. Смысл в том, что в джаве, по дефолту, при изменении значения переменной одним потоком совсем не гарантируется, что это изменение сразу одновременно увидят все остальные потоки.
Почему так происходит - то ли это из-за того что компилятор "скешировал" переменную в регистре, то ли из-за того что компилятор реордерит инструкции, то ли еще чего - не говорится.
Эта проблема решается простым способом, который описывается в любой книжке по малтитред программингу: обязательно синхронизируйте те переменные к которым возможен одновременный доступ, старайтесь писать программы так, чтобы таких переменных было как можно меньше, ибо синхронизация есть медленно.
Этот совет автоматичекси покрывает проблему с RFO оверхедами в процессорных кешах. Так что в данном случае проблема не только и не столько в кешах.
В той статье, что слинковал Фиджей, кстати, не очень много говорится про параллельное программирование. Есть где-то в середине 6 главы по конкарренси, и связанный с ним RFO оверхед. Но никаких новых советов по исправлению ситуации не дается.
Более того, там приводятся измерения RFO оверхеда для Core 2 Quad проца, из которых видно, что этот оверхед не растет с увеличением кол-ва тредов, а держится на константном уровне. То есть в этом конкретном треде про эту проблему вообще можно было не заводить разговор ;-)
Еще в статье ведется разговор про атомарные операции типа компэр-энд-сет, но исключительно на уровне - глядите какие клевые.
Плюс бэндвиз, мол если у вас много кешей, и они шарятся между ядрами, то потоки скедулить надо особым образом, что опять же не есть наш случай (у нас один l2 кеш).
Кстати, сама статья действительно интересная, было очень интересно посмотреть на многочисленные бенчмарки. За это Фиджею отдельное спасибо =)
Правда, в качестве пособия по эффективному мультитредовому программингу, особенно для новичка, статья мало пригодна.
В своем посте, где я говорил про некогерентность кешей в процессоре, я действительно облажался. На самом деле я имел ввиду не L1\L2, а более высокоуровневые "кеши".
Например, в джаве в JSL'е для переменных есть понятие уровня visibility. Смысл в том, что в джаве, по дефолту, при изменении значения переменной одним потоком совсем не гарантируется, что это изменение сразу одновременно увидят все остальные потоки.
Почему так происходит - то ли это из-за того что компилятор "скешировал" переменную в регистре, то ли из-за того что компилятор реордерит инструкции, то ли еще чего - не говорится.
Эта проблема решается простым способом, который описывается в любой книжке по малтитред программингу: обязательно синхронизируйте те переменные к которым возможен одновременный доступ, старайтесь писать программы так, чтобы таких переменных было как можно меньше, ибо синхронизация есть медленно.
Этот совет автоматичекси покрывает проблему с RFO оверхедами в процессорных кешах. Так что в данном случае проблема не только и не столько в кешах.
В той статье, что слинковал Фиджей, кстати, не очень много говорится про параллельное программирование. Есть где-то в середине 6 главы по конкарренси, и связанный с ним RFO оверхед. Но никаких новых советов по исправлению ситуации не дается.
Более того, там приводятся измерения RFO оверхеда для Core 2 Quad проца, из которых видно, что этот оверхед не растет с увеличением кол-ва тредов, а держится на константном уровне. То есть в этом конкретном треде про эту проблему вообще можно было не заводить разговор ;-)
Еще в статье ведется разговор про атомарные операции типа компэр-энд-сет, но исключительно на уровне - глядите какие клевые.
Плюс бэндвиз, мол если у вас много кешей, и они шарятся между ядрами, то потоки скедулить надо особым образом, что опять же не есть наш случай (у нас один l2 кеш).
Кстати, сама статья действительно интересная, было очень интересно посмотреть на многочисленные бенчмарки. За это Фиджею отдельное спасибо =)
Правда, в качестве пособия по эффективному мультитредовому программингу, особенно для новичка, статья мало пригодна.
Оставить комментарий
mkrec
вычислительная задача, вещественные числа. Что бы сделать, чтобы получить максимум преимуществ проца? Как программить, как оптимизировать компиляцию?