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

СОЮЗ СОВЕТСКИХСОЦИАЛ ИСТИЧЕСНИХРЕСПУБЛИК 1520 ПИСАНИЕ ИЗОБРЕТ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Р 21 С.А.Вас чкула 8) детельст С 7/122 тельство б Г 15/2 ьков ский,а СССР 1977.СССР 1986,риц бло 54) УСТРОЙСТВО ДЛ Ы ПАРАЛЛЕЛЬНЫХ ПР 5) Изобретение к аделиравания и пр овышения эффектив бщих данных взаим ИИ РАБ Я ОПТИМИОЦЕССОВасаетсяеднззнач ифрового но дляности исодействую ользовани щими пара Модель 1 графа предназначеназадания топологии и весов дуг грэквивалентного задаче оптимизацисхемы использования общих данныхМодель графа содержит модели дуг6;1, ,1 =1,п, 1=1-1,п, каж,рьж состоит из счетчика 7И 8, диода 9, ключей 10-1диода 14.Блок 2 управления предназначеуправления работой устройства прределении кратчайшего пути в эквлентном графе и содержит генератимпульсов, счетчиков 16, клочи 1и 18 и выключатель 19 кнопочный.Коммутатор 3 предназначен дляравления работой устройства нри цая из катаэлемента 3 и свето н дл и опива- Ъ.ар 1 граор 3,1 ар ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГКНТ СССР(56) Авторское свиР 651358, кл. С 06Авторское свидеР 1339582, кл С 0 Изобретение относится к цифровомумоделированию и предназначено для оптимизации схемы использования общихданных взаимодействующими параллельными процессами многопроцессорных вычислительных систем.Цель изобретения - расширениефункциональных вазможностей устройства за счет решения задач оптимизациисхемь использования общих данныхвзаимодействующими вычислительнымипроцессами,На чертеже поиведена функциональная схема устройства.Устройство содержит модель 1фа, блок 2 управления, коммутатматрицу 4 использования данных ирасчетный блок 5,2;лельными процессами за счет апреде.11 ения схемы организации вычислительнагапроцесса с общими данными, минимизирующей суммарные затраты на блскиров .ку компонент сбщих данных, синхронизацию работы параллельных процессови организацию вычислительного прапе "са. Устройство содержит модель графа, блок управления, коммутатор, и;.ту использования данных и расчетек, Работа устройства основана наавтоматическом формировании графа,эквивалентного задаче оптимизациисхемы использования общих данных, ипоследующем решении .этой задачи засчет определения кратчайшего путив эквивалентном графе. 1 ич, 1569844мировации эквивалентного граФа и содержит (й+1)-канальный распределитель20 импульсов (и - число интервалов,на которое Разбивается исходный про 5цесс), триггер 21, группу триггеров22;, 1=1,п, элемент И 23, группы элементов И 24 .=2,п, элементы ИЛИ25, ШИ 26, л.=2,п, ключи 27, 3.1,п, элемент 28 задержки, группуэлементов 29, задержки, 1=1,п, одно"вибраторы 30;, з.=1,п, диод 31 и выключатель 32 кнопочный.Распределитель 20 имеет входы А, Ви выходы (каналы) С;, =1,п+1, Питание 5подается ца вход В. При поступлениина вход А ь-го импульса по его переднему Фронту происходит снятие напряжения С (1- 1)-го выхода, а по его заднему Фронту подача напряжения на -йвыход распределителя. При поступлениина вход А (и+2)-го импульса распреде,литель возвращается в исходное состояние. при котором отсутствует уровеньлогической единицы на всех его выходах,Матрица 4 использования данныхпредназначена для задания матрицы А,;азмерности (и+в), элементы которойа" 1, если 1-я компонента используется ца х-и интервале, и а, =О в противном случае (т число компонент .общих данных, которые могут использоваться параллельными процессаминезависимо, цо в режиме взаимногоискщочеция). Кроме того, данный блокпозволяет определить поэлементнуюдизъюцкцию соответствующих шагу решения строк матрицы А в пгоцессе Формирования эквивалентного грасЬа. Матрица 403 использования данных содержит матрицу ячеек 33, х=1 и, 1=1,ш, элементы ИЛИ 34, 1=1,т и группу входов35, 1=1,ш задания исходных данных,каждая ячейка блока содержит триггер36 и элемент И 37.Расчетный блок 5 предназначен дляопределения значения потерь на организацию рабаты с общими данными впроцессе Формирования эквивалентногограФа. Блок 5 содержит группы регистров 38 1.=1,п, 39, 1=1,тп и 40, сумматоры 41-44, блокй 45 и 46 умноженияи элементы 47-49 задержки.Работа устройства может быть раз"55делена на два этапа,На нервом осуществляется формирование граФа, эквивалентного задачеоптимизации схемы использования общих данных, а на втором - решение этой задачи за счет определения кратчайшего пути в эквивалентном граФе.Перед решением, подачей импульсов ца соответствующие входы групп вхо- дов 35, 1=1,ш в блок 4 вводится матрица использования общих данных. При этом, если а, =1, то триггер 36 ячейки 33переводится в единичное состояние, а если а, =О, то триггер со" ответствующей ячейки остается в нулевом состоянии, В регистры 38;, 1=7;и записываются значения численно равные времени выполнения 1-го интервала, в регистры 39 1=1,ш записываются значения М, численно равные средней стоимости использования 1-й компоненты общих данных в течение единицы времени ( К 1 определяется с учетом интенсивности использования1-й компоненты общих данных параллельными процессами), а в регистр 40 записывается значение К, численно равное затратам на организацию .-го интервала при использовании одной компоненты общих данных.Первый цикл первого этапа работы устройства начинается кратковременным нажатием выключателя 32 кнопочного коммутатора 3, При этом напряжение от шины питания через замыкающие контакты выклочателя 32 кнопочного поступает на вход установки триггера 21, Триггер переходит в единичное состояние и сигнал уровня логической единицы поступает с его прямого выхода на такирующий вход А распределителя 20, готовя его переход в первое состояние, на объединенные входы, сброса триггера 22 д=1,п и вход элемента 28 задержки. Триггеры 22 1=1,п, не находящиеся до этого момента в нулевом состоянии, переходят в него. Че" рез времянеобходимое для срабатывания элементов распределителя 20, сигнал с выхода элемента 28 задержки поступает на вход сброса триггера 21, Триггер переходит в нулевое состояние, снимается сигнал высокого уровня с тактирующего входа распределителя 20 и он переходит в первое состояние, при котором сигнал уровня логической единицы присутствует на выходе (канала) С,. С выхода С сигнал поступает на вход установки триггера 22, а через соответствующие выход блока 3 и вход блока 1 на объединенные четвертые входы моделей, а,т поступают на входы сумматора 44, Через время сд сигнал с выхода элементал48 задержки поступает на вход элемента 49 задержки и стробируюший вход сумматора 44, В сумматоре 44 осуществляется суммирование поступающих на его входы величин, С выхода сумматорам И 44 значение Б=Т , а(, а,+Р а; пост 1,)1 тупает параллельным кодом через выход блока 5 и вход модели графа 1 на объединенные третьи входы всех моделей дуг, Так как к этому моменту времени присутствует сигнал уровня логической единицы на обоих входах элемента И 8 только модели дуги 6 то через замкнутую информационцуто цепь ключа 10 значение Б записывается в счетчиклэтой модели дуги, Через времясигнал с выхода элемента 49 задержки поступает на вход коммутатора 3, а с него - на первый вход элемента И 23 и объединенные входы элементов И 24;, .=2,т 1, К этому моменту на втором вхсде ттрисутствует сигнал высокого уровня только у элемента И 24.На этом завершается первый шаг первого цикла решения и начинается второй, который как и последующие (и) аналогичен рассмотренному. Прц этом на каждом шаге будет записано в счетчик 7 моделей дуг 6 о т.=2,и соответствующее значение дпцн дуг эквивалентного графа. В начале и-го шага решения с выхода элемента задержки 29 сигнал поступает не только на управляющий вход ключа 27 вход одновибратора 30 и соответствующие выходы коммутатора 3, но и на второй вход элемента И 23. Поэтому по окончанию и-го шага, прц поступлении на вход коммутатора 3 сигнала с выхода элемента 49 задержки, сигнал уровня логической единицы будет присутствовать на обоих входах элемента И 23 и с выхода этого элемента сигнал через диод 31 поступит на вход установки триггера 21. На . том заканчивается первый цикл и начинается 5 156984 дуг первой строки матртщы - 6 1 1,п, С четвертого входа этих моделей дуг сигнал поступает на один вход их элементов И 8. триггер 22 т переходит в единичное состояние и сигнал с его прямого выхода поступает на вход элемента 29.т задержки, Через вревремя С сигнал с выхода элемента 29, задержки поступает. на вход элемента И 24 , на объединенные входы ячеек 33 11 3=1 ФВ матрицы 4 использования данных, считывающий вход регистра 38.1 блока 5, а через информационную цепь ключа 2 т на пятый вход модели 15 дуги бт, с которого он поступает на второй .вход элемента И 8 этой модели дуги. Кроме того, сигнал с выхода элемента задержки поступает на вход одновибратора 30 т. С выходов ячеек 20 33,1, 3=1,пт сигнал поступает на объединенные входы элементов И 37 этих ячеек, Вторые входы элементов И 37 соединены с прямыми выходами триггеров 36 и сигналы уровня логической 25 единицы с выходов элементов И 33 ячеек 33 3 =1,ш, соответствующих а, =3=1,п, через элементы ИЛИ 34, 1=1,тп поступают на считывающие входы регистров 39,3 =1,тп и информационные 30 входы сумматора 42 блока 5 (на последующих шагах решения, когда единичный сигнал присутствует на объединенных первых входах ячеек 33не только первой строки матрицы 4, на выходе элементов ИЛИ 34; будут сигналы а, соответствующие поэлементной дизъюнкции "включенцьтх" строк матрицы 4).С информационных выходов регистра 381 значение С, поступает на соответ О ствующий вход сумматора 41, а с информационных регистров 39, 3 =1,ш значения Ж апоступают на соответствующие входы сумматора 43.Через время задержки ь с выхода д одновибратора 301 импульс поступает через элемент ИЛИ 26 на объединенные стробирующие входы сумматоров 41-43 и вход э;,емента 47 задержки, В сумматорах осуществляется суммирование по ступающих на их входы величин и с выхода сумматора 41 значение с, поступает на один вход блока 45 умножения, на другой вход которого поступает значение ,", с а с выхода сумматора3 т1 юм43, а значение Х. ас выхода суммато- ра 42 поступает на один вход блока 46 4 6умножения, на другой вход которого поступает значенье й с информаццоннсл го выхода регистра 40. Через время т сигнал с выхода элемента 47 задержки поступает на стробирующпе входы блоков 45 и 46 умножения и вход элемента 48 задержки. С выходов блоков 45 и 46второй, который как и последующие циклы первого этапа работы устройства аналогичен. рассмотренному, Отличие заключается лишь в том что 1 с-й циклФ5 состоит из (п-Е+1) шагов на каждом из которых осуществляется запись длин дуг эквивалентного графа в счетчики соответствующих моделей дуг (к) строки модели графа.Таким образом, за - 1 п(п+1) шагов этапа работы устройства будет сформирована модель графа, эквивалентного задаче оптимизации схемы использова 15 ния,общих данных.По окончании последнего шага первого этапа распределитель 20 перейдет в (и+1)"е состояние и на этом заканчивается первый этап работы уст 20 ройства и начинается второй этап, на котором определяется кратчайший путь в полученном эквивалентном графе.На втором этапе сигнал с выходараспределителя 20 коммутатора 3 25 поступает на управляющий вход ключа 17 блока 2 управления. Информационная цепь ключа 17 замыкается и напря,;ение от шины питания через замкнутую информационную цепь ключа 17 поступа.Вет на объединенные вторые входы моделей дуг 60;,=1,п модели графа 1, а через информационную цепь ключа 18 - на вход запуска генератора 15 импуль"ов, Генератор 15 начинает вырабатывать импульсы, которые поступают на счетный вход счетчика 16, а через соответствующие выход блока управления и вход модели графа, на объединенные первые входы всех моделей дуг,С вторых входов моделей дуг 60, д= =Г,п напряжение поступает на катоды светодиодов 14, а через замкнутую информационную цепь ключей 11 на управляющий вход ключей 12 этих моделей дуг, Информационные цепи ключей 12 замыкаются и через них импульсы от . генератора импульсов поступают на вычитающие входы счетчиков 7 моделей дуг бо;, 1=1,п, При поступлении г импульсов г=пппЯО; , где Б , - длинаГ(О,)-й дуги моделируемого графа, на выходе индикации нулевого состояния счетчика 7 соответствующей модели дуги, например, 6 ; появляется сигнал, который поступает на управляющий вход ключа 13, а через диод 9 на первый выход этой модели дуги и управляющий вход ключа 11. Информационная цепь ключа 11 размыкается, снимается напряжение с управляющего входа ключа 12и прекращается поступление импульсовна счетчик 7, Так как первые выходымоделей дуг объединены по столбцам,то аналогичным образом размыкаютсяинформационные цепи ключей 11 и 12всех остальных моделей дуг -го столбца, те. будет смоделировано достижение х-й вершины графа.Кроме того, при этом замыкаетсяинформационная цепь ключа 13 моделидуги 6 ; и напряжение поступает через светодиод 14, информационную цепьключа 13 и второй выход модели дуги6 ,на объединен 11 ые вторые входы моделей дуг 6;, 1=+1,п, соответствующихдугам, исходящим из -й вершины моделируемого графа, При этом аналогичнорассмотренному начинают поступатьимпульсы и на счетчики 7 моделей дуг6,", ) =1+1,п,Дальнейшая работа происходит такимже образом, пока наконец не появитсясигнал на втором выходе одной из моделей дуг последнего столбца - 6;,1=0,п. При этом составится цепь отшины питания через информационнуюцепь ключа 17, выход блока управлениявход модели графа, вторые входы "включенных моделей дуг, принадлежащихкратчайшему пути, через светодиод 14,информационную цепь ключа 13 и второйвыход этих моделей дуг, на выход модели графа, а с него на управляющийвход ключа 18, Лрн этом "загораются"светодиоды моделей дуг, принадлежащихкратчайшему пути, размыкается информационная цепь ключа 18 и прекращается работа генератора импульсов 15;В счетчике 16 блока управления будетзафиксировано значение суммарных затрат при оптимальной схеме использования параллельными процессами общихданных, Сама схема определяется подугам, принадлежащим кратчайшему пути.Напркчер, при числе интервалов исходного процесса п=7 и если в результа"те решения в кратчайший путь вошлидуги (0,3) - (3,5) - (5,7), то необходимо в один интервал для параллельной работы исходные интервалы (1,2,3);(4,5) и (6,7),Для возврата схемы в исходное состояние необходимо еще раз кратковременно нажать выключатель 32 кнопочныйкоммутатора 3, при том осуществляется возврат в исход о:. состояние тригмоделей дуг объединены по строкамматрицы и соединены с соответствующими выходами коммутатора, пятые входымоделей дуг объединены по столбцамматрицы и соединены с соответствующими выходами коммутатора, первый ивторой выходы моделей дуг объединеныпо столбцам матрицы модели графа, авторые выходы моделей дуг последне 1 остолбца матрицы объединены и соеди .ны с выходом модели графа, причемкоммутаторе первый выхоц распрделителя импульсов соединен с входом установки первого триггера группы тр; ггеров и соответствующ,1 м выходом ка:; -мутатора, (п+1)-й выход расгрецелптеля импульсов соедР 1 кея с входом при" 9 15698 геров 22ь=1,п, а через время 7твозврат в нулевое состояние триггера 21 и возврат в исходное распределителя 20. Далее кратковременно нажимается выключатель 19 кнопочный блока 2 управления и напряжение от шины питания поступает на вход возврата в исходное состояние счетчика 16, а через. соответствующие выход блока 2 и вход блока 4 - на объединенные входы сброса триггеров Зб ячеек 33;, =1,п, 1 щ 1,ш.Таким образом, устройство обеспечивает как автоматическое формирование по заданным исходным данным (д, ш,;, 1=1,п, К, 1=1,ш, а; , =1,п, =Г,ш) графа, эквивалентного задаче оптимизации схемы использования параллельными процессами общих данных, 20 так и решение этой задачи за счет определения кратчайшего пути в эквивалентном графе. Формула из обретения 25 Устройство для оптимизации работы параллельных процессов, содержащее модель графа и блок управления, моцель графа состоит иэ верхней тре 1угольной матрицы из 2 (и+1) (и+2) моделей дуг, каждая из которых содержит с 1 тсдиод, ключ и счетчик (и - количество интервалов оптимизируемого вычислительного процесса), блок управления содержит генератор импульсов, счетчик и киоч, выход генератора импульсов соединен с входом счетчика и с соответствующРск входом модели гра г. фа, а выход модели графа соединен с управляющим входом ключа блока управления, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет решения задач 45 оптимизации схемы использования общих данных взаимодействующими вычислительными процессами, в него введены коммутатор, содержащий (и+1)-канальный распределитель импульсов, 1,п+1) триггеров и элементов задержки и группу элементов задержки, элемент И и группу элементов И, и элементов ИЛИ, одновибраторов и п) ключей, матрица использования данных, содержащая матрицу из и 11 ш ;.чеек, каждая, з которых состоит из триггера и элемечта И, и ш элементов ИЛИ (ш - число компонент общих данных)у а также 44 Орасчетный блок, содержащий шг 1+ 1 ) регистров, четыре сумматора, два блока умножения и три элемента задержки, кроме того, в каждую модель дуги модели графа, введены три ключа, элемент ИЛИ и диод, причем первый вход модели дуги соедчнен через информационную цепь первого ключа с вычитающ 1 ц. входом счетчика, управляющий вход первого ключа соединен через информационную цепь второго ключа с вторым входом модели дуги, который соединен и с катодом светодиода, вычитающнй вход счетчика соединен через информационную цегь третьего ключа с третьи: входом модели дуги, четвертый и пятый входы которой соединены с соответствующими входами элемента И, выход элемента И соединен с управляющим входом третьего кгпоча, выход сигнализации о нулевом состоянии счетчика соединен с катодом диода и управляющим входом четвертого ключа, анод диода соединен с управляющим ьходом второго ключа и первым выходом модел.1" дуги, второй выход которой соединен через информационную цепь четвертого ключа с анодом светодиода, первые входы всех моделей дуг объединены и соединены с выходом тактирования блока управления, вторые входы моделей дуг объединены по строкам ма грицы модели графа и соединены с вторым выходом модели дуги соответственно предшествующих столбца и строки матрицы модели графа, а вторые входь модели дуг первой строки матр 1.гы соединены с выходом режима блока управления, третьи входы всех моделей дуг объединены и соединены с выходом расчетного блока, четвертые входь:1115 б 98 знака йзменения режйма блока управления, с второго по и-, й выходы распределителя импульсов соединены с первыми,входами .соответствующих элементов ИЛИ, вторые Входы которых подключены к .выходам элемейтав И группы, а выходы соединены с входами установки соответствующих триггеров .группы, прямые выходы которых соединены с входами соответствующих элементов задержки группы, выходы элементов задержки группы соединены с соответствующими выходами коммутатора, входами соот-ветствующих одновибратаров, первыми входами соответствующих элементов И группы, и через информационные цепи ключей - с соответствующими выходами коммутатора, вторые входы элементов И группы объединены и соединены с М , выходом признака готовности расчетнога блока, элемент И соединен через диод с входом установки триггера, который через замыкающие контакты выключателя кнопочного соединен с 25 ыинай питания, прямой выход триггера соединен с входам элемента задержки и объединенными входамй сброса триге,;ав группы, выход элемента задержки:.динен с входом сброса триггера, з .правляющие входы кщочей соединены с выхалами соответственно последующих элементов задержки группы, причем в матрице использования данных первые входы всех ячеек матрицы использовазия данных, соединенные с первыми вхацами элементбв И этих ячеек, объет.,инены па строкам матрицы и соединены с соответствующими выходами коммутаторов, которые соединены и с соответствующими входами расчетного блока, вторые входы ячеек соединенные с входами сброса их триггеров, объе- с 12динены у всех ячеек матрицы и соединены с выходом запуска блока .управления, входы установки триггеров соединены с соответствующими входами матрицы использования данных, а их прямые выходы подключены к входам элементов И, выходы которых являются выходами ячеек и соединены с входамисоответствующих элементов ИЛИ, выходыэлементов ИЛИ соединены с входамирасчетного блока, к которым подключены входы второго сумматора и считывающие входы группы из щ регистров,причем в расчетном блоке выходы шрегистров подключены к входам третьего сумматора, а считывающие входыгруппы из и регистров соединены ссоответствующими входами расчетногоблока, выходы этих регистров соединены с входами первого сумматора, страбирующие входы первого, второго итретьего сумматоров объединены с входам первого элемента задержки и соединены со стробирующим входом расчетного блока, выходы первого и третьегосумматоров соединены с входами первого блока умножения, а входы второгоблока умножения подключены к выходувторого сумматора и выходу соответствующего регистра, выход первого элемента задержки соединен с входом второго элемента задержки и стробирующими входами блоков умножения, выходыкоторых соединены с входами четвертого сумматора, стробирующий вход которого соединен с выходом второго элемента задержки и с входом третьегоэлемента задержки, выход четвертогосумматора соединен с выходом расчетного блока, с выходом признака готовности которого соединен выход третьего элемента задержки,1=с,аЯ 44 С.Шевкун роиэводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 Составитель А,ушаковедактор Л.Зайцева Техред М.Ходанич Кор Заказ 1451 Тираж 570 Подпис ВНИИПИ Государственного комитета по изобретениям и113035, Москва, Ж, Раушская наб крьгтиям при ГЕНТ СССРд. 4/5