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

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

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

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

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

// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm>    // Needed for the "max" function
#include <cmath>
#include <iostream>

// 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 <random> 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<double>(RAND_MAX)-1;
    y = 2.0 * rand() / static_cast<double>(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<double>(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<double>(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;
}

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

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

основные выводы:

  • это a второй семестр архитектурный класс в местном колледже (с использованием учебника Хеннесси и Паттерсона).
  • лабораторные компьютеры имеют процессоры Haswell
  • студенты были подвергнуты воздействию CPUID инструкции и как определить размер кэша, а также встроенные функции и CLFLUSH инструкция.
  • разрешены любые параметры компилятора, а также встроенный asm.
  • написание собственного алгоритма квадратного корня было объявлено как находящееся за пределами бледно -
Cowmoogun на мета резьба свидетельствуют о том, что не было ясно, оптимизация компилятора может быть частью этого, и предполагается -O0, и что увеличение времени выполнения на 17% было разумным.

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

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

1 295
c++ x86 intellij-idea optimization cpu-architecture

1 ответ:

важное значение фон значение: Агнер туман в формате PDF, и, вероятно, также Ульриха Дреппера Что Каждый Программист Должен Знать О Памяти!--99-->. Смотрите также другие ссылки в x86 tag wiki, особенно руководства по оптимизации Intel и Дэвида Кантера анализ микроархитектуры Haswell, с диаграммами.

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

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

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

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

процессоры семейства Intel Sandybridge-это агрессивные нестандартные конструкции, которые тратят много транзисторов и мощности, чтобы найти параллелизм и избежать опасностей (зависимостей), которые будут беспокоить классический конвейер RISC in-order. Обычно единственными традиционными опасностями, которые замедляют его, являются необработанные" истинные " зависимости, которые ограничивают пропускную способность задержка.

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

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

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

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

  • Multi-резьбы с одним sharedstd::atomic<uint64_t> счетчик циклов, поэтому правильное общее количество итераций происходит. Atomic uint64_t особенно плох с -m32 -march=i586. Для получения бонусных очков, организовать его чтобы быть смещенным и пересекать границу страницы с неравномерным разделением (не 4:4).
  • ложного совместного использования для некоторых других неатомных переменных- > конвейер mis-спекуляции порядка памяти очищается, а также дополнительные пропуски кэша.
  • вместо - на переменных FP, XOR высокий байт с 0x80, чтобы перевернуть знаковый бит, вызывая магазин-экспедиционных палатках.
  • время каждой итерации независимо, с чем - то еще тяжелее чем RDTSC. например,CPUID/RDTSC или функция времени, которая делает системный вызов. Сериализация инструкций по своей сути является недружественной для конвейера.
  • изменение умножается на константы и делится на их взаимные ("для удобства чтения"). div является медленным и не полностью конвейерным.
  • векторизовать multiply/sqrt с AVX (SIMD), но не использовать vzeroupper перед вызовами скалярной математической библиотеки exp() и log() функции, вызывая AVX SSE transition stalls.
  • сохраните выходные данные RNG в связанном списке или в массивах, которые вы пересекаете не по порядку. То же самое для результата каждой итерации, и сумма в конце.

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

многопоточность плохо

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

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

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

случайные уарч-конкретные идеи:

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

цепочек зависимостей:

я думаю, что это была одна из предполагаемых частей задания.

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

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

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

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

разделить на 2.0 вместо умножение на 0.5, и так далее. ФП размножаются активно задействованы в конструкции процессоров Intel, а также имеет на пропускную способность 0.5 C на Haswell и позже. FP divsd/divpd только частично переданные. (Хотя Skylake имеет впечатляющую пропускную способность на 4C для divpd xmm, С задержкой 13-14c, vs вообще не конвейеризован на Nehalem (7-22c)).

The 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 не по умолчанию). Смотрите Павел комментарий для очень волосатых вложенных pow() предложение.

если вы можете масштабировать вычисления до очень малых чисел, то FP math ops take ~120 дополнительных циклов ловушка для микрокода, когда работа на двух обычных чисел производит Донормила. Увидеть палочек agner туман microarch PDF для точных цифр и деталей. Это маловероятно, так как у вас есть много умножений, поэтому масштабный коэффициент будет возведен в квадрат и уменьшится до 0.0. Я не вижу никакого способа оправдывать необходимое масштабирование нужно некомпетентностью (даже дьявольской), только умышленной злобой.

если вы можете использовать встроенные функции (<immintrin.h>)

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

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

смешивание инструкций SSE и AVX без надлежащего использования vzeroupper вызывает большие киоски в pre-Skylake (и другой штраф в армию). Даже без этого плохая векторизация может быть хуже скалярной (больше циклов, затраченных на перетасовку данных в / из векторов, чем сохраненных при выполнении добавьте/sub/mul/div / sqrt операции для 4 итераций Монте-Карло сразу, с векторами 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-битные операции. В большинстве случаев ССЗ будет использовать movzx после 8-или 16-bit работа, но вот случай, когда gcc изменяет ah а потом читает ax

с (встроенным) asm:

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

используйте самомодифицирующийся код для запуска очистки конвейера (он же machine-nukes).

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

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

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

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

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

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

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

выберите макет памяти так все идет в другую строку в том же" наборе " в кэше L1. Это только 8-полосная ассоциативная, т. е. каждый набор имеет 8 "путей". Строки кэша являются 64B.

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

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

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

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

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

пересекать массивы в несмежном порядке

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

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

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

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

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

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

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

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

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

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

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

Используйте C++11 std::atomic<int> и std::atomic<double> для самых пессимальный код. В MFENCEs и lockинструкции ed довольно медленны даже без конкуренции из другого потока.

-m32 сделает более медленный код, потому что код x87 будет хуже, чем код SSE2. Стек на основе 32-битного соглашения о вызовах принимает больше инструкций и передает даже FP args в стеке таким функциям, как exp().

380