автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы параллельной цифровой обработки информации в трехмерных оптических интегральных схемах

ГРИГОРЬЕВ ВИТАЛИЙ РОБЕРТОВИЧ

МЕТОДЫ ПАРАЛЛЕЛЬНОЙ ЦИФРОВОЙ ОБРАБОТКИ ИНФОРМАЦИИ В ТРЁХМЕРНЫХ ОПТИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМАХ

Специальность - 05.13.17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Москва - 2005

Диссертация выполнена в Государственном учреждении «Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования» (ГУ РосНИИ ИТ и АП).

Научный руководитель:

Официальные оппоненты:

академик РАН, доктор технических наук, профессор Левин В.К.

доктор технических наук, профессор Голованов П.Н.

доктор физико-математических наук, профессор Грушо А.А.

Ведущая организация - ФГУП «НПО Астрофизика»

Защита диссертации состоится "23" сентября 2005 г. в_часов 00 мин. на

заседании диссертационного совета Д 217.031.01 при Госу-

дарственном учреждении «Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования» по адресу: 129090, Москва, ул. Щепкина, 22.

С диссертацией можно ознакомиться в библиотеке ГУ РосНИИ ИТ и АП.

Автореферат разослан '¿О" августа 2005

г.

Ученый секретарь

диссертационного совета Д 217.031.01

кандидат технических наук, доцент М.М.Виньков

Tggqt- Ж93Х> 3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Важный вклад в развитие цифровых оптоэлектронных систем внесли такие отечественные и зарубежные ученые как Басов Н.Г., Морозов В.Н., Лаврищев В.П., Свидзинский К.К., Бурцев B.C., Фёдоров Б.Н., Торчигин В.П., Р.Арратун, К.Хуан, К.М.Вербер, С.А.Коллинз, А.А.Сочук, Т.С.Стренд, С.Исихара и другие. В их работах определены подходы к организации дискретной оптической обработки, исследованы модели цифровых оптических вычислителей с нетрадиционной архитектурой, а также механизмы реализации фотонных логических операций над двухмерными массивами данных. Однако эти подходы, как и аналоговые, существенным образом ориентированы на использование дискретных-* оптических эле-

гОС пАПИОНА >

ментов (призмы, линзы, транспаранты, фо гопр^|Щ§||^щройства и т.д.),

irsssfti

или планарную оптоэлектронику (волноводные переключатели, дифракционные решетки и т.д.) и не в полной мере обеспечивают решение указанной проблемы.

Повышенные требования к производительности вычислительных систем (ВС) могут быть реализованы при переходе от планарной опто-электроники к трёхмерной. В работах коллектива ученых из ИАиЭ СО РАН и ВЦ СО РАН Косцова Э.Г., Егорова В.М., Твердохлеба П.Е., Пис-кунова C.B., Бандман O.JL, Ачасовой С.Н., Марковой В.П. и др. представлено логическое и физическое описание семейства многослойных трёхмерных электрооптических матриц с настраиваемой структурой, с помощью которых можно создавать оптические вычислительные устройства, выполняющие алгоритмы параллельных подстановок для массовой обработки информации.

Спецпроцессор трёхмерной архитектуры, ориентированной на применение принципов электрооптической модуляции логических сигналов в структуре СБИС, в максимальной степени использует скоростные и технологические возможности многослойных трёхмерных оптических интегральных схем (ТМОИС). Такие спецпроцессоры могут использоваться в мощных вычислительных комплексах производительностью порядка 1015 оп/с и выше.

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

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

Для достижения поставленной цели решались следующие задачи:

- анализ состояния проблемы разработки элементной базы двумерных и трёхмерных СБИС, а также тенденций создания электронных и оптических цифровых вычислительных машин (ОЦВМ) петафлопной производительности, ориентированных на решение прикладных задач ЦОС;

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

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

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

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

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

Теоретическая значимость исследования. Разработанная совокупность методов и технических средств, обладающих единством трёхмерных принципов логической обработки, архитектуры и элементной базы ТМОИС, расширяет и углубляет теоретические основы методов и принципов построения алгоритмических, программных и аппаратных средств высокопроизводительных ЭВМ, вычислительных комплексов и систем, ориентированных на решение задач ЦОС, связанных с обработкой больших массивов бинарных и многозначных данных.

Практическая значимость исследования заключается в создании практических методик и рекомендаций при проектировании специализированных оптоэлектронных процессоров для решения практически важных задач ЦОС на основе использования ТМОИС.

Результаты работы в виде математических моделей, алгоритмов, программ и аппаратных решений применялись при создании вычислительных средств специального назначения на новой элементной базе ТМОИС.

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

Основные положения, выдвигаемые на защиту. На защиту выносятся следующие новые научные положения, предложенные и разработанные лично автором:

1. Принципы построения цифровых оптических вычислительных средств, основанные на соответствии класса алгоритмов и архитектур, на совместном учете вычислительных схем, электрических, оптических и топологических характеристик ТМОИС.

2. Методика определения нижних и верхних оценок сложности ТМОИС и сложности реализуемых на них прикладных алгоритмов цифровой обработки сигналов.

3. Модели, структурные и архитектурные решения ТМОИС.

4. Методы и схемотехнические решения по построению аппаратных средств реализации компьютерной алгебры в системах цифровой обработки сигналов на основе использования ТМОИС.

Апробация результатов исследования. Результаты диссертационной работы докладывались и обсуждались в течение 1982-2005 гг. на международных, всесоюзных, всероссийских и ведомственных научно-технических и военно-научных конференциях КГБ СССР, Академии ФСБ России, Академии криптографии РФ, Академии ФАПСИ, МИРЭА, МТУ-СИ, на всесоюзных совещаниях, научных семинарах 2ГУ и ЗГУ ФАПСИ, НИИ "КВАНТ", кафедрах К-71, К-75 и К-76 ИКСИ Академии ФСБ России.

Реализация и внедрение результатов. Основные результаты диссертации реализованы в НИР и ОКР, проводимых:

ФГУП НИИ «КВАНТ» при разработке высокопроизводительных вычислительных комплексов;

ФГУП НИИ «Восход» при разработке методических положений по созданию технических средств, специального программного и информационного обеспечения автоматизированных комплексов обработки информации;

Академией криптографии Российской Федерации при исследовании возможности создания проблемно-ориентированных высокопроизводительных вычислительных систем и специальных средств защиты информации,

а также использованы при организации учебного процесса:

Московским государственным университетом им. М.В. Ломоносова;

Институтом криптографии, связи и информатики Академии ФСБ России;

Московским государственным институтом радиоэлектроники и автоматики (технический университет).

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

Публикации. По теме диссертации опубликовано 36 печатных работ (из них - 3 книги (курсы лекций), 11 статей, 17 тезисов докладов на конференциях), 7 отчётов о научно - исследовательской работе.

Технические решения, предложенные в работе, защищены 5 авторскими свидетельствами.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Работа содержит 231 страниц основного текста, 85 иллюстраций, 6 таблиц. В библиографию включено 332 наименования литературы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Большое число простых и повторяющихся операций, необходимых для выполнения многомерных алгоритмов ЦОС, естественным образом приводит к концепции однокристальной мультипроцессорной системы. Однако в кремниевом исполнении отображение таких алгоритмов производится на одно- и двумерные систолические структуры и, следовательно, требуются вынужденные преобразования объективно существующей трёхмерной области вычислений к абстрактной двумерной, отвечающей присущему на сегодняшний день требованию планарности СБИС.

Показано, что появление трёхмерных СБИС предельно увеличивает размерность возможного физического пространства осуществления вычислений

Очевидно, что любой граф с локальными информационными связями (ЛИС-граф) Г* можно интерпретировать как трёхмерную (dim Pint=3) сеть s0, содержащую v=||Pint|| локально связанных в трёх измерениях процессорных элементов (ПЭ). В этом случае каждой вершине ре Pint сопостав-

ляется отдельный ПЭ, а каждой дуге, связывающей соседние вершины графа - информационный канал связи.

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

Проведенный в первой главе анализ состояния разработок электронных и оптических ЭВМ петафлопной производительности, полученная классификация технологий изготовления трёхмерных БИС и выработанные новые пространственно-временные критерии обработки информации в ТМОИС для решения прикладных задач ЦОС в зависимости от размерности пространства осуществления вычислений определяют основные направления диссертационного исследования. Они состоят в разработке теоретических основ проектирования ТМОИС, создании алгоритмических моделей решения класса прикладных задач ЦОС в ВС с трёхмерной операционной средой, синтезе новых арифметических и логических методов, ориентированных на вычислительные средства общего и проблемно-ориентированного назначения, и разработке схемотехнических решений ТМОИС для их аппаратной поддержки.

Во второй главе оценены нижние и верхние пространственно-временных границы сложности реализации вычислительных алгоритмов на базе двумерных и трёхмерных (объёмных) СБИС.

Показано, что использование оптики для организации каналов передачи информации в ТМОИС позволит в некоторых случаях отказаться от ограничений для манхэттонской (сеточной) модели электронных СБИС и процессора на их основе.

Исследованы вопросы реализации логических сетей в трёхмерном пространстве.

Под (й?,«)-сетью будем понимать направленный граф с п нумерованными вершинами аьа2,...а„ и с1п отмеченными дугами такой, что в каждую вершину входит ровно с! дуг, одна из которых помечена буквой хь другая - буквой хг, и т.д. и, наконец, последняя - буквой х^. Примерами таких сетей являются логические сети и нейронные сети. При реализации сети в 3-мерном пространстве электронных СБИС расстояние между любыми про-

водниками, соответствующими неинцендетным дугам, должно быть не меньше 1.

В случае использования в ТМОИС в качестве проводников оптических соединений этим ограничением можно пренебречь, так как:

1) близлежащие оптические каналы (как горизонтальные, так и вертикальные в трёхмерном сеточном пространстве), в силу нейтральности фотонов, не создают электромагнитных наводок при пересечении, и, как следствие, не имеют ограничений на число пересечений в одной точке (узле) координатной сетки трёхмерных оптических СБИС.

2) по каждому оптическому каналу, соответствующему дуге графа вычислений, возможна передача множества данных, одновременно распространяющихся на разной длине волны X, (1 =1,...,к). Т.е. в ТМОИС возможно одновременно оперировать с данными, передаваемыми и обрабатываемыми посредством большого числа несмешивающихся «разноцветных» световых лучей. Это свойство фотоники может быть использовано в оптическом компьютере для объединения множества параллельно работающих «разноцветных» процессоров, расположенных в вершинах вычислительного графа, оперирующих с данными, «окрашенными» в «свой цвет».

Исходя из выше сказанного, доказана теорема 1 о размещении в трёхмерном пространстве (1,«)-сети, т.е. графа, в каждую вершину которого входит только одна дуга.

Теорема 1. Для (1,я)-сети, объём занимаемый сетью У(И) <0(пзп).

Для трёхмерного случая доказывается теорема 2 о вложимости произвольных графов с п вершинами в трёхмерную область объёмных СБИС, и на основе характеристики степени информативности функции произведена оценка пространственно-временных границ сложности вычислений для объёма У(Я) трёхмерной области электронных трёхмерных ИС (ТМИС).

Теорема 2. Пусть С1(/л) - площадь некоторого сечения, ортогонального диаметру ё(Я) области Я. Тогда <1(К) =П(/лт) и У(Ы) =0(/}/2).

Получены нижние оценки для объёма V электронных ТМИС, необходимого для реализации коммутирующей сети с п узлами и задержкой, равной Т единиц времени. Для этого сформулирована и доказана теорема 3.

Теорема 3. Пусть СБИС, вычисляющая функцию /, реализована в трёхмерной области Я, тогда У2Т3 =£!(//), где ц - степень информативности функции, V- объём, занимаемый схемой.

Показано, что для ряда нерегулярных и регулярных графов более предпочтительной по сравнению с двумерной является трёхмерная реализация, поскольку длина связей графа уменьшается от 0(л/1о§2л) для плоских схем до 0(и1/2) для трёхмерных. Соответственно, граф занимает пло-

щадь 0(п2) - для плоских схем, и объём 0(пш) - для трёхмерных.

На основе сравнения размещения схем на плоскости и в трёхмерном пространстве сделан вывод, что в принципе трёхмерная технология позволит сократить линейные размеры схем с С2(п) до 0(пш), а максимальную длину проводников с О (п/1оя п) до 0(пш).

Исследованы вопросы проектирования трёхмерных СБИС-структур с точки зрения условий вложимости графа прикладной задачи в трёхмерную решетку.

Исследованы особенности разработки массово параллельных вычислительных систем (МРР), имеющих в своей основе архитектуру гиперкуб. Показано, что внедрение новой элементной базы и создание сверхпроизводительных ЭВМ с архитектурой Ы-куб и тор привело к комбинаторным задачам оценки числа неэквивалентных вложений в //-куб некоторых классов графов, например, деревьев.

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

В развитие результатов, полученных Никоновым В.Г., Зайцевой Ж.Н. и Шевелёвым Д.В., исследован вопрос о покрытиях булевых функций и возможности использования аппарата теории булевых функций при решении задачи размещения элементов при проектировании «многомерных» типов архитектур многопроцессорных вычислительных систем.

Исходя из того, что для М-мерной решетки Л'-мерный куб является подграфом, было показано, что верно и обратное: для любой решетки существует куб соответствующей размерности, содержащий данную решетку в качестве подграфа.

Подграф тУ-куба называется булевым графом. Произвольное с точностью до автоморфизма ТУ-куба вложение булевого графа в //-куб определяет класс эквивалентности булевых функций или класс однотипных функций. Граф, порождающий / типов функций, называется ¿-типным, граф, порождающий один тип - монотипным.

С учетом того, что структуры подграфов Л^-куба и М-решетки во многом совпадают, исследованы монотипные графы с точки зрения их вложимости в качестве подграфов в Ы-куб. Возможность распознавания таких графов представляет интерес для исследования булевых графов в целом, так как, по сути, монотипные графы - это "жестко" (однозначно, с точностью до перестановки цветов) вложимые в Ы-куб подграфы.

Показано, что исследованные типы графов естественным образом со-

гласуются с трёхмерным операционным пространством как внутри ТМОИС, так и на верхнем уровне пространственной архитектуры трёхмерного оптического цифрового вычислителя, где в вершинах графа расположены однокристальные мультипроцессорные трёхмерные СБИС.

Произведена оценка нижних границ временной сложности вычислений параллельного алгоритма в ¿/-размерной систолической структуре, в том числе, в трёхмерных систолических матрицах с оптическими информационными каналами.

Введен критерий сложности реализации алгоритмов в систолических матрицах, задаваемый парой ((, р), где t - порядок времени вычислений и р - количество необходимых ПЭ. И t и р зависят от длины входных данных, результатов на выходе и объема необходимых вычислений, связанных с реализацией алгоритма.

Показано, что параллельный алгоритм сложности (t0, ро) может быть сведен к совокупности параллельных алгоритмов со сложностью (t, р) и тогда tp = to ро для р < р0- В частном случае, когда р = 1, временная сложность реализации последовательного алгоритма составляет t = Т.

Теорема 4. Временная сложность параллельного алгоритма ограничена величиной

t>T/p.

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

(1) число необходимых входов -1.

(2) число необходимых выводов - О.

(3) необходимость выполнения, по крайней мере, Т вычислений.

Полагая, что Qd - некоторый коэффициент в ¿/-размерных структурах,

доказаны утверждения, определяющие ограничения на временную сложность вычислений и сложность времени ожидания в систолических структурах ¿/-размерности.

Из доказанных утверждений следует, что нижняя граница временной сложности вычисления параллельного алгоритма в ¿/-размерной систолической структуре определяется как

t = Q(max(1Ш, 01/d, Tl/(dH), Т/р)\

а нижняя граница времени ожидания, под которым понимается время, затрачиваемое на прохождение входных операндов через вычислительную структуру до получения результатов на ее выходе:

I = Q(p,/d).

С учетом природы оптических каналов передачи и обработки данных предложен метод получения оценок аппаратурной и временной сложности

проектирования программируемых логических матриц (ПЛМ) на основе реализации электрооптических ТМОИС.

Показано, что регулярность логической структуры ПЛМ позволяет получить приближенные оценки аппаратурной и временной сложности реализации заданной параллельной микропрограммы до проведения технического проектирования устройств, основанных на модуляции светового потока в объёме ТМОИС. Аппаратурная сложность оценивалась через объём, который занимает электрооптическое устройство, реализующее заданную микропрограмму Ф:

У(у, и, V) =Ак,

где А — площадь слоя; к — число слоев; V, и, V — параметры параллельной микропрограммы. Площадь слоя электрооптического устройства с клеточной организацией, в свою очередь, равна площади единичной клетки А к, умноженной на их число Ы= \М\. Площадь выражается в условных квадратах со стороной а, равной минимальному линейному размеру окна модулятора света.

Площадь клетки складывается из площади ПЛМ, площади триггера и площади, занимаемой проводниками связи с другими клетками

Ак = (АПлм + Ат + Асв) Д где /3 — технологический коэффициент, учитывающий необходимость размещения емкостей, резисторов, электронных повторителей и т.д., /3 = 1,5-2

Для двухслойной схемы клеточного сумматора, предназначенного для сложения т целых п-разрядных чисел, подсчитаны конкретные значения параметров А и V. Параллельная микропрограмма такого сумматора содержит две микрокоманды, а количество соседей по входам и выходам — соответственно и = 5, ¥= 3. Общая площадь устройства А = (я + \ogrn) тАь где (п + \ogrn) — разрядность суммы, равная числу столбцов клеточного поля; т — число слагаемых, равное числу строк клеточного поля. При т = 10, п = 12, а = 10 мкм, /3 = 1,6 и расстоянии между слоями <1= 0,5 мм площадь сумматора А = 16 мм2, объём У= 8 мм3.

Показано, что площадь двухслойной электрооптической БИС равна \0Wti. При а = 10 мкм это составляет 1 мм2 на каждый разряд. Время умножения при тактовой частоте 109 1/с равно 2я10"9.

Третья глава посвящена разработке методов и средств выполнения параллельных вычислений в конечных полях и кольцах на основе использования трёхмерных оптических интегральных схем в качестве аппаратных средств реализации компьютерной алгебры в системах цифровой обработки сигналов. Актуальность этого подхода связана с широким кругом приложений конечных полей Галуа ОР(2т) в задачах ЦОС, в области организации связи и защиты информации.

Предложен подход, ориентированный на создание математических

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

Введено понятие параллельной обработки данных на элементном уровне, под которой понимается выполнение «-арной (групповой) операции (п > 2) суммирования операндов в одном элементарном устройстве обработки. На основе указанной операции эффективно могут быть реализованы алгоритмы Фурье, Уолша, Хаара, вычисление элементарных функций, задачи линейной алгебры и т.д.

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

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

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

Общий вид электрооптического устройства быстрой арифметики в ССОК с трёхмерной архитектурой представлен на рис. 1.

Рис. 1. Трёхмерная архитектура логического операционного электрооптического тонкопленочного устройства в ССОК. !'- плоскость ввода разрядного слова первого слагаемого, 2 - трехмерный «лабиринт» ввода второго слагаемого, 3 - фогоприймная мафица вывода результата

Показано, что применение теоретико-числовых преобразований в алгебре конечных полей при вычислении динамических спектральных характеристик позволяет значительно повысить быстродействие системы обработки, избежать ошибок округления в результатах вычислений, сократить объем аппаратуры.

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

Показано, что с помощью одной микросхемы можно выполнять 4-байтные арифметические операции в системе остаточных классов с тактом порядка 1 ГГц.

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

Предложен подход к реализации трёхмерного систолического вычислителя дискретного преобразования Фурье на основе кронекеровского произведения матриц. В основу положена структура вычислений с ис-почьзованием схемы индексации Гуда-Томаса для простых делителей, выполнение кронекеровского произведения матриц и реализация прямого метода вычисления циклической свертки для небольшого простого числа входных данных.

Выбор длины последовательности позволяет, используя схему индексации Гуда-Томаса для простых делителей, преобразовать входной вектор данных в трёхмерную таблицу. Затем эта таблица преобразуется в новый вектор, формируемый как «стек столбцов». Скорость вычислений при этом достигается благодаря тому, что все эти действия можно проделывать с индексами, а не с данными. Такая же операция проделывается и с выходным вектором.

Пусть, например, п = п\п2 щ, тогда входные индексы задаются вычетами по правилу

/; = i(mod tti), ¡2 = i(mod пи i3 = i(mod пз).

Это правило представляет собой отображение индекса i на расширенную диагональ трёхмерной таблицы, элементы которой занумерованы тройками индексов (i 1,12,13)- Согласно китайской теореме об остатках, существуют такие целые Ni, N2 и N3, что выполняются равенства NIn2ii3(modrtj) = 1, N2nin3(modп^ = 1 и N3 nin2(modП3) = 1, тогда

/= iiNin2Tl3 + i2N2n,n3 +

Выходные индексы определяются несколько иначе к 1 = Nik(mod nt), к2 = N2k(mod п2) и к3 = N3k(mod П3), и

к = kin2 п3 + к2п: п3 + k3tii п2 (mod п).

После описанного преобразования трёхмерные массивы формируются в новые одномерные как «стек столбцов». На рис. 2 и рис. 3 приведены примеры для 15-точечного преобразования.

В результате таких перестановок изменившаяся матрица преобразования Фурье раскладывается в кронекеровское произведение матриц.

Рис. 2. Переиндексация на входе Рис. 3. Переиндексация на выходе

1 15-точечного преобразования Винограда 15-точечного преобразования Винограда

Пусть Ж2 и IVз обозначают соответственно матрицы П]-точечного, 4 «2-точечного и «3-точечного преобразований Фурье. Тогда, если под V и V понимать соответственно входной и выходной векторы, переставленные описанным образом, то можно записать

Алгоритм Рейдера сведения ДПФ к циклической свертке основывается на существовании примитивного элемента л поля ОР(и) в случае простого п. Т.к. и-простое число, то можно воспользоваться структурой поля ОГ(и) для переиндексации компонент входного вектора. Поле СтР(л) не следует путать с полем, в котором вычисляется ДПФ.

Выберем примитивный элемент п простого поля вБ(«). Тогда каждое, не превосходящее п, целое число можно однозначно записать в виде степени элемента л. Преобразование Фурье можно переписать, заменив индексы / и к соответствующими степенями элемента л. Компоненты входного вектора с нулевыми значениями этих индексов удобнее рассматривать отдельно. Тогда

/1—1 п-1

У0 = 2] V, и V = Уо + к =

/=0 1=0

1,..., п-1.

Пусть г(0 обозначает единственное для каждого / от 1 до п-\ целое число, такое, что в поле ОР(л) выполняется равенство И1' = ¡. Функция г(1) является отображением множества {1,2,...,л-1} на самого себя, т.е. она задает перестановку на множестве {1,2,...,и-1}. Тогда Ук можно записать в виде

В

л-1

Уяг(к) = Уо+

г(,) '

Рис. 4. Схема трёхмерного вычислителя ДПФ.

1=0

Так как г(0 задает перестановку, то можно положить / = г(1) иу = п-1 -г(1) и выбрать у в качестве индекса суммирования. Это дает

п-1 /-у п-2 1-1

V' =уо+ V- или V, = у° + I/ ^

П 7=0 7=о

где V'/ = УП' и у\ = — соответственно переставленные компоненты

последовательностей входных и выходных данных. Таким образом, переставив индексы входных и выходных данных, мы записали ДПФ последовательности {у,} в виде свертки {v1} и {

Т.к. П\, «г и «з - простые числа, то в соответствии с алгоритмом Рейдера, переставив строки и столбцы в матрицах преобразований И/ь ]¥г и можно свести их к циклической свертке. На основе описанного алгоритма разработана следующая структурная схема систолического вычислителя ДПФ (рис. 4).

На вход поэлементно поступают перетасованные блоки данных, состоящие из п = щпгщ = 13x11x7 = 1001 компонент. Текущий обрабатываемый элемент входного вектора обозначен Р. После начала обработки элемента, необходимость его хранения отпадает.

На первых п1 тактах в блоке А происходит вычисление ДПФ Щ с накоплением информации в промежуточном буфере. На последующих п2

тактах параллельно происходит вычисление ДПФ IV, в блоке В с новыми входными данными и вычисление ДПФ Щ в блоке В над результатами первых п/ тактов. Заметим, что, так как Пг<П\, то к моменту завершения вычисления в блоке А блок В уже передал результаты работы в блок С и готов к обработке результатов из блока А. Таким образом, в произвольный момент времени вся аппаратура задействована наиболее оптимально. Обработка будет проходить фактически в реальном масштабе времени, а время вычисления Т=2п.

Показано, что для вычисления ДПФ длины п с использованием предлагаемой комбинации систолического алгоритма и структуры трёхмерного оптического вычислителя необходимо в среднем 77*10"1 вычислительных элементов (умножитель + сумматор), тогда как при систолизации ДПФ в обычном виде требуются затраты порядка п вычислительных элементов, т.е. на порядок больше.

Таким образом, показано, что сочетание принципа систолической обработки в третьем измерении, использования системы счисления в ССОК и технологии трёхмерного монтажа в виде ТМОИС дает новый тип вычислителя ЦОС, с помощью которого возможно достижение высоких скоростей обработки информации при малых масса-габаритных параметрах.

Исследована возможность использования трёхиндексного вычислительного пространства ТМОИС для реализации алгоритмов свертки и умножения полиномов.

Предложены структурные и схемотехнические решения по реализации предложенных алгоритмов на трёхмерных систолических электрооптических структурах.

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

Разработаны как сам алгоритм быстрого обращения элемента в поле СтР(2т), так и принципы его реализации на основе ТМОИС, построенной на бит-слайсовой архитектуре.

Рис. 5. Структурная схема конвейерного оптического умножителя

в поле GF(2m).

1 - последовательный по входу - параллельный по выходу умножитель,

2 - мультиплексор, 3 - параллельная оптическая шина,

4 - регистры данных, 5 - матрица излучателей.

Даны оценки временной и емкостной сложности для предложенных алгоритмов, реализованных на оптических трёхмерных вычислителях в сравнении с ЭВМ. Показано, что быстрое обращение требует m-(q+p) временных тактов, где q = Llog raj и р являются числом единиц в двоичном представлении. Этот результат особенно привлекателен для использования в криптосистемах, где данные сегментируются на длинные блоки, т.е., где m является очень большим для достижения необходимых параметров защиты и желательна высокая производительность.

Показано, что общая потребляемая элементарной ячейкой мощность равна = 0,45 мВт, плотность размещения на подложке N= 2,2*103 ячеек/см2, а площадь, занимаемая ячейкой, составит Q - 4,54*104 мкм2. Параметры элементов ТМОИС допускают возможность достижения скорости обмена информацией между двумя плоскостями более 3 Тбит/см2с при теплоотводе до 10 Вт/см2.

В заключении приведены основные результаты работы.

В приложении 1 приведена методологическая структура диссертации. В приложении 2 указаны основные направления диссертационных исследований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты работы сформулированы следующим образом:

1. Проведен анализ состояния проблемы разработки элементной базы двумерных и трёхмерных СБИС, а также тенденций создания электронных и оптических цифровых вычислительных машин петафлопной производительности, ориентированных на решение прикладных задач цифровой обработки сигналов и защиты информации. Проанализированы системные физические, технологические, схемотехнические и алгоритмические ограничения реализаций двумерных и трехмерных СБИС. Предложена классификация трехмерных СБИС и основанных на них архитектурных принципов системной организации вычислений в однокристальных многопроцессорных вычислительных системах. Обоснована необходимость создания новой элементной базы для цифровых сигнальных процессоров на основе ТМОИС. Определены требования к физическим характеристикам элементов ТМОИС.

2. Исследованы характерные особенности организации вычислительных процессов с массовым параллелизмом в ТМОИС при решении прикладных задач цифровой обработки сигналов, которые потребовали введения новых пространственно-временных критериев организации обработки информации в трёхмерных оптических интегрированных вычислительных структурах (архитектурных, алгоритмических, структурных, объемно-временных, энергетических, физических и т.д.). Показано, что ТМОИС по сравнению с электронными СБИС имеют качественно более высокую производительность при решении указанного класса задач.

3. Для реализации трехмерной технологии построения оптических интегральных устройств предложена методика получения верхних и нижних оценок пространственно-временных границ размещения произвольного вычислительного графа на п вершинах в трехмерном пространстве. С этой целью сформулирован и доказан ряд теорем. Доказано, что для ряда нерегулярных и регулярных графов более предпочтительной по сравнению с двумерной является трёхмерная реализация, поскольку длина связей графа уменьшается от 0(и/1о§2«) для плоских схем до 0(п п) для трёхмерных. Соответственно, граф занимает площадь 0(я2) - для плоских схем, и объём 0(л3/2) - для трёхмерных. На основе сравнения размещения схем на плоскости и в трёхмерном пространстве сделан вывод, что в принципе трёхмерная технология позволит сократить линейные размеры схем с О(п) до 0(п1/2), а максимальную длину проводников с <Г2(п/1оц п) до 0(п1/2). Разработаны принципы отображения параллельных алгоритмов на трехмерные матричные оптические структуры, обеспечивающие структурно-параметрическую организацию вычислительного процесса. Произведена оценка нижних границ временной сложности вычислений параллельного

алгоритма в ¿/-размерной систолической структуре, в том числе, в трёхмерных систолических матрицах с оптическими информационными каналами. С учетом природы оптических каналов передачи и обработки данных предложен метод получения оценок аппаратурной и временной сложности проектирования программируемых логических матриц на основе реализации электрооптических ТМОИС.

4. Предложены модели, структурные и архитектурные решения ТМОИС с массовыми параллельными каналами обработки для решения прикладных задач цифровой обработки сигналов и защиты информации, основанные на новом физическом принципе - введении в структуру СБИС оптических каналов связи.

5. Предложена базовая модель трёхмерного оптоэлектронного вычислителя в системе счисления в остаточных классах на основе использования массовых оптических связей между слоями и оптическими (электронными) соединениями в рамках отдельных слоев. Разработано устройство непозиционного процессора для выполнения немодульных операций. Структура непозиционного процессора позволяет уменьшить деградацию при отказе и обеспечить более надежную работу процессора, причем в отличие от традиционных процессоров не потребуется усложнение программы или введения дополнительной аппаратуры, а корректирующие коды в СОК позволяют обнаруживать и исправлять ошибки, возникающие во всех устройствах предложенного вычислителя. Показано, что с помощью одной ТМОИС можно выполнять 4-байтные арифметические операции в СОК с тактом порядка 1 ГГц.

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

7. Предложены новые методы выполнения базовых операций цифровой обработки сигналов: дискретного преобразования Фурье и свертки на основе аппаратной реализации операций модульной арифметики в кольце целых чисел на трехмерных бит-слайсовых архитектурах многоканальных ТМОИС. Разработаны эффективные систолические алгоритмы реализации этих операций, являющихся вычислительным ядром для решения широкого класса задач цифровой обработки сигналов, имеющих теоретическое и практическое применение.

8. Предложена архитектура трёхмерного систолического вычислителя дискретного преобразования Фурье и разработан эффективный систолический алгоритм его реализации. В основу подхода положена структура вычислений с использованием схемы индексации Гуда-Томаса для простых делителей, выполнение кронекеровского произведения матриц и реализация прямого метода вычисления циклической свертки для небольшого простого числа входных данных. Показано, что для вычисления ДПФ длины п с использованием предлагаемой комбинации систолического алгоритма и структуры трёхмерного оптического вычислителя необходимо на порядок меньше вычислительных элементов (умножитель + сумматор), чем при систолизации ДПФ в случае использования обычных двумерных электронных СБИС. При этом обработка данных осуществляется фактически в реальном масштабе времени, а время вычисления составляет Т=2 п.

9. Предложено несколько типов архитектуры вычислителей свертки полиномов, отличающихся по степени параллелизма Ы, 1Ч2 и 1Ч3. Проведено сравнение предложенных вариантов систолических вычислителей свертки по следующим параметрам: временной и емкостной сложности, а также параметру эффективности (ускорения вычислений). Показано, что увеличение размерности обработки в объемных - трехмерных вычислителях со встроенными оптическими связями приводит к существенному росту производительности (на порядок и выше) при меньших аппаратных затратах. Выполнена оценка требований к технической реализации предложенных типов оптических цифровых сигнальных процессоров. Сделан вывод, что современный уровень развития технологий создания элементной базы цифровой оптики позволяет достигнуть на предложенных вычислителях производительности порядка 1015 оп/с.

10. Разработаны методы и схемотехнические решения аппаратных средств реализации компьютерной алгебры в оптоэлектронных систолических процессорах на основе ТМОИС для решения прикладных задач цифровой обработки сигналов, в том числе систолических алгоритмов вычисления обратного элемента в поле ОР(2т). Предложена новая последовательная по входу - параллельная по выходу конвейерная архитектура оптического умножителя в СР(2т). Показано, что процедура выполнения быстрой инверсии на предложенном вычислителе требует тх^+р) временных тактов, при этом вычислительная сложность обращения элемента в СР(2т) составляет 0(т^2т). Этот результат представляет практический интерес для использования в криптосистемах, где данные сегментируются на длинные блоки, т.е., где т является очень большим для достижения необходимых параметров защиты и желательна высокая производительность.

Основные публикации по теме диссертации

1. Авторское свидетельство № 1213477 от 22.10.85. Кл. Н 03 М 7/18. Оптоэлектронный сумматор по модулю Р./ Григорьев В.Р., Цветков В.А.

2. Авторское свидетельство № 1290916 от 15.10.86. Кл. G 06 F 7/56. Оптоэлектронное устройство умножения по модулю Р/Григорьев В.Р., Цветков В.А.

3. Авторское свидетельство № 1317663 от 15.06.87. Кл. Н 03 М 7/18. Электрооптический преобразователь кодов./Григорьев В.Р., Цветков В.А. - Открытия. Изобретения. - Бюл. № 22,15.06.87.

4. Авторское свидетельство № 1363193 от 1.09.87. Кл. G 06 F 7/56. Оптоэлектронный сумматор по модулю Р./ Григорьев В.Р., Тройков A.C., Цветков В.А. - Открытия. Изобретения. - Бюл. № 48, 30.12.87.

5. Григорьев В.Р., Тройков A.C., Цветков В.А. Электрооптический вычислитель в остаточных классах. //Вопросы радиоэлектроники. Сер. ЭВТ, вып. 12,1986, с. 102-109.

6. Григорьев В.Р. Перспективы использования интегральной опто-электроники в высокопроизводительных вычислительных комплексах. /В сб.: Тезисы докладов на научно-теоретической конференции НИИ "Квант", 1983, инв. № 9951.

7. Григорьев В.Р., Колобашкин С.М. Реализация алгоритма сборки вектора на специализированном электрооптическом коммутаторе.// Автометрия, №3, 1989, с. 68-76.

8. Григорьев В.Р. Применение высокопроизводительных систем для решения спецзадач. Параллельные вычислительные системы с распределенным управлением. Курс лекций. Часть II (в 2-х книгах). Книга 1. -М.: Академия безопасности ФСК России, 1996 г., 341 с.

9. Григорьев В.Р. Применение высокопроизводительных систем для решения спецзадач. Параллельные вычислительные системы с распределенным управлением. Курс лекций. Часть II (в 2-х книгах). Книга 2. -М.: Академия безопасности ФСК России, 1996 г., 300 с.

Ю.Григорьев В.Р. Синтез трёхмерных клеточных процессоров и отображение параллельных алгоритмов на трёхмерные СБИС-структуры.// Академия криптографии РФ, Тезисы докладов VIII теоретич. конференции по криптографии. Подсекция 6.1. апрель, 1996г., стр. 96.

П.Григорьев В.Р., Корольков A.B. Оптические межсоединения в мультипроцессорных вычислительных системах и нейронных сетях.// ИКСИ Академии ФСБ. Материалы Первой межведомственной конференции "Научно-техническое и информационное обеспечение деятельности специальных служб", ч.1. т.2, 1996, с. 134-136.

12. Grigor'ev V.R. Three-dimensional integral optical threshold elements. Proc. the RNNS/IEEE Symp. on Neuroinformatics and Neurocomputers. - Rostov-on-Don, Russia. -1992,- p. 161-163.

13. Авторское свидетельство на изобретение № 1739520, кл. Н 05 К 7/20. Радиоэлектронный блок.//Григорьев В.Р., Федоров В.В. - Открытия. Изобретения. - Бюлл. № 21 от 07.06.92.

14. Воробьёв Д.В., Григорьев В.Р., Резник E.H. Вычислитель дискретного преобразования Фурье на основе кронекеровского произведения матриц с использованием систолического подхода// Вопросы радиоэлектроники, сер. ЭВТ, вып. 8,1991 г., с.76-84.

15. Григорьев В.Р., Наумов С.П. Нейросетевая реализация алгоритма сортировки на трехмерном оптическом нейрочипе.// Автометрия. - № 3, 1993, с.28-37.

16. Grigor'ev V.R., Naumov S.P. Optoelectronic sorting neurochip.- In Technical Digest of Intern. Conf. on Optical Computing.- Edinburgh, Scotland, aug. 22-25,1994, pp. 311-312.

17.Григорьев В.P., Резник E.H. Трёхмерный систолический вычислитель дискретного преобразования Фурье с использованием арифметики остаточных классов.// Тезисы докладов VII Всероссийской конференции «Однородные вычислительные структуры, среды и распределенные системы» (ОВС- 94).-М.: 1994, стр. 34.

18.Григорьев В.Р. Нейронные сети и клеточные автоматы./ Обозрение прикладной и промышленной математики//Москва, научное изд-во «ТВП», сер. «Дискретная математика», т.1, № 3, 1994 г., с. 357-376.

19. Григорьев В.Р. Трехмерный оптический систолический вычислитель быстрого обращения матрицы в поле GF(2m).// Академия криптографии РФ, Тезисы докладов VIH теоретич. конференции по криптографии. Подсекция 6.1. апрель, 1996г., стр. 91.

20.Григорьев В.Р. Оптический программируемый трёхмерный вычислитель быстрой арифметики в остаточных классах для решения прикладных задач.// Академия криптографии РФ, Тезисы докладов VIII теоретич. конференции по криптографии. Подсекция 6.1. апрель, 1996г., стр. 93.

21.Grigor'ev V.R. Some problems of optoelectronics computing tools application in the tasks of digital signals processing. Некоторые проблемы применения оптоэлектронных вычислительных средств в задачах цифровой обработки сигналов. Доклады 1-ой Международной конф. «Цифровая обработка сигналов и ее применение», 30 июня-3 июля 1998, Москва, Россия, т. I, стр. 293-296.

22. Григорьев В.Р., Зязин В.П. Перспективы развития оптических цифровых вычислителей./ Труды научной конференции МИРЭА (технический университет), 2005 г.

»1566?

РНБ Русский фонд

2006-4 12364

/

Подписано в печать 10.08.05г. Формат 60x84/16. Объем 1,4 усл.п.л.

Тираж 100 экз. Заказ № 519ф/05 _

ФГУП НИИ «Квант», Москва, 4-й Лихачёвский пер., д. 15

ВВЕДЕНИЕ.

1 РАЗРАБОТКА АЛГОТРОННОГО ПОДХОДА К ПРОЕКТИРОВАНИЮ ОЦВМ НА ОСНОВЕ ТРЕХМЕРНЫХ ИНТЕГРАЛЬНО-ОПТИЧЕСКИХ СХЕМ.

1.1. Систематизация прикладных задач по размерности индексного пространства реализации графа потока вычислений.

1.1.1. Алготронный подход к пространственно-временному осуществлению вычислений в трехмерных матричных 19 процессорах.

1.1.2. Особенности отображения параллельных алгоритмов на высокопроизводительные вычислительные системы с массовым параллелизмом.

1.2. Анализ подходов к реализации трехмерных вычислительных СБИС-структур.

1.2.1. Анализ текущего состояния технологий изготовления СБИС.

1.2.2. Анализ состояния разработок и перспектив развития требуемых для изготовления ТМОИС микроэлектронных, оптоэлектронных и оптических технологий.

1.2.3. Физические, схемотехнические и алгоритмические ограничения реализаций СБИС.

1.2.4. Классификация трехмерных СБИС (ТМИС).

1.2.5. Функциональные возможности ТМИС и их влияние на архитектуру вычислительной системы.

Выводы по разделу.

2 ОТОБРАЖЕНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ В МАТРИЧНЫЕ СТРУКТУРЫ НА ОСНОВЕ ТРЁХМЕРНЫХ СБИС

2.1. Определение нижних и верхних пространственно-временных границ двумерных СБИС.

2.1.1 Определение нижних пространственно-временных границ сложности вычислений на двумерных СБИС.

2.1.2. Нахождение оценок сложности вычислений для двумерных планарных) СБИС.

2.2. Вложимость произвольного графа с п вершинами в трёхмерную область вычислений объёмных ТМИС.

2.2.1. Реализация логических сетей в трёхмерном пространстве.

2.2.2. Обобщения оценок пространственно-временных границ сложности вычислений для трёхмерных СБИС.

2.2.3. Отображение вычислительных графов на ТМИС.

2.3. Размещение схем из объёмных функциональных элементов в трёхмерном пространстве.

2.4. Исследование графов, применяемых при проектировании цифровых трёхмерных оптических матричных вычислительных структур с массовым параллелизмом.

2.4.1. Вложение графов в трёхмерное операционное пространство ТМИС.

2.4.2. N-куб и связанные с ним задачи, возникающие при проектировании цифровых трёхмерных оптических вычислительных 103 структур.

2.4.3. Синтез характеристик архитектуры проектируемой схемы, соответствующей оптимальному распараллеливанию данного алгоритма.

2.5. Нижние границы сложности вычислений в d-размерной систолической структуре.

2.6. Оценка аппаратурной и временной сложности проектирования программируемых логических матриц на основе электрооптических ТМОИС.

Выводы по разделу.

3 ОРГАНИЗАЦИЯ ВЫПОЛНЕНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В ССОК НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ТРЕХМЕРНЫХ ОПТИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМ.

3.1. Принципы построения и особенности разработки аппаратных средств на основе ТМОИС для реализации базисных операций компьютерной алгебры.

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

3.2.1. Оптический трехмерный вычислитель быстрой арифметики в остаточных классах на основе ТМОИС для решения прикладных 133 задач.

3.2.2. Функциональные устройства непозиционного процессора для выполнения немодульных операций на основе ТМОИС.

3.2.3. Реализация на основе ТМОИС операции вычисления полиномов в ССОК.

3.2.4. Оценка производительности ТМОИС для выполнения логических операций в ССОК.

Выводы по разделу.

4 СИНТЕЗ ТРЕХМЕРНЫХ ОПТИЧЕСКИХ СИСТОЛИЧЕСКИХ

ВЫЧИСЛИТЕЛЕЙ ДЛЯ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ. 155 4.1. Трехмерный систолический вычислитель дискретного преобразования Фурье на основе кронекеровского произведения матриц с использованием арифметики в остаточных классах.

4.2. Алгоритмы свертки и умножения полиномов на основе использования ТМОИС.

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

Выводы по разделу.

5 ТРЕХМЕРНЫЙ СИСТОЛИЧЕСКИЙ ВЫЧИСЛИТЕЛЬ

БЫСТРОГО ОБРАЩЕНИЯ МАТРИЦЫ В ПОЛЕ GF(2m).

5.1. Конвейерная структура для умножения в GF(2pi).

5.2. Распараллеливание алгоритма умножения в GF(2m) в пространстве 188 систолических функций.

5.3. Конвейерная структура для быстрого обращения в поле GF(2m).

5.4. Синтез электрооптического умножителя в поле GF(2m).

5.4.1. Сумматор с последовательным переносом.

5.4.2. Функциональная схема АЛУ.

5.4.3. Схема оптических связей сумматора.

5.4.4. Алгоритм сложения двух чисел с последовательным переносом.

5.4.5. Электрооптический динамический регистр сдвига.

-Выводьгпо разделу.

Резкое возрастание информационных потоков, циркулирующих в интегрированных распределённых информационно-телекоммуникационных системах, необходимость высокоскоростной обработки данных и сигналов в реальном масштабе времени, тенденции перехода к широкополосным волоконно-оптическим каналам передачи информации, широкое внедрение систем искусственного интеллекта во все составляющие организации информационного процесса ставят на повестку дня создание петафлопных (1015 оп/с) и петабайтных (1015 байт) вычислительных систем (ВС) нового поколения [1-13]. Для обеспечения такой производительности требуется наличие высокопараллельных процессоров, непосредственно реализующих в аппаратуре базовые операции линейной алгебры, цифровой обработки сигналов, анализа графов, трехмерной графики, сжатия изображений и др. При этом широкий спектр приложений, реализующих данные операции, определяет высокие требования к гибкости архитектуры ВС при цифровой обработке данных. Это требование традиционно обеспечивалось, благодаря использованию в структуре систем программируемых процессоров. Основой физико-технологической базы современных ЭВМ являются микропроцессоры, которые на сегодня характеризуется тактовой частотой порядка 1 ГГц, несколькими десятками млн. транзисторов (в чипе) и технологическими нормами - 0,2 мкм, т.е. меньше длины волны видимого света [14,15]. Производительность современных цифровых электронных однокристальных процессоров достигает 100 — 2000 млн. оп/с (Pentium III/1 ГТп, Pentium IV Хеоп/2,4 ГГц, Itanium/1,6 ГГц, IBM SP Power 3/375 МГц, Alpha 21164/667 МГц, и др.), а ВС на их основе - 1000 - 70000 млрд. оп/с [16].

Однако применительно к задачам цифровой обработки сигналов (ЦОС) применение более сложных сигналов вызывают необходимость повышения скорости обработки в 100-1000 раз. Решить эту задачу невозможно лишь за счёт совершенствования электронных аппаратных средств и приборов, так как создание сверхпроизводительных процессоров с традиционной программируемой архитектурой наталкивается на принципиальные ограничения, связанные с необходимостью обеспечения высокого уровня интеграции [17-19]; Так, микроэлектронная элементная база приближается к предельным возможностям: её слабым звеном являются соединения, с одной стороны, ограничивающие тактовые частоты работы логических устройств, а с другой -сужающие функциональные возможности ВС по эффективной параллельной реализации процессов решения практически важных задач [20-24]. В связи с этим эволюционное развитие и смена поколений ЭВМ подходит к своим пределам по производительности при переходе к рабочим частотам отдельных вентилей в субнаносекундном диапазоне. Эти пределы возникают на технологическом, физическом, алгоритмическом, архитектурном и системном уровнях [18-24].

В качестве альтернативного подхода к достижению сверхпроизводительности

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

Свое начало исследования в области создания подобных систем получили в работах таких отечественных и зарубежных ученых как Сороко В.М. [27], Василенко Г.И. [28], Микаэлян А.Л. [29], Дж. Гудмен [30,31], К.Престон [32], Г.Старк [33], Д. Кейсесент [34,35] и др. В них была показана возможность реализации систем обработки информации с параллельной обработкой массивов порядка 106 элементов. Такие оптические процессоры работают в специализированных системах, в которых нужна не точность, а высокая производительность. Построение автоматизированных когерентных оптических процессоров для обработки больших массивов требует применения уникальных узлов и учета влияния оптических шумов на точность вычислений.

Необходимость преодоления проблем, с которыми столкнулась аналоговая оптическая вычислительная техника - малая точность вычислений и отсутствие гибкости, присущей электронной технике, - стимулировала интерес к цифровой оптической обработке информации и созданию оптических сверхбыстродействующих вычислительных машин (ОСВМ). Развитие работ в этой области привело к необходимости разрабатывать новые способы представления данных, новые алгоритмы их преобразования и описания вычислительных процессов. Все эти проблемы составляют новое научное направление, которое получило название "Оптические вычисления" (Optical Computing). Физические особенности оптических методов предопределяют основные архитектурные принципы ОСВМ: параллельность работы, представление данных в виде двумерных образов, коммутация в свободном пространстве.

Важный вклад в развитие цифровых оптоэлектронных систем внесли такие отечественные и зарубежные ученые как Басов H.F. [36] и представители его школы [37,38], Лаврищев В.П. и Свидзинский К.К. [39,40], Ярославский Л.П. [41], Бурцев B.C. [42,43], Фёдоров Б.Н. [44], Торчигин В.П. [45,46], Р.Арратун [47], К.Хуан [48], К.М.Вербер [49], С.А.Коллинз [50,51], А.А.Сочук и Т.С.Стренд [52], С.Исихара [53] и другие. В их работах определены подходы к организации дискретной оптической обработки, исследованы модели цифровых оптических вычислителей с нетрадиционной архитектурой, а также механизмы реализации фотонных логических операций. Однако эти подходы, как и аналоговые, существенным образом ориентированы на использование дискретных оптических элементов (призмы, линзы, транспаранты, фотоприемные устройства и т.д.), или планарную оптоэлектронику (волноводные переключатели, дифракционные решетки и т.д.).

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

Важную стимулирующую роль для развития оптических цифровых вычислений играет развитие оптической элементной базы и схемотехнических принципов, адекватных фотонной природе носителя информации. В связи с разработкой и вводом в эксплуатацию волоконно-оптических систем передачи информации (ВОСПИ) получило решающее ускорение развитие интегральных методов производства приемопередающего и коммутационного оборудования. В результате появилось новое направление в создании элементной базы для оптических устройств передачи и обработки данных - «интегральная оптика» [58-61]. Однако с точки зрения создания больших логических систем ОСВМ планарные интегрально-оптические схемы (ОИС), по существу, в принципе не могут обеспечить эксплуатационных параметров, сравнимых с микроэлектроникой, и тем более, с наноэлектроникой (плотность упаковки, быстродействие, гибкость логических функций и т.д.) [62-68].

В настоящее время отмечается необходимость перехода от планарного к трехмерному синтезу в области технологии, которому, в свою очередь, соответствует уровень ультрамикро- и наносхемотехники [69-80], при этом на системном уровне происходит закономерный процесс трансформации эволюционного развития фон-неймановских машин к электронно-квантовым системам [7, 21,25,81-83], и в дальнейшем - к биомолекулярным системам [84-87]. Очевидна необходимость перехода от планарного мышления в сторону трехмерного пространственного, с соответствующей разработкой принципиально новых подходов к проектированию объемных трехмерных микросхем со сверхплотной упаковкой элементов и эффективному использованию третьей координаты в организации вычислительных процессов непосредственно в объеме суперсистем - однокристальных многопроцессорных вычислительных систем [88-92].

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

Вместе с тем, как показывает анализ результатов исследований последних десятилетий [25,26,57,84], сверхвысокие требования к производительности ВС могут быть реализованы при переходе от планарной оптоэлекгроники к трёх-мерной, основанной на встраивании оптических связей непосредственно в ТМИС. Принципиальную роль здесь играют непланарность размещения элементов, локальность их взаимодействий, распределенность выполняемых функций и т.д. Широкий спектр предъявляемых к вычислительным системам требований и разнообразие возможной номенклатуры трехмерных интегрально-оптических схем (ТМОИС) обусловливают множество путей в организации параллельных вычислений, отличающихся типами и степенью параллелизма, соответствием топологической структуры системы структуре выполняемых алгоритмов [93-119].

В работах коллектива ученых из ИАиЭ СО РАН и ВЦ СО РАН Косцова Э.Г., Егорова В.М., Твердохлеба П.Е., Пискунова С.В., Бандман O.JL, Ачасовой С.Н., Марковой В.П. [93-107], представлено логическое и физическое описание семейства трехмерных (многослойных) электрооптических матриц с настраиваемой структурой, используя которые можно строить оптические вычислительные устройства, выполняющие алгоритмы параллельных подстановок для массовой обработки информации.

В области цифровой обработки сигналов (ЦОС) большинство алгоритмов сводится к многократно повторяемым элементарным операциям типа скалярного перемножения и суммирования парных произведений, причем требования к скорости реализации алгоритмов и массогабаритным характеристикам вычислительного устройства очень жесткие. Как правило, реализация алгоритмов ЦОС в реальном времени возможна лишь с помощью быстродействующих специализированных процессоров. Наиболее эффективны процессоры ЦОС на основе систолических или однородных вычислительных сред (ОВС), сочетающих матричные и конвейерные методы организации параллельных вычислений [10,120-124]. Кроме того, многие алгоритмы ЦОС по своей природе носят сугубо трехмерный пространственный характер, что требует соответствующего подхода к технической реализации. Возможным вариантом такого решения может быть использование ТМОИС [67,68,108-119].

Появление новых технологий трехмерной интеграции электронных и оптических компонент, исследования в области создания трехмерных автоволновых сред, наноэлектроники и молекулярных биочипов обозначило настоятельную необходимость алгоритмической оснастки новых "многослойных" микро- и нанопроцессоров с точки зрения максимальной эффективности использования множества операционных устройств, совмещения разных форм параллелизма в едином устройстве (параллелизм в пространстве - массовые операции на множестве ПЭ и параллелизм во времени -конвейеризация на уровне отдельных вентилей): систолической-синхронной и волновой-асинхронной обработки, потоковой, использования принципов локальной и глобальной обработки, клеточной обработки, организации пространственной коммутации.

При этом необходимо обеспечивать максимальное согласование алгоритмического базиса организации параллельных вычислений и архитектуры трёхмерных оп-тоэлектронных ВС, которое реализует так называемый алготронный принцип проектирования [125], основанный на соответствии класса алгоритмов и архитектурных принципов, на совместном учете вычислительных схем, электрических, оптических и технологических характеристик цепей ТМОИС.

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

Данное обстоятельство определяет актуальность создания методов реализации высокоскоростных алгоритмов ЦОС на основе ТМОИС с учетом специфики фотонной обработки информации и особенностей построения высокопроизводительных цифровых оптических вычислительных средств.

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

Для достижения поставленной цели решались следующие задачи:

- анализ состояния проблемы разработки элементной базы двумерных и трёхмерных СБИС, а также тенденций создания электронных и оптических цифровых вычислительных машин (ОЦВМ) петафлопной производительности, ориентированных на решение прикладных задач ЦОС;

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

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

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

Решение указанной задачи обусловливает выделение в качестве предмета исследований алготронного подхода к построению цифровых оптических ВС, основанного на соответствии класса алгоритмов и архитектурных принципов, на совместном учете вычислительных схем, электрических, оптических и технологических характеристик трехмерных ОИС и предполагает: разработку теоретических основ выполнения трёхмерной цифровой оптической логической обработки (по трем индексам евклидова пространства) с учетом реализации в высокоинтегрированных объёмных интегральных схемах; разработку принципов системной организации трёхмерных интегрально-оптических коммуникационных систем и трехмерных логических систем обработки на основе элементов трехмерной интегральной оптики; разработку и исследование методов организации вычислительных процессов и построение реализующих их высокопроизводительных аппаратно-программных средств, предназначенных для обработки данных в булевом, многозначном и пороговом базисе; разработку алгоритмических и схемотехнических решений оптоэлектронных проблемно-ориентированных вычислителей в рамках единой идеологии однородных цифровых трехмерных интегрально-оптических схем (ТМОИС); разработку оптических принципов обработки данных на внутричиповом уровне, в том числе с конвейеризацией на максимально низком уровне - отдельных вентилей, позволяющих на уровне единичной ТМОИС реализовать мультипроцессорную архитектуру с "картинной" обработкой информации при использовании алгоритмов клеточных вычислений.

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

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

Основные результаты диссертации реализованы в НИР и ОКР, проводимых:

ФГУП НИИ «КВАНТ» при разработке высокопроизводительных вычислительных комплексов;

ФГУП НИИ «Восход» при разработке методических положений по созданию технических средств, специального программного и информационного обеспечения автоматизированных комплексов обработки информации;

Академией криптографии Российской Федерации при исследовании возможности создания проблемно-ориентированных высокопроизводи-тельных вычислительных систем и специальных средств защиты информации, а также использованы при организации учебного процесса:

Московским государственным университетом им. М.В. Ломоносова;

Институтом криптографии, связи и информатики Академии ФСБ России;

Московским государственным институтом радиоэлектроники и автоматики (технический университет).

Материалы диссертации опубликованы в 36 печатных работах (из них - 3 книги (курсы лекций), 11 статей, 17 тезисов докладов на конференциях), 7 отчётах о научно - исследовательской работе.

Технические решения, предложенные в работе, защищены 5 авторскими свидетельствами.

Основные положения диссертации в период с 1982 по 2005 годы доложены и одобрены на международных, Всесоюзных и Всероссийских конференциях, школах-семинарах и совещаниях; ведомственных научно-технических и военно-научных конференциях КГБ СССР, Академии ФСБ России, Академии криптографии РФ, Академии ФАПСИ, НИИ "КВАНТ" и др.

Полученные результаты могут найти применение в научно - исследовательских учреждениях федеральных органов исполнительной власти, организациях промышленности и высших учебных заведениях при решении задач:

• построения алгоритмических, программных и аппаратных средств высокопроизводительных ЭВМ, вычислительных комплексов и систем, ориентированных на решение задач цифровой обработки сигналов, кодирования и защиты информации, связанных с обработкой больших массивов бинарных и многозначных данных;

• создания практических методик и рекомендаций при проектировании специализированных оптоэлектронных процессоров для решения практически важных задач цифровой обработки сигналов на основе использования ТМОИС;

• решения в реальном масштабе времени многомерных задач цифровой обработки сигналов, кодирования и защиты информации на основе перспективной технологии ТМОИС;

• организации учебного процесса по специальностям: «Компьютерная безопасность» (075200), «Комплексное обеспечение информационной безопасности автоматизированных систем» (075500), «Информационная безопасность телекоммуникационных систем» (075600).

ЗАКЛЮЧЕНИЕ

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

В ходе исследований получены следующие новые теоретические и практические результаты.

1. Проведен анализ состояния проблемы разработки элементной базы двумерных и трёхмерных СБИС, а также тенденций создания электронных и оптических цифровых вычислительных машин петафлопной производительности, ориентированных на решение прикладных задач цифровой обработки сигналов и защиты информации. Проанализированы системные физические, технологические, схемотехнические и алгоритмические ограничения реализаций двумерных и трехмерных СБИС. Предложена классификация трехмерных СБИС и основанных на них архитектурных принципов системной организации вычислений в однокристальных многопроцессорных вычислительных системах. Обоснована необходимость создания новой элементной базы для цифровых сигнальных процессоров на основе ТМОИС. Определены требования к физическим характеристикам элементов ТМОИС.

2. Исследованы характерные особенности организации вычислительных процессов с массовым параллелизмом в ТМОИС при решении прикладных задач цифровой обработки сигналов, которые потребовали введения новых пространственно-временных критериев организации обработки информации в трёхмерных оптических интегрированных вычислительных структурах (архитектурных, алгоритмических, структурных, объемно-временных, энергетических, физических и т.д.). Показано, что ТМОИС по сравнению с электронными СБИС имеют качественно более высокую производительность при решении указанного класса задач.

3. Для реализации трехмерной технологии построения оптических интегральных устройств предложена методика получения верхних и нижних оценок пространственно-временных границ размещения произвольного вычислительного графа на п вершинах в трехмерном пространстве. С этой целью сформулирован и доказан ряд теорем. Доказано, что для ряда нерегулярных и регулярных графов более предпочтительной по сравнению с двумерной является трёхмерная реализация, поскольку длина 1 связей графа уменьшается от 0(n/log2n) для плоских схем до 0(п ) для трёхмерных.

Соответственно, граф занимает площадь 0(и2) - для плоских схем, и объём 0(л3/2) - для трёхмерных. На основе сравнения размещения схем на плоскости и в трёхмерном пространстве сделан вывод, что в принципе трёхмерная технология позволит сокра

1 /9 тить линейные размеры схем с Q(n) до 0(п ), а максимальную длину проводников с

1 ГУ

Q(n/loq п) до 0(п ). Разработаны принципы отображения параллельных алгоритмов на трехмерные матричные оптические структуры, обеспечивающие структурно-параметрическую организацию вычислительного процесса. Произведена оценка нижних границ временной сложности вычислений параллельного алгоритма в соразмерной систолической структуре, в том числе, в трёхмерных систолических матрицах с оптическими информационными каналами. С учетом природы оптических каналов передачи и обработки данных предложен метод получения оценок аппаратурной и временной сложности проектирования программируемых логических матриц на основе реализации электрооптических ТМОИС.

4. Предложены модели, структурные и архитектурные решения ТМОИС с массовыми параллельными каналами обработки для решения прикладных задач цифровой обработки сигналов и защиты информации, основанные на новом физическом принципе - введении в структуру СБИС оптических каналов связи.

5. Предложена базовая модель трёхмерного оптоэлектронного вычислителя в системе счисления в остаточных классах на основе использования массовых оптических связей между слоями и оптическими (электронными) соединениями в рамках отдельных слоев. Разработано устройство непозиционного процессора для выполнения немодульных операций. Структура непозиционного процессора позволяет уменьшить деградацию при отказе и обеспечить более надежную работу процессора, причем в отличие от традиционных процессоров не потребуется усложнение программы или введения дополнительной аппаратуры, а корректирующие коды в СОК позволяют обнаруживать и исправлять ошибки, возникающие во всех устройствах предложенного вычислителя. Показано, что с помощью одной ТМОИС можно выполнять 4-байтные арифметические операции в СОК с тактом порядка 1 ГГц.

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

7. Предложены новые методы выполнения базовых операций цифровой обработки сигналов: дискретного преобразования Фурье и свертки на основе аппаратной" реализации операций модульной арифметики в кольце целых чисел на трехмерных бит-слайсовых архитектурах многоканальных ТМОИС. Разработаны эффективные систолические алгоритмы реализации этих операций, являющихся вычислительным ядром для решения широкого класса задач цифровой обработки сигналов, имеющих теоретическое и практическое применение.

8. Предложена архитектура трёхмерного систолического вычислителя дискретного преобразования Фурье и разработан эффективный систолический алгоритм его реализации. В основу подхода положена структура вычислений с использованием схемы индексации Гуда-Томаса для простых делителей, выполнение кронекеровского произведения матриц и реализация прямого метода вычисления циклической свертки для небольшого простого числа входных данных. Показано, что для вычисления ДПФ длины п с использованием предлагаемой комбинации систолического алгоритма и структуры трёхмерного оптического вычислителя необходимо на порядок меньше вычислительных элементов (умножитель + сумматор), чем при систолизации ДПФ в случае использования обычных двумерных электронных СБИС. При этом обработка данных осуществляется фактически в реальном масштабе времени, а время вычисления составляет Т~2п.

9. Предложено несколько типов архитектуры вычислителей свертки полиномов, отличающихся по степени параллелизма N, N2 и N3. Проведено сравнение предложенных вариантов систолических вычислителей свертки по следующим параметрам: временной и емкостной сложности, а также параметру эффективности (ускорения вычислений). Показано, что увеличение размерности обработки в объемных-трехмерных вычислителях со встроенными оптическими связями приводит к существенному росту производительности (на порядок и выше) при меньших аппаратных затратах. Выполнена оценка требований к технической реализации предложенных типов оптических цифровых сигнальных процессоров. Сделан вывод, что современный уровень развития технологий создания элементной базы цифровой оптики позволяет достигнуть на предложенных вычислителях производительности порядка 1015 оп/с.

10. Разработаны методы и схемотехнические решения аппаратных средств реализации компьютерной алгебры в оптоэлектронных систолических процессорах на основе ТМОИС для решения прикладных задач цифровой обработки сигналов, в том числе систолических алгоритмов вычисления обратного элемента в поле GF(2m). Предложена новая последовательная по входу - параллельная по выходу конвейерная архитектура оптического умножителя в GF(2m). Показано, что процедура выполнения быстрой инверсии на предложенном вычислителе требует mx(q+p) временных тактов, при этом вычислительная сложность обращения элемента в GF(2m) составляет 0(mlog2m). Этот результат представляет практический интерес для использования в криптосистемах, где данные сегментируются на длинные блоки, т.е., где m является очень большим для достижения необходимых параметров защиты и желательна высокая производительность.

Диссертация основана на исследованиях, выполненных автором самостоятельно.

1. Левин В.К. Высокопроизводительные мультимикропроцессорные системы// Информационные технологии и вычислительные системы, 1995, № 1, с. 12-20.

2. Левин В.К. Структурно-технические характеристики и направления развития высокопроизводительных вычислительных систем/ Сб. статей ЭВТ. Вып. 2. /Под ред. В.В.Пржиялковского М.: Радио и связь, 1988. - с.4-16.

3. Фортов В.Е., Левин В.К., Савин Г.И., Забродин А.В., Каратанов В.В., Елизаров Г.С., Корнеев В.В., Шабанов Б.М. "Наука и промышленность России". Суперкомпьютер МВС-1000М и перспективы его применения. "Наука и промышленность России" 2001, № 11(55).

4. Корнеев В.В. Будущее высокопроизводительных вычислительных систем// Открытые системы, № 5, 2003.

5. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», 1999.320 с.

6. Митрофанов В., Ларионов К-, Слуцкин Д., Эйсымонт Л. Направления развития отечественных высокопроизводительных вычислительных систем// Открытые системы, № 5, 2003.

7. Бурьянофф Дж. Будущее нановычислений// Открытые системы, № 10, 2003.

8. Бурцев B.C. Тенденции развития супер-ЭВМ.// Вычислительные машины с нетрадиционной архитектурой. Супер-ЭВМ. Сб. науч. тр. ВЦКП АН СССР- М.: Наука, 1990, с. 3-26.

9. Бурцев B.C. О необходимости создания супер-ЭВМ в России.// Информационные технологии и вычислительные системы, 1995, № 1, с.5-11.

10. Кун С. Матричные процессоры на СБИС: Пер. с англ. М.: Мир, 1991. - 672 с.

11. Григорьев В.Р., Колобашкин С.М. Параллельные вычислительные системы с общим управлением. /Курс лекций. Часть I М.: Высшая школа КГБ, 1991г., 260(234).

12. Григорьев В.Р. Применение высокопроизводительных систем для решения спецзадач. Параллельные вычислительные системы с распределенным управлением. Курс лекций. Часть II (в 2-х книгах). Книга 1. М.: Академия безопасности ФСК России, 1996 г., 341 с.

13. Григорьев В.Р. Применение высокопроизводительных систем для решения спецзадач. Параллельные вычислительные системы с распределенным управлением. Курс лекций. Часть II (в 2-х книгах). Книга 2. М.: Академия безопасности ФСК России, 1996 г., 300 с.

14. Шахнов В., Власов А., Кузнецов А. Элементная база параллельных вычислений// Открытые системы, № 5-6, 2001.

15. Корнеев В. В., Киселев А. В. Современные микропроцессоры, 2-е изд. М.: НОЛИДЖ, 2000,315 с.16. hftp://www./ТОР500 List 71-2004.htm

16. Новиков А.А. Состояние и основные направления развития технической базы суперЭВМ //Сб. статей ЭВТ. Вып. 3. /Под ред. В.В.Пржиялковского М.: Радио и связь, 1989. - с.66-89.

17. Самсонов Н.С. Проблемы повышения функциональной производитель-ности и интеграции СБИС. //Сб. статей ЭВТ. Вып. 3. /Под ред. В.В.Пржиялковского -М.: Радио и связь, 1989. с.90-96.19.20,2122,23,2425,2627,28