Содержание к диссертации
Введение
Глава 1. Аналитический обзор вопросов обеспечения отказоустойчивости специализированных вычислительных структур ЦОС 24
1.1. Исследование общих принципов проектирования высокоскоростных и высокоточных вычислительных структур ЦОС 24
1.2. Анализ требований, предъявляемых к надежности и живучести вычислительных структур 38
1.3. Проблемы реализации ЦОС с использованием специализированных нейронных вычислительных структур 47
1.4. Исследование целесообразности реализации параллельных нейронных вычислений в базисе непозиционной системы счисления в вычетах 57
1.5. Постановка проблемы исследований 72
1.6. Выводы к первой главе 78
Глава 2. Развитие теоретических концепций обеспечения отказоустойчивости непозиционных процессоров ЦОС 80
2.1. Исследование особенностей распределения ошибок в модулярных процессорных элементах 80
2.2. Методика введения избыточности системы вычетов для обеспечения функций контроля и диагностики специализированного процессора 86
2.2.1. Минимизация избыточности СВ 92
2.3. Разработка метода контроля и диагностики неисправностей непозиционного процессора 95
2.4. Обоснование принципов применения самопроверяемых блоков встроенного контроля в непозиционных нейропроцессорах ЦОС 97
2.5. Выводы к второй главе 112
Глава 3. Теоретические принципы и аппаратурная реализация модульных процедур в системе вычетов ... 114
3.1. Постановка задачи 114
3.2 Методика синтеза отказоустойчивых устройств, выполняющих арифметические операции 116
Алгоритмы функционирования и структуры модульных умножителей 116
Алгоритмы функционирования и структуры модульных умножителей 121
3.3. Выбор рациональных наборов оснований корректирующей системы вычетов 128
3.4. Выводы к третьей главе 136
Глава 4. Теоретические принципы и аппаратурная реализация немодульных процедур в системе вычетов 138
4.1. Постановка задачи 138
4.2. Алгоритмы определения знака числа в системе вычетов 139
4.3. Развитие методов теории чисел для повышения эффективности преобразований позиционных кодов в код системы вычетов и обратно 152
4.3.2. Методы и алгоритмы преобразования чисел из системы вычетов в позиционную систему счисления 161
4.4. Масштабирование чисел в системе вычетов 175
4.5. Методика определения позиционных характеристик системы вычетов... 183
4.5.1. Методика определения ранга числа 183
4.6. Выводы к четвертой главе 189
Глава 5. Синтез отказоустойчивых моделей нейронных сетей ЦОС 190
5.1. Методика разработки модели непозиционной НС 190
5.2. Оптимизация структуры непозиционной НС 198
5.3. Моделирование процессов определения позиционных характеристик СВ в структуре нейросети 205
5.4. Аппаратная реализация СВ в нейросетевом базисе современных интегральных схем 212
5.5. Моделирование процессов ЦОС на основе отказоустойчивой структуры НС
227
5.4.1. Методика определения объема контролируемого оборудования специализированного нейропроцессора ЦОС 244
5.6. Выводы 252
Глава 6. Оценка эффективности синтезируемой нейронной сети ЦОС 254
6.1. Определение качества разработанных средств контроля и 254
6.1.1. Оценка качества устройства контроля и исправления ошибок в непозиционном процессоре 254
6.1.2. Оценка качества самопроверяемых блоков встроенного контроля 258
6.1.3. Определение границ применения средств контроля и диагностики в спецпроцессорах 261
6.2. Расчёт живучести спецпроцессоров с учётом средств контроля и диагностики 264
6.3. Сравнительная оценка живучести процессора ДПФ 278
6.4. Сравнительная оценка надежности нейрокомпьютера, функционирующего в системе вычетов 285
6.5. Выводы к шестой главе 294
Заключение 296
Библиографический список 300
Приложения
- Анализ требований, предъявляемых к надежности и живучести вычислительных структур
- Методика введения избыточности системы вычетов для обеспечения функций контроля и диагностики специализированного процессора
- Методика синтеза отказоустойчивых устройств, выполняющих арифметические операции
- Развитие методов теории чисел для повышения эффективности преобразований позиционных кодов в код системы вычетов и обратно
Введение к работе
Актуальность темы. Значительное увеличение количества, многообразия и сложности информации является отличительной чертой современного общества. Существующая тенденция передачи функций управления электронно-вычислительным машинам требует ответственного подхода их создателей к вопросам обеспечения надежности управляющих машин. Особую значимость указанные вопросы приобретают в процессах управления сложными и опасными для жизни человека системами. Примерами подобных технических систем могут служить гидротехнические сооружения, системы вооружения, атомные электростанции, системы нефтегазовых комплексов и т.д.
Прямые экономические потери от снижения эффективности подобных систем (вплоть до полного отказа в результате их ненадежного функционирования) очевидны. Поэтому возникает необходимость в дополнительных затратах на повышение надежности в процессе эксплуатации, которые могут составлять десятки миллиардов рублей. Однако эти потери не сопоставимы с теми потерями, к которым приводят отказы подобных систем, с их экологическими и социальными последствиями (трагедия Бхопала, авария в Базеле, связанная с отравлением Рейна, наконец, Чернобыль и Фукусима).
С практической точки зрения, уровень надежности управляющих вычислительных структур сегодня совершенно недостаточен для ответственных применений без принятия специальных мер, которые предусматривают предупреждение отказов и обеспечение отказоустойчивости.
Естественно, что создать абсолютно надежные компоненты автоматизированных систем управления сложными системами принципиально невозможно. Однако обеспечить максимально возможную отказоустойчивость вычислительных структур явно необходимо.
Развитие отечественной и зарубежной вычислительной техники всегда базировалось на совершенствовании методов и способов повышения производительности, расширения функциональных возможностей на трех основных уровнях разработки вычислительных структур: архитектурном, алгоритмическом и арифметическом. Сегодня данные уровни находятся в тесной взаимосвязи друг с другом, выделяя общую, наиболее тенденциозную черту - стремление к максимальному распараллеливанию операций. Это нашло свое отражение в исследованиях по вопросам поиска и применения новых, нетрадиционных способов кодирования информации, которые способны обеспечить не только высокоскоростные вычисления, но и добиться высокой отказоустойчивости структур, управляющих сложными системами.
Наиболее привлекательными в этом отношении являются системы на основе нейронных сетей с использованием кодирования посредством модулярного представления информации. Указанный аспект становится особенно актуальным в период появления новой организации сверхскоростных вычислений - нейронных сетей.
Особая ценность нейронных сетей, применительно к вопросам обеспечения высокой отказоустойчиости, заключается в том, что они являются самоорганизующимися. Значит, система способна к обучению, и, следовательно, к самостоятельному обнаружению и исправлению возникающих внутри ее ошибок.
Вместе с тем создание данной теории породило множество вопросов, связанных с ее реализацией. Как оказалось, модели современных искусственных нейронных сетей в большинстве своем являются чисто математической интерпретацией построения биологических нейронных сетей, что приводит к потере значительной части способностей своего биологического прототипа. Кроме того, очевидна невозможность использования традиционных алгоритмов в нейросетевом базисе в виду его параллельной архитектуры. Для моделирования нейронных сетей необходимы специальные средства:
программы-эмуляторы (нейропакеты) или аппаратные ускорители-нейрокомпьютеры.
Следует также отметить, что скоростные возможности нейронных сетей (НС), функционирующих в обычной позиционной системе представления информации, все же имеют свои границы. Кроме того, вопросы обеспечения требуемого уровня отказоустойчивости вычислительных структур ЦОС с помощью обычной системы счисления весьма проблематичны.
В этой связи наиболее уместным является применение модулярных систем счисления, и в частности, системы вычетов.
Опыт проектирования первых вычислительных устройств на базе модулярного кодирования информации показал, что в плане повышения скорости и достоверности обработки числовой информации системы вычетов обладают более широкими возможностями, чем обычные позиционные системы счисления (ПСС). Как известно, отказоустойчивость процессоров обеспечивается за счет введения разнообразных форм избыточности: аппаратной, программной и временной. С точки зрения обеспечения аппаратной избыточности можно использовать специальное кодирование, обладающее не только свойствами параллелизма, но и естественными корректирующими способностями. Исследования показали, что в теории чисел существует модулярная система счисления в вычетах (СВ), основанная на китайской теореме об остатках Сун-Цзы. Данная непозиционная модульная система позволяет не только распараллеливать выполнение машинных операций, но и обладает способностью информационного резервирования. Уникальность системы вычетов состоит в том, что аппаратные средства обработки информации в данной системе относятся к легко контролируемым и диагностируемым. Это обусловлено специфическими особенностями представления и обработки кодовых структур в системе вычетов и характером проявления в них отказов и сбоев. Теоретические основы построения числовой системы в вычетах являются развитием широко известного в теории чисел
раздела сравнений. Этому направлению посвятили свои работы чешские исследователи А. Свобода и М. Валах, а также российские ученые В.М. Амербаев, Ю.Г. Дадаев, А.А. Коляда, В.А. Краснобаев, Н.И.Червяков и др.
С внедрением в практику проектирования нейровычислителей высоких интегральных технологий появилась возможность учитывать наиболее существенные достоинства системы вычетов: прежде всего табличную структуру алгоритмов модулярной арифметики и относительную простоту их параллелизации при выполнении операций над малоразрядными остатками. Важнейшей отличительной особенностью разработанных подходов к построению более совершенных по сравнению с существующими вариантами машинной арифметики модульных структур является использование избыточного кодирования элементов рабочих диапазонов, что, безусловно, обязано возросшим техническим возможностям нейросетей. При этом большое внимание уделяется проблеме совмещения вычислительных особенностей модулярного кодирования с архитектурными особенностями строения НС. Кроме того, необходимо выработать единый подход к обеспечению необходимого уровня отказоустойчивости НС при выполнении высокоскоростной цифровой обработки сигналов на этапах реализации как модульных, так и немодульных процедур.
Поэтому в рамках исследований по данной проблеме ключевая роль отводится развитию теории алгоритмического конструирования, формированию принципов построения, разработке методов проектирования и средств реализации отказоустойчивых вычислительных структур на основе нейронных сетей в базисе алгоритмов модулярной арифметики, функционирующих в автоматизированных системах управления нефтегазовых комплексов и решающих задачи цифровой обработки сигналов.
Существующие публикации по модулярным способам кодирования информации отражают, главным образом, начальный период их развития, замыкаясь в рамках внутренних исследований. Что же касается текущего
6
периода, то систематическое изложение его содержания, а тем более разработка
теоретического аппарата, обеспечивающего отказоустойчивость
нейропроцессоров ЦОС в нефтегазовой отрасли, в литературе фактически отсутствуют. Настоящие исследования в значительной мере восполняют данный пробел.
Небезызвестен тот факт, что многие производители современных процессоров ЦОС встают перед реальностью, когда исчерпываются возможности дальнейшего улучшения характеристик отказоустойчивости цифровых компьютеров и с точки зрения технологий и с точки зрения программ. Попытки создания некоторых алгоритмических конструкций (активная и пассивная реконфигурация, мажоритарное резервирование при выполнении быстрого преобразования Фурье, быстрых алгоритмов свертки и Z -преобразования в различных базисах) позволили в той или иной мере решить поставленные задачи. Однако, отсутствие в них общего подхода, единых критериев, а также использование различных ограничений, не позволяет выработать четкие рекомендации по эффективному синтезу и использованию конкретного метода для реализации высокопроизводительного и отказоустойчивого управления цифровой обработкой сигналов в системах нефтегазового комплекса. Именно данные аспекты в первую очередь определяют актуальность темы и научную проблему диссертационных исследований: создание теоретического аппарата синтеза вычислительных структур цифровой обработки сигналов на основе нейронных сетей, функционирующих в базисе алгоритмов модулярной арифметики и отвечающих современным требованиям отказоустойчивости, предъявляемым к автоматизированным системам управления нефтегазовыми комплексами.
Цель и задачи исследований
Целью работы является развитие теории алгоритмического конструирования, формирование принципов построения, разработка методов проектирования и средств реализации отказоустойчивых вычислительных
структур на основе нейронных сетей (ОВНС) в базисе алгоритмов модулярной арифметики, функционирующих в системах цифровой обработки сигналов.
Для достижения этой цели в работе поставлены и решаются следующие основные задачи:
Анализ существующих подходов к обеспечению высокой отказоустойчивости вычислительных структур ЦОС и обоснование целесообразности декомпозиции параллельных нейронных вычислений в базис непозиционной системы вычетов.
Разработка научно-методического аппарата исследования процессов обработки информации в ОВНС.
Развитие теоретических концепций параллельной обработки информации в ОВНС.
Разработка теоретических принципов и аппаратурной реализации немодульных процедур в системе избыточного кодирования информации.
Разработка метода синтеза отказоустойчивых моделей нейронных сетей ЦОС в базисе алгоритмов модулярной арифметики и исследование эффективности предложенных структур в новом поколении интеллектуальных скважин нефтегазовых комплексов на месторождениях Российской Федерации.
Методы исследования базируются на использовании методологии системного анализа, методов математического моделирования, математического аппарата теории чисел, теории кодирования, теории вероятности.
Объект исследования: Отказоустойчивые вычислительные структуры цифровой обработки сигналов на основе нейронных сетей, функционирующие в базисе алгоритмов модулярной арифметики.
На защиту выносятся:
Методика оценки живучести спецпроцессора с учётом влияния средств контроля и диагностики;
Методика определения объёма контролируемого оборудования
спецпроцессоров;
3. Метод контроля и диагностики непозиционного нейропроцессора;
4. Алгоритм проектирования схем встроенного контроля унитарного
кода.
Научная новизна. В работе получены научно обоснованные технические решения, внедрение которых вносит значительный вклад в развитие теории и принципов построения отказоустойчивых непозиционных вычислительных структур на основе нейросетей. Среди указанных решений можно выделить следующие:
Обоснование единого методологического подхода к разработке и исследованию отказоустойчивых вычислительных нейропроцессорных структур в базисе системы вычетов, предназначенных для использования в инженерных сетях нефтегазовых комплексов.
Развитие теоретических концепций обеспечения отказоустойчивости высокопроизводительных непозиционных процессоров ЦОС в части, касающейся: исследований особенностей распределения ошибок в модулярных процессорных элементах; разработки новой методики введения избыточности в системе вычетов для обеспечения функций контроля и диагностики специализированного процессора; разработке методики минимизации избыточности СВ; разработке метода контроля и диагностики неисправностей непозиционного процессора; разработки принципов применения самопроверяемых блоков встроенного контроля в непозиционных нейропроцессорах ЦОС.
Разработка теоретических основ и принципов построения кодов класса вычетов с высокими корректирующими способностями, применение которых позволяет обнаруживать и исправлять ошибки в процессе функционирования нейропроцессорных структур.
Разработка методов и алгоритмов выполнения модульных и труднореализуемых (немодульных) операций в системе вычетов,
характеризующиеся меньшими временными и аппаратурными затратами по сравнению с ранее известными реализациями и являющиеся базисными элементами непозиционных нейросетевых структур.
5. Разработка метода определения границ ошибочных интервалов в зависимости от оснований системы вычетов, учитывающего неравномерность и симметричность распределения ошибок в полном диапазоне модулярной системы вычетов;
Развитие метода контроля и диагностики ошибок в непозиционном процессоре на основе ошибочных интервалов, не требующего больших объёмов вычислений и сокращающего время обнаружения и локализации неисправностей до времени цикла спецпроцессора;
Разработка методологии синтеза отдельных элементов и общей структуры устойчивого к отказам непозиционного нейропроцессора для решения задач управления нефтегазовыми комплексами, с последующим внедрением в производство.
8. Новизна выполненной проверки отказоустойчивости промышленной
системы управления, построенной на основе предложенных нейросетевых
модулярных моделей и методов состоит в разработке высоконадежной
вычислительной структуры в составе системы управления автономными
скважинными измерительными модулями ОАО НЛП "ВНИИГИС".
Практическое значение данной работы заключается в разработке технологии создания в составе АСУТП отказоустойчивых интегрированных нейронных структур, обеспечивающих цифровую обработку сигналов в системе класса вычетов и решение задач контроля и диагностики инженерных сетей нефтегазодобычи.
Теоретические результаты работы, полученные в 1993-1998 годах, применялись при разработке специализированных процессоров цифровой обработки широкополосных сигналов в Воронежском НИИ связи (НПО «Заря») и НПО «Селена» (г. Краснодар), ОАО НЛП "ВНИИГИС".
Внедрение результатов работы. Выявленные принципы структурно-функциональной организации нейронных сетей использованы при разработке других сложных модулярных технических систем специального назначения, а также внедрены в учебный процесс по дисциплине Интеллектуальные информационные системы в Ставропольском институте управления; по дисциплине информатика в Ставропольском военном институте связи Ракетных войск; по дисциплине информатика и в учебно-инновационной лаборатории "Автоматизация и управление технологическим процессами в нефтегазодобыче" филиала ФГБОУ ВПО УГНТУ в г. Октябрьском.
Апробация работы
Основные теоретические и экспериментальные результаты диссертации докладывались и обсуждались на ведомственных, республиканских (краевых), всероссийских и международных конференциях и семинарах, в том числе на 11-ом межгосударственном научно-техническом семинаре «Надежность, отказоустойчивость и производительность информационных систем». (г.Туапсе, - 1994 г.); VIII-ой НТК Ставропольского высшего военного инженерного училища связи (г. Ставрополь, 19-21 октября 1994г); 13-ой научно-технической конференции Серпуховского высшего военного инженерного училища ракетных войск (г. Серпухов, 1995 г.); ГХ-ой НТК Ставропольского высшего военного инженерного училища связи «Состояние и перспективы развития космической связи вида войск» (г. Ставрополь, 16-17 марта 1995г.); НТК академии им. Можайского «Роль и место военно-космических сил в современных операциях Вооруженных сил РФ» (г. Москва, 21-23 марта 1995 г.); научной конференции Орловского военного института правительственной связи «Актуальные вопросы развития защищенных телекоммуникационных сетей связи» (г. Орел, 07-09 февраля 1995г.); НТК Воронежского НИИ связи «Направления развития систем и средств радиосвязи», (г. Воронеж, 1996 г.); Х-ой НТК Ставропольского высшего военного инженерного училища связи «Проблемы построения и развития
11 теории и практики пакетных радиосетей передачи информации ЕАСС» (г. Ставрополь, 24-25 октября 1996г.); XI-ой НТК Серпуховского ВВКИУ «Проблемы обеспечения высокой боеготовности мобильных ракетных комплексов и их систем» (г. Серпухов 28-29 ноября 1996г.); научно-технической конференции Воронежского научно-исследовательского института связи (ВНИИС, 1998 г.); П-ой международной НТК Московской государственной академии приборостроения и информатики (г. Сочи, сентябрь 1999 г.); XIV-ой НТК Ставропольского филиала Ростовского военного института ракетных войск стратегического назначения (г. Ставрополь, 2000 г.); Ш-ей международной НПК «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (г.Сочи, 02-06 октября 2000г.); XV-ой НТК Ставропольского филиала Ростовского военного института ракетных войск «Проблемы совершенствования автоматизированных систем боевого управления и связи ракетных войск стратегического назначения» (Ставрополь 22-23 ноября 2001 г); IV-ой международной НПК «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (г.Сочи, октябрь 2001г.); VII-ой международной НПК «Ашировские чтения», г. Туапсе, 6-9 октября 2010 г.
Публикации
Всего по теме диссертации в период с 1993 по 2011 годы автором опубликовано более ПО работ, из них 10 статей в рецензируемых журналах из списка ВАК, выполнены две НИР, внедрены результаты четырех хоздоговорных работ, получено пять положительных решений по заявкам на изобретения, опубликованы одно учебное пособие, две монографии (одна из них в соавторстве).
Структура и объем работы
Анализ требований, предъявляемых к надежности и живучести вычислительных структур
В связи с наметившейся устойчивой тенденцией постоянного усложнения современной вычислительной техники наиболее важными становятся задачи, связанные с обеспечением необходимого уровня их надежного функционирования. Известное высказывание о том, что чем проще устройство, тем оно надежнее, к сожалению, теряет свою актуальность. Непрерывный рост объема информации при цифровой обработке сигналов диктует необходимость расширения функций и возможностей техники, что приводит к усложнению вычислительных структур. Поэтому требования к таким показателям как надежность и живучесть постоянно растут. Особая значимость этих показателей проявляется в сложных вычислительных структурах цифровой обработки сигналов.
Под надежностью вычислительной системы понимают ее свойство сохранять во времени в установленных пределах значения всех параметров, характеризующих способность выполнять требуемые функции в заданных режимах (ГОСТ 27.002-89) [7-8]. Она отражает влияние на работоспособность системы главным образом внутрисистемных факторов - случайных отказов техники, вызываемых физико-химическими процессами старения аппаратуры, дефектами технологии ее производства или ошибками обслуживающего персонала.
Под живучестью вычислительной системы подразумевают устойчивость системы против действия причин, лежащих вне системы, приводящих к разрушениям или значительным повреждениям некоторой части ее элементов, а также устойчивость к каскадному (системному) распространению отказов, приводящего к нарушению вычислительного процесса [12-13,110].
Определяется живучесть следующим образом: где Q(y,/)- математическое ожидание производительности вычислительной структуры в момент t О, при условии, что в момент начала функционирования в структуре было і работоспособных элементарных вычислителей j є [О п], nw -суммарная производительность всех элементарных вычислителей, п - число элементарных вычислителей в структуре. Факторы живучести вычислительной структуры: выбор базовой архитектуры вычислительной структуры, допускающей и облегчающей применение средств повышения живучести; использование и разумное сочетание различных видов избыточности (структурной, временной, информационной, энергетической); автономность и модульность устройств, блоков, подсистем вычислительной структуры; наличие и обеспечение работы процедур контроля, диагностики и восстановления; введение специальных механизмов и подсистем обеспечения живучести вычислительной структуры (реконфигурации, перераспределения ресурсов, постепенной функциональной деградации).
Эти два понятия объединяет принцип отказоустойчивости, который учитывает все разнообразие факторов, включая эксплуатационно-технические отказы, повреждения элементов стихийными факторами или преднамеренным воздействием. Показатель устойчивости является функцией показателей надежности, живучести и помехоустойчивости.
Различия в этих понятиях обусловлены существенными отличиями в их проявлении, характере и масштабности нарушений, их продолжительности, путях и способах устранения и методах повышения устойчивости системы. Соответственно, существенно различаются и исходные данные, методы расчета, точность и суть показателей надежности и живучести [12].
Надежность тесно связана с понятиями «отказ» и «работоспособность». Работоспособность - это состояние вычислительной структуры, при котором она способна выполнять заданные функции с параметрами, требованиями, установленными технической документацией.
Отказ - случайное событие, заключающееся в нарушении работоспособности вычислительной структуры. Известно, что отказы делятся на: внезапные, постепенные и приработочные. Кроме того, существуют явные и неявные, устойчивые и самоустраняющиеся отказы.
Одним из естественных показателей количественного измерения живучести является показатель эффективности Е, сохранившийся у системы после фиксированной совокупности воздействий.
Исходя из приведенных определений, можно вывести основные показатели надежности вычислительных структур ЦОС. При этом вычислительные структуры делятся на две основные группы: неремонтируемые и ремонтируемые (восстанавливаемые).
На практике повышение надежности и живучести вычислительных структур связано с введением резервирования.
Резервирование - это метод повышения надежности вычислительных структур, основанный на введении дополнительных элементов и функциональных возможностей сверх минимально необходимых для нормального выполнения объектом заданных функций [13]. Основными видами резервирования являются: структурное резервирование (метод повышения надежности, предусматривающий использование избыточных элементов, входящих в физическую структуру объекта); временное (использование избыточного времени, выделенного для выполнения задач); функциональное и нагрузочное.
Методика введения избыточности системы вычетов для обеспечения функций контроля и диагностики специализированного процессора
Весь процесс от возникновения до устранения ошибки в НС можно представить как выполнение следующих основных функций средств контроля и диагностики: обнаружение, локализация и исправление. Из [169] известно, что для локализации и исправления ошибок требуется гораздо больше избыточности, чем для простого обнаружения тех же ошибок. С увеличением избыточности повышаются корректирующие способности СВ [162], однако одновременно с этим растут аппаратурные затраты как на реализацию самого непозиционного неиропроцессора, так и на средства контроля и диагностики (обучения). Следовательно определение избыточности кода СВ должно производиться с учетом двух факторов: 1. Обеспечения высоких корректирующих способностей. 2. Минимизации аппаратурных затрат.
Появился смысл в проведении анализа влияния избыточности кода СВ на реализацию основных функций контроля и диагностики нейронной сети: обнаружение, локализацию и исправление ошибок.
Обнаружение ошибок. Пусть задана система оснований т1,т2,...,тп,тп+] и число А = (а1,а2,...,а„,а„ ). Из [9] известно, что если 0 А Мр, то число правильное, если А М - неправильное. При исследовании распределения ошибочных интервалов в полном диапазоне СВ установлено, что ошибка в числе А Мр может быть обнаружена лишь при условии, что все избыточные интервалы располагаются внутри избыточного диапазона М-Мр и не имеют пересечений с рабочим диапазоном Мр, т.е. {К/} g {0,Мр}
Таким образом, избыточность, необходимая для обнаружения двукратной ошибки, более чем в два раза превышает избыточность, используемую для обнаружения однократной ошибки. Локализация и исправление ошибок.
Процедуры локализации и исправления объединены вместе в силу того, что исправление представляет собой чисто техническую операцию, выполнение которой осуществляется при известном неисправном модуле и глубине ошибки. Определение же неисправного модуля и глубины ошибки производится процедурой локализации.
Анализ распределения ошибочных интервалов (рис.2.1), проведенный с точки зрения локализации и исправления ошибок в СВ, позволяет сделать следующие утверждения [178].
Действительно, при превышении суммы чисел, расположенных в ошибочных интервалах К\, даже в случае их равномерного распределения (что маловероятно), наблюдается пересечение ошибочных интервалов К? между собой (рис.2.1).
В зонах пересечения ошибочных интервалов невозможно обеспечить однозначность локализации ошибочного основания т, или величины ошибки Да, вследствие наложения ошибок по различным основаниям.
Исходя из выражений (2.20-2.21) и условия (2.19) можно предположить, что для локализации двукратных ошибок избыточность потребуется как минимум в два раза большая, чем для однократных ошибок. Это в свою очередь потребует более чем двукратного увеличения оборудования контроля и диагностики неисправностей нейронной сети.
Прежде чем точно определить величину избыточности, необходимую для локализации ошибок, следует рассмотреть вероятностные характеристики возникновения ошибок различной кратности.
Для этого воспользуемся рядом допущений. 1. Возникновение арифметических ошибок происходит в результате отказов или сбоев в работе арифметических устройств непозиционного нейропросессора по модулю. 2. Появление ошибок по каждому из модулей - события случайные, независимые. 3. Вероятности ошибок по всем модулям одинаковы и равны Рош = \-Рбр, где Р6 - вероятность безотказной работы одного арифметического устройства нейронной сети по модулю. Так как в произвольный момент времени может выйти из строя любое из оснований, то вероятность однократной ошибки определится РХош = п{\-Р6р), где п- число модулей в коде СВ.
Вероятность появления двукратной ошибки определяется вероятностью одновременного поступления отказов по двум основаниям Р2ош = С2п{\-Рбр)2. Общее выражение для определения вероятности появления ошибки ПО Г основаниям можно записать в виде Рюш = Сгп(1-Рбр)г, а графически представить так, как это показано на рис. 2.2.
Из представленной на рис.2.2 зависимости вероятности появления ошибок по г модулям следует, что вероятность ошибок по двум основаниям и более значительно (как минимум на два порядка) меньше, чем вероятность однократной ошибки. Следовательно, основным классом ошибок, возникающих в модулях нейронных сетей, являются ошибки по одному основанию. Т.е. при анализе минимальной избыточности, необходимой для обнаружения и локализации ошибок в модульных НС, можно ограничиться классом однократных ошибок.
Анализ литературы [178-180] позволяет утверждать, что авторами, как правило, предлагается увеличенная избыточность кодов СВ. Поскольку это влечет за собой неоправданные аппаратурные затраты, есть смысл в исследовании вопросов уменьшения избыточности. В [81] приводится теорема, позволяющая выработать теоретическое обоснование минимизации избыточности. Теорема 2.1. Для упорядоченной системы оснований т1,т2,...,тп,тп+1 величина контрольного модуля тп+1, выбранная из условия wn+1 w„m„_,, позволяет однозначно определить ошибочное основание т, и глубину однократной ошибки Да, в числе А = (а1,а2,...,ап,ап+1). В качестве доказательства этой теоремы можно привести следующее. Перевод числа из системы вычетов в позиционную систему счисления, как правило, осуществляется через ортогональные базисы В1.
Методика синтеза отказоустойчивых устройств, выполняющих арифметические операции
Рассмотрим алгоритм реализации операции модульного умножения (or,Д)modт,. Таблица 3.1 составлена для модуля т1 =7, причем по горизонтали отложены значения операнда а, по вертикали Д а между числами (т, - Г) / 2 и (т1 +1)/2 находится результат умножения этих операндов. Из табл. 3.1 видно, что для ее восстановления достаточно иметь информацию об одной четвертой ее части. Есть возможность восстановления данной таблицы и по одной восьмой ее части, однако проведенные в [74,119,128] исследования свидетельствуют о том, что в этом случае значительно увеличивается время на выполнение арифметических операций в целом. Вследствие этого для реализации операции вида (alfil)modml представляется наиболее целесообразным применение методов специального кодирования, позволяющих уменьшить таблицу модульного умножения в четыре раза.
Для выполнения операции инвертирования по модулю т,, как правило, используется «вычитатель» по модулю т,. Для выполнения данной операции требуется при сумматорном варианте построения 5 + /?-l+]log2«[- тактов, где п-разрядность оснований СВ, а при табличной реализации - 3-4 г.
Следовательно, при реализации вычитателя по модулю время для выполнения операции умножения увеличивается в два раза, по сравнению с обычной табличной реализацией. Если после коммутатора поставить блок переключателей и {т1 -1) элементов ИЛИ, то необходимость во введении вычитателя отпадает. Это в значительной мере снижает временные затраты по сравнению с существующим умножителем, представленным в [120].
Таким образом, инвертирование по модулю результата операции умножения, представленного унитарным кодом "1 из т", не требует дополнительного вычитания по модулю, что влечет за собой значительную экономию времени выполнения операции [123].
Устройство работает следующим образом. Первый и второй сомножители поступают на соответствующие дешифраторы DC1 и DC2. С выходов DC1 и DC2 операнды в унитарном коде поступают на соответствующие элементы ИЛИ первой и второй групп. Сигнал по входу запуска открывает блоки элементов И, и операнды одновременно поступают на входы коммутатора. Коммутатор имеет размер (т, -\)/4х(т1 -1)/4. На его выходе появляется промежуточный результат операции модульного умножения в унитарном коде. С выхода коммутатора результат поступает на входы блоков переключателей Пркл. Сигналы с выходов DC1 и DC2 поступают также на входы элементов ИЛИ, а с них - на сумматор 2 по модулю два. Выходной сигнал с данного сумматора присутствует только в случае, когда /(а) у(Р) Далее этот сигнал поступает на управляющий вход блока переключателей. Переключатели осуществляют инвертирование по модулю результата операции. Полученный при этом сигнал подается на шифратор CD, где и преобразуется в двоичный код. При равенстве индексов у(а) = у(Р) сигнал на выходе сумматора Z2 отсутствует и результат с выхода коммутатора в инвертированном виде поступает на вход CD, а затем с его выхода - на выход устройства.
На примере разработанного умножителя показан выигрыш в быстродействии. Значит, используя основополагающие принципы табличного алгоритма умножения, можно разработать алгоритм отказоустойчивого быстродействующего сумматора. Т.е. сумматор должен обладать не только высоким быстродействием, но и отказоустойчивостью.
В соответствии с этим требованием разработку алгоритма сложения и синтез структуры отказоустойчивого табличного сумматора вычетов проведем исходя из компромисса между скоростью вычислений, аппаратурными затратами и обеспечением отказоустойчивости.
Представим табличную реализацию операции сложения в классе вычетов по модулю тг1 (табл. 3.4). В табл. 3.4 отсутствует строка а, =0 и столбец Д =0, т.к. сложение с нулем не изменяет значение второго операнда. Как видно из таблицы, вторая и четвертая четверти таблицы идентичны друг другу, а первая и третья отличаются друг от друга на единицу. Если первую четверть модифицировать, т.е. уменьшить значение суммы на единицу, то можно получить таблицу следующего вида (табл. 3.5).
Развитие методов теории чисел для повышения эффективности преобразований позиционных кодов в код системы вычетов и обратно
Прямой перевод чисел из позиционной системы счисления (ПСС) в СВ может осуществляться различными методами [151,152,160,163-165,166,170-172]. Так, перевод числа А в систему вычетов можно выполнить путем поочередного деления исходного числа на модули (основания) системы тх,т2,...,тп и определения наименьшего остатка а,, который и представляет число по данному основанию а, = A-[A/ml]modm1, i= 1,2,...,w, (4-14) где цифра /- го разряда а, числа А является наименьшим неотрицательным вычетом от деления А на mt. Использование выражения (4.14) на практике ограничено наличием операции деления А на основания т1 и необходимостью использования арифметического устройства, функционирующего в ПСС.
Есть и другие способы преобразования ПСС-СВ. Анализ теоретических исследований и опыта конструирования устройств в СВ [119,141,161-164] позволяет утверждать, что при формировании остатков от числа широкое распространение получили схемы свертки по модулю.
Однако и им присущи свои недостатки: низкое быстродействие образования вычета при допустимых аппаратурных затратах; при повышении быстродействия значительно растут аппаратурные затраты, и, как следствие, понижается надежность; отсутствие разработок для формирования остатков квадратичной СВ и ряд других. Поэтому разработку и совершенствование способов формирования остатка от числа необходимо направить на реализацию следующих возможностей: 1. Сокращение аппаратурных затрат на процедуры быстрого преобразования ПСС-СВ при обеспечении высокой точности и надежности. 2. Совместимость с нейросетевой организацией вычисления, которая в свою очередь накладывает дополнительные требования: простота, гибкость, наращиваемость исходного модуля, отсутствие скважности выдачи результатов. С учетом этого разработаны различные варианты алгоритмов и конкретных конструкций преобразователей, реализующих указанные выше требования.
Для реализации данного алгоритма необходимо выбрать устройство, обладающее максимально возможным быстродействием. Данное устройство функционирует по принципу: число в ПСС — ПЗУ - число в СВ. Необходимо однозначно определить принадлежность двоичного числа X множеству S с помощью представления -разрядных двоичных чисел в поддиапазонах.
Данное устройство работает следующим образом. Входное двоичное число через информационный вход поступает на входной регистр. По управляющим сигналам, которые поступают на разряды входного регистра, с к 12 старших разрядов считывается информация и пересылается на схемы сравнения. С к 12 младших разрядов информация пересылается на входы ПЗУ.
В схеме сравнения (рис. 4.2) информация с входного регистра поступает на первые входы сумматоров по модулю два, соответственно, где происходит модульное суммирование со значением блока памяти, соответствующего рассматриваемому коду. Если значения обоих чисел совпадут, то на выходе элемента ИЛИ-НЕ появится сигнал единицы.
В ПЗУ записаны значения остатков чисел в соответствии с выражением (4.19). При поступлении в ПЗУ сигнала единицы с одной из схем сравнения происходит выбор соответствующего значения остатка. Результат поступает на выход.
Несмотря на пристальное внимание, уделяемое разработчиками арифметическим устройствам, функционирующим на основе квадратичных вычетов, теория и практика преобразования чисел в КвСВ развиты слабо. Между тем, данное преобразование имеет, в отличие от обычной СВ, свои особенности. В первую очередь это связано с тем, что приходится оперировать с числами вида a + ib, т.е. возникает необходимость в раздельной обработке мнимой и действительной частей числа путем обеспечения двойных информационных каналов. Необходимо предусмотреть определенные межсоединения для обслуживания возможных операций пересчета данных. Это влечет за собой усложнение аппаратной части и увеличение стоимости преобразователя. Поэтому создание эффективного способа преобразования ПСС-КвСС является важным этапом проектирования нейропроцессоров, функционирующих на основе непозиционной арифметики в квадратичных вычетах.
В настоящее время существует несколько подходов к задаче быстрого преобразования ПСС-КвСВ [141,164,166]. В основном, эти подходы предполагают переход от стандартного квадратичного модуля т = Ак +1 к числам Ферма вида 2 +1. Различны лишь структурные решения. Данный переход, несомненно, обладает рядом преимуществ: увеличение быстродействия преобразования, уменьшаются структурная сложность и стоимость. Но при всем этом значительно сокращается количество оснований системы счисления, что не может не сказаться на динамическом диапазоне М, а это уже неприемлемо при вычислении ДПФ больших последовательностей. Сокращение количества оснований при этих подходах происходит ввиду того, что из всего многообразия форм оснований вида 4к + \ выбираются лишь те, значения которых совпадают со значениями чисел Ферма.
Полученный вычет, соответствующий мнимой части, умножается на корень квадратный из единицы, принадлежащий кольцу целых чисел, а также на обратную величину этого мнимого числа. Остаток, соответствующий действительной части, прибавляется к каждому из этих произведений. В результате получаем код в квадратичных остатках. Порядок поступления данных можно менять в зависимости от компромисса между быстродействием и аппаратурными затратами. При этом раздельную обработку комплексных чисел можно организовать двумя способами. Первый из этих способов предполагает получение остатков мнимой и действительной частей комплексного числа из двух наборов таблиц. Наборы существуют и для мнимой, и для действительной частей числа. Второй способ основан на использовании одного набора таблиц для поочередной обработки числа.
