Оказывание программы для конвейера в процессорах Intel Sandybridge

Я пробовал свой мозг в течение недели, пытаясь выполнить это задание, и я надеюсь, что кто-то может привести меня к правильному пути. Позвольте мне начать с инструкций инструктора:

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

Чтобы обезвредить программу, используйте свои знания о том, как работает конвейер Intel i7. Представьте себе способы переупорядочения инструкций для введения WAR, RAW и других опасностей. Подумайте о способах минимизации эффективности кеша. Будьте дьявольски некомпетентны.

В задании был выбран выбор программ Whetstone или Monte-Carlo. Комментарии к эффективности кэша в основном применимы только к Whetstone, но я выбрал программу моделирования Monte-Carlo:

// Un-modified baseline for pessimization, as given in the assignment #include  // Needed for the "max" function #include  #include  // A simple implementation of the Box-Muller algorithm, used to generate // gaussian random numbers - necessary for the Monte Carlo method below // Note that C++11 actually provides std::normal_distribution in // the  library, which can be used instead of this function double gaussian_box_muller() { double x = 0.0; double y = 0.0; double euclid_sq = 0.0; // Continue generating two uniform random variables // until the square of their "euclidean distance" // is less than unity do { x = 2.0 * rand() / static_cast(RAND_MAX)-1; y = 2.0 * rand() / static_cast(RAND_MAX)-1; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); return x*sqrt(-2*log(euclid_sq)/euclid_sq); } // Pricing a European vanilla call option with a Monte Carlo method double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) { double S_adjust = S * exp(T*(r-0.5*v*v)); double S_cur = 0.0; double payoff_sum = 0.0; for (int i=0; i<num_sims; i++) { double gauss_bm = gaussian_box_muller(); S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm); payoff_sum += std::max(S_cur - K, 0.0); } return (payoff_sum / static_cast(num_sims)) * exp(-r*T); } // Pricing a European vanilla put option with a Monte Carlo method double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) { double S_adjust = S * exp(T*(r-0.5*v*v)); double S_cur = 0.0; double payoff_sum = 0.0; for (int i=0; i<num_sims; i++) { double gauss_bm = gaussian_box_muller(); S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm); payoff_sum += std::max(K - S_cur, 0.0); } return (payoff_sum / static_cast(num_sims)) * exp(-r*T); } int main(int argc, char **argv) { // First we create the parameter list int num_sims = 10000000; // Number of simulated asset paths double S = 100.0; // Option price double K = 100.0; // Strike price double r = 0.05; // Risk-free rate (5%) double v = 0.2; // Volatility of the underlying (20%) double T = 1.0; // One year until expiry // Then we calculate the call/put values via Monte Carlo double call = monte_carlo_call_price(num_sims, S, K, r, v, T); double put = monte_carlo_put_price(num_sims, S, K, r, v, T); // Finally we output the parameters and prices std::cout << "Number of Paths: " << num_sims << std::endl; std::cout << "Underlying: " << S << std::endl; std::cout << "Strike: " << K << std::endl; std::cout << "Risk-Free Rate: " << r << std::endl; std::cout << "Volatility: " << v << std::endl; std::cout << "Maturity: " << T << std::endl; std::cout << "Call Price: " << call << std::endl; std::cout << "Put Price: " << put << std::endl; return 0; } 

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


Обновление: профессор, который дал это задание, разместил некоторые подробности

Основные моменты:

  • Это второй class архитектуры семестра в колледже (используя учебник Hennessy и Patterson).
  • компьютеры лаборатории имеют процессоры Haswell
  • Студенты были ознакомлены с инструкцией CPUID и как определить размер кеша, а также встроенные функции и инструкцию CLFLUSH .
  • любые параметры компилятора разрешены, а также встроенный asm.
  • Написание собственного алгоритма с квадратным корнем было объявлено как находящееся за пределами бледного

Комментарии Cowmoogun в мета-streamе указывают на то, что неясно, оптимизация компилятора может быть частью этого и предполагаемого -O0 , и что 17-процентное увеличение времени выполнения было разумным.

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


Имейте в виду, что это вопрос компьютерной архитектуры, а не вопрос о том, как сделать C ++ медленным в целом.

Важное справочное чтение: микроархант Agner Fog pdf , и, возможно, также « Каждый программист» Ульриха Дреппера должен знать о памяти . См. Также другие ссылки в вики-теге x86 , особенно руководства по оптимизации Intel, и анализ Дэвида Кантера по микроархитектуре Haswell с диаграммами .

Очень classное задание; намного лучше, чем те, которые я видел, когда ученикам предлагалось оптимизировать код для gcc -O0 , изучая кучу трюков, которые не имеют значения в реальном коде. В этом случае вас просят узнать о конвейере процессора и использовать его для управления вашими усилиями по оптимизации, а не только слепым угадыванием. Самая забавная часть этого – оправдывает каждую пессимизацию «дьявольской некомпетентностью», а не преднамеренной злобой.


Проблемы с формулировкой задания и кодом :

Уарх-специфические опции для этого кода ограничены. Он не использует никаких массивов, и большая часть затрат – это вызовы функций библиотеки exp / log . Нет очевидного способа иметь более или менее параллелизм на уровне инструкций, а цепочка зависимостей с петлей очень короткая.

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

Семейство процессоров Intel Sandybridge – это агрессивные конструкции вне порядка, которые проводят много транзисторов и обладают способностью находить параллелизм и избегать опасностей (зависимостей), которые могут помешать classическому конвейеру RISC по заказу . Обычно единственными традиционными опасностями, которые замедляют его, являются RAW «истинные» зависимости, которые ограничивают пропускную способность за счет латентности.

WAR и WAW опасности для регистров в значительной степени не являются проблемой, благодаря переименованию регистра . (за исключением popcnt / lzcnt / tzcnt , которые имеют ложную зависимость от своего места назначения на процессорах Intel , хотя это только запись, т. е. WAW обрабатывается как риск RAW + запись). Для упорядочения памяти современные процессоры используют очереди хранилищ для задержки фиксации в кэше до выхода на пенсию, а также избегают опасностей WAR и WAW .

Бренд «i7» был представлен с Nehalem (преемником Core2), а некоторые руководства Intel даже говорят «Core i7», когда они, похоже, означают Nehalem, но они сохранили бренд «i7» для Sandybridge и более поздних микроархитектур. SnB – это когда семейство P6 превратилось в новый вид семейства SnB . Во многих отношениях Nehalem имеет больше общего с Pentium III, чем с Sandybridge (например, регистрационные стойки для чтения и ROB-считывающие стойки не происходят на SnB, поскольку они были изменены на использование файла физического регистра. Также кэш uop и другой внутренний uop). Термин «архитектура i7» не полезен , поскольку нет смысла группировать SnB-семейство с Nehalem, но не Core2. (Однако Nehalem действительно представила общую общую архитектуру кэша L3 для одновременного соединения нескольких ядер, а также интегрированные графические процессоры. Таким образом, уровень чипа, именование имеет больше смысла.)


Резюме хороших идей, которые может привести к дьявольской некомпетентности

Даже дьявольски некомпетентные вряд ли добавят явно бесполезную работу или бесконечный цикл, а беспорядок с classами C ++ / Boost выходит за frameworks назначения.

  • Многопоточный stream с одним общим std::atomic счетчиком циклов, поэтому происходит полное общее число итераций. Atomic uint64_t особенно плохо работает с -m32 -march=i586 . Для бонусных очков устраивайте его смещение и пересечение границы страницы с неравномерным расщеплением (не 4: 4).
  • Ложное совместное использование для какой-либо другой неатомной переменной -> рассыпкой неверно-спекулятивного порядка памяти, а также лишние промахи в кэше.
  • Вместо того, чтобы использовать переменные FP, XOR – старший байт с 0x80, чтобы перевернуть знаковый бит, вызывая переадресацию магазина .
  • Время каждой итерации независимо, с чем-то даже более тяжелым, чем RDTSC . например CPUID / RDTSC или функция времени, которая выполняет системный вызов. Инструкции по сериализации по своей сути являются непрямыми для трубопроводов.
  • Изменять умножения на константы на деления на их взаимные («для удобства чтения»). div медленный и не полностью конвейерный.
  • Вектируйте multiply / sqrt с помощью AVX (SIMD), но не используйте vzeroupper перед вызовами vzeroupper скалярной математической библиотеки exp() и log() , вызывая переходы AVX <-> SSE .
  • Храните вывод RNG в связанном списке или в массивах, которые вы выходите из строя. То же самое для результата каждой итерации и суммы в конце.

Также рассматривается в этом ответе, но исключается из резюме: предложения, которые будут столь же медленными на не-конвейерном процессоре, или которые, похоже, не оправданы даже с дьявольской некомпетентностью. например, многие идеи gimp-компилятора, которые производят явно разные / худшие asm.


Многопоточная проблема

Может быть, использовать OpenMP для многопоточных циклов с очень небольшим количеством итераций, с большим количеством накладных расходов, чем увеличение скорости. У вашего кода monte-carlo достаточно параллелизма, чтобы фактически получить ускорение, тем не менее, особенно. если нам удастся сделать каждую итерацию медленной. (Каждый stream вычисляет частичный payoff_sum , добавленный в конце). #omp parallel в этом цикле, вероятно, будет оптимизацией, а не пессимизацией.

Многопоточность, но заставляют обе streamи использовать один и тот же счетчик циклов (с atomic приращениями, чтобы общее число итераций было правильным). Это кажется дьявольски логичным. Это означает использование static переменной в качестве счетчика циклов. Это оправдывает использование atomic счетчиков циклов и создает фактическое кэширование ping-ponging (пока streamи не будут работать на одном физическом ядре с гиперstreamом, это может быть не так медленно). Во всяком случае, это намного медленнее, чем непредвиденный случай для lock inc . И lock cmpxchg8b для атомарного приращения uint64_t в 32-битной системе придется повторять в цикле вместо того, чтобы аппаратное обеспечение арбитража атома inc .

Также создайте ложный общий доступ , где несколько streamов сохраняют свои личные данные (например, состояние RNG) в разных байтах одной и той же строки кэша. (Руководство Intel об этом, в том числе перфоманс, чтобы посмотреть) . Для этого характерен микроархитектурный аспект : процессоры Intel предполагают, что неправильное упорядочение памяти не происходит, и для обнаружения этого, по крайней мере, на P4, есть явное перфекционное устройство памяти . На Хасуэлла наказание может быть не таким большим. Как видно из этой ссылки, инструкция locked предполагает, что это произойдет, избегая неправильной спекуляции. Нормальная нагрузка предполагает, что другие ядра не будут лишать строку кэша недействительной между тем, когда выполняется загрузка, и когда она удаляется в программном порядке ( если вы не используете pause ). Истинное совместное использование без lock инструкций обычно является ошибкой. Было бы интересно сравнить неатомный счетчик общих циклов с атомным корпусом. Чтобы действительно пессимизировать, сохраняйте общий счетчик атомных циклов и вызывайте ложное совместное использование в той же или другой строке кэша для какой-либо другой переменной.


Случайные урч-специфические идеи:

Если вы можете ввести любые непредсказуемые ветви , это существенно повлияет на код. Современные процессоры x86 имеют довольно длинные конвейеры, поэтому неверный outlook стоит ~ 15 циклов (при запуске из кэша uop).


Цепи зависимостей:

Я думаю, что это была одна из целей части задания.

Поразите способность ЦП использовать параллелизм на уровне инструкций, выбирая порядок операций с одной длинной цепочкой зависимостей вместо нескольких коротких цепочек зависимостей. Компиляторам не разрешается изменять порядок операций для вычислений FP, если вы не используете -ffast-math , потому что это может изменить результаты (как обсуждается ниже).

Чтобы действительно сделать это эффективным, увеличьте длину цепи зависимостей, связанной с циклом. Однако ничто не бросается в глаза как очевидное: петли, как написано, имеют очень короткие петлевые цепи зависимостей: просто добавление FP. (3 цикла). Несколько итераций могут иметь свои вычисления в полете сразу, потому что они могут начинаться задолго до payoff_sum += в конце предыдущей итерации. ( log() и exp принимают множество инструкций, но не намного больше, чем окно отсутствия заказа Haswell для поиска параллелизма: ROB size = 192 fused-domain uops и размер планировщика = 60 unused-domain uops . Как только выполнение текущей итерации продвигается достаточно далеко, чтобы освободить место для инструкций от следующей итерации для выпуска, любые ее части, у которых есть готовые входы (то есть независимая / отдельная цепочка отрезка), могут запускаться, когда более старые инструкции оставляют исполняемые блоки свободными (например, потому что они отстают от латентности, а не пропускной способности.).

Состояние RNG почти наверняка будет более длинной цепью зависимых циклов, чем addps .


Используйте более медленные / дополнительные операции FP (особенно разделение):

Разделите на 2.0 вместо умножения на 0.5 и т. Д. Многопоточность FP в значительной степени конвейерна в дизайнах Intel и имеет пропускную способность по 0,5 с на Haswell и позже. FP divsd / divpd только частично конвейерно . (Хотя Skylake имеет впечатляющую производительность на 4 divpd xmm для divpd xmm , с задержкой 13-14 c, а не с конвейером на Nehalem (7-22c)).

do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); явно тестируется на расстояние, поэтому ясно, что это будет правильно для sqrt() . : P ( sqrt еще медленнее, чем div ).

Как предполагает @Paul Clayton, переписывание выражений с ассоциативными / дистрибутивными эквивалентами может привести к большей работе (пока вы не используете -ffast-math чтобы позволить компилятору повторно оптимизировать). (exp(T*(r-0.5*v*v)) может стать exp(T*r - T*v*v/2.0) . Заметим, что хотя математика на вещественных числах ассоциативна, математика с плавающей запятой отсутствует , даже без учитывая переполнение / NaN (именно поэтому -ffast-math по умолчанию не -ffast-math ). См . комментарий Пола для очень волосатого вложенного предложения pow() .

Если вы можете масштабировать вычисления до очень малых чисел, тогда математические операторы FP берут ~ 120 дополнительных циклов, чтобы захватить микрокод, когда операция на двух нормальных числах создает денормальность . См. Микроархив Agner Fog для точных цифр и деталей. Это маловероятно, так как у вас много размножений, поэтому коэффициент масштабирования будет квадратным и будет уменьшаться до 0.0. Я не вижу никакого способа оправдать необходимое масштабирование с некомпетентностью (даже дьявольской), только преднамеренной злобой.


Если вы можете использовать intrinsics ( )

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

Используйте целочисленные перетасовки между математическими операциями FP, чтобы вызвать задержки байпаса.

Смешивание инструкций SSE и AVX без правильного использования vzeroupper вызывает большие киоски в pre-Skylake (и другое наказание в Skylake ). Даже без этого, векторизация плохо может быть хуже скалярного (больше циклов, потраченных на перетасовку данных в / из векторов, чем сэкономленных путем выполнения операций add / sub / mul / div / sqrt для четырех итераций Monte-Carlo сразу, с векторами 256b) , add / sub / mul исполняются полностью конвейерно и полноразмерно, но div и sqrt на векторах 256b не так быстро, как на векторах 128b (или скалярах), поэтому ускорение не является драматичным для double .

exp() и log() не имеют аппаратной поддержки, поэтому для части потребуется извлечь векторные элементы обратно в скаляр и вызвать функцию библиотеки отдельно, а затем перетащить результаты обратно в вектор. libm обычно скомпилирован для использования SSE2, поэтому будет использовать кодировки устаревшего SSE скалярных математических инструкций. Если ваш код использует 256b векторов и вызовы exp не делая сначала vzeroupper , тогда вы останавливаетесь. После возврата команда AVX-128, такая как vmovsd для установки следующего векторного элемента как arg для exp , также остановится. И тогда exp() снова остановится, когда будет выполняться инструкция SSE. Именно это и произошло в этом вопросе , вызвав 10-кратное замедление. (Спасибо @ZBoson).

См. Также эксперименты Натана Курза с математикой Intel по сравнению с glibc для этого кода . Будущий glibc будет иметь векторизованные реализации exp() и т. Д.


Если таргетинг на pre-IvB или esp. Nehalem, попытайтесь получить gcc, чтобы вызвать парные регистры с 16-битными или 8-битными операциями, за которыми следуют 32-битные или 64-битные операции. В большинстве случаев gcc будет использовать movzx после операции 8 или 16 movzx , но вот случай, когда gcc модифицирует ah а затем читает ax


С (inline) asm:

С (inline) asm вы можете сломать кэш uop: кусок кода 32B, который не вписывается в три строки кэша 6uop, заставляет переключиться с кэша uop на декодеры. Некомпетентный ALIGN использующий много однобайтовых nop s вместо пары длинных nop s на цели ветви внутри внутреннего цикла, может сделать трюк. Или поставьте выравнивание после метки, а не раньше. : P Это имеет значение только в том случае, если внешний интерфейс является узким местом, чего не будет, если нам удастся пессимизировать остальную часть кода.

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

LCP-киоски из 16-битных команд с непосредственными слишком большими, чтобы вписаться в 8 бит, вряд ли будут полезны. Кэш uop на SnB и позже означает, что вы платите только штраф за декодирование. В Nehalem (первый i7) он может работать для цикла, который не подходит в буфере цикла 28 uop. gcc иногда генерирует такие инструкции, даже с -mtune=intel и когда он мог бы использовать 32-битную инструкцию.


Общей идиомой для синхронизации является CPUID (для сериализации), затем RDTSC . Время каждой итерации отдельно с CPUID / RDTSC чтобы убедиться, что RDTSC не переупорядочивается с более ранними инструкциями, что значительно замедлит работу. (В реальной жизни разумный способ времени состоит в том, чтобы объединить все итерации вместе, вместо того, чтобы выбирать каждый отдельно и добавлять их).


Причиняет много промахов в кеше и других замедлений памяти

Используйте union { double d; char a[8]; } union { double d; char a[8]; } union { double d; char a[8]; } для некоторых ваших переменных. Вызов хранилища пересылки , делая узкий магазин (или Read-Modify-Write) только одному из байтов. (Эта статья wiki также охватывает множество других микроархитектурных материалов для очередей загрузки / хранения). например, перевернуть знак double с помощью XOR 0x80 только на высокий байт , а не на оператор. Дьявольски некомпетентный разработчик, возможно, слышал, что FP медленнее, чем целое число, и поэтому старайтесь делать как можно больше, используя целые операционные системы. (Очень хороший компилятор, ориентированный на математику FP в SSE-регистрах, может, возможно, скомпилировать это с xorps с константой в другом регистре xmm, но единственный способ, который это не ужасно для x87, заключается в том, что компилятор понимает, что он отрицает значение и заменяет следующий добавить с вычитанием.)


Используйте volatile если вы компилируете с -O3 и не используете std::atomic , чтобы заставить компилятор фактически хранить / перезагружать все место. Глобальные переменные (вместо locals) также будут вынуждать некоторые магазины / перезагрузки, но слабое упорядочение модели памяти C ++ не требует, чтобы компилятор постоянно проливал / перезагружал память.

Замените локальные вары членами большой структуры, чтобы вы могли управлять макетом памяти.

Используйте массивы в структуре для заполнения (и хранения случайных чисел, чтобы оправдать их существование).

Выберите макет памяти, чтобы все перешло в другую строку в том же «наборе» в кеше L1 . Это всего лишь 8-полосная ассоциативность, т. Е. Каждый набор имеет 8 “способов”. Кэш-линии – 64B.

Еще лучше, поставьте вещи точно на 4096B друг от друга, так как нагрузки имеют ложную зависимость от магазинов на разные страницы, но с одинаковым смещением внутри страницы . Агрессивные процессоры вне порядка используют Memory Disambiguation, чтобы выяснить, когда нагрузки и магазины могут быть переупорядочены без изменения результатов , а реализация Intel имеет ложные срабатывания, которые предотвращают начало загрузки. Вероятно, они проверяют только биты ниже смещения страницы, поэтому проверка может начинаться до того, как TLB переведет старшие биты с виртуальной страницы на физическую страницу. Как и руководство Агнера, см. Ответ от Стивена Канона , а также раздел в конце ответа @ Krazy Glew по тому же вопросу. (Энди Глев был одним из архитекторов оригинальной микроархитектуры P6 от Intel).

Используйте __attribute__((packed)) чтобы вы могли неправильно выровнять переменные, чтобы они охватывали границы кеша или даже границы страниц. (Таким образом, загрузка одного double требует данных из двух строк кэша). Несбалансированные нагрузки не имеют никакого штрафа в любом Intel i7 uarch, за исключением случаев, когда пересекаются линии кэша и строки страниц. Разделители кэширования по-прежнему занимают дополнительные циклы . Skylake резко снижает штраф за нагрузку с разбивкой по страницам, от 100 до 5 циклов. (Раздел 2.1.3) . Возможно, это связано с возможностью параллельной работы двух страниц.

atomic страницы на atomic должно быть примерно в худшем случае , особенно. если это 5 байт на одной странице и 3 байта на другой странице или что-то другое, кроме 4: 4. Даже расщепления по центру более эффективны для расщеплений кэш-линий с векторами 16B на некоторых урнах, IIRC. Поместите все в alignas(4096) struct __attribute((packed)) (для экономии места, конечно), включая массив для хранения результатов RNG. uint8_t несогласованности, используя uint8_t или uint16_t для чего-то перед счетчиком.

Если вы можете заставить компилятор использовать индексированные режимы адресации, это приведет к поражению микро-фьюжн . Возможно, используя #define s для замены простых скалярных переменных с помощью my_data[constant] .

Если вы можете ввести дополнительный уровень косвенности, поэтому адреса загрузки / хранения не известны раньше, что может пессимизировать дальше.


Трассировочные массивы в несмежном порядке

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

Для «максимальной случайности» у нас может быть stream, зависящий от случайного массива, записывающего в него новые случайные числа. Нить, использующая случайные числа, может генерировать случайный индекс для загрузки случайного числа из. (Здесь есть какая-то макетная работа, но микроархитектурно это помогает для определения адресов загрузки, чтобы быть известными раньше, чтобы любая возможная латентность загрузки могла быть разрешена до того, как загруженные данные понадобятся.) Наличие читателя и писателя на разных ядрах приведет к неправильному упорядочению памяти -speculation конвейер очищается (как обсуждалось ранее для случая ложного обмена).

Для максимальной пессимизации, петля над вашим массивом с шагом 4096 байт (т.е. 512 удваивается). например

 for (int i=0 ; i<512; i++) for (int j=i ; j 

Таким образом, шаблон доступа равен 0, 4096, 8192, ...,
8, 4104, 8200, ...
16, 4112, 8208, ...

Это то, что вы получите для доступа к 2D-массиву, например double rng_array[MAX_ROWS][512] в неправильном порядке (зацикливание по строкам вместо столбцов внутри строки во внутреннем цикле, как было предложено @JesperJuhl). Если дьявольская некомпетентность может оправдать 2D-массив с такими размерами, то некомпетентность садового разнообразия в реальном мире легко оправдывает цикл с неправильным шаблоном доступа. Это происходит в реальном коде в реальной жизни.

При необходимости отрегулируйте границы цикла, чтобы использовать много разных страниц вместо повторного использования одних и тех же нескольких страниц, если массив не такой большой. Предварительная выборка аппаратного обеспечения не работает (как и вообще) на всех страницах. Prefetcher может отслеживать один прямой и один обратный stream внутри каждой страницы (что и происходит здесь), но будет действовать только тогда, когда пропускная способность памяти уже не насыщена непревышением.

Это также будет генерировать много промахов TLB, если только страницы не будут объединены в огромную страницу ( Linux делает это оппортунистически для анонимных (не поддерживаемых файлом) распределений, таких как malloc / new которые используют mmap(MAP_ANONYMOUS) ).

Вместо массива для хранения списка результатов вы можете использовать связанный список . Тогда для каждой итерации потребуется скачкообразная нагрузка (реальная зависимость RAW для загрузочного адреса следующей нагрузки). С плохим распределителем вы можете разбросать узлы списка в памяти, побеждая кеш. С дьявольски некомпетентным распределителем он может помещать каждый узел в начало своей собственной страницы. (например, выделять с помощью mmap(MAP_ANONYMOUS) напрямую, без разбивки страниц или размеров объектов отслеживания для правильной поддержки free ).


Они не являются специфическими для микроархитектуры и имеют мало общего с конвейером (большинство из них также будет замедлять работу на неконвейерном процессоре).

Немного не по теме: заставить компилятор скомпрометировать код / ​​сделать больше работы:

Используйте C ++ 11 std::atomic и std::atomic для самого пессимального кода. Команды MFENCE и locked довольно медленны даже без конкуренции с другим streamом.

-m32 сделает медленный код, потому что код x87 будет хуже, чем код SSE2. 32-битное соглашение на основе стека принимает больше инструкций и передает даже аргументы FP в стек для таких функций, как exp() . atomic::operator++ on -m32 требует lock cmpxchg8B цикла lock cmpxchg8B (i586). (Так что используйте это для счетчиков циклов! [Зло смеется]).

-march=i386 также будет пессимизировать (спасибо @Jesper). fcom FP с fcom медленнее, чем 686 fcomi . Pre-586 не предоставляет атомный 64-битный магазин (не говоря уже о cmpxchg), поэтому все 64-битные атомы обрабатывают вызовы функций libgcc (которые, вероятно, скомпилированы для i686, а не с использованием блокировки). Попробуйте использовать ссылку на компилятор Godbolt в последнем абзаце.

Используйте long double / sqrtl / expl для дополнительной точности и дополнительной медленности в ABI, где sizeof ( long double ) - 10 или 16 (с отступом для выравнивания). (IIRC, 64-битная Windows использует long double эквивалент удвоенной long double 8байт (во всяком случае, загрузка / сохранение 10-битных (80 бит) операндов FP - это 4/7 uops, против float или double только по 1 fld m64/m32 для fld m64/m32 / fst ) Принуждение x87 с long double -m64 -march=haswell -O3 даже для gcc -m64 -march=haswell -O3 .

Если не использовать atomic циклов atomic , используйте long double для всего, включая счетчики циклов.

atomic , но операции чтения-изменения-записи, такие как += , не поддерживаются (даже на 64-битной). atomic должен вызывать библиотечную функцию только для атомных нагрузок / хранилищ. Вероятно, это действительно неэффективно, потому что x86 ISA естественно не поддерживает атомные 10-байтовые нагрузки / хранилища , и единственный способ, которым я могу думать без блокировки ( cmpxchg16b ), требует 64- cmpxchg16b режима.


При -O0 разложение большого выражения путем назначения частей временным варам приведет к большему количеству хранилищ / перезагрузок. Без volatile или чего-то, это не имеет значения с настройками оптимизации, которые будет использовать реальная assembly реального кода.

Правила сглаживания C позволяют char псевдоним, поэтому сохранение через char* заставляет компилятор хранить / перезагружать все до / после байтового хранилища даже на -O3 . (Это проблема для автоматического векторизации кода, который работает , например, с массивом uint8_t .)

Попробуйте uint16_t циклов uint16_t , чтобы uint16_t до 16 бит, возможно, используя 16-разрядный размер операнда (потенциальные киоски) и / или дополнительные инструкции movzx (безопасные). Подписанное переполнение - неопределенное поведение , поэтому, если вы не используете -fwrapv или, по крайней мере, -fno-strict-overflow , подписанные счетчики циклов не должны быть повторно подписаны на каждую итерацию , даже если они используются в качестве смещений для 64-битных указателей.


Принудительное преобразование из целого числа в float и обратно. И / или double <=> конверсии float . Инструкции имеют более чем одну задержку, а скалярный int-> float ( cvtsi2ss ) плохо разработан, чтобы не обнулить остальную часть регистра xmm. (gcc вставляет дополнительный pxor для разрыва зависимостей, по этой причине.)


Часто устанавливайте близость вашего процессора к другому CPU (предлагается @Egwor). дьявольское рассуждение: вы не хотите, чтобы одно kernel ​​перегрелось от работы с вашей нитью в течение длительного времени, не так ли? Может быть, обмен на другое kernel ​​позволит этому базовому турбому увеличить тактовую частоту. (На самом деле: они настолько термически близки друг к другу, что это маловероятно, за исключением многосетевой системы). Теперь просто настройте настройку неправильно и делайте это слишком часто. Помимо времени, затрачиваемого на сохранение и восстановление состояния ОС, новое kernel ​​имеет холодные кеши L2 / L1, кэш uop и предикторами ветвей.

Внедрение частых ненужных системных вызовов может замедлить вас независимо от того, что они собой представляют. Хотя некоторые важные, но простые, такие как gettimeofday могут быть реализованы в пользовательском пространстве без перехода в режим ядра. (glibc в Linux делает это с помощью ядра, так как kernel ​​экспортирует код в vdso ).

Для получения дополнительной информации о служебных расходах системного вызова (включая пропуски кэша / TLB после возвращения в пользовательское пространство, а не только сам контекстный коммутатор), в документе FlexSC имеется отличный анализ производительности в реальном времени, а также предложение для системы дозирования вызовы от многопоточных серверных процессов.

Несколько вещей, которые вы можете сделать, чтобы сделать все как можно хуже:

  • скомпилируйте код для архитектуры i386. Это предотвратит использование SSE и новых инструкций и заставит использовать FPU x87.

  • используйте std::atomic переменные везде. Это сделает их очень дорогими из-за того, что компилятор вынужден вставлять барьеры памяти повсюду. И это то, что некомпетентный человек может правдоподобно сделать, чтобы «обеспечить безопасность streamа».

  • убедитесь, что вы получили доступ к памяти наихудшим образом, чтобы предсказатель мог предсказать (основной столбец и основной массив).

  • чтобы сделать ваши переменные более дорогостоящими, вы можете убедиться, что у них у всех есть «динамическая продолжительность хранения» (выделенная куча) путем выделения их new а не предоставления им «автоматической продолжительности хранения» (выделение стека).

  • убедитесь, что вся память, которую вы выделяете, очень странно выровнена и, во всяком случае, избегает выделения огромных страниц, так как это будет слишком эффективным TLB.

  • что бы вы ни делали, не создавайте свой код с включенным оптимизатором компиляторов. И обязательно включите наиболее выразительные символы отладки, которые вы можете (не будет делать код медленнее, но он будет тратить лишнее место на диске).

Примечание. Этот ответ в основном просто обобщает мои комментарии, которые @Peter Cordes уже включил в его очень хороший ответ. Предложите, чтобы он получил ваше преимущество, если у вас есть только один:

Вы можете использовать long double для вычисления. На x86 это должен быть 80-битный формат. Только поддержка x87 FPU имеет поддержку для этого.

Немного недостатков x87 FPU:

  1. Отсутствие SIMD, может потребоваться больше инструкций.
  2. Основанный на стеках, проблематичный для суперскалярных и конвейерных архитектур.
  3. Separate and quite small set of registers, may need more conversion from other registers and more memory operations.
  4. On the Core i7 there are 3 ports for SSE and only 2 for x87, the processor can execute less parallel instructions.

Late answer but I don’t feel we have abused linked lists and the TLB enough.

Use mmap to allocate your nodes, such that your mostly use the MSB of the address. This should result in long TLB lookup chains, a page is 12 bits, leaving 52 bits for the translation, or around 5 levels it must travers each time. With a bit of luck they must go to memory each time for 5 levels lookup plus 1 memory access to get to your node, the top level will most likely be in cache somewhere, so we can hope for 5*memory access. Place the node so that is strides the worst border so that reading the next pointer would cause another 3-4 translation lookups. This might also totally wreck the cache due to the massive amount of translation lookups. Also the size of the virtual tables might cause most of the user data to be paged to disk for extra time.

When reading from the single linked list, make sure to read from the start of the list each time to cause maximum delay in reading a single number.

  • Самый быстрый способ прокрутки массива 2d?
  • Самый эффективный способ расчета расстояния Левенштейн
  • Почему всегда закрывается соединение с базой данных?
  • Django: установить внешний ключ с помощью целого числа?
  • Является ли тернарный оператор быстрее, чем условие «если»
  • Измерение времени выполнения функции в C ++
  • Как читать содержимое файла в istringstream?
  • Proguard с OrmLite на Android
  • Как предотвратить GCC от оптимизации цикла ожидания занятости?
  • Использование индекса, используя временный, с помощью filesort - как это исправить?
  • Различные результаты с плавающей запятой с включенной оптимизацией - ошибка компилятора?
  • Interesting Posts

    Получение исключения ConcurrentModificationException при удалении элемента из java.util.List во время итерации списка?

    ISP блокирует использование ssh?

    Как выразить запрос NOT IN с помощью ActiveRecord / Rails?

    Как команда Windows RENAME интерпретирует подстановочные знаки?

    Как отключить прокрутку средней кнопки в Chrome

    Полный рабочий пример сценария анимации с тремя fragmentами Gmail?

    Оптимизация MySQL для ALTER TABLE of InnoDB

    Использование strtok в c

    Как преобразовать целое число цвета в шестнадцатеричную строку в Android?

    Предназначение камеры Android Сохранение ландшафта изображения при съемке

    Партнерская сеть MSFT Обновление для Windows 8 Enterprise до Windows 8.1 – Нет приложений

    Как синхронизировать произвольную папку Windows с учетной записью Dropbox?

    Как создать строки, содержащие двойные кавычки в формулах Excel?

    Android – ListView для загрузки большего количества предметов по достижении конца

    Почему по умолчанию stream файлов в C ++ имеет узкие письменные данные?

    Давайте будем гением компьютера.