Деоптимизация программы для конвейера в процессорах семейства Intel Sandybridge
Я целую неделю ломал голову, пытаясь выполнить это задание, и я надеюсь, что кто-то здесь может привести меня к правильному пути. Позвольте мне начать с инструкций инструктора:
Ваше задание противоположно нашему первому лабораторному заданию, которое должно было оптимизировать программу простых чисел. Ваша цель в этом задании - пессимизировать программу, то есть заставить ее работать медленнее. Обе программы загружают процессор. На наших лабораторных ПК им требуется несколько секунд. Вы не можете изменить алгоритм.
Чтобы деоптимизировать программу, используйте свои знания о том, как работает конвейер Intel i7. Представьте себе способы переупорядочить пути инструкций, чтобы представить WAR, RAW и другие опасности. Подумайте, как минимизировать эффективность кэша. Быть дьявольски некомпетентным.
Задание предоставило выбор программ Whetstone или Monte-Carlo. Комментарии по эффективности кэширования в основном применимы только к Уитстоуну, но я выбрал программу моделирования Монте-Карло:
// 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;
}
Внесенные мной изменения, казалось, увеличили время выполнения кода на секунду, но я не совсем уверен, что я могу изменить, чтобы остановить конвейер без добавления кода. Точка в правильном направлении была бы потрясающей, я ценю любые ответы.
Обновление: профессор, который дал это назначение, отправил некоторые детали
Основные моменты:
- Это второй семестр урок архитектуры в колледже (с использованием учебника Хеннесси и Паттерсона).
- лабораторные компьютеры имеют процессоры Haswell
- Студенты были подвергнуты
CPUIDинструкция и как определить размер кэша, а также встроенныеCLFLUSHинструкция. - разрешены любые параметры компилятора, как и встроенный asm.
- Написание собственного алгоритма квадратного корня было объявлено вне рамок
Комментарии Cowmoogun к мета-ветке показывают, что неясно, что оптимизация компилятора может быть частью этого, и предполагал, что-O0и что увеличение времени выполнения на 17% было разумным.
Похоже, что цель задания состояла в том, чтобы заставить студентов переупорядочить существующую работу, чтобы уменьшить параллелизм на уровне обучения или тому подобное, но это не плохо, что люди углубились и узнали больше.
Имейте в виду, что это вопрос компьютерной архитектуры, а не вопрос о том, как сделать C++ медленным в целом.
4 ответа
Важная справочная информация: микроарх pdf Агнера Фога и, вероятно, также Ульрих Дреппер, что каждый программист должен знать о памяти. См. Также другие ссылки в вики-теге x86, особенно руководства по оптимизации Intel, и анализ микроархитектуры Haswell Дэвидом Кантером с диаграммами.
Очень классное задание; гораздо лучше, чем те, которые я видел, где студентов попросили оптимизировать некоторый код для gcc -O0, изучая кучу трюков, которые не имеют значения в реальном коде. В этом случае вас просят узнать о конвейере ЦП и использовать его для руководства вашими усилиями по де-оптимизации, а не только для слепых предположений. Самая забавная часть этого оправдывает каждую пессимизацию "дьявольской некомпетентностью", а не преднамеренной злобой.
Проблемы с назначением формулировки и кода:
Параметры, специфичные для uarch, для этого кода ограничены. Он не использует никаких массивов, и большая часть затрат - это вызовы exp / log библиотечные функции. Не существует очевидного способа получить более или менее параллелизм на уровне команд, и цепочка зависимостей, переносимых циклами, очень коротка.
Мне бы очень хотелось увидеть ответ, в котором была предпринята попытка замедлить процесс реорганизации выражений, чтобы изменить зависимости, уменьшить ILP только из зависимостей (опасностей). Я не пытался это сделать.
Процессоры семейства Intel Sandybridge представляют собой агрессивные нестандартные конструкции, которые расходуют много транзисторов и мощности для нахождения параллелизма и избегания опасностей (зависимостей), которые могли бы создать проблему для классического конвейера RISC по порядку. Обычно единственными традиционными опасностями, которые замедляют его, являются "истинные" зависимости RAW, которые приводят к тому, что пропускная способность ограничивается задержкой.
Опасности для регистров WAR и WAW в значительной степени не проблема, благодаря переименованию регистров. (кроме popcnt / lzcnt / tzcnt, которые имеют ложную зависимость их назначения на процессорах Intel, хотя это только для записи. т.е. WAW обрабатывается как RAW-опасность + запись). Для упорядочения памяти современные процессоры используют очереди хранилищ, чтобы задержать фиксацию в кеше до выхода на пенсию, также избегая опасностей WAR и WAW.
Почему Мулсс занимает всего 3 цикла в Haswell, в отличие от таблиц инструкций Агнера? больше о переименовании регистров и сокрытии задержки FMA в цикле FP.
Фирменное наименование "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 с инклюзивным доступом для соединения нескольких ядер друг с другом. А также с интегрированными графическими процессорами. Таким образом, на уровне чипов наименование имеет больше смысла.)
Резюме хороших идей, которые может оправдать дьявольская некомпетентность
Даже дьявольски некомпетентные люди вряд ли добавят заведомо бесполезную работу или бесконечный цикл, и создание беспорядка с классами C++/Boost выходит за рамки назначения.
- Многопоточность с одним общим
std::atomic<uint64_t>счетчик циклов, так что правильное общее количество итераций происходит. Атомная uint64_t особенно плоха с-m32 -march=i586, Чтобы получить бонусные баллы, сделайте так, чтобы они были выровнены, и пересечение границы страницы неравномерным (не 4:4). - Ложное совместное использование для некоторой другой неатомарной переменной -> конвейер неправильной спекуляции порядка памяти очищает, а также лишние ошибки кэширования.
- Вместо того, чтобы использовать
-для переменных FP: XOR старшего байта с 0x80, чтобы перевернуть знаковый бит, вызывая остановку пересылки магазина. - Время каждой итерации независимо, с чем-то еще тяжелее, чем
RDTSC, напримерCPUID/RDTSCили функция времени, которая делает системный вызов. Инструкции по сериализации по своей сути являются недружественными. - Измените умножения на константы на деления на их взаимные ("для удобства чтения"). div медленный и не полностью конвейерный.
- Векторизация умножения /sqrt с AVX (SIMD), но не использовать
vzeroupperперед вызовами в скалярную математическую библиотекуexp()а такжеlog()функции, вызывающие AVX <-> SSE переходные срывы. - Сохраните выходные данные ГСЧ в связанном списке или в массивах, которые вы просматриваете не по порядку. То же самое для результата каждой итерации, и сумма в конце.
Также рассматривается в этом ответе, но исключается из резюме: предложения, которые были бы такими же медленными для непотрубного процессора, или которые не кажутся оправданными даже при дьявольской некомпетентности. например, много идей gimp-the-compiler, которые приводят к явно другому / худшему асму.
Многопоточность плохо
Возможно, используйте OpenMP для многопоточных циклов с очень небольшим количеством итераций, с гораздо большими накладными расходами, чем прирост скорости. Ваш код Монте-Карло имеет достаточно параллелизма, чтобы на самом деле получить ускорение, тем не менее, особенно. если нам удастся сделать каждую итерацию медленной. (Каждый поток вычисляет частичное payoff_sum, добавил в конце). #omp parallel в этом цикле, вероятно, будет оптимизация, а не пессимизация.
Многопоточность, но вынуждает оба потока использовать один и тот же счетчик цикла atomic увеличивается, поэтому общее число итераций будет правильным). Это кажется дьявольски логичным. Это означает использование static переменная как счетчик цикла. Это оправдывает использование atomic для счетчиков цикла и создает фактический пинг-понг на линии кэша (если потоки не работают на одном физическом ядре с гиперпоточностью; это может быть не так медленно). Во всяком случае, это гораздо медленнее, чем необоснованный случай lock inc, А также lock cmpxchg8b атомарно увеличить утверждаемый uint64_t в 32-битной системе придется повторить цикл вместо аппаратного арбитра атомного inc,
Также создайте ложное совместное использование, где несколько потоков хранят свои личные данные (например, состояние RNG) в разных байтах одной и той же строки кэша. (Учебное пособие Intel об этом, включая счетчики перфорации). В этом есть аспект, специфичный для микроархитектуры: процессоры Intel предполагают, что неправильное упорядочение памяти не происходит, и есть событие машинного сброса порядка порядка памяти, чтобы обнаружить это, по крайней мере, на P4. Наказание может быть не таким большим на Haswell. Как указывает эта ссылка, lock Инструкция ed предполагает, что это произойдет, избегая неправильных предположений. Нормальная загрузка предполагает, что другие ядра не будут делать недействительной строку кэша между тем, когда загрузка выполняется и когда она удаляется в программном порядке ( если вы не используете pause). Правда делиться без lockРедакция инструкции обычно является ошибкой. Было бы интересно сравнить неатомарный счетчик общего цикла с атомарным случаем. Чтобы по-настоящему пессимизировать, сохраняйте счетчик общего атомарного цикла и вызывайте ложное совместное использование в той же или другой строке кэша для некоторой другой переменной.
Случайные уарх-специфические идеи:
Если вы можете ввести какие-либо непредсказуемые ветки, это существенно снизит код. Современные процессоры x86 имеют довольно длинные конвейеры, поэтому ошибочный прогноз стоит ~15 циклов (при работе из кэша UOP).
Цепочки зависимостей:
Я думаю, что это была одна из предполагаемых частей задания.
Отказаться от способности процессора использовать параллелизм на уровне команд, выбрав порядок операций, который имеет одну длинную цепочку зависимостей вместо нескольких коротких цепочек зависимостей. Компиляторы не могут изменять порядок операций для вычислений FP, если вы не используете -ffast-math потому что это может изменить результаты (как обсуждается ниже).
Чтобы действительно сделать это эффективным, увеличьте длину цепочки зависимостей, переносимых циклами. Тем не менее, ничто не выглядит так очевидно: циклы, как написано, имеют очень короткие цепочки зависимостей, переносимых циклами: просто добавление FP. (3 цикла). Многократные итерации могут иметь свои вычисления в полете сразу, потому что они могут начаться задолго до payoff_sum += в конце предыдущей итерации. (log() а также exp потребуется много инструкций, но не намного больше, чем окно неупорядоченности Haswell для нахождения параллелизма: размер ROB =192 мопов в слитых доменах и размер планировщика =60 мопов в неиспользуемых доменах. Как только выполнение текущей итерации продвигается достаточно далеко, чтобы освободить место для инструкций из следующей итерации, чтобы выполнить, любые ее части, у которых есть готовые входные данные (то есть независимая / отдельная цепочка депозита), могут начать выполняться, когда более старые инструкции покидают блоки выполнения бесплатно (например, потому что они имеют узкое место по задержке, а не по пропускной способности).
Состояние RNG почти наверняка будет более длинной цепочкой зависимостей, чем addps,
Используйте более медленные / больше операций FP (особенно больше деления):
Разделите на 2,0 вместо умножения на 0,5 и так далее. Умножение FP в значительной степени конвейеризовано в проектах Intel и имеет пропускную способность на 0.5c в Haswell и более поздних версиях. FP divsd / divpd только частично конвейеризован. (Хотя Skylake имеет впечатляющую пропускную способность на 4C для divpd xmm с задержкой 13-14c, против конвейера на Nehalem (7-22c)).
do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); явно тестирует на расстоянии, так ясно, что было бы правильно sqrt() Это.:П (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 для точного числа и деталей. Это маловероятно, поскольку у вас много множителей, поэтому масштабный коэффициент будет возведен в квадрат и уменьшен до 0,0. Я не вижу способа оправдать необходимое масштабирование некомпетентностью (даже дьявольской), только преднамеренной злобой.
Если вы можете использовать встроенные (<immintrin.h>)
использование movnti выселить ваши данные из кеша. Diabolical: он новый и слабо упорядоченный, так что процессор должен его запускать быстрее, верно? Или посмотрите этот связанный вопрос для случая, когда кто-то был в опасности сделать именно это (для разрозненных записей, где только в некоторых местах было жарко). clflush вероятно, невозможно без злого умысла.
Используйте целочисленные тасования между математическими операциями FP, чтобы вызвать задержки обхода.
Смешивание инструкций SSE и AVX без надлежащего использования vzeroupper вызывает большие киоски в до Skylake (и другой штраф в Skylake). Даже без этого плохая векторизация может быть хуже скалярной (больше циклов тратится на перетасовку данных в / из векторов, чем на сохранение, выполняя операции add/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 установить следующий элемент вектора в качестве аргумента для exp также остановится. А потом exp() остановится снова, когда он выполнит инструкцию SSE. Это именно то, что произошло в этом вопросе, вызвав 10-кратное замедление. (Спасибо @ZBoson).
Посмотрите также эксперименты Натана Курца с математической библиотекой Intel и glibc для этого кода. Будущий glibc будет поставляться с векторизованными реализациями exp() и так далее.
Если нацелен на pre-IvB или esp. Нехалем, попробуй заставить gcc вызвать частичные регистры с 16-битными или 8-битными операциями, за которыми следуют 32-битные или 64-битные операции. В большинстве случаев GCC будет использовать movzx после 8 или 16-битной операции, но вот случай, когда gcc изменяет ah а потом читает ax
С (встроенным) asm:
С помощью (встроенного) asm вы можете разбить кэш uop: 32-килобайтный фрагмент кода, который не помещается в три строки кэша 6uop, заставляет переключиться с кэша uop на декодеры. Некомпетентный ALIGN используя много однобайтовых nop с вместо пары длинных nop s на целевой ветви во внутреннем цикле может помочь. Или поместите выравнивающий отступ после метки, а не до.:P Это имеет значение только в том случае, если внешний интерфейс является узким местом, чего не будет, если мы преуспеем в пессимизации остальной части кода.
Используйте самоизменяющийся код для запуска очистки конвейера (также называемой машинным ядром).
LCP-киоски из 16-битных инструкций с непосредственными значениями, слишком большими, чтобы поместиться в 8-битные, вряд ли будут полезны. Кэш UOP в SnB и более поздних версиях означает, что вы платите штраф за декодирование только один раз. На Nehalem (первый i7) он может работать для цикла, который не помещается в буфер цикла на 28 моп. gcc иногда генерирует такие инструкции, даже если -mtune=intel и когда он мог бы использовать 32-битную инструкцию.
Распространенной идиомой для выбора времени является CPUID (для сериализации) тогда RDTSC, Время каждой итерации отдельно с CPUID / RDTSC чтобы убедиться, что RDTSC не переупорядочено с более ранними инструкциями, которые сильно замедляют работу. (В реальной жизни разумный способ рассчитать время - это провести все итерации по времени, вместо того, чтобы рассчитывать каждую из них по отдельности и складывать их).
Вызывает много пропусков кэша и других замедлений памяти
Использовать union { double d; char a[8]; } для некоторых из ваших переменных. Вызвать переадресацию магазина, выполнив узкое хранилище (или Read-Modify-Write) только для одного из байтов. (Эта вики-статья также охватывает много других микроархитектурных вещей для очередей загрузки / хранения). например, переверните знак double используя XOR 0x80 только для старшего байта вместо - оператор. Дьявольски некомпетентный разработчик, возможно, слышал, что FP медленнее, чем целое число, и, таким образом, пытается сделать как можно больше, используя целочисленные операции. (Очень хороший компилятор, нацеленный на математику FP в регистрах SSE, может скомпилировать это в xorps с константой в другом регистре xmm, но единственный способ, которым это не страшно для x87, - это если компилятор понимает, что он отрицает значение и заменяет следующее сложение вычитанием.)
использование volatile если вы компилируете с -O3 и не используя std::atomic, чтобы заставить компилятор фактически хранить / перезагружать повсюду. Глобальные переменные (вместо локальных) также будут вызывать некоторые сохранения / перезагрузки, но слабый порядок модели памяти C++ не требует, чтобы компилятор постоянно проливал / перезагружал в память.
Замените локальные переменные членами большой структуры, чтобы вы могли контролировать структуру памяти.
Используйте массивы в структуре для заполнения (и хранения случайных чисел, чтобы оправдать их существование).
Выберите свой макет памяти, чтобы все входило в другую строку в том же "наборе" в кэше L1. Это только 8-сторонняя ассоциация, то есть каждый набор имеет 8 "путей". Строки кэша 64B.
Более того, поместите вещи точно в 4096B, так как нагрузки имеют ложную зависимость от хранилищ на разных страницах, но с одинаковым смещением на странице. Агрессивные неупорядоченные процессоры используют устранение неоднозначности памяти, чтобы выяснить, когда загрузки и хранилища можно переупорядочить без изменения результатов, а реализация Intel имеет ложные срабатывания, которые предотвращают раннее начало загрузки. Возможно, они проверяют только биты ниже смещения страницы, поэтому проверка может начаться до того, как TLB переведет старшие биты с виртуальной страницы на физическую страницу. Как и руководство Агнера, см. Ответ Стивена Кэнона, а также раздел в конце ответа @Krazy Glew на тот же вопрос. (Энди Глеу был одним из архитекторов оригинальной микроархитектуры P6 от Intel.)
использование __attribute__((packed)) чтобы позволить вам неправильно выровнять переменные так, чтобы они перекрывали строки кэша или даже границы страниц. (Так что нагрузка одного double нужны данные из двух строк кэша). Нераспределенные нагрузки не имеют штрафов ни в одном Intel i7 uarch, за исключением случаев пересечения строк кэша и строк страницы. Разделение строк кэша все еще требует дополнительных циклов. Skylake значительно снижает штраф за загрузку страниц с 100 до 5 циклов. (Раздел 2.1.3). Возможно, связано с возможностью параллельного обхода двух страниц.
Разделение страницы на atomic<uint64_t> должно быть примерно в худшем случае, особенно если это 5 байт на одной странице и 3 байта на другой странице, или что-то кроме 4:4. Даже расщепления по середине более эффективны для расщепления строк кэша с векторами 16B на некоторых уровнях, IIRC. Положите все в alignas(4096) struct __attribute((packed)) (для экономии места, конечно), включая массив для хранения результатов ГСЧ. Добиться смещения с помощью uint8_t или же uint16_t за что-то до прилавка.
Если вы можете заставить компилятор использовать индексированные режимы адресации, это победит микроплавление. Может быть, используя #define s заменить простые скалярные переменные my_data[constant],
Если вы можете ввести дополнительный уровень косвенности, чтобы адреса загрузки / хранения не были известны раньше, это может привести к дальнейшей пессимизации.
Массивы перемещения в несмежном порядке
Я думаю, что мы можем придумать некомпетентное обоснование для введения массива в первую очередь: он позволяет нам отделить генерацию случайных чисел от использования случайных чисел. Результаты каждой итерации также могут быть сохранены в массиве для последующего суммирования (с большей дьявольской некомпетентностью).
Для "максимальной случайности" у нас может быть поток, перебирающий случайный массив и записывающий в него новые случайные числа. Поток, использующий случайные числа, может генерировать случайный индекс для загрузки случайного числа. (Здесь есть некоторая предварительная работа, но микроархитектурно это помогает заранее определить адреса загрузки, поэтому любое возможное время задержки загрузки может быть решено до того, как потребуются загруженные данные.) Наличие устройства чтения и записи на разных ядрах приведет к неправильному упорядочиванию памяти -спекуляция конвейера очищается (как обсуждалось ранее для случая ложного обмена).
Для максимальной пессимизации зациклите ваш массив с шагом 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). Если дьявольская некомпетентность может оправдать двумерный массив с такими размерами, то реальная некомпетентность садового разнообразия легко оправдывает зацикливание с неправильным шаблоном доступа. Это происходит в реальном коде в реальной жизни.
При необходимости измените границы цикла, чтобы использовать много разных страниц вместо повторного использования одних и тех же нескольких страниц, если массив не такой большой. Аппаратная предварительная выборка не работает (также / вообще) на всех страницах. Устройство предварительной выборки может отслеживать один прямой и один обратный поток на каждой странице (что здесь происходит), но будет действовать на него, только если пропускная способность памяти еще не заполнена без предварительной выборки.
Это также приведет к большому количеству пропусков TLB, если только страницы не будут объединены в огромную страницу ( Linux делает это условно для анонимных (не поддерживаемых файлами) размещений, таких как malloc / new это использование mmap(MAP_ANONYMOUS)).
Вместо массива для хранения списка результатов вы можете использовать связанный список. Тогда каждая итерация будет требовать загрузки с указателем (реальная опасность зависимости RAW для адреса загрузки следующей загрузки). При плохом распределителе вам, возможно, удастся разбросать узлы списка в памяти, победив кеш. С дьявольски некомпетентным распределителем он может поместить каждый узел в начало своей собственной страницы. (например, выделить с mmap(MAP_ANONYMOUS) напрямую, без разбивки страниц или отслеживания размеров объектов для правильной поддержки free).
Они на самом деле не зависят от микроархитектуры и имеют мало общего с конвейером (большинство из них также будут замедлять работу нетранслируемого процессора).
Несколько не по теме: заставить компилятор генерировать худший код / делать больше работы:
Используйте C++11 std::atomic<int> а также std::atomic<double> для самого пессимального кода. MFENCEs и lock Инструкции ed довольно медленные, даже без конфликтов из другого потока.
-m32 сделает код медленнее, потому что код x87 будет хуже, чем код SSE2. Основанное на стеке 32-битное соглашение о вызовах требует больше инструкций и передает даже аргументы FP в стеке таким функциям, как exp(), atomic<uint64_t>::operator++ на -m32 требует lock cmpxchg8B петля (i586). (Так что используйте это для счетчиков циклов! [Злой смех]).
-march=i386 также будет пессимизировать (спасибо @Jesper). FP сравнивается с fcom медленнее, чем 686 fcomi, Pre-586 не предоставляет атомарного 64-битного хранилища (не говоря уже о cmpxchg), поэтому все 64-битные atomic ops компилируется в вызовы функций libgcc (которые, вероятно, скомпилированы для i686, а не фактически используют блокировку). Попробуйте это по ссылке на Godbolt Compiler Explorer в последнем абзаце.
использование long double / sqrtl / expl для дополнительной точности и медленности в ABI, где sizeof (long double) - 10 или 16 (с отступом для выравнивания). (IIRC, 64-битная Windows использует 8 байтов long double эквивалентно double, (В любом случае загрузка / сохранение 10-байтовых (80-битных) операндов FP составляет 4 / 7 мопов, по сравнению с float или же double беря только 1 моп каждый за fld m64/m32/ fst). Принудительно х87 с long double побеждает авто-векторизацию даже для gcc -m64 -march=haswell -O3,
Если не используется atomic<uint64_t> счетчики циклов, используйте long double для всего, включая счетчики циклов.
atomic<double> компилируется, но операции чтения-изменения-записи, такие как += не поддерживаются (даже на 64-битной). atomic<long double> должен вызывать библиотечную функцию только для атомарных загрузок / хранилищ. Это, вероятно, действительно неэффективно, потому что x86 ISA не поддерживает атомарные 10-байтовые загрузки / хранилища, и единственный способ, которым я могу думать без блокировки (cmpxchg16b) требуется 64-битный режим.
В -O0 разбиение большого выражения путем назначения частей временным переменным приведет к большему количеству хранилищ / перезагрузок. Без volatile или что-то еще, это не будет иметь значения с настройками оптимизации, которые будет использовать реальная сборка реального кода.
Правила псевдонимов позволяют char чтобы псевдоним ничего, так что хранение через char* заставляет компилятор хранить / перезагружать все до / после байтового хранилища, даже при -O3, (Это проблема для автоматического векторизации кода, который работает с массивом uint8_t, например.)
Пытаться uint16_t счетчики цикла для принудительного усечения до 16 бит, возможно, с использованием размера операнда 16 бит (потенциальные задержки) и / или дополнительного movzx инструкции (безопасно). Переполнение со знаком - неопределенное поведение, поэтому, если вы не используете -fwrapv или по крайней мере -fno-strict-overflow Счетчики циклов со знаком не требуют повторного расширения на каждой итерации, даже если они используются как смещения для 64-битных указателей.
Сила преобразования из целого числа в float и обратно И / или double <=> float преобразования. Инструкции имеют задержку больше единицы и скалярное int-> float (cvtsi2ss) плохо спроектирован, чтобы не обнулять остальную часть регистра xmm. (GCC вставляет дополнительный pxor по этой причине нарушать зависимости.)
Часто устанавливайте привязку вашего процессора к другому процессору (предложено @Egwor). дьявольские рассуждения: вы не хотите, чтобы одно ядро перегревалось при долгом запуске потока, не так ли? Возможно, переключение на другое ядро позволит этому ядру работать на более высокой тактовой частоте. (На самом деле: они настолько термически близки друг к другу, что это маловероятно, за исключением системы с несколькими разъемами). Теперь просто сделайте неправильную настройку и делайте это слишком часто. Помимо времени, потраченного на сохранение / восстановление состояния потока ОС, новое ядро имеет холодные кэши L2/L1, кэши UOP и предикторы ветвления.
Введение частых ненужных системных вызовов может замедлить вас, независимо от того, кто они. Хотя некоторые важные, но простые, такие как gettimeofday может быть реализовано в пользовательском пространстве без перехода в режим ядра. (glibc в Linux делает это с помощью ядра, так как ядро экспортирует код в vdso).
Для получения дополнительной информации о накладных расходах системных вызовов (включая пропуски кеша /TLB после возврата в пользовательское пространство, а не только самого переключения контекста), в документе FlexSC имеется отличный анализ текущей ситуации, а также предложение по пакетной системе. звонки от многопоточных серверных процессов.
Несколько вещей, которые вы можете сделать, чтобы все работало как можно хуже:
скомпилируйте код для архитектуры i386. Это предотвратит использование инструкций SSE и более новых инструкций и приведет к принудительному использованию FPU x87.
использование
std::atomicпеременные везде. Это сделает их очень дорогими из-за того, что компилятор вынужден вставлять барьеры памяти повсюду. И это то, что некомпетентный человек мог бы правдоподобно сделать, чтобы "обеспечить безопасность потока".Удостоверьтесь, что доступ к памяти наихудшим образом возможен для прогнозирования средством предварительной выборки (основной столбец или основной ряд).
чтобы сделать ваши переменные более дорогими, вы можете убедиться, что все они имеют "динамическую продолжительность хранения" (выделена куча), выделив их с помощью
newвместо того, чтобы позволить им иметь "автоматическую продолжительность хранения" (выделенный стек).убедитесь, что вся выделенная память очень странно выровнена, и во что бы то ни стало избегайте выделения огромных страниц, так как это слишком эффективно для TLB.
что бы вы ни делали, не создавайте свой код с включенным оптимизатором компиляторов. И убедитесь, что вы включили наиболее выразительные символы отладки, которые вы можете (не заставит код работать медленнее, но это потратит немного дополнительного дискового пространства).
Примечание. Этот ответ в основном просто суммирует мои комментарии, которые @Peter Cordes уже включил в свой очень хороший ответ. Предложите, чтобы он получил ваше мнение, если у вас есть только один запасной:)
Ты можешь использовать long double для расчета. На x86 это должен быть 80-битный формат. Только старая версия x87 FPU поддерживает это.
Несколько недостатков x87 FPU:
- Отсутствие SIMD, возможно, потребуется больше инструкций.
- На основе стека, проблематично для суперскалярных и конвейерных архитектур.
- Отдельный и довольно небольшой набор регистров, возможно, потребуется больше преобразования из других регистров и больше операций с памятью.
- На Core i7 есть 3 порта для SSE и только 2 для x87, процессор может выполнять меньше параллельных инструкций.
Поздний ответ, но я не чувствую, что мы злоупотребили связанными списками и TLB достаточно.
Используйте mmap для размещения ваших узлов, так что вы в основном используете MSB адреса. Это должно привести к появлению длинных цепочек поиска TLB, страница имеет 12 бит, оставляя 52 бита для перевода, или около 5 уровней, которые она должна проходить каждый раз. Если повезет, они должны каждый раз заходить в память для поиска 5 уровней и 1 доступа к памяти, чтобы добраться до вашего узла. Скорее всего, верхний уровень будет где-то в кеше, поэтому мы можем надеяться на 5* доступ к памяти. Поместите узел так, чтобы он проходил по наихудшей границе, чтобы чтение следующего указателя вызвало еще 3-4 поиска перевода. Это может также полностью разрушить кэш из-за огромного количества поисков перевода. Кроме того, размер виртуальных таблиц может привести к тому, что большая часть пользовательских данных будет выгружена на диск в течение дополнительного времени.
При чтении из единого связанного списка, убедитесь, что читаете с самого начала списка каждый раз, чтобы вызвать максимальную задержку при чтении одного числа.