Устройство для оптимизации работы параллельных процессов

 

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

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

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

РЕСПУБЛИК (Я) С 06 Р 15/20

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21 ) 4395028/24-24 (22) 22.02.88 (46) 07,06.90. Бюл, ¹ 21 (72) О.Г.Алексеев, С.А.Васильковский, В.Т.Данцев и Н.И.Ячкула (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 651358, кл. С 06 G 7/122, 1977.

Авторское свидетельство СССР № 1339582, кл„ G 06 Г 15/20, 1986, (54) УСТРОЙСТВО ДЛЯ ОПТИМИЗАЦИИ РАБОТЫ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ (57) Изобретение касается цифрового моделирования и предназначено для повышения эффективности использования общих данных взаимодействующими паралИзобретение относится к цифровому моделированию и предназначено для оптимизации схемы использования общих данных взаимодействующими параллельными процессами многопроцессорных вы» числительных систем.

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

На чертеже приведена функциональная схема устройства.

Устройство содержит модель 1 графа, блок 2 управления, коммутатор 3, матрицу 4 использования данных и расчетный блок 5, „.SU„„ 344

;лельными процессами за счет определения схемы организации вычислительного процесса с общими данными, минимизирующей суммарные затраты на блокиров-ку компонент общих данных, синхронизацию работы параллельных процессов и организацию вычислительного пропе "са. Устройство содержит модель графа, блок управления, коммутатор, и;т. рицу использования данных и расчет.и .", блок. Работа устройства основана на автоматическом формировании графа, эквивалентного задаче оптимизации схемы использования общих данных, н последующем решении .этой задачи ".a счет определения кратчайшего пути в эквивалентном графе. 1 ил.

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

Модель графа содержит модели дуг

6;, j =1,n, i=j-1,п, каждая из которьж состоит из счетчика 7, элемента

И 8, диода 9, ключей 10-13 и светодиода 14.

Блок 2 управления предн аз н ачен дл:. управления работой устройства при определении кратчайшего пути в эквива- 1.-:=Ъ. лентном графе и содержит генератор 1 импульсов, счетчиков 16, клочи 17 и 18 и выключатель 19 кнопочный.

Коммутатор 3 предназначен для управления работой устройства нри фор1569844 миронании эквивалентного графа и содержит (И+1)-канальный распределитель

20 импульсов (n — число интерналов, на которое разбивается исходный про5 цесс), триггер 21, группу триггеров

22;, i=1,п, элемент И 23, группы элементов И 24,, i=2,п, элементы ИЛИ

25, ШИ 26, i=2,п, ключи 27, i

1,п"1, элемент 28 задержки, группу элементов 29, задержки, i=1,п, одно" вибраторы 30;, i=1,ï, диод 31 и выключатель 32 кнопочный.

Распределитель 20 имеет входы А, В и выходы (каналы) С;, i=1,п+1, Питание 5 подается на вход В. При поступлении на вход A i-го импульса по его переднему фронту происходит снятие напряжения С (i-1)-го выхода, а по его заднему фронту подача напряжения на 1-й выход распределителя. При поступлении на вход A (n+2)-го импульса распреде,литель возвращается в исходное состо;вше„. при котором отсутствует уровень логической единицы на всех его выхо-. дах.

Матрица 4 использования данных предназначена для задания матрицы А ,;а;-;ÿepíîñòè (n+m), элементы которой

a„" - -I, если j-я компонента использу- 30. ется на i-м интервале, и а, „ =0 в про-:".ивном случае (m число компонент . общих данных, которые могут использоваться параллельными процессами независимо, но в режиме нэаимного искжочения). Кроме того, данный блок позволяет определить поэлементную дизъюнкцию соответствующих шагу решения строк матрицы A в пгоцессе формирования эквивалентного графа. Матрица 40

3 использования данных содержит матрицу ячеек 33;„, i=1 и, j=1 m, элементы ИЛИ 34, j=1,m и группу входов

35>, j =1,m задания исходных данных, каждая ячейка блока содержит триггер

36 и элемент И 37.

Расчетный блок 5 предназначен для определения значения потерь на организацию работы с общими данными в процессе формирования эквивалентного графа. Блок 5 содержит группы регистров 38, i=1,ï, 39,, j=1 m и 40, сумматоры 41-44, блокй 45 и 46 умножения и элементы 47-49 задержки.

Работа устройства может быть раз55 делена на два этапа, На ервом осуществляется формирование графа, эквивалентного задаче оптимизации схемы использования общих данных, а на втором — решение этой задачи за счет определения кратчайшего пути в эквивалентном графе.

Перед решением, подачей импульсов на соответствующие входы групп вхо- дов 35, j=-1 m в блок 4 вводится матрица использования общих данных. При этом, если а, =1, то триггер 36 ячейки 33 „ „ переводится н единичное состояние, а если а<, =О, то триггер соЕ ответствующей ячейки остается в нулевом состоянии, В регистры 38;, i=T,п записываются значения t,, численно равные времени выполнения i-го интервала, в регистры 39,, 1=1,ш записываются значения ос„, численно равные средней стоимости использования j-й компоненты общих данных н течение единицы времени (о 1 определяется с учетом интенсивности использонания

j-й компоненты общих данных параллельными процессами), а н регистр 40 записывается значение R, численно равное затратам на организацию s --го интервала при использовании одной компоненты общих данных.

Первый цикл первого этапа работы устройства начинается кратковременным нажатием выключателя 32 кнопочного коммутатора 3, При этом напряжение от шины питания через замыкающие контакты выклочателя.32 кнопочного поступает на вход установки триггера 21, Триггер переходит н единичное состояние и сигнал уровня логической единицы поступает с его прямого выхода на такирующий вход А распределителя 20, готовя его переход в первое состояние, на объединенные входы, сброса триггера 22,, i=1,ï и нход элемента

28 задержки. Триггеры 22,, 1=1,п не находящиеся до этого момента в нулевом состоянии, переходят в него. Через время с,, необходимое для срабатывания элементов распределителя 20, сигнал с выхода элемента 28 задержки поступает на вход сброса триггера 21.

Триггер переходит н нулевое состояние, снимается сигнал высокого уровня с тактирующего входа распределителя 20 и он переходит н первое состояние, при котором сигнал уровня логической единицы присутствует на выходе (канала) С,. С выхода С< сигнал поступает на вход установки триггера 22!, а через соответствующие выход .блока 3 и вход блока 1 на объединенные четвертые входы моделей

ГВ1 Ъ% умножения значения t, Ф а и R. a, а!

° „ поступают на входы сумматора 44, Через время сд сигнал с выхода элемента и

48 задержки поступает на вход элемента 49 задержки и стробируюший вход сумматора 44, В сумматоре 44 осуществляется суммирование поступающих на

его входы величин, С выхода сумматора !

Ъ\ Ь!

44 значение S=t, c(à +R а; пос)=1,=1 тупает параллельным кодом через выход блока 5 и вход модели графа 1 на объединенные третьи входы всех моделей дуг. Так как к этому моменту времени присутствует сигнал уровня логической единицы на обоих входах элемента И 8 только модели дуги 6,, то через замкнутую информационную цепь ключа

10 значение S записывается н счетчик л

7 этой модели дуги, Через время - : сигнал с выхода элемента 49 задержки поступает на вход коммутатора 3, а с него — на перный вход элемента И

23 и объединенные входы элементов

И 74 =2,и. К этому моменту на втором входе присутствует сиг".àë высокого уровня только у элемента И 24<, На этом завершается первый шаг первого цикла решения и начинается второй, который как и последующие (и-2) аналогичен рассмотренному. Прн этом на каждом шаге б.-дет запн-"ано н счетчик 7 моделей дуг 6,!., i=2,n соответствующее значение дпин дуг эквивалентного графа. В начале и-го шага решения с выхода элемен-.à задержки 29„ сигнал поступает не только на управляющий вход ключа 27„,, вход одновибратора 30!1 и соответствующие выходы коммутатора 3, но и на второй вход элемента И 23. Поэтому по окончанию п-ro шага, при поступлении на вход коммутатора 3 сигнала с выхода элемента 49 задержки, сигнал уровня логической единицы будет присутствовать на обоих входах элемента И 23 и с выхода этого элемента сигнал через диод 31 поступит на вход установки триггера 21. На . том заканчивается первый цикл и начинается

5 156984 дуг первой строки матрицы — 6> 1

1,п. С четвертого входа этих моделей дуг сигнал поступает на один вход их элементов И 8. триггер 22 переходит в единичное состояние и сигнал с его прямого выхода поступает на вход элемента 29. задержки. Через нревремя ь сигнал с выхода элемента 29, задержки поступает. на вход элемента

И 24, на объединенные входы ячеек

ЗЗ;1, j 1 m матрицы 4 использования данных, считывающий вход регистра

38.1 блока 5, а через информационную цепь ключа 27 на пятый вход модели дуги 6, с которого он поступает на .второй .вход элемента И 8 этой модели дуги. Кроме того, сигнал с выхода элемента задержки поступает на вход одновибратора 30!. С выходов ячеек 20

33 " 1=1,m сигнал поступает на объединенные входы элементов И 37 этих ячеек. Вторые входы элементов И 37 соединены с прямыми выходами триггеров 36 и сигналы уровня логической 25 единицы с выходов элементов И 33 ячеек 33,, j =1 m, соответствующих а,„ =

j=1,m, через элементы ИЛИ 34>1, j =1 m поступают на считывающие входы регистров 391,j =1 m и информационные 30 входы сумматора 42 блока 5 (на последующих шагах решения, когда единичный сигнал присутствует на объединенных первых входах ячеек 33 11 не только первой строки матрицы 4, на выходе элементов ИЛИ 34; будут сигналы а!, соответствующие поэлементной дизъюнкции "включен ы" строк матрицы 4).

С информационнь!х выходов регистра

381 значение t, поступает на соответ- .<О ствующий вход сумматора 41, а с информационных регистров 39 1, j =1,m значения Ж а поступают на соответ,1 ствующие входы сумматора 43.

Через время задержки 1 с выхода д одновибратора 301 импульс поступает через элемент ИЛИ 26 на объединенные стробирующие входы сумматоров 41 43 и вход э;,емента 47 задержки, В сумматорах осуществляется суммирование по- 5П ступающих на их входы величин и с выхода сумматора 41 значение t, поступает на один вход блока 45 умножения, на другой вход которого поступает !

11 значение .",> с а с выхода сумматора

J 3

1=1 м

43, а значение Х а с выхода суммато-

j=! ра 42 поступает на один вход блока 46

4 6 умножения, на другой Вход которого поступает значенье и с информацноннол го выхода регистра 40. Через время 1, сигнал с выхода элемента 47 задержки поступает на стробирующпе входы блоков 45 и 46 умножения и вход элемента

48 задержки. С выходов блоков -:5 и 46

1569844 второй, который как и последующие циклы первого этапа работы устройства аналогичен. рассмотренному, Отличие заключается лишь в том что k-й цикл

В

5 состоит из (n-k+1) шагов„на каждом из которых осуществляется запись длин дуг эквивалентного графа в счетчики соответствующих моделей дуг (k-1) строки модели графа.

Таким образом, за - п(п+1) шагов этапа работы устройства будет сформирована модель графа, эквивалентного задаче оптимизации схемы использова15 ния,общих данных.

По окончании последнего шага перaoro этапа распределитель 20 перейдет в (п+1)-е состояние и на этом заканчивается первый этап работы уст20 ройства и начинается второй этап, на котором определяется кратчайший путь в полученном эквивалентном графе.

На втором этапе сигнал с выхода распределителя 20 коммутатора 3 25 поступает на управляющий вход ключа 17 блока 2 управления. Информационная цепь ключа 17 замыкается и напря,.::;ение от шины питания через замкнутую информационную цепь ключа 17 поступаВ

BT на объединенные вторые входы моделей дуг 60;,i=1,п модели графа 1, а через информационную цепь ключа 18— на вход запуска генератора 15 импуль"ов, Генератор 15 начинает вырабатывать импульсы, которые поступают на счетный вход счетчика 16, а через соответствующие выход блока управления и вход модели графа, на объединенные первые входы всех моделей дуг.

С вторых входов моделей дуг 60„, =7,n напряжение поступает на катоды светодиодов 14, а через замкнутую информационную цепь ключей 11 на управляющий вход ключей 12 этих моделей дуг. Информационные цепи ключей 12 замыкаются и через них импульсы от . генератора импульсов поступают на вычитающие входы счетчиков 7 моделей дуг 60;, =1,п. При поступлении г импульсов r=minqS ;), где S — длина

Г (О,i)-й дуги моделируемого графа, на выходе индикации нулевого состояния счетчика 7 соответствующей модели дуги, например, 6 ; появляется сигнал, который поступает на управляющий вход ключа 13, а через диод 9 на первый выход этой модели дуги и управляющий вход ключа 11. Информационная цепь ключа 11 размыкается, снимается напряжение с управляющего входа ключа 12 и прекращается поступление импульсов на счетчик 7. Так как первые выходы моделей дуг объединены по столбцам, I то аналогичным образом размыкаются информационные цепи ключей 11 и 12 всех остальных моделей дуг i-ro столбца, т ° е. будет смоделировано достижение i-й вершины графа.

Кроме того, при этом замыкается информационная цепь ключа 13 модели дуги 6 ; и напряжение поступает через светодиод 1l», информационную цепь ключа 13 и второй выход модели дуги

6, на объединеш ые вторые входы моделей дуг 6;„, j =i+1 n соответствующих дугам, исходящим из i-й вершины моделируемого графа, При этом аналогично рассмотренному начинают поступать импульсы и на счетчики 7 моделей дуг

6iJ j=i+1 n°.

Дальнейшая работа происходит таким же образом, пока наконец не появится сигнал на втором выходе одной из моделей дуг последнего столбца — 6;„, i=0,n-1. При этом составится цепь от шины питания через информационную цепь ключа 17, выход блока управления вход модели графа, вторые входы "включенных11 моделей дуг принадлежащих кратчайшему пути, через светодиод 14, информационную цепь ключа 13 и второй выход этих моделей дуг, на выход модели графа, а с него на управляющий вход ключа 18, Лрн этом "загораются" светодиоды моделей дуг, принадлежащих кратчайшему пути, размыкается информационная цепь ключа 18 и прекращается работа генератора импульсов 15.

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

Напрк ер, при числе интервалов исходного процесса п=7 и если в результате решения в кратчайший путь вошли дуги (0,3) — (3,5) — (5,7), то необходимо в один интервал для параллельной работы исходные интервалы (1,2,3); (4,5) и (6,7), Для возврата схемы в исходное состояние необходимо еще раз кратковременно нажать выключатель 32 кнопочный коммутатора 3, при том осуществляется возврат в исхоI! о-: состояние триг9 15698 геров 22;, i=1,п, а через время 7„ т возврат в нулевое состояние триггера

21 и возврат в исходное распределителя 20. Далее кратковременно нажимается выключатель 19 кнопочный блока 2 управления и напряжение от шины питания поступает на вход возврата в исходное состояние счетчика 16, а через. соответствующие выход блока 2 и вход блока 4 — на объединенные входы сброса триггеров Зб ячеек 33;, i=1 п

j--1 m, Таким образом, устройство обеспечивает как автоматическое формирование по заданным исходным данным (n, m,t;, i=1 n, c(>, j=1 m, а;, i=1 п, j= im) графа, эквивалентного задаче оптимизации схемы использования параллельными процессами общих данных, 20 так и решение этой задачи за счет определения кратчайшего пути в эквивалентном графе.

Устройство для оптимизации работы параллельных процессов, содержащее модель графа и блок управления, моцель графа состоит иэ верхней тре1 угольной матрицы из 2 (и+1) (n+2) моделей дуг, каждая из которых содержит г тадиад, ключ и счетчик (n — количество интервалов оптимизируемого

35 вычислительного процесса), блок управления содержит генератор импульсов, .".четчик и ключ, выход генератора импульсов соединен с входом счетчика и с соответствующе входом модели гра- 4Г, фа, а выход модели графа соединен с управляющим входом ключа блока управления, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет решения задач 45 оптимизации схемы использования общих данных взаимодействующими вычислительными процессами, в него введены коммутатор, содержащий (n+1)-канальный распределитель импульсов, (п+1) триггеров и элементов задержки и группу элементов задержки, элемент

И и группу элементов И, и элементов

ИЛИ, одновибраторов и (и-1) ключей, матр"ца использования д =нн i содер- Ы жащая матрицу из n g ш .чеек, каждая. .з которых состоит из триггера и элемечта И, и m элементов ИЛИ (ш — числа компонент общих данных), - также моделей дуг объединены по строкам матрицы и соединены с соответствующими выходами коммутатора, пятые входы моделей дуг объединены по столбцам матрицы и соединены с соответствующими выходами коммутатора, первый и второй выходы моделей дуг объединены по столбцам матрицы модели графа, а вторые выходы моделей дуг последне1 о столбца матрицы объединены и соеди .;;. ны с выходом модели графа, причем коммутаторе первый выхоц распр дели" теля импульсов соединен с входом установки первого триггера группы ð;.ãгеров и соответствующ,1м выходом ка:-.— мутатора, (и+1)-й выход расгрецелптеля импульсов соединен с входам приФормула изобретения

44 l0 расчетный блок, содержащий (m+n+i) регистров, четыре сумматора, два блока умножения и три элемента задержки, кроме того, в каждую модель дуги модели графа, введены три ключа, элемент ИЛИ и диод, причем первый вход модели дуги соедч".åí через информационную цепь первого ключа с вычитающпк входом счетчика, управляющий вход первого ключа соединен через информационную цепь второго ключа с вторым входом модели дуги, который соединен и с катодом светодиода, вычитающнй вход счетчика соединен через информационную цегь третьего ключа с третьи:. входам модели дуги, четвертый и пятый входы которой соединены с саатзетствующими входами элемента И, выход элемента И соединен с управляющим входом третьего кгпоча, выход сигнализации à нулевом состоянии счетчика соединен с катодом диода и управляющим входом четвертого ключа, анод диода соединен с управляющим ьхадом второго ключа и первым выходом модел .." дуги, второй выход которой соединен через информационную цепь четвертого ключа с анодом светодиода, первые входы всех моделей дуг абъединень1 и соединены с выходом тактиравания блока управления, вторые входы моделей дуг объединены па строкам ма грицы модели графа и соединены с вторым выходом модели дуги соответственно

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

11

15б98 знака йзменения режйма блока управления, с второго по п-,é выходы распределителя импульсов соединены с первыми.входами .соответствующих элементов

ИЛИ, вторые входы которых подключены

5 к .выходам элемейтав И группы, а выходы соединены с входами установки соответствующих триггеров .группы, прямые выходы которых соединены с входагm соответствующих элементов задержки группы, выходы элементов задержки группы соединены с соответствующими выходами коммутатора, входами соот ветствующих одновибратаров, первыми входами соответствующих элементов И группы, и через информационные цепи ключей — с соответствующими выходами коммутатора, вторые входы элементов

И группы объединены и соединены с 29, выходом признака готовности расчетнога блока, элемент И соединен через диод с входом установки триггера, .":аторый через замыкающие контакты выключателя кнопочного соединен с 25

ыинай питания, прямой выход триггера с.аединен с входам элемента задержки и объединенными входамй сброса триг е. ;а;: группы, выход элемента задержки .с -.динен с входом сброса триггера, ЗО ,з ..правляющие входы кгпочей соединены с выхалами соответственно последующих зл-.ментов задержки группы, причем в матрице использования данных первые входы всех ячеек матрицы использовазия данных, соединенные с первыми вхацами элементбв И этих ячеек, объеинены па строкам матрицы и соединены с соответствующими выходами коммутаторов, которые соединены и с. соответствующими входами расчетного блока, вторые входы ячеек„ соединенные с входами сброса их триггеров, объе 12 динены у всех ячеек матрицы и соединены с выходом запуска блока .управления, входы установки триггеров соединены с соответствующими входами матрицы использования данных, а их прямые выходы подключены к входам элементов И Выходы которых являются выходами ячеек и соединены с входами соответствующих элементов ИЛИ, выходы элементов ИЛИ соединены с входами расчетного блока, к которым подключены входы второго сумматора и считывающие входы группы из m регистров, причем в расчетном блоке выходы m регистров подключены к входам третьего сумматора, а считывающие входы группы из и регистров соединены с соответствующими входами расчетного блока, выходы этих регистров соединены с входами первого сумматора, страбирующие входы первого, второго и третьего сумматоров объединены с входам первого элемента задержки и соединены со стробирующим входом расчетного блока, выходы первого и третьего сумматоров соединены с входами первого блока умножения, а входы второго блока умножения подключены к выходу второго сумматора и выходу соответствующего регистра, выход первого элемента задержки соединен с входом второго элемента задержки и стробирующими входами блоков умножения, выходы которых соединены с входами четвертаго сумматора, стробирующий вход которого соединен с выходом второго элемента задержки и с входом третьего элемента задержки, выход четвертого сумматора соединен с выходом расчетного блока, с выходом признака готовности которого соединен выход третьего элемента задержки.

i -jA,0044

Составитель А.ушаков

Редактор Л.Зайцева Техред М.Ходанич Корректор С Шевкун

Заказ 1451 Тираж 570 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101