В следующих разделах сравниваются реализации интерполяционных таблиц, которые используют точки останова, интервалы которых неравномерны, четны и степень двойки. Сравнение фокусируется на:
Скорость выполнения команд
Ошибка округления во время интерполяции
Объем памяти (ПЗУ) только для чтения для данных
Объем ПЗУ для команд
Это сравнение допустимо только, когда точки останова не настраиваются. Если точки останова настраиваются в сгенерированном коде, все три случая генерируют один и тот же код. Для сводных данных о влияниях интервалов точек по оси Х на скорость выполнения, ошибку и использование памяти, см. «Сводные данные эффектов интервалов точек Х».
Это сравнение использует модель fxpdemo_approx_sin. В этой модели появляются три интерполяционные таблицы с фиксированной точкой. Все три таблицы аппроксимируют функцию sin(2*pi*u) по первому квадранту и достигнуть наихудшей ошибки меньше 2^-8. Однако они имеют различные ограничения на интервалы между точками останова.
Можно использовать модель fxpdemo_approx, что fxpdemo_approx_sin открывает, чтобы сгенерировать Simulink® Coder™ код (требуется лицензия программного обеспечения Simulink Coder). В следующих разделах представлены несколько сегментов сгенерированного кода, чтобы подчеркнуть ключевые различия.
Чтобы открыть модель, введите в MATLAB® приглашение:
fxpdemo_approx_sin
В этом разделе рассматривается ПЗУ данных, требуемое для каждого из трёх опций интервалов.
Для неравномерного интервала требуются как точки данных Y, так и точки прерывания:
int16_T yuneven[8]; uint16_T xuneven[8];
Всего используемых байтов 32.
Для четного интервала требуются только точки данных Y:
int16_T yeven[10];
Всего используемых байтов 20. Точки останова явно не требуются. Код использует интервал между точками останова и может использовать самые маленькие и самые большие точки останова. Самое большее, три значения, связанные с точками останова, необходимы.
Степень двойки интервалов требует только Y точек данных:
int16_T ypow2[17];
Всего используемых байтов 34. Точки останова явно не требуются. Код использует интервал между точками останова и может использовать самые маленькие и самые большие точки останова. Самое большее, три значения, связанные с точками останова, необходимы.
Во всех трех случаях вы должны защитить от вероятности того, что вход меньше, чем наименьшая точка останова или больше, чем самая большая точка останова. Могут быть различия в том, как обрабатываются вхождения этих возможностей. Однако различия, как правило, незначительны и обычно не являются ключевым фактором при принятии решения использовать один метод интервала между ними. Последующие разделы предполагают, что входы вне области допустимого значения невозможны или уже обработаны.
В этом разделе описывается, как три интерполяционные таблицы с фиксированной точкой определяют, где текущий вход относится к точкам останова.
Неравномерно разнесенные точки останова требуют алгоритма общего назначения, такого как двоичный поиск, чтобы определить, где вход лежит относительно точек останова. Пример приведен в следующем коде:
iLeft = 0;
iRght = 7; /* number of breakpoints minus 1 */
while ( ( iRght - iLeft ) > 1 )
{
i = ( iLeft + iRght ) >> 1;
if ( uAngle < xuneven[i] )
{
iRght = i;
}
else
{
iLeft = i;
}
}Цикл while выполняется до log2 (N) раз, где N - количество точек останова.
Равномерно расположенные точки прерывания требуют только одного шага, чтобы определить, где вход лежит относительно точек прерывания:
iLeft = uAngle / 455U;
Делитель 455U представляет интервал между точками останова. В целом дивиденды будут (uAngle - SmallestBreakPoint). В этом примере самая маленькая точка останова равна нулю, поэтому код оптимизирует вычитание.
Степень двойки разнесенных точек прерывания требует только одного шага, чтобы определить, где вход лежит относительно точек прерывания:
iLeft = uAngle >> 8;
Количество сдвигов составляет 8, потому что точки останова имеют интервалы 2^8. Самая маленькая точка останова равна нулю, так что uAngle заменяет общий случай (uAngle - SmallestBreakPoint).
Чтобы определить, где вход лежит относительно точек останова, неравномерно разнесенный случай требует гораздо больше кода, чем другие два случая. Этот код требует дополнительного ПЗУ команды. Если многие интерполяционные таблицы используют двоичный алгоритм поиска как функцию, можно уменьшить этот штраф ROM. Даже если код разделяется, количество тактовых импульсов, требуемых для определения местоположения входа, намного выше для неравномерно разнесенных случаев, чем в двух других случаях. Если код является общим, накладные расходы на вызов функции уменьшают скорость выполнения еще немного.
В равномерно разнесенном случае и степени двойки разнесенных случаев можно определить местоположение входа с помощью одной строки кода. В равномерно разнесенном случае используется общее целое деление. В степень двойки случае вместо общего деления используется сдвиг, потому что делитель является точной степенью двойки. Не зная конкретного процессора, вы не можете быть уверены, что сдвиг лучше деления.
Многие процессоры могут реализовать деление с одной инструкцией по языку сборки, поэтому код будет маленьким. Однако для выполнения этой команды часто требуется много тактов. Многие процессоры не предоставляют инструкцию деления. Деление на этих процессорах происходит посредством повторных вычитаний. Этот процесс идет медленно и требует большого количества машинного кода, но этим кодом можно делиться.
Большинство процессоров обеспечивают способ сделать логические и арифметические сдвиги влево и вправо. Ключевым различием является то, может ли процессор выполнить N сдвигов в одной команде (сдвиг ствола) или требует N команд, которые сдвигают по одному биту за раз. Сдвиг ствола требует меньше кода. Увеличивает ли сдвиг ствола также скорость, зависит от оборудования, которое поддерживает операцию.
Компилятор также может усложнить сравнение. В предыдущем примере команда uAngle >> 8 по существу берёт верхние 8 биты в 16-битном слове. Компилятор может обнаружить эту ситуацию и заменить битовые сдвиги командой, которая принимает биты непосредственно. Если количество сдвигов является некоторым другим значением, таким как 7, эта оптимизация не произойдет.
В теории можно вычислить интерполяцию со следующим кодом:
y = ( yData[iRght] - yData[iLeft] ) * ( u - xData[iLeft] ) ...
/ ( xData[iRght] - xData[iLeft] ) + yData[iLeft]Термин (xData[iRght] - xData[iLeft]) - интервал между соседними точками останова. Если это значение является постоянным, из-за четного интервала, возможно некоторое упрощение. Если интервал является не только даже, но и степенью двойки, для реализаций с фиксированной точкой возможны значительные упрощения.
Для неравномерного случая одной возможной реализацией идеальной интерполяции в фиксированной точке является:
xNum = uAngle - xuneven[iLeft]; xDen = xuneven[iRght] - xuneven[iLeft]; yDiff = yuneven[iRght] - yuneven[iLeft]; MUL_S32_S16_U16( bigProd, yDiff, xNum ); DIV_NZP_S16_S32_U16_FLOOR( yDiff, bigProd, xDen ); yUneven = yuneven[iLeft] + yDiff;
Умножение и стандартные программы деления здесь не показаны. Эти стандартные программы могут быть сложными и зависеть от целевого процессора. Например, эти стандартные программы выглядят иначе для 16-битного процессора, чем для 32-битного процессора.
Равномерно расположенные точки останова реализуют интерполяцию, используя несколько другие вычисления, чем неравномерный случай. Основным различием является то, что вычисления не используют непосредственно точки останова. Когда точки останова не требуются в ПЗУ, можно сэкономить много памяти.
xNum = uAngle - ( iLeft * 455U ); yDiff = yeven[iLeft+1] - yeven[iLeft]; MUL_S32_S16_U16( bigProd, yDiff, xNum ); DIV_NZP_S16_S32_U16_FLOOR( yDiff, bigProd, 455U ); yEven = yeven[iLeft] + yDiff;
Степень двойки разнесенных точек останова реализует интерполяцию, используя очень разные вычисления, чем два других случая. Как и в четном случае, точки останова не используются в сгенерированном коде и поэтому не требуются в ПЗУ.
lambda = uAngle & 0x00FFU; yPow2 = ypow2[iLeft)+1] - ypow2[iLeft]; MUL_S16_U16_S16_SR8(yPow2,lambda,yPow2); yPow2 += ypow2[iLeft];
Эта реализация имеет значительные преимущества перед неровными и даже реализациями:
Битовая AND, объединенная со сдвигом прямо в конце умножения, заменяет вычитание и деление.
Термин (u - xData[iLeft] ) / ( xData[iRght] - xData[iLeft]) не приводит к потере точности, потому что интервал является степенью двойки.
Напротив, неравномерные и даже случаи обычно вносят ошибку округления в этом вычислении.
В следующей таблице суммированы эффекты интервалов между точками останова для скорости выполнения, ошибки и использования памяти.
Параметр | Четная степень 2-х разнесенных данных | Равномерно разнесенные данные | Неравномерно разнесенные данные |
|---|---|---|---|
Скорость выполнения | Скорость выполнения самая быстрая. Поиск и интерполяция положения те же, что и для данных с равномерными интервалами. Однако, чтобы увеличить скорость, битовый сдвиг заменяет поиск положения, и битовая маска заменяет интерполяцию. | Скорость выполнения быстрее, чем для неравномерно разнесенных данных, потому что поиск положения быстрее, и интерполяция требует простого деления. | Скорость выполнения является самой медленной из различных интервалов, потому что поиск положения медленнее, и интерполяция требует большего количества операций. |
Ошибка | Ошибка может быть больше, чем ошибка для неравномерно разнесенных данных, потому что для аппроксимации функции с неоднородной кривизной требуется больше точек, чтобы достичь той же точности. | Ошибка может быть больше, чем ошибка для неравномерно разнесенных данных, потому что для аппроксимации функции с неоднородной кривизной требуется больше точек, чтобы достичь той же точности. | Ошибка может быть меньше, потому что для аппроксимации функции с неоднородной кривизной требуется меньше точек, чтобы достичь той же точности. |
Использование ПЗУ | Использует меньше ПЗУ команд, но больше ПЗУ данных. | Использует меньше ПЗУ команд, но больше ПЗУ данных. | Использует больше командного ПЗУ, но меньше ПЗУ данных. |
Использование оперативной памяти | Несущественный. | Несущественный. | Несущественный. |
Количество точек данных Y соответствует ожидаемому шаблону. Для той же самой ошибки в худшем случае неограниченный интервал (неровный) требует наименьшего количества точек данных, а степени - двух-разнесенных точек останова - больше всего. Однако реализация для равномерно разнесенных и степени двойки случаев не нуждается в точках останова в сгенерированном коде. Это уменьшает требования к ПЗУ данных в два раза. В результате равномерно разнесенный случай фактически использует меньше ПЗУ данных, чем неравномерно разнесенный случай. Кроме того, степень двойки случаев требует лишь немного больше ПЗУ, чем у неравномерного случая. Изменение ошибки наихудшего случая может изменить эти рейтинги. Тем не менее, при сравнении использования ПЗУ данных всегда следует учитывать тот факт, что равномерные интервалы и степень двойки разнесенных случаев не требуют их точек останова в ПЗУ.
Усилия по определению, где вход тока относительно точек останова, решительно благоприятствуют равномерно распределенным и степени двойки разнесенных случаев. С неравномерным интервалом вы используете двоичный метод поиска, который зацикливается до log2 (N) раз. При четности и степени двойки интервалов можно определить местоположение с выполнением одной линии кода С Но вы не можете решить относительные преимущества степени двойки от равномерно разнесенных без детального знания оборудования и компилятора C.
Усилие вычисления интерполяции благоприятствует степени двойки случаев, которая использует побитовую операцию AND и сдвиг, чтобы заменить вычитание и деление. Преимущество такого поведения зависит от конкретного оборудования, но можно ожидать преимущества в размере кода, скорости, а также в точности. Равномерно разнесенный случай вычисляет интерполяцию с незначительным улучшением эффективности по неравномерно разнесенному случаю.