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

 

Изобретение относится к вычислительной технике и может быть использовано для распараллеливания линейных участков программ с учетом информационных и конкуренционных связей операторов, входящих в линейные , участки. Целью изобретения является повьшение быстродействия устройства и расширение функциональных возможностей за счет распределения вершин графа tio рангам с учетом информационных и конкуренционных связей. Устройство для исследования графов содержит матрицу 1 формирователей дуг, генератор 2 тактовых импульсов, триггеры 3 -З/гп формирователей дуг. (Л с оо о 4 Oi СО

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3946299/24-24 (22) 21.08.85 (46) 30.04.87. Бюл. Ф 16 (72) И.Н. Швыркин, С.В. Назаров, В.И. Сущев и А.А. Примаков (53) 681.333(088.8) (56) Авторское свидетельство СССР

В 526954, кл. С 06 F 15/20, 1974, Авторское свидетельство СССР

11 716043, кл. С 06 F 15/20, 1979. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть исЛ, 1 07463 А1 пользовано для распараллеливания линейных участков программ с учетом информационных и конкуренционных связей операторов, входящих в линеиные, участки. Целью изобретения является повышение быстродействия устройства и расширение функциональных возможностей за счет распределения вершин графа по рангам с учетом информационных и конкуренционных связей. Устройство для исследования графов содержит матрицу формирователей дуг, генератор 2 тактовых импульсов, триггеры 3« -З н формирователей дуг, 130746 группу элементов ИЛИ 4 -4 „, группу

2и элементов И 51 -5„ группу регистрирующих счетчиков 6, -6„, счетчик 7 числа импульсов, группу схем сравнения 8 —

8 . Новыми являются блок 15 информационных и конкуренционных связей (БИКС), который предназначен для хранения информации о связях операторов линейного участка, первый 13 и второй

14 сдвиговые регистры, предназначенные для организации просмотра матриц формирователей входных и выходных воздействий, элемент ИЛИ-НЕ 12, который предназначен для выработки сигнала останова генератора тактовых импульсов. 3 ил, !

Изобретение относится к вычислительной технике и может быть использовано для автоматического распараллеливания линейных участков программ в параллельных вычислительных системах, т.е. дпя распределения операторов линейных участков по рангам с учетом информационных и конкуренционных связей между операторами. Данная задача возникает тогда, когда вычисления ведутся над общей памятью и перемещение операторов при сборке в ярусы может вызвать конкуренцию над памятью, т.е, затирание некоторых переменных до их использования. Необходимое и достаточное условие конкуренционной зависимости между операторами А и B имеет вид: (InA11OutB)U(InBIIOutA)U(OutAII0utB)ф0, 29 где In А — набор используемых;

Ou t А — набор изменяемых оператором А переменных.

Если для пары операторов присутст- 5 вует это условие, то между ними вводится фиктивная связь, т.е. им не разрешается выполняться одновременно или в произвольном порядке. Программные методы выявления и устранения конкуренционных зависимостей требуют значительных затрат памяти и машинного времени.

Цель изобретения — повышение быстродействия и расширение функциональ" ных возможностей устройства путем распределения вершин графа по рангам. с учетом информационных и конкуренционных связей между ними.

На фиг, 1 приведена структурная схема устройства; на фиг. 2 — структурная схема блока информационных и конкуренционных связей; на фиг: 3—

2 пример графа и соответствующие ему матрицы входных и выходных воздействий и матрицы формирователей дуг.

Устройство для исследования графов.содержит матрицу 1 формирователей дуг, генератор 2 тактовых импульсов, триггеры 3 формирователей дуг, группу элементов ИЛИ 4, группу элементов И 5, группу регистрирующих счетчиков 6,. счетчик 7 числа импульсов, группу схем 8 сравнения, первый

9 и второй 10 элементы И, элемент

ИЛИ ll элемент ИЛИ-НЕ 12, первый

1I3 и второй 14 сдвиговые регистры, блок 15 информационных и конкуренционных связей и вторую группу элементов И 16.

Блок 15 содержит матрицу 17 формирователей выходных воздействий и матрицу 18 формирователей входных воздействий, причем каждый формирователь матрицы 17 входных воздействий, кроме формирователей последней строки матрицы содержит триггер 19 и элемент И 20, а каждый формирователь матрицы 18 входных воздействий, кроме формирователей последней строки матрицы, содержит триггеры 21 и элементы И 22, кроме того, устройство содержит первую 23, вторую 24, третью 25 и шестую 26 группы элементов

И, первую группу элементов ИЛИ 27, вторую группу ш-входовых элементов

ИЛИ 28, группы управляющих входов 29 и 30 блока, группу информационных выходов 31 блока и вход 32 установки нуля °

Работу устройства рассмотрим на примере решения задачи распараллеливания линейного участка„ структура которого представлена на Фиг. 3а, 1307463 где цифрами. обозначены операторы, а буквами — переменные.

Первоначально в матрицы 17 и 18 заносится информация о наборах переменных, изменяемых и используемых 5 операторами линейного участка программы соответственно. В матрице 17 формирователей выходных воздействий триггер 19 i j (i=1,n; j=l,m) устанавливается в единичное состояние в том .случае, если i-й оператор изменяет j-ю переменную. В матрице 18 формирователей входных воздействий триггер 21 i j (i=2,n; j=l,m) устанавливается в единичное состояние в том случае, если i-й оператор использует 1-ю переменную. Для приведенного на фиг. За примера матрицы 17 и 18 формирователей приведены на фиг. Зб.

В исходном состоянии в нулевой разряд первого сдвигового регистра

13 и первый разряд второго сдвигового регистра 14 занесены единицы. Регистрирующие счетчики 6 и счетчик ! 2с

7 числа импульсов сброшены в нулевое состояние. Устройство начинает работать с запуска генератора 2 по входу запуска. При этом первый импульс с генератора 2 проходит через элемент И 10, второй вход которого подготовлен к работе высоким потенциалом с выхода элемента ИЛИ 11, на вход которого поступает потенциальный сигнал с выхода первого разряда второго сдвигающего регистра 14. Этот35 импульс поступает на вход сдвига первого сдвигового регистра 13 и осуществляет сдвиг единицы из нулевого разряда в первый. Высокий потенциал с выхода этого разряда поступает через вход 29.1 в блок 15 на первые входы элементов И 20 первой строки матрицы 17 формирователей выходных воздействий и на входы элементов И 16

Д первой строки матрицы 1 формирователей дуг, При этом появляются высокие потенциалы на выходах тех элементов

И 20 первой строки матрицы 17 формирователей, вторые входы которых подготовлены к работе высоким потенциалом с прямых выходов триггеров

19. Эти высокие потенциалы поступают на входы элементов И 24, другие входы которых подготовлены к работе .вы55 соким потенциалом с выхода первого разряда второго сдвигового регистра

14 через вход 30.1 блока 15. Высокий потенциал с выходов элементов

И 24 поступает на вторые входы элементов И 25. На данном этапе работы устройства производится одновременное выявление информационных связей и конкуренционных связей типа

Out(I,j) IIOut (i.j)ф0; (i=2,п}, т.е. в триггер 3, находящийся на пересечении первой строки и i-ro столбца матрицы 1 формирователей дуг заносится единица в том случае, если i-й оператор изменяет ту же переменную, что и первый оператор и/или если i-й оператор использует переменную, которую изменяет первый оператор, Занесение этой информации в первую строку матрицы 1 формирователей дуг происходит одновременно для всех операторов i следующим образом.

На первом этапе производится выявление конкуренционных связей.

Высокие потенциалы с прямых выходов триггеров 19 ij j-го столбца матрицы 17 формирователей поступают на одни входы соответствующих i-x элементов ИЛИ 27 и далее с выходов элементов ИЛИ 27 — на первые входы соответствующих элементов И 25, вторые входы которых подготовлены к работе высокими потенциалами с выходов элементов И 24. С выходов i-x элементов И 25 j-й группы высокие потенциалы поступают на входы соответствующих i-х элементов ИЛИ 28 и далее через группу информационных выходов

31 i блока (i-=l, и-1) на одни входы

i-x элементов И 16, другие входы которых подготовлены к работе сигналом с выхода первого разряда первого сдвигового регистра 13. Сигналы с выходов элементов И 16 устанавливают соответствующие триггеры 3 в единичное состояние.

На втором этапе производится выявление информационных связей.

Высокие потенциалы с прямых выходов триггеров 21 1 1 j-го столбца матрицы 18 входов операторов поступают на первые входы соответствующих

i-х элементов И 26, вторые входы которых подготовлены к работе высоким потенциалом с выхода первого разряда второго сдвигающего регистра

14 через вход 30.1 блока 15. Высокие потенциалы с выходов i-x элементов

И 26 поступают на входы соответствующих элементов ИЛ11 27. Дапьнейшая

1307463 работа устройства осуществляется так же, как при выявлении конкуренционных связей типа

Out (l, j ) II Ou t (i, j ) O °

С приходом последующих (n-2)-х импульсов с генератора 2 на сдвигающий вход первого сдвигового регист.ра 13 аналогичным образом осуществляется занесение информации во все остальные строки матрицы 1 формирователей дуг. При поступлении n-ro импульса на вход сдвига первого сдвигового регистра 13 возникает сигнал переполнения, который осуществляет запись единицы во второй разряд первого сдвигового регистра 13 и сдвиг единицы из первого во второй разряд второго сдвигового регистра 14. При этом высокий потенциал с выхода второго разряда первого сдвигового регистра 13 поступает через вход 29.2 в блок 15 на первые входы элементов

И 22 первой строки матрицы 18 формирователей входных воздействий и первые входы элементов И 20 матрицы фор мирователей 17 выходных воздействий, а также на вторые входы элементов

И 16 второй строки матрицы 1 формирователей дуг. При этом появляются высокие потенциалы на выходах тех элементов И 22 первой строки матрицы 18 формирователей, одни входы которых подготовлены к работе высоким потенциалом с прямых выходов триггеров 21. Эти высокие потенциалы посту пают на одни входы соответствующих элементов И 23, другие входы которых подготовлены к работе высоким потенциалом с выхода второго разряда второго сдвигового регистра 14 через вход 30 ° 2 блока 15, Высокий потенци с выходов элементов И 23 поступает на входы элементов И 25. На данном этапе работы устройства производится выявление конкуренционных связей типа

In(2,j) IIOut(i,j)$0; (э=3,п).

20

При этом в триггер 3, находящийся на пересечении второй строки и i-ro столбца матрицы 1 формирователей дуг заносится единица в том случае, если i-й оператор изменяет переменную, которую использует второй оператор. Занесение этой информации во вторую строку матрицы 1 формирователей дуг происходит одновременно для всех операторов следующим образом.

30 — 35

Высокие потенциалы с прямых выходов триггеров 19 j-ro столбца матрицы 17 формирователей поступают на входы соответствующих i-х элементов

ИЛИ 27 и далее с выходов элементов

ИЛИ 27 на одни входы соответствующих элементов И 25, другие входы которых подготовлены к работе высокими потенциалами с выходов элементов И 23.

Дальнейшая работа устройства осуществляется так же, как при выявлении конкуренционных связей типа

Ou t (I,j) 1lOu t (i,j)$0 .

С приходом последующих (n-3)-х импульсов с генератора 2 на вход сдвига первого сдвигового регистра

13 аналогичным образом осуществляется занесение информации о конкурирующих операторах во все остальные строки матрицы 1 формирователей дуг.

В результате в матрицу 1 формирователей дуг будет записана информация, представленная на фиг, 3в.

С приходом (n-2)-ro импульса на вход сдвига первого сдвигового регистра 13 возникает сигнал переполнения, который осуществляет запись единицы во второй разряд первого сдвигового регистра 13 и сдвиг единицы из второго разряда в третий разряд второго сдвигового регистра

14. При этом низкие потенциалы с первого и второго разрядов второго сдвигового регистра 14 поступают на входы элемента ИЛИ 11, низкий потенциал с выхода которого поступает на второй вход элемента И 10, запрещая прохождение импульсов с.генератора

2 на вход сдвига первого сдвигового регистра 13. Кроме того, низкие потенциалы с выходов первого и второго разрядов второго сдвигового регистра. через входы 30.1 и 30.2 поступают соответственно на первые входы элементов И 23 и 24 в результате чего на вторые входы всех элементов И 25 поступает низкий потенциал, что обеспечивает запрещение записи информации в матрицу 1 формирователей дуг.

Высокий потенциал с выхода третьего разряда второго сдвигового регистра

14 поступает на второй вход первого элемента И 9. На данном этапе работы устройства осуществляется распределение операторов линейного участка программы по рангам.уже с учетом информационных и конкуренционных связей между ними. Очередной импульс

1307463 с генератора 2 поступает на первый вход первого элемента И 9 и далее на вторые входы элементов И 5 и счетчик 7 числа импульсов. При этом на входы регистрирующих счетчиков 6 тех столбцов, все триггеры 3 которых находятся в нулевом состоянии, импульсы через элементы И 5 не проходят..

Далее содержимое регистрирующих счетчиков 6 поступает нй первые входы блоков 8 сравнения соответствующих столбцов, на второй вход которых поступает информация со счетчика 7 числа импульсов. При несовпадении показаний счетчиков 6 и 7 блок срав- 15 нения вырабатывает сигнал, который сбрасывает в нулевое состояние триггера 3 формирователей дуг строки с номером, равным номеру столбца, в блоке сравнения которого сравнение 20 не произошло. Вычислительный процесс продолжается до тех пор, пока происходит сравнения в блока-.. 8 сравнения.

Отсутствие сигналов сравнения сви25 детельствует о том, что все операторы линейного участка программы распределены по рангам. При возникновении низкого потенциала на выходах всех блоков сравнения 8 на выходе элемента ИЛИ-НЕ 12 появляется высокий потенциал, который поступает на вход останова генератора 2. При этом генератор 2 прекращает подачу импульсов на входы элементов И 9 и 10. Число импульсов, зафиксированное на регистрирующих счетчиках 6, соответствует номеру ранга каждого оператора линейного участка программы.

Формул а и з о бр е т ения

Устройство для исследования графов, содержащее матрицу из P(n -n)/2)+

+1, (где n — число вершин графа) фор45 мирователей дуг, каждый формирователь дуги выполнен в виде триггера, генератор тактовых импульсов, первую группу из (и-2) элементов ИЛИ, первую группу элементов И, группу регистрирующих счетчиков, счетчик импульсов, группу схем сравнения, выход триггера каждого i-ro формирователя дуги (i=1, n-1) каждого j-го столбца, кроме первого и второго столбцов (где

)=1,2,...,n), матрицы формирователей дуг подключен к i-му входу j-го элемента ИЛИ первой группы, выход которого подключен к гервому входу одноименного элемента И первой группы, выход каждого элемента И первой группы подключен к входу одноименного регистрирующего счетчика группы, выход которого подключен к первому входу одноименной схемы сравнения группы, выход каждой i-й схемы сравнения подключен к входу установки в 0 триггера каждого формирователя дуги i-й строки матрицы формирователей дуг, вторые входы всех схем сравнения группы объединены и подключены к выходу счетчика импульсов, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей устройства путем распре деления вершин графа по рангам с учетом информационных и конкуренционных связей между ними, в .него введены первый и второй элементы И, элемент

ИЛИ, элемент ИЛИ-НЕ, первый и второй сдвиговые регистры, блок формирования информационных и конкуренционных связей, в каждый формирователь дуг, кроме первого формирователя дуги первой строки матрицы формирователей дуг, введен элемент И, блок формирования информационных и конкуреиционных связей содержит первую группу из

m элементов И (где m — количество используемых переменных), вторую группу из m элементов И, третью группу из m подгрупп элементов И по (n — 1 )-му элементу

И в каждой подгруппе, четвертую группу из m элементов И по (n-1)-му элементу И в каждой подгруппе, первую группу элементов ИЛИ из m подгрупп по (n-1)-му элементу ИЛИ в каждой подгруппе, вторую группу из (n-1) элементов ЮП1,матрицу из и тформирователей выходных воздействий, каждый формирователь которой, кроме формирователей последней строки,содержит триггер и элемент И, формирователи последней строки матрицы выполнены в виде триггеров, матрицу из. (и-1)m формирователей входных воздействий, каждый формирователь которой, кроме фррмирователей последней строки, содержит триггер и элемент И,формирователи последней строки матрицы выполнены в виде триггера,причем вход установки в "1" триггера каждого формирователя дуг матрицы формирователей дуг подключен к выходу элеО мента И этого же формирователя дуг матрицы, первые входы элементов И формирователей дуг каждой i-й строки матрицы формирователей дуг объединены и подключены к выходу i-ro разря1307463

10 да первого и сдвигового регистра вторые входы элементов И формирователей дуг каждого j-ro столбца матрицы, кроме первого столбца, объединены и подключены к выходу )-ro элемента 5

ИЛИ второй группы блока формирования информационных иконкуренционных связей, вторые входы всех схем сравнения группы объединены и подключены к выходу счетчика импульсов, выход ®0 каждой j-й схемы сравнения группы подключен к j-му входу элемента ИЛИНЕ, выход которого подключен к входу останова генератора тактовых импульсов, вход запуска которого является выходом запуска устройства, выход генератора тактовых импульсов подключен к первым входам первого и второго элементов И, выход первого элемента И подключен к счетному входу счетчика импульсов и вторым входам элементов И группы, второй вход первого элемента И подключен к выходу соответствующего разряда второго сдвигового регистра, второй

25 вход второго элемента И подключен к выходу элемента ИЛИ, первый и второй входы которого подключены к выходам соответствующих разрядов второго сдвигового регистра, выход второго элемента И подключен к входу сдвига первого сдвигового регистра, выход переполнения сдвигового регистра подключен к входу записи этого же сдвигового регистра и входу сдвига вто- 35 рого сдвигового регистра, выход каждого i-го разряда первого сдвигового регистра подключен к первым входам элементов И формирователей выходных

40 воздействий i-й строки матрицы, формирователей выходных воздействий блока формирования информационных и конкуренционных связей, кроме того, выход каждого i-го разряда кроме выхоФ

45 да первого разряда, первого сдвигового регистра подключен к первым входам элементов И формирователей входных воздействий (i-i)-й строки матрицы формирователей входных воздействий

50 блока информационных и,конкуренционных связей, первые входы элементов И первой группы блока формирования информационных и конкуренционных свя-зей объединены и подключены к выходу

55 соответствующего разряда второго сдвигового регистра, первые входы элементов И второй и четвертой групп блока формирования информационных и конкуренционных связей объединены и подключены к выходу соответствующего разряда второго сдвигового регистра, входы установки в "1" триггеров формирователей входных воздействий матрицы и входы установки в "1" триггеров формирователей выходных воздействий матрицы блока формирования информационных и конкуренционных связей являются группой установочных входов устройства, входы установки в "0" триггеров формирователей входных воздействий матрицы и входы установки в "0" триггеров формирователей выходных воздействий матрицы объединены и являются входом установки нуля устройства, прямой выход триггера каждого формирователя выходных воздействий, кроме формирователей выходных воздействий последней строки, матрицы блока формирования информационных и конкуренционных связей подключены к второму входу элемента И этого же формирователя выходных воздействий, выходы элементов И всех формирователей выходных воздействий каждого

k-ro столбца матрицы объединены и подключены к второму входу k-ro элемента И второй группы (где k=1,2, ...,m) блока формирования информационных и конкуренционных связей, прямой выход триггера каждого j-ro формирователя выходных воздействий к.".ждого k-ro столбца матрицы, кроме формирователей выходных воздействий, принадлежащих первой строке матрицы, подключен к первому входу (j-1)-ro элемента ИЛИ k-й подгруппы первой группы блока формирования информационных и конкуренционных связей, второй вход каждого i-го элемента ИЛИ k-й подгруппы первой группы подключен к выходу i-ro элемента И k-й подгруппы четвертой группы элемента И блока формирования информационных и конкуренционных. связей, выход каждого i-го элемента ИЛИ

k-й подгруппы первой группы подключен к первому входу i-го элемента И k-й подгруппы третьей группы блока формирования информационных и конкуренционных связей, вторые входы всех элементов И каждой k-й подгруппы третьей группы объединены и подключены к выходу k-го элемента И второй группы блока формирования информационных и конкуренционных связей, выход каждого д-ro элемента И

k-й подгруппы третьей группы подключен к k-му входу i-ro элемента ИЛИ

ll 1 307463 12 второй группы блока формирования ин- входных воздействий каждого k-ro формационных и конкуренционных свя- столбца матрицы формирователей входзей, прямой выход триггера каждого ных воздействий объединены и подклюi-ro формирователя входных воздейст- чены к второму входу k-ro элемента И вий каждого i-го столбца матрицы 5 первой группы блока формирования информирователей входных воздействий формационных и конкуренционных подключен к второму входу i-го эле- связей выход каждого k-го элемента И k-й подгруппы с четвертой мента И первой группы подклюгруппы блока формирования информа- чен к вторым входам элементов ционных и конкуренционных связей, о И k — и подгруппы четвертой групвыходы элементов И формирователей пы.

1307463

12 Ю 41 Ю7ä а Юсб

2 д

Ю

В

7 д иатроаа йчадоФ

П7тРида ЮЮдОУ

128 45 6 78

Составитель Т. Сапунова

Редактор Л. Пчолинская Техред Л.Олейник Корректор А. Ильин

Заказ 1634/49 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4