Я целую неделю ломал голову, пытаясь выполнить это задание, и я надеюсь, что кто-то здесь может привести меня к правильному пути. Позвольте мне начать с инструкций инструктора:
Ваше задание противоположно нашему первому лабораторному заданию, которое должно было оптимизировать программу простых чисел. Ваша цель в этом задании - пессимизировать программу, то есть заставить ее работать медленнее. Обе программы загружают процессор. На наших лабораторных ПК им требуется несколько секунд. Вы не можете изменить алгоритм.
Чтобы деоптимизировать программу, используйте свои знания о том, как работает конвейер 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 ++ медленным в целом.
источник
while(true){}
Ответы:
Важная справочная информация: микроарх pdf Агнера Фога и, вероятно, также Ульрих Дреппер, что каждый программист должен знать о памяти . Смотрите также другие ссылки вx86tag wiki, особенно руководства по оптимизации 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
или функция времени, которая делает системный вызов. Инструкции по сериализации по своей сути являются недружественными.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
инструкций ed - это обычно ошибка. Было бы интересно сравнить неатомарный счетчик общего цикла с атомарным случаем. Чтобы по-настоящему пессимизировать, сохраняйте счетчик общего атомарного цикла и вызывайте ложное совместное использование в той же или другой строке кэша для некоторой другой переменной.Случайные уарх-специфические идеи:
Если вы можете ввести какие-либо непредсказуемые ветки , это существенно снизит код. Современные процессоры 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()
это. : 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 для точных чисел и деталей. Это маловероятно, поскольку у вас много множителей, поэтому коэффициент масштабирования будет возведен в квадрат и уменьшен до 0,0. Я не вижу способа оправдать необходимое масштабирование некомпетентностью (даже дьявольской), только преднамеренной злобой.
Если вы можете использовать intrinsics (
<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
для установки следующего векторного элемента в качестве аргумента forexp
, также будет остановлена. И затем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
s вместо пары longnop
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 удваивается). например
Таким образом, шаблон доступа: 0, 4096, 8192, ...,
8, 4104, 8200, ...
16, 4112, 8208, ...
Это то, что вы получили бы за доступ к двумерному массиву, как
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>
для самого пессимального кода. MFENCE иlock
инструкции ed довольно медленные, даже без конфликтов из другого потока.-m32
сделает код медленнее, потому что код x87 будет хуже, чем код SSE2. Основанное на стеке 32-битное соглашение о вызовах принимает больше инструкций и передает даже аргументы FP в стеке таким функциям, какexp()
.atomic<uint64_t>::operator++
на-m32
требуетlock cmpxchg8B
петли (i586). (Так что используйте это для счетчиков циклов! [Злой смех]).-march=i386
также будет пессимизировать (спасибо @Jesper). FP сравниваетсяfcom
медленнее, чем 686fcomi
. Pre-586 не предоставляет атомарного 64-битного хранилища (не говоря уже о cmpxchg), поэтому все 64-atomic
битные операции компилируются в вызовы функций 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
). Форсирование x87 сlong double
автоматическим векторизацией побеждает даже для GCC-m64 -march=haswell -O3
.Если
atomic<uint64_t>
счетчики циклов не используются , используйте ихlong double
для всего, включая счетчики циклов.atomic<double>
компилируется, но подобные операции чтения-изменения-записи+=
не поддерживаются (даже на 64-битной версии).atomic<long double>
должен вызывать библиотечную функцию только для атомарных загрузок / хранилищ. Вероятно, это действительно неэффективно, потому что x86 ISA не поддерживает атомные 10-байтовые загрузки / хранилища , и единственный способ, которым я могу придумать без lock (cmpxchg16b
), - это 64-битный режим.Если
-O0
разбить большое выражение, присваивая части временным переменным, это приведет к большему количеству хранилищ / перезагрузок. Безvolatile
или что-то, это не будет иметь значения с настройками оптимизации, которые будет использовать реальная сборка реального кода.Правила
char
псевдонимов позволяют a псевдониму чего угодно, поэтому при хранении с помощьюchar*
компилятора все элементы сохраняются / перезагружаются до / после байтового хранилища, даже в-O3
. (Это проблема для автоматической векторизации кода, который работаетuint8_t
, например, с массивом .)Попробуйте
uint16_t
счетчики циклов для принудительного усечения до 16 бит, возможно, используя 16-битный размер операнда (потенциальные задержки) и / или дополнительныеmovzx
инструкции (безопасно). Переполнение со знаком является неопределенным поведением , поэтому, если вы не используете-fwrapv
или, по крайней мере-fno-strict-overflow
, счетчики циклов со знаком не должны повторно расширяться при каждой итерации , даже если они используются как смещения для 64-битных указателей.Принудительное преобразование из целого числа в
float
и обратно. И / илиdouble
<=>float
конверсии. Команды имеют задержку больше единицы, и скалярная функция int-> float (cvtsi2ss
) плохо спроектирована так, чтобы не обнулять остальную часть регистра xmm. (Поpxor
этой причине gcc вставляет дополнительные для разрыва зависимостей.)Часто устанавливайте привязку вашего процессора к другому процессору (предложено @Egwor). дьявольские рассуждения: вы не хотите, чтобы одно ядро перегревалось при долгом запуске потока, не так ли? Возможно, переключение на другое ядро позволит этому ядру работать на более высокой тактовой частоте. (На самом деле: они настолько термически близки друг к другу, что это маловероятно, за исключением системы с несколькими разъемами). Теперь просто сделайте неправильную настройку и делайте это слишком часто. Помимо времени, потраченного на сохранение / восстановление состояния потока ОС, новое ядро имеет холодные кэши L2 / L1, кэши UOP и предикторы ветвления.
Введение частых ненужных системных вызовов может замедлить вас, независимо от того, кто они. Хотя некоторые важные, но простые, например,
gettimeofday
могут быть реализованы в пользовательском пространстве без перехода в режим ядра. (glibc в Linux делает это с помощью ядра, поскольку ядро экспортирует код вvdso
).Для получения дополнительной информации о накладных расходах системных вызовов (включая пропуски кэша / TLB после возврата в пользовательское пространство, а не только самого переключения контекста), в документе FlexSC представлен отличный анализ текущей ситуации, а также предложение по пакетной системе. звонки от массовых многопоточных серверных процессов.
источник
exp(T*(r-0.5*v*v))
становленияexp(T*r - T*v*v/2.0)
;exp(sqrt(v*v*T)*gauss_bm)
становленияexp(sqrt(v)*sqrt(v)*sqrt(T)*gauss_bm)
). Ассоциативность (и обобщение) также может преобразовыватьсяexp(T*r - T*v*v/2.0)
в `pow ((pow (e_value, T), r) / pow (pow (pow ((pow (e_value, T), v), v)), - 2.0) [или что-то еще . как это] Такие математические приемы на самом деле не считаются микроархитектурой deoptimizations.Несколько вещей, которые вы можете сделать, чтобы все работало как можно хуже:
скомпилируйте код для архитектуры i386. Это предотвратит использование инструкций SSE и более новых инструкций и приведет к принудительному использованию x87 FPU.
std::atomic
везде используйте переменные. Это сделает их очень дорогими из-за того, что компилятор вынужден вставлять барьеры памяти повсюду. И это то, что некомпетентный человек мог бы правдоподобно сделать, чтобы «обеспечить безопасность потоков».Удостоверьтесь, что доступ к памяти наихудшим образом возможен для прогнозирования средством предварительной выборки (основной столбец или основной ряд).
чтобы сделать ваши переменные более дорогими, вы можете убедиться, что у всех них есть «динамическая продолжительность хранения» (выделена куча),
new
вместо того, чтобы дать им «автоматическую продолжительность хранения» (выделен стек).убедитесь, что вся выделенная память очень странно выровнена, и во что бы то ни стало избегайте выделять огромные страницы, так как это слишком эффективно для TLB.
что бы вы ни делали, не создавайте свой код с включенным оптимизатором компиляторов. И убедитесь, что вы включили наиболее выразительные символы отладки, которые вы можете (не заставит код работать медленнее, но это потратит дополнительное дисковое пространство).
Примечание. Этот ответ в основном просто суммирует мои комментарии, которые @Peter Cordes уже включил в свой очень хороший ответ. Предложите, чтобы он получил ваше мнение, если у вас есть только один запасной :)
источник
std::atomic
, или дополнительный уровень косвенности от динамического распределения. Они собираются быть медленными на Атоме или K8 также. Все еще голосую, но именно поэтому я сопротивлялся некоторым вашим предложениям.movapd xmm, xmm
обычно не требуется порт выполнения (он обрабатывается на этапе переименования регистра в IVB и более поздних версиях). Это также почти никогда не требуется в коде AVX, потому что все, кроме FMA, неразрушающее. Но, честно говоря, Haswell запускает его на порту 5, если он не устранен. Я не смотрел на x87 register-copy (fld st(i)
), но вы подходите для Haswell / Broadwell: он работает на p01. Skylake запускает его на p05, SnB запускает на p0, IvB запускает на p5. Таким образом, IVB / SKL делает некоторые вещи x87 (включая сравнение) на p5, но SNB / HSW / BDW вообще не использует p5 для x87.Вы можете использовать
long double
для расчетов. На x86 это должен быть 80-битный формат. Только старая версия x87 FPU поддерживает это.Несколько недостатков x87 FPU:
источник
fxch
). С-ffast-math
, хороший компилятор может векторизации петли методом Монте-Карло, хотя и x87 бы предотвратить.mulss
на p01, ноfmul
только наp0
.addss
только работаетp1
, так же, какfadd
. Есть только два исполнительных порта, которые обрабатывают математические операции FP. (Единственное исключение из этого - то, что Skylake отбросил выделенный блок добавления и работаетaddss
в блоках FMA на p01, ноfadd
на p5. Поэтому, смешивая некоторыеfadd
инструкции сfma...ps
, вы теоретически можете сделать чуть больше общего FLOP / с.)long double
, то есть это все-таки простоdouble
. А вот SysV ABI использует 80 битlong double
. Кроме того, переименование регистров re: 2: выставляет параллелизм в регистрах стека. Архитектура на основе стека требует некоторых дополнительных инструкций, напримерfxchg
, esp. при чередовании параллельных вычислений. Так что больше похоже на то, что трудно выразить параллелизм без обходов памяти, а не на то, чтобы уарху было трудно использовать то, что там есть. Вам не нужно больше преобразования из других рег, хотя. Не уверен, что вы подразумеваете под этим.Поздний ответ, но я не чувствую, что мы злоупотребили связанными списками и TLB достаточно.
Используйте mmap для выделения ваших узлов, так что вы в основном используете MSB адреса. Это должно привести к появлению длинных цепочек поиска TLB: страница имеет 12 бит, оставляя 52 бита для перевода, или около 5 уровней, которые она должна проходить каждый раз. Если повезет, они должны каждый раз заходить в память для поиска 5 уровней и 1 доступа к памяти, чтобы добраться до вашего узла, верхний уровень, скорее всего, будет где-то в кеше, поэтому мы можем надеяться на 5 * доступ к памяти. Поместите узел так, чтобы он проходил по наихудшей границе, чтобы чтение следующего указателя вызвало еще 3-4 поиска перевода. Это также может полностью разрушить кэш из-за огромного количества поисков перевода. Кроме того, размер виртуальных таблиц может привести к тому, что большая часть пользовательских данных будет выгружена на диск в течение дополнительного времени.
При чтении из единственного связанного списка, убедитесь, что читаете с начала списка каждый раз, чтобы вызвать максимальную задержку при чтении одного числа.
источник
mmap
файл или область общей памяти, чтобы получить несколько виртуальных адресов для одной и той же физической страницы (с одним и тем же содержимым), что позволяет пропускать больше TLB при том же объеме физической памяти. Если ваш связанный списокnext
был просто относительным смещением , вы можете иметь серию отображений одной и той же страницы с,+4096 * 1024
пока вы, наконец, не перейдете на другую физическую страницу. Или, конечно, охватывая несколько страниц, чтобы избежать попаданий в кэш L1d. Существует кэширование PDE более высокого уровня в оборудовании для перемещения по страницам, так что да, распределите его в виртуальном пространстве addr![reg+small_offset]
режима адресации] ( Есть ли штраф, когда base + offset находится на другой странице, чем base? ); вы либо получите источникadd
памяти с 64-битным смещением, либо получите нагрузку и режим индексированной адресации, например[reg+reg]
. Также смотрите Что происходит после пропуска L2 TLB? - просмотр страниц через L1d-кеш на SnB-семействе.