Ускорение цикла ADID для ассемблера x64

Я работаю над арифметикой для умножения очень длинных целых чисел (около 100 000 десятичных цифр). В рамках моей библиотеки я добавлю два длинных номера.

Профилирование показывает, что мой код работает до 25% его времени в подпрограммах add() и sub(), поэтому важно, чтобы они были как можно быстрее. Но я пока не вижу большого потенциала. Может быть, вы можете дать мне помощь, советы, идеи или идеи. Я проверю их и вернусь к вам.

До сих пор моя программа добавления выполняет некоторую настройку, а затем использует 8-разный развернутый цикл:

mov rax, QWORD PTR [rdx+r11*8-64]
mov r10, QWORD PTR [r8+r11*8-64]
adc rax, r10
mov QWORD PTR [rcx+r11*8-64], rax

Далее следуют еще несколько блоков с разными смещениями, а затем они петли.

Я попытался загрузить значения из памяти ранее, но это не помогло. Я думаю, это из-за хорошей предварительной выборки. Я использую четырехъядерный процессор Intel I7-3770 Ivy Bridge. Но я бы хотел написать код, который хорошо работает на любом современном процессоре.

Изменить. Я сделал несколько таймингов: он добавляет 1k слов примерно в 2,25 цикла/слова. Если я удалю АЦП, останутся только MOV, все равно потребуется около 1,95 цикла/слова. Таким образом, основным узким местом является доступ к памяти. Библиотека memcpy() работает примерно в 0.65 циклах/словах, но имеет только один вход, а не два. Тем не менее, это намного быстрее из-за использования регистров SSE, я думаю.

Некоторые вопросы:

Полезно ли использовать структуру "загрузить, загрузить, добавить, сохранить" или "загрузить, добавить в память"? Пока мои тесты не показали никаких преимуществ.
Как обычно, от SSE (2,3,4) не ожидается никакой поддержки?
Не влияет ли адресация (масштабированный индекс плюс базовая плюс смещение)? Вместо этого я мог бы использовать ADD r11, 8.
Как насчет разворота цикла? Я читал, что разворачивание было плохо для архитектуры Sandy Bridge (Agner Fog http://www.agner.org/optimize/). Это должно быть предпочтительным или избегать?
(Изменить) Могу ли я использовать регистры SSE для загрузки и хранения слов в больших кусках из памяти и эффективного обмена словами с регистрами общего назначения и SSE-регистрами?

Я высоко ценю любые комментарии.

Ответ 1

Я уверен, что memcpy работает быстрее, потому что у него нет зависимости от данных, которые будут извлечены, прежде чем он сможет выполнить следующую операцию.

Если вы можете разместить свой код так, чтобы он сделал что-то вроде этого:

mov rax, QWORD PTR [rdx+r11*8-64]
mov rbx, QWORD PTR [rdx+r11*8-56]
mov r10, QWORD PTR [r8+r11*8-64]
mov r12, QWORD PTR [r8+r11*8-56]
adc rax, r10
adc rbx, r12
mov QWORD PTR [rcx+r11*8-64], rax
mov QWORD PTR [rcx+r11*8-56], rbx

Я не уверен на 100%, что смещение -56 является правильным для вашего кода, но концепция "правильная".

Я бы также рассмотрел кеш-хиты/кеш-коллизии. Например. если у вас есть три блока данных [которые, как вам кажется, вы это делаете], вы убедитесь, что они НЕ привязаны к одному и тому же смещению в кеше. Плохой пример - если вы выделите все свои блоки с кратным размером кеша из одного и того же места в кеше. Over-allocating and make Убедитесь, что ваши разные блоки данных смещены по меньшей мере на 512 байт [так что распределите 4K негабаритных и округлите до 4K пограничного начального адреса, затем добавьте 512 во второй буфер и 1024 в третий буфер]

Если ваши данные достаточно большие (больше, чем кэш L2), вы можете использовать MOVNT для извлечения/хранения ваших данных. Это позволит избежать чтения в кеш - это ТОЛЬКО польза, когда у вас очень большие данные, где следующее чтение просто вызовет что-то еще, что вы можете найти "полезным" для выхода из кеша, и вы не получите вернемся к нему, прежде чем вы выкидываете его из кэша в любом случае - поэтому сохранение значения в кеше фактически не поможет...

Изменить: использование SSE или подобного не поможет, как описано здесь: Могут ли длинные целочисленные процедуры использовать SSE?

Ответ 2

Самая сложная зависимость - это распространение переноса между каждым блоком памяти; Я бы попробовал на первом устройстве метод борьбы с этим.

Следующий фрагмент моделирует перенос переноса, но с "преимуществом" использования флага переноса. Это можно распараллеливать для трех или четырех отдельных потоков, каждый из которых производит половину, несущую около 25000 десятичных цифр (или 10000 байт) друг от друга. Тогда вероятность того, что они переносятся только на один байт, слово, слово и т.д., Асимптотически достигнет нуля.

 long long carry=0;
 for (int i=0;i<N;i++) {
     carry += (long long)*a++ + (long long)*b++;
     *c++ = carry; carry>>=32;
 }

Согласно моему профилированию, безличное добавление с использованием xmm займет ~ 550 мс (1е9 слов), имитированный перенос займет ~ 1020 мс, а 4-позиционная параллельная версия займет ~ 820 мс (без какой-либо ассемблерной оптимизации).

Архитектурные оптимизации могут включать использование избыточной системы счисления, где перенос не должен распространяться все время и где оценка переноса может быть отложена почти до бесконечности.

Ответ 3

Сначала попробуйте предварительно запрограммировать данные (сначала вы можете прочитать больше блоков данных в регистрах x64, затем выполнить вычисления), проверить правильность выравнивания данных в памяти, поместить код цикла на метку, выровненную до 16, попытаться удалить Адрес SIB

Вы также можете попытаться сократить код:

mov rax, QWORD PTR [rdx+r11*8-64]
adc rax, QWORD PTR [r8+r11*8-64]
mov QWORD PTR [rcx+r11*8-64], rax