ISBN 5-256-00179-5.
Книга специалистов из многих стран является введением в круг разнообразных проблем, возникающих при создании высокопроизводительных систем обработки информации. Рассмотрены типичные задачи обработки сигналов, иллюстрирующие возможности организации параллельных вычислений. Проведен обзор перспективных разработок специализированных процессоров на основе применения сверхбольших интегральных микросхем: в виде систолической матрицы и со связью через систему программируемых коммутаторов. Приведены примеры различного применения параллельных вычислительных систем и их конкретной реализации.
Для инженерно-технических работников.
1402030000-183 ,„ „„
ZT/1 11 Q 1 1
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
После нескольких десятилетий развития теории и техники радиосистем в среде радиоинженеров созрело понимание того, что эти системы состоят в основном из двух частей: датчика сигналов и вычислительного устройства, осуществляющего обработку сигналов. Все остальное по сути предназначено для сопряжения этих частей и вывода информации. Первые радиосистемы выполняли скромные задачи. Поэтому их вычислительная часть была проста и обработка сигналов осуществлялась аналоговыми устройствами. Разрабатываемые в настоящее время радиосистемы будут выполнять сложные задачи, решение которых под силу только современным цифровым вычислительным машинам.
В связи с этим радиоинженеры - разработчики современных радиосистем оказались в ситуации, когда им необходимо быть и специалистами по вычислительной технике, и программистами, и математиками-прикладниками. К сожалению, эта ситуация осложняется острым дефицитом научно-технической литературы по вопросам применения средств вычислительной техники в современных радиосистемах.
Предлагаемая книга, являющаяся одной из первых в указанной области, представляет собой сборник статей известных зарубежных (в основном — американских) специалистов, написанных в форме научно-технических отчетов. Она является по существу введением в круг разнородных проблем, возникающих перед создателями современных высокопроизводительных систем обработки информации. Технической основой решения этих проблем являются новые возможности, предоставляемые технологией сверхбольших интегральных схем. Но не технологии, а математическим и алгоритмическим аспектам создания вычислительных систем обработки сигналов посвящена эта книга.
Здесь нет необходимости характеризовать ее содержание, которое кратко изложено в предисловии редакторов к книге и во введениях к отдельным ее частям. Необходимо только отметить, что широкий круг рассмотренных вопросов и "отчетный" стиль отдельных глав не способствуют легкому чтению. Однако этот недостаток является обратной стороной главных достоинств — актуальности рассматриваемых проблем и новизны предлагаемых решений. Активный исследователь может найти в книге много новых идей, которые окажут стимулирующее влияние на его деятельность. Книга полезна также студентам старших курсов радиотехнических специальностей и инженерам, желающим повысить свою квалификацию в области обработки сигналов.
Переводчики приложили немало усилий по согласованию английских и РУССКИХ терминов. Предисловие к книге, введение к части I и гл. 1, 2, 3, 6 пе-ревелК.Т.Михайлуца; гл. 4, 5, 19 - В. Г. Челпанов; введение к части II, главы 7-16, 20, 26 - В. В. Никонов; введение к части III, гл. 17, 18, 21-25 -ш- L. Малофеев.
СОДЕРЖАНИЕ
Предисловие редактора перевода..................................5
Предисловие............................................. . .6
Часть I. Обработка сигналов: теория и алгоритмы........................8
1.Обработка сигналов в эпоху СБИС (Т. Кайлат)......................10
1.1. Введение............................................10
1.2. Некоторые алгоритмы для теплицевых матриц....................12
1.3. Распространение результатов разд. 1.2 на матрицы, близкие к теплицевым. . . 20
1.4. Заключение..........................................25
Список литературы.....................................25
2.Применение параллельных матричных процессоров для обработки сигналов
(X. Уайтхаус, Дж. Спейзер, К. Бромли)...........................28
2.1. Введение.............................^..............28
2.2. Задачи метода наименьших квадратов......... . .*...............31
2.3. Встречно-поточный процессор...............................34
2.4. Заключение..........................................43
Список литературы.....................................44
3.Спектральный анализ: от обычных методов к методам с высокой разрешающей способностью (С. Гун, Д. Рао, К. Арун)...........................45
3.1. Введение............................................45
3.2. Обычные методы спектрального анализа [5].....................46
3.3. Методы, основанные на моделях исследуемых процессов..............48
3.4. Моделирование сигналов на основе сингулярного разложения...........57
3.5. Заключение..........................................60
Список литературы.....................................61
4.Спектральный анализ с высокой разрешающей способностью. Подчеркивание основных мод (Н. Аузпи)....................................64
4.1. Введение............................................64
4.2. Модель сигнала........................................65
4.3. Спектральный анализ....................................68
4.4. Разрешающая способность.................................73
4.5. Вычисление модифицированных спектральных оценок...............74
4.6. Оценивание дальности с высокой разрешающей способностью...........77
4.7. Заключение..........................................84
Список литературы.....................................84
5.Принципы обработки сигналов антенных решеток, обеспечивающие высокую разрешающую способность (Г. Бьенвеню, А. Мермо)...................86
5.1. Введение............................................86
5.2. Основные принципы методов, обеспечивающих высокую разрешающую способность..........................................88
5.3. Обобщения методов, обеспечивающих высокую разрешающую способность . . 92
5.4. Реализация метода высокой разрешающей способности..............102
5.5. Заключение.........................................107
Список литературы......,.............................107
6. Замечания по поводу вычисления собственных значений матриц (Б. Парлетт) . . 108
6.1. Введение...........................................108
6.2. Приведение к стандартному виду............................109
6.3. Возможности современных программ.........................110
6.4. Положение дел при решении проблем, приводящих к большим матрицам . . 112
6.5. Методы анализа малых матриц.............................113
6.6. Обратная итерация.....................................116
6.7. О методах решения проблемы собственных значений больших симметричных матриц............................................117
6.8. Метод итерирования подпространства для решения уравнения (К - ЛМ)2 = 0. 118
6.9. Алгоритм Ланцоша [ 12, гл. 13].............................119
6.10. Сингулярные значения (для малых матриц)....................120
6.11. Сингулярные значения (для больших матриц)...................122
6.12. О проблеме собственных значений для больших несимметричных матриц. . 122
6.13. Вопросы на будущее...................................122
Список литературы....................................123
Часть II. Параллельные матричные процессоры: архитектура и языки..........126
7.СБИС-обработка сигналов: от трансверсальной фильтрации к параллельной обработке (С. Гун).......................................131
7.1. Введение...........................................131
7.2. Матричные СБИС-процессоры для обработки сигналов..............133
7.3. От анализа алгоритмов к разработке архитектуры.................135
7.4. Волновая матричная обработка.............................141
7.5. Программное обеспечение и средства автоматизации проектирования для разработки СБИС-структур...............................149
7.6. Заключение.........................................155
Список литературы....................................156
8.Специализированные СБИС-архитектуры: общее суждение и анализ опыта
(А. Фишер, С. Кунг)......................................157
8.1. Введение...........................................157
8.2. Слагаемые успеха.....................................158
. 8.3. Программируемые систологические кристаллы: анализ опыта..........161
8.4. Заключение.........................................170
Список литературы....................................171
9.Роль высокопараллельных вычислителей с перестраиваемой конфигурацией в обработке сигналов (Л. Снайдер).............................175
9.1. Введение...........................................175
9.2. ВППК-процессор......................................176
9.3. Универсальный сигнальный процессор на основе ВППК-процессора.......178
9.4. Некоторые проблемы реализации...........................180
9.5. Заключение.........................................181
Список литературы....................................182
10.Увеличение доли выхода годных СБИС за счет обеспечения свойства отказоустойчивости систолических структур (Р. Кун)..................... 182
10.1. Введение.......................................... 182
'10.2. Структурная отказоустойчивость........................... 184
10.3. Анализ выхода годных................................. 185
10.4. Заключение ........................................ 188
Список литературы.................................... 188
468
И.Декомпозиция больших матриц для ограниченных систолических структур
(Д. Хеллер)...........................................189
11.1. Введение...........................................189
11.2. Аддитивное разбиение..................................191
11.3. QR-разложение......................................193
И.4. Разбиения.........................................200
11.5. Разреженные матрицы..................................201
Список литературы....................................202
12. Спецификация параллельных алгоритмов в терминах аппликативного пространства данных (А. Кремерс, Т. Хиббард)........................201
12.1. Введение...........................................203
12.2. Пространство данных и запись алгоритмов.....................205
12.3. Глобальная синхронизация...............................209
12.4. Локальная синхронизация...............................214
Приложение........................................218
Список литературы...................................223
13. Параллельные алгоритмы в терминах пространственно-временных рекуррентных уравнений (М. Чен, К. Рид)............................... 224
13.1. Введение..........................................224
13.2. Модель вычислений...................................228
13.3. Язык Кристал.......................................229
13.4. Поведение алгоритма..................................231
13.5. Простой пример пространственно-временного алгоритма............231
13.6. Пространственно-временные алгоритмы для параллельных систем......233
13.7. Заключение........................................240
Список литературы...................................240
14. Обзор способов представления сигналов в программах (Г. Копец).........241
14.1. Введение..........................................241
14.2. Требования к способу представления сигналов..................243
14.3. Потоки и языки блок-схем..............................244
14.4. Массивы и их обработка................................249
14.5. Язык представления сигналов.............................250
Заключение........................................255
Список литературы...................................255
15. Параллельный и конвейерный способы реализации алгоритмов обработки сигналов на СБИС (П.Девильд,Е.Депреттьер,Р.Нута)................257
15.1. Введение..........................................257
15.2. Параллелизм и конвейерность.............................258
15.3. Параллельно и конвейерные ортогональные фильтры..............263
15.4. Модуль алгоритма Cordic с двойным конвейером.................269
15.5. Заключение........................................272
Список литературы...................................273
16. Архитектура арифметических устройств для цифровых процессоров сигналов на СБИС (X. Ахмед)...................................274
16.1. Введение..........................................274
16.2. Взаимозависимость арифметических операций и операций управления . . . 275
16.3. Основные операции, используемые при обработке сигналов..........277
16.4. Архитектуры устройств быстрого умножения...................279
16.5. Алгоритм Cordic.....................................287
16.6 Метод последовательных приближений.......................294
469
16.7. Сравнение арифметических устройств........................295
16.8. Заключение........................................298
Список литературы...................................299
Часть III. Применение параллельных матричных процессоров...............302
17. Применение параллельных систем на СБИС при двумерной обработке сиг-
налов (Г. Надд, Дж. Наш)..................................304
17.1. Введение..........................................304
17.2.Требования к производительности при анализе изображений..........305
17.3. Архитектура для анализа изображений.......................308
17.4. Архитектура параллельных СБИС..........................310
Список литературы...................................320
18. Кристаллы СБИС-процессоров для матричной обработки (Р. Вуб, Г. Камер,
Э. Гринвуд.Д. Харрисон)................................321
18.1. Введение..........................................321
18.2. Обоснование выбора матричного процессора...................321
18.3. Характеристики матричного процессора......................323
18.4. Основные характеристики арифметического устройства обработки.....324
18.5. Кристалл арифметического устройства обработки................325
18.6. Выбор функций кристалла...............................336
18.7. Разработка СБИС....................................337
18.8. Заключение........................................343
Список литературы...................................344
19. Цифровая фильтрация в частотной области при использовании СБИС (Е. Шварц-ландер мл., Г. Холлнор)....................................345
19.1. Введение..........................................345
19.2. Требования к фильтру.................................346
19.3. Разработка вычислительных блоков.........................348
19.4. Полная структура фильтра...............................353
Список литературы...................................355
20. Параллельная СБИС-архитектура цифрового фильтра, использующего теоретико-числовые преобразования (Т. Труонг, И. Рид, К. Йе, Г. Чанг.Х.Шао) .... 356
20.1. Введение..........................................356
• 20.2. Числовое преобразование Ферма...........................357
20.3. Конвейерная структура для 128-точечного ЧПФ..................360
20.4. Архитектура цифрового фильтра с произвольной длиной преобразования ЧПФ.............................................363
20.5. Заключение........................................367
Список литературы...................................368
!1. Применение систолических матриц в рекурсивных фильтрах (Г. Травассос) . . . 369
21.1. Введение..........................................369
21.2. Формализация задачи..................................370
21.3. Параллельная калмановская фильтрация..............•........372
21.4. Некоторые вопросы проектирования процессора.................376
21.5. Заключение........................................380
Список литературы......................•.............381
2..Систолические линейные алгебраические машины (Р. Шрайбер, Ф. Кьюкес) .... 382
22.1. Введение..........................................382
22.2. Процессор QU-разложения...............................383
22.3.Матричный процессор для обратного хода.............'........391
70
22.4. Комплексное QU-разложение.............................392
22.5. Реализация СБИС....................................393
Список литературы...................................396
23. Многопроцессорные параллельные структуры, конвейеры и пирамиды для восприятия образов (Л. Ур)..................................397
23.1. Введение: значительное увеличение мощности и производительности при использовании СБИС.................................397
23.2. Традиционные однопроцессорные последовательные ЭВМ и многопроцес-
сорные сети.......................................398
23.3. Конвейерные системы компьютеров (или процессоров)............398
23.4. Матричные структуры из очень большого числа простых процессоров . . . 399
23.5. Множество вариантов более общих структур сетей...............404
23.6. Алгоритмически структурированные многопроцессорные сети........405
23.7. Архитектура аппаратных средств пирамидальных матричных многопроцессорных систем......................................405
23.8. Последовательное объединение матриц для построения пирамиды.....406
23.9. Составление пирамид соединением в матрицу каждого из ярусов дерева . 406
23.10. Различные способы видоизменения пирамид...................407
23.11. Реализация пирамид..................................409
23.12. Архитектура проблемно-ориентированных систем для преобразования потоков данных.....................................409
23.13. Соответствие матричных и пирамидальных процессоров технологии СБИС.410
23.14. Заключение.......................................411
Список литературы...................................412
24. Параллельные алгоритмы для анализа изображений (А.Розенфелд)........414
24.1. Введение..........................................414
24.2. Обработка на уровне элементов растра.......................415
24.3. Обработка на уровне регионов............................419
24.4. Заключение........................................423
Список литературы...................................424
25. СБИС-архитектуры для анализа формы и управление базой данных изображения (К. Фу, К. Хуанг, Б.Ва).................................425
25.1. Введение..........................................425
25.2. СБИС и машинная графика..............................425
25.3. Процессоры на СБИС для обработки изображений................427
25.4. Машины баз данных изображения..........................434
25.5. Распределение ресурсов.................................436
25.6. Заключение........................................439
Список литературы..........................'.........440
26. Обработка сигналов при высокой скорости поступления данных: использование систем с параллельной архитектурой и высокими тактовыми частотами
(Б. Гилберт, Т. Кинтер, Д. Шваб, Б. Hay сед, Л. Крюгер, В. ВанНурден, Р. Зукка) . . 441
26.1. Введение.........................................441
26.2. Примеры задач с большим объемом вычислений, возникшие в биомеди-
цине............................................443
26.3. Архитектурные решения, направленные на увеличение пропускной способности процессора..................................446
26.4.. Почему решение задач большой вычислительной сложности не всегда может быть достигнуто архитектурным решением: анализ опыта........447
26.5. Методы увеличения скорости обработки, основанные на использовании
более совершенных технологий...........................451
471
26-6. Использование an
456 - -•—УРЫ "0^еСГаНИв:Треб^е дая разрабГ 458
"переведеннь™ «* русски язьж.........::::::..........«9
............. ........462
.............4Л1
. 465
Цена: 300руб.
