Устройство для управления распределенной вычислительной системой Советский патент 1985 года по МПК G06F9/00 

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

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

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

узла блока, вход требуемых данных и вход наличия данных которого являются первым и вторым входами узлов анализа группы соответственно, а каждый блок анализа содержит группу сумматоров по модулю два, группу элементов НЕ и элемент И, выход Которого является выходом блока анализа, выходы сумматоров по модулю два группы через элементы НЕ группы подключены к входам элемента И, первые и вторые входы сумматоров по модулю два являются первым и вторым входами блока анализа соответственно.

УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМОЙ, содержащее блок управления, регистр сдвига, регистр номера задания, регистр номера запрашиваемого узла, регистры числа процессоров, регистры маршрутов, первый и второй счетчики адресов, группу счетчиков занятых каналов, дешифратор узлов, блок памяти узлов, блок памяти маршрутов, регистры готовности, первую и вторую группы элементов ИЛИ, с первой по пятнадцатую группы элементов И, элемент ИЛИ-НЕ, первый элемент И, два элемента ИЛИ, элемент НЕ, причем единичные выходы регистра сдвига подключены к первым входам элементов И первой группы и входам элемента ИЛИ-НЕ, выход которого соединен с первыми входами элементов И с второй по седьмую группы и входом конца распределения блока управления, вход числа необходимых процессоров которого соединен с информационным входом регистра сдвига и является входом числа необходимых процессоров устройства. Выход управления сдвигами блока управления подключен к входу управления сдвигом регистра сдвига, входы поразрядного сброса которого соединены с выходами элементов И первой группы и первыми входаЛ1и элементов И восьмой группы, вторые входы которых подключены к прямым входам элементов И девятой группы, первым входам элементов И десятой группы, группе входов дешифратора узлов и первым входам элементов И одиннадцатой группы, вторые входы которых объединены и подключены к выходу записи маршрута блока управления, а третьи входы подключены к выходам элементов И двенадцатой группы, первые входы которых подключены к входам первого элемента И, выходу блока памяти маршрутов и первым входам элементов И тринадцатой группы, зторые входы которых соединены с выходами группы счетчиков занятых каналов, а выходы соединены с вхо.т,ами первого элемента ИЛИ, выход которого соединен с входом отсутствия свободного маршрута блока управления и через элемент НЕ - с вторыми входами элементов И двенадцатой группы и с входом наличия маршрута блока управления, вход окон чания просмотра маршрутов которого соединен с выходом первого элемента ИЛИ, выходы элементов И восьмой группы подключены к входам регистров числа процессоров, выход приема блока управления соединен с первыми входами элементов И четырнадцатой и пятнадцатой групп, выходы которых соединены с информационным входом регистра номера задания и информационным входом регистра номера запрашивае- 00 О5 мого узла соответственно, вы-ходы регистра номера задания регистров маршрута, регистра номера запрашиваемого узла, регистров числа процессоров соединены с вторысл ми входами элементов И с второй по седьсо мую группы, выходы которых являются группой выходов заголовка задания устройства, группа входов готовности каналов связи устройства соединена с информационными входами группы счетчиков занятых каналов, управляющие входы которых подключены к выходам элементов ИЛИ первой группы, входы которых подключены к выходам элементов И восьмой группы, выход регистра номера запрашиваемого узла соединен с информационным входом блока памяти узлов и информационным входом блока

1

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

Известно устройство для распределения заданий процесорам, содержащее блок управления поиском и распределением, регистры готовности процессоров, регистр сдвига, группы элементов И, элементы ИЛИ, триггеры.

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

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

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

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

десятого элемента ИЛИ, первому входу восьмого элемента ИЛИ, к второму входу третьего элемента ИЛИ, выход которого соединен с нулевым входом триггера пуска, единичный выход которого подключен к пер, вому входу четвертого элемента И, выход генератора импульсов подключен к второму входу четвертого элемента И, выход которого соединен с вторыми входами пятого, седьмого и девятого элементов И, вход отсутствия свободного маршрута подключен

0 к третьему входу четвертого элемента ИЛИ, второму входу восьмого элемента ИЛИ, первому входу седьмого элемента ИЛИ, первому входу девятого элемента ИЛИ, выход восьмого элемента ИЛИ является выходом

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

5 шестого элемента И и первому входу восьмого элемента И, выход которого соединен с выходом записи маршрута, вторым входом девятого элемента ИЛИ и единичным входом триггера распределения, единичный

0 выход которого подключен к первому входу девятого элемента И, выход которого соединен с выходом управления сдвигом, выход десятого элемента ИЛИ подключен к нулевому входу триггера распределения, единичный выход которого соединен с выходом

5 разрешения распределения и третьим седьмого элемента ИЛИ, выход которого подключен к нулевому входу триггера маршрутов, единичный выход которого соединен с вторым входом пятого элемента ИЛИ, выход

0 которого подключен к нулевому входу триггера узлов, вход начала маршрутизации соединен с первым входом шестого элемента И, выход которого подключен к единичному входу триггера маршрутов, единичный выход которого соединен с первым входом

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

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

Предлагаемое устройство содержит (фиг. 1 и 2) блок 1 управления, регистры 2 готовности, элемент ИЛИ-НЕ 3, регистр 4 сдвига, группу элементов И 5, группу элементов ИЛИ 6, группы элементов И 7-9, элемент ИЛИ 10, счетчик 11 адреса, блок

12 памяти узлов, дешифратор 13 узлов, счетчик 14 адреса, блок 15 памяти маршрутов, группу элементов И 16, счетчик 17 занятых каналов, элемент И 18, элемент ИЛИ 19, группу элементов И 20, элемент НЕ 21, группы элементов И 22-24, регистр 25 номера задания, регистр 26 номера запрашиваемого .узла, регистры . 27 числа процессоров, регистры 28 маршрутов, шесть групп элементов И 29, группу элементов ИЛИ 30, первый вход 31 узла анализа, схему 32 сравнения, группу элементов И 33, элемент ИЛИ 34, триггер 35 пуска, элемент И 36, генератор 37 импульсов, элементы ИЛИ 38 и 39, триггер 40 узлов, элемент И 41, второй 42 вход узла анализа, элемент И 43, триггер 44 маршрутов, элемент И 45, элементы ИЛИ 46 и 47, выход 48 блока анализа, элемент И 49, триггер 50 распределения, элемент И 51, элемент ИЛИ 52, элемент НЕ 53, входы 54 кода числа необходимых процессоров, входы 55 готовых процессоров, входы 56 готовности каналов связи, выходы 57 заголовка задания, входы 58 номера запрашивающего узлы, входы 59 номера задания, группа регистров 60 наличия данных, регистр 61 требуемых данных, группа элементов И 62; группа сумматоров 63 по модулю два, группа 64 элементов НЕ, элемент И 65, группа узлов 66 анализа, входы 67 наличия данных, группа элементов И 68, девятый выход 69 блока 1 управления, первый выход 70 отказа, первый вход 71, второй выход 72, второй вход 73, третий выход 74, четвертый выход 75, пятый выход 76, третий вход 77, шестой выход 78, седьмой выход 79, четвертый вход 80, пятый вход 81, шестой вход 82, восьмой выход 83, седьмой вход 84, восьмой вход 85, девятый вход 86, десятый выход 87, вход 88 требуемых данных.

На фиг. 3 изображены блок 1 управления, элемент ИЛИ-НЕ 3, регистр 4 сдвига, группа элементов И 5, группа элементов ИЛИ 6, вход 54 кода числа необходимых процессоров, второй выход 72, второй вход 73 и третий выход 74 блока 1 управления. Регистр 4 сдвига содержит (фиг. 3) группу элементов И 89, группу триггеров 90.

Предлагаемое устройство работает следующим образом.

Известно, что распределенные вычислительные системы (РВС) могут содержать п (п 1) узлов обработки данных, соединенных между собой Z линиями связи. Каждый j-й (j-TTn) узел включает в свой состав mj программно совместимых процессоров, позволяющих независимо друг от друга выполнять задания по обработке данных, а Р-я (E-1,Z) линия связи состоит из Ре () каналов связи.

В таких РВС задания на обработку данных выдаются пользователями, размещенными на узлах обработки. Задания пользователей, располагаемых на i-м узле, могут быть выполнены на j-м узле, если на этом узле имеется необходимое количество свободных процессоров и есть необходимые данные для выполнения заданий, или же на группе узлов обработки, если суммарное количество свободных процессоров на этой группе узлов больше либо равно количеству необходимых для выполнения заданий процессоров и на каждом узле имеются необходимые данные. Кроме того, должны быть свободные каналы связи, обеспечивающие передачу заданий на выбранные узлы. В первую очередь для выполнения задания назначаются процессоры тех узлов, передача задания к которым потребует меньшего количества линий связи и промежуточных узлов коммутации. В исходном состоянии в J-M (j-l,n) регистре 2 готовности хранятся данные о готовности к работе процессоров

0 j-ro узла обработки. В регистрах 60 хранится информация о наличии данных того или иного типа на каждом узле обработки, причем если на узле есть данные нескольких типов, то в соответствующие разряды регистра данных записаны единицы, в противном случае нули, В t-м (I-1,Z) счетчике 17 записан код количества занятых каналов Z-й линии связи.

Триггеры счетчиков 1I и 14 адресов и триггеры 35, 40, 44 и 50 находятся в нулевом

0 состоянии.. В блоке 12 памяти узлов хранятся массивы г-разрядных чисел (r-loggn). Любой массив содержит п ячеек, в каждой из которых записан код номера узла, на котором возможна обработка задания. Коды номеров узлов внутри i-ro массива могут быть упорядочены, например, по удаленности от i-ro узла обработки.

Для обращения к блоку 12 памяти узлов используется адрес, включающий поле

базы, которая задает номер i-ro массива и поле адреса, задаюшего номер числа в массиве. В блоке 15 памяти маршрутов хранится п массивов Z-разрядных чисел. Каждый ij-й массив содержит Yj чисел, соответствующих количеству маршрутов из ч-го в j -и узел. MapujpyTbi могут быть упорядочены в каждом J-M массиве, например, в порядке возрастания их длины. Каждый ij-й массив заканчивается ячейкой, содержащей единицы во всех разрядах для отделе0 ния одного массива от другого.

Для обращения к блоку 15 памяти маршрутов используется адрес, включающий поле базы и поле смещения, задающие номер ij-ro массива, а также поле адреса, задающего номер числа в массиве.

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

В работе устройства можно выделить три этапа.

На первом этапе осуществляется проверка возможности выполнения задания и РВС и прием задания на обслуживание. По входу 54 код числа процессоров, необходимых для выполнения задания, поступает на первую группу входов схемы 32 сравнения. Одновременно на регистр 61 требуемых данных по входу 88 записывается код, причем единица К-го разряда свидетельствует о том, что для выполнения задания требуются данные К-го типа. Таким образом, на группы элементов И 62 поступают коды с выхода регистра 61 и коды с выхода регистров 60 наличия данных. В случае, если в одноименных разрядах регистров 61 и 60 записаны единицы, то это свидетельствует о наличии на данном узле обработки данных нужного типа. На выходе соответствующих элементов И 62 появляются единичные сигналы, которые через девятый вход 86 блока 1 управления поступают на первые входы сумматоров 63 по модулю два. Одновременно на вторые входы сумматоров 63 по модулю два поступает код требуемых данных с единичных выходов регистра 61 требуемых данных. Таким образом, на входах элемента И 65 имеются единичные сигналы только в том случае, если все единичные разряды регистра 61 требуемых данных совпадают с единичными сигналами на выходе регистров 60. На выходе элемента И 65 появляется единичный сигнал, разрешающий прохождение кода с соответствующего регистра 2 готовности через группы элементов И 68 на вторую группу входов схемы 32 сравнения только в случае, если на узле обработки есть данные, необходимые для выполнения поступившего задания.

Если суммарное число свободных процессоров на узлах обработки с учетом имеющихся на узлах необходимых данных больше либо равно числу процессоров, необходимых для выполнения задания, то на первом выходе «Больше или равно схемы 32 сравнения появляется единичный сигнал, который устанавливает триггер 35 пуска в единичное состояние, разрешая тем самым прохождение тактовых импульсов генератора 37 через элемент И 36. Одновременно единичный сигнал с первого выхода схемы 32 сравнения поступает на первый вход элемента И 38 и на вторые входы групп элементов И 23 и 24 и на третий вход разрешения записи входного кода регистра 4. Благодаря этому в регистр 4 записывается код числа необходимых для выполнения задания процессоров, а в регистры 25 и 26 записывается номер задания и номер запрашивающего узла соответственно.

Если число свободных процессоров меньше требуемого, то появляется единичный

сигнал с второго выхода «Меньше схемы 32 сравнения и через элемент ИЛИ 42 в качестве сигнала «Отказ по выходу 70 поступает на выход устройства. На этом первый этап работы предлагаемого устройства заканчивается.

На втором этапе производится определение номеров узлов, на которых возможна обработка маршрутов передачи данных на эти узлы, а также выделение процессоров на выбранных узлах для выполнения задания.

Этап выполняется за несколько шагов. Каждый шаг в общем случае включает три типа итерадий. В начале каждого шага выполняется итерация первого типа, обеспечивающая поиск ближайшего к i-му запрашивающему узлу j-ro узла обработки, на котором имеются в рассматриваемый момент времени свободные процессоры. Выполнение итерации начинается с установки в единичное состояние триггера 40 узлов и обращения к блоку 12 памяти по адресу, образованному кодом номера запращивающего узла и содержимым счетчика 11 адреса. С появлением импульса на выходе элемента И 41 из блока 12 памяти узлов считывается

0 номер j узлаи на j-м выходе дешифратора 13 появляется сигнал. Этот сигнал разрешает выдачу содержимого j-ro регистра 2 готовности через группу элементов И 9. Если с выходов И 68 поступают нулевые сигналы, сообщающие о том, что в j-м

5 узле все процессоры заняты, или о том, что там нет необходимых для выполнения задания данных, то на выходе j-ro элемента И 9 появляется единичный сигнал, поступающий через элементы ИЛИ 10 и 38 на единичный

0 вход триггера 40 узлов, разрешая прохождение импульсов на счетный вход счетчика

11и запускающий вход блока 12 памяти узлов. При этом адрес обращения к блоку

12памяти узлов увеличивается на единицу по сравнению с предыдущим циклом считывания, что обеспечивает выборку очередного узла.

Описанная итерация первого типа повторяется до тех пор, пока не найден узел,

на котором возможно выполнение данного задания. В этом случае появляется нулевой сигнал на выходе i -го элемента И 9, а на выходе элемента НЕ 53 появляется единичный сигнал. Этот сигнал через элемент И 43 устанавливает в единичное состояние триггер 44 маршрутов. Сигнал с единичного выхода триггера 44 через элемент ИЛИ 39 устанавливает в нулевое состояние триггер 40 узлов, что запрещает прохождение

импульсов на запускающий вход блока 12 памяти узлов. Этим обеспечивается запоминание номера узла, на котором возможно выполнение задания или его части. На этом итерация первого типа заканчивается.

Итерация второго типа выполняется после итерации первого типа и осуществляет выбор кратчайщего марщрута из1-го узла в j-й с учетом свободных каналов связи. Выполнение итерации начинается с обращения к блоку 15 памяти маршрутов по адресу, образованному кодом номера запращивающего узла, кодом номера узла обработки 1 содержимым счетчика 14 адреса. С появлением сигнала на выходе элемента И 45 из блока 15 памяти маршрутов считывается по сформированному адресу код марщрута из i-ro узла в j-й. Этот код поступает на первые входы группы элементов И 16, на вторые 1зходы которых поступают сигналы готовности линий связи с выходов счетчиков 17. Предполагается, что разряды счетчика 17 находятся в единичном состоянии, если в соответствующей линии связи заняты все каналы.

Если хотя бы одна линия связи в выбранном марщруге занята, то на выходе соответствующего элемента И 16 появляется сигнал, запрещающий выдачу кода марщрута из блока 15 памяти марщрутов в J- регистр 28.

С приходом очередного импульса с выхода элемента И 45 осуществляется формирование последовательности номеров маршрутов с помощью счетчика 14 адресов, пуск блока 15 памяти марщрутов для считывания кода марщрута и проверка наличия свободных каналов связи, используемых в данном марщруте.

Описанный процесс поиска свободных маршрутов повторяется до тех пор, пока не обнаружен свободный марщрут, либо не считаны все марщруты из ij-ro массива данных блока памяти марщрутов. В последнем случае при очередном запуске блока 15 памяти маршрутов считан код, содержащий единицы во всех разрядах. В этом случае прерывается выполнение итерации второго типа и производится переключение на выполнение итерации первого типа. Для этого с выхода элемента И 18 сигнал поступает на единичный вход триггера 40 узлов, нулевой вход триггера 44 марщрутов и на первый вход элемента ИЛИ 47. На выходе элемента ИЛИ 47 появляется единичный сигнал, устанавливающий в нулевое состояние счетчик 14 адреса.

Если при выполнении итерации второго типа из блока 15 памяти марщрутов считан код марщрута, для которого имеются свободные каналы связи, то на выходе элемента НЕ 21 появляется сигнал, разрешающий

выдачу кода маршрута через группу элементов И 20 на входы j-й группы элементов И 22, Запись кода марщрута в j-й регистр 28 марщрута осуществляется при наличии сигналов на j-м выходе дещифратора 13, и на выходе элемента И 49, поступающих на входы j-й группы элементов И 22. Сигнал с выхода элемента И 49 поступает на единичный вход триггера 50 распределения и через элемент ИЛИ 48 на обнуление счетчика 14 адреса. На этом итерация второго типа заканчивается.

Итерация третьего типа осуществляет назначение частей задания на свободные процессоры выбранного узла обработки.

С этой целью производится выдача содержимого j-ro регистра 2 готовности по сигналу с единичного выхода триггера 50 распределения на первые входы группы.элементов И 7. При этом на выходах некоторых

элементов И 5 появляется единичный сигнал Очевидно, что номера этих элементов определяются совпадением одноименных единичных разрядов в J-M регистре 2 готовности и регистре 4 сдвига. С выходов элементов И 5 сигналы поступают на сброс соответствующих триггеров регистра 4 сдвига и j-ro регистра 2 готовности через соответствующие элементы И 8 j-й группы. Одновременно с этим сигналы с соответствующих выходов элементов И 8 j-й группы поступают

на установку в единичное состояние триггеров i-ro регистра 27 числа процессоров на J-M узле обработки, назначенных на выполнение части задания. Если при этом в регистре 4 сдвига остались триггеры в единичном состоянии, о чем сообщает сигнал на

выходе элемента ИЛИ-НЕ 3, то с выхода элемента И 51 в регистр 4 сдвига подаются импульсы сдвига до тех пор, пока j-й регистр 2 готовности полностью не обнулен. Если все триггеры j-ro регистра 2 готовности установлены в нулевое состояние, то на выходе j-ro элемента И 9 появляется единичный сигнал, который через элементы ИЛИ 10 и 52 установит триггер распределения 50 в нулевое, а через элемент ИЛИ 38 триггер 40 узлов в единичное состояние. На этом

итерация третьего типа заканчивается.

Если при этом не все разряды регистра 4 сдвига- обнулены, то устройство повторяет итерацию первого типа поиска свободных узлов рве, выдавая разрешающий сигнал через элемент И 41 на прохождение, импульсов на счетный вход счетчика 11 адреса и запуск блока 12 памяти узлов.

При установке в нулевое состояние всех разрядов регистра 4 сдвига на очередном шаге выполнения итерации третьего типа

элемент ИЛИ-НЕ 3 выдает сигнал, который через элементы ИЛИ 34, 39, 46 и 52 сбрасывает триггеры 35, 40, 44 и 50 в нулевое состояние. Это означает, что задание распределено среди процессоров на выбранных узлах обработки. На этом заканчивается выполнение итерации третьего типа и выполнение второго этапа. На третьем этапе производится выдача сформированного заголовка задания на выходы 57 устройства. Сигнал с выхода элемента ИЛИ-НЕ 3 поступает на вход всех групп элементов И 29 и разрешает выдачу заголовка задания из регистров 25- 28 и 79 на выходы 57. При выдаче заголовка задания появляется сигнал на выходе -го (M,Z) элемента ИЛИ 30, если имеется единицы, в i-M разряде одного из регистров 28 маршрута. Этот сигнал поступает на вход Р-го счетчика 17 и увеличивает его содержимое на единицу, что обеспечивает учет занятости канала в -й линии связи. Работу устройства можно пояснить с помощью временных диаграмм (фиг. 4). В исходном состоянии все триггеры и счетчики устройства установлены в нулевое состояние. На выходе элемента ИЛИ 10 - единичный сигнал, на выходе элемента ИЛИ-НЕ 3 также единичный сигнал. Работа устройства начинается с момента времени Т1, когда на вход 54 и на регистр 61 требуемых данных поступают соответствующие коды (фиг. 4а). После сравнения числа требуемых и имеющихся в РВС свободных процессоров с учетом требуемых данных, на выходе «Больше либо равно схемы 32 сравнения появляется единичный сигнал, говорящий о том, что число свободных процессоров в системе не меньше числа требуемых (фиг. 46). По этому сигналу осуществляется прием кода числа требуемых процессоров на регистр 4 сдвига и установка триггеров 35 и 40 в единичное состояние (фиг. 4в и г соответственно). Таким образом. в момент времени Т2 заканчивается первый этап работы устройства и начинается второй этап с итерации первого типа. Выполнение итерации первого типа начинается с установки в единичное состояние триггера 40 узлов (фиг. 4д) и обращения к блоку 12 памяти по адресу, образованному кодом номера запрашивающего узла и содержимым счетчика 11 адреса. С появлением импульса на выходе элемента И 41 (фиг.,, 4 ж) из блока 12 памяти узлов считывается код номера узла (кандидата на выполнение задания) и на соответствую1цем выходе дешифратора 13 появляется сигнал, который разрешает выдачу содержимого выбранного регистра 2 готовности через группу элементов И 9. Если на выбраиузле нет свободных процессоров или необходимых данных, то на выходе элемента ИЛИ 10 сохраняется единичный сигнал (фиг. 4з), удерживающий триггер 40 узлов в единичном состоянии, благодаря чему через элемент И 41 (фиг. 4ж) на счетный вход счетчика 11 и запускающий вход блока 12 памяти узлов поступают тактовые импульсы генератора 37. При этом последовательно считываются коды номеров узлов из блока 12 памяти узлов до тех пор, пока не найден узел, на котором возможна обработка задания. В этом случае на выходе элемента ИЛИ 10 появляется нулевой сигнал, который через элемент НЕ 53 устанавливает триггер 44 маршрутов в единичное состояние (фиг. 4 и), который в свою очередь устанавливает триггер 40 узлов в нулевое состояние (фиг. 4п), который запреш,ает прохождение тактовых импульсов на счетчик 11 адреса. Этим обеспечивается запоминание номера узла, на котором возможно выполнение задания. Таким образом, в момент времени ТЗ заканчивается итерация первого типа. Итерация второго типа начинается с обращения к блоку 15 памяти маршрутов по адресу, образованному кодом номера запрашивающего узла, кодом номера узла обработки и содержимым счетчика 14 адреса. С появлением сигнала на выходе элемента И 45 (фиг. 4к) из блока 15 памяти маршрутов считывается код маршрута: Этот код анализируется с помощью элементов И 16. Считывание кодов маршрутов под воздействием тактовых импульсов продолжается до тех пор, пока не найден свободный маршрут. В этом случае на выходе элемента НЕ 21 (фиг. 4л) появляется сигнал, который, проходя через элемент И 49, устанавливает триггер 50 распределения в единичное состояние (фиг. 4м) Тем самым разрешается прохождение тактовых импульсов через элемент И 51 (фиг. 4н). Таким образом, в момент времени Т4 заканчивается выполнение итерации второго типа. Итерация третьего типа осуществляет назначение задания на свободные процессоры выбранного узла обработки. Для этого тактовые импульсы с выхода элемента И 51 поступают на вход сдвига кода регистра 4 сдвига до тех пор, пока все его триггеры ие установлены в нулевое состояние. Установка триггеров регистра 4 сдвига в нулевое состояние происходит при совпадении одноименных разрядов установленных в единичное состояние, регистра 2 готовности процессоров и регистра 4 сдвига. Одновременно с этим происходит запись единиц в соответствующие разряды регистра 27, что обеспечивает формирование части заголовка задания. Если окажется, что после поступления очередного тактового импульса с выхода элемента И 51 все триггеры регистра 4 сдвига установлены в ноль, то на выходе элемента ИЛИ-НЕ 3 появляется единичный сигнал, который устанавливает все триггеры в нулевое состояние (фиг. 4о). В противном случае может осуществляться переключение на итерацию первого типа (данный случай на диаграмме не отражен).

Таким образом, в момент времени Т5 закончится итерация третьего типа и второй этап работы устройства.

На третьем этапе работы устройства производится выдача сформированного заголовка на выход 57 и учет занятости каналов в линиях связи, для чего при наличии единиц в соответствующих разрядах кода марщрута сигналы с выхода элементов И 29 через элементы ИЛИ 30 поступают на входы счетчиков 17, добавляя тем самым единицу в соответствующий счетчик (фиг. 4п). На этом заканчивается третий этап работы устройства и его работа в целом по распределению задания для случая, когда все задание назначено на один узел обработки.

5457

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

Использование предлагаемого устройства в РВС позволит повысить пропускную способность системы за счет сокращения времени реакции РВС, измеряемого с момента поступления запроса на выполнение задания до приема задания узлом обработки к выполнению.

lU

D

a

77 TfT

A L

/

(i

6

u

Ж

ПТ