Устройство для исследования графов

СОЮЗ СОВЕТСКИХСОЦИА ЛИСТ ИЧЕСНИХРЕСПУ БЛИН 9) (Н) 51)4 606 Г ССРРЫТИИ ИЕ ИЗОБРЕТЕНИЯ пользовано для распараллеливаниялинейных участков программ с учетоминформационных и конкуренционных связей операторов, входящих в линеиные,участки, Целью изобретения являетсяповышение быстродействия устройстваи оасширение Функциональных возможностей за счет распределения вершинграфа по рангам с учетом информационных и конкуренционных связей. Устройство для исследования графов содержит матрицуФормирователей дуг,генератор 2 тактовых импульсов, триггеры 3, -Злн формирователей дуг,заров,о С,СР 1974,СССР 1979,ВАНИЯ(54) УСТРОЙСТВО ДЛЯ ИССЛЕДГРАФОВ(57) Изобретение относитсялительной технике и может 07463 А 1130746 группу элементов ИЛИ 4 -4, группу2 иф элементов И 5 -5 группу регистрирующих счетчиков 6, -6, счетчик 7 числа импульсов, группу схем сравнения 8 - 81, Новыми являются блок 15 информационных и конкуренционных связей (БИКС), который предназначен для хранения информации о связях операторов линейного участка, первый 13 и второй14 сдвиговые регистры, предназначенные для организации просмотра матрицформирователей входных и выходныхвоздействий, элемент ИЛИ-НЕ 12, который предназначен для выработки сигнала останова генератора тактовых импульсов3 илИзобретение относится к вычислительной технике и может быть использовано для автоматического распараллеливания линейных участков программ в параллельных вычислительных системах, т.е. дпя распределения операторов линейных участков по рангам с учетом информационных и конкуренционных связей между операторами. Данная задача возникает тогда, когда вычисления ведутся над общей памятью и перемещение операторов при сборке в ярусы может вызвать конкуренцию над памятью, т.е, затирание некоторых переменных до их использования. Необходимое и достаточное условие конкуренционной зависимости между операторами А и В имеет вид:(1 пАПОцйВ)П(1 пВПОцйА)П(ОцАПОцВ)ФО, 2 Огде 1 п А - набор используемых;ОцА - набор изменяемых оператором А переменных.Если для пары операторов присутст вует это условие, то между ними вводится фиктивная связь, т.е. им не разрешается выполняться одновременно или в произвольном порядке. Программные методы выявления и устранения конкуренционных зависимостей требуют значительных затрат памяти и машинного времени.Цель изобретения - повышение быстродействия и расширение функциональ" ных возможностей устройства путем распределения вершин графа по рангам с учетом информационных и конкуренционных связей между ними,На фиг, 1 приведена структурная схема устройства; на фиг. 2 - структурная схема блока информационных и конкуренционных связей; на фиг; 3 -2пример графа и соответствующие ему матрицы входных и выходных воздействий и матрицы формирователей дуг.Устройство для исследования графов.содержит матрицу 1 формирователей дуг, генератор 2 тактовых импульсов, триггеры 3 формирователей дуг, группу элементов ИЛИ 4, группу элементов И 5, группу регистрирующих счетчиков 6, счетчик 7 числа импульсов, группу схем 8 сравнения, первый 9 и второй 10 элементы И, элемент ИЛИ 11, элемент ИЛИ-НЕ 12, первый 13 и второй 14 сдвиговые регистры, блок 15 информационных и конкуренционных связей и вторую группу элементов И 16.Блок 15 содержит матрицу 17 формирователей выходных воздействий и матрицу 18 формирователей входных воздействий, причем каждый формирователь матрицы 17 входных воздействий, кроме формирователей последней строки матрицы содержит триггер 19 и элемент И 20, а каждый формирователь матрицы 18 входных воздействий, кроме формирователей последней строки матрицы, содержит триггеры 21 и элементы И 22, кроме того, устройство содержит первую 23, вторую 24, третью 25 и шестую 26 группы элементов И, первую группу элементов ИЛИ 27, вторую группу ш-входовых элементов ИЛИ 28, группы управляющих входов 29 и 30 блока, группу информационных выходов 31 блока и вход 32 установки нуляРаботу устройства рассмотрим на примере решения задачи распараллеливания линейного участка структура которого представлена на Фиг. За, 1307463где цифрами обозначены операторы, абуквами - переменные,Первоначально в матрицы 17 и 18заносится информация о наборах переменных, изменяемых и используемых 5операторами линейного участка программы соответственно. В матрице 17формирователей выходных воздействийтриггер 19 д 3 (д=1,п; 1=1,п) устанавливается в единичное состояние втом .случае, если д-й оператор изменяет 1-ю переменную. В матрице 18 Формирователей входных воздействийтриггер 21 1 3 (=2,п; 3=1,щ) устанавливается в единичное состояние в томслучае, если д-й оператор использует 1-ю переменную. Для приведенногона фиг. За примера матрицы 17 и 18Формирователей приведены на фиг, Зб.В исходном состоянии в нулевойразряд первого сдвигового регистра13 и первый разряд второго сдвигового регистра 14 занесены единицы, Регистрирующие счетчики 6 и счетчик257 числа импульсов сброшены в нулевое состояние. Устройство начинаетработать с запуска генератора 2 повходу запуска, При этом первый импульс с генератора 2 проходит черезэлемент И 10, второй вход которогоподготовлен к работе высоким потенциалом с выхода элемента ИЛИ 11, навход которого поступает потенциальный сигнал с выхода первого разрядавторого сдвигающего регистра 14. Этот 35импульс поступает на вход сдвига первого сдвигового регистра 13 и осуществляет сдвиг единицы из нулевогоразряда в первый. Высокий потенциалс выхода этого разряда поступает через вход 29.1 в блок 15 на первыевходы элементов И 20 первой строкиматрицы 17 Формирователей выходныхвоздействий и на входы элементов И б45первой строки матрицы 1 формирователей дуг,При этом появляются высокие потенциалы на выходах тех элементовИ 20 первой строки матрицы 7 формирователей, вторые входы которыхподготовлены к работе высоким потенциалом с прямых выходов триггеров19. Эти высокие потенциалы поступаютна входы элементов И 24, другие входы которых подготовлены к работе вы 55соким потенциалом с выхода первогоразряда второго сдвигового регистра14 через вход 30,1 блока 15, Высокий потенциал с выходов элементовИ 24 поступает на вторые входы элементов И 25,На данном этапе работыустройства производится одновременное выявление информационных связейи конкуренционных связей типаОие(1,3) ПОцс (1.3)0; (ь=2,п),т.е. в триггер 3, находящийся напересечении первой строки и 1-гостолбца матрицы 1 Формирователейдуг заносится единица в том случае,если 1-й оператор изменяет ту жепеременную, что и первый оператори/или если 1.-й оператор используетпеременную, которую изменяет первыйоператор, Занесение этой информациив первую строку матрицы 1 формирователей дуг происходит одновременнодля всех операторовследующим образом.На первом этапе производится выявление конкуренционных связей.Высокие потенциалы с прямых выходов триггеров 19 3.3 1-го столбцаматрицы 17 формирователей поступаютна одни входы соответствующих -хэлементов ИЛИ 27 и далее с выходовэлементов ИЛИ 27 - на первые входысоответствующих элементов И 25, вторые входы которых подготовлены к работе высокими потенциалами с выходовэлементов И 24, С выходов 1-х элементов И 25 1-й группы высокие потенциалы поступают на входы соответствующих д-х элементов ИЛИ 28 и далеечерез группу информационных выходов31 1 блока (х=1, и) на одни входы1-х элементов И 16, другие входы которых подготовлены к работе сигналом с выхода первого разряда первогосдвигового регистра 13. Сигналы свыходов элементов И 16 устанавливают соответствующие триггеры 3 вединичное состояние,На втором этапе производится выявление информационных связей.Высокие потенциалы с прямых выходов триггеров 21 1. 3 1-го столбцаматрицы 18 входов операторов поступают на первые входы соответствующихд-х элементов И 26, вторые входыкоторых подготовлены к работе высоким потенциалом с выхода первогоразряда второго сдвигающего регистра14 через вход 30,1 блока 15, Высокиепотенциалы с выходов д-х элементовИ 26 поступают на входы соответствующих элементов И 27. Дапьнейшая1307463 работа устройства осуществляется так же, как при выявлении конкуренционных связей типаОце(1,3) П Оц с (д, 1) ФОС приходом последующих (и)-х импульсов с генератора 2 на сдвигающий вход первого сдвигового регист.ра 13 аналогичным образом осуществляется занесение информации во все остальные строки матрицы 1 формирователей дуг, При поступлении и-го импульса на вход сдвига первого сдвигового регистра 13 возникает сигнал переполнения, который осуществляет запись единицы во второй разряд первого сдвигового регистра 13 и сдвиг единицы из первого во второй разряд второго сдвигового регистра 14. При этом высокий потенциал с выхода второго разряда первого сдвигового регистра 13 поступает через вход 29,2 в блок 15 на первые входы элементов И 22 первой строки матрицы 18 формирователей входных воздействий и первые входы элементов И 20 матрицы фор мирователей 17 выходных воздействий, а также на вторые входы элементов И 16 второй строки матрицы 1 формирователей дуг, При этом появляются высокие потенциалы на выходах тех элементов И 22 первой строки матрицы 18 формирователей, одни входы которых подготовлены к работе высоким потенциалом с прямых выходов триггеров 21. Эти высокие потенциалы посту пают на одни входы соответствующих элементов И 23, другие входы которых подготовлены к работе высоким потенциалом с выхода второго разряда второго сдвигового регистра 14 через вход 302 блока 15, Высокий потенци с выходов элементов И 23 поступает на входы элементов И 25. На данном этапе работы устройства производится выявление конкуренционных связей типа1 п(2,3) ПОцй(з.,1) 0; (з.=3,п),10 20 25 30 - 35 40 45 5055 При этом в триггер 3, находящийся на пересечении второй строки и д-го столбца матрицы 1 формирователей дуг заносится единица в том случае, если -й оператор изменяет переменную, которую использует второй оператор. Занесение этой информации во вторую строку матрицы 1 формирователей дуг происходит одновременно для всех операторов следующим образом. Высокие потенциалы с прямых выходов триггеров 19 1-го столбца матрицы 17 формирователей поступают на входы соответствующих ь.-х элементов ИЛИ 27 и далее с выходов элементов ИЛИ 27 на одни входы соответствующих элементов И 25, другие входы которых подготовлены к работе высокими потенциалами с выходов элементов И 23.Дальнейшая работа устройства осуществляется так же, как при выявлении конкуренционных связей типаОцс (1,1) ПОц С (1,3)ОС приходом последующих (и)-х импульсов с генератора 2 на вход сдвига первого сдвигового регистра 13 аналогичным образом осуществляется занесение информации о конкурирующих операторах во все остальные строки матрицы 1 формирователей дуг. В результате в матрицу 1 формирователей дуг будет записана информация,представленная на фиг, 3 в,1 С приходом (и)-го импульса на вход сдвига первого сдвигового регистра 13 возникает сигнал переполнения, который осуществляет запись единицы во второй разряд первого сдвигового регистра 13 и сдвиг единицы из второго разряда в третий разряд второго сдвигового регистра 14. При этом низкие потенциалы с первого и второго разрядов второго сдвигового регистра 14 поступают на входы элемента ИЛИ 11, низкий потенциал с выхода которого поступает на второй вход элемента И 10, запрещая прохождение импульсов с,генератора 2 на вход сдвига первого сдвигового регистра 13, Кроме того, низкие потенциалы с выходов первого и второго разрядов второго сдвигового регистра через входы 30.1 и 30.2 поступают соотВетственно на первые входы элементов И 23 и 24 в результате чего на вторые входы всех элементов И 25 поступает низкий потенциал, что обеспечивает запрещение записи информации в матрицу 1 формирователей дуг, Высокий потенциал с выхода третьего разряда второго сдвигового регистра 14 поступает на второй вход первого элемента И 9, На данном этапе работы устройства осуществляется распределение операторов линейного участка программы по рангам.уже с учетом информационных и конкуренционных связей между ними, Очередной импульс1307463 40Формула изобретения с генератора 2 поступает на первый вход первого элемента И 9 и далее на вторые входы элементов И 5 и счетчик 7 числа импульсов, При этом на входы регистрирующих счетчиков 6 тех столбцов, все триггеры 3 которых находятся в нулевом состоянии, импульсы через элементы И 5 не проходят Далее содержимое регистрирующих счетчиков 6 поступает нй первые входы блоков 8 сравнения соответствующих столбцов, на второй вход которых поступает информация со счетчика 7 числа импульсов, При несовпадении показаний счетчиков 6 и 7 блок срав нения вырабатывает сигнал, который сбрасывает в нулевое состояние триггера 3 формирователей дуг строки с номером, равным номеру столбца, в блоке сравнения которого сравнение 20 не произошло. Вычислительный процесс продолжается до тех пор, пока происходит сравнения в блока: 8 сравнения. Отсутствие сигналов сравнения сви 25 детельствует о том, что все операторы линейного участка программы рас.пределены по рангам. При возникновении низкого потенциала на выходах всех блоков сравнения 8 на выходе элемента ИЛИ-НЕ 12 появляется высокий потенциал, который поступает на вход останова генератора 2. При этом генератор 2 прекращает подачу импульсов на входы элементов И 9 и 10. Число импульсов, зафиксированное на регистрирующих счетчиках 6, соответствует номеру ранга каждого оператора линейного участка программы,Устройство для исследования графов, содержащее матрицу из 1(и-и)/2+ +1, (где и - число вершин графа) фор 45мирователей дуг, каждый формирова тель дуги выполнен в виде триггера, генератор тактовых импульсов, первую группу из (и) элементов ИЛИ, первую группу элементов И, группу регистрирующих счетчиков, счетчик импульсов, группу схем сравнения, выход триггера каждого х-го формирователя дуги (=1, и) каждого 1-го столбца, кроме первого и второго столбцов (где 3=1,2и), матрицы формирователей дуг подключен к д-му входу 3-го элемента ИЛИ первой группы, выход которого подключен к гервому входу одноименного элемента И первой группы, выход каждого элемента И первой группы подключенк входу одноименного регистрирующего счетчика группы, выход которого подключен к первому входу одноименной схемы сравнения группы, выход каждой д-й схемы сравнения подключен к входу установки вОп триггера каждого формирователя дуги д-й строки матрицы формирователей дуг, вторые входы всех схем сравнения группы объединены и подключены к выходу счетчика импульсов, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей устройства путем распре- деления вершин графа по рангам с учетом информационных и конкуренционных связей между ними, в него введены первый и второй элементы И, элемент ИЛИ, элемент ИЛИ-НЕ, первый и второй сдвиговые регистры, блок формирования информационных и конкуренционных связей, в каждый формирователь дуг, кроме первого формирователя дуги первой строки матрицы формирователей дуг, введен элемент И, блок формирования информационных и конкуреиционных связей содержит первую группу из ш элементов И (где ш - количество используемых переменных), вторую группу из ш элементов И, третью группу из ш подгрупп элементов И по (и - 1)-му элементу И в каждой подгруппе, четвертую группу из ш элементов И по (и)-му элементу И в каждой подгруппе, первую группу элементов ИЛИ из ш подгрупп по (и)-му элементу ИЛИ в каждой подгруппе, вторую группу из (и) элементов ЮП 1,матрицу из и шформирователей выходных воздействий, каждый Формирователь которой, кроме формирователей последней строки,содержит триггер и элемент И, формирователи последней строки матрицы выполнены в виде триггеров, матрицу из. (и)ш формирователей входных воздействий, каждый формирователь которой, кроме формирователей последней строки, содержит триггер и элемент И,формирователи последней строки матрицы выполнены в виде триггера,причем вход установки в "1" триггера каждого формирователя дуг матрицы формирователей дуг подключен к выходу элеО мента И этого же формирователя дуг матрицы, первые входы элементов И формирователей дуг каждой -й строки матрицы формирователей дуг объединены и подключены к выходу -го разря 1307463 1 Ода первого и сдвигового регистра вторые входы элементов И формирователей дуг каждого 1-го столбца матрицы, кроме первого столбца, объединены и подключены к выходу 5-го элемента 5 ИЛИ второй группы блока формирования информационных иконкуренционных связей, вторые входы всех схем сравнения группы объединены и подключены к выходу счетчика импульсов, выход 0 каждой 1-й схемы сравнения группы подключен к 1-му входу элемента ИЛИНЕ, выход которого подключен к входу останова генератора тактовых импульсов, вход запуска которого является выходом запуска устройства, выход генератора тактовых импульсов подключен к первым входам первого и второго элементов И, выход первого элемента И подключен к счетному вхо ду счетчика импульсов и вторым входам элементов И группы, второй вход первого элемента И подключен к выходу соответствующего разряда второго сдвигового регистра, второй25 вход второго элемента И подключен к выходу элемента ИЛИ, первый и второй входы которого подключены к выходам соответствующих разрядов второго сдвигового регистра, выход второго элемента И подключен к входу сдвига первого сдвигового регистра, выход переполнения сдвигового регистра подключен к входу записи этого же сдвигового регистра и входу сдвига вто" 35 рого сдвигового регистра, выход каждого -го разряда первого сдвигового регистра подключен к первым входам элементов И формирователей выходных40 воздействий х-й строки матрицы, формирователей выходных воздействий блока формирования информационных и конкуренционных связей, кроме того, выход каждого -го разряда кроме выхоФ45 да первого разряда, первого сдвигового регистра подключен к первым входам элементов И формирователей входных воздействий (1-1)-й строки матрицы формирователей входных воздействий50 блока информационных и,конкуренционных связей, первые входы элементов И первой группы блока формирования информационных и конкуренционных свя-зей объединены и подключены к выходу55 соответствующего разряда второго сдвигового регистра, первые входы элементов И второй и четвертой групп блока формирования информационных и конкуренционных связей объединеныи подключены к выходу соответствующего разряда второго сдвигового регистра, входы установки в "1" триггеровформирователей входных воздействийматрицы и входы установки в "1" триггеров формирователей выходных воздействий матрицы блока формирования информационных и конкуренционных связейявляются группой установочных входовустройства, входы установки в "0"триггеров формирователей входных воздействий матрицы и входы установкив "0" триггеров формирователей выходных воздействий матрицы объединеныи являются входом установки нуля устройства, прямой выход триггера каждого формирователя выходных воздействий, кроме формирователей выходныхвоздействий последней строки, матрицыблока формирования информационныхи конкуренционных связей подключенык второму входу элемента И этого жеформирователя выходных воздействий,выходы элементов И всех формирователей выходных воздействий каждогоК-го столбца матрицы объединены иподключены к второму входу К-го элемента И второй группы (где 1=1,2,,щ) блока формирования информационных и конкуренционных связей,прямой выход триггера каждого 1-гоформирователя выходных воздействийкаждого К-го столбца матрицы, кромеформирователей выходных воздействий,принадлежащих первой строке матрицы,подключен к первому входу (1-1)-гоэлемента ИЛИ Е-й подгруппы первойгруппы блока формирования информационных и конкуренционных связей, второй вход каждого -го элемента ИЛИ 1-йподгруппы первой группы подключен к выходу -го элемента И 1-й подгруппы четвертой группы элемента И блока формирования информационных и конкуренционных,связей, выход каждого д-го элемента ИЛИ1-й подгруппы первой группы подключен кпервому входу -го элемента И 1-й подгруппы третьей группы блока формирования информационных и конкуренционныхсвязей, вторые входы всех элементов Икаждой К-й подгруппы третьей группы объединены и подключены к выходу Е-го элемента И второй группы блока формированияинформационных и конкуренционных связей, выход каждого 1-го элемента ИЕ-й подгруппы третьей группы подключен к 1-му входу 1-го элемента ИЛИ1 г зо 746 з 12второй группы блока формирования ин- входных воздействий каждого Е-го формационных и конкуренционных свя- столбца матрицы формирователей входзей, прямой выход триггера каждого ных воздействий объединены и подклю-го формирователя входных воздейст- чены к второму входу 1-го элемента И вий каждого -го столбца матрицыпервой группы блока формирования информирователей входных воздействий формационных и конкуренционных подключен к второму входу -го эле- связей выход каждого 1-го элемента И 1-й подгруппы с четвертой мента И первой группы подклюгруппы блока формирования информа- чен к вторым входам элементов ционных и конкуренционных связей, 10 И 1-й подгруппы четвертой груп- выходы элементов И формирователей пы.