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

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

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

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

// 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)) * 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)) * 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;
}

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


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

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

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

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

• 100001 100002 *

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

Ответы (4)

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

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


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

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

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

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

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

Для упорядочивания памяти современные процессоры используют буфер хранения , чтобы отложить фиксацию в кеш до вывода из эксплуатации, также избегая опасностей WAR и WAW. См. Также этот ответ о том, что такое буфер хранилища, и это важно для OoO exec, чтобы отделить выполнение от вещей, которые могут видеть другие ядра.

Почему на Haswell требуется только 3 цикла обработки, в отличие от таблиц инструкций Агнера? (Развертывание циклов FP с несколькими накопителями) содержит дополнительную информацию о переименовании регистров и сокрытии задержки FMA в цикле скалярного произведения FP.


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


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

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

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

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


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

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

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

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


Случайные идеи, специфичные для uarch:

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


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

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

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

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

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


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

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

The do {...; euclid_sq = х * х + у * у; } while (euclid_sq> = 1.0); явно тестирует расстояние, поэтому очевидно, что было бы правильно использовать sqrt () it. : 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 потребуется ~ 120 дополнительных циклов для захвата микрокода, когда операция с двумя нормальными числами дает денормальное. См. Точные цифры и подробности в pdf-формате микроархитектуры Agner Fog. Это маловероятно, так как у вас много умножений, поэтому коэффициент масштабирования будет возведен в квадрат и полностью исчезнет до 0,0. Я не вижу никакого способа оправдать необходимое масштабирование некомпетентностью (даже дьявольской), только преднамеренной злобой.


### Если вы можете использовать встроенные функции ()

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

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

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

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

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


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


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

• 100001 Некомпетентный ALIGN (например, NASM по умолчанию), использующий много однобайтовых nops вместо пары long nops на целевой ветви внутри внутреннего цикла, может сделать Хитрость. Или поместите выравнивающую прокладку после метки, а не перед ней. : P Это имеет значение только в том случае, если интерфейс является узким местом, чего не будет, если нам удастся пессимизировать остальную часть кода.

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

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


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


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

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


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

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

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

Выберите структуру памяти, чтобы все помещалось в другую строку того же «набора» в кэше L1. Это только 8-сторонняя ассоциативная связь, т.е. в каждом наборе есть 8 «путей». Строки кэша - 64Б.

Еще лучше, разделяет вещи точно на 4096B, поскольку загрузки имеют ложную зависимость от хранилищ на разных страницах, но с одинаковым смещением внутри страницы. Агрессивные вышедшие из строя ЦП используют Устранение неоднозначности памяти, чтобы выяснить, когда можно переупорядочить загрузки и сохранения без изменения результатов, а реализация Intel имеет ложные срабатывания, предотвращающие ранний запуск загрузки. Вероятно, они проверяют только биты ниже смещения страницы, чтобы он мог начаться до того, как TLB переведет старшие биты с виртуальной страницы на физическую страницу. Помимо руководства Агнера, см. этот ответи раздел в конце ответа @Krazy Glew на тот же вопрос. (Энди Глю был архитектором микроархитектуры Intel PPro - P6.) (Также связаны: https://stackoverflow.com/a/53330296 и https://github.com/travisdowns/uarch-bench/wiki/Memory-Disambiguation-on-Skylake)

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

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

Если вы можете заставить компилятор использовать режимы индексированной адресации, это приведет к поражению uop micro-fusion. Возможно, используя # defines, чтобы заменить простые скалярные переменные на my_data [constant].

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


Обход массивов в несмежном порядке

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

Для «максимальной случайности» у нас может быть поток, перебирающий случайный массив с записью в него новых случайных чисел. Поток, использующий случайные числа, может сгенерировать случайный индекс для загрузки случайного числа. (Здесь есть некоторая работа, но с точки зрения микроархитектуры это помогает заранее узнать адреса загрузки, поэтому любая возможная задержка загрузки может быть устранена до того, как потребуются загруженные данные.) Наличие устройства чтения и записи на разных ядрах приведет к неправильному упорядочиванию памяти. -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). Если дьявольская некомпетентность может оправдать двумерный массив с такими размерами, то реальная некомпетентность садового разнообразия легко оправдывает зацикливание с неправильным шаблоном доступа. Это происходит в реальном коде в реальной жизни.

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

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

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


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

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

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

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

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

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

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

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


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

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

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


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


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

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

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

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

Несколько недостатков x87 FPU:

  1. Отсутствие SIMD, может потребоваться дополнительная инструкция.
  2. На основе стека, проблематично для суперскалярных и конвейерных архитектур.
  3. Отдельный и довольно небольшой набор регистров, может потребоваться большее преобразование из других регистров и больше операций с памятью.
  4. На Core i7 есть 3 порта для SSE и только 2 для x87, процессор может выполнять меньше параллельных инструкций.

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

  • compile the code for the i386 architecture. This will prevent the use of SSE and newer instructions and force the use of the x87 FPU.

  • use std::atomic variables everywhere. This will make them very expensive due to the compiler being forced to insert memory barriers all over the place. And this is something an incompetent person might plausibly do to "ensure thread safety".

  • make sure to access memory in the worst possible way for the prefetcher to predict (column major vs row major).

  • to make your variables extra expensive you could make sure they all have 'dynamic storage duration' (heap allocated) by allocating them with new rather than letting them have 'automatic storage duration' (stack allocated).

  • make sure that all memory you allocate is very oddly aligned and by all means avoid allocating huge pages, since doing so would be much too TLB efficient.

  • whatever you do, don't build your code with the compilers optimizer enabled. And make sure to enable the most expressive debug symbols you can (won't make the code run slower, but it'll waste some extra disk space).

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

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

Используйте mmap для выделения ваших узлов, так что вы в основном используете MSB адреса. Это должно привести к длинным цепочкам поиска TLB, страница состоит из 12 бит, оставляя 52 бита для трансляции, или около 5 уровней, которые она должна проходить каждый раз. Если повезет, они должны обращаться в память каждый раз для поиска на 5 уровнях плюс 1 доступ к памяти, чтобы добраться до вашего узла, верхний уровень, скорее всего, будет где-то в кеше, поэтому мы можем надеяться на доступ к памяти 5 *. Разместите узел так, чтобы он проходил через худшую границу, чтобы чтение следующего указателя вызывало еще 3-4 поиска перевода. Это также может полностью разрушить кеш из-за огромного количества поисков переводов. Также размер виртуальных таблиц может привести к тому, что большая часть пользовательских данных будет выгружена на диск на дополнительное время.

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

2022 WebDevInsider