Введение
Аппаратная реализация вычислительных систем цифровой обработки сигналов (ЦОС) насыщенна и очень сложна. Поэтому отказы процессорных элементов в таких процессорных матрицах практически неизбежны, и обеспечение отказоустойчивости должно быть неотъемлемой частью разработки специализированных процессоров (СП), особенно для применений в реальном времени.
Основная часть
В настоящее время в вычислительных системах широкое распространение получил целый ряд методов обеспечения отказоустойчивости. Несмотря на их многообразие, данные методы можно разделить на три основные группы, которые в своей основе используют следующие виды избыточности:
- аппаратную избыточность;
- временную избыточность;
- алгоритмическую избыточность, основанную на корректирующих кодах.
Обеспечение отказоустойчивости СП ЦОС во время работы является наиболее сложным [1-4]. Главная цель состоит в том, чтобы гарантировать непрерывность функционирования крупного матричного процессора во время его работы. Обеспечение отказоустойчивости на этом этапе включает тестирование, реконфигурацию и перезапуск. При разработке отказоустойчивых вычислительных устройств ставятся задачи [1]:
- использовать регулярность и локальность, присущую матричным процессорам, и принцип управления потоком данных;
- выявить структурные особенности матричных алгоритмов;
- минимизировать затраты времени на реализацию отказоустойчивой работы.
Особое место среди методов обеспечения отказоустойчивости многопроцессорных вычислительных устройств занимают методы, построенные на основе временной избыточности. В настоящее время наибольшее распространение получили два способа использования временной избыточности:
1. обнаружение и исправление ошибок, основанное на чередовании графов зависимости данных;
2. амортизация отказов, основанная на алгоритмах разбиения.
Одно из основных предположений данного подхода к отказоустойчивости (ОУ) состоит в том, что каждый процессорный элемента (ПЭ) может некоторым способом выполнять самопроверку. Поэтому неисправность, возникшая в процессе вычислений, диагностируется прежде, чем неисправный ПЭ выдаст свои, возможно, неверные результаты. В этом случае необходимости в возврате нет, поскольку предполагается, что период действия ошибки минимален.
Однако, несмотря на то, что схемы временной избыточности, представляют эффективные способы восстановления в случае возникновения отказов, к сожалению, они не могут быть легко интегрированы в структурные схемы обеспечения отказоустойчивости СП ЦОС из-за высоких требований к производительности таких вычислительных устройств.
В настоящее время существуют два типа подходов к обеспечению ОУ во время работы – архитектурный и алгоритмический. Архитектурные подходы являются алгоритмически независимыми [2]. Так в случае фиксированного размера процессорных массивов с помощью переключателей можно произвести реконфигурацию массива таким образом, что, несмотря на отказ некоторых ПЭ, размер массива сохранится. Другой подход состоит в маскировании отказов, т.е. немедленном восстановлении работоспособности устройства, при котором возникновение отказа не замечается. Этот способ эффективен для достижения динамической ОУ и может быть реализован с помощью трехкратной аппаратурной избыточности или в общем случае N-кратной избыточности.
С другой стороны, алгоритмические подходы к ОУ используют некоторые алгебраические свойства, присущие многим приложениям ЦОС. Одним из подходом, например, является обеспечение ОУ на основе кодирования данных, позволяющие восстановить правильный результат при неисправном ПЭ. Можно одновременно перестраивать структуру процессорного массива и алгоритм так, чтобы задача оказалась выполнимой на массиве меньшего размера. Этот подход позволяет строить вычислительные структуры с амортизацией отказов.
Важным в обеспечении ОУ в процессе работы является устранение сбоев [3]. Известно, что частота возникновения сбоев, вызванных главным образом временными изменениями условий функционирования, в десятки раз превышают частоту постоянных неисправностей. Поскольку продолжительность перемежающихся неисправностей – величина случайная, некоторые из них можно трактовать как постоянные и использовать повторное выполнение. Вообще говоря, восстановление работы при перемежающихся неисправностях значительно повышает надежность всей вычислительной системы.
Анализ технических реализаций алгоритмов ЦОС показывает, что архитектура СП, его функциональные характеристики, прежде всего, определяются алгебраической системой, на базе которой строится цифровая обработка сигналов. Таким образом, правильный выбор алгебраической системы является мощным средством повышения устойчивости функционирования вычислительных устройств ЦОС. Большое значение при этом имеет также способность системы счисления аккумулировать свою естественную (первичную) избыточность и вводимую дополнительную (вторичную) избыточность.
Основную массу вычислительных устройств ЦОС составляют СП, базирующиеся на математических моделях с позиционной системой счисления (ПСС). В ПСС выполнение арифметической операции полагает последовательную обработку разрядов операндов по правилам, определяемым содержанием данной операции, и не может быть закончено до тех пор, пока не будут определены последовательно значения всех результатов с учетом всех связей между разрядами. Таким образом, ПСС, являясь основой современных вычислительных средств, имеет строго последовательную структуру и обладает минимальной первичной избыточностью. Это в свою очередь обуславливает необходимость принятия дополнительных мер по введению вторичной избыточности, что накладывает существенный отпечаток на способы реализации обеспечения отказоустойчивости вычислительных систем в процессе функционирования.
По способу введения вторичной (структурной, информационной и др.) избыточности существующие методы повышения устойчивости функционирования СП ПСС цифровой обработки информации можно разбить на два основных класса. К первому относятся методы обеспечения отказоустойчивости, реализующие различные варианты кодирования данных. Несмотря на свою привлекательность с точки зрения обеспечения информационной надежности, позиционные коды, как правило, не обладают арифметичностью. Именно это свойство специальных кодовых конструкций препятствует их широкому применению в вычислительных устройствах ЦОС, поскольку введенные избыточные разряды не позволяют контролировать результаты арифметических операций в реальном масштабе времени [1].
Ввиду указанного обстоятельства в последние годы наблюдается рост исследований в сфере разработки методов, базирующихся на использовании кодов, обладающих свойством арифметичности. Важнейшая особенность данных методов заключается в возможности организации пространственного распределения совмещенных во времени вычислительных процессов цифровой обработки информации или их составляющих. Обращаясь к машинным алгоритмам, базирующимся на многопроцессорной структуре вычислительного устройства, легко заметить, что благодаря параллелизму на уровне вычислительных процессов повышается не только производительность, но и отказоустойчивость системы. Параллельные вычислительные процедуры являются идеальной основой для синтеза устойчивых к отказам вычислительных систем. Ключевую роль в процессе построения таких вычислительных устройств играет способность сохранения работоспособного состояния за счет снижения в допустимых пределах каких-либо показателей качества при возникновении отказов в системе. Достоинства данного подхода к выполнению процедур обеспечения отказоустойчивости реализуется в полной мере при перераспределении исходных данных и сохранившихся вычислительных ресурсов при деградации структуры [1]. В тоже время многопроцессорные вычислительные устройства обладают рядом существенных недостатков, которые сужают сферу их применения. Основными из них являются:
- значительные аппаратурные и программные затраты необходимые на реализацию вычислительной системы;
- необходимость разработки новых алгоритмов ЦОС, обладающих полным параллелизмом;
- сложность реализации процедур поиска и локализации ошибок в процессе вычислений;
- возможность потери части обрабатываемых данных при восстановлении работоспособной структурной конструкции вычислительной системы.
Таким образом, применение рассмотренных выше методов обеспечения устойчивости функционирования цифровых устройств, базирующихся на принципах распараллеливания на уровне вычислительных процессоров, является нецелесообразным.
Выход из указанной ситуации может быть найден на пути применения алгебраических систем конечного поля и кольца для реализации цифровых систем обработки информации, базирующихся на максимально независимых функциональных компонентах вычислительных средств и обладающих поразрядным характером распространения ошибок при выполнении последовательности арифметических операций.
Применение полиномиальной системы классов вычетов, в которой в качестве модулей непозиционной системы используются минимальные многочлены расширенного поля Галуа p1(z), h2(z), ... , p3(z) позволяет задать следующее отображение
, (1)
где
.
Обратный изоморфизм задается отображением
, (2)
где
;
Применяя выражения (1) и (2) соответственно к алгоритмам цифровой обработки сигналов получаем
, (3)
. (4)
Обладая однородным составом арифметических устройств, высоким параллелизмом на уровне арифметических операций, вычислительные системы ПСКВ полностью соответствуют алгоритмам ЦОС и обеспечивают реализацию последних в реальном масштабе времени. Кроме этого, ПСКВ обладает достоинствами[1,3,10]:
- независимость разрядов обуславливает возможность построения автономных вычислительных трактов (каналов) по каждому основанию и позволяет считать последние независимыми элементами;
- равноправность разрядов дает возможность изменения функциональных назначений последних, выражающуюся в переводе информационных вычислительных каналов в множество избыточных и наоборот;
- использование табличных методов реализации арифметических операций обуславливает малый разброс надежностных характеристик вычислительных каналов;
- отсутствие межразрядных переносов по основаниям ПСКВ.
Из сказанного выше видно, что существующее состояние разработок по теории ПСКВ обеспечивает потенциальную возможность повышения не только производительности реализаций арифметических операций, но и информационной надежности вычислительной системы в целом. Поэтому очевидна актуальность разработки алгоритмов построения корректирующих кодов ПСКВ [2,8,9].
Для осуществления процедур поиска и коррекции в полиномиальной системе классов вычетов используют позиционные характеристики. Последние позволяют определить «позиционирование» запрещенных непозиционных комбинаций относительно рабочего диапазона, величина которого определяется произведением рабочих оснований. В настоящее время известен целый ряд так характеристик. В работе [5] для определения местоположения и глубины ошибки используют позиционную характеристику – след полинома. С этой целью используются псевдоортогональные полиномы. Вычисление разности полинома A(z), представленного в полиномиальной системе классов вычетов, и псевдоортогональных форм, задаёт величину следа полинома (5)
где
, – нарушение ортогональности по контрольным основаниям ПСКВ.
Применение алгоритма (5) позволяет обеспечивать вычисление этой позиционной характеристики с меньшими временными затратами по сравнению с классическим алгоритмом.
Для обнаружения и коррекции ошибочных кодовых комбинаций ПСКВ в работе [2] применяют алгоритм вычисления интервального полинома кода ПСКВ
, (6)
где K*(z) – ранг безизбыточной системы оснований ПСКВ;
;
– ортогональный базис;
– рабочий диапазон.
При этом ранг безизбыточной системы определяется выражением
. (7)
Использование данной позиционной характеристики позволяет осуществлять процедуры коррекции запрещенных комбинаций на основе нейросетевого логического базиса.
Наряду с позиционными характеристиками модулярного кода, для построения отказоустойчивых спецпроцессоров класса вычетов, могут использоваться и характеристики, которые вычисляются в «частотной» области. В работе [4] приведен алгоритм вычисления спектральных составляющих кодовой комбинации ПСКВ, который базируется на определении корней интервального полинома. Дальнейшее развитие данного алгоритма позволило разработать устройство, реализующее данный алгоритм. В работе [7] приведена структура такого устройства.
Кроме того, ПСКВ расширенного поля Галуа обладает способностью к варьированию точностью, быстродействием и информационной надежностью в процессе вычисления. Данная способность базируется на обменных операциях ПСКВ. В настоящее время проявляется повышенный интерес к возможности варьирования корректирующей способностью модулярного кода за счет изменения точности и производительности вычислений в пределах одного цифрового устройства. В первую очередь это объясняется тем, что учет указанного свойства ПСКВ является мощным средством повышения надежности, т.е. при отказе r каналов их можно просто удалить из процессора, не оказывая влияния на точность выполнения задания. Но с другой стороны данные r избыточных каналов предопределяют корректирующие способности вычислительной системы, другими словами – гарантию защиты от недостоверного результата.
Таким образом, изменяя количество информационных k и избыточных r оснований в заданной структуре СП ПСКВ, можно варьировать его основными показателями – точностью, информационной надежностью вычислительной системы.
Если некоторая упорядоченная ПСКВ расширяется путем добавления l оснований, каждое из которых больше основания исходной ПСКВ, то минимальное кодовое расстояние dmin автоматически увеличивается. Того же эффекта можно добиться, уменьшая число информационных оснований, т.е. переходя к вычислениям с меньшей точностью. На одном и том же СП можно одни и те же вычисления выполнять с высокой точностью, но с меньшей информационной надежностью или с меньшей точностью, но с более высокими значениями надежности и скорости.
Таким образом, очевидно, что ПСКВ обладает свойством, позволяющим ей гибко использовать резервы точности и надежности при наличии ограничений на увеличение веса, габаритов и стоимости цифрового устройства.
В работе [6] приведен алгоритм позволяющий осуществлять перевод полиномиального модулярного кода в позиционный код на основе китайской теоремы об остатках при постепенной деградации структуры СП ЦОС. Использование данного алгоритма позволяет обеспечить сохранение работоспособного состояния вычислительного устройства за счет снижения в допустимых пределах основных показателей качества функционирования. В работе [6] представлена структура преобразователя из модулярного кода в позиционный код с пересчетом значений ортогональных базисов. Хорошие реализационные свойства вышеуказанной особенности ПСКВ, заключающиеся в возможности варьирования точностью, производительностью и корректирующими способностями, представляют собой идеальную основу для разработки высокоэффективных методов реконфигурации вычислительных устройств ЦОС класса вычетов.
Выводы
Внедрение математической модели ПСКВ, позволяющей представлять числа в модулярном коде, является одним из наиболее перспективных путей повышения отказоустойчивости и быстродействия вычислительных средств ЦОС.
В этом случае преимущества модулярной арифметики реализуются наиболее полно как в направлении обеспечения высокой отказоустойчивости, так и в направлении повышения производительности функционирования СП ЦОС.
Библиографическая ссылка
Мартиросян А.Г., Калмыков М.И. ОСНОВНЫЕ МЕТОДЫ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ СПЕЦИАЛИЗИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ // Современные наукоемкие технологии. – 2014. – № 3. – С. 62-67;URL: https://top-technologies.ru/ru/article/view?id=34112 (дата обращения: 20.04.2024).