Почему умножение происходит так же быстро, как сложение для значений двойного типа в C ++?

Question

#include<vector>
#include<iostream>
#include<random>
#include<chrono>

int main()
{
    int i;
    std::mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
    std::uniform_real_distribution<double> dist(0.5, 1);
    std::vector<double> q;
    int N = 100000000;
    for (i = 0; i < N; ++i) q.emplace_back(dist(rng));

    double sum = 0;

    auto start = std::chrono::steady_clock::now();
    for (i = 1; i < 100000000; ++i) {
        sum += q[i] + q[i - 1]; // change + to - or * or /, it takes same time.
    }

    auto end = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << std::endl;
    std::cout << sum << std::endl;

}

Сложение и вычитание должны быть простым процессом, может быть, некоторые сдвиги и побитовые операции, стоимость которых пропорциональна точности.

В то время как умножение и деление являются, естественно, более сложным процессом. Скажем, для умножения вполне естественно, что оно будет на несколько медленнее (что-то вроде O (n ^ 2), если сложение занимает O (n), так как умножение можно разбить на сложение сдвинутых значений). Для деления это должно быть еще сложнее.

Тем не менее для всех 4 арифметических операций, использующих значения двойного типа, этот код занимает ~ 110 мс с оптимизацией. Как это возможно? Что здесь происходит с магией, которая позволяет C ++ обрабатывать умножение так же быстро, как сложение, ... или обрабатывать сложение так же медленно, как умножение?

пс для целых чисел, это занимает ~ два раза, только для деления. *

Answer 1

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

• Разработчики аппаратного обеспечения установили множество логических элементов в модулях с плавающей запятой.
• Инструкции могут быть разделены на несколько этапов, которые выполняются в конвейере. Например, умножение может выполнять часть своей работы в блоке M0, а затем передавать результаты в блок M1, который выполняет другую часть, затем M2, затем M3. Пока M1 работает со своей стороны, M0 может начать работу с другим умножением. При таком расположении умножение может фактически занять четыре такта процессора для завершения, но, поскольку четыре блока работают на четырех этапах, процессор может завершать одно умножение каждый цикл. Напротив, более простая инструкция, такая как XOR, имеет только одну стадию.
• Хотя некоторые инструкции могут быть выполнены быстро, а некоторые требуют большего времени, весь процессор синхронизируется с помощью часов, и каждый этап конвейера в каждом исполнительном блоке имеетзавершить свою работу в один такт. Это налагает некоторую жесткость на дизайн процессора - некоторые простые операции завершат свою работу до окончания тактового цикла, в то время как сложные операции требуют полного цикла. Дизайнеры принимают решение о том, как долго делать тактовый цикл. Если тактовый цикл слишком короткий (относительно скорости, с которой работают логические элементы), тогда для многих команд требуется несколько циклов и могут потребоваться дополнительные издержки для их управления. Если тактовый цикл слишком длинный, то время тратится впустую, ожидая инструкций, которые могли бы завершиться раньше. В современной процессорной технологии распространено, что ступени умножителя с плавающей запятой хорошо работают с временем цикла процессора.

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

Однако, соблюдайте выражение, которое вы используете:

sum += q[i] + q[i - 1];

Это приводит к последовательной зависимости sum от его предыдущего значения. Процессор может добавить q[i] к q[i-1], не дожидаясь предшествующего добавления, но затем, чтобы добавить к sum, он должен дождаться завершения предыдущего добавления к sum. Это означает, что, если процессор имеет два дополнительных блока, он может одновременно работать как с q[i] + q[i-1], так и с предыдущим добавлением к sum. Но, если бы у него было больше дополнительных единиц, он не мог бы двигаться быстрее. Он может использовать дополнительные единицы, чтобы сделать больше этих q[i] + q[i - 1] дополнений для различных значений i, но каждое добавление к sum должно ждать предыдущего. Следовательно, с двумя или более единицами сложения это вычисление зависит от задержки сложения, то есть того, сколько времени требуется для одного сложения. (Это в отличие от пропускной способности сложения, то есть того, сколько сложений процессор может сделать за единицу времени, если нет последовательной зависимости.)

Если вы использовали другойвычислений, таких как sum += q[i]; или sum0 += q[i]; sum1 += q[i+1]; sum2 += q[i+2]; sum3 += q[i+3];, тогда вы могли видеть различное время сложения и умножения, которое зависело от того, сколько единиц сложения и сколько умножителей было у процессора.