Основные методы обеспечения отказоустойчивости специализированных вычислительных устройств цифровой обработки сигналов

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы естественных и точных наук


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 3
ОСНОВНЫЕ МЕТОДЫ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ СПЕЦИАЛИЗИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
Мартиросян А. Г., Калмыков М. И.
ФГАОУ ВПО «Северо-Кавказский федеральный университет», Ставрополь,
e-mail: kia762@yandex. ru
Эффективность цифровой обработки сигналов (ЦОС) полностью определяется объемом вычислений, которые получаются при реализации математической модели процесса цифровой обработки сигнала с помощью специализированного процессора. Рассмотрены основные виды обеспечения отказоустойчивости специализированных процессоров ЦОС. Проведенный в работе анализ этих методов показал, что наиболее привлекательным, с точки зрения сохранения работоспособного состояния вычислительного устройства при возникновении отказов оборудования, является применения корректирующих кодов. При этом данные коды должны обладать свойством арифметичности и соответствовать алгебраической системе, которая используется при ортогональных преобразованиях сигналов. Рассмотрены основные алгоритмы поиска и коррекции ошибок с использованием полиномиальной системы классов вычетов.
Ключевые слова: алгоритмы отказоустойчивости, корректирующие коды, полиномиальная система классов вычетов, позиционные характеристики кода, деградация структуры процессора
BASIC METHODS RESILIENCY SPECIALIZED COMPUTING DEVICES DIGITAL SIGNAL PROCESSING Martirosyan A.G., Kalmykov M.I.
Federal state Autonomous educational institution higher professional education «North-Caucasian federal university», Stavropol, e-mail: kia762@yandex. ru
The efficiency of digital signal processing (DSP) is completely defined by the volume of calculations, which are obtained by implementing a mathematical model of the digital signal processing by a dedicated processor. The basic kinds of resiliency specialized DSP processors. Carried out in the analysis of these methods showed that the most attractive in terms of maintaining a healthy state of the computing device in the event of equipment failure, is the application of error-correcting codes. The data codes must have the property is arithmetic and algebraic fit system that is used under orthogonal transformations of signals. The basic search algorithms and error correction using a polynomial system of residue classes.
Keywords: algorithms fault tolerance, error-correcting codes, polynomial system of residue classes, positional code characteristics, the degradation of the structure of the processor
Введение
Аппаратная реализация вычислительных систем цифровой обработки сигналов (ЦОС) насыщенна и очень сложна. Поэтому отказы процессорных элементов в таких процессорных матрицах практически неизбежны, и обеспечение отказоустойчивости должно быть неотъемлемой частью разработки специализированных процессоров (СП), особенно для применений в реальном времени.
Основная часть
В настоящее время в вычислительных системах широкое распространение получил целый ряд методов обеспечения отказоустойчивости. Несмотря на их многообразие, данные методы можно разделить на три основные группы, которые в своей основе используют следующие виды избыточности:
— аппаратную избыточность-
— временную избыточность-
— алгоритмическую избыточность, основанную на корректирующих кодах.
Обеспечение отказоустойчивости СП ЦОС во время работы является наиболее сложным [1−4]. Главная цель состоит в том, чтобы гарантировать непрерывность функционирования крупного матричного процессора во время его работы. Обеспечение отказоустойчивости на этом этапе включает тестирование, реконфигурацию и перезапуск. При разработке отказоустойчивых вычислительных устройств ставятся задачи [1]:
— использовать регулярность и локальность, присущую матричным процессорам, и принцип управления потоком данных-
— выявить структурные особенности матричных алгоритмов-
— минимизировать затраты времени на реализацию отказоустойчивой работы.
Особое место среди методов обеспечения отказоустойчивости многопроцессорных вычислительных устройств занимают методы, построенные на основе временной избыточности. В настоящее время наиболь-
шее распространение получили два способа использования временной избыточности:
1. обнаружение и исправление ошибок, основанное на чередовании графов зависимости данных-
2. амортизация отказов, основанная на алгоритмах разбиения.
Одно из основных предположений данного подхода к отказоустойчивости (ОУ) состоит в том, что каждый процессорный элемента (ПЭ) может некоторым способом выполнять самопроверку. Поэтому неисправность, возникшая в процессе вычислений, диагностируется прежде, чем неисправный ПЭ выдаст свои, возможно, неверные результаты. В этом случае необходимости в возврате нет, поскольку предполагается, что период действия ошибки минимален.
Однако, несмотря на то, что схемы временной избыточности, представляют эффективные способы восстановления в случае возникновения отказов, к сожалению, они не могут быть легко интегрированы в структурные схемы обеспечения отказоустойчивости СП ЦОС из-за высоких требований к производительности таких вычислительных устройств.
В настоящее время существуют два типа подходов к обеспечению ОУ во время работы — архитектурный и алгоритмический. Архитектурные подходы являются алгоритмически независимыми [2]. Так в случае фиксированного размера процессорных массивов с помощью переключателей можно произвести реконфигурацию массива таким образом, что, несмотря на отказ некоторых ПЭ, размер массива сохранится. Другой подход состоит в маскировании отказов, т. е. немедленном восстановлении работоспособности устройства, при котором возникновение отказа не замечается. Этот способ эффективен для достижения динамической ОУ и может быть реализован с помощью трехкратной аппаратурной избыточности или в общем случае Л-кратной избыточности.
С другой стороны, алгоритмические подходы к ОУ используют некоторые алгебраические свойства, присущие многим приложениям ЦОС. Одним из подходом, например, является обеспечение ОУ на основе кодирования данных, позволяющие восстановить правильный результат при неисправном ПЭ. Можно одновременно перестраивать структуру процессорного массива и алгоритм так, чтобы задача оказалась
выполнимой на массиве меньшего размера. Этот подход позволяет строить вычислительные структуры с амортизацией отказов.
Важным в обеспечении ОУ в процессе работы является устранение сбоев [3]. Известно, что частота возникновения сбоев, вызванных главным образом временными изменениями условий функционирования, в десятки раз превышают частоту постоянных неисправностей. Поскольку продолжительность перемежающихся неисправностей — величина случайная, некоторые из них можно трактовать как постоянные и использовать повторное выполнение. Вообще говоря, восстановление работы при перемежающихся неисправностях значительно повышает надежность всей вычислительной системы.
Анализ технических реализаций алгоритмов ЦОС показывает, что архитектура СП, его функциональные характеристики, прежде всего, определяются алгебраической системой, на базе которой строится цифровая обработка сигналов. Таким образом, правильный выбор алгебраической системы является мощным средством повышения устойчивости функционирования вычислительных устройств ЦОС. Большое значение при этом имеет также способность системы счисления аккумулировать свою естественную (первичную) избыточность и вводимую дополнительную (вторичную) избыточность.
Основную массу вычислительных устройств ЦОС составляют СП, базирующиеся на математических моделях с позиционной системой счисления (ПСС). В ПСС выполнение арифметической операции полагает последовательную обработку разрядов операндов по правилам, определяемым содержанием данной операции, и не может быть закончено до тех пор, пока не будут определены последовательно значения всех результатов с учетом всех связей между разрядами. Таким образом, ПСС, являясь основой современных вычислительных средств, имеет строго последовательную структуру и обладает минимальной первичной избыточностью. Это в свою очередь обуславливает необходимость принятия дополнительных мер по введению вторичной избыточности, что накладывает существенный отпечаток на способы реализации обеспечения отказоустойчивости вычислительных систем в процессе функционирования.
По способу введения вторичной (структурной, информационной и др.) избыточности существующие методы повышения устойчивости функционирования СП ПСС цифровой обработки информации можно разбить на два основных класса. К первому относятся методы обеспечения отказоустойчивости, реализующие различные варианты кодирования данных. Несмотря на свою привлекательность с точки зрения обеспечения информационной надежности, позиционные коды, как правило, не обладают ариф-метичностью. Именно это свойство специальных кодовых конструкций препятствует их широкому применению в вычислительных устройствах ЦОС, поскольку введенные избыточные разряды не позволяют контролировать результаты арифметических операций в реальном масштабе времени [1].
Ввиду указанного обстоятельства в последние годы наблюдается рост исследований в сфере разработки методов, базирующихся на использовании кодов, обладающих свойством арифметичности. Важнейшая особенность данных методов заключается в возможности организации пространственного распределения совмещенных во времени вычислительных процессов цифровой обработки информации или их составляющих. Обращаясь к машинным алгоритмам, базирующимся на многопроцессорной структуре вычислительного устройства, легко заметить, что благодаря параллелизму на уровне вычислительных процессов повышается не только производительность, но и отказоустойчивость системы. Параллельные вычислительные процедуры являются идеальной основой для синтеза устойчивых к отказам вычислительных систем. Ключевую роль в процессе построения таких вычислительных устройств играет способность сохранения работоспособного состояния за счет снижения в допустимых пределах каких-либо показателей качества при возникновении отказов в системе. Достоинства данного подхода к выполнению процедур обеспечения отказоустойчивости реализуется в полной мере при перераспределении исходных данных и сохранившихся вычислительных ресурсов при деградации структуры [1]. В тоже время многопроцессорные вычислительные устройства обладают рядом существенных недостатков, которые сужают сферу их применения. Основными из них являются:
— значительные аппаратурные и программные затраты необходимые на реализацию вычислительной системы-
— необходимость разработки новых алгоритмов ЦОС, обладающих полным параллелизмом-
— сложность реализации процедур поиска и локализации ошибок в процессе вычислений-
— возможность потери части обрабатываемых данных при восстановлении работоспособной структурной конструкции вычислительной системы.
Таким образом, применение рассмотренных выше методов обеспечения устойчивости функционирования цифровых устройств, базирующихся на принципах распараллеливания на уровне вычислительных процессоров, является нецелесообразным.
Выход из указанной ситуации может быть найден на пути применения алгебраических систем конечного поля и кольца для реализации цифровых систем обработки информации, базирующихся на максимально независимых функциональных компонентах вычислительных средств и обладающих поразрядным характером распространения ошибок при выполнении последовательности арифметических операций.
Применение полиномиальной системы классов вычетов, в которой в качестве модулей непозиционной системы используются минимальные многочлены расширенного поля Галуар (г), И2(г), …, р3(г) позволяет задать следующее отображение
: А (г) ^ («1(2), а2(г),., а"(г)), (1)
где
М (г) = Пр,(г)-А (г) еМ (г) — а,(г) = /=1
= А (z)modр1 (г)-, = 1,…, п
Обратный изоморфизм задается отображением
-1: («1(г), «2(г),…, «п (г)) ^ А (г), (2)
где
А (г) = т1 (г) Р1 (г)а1 (г) + т2 (г)Р2 (г)а2 (г) +
+ … + тп (г) Рп (г)ап (г) —
Р!(г) = М (г)/р,(г) — т!(г) =
=(Р (г) mod р,(гУ)1 mod р,(г)
Применяя выражения (1) и (2) соответственно к алгоритмам цифровой обработки сигналов получаем
^ [X ('-)] = § ^ [х (У)]Р № ]
1=0
(3)
ристику — след полинома. С этой целью используются псевдоортогональные полиномы. Вычисление разности полинома А (2), представленного в полиномиальной системе классов вычетов, и псевдоортогональных форм, задаёт величину следа полинома (5)
ф (/)] = ?^[Х^-*]. (4)
1=0
Обладая однородным составом арифметических устройств, высоким параллелизмом на уровне арифметических операций, вычислительные системы ПСКВ полностью соответствуют алгоритмам ЦОС и обеспечивают реализацию последних в реальном масштабе времени. Кроме этого, ПСКВ обладает достоинствами[1,3,10]:
— независимость разрядов обуславливает возможность построения автономных вычислительных трактов (каналов) по каждому основанию и позволяет считать последние независимыми элементами-
— равноправность разрядов дает возможность изменения функциональных назначений последних, выражающуюся в переводе информационных вычислительных каналов в множество избыточных и наоборот-
— использование табличных методов реализации арифметических операций обуславливает малый разброс надежностных характеристик вычислительных каналов-
— отсутствие межразрядных переносов по основаниям ПСКВ.
Из сказанного выше видно, что существующее состояние разработок по теории ПСКВ обеспечивает потенциальную возможность повышения не только производительности реализаций арифметических операций, но и информационной надежности вычислительной системы в целом. Поэтому очевидна актуальность разработки алгоритмов построения корректирующих кодов ПСКВ [2,8,9].
Для осуществления процедур поиска и коррекции в полиномиальной системе классов вычетов используют позиционные характеристики. Последние позволяют определить «позиционирование» запрещенных непозиционных комбинаций относительно рабочего диапазона, величина которого определяется произведением рабочих оснований. В настоящее время известен целый ряд так характеристик. В работе [5] для определения местоположения и глубины ошибки используют позиционную характе-
Гк+1(2) = (А+1(2)& quot-Ё Ук*1(г))т°аPk+l (z), 1=1 к
Гк+2(= («к+2(2) & quot-Е Гк+2(г))т°& lt-1 Рк+2(1=1 к
Гк+г (г) = («к+г (г)& quot-Е 1(z))m°dРк+Г (2).
1=1
где 7к+1(2),…, Тк+г (2), — нарушение ортогональности по контрольным основаниям ПСКВ.
Применение алгоритма (5) позволяет обеспечивать вычисление этой позиционной характеристики с меньшими временными затратами по сравнению с классическим алгоритмом.
Для обнаружения и коррекции ошибочных кодовых комбинаций ПСКВ в работе [2] применяют алгоритм вычисления интервального полинома кода ПСКВ
'-'-иит (2)
(2)К, (2) + К *(2)
, (6)
Р» (2)
где К*(г) — ранг безизбыточной системы оснований ПСКВ-
К (2) =в, (2)/Рра6 (2)] -
В* (2) — ортогональный базис-
к
Р 6 (?) = Пр1 (2) — рабочий диапазон.
& quot- /=1
При этом ранг безизбыточной системы определяется выражением
К «=
?"1 (2)В* (2)Да6 (2)
. (7)
Использование данной позиционной характеристики позволяет осуществлять процедуры коррекции запрещенных комбинаций на основе нейросетевого логического базиса.
Наряду с позиционными характеристиками модулярного кода, для построения отказоустойчивых спецпроцессоров класса вычетов, могут использоваться и характеристики, которые вычисляются в «частотной»
1=1
области. В работе [4] приведен алгоритм вычисления спектральных составляющих кодовой комбинации ПСКВ, который базируется на определении корней интервального полинома. Дальнейшее развитие данного алгоритма позволило разработать устройство, реализующее данный алгоритм. В работе [7] приведена структура такого устройства.
Кроме того, ПСКВ расширенного поля Галуа обладает способностью к варьированию точностью, быстродействием и информационной надежностью в процессе вычисления. Данная способность базируется на обменных операциях ПСКВ. В настоящее время проявляется повышенный интерес к возможности варьирования корректирующей способностью модулярного кода за счет изменения точности и производительности вычислений в пределах одного цифрового устройства. В первую очередь это объясняется тем, что учет указанного свойства ПСКВ является мощным средством повышения надежности, т. е. при отказе г каналов их можно просто удалить из процессора, не оказывая влияния на точность выполнения задания. Но с другой стороны данные г избыточных каналов предопределяют корректирующие способности вычислительной системы, другими словами — гарантию защиты от недостоверного результата.
Таким образом, изменяя количество информационных к и избыточных г оснований в заданной структуре СП ПСКВ, можно варьировать его основными показателями -точностью, информационной надежностью вычислительной системы.
Если некоторая упорядоченная ПСКВ расширяется путем добавления I оснований, каждое из которых больше основания исходной ПСКВ, то минимальное кодовое расстояние й автоматически увеличивается. Того
тт
же эффекта можно добиться, уменьшая число информационных оснований, т. е. переходя к вычислениям с меньшей точностью. На одном и том же СП можно одни и те же вычисления выполнять с высокой точностью, но с меньшей информационной надежностью или с меньшей точностью, но с более высокими значениями надежности и скорости.
Таким образом, очевидно, что ПСКВ обладает свойством, позволяющим ей гибко использовать резервы точности и надежности при наличии ограничений на увеличение веса, габаритов и стоимости цифрового устройства.
В работе [6] приведен алгоритм позволяющий осуществлять перевод полиномиального модулярного кода в позиционный код на основе китайской теоремы об остатках при постепенной деградации структуры СП ЦОС. Использование данного алгоритма позволяет обеспечить сохранение работоспособного состояния вычислительного устройства за счет снижения в допустимых пределах основных показателей качества функционирования. В работе [6] представлена структура преобразователя из модулярного кода в позиционный код с пересчетом значений ортогональных базисов. Хо -рошие реализационные свойства вышеуказанной особенности ПСКВ, заключающиеся в возможности варьирования точностью, производительностью и корректирующими способностями, представляют собой идеальную основу для разработки высокоэффективных методов реконфигурации вычислительных устройств ЦОС класса вычетов.
Выводы
Внедрение математической модели ПСКВ, позволяющей представлять числа в модулярном коде, является одним из наиболее перспективных путей повышения отказоустойчивости и быстродействия вычислительных средств ЦОС.
В этом случае преимущества модулярной арифметики реализуются наиболее полно как в направлении обеспечения высокой отказоустойчивости, так и в направлении повышения производительности функционирования СП ЦОС.
Список литературы
1. Бережной В. В., Калмыков И. А., Червяков Н. И., Щел-кунова Ю.О., Шилов А. А. Нейросетевая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности // Нейрокомпьютеры: разработка и применение. — 2004. — № 5−6. — С. 94.
2. Бережной В. В., Калмыков И. А., Червяков Н. И., Щел-кунова Ю.О., Шилов А. А. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов // Нейрокомпьютеры: разработка и применение. — 2004. — № 12. -С. 51−57.
3. Емарлукова Я. В., Калмыков И. А., Зиновьев А. В. Высокоскоростные систолические отказоустойчивые процессоры цифровой обработки сигналов для инфотелекоммуника-ционных систем // Инфокоммуникационные технологии. Самара. — 2009. — № 2. — С. 31−37.
4. Калмыков И. А., Щелкунова Ю. О., Гахов Р. П., Шилов А. А. Математическая модель коррекции ошибок в полиномиальной системе классов вычетов на основе определения корней интервального полинома // Физика волновых процессов и радиотехнических систем. — 2002. — Т.6. — № 5. — С. 30.
5. Калмыков И. А. Устройство для коррекции ошибок в полиномиальной системе классов вычетов с использованием псевдоортогональных полиномов // Патент России № 2 294 529. 05. 05. 2005.
6. Калмыков И. А., Сагдеев А. К., Петлеванный С. В., Лисицын А. В. Устройство для преобразования из полиномиальной системы классов вычетов в позиционный код с пересчетом ортогональных базисов // Патент России № 2 298 873. 24. 11. 2005.
7. Фалько А. А., Калмыков И. А., Барильская А. В., Ких-тенко О. А., Дагаева О. И. Устройство спектрального обнаружения и коррекции в кодах полиномиальной системы классов вычетов // Патент России № 2 390 051. от 09. 07. 2008.
8. Хайватов А. Б., Калмыков И. А. Математическая модель отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов // Инфоком-муникационные технологии. — 2007. — Т.5. — № 3. — С. 39−42.
9. Червяков Н. И., Калмыков И. А., Щелкунова Ю. О., Бережной В. В. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа // Нейрокомпьютеры: разработка и применение. — 2003. — № 8−9. — С. 10−17.
10. Чипига А. Ф., Калмыков И. А. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности // Наука. Инновации. Технологии. -2004. — Т. 38. — С. 46.

ПоказатьСвернуть
Заполнить форму текущей работой