Изобретение относится к цифровому моделированию и предназначено для оптимизации схемы использования общих данных взаимодействующими параллельными процессами многопроцессорных вычислительных систем.
Цель изобретения - расширение функциональных возможностей устройства за счет решения задач оптимизации схемы использования общих данных взаимодействующими вычислительными процессами.
На чертеже приведена функциональная схема устройства.
Устройство содержит модель 1 графа, блок 2 управления, коммутатор 3, матрицу 4 использования данных и расчетный блок 5.
Модель 1 графа предназначена для задания топологии и весов дуг графа, эквивалентного задаче оптимизации схемы использования общих данных. Модель графа содержит модели дуг 6;:, j 1 ,n, ,n, каждая из кот - рых состоит из счетчика 7, элемента И 8, диода 9, ключей 10-13 и свето- диода 14.
I
Блок 2 управления предназначен дл управления работой устройства при определении кратчайшего пути в эквивалентном графе и содержит генератор Г импульсов, счетчиков 16, ключи 17 и 18 и выключатель 19 кнопочный.
Коммутатор 3 предназначен для управления работой устройства при cKv
СЛ
О5
СЈ оо
4Ь
Ј
i X
мированин эквивалентного графа и содержит (fl+1)-канальный распределитель 20 импульсов (п - число интервалов, на которое разбивается исходный процесс), триггер 21, группу триггеров 22;, ,n, элемент И 23, группы элементов И 24;, , элементы ИЛИ 25; t Ш1И 26, i 27n ключи 27Ц , i в 1,п-1, элемент 28 задержки, группу элементов 29, задержки, 1 1,п, одно- вибраторы 30;, ,п, диод 31 и выключатель 32 кнопочный.
Распределитель 20 имеет входы А, В и выходы (каналы) Cj, ,п+1. Питани подается на вход В. При поступлении на вход Л 1-го импульса по его переднему фронту происходит снятие напряжения С (i-1)-го выхода, а по его заднему фронту подача напряжения на 1-й выход распределителя. При поступлении на вход Л (п+2)-го импульса распределитель возвращается в исходное состо- чнне, при котором отсутствует уровень ьогичегкой единицы на всех его выходах.
Матрица 4 использования данных предназначена для задания матрицы А л-чмерности (n+m), элементы которой а;: -1, если j-я компонента использу- ется на i-м интервале, и а;. 0 в противном случае (т число компонент . общих данных, которые могут использоваться параллельными процессами независимо, но в режиме взаимного исключения). Кроме того, данный блок позволяет определить поэлементную дизъюнкцию соответствующих шагу решения строк матрицы А в процессе формирования эквивалентного графа. Матрица 3 использования данных содержит матрицу ячеек 33;: , ,n, j 1,m, элементы ИЛИ 34, , j 1,m и группу входов 351, ,m задания исходных данных, каждая ячейка блока содержит триггер 36 и элемент И 37.
Расчетный блок 5 предназначен для определения значения потерь на организацию работы с общими данными в процессе формирования эквивалентного графа. Блок 5 содержит группы регистров 38;, ,n, 39j, ,m и 40, сумматоры 41-44, блоки 45 и 46 умножения и элементы 47-49 задержки.
Работа устройства может быть разделена на два этапа.
На первом осуществляется формирование графа, эквивалентного задаче оптимизации схемы использования общих
0
0
5
е
0 0
5
5
0
данных, а на втором - решение этой задачи за счет определения кратчайшего пути в эквивалентном графе.
Перед решением, подачей импульсов на соответствующие входы групп вхо- дов 35j, ,m в блок 4 вводится матрица использования общих данных. При этом, если , то триггер 36 ячейки 33; переводится в единичное состояние, а если a;j 0, то триггер соответствующей ячейки остается в нулевом состоянии. В регистры 38;, ,п записываются значения t,1 , численно равные времени выполнения 1-го интервала, в регистры 39j , ,m записываются значения tfj, численно равные средней стоимости использования j-й компоненты общих данных в течение единицы времени ( tfj определяется с учетом интенсивности использования j-й компоненты общих данных параллельными процессами), а в регистр 40 записывается значение R, численно равное затратам на организацию 1-го интервала при использовании одной
компоненты общих данных, i
Первый цикл первого этапа работы устройства начинается кратковременным нажатием выключателя 32 кнопочного коммутатора 3. При этом напряжение от шины питания через замыкающие контакты выключателя 32 кнопочного пос-- тупает на вход установки триггера 21. Триггер переходит в единичное состояние и сигнал уровня логической единицы поступает с его прямого выхода на такирующий вход А распределителя 20, готовя его переход в первое состояние, на объединенные входы, сброса триггера 22;, ,п и вход элемента 28 задержки. Триггеры 22;, ,п, не находящиеся до этого момента в нулевом состоянии, переходят в него. Через время Ј,, необходимое для срабатывания элементов распределителя 20, сигнал с выхода элемента 28 задержки поступает на вход сброса триггера 21. Триггер переходит в нулевое состоя- , ние, снимается сигнал высокого уровня с тактирующего входа распределителя 20 и он переходит в первое состояние, при котором сигнал уровня логической единицы присутствует на выходе (канала) С,. С выхода С, сигнал поступает на вход установки триггера 22i, а через соответствующие выход .блока 3 и вход блока 1 на объединенные четвертые входы моделей
дуг первой строки матрицы - 6,, i
. С четвертого входа этих моделей дуг сигнал поступает на один вход их элементов И 8. триггер 22, переходит в единичное состояние и сигнал с его прямого выхода поступает на вход элемента 29( задержка. Через вре время Јг сигнал с выхода элемента 29, задержки поступает на вход элемента И 24г, на объединенные входы ячеек 33 jj , j 1 ,m,матрицы 4 использования данных, считывающий пход регистра 38 ( блока 5, а через информационную цепь ключа 27 на пятый вход модели
дуги 60, с которого он поступает на второй.вход элемента И 8 этой модели дуги. Кроме того, сигнал с выхода элемента задержки поступает на вход одновибратора 30(. С выходов ячеек 33ij, ,n сигнал поступает на объединенные входы элементов И 37 этих ячеек. Вторые входы элементов И 37 соединены с прямыми выходами триггеров 36 и сигналы уровня логической единицы с выходов элементов И 33 ячеек 334 j j 1,m, соответствующих а;: , ,m, через эпементы ИЛИ 34;, ,ra поступают на считьшпющие входы регистров 39.,j 1 ,m и информационные входы сумматора 42 блока 5 (на последующих шагах решения, когда единичный сигнал присутствует на объединенных первых входах ячеек 33 , j не только первой строки матрицы 4, на выходе элементов ИЛИ 34jj будут сигналы aj, соответствующие поэлементной дизъюнкции включенных строк матрицы 4).
С информационных выходов регистра 38| значение t, поступает на соответствующий вход сумматора 41, а с ин- формационных регистров 39j, ,m
°узначения Л, -а: поступают на ссответствующие входы сумматора 43.
Через время задержки Ј с выхода одновибратора 30( импульс поступает через элемент ИЛИ 26 на объединенные стробирующие входы сумматоров 41-43 и вход э .смента 47 задержки. В сумматорах осуществляется суммирование по- ступающих на их входы величин и с выхода сумматора 41 значение t, поступает на один вход блока 45 умножения,
на другой вход которого поступает
m
значение 21 j -a j c выхода сумматора м
значение 2L-a. с выхода суммато. i
г
поступает на один вход блока 46
умножения, на другой вход которого поступает значенье R с информационного выхода регистра 40. Через «ремя сигнал с выхода элемента 47 задержки поступает на стробирующне входы блоков 45 и 46 умножения и вход элемента 48 задержки. С выходов локив - -5 и 46
0
5
0
5
0
5
Q
5 0
а.
и R Z-Я:
ПЧ
умножения значения t.
j«« J j J поступают на входы сумматора 44. Через время С сигнал с выхода .элемента 48 задержки поступает на вход элемента 49 задержки и стробируюпий вход сумматора 44. В сумматоре 44 осуществляется суммирование поступающих на его входы величин, С выхода сумматора
т м 44 значение S t, 51 a:+R Zlr. посj-iтупает параллельным кодом через выход
блока 5 и вход модели графа 1 на объединенные третьи входы всех моделей дуг. Так как к этому моменту времени присутствует сигнал уровчя логической единицы на обоих входах элемента И В только модели дуги 60, , то через замкнутую информационную цепь ключа 10 значение S записывается в счетчик 7 этой модели дуги. Через время b сигнал с выхода элемента 49 задержан поступает на вход коммутатора 3, а с него - на первый вход элемента И 23 и объединенные входы элементов И -4 , ,n. К этому моменту на втором входе присутствует сигнал высокого уровня только у элемента И 244.
На этом завершается первый шаг первого цикла решения и начинается второй, который как и последующие (п-2) аналогичен рассмотренному. При этом на каждом шаге будет записано в счетчик 7 моделей дуг 6 01 , i 2,n соответствующее значение длин дуг эквивалентного графа. В начале п-го шага решения с В1схода элемента задержки 29„ сигнал поступает не только на управляющий вход ключа 27,, ,, вход одновибратора 30 и соответствующие выходы коммутатора 3, но и на второй вход элемента И 23. Поэтому по окончанию n-го шага, при поступлении на вход коммутатора 3 сигнала с выхода элемента 49 задержки, сигнал уровня логической единицы будет присутствовать на обоих входах элемента И 23 и с выхода этого элемента сигнал через диод 31 поступит на вход устанопки триггера 21. На том заканчивается первый цикл и начинается
второй, который как и последующие циклы первого этапа- работы устройства аналогичен рассмотренному. Отличие заключается лишь в том, что k-й цикл состоит из (n-k+1) шагов, на каждом из которых осуществляется запись длин дуг эквивалентного графа в счетчики соответствующих моделей дуг (k-1) строки модели графа.
Таким образом, за п(п-Н) шагов
этапа работы устройства будет сформирована модель графа, эквивалентного задаче оптимизации схемы использования общих данных.
По окончании последнего шага первого этапа распределитель 20 перейдет в (п+1)-е состояние и на этом заканчивается первый этап работы устройства и начинается второй этап, на котором определяется кратчайший путь в полученном эквивалентном графе.
На втором этапе сигнал с выхода , распределителя 20 коммутатора 3 поступает на управляющий вход ключа ;7 блока 2 управления. Информационная цепь ключа 17 замыкается и напря- ..ение от шины питания через замкнутую информационную цепь ключа 17 поступает на объединенное вторые входы моде- тей дуг 60; ,,n модели графа 1, а через информационную цепь ключа 18 - на вход запуска генератора 15 импульсов. Генератор 15 начинает вырабатывать импульсы, которые поступают на счетный вход счетчика 16, а через соответствующие выход блока управления и вход модели графа, на объединенные первые входы всех моделей дуг. С вторых входов моделей дуг 60Р;, i 1,п напряжение поступает на катоды светодиодов 14, а через замкнутую информационную цепь ключей 11 на управляющий вход ключей 12 этих моделей дуг. Информационные цепи ключей 12 замыкаются и через них импульсы от генератора импульсов поступают на вычитающие входы счетчиков 7 моделей дуг 60;, ,п. При поступлении г импульсов (so; , где S 0; - длина (0,1)-и дуги моделируемого графа, на выходе индикации нулевого состояния счетчика 7 соответствующей модели дуги, например, 60; появляется сигнал который поступает на управляющий вход ключа 13, а через диод 9 на первый выход этой модели дуги и управляющий вход ключа 11. Информационная цепь
0
5
ключа 11 размыкается, снимается напряжение с управляющего входа ключа 12 и прекращается поступление импульсов на счетчик 7. Так как первые выходы моделей дуг объединены по столбцам, то аналогичным образом размыкаются информационные цепи ключей 11 и 12 всех остальных моделей дуг 1-го столбца, т.е. будет смоделировано достижение 1-й вершины графа.
Кроме того, при этом замыкается информационная цепь ключа 13 модели дуги 60; и напряжение поступает через светодиод 14, информационную цепь ключа 13 и второй выход модели дуги 60;на объединенные вторые входы моде0
5
0
5
0
5
0
5
леи дуг
О
,n, соответствующих дугам, исходящим из i-й вершины моделируемого графа. При этом аналогично рассмотренному начинают поступать импульсы и на счетчики 7 моделей дуг
6ij , + 1 ,.
Дальнейшая работа происходит таким
же образом, пока наконец не появится сигнал на втором выходе одной из моделей дуг последнего стопбца - 6 ;п, ,п-1. При этом составится цепь от
шины питания через информационную цепь ключа 17, выход блока управления вход модели графа, вторые входы включенных моделей дуг, принадлежащих кратчайшему пути, через светодиод 14, информационную цепь ключа 13 и второй выход этих моделей дуг, на выход модели графа, а с него на управляющий вход ключа 18. При этом загораются светодиоды моделей дуг, принадлежащих кратчайшему пути, размыкается информационная цепь ключа 18 и прекращается работа генератора импульсов 15. В счетчике 16 блока управления будет зафиксировано значение суммарных затрат при оптимальной схеме использования параллельными процессами общих данных. Сама схема определяется по дугам, принадлежащим кратчайшему пути. Например, при числе интервалов исходного процесса и если в результате решения в кратчайший путь вошли дуги (0,3) - (3,5) - (5,7), то необходимо в один интервал для параллельной работы исходные интервалы (1,2,3); (4,5) и (6,7).
Для возврата схемы в исходное состояние необходимо еп;е раз кратковременно нажать выключатель 32 кнопочный коммутатора 3, при ттом ос ществляет- ся возврат в Hcxmi состояние триггеров 22 j, ,n, а через время tv- возврат в нулевое состояние триггера 21 и возврат в исходное распределителя 20. Далее кратковременно нажимается выключатель 19 кнопочный блока 2 управления и напряжение от шины питания поступает на вход возврата в исходное состояние счетчика 16, а через соответствующие выход блока 2 и вход блока А - на объединенные входы сброса tтриггеров 36 ячеек 33;;, ,п, j-1,m.
Таким образом, устройство обеспечивает как автоматическое формирование по заданным исходным данным (jn m,t; , ,n, c(j , j 1,m, a;j , ,n, j r,m) графа, эквивалентного задаче оптимизации схемы использования параллельными процессами общих данных, так и решение этой задачи за счет определения кратчайшего пути в эквивалентном графе.
Формула изобретения 25
15
Устройство для оптимизации работы параллельных процессов, содержащее модель графа и блок управления, мо- пель графа состоит из верхней треугольной матрицы из г (п-Н)(п+2) морасчетный блок, содержащт} (га-ми-О регистров, четыре сумматора, дпд бло ка умножения и три элемента задержк кроме того, в каждую модель дуги модели графа, введены три ключа, элемент ИЛИ и диод, причем первый вход модели дуги соединен через информац онную цепь первого ключа с вычитающи входом счетчика, управляющий вход первого ключа соединен через информа ционную цепь второго ключа с вторым входом модели дуги, который соединен и с катодом светодиода, вычитающий 15 вход счетчика соединен через информа ционную цепь третьего ключа с третьи входом модели дуги, четвертый и пяты входы которой соединены с соответствующими входами элемента И, выход элемента И соединен с управляющим входом третьего ключа, выход сигнали зации о нулевом состоянии счетчика соединен с катодом диода и управляющим входом четвертого ключа, анод диода соединен с управляющим входом второго ключа и первым выходом модел дуги, второй выход которой соединен через информационную цепь четвертого ключа с анодом светодиода, первые входы всех моделей дуг объединены н соединены с выходом тактирования бло ка управления, вторые входы моде.чеи дуг объединены по строкам -магрицы модели графа и соединены с вторым выходом модели дуги соответственно предшествующих столбца и строки матрицы модели графа, а вторые входь- модели дуг первой строки матрицы соединены с выходом режима блока уг.
35
делей дуг, каждая из которых содержит .Т т«лиод, ключ и счетчик (п - количество интервалов оптимизируемого
вычислительного процесса), блок упр-ав- пения содержит генератор импульсов, четчик и ключ, выход генератора импульсов соединен с входом счетчика и с соответствующим входом модели гра-40 Равления, третьи входы всех моделей Фа, а выход модели графа соединен с ДУГ объединены и соединены с выходом управляющим входом ключа блока управ- расчетного блока, четвертые входь- ления, отличающееся тем, что, с целью расширения функциональных возможностей за счет решения задач ми выходами коммутатора, пятые входы оптимизации схемы использования об- моделей дуг объединены по столбцам
моделей дуг объединены по строкам матрицы и соединены с соответствующи10
5
расчетный блок, содержащт} (га-ми-О регистров, четыре сумматора, дпд блока умножения и три элемента задержки, кроме того, в каждую модель дуги модели графа, введены три ключа, элемент ИЛИ и диод, причем первый вход модели дуги соединен через информационную цепь первого ключа с вычитающим входом счетчика, управляющий вход первого ключа соединен через информационную цепь второго ключа с вторым входом модели дуги, который соединен и с катодом светодиода, вычитающий 15 вход счетчика соединен через информационную цепь третьего ключа с третьи - входом модели дуги, четвертый и пятый входы которой соединены с соответствующими входами элемента И, выход элемента И соединен с управляющим входом третьего ключа, выход сигнализации о нулевом состоянии счетчика соединен с катодом диода и управляющим входом четвертого ключа, анод диода соединен с управляющим входом второго ключа и первым выходом моделм дуги, второй выход которой соединен через информационную цепь четвертого ключа с анодом светодиода, первые входы всех моделей дуг объединены н соединены с выходом тактирования блока управления, вторые входы моде.чеи дуг объединены по строкам -магрицы модели графа и соединены с вторым выходом модели дуги соответственно предшествующих столбца и строки матрицы модели графа, а вторые входь- модели дуг первой строки матрицы соединены с выходом режима блока уг.
20
0
5
0 Равления, третьи входы всех моделей ДУГ объединены и соединены с выходом расчетного блока, четвертые входь- ми выходами коммутатора, пятые входы моделей дуг объединены по столбцам
Равления, третьи входы всех моделей ДУГ объединены и соединены с выходом расчетного блока, четвертые входь- ми выходами коммутатора, пятые входы моделей дуг объединены по столбцам
моделей дуг объединены по строкам матрицы и соединены с соответствующи
Изобретение касается цифрового моделирования и предназначено для повышения эффективности использования общих данных взаимодействующими параллельными процессами за счет определения схемы организации вычислительного процесса с общими данными, минимизирующей суммарные затраты на блокировку компонент общих данных, синхронизацию работы параллельных процессов и организацию вычислительного процесса. Устройство содержит модель графа, блок управления, коммутатор, матрицу использования данных и расчетный блок. Работа устройства основана на автоматическом формировании графа, эквивалентного задаче оптимизации схемы использования общих данных, и последующем решении этой задачи за счет определения кратчайшего пути в эквивалентном графе. 1 ил.
щих данных взаимодействующими вычислительными процессами, в него введены коммутатор, содержащий (п-Н)-канальный распределитель импульсов, in+1) триггеров и элементов задержки ч группу элементов задержки, элемент И и группу элементов И, п элементов ИЛИ, одновибраторов и (п-1) ключей, матрица использования д. иных, содержащая матрицу из п m , каждая. з которых состоит из триггера и элемента И, и m элементов ИЛИ (т - чис- , :о компонент общих дачных.), также
матрицы и соединены с соответствующими выходами коммутатора, первый и второй выходы моделей дуг объединены по столбцам матрицы модели графа, л вторые выходы моделей дуг последнею столбца матрицы объединены и соеди ны с выходом модели графа, причем г коммутаторе первый выход распредели теля импульсов соединен с входом установки первого триггера группы тг.,-- геров и соответствующе выходом коммутатора, (п+1)-й выход расгречелитч- ля импульсов соединен с входом при
знака изменения режима блока управления, с второго по выходы распределителя импульсов соединены с первыми входами .соответствующих элементов ИЛИ, вторые входы которых подключены к выходам элементов И группы, а выходы соединены с входами установки соответствующих триггеров группы, прямые выходы которых соединены с входами соответствующих элементов задержки группы, выходы элементов задержки группы соединены с соответствующими выходами коммутатора, входами соответствующих одновнбраторов, первыми входами соответствующих элементов И группы, и через информационные цепи ключей - с соответствующими выходами коммутатора, вторые входы элементов И группы объединены и соединены с выходом признака готовности расчетного блока, элемент И соединен через лиод с входом установки триггера, который через замыкающие контакты ;ыключателя кнопочного соединен с шинон питания, прямой выход триггера соединен с входом элемента задержки и объединенными входами сброса триг- с; оь группы, выход.,элемента задержки
динен с входом сброса триггера, управляющие входы ключей соединены с выходами соответственно последующих ст.г-ментов задержки группы, причем в матрице использования данных первые входы ьсех ячеек матрицы использова- шя данных, соединенные с первыми входами элементов И этих ячеек, о бъе- - инены но строкам матрицы и соединены с соответствующими выходами коммутаторов, которые соединены и с соответствующими входами расчетного блока, вторые входы ячеек, соединенные с входами сброса их триггеров, объе
5
5
0
5
0
динены у всех ячеек матрицы и соединены с выходом запуска блока управления, входы установки триггеров соединены с соответствующими входами матрицы использования данных, а их прямые выходы подключены к входам элементов И, выходы которых являются выходами ячеек и соединены с входами соответствующих элементов ИЛИ, выходы элементов ИЛИ соединены с входами расчетного блока, к которым подключены входы второго сумматора и считывающие входы группы из m регистров, причем в расчетном блоке выходы m регистров подключены к входам третьего сумматора, а считывающие входы группы из п регистров соединены с соответствующими входами расчетного блока, выходы этих регистров соединены с входами первого сумматора, стро- бирующие входы первого, второго и третьего сумматоров объединены с входом первого элемента задержки п соединены со стробирующим входом расчетного блока, выходы первого и третьего сумматоров соединены с входами первого блока умножения, а входы второго блока умножения подключены к выходу второго сумматора и выходу соответствующего регистра, выход первого элемента задержки соединен с входом второго элемента задержки и стробирующи- ми входами блоков умножения, выходы которых соединены с входами четвертого сумматора, стробирующий вход которого соединен с выходом второго элемента задержки и с входом третьего элемента задержки, выход четвертого сумматора соединен с выходом расчетного блока, с выходом признака готовности которого соединен выход третьего элемента задержки.
Матрица нтвльжому 
