Ассоциативный параллельный процессор

ОП ИСДН И Е аЮИФИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик, 6 061 15/О 51) М присоединением заявк Государственный комитет Совета Министров СССР не данам нвееретенийа открытий) УДК 681,325(088,8 Дата опубликования ания 09.10.7. Л. Медведев, И, В. Прангишвили и А. А. Чудин рдена Ленина институт пробл лен ИАТИВНЫЙ ПАРАЛЛЕЛЬНЫЙ ПРОЦЕССОР 54) А 2 ь ассоциатив памяти (т и памя иггера) л Изобретение относится к области вычислиельной техники и может быть использовано ля параллельной обработки массивов инфора ии. м цИзвестны ассоциативные процессоры, содержащие прямоугольную матрицу элементов ассоциативной памяти, состоящую из ряда строк и столбцов, и схему местного устройства управления, предназначенные для решения задач, описываемых групповыми арифметическими и логическими операциями над массивами пар чисел.Однако такие процессоры имеют низкую производительность и, кроме того, не обеспечивают одновременного решения задач, описываемых разными алгоритмами.Цель изобретения - повышение производительности процессора.Это достигается тем, что в процессор дополнительно введены две прямоугольные матрицы элементов ассоциативной памяти с самостоятельными входными устройствами и схемами местного устройства управления, причем шины сравнения, разрешения записи и считывания одноименных строк соседних матриц соединены между собой через ключи, а выходной регистр одной из матриц - с входом одного из введенных входных устройств,Матрицы могут работать либо независимо, выполняя одновременно в разных матрицах различные операции, например ввода обработ.ки и вывода, либо совместно, объединяясь по сигналу из внешнего устройства управления в одну матрицу большей размерности.5 Благодаря этому удается организовать поточное выполнение вычислительного процесса, динамическую перестройку связей между отдельными операторами задач, расположенными в различных участках ассоциативной 0 памяти, и выполнение различных операций вэтих участках. Схема процессора представлена на чертеже.Она содержит матрицы 11 - 1 з, состоящие изстРок 2 2 2 з, 2, элементов 3 ассоциативной памяти; местные устройства 4, - 4, управления; входные устройства 51 - 5, с регистрами опроса и записи; ключи 66,; выходной регистр 7; внешнее устройство 8 уп равления; шины 9 сравнения; шины 10 разрешения записи; шины 11 разрешения считывания; шины 12, - 12 з опроса, шины 131 - 13 з записи; шину 14 считывания; шину 15 управ.ления; вход 16 процессора.Каждая матрица 1 ь 1 з, 1 з включает в себяодинаковое число строк и определенное для каждой матрицы число столбцов элементов 3 ассоциативной памятиКаждый элемент но ти 30 имеет кроме элемента Ргические схемы, обеспечивающие запись внешней информации в триггер, считывание безразрушения информации и сравнение содержимого триггера с входной информацией. Навыходе сравнения элемента 3 вырабатываетсяединичный сигнал, если на этот разряд наложена маска, или когда информация, содержащаяся в триггере, совпадает с входной информацией, поступающей от одноименного разряда регистра опроса, входящего в составсхемы входного устройства.Выходы сравнения элементов 3 и входы разрешения записи и разрешения считывания вкаждой строке матрицы объединены общимигоризонтальными шинами сравнения 9, разрешения записи 10 и разрешения считывания11 соответственно. Строка считается выбранной, если на шине 9 сравнения этой строкипоявляется единичный сигнал.В вертикальном направлении элементы объединены в столбцы шинами опроса записи исчитывания.Работа происходит следующим образом.По шинам 121 - 13, опроса из входных устройств 51 - 5 з к элементам 3 матрицы подаетсячисло, которое содержит признак опроса, Попризнаку опроса отыскивается (выбирается)строка, содержащая этот признак, При этомиз местных устройств 41 - 4 з управления нашину разрешения записи 10 или разрешениясчитывания 11 выбранной строки поступаетединичный сигнал.Подавая по шинам опроса и записи из входного устройства в определенной последовательности микропрограммы, составленные изпризнаков опроса и кодов записи, можно выполнять групповые арифметические и логические операции параллельно над парами чисел,размещенными в отдельных строках матрицы,проводить последовательно по строкам считывание чисел из матрицы в выходной регистр 7или запись чисел из входного устройства встроки матрицы, осуществлять параллельныепересылки чисел между соседними строкамив матрице и т. д.Структурное моделирование алгоритмов решаемых задач в ассоциативной памяти проводится в два этапа,На первом этапе отдельные группы строкассоциативной памяти настраиваются на реа.лизацию заданных алгоритмов. На второмэтапе выполняется одновременное вычислениезадач в предварительно настроенных (запрограммированных) строках ассоциативной памяти.Настройка состоит из записи в отдельныестроки ассоциативной памяти признаков типавычислений, обеспечивающих реализацию вэтих строках заданного множества операций,определяемого составом алгоритма решаемойв этих строках задачи, а также из записи признаков типа связей, обеспечивающих пересылки чисел между отдельными строками матриц ассоциативной памяти или между матрицей ассоциативной памяти и внешними уст 5 1 О 15 20 25 ЗО 35 40 45 50 55 60 б 5 ройствами в соответствии с топологией связейсхем алгоритмов решаемых задач,Метод структурного моделирования алгоритмов решения задач можно проиллюстрировать на примере использования разностныхуравнений вида;у и =а,х, и - гТ (1)или формул Горнера:- +(2)Подбором коэффициентов а; через выражения (1), (2) можно вычислять интегралы,определять значение элементарных тригонометрических функций и т. д.Задачи статистической обработки данных,цифровой фильтрации случайных процессов,моделирование импульсных систем и регуляторов и многие другие задачи целиком или почастям могут быть представлены совокупностью уравнений (1) и (2).Настройка процессора, используемого длярешения задач, выраженных через уравнения(1) и (2), выполняется с учетом того обстоятельства, что матрица 1, используется дляввода массива данных, матрица 1, - для обработки, а матрица 1, - для вывода массива данных, Поэтому в каждой строке матрицы ввода выделены две зоны элементов: одна - для записи значений входных переменных, другая - для записи признаков вводаи имени входной переменной в тех строках,которые должны принять эту переменную.В каждой строке матрицы вывода такжеимеются две зоны элементов: одна для записи значений выходной переменной, другая -для записи признаков вывода и имени выходной переменной в тех строках, которыедолжны передать эту переменную,В каждой строке матрицы обработки естьнесколько зон для записи значений множителя, множимого, произведения (которое затемстановится первым слагаемым), второго слагаемого и суммы, Причем, если в )-строку всоответствующие зоны помещены коэффициент а; и переменная х;, то в соседнюю снизустроку записаны а;+, и х;+, и т. д.Кроме того, в группы строк, реализующиевыражение (1), заносится признак тип вычисления 1, а в строки, реализующие выражение (2), - признак тип вычисления О. Приэтом в крайние сверху и крайние снизу строкикаждой группы строк вводятся, признаки начала группы и конца группы, запрещающие вэтих строках прием числа от соседней сверхустроки и передачу числа в соседнюю снизустроку соответственно.Процесс вычисления задач состоит в том,что в устройстве параллельно проводятся ициклически повторяются две процедуры: процедура пересылки чисел из матрицы выводав матрицу ввода и процедура вычислений вматрице обработки. Процедура пересылок состоит в последовательном считывании вычисленных значений выходных переменных ц их имен из строк матрицы вывода, помеченных признаком вывод, чсрсз выходной регистр 7 во входное устройство 5 матрицы 1 Э. Переменная поступает в регистр записи, а ее имя - в регистр опроса входного устройства. Из входного устройства переменная переписывается за один такт в те строки матрицы ввода, в которых предварительно (в процессе настройки) было занесено цмя этой переменной.Процедура вычислений состоит из последовательного выполнения микропрограмм операций, обеспечивающих вычисление выражений (1) ц (2): умножения, сложения и пересылок между соседними строками вычисленной суммы в зону второго слагаемого для выражения (1), а затем в зону мно)кимого для выражения (2). По окончании обеих:роцедур трц соседние матрицы по сигналу, присутствующему на шине 15 и поступающему из внешнего устройства 8 управления, объединяются в одну большую матрицу ц вновь вычисленные в зоне обработки (матрица обработки) переменные переписываются в зону вывода (матрица вывода), а вновь поступившие в зону ввода (матрица ввода) переменные - в зону обработки. Затем эти процедуры вновь повторяются. Обе процедуры выполняются в ассоциативновй памяти по микропрограммам, поступающим из внешнего устройства 8 управления, через соответствующие входные устройства 5, - 5,.Каждая из микропрограмм снабжена специальными дополнительными признаками, обеспечивающими сс ьыполцспцс только в тсх строках, которые был предварительно ца нее выстроены, ц только послс того, кяк г, нцх от других строк цл 11 цзине:1 Остуцят якт:1 вныс данные. Так, например, гО окончании вычислений В кяк 011-л 1 бо строес Оораоотяппыс данные становятся цсактцвцымц, а активным результат в 1 числсп 11 который Затем псрссылается в другую, связанную зя сцст ццформации настройки, строку. Таким образом, ь раз.личных строках ассоциативной памяти реализуется данное подмножество операций и пересылок, а также автоматически обеспечивается управление процессом вычислений и его волновое распространение по цепочке связанных между собой отдельных строк.При поступлении на вход 16 устройства нового массива данных процедуры пересылок и 10 обработки временно прерываются и вновь возобновляются после ввода этого массива в матрицу ввода,Предмет изобретения15Ассоциативный параллельный процессор, содержащий входное устройство, внешнее устройство управления, местное устройство управления, выходной регистр ц матрицу эле ментов ассоциативной памяти, соответствующие входы и выходы каждого из которых соединены с местным устройством управления общцми для каждой строки шинами сравнения, разрешения записи и разрешения считы вания, с входным устройством общими длякаждого столбца шинами опроса и записи и с выходным регистром шинами считывания, о тл ц ч а ю щ п й с я тем, что, с целью повышения производительности процессора, в него допол цительно введены ключи; две матрицы элементов ассоциативной памяти, соединенные шинами сравнения, разрешения записи и разрешения считывания с соответствующими местными устройствами управления, а шинами 35 опроса и записи - с соответствующими входными устройствамц, шины сравнения, разрешсция заппсц и разрешения считывания одноименных строк соседних матриц соединены между собой через ключи, управляющие вхо ды которых подключены и выходу внешнегоустройства управленця, выход выходного регистра соединен с первым входом одного цз введенных входных устройств, второй вход которого подключен к входу процессора.Ыр г С ос и вп тель Л, 3(ср с по вактор И. Грузова Тсхред М. Семенов Корректор Е. Рогайл аказ 2486,3ЦНИИПИ одписное ппография, пр. Сапунова, 2 3 10 Изд.1649 сударственпого комптсга по делам изобретений и Москва, М(.35, Раушская