Содержание к диссертации
Введение
1 Разработка алготронного подхода к проектированию оцвм на основе трехмерных интегрально-оптических схем 19
1.1. Систематизация прикладных задач по размерности индексного пространства реализации графа потока вычислений. 19
1.1.1. Алготронный подход к пространственно-временному осуществлению вычислений в трехмерных матричных процессорах 19
1.1.2. Особенности отображения параллельных алгоритмов на высокопроизводительные вычислительные системы с массовым параллелизмом 28
1.2. Анализ подходов к реализации трехмерных вычислительных СБИС-структур 39
1.2.1. Анализ текущего состояния технологий изготовления СБИС... 39
1.2.2. Анализ состояния разработок и перспектив развития требуемых для изготовления ТМОИС микроэлектронных, оптоэлектронных и оптических технологий 44
1.2.3. Физические, схемотехнические и алгоритмические ограничения реализаций СБИС 55
1.2.4. Классификация трехмерных СБИС (ТМИС) 70
1.2.5. Функциональные возможности ТМИС и их влияние на архитектуру вычислительной системы 74
2 Отображение параллельных алгоритмов в матричные структуры на основе трёхмерных сбис 80
2.1. Определение нижних и верхних пространственно-временных границ двумерных СБИС. 80
2.1.1 Определение нижних пространственно-временных границ сложности вычислений на двумерных СБИС 82
2.1.2. Нахождение оценок сложности вычислений для двумерных (планарных) СБИС 83
2.2. Вложимость произвольного графа с п вершинами в трёхмерную область вычислений объёмных ТМИС 87
2.2.1. Реализация логических сетей в трёхмерном пространстве 88
2.2.2. Обобщения оценок пространственно-временных границ сложности вычислений для трёхмерных СБИС 91
2.2.3. Отображение вычислительных графов на ТМИС 93
2.3. Размещение схем из объёмных функциональных элементов в трёхмерном пространстве 95
2.4. Исследование графов, применяемых при проектировании цифровых трёхмерных оптических матричных вычислительных структур с массовым параллелизмом 98
2.4.1. Вложение графов в трёхмерное операционное пространство ТМИС 98
2.4.2. N-куб и связанные с ним задачи, возникающие при проектировании цифровых трёхмерных оптических вычислительных структур 103
2.4.3. Синтез характеристик архитектуры проектируемой схемы, соответствующей оптимальному распараллеливанию данного алгоритма 139
2.5. Нижние границы сложности вычислений в d-размерной систолической структуре 111
2.6. Оценка аппаратурной и временной сложности проектирования программируемых логических матриц на основе электрооптических ТМОИС 113
3 Организация выполнения параллельных вычислений в ССОК на основе использования трехмерных оптических интегральных схем 120
3.1. Принципы построения и особенности разработки аппаратных средств на основе ТМОИС для реализации базисных операций компьютерной алгебры 120
3.2. Синтез вычислительных устройств на основе использования трехмерных оптических интегральных схем для выполнения групповых арифметических операций в системе счисления в остаточных классах 131
3.2.1. Оптический трехмерный вычислитель быстрой арифметики в остаточных классах на основе ТМОИС для решения прикладных 133
задач
3.2.2. Функциональные устройства непозиционного процессора для выполнения немодульных операций на основе ТМОИС 145
3.2.3. Реализация на основе ТМОИС операции вычисления полиномов вССОК 150
3.2.4. Оценка производительности ТМОИС для выполнения логи ческих операций в ССОК 152
Выводы по разделу 156
4 Синтез трехмерных оптических систолических вычислителей для цифровой обработки сигналов . 155
4.1. Трехмерный систолический вычислитель дискретного преобразования Фурье на основе кронекеровского произведения матриц с использованием арифметики в остаточных классах 155
4.2. Алгоритмы свертки и умножения полиномов на основе использования ТМОИС 164
4.3. Оценка физических параметров для технической реализации цифровых сигнальных процессоров на основе использования оптоэлектронных трехмерных устройств 177
5 Трехмерный систолический вычислитель быстрого обращения матрицы в поле GF(2m) 185
5.1. Конвейерная структура для умножения в GF(2'n) 185
5.2. Распараллеливание алгоритма умножения в GF(2m) в пространстве 188 систолических функций
5.3. Конвейерная структура для быстрого обращения в поле GF(2m) .192
5.4. Синтез электрооптического умножителя в поле GF(2m) 198
5.4.1. Сумматор с последовательным переносом 198
5.4.2. Функциональная схема АЛУ 198
5.4.3. Схема оптических связей сумматора 200
5.4.4. Алгоритм сложения двух чисел с последовательным переносом... 201
5.4.5. Электрооптический динамический регистр сдвига 203
Заключение 208
Список использованных источников
Приложения.
- Анализ подходов к реализации трехмерных вычислительных СБИС-структур
- Вложимость произвольного графа с п вершинами в трёхмерную область вычислений объёмных ТМИС
- Синтез вычислительных устройств на основе использования трехмерных оптических интегральных схем для выполнения групповых арифметических операций в системе счисления в остаточных классах
- Алгоритмы свертки и умножения полиномов на основе использования ТМОИС
Введение к работе
Резкое возрастание информационных потоков, циркулирующих в интегрированных распределённых информационно-телекоммуникационных системах, необходимость высокоскоростной обработки данных и сигналов в реальном масштабе времени, тенденции перехода к широкополосным волоконно-оптическим каналам передачи информации, широкое внедрение систем искусственного интеллекта во все составляющие организации информационного процесса ставят на повестку дня создание петафлопных (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].
В работах коллектива ученых из ИАиЭ СО РАН и ВЦ СО РАН Косцова Э.Г., Егорова В.М., Твердохлеба П.Е., Пискунова СВ., Бандман О.Л., Ачасовой С.Н., Марковой В.П. [93-107], представлено логическое и физическое описание семейства трехмерных (многослойных) электрооптических матриц с настраиваемой структурой, используя которые можно строить оптические вычислительные устройства, выполняющие алгоритмы параллельных подстановок для массовой обработки информации. В области цифровой обработки сигналов (ЦОС) большинство алгоритмов сводится к многократно повторяемым элементарным операциям типа скалярного перемножения и суммирования парных произведений, причем требования к скорости реализации алгоритмов и массогабаритным характеристикам вычислительного устройства очень жесткие. Как правило, реализация алгоритмов ЦОС в реальном времени возможна лишь с помощью быстродействующих специализированных процессоров. Наиболее эффективны процессоры ЦОС на основе систолических или однородных вычислительных сред (ОВС), сочетающих матричные и конвейерные методы организации параллельных вычислений [10,120-124]. Кроме того, многие алгоритмы ЦОС по своей природе носят сугубо трехмерный пространственный характер, что требует соответствующего подхода к технической реализации. Возможным вариантом такого решения может быть использование ТМОИС [67,68,108-119].
Появление новых технологий трехмерной интеграции электронных и оптических компонент, исследования в области создания трехмерных автоволновых сред, наноэлектроники и молекулярных биочипов обозначило настоятельную необходимость алгоритмической оснастки новых "многослойных" микро- и нанопроцессоров с точки зрения максимальной эффективности использования множества операционных устройств, совмещения разных форм параллелизма в едином устройстве (параллелизм в пространстве - массовые операции на множестве ПЭ и параллелизм во времени -конвейеризация на уровне отдельных вентилей): систолической-синхронной и волновой-асинхронной обработки, потоковой, использования принципов локальной и глобальной обработки, клеточной обработки, организации пространственной коммутации.
При этом необходимо обеспечивать максимальное согласование алгоритмического базиса организации параллельных вычислений и архитектуры трёхмерных оп-тоэлектронных ВС, которое реализует так называемый алготронный принцип проектирования [125], основанный на соответствии класса алгоритмов и архитектурных принципов, на совместном учете вычислительных схем, электрических, оптических и технологических характеристик цепей ТМОИС.
Полученные результаты ставят на повестку дня вопрос о разработке специализированных ВС на основе ТМОИС для решения специальных задач информационно-логической обработки данных. Их объединяет использование трех принципов - трёхмерности операционного пространства организации вычислительного процесса в объеме СБИС, систолизации алгоритмического базиса решаемых классов задач, многопроцессорности обработки данных в составе однокристальных ТМОИС. Подобная универсальность приводит к возможности проектирования мультипроцессорного кристалла с программируемыми оптическими связями между конвейерами с параметризацией соответствующих внутри- и межслойных связей в ТМОИС.
Данное обстоятельство определяет актуальность создания методов реализации высокоскоростных алгоритмов ЦОС на основе ТМОИС с учетом специфики фотонной обработки информации и особенностей построения высокопроизводительных цифровых оптических вычислительных средств.
Целью работы Целью диссертационной работы является повышение эффективности использования операционного ресурса вычислительных средств на базе многослойных трёхмерных оптических интегральных схем для решения актуальных прикладных задач ЦОС путем развития их методического, алгоритмического и схемотехнического обеспечения.
Для достижения поставленной цели решались следующие задачи:
анализ состояния проблемы разработки элементной базы двумерных и трёхмерных СБИС, а также тенденций создания электронных и оптических цифровых вычислительных машин (ОЦВМ) петафлопной производительности, ориентированных на решение прикладных задач ЦОС;
разработка принципов выполнения трёхмерной цифровой оптической логики (по трем индексам евклидова пространства) с учетом реализации в высокоинтегриро-ванных трёхмерных интегрально-оптических схемах и системах;
разработка методов и схемотехнических решений построения трёхмерных интегрально-оптических схем с модуляцией светового потока;
разработка принципов системной организации вычислительных процессов и построения высокопроизводительных оптоэлектронных аппаратно-программных средств для обработки данных в булевом, многозначном и пороговом базисе, а также методов их реализации.
Решение указанной задачи обусловливает выделение в качестве предмета исследований алготронного подхода к построению цифровых оптических ВС, основанного на соответствии класса алгоритмов и архитектурных принципов, на совместном учете вычислительных схем, электрических, оптических и технологических характеристик трехмерных ОИС и предполагает:
разработку теоретических основ выполнения трёхмерной цифровой оптической логической обработки (по трем индексам евклидова пространства) с учетом реализации в высокоинтегрированных объёмных интегральных схемах;
разработку принципов системной организации трёхмерных интегрально-оптических коммуникационных систем и трехмерных логических систем обработки на основе элементов трехмерной интегральной оптики;
разработку и исследование методов организации вычислительных процессов и построение реализующих их высокопроизводительных аппаратно-программных средств, предназначенных для обработки данных в булевом, многозначном и пороговом базисе;
разработку алгоритмических и схемотехнических решений оптоэлектронных проблемно-ориентированных вычислителей в рамках единой идеологии однородных цифровых трехмерных интегрально-оптических схем (ТМОИС);
разработку оптических принципов обработки данных на внутричиповом уровне, в том числе с конвейеризацией на максимально низком уровне - отдельных вентилей, позволяющих на уровне единичной ТМОИС реализовать мультипроцессорную архитектуру с "картинной" обработкой информации при использовании алгоритмов клеточных вычислений.
Методы исследования. При решении поставленной в диссертации задачи использовались методы системного анализа, теории графов, теории групп, теории конечных колец и полей, теории кодирования, линейной алгебры, положений вычислительной математики (в том числе, непозиционных систем счисления), теории чисел, теории искусственных нейронных сетей, логических и схемотехнических методов синтеза вычислительных устройств.
Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. В приложении 1 приведена методологическая структура диссертации. В приложении 2 указаны основные направления диссертационных исследований (заштриховано желтым цветом).
Во введении обосновывается актуальность работы, формулируются цель, задачи, объект и предмет диссертационного исследования, показываются научная новизна, теоретическая и практическая значимость работы, приводятся основные положения, выносимые на защиту.
В первой главе исследуется проблема разработки оптических ЦВМ петафлоп-ной производительности, и обосновывается необходимость пересмотра совокупности стоимостных критериев (архитектурных, алгоритмических, структурных, объемно-временных, энергетических, физических и т.д.), определяющих производительность суперЭВМ нового поколения. Предлагается системная классификация взаимовлияния этих критериев на эффективность и производительность оптических ЦВМ.
Развивается "алготронный" подход (одновременное рассмотрение характеристик алгоритмов и реализующих их электронных СБИС) к разработке однокристальной мультипроцессорной системы на ТМОИС, основанный на естественном «природном» соответствии класса многомерных алгоритмов и адекватных по размерности пространства вычислений архитектурных принципов, на совместном учете вычисли-
тельных схем, электрических, оптических, топологических и технологических характеристик цепей ТМ СБИС.
Проводится анализ состояния технологий изготовления СБИС и тенденций развития интеграции кремниевых УБИС в период с середины 1990-х гг. вплоть до 2010 г. В области развития перспективных технологий создания петафлопных суперЭВМ обосновывается необходимость перехода от планарного к трехмерному синтезу, которому, в свою очередь, соответствует уровень ультрамикро- и наносхемотехники, при этом на системном уровне исследуется закономерный процесс трансформации эволюционного развития фон-неймановских машин к электронно-квантовым системам с соответствующей разработкой принципиально новых подходов к проектированию объемных трехмерных микросхем со сверхплотной упаковкой элементов и эффективному использованию третьей координаты в организации вычислительных процессов непосредственно в объеме твердотельных суперсистем - однокристальных многопроцессорных вычислительных систем.
Проводится анализ состояния и перспектив развития требуемых для изготовления ТМОИС микроэлектронных, оптоэлектронных и оптических технологий. Анализируются системные физические, схемотехнические и алгоритмические ограничения реализаций двумерных и трехмерных СБИС. Проводится классификация трехмерных СБИС (ТМИС).
Проведенный в первой главе анализ состояния разработок электронных и оптических ЦВМ петафлопной производительности, полученная классификация технологий изготовления трёхмерных БИС и выработанные новые пространственно-временные критерии обработки информации в ТМОИС для решения прикладных задач ЦОС в зависимости от размерности пространства осуществления вычислений определяют основные направления диссертационного исследования, состоящие в разработке теоретических основ проектирования ТМОИС, создании алгоритмических моделей решения класса прикладных задач ЦОС в ВС с трёхмерной операционной средой, синтезе новых арифметических и логических методов, ориентированных на вычислительные средства общего и проблемно-ориентированного назначения, и разработке схемотехнических решений ТМОИС для их аппаратной поддержки.
Во второй главе на основе анализа графов вычислительной структуры проводится оценка нижних и верхних пространственно-временных границ сложности реализации вычислительных алгоритмов на базе двумерных и трехмерных СБИС. Доказывается ряд теорем о вложимости произвольных графов с п вершинами в трехмерную область объёмных ТМИС, и на основе характеристики степени информативности функции производится оценка сложности вычислений для электронных ТМИС.
Производится оценка нижних границ временной сложности вычислений параллельного алгоритма в ^/-размерной систолической структуре, в том числе, в трехмерных систолических матрицах.
Исследуются вопросы проектирования трехмерных СБИС-структур с точки зрения условий вложимости графа прикладной задачи в трехмерную решетку. Исследуется вопрос о покрытиях булевых функций и возможности использования аппарата теории булевых функций при решении задачи размещения элементов при проектировании «многомерных» типов архитектур многопроцессорных вычислительных систем. С учетом того, что структуры подграфов N-куба. и М-решетки во многом совпадают, исследуются монотипные графы, порождающие один тип функций, с точки зрения их вложимости в качестве подграфов в N-куб. Показывается, что исследованные типы графов естественным образом согласуются с трехмерным операционным пространством как внутри ТМИС, так и на верхнем уровне пространственной архитектуры трехмерного оптического цифрового вычислителя.
Предлагается метод получения оценок аппаратурной и временной сложности проектирования программируемых логических матриц (ПЛМ) на основе реализации электрооптических ТМОИС.
Третья глава посвящена разработке методов и средств выполнения параллельных вычислений в конечных полях и кольцах на основе использования трехмерных оптических интегральных схем в качестве аппаратных средств реализации компьютерной алгебры в системах цифровой обработки сигналов.
Предлагается подход к реализации трехмерного ассоциативного таблично-алгоритмического электрооптического вычислителя в остаточных классах. Предлагаются схемотехнические реализации сумматора, устройств вычитания, умножения и деления, устройства непозиционного процессора для выполнения немодульных операций, а также рассматриваются алгоритмы и структуры преобразования числа из позиционной системы счисления в систему остаточных классов и обратно.
В четвертой главе предложена реализация нового типа трехмерного вычислителя для решения нескольких практически важных задач ЦОС, где операции в ССОК являются базовыми. Вычисления в конечных кольцах являются важным разделом специальных задач ЦОС. Предлагается подход к реализации трехмерного систолического вычислителя дискретного преобразования Фурье на основе кронекеровского произведения матриц. Исследуется возможность использования трехиндексного вычислительного пространства ТМ ОИС для реализации алгоритмов свертки и умножения полиномов..
Показывается, что данный тип вычислителя ЦОС может быть построен на основе сочетания систолической обработки в третьем измерении, использования системы счисления в СОК и технологии трёхмерного монтажа в виде ТМОИС. Предлагаются структурные и схемотехнические решения по реализации предложенных алгоритмов на трёхмерных систолических электрооптических структурах.
Пятая глава посвящена вопросам разработки быстрого алгоритма обращения матрицы в поле GF(2m). Актуальность этой задачи связана с широким кругом
приложений конечных полей Галуа GF(2m) в задачах цифровой сигнальной обработки, теории переключений, в области организации связи: от кодов, исправляющих ошибки, до криптографии. В связи с этим существует настоятельная необходимость в быстрых алгоритмах умножения и обращения в конечных полях. Разрабатываются технические предложения по реализации рассмотренных алгоритмов на основе использования трехмерных оптических чипов. Даются оценки временной и емкостной сложности для предложенных алгоритмов, реализованных на оптических трехмерных вычислителях в сравнении с ЭВМ.
В заключении приведены основные результаты работы.
Научная новизна диссертационной работы заключается в разработке принципов и методов повышения производительности и эффективности использования операционных ресурсов оптических цифровых вычислительных средств, в разработке алгоритмов обработки логических и арифметических данных в оптических микропроцессорах и схемотехнических решений по построению скоростных трехмерных многослойных оптических интегральных схем.
Теоретическая значимость исследования. Разработанная совокупность методов и технических средств, обладающих единством трёхмерных принципов логической обработки, архитектуры и элементной базы ТМОИС, расширяет и углубляет теоретические основы методов и принципов построения алгоритмических, программных и аппаратных средств высокопроизводительных ЭВМ, вычислительных комплексов и систем, ориентированных на решение задач ЦОС, связанных с обработкой больших массивов бинарных и многозначных данных.
Практическая значимость исследования заключается в создании практических методик и рекомендаций при проектировании специализированных оптоэлек-тронных процессоров для решения практически важных задач ЦОС на основе использования ТМОИС.
Результаты работы в виде математических моделей, алгоритмов, программ и аппаратных решений применялись при создании вычислительных средств специального назначения на новой элементной базе ТМОИС.
Предложены и исследованы оригинальные, защищенные авторскими свидетельствами, схемотехнические решения организации вычислений в системе остаточных классов, а также архитектурные принципы построения гибридных оптоэлек-тронных специализированных вычислительных устройств.
Основные положения, выдвигаемые на защиту. На защиту выносятся следующие новые научные положения, предложенные и разработанные лично автором:
1. Принципы построения цифровых оптических вычислительных средств, основанные на соответствии класса алгоритмов и архитектур, на совместном учете вычислительных схем, электрических, оптических и топологических характеристик ТМОИС.
2. Методика определения нижних и верхних оценок сложности ТМОИС и
сложности реализуемых на них прикладных алгоритмов цифровой обработки сигна
лов.
Модели, структурные и архитектурные решения ТМОИС.
Методы и схемотехнические решения по построению аппаратных средств реализации компьютерной алгебры в системах цифровой обработки сигналов на основе использования ТМОИС.
Автор выражает глубокую благодарность научному руководителю д.т.н., профессору, академику РАН, академику Академии криптографии РФ Левину В.К. за ценные замечания, полезные обсуждения и помощь в работе. Автор искренне признателен д.ф.-м.н. Косцову Э.Г. за выбор направления научных исследований в области цифровой трёхмерной оптики. Автор выражает особую признательность д.т.н., профессору, академику РАЕН, члену-корреспонденту Академии криптографии РФ Никонову В.Г., д.т.н., профессору, академику РАЕН Шубинскому И.Б., д.т.н. Тарасову А.А., к.ф.-м.н., доценту Зязину В.П., взявших на себя труд прочитать диссертацию и своими ценными советами и рекомендациями способствовавших завершению работы над ней. Автор считает своим долгом поблагодарить всех коллег, которые проявили заинтересованность в данной работе и оказали существенную моральную поддержку.
Анализ подходов к реализации трехмерных вычислительных СБИС-структур
В настоящее время совершенствование технологии изготовления СБИС осуществляется в основном по линии уменьшения геометрических размеров активных и пассивных элементов (принцип масштабирования), а также путем улучшения качества изоляции между этими элементами. Технологически все труднее уменьшать размеры деталей транзисторов, а по мере того, как это все же удается делать, лавинообразно нарастают сложные физические явления в работающих приборах. Быстродействие приборов приближается к верхнему, а энергопотребление - к нижнему пределу, на совершенно ином уровне проявляются проблемы отвода мощности и проблемы внутренних связей в СБИС-системах в целом. Проектирование элементов становится столь сложным, что продолжать его в рамках старых концепций и старыми средствами оказывается невозможным, а проектирование ЭВМ требует принципиально нового понимания основных функций и архитектуры машин.
В той же степени, в какой физические явления обеспечивают реализацию информационных функций, технология обеспечивает реализацию необходимых физических структур и протекающих в них явлений. Практическое применение новых методов фотолитографии и рентгенолитографии позволило перейти к реализации субмикронных размеров элементов. По мере приближения к субмикронному рубежу линейных размеров активной области транзисторов нелинейные эффекты, а также краевые явления рассеяния носителей, «короткий» и «узкий» каналы, насыщение скорости и изменение подвижности носителей и другие эффекты сильного поля приобрели принципиальный характер. Это привело к радикальному изменению методики расчета и оптимизации приборов: линейные модели заменены двумерными, частично начинается переход к трехмерным моделям; аналитические методы решения уравнений заменяются численным моделированием на ЭВМ [19-21].
Асинхронно с формальными показателями прогресса микроэлектроники -ростом быстродействия и степени интеграции элементов - имеется скрытая тенденция функциональной интеграции - перевода в кристалл цифро-аналоговых, аналого-цифровых и множества специализированных функций и постепенной «вторичной» интеграции гетерогенных по своим функциям устройств в одном кристалле сверхбольших ИС [1-15,19-21,124].
Объединение элементно-технологической и аппаратно-конструкторской ветвей технических средств ВТ произошло вместе с возникновением электроники. На протяжении всей предшествующей истории технологии принадлежал синтез исходных материалов, а конструирование включало создание элементов и аппаратуры (рис. 1.4) [21]. Современная история ВТ начинается с момента слияния указанных ветвей, т.е. с возникновения микроэлектроники. Дальнейшая эволюция - это прогрессирующее слияние технологии и конструирования, технологии и системотехники, технологии и прикладной математики. Иными словами, с ростом степени интеграции в единое кристаллическое устройство переходят все более высокие ранги проектирования и изготовления средств ВТ. Результатом этих тенденций к настоящему времени явилось создание СБИС, сложность внутренней организации и производительность которых многократно превышает соответствующие показатели первых ЭВМ. Машина недавнего прошлого вместе со своими базисными принципами оказалась составной частью или элементом машин новых классов. Эта революция в масштабировании требует радикального пересмотра всех аспектов техники обработки информации — проектирования элементов, машин и их программного обеспечения.
Но, несмотря на все достижения в твердотельной элементной базе, надо отметить, по крайней мере, четыре противоречия, которые присущи развитию современной микроэлектроники.
Во-первых, при переходе к субмикронным размерам не удается автоматически уменьшить размеры некоторых областей, определяемых их физической природой. Определяющими параметрами являются тогда размеры барьерных областей, которые не зависят от разрешающей способности того или иного фотолитографического про цесса. Применение физического масштабирования (изменение концентраций примесей или законов их распределения) наряду с геометрическим масштабированием частично снимает остроту этого противоречия, но не снимает его полностью [18-24].
Во-вторых, нерешенной остается проблема использования исходного полупроводникового материала («кремниевая эффективность»). Глубина кармана для реализации элементов обычно не превышает 5-8 мкм, что составляет не более 2 % от толщины исходной полупроводниковой подложки равной 360-400 мкм. Если учесть, что в карманах формируется только половина активных элементов (при КМДП-технологии), то можно заключить, что даже при наиболее материалоемкой технологии на изготовление элементов расходуется лишь около 1% исходного полупроводникового материала [14,20,21,24,84,90].
В-третьих, даже при создании СБИС, содержащих однотипные субэлементы, связанные между собой локально и регулярно, большую роль играет площадь, занимаемая линиями связи. На практике доказано, что в СБИС, содержащей порядка 105 ячеек (простых субэлементов), площадь, занимаемая коммутационными линиями (до 90% всей площади кристалла), значительно превышает площадь, занимаемую активными и пассивными элементами [20,21, 23]. Таким образом, падает эффективность использования площади кристалла.
В-четвертых, классический подход к изготовлению систолических СБИС (на основе систолических матриц) и СБИС в виде спецпроцессоров позволяет реализовать на уровне схемной архитектуры только алгоритмы тех классов задач, в вычислениях которых фигурирует не более четырех независимых потоков данных. Для решения задач с большим числом независимых потоков данных необходимо прибегать к специальным приемам (микропрограммирование, арбитраж, конвейеризация и т.п.), которые существенно усложняют архитектуру СБИС.
Первые два противоречия можно отнести к области технологии изготовления СБИС, а оставшиеся два противоречия - к их функциональному назначению. По мнению специалистов передовых зарубежных фирм, эти противоречия можно разрешить только путем принципиально нового подхода к проектированию и созданию СБИС. Именно поэтому в начале 80-х годов в Японии, США, ФРГ и других странах были начаты работы по созданию трехмерных интегральных схем (ТМ ИС или, как принято в лшературе [69-79,88-92,151], 3D-HC).
На рис. 1.5 представлены две сложившиеся тенденции развития интеграции кремниевых УБИС в период с середины 1990-х гг. вплоть до 2010 г. [84]. График построен для однородных схем - памяти динамических ОЗУ (ДОЗУ) и неоднородных схем - микропроцессоров, на основе данных наиболее обоснованного и сбалансированного прогноза развития мирового микроэлектронного производства и бизнеса [192-193]. В составлении прогноза принимали участие эксперты ведущих фирм США.
Вложимость произвольного графа с п вершинами в трёхмерную область вычислений объёмных ТМИС
Одна из особенностей систолического подхода к организации вычислений заключается том, что, выполняя работу, аналогичную работе программиста, пользователь может самостоятельно спроектировать процессор, реализующий решение имеющейся у него задачи. Для того, чтобы проектируемый процессор оказался тех нологичным в производстве и его характеристики оказались достаточно близкими к заложенным в проекте, необходимо учитывать особенности кремниевой технологии. При разработке принципиальной схемы процессора достаточно учитывать лишь общие принципы физической реализации вычислительных структур.
Известны два подхода к определению физической реализации: трехмерный (без учета требований существующих технологий или с ориентацией на перспективные технологии) [69-73,88-92] и пленарный (с учетом требований, например, ТТЛ-или КМОП-технологий) [15-22]. Относительно первого подхода отметим, что многие из приводимых ниже результатов о планарном размещении вычислительных структур переносятся также на трехмерные физические реализации. Излагаемый в [15] метод получения нижних оценок для произведения времени и памяти, известный как метод сечений, возник в работе А.Н.Колмогорова и Я.М.Барздиня [150] при изучении размещения логических и нейронных сетей в трехмерном пространстве. Однако следует отметить, что приводимые в этой работе ограничения не имеют места, как будет показано далее, для оптических межсоединений.
Под (б?,и)-сетью будем понимать направленный граф с п нумерованными вершинами 1 2,... и dn отмеченными дугами такой, что в каждую вершину входит ровно d дуг, одна из которых помечена буквой хь другая - буквой х2, и т.д. и, наконец, последняя - буквой Xd.
Примерами таких сетей являются логические сети и нейронные сети. Именно по этой причине представляет интерес вопрос о реализации таких сетей в обычном 3-мерном пространстве при условии, что вершины являются шарами, а дуги - трубками с некоторым положительным диаметром. В [150] без существенного ограничения общности (ввиду того, что оценки произведены только с точностью до порядка) авторы ограничились рассмотрением только (2,л)-сетей, которые далее будем называть просто сетями. Будем говорить, что сеть U реализована в 3-мерном пространстве, если: 1) Каждой вершине а из U сопоставлена некоторая точка fa данного пространства (для разных а и bfa и/Ь - разные); эту точку будем называть /точкой; 2) Каждой дуге р = (а, Ь), исходящей из а и входящей в Ь, сопоставлена некоторая непрерывная кривая Кр, соединяющая точки fa nfb; эту кривую будем называть проводником; 3) Расстояние между любыми двумя различными/точками не меньше 1; 4) Расстояние между любыми проводниками, соответствующими неинцендет-ным дугам, не меньше 1; 5) Расстояние между любыми двумя проводниками, соответствующими дугам вида (а,Ь) и (с,а) или (Ь,а) и (с,а), СФЪ соответственно, вне окрестности радиуса 1 ТОЧКИ/И не меньше 1. Пусть R - некоторая реализация сети U в 3-мерном пространстве. Будем говорить, что тело W содержит реализацию R, если все/Игочки и проводники, возникающие при этой реализации, лежат в теле W и находятся от его поверхности на расстоянии, не меньшем 1. Под объемом реализации R будем понимать минимальный объем тел, содержащих данную реализацию R. Под объёмом V(U) сети U будем понимать минимальный объём ее реализаций в 3-мерном пространстве. Будем говорить, что почти все сети обладают некоторым свойством Е, если где S(n) - число всех попарно различных сетей с п вершинами и Е(п) - число тех попарно различных сетей с п вершинами, которые обладают свойством Е. Было показано [150], что для сети XJ(dn), где d 2, объём V(U), занимаемый сетью, равен: где С2 - некоторая константа 0, не зависящая от п. Теорема 2.6 вытекает из более сильного утверждения: Теорема 2.6 . Любая сеть с л вершинами может быть реализована в сфере радиуса cVw, где С - константа, не зависящая от п. Справедливость данной теоремы для произвольных сетей вытекает из того, что любую сеть U с п вершинами ((2,и)-сеть), добавляя не более 2п новых вершин, можно перестроить в сеть U с ограниченным ветвлением. Например, дуги вида рис. 2.3 можно заменить деревом вида рис. 2.4 (угновые вершины). В результате мы получим (2,п )-сеть с ограниченным ветвлением и п Ъп вершинами. Эту сеть можно реализовать в сфере радиуса cV ri. Заметим, что если сеть построена таким образом, что в каждую вершину входит более одной дуги то, объём занимаемый данной сетью в трёхмерном евклидовом пространстве есть величина равная 0(п ), исходя из условий предыдущей теоремы.
Синтез вычислительных устройств на основе использования трехмерных оптических интегральных схем для выполнения групповых арифметических операций в системе счисления в остаточных классах
Процессы контроля, управления, фильтрации сигналов и изображений, алгоритмы машинной графики и многие другие важные применения характеризуются наличием больших массивов информации, которые необходимо обрабатывать в реальном масштабе времени, что предъявляет высокие требования к быстродействию современных универсальных и специализированных ЭВМ.
Один из важных вопросов при разработке архитектуры высокопроизводительных вычислительных систем - выбор и обоснование системы счисления. Основой построения существующих ЭВМ является традиционная элементная база, позволяющая выполнять только бинарные операции в двоичной системе счисления (СС). В тоже время известно, что главным недостатком двоичной СС является наличие "длинных" межразрядных переносов, возникающих при выполнении арифметических операций. Указанные факторы в значительной степени снижают производительность как последовательных, так и параллельных ЭВМ и приводят к необходимости поиска новых технических решений.
Одним из возможных подходов, ведущих к увеличению быстродействия различного класса ЭВМ, является использование для их построения новых элементарных устройств обработки (ЭУО) данных, выполняющих модулярные вычисления, в конечных полях и кольцах [142,143,146,324,325].
Другим фактором роста производительности может служить использование в одной ЭВМ некоторого комплекса СС и организация вычислительного процесса в изменяемой системе счисления в одном процессоре [293-295].
Обозначим через Vb V2 - объемы вводимых и выводимых данных, соответственно, Уз - объем вычислений. Известно, что если Vi+V2 «Уз т0 целесообразно использовать двоичную, а в случае, когда Vi+V2 »V3 двоично-десятичную арифметику. Если же Vi+V2«V3, или Vi«V2«V3, то вопрос о выборе наилучшей СС остается открытым. Ситуация, безусловно, значительно усложняется при наличии на входах и выходах системы операндов, представленных в различных СС.
В общем случае каждый конкретный алгоритм обработки может быть наилучшим образом реализован с применением вполне определенного набора СС, при этом устройство управления должно обеспечить настройку решающего поля на соответствующую последовательность СС. Задача формально сводится к нахождению кратчайшего пути на графе G(U,V), вершинам V которого соответствуют различные СС2 а дугам U - арифметические операции или операции преобразования кодов. Каждой дуге приписывается вес, равный времени преобразования или выполнения операции в даннойСС.
Предложенные способы ускорения позволяют перейти к построению структуры ЭВМ с изменяемой СС, в решающем поле которой содержатся процессорные элементы, способные функционировать в различных СС с ориентацией на массовую обработку чисел [293-295].
Анализ алгоритмов цифровой обработки сигналов (ЦОС) и асимметричных криптографических алгоритмов с открытым ключом показывает, что их ядрами являются групповые операции, такие как скалярное произведение любых двух п-мерных векторов, сумма парных произведений, весовое суммирование, умножение с накоплением и некоторые другие. Из этого следует, что характеристики процессора ЦОС и СКЗИ будут определяться в основном характеристиками устройств, аппаратурно реализующих эти базовые макрооперации. Одним из направлений дальнейшего повышения производительности процессоров цифровой обработки сигналов (ЦОС) является использование систем остаточных классов (СОК). Основу устройств, выполняющих групповые операции в СОК, составляют многооперандные сумматоры.
Выполнение групповых операций в позиционных системах счисления затруднено ввиду чрезвычайной сложности многооперандных арифметических устройств, их большой общей входной/выходной разрядности и проблемой переноса при выполнении операций с числами большой разрядности, что ограничивает применение технологии СБИС (в том числе ПЛИС).
Разработчики ПЛИС для ускорения выполнения математических операций оснащают свои изделия специальными выделенными схемами формирования и передачи переноса. Несмотря на это, последовательный перенос существенно замедляет работу аппаратной части, а использование схемных решений для ускорения переноса чрезмерно усложняет схему и требует для своей реализации слишком много ресурсов кристалла. При использовании СОК эти недостатки во многом могут быть устранены.
Переход в СОК, с другой стороны, может оказаться слишком трудоемкой операцией для ПЛИС. Возможным решением может быть совместное применение ПЛИС и элементов оптоэлектроники, когда стандартное преобразование в СОК из позиционной (двоичной) системы и обратно, а также все непозиционные арифметические вычисления выполняет оптоэлектронная часть аппаратуры, а позиционные вычисления - ПЛИС. В таком тандеме ПЛИС обеспечивает гибкость, а оптоэлектроника - высокую производительность.
Применение арифметики остаточных классов (вычетов) в системах обработки сигналов представляет большой практический интерес с точки зрения возможности реализации параллельных вычислений при решении широкого класса прикладных задач цифровой обработки сигналов (ЦОС) и изображений, кодирования и криптографии, так как все разряды в представлении вычета имеют равный вес. Отпадает необходимость в информации о переносе (из разряда в разряд), так как нет ни младших, ни старших разрядов и, таким образом, арифметические операции реализуются очень быстро: Например,- пусть Р = Pi,P2, . . . ,Рк - множество модулей, элементы которого относительно просты. Единственное представление числа Хе [-N/2,N/2] через вычеты задается К-компонентным вектором X = Хь Хь . .., Хь где
Известны эффективные математические методы вычислений в больших полях и кольцах, например модулярная арифметика в классе вычетов [268-270]. Следует отметить большое прикладное значение использования модулярной системы в теории кодирования и криптографии [278-284]. В настоящее время в создании средств защиты информации (СКЗИ) наблюдается тенденция перехода на новую элементную базу, в первую очередь - на микропроцессоры [282].
В связи с этим изменяется и алгоритмический базис криптографических задач. Появляется необходимость быстро производить вычисления в конечных полях и кольцах большой размерности. Эти изменения касаются как дешифровальных задач, так и задач, возникающих при конструировании и оценке стойкости СКЗИ.
В частности, большие вычисления в конечных полях и кольцах требуются в ряде исследовательских задач синтеза СКЗИ с заданными криптографическими параметрами [312,313]. Причем есть основания предполагать, что со временем доля таких криптографических задач будет увеличиваться [278,283],
Применение системы остаточных классов (СОК) в отличие от двоичной системы счисления дает возможность разделить динамический диапазон вычислений на полностью независимые элементы. При этом вычислительные операции над этими элементами выполняются параллельно. Комбинация вычислений, выполняемых "классическими" систолическими матрицами, с арифметическими операциями над конечными полями и кольцами при надлежащем использовании дает дополнительную свободу при проектировании как однокристальных, так и многокристальных систем.
Алгоритмы свертки и умножения полиномов на основе использования ТМОИС
Цифровая обработка сигналов (ЦОС) и изображений охватывает широкий диапазон математических и алгоритмических методов. Однако в большинстве задач обработки сигналов и изображений преобладают методы преобразований, фильтрации на основе свертки и корреляции, а также базовые методы линейной алгебры.
В задачах ЦОС объектом изучения являются дискретные сигналы и системы. Дискретизированные во времени сигналы возникают либо естественным путем, либо, и это достаточно распространенная ситуация - получаются в результате дискретизации аналоговых (непрерывных по времени) сигналов. В наиболее общей форме операция над дискретной последовательностью выглядит так: последовательность пропускается через некоторую дискретную систему, и в результате на выходе получаем преобразованную последовательность.
Свертку двух последовательностей u(n) и w(n), определяемую как будем обозначать
Если u(n) и w(n) - каузальные последовательности конечной длины N, т.е. n = 0,1,2,..., N-1, то линейная свертка этих последовательностей также каузальна и опр ед еляется выражением N При использовании свертки для цифровой фильтрации u(n) представляет обрабатываемую входную последовательность, a w(n) - импульсную характеристику цифрового фильтра. В общем случае две эти последовательности могут иметь разную длину. Получаемая на выходе последовательность у(п) представляет обработанный сигнал.
Прямое вычисление свертки двух N-членных последовательностей требует порядка N2 арифметических операций. С точки зрения обеспечения вычислительной эффективности для вычисления свертки надо сначала перейти в область преобразований, в которой операции можно выполнить проще, чем во временной области, после чего можно применить обратное преобразование. Для этой цели наиболее часто используется быстрое преобразование Фурье, применение которого позволяет умень-шить порядок вычислительной сложности от 0(N ) до 0(Nlog N).
Решение задач обработки сигналов и изображений в реальном времени связано с созданием-новейших матричных процессоров для таких общих в обработке- сигна лов и изображений функций, как свертка, БПФ, и матричные операции. Большинство методов обработки сигналов и изображений распадается на классы алгоритмов типа свертки, фильтрации, обработки матриц, преобразований. Эти алгоритмы обладают некоторыми общими полезными свойствами (регулярность, рекурсивность и локальный обмен данными) и относятся к классу алгоритмов с локальной связью. С другой стороны, в области цифровой обработки изображений, где требуется обрабатывать многомерные сигналы с частотой дискретизации в сотни мегагерц в реальном масштабе времени, электроника встречает серьезные трудности. Необходима аппаратная реализация наиболее важных алгоритмов ЦОС, которая предполагает создание параллельных структур со многими перестраиваемыми связями. Такие структуры могут быть получены в специализированных оптоэлектронных вычислительных системах. Далее предлагается трехмерная архитектура ОЦВС обработки сигналов, элементной базой которой являются трехмерные интегрально-оптические схемы.
Следует отметить, что базовой операцией базиса алгоритмов цифровой обработки сигналов и изображений является операция умножения вектора на матрицу, которая лежит в основе широкого класса алгоритмов ЦОС: где ап— элемент входного вектора; Ь - элемент матрицы преобразования; ск— элемент вектора-результата. К этой операции сводятся некоторые важные алгоритмы ДОС. Циклическая (круговая) сверткатхъух периодических последовательностей сводится к умножению входного вектора X на теплицеву матрицу Н, элементы которой hkn = hk.n. (Теплицевой называется матрица, элементы которой на каждой диагонали одинаковые, т.е. элементы соседних строк одни и те же со сдвигом на одну позицию.) Корреляция двух периодических последовательностей также сводится к умножению входного вектора X на теплицеву матрицу Н: Цифровой фильтр реализует алгоритм представляющий собой сумму двух сверток. В создании - специализированного - алгоритмического обеспечения решения задач ЦОС выделяется несколько подходов: вывод принципиально новых, более производительных алгоритмов; создание комплекса алгоритмов для различных классов задач; разработка ориентированных алгоритмов с учетом элементной базы, технологии изготовления устройств и др. В настоящее время технологические успехи в области интегрально-оптических БИС и новые подходы в разработках архитектуры вычислительных систем позволили объединить вышеперечисленные подходы в возможности реализации базиса высокопроизводительных алгоритмов ЦОС в объеме отдельных кристаллов - трехмерных СБИС. В этом параграфе, на примере одной задачи - свертки полиномов, покажем, что увеличение размерности вычислителя неизменно ведет к повышению производительности. Заметим, что свертку можно интерпретировать и как частный случай операции умножения вектора на матрицу. Реализация устройств свертки или цифровых фильтров является одной из перспективных областей применения ССОК в ЦОС. На рис. 4.11, б) представлена структура отдельной систолической ячейки. Ячейка содержит два внутренних 1-битных регистра t и р, три 1-битных ввода Ь,, а; и СІ, а также два 1-битных вывода ао и CQ.
