Где я могу узнать об оптимальной математике в C на микроконтроллере, например, ARMv7? - PullRequest
3 голосов
/ 25 марта 2011

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

Я могу задать все вопросы здесь, но я бы просто нашел хорошийстатья на эту тему, если кто-то знает.

Я использую IAR, чтобы написать программу на C для процессора ATMEL SAM7S.У меня есть функция сортировки, которая занимает 500 мкс или около того, и я хотел посмотреть, смогу ли я ускорить ее.Я также мог бы просто опубликовать это здесь, но я надеялся научиться сам.

Например, быстрее ли вычесть два 16-битных целых числа, чем вычесть два 32-битных целых числа?И как долго длится такая операция?Всего один цикл или больше?Сколько времени занимает умножение по сравнению с вычитанием?

Кто-нибудь знает, где искать?Я пытался найти что-то в поиске, но не смог найти ни одного полезного поискового запроса.

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

Ответы [ 3 ]

1 голос
/ 25 марта 2011

Разве можно вычесть два 16-битных целых числа быстрее, чем вычесть два 32-битных целых числа?

Не в архитектуре ARM, которая имеет собственные 32-битные регистры, нет.

Кто-нибудь знает, где искать?

Каноническим местом для временных циклов инструкций будет Руководство по техническому обслуживанию для конкретной архитектуры, которую реализует ваш чип, например. ARM7TDMI ; время для простых операций здесь и да, это один цикл. Этот документ неудобен для чтения, если вы еще не очень хорошо знакомы с набором инструкций ...

Прямо сейчас я перебираю всю таблицу

Вам будет гораздо лучше взглянуть на алгоритмическую оптимизацию здесь (например, индексировать таблицу, отсортировать по одной координате, чтобы сузить ее и т. Д.), Чем беспокоиться о микрооптимизации на уровне команд.

1 голос
/ 25 марта 2011

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

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

0 голосов
/ 25 марта 2011

Вы можете использовать таймеры в вашем SAM7S. Считайте таймер при запуске и прочитайте его после N числа поисков и вычтите, чтобы получить разницу. Попробуйте разные алгоритмы и посмотрите, что вы видите.

Что касается 16-битной математики против 32-битной математики, да, разница может быть огромной, но вы должны взглянуть на свою архитектуру. Операция вычитания между двумя регистрами займет один и тот же такт, будь то 16 бит или 32 бита. Но, исходя из кода C, переменные могут в конечном итоге оказаться в памяти, и вы должны знать, есть ли у вас 16-битная или 32-битная шина данных (да, ARM7 могут иметь 16-битную шину, посмотрите на GameBoy Advance, большой палец работает значительно быстрее, чем Код ARM на этом процессоре). Требуется вдвое больше циклов для чтения или записи 32-битных чисел на 16-но шине. У вас, скорее всего, нет 16-битной шины. Использование 16-битных переменных на 32-битном процессоре приводит к тому, что процессору приходится добавлять дополнительные инструкции для удаления или расширения верхних битов, чтобы математика была правильной для 16-битной переменной. Эти дополнительные инструкции могут вызвать снижение производительности, простое вычитание, которое могло бы быть, скажем, 3 или 4, наихудшим случаем команд теперь может быть 5 или 6, и это заметно, если оно находится в узком цикле. Как правило, вы хотите использовать переменные, соответствующие размеру регистра процессоров, в 32-битном ARM используйте как можно больше 32-битных переменных, даже если вы рассчитываете только до 10.

Надеюсь, я понимаю проблему, которую вы пытаетесь решить, если нет, дайте мне знать, и я отредактирую / удалю этот ответ:

В зависимости от того, сколько бит в вашем измерении, типичным решением для того, что вы делаете, является использование справочной таблицы. Чтобы я мог показать пример, скажем, вы выполняете 4-битное измерение, которое хотите откалибровать. Назовите это от 0 до 15. Калибровка датчика сгенерировала список точек данных, скажем:

raw cal
0x03  16
0x08  31
0x14  49

Я предполагаю, что то, что вы делаете во время выполнения, выглядит примерно так: если датчик читает 0x5, вы просматриваете список в поисках записей, совпадающих с показаниями вашего датчика, или между двумя точками калибровки.

при поиске вы найдете его в диапазоне от 0x03 до 0x08, чтобы получить калиброванный результат из необработанного измерения 0x05

cal=  (((0x05-0x03)/(0x08-0x03))*(31-16)+16 = 22

У вас есть разрыв, который является ОГРОМНЫМ убийцей производительности на большинстве процессоров, в частности ARM7, поскольку у него нет разрыва. Не уверен насчет умножения, но вы также хотите избежать таких, как чума. И если вы думаете о том, сколько инструкций все это занимает.

Вместо этого вы берете алгоритм, который используете во время выполнения, и в специальной программе генерируете все возможные выходные данные из всех возможных входных данных:

0  7
1  10
2  13
3  16
4  19
5  22
6  25
7  28
8  31
9  34
10 37
11 40
12 43
13 46
14 49
15 52

Теперь превратите это в таблицу в вашем коде времени выполнения:

unsigned char cal_table [16] = {7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52};

и затем время выполнения

cal = cal_table [raw & 15];

Код для реализации этого выглядит примерно так:

ldr r3, =cal_table
and r0, r0, #15
ldrb    r0, [r3, r0]

занимает около 5 часов.

Просто математика для поиска cal из raw после того, как вы просмотрели таблицу:

cal=  (((raw-xlo)/(xhi-xlo))*(yhi-ylo)+ylo);

выглядит примерно так:

docal:
    stmfd   sp!, {r3, r4, r5, lr}
    ldr r3, .L2
    ldr r5, .L2+4
    ldr lr, .L2+8
    ldr ip, [r5, #0]
    ldr r0, [r3, #0]
    ldr r1, [lr, #0]
    ldr r2, .L2+12
    rsb r0, ip, r0
    rsb r1, ip, r1
    ldr r5, [r2, #0]
    bl  __aeabi_uidiv
    ldr r4, .L2+16
    ldr r3, .L2+20
    ldr r4, [r4, #0]
    rsb r5, r4, r5
    mla r4, r0, r5, r4
    str r4, [r3, #0]
    ldmfd   sp!, {r3, r4, r5, pc}

И функция деления такая же плохая, если не хуже. Таблица поиска должна заставить ваш код работать в десятки раз быстрее.

Проблема с поисковыми таблицами заключается в том, что вы тратите память на производительность, поэтому вам необходимо иметь таблицу, достаточно большую, чтобы охватить все возможные входные данные. Например, 12-битный датчик даст вам 4096 записей в таблице поиска. Если, скажем, вы знали, что измерение никогда не будет ниже 0x100, вы можете сделать таблицу 0x1000 - 0x100 или 3840 записей глубиной и вычесть 0x100 из необработанного значения, прежде чем искать его, торгуя пару инструкций во время выполнения, чтобы сэкономить несколько сотен байтов память.

Если таблица была бы слишком большой, вы могли бы попробовать другие приемы, такие как составление справочной таблицы старших битов, и результатом этого может быть предварительно вычисленное смещение в таблице cal, чтобы начать поиск.Поэтому, если у вас был 12-разрядный АЦП, но у вас не было места для таблицы поиска с 4096 записями, вы могли бы создать таблицу поиска с 16 записями, взять верхние 4 бита выхода АЦП и использовать их для просмотра в таблице.Таблица будет содержать запись в таблице cal, чтобы начать поиск.Скажем, в вашей таблице калибровки были следующие записи:

....
entry 27 raw = 0x598 cal = 1005
entry 28 raw = 0x634 cal = 1600
entry 29 raw = 0x6AB cal = 1800
entry 30 raw = 0x777 cal = 2000

ваша 16-я таблица глубокого просмотра будет иметь эти записи

...
[6] = 27;
[7] = 29;
...

И как бы вы ее использовали -

start = lut[raw>>8];
for(i=start;i<cal_tab_len;i++)
{
...
}

вместо

for(i=0;i<cal_tabl_len;i++)
{
}

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

Для решения конкретной задачинеобработанное значение и превращение его в калиброванное значение во время выполнения, есть много много подобных ярлыков.Я не знаю ни одной книги, которая бы охватывала их все.Какой путь выбрать во многом зависит от вашего процессора, системы памяти и доступности, а также от размера и характера ваших данных.Как правило, вы хотите избегать делений, в частности, и умножения, если ваш процессор их не поддерживает (используя очень мало тактов).Большинство процессоров этого не делают.(Да, один или два процессора, на которые ориентируется большинство программистов, имеют один цикл умножения и деления).Даже для процессоров, которые имеют один цикл умножения и деления, они часто должны быть обернуты библиотекой C, чтобы решить, безопасно ли выполнять операцию с аппаратной инструкцией или ее нужно синтезировать с библиотекой.Я упоминал выше, что для большинства переменных вы хотите соответствовать собственному размеру регистра процессора.Если у вас есть умножение или деление с фиксированной запятой, вы часто захотите использовать половину размера регистра процессора.32-битный процессор, если вы не потратите время на подробное изучение инструкций, вы, вероятно, захотите ограничить свои кратные 16-битными входами с 32-битным выходом и разделить на 32-битные входы с 16-битным выходом и надеяться, что оптимизатор поможет вамout.

Опять же, если я неправильно предположил, какую проблему вы пытаетесь решить, пожалуйста, прокомментируйте, и я отредактирую / отредактирую этот ответ.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...