Устройство для параллельной обработки трехмерных сцен
Изобретение относится к вычислительной технике и предназначено для обработки трехмерных изображений. Цель изобретения -повышение отказоустойчивости устройства. Отказавшие в устройстве связи обнаруживаются с помощью диагностирующей программы . Функции отказавших процессоров выполняют работающие процессоры за счет программного обеспечения блока программного управления. 8 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (и)з G 06 Г 15/16, 15/62
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
Пд ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОЛИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТО РС КО МУ С В ИДЕТ ЕЛ ЬСТВУ. (21) 4433226/24 (22) 05.04.88 (46) 07 11.91. Бюл. й. 41 (71) Ижевский механический институт (72) 8.А.Бима ков (53) 681.325 (088.8) (56) Авторское свидетельство СССР
Q 1456965, кл. 6 Об F 15/16, 1986.
Авторское свидетельство СССР по заявке М 4365371/24, кл. G 06.F 15/16, 15/62, 1988.
Изобретение относится к вычислительной технике и предназначено для обработки трехмерных изображений.
Цель изобретения — повышение отказоустойчивости устройства.
На фиг. 1.и 2 представлено устройство параллельной обработки трехмерных сцен; на фиг. 3 — общий принцип построения процессорной матрицы устройства с использованием универсальных 24-процессорных модулей; на фиг. 4 — варианты распределения памяти процессоров для различных режимов работы матрицы; на фиг, 5 — общая схема алгоритма микропрограммы, реализующей в устройстве команду управления матрицей; на фиг. 6 и 7 — способы обхода отказавших элементов матрицы: на фиг. 8способ "прокачки" содержимого. двухуровневой сцены А х А х А через исправную . кубовую оболочку С х С х С.
Устройство содержит блок матрицы процессоров. состоящий из трехмерной . матрицы 1 А х А х А процессоров и блок 2
„„53JÄÄ 1689966 А1 (54) УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ
ОБРАБОТКИ ТРЕХМЕРНЫХ СЦЕН (57) Изобретение относится к вычислительной технике и предназначено для обработки трехмерных изображений. Цель изобретения
-повышение отказоустойчивости устройства.
Отказавшие в устройстве связи обнаруживаются с помощью диагностирующей программы. Функции отказавших процессоров выполняют работающие процессоры за счет программного обеспечения блока программного управления. 8 ил.
3 управления. К устройству могут быть подключены блоки 3 поворота через входы 4 и выходы 5 матрицы. Матрица 1 состоит иэ А процессоров 6. Каждый иэ которых включает в себя узел 7 памяти, первый регистр 8 операнда, второй регистр 9 операнда, элемент ИЛИ 10, блок элементов И, состоящий из элементов И 11-14; элемент ИЛИ-НЕ 15.
Блок 2 управления содержит управляющий процессор, узел 16 памяти программ и данных, программноадресуемые регистры 17- 0
24; таймер 25, узел 26 прерывания. «О
Устройство содержит также группу аналого- О вых сумматоров в виде ступеней 27-29 ана- Яс логового сумматора, аналого-цифровой преобразователь 30, узел многовходовмх 1в элементов ИЛИ в. виде ступеней 31-33 многовходового элемента ИЛИ, мультиплексор 34 признака состояния процессоров. Управляющий процессор содержит арифметико-логической узел 35. мультиплексор 36 адреса, преобразователь
37 адреса, дешифратор 38 команды, дешифратор 39 выбора слоя поворота, элементы И
1689966
40, узел микропрограммного управления, Узел микропрограммного управления состоит иэ генератора 41 синхронизирующих импульсов, генератора 42 адреса микрослова, регистра 43 адреса микрослова, узла 44 памяти микрослов, регистра 45 микрослова, дешифраторов 46 кода микрооперации, дешифратора 47 кода режима ввода-вывода, элементов И 48-52. Ступени
28 и 29 соединены с преобразователем 30 посредством коммутатора 53. Процессоры
6, образующие относительно своих ортогонально-кольцевых связей замкнутую систему, и связанные с ними дешифратор 46, ступени 2 ?, 31 объединяются в конструктивный модуль 54. Регистр 17 связан с входами
4 матрицы 1 посредством блока 55 элементов И.
Структура межмодульных связей матрицы 1, построенной на универсальных 24процессорных модулей, изображена на фиг.
3. Из фиг. 3 видно, что все межмодульные связи матрицы могут быть разбиты на две большие группы: группы связей, соединяющих модули, процессоры 6 которых образуют в кубе А х А х А кубовые оболочки с толщиной, равной 1 (вкладываемые друг в друга по принципу "матрешки"); и группы связей, "сшивающих" эти оболочки в единый куб А х А х А. При отказе межмодульной связи нарушение нормального функционирования прототипа происходит из-за отсутствия воэможности выполнить операцию переноса сцены А х А х А на шаг по В без искажений. В случае отказа процессора 6 нарушение нормального функционирования прототипа происходит: изза отсутствия возможности выполнить оперэцик> переноса сцены А х А х А на шаг по В беэ искажений; из-за потери аппаратных средств для хранения и параллельной обработки информации об уровнях яркости куба i х х I отказавшего процессора 6. В предлагаемом устройстве первые две из названных причин устраняются путем организации автоматического обхода отказавших модулей и межмодульных связей, Последняя из причин устраняется путем использования аппаратных средств исправных модулей для хранения и обработки информации об уровнях яркости кубиков I x i x I отказавших процессоров 6. Адресуемой информационной единицей матрицы 1 является двухуровневая сцена формата F. Формат
F составлен из кубиков x! x I исправных процессоров 6, Уровень яркости каждого кубика I х х в двухуровневой сцене формата F принимает значение "1" или "0". При наличии в матрице 1 А исправных процессоров 6 формат F совпадает с формой, куба
А х А х А. Выход из строя процессоров 6 равнозначен изменению формата F сцены, это изменение заключается в удалении из куба А х Л х А кубиков I х x отказавших процессоров 6, Команды управления матрицей, хранящиеся в узле 16, оперируют двухуровневыми сценами формата А х А х А. Это объясняется тем, что текущий формат F в силу случайности отказа процессоров 6 является непредсказуемым, формат А х А х А заранее известен и при абсолютно исправной матрице 1 обеспечивает максимальную скорость обработки информации в устройстве. В случае отказа хотя бы одного процессора 6 становится невозможным размещение обрабатываемой двухуровневой сцены А х А х А внутри одной адресуемой сцены формата Е, обмен информацией между процессорами 6 нарушается. Поэтому при отказе элементов матрицы выполнение команд, оперирующих полноформатными сценами А х А х А, осуществляется в устройстве с использованием метода эмуляции. В роли эмулируемой вычислительной системы выступает устройство с абсолютно исправной матрицей 1, а в роли эмулирующей — устройство с матрицей текущего состояния (имеющей неисправные модули или неисправные межмодульные. связи), .Для предотвращения потери информации об уровнях яркости кубиков I х х I отказавших процессоров 6 в сценах А х А х А функцию хранения содержимого узла 7 отказавших процессоров 6 берут на себя узлы
7 исправных модулей. В этом случае адресное поле узлов 7 разбивается на три части.
Первая часть, содержащая N> адресов, предназначена для хранения информации об уровнях яркости кубиков x I х исправных процессоров 6 в N> двухуровневых сценах формата А х А х А (другими словами — для хранения О-фрагментов сцен А х А х А).
Вторая часть, содержащая N2 адресов, предназначена для хранения информации об уровнях яркости кубиков l x I х отказавших процессоров 6 в N< двухуровневых сценах А х А х А (другими словами — для хранения 0-фрагментов сцен А х А х А).
Третья часть, содержащая Na адресов, предназначена для хранения сцен-масок (двухуровневых сцен-констант) и рабочих сцен, имеющих формат F и используемых микропрограммами эмуляции для формирования и хранения промежуточных результатов, получаемых в ходе обработки полноформатных сцен. Из указанного распределения адресов узла 7 памяти становится очевидным, что отказоустойчивые программы, оперирующие полноформатны1689966 ми сценами А х А х А, должны использовать не всю область адресов узла 7 памяти, а только N1адресов. Процессор 6 исправного модуля, содержащий в своем узле 7 информацию об уровне яркости кубика х l x l i-ro отказавшего процессора 6 в сцене А х А х А, назовем дублером 1-го отказавшего процессора. Поскольку в устройстве устойчивость к отказам процессоров 6 достигается, если число отказавших процессоров 6 не превышает А /2, для представления одной полноформатной сцены А х А х А достаточно двух двухуровневых сцен формата F. Первая из этих сцен, называемая в дальнейшем Осценой (или О-фрагментом сцены А х А х А), содержит информацию об уровнях яркости собственных кубиков 1 х х l исправных процессоров 6 в 1редставляемой сцене Л х
А х А. Вторая сцена, называемая 0-сценой, содержит информацию об уровнях яркости кубиков l x l x l отказавших процессоров 6 в представляемой сцене А х А х А (другими словами — содержит D-фрагмент представляемой сцены Л х А х А), При !11jN2 =
m каждая D-сцена содержит m D-фрагментов, дополняющих m О-сцен до полноформатных двухуровневых сцен, Варианты положения D-фрагментов в D-сцене показаны на фиг. 4 (г — и), Каждому такому положению соответствует свой D-адрес. При m > 1 адресное поле памяти в узле 7 распределяется более экономно, чем при m = 1 (т.е. число N< здесь существенно выше), однако в этом случае возникает необходимость в процедуре установки сформированного Dфрагмента в D-сцену по заданному D-адресу. Микропрограммы, реализующие команды управления матрицей, можно представить в виде последовательности более крупных, чем микрослова, структурных единиц — псевдокоманд, Псевдокоманды по выполняемой функции и способу микропрограммной реализации аналогичны командам И НЕ А1, А2, СДВ А1, А2, ПВ1 А1, А2, но оперируют сценами текущего формата F.
Для различия между мнемоническими обозначениями команд и псевдокоманд между мнемоническими обозначениями сцен и адресов сцен в дальнейшем сцены и коды операций команд условимся обозначать прописными буквами, а адреса сцен и коды операций псевдокоманд — строчными буквами (например: a1 — адрес сцены А, пв1 d1, d2 — обозначение псевдокоманды, осуществляющей поворот содержимого сцены 01 формата F на угол 90 вокруг оси Ох и запись результата поворота в сцену Д2, СДВ а1, а2 — обозначение команды, осуществляющей сдвиг одержимого полноформатной сцены
А1 на шаг по В и запись результата сдвига
55 в полноформатную сцену А2), Двухуровневые сцены формата А х А х А условимся обозначать AN (где N — номер сцен ы1, а их адреса—
aN. О-сцену сцены AN условимся обозначать ON, а ее адрес — oN. 0-сцену сцены AN будем обозначать DN, a ее адрес — dN. Сцены-маски (формата F) сбоэкачим М! (где L— номер сцены-маски), а их адреса L Рабочие сцены (формата F) условимся обозначать PD (где D — комер рабочей сцены), а их адреса — pD, В момент включения устройства или в процессе работы устроиства в результате прерывания по таймеру 25 (цикл запроса прерывания определяется исходя из значения предельно допустимой вероятности наработки матрицы на отказ) производится запуск диэгностирующей программы. По окончании рабо ы диагностирующей программь1 делается вывод о работоспособности матрицы. Если матрица признана работоспособной, но имеет отдельные неисправные элементы, в регистре
21 устанавливается соответствующий код режима работы матрицы, в матрице синтезируются необходимые сцены-маски, Каждый из режимов работы матрицы характеризуется своим распределением адресов памяти в узле 7, своим способом выполнения команд управления матрицей. Возможные варианты распределения адресов памяти в узле 7 для различных режимов работы матрицы показаны на фиг. 4. Распределение, изображенное на фиг. 4 (а), соответствует режиму рабаты матрицы, когда устройство абсолютно исправно. Распределение, изображенное на фиг, 4 (б). соответствует случаю, когда матрица имеет только отдельные неисправные межмодульные связи, Распределение, изображенное нэ фиг. 4 (в — и), соответствует случаю, когда в матрице имеются отдельные неисправные модули и отдельные неисправные межмодульные связи. Код режима работы матрицы однозначно определяет: число, вид используемых сцен-масок, коды их адресов; число используемых рабочих сцен, коды их адресов. Код режима работы матрицы совместно с кодом адреса aN однозначно определяют: код адреса oN; код адреса dN; положение
D-фрагмента сцены AN в DN. Генерация всех перечисленных кодов по коду режима работы матрицы и кодам aN, хранящимся в адресной части регистра 22 команды, осуществляется в преобразователе 37 адреса.
B зависимости от кода, поступающего с многоразрядного паля РУАВ регистра 45 микрослова, на выходе преобразователя 37 формируется один из кодов ON, dN, m1, Р1 и т.д. При неисправной, но работоспособной матрице 1 выполнение команд типа
1689966
СДВ, а1, а2; ПВЗ а1; ВВ а1; ВЫВ а1 связано с обходом отказавшихся элементов матрицы. Во избежание значительного снижения скорости обработки полноформатных сцен
А х А х А в устройстве обход отказавших модулей и межмодульных связей при эмуляции команд СДВ, ПВЗ, ВВ, ВЫВ должен осуществляться с высокой степенью параллелизации, а путь обхода был коротким, дублеры отказавших процессоров 6 должны располагаться в непосредственной близости к модулю, содержащему эти отказавшие процессоры 6. Этому условию удовлетворяют варианты размещения процессоровдублеров, изображенные на фиг, 4 (r — и).
Здесь кубики I х х I процессоров отказавшего модуля заштрихованы, кубики I х х их процессоров-дублеров незаштрихованы; кубик отказавшего процессора и кубик его дублера имеют общую грань. Возможные пути обхода отказавших элементов матрицы условно изображены на фиг. 6 (б — и), Обход отказавших процессоров 6 включает две основные процедуры, формирование фрагмента 02 результирующей сцены А2 иэ 0- и D-фрагментов исходной сцены А1; формирование D-фрагмента сцены А2 из фрагмента 01 исходной сцены А1. Формирование 02 осуществляется путем использования двух сцен-масок; М1 и М2, Все кубики х х сцены-маски М1 имеют уровень яркости и0", кроме кубиков, являющихся ближайшими соседями кубиков 1 x I x отказавших процессоров в направлении В. Сцена-маска М2 является теоретико-множественным дополнением сцен ы М1. Вариант обхода отказа вшего процессора б показан на фиг. 6 (к, л) и соответствует направлению обхода, условно изображенному на фиг, 6 (б). Здесь Х вЂ” отказавший процессор 6; М/ — процессор 6, передающий в абсолютно исправной матрице
1 информацию в процессор X; V — процессор
6, принимающий в абсолютно исправной матрице 1 информацию из процессора Х; S — дублер процессора Х; М2 = М1, Уровень
"1" в сцене М1 имеет только кубик ! процессора V.
Микроподпрограмма обхода при выполнении команды СДВ А1, а2 (фиг. 6, к, л) в терминах псевдокоманд имеет вид:
1. пв2 о1, р1; поворот 01 на 90 вокруг
Gy и запись результата поворота в сцену Р1 (на случай, если А2 = А1) — фиг. 6, к — 1.
2. сдв 01, 02
3. ине о2, о2; маскирование 02 = 02nM2
= 02UMi.
4. ине м1, о2
5. сдвд1, р2; фиг. 6, л — 1.
6. пв2, р2, р2; фиг. 6, л — 2, 3, 4, 7. пв2 р2, р2
8. пв2 р2, р2
9. сдв р2, р2; фиг. 6, л — 5.
10. пв2 р2, р2; фиг. 6, в — 6.
5 11. ине р2 р2 маскирование P2 =
=P2nM1 = P2 VM1 = P2u М2.
12. ине М2, р2
13. ине р2. 02; склеивание 02 = 02 002 =
=Р2 ll02.
10 14. ине о2, о2; сцена 02 сформирована.
15. сдв р1, р1; фиг. 6, к — 2.
16. пв2 р1, р1; фиг. 6, к — 3, 4, 5.
17. пв2 р1, р1.
18. пв2 р1, р1.
15 19. сдв р1, р1; фиг. 6, к — 6. D-фрагмент сцены А2 сформирован и находится в Р1.
20, ине d2, d2; начало размещения Dфрагмента сцены А2 в Д2 (положение 0фрагмента сцены А1 и Д1 и положение
20 D-фрагмента смены А2 в Д2 совпадают и соответствуют фиг. 4, г), 21, ине м3 д2; маскирование Д2 =
=Д2пМ4 = Дн2!0МЗ. Уровень яркости и1и в сцене-маске МЗ имеет только кубик !"!"!
25 процессора S, M4-- МЗ.
22. ине р1, р1; выделение 0-фрагмента сцены А2 иэ Р1 Р1 = PinM3 = P1UM4.
23. ине р1, d2; склеивание D2 = 02 UP1 =
=D2 UP).
30 Как видно из приведенного примера, способ обхода отказавшего процессора 6 (а значит и вид соответствующей микроподпрограммы обхода) зависит от положения дублера отказавшего процессора в матрице
35 1, Если I процессоров-дублеров расположены относительно своих дублируемых процессоров одинаковым образом, обход всех f отказавших процессоров осуществляется одновременно путем использования одной
40 общей микроподпрограммы обхода и общих масок М1, М2, МЗ, М4. Например, обход 24 отказавших процессоров 6, изображенных на фиг. 4 (г), осуществляется одновременно в соответствии с ранее рассмотренным ал45 горитмом, но с применением собственных сцен-масок. Вариант обхода отказавшей межмодульной связи (соединяющей в абсолютно исправной матрице 1 выход процессора W с входом процессора V) показан на
50 фиг, 7 (а). Обход осуществляется по направлению, условно изображенному на фиг. 6 (е).
Уровень яркости "1и в сцене-маске М5 имеет кубик ЙИ процессора V, вход которого соединен с отказавшей межмодульной связью.
55 В терминах псевдокоманд микроподпрограмма обхода отказавшей межмодульной связи имеет вид:
1. пв2 а1, р1; поворот сцены А1 на угол
90 вокруг Оу и запись результата поворота
1689966
10 в сцену Р1 (на случай. если А2 - А1) — фиг. 7 (а — 1).
2. сдв а1. а2
3. ине а2, а2; маскирование А2- А2пМ6
-A2u М5. Мб М5.
4. ине м5, а2
5. сдв р1, р1: фиг. 7 (а — 2).
6. и в2 р11 р1; фи г. 7 (а — 3, 4, 5).
7. пв2 р1, р1
8. пв2 р1, р1
9. сдв р1, р1; фиг. 7 (а — 6).
10. пв2 р1, р1; фиг. 7 (а — 7, 8, 9), 11. пв2 р1, р1
12. пв2 р1, р1
13. сдв р1,р1; фиг. 7(а — 10).
14. пв2 р1, р1. фиг. 7 (а — 11).
15, цне р1, р1; маскирование Р1 " Р1п М5
P1U М6.
16. ине мб, р1
17. ине р1. а2, склеиеание А2 =A2UP1Д2и Р1.
18. ине а2, а2 ".
Если одновременный обход всех отказавших элементов матрицы невозможен (отсутствует общее направление обхода, процессоры-дублеры в 0-фрагменте расположены относительно дублируемых процессоров не одинаковым образом), отказавшие процессоры и межмодульные связи делятся на m групп. Элементы, входящие в группу, обходятся одновременно с использованием общей микроподпрограммы и общих сценмасок. Обход групп осуществляется последовательно — группа за группой. По результатам обхода всех групп формируется общий О- и общий 0-фрагменты результирующей сцены А х А х А. Микроподпрограммы, реализующие команды ПВЗ а1;
ВВ а1; ВЫВ а1. отличаются от рассмотренных микроподпрограмм, реализующих команду СДВ а1, а2, тем, что А2 = А1, 02 = 01, Д2 = Д1. В отличие от команд СДВ, ПВЗ, ВВ, ВЫВ выполнение команд ПВ1 и ПВ2 не требует обхода отказавших модулей и меж- модульных связей, так как все ортогонально-кольцевые связи расположены внутри
24-процессорных модулей. Однако, если при отказе только межмодульных связей способ микропрограммной реализации команд ПВ1 и ПВ2 практически не отличается от способа реализации команд ПВ1 А1, А2 и
ПВ2 А1, А2 прототипа(за исключением кода
РУА — в предлагаемом устройстве этот код многоразрядный), то выход иэ строя модулей изменяет способ микропрограммной реализации этих команд вследствие изменения способа внутреннего представления сцен А х А х А в устройстве. В последнем случае процесс выполнения команд
ПВ1 а1, а2 и ПВ2 а1, а2 включает три основных этапа: 1) поворот О-фрагмента сцены А1 на 90 вокруг оси Ох (для ПВ2 — вокруг оси
Оу); 2) поворот копии 0-фрагмента сцены А1 на 90 вокруг оси Ох (для ПВ2 — вокруг оси
5 Оу); 3) запись повернутой копии 0-фрагмента по адресу О-фрагмента сцены А2. В терминах псевдокоманд микропрограмма, реализующая команду ПВ2 а1, а2 имеет вид:
1. пв2 о1, о2; поворот О-фрагмента, 10 2. пв2 д1, р1: поворот О-фрагмента.
3. сдв р1, р2. размещение О-фрагмента в Д2. В рассматриваемом приме7 е положение О-фрагмента сцены А1 в Д1 соответствует положению, изображенному на фиг. 4
15 (x); положение О-фрагмента сцены А2 в Д2 соответствует положению, изображенному на Фиг. 4(д).
4, ns2 р1, р1
5. пв2 р1, р1
20 6. пв2 р1, р1
7. сдв р1, р1
8. пв2 р1, р1
9. ине р1, р1; максирование Р1 - P1tl М2
Р10 М1, 2S 10, ине м1, р1
11. ине д2, д2. максирование д2 - Д2п М1
Д2оМ2.
12. ине м2, д2
Я, ине р1, д2; склеивание Д2 - Р1УД230 210Д2.
14. ине д2, д2.
В случае отказа процессоров 6 микропрограмма, реализующая команду ИНЕ а1, а2, производит следующие виды операци
35 теоретикомножественную операцию 02 = 020
ЙЙ над О-фрагментами сцен А1 и А2; осуществляет привязку копии (D 1) сцены 01 к
0-фрагменту сцены А2 (в результате выполненной привязки информация об уровнях
40 яркости кубика х х одного и того же отказавшего процессора 6, относящаяся к двум различным сценам А1 и А2 располагается в одном процессоре-дублере); теоретическо-множественную операцию Р1 О 77
45 R)2; осуществляет. выделение результирующего 0-фрагмента иэ сцен Р1 и записывает его по 0-адресу О-фрагмента сцены А2 данного вида отказа матрицы:
1. ине 01, о2; 02001.
50 2. сдв д1, р1, в рассматриваемом примере положение О-фрагмента сцены А1 в 01 соответствует положению, изображенному на фиг. 4 (г); положение 0-фрагмента сцены
А2 в 02 соответствует положению, иэобре-
55 женному на фиг. 4 (д).
3. пв2 р1, р1
4, пв2 р1, р1
5. по2 р1, р1
6, сдв р1, р1
7, пв2 р1, р1; привязка закончена
1689966
8. инед2, р1
9. ине р1, р1; маскирование Р1 = Р1йМ2=
= P1UM1
1G. ине м1, р1; маски М1 и М2 определены на стр. 8
11. ине Д2, д2; маскирование 02 = D2n
М1 = 02И42
12. ине м2, д2
13. инв р1, д2; склеивание D2 = РРО2 =Р 1UD2
14, ине д2. д2 ".
В систему команд устройства введена команда условного перехода, ПП aN, в— если содержимое полноформатной сцены
AN пусто, передать управление команде, хранящейся в узле памяти 16 па адресу в: в противном случае — перей и к следующей по порядку команде. Под пустой двухуровневой сценой А х А х А здесь понимается полноформатная сцена, все кубики ИЧ которой имеют уровень яркости "1" (негативное представление). Анализ содержимого сцены AN осуществляется при помощи комбинационной схемы, состоящей в общем случае из последовательно соединенных ступеней 31-33 (фиг, 1, 2). Каждая ступень 31 входит в состав модуля 54 и представляет собой 24-входовую схему ИЛИ, входы когорой соединены с инверсными выходами одноразрядных регистров 8 этого модуля, Каждая ступень 32 является многовходовой схемой ИЛИ, входы j-й ступени 32 соединены с выходами ступеней 31 тех модулей, кубики I x. I x I процессоров 6 которых образуют в кубе А х А х А матрицы j-ю кубовую оболочку (фиг. 3). Каждая ступень 33 представляет собой многовходавую схему ИЛИ, входы которой соединены с выходами двух или более ступеней 32. В процессе выпалнения команды ПП aN, в содержимое сцены
AN (если в матрице 1 отсутствуют отказавшие процессоры 6) или ON (при наличии отказавших процессоров 6 в матрице 1) извлекается из узлов 7 и записывается в регистры 8. В зависимости от кода режима работы матрицы, хранящегося в регистре
21, мультиплексор 34 подключает вход генератора 42 адреса микрослова к выходу одной из ступеней ЗЗ или 32. Например, при абсолютно исправной матрице к входу генератора 42 подключается выход той ступени
33, входы которой соединены с выходами всех ступеней 32 устройства, при этом сиг-. нал, снимаемый с выхода мультиплексора
34, характеризует сразу все содержимое сцены AN. Если в матрице 1 имеются отказавшие и роцессоры 6, к входу генератора 42 подключается ступень 33 (или 32). все nepBbl8 ступени 31 которой соединены с и< и" равными процессорами 6, Кубовые
Q0
55 оболочки ступеней 32, подключенных к входам указанной ступени 33, образуют фильтрирующую зону куба А х А х А матрицы (фиг.
7, б, в, г), При наличии отказавших процессоров 6 анализ содержимого сцены AN состоит в последовательной прокачке всего содержимого копии сцены через данную фильтрующую зону. Элементарный шаг прокатки включает; перемещение анализируемого участка копии сцены AN в фильтрующую зону; пере-ылку О-фрагмента перемещенной сцены-копии из узлов 7 в регистры 8; 3) микроветвление по результатам анализа сигнала, снимаемого с выхода ступени 33 (32), связанной с входом генератора 42, Если сигнал равен "1" (что означает содержимое фильтрующей зоны не пусто), осуществляется передача управления команде, следующей по порядку за выполняемой командой ПП aN, в, Если сигнал равен
"0", производится установка следующего участка сцены-копии в фи-;ьтрующую зону и анализ содержимого этого участка. Процедура прокачки через фильтрующую зону продолжается до тех пор, пока все содержи ое анализируемой сцены AN не пройдет через фильтрующую зону, после чего осуществляется передача управления команде, расположенной в памяти 16 по адресу в. Процесс перемещения сценыкопии через фильтрующую зону осуществляется с обходом отказавших процессоров
6 (подобно тому, как это делается при выполнении командь| СДВ). На фиг. 8 (1 — 6) показаны способы прокачки различных областей сцены AN (I, II, Ill) через фильтрующую зону, представляющую собой кубовую оболочку с габаритами С х С х С (С А/2), Прокачка через составной фильтр, содержащий более одной кубовой оболочки (фиг. 7, б, в), является предпочтительней, поскольку отличается большей скоростью (поверхность фильтрующей зоны в этом случае больше), При использовании составного фильтра анализу подвергается сигнал, снимаемый с выхода ступени 33. кубовые оболочки ступеней 32 которой входят в состав данного составного фильтра. В систему команд устройства входит команда ОБ aN—
"Сформировать в регистре 19 код значения величины объема нулевогс содержимого сцены AN". Команда ОБ выполняется в устройстве при помощи аналогового сумматора, состоящего из ступеней 27-29; коммутатора
53; аналого-цифровых преобразователей 30; программно-адресуемых регистров 19 и 24; арифметико-логическага узла 35. Каждая ступень 27 расположена в модуле 54 и выполнена по параллельной схеме аналогового сумматора, входы ступени 27 соединены
1689966 с инверсными выходами регистров 8 модула. Ступень 28 с целью уменьшения погрешности суммирования выполнена по последовательной схеме сумматора. входы каждой ступени 28 соединены с выходами ступеней 27 тех модулей, кубики 1 х х процессоров 6 которых образуют одну из кубовых оболочек(фиг. 3). Ступень 29 выполнена также по последовательной схеме аналогового сумматора, входы ступени 29 соединены с выходами двух или более ступеней 28. В процессе выполнения команды
ОБ aN содержимое сцены AN (если в матрице 1 отсутствуют отказавшие процессоры 6) хранящегося в регистре 21, коммутатор 53 подключает вход преобразователя 30 к выходу одной иэ ступеней 29 или 28. Например, при абсолютно исправной матрице 1 к входу преобразователя 30 подключается выход той ступени 29, входы которой соединены с выходами всех ступеней 28 устрой20 ства. С момента появления сигнала на 25 выходе элемента И 52 через временную за,держку, связанную с аналоговым суммированием, на входе преобразователя .30 поя вля ется им пул ьс, ам пл итуда которого
30 пропорциональна числу кубиков!х х I сцены AN, имеющих уровень яркости "0". Для того, чтобы данная пропорциональность соблюдалось, ступени 27, 24 процессорных модулей 54, моделирующих замкнутые (относительно 0ртогонально-кольцевых связей) системы, содержащие Е = 1, 6, 8, 12 процессоров 6, соединены с входами ступеней 28, с коэффициентом передачи по входу, равному 24/Е. В момент появления импуль40 са на выходе аналогового сумматора.начинается процесс измерения его амплитуды, по окончании которого в регистре 24 формируется код значения амплитуды импульса.
Далее этот код из регистра 24 передается в регистр 19. При наличии отказавших про45 цессоров 6 в матрице 1 вход преобразователи 30 посредством коммутатора 53 и в соответствии с кодом, хранящимся в регистре 21, соединяется с выходом той ступени
29 (или 28), все кубовые оболочки (оболочка) которой исправны и образуют в совокупности область измерения (фиг. 7; б, в, г). Вы50 полнение команды ОБ aN в этом случае начинается с обнуления регистра 19. Код значения объема нулевого содержимого сцены aN формируется в результате последовательной прокачки содержимого копии сцены AN через облать измерения. Каждый элементарный шаг прокачки включает перемещение участка копии сцены AN, предназили ON(a противном случае извлекается из 15 узлов 7 и записывается в регистры 8. В зависимости от кода режима работы матрицы, наченного для измерения его нулевого содержимого, в область измерения; извлечение О-фрагмента перемещенной сцены-копии из узлов 7 и запись извлеченного фрагмента в регистры 8; собственно измеpeeve (аналоговое суммирование кубиков ! х I х !, принадлежащих области измерения и имеющих уровень яркости "0", аналогоцифровое преобразование амплитуды импульса-результата суммирования); цифровое суммирование нового содержимого регистра 24 с содержимым регис- а 19, полученным на предыдущем шаге, и запись результата суммирования в регистр 19;
"гашение" измеренного участка (запись "1" в узлы 7 процессоров 6, чьи кубики х I x I принадлежат области измерения по адресу сцены-копии) с целью исключения иэ процесса суммирования нулевого содержимого этого у гастка в случае попадания его в область измерения при последующих шагах прокачки. Как видно иэ всего изложенного, выполнение микропрограмм, реализующих команды управления матрицей, в зависимости от содержимого регистров 21, 22 (фиг. 5), а также в зависимости от значений анализируемых признаков осуществляется по одному иэ альтернативных путей. Выбор пути происходит в результате микроветвлений, производимых в генераторе 42 адреса микрослова. Для того, чтобы выработать надлежащую последовательность микрокоманд, каждое микрослово памяти 44 содержит поле микроадреса следующего микрослояа (базовый микроадрес). Этот микроадрес при необходимости ветвления на другие микропрограммы может быть модифицирован в зависимости от состояния разрядов регистра 21, 22, от значения признаков, снимаемых с выходов мультиплексоров 34 и узла
35. С этой целью микрослово содержит поле кода микроветвления (KMB).
Формула изобретения
Устройство для параллельной обработки трехмерных сцен, содержащее блок матрицы процессоров и блок программного управления, соответствующие выходы которого соединены с входами адреса и кодов операций обмена и обработки блока матрицы процессоров, группу аналоговых сумматоров и аналого-цифровой преобразователь, выход которого соединен с соответствующим входом логических условий блока программного управления, входы аналоговых сумматоров группы соединены с выходами состояния соответствующих процессоров блока матрицы процессора, о т л и ч а ю щ е е с я тем, что, с целью повышения отказоустойчивости устройства, в блок матрицы процессоров введен узел
1689966 многовходовых элементов ИЛИ, а в устройство введены мультиплексоры признака и коммутатор, информационные входы которого соединены с выходами аналоговых сумматоров группы, а выход соединен с информационным входом аналого-цифрового преобразователя, входы узла многовходовых элементов ИЛИ соединены с выходами состояния соответствующих процессоров блока матрицы процессоров, а выходы сое- . динены с информационными входами мультиплексора признака, выход которого соединен с соответствующим входом логи5 ческих условий блока программного управления, соответствующие выходы которого соединены с управляющими входами коммутатора и мультиплексора признака состояния процессоров.
3689966
1689966
1689966
of
Z а) 1689966
1689866
1689966
1689966
1, 1
Составитель А,Ушаков
Техред M.Моргентал Корректор О.Кравцова
Редактор С.Патрушев
Производственно-издательский комбинат "Патент", г. Ужгород, ул.Га арина, 101
Заказ 3815 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
