Я пришел в эту тему, чтобы получить представление о том, что современные процессоры делают в отношении целочисленной математики и количества циклов, необходимых для их выполнения. Я работал над проблемой ускорения операций умножения и деления 32-битных целых чисел на процессоре 65c816 в 1990-х годах. Используя описанный ниже метод, я смог утроить скорость стандартных математических библиотек, доступных в то время в компиляторах ORCA/M.
Таким образом, идея о том, что умножение быстрее, чем добавление, просто не соответствует действительности (за исключением редких случаев), но, как говорили люди, это зависит от того, как реализована архитектура. Если между тактовыми циклами выполняется достаточное количество шагов, да, умножение может фактически иметь ту же скорость, что и сложение, основанное на тактах, но будет много потраченного времени. В этом случае было бы неплохо иметь инструкцию, которая выполняет несколько (зависимых) сложений/вычитаний с учетом одной инструкции и нескольких значений. Можно мечтать.
На процессоре 65c816 не было инструкций умножения или деления. Mult и Div были выполнены со сдвигами и добавлениями.
Чтобы выполнить 16-битное добавление, вы должны сделать следующее:
LDA $0000 - loaded a value into the Accumulator (5 cycles)
ADC $0002 - add with carry (5 cycles)
STA $0004 - store the value in the Accumulator back to memory (5 cycles)
15 cycles total for an add
Если вы имеете дело с вызовом, подобным из C, у вас будут дополнительные накладные расходы, связанные с проталкиванием и извлечением значений из стека. Например, создание подпрограмм, которые выполняли бы два умножения одновременно, сэкономило бы накладные расходы.
Традиционный способ выполнения умножения - это сдвиг и сложение всего значения одного числа. Каждый раз, когда перенос становится единицей, поскольку он смещается влево, это означает, что вам нужно снова добавить значение. Это требовало проверки каждого бита и сдвига результата.
Я заменил это таблицей поиска из 256 элементов, чтобы не нужно было проверять биты переноса. Также можно было определить переполнение перед выполнением умножения, чтобы не терять время. (На современном процессоре это можно сделать параллельно, но я не знаю, делают ли они это аппаратно). Учитывая два 32-битных числа и предварительно экранированное переполнение, один из множителей всегда равен 16 битам или меньше, поэтому для выполнения всего 32-битного умножения достаточно один или два раза выполнить 8-битное умножение. Результатом этого стало умножение в 3 раза быстрее.
скорость 16-битного умножения варьировалась от 12 до примерно 37 тактов.
multiply by 2 (0000 0010)
LDA $0000 - loaded a value into the Accumulator (5 cycles).
ASL - shift left (2 cycles).
STA $0004 - store the value in the Accumulator back to memory (5 cycles).
12 cycles plus call overhead.
multiply by (0101 1010)
LDA $0000 - loaded a value into the Accumulator (5 cycles)
ASL - shift left (2 cycles)
ASL - shift left (2 cycles)
ADC $0000 - add with carry for next bit (5 cycles)
ASL - shift left (2 cycles)
ADC $0000 - add with carry for next bit (5 cycles)
ASL - shift left (2 cycles)
ASL - shift left (2 cycles)
ADC $0000 - add with carry for next bit (5 cycles)
ASL - shift left (2 cycles)
STA $0004 - store the value in the Accumulator back to memory (5 cycles)
37 cycles plus call overhead
Поскольку шина данных AppleIIgs, для которой это было написано, имела ширину всего 8 бит, для загрузки 16-битных значений требовалось 5 циклов для загрузки из памяти, один дополнительный для указателя и один дополнительный цикл для второго байта.
Инструкция LDA (1 цикл, так как это 8-битное значение) $0000 (для загрузки 16-битного значения требуется два цикла) ячейка памяти (для загрузки требуется два цикла из-за 8-битной шины данных)
Современные процессоры могли бы сделать это быстрее, потому что у них в худшем случае 32-битная шина данных. В самой логике процессора система вентилей вообще не имела бы дополнительной задержки по сравнению с задержкой шины данных, так как все значение загружалось бы сразу.
Чтобы выполнить полное 32-битное умножение, вам нужно будет сделать это дважды и сложить результаты вместе, чтобы получить окончательный ответ. Современные процессоры должны иметь возможность выполнять эти два задания параллельно и добавлять результаты к ответу. В сочетании с предварительной проверкой переполнения, выполняемой параллельно, это минимизирует время, необходимое для выполнения умножения.
В любом случае, очевидно, что умножение требует значительно больше усилий, чем добавление. Сколько шагов для обработки операции между тактовыми циклами процессора будет определять, сколько тактовых циклов потребуется. Если часы достаточно медленные, то сложения будут иметь ту же скорость, что и умножение.
С уважением, Кен
person
Kenneth C Richardson
schedule
18.11.2019
std::push_heapи т. д.), чтобы я мог обрабатывать элементы в порядке приоритета. У меня закончились идеи, чтобы сделать его быстрее; мне потребовалось много попыток отладки/профилирования, чтобы выяснить причину, и я остался чесать голову, когда увидел инструкциюimul, которую я не ожидал. Я знаю, это удивительно, но моя задача была чертовски типичной, и это вычитание указателя в куче действительно было узким местом. - person user541686 schedule 17.02.2014