Scientific journal
Advances in current natural sciences
ISSN 1681-7494
"Перечень" ВАК
ИФ РИНЦ = 0,775

DEVELOPMENT OF METHOD OF CONSTRUCTION NONPOSITIONAL WITH PROCESSOR DEGRADABLE STRUCTURE

Schelkunova J.O. 1 Kalmykov M.I. 1 Goncharov P.S. 1 Petrova E.V. 1
1 North-Caucasian federal university
3293 KB
This paper describes a method of constructing special processor failover digital signal processing (DSP ) capable of maintaining a healthy state when a sequence of failures and crashes. Application of this technique allows for the development nonpositional th special processor with degradable structure. Implementation of the computing device based on the system of the polynomial residue class allows , through the use of integer nonpositional mathematical model DSP to provide not only high-speed signal processing, but also perform procedures associated with finding and correcting errors that occur in the process of JV .
methodology special processor
polynomial system of residue classes
modular codes
parallel computing
balances
orthogonal bases
the degradation of the structure

Одним из наиболее важных направлений развития научно-технического прогресса в сфере информатизации в настоящее время является микропроцессорная революция, для которой характерно широкое использование в системах обработки информации вычислительных систем (ВС), персональных компьютеров, микропроцессоров универсального и специального назначения. Основным направлением развития и совершенствования вычислительных устройств является неуклонный рост производительности и точности вычислений.

Существующая в последние годы в вычислительной технике тенденция к распараллеливанию вычислений связана с непрерывным ростом требований к производительности вычислительных средств. В принципе распараллеливание может быть осуществлено на нескольких уровнях:

• на уровне построения физических моделей объектов или процессов, создания математических моделей, позволяющих организовать параллельную обработку информации;

• на уровне метода решения;

• на уровне алгоритмов известных методов;

• на уровне программ;

• на уровне арифметических операций;

• на уровне обменов информации в ВС, ввода и вывода данных.

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

В современных и перспективных алгоритмах, использующих аппарат линейной алгебры, основными вычислительными процедурами являются операции типа перемножения векторов и матриц, обращение матриц, поиска собственных векторов и собственных значений матриц, решение систем линейных алгебраических уравнений. Данные процедуры линейной алгебры обладают повышенной вычислительной сложностью.

Качественным скачком в обеспечении реального масштаба времени и высокой точности вычислений является применение полиномиальной системы классов вычетов (ПСКВ), определяемой в расширенных полях Галуа GF(2v). Внутренний параллелизм, присущий арифметике ПСКВ, независимость обработки данных в вычислительных трактах, распараллеливание на уровне арифметических операций позволяют использовать перспективные принципы организации вычислительных систем [1-4].

Однако процессоры, составляющие значительную часть аппаратной реализации вычислительной техники, относятся к числу наименее надежных устройств, доля отказов и сбоев которых составляет более 50 процентов от общего числа отказов и сбоев аппаратуры. При этом среднее время ликвидации последствий последних, как правило, на 6-8 порядков превышает среднюю продолжительность выполнения задачи.

Таким образом, очевидна следующее противоречие: с одной стороны, постоянный рост требований к скоростным характеристикам вычислительных устройств приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов, и возрастает время простоя, вызванное трудностью отыскания неисправности.

Наиболее перспективным путем разрешения данного противоречия является придание вычислительным системам свойства устойчивости к отказам в процессе функционирования. При этом fail-soft устойчивость к отказам (с амортизацией отказов) характеризует способность ВС обеспечивать обслуживание, несмотря на возникновение отказа, хотя и с понижением качества, то есть, находясь в состоянии постепенной деградации.

В работах [1-4, 8, 9, 10] показано, что полиномиальная система классов вычетов (ПСКВ) может быть использована при реализации цифровой обработки сигналов (ЦОС). Построение спецпроцессоров (СП) ЦОС, функционирующих в ПСКВ, позволяет обеспечивать обработку сигналов в реальном масштабе времени. Однако параллельная обработка информации в независимых вычислительных трактах позволяет не только повысить скорость обработки сигналов, но и может быть положена в основу построения корректирующих кодов ПСКВ [5-10].

Базисом в построении корректирующих кодов ПСКВ является распределение полиномов в полном диапазоне системы. В работе [2] показано, что в полиномиальной системе класса вычетов с основаниями shуl1.wmf в каждом интервале shуl2.wmf, где shуl3.wmf полного диапазона P(z) содержится по одному элементу последовательности .. В таблице приведен пример такого распределения для поля GF(23).

Распределение по диапазонам элементов shуl4.wmf

A2,0 = (0,0,0)

М2,0=0;

A2,Z2= (0,z2,0)

М2,Z2=z+1

A2,1= (0,1,0)

М2,1=z2+1

A2,Z2+1= (0,z2+1,0)

М2,Z2+1=z2+z

A2,Z= (0,z,0)

М2,Z=z2+z+1;

A2,Z2+Z= (0,z2+z,0)

М2,Z2+Z=z2

A2,Z+1=(0,z+1,0)

М2,Z+1=z;

A2,Z2+Z+1=(0,z2+z+1,0)

М2,Z2+Z+1=1

Из таблицы наглядно видно что, каждый элемент shуl5.wmf последовательности лежит в своем диапазоне. При этом только один находится в нулевом интервале. Таким образом, если правильно подобрать количество рабочих и избыточных оснований, то можно обеспечить выполнение процедур поиска и коррекции ошибок.

При построении корректирующих кодов ПСКВ используют n оснований, из которых k являются информационными, а r – проверочными основаниями. Тогда полный диапазон

shуl6.wmf, (1)

разбивается на рабочий диапазон

shуl7.wmf

и контрольный shуl8.wmf.

Многочлен A(z) с коэффициентами из поля GF(pv) будет считаться разрешенным в том и только том случае, если он является элементом нулевого интервала полного диапазона, то есть принадлежит рабочему диапазону. Если А(z) является элементом второго подмножества, то считается, что данная комбинация содержит ошибку. Таким образом, местоположение полинома А(z) относительно двух данных подмножеств позволяет однозначно определить, является ли кодовая комбинация разрешенной, или она содержит ошибочные символы. Характерной чертой избыточных кодов ПСКВ является их арифметичность, а так же равноправность информационной и избыточных частей кодограмм. При этом для выполнения процедур поиска и коррекции ошибок в кодах ПСКВ используются различные позиционные характеристики, алгоритмы вычисления которых приведены в работах [7-9].

Чтобы разработать структуру отказоустойчивого спецпроцессора ЦОС, функционирующего в ПСКВ, необходимо использовать методику, которая включает в себя следующие этапы.

На первом этапе решается задача, связанная с выбором пространственно-временного распределения реализуемого вычислительного процесса we из множества shуl9.wmf структурированных алгоритмов его решения.

shуl10.wmf. (2)

Второй этап методики посвящен вопросам выбора системы информационных и контрольных оснований ПСКВ. Математическая постановка задачи второго этапа имеет вид

shуl11.wmf, (3)

shуl12.wmf, (4)

где Vпскв – схемные затраты необходимые на реализацию спецпроцессора ПСКВ; Qпскв и Qдоп – точность обрабатываемых данных в модулярном коде и предельно допустимая точность; Nпскв и Nдоп – количество отказов, парируемых при обрабатываемых данных в модулярном коде, и предельно допустимое значение.

На третьем этапе проводится выбор алгоритма осуществляющего преобразование из позиционного кода в модулярный. Математическая постановка задачи имеет вид

shуl13.wmf (5)

где shуl14.wmf – j-й алгоритм прямого преобразования ПСС-ПСКВ, реализованный в нейросетевом базисе из S совокупности возможных алгоритмов; Тпсс-пскв – временные затраты на реализацию процедуры преобразований ПСС-ПСКВ.

На четвертом этапе выполняется выбор алгоритма преобразования ПСКВ-ПСС и его реализации базисе нейронной логики. Математическая постановка задачи имеет вид

shуl15.wmf (6)

где shуl16.wmf – l-й алгоритм преобразования ПСКВ-ПСС; Тпскв-псс – временные затраты на реализацию процедуры преобразований ПСКВ-ПСС.

На пятом этапе производится выбор позиционной характеристики для выполнения контроля и коррекции ошибок. Математическая постановка задачи, решаемой на данном этапе, имеет вид

shуl17.wmf, (7)

где shуl18.wmf– алгоритм коррекции ошибок в кодах ПСКВ; Vпсс – схемные затраты на ТМС СП ПСС; shуl19.wmf – суммарные схемные затраты на СП ПСКВ; Nдоп и shуl20.wmf– допустимое и парируемые отказы.

На шестом этапе решается задача определения стратегии реконфигурации СП ПСКВ известной структуры, обеспечивающей сохранение одного из показателей качества функционирования за счет снижения других показателей в заданных пределах при возникновении сбоев и отказов. Математическая постановка задачи имеет вид

shуl21.wmf, (8)

где shуl22.wmf – время и точность реализации ортогональных преобразований сигнала СП ПСКВ при реализации выбранного оа – го алгоритма реконфигурации; shуl23.wmf – совокупность возможных методов реконфигурации.

Проведем разработку структуры непозиционного спецпроцессора ЦОС, способного сохранять работоспособное состояние при возникновении потока отказов и сбоев за счет снижения в допустимых пределах основных показателей качества функционирования. В качестве исходных данных выбраны следующие параметры:

– частота дискретизации – 50 кГц;

– разрядность кодирования (входного слова) – 31 бит;

– минимально допустимая разрядность входного слова – 11 бит.

На первом шаге проводится анализ основных видов математических моделей цифровой обработки сигналов. В ходе анализа были рассмотрены дискретное преобразование Фурье (ДПФ)

shуl24.wmf, (9)

быстрое преобразование Фурье (БПФ) с прореживание по времени

shуl25.wmf, (10)

алгоритм Винограда для вычисления спектра сигнала

shуl26.wmf, (11)

а также теоретико-числовые преобразования (ТЧП)

shуl27.wmf, (12)

где М – число Мерсена над конечным полем Галуа shуl28.wmf; shуl29.wmf.

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

shуl30.wmf (13)

где shуl31.wmf.

Применение выражения (13) позволяет свести вычисление ортогональных преобразований сигналов в расширенном поле Галуа над кольцом Р(z) к n независимым вычислениям, проводимым по модулям pi(z) полиномиальной системы классов вычетов [3, 4, 7].

На втором шаге. Определяются основания и динамический диапазон обрабатываемых данных. В качестве рабочих модулей выступают полиномы

shуl32.wmf, shуl33.wmf,

shуl34.wmf,

shуl35.wmf.

В этом случае рабочий диапазон

shуl36.wmf.

Контрольными модулями являются shуl37.wmf, shуl38.wmf.

При этом аппаратурные затраты необходимые на реализацию (13) составят

shуl39.wmf, (14)

shуl40.wmf, (15)

где shуl41.wmf – количество оснований в ПСКВ.

Для выбора алгоритма прямого преобразования из позиционного кода в полиномиальную систему класса вычетов проведен анализ работ [1, 3, 4, 10], на основании которого выбран алгоритм непосредственного суммирования, который задается равенством

shуl42.wmf, (16)

где shуl43.wmf, shуl44.wmf.

В этом случае затраты для прямого преобразования ПСС в ПСКВ составят

shуl45.wmf. (17)

На четвертом этапе методики производится выбор алгоритма, реализующего обратное преобразование из модулярного кода в позиционный код. Проведенный анализ работ [3-5, 7] позволил выбрать алгоритм, базирующийся на основе китайской теоремы об остатках (КТО).

Согласно этой теореме обратное преобразование определяется

shуl46.wmf, (18)

где shуl47.wmf – ортогональный базис системы; shуl48.wmf, K(z) – ранг, P(z) – полный диапазон.

При этом ортогональный базис должен удовлетворять требованию

shуl49.wmf. (19)

На пятом этапе методики производится выбор позиционной характеристики, с помощью которой можно определить местоположение и глубину ошибки. На основе анализа работ [1, 2, 8-10] был выбран алгоритм параллельной нулевизации. В работе [6] приведена структура устройства, вычисляющего с помощью данного алгоритма позиционную характеристику – нормированный след полинома.

На последнем этапе методики для реализации метода реконфигурации целесообразно воспользоваться алгоритмом пересчета ортогональных базисов, реализованном на основе многослойной нейронной сети. Аппаратурные затраты на данную процедуру составляют

shуl50.wmf (20)

где ρ – разрядность сумматоров по модулю два.

Тогда вероятность безотказной работы нейросетевого СП ПСКВ будет определяться

shуl51.wmf, (21)

где

shуl52.wmf

верояность безотказной работы подсети, реализующей ортогональное преобразование сигналов; shуl53.wmf и shуl54.wmf – вероятность безотказной работы устройства ПСС – ПСКВ и устройства перевода из ПСКВ в ПСС.

На рисунке приведены вероятности безотказной работы для спецпроцессора ДПФ, реализующего метод маскирования отказа «2 из 3», спецпроцессора ТЧП, реализующий метод «2 из 3» и СП ПСКВ с реконфигурируемой структурой.

shelkun1.wmf

Вероятность безотказной работы СП ЦОС: 1 – СП ДПФ реализующий метод «2 из 3»; 2 – СП ТЧП реализующий метод «2 из 3»; 3 – СП ПСКВ с реконфигурируемой структурой

Анализ рисунка показывает, что применение полиномиальной системы классов вычетов для реализации цифровой обработки сигналов позволяет сохранять работоспособное состояние при возникновении потока отказов за счет деградации структуры СП и снижения в допустимых пределах основных показателей качества функционирования. При этом обеспечивается более высокая вероятность безотказной работы по сравнению с методом маскирования отказов «2 из 3».

Заключение. В работе приведена методика построения спецпроцессора ЦОС, реализация которой позволяет за счет применения корректирующих кодов ПСКВ и деградации его структуры обеспечить более высокую степень надежности функционирования по сравнению с классическим методом маскирования отказов «2 из 3». При этом СП сохраняет работоспособное состояние за счет снижения в допустимых пределах основных показателей качества функционирования.