Устройство для исследования графов Советский патент 1987 года по МПК G06F15/173 

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

1

Изобретение относится к вычислительной технике и может быть использовано для автоматического распараллеливания линейных участков программ в параллельных вычислительных системах, т.е. для распределения операторов линейных участков по рангам с учетом информационных и конкуренционных связей между операторами. Данная задача возникает тогда, когда вычисления ведутся над общей памятью и перемещение операторов при сборке в ярусы может вызвать конкуренцию над памятью, т.е. затирание некоторых переменных до их использования. Необходимое и достаточное условие конку- ренционной зависимости между операторами А и В имеет вид:

(InAnOutB)U(InBnOutA)U(OutAnOutB) 0,

где In А - набор используемых;

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

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

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

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

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

S

0

5

5

0

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

Устройство для исследования графов .содержит матрицу I формирователей дуг, генератор 2 тактовых импульсов, триггеры 3 формирователей дуг, группу элементов ИЛИ 4, группу элементов И 5, группу регистрируюпщх счетчиков 6, счетчик 7 числа импульсов, группу схем 8 сравнения, первый 9 и второй 10 элементы И, элемент ИЛИ 11, элемент ИЛИ-НЕ 12, первый 13 и второй 14 сдвиговые регистры, блок 15 информационных и конкуренционных связей и вторую группу элементов И 16.

Блок 15 содержит матрицу 17 формирователей выходных воздействий и матрицу 18 формирователей входных воздействий, причем каждый формирователь матрицы 17 входных воздействий, кроме формирователей последней строки матрицы содержит триггер 19 и элемент И 20, а каждый формирователь матрицы 18 входных воздействий, кроме формирователей последней строки матрицы, содержит триггеры 21 и элементы Vi 22, кроме того, устройство содержит первую 23, вторую 24, третью 25 и шестую 26 группы элементов И, первую группу элементов ИЛИ 27, ззторую группу га-входовых элементов ШШ 28, группы управляющих входов 29 и 30 блока, группу информационных выходов 31 блока и вход 32 установки нуля.

Работу устройства рассмотрим на примере решения задачи распараллеливания линейного участка, структура которого представлена на фиг. За,

31307463

где цифрами.обозначены операторы, а буквами - переменные.

Первоначально в матрицы 17 и 18 заносится информация о наборах переменных, изменяемых и используемых операторами линейного участка программы соответственно. В матрице 17 формирователей выходных воздействий триггер 19 ij (,п; j l,ni) устанавливается в единичное состояние в том .случае, если i-й оператор изменяет ) переменную. В матрице 18 формирователей входных воздействий

Ш

ки И ме ус но и

т. пе ст ду ес пе и/ пе оп в ва дл ра

триггер 21 ij (,n; ,m) устанавf5

20

25

ливается в единичное состояние в том случае, если i-й оператор использует J-ю переменную. Для приведенного на фиг. За примера матрицы 17 и 18 формирователей приведены на фиг. Зб.

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

30

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

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

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

вого сдвигового регистра 13 и осуществляет сдвиг единицы из нулевого разряда в первый. Высокий потенциал с выхода этого разряда поступает через вход 29.1 в блок 15 на первые входы элементов И 20 первой строки матрицы 17 формирователей выходных воздействий и на входы элементов И 1 первой строки матрицы 1 формирователей дуг.

При этом появляются высокие потенциалы на выходах тех элементов И 20 первой строки матрицы 17 формирователей, вторые входы которых подготовлены к работе высоким потенциалом с прямых выходов триггеров 19. Эти высокие потенциалы поступают на входы элементов И 24, другие входы которых подготовлены к работе -высоким потенциалом с выхода первого разряда второго сдвигового регистра 14 через вход 30,1 блока 15. Высо

5

0

5

5 ствующих 1-х элементов ИЛИ 28 и далее через группу информационных выходов

0

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

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

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

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

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

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

Высокие потенциалы с прямых выходов триггеров 21 i j j-го столбца матрицы 18 входов операторов поступают на первые входы cooтвeтcтвyющJix i-x элементов И 26, вторые входы которых подготовлены к работе высоким потенциалом с выхода первого разряда второго сдвигающего регистра 14 через вход 30.1 блока 15, Высокие потенциалы с выходов i-x элементов И 26 поступают на входы соответствующих элементов ИЛ1 27. Дальнейшая

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

Out(l,j) nout (i,j)5tO .

С приходом последующих (п-2)-х импульсов с генератора 2 на сдвигающий вход первого сдвигового регистра 13 аналогичным образом осуществляется занесение информации во все остальные строки матрицы 1 формирователей дуг. При поступлении п-го импульса на вход сдвига первого .сдвигового регистра 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) nOut(i,j)iO; (,n).

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

5

0

5

0

5

0

5

5

Высокие потенциалы с прямых выходов триггеров 19 j-ro столбца мат- 17 формирователей поступают на входы соответствующих i-x элементов ИЛИ 27 и далее с выходов элементов ИЛИ 27 на одни входы соответствующих элементов И 25, другие входы которых подготовлены к работе высокими потенциалами с выходов элементов И 23. Дальнейшая работа устройства осуществляется так же, как при выявлении конкуренционных связей типа Out (I,j) nOut (i,j)tO .

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

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

С приходом (п-2)-го импульса на вход сдвига первого сдвигового регистра 13 возникает сигнал переполнения, который осуществляет запись единицы во второй разряд первого сдвигового регистра 13 и сдвиг единицы из второго разряда в третий разряд второго сдвигового регистра 14. При этом низкие потенциалы с первого и второго разрядов второго сдвигового регистра 14 поступают на входы элемента ИЛИ I1, низкий потенциал с выхода которого поступает на второй вход элемента И 10, запрещая прохождение импульсов с,генератора 2 на вход сдвига первого сдвигового регистра 13. Кроме того, низкие потенциалы с выходов первого и второго разрядов второго сдвигового регистра- через входы 30.1 и 30.2 поступают соответственно на первые входы элементов И 23 и 24 в результате чего на вторые входы всех элементов И 25 поступает низкий потенциал, что обеспечивает запрещение записи информации в матрицу 1 формирователей дуг. Высокий потенциал с выхода третьего разряда второго сдвигового регистра

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

71307463

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

8

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

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

нения вырабатывает сигнал, который сбрасывает в нулевое состояние триггера 3 формирователей дуг строки с номером, равным номеру столбца, в блоке сравнения которого сравнение не произошло. Вычислительный процесс продолжается до тех пор, пока происходит сравнения в блока:: 8 сравнения. Отсутствие сигналов сравнения свидетельствует о том, что все операторы линейного участка программы рас- -пределены по рангам. При возникновении низкого потенциала на выходах всех блоков сравнения 8 на выходе

элемента ИЛИ-НЕ 12 появляется высокий ° элементов И (где m - количество испотенциал, который поступает на входпользуемых переменных), вторую группу останова генератора 2. При этом генератор 2 прекращает подачу импульсов

на входы элементов И 9 и 10. Число импульсов, зафиксированное на регистрирующих счетчиках 6, соответствует номеру ранга каждого оператора линейного участка программы.

Формула изобретения Устройство для исследования граиз m элементов И, третью группу из m подгрупп элементов И по (п-1)-му элементу N И в каждой подгруппе,четвертую группу 35 из m элементов И по (п-1 )-му элементу И в каждой подгруппе,первую группу элементов ИЛИ из m подгрупп по (п-1)-му элементу ИЛИ в каждой подгруппе,вторую группу из Сп-1) элементов ИЛИ,матрицу из 0 П Шформирователей выходных воздействий, каждый формирователь которой,кроме формирователей последней строки,содерфов, содержащее матрицу из () жит триггер и элемент И, формирователи + 1, (где п - число вершин графа) фор- последней строки матрицы выполнены в мирователей дуг, формирова- виде триггеров,матрицу из. (п-1 )т форми- тель дуги выполнен в виде триггера, рователей входных воздействий,каждый генератор тактовых импульсов, первую формирователь которой,кроме фррмирова- группуиз (п-2) элементов ИЛИ, первую теле.й последней строки,содержит триггер группу элементов И, группу регистри- и элемент И,формирователи последней рующих счетчиков, счетчик импульсов, строки матрицы выполнены в виде тригге- группу схем сравнения, выход тригге- ра,причем вход установки в 1 триггера ра каждого i-ro формирователя дуги каждого формирователя дуг матрицы фор- () каждого j-ro столбца, кро- мирователей дуг подключен к выходу эле- ме первого и второго столбцов (где мента И этого же формирователя дуг мат- ,2,.,,,п), матрицы формирователей рицы, первые входы элементов И фор- дуг подключен к i-му входу j-ro эле- мирователей дуг каждой i-й строки мента ИЛИ первой группы, выход кото- матрицы формирователей дуг объедине- рого подключен к первому входу одно- ны и подключены к выходу i-ro разря

8

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

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

s

0

5

0

5

0

5

0

5

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

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

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

0746312

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

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

J

32 Da&.2

Фиг.З

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

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

ВНИИГШ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

а в С а

1 г 3 5 S 7 д

патрица входов

матрица SbixogoS