Перейти к содержанию
    

Ассемблерная оптимизация маленького куска (порядка 10-15 инструкций)

Здравствуйте, товарищи.

 

Имеется старенький arm926, на нём потребовалось запилить определённый алгоритм.

 

Основная тяжеловесная часть данного алгоритма делают следующее:

 

На входе - 32-битное слово (лежит в регистре R0), в памяти (время доступа - 1 такт) лежат 4 таблицы по 256 однобайтовых элементов каждая.

 

-Выковыриваем из входного слова отдельно все 4 байта

-Из таблицы 1 дёргаем байт, позиция которого определяется первым выдернутым байтом входного слова

-Из таблицы 2 дёргаем байт, позиция которого определяется вторым выдернутым байтом входного слова

-Из таблицы 3 дёргаем байт, позиция которого определяется третьим выдернутым байтом входного слова

-Из таблицы 4 дёргаем байт, позиция которого определяется четвёртым выдернутым байтом входного слова

-Из четырёх надёрганных байтов формируем выходное 32-битное слово

 

Реализация в лоб занимает у меня 11 команд (4 логических И с маской, затем 4 загрузки из таблиц в регистры, затем 3 сложения, чтобы получить выходное слово. Сдвиги не учитываю, так как они прилеплены к другим командам и даются "бесплатно")

 

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

 

Очень надеюсь, что есть опытные сограждане.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Пардон, ерунду сказал, в стек - это же отдельная инструкция.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

На входе - 32-битное слово (лежит в регистре R0), в памяти (время доступа - 1 такт) лежат 4 таблицы по 256 однобайтовых элементов каждая.

 

-Выковыриваем из входного слова отдельно все 4 байта

-Из таблицы 1 дёргаем байт, позиция которого определяется первым выдернутым байтом входного слова

-Из таблицы 2 дёргаем байт, позиция которого определяется вторым выдернутым байтом входного слова

-Из таблицы 3 дёргаем байт, позиция которого определяется третьим выдернутым байтом входного слова

-Из таблицы 4 дёргаем байт, позиция которого определяется четвёртым выдернутым байтом входного слова

-Из четырёх надёрганных байтов формируем выходное 32-битное слово

Просто поразительно как Ваша задача напоминает решение задачи изложенной только что, практически одновременно с Вами в этом посте:

http://electronix.ru/forum/index.php?showt...p;#entry1407211

Правда там нужны таблицы не байтовые, а состоящий из 32-битных слов, и ядро другое - M0.

Но всё-же, всё-же..... очень подозрительно..... B)

 

Касательно сути проблемы:

Вы не озвучили требования по памяти. Тупо в лоб оптимизация за счёт объёма памяти: разбивать входное 32-бит слово не на байты, а на куски большей разрядности - например 11/11/10 бит; ну или 16/16бит.

Памяти израсходуете больше, но тактов - меньше.

 

PS: Только что в голову пришёл самый быстрый метод - в зависимости от функционирования GPIO в Вашем МК, этот метод вообще может занимать всего пару тактов :rolleyes:

Выделяете 2-а 32-битных порта GPIO. Соединяете вых. линии первого порта с вх. линиями второго в соответствии с таблицей перестановки бит, выводите слово в первый порт, считываете со второго. На ядре M3 этот алгоритм может занимать всего два такта, если GPIO сидит на быстрой шине.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

PS: Только что в голову пришёл самый быстрый метод - в зависимости от функционирования GPIO в Вашем МК, этот метод вообще может занимать всего пару тактов :rolleyes:

Выделяете 2-а 32-битных порта GPIO. Соединяете вых. линии первого порта с вх. линиями второго в соответствии с таблицей перестановки бит, выводите слово в первый порт, считываете со второго. На ядре M3 этот алгоритм может занимать всего два такта, если GPIO сидит на быстрой шине.

 

Тут не перестановка битов, а выборка из массива.

 

 

Смотря что у вас там за доступы, может помочь кэширование результатов.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Дело в том, что расширить таблицы мне уже не удастся, так как если сделать их не 1-байтовыми, а 2-байтовыми, то они будут занимать уже не 1 килобайт (4*16*16*1), а 256 килобайт (2*256*256*2).

А быстрой однотактовой памяти у меня всего 32 килобайта. Есть огромная ддр-ка, но она дико медленная, обращение к ней съест весь выигрыш. И прекешировать нужное не получится, потому как индексы прыгают хаотически согласно входному слову.

 

Насчёт GPIO идеи не понял - как можно соединить входы с выходами так, чтобы такое соединение охватывало 2^32 состояний ?

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Дело в том, что расширить таблицы мне уже не удастся, так как если сделать их не 1-байтовыми, а 2-байтовыми, то они будут занимать уже не 1 килобайт (4*16*16*1), а 256 килобайт (2*256*256*2).

А быстрой однотактовой памяти у меня всего 32 килобайта. Есть огромная ддр-ка, но она дико медленная, обращение к ней съест весь выигрыш. И прекешировать нужное не получится, потому как индексы прыгают хаотически согласно входному слову.

Но 11/11/10 потребует только (2^11*2+2^10)*2 = 10240 байт. Хотя (не помню точно систему команд) возможно потребуется доп. сдвиг для преобразования индекса в смещение.

 

Насчёт GPIO идеи не понял - как можно соединить входы с выходами так, чтобы такое соединение охватывало 2^32 состояний ?

Забудьте. Я думал у Вас такая-же задача, как у товарища переставляющего биты.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

В принципе да, я могу уместиться в память, если переделаю 4 таблицы по 8 бит в 3 таблицы по 12/12/8 бит.

 

Тогда алгоритм получится следующий:

 

-Выковыриваем из входного слова отдельно 12 байт, потом ещё 12, и последние 8.

-Из таблицы 1 дёргаем 12 бит, позиция которых определяется первым выдернутым значением из входного слова

-Из таблицы 2 дёргаем 12 бит, позиция которых определяется вторым выдернутым значением из входного слова

-Из таблицы 3 дёргаем 8 бит, позиция которого определяется третьим выдернутым значением из входного слова

-Из трёх надёрганных кусков формируем выходное 32-битное слово

 

Итого: 3 логических И с маской, 3 загрузки из памяти в регистры, 2 суммирования.

Экономия, несомненно есть.

 

Хотелось бы услышать ещё предложения, возможно есть инструкции, позволяющие сложить три значения за такт, или опять же какая-либо хитрость с масками.

 

P.S. Вот я тут подумал, при разбиении входного слова на куски можно ещё одну инструкцию сэкономить - не брать маску для старших бит, а передать входное слово с нужным сдвигом, получив тем самым нужное количество старших бит в качестве индекса внутри массива в третьей таблице.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Можно в 9 команд уложиться.

В R0 исходное слово 32 бит

В R1 адрес первой таблицы(table_0), в процессе выполнения не меняется,

Таблицы идут последовательно: table_0, table_1, table_2, table_3

На выходе в R6 - значения таблиц по условию: [t3],[t2],[t1],[t0].

post-45309-1456517299_thumb.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Можно в 9 команд уложиться.

Только борьба не за память идет, а за быстродействие.

Разверните цикл и посмотрите сколько инструкций получится.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Если организовать результирующее слово как структуру из указателей?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Действительно, я наверное некорректно в постановке вопроса употребил слово "команда". В моём случае все инструкции, кроме загрузки из памяти выполняются за 1 такт, а латентность, вызываемая загрузкой из памяти маскируется во-первых конвейерной загрузкой, а во-вторых использованием загруженных данных через 2 инструкции после команды загрузки.

А борьба идёт, естественно, за количество тактов. И предложенное выше укрупнение таблиц + экономия одной операции с маской позволяет выполнить алгоритм за 7 тактов. На мой взгляд, гипотетически сэкономить можно на сложении трёх значений и на операциях с маской. Но как именно - пока не знаю.

 

Если организовать результирующее слово как структуру из указателей?

А именно ?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

А борьба идёт, естественно, за количество тактов.

Понятно.

А как оказались четыре 8-битных числа собранными в один регистр R0? Зачем их туда сложили?

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

 

Можно ещё сэкономить время на сдвигах (безотносительно к вышенаписанному), если сделать 4 таблицы (каждая по 256*32битных слова) с заранее смещёнными в них 8-битными данными.

В таблице 0 все данные вида 0х000000NN, в таблице 1 данные вида 0х0000NN00, и так далее.

Тогда таблицы займут 4кБ всего. А данные берутся из памяти за 1 такт, и ещё за 1 складываются в общий регистр без сдвига (который тоже вроде бы ест такты).

Вынуть все 4 байта из 4 таблиц, и сложить в один регистр займёт 7 тактов:

post-45309-1456522631_thumb.png

Изменено пользователем controller_m30

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Понятно.

А как оказались четыре 8-битных числа собранными в один регистр R0? Зачем их туда сложили?

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

 

Можно ещё сэкономить время на сдвигах (безотносительно к вышенаписанному), если сделать 4 таблицы (каждая по 256*32битных слова) с заранее смещёнными в них 8-битными данными.

В таблице 0 все данные вида 0х000000NN, в таблице 1 данные вида 0х0000NN00, и так далее.

Тогда таблицы займут 4кБ всего. А данные берутся из памяти за 1 такт, и ещё за 1 складываются в общий регистр без сдвига (который тоже вроде бы ест такты).

Вынуть все 4 байта из 4 таблиц, и сложить в один регистр займёт 7 тактов:

 

Это не 4 8-битных числа, разбиение условное, можно побить как 12/12/8. Входной вектор - 32-битный, выходной - тоже 32-битный. Идеальный вариант однотактового преобразователя - таблица на 4 миллиарда состояний, по 32 бита в каждом. Но ввиду очевидной невозможности такого безумия приходится разбивать преобразование на куски. Можно преобразовывать по 4 бита 8 раз, а можно по 8 бит 4 раза, а можно по 16 бит 2 раза (но на это памяти уже не хватит). По доступной памяти уложусь максимум в 12/12/8.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Не понимаю как у вас получается 9 команд, и 18 в уме. У меня получилось 20 команд, и 35 системных тиков.

        // Cortex-M3
        // r0  вход-выход    
        push   {r1, r2, r3, r4, r5, lr}
        ldr     r0, =входное
        ldr     r1, =адрес таблиц (1+2+3+4)
        mov     r2, #0xFF                   // маска
        and     r3, r0, r2
        ldrb    r4, [r1, r3]                // первый байт
        and     r3, r2, r0, lsr #8
        add     r0, r0, #0x100
        ldrb    r5, [r0, r3]                // второй байт
        add     r0, r0, #0x100
        and     r3, r2, r0, lsr #16
        add     r4, r4, r5, lsl #8
        ldrb    r5, [r0, r3]                // третий байт
        add     r0, r0, #0x100
        lsr     r0, r0, #24
        add     r4, r4, r5, lsl #16
        ldrb    r5, [r0, r3]                // последний байт
        add     r0, r4, r5, lsl #24
        pop     {r1, r2, r3, r4, r5, lr}

Можно ещё читать байт прямо в разряды регистра, но без выравнивания таблиц - может получиться кака.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

.

 

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

 

Примерно получается (если считать, что входное слово, 12-битная маска, адреса таблиц уже загружены,регистры сохранены, и таблиц всего 3 по 12/12/8 бит):

 

and r1, r0, r7; получаем указатель в первой таблице (r7 = 0x00000fff)
and r2, r0, r7, LSL #12; получаем указатель во второй таблице

ldr r1, [r4, r1]; загружаем младшие 12 бит (r4 был предварительно загружен и будет ещё многократно использоваться)
ldr r2, [r5, r2, LSR #12]; загружаем средние 12 бит (r5 был предварительно загружен и будет ещё многократно использоваться)
ldr r3, [r6, r0, LSR #24]; загружаем старшие 8 бит (r6 был предварительно загружен и будет ещё многократно использоваться)

add r1, r1, r2, LSL #12; собираем 3 куска в одно 32-битное слово
add r1, r3, LSL #24; собрали

Изменено пользователем IgorKossak
бездумное цитирование

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...