Диссертация (1150736), страница 11
Текст из файла (страница 11)
Принципиальным отличием системы от обычного тестирования являетсягарантированное обнаружение ошибок, даже если вероятность их воспроизведения тестом пренебрежимо мала, но отлична от нуля.Условия отсутствия тупиков и конкурентной модификации автоматическиизвлекаются из модели.
Поскольку понятие полезной работы зависит от алгоритма, то для обнаружения повисаний используется пользовательская разметка в исходном коде. Пользовательская разметка имеет вид условных выражений на языке C++, что существенно упрощает ее применение разработчикамипо сравнению с языками контрактов на основе темпоральных логик.Проблемой подхода на основе статического анализа является большое количество ложных срабатываний [70]. Для уменьшения влияния этой проблемысистема поддерживает контракты, определенные пользователем, для маркиро-57вания нереализуемых состояний в исходном коде, таким образом, система небудет обнаруживать ложные срабатывания повторно.Инструментальное средство “Aegis for SystemC” поддерживает большоеподмножество C++, SystemC и STL. В процессе тестирования оно было применено к 21 модели программно-аппаратных систем с более чем 30К строккода (не считая комментариев) и продемонстрировало возможность обнаружения реальных ошибок синхронизации.Примененный подход использует технику абстрактной интерпретации исходного кода [71] для определения множества возможных состояний модели.Эта техника подобна исполнению кода, но значения переменных описываютсяне как скалярные значения, а как абстрактные домены значений, что позволяетсократить сложность анализа за счет склеивания путей исполнения и исключения экспоненциального роста пространства состояний.58Глава 2Аппаратное ускорениевычисления элементарныхфункций при помощиспециализированныхвычислительных блоковВычисление элементарных функций от массивов данных является важнойсоставляющей многих алгоритмов цифровой обработки сигналов.
Вычисление может быть реализовано программно на процессоре или как специализированная логическая схема. Алгоритмически могут использоваться разложения в ряд функции на всем интервале, кусочно-полиномиальная интерполяция, сплайны. Программная реализация не является энергоэффективной длябольших объемов вычислений, поскольку накладные расходы на выборку идекодирование инструкций и доступ к памяти таблиц сопоставимы с затратами на вычисления. При аппаратной реализации часто используется схемаCORDIC со скоростью вычислений один такт на бит точности.
Схема CORDICвысокоэффективная, но очень медленная. При больших объемах вычислениймалая скорость работы может вывести схему за границы участка линейного масштабирования мощности от частоты. Кроме того, другие компоненты59в простое будут потреблять энергию из-за токов утечки, поскольку отключение от питания возможно только для крупных блоков целиком.
В случаебольших объемов вычислений, которые не могут быть табулированы, применяются другие методы. Для точностей менее 18 бит обычно применяютсяалгоритмы кусочно-линейной аппроксимации, поскольку они могут быть реализованы без использования умножителей только при помощи суммированияи сдвига. Для больших точностей более эффективными являются аппаратнореализованные алгоритмы кусочно-полиномиальной аппроксимации, обеспечивающие вычисление одного значения с задержкой запуска в один такт и произвольной точностью. Такие вычислительные компоненты, как умножители исумматоры, могут также переиспользоваться в других алгоритмах, например,БПФ.При разработке специализированной схемы точности таблиц и промежуточных данных не ограничены шириной машинного слова и могут быть произвольными.
Для таких схем важной с точки зрения энергоэффективности является минимизация размера таблиц и точности вычислений при сохранениитребуемой точности результата.Задача кусочно-полиномиальной аппроксимации в целом считается решенной для вычислений с плавающей точкой на программируемых устройствах. Спомощью метода Ремеза можно найти интерполяционный многочлен наилучшего равномерного приближения и его узлы интерполяции. Также известнаоценка ошибки аппроксимации по невязке в узлах интерполяции, которая возникает из-за округления коэффициентов многочлена.В практической постановке задачи при разработке специализированногоустройства требуется найти минимальные ширины таблиц при заданном ограничении на точность аппроксимации.
Метод Ремеза не позволяет решить этузадачу. Кроме округления, другим способом сокращения размера таблиц является переиспользование коэффициентов между сегментами. Для аппроксимации функций часто используются гладкие сплайны. Описанная выше задачааппроксимации не накладывает требований на гладкость, однако дополнительные ограничения позволяют уменьшить размер таблиц. Требования гладкостиявляются чрезмерно сильными и могут приводить к увеличению количества60сегментов аппроксимации. Поэтому будем рассматривать почти гладкий квазисплайн с минимальными невязками.Для нахождения кусочно-полиномиальной аппроксимации с минимальными таблицами и аппроксимации почти гладким квазисплайном с минимальными невязками сведем задачу к задаче смешанного целочисленного программирования.Использование предложенных методов приводит к существенному сокращению размера таблиц.
Прототипирование показывает практическое влияниеэтого сокращения на площадь и энергопотребление вычислительного блока.2.1Постановка задачи аппроксимации с заданнойточностьюОпределим требования к точности при вычислении в точно представимыхточках‖ − ‖ = sup |( − )()| < = 2− .∈[,]Здесь - аппроксимирующая функция, - количество бит в дробной частипредставления с фиксированной точкой.Определение 1 Назовем округленный (квантизованный) метод вычисленийконсервативным при выполнении следующего неравенства:‖ − ‖ ≤ ‖ − ‖ + ‖ − ‖ = + < ,где - наилучшая аппроксимация с аппаратно представимыми коэффициентами, - аппаратно вычислимые значения с ошибкой округления, ошибка аппроксимации и округления коэффициентов, - ошибка округлениявычислений.Для ошибки округления вычислений выполняется следующая нижняяоценка: ≥)︀ (︀1 + 2− ,261где - количество дополнительных защитных битов в вычислительном блоке Ошибка округления вычислений складывается из ошибки округления привычислении с дополнительными битами и финального округления до бит.Можно подобрать параметры округления вычислений таким образом, чтобы выполнялось неравенство ≤)︀ (︀1 + 2− ,2где - количество дополнительных битов точности таблиц.
Таким образом,можно установить следующее априорное требование к точности метода аппроксимации:)︀ (︀1 − 2− .2От требования консервативности можно отказаться, поскольку точки с ≤максимальной ошибкой аппроксимации и округления вычислений обычно несовпадают. Такая оптимизация позволяет дополнительно уменьшить площадьвычислительных компонент блока на 10% и более. Но для этого требуетсяполный перебор всех представимых точек, что при точностях более 25 битприводит к большому времени вычислений. Для больших точностей требование консервативности позволяет решать каждую задачу отдельно аналитическими методами, что сокращает пространство поиска и делает их практическиразрешимыми.2.2Задача уменьшения размера таблицПусть функция задана на промежутке [, ].
Пусть возрастающий наборточек ( )=0 разбивает этот промежуток на равных отрезков. Сужение функции обозначим = |[ ,+1 ] при 0 ≤ ≤ − 1.Определение 2 Пусть > 0. Набор многочленов { }−1=0 назовём квазисплайном степени , аппроксимирующим с точностью , если в равномернойметрике‖ − ‖[ ,+1 ] ≤ ,deg ≤ ,620 ≤ ≤ − 1.Задача расчёта элементарных функций сводится к подбору аппроксимирующих квазисплайнов заданной точности и минимальной сложности, которойв данном случае является длина таблицы. Если требуемой аппроксимации несуществует, то область определения разбивается на более мелкие отрезки,для каждого из которых рассматривается та же задача.Рассмотрим дефекты гладкости квазисплайна()(), = ( ) − −1 ( ),0 < < .Если для любых , < , , = 0, то квазисплайн { } является гладкимсплайном минимального дефекта.
Из существования квазисплайна для данного набора (, , , ) в общем случае не следует существования сплайнаминимального дефекта для того же набора (, , , ).Квазисплайн полностью определяется коэффициентами ( , {, }). Дляхранения требуется таблица в среднем в раз меньше, чем для хранениявсех { }. В предположении гладкости можно также ожидать, что все ,малы. Если = 2 , то аппаратная реализация вычисления квазисплайна понабору коэффициентов ( , {, }) несущественно усложняется по сравнениюс { }, поскольку требует только дополнительных целочисленных сумматоров и сдвигов, которые существенно проще уже используемых умножителей.Таким образом, хранение коэффициентов ( , {, }) вместо { } приводит ксущественному уменьшению сложности аппаратной реализации аппроксимации.Предположим, что таблица в аппаратуре представлена как логическаяфункция в дизъюнктной нормальной форме (ДНФ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
