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