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

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

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

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

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

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

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

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

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

Просто поразительно как Ваша задача напоминает решение задачи изложенной только что, практически одновременно с Вами в этом посте:
http://electronix.ru/forum/index.php?showt...p;#entry1407211
Правда там нужны таблицы не байтовые, а состоящий из 32-битных слов, и ядро другое - M0.
Но всё-же, всё-же..... очень подозрительно.....

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

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

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


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

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

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

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

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


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

В принципе да, я могу уместиться в память, если переделаю 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].

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

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

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


А именно ?

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

Можно ещё сэкономить время на сдвигах (безотносительно к вышенаписанному), если сделать 4 таблицы (каждая по 256*32битных слова) с заранее смещёнными в них 8-битными данными.
В таблице 0 все данные вида 0х000000NN, в таблице 1 данные вида 0х0000NN00, и так далее.
Тогда таблицы займут 4кБ всего. А данные берутся из памяти за 1 такт, и ещё за 1 складываются в общий регистр без сдвига (который тоже вроде бы ест такты).
Вынуть все 4 байта из 4 таблиц, и сложить в один регистр займёт 7 тактов:

Сообщение отредактировал controller_m30 - Feb 26 2016, 21:38

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

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

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

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

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



Сообщение отредактировал IgorKossak - Feb 27 2016, 15:39