Матричная вычислительная система

.11.90. Бюл. й 43ститут проблем моделироетике АН УССР.Ф. Евдокимов, И.ф, Зубенкнохин и А.А, Сигарев1.325 (088.8)рбер К.Дж. Архитектура выдительных вычислительныхМ.: Наука, 1985, с, 114,нт Японии Ф 6 1-55706,6 Р 15/16, 1985.ТРИЧНАЯ ВЫЧИСЛИТЕЛЬНАЯ СИ ычиси нь вания иоср оис коро т устрой-лы,(5 ТЕ(21) 4 (22) 2 (46) 2 (71) И в энер (72) В А.Г. (53) 6 ,(56) Т произв тем.Пат СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ у/ -. РЕСПУБЛИК ТВЕННЫЙ КОМИТЕТБРЕТЕНИЯМ И ОТКРЫТИЯМ Т СССР ТОРСКОМУ СВИ(57) Изобретение относится к влительной технике и, в частноск многопроцессорным вычислителсистемам. Цель изобретения - учение быстродействия за счет упщения межпроцессорного обмена.ричная вычислительная системажит матрицу вычислительных уси запоминающих устройств размепп, В узлах главной диагоналирицы находятся вычислительныества 1, а в остальных ее узлахпоминающие устройства 2. 1 з.пИзобретение относится к вычислительной технике, в частности к многопроцессорным вычислительным системам.Цель изобретения - увеличение быстч5родеиствия системы за счет упрощениямежпроцессорного обмена.На Фиг,1 представлена схема матричной вычислительной системы: нафиг.2 - схема вычислительного устройства; на Фиг.3 - схема узла синхронизации на Фиг.4 - формат адресной команды вычислительного устройства; на Фиг.5 и 6 - форматы адреснойчасти команд обращения к запоминающим устройствам соответственно с циклом записи и циклом чтения.Матричная вычислительная системасодержит вычислительные устройства1, запоминающие устройства 2, первый 3 и второй 4 элементы И.Каждое вычислительное устройство1 содержит Формирователь 5 синхроимпульсов, узел 6 обработки, узел 7синхронизации, узел 8 формирования,маски, дешифратор 9, шинный формирователь 10.Узел 7 синхронизации содержит элемент НЕ 11, первый 12 и второй 13триггеры, первый 14 и второй 15 элементы И, третий 16 и четвертый 17триггеры, первый 18 и второй 19 элементы И-НЕ, элемент ИЛИ 20,Система команд вычислительногоустройства содержит арифметико-логические операции, операции управления, к которым отнесены операциибезусловного и условного переходов,обращение к подпрограммам и операцииввода-вывода. Для осуществления синх 40ронизации обмена в систему командывычислительного устройства введеныоперации РОБТ 1 и РОБТ 2.Для реализации единой системыадресации каждому вычислительномуустройству системы присвоен абсолютный номер, равный номеру строки(столбца) матрицы, в которой он размещается. Кроме того, для определения адресных частей команд обмена вкаждом вычислительном устройствесистемы введена внутренняя (относительная) нумерация всех остальныхвычислительных устройств системы.Относительный номер и, 1-го вычислительного устройства 1 (1, )11( Ф1, если осуществляется записьоперанда в запоминающее, устройство 2 (д,.1),где В= 2, .если запись операнда взапоминающее устройство 2 (1, 1) не производится )0 - номер ячейки запоминающегоустройства, в которую производится запись операнда.При чтении информации д-и вычислительным устройством из ячейки с номером 06 запоминающего устройства 2 (1, ) адресная часть команды опреде ляется из соотношения Р+Л А," = 2. (2. + и; - 1) +о, (3) Узел 7 синхронизации предназначен для формирования сигналов "Блокировка записи" и "Блокировка чте-1ния, длительности положительной Фазы синхроимпульсов, для Фиксации сигналов "Готовность обмена" и "Конец обмена",Узел 8 формирования маски пред-. назначен для инвертирования и передачи значений р + 1, р + 2 р + + и + 1 разрядов. адреса выборки соот- ветствующих запоминающих устройств в режиме записи информации.Работу системы рассмотрим на примере решения на ней методом простых итераций системы линейных уравнений вида КХ = ВХ + Ь, (4)где В - заданная числовая квадрат)бная матрица ш-го порядка;ЬЕК - заданный вектор (свободныйчлен) .Итерационная последовательность векторов имеет вид К К Х=ВХ+Ь(5) Пусть порядок системы линейных уравнений (4) больше числа вычисли При записи информации -м вычислительным устройством системы в запоминающие устройства адресная часть команды записи определяется из соотно- шения5 1608700ых устройств, т.е. ш ) и, тогдаый вектор можно разложить натавляющих векторов тель иско п со где Ь; Вк4(1= ш при д)1 0 при х=1, где Нтп =т 1-1 прич едовательно, решение системы нейных алгебраических уравнеожно распараллелить таким обрачтобы вычисление каждого -го ра происходило в д-м вычислитель- стройстве. Для определения полачто ш,( 2 г,и решении системы (4) каждое ычислительное устройство выполняедназначенную ему часть общесисг о алгоритма, функционир уя паьно с остальными вычислительнытройствами системы, вычисляя) том на каждом шаге итерации ш; нент вектора и обмениваясь ими ими вычислительными устройстваС(4) ний зом, вект ном гаем П3.-еет птеми ралл ми у прикомп с др мнеК рой адр т.-г абс. тло зап рой чи ной ным щиепо кХ= ; Х;=к , к-ВХ + Ь1 У- числовая матрица размерности та хщ1К - заданный вектор (свободныйчлен)ктор Х имеет компоненты Х1 с Ю)ф 1й101 М ждая ячейка запоминающего усттва имеет некоторый абсолютный с А; в адресном пространствевычйслительного устройства и лютный адрес А, - в адресном транстве 1-го вычислительного ойства.результате исполнения оператора си (БТ А 1 И) в запоминающее усттво операнд, находящийся в выительном устройстве, засыпается дресу", определяемому символичесменем А 1 Ж, Оператор одновремензаписи операнда -м вьтчислительустройством системы в запоминаю- устройства 2(д, 31)2(1,3 е) ресу А имеет вид Т ИА (, 11, 32,..,1 е) + А 5 10 15 20 25 30 35 40 45 50 55 Чтение операнда из запоминающего устройства может осуществляться под управлением любой арифметико - логической адресной команды. Например, при выполнении оператора сложения А 1 Ю ИА (3, д) + А 1-е вычислительное устройство складывает содержимое своего аккумулятора с содержимым А-й ячейки запоминающего устройства 2(т., 3) и результат помещается в аккумулятор.С выхода Формирователя 5 синхроимпульсов синхроимпульсы поступают на тактовый вход узла 7 синхронизации, Если в выполняемой операции нет обращения к запоминающим устройствам, то синхроимпульс, пройдя по цепям узла синхронизации, подается на вход синхронизации узла 6 обработки,Загрузка каждой компоненты вектора осуществляется следующим образом. На информационном входе-выходе вычислительного устройства устанавливается содержимое его аккумулятора, на выходе адреса - содержимое (р + 1) - го младшего разряда адресной части команды, на выходе маски инвертируемое содержимое (р + 1) - (р+и+1) разрядов адресной части команды, .Содержимое аккумулятора с информационного входа-выхода и адрес с выхода адреса -го вычислительного устройства поступают соответственно на информационные входы и на первые адресные входы всех запоминающих устройств 1-й строки матрицы. Каждый из разрядов инвертированного кода маски подается на второй вход записи-чтения соответствующего запоминающего устройства в -й строке матрицы. В те запоминающие устройства, на вторые входы записи-чтения которых будет подан логический нуль (активный уровень выборки), произойдет запись содержимого аккумулятора, Это позволяет в одном машинном цикле всем вычислительным устройствам системы обменяться одним операндом. После загрузки компонент вектора каждое вычислительное устройство выполняет оператор РОБТ 1, который является сигналом систем о том, что запись информации данным .вычислительным устройством в запоминающее устройство завершена. Параллельно с процессом чтения из запоминающих устройств осуществляется аппаратный анализ состояния запоминающих устройств системы и в случае неготовности запоминающихустройств для чтения цикл чтения затягивается посредством блокированияпрохождения заднего фронта синхроимпульса узлом синхронизации, т,е.реализуется режим ожидания вычисли 5тельного устройства,В цикле выполнения операции РОБТ 1каждое вычислительное устройство системы вырабатывает сигнал "Конец обмена" уровня логической единицы,который фиксируется триггером в узлесинхронизации и выдается на выходпризнака конца обмена вычислительноГО устроиства, с которОГО Он подается на один из входов элемента И 4. Заоператором РОБТ 1 может сразу последовать оператор с циклом чтения из запоминающих устройств. В общем случаесигнал "Конец обмена" вырабатывается20вычислительными устройствами не одновременно, поэтому все вычислительныеустройства, которые начали цикл чтения из запоминающих устройств до выработки последним вычислительным устройством сигнала "Конец обмена", перейдут в режим ожидания. С приходомпоследнего сигнала "Конец обмена" навыходе элемента И 4 вырабатываетсясигнал "Разрешение системного чтения"который поступает на вход признака"Разрешение системного чтения" всехвычислительных устройств системы,разблокирует прохождение отрицатель .ной Фазы синхроимпульсов, находящихся в режиме ожидания вычислительныхустройств, давая тем самым им возможность завершить чтение первой компоненты вектора и продолжить Функциони-рование.Каждое вычислительное устройствоначинает загрузкой первой компонентывектора в свой аккумулятор путем исполнения оператора45Ы) МА(3, 1) + АДопустим, что на первой итерации выполняется условие 1(Х - Х(Е, тогда вновь вычисленные компоненты вектора Х" заменяют в локальной памяти 50 вычислительного устройства компоненты вектора Х, Далее каждое вычислительное устройство выполняет операцию РОБТ 2, по завершении которой на выходе признака "Готовность обмена" устанавливается уровень логической единицы, который поступает на соответствующий вход элемента И 3. После исполнения всеми вычислительными устройствами операции РОБТ 2 на выходе элемента И 3 вырабатывается сигнал, который подается на вход призна" ка разрешения системной записи всех вычислительных устройств, Далее может выполняться оператор БТ МА (1, 3 13 е) записи в запоминающие устройства.Если даже одно из вычислительных устройств не исполнило операции РОБТ 2, то те вычислительные устройства, которые начали операцию записи информации в запоминающие устройства, перейдут в режим ожидания. Начатые операции записи завершатся ими только после исполнения последним вычислительным устройством операции РОБТ 2,После выполнения операции РОЯТ 2 цикл итерации системы (4) повторяется. После того, как на некоторой итерации будет выполнено условие завершения итераций (по достижению точности), приходит выдача результата.Узел 7 синхронизации формирует сигналы "Блокировка записи", "Конец обмена", Фиксирует сигналы "Готовность обмена", "Конец обмена", вырабатываемые в узле 6 обработки, и управляет длительностью синхроимпульсов, которые первоначально Формируются в формирователе 5 синхроимпульсоьВ процессе начальной установки триггеры 16 и 17 устанавливаются в единичное состояние, а триггеры 12 и 13 - в нулевое состояние.Триггер 16 предназначен для фиксации сигнала "Конец обмена" уровня логической единицы, который формируется узлом обработки в цикле исполнения ипструкции РОБТ 1 и подается на четвертый вход режима узла синхрони-зации и далее на информационный вход триггера 16, устанавливая его в единичное состояние. Эта единица подается на соответствующий вход элемента И 4, По приходу единичных сигналов со всех процессоров на выходе элемента И 4 вырабатывается сигнал, который поступая на вход признака разрешения системного чтения вычислительных устройств и далее на информационные входы всех триггеров 13, переводит их в единичное состояние, триггеры 17 устанавливает в нулевое состояние, Установка даже одного из триггеров 17 в нулевое состояние устанавливает на выходе элемента И 3 нулевой уровень, который переводит триггеры12нусаУР фо исетро гехолитату сии13нонаусвтавеньво 12РУ до си "стци ге ст но РУ вещи силинеад (р Р 6то с( ед .етвхховьховсех вычислительных устройств вевое состояние,Триггер 17 предназначен для фики сигнала "Готовность обмена"вня логической единицы, которыймируется узлом обработки в циклеолнения инструкции РОЯТ 2 и подая на третий вход режима узла синхизации и далее устанавливает триг О17 в единичное состояние. По приу единичных сигналов со всех вычисельных устройств на выходе элеменИ 3 вырабатывается сигнал, посая на вход признака разрешения 15темной записи всех и далее наормационные входы всех триггеровпереводит их в единичное (исход) состояние, а триггеры 16 уста-;ивает в нулевое состояние. При,ановке любого из триггеров 16улевое состояние на выходе элеменИ 3 устанавливается нулевой уроь и тригг еры 13 вс ех вычислит ельустройств устанавливаются в нулесостояние, Состояние триггеров13, 16 и 17, фиксируемое инстцией РОБТ 2 и начальной установкой,ускает обращение только для запи-,информации в запоминающие устройа, и ояращение для чтения ипформаиз них при таком состоянии тригов переводит вычислительное устройо в режим ожидания, Противоположих состояние, фиксируемое инстцией РОЯТ 1, разрешает соответст 35но чтение информации с запоминаюустройств, и обращение для запиинформации в них переводит вычисельное устройство В Режим ожидания.40В узле 6 обработки в цикле выполия любой адресной инструкции наесном выходе устанавливается+ и + 1) - разрядное значение ад-,ной части исполняемой команды. Ес 45при этом происходит обращение,значение старшего разряда адреса+ и) принимает значение, равноенице. Если адресной командой являя команда записи информации в паь, то на информационном выходеде устанавливается операнд.Единица устанавливается на вые признака конца обмена в циклеолнения инструкции РОЯТ 1 и на вые признака готовности обмена в:е выполнения инструкции РОЯТ 2.евое значение сигнала, поступаюо на вход синхронизации узла 8 фор- . мирования маски, обеспечивает инвертирование и передачу маски на еговыход.Выполнение любой инструкции состоит из выполнения последовательностимикрооперации.Выполнение каждой микроинструкции начинается с формирования синхроимпульса формирователем 5 синхроимпульсов, с выхода которого синх-роимпульс поступает на тактовый входузла 7 синхронизации. Положительнаяфаза синхроимпульса поступает наодин из входов элемента ИЛИ 20 и далее положительная фаза синхроимпульсапоступает на вход узла 6 обработки,После окончания начальной установки, когда каждое вычислительное устройство приступает к осуществлениюпервого шага итерации, первой опера-.цией обмена является инструкцияБТ МА (1, 11,,1 е) + А, при выполнении которой во время действия положительной фазы синхроимпульса обеспечивается передача операнда с информационного выхода узла 6 обработки наинформационный вход-выход вычислительного устройства, Сигнал с первого выхода узла синхронизации принимаетнулевое значение,что обеспечивает запись операнда в соответствии с адресом на выходе адреса вычислительногоблока в соответству 1 шие запоминающие устройства,По завершении операции записи взапоминающие устройства вычислительным блоком исполняется инструкция,РОБТ 1, в цикле выполнения которойустанавливается единица на выходепризнака конца обмена узла обработкикоторая устанавливает триггер 17 вединичное состояние,После выполнения вычислительнымустройством инструкции РОЯТ 1 инструкция ЯТ МА (1., 11, 1 е)++А становится запрещенной для него,так как может заблокировать подачусинхроимпульсов на узел обработки беэвозможности снятия этой блокировки.Зафиксированный триггером 16 сигнал"Конец обмена" единичного уровняпоступает на один из входов элементаИ 3, на другие входы которого поступают аналогичные сигналы от другихвычислительных устройств. Так какразличные вычислительные устройствавырабатывают такие сигналы не одновременно, то процедура исполнениялюбой инструкции с циклом чтения ин 1608 700 1250 55 формации из запоминающего устройства зависит от состояния выходов элементов И 3 и И 4.Рассмотрим выполнение инструкции ЬР МА(1, ) + А при условии, что на один из входов элемента И 4 поступает нулевой сигнал, и, следовательно, системный сигнал "Разрешение системного чтения" имеет нулевое значение, Во время действия положительной фазы синхроимпульса выход старшего разряда адреса и выход признака записи- чтения узла обработки устанавливаются в единичное состояние. Сочетание этих сигналов обеспечивает передачу операнда с информационного входа-выхода вычислительного устройства на информационный вход узла обработки с помощью шинного формирователя 10. Сигнал, формируемый элементом И 14, принимает при этом нулевое значение, а сигнал с выхода элемента И 15 принимает значение, равное единице, которое заблокирует прохождение отрицательной фазы синхроимпульсов на вход синхронизации узла обработки, до тех пор, пока триггер 13 не будет установлен в единичное состояние, Единица на выходе элемента И 4 устанавливается после исполнения последним вычислительным устройством инструкции РОБТ 1.Сигнал с входа элемента И 4 поступает на информационные входы триггеров 13 всех вычислительных устройств, устанавливает их в единичное состояние и переводит триггеры 17 в нулевое состояние, что влечет за собой установку триггеров 12 в нулевое состояние. С этого момента дешифратор 9 выбирает заданное запоминающее устройство из соответствующего столбца матрицы, считанный с него операнд поступает через шинный формирователь 10 на информационный вход узла обработки, Отрицательная фаза синхроимпульса на входе синхрониза-: ции узла обработки фиксирует операнд. в аккумуляторе узла обработки,.На этом выполнение операции завершается.После завершения чтения необходимых операндов выполняется инструкция РОБТ 2, в цикле выполнения которой устанавливается единица на выходе признака готовности обмена узла обработки, которая устанавливает триггер 17 в единичное состояние.После исполнения вычислительным уст 5 10 15 20 25 30 35 40 45 ройством инструкции РОБТ 2 любая инструкция с циклом чтения из запоминающих устройств становится запрещенной для него, так как может заблокировать подачу синхроимпульсов на узел обработки без возможности снятия этой блокировки. Таким образом, триггер 17 фиксирует сигнал "Готовиность обмена , который с его выхода поступает на один из входов элемента И 3, на другие входы которого посгтупают аналогичные сигналы от других вычислительных устройств системы, Выработка сигналов "Готовность обмена" различными вычислительными устройствами может происходить не одновременно, а потому процесс исполнения инструкции ЗТ МА(, 11 1 е)+ + А, которая может последовать после операции РОБТ 2, зависит от состояния выходов элементов И 3 и 4. Рассмотрим ее исполнение при условии, что на один из входов элемента И 3 поступает нулевой сигнал, а сигнал на выходе элемента И 3 имеет еще нулевое значение.При данном условии вычислительное устройство переводится в режим ожидания и блокируется прохождение маски через узел 8, задерживая запись с информационного входа-выхода вычислительного устройства операнда в запоминающие устройства, с которых к этому моменту может быть не считана информация, записанная на предыдущем шаге итерации. Как только сигнал на выходе элемента И 3 устанавливается в единицу, устанавливаются в единичное состояние триггеры 12 всех вычислительных устройств, триггеры 1 б устанавливаются в нулевое состояние, что влечет за собой сброс в нулевое состояние триггеров 13 всех вычислительных устройств.Формула изобретения1, Матричная вычислительная система, содержащая матрицу вычислительных устройств и запоминающих устройств размером пМп, причем в узлах главной диагонали которой находятся вычислительные устройства, а в остальных узлах матрицы находятся запоминающие устройства, о т л и ч аю щ а я с я тем, что, с целью увеличения быстродействия системы за счет упрощения межпроцессорного обме 1608700 14на, менвхо ройк воннпорипоматлитперуствтусвьус нь нькаусда ро маваэастторо элче теус обвтпониус она с од ержи т п ер вый и втор ой эл еы И, причем информационный -выход х-го вычислительного устства (где 1 = 1и) подключен ходам запоминающих устройств о столбца матрицы и к информациым входам запоминающих устройств строки матрицы выхода адреса о вычислительного устройства поден к первым адресным входам за" нающих устройств 1-й строки маты и к вторым адресным входам занающих устройств 1-го столбца ицы, выход адреса первого вычисельного устройства подключен к вым адресным входам запоминающих ойств первой строки матрицы и к рым адресным входам запоминающих ройств первого столбца матрицы, од адреса и-го вычислительного ройства подключен к первым адрес- входам запоминающих устройств строки матрицы и к вторым адрес- входам запоминающих устройств о столбца матрицы, выход выборки ала чтения- го вычислительного ройства подключен к первым вхочтения-записи запоминающих устств д-го столбца матрицы, выход ки 1-го вычислительного устройстподключен к вторым входам чтенияиси запоминающих устройств -й оки матрицы, выходы признака гоности обмена вычислительных устств подключены к входам первого. мента И, выход которого подклюк входам признака разрешениясисной записи всех вычислительных ройств, выходы признака конца ена которых подключены к входам рого элемента И, выход. которого ключен к входам признака разрешесистемного чтения всех вычислиьных устройств.2, Система по п,1, о т л и ч а- а я с я тем, что вычислительное ройство содержит формирователь синхроимпульсов, узел обработки, узелсинхронизации,дешифратор, узел Формирования маски и шинный формирова-.тель, причем вход признака разрешения системной записи и вход признака разрешения системного чтения вычислительного устройства подключенысоответственно к первому и второму 10 входам режима узла синхронизациивход тактовых импульсов которого подключен к выходу формирователя синхроимпульсов, выходы признака готовности обмена ипризнака конца обменаподключены соответственно к третьемуи четвертому входам режима узла синхронизации, с первого по пятый выходыкоторого подключены соответственнок входу синхронизации узла Формирования маски, к выходу признака готовности обмена вычислительного устройства, к выходу признака конца обменавычислительного устройства, к входусинхронизации дешифратора и к входусинхронизации узла обработки, выходпризнака записи-чтения которого подключен к пятому входу режимаузла синхронизации и к входу синхронизации шннного формирователя, информационный вход-выход которого подключен к информационному входу-выходу вычислительного устройства, выходшинного Формирователя подключен к инФормационному входу узла обработки,информационный выход которого подключен к информационному входу шинного формирователя, выход адреса узлаобработки подключен.к шестому входурежима узла синхронизации, к информационному входу узла формированиямаски, к информационному входу дешифратора, к управляющему входу шинного формирователя и к выходу адресавычислительного устройства, выходмаски и выход выборки канала чтениякоторого подключены соответственнок выходам узла формирования маски идешифратора.1608 700 Р пРфпРф 1 Р Аоресная часть йод операции фиг, Ф 1 О РпР+п1+1 Р Ном ьзод фиг.б Составитель В. Смирновор Н. Тупица Техред А.Кравчук Корректо авц 3619 ираж 56 Подписноепо изобретениям и открытиям при ГК-35 Раушская наб., д. 4/5 Государс нного комите 3035, Москва водственно-издательский комбинат "Патент", г од, ул. Гагарина, 101 Признак Обращ к запоиинающдстройстду изиак оЮр ще ьапоминающ усвройстд баскаФиг, Г Рдрес ячеакиаооминающ егодстройстда Адрес ячейкиапоиинающего дстройсшда