Himmler 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Здравствуйте, товарищи. Имеется старенький arm926, на нём потребовалось запилить определённый алгоритм. Основная тяжеловесная часть данного алгоритма делают следующее: На входе - 32-битное слово (лежит в регистре R0), в памяти (время доступа - 1 такт) лежат 4 таблицы по 256 однобайтовых элементов каждая. -Выковыриваем из входного слова отдельно все 4 байта -Из таблицы 1 дёргаем байт, позиция которого определяется первым выдернутым байтом входного слова -Из таблицы 2 дёргаем байт, позиция которого определяется вторым выдернутым байтом входного слова -Из таблицы 3 дёргаем байт, позиция которого определяется третьим выдернутым байтом входного слова -Из таблицы 4 дёргаем байт, позиция которого определяется четвёртым выдернутым байтом входного слова -Из четырёх надёрганных байтов формируем выходное 32-битное слово Реализация в лоб занимает у меня 11 команд (4 логических И с маской, затем 4 загрузки из таблиц в регистры, затем 3 сложения, чтобы получить выходное слово. Сдвиги не учитываю, так как они прилеплены к другим командам и даются "бесплатно") Есть ли предложения по сокращению количества команд, если алгоритмическая оптимизация недоступна (то есть только грамотным подбором ассемблерных инструкций) ? Очень надеюсь, что есть опытные сограждане. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
scifi 1 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Может быть, можно сделать 4 байтовые загрузки в стек, и тогда слово там получится само без всяких сложений? Пардон, ерунду сказал, в стек - это же отдельная инструкция. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 166 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба На входе - 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 сидит на быстрой шине. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
slavka012 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба PS: Только что в голову пришёл самый быстрый метод - в зависимости от функционирования GPIO в Вашем МК, этот метод вообще может занимать всего пару тактов :rolleyes: Выделяете 2-а 32-битных порта GPIO. Соединяете вых. линии первого порта с вх. линиями второго в соответствии с таблицей перестановки бит, выводите слово в первый порт, считываете со второго. На ядре M3 этот алгоритм может занимать всего два такта, если GPIO сидит на быстрой шине. Тут не перестановка битов, а выборка из массива. Смотря что у вас там за доступы, может помочь кэширование результатов. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Himmler 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Дело в том, что расширить таблицы мне уже не удастся, так как если сделать их не 1-байтовыми, а 2-байтовыми, то они будут занимать уже не 1 килобайт (4*16*16*1), а 256 килобайт (2*256*256*2). А быстрой однотактовой памяти у меня всего 32 килобайта. Есть огромная ддр-ка, но она дико медленная, обращение к ней съест весь выигрыш. И прекешировать нужное не получится, потому как индексы прыгают хаотически согласно входному слову. Насчёт GPIO идеи не понял - как можно соединить входы с выходами так, чтобы такое соединение охватывало 2^32 состояний ? Я пока копаю в сторону именно удачно подходящих инструкций, например чтобы не выделять отдельно 4 байта четыремя командами, или например избавиться от тройного сложения и как-то иначе собрать выходное 32-битное слово из однобайтовых кусков. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 166 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Дело в том, что расширить таблицы мне уже не удастся, так как если сделать их не 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 состояний ? Забудьте. Я думал у Вас такая-же задача, как у товарища переставляющего биты. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Himmler 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба В принципе да, я могу уместиться в память, если переделаю 4 таблицы по 8 бит в 3 таблицы по 12/12/8 бит. Тогда алгоритм получится следующий: -Выковыриваем из входного слова отдельно 12 байт, потом ещё 12, и последние 8. -Из таблицы 1 дёргаем 12 бит, позиция которых определяется первым выдернутым значением из входного слова -Из таблицы 2 дёргаем 12 бит, позиция которых определяется вторым выдернутым значением из входного слова -Из таблицы 3 дёргаем 8 бит, позиция которого определяется третьим выдернутым значением из входного слова -Из трёх надёрганных кусков формируем выходное 32-битное слово Итого: 3 логических И с маской, 3 загрузки из памяти в регистры, 2 суммирования. Экономия, несомненно есть. Хотелось бы услышать ещё предложения, возможно есть инструкции, позволяющие сложить три значения за такт, или опять же какая-либо хитрость с масками. P.S. Вот я тут подумал, при разбиении входного слова на куски можно ещё одну инструкцию сэкономить - не брать маску для старших бит, а передать входное слово с нужным сдвигом, получив тем самым нужное количество старших бит в качестве индекса внутри массива в третьей таблице. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
controller_m30 1 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Можно в 9 команд уложиться. В R0 исходное слово 32 бит В R1 адрес первой таблицы(table_0), в процессе выполнения не меняется, Таблицы идут последовательно: table_0, table_1, table_2, table_3 На выходе в R6 - значения таблиц по условию: [t3],[t2],[t1],[t0]. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
adnega 10 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Можно в 9 команд уложиться. Только борьба не за память идет, а за быстродействие. Разверните цикл и посмотрите сколько инструкций получится. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
s_gary 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Если организовать результирующее слово как структуру из указателей? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Himmler 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Действительно, я наверное некорректно в постановке вопроса употребил слово "команда". В моём случае все инструкции, кроме загрузки из памяти выполняются за 1 такт, а латентность, вызываемая загрузкой из памяти маскируется во-первых конвейерной загрузкой, а во-вторых использованием загруженных данных через 2 инструкции после команды загрузки. А борьба идёт, естественно, за количество тактов. И предложенное выше укрупнение таблиц + экономия одной операции с маской позволяет выполнить алгоритм за 7 тактов. На мой взгляд, гипотетически сэкономить можно на сложении трёх значений и на операциях с маской. Но как именно - пока не знаю. Если организовать результирующее слово как структуру из указателей? А именно ? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
controller_m30 1 26 февраля, 2016 Опубликовано 26 февраля, 2016 (изменено) · Жалоба А борьба идёт, естественно, за количество тактов. Понятно. А как оказались четыре 8-битных числа собранными в один регистр R0? Зачем их туда сложили? Если эти 4 байта лежали рядом в какой-то другой таблице, то их можно было считать побайтно в 4 отдельных регистра и не пользоваться для их разделения масками и сдвигами вообще. Можно ещё сэкономить время на сдвигах (безотносительно к вышенаписанному), если сделать 4 таблицы (каждая по 256*32битных слова) с заранее смещёнными в них 8-битными данными. В таблице 0 все данные вида 0х000000NN, в таблице 1 данные вида 0х0000NN00, и так далее. Тогда таблицы займут 4кБ всего. А данные берутся из памяти за 1 такт, и ещё за 1 складываются в общий регистр без сдвига (который тоже вроде бы ест такты). Вынуть все 4 байта из 4 таблиц, и сложить в один регистр займёт 7 тактов: Изменено 26 февраля, 2016 пользователем controller_m30 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Himmler 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Понятно. А как оказались четыре 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. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AVI-crak 0 26 февраля, 2016 Опубликовано 26 февраля, 2016 · Жалоба Не понимаю как у вас получается 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} Можно ещё читать байт прямо в разряды регистра, но без выравнивания таблиц - может получиться кака. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Himmler 0 27 февраля, 2016 Опубликовано 27 февраля, 2016 (изменено) · Жалоба . Дело в том, что такие операции, как загрузка адресов таблиц, сохранение регистров в стек, загрузка входного и выгрузка выходного слов выполняются по одному разу, а вот основная часть крутится многократно. Примерно получается (если считать, что входное слово, 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; собрали Изменено 27 февраля, 2016 пользователем IgorKossak бездумное цитирование Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться