УД К 681.3 Самофалов К. Г., Луцкий Г. М. Основы теории многоуровневых конвейерных вычислительных систем. — Москва: Радио и связь, 1989. — 272- с • ил — ISBN 5-256-00302-Х. Рассмотрены концептуальные, структурные и алгоритмические основы повы- шения эффективного быстродействия параллельных вычислительных систем, из- ложены принципы и методы построения высокопроизводительных конвейерных вычислительных средств с динамической организацией вычислений. Основное внимание уделено структурным и алгоритмическим методам векто- ризации вычислительных процессов, определяющих возможность параллельной интерпретации последовательных программ, представленных в объектном коде вычислительной системы. При этом основой алгоритмических методов является динамический (неавтономный) режим вычислений, а структурных—конвейерный метод обработки информации. Показана конструктивность предложенных методов с точки зрения наращи- вания эффективной производительности вычислительных систем. При этом преж- де всего выделяются многомерные конвейерные организации как эффективное средство для интенсификации конвейерной обработки. Кроме того, большое вни- мание уделено вопросам унификации вычислений на основе введения в машин- ный язык обобщенных вычислительных схем и процедур, которые позволяют значительно повысить информационную емкость команд и соответственно умень- шить плотность потоков команд. Вопросы реализации предложенных конвейерных средств вычислительной тех- ники тесно увязаны с требованиями технологии построения БИС, СБИС. На ос- нове предложенных методов рассмотрены эффективные алгоритмы решения за- дач матричной арифметики, линейной алгебры и спектрально-корреляционного анализа, а также способы их реализации. Для научных работников в области вычислительной техники, может бьть ре- комендована инженерам. Табл. 8. Ил. 98. Библ. 128 назв. Рецензент: д-р техн. наук, профессор В. Г. Хорошевский Редакция литературы по вычислительной технике 2404010000-150 С —————————— 61—89 046(01 )-89 ISBN 5-256-00302-Х © Издательство <Радио и связь», 1989 ПРЕДИСЛОВИЕ В настоящее время возможности дальнейшего наращивания про- изводительности средств вычислительной техники в рамках последо- вательных принципов обработки информации считаются практически исчерпанными, что обусловлено в основном конечной скоростью рас- пространения сигналов. Поиск решений проблемы повышения произ- водительности идет в направлении развития принципов параллельной обработки информации. Однако и при использовании этих принципов возникает множество проблем, которые прежде всего связаны с эф- фективным использованием потенциальных возможностей параллель- ных вычислительных систем. Эти проблемы в основном обусловлены тем, что при разработке высокопроизводительных вычислительных систем качественно новый подход к обработке информации в боль- шинстве случаев реализуется путем количественных изменений, а именно, объединением в некоторую конфигурацию процессоров или процессорных элементов, предназначенных для последовательной об- работки информации. Отсюда возникают проблемные задачи распарал- леливания или векторизации решаемых задач, распределения ресур- сов, коммутации, взаимодействия, разрешения конфликтных ситуа- ций и множество других. С увеличением степени распараллеливания данные проблемы усложняются и становятся трудно разрешимыми. Это приводит к тому, что потенциальные возможности параллельных средств вычислительной техники при решении конкретных задач ока- зываются недоиспользованными. При этом эффективная производи- тельность этих средств обычно существенно уступает их номинальной производительности. В книге рассмотрен принципиально новый подход к повышению эффективной производительности параллельных средств вычисли- тельной техники. При его реализации допускается возможность па- раллельной интерпретации последовательных программ, представ- ленных в объектном коде вычислительной системы. Иными словами, в книге вместо вопросов векторизации задач решается задача векто- ризации вычислительных процессов. При этом основой данного под- хода являются неавтономный (динамический) режим вычислений и структурная организация конвейерных средств вычислительной тех- ники, отвечающих требованиям реализации конвейерного метода об- работки информации в новой интерпретации, предложенной авторами. В соответствии с рассмотренным подходом в книге ставятся и ре- шаются и другие важнейшие проблемные задачи, к которым в первую СПИСОК ЛИТЕРАТУРЫ 1. Айлиф Дж. Принципы построения базовой машины: Пер. с англ. — М.: Мир. 1973. — 120с. 2. Алгоритмы, математическое обеспечение и архитектура многопроцессор- ных вычислительных систем/Под общ. ред. А. П. Ершова. — М.: Наука, 1982. 3. Алексенко А. Г. Основы микросхемотехники. — М.: Сов. радио, 1977. 4. Алексенко А. Г., Шагурин И. И. Микросхемотехника. — М.: Радио и связь, 1982. — 414 с. 5. А. с. 656059 СССР, MKИЗG06F7/52. Арифметическое устройство/Г. М. Луц- кий. С. В. Дрофа, В. Н. Чинок. — Опубл. 1979, Бюл. № 13. 6. А. с. 1254470 СССР, МКИ3 G06F7/49. Конвейерное операционное устрой- ство/Г. М. Луцкий, Т. А. Блинова, С. В. Дрофа. — Опубл. 1986, Бюл. № 32. 7. А. с. 1137460 СССР, МКИ3 G06F7/49. Конвейерный сумматор /Г. М. Луц- кий, Т. А. Блинова, А. В. Корочкин. — Опубл. 1985, Бюл. № 4. 8. А. с. 849205 СССР, МКИ8 G06F7/38. Конвейерное устройство для выпол- нения арифметических операций над множеством чисел /Г. М. Луцкий, М. А. Вилкул, А. Н. Долголенко. —Опубл. 1981, Бюл. №27. 9. А. с. 1072039 СССР, МКИ3 G06F7/49. Конвейерное устройство для вы- числения сумм произведений/Г. М. Луцкий, В. В. Коваленко, А. Н. Долго- ленко, А. В. Корочкин, Т. А. Блинова. — Опубл. 1984, Бюл. № 5. 10. А. с. 972503 СССР, МКИ3 G06F7/544. Конвейерное устройство для вычис- ления цепных дробей/Г. М. Луцкий, А. В. Корочкин, А. Н. Долголенко, О. И. Пенчев. —Опубл. 1982, Бюл. №41. 11. А. с. 662935 СССР, МКИ3 G06F7/38. Конвейерное устройство для одно- временного выполнения арифметических операций над множеством п-разрядных чисел/Г. М. Луцкий, А. Н. Долголенко, Л. Н. Корчинская. — Опубл. 1979, Бюл. № 28. 12. А. с. 1111206 СССР, МКИ3 G11C29/00. Оперативное запоминающее уст- ройство с коррекцией информации/А. Г. Засыпкин, Г. М. Луцкий, А. Н. Дол- голенко, В. Д. Трунов. — Опубл. 1984, Бюл. № 32. 13. А. с. 1056184 СССР, МКИ3 Q06F7/52. Устройство дл» вычисления сумм произведений/В. П. Денисенко, Г. М. Луцкий, А. Н. Долголенко, А. Г. Засып- кин. — Опубл. 1983, Бюл. № 43. 14. А. с. 905814 СССР, МКИ3 Q06F7/52. Устройство для вычисления сумм 264 произведений/Г. М. Луцкий, В. А. Корочкин, Ю. А. Кулаков, А. Н. Долго- ленко. — Опубл. 1982, Бюл. № 6. 15. А. с. 1166101 СССР, МКИ3 G06F7/52. Устройство для вычисления сумм произведений/Г. М. Луцкий, Ю. А. Кулаков, А. Н. Долголенко, В. Н. По- рев. — Опубл. 1985, Бюл. № 25. 16. А. с. 479111 СССР, МКИ3 G06F7/52. Устройство для одновременного вы- полнения арифметических операций над множеством чисел/Г. М. Луцкий, К. Г. Самофалов, Б. П. Хижинский. — Опубл. 1975, Бюл. № 28. 17. А. с. 558276 СССР, МКИ3 G06F7/385. Устройство для одновременного выполнения операций сложения над множеством чисел/Г. М. Луцкий, Ю. А. Ку- лаков, А. Н. Долголенко. — Опубл. 1977, Бюл. № 18. 18. А. с. 1182512 СССР, МКИ3 G06F7/50. Устройство для сложения после- довательности чисел с плавающей запятой/Г. М. Луцкий, В. П. Денисенко, А. Н. Долголенко, А. Г. Засыпкин, Е. К. Кошкин. — Опубл. 1985, Бюл. № 36. 19. Аристов В. В. Интегро-алгоритмические вычисления. — Киев: Наукова думка. 1980. — 192 с. 20. Байков В. Д., Смолов В. Б. Специализированные процессоры: Итерацион- ные алгоритмы и структуры. — М.: Радио и связь, 1985. — 288 с. 21. Баррон И., Кэвил П., Май Д. и др. Транспьютер с быстродействием 5 млн. операций/с и болееУУЭлектроника. —1983. — № 23. — С. 26—35. 22. Бахтиаров Г. Д., Знняков Н. Л. Алгоритм Волдера и его применение в вычислительной технике и цифровой обработке сигналовУУЗарубежная радио- электроника. — 1983. — №. 3. — С. 3—23. 23. Березин А. С., Мочалкина О. Р. Технология и конструирование инте- гральных микросхем. — М.: Радио и связь, 1983. — 232 с. 24. Бессалах X., Луцкий Г. М. Алгоритмы быстрого преобразования Фурье и их реализация на рекурсивных конвейерных процессорахУУВестн. КПИ. Сер. автоматики и электроприборостроения. — 1981. — № 18. — С. 55—59. 25. Брусенцов Н. П. Усовершенствованная запись формулУУЖурн. вычис- лительной математики и математической физики. — 1972. — № 12. —С. 820— 822. 26. Валиев К- А., Кармазннский А. Н., Королев М. А. Цифровые интеграль- ные схемы на МДП — транзисторах. — М.: Сов. радио, 1977. — 405 с. 27. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Методы символьной муль- тиобработки.—Киев: Наукова думка, 1980.—252с. 28. Головкин Б. А. Параллельные вычислительные системы. — М.: Наука, 1980. — 519 с. 29. Деннис Дж. Б., Фоссин Дж. Б., Линдерман Дж. П. Схемы потока данных/У Теория программирования: Пер. с англ. Ч. 2/ВЦ СО АН СССР. Новосибирск, 1972. — С. 7—43. 30. Дмитриев Ю. К., Хорошевский В. Г. Вычислительные системы из ми- ни-ЭВМУПод ред. Э. В. Евреинова. — М.: Радио и связь, 1982. —304с. 31. Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислитель- ные системы высокой производительности. — Новосибирск: Наука, 1966. 32. Зарубежные интегральные микросхемы широкого примененияУА. А. Чер- нышев, Ю. М. Кутыркин, А. В. Нефедов, А. М. Савченко. — М.: Энергоатом- издат, 1984. — 145 с. 33. Карцев М. А. Арифметика цифровых машин. — М.: Наука, 1969. — 576 с. 34. Карцев А. М., Брик В. А. Вычислительные системы и синхронная ариф- метика. — М.: Радио и связь. 1981. — 360 с. 35. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгорит- мы: Пер. с англ. — М.: Мир, 1976. — 735 с. 36. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы: Пер. с англ. — М.: Мир, 1977. — 723 с. 37. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. — М.: Наука, 1975. — 360 с. 265 38. Корочкии А. В., Коваленко В. В.. Луцкнй Г. М. Вычисление арифмети- ческих выражений в конвейерных ЭВМУУВестн. КПИ. Сер. автоматики и элеи- троприборостроения. — 1982 — № 19. — С. 130—133. 39. Кулаков Ю. А., Луцкий Г. М. Вопросы организации внутренней струк- туры памяти в конвейерной ЦВМУУОднородные вычислительные и интегрирую- щие структуры/ТРТИ — Таганрог, 1975. — Вып. 4. — С. 32—46. 40. Кухарчук А. Г., Луцкий Г. М. Некоторые вопросы проектирования логи- ческих структур на интегральных схемахУУУправляющие машины и системы. — 1968. — Вып. 3. — С. 18—27. 41. Кухарчук А. Г., Луцкий Г. М., Реутов Г. В. Конвейерный принцип обра- ботки информации.//Кибернетика. — 1968. — № 6. — С. 43—49. 42. Луцкий Г. М. Вопросы эффективного использования аппаратуры кон- вейерных устройствУ/Конструирование и внедрение новых средств вычисли- тельной техники/Ин-т кибернетики АН УССР — Киев, 1971. —Т. 2. — С. 40 - 65. 43. Луцкий Г. М. Выполнение операции деления в операционном устройстве, работающем по принципу конвейера. //Управляющие машины и системы. — 1969. — Вып. 2. — С. 65—78. 44. Луцкий Г. М. Вычисление элементарных функций в неавтономном режи- ме вычисленийУУРаспараллеливание обработки информации. Ч. 2/ФМИ АН УССР. — Львов, 1985. — С. 75. 45. Луцкий Г. М. Классификация совмещений, реализуемых с помощью кон- вейерных преобразователей информацииУУВестн. КПИ. Сер. автоматики и элек- троприборостроения. — 1975. — № 12. — С. 3—5. 46. Луцкий Г. М. Конвейерно-циклический метод обработки информации// Тез. докл. Всесоюз. совещ. «Конвейерные вычислительные системы»/КПИ. — Ки- ев, 1985. — С. 6—8. 47. Луцкий Г. М. Конвейерный процессор для параллельной обработки по- токов командУУВестн. КПИ. Сер. автоматики и электроприборостроения. — 1978. — № 5. — С. 28—30. 48. Луцкий Г. М. Концепция структурной организации эффективных ВС конвейерного типаУУРаспараллеливание обработки информации. Ч.З./ФМИ АН УССР. — Львов, 1983. — С. 11—12. 49. Луцкнй Г. М. Методы выполнения операции умножения в операционном устройстве, работающем по принципу конвейераУУУправляющие машины и сис- темы. — 1969. — Вып. 2. — С. 48—64. 50. Луцкий Г. М. Основы теории вычислений в избыточных системах счисле- нияУУТез. докл. Всесоюз. совещ. «Конвейерные вычислительные системы»У КПИ. — Киев, 1985. — С. 15—18. 51. Луцкий Г. М. Особенности выполнения типовых элементарных операций над словами в конвейерных функциональных блокахУУУправляющие машины и системы. — 1969. — Вып. 4. — С. 55—71. 52. Луцкнй Г. М. Структурная организация многомерных конвейерно-цикли- ческих вычислительных средстаУУРаспараллеливание обработки информации. Ч.2УФМИ АН УССР. — Львов, 1985. — С. 76. 53. Луцкий Г. М., Бессалах X. Анализ подходов к реализации алгоритмов быстрого преобразования ФурьеУУВестн. КПИ. Сер. автоматики и электропри- боростроения. — 1980. — № 17. — С. 42—44. 54. Луцкий Г. М., Долголенко А. Н., Дрофа С. В. Способы выполнения опе- раций с плавающей запятой в конвейерных вычислительных системах УУВестн. КПИ. Сер. автоматики и электроприборостроения. 1983. — № 12. — С. 53—56. 55. Луцкий Г. М., Корочкнн А. В. Алгоритмы деления в полуавтономном режиме вычисленийУУЭлектронное моделирование. — 1982. — № 5. — С. 9—15, 56. Луцкий Г. М., Кулаков Ю. А., Русанова О. В. Повышение эффективнос- ти выполнения линейных программ в конвейерных вычислительных стистемах/У Параллельное программирование и высокопроизводительные системы. — Киев: Наукова думка, 1982. Ч. 3. — С. 45—48. 266 57. Луцкий Г. М., Лекса И., Рукованскнй И. Методика выбора минимального набора научно-технических задач для оценки эффективной производительности вычислительных систем УУТез. докл. Всесоюз. совещ. «Конвейерные вычисли- тельные системы»УКПИ. — Киев, 1985. — С. 23, 24. 58. Луцкий Г. М., Пенчев О. И. Вычисление элементарных функций методом «цифра за цифрой» в избыточных системах счисления. — Препринт. — Киев, 1983. — 30 с. — (Ин-т кибернетики АН УССР, № 83—22). 59. Луцкнй Г. Н., Пенчев О. И. Методология вычислений в знакоразрядных системах счисленияУУГибридные вычислительные машины и комплексы. — Ки- ев: Наукова думка, 1983. — Вып. 6. —С. 3—12. 60. Луцкий Г. М., Пенчев О. И. Об одной теореме машинной арифметики с фиксированной запятой в избыточной двоичной квазиканонической системе счисленияУУКибернетика. — 1983. — № 6. — С. 50—56. 61. Луцкий Г. М., Пенчев О. И. Реализация итерационных методов вычис- лений в конвейерных ЭВМУУВестн. КПИ. Сер. автоматики и электроприборо- строения. — 1982. — № 19. — С. 92—95. 62. Луцкнй Г. М., Романовский А. А., Кулаков Ю. А. Вопросы реализации матрично-полиномиальных выражений в вычислительных системах с конвейер- ным принципом обработки информации. — Препринт. — Киев, 1979. — 33 с. — (Ин-т кибернетики АН УССР, № 79—76). 63. Луцкнй Г. М., Самофалов К- Г., Хнжинский Б. П. Аппаратный метод вы- полнения операции вычисления многочленаУУУправляющие системы и машины. — 1974. — № 2. — С. 73—76. 64. Луцкий Г. М., Самофалов К. Г., Хижинский Б. П. Принципы выполнения операций вычисления функций в конвейерных преобразователях информацииУУ Однородные вычислительные и интегрирующие структурыУТРТИ. — Таганрог, 1976. — Вып. 6. — С. 6—13. 65. Луцкий Г. М., Хижинскнй Б. П. Способ вычисления многочленов с по- мощью конвейерных преобразователей информацииУУОднородные вычисли- тельные и интегрирующие структурыУТРТИ. — Таганрог, 1976. — Вып. 6. 66. Луцкий Г. М., Януков К. И. Специализированное конвейерное устройство на криотронахУУУправляющие системы и машины. — 1977. — № 1. 67. Макроконвейерные вычисления функций над структурами данных / В. М. Глушков, Ю. В. Капитонова, А. А. Летичевский, С. П. ГорлачУУКиберне- тика. — 1981. — № 4. — С. 13—21. 68. Мануэль Т. Усовершенствованные параллельные архитектуры как способ ускорения вычисленийУУЭлектроника. — 1983. — № 12. — С. 25—39. 69. Михалевич В. С., Кукса А. И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. — М.: Нау- ка, 1983. — 208 с. 70. Нагорный Л. Я. Методы распараллеливания систем управлений большой размерности для решения их на многопроцессорных структурахУУЭлектронное моделирование. — 1980. — № 1. — С. 28—32. 71. Ниссен К. Методология и средства иерархического проектирования СБИСУУТИИЭР. — 1983. — № 1. — С. 81-94. 72. Оранский А. М. Аппаратные методы в цифровой вычислительной техни- ке. — Минск: БГУ, 1977. — 208 с. 73. Основы моделирования сложных системУПод ред. И. В. Кузьмина. — Киев: Виша школа, 1981. —360с. 74. Повышение эффективности выполнения линейных программ в конвейер- ных вычислительных системахУК. Г. Самофалов, Г. М. Луцкий, Ю. А. Кулаков, О. В. РусановаУУКибернетика. — 1985. — № 6. — С. 122—124. 75. Прангишвили И. В. Архитектурные концепции высокопроизводительных параллельных вычислительных систем 80-х годовУУВопросы кибернетики: мно- гопроцессорные вычислительные системы с перестраиваемой структурой (архи- тектура, структура, применения). — М., 1978, —С. 3—14. 76. Прангишвилн И. В., Внленкин С. Я., Медведев И. Л. Параллельные вы- числительные системы с общим управлением. — М.: Энергоатомиздат, 1983. — 312 с. 267 77. Прангишвили И. В., Стецюра Г. Г. Современное состояние проблемы соз- дания ЭВМ с нетрадиционной структурой и архитектурой, управляемых потоком данных/УЭлектронная промышленность. — 1981. — № 1. — С. 36—48. 78. Принципы организации конвейерной вычислительной системы с разви- тым внутренним языком/Г. М. Луцкий, И. Д. Бутомо, В. П. Котляров, К. Г. Са- мофалов/Управляющие системы и машины. — Киев, 1979. — № 1. —С. 39—47. 79. Пухов Г. Е., Бардаченко В. Ф., Королев Ю. В. Вычислительные устрой- ства на скаляторах. — Киев: Техника, 1983. — 145 с. 80. Рабинович 3. Л., Раманаускас В. А. Типовые операции в вычислительных машинах. — Киев: Техника, 1980. — 264 с. 81. Результаты двух лет работы компании TRW по созданию ИС с 1-мкм раз- мерами элементов/УЭлектроника. — 1983. — № 23. — С. 5, 6. 82. Рейсмэн А. Переход к микронным и субмикронным размерам в технике интегральных схем/УТИИЭР. — 1983. — 5. — С. 6—24. 83. Рекурсивные машины и вычислительная техника/В. М. Глушков, М. В. Иг- натьев, В. А. Мясников, В. А. ТоргашевУУПрепринт. — Киев, 1974. — 26 с. — (Ин-т кибернетики АН УССР; № 74—57). 84. Самофалов К. Г., Кухарчук А. Г., Луцкий Г. М. Структуры ЭЦВМ чет- вертого поколения. — Киев: Техника, 1972. — 256 с. 85. Самофалов К. Г., Луцкий Г. М. Основы построения конвейерных ЭВМ.— Киев: Вища школа, 1981. — 224 с. 86. Самофалов К. Г., Луцкий Г. М. Структуры и организация функциониро- вания ЭВМ и систем. — Киев: Вища школа, 1978. — 392 с. 87. Самофалов К. Г., Луцкий Г. М., Кулаков Ю. А. Организация вычисли- тельных процессов в конвейерной ЦВМ/УПараллельные машины и параллель- ная математика. — Киев: ... 1977. — С. 21, 22. 88. Самофалов К. Г., Луцкнй Г. М., Кулаков Ю. А. Проблемы разработки и создания математического обеспечения конвейерных вычислительных систем// Распараллеливание обработки информации. Ч. 3/ФМИ АН УССР. — Львов, 1983. —С. 178—180. 89. Самофалов К. Г., Луцкий Г. М., Талаев А. К. Архитектура многоуров- невых конвейерных вычислительных системУУРаспараллеливание обработки ин- формации. Ч. 2/ФМИ АН УССР. — Львов, 1985. — С. 23. 90. Самофалов К. Г., Луцкий Г. М., Талаев А. К. Организация параллель- ных вычислений в многоуровневых конвейерных вычислительных системах// Распараллеливание обработки информации/ФМИ АН УССР. — Львов, 1983. — С. 12,13. 91. Самофалов К. Г., Луцкнй Г. М., Талаев А. К. Структурная организация многомерных конвейерных вычислительных системУУПрепринт. — Львов, 1981. — С. 11—13 (ФМИ АН УССР, № 44). 92. Самофалов К. Г., Луцкий Г. М., Хижинский Б. П. Принципы построения высокопроизводительных вычислительных систем, оперирующих сложными функциональными зависимостями на уровне машинных операцийУУМеханизация и автоматизация управления/УкрНИИНТИ. — Киев, 1974.— №4.— С. 45—50. 93. Тьюарсон Р. Разреженные матрицы: Пер. с англ. — М.: Мир; 1977. — 189 с. 94. Уоллер Л. Положение дел в области цифровых умножителейУУЭлектрони- ка. — 1983. — № 14. — С. 94—96. 95. Уэйзер Л. Быстродействующий цифровой умножитель для обработки сиг- налов в реальном времени/УЭлектроника. — 1977. — № 20. — С. 40—49. 96. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математичес- ких вычислений: Пер. с англ. — М.: Мир, 1980. — 279 с. 97. Шауман А. М. Основы машинной арифметики. — Ленинград: Изд-во Ленингр. ун-та, 1979. —312с. 98. Эффективные методы решения некоторых задач линейной алгебры в кон- вейерных вычислительных системах/К. Г. Самофалов, Г. М. Луцкий, А. В. Ко- 268 рочкин, Т. А. Блинова/УПрепринт. — Киев, 1980. — С. 3. 4. — (Ин-т электро- динамики АН УССР, № 224). 99. Andrews М., Eggerding D. A. A Pipeline Computer Architecture for Unified Function Evaluation/yComput. and Elec. Eng. — 1978. — N 2. — P. 189—202. 100. Atkins D. E. Higher Radix Division Using Estimates of the Divisor and the Partial RemaindersVyiEEE Trans. — 1968. — Vol. C-17, N 10. — P. 925—934. 101. Baker P. W. Parallel Multiplicative Algorithms for some Elementary Func- tionsVyiEEE Trans. — 1975. —Vol. C-24, N 3. — P. 322—325. 102. Baker P. W. Suggestion for a Fast Binary Sine/cosine Generator/VlEEE Trans. — 1976. — Vol. C-35. N 11. — P. 1134—1136. 103. Campeau J. 0. Cellular Redundancy Brings New Life to an Old AlgorithmVY Electronics. — 1969. — Vol. 42, N 15. — P. 98—104. 104. Come D., Syre J. С. et al. The LAU Parallel System Software Definition and Implementation Through a Multimicroproscessor Architecture//EUROMlCRO symposium, prep, 1976. — P. 109—117. 105. De Lugish B. G. A Class of Algorithms for Automatic Evaluation of Cer- tain Elementary Functions in a Binary Computer//Comput. Sci. Rep./Univ. Il- linois. — Urbana. — 1970. — 181. p. 106. Dennis J. B. Data Flow Super-computers//Computer. — 1980. — N. 11. — P. 48—56. 107. Ercegovac M. D. An On-line Square-rooting Algorithm//Proc. 4th Symp. Comput. Arith. — Santa Monica, Calif., 1978. — P. 183—189. 108. Ercegovac M. D. Radix-16 Evaluation of Certain Elementary Functions// IEEE Trans, — 1973. — Vol. C-22, N 6. — P. 561—566. 109. Frieman С. V. Statistical Analysis of Certain Binary Division Algorithms// Proc. IRE. — 1961. — Vol. 49, N 1. — P. 91—103. 110. Gorji-Sinaki A., Ercegovac М. D. Design of a Digitslice On-line Arithme- tic Unit//Proc. 5th Symp. Comput. Arith. — Ann Arbor, Mich. — 1981. — P.72— 80. 111. Irwin M. J. A Pipeline Processing Unit for on-line Division//SIGARCH Newsletter. — 1978. — N 7. — P. 56—61. 112. Liddiard L. A. Required Scientific Floating-point Arithmetic//Proc. 4th Symp. Comput. Arith. — New York, 1978. — P. 56—62. 113. Meggitt J. E. Pseudo Division and Pseudo Multiplication Processes'/IBM J. Res. and Develop. — 1962. — N 2. — P. 210—226. 114. Metze G. Minimal Square—Rooting//IEEE Trans. Comput. — 1965. — N 2. — P. 181—185. 115. Oklobdizija V. G., Ercegovac M. D. An On-line Squreroot algorithmY/IEEE Trans. — 1982. — Vol. C-31, N 1. — P. 70—75. 116. Owens R. M. Compound Algorithms for Digit On-line Arithmetic//Proc. 5th Symp. Comput. Arith. — Ann Arbor, Mich., 1981. — P. 64—71. 117. Raghavendra С. S., Ercegovac M. D. A Simulator for on-Line Arithmetic// Proc. 5th Symp. Comput. Arith. — Ann Arbor, Mich., 1981. — P. 92—99. 118. Robertson J. E. A New Class of Digital Division Methods//lRE Trans. Electron. Comput. — 1958. — N 3. — P. 218—222. 119. Trivedi К. S., Ercegovac M. D. On-line Algorithms for Division and Multi- plication//IEEE Trans. — 1977. — Vol. C-26, N 7 — P. 681—687. 120. Trivedi К. S., Rusnak J. G. Higher Radix On-line Division//Proc. 4th Symp. Comput. Arith. —Santa Monica, Calif., 1978. —P. 164—174. 121. Voider J. E. The CORDIC Trigonometric Computing Technique//! RE Trans. Electron. Comput. — 1959. — Vol. EC-8, N 3. — P. 330—334. 122. Watanuki 0., Ercegovac M. D. Floating-point On-line Arithmetic: Algo- rithm s//Proc. 5th Symp. Comput. Arith. — Ann Ardor, Mich., 1981. — P. 81—86. 123. Watanuki 0., Ercegobac M. D. Floating-point On-line Arithmetic: Error Analysis//Proc. 5th Symp. Comput. Arith.—Ann Arbor, Mich., 1981. — P. 87—91. 269 Предисловие ... ......................... Введение ... ........................... 1. Разработка и анализ сетевой модели параллельных вычислений .... 1.1. Вводные замечания . . .................... 1.2. Структурно-графический способ представления параллельных вы- числений ... ........................ 1.2.1. Операции и работы . ................. 1.2.2. Системы операций и ресурсы . ............. 1.2.3. Варианты упорядочения работ и способы формирования се- тей ... ........................ 1.3. Сетевая модель параллельных вычислений ........... 1.3.1. Пространственно-временное представление параллелизма 1.3.2. Декомпозиция сетей . . ................. 1.3.3. Структурный синтез сетевой модели параллельных вычисле- ний ... ....................... 1.3.4. Классификация цепей и подсетей . ........... 1.3.5. Составные цепи и их анализ ............... 1.3.6. Цепи второго порядка . . ................ 1.3.7. Многомерные цепи и подсети . ............. 1.3.8. Вопросы оптимизации подсетей . . ............ 1.3.9. Сеть подсетей как модель параллельной организации вычис- лений ... ....................... 1.4. Заключение ... ....................... 2. Структурная интерпретация сетевой модели параллельных вычислений 2.1. Вводные замечания . . .................... 2.2. Виды параллелизма и унификация вычислений ........ 2.3. Структурная интерпретация сетевой модели подсистемы управле- ния вычислительной системы . ................ 2.4. Структурные аспекты оптимизации исполнительных подсистем 2.5. Обобщенная функциональная модель конвейерного преобразовате- ля информации . . ....................... 2.6. Организация управления в конвейерных преобразователях ин- формации ... ........................ 1 2.7. Структурная классификация конвейерных преобразователей ин- формации ... ........................ 2.8. Заключение ... .......................: 3. Основы теории вычислений в двоичной избыточной квазиканонической системе счисления . ....................... I 3.1. Вводные замечания . . .................... 270 3.2. Метод SRT-деления . . .................... 1 3.3. Метод вычисления «цифра за цифрой» . ............. 1 3.4. Неавтономный режим вычисления . .............. 1 3.5. Введение избыточности в итерационные вычислительные алгоритмы машинной арифметики . . .................. 1 3.6. Обобщенная процедура выполнения арифметических операций в неавтономном режиме вычислений . .............. 1 3.7. Синтез алгоритмов арифметических операций в автономном и неавто- номном режимах вычислений . ................ 1 3.7.1. Алгоритмы операции алгебраического сложения ..... 1 3.7.2. Алгоритмы операции деления . ............. 1 3.7.3. Алгоритмы операции умножения . ........... 1 3.7.4. Алгоритмы операции извлечения квадратного корня . . . ' 3.7.5. Алгоритмы вычисления функции натурального логарифма 3.7.6. Алгоритмы вычисления функции экспоненты ....... I 3.8. Синтез алгоритмов арифметических операций в полуавтономном и частично автономном режимах вычислений . .......... 1 3.8.1. Алгоритм операции алгебраического сложения ....... 1 3.8.2. Алгоритм операции деления . ............. 1 3.8.3. Алгоритм операции умножения . ....... .....] 3.8.4. Алгоритм вычисления конвейерных функций . . . . . . ] 3.9. Особенности выполнения операций в конвейерных преобразовате- лях информации с однородной структурой . .......... 1 3.9.1. Элементарная операция передачи слов . .........! 3.9.2. Элементарная операция сдвига слов . .......... I 3.9.3. Элементарная операция суммирования слов ....... 3.9.4. Элементарная операция прибавления единицы к слову . . . 3.9.5. Алгебраическое сложение и вычитание чисел с фиксирован- ной точкой . . ..................... 1 3.9.6. Способы выполнения операции умножения ........ 3.9.7. Способы выполнения операции умножения в дополнительных кодах ... ....................... 3.10. Заключение ... ...................... 4. Организация динамических режимов вычислений в конвейерных вычис- лительных системах . . ..................... 4.1. Вводные замечания. . .................... 4.2. Особенности программирования и формирования вычислительных последовательностей ... ................... 4.3. Формирование вычислительных последовательностей в конвейер- ных вычислительных системах . ................ 4.3.1. Представление арифметических выражений в модифициро- ванной совершенной бесскобочной записи ........ 4.3.2. Полиномиальная форма представления вычислительных по- следовательностей . . ................. 4.3.3. Реализация вычислительных последовательностей в конвей- ерных преобразователях информации . ......... 4.4. Организация в конвейерных вычислительных системах частично автономных режимов вычислений чисел с плавающей точкой . . . 4.5. Заключение ... ....................... 5. Особенности реализации вычислительных алгоритмов в конвейерных вычислительных системах . . .................. 5.1. Вводные замечания. . . .................... 5.2. Способы вычисления суммы парных произведений в линейно-цик- лических конвейерных преобразователях информации. ...... 5.3. Способы вычисления суммы парных произведений в квазилиней- ных конвейерных преобразователях информации . . ....... 5.4. Оценка эффективности различных методов параллельной обработ- ки информации при вычислении суммы парных произведений . . 5.5. Мультиконвейерные вычислительные системы для обработки сиг налов ... ......................... 5.6. Решение систем линейных алгебраических уравнений ..... 5.7. Заключение ... ...................... 6. Особенности разработки и реализации алгоритмов и примеры структур ной организации конвейерных средств вычислительной техники . . 6.1. Алгоритмы алгебраического сложения произвольных последова тельностей чисел с заданной точностью представления результат, 6.2. Векторизация алгоритмов решения систем линейных алгебраичес ких уравнений большой размерности с разреженными матрицам! коэффициентов ... .................... 6.3. Структура многофункционального линейно-циклического конвей ерного преобразователя информации. . ........... 6.4. Разработка конвейерных СБИС для выполнения операций сумми рования с заданной точностью представления результата . . . 6.5. Заключение ... ...................... Заключение ... ........................ -Список литературы . . .....................