Введение в основную проблему
[Пожалуйста, прокрутите вниз до «Фактическая проблема (stackoverflow)», если вы просто хотите увидеть, с чем у меня проблема]
Рассмотрим следующий код цикла задержки:
using clock_type = std::chrono::steady_clock;
std::atomic<uint64_t> m_word;
constexpr uint64_t tokens_mask = 0xffffffff;
double measure_delay_loop_in_ms(int delay_loop_size, int inner_loop_size)
{
auto start = clock_type::now();
// The actual delay loop under test.
for (int i = delay_loop_size; i != 0; --i)
{
if ((m_word.load(std::memory_order_relaxed) & tokens_mask) != 0)
break;
for (int j = inner_loop_size; j != 0; --j)
asm volatile ("");
}
// End of actual delay loop test code.
auto stop = clock_type::now();
return std::chrono::duration<double, std::milli>(stop - start).count();
}
, где m_word - это std::atomic<uint64_t>, равное нулю на протяжении всей продолжительности теста: break никогда не выполняется. tokens_mask - это constexpr uint64_t с установленными младшими 32 битами. Не то чтобы этот точный выбор кода был актуален для этого вопроса;это просто выбор, который я сделал.
Полученный код сборки, например, (здесь используется g ++ 8.3.0 и -O2):
.L5:
mov rax, QWORD PTR m_word[rip] // m_word & tokens_mask
test eax, eax // != 0
jne .L2 // break;
test ebp, ebp // inner_loop_size
je .L3 // != 0
mov eax, ebp // j = inner_loop_size
.L4:
sub eax, 1 // --j
jne .L4 // j != 0
.L3:
sub ebx, 1 // --i
jne .L5 // i != 0
.L2:
Время, когда этот циклвыполнение зависит от многих вещей:
1) значений delay_loop_size и inner_loop_size.
2) аппаратного обеспечения, на котором оно работает (например, частота процессора).
3) используемого компилятора / оптимизации.
4) недавняя история ЦП (например, кэш и конвейер выполнения).
5) была ли прервана петля задержки во время работы.
Из-за пунктов 2) и 3) Я хочу откалибровать контур задержки в начале программы, иначе во время выполнения.
Требуется хорошая оценка задержки как функции delay_loop_size и inner_loop_size с линейной аппроксимацией.
То есть нам нужна функция
double delay_estimate_in_ms(int delay_loop_size, int inner_loop_size)
{
return offset + delay_loop_size * (alpha + beta * inner_loop_size);
}
, где необходимо определить двойные offset, alpha и beta в начале программы, выполняя измерения сmeasure_delay_loop_in_ms.
что это приближение хорошееэто следует из того факта, что я не интересуюсь выбросами в результате пункта 5). Затем, предполагая, что отклонения в результате пункта 4) усредняются, то есть можно считать нормальным «шумом», вполне вероятно, что число (средних) тактовых циклов будет линейным в inner_loop_size для фиксированных delay_loop_size. Аналогично, число средних тактовых циклов будет линейным в delay_loop_size, когда мы сохраняем inner_loop_size fixed. Затем это приводит к приведенной выше формуле.
Если предположить, что точное измерение, мы можем найти offset, установив delay_loop_size и inner_loop_size в ноль, а затем найти альфа и бета с двумябольше измерений:
offset = measure_delay_loop_in_ms(0, 0);
alpha = (measure_delay_loop_in_ms(10000, 0) - offset) / 10000;
beta = ((measure_delay_loop_in_ms(10000, 10000) - offset) / 10000 - alpha) / 10000;
Это не будет работать по понятным причинам. По крайней мере, мы должны были бы сделать много измерений каждого, чтобы избавиться от выбросов и взять некоторое среднее значение. Тогда это просто неправильный способ найти лучшее линейное соответствие. И, наконец, поскольку неизвестно, сколько времени занимает каждый цикл задержки, для определения бета-версии таким способом может потребоваться много времени (то есть эти значения 10000 являются произвольными и могут быть не очень практичными, если вы хотите провести быструю калибровку наначало каждого запуска программы). Наконец, немыслимо, что наша оценка линейности верна только как хорошее приближение к нормальным значениям, то есть значениям, которые мы будем использовать в конечном итоге.
Поэтому необходимо учитывать следующее:
- Цикл задержки должен быть настроен примерно на 1 мс (или на любое другое значение, которое вы пожелаете, но сочтите его фиксированным; после этого мы можем выяснить, зависят ли смещение, альфа и бета от этого или нет).
- delay_loop_size должен быть между 10000 и 100000, если это вообще возможно (если нет, тогда установите inner_loop_size в ноль и просто найдите наилучшее соответствие). Если возможно, inner_loop должен быть больше 10, для значений больше 10 предпочтительно иметь больший delay_loop_size.
У меня есть причины для этого, но они выходят за рамки этого вопроса (этоимеет отношение к состязанию шины и времени отклика, чтобы разбудить этот поток счетчика, изменив m_word).
Вышеприведенное приведено в следующей стратегии, чтобы найти оптимальные значения delay_loop_size и inner_loop_size:
- Установите inner_loop_size равным 10 и найдите хорошее линейное соответствие как функцию
delay_loop_size с высокой точностью около 1 мс. - Убедитесь, что это приводит к значению
delay_loop_size между 10000 и 100000. Если это так, то бета можно определить тривиально по (достаточному) количеству измерений с этим фиксированным значением delay_loop_size и значениями inner_loop_size из 9, 10. и 11. Итак, предположим, что мы сделали. delay_loop_size меньше 10000, исправьте его на 10000 и найдите хорошее линейное приближение для inner_loop_size (теперь мы будем меньше 10, так что вы можете даже просто выполнить быстрый двоичный поиск по этим немногимценности). - Если
delay_loop_size превышает 100000, то установите его на 100000 и найдите хорошее линейное приближение для задержки как функцию inner_loop_size с высокой точностью около 1 мс. Затем зафиксируйте inner_loop_size в соответствующем значении в течение 1 мс, но округлите и найдите хорошее линейное приближение для задержки как функцию delay_loop_size в районе 1 мс. - Рассчитать смещение, альфа и бета из ранее найденных линейных приближений.
Важной частью этой стратегии является найти хорошее линейное приближение для x около y .
Актуальная проблема (stackoverflow)
Следовательно, представьте, что нам дана константа goal.
double const goal = 1.0; // 1.0 is just an example.
И функция measure(int x).
double measure(int x);
Избегайте вызова measure для произвольногозначения x, поскольку большее значение x приводит к более длительным задержкам. Однако нам нужно найти значение x, чтобы measure(x) возвращало значение как можно ближе к goal, насколько это возможно в большинстве случаев времени. Иногда measure возвращает произвольное большое значение, но можно предположить, что это происходит менее чем в 1% случаев. Если это произойдет, можно предположить, что эти измерения могут быть распознаны по тому факту, что они лежат вне диапазона 2 сигма. Следовательно, нам нужно найти наилучшее линейное соответствие для measure как функцию x вокруг goal, включая сигму (предполагаемых) нормальных распределенных значений, игнорируя те значения, которые лежат слишком далеко над этой линией.
Обратите внимание, что на самом деле это НЕ нормальное распределение - и на самом деле все, что приближается к «спреду», достаточно хорошо - до тех пор, пока оно хорошо обнаруживает выбросы. Я бы предпочел провести линию просто через «центр масс» измерений, а именно: чем дальше от среднего значения, тем менее интересны они (чем меньше веса следует применять). Точки под линией можно измерить на предмет ошибки, взяв их расстояние до линии (в отличие от обычного квадрата), то же самое для точек над линией, но затем с некоторыми отсечками, когда они полностью отбрасываются.
В этом случае нормального распределения нет, поэтому и сигма отсутствует. Можно просто написать программу, которая возвращает значения a и b, так что y = a * x + b является хорошим приближением и предельным значением.
Это может быть катастрофой, если даже один выброс используется дляоднако оцените линейное приближение;простое игнорирование первых 10% измерений не сработает (я хотел бы быть на 99,999999% уверенным, что аппроксимация верна с точностью до коэффициента 2, и использование одного случайного выброса может привести к этому).
Дополнительная проблема заключается в том, что я не совсем уверен в том, насколько линейными будут реальные измерения (хотя я думаю, что они должны быть). Определенная проблема, однако, заключается в том, что, когда по очевидным причинам можно выполнить несколько измерений далеко от цели, но означает ли это, что мы также должны игнорировать измерения, которые находятся далеко от цели? Вероятно, нет - возможно, было бы более полезно иметь приближение, которое работает в более широком диапазоне, чем то, которое является более точным в отношении цели ... Тем не менее, я действительно хотел бы иметь измерения по обе стороны от цели;).
Как написать этот калибровочный код?
РЕДАКТИРОВАТЬ
Вот изображение подхода, подобного RANSAC, в котором все цветные точки, отмеченные как «errXYZ», были удаленыодин за другим (начиная с err0 .. err27) как «выбросы».
Но есть и такой вид измерения:
Хорошо, я закончил с моим алгоритмом ... Случай, подобный приведенному выше, теперь обрабатывается так:
Как вы можетевидите, это соответствует линии для случая петли с более быстрой задержкой (оранжевые ромбы), игнорируя при этом одно быстрое (???) измерение SUPER за 0,4 мс с размером петли 50000 (черный треугольник). Большинство точек были проигнорированы одна за другой, потому что они в одиночку слишком сильно сместили наклон OLS, но (много) зеленых X были обрезаны по другой причине;они были частью натянутой линии вместе с оранжевыми алмазами, но оранжевый алмаз лежал более чем на 2% (по уклону) ниже этой натянутой линии! В этом случае я обрезаю все точки, которые более чем на 2% выше линии (и устанавливаю новую линию).