Разделы, которые следуют, сравнивают реализации интерполяционных таблиц, которые используют точки останова, интервал которых является неравномерным, даже, и степень двойки. Сравнение фокусируется на:
Скорость выполнения команд
Погрешность округления во время интерполяции
Сумма постоянной памяти (ROM) для данных
Сумма ROM для команд
Это сравнение допустимо только, когда точки останова не являются настраиваемыми. Если точки останова являются настраиваемыми в сгенерированном коде, все три случая генерируют тот же код. Для сводных данных эффектов интервала точки останова на скорости выполнения ошибка и использование памяти, видят Сводные данные Эффектов Интервала Точки останова.
Это сравнение использует модель fxpdemo_approx_sin. Три интерполяционных таблицы фиксированной точки появляются в этой модели. Все три таблицы аппроксимируют функциональный sin(2*pi*u) по первому квадранту и достигают ошибки худшего случая меньше, чем 2^-8. Однако у них есть различные ограничения на их интервал точки останова.
Можно использовать модель fxpdemo_approx, который fxpdemo_approx_sin открывается, чтобы сгенерировать Simulink® Код Coder™ (требуемая лицензия на программное обеспечение Simulink Coder). Разделы, которые следуют за подарком несколько сегментов сгенерированного кода, чтобы подчеркнуть основные отличия.
Чтобы открыть модель, введите в MATLAB® подсказка:
fxpdemo_approx_sin
Этот раздел смотрит на данные ROM, требуемый каждой из трех опций интервала.
Неравномерный интервал требует и точек данных 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;
}
}Цикл с условием продолжения выполняет до log2 (N) времена, где N является количеством точек останова.
Равномерно распределенные точки останова требуют, чтобы только один шаг определил, где вход находится относительно точек останова:
iLeft = uAngle / 455U;
Делитель 455U представляет интервал между точками останова. В общем случае дивидендом был бы (uAngle - SmallestBreakPoint). В этом примере самая маленькая точка останова является нулем, таким образом, код оптимизирует вычитание.
Распределенные точки останова степени двойки требуют, чтобы только один шаг определил, где вход находится относительно точек останова:
iLeft = uAngle >> 8;
Количество рабочих смен - 8, потому что точки останова имеют интервал 2^8. Самая маленькая точка останова является нулем, таким образом, uAngle заменяет общий случай (uAngle - SmallestBreakPoint).
Чтобы определить, где вход находится относительно точек останова, неравномерно расположенный с интервалами случай требует намного большего количества кода, чем другие два случая. Этот код требует дополнительной команды ROM. Если много интерполяционных таблиц совместно используют алгоритм двоичного поиска как функцию, можно уменьшать этот штраф 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-битного процессора.
Равномерно распределенные точки останова реализуют интерполяцию с помощью немного отличающихся вычислений, чем неровный случай. Основное отличие - то, что вычисления непосредственно не используют точки останова. Когда точки останова не требуются в ROM, можно сохранить большую память.
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;
Степень двойки расположила интерполяцию реализации точек останова с интервалами с помощью совсем других вычислений, чем другие два случая. Как в ровном случае, точки останова не используются в сгенерированном коде и поэтому не требуются в ROM.
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 расположенных с интервалами данных | Равномерно распределенные данные | Неравномерно распределенные данные |
|---|---|---|---|
Скорость выполнения | Скорость выполнения является самой быстрой. Поиск положения и интерполяция эквивалентны для равномерно расположенных с интервалами данных. Однако, чтобы увеличить скорость больше, немного сдвига заменяет поиск положения, и немного маски заменяет интерполяцию. | Скорость выполнения быстрее, чем это для неравномерно расположенных с интервалами данных, потому что поиск положения быстрее, и интерполяция требует простого деления. | Скорость выполнения является самой медленной из различных интервалов, потому что поиск положения медленнее, и интерполяция требует большего количества операций. |
Ошибка | Ошибка может быть больше, чем это для неравномерно расположенных с интервалами данных, потому что аппроксимация функции с неоднородным искривлением требует, чтобы больше точек достигло той же точности. | Ошибка может быть больше, чем это для неравномерно расположенных с интервалами данных, потому что аппроксимация функции с неоднородным искривлением требует, чтобы больше точек достигло той же точности. | Ошибка может быть меньшей, потому что аппроксимация функции с неоднородным искривлением требует, чтобы меньше точек достигло той же точности. |
Использование ROM | Использование меньше команды ROM, но больше данных ROM. | Использование меньше команды ROM, но больше данных ROM. | Использование больше команды ROM, но меньше данных ROM. |
Использование оперативной памяти | Не значительный. | Не значительный. | Не значительный. |
Количество точек данных Y следует за ожидаемым шаблоном. Для той же ошибки худшего случая неограниченный (неравномерный) интервал требует наименьшего количества точек данных, и степень двух расположенных с интервалами точек останова требует большинства. Однако для реализации для равномерно расположенного с интервалами и случаи степени двойки не нужны точки останова в сгенерированном коде. Это уменьшает их данные требования ROM наполовину. В результате равномерно расположенный с интервалами случай на самом деле использует меньше данных ROM, чем неравномерно расположенный с интервалами случай. Кроме того, случай степени двойки требует незначительно большего количества ROM, чем неровный случай. Изменение ошибки худшего случая может изменить эти рейтинги. Тем не менее, когда вы сравниваете данные использование ROM, необходимо всегда учитывать то, которые равномерно расположенный с интервалами и распределенные случаи степени двойки не требуют их точек останова в ROM.
Усилие по определению, где текущий вход относительно точек останова строго, способствует равномерно расположенный с интервалами, и степень двойки расположила случаи с интервалами. С неравномерным интервалом вы используете метод двоичного поиска что циклы до log2 (N) времена. С даже и интервал степени двойки, можно определить местоположение с выполнением одной линии кода С. Но вы не можете решить относительные преимущества степени двойки по сравнению с равномерно расположенным с интервалами без детального знания оборудования и компилятора C.
Усилие по вычислению интерполяции способствует случаю степени двойки, который использует поразрядную операцию И и сдвиг, чтобы заменить вычитание и деление. Преимущество этого поведения зависит от определенного оборудования, но можно ожидать преимущество в размере кода, скорости, и также в точности. Равномерно расположенный с интервалами случай вычисляет интерполяцию с незначительным улучшением КПД по неравномерно расположенному с интервалами случаю.