Какая архитектура процессора лучше всего подходит для арифметики biginteger? - PullRequest
1 голос
/ 09 сентября 2011

Если бы я писал код на ассемблере для больших целочисленных вычислений (например, простого факторинга, вычислений по модулю и т. Д.) С акцентом на скорость, какая архитектура лучше всего подходит для этого: x86 (-64), ARM, PowerPC,MIPS или другие?

Ответы [ 2 ]

1 голос
/ 01 мая 2019

IMO ничто не сравнится с x86-64, потому что никто больше не заботится о арифметике с более высокой точностью

Многие архитектуры RISC, такие как MIPS, DEC Alpha или RISC-V, не имеютОтметьте регистр, поэтому вам понадобится отдельная инструкция для переноса.Поэтому они являются плохим выбором и устранены сразу же.Например, чтобы сделать a += b в MIPS, вам нужно

addu aLow, aLow, bLow     # aLow += bLow
sltu tmp, aLow, bLow      # carry: tmp = (aLow < bLow)
addu aHigh, aHigh, bHigh  # aHigh += bHigh
addu aHigh, aHigh, tmp    # aHigh += carry

. С флагом переноса вам понадобятся только 2 инструкции: add aLow, bLow; adc aHigh, bHigh

Дизайнеры MIPS могли бы сделать это лучше, но они не

Более высокие тактовые частоты помогают, как Марко ван де Воорт сказал , но эти архитектуры не имеют на 50% -100% более быстрых тактовых импульсов, чем эквивалентный x86.Остальные вещи, которые он сказал, довольно неверны.Важно отметить, что математика произвольной точности не тривиально распараллеливается, поэтому

Короче говоря: Вы действительно хотитерассчитать переносы параллельно , что очень сложно


В мире x86 у вас уже есть флаг переноса с самого начала.Но позже Intel представила набор команд ADX с новыми инструкциями ADOX, ADCX и MULX для еще большего ускорения арифметики больших целых чисел.Как они помогают, объясняется в статье Intel Новые инструкции по поддержке большой целочисленной арифметики на процессорах архитектуры Intel

Но не только ADX обеспечивает скорость x86.Как я упоминал ранее (), SIMD не очень помогает, но в настоящее время на x86 все может быть иначе.У нас есть очень длинные векторы в x86 (256 бит с AVX2, 512 бит с AVX512 и, возможно, больше в будущем), поэтому, если вы используете различные приемы, такие как использование арифметики с частичными словами для задержки распространения переноса, илирасположите слова странным образом (например, llhhllhhllhhllhh) вместо линейного, как в обычной большой целочисленной арифметике (llllllllhhhhhhhh), тогда SIMD может быть быстрее, чем скалярные операции.Для получения дополнительной информации вы должны прочитать

Конечно, AVX512 поможет, только если у вас очень большие числа .В противном случае для 512-битного числа вы можете получить лучшие результаты со скалярным кодом

Ни одна другая архитектура в настоящее время не имеет регистров SIMD длиннее 128 бит, поэтому, даже если вы можете использовать SIMD на них, стоимость вычисленияперенос будет намного перевешивать стоимость параллельного сложения.Опять же, это причина, по которой x86 побеждает их всех

1 голос
/ 13 сентября 2011

Если вы работаете с небольшим числом чисел переменного размера, я думаю, что POWER 6 подойдет вам лучше всего (хотя я не работал с этой архитектурой), поскольку она обеспечивает высокую IPC и очень высокую частоту (до 5 ГГц) .

Если вы работаете с большим числом чисел фиксированного размера, x86-64 будет лучшим выбором, поскольку он имеет SIMD-операции, которые работают с 64-битными числами, и вы можете использовать эти операции для ускорения длинных арифметических операций на несколько номеров. Скорее всего, вам понадобится процессор с поддержкой SSE 4.2 (Intel Nehalem / Westmere / Sandy Bridge или грядущий AMD Bulldozer), поскольку инструкция 64-битного сравнения PCMPGTQ была добавлена ​​только в SSE 4.2

Кроме того, эти результаты теста GMP могут быть интересны для вас

...