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

, 1462315 15 И 4 С 06 Е 9/4 8 ЖОИЗВ 8 ИСАНИЕ ИЗОБРЕТЕН числительныхЦель изобгоманиннь х систем х ил и управляющиретения - р возможностей за счет адаптации усткачественному составу по- .з аданий, Устройство содерсчетчиков, четыре блока памяти, четыре элемента ИЛИ, три э та И-Н 1 два элемента И-ИЛИ-НЕ,триггеров, три мультиплексора,риоритетных кийратора, восемьтров, три дешийратора, группуеров, генератор импульсов, Вяство вводится новая дисциплин нкпионированияя - мультипроцесе граммирование, состов и рещением нескольк роиства к ступающих жит группь СССР984.СР984. лемен ЕНИЯ автомае, а именм длясорам, и мультипро управлени сорноящее истеме. рограмм алл ельнь я в вы-. ессор 2Маай ементов И 5, блоки 6-9 памяти, ьРькодовых входов 10 и 11 уст- Жэлементы ИЛИ 12-15, элемен- Я-19, приоритетные иифраторы (4регистры 22-29, группу вы- вам до 30 номера задания устройства, фиплексоры 31-33, дещифраторы 34 группы кодовых входов 37-41 усттва, вход 42 считывания устройстгруппу кодовых входов 43 устройствходы 44 сброса, вход 45 запуска фф ройства, триггеры 46-51, генератор Ъьсов, элементы И-ИЛИ-НЕ 53 иенты И-НЕ 55-57, группу вхоотовности устройства, группунс выходов 59 устройства, у выходов 50 прерывания устройгруппыройстваты И 1620 и 21 в мульт36,ройс ва, ва, уст 52 импул 54, элем дов 58 г сигнальнь ппу ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ РАС 11 РЕДРДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относитсятике и вычислительной технино к приоритетным устройствраспределения заданий процепредназначено для использовсокопроизводительных многоп Изобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в высокопроизводительных многопроцессорных и многомашинных вычислительных и управляющих системах.Цель изобретения - расширение функциональных возможностеи устройства за счет адаптации к качественному составу поступающих заданий.На Анг, 1-3 дана схема предлагаемого устройства.Устройство содержит группу триггеров 1, группы счетчиков 2 и 3, группу элементоь ИЛИ-НЕ 4, группу ширение ункциональныхз 146ства, выход 61 записи устройства,элемент 62 задержки, группу информационных выходов 63 устройства, элемент ИЛИ-НЕ 64,Устройство работает следующим образом.Перед началом работы устройстваподачей импульсного сигнала на вход44 все элементы памяти устройства,кроме блока 7 памяти переводятся в,исходное нулевое состояние. При этомна группе выходов 63 устройства уста",новлены, единичные сигналы, а на. выхо, дах 30, 59 и 60 устройства - нулевые.Триггер 46 нулевым уровнем сигналана прямом выходе запрещает работу генератора импульсов.Блок 7 памяти выполнен в виде ПЗУ:и реализует следующую группу функций.Пусть Р - максимальное число параллельных программ, которые могут одновременно решаться в системе. Пусть врегистре 23 записан код числа и, ав регистре 24 записан код числа ш,где ш и Е Р). Таким образом, из блока 7 памяти 7 выбирается п-я страница, а на ней ячейка с номером ш. Вячейке ш занесено 1-разрядное число,(где 1 - число счетчиков 2 в устройстве и 1 кратно п=1,Р), имеющее вс(г.п+ш)-ом (где г.=О, (1-п)/и и ши)разряде единицу.Пуск устройства производится подачей единичного импульсного сигналана вход 45, При этом триггер 46 переводится в единичное состояние иединичным уровнем сигнала на прямомвыходе разрешает работу генератораимпульсов.Далее дпя работы устройства необходимо занести на его элементы памяти следующую информацию, Пусть на основании анализа поступающих на решение программ управляющий монитор выбирает и-программный режим работыустройства и заносит код числа и врегистр 23. Пусть также запускаемаяпрограмма будет решаться в системепод номером ш. Для этого в регистр24 заносится код числа ш. Далее всчетчики 2 первой группы с номерами1=дп+п, где х=О, (1-и)/и с входов10 заносятся в прямом коде коды сте.пени захода соответствующих вершинграфа программы. Соответствие вершины графа и счетчика 2 определяетсявесом вершины, представляющим собой величину максимального пути из 2315 данной вершины до конечной вершины графа программы, имеющего в качествевеса дуг длительности решения задач,При этом н-му счетчику 2 должна соответствовать вершина графа с наибольшим весом, (и+ш)-му счетчику 2вторая по весу вершина графа и т.д,Последнему счетчику 2 распределенному ш-й программе будет соответствовать конечная вершина графа, име-ющая нулевой вес, Такое соответствие вершин и счетчиков 2 позволяетминимизировать время решения параллельной программы, так как из некоторой совокупности запрашивающих решений заданий ( представляющих программу) и для .решения которых имеетсявся необходимая инФормация первымвыбирается на решение задание, имеющее больший вес. При этом, еслииспользуются не все счетчики 2, распределенные ш-й программе, то в нихзаносится произвольная ненулевая25 инФормация,Далее в счетчик 3 с номером ш заносится в дополнительном коде кодколичества заданий в программе, Позавершению каждого задания к содержиЗ 0 мому счетчика добавляется единица исигнал переполнения на сигнальномвыходе счетчика свидетельствует о завершении выполнения одноименной прогр аммы.Для управления ходом выполненияпрограммы ш в блоки 6, 8 и 9 памятизаносится следующая информация. Вблок б памяти заносится информация отопологии графа, описывающего набор4 О информационно связанных заданий,представляющих параллельную программу. По адресу, соответствующему кодузавершенного задания, относящегосяк программе ш, в блок б памяти зане 4 сено число, имеющее в соответствующем и-м разряде единицу, если из г-йвершины графа исходит дуга, ведущаяв 1-тую вершину графа. По адресу,соответствующему конечной вершинеграфа, в блок б памяти занесен нуль,В блок 8 памяти заносится информация, отражающая соответствие номерапрограммы ш и номера процессорногомодуля системы, распределенного дляего выполнения, По адресу, соответствующему номеру г некоторой вершины графа (счетчика 2 с номером г), в блок 8 памяти занесен код номера процессорного модуля, распределенного1 5 14623для выполнения задания , относящегося к программе ш,В блок 9 памяти заносится информация, отражающая соответствие кодазавершенного задания и номера счетчика 3 второй группы, распределенного данной программе, для учета выполненных заданийПо адресу, соответствующему коду завершенного задания 1, в блок 9 памяти занесено число, имеющее в соответствующем ш-мразряде (где щ - номер программы)единицу, если завершенное задание ,относится ц программе ш). 15На тактах, предшествующих К-му,в регистр 29 заносится в унитарномкоде код числа "3", а в регистр 26заносится двоичный код числа 1. НаК-м такте в регистр 25 заноситея двоичный код числа Р. На выходе элемента ИЛИ 13 появляется единичныйсигнал, который создает условия дляпрохождения синхроимпульса на (К+1)-мтакте через элементы И 17 и 18. Если на К-м такте не выполнялось условие готовности ни для одного из заданий, то на (К+1)-м такте триггер.48 останется в сброшенном состояниии единичном сигналом на инверсном 30выходе разрешит прохождение синхро - импульса через элемент И 18. На(К+1)-м такте синхроимпульс проходитчерез элемент И 18 и поступает на, синхровход.триггера 51, на информа. ционный вход которого поступает единичный сигнал с выхода третьего разряда регистра 29, Одновременно сэтим, если не поступало сигналов готовности от процессоров и триггер 4 40.остался в сброшенном. состоянии, синхроимпульс проходитчерез элемент И 17и поступает на синхровход триггера 49, на информационный вход которого приходит нулевой сигнал с выхода 45разряда регистра 29 (поскольку соответствующий блок памяти не был выбран)По заднему фронту синхроимпульсатриггер 51 переходит в единичноеБОсостояние. Сигнал высокого уровня напрямом выходе триггера 51 поступаетна вход элемента И-НЕ 57 и создаетусловия дляпрохождения синхроимпуль"са, а также поступает на вход элемента ИЛИ-НЕ 64 и формирует разрешениедоступа к блоку 8 памяти. При этомнулевой сигнал на прямом выходе триггера 48 поступает на управляющий 15 6вход мультиплексора 31 и создает условия для прохождения кода адреса ячейки 1 с выходов регистра 26 на адресный вход блока 8 памяти, на информационный вход которого поступает код из регистра 25. Синхроимпульс проходит через элемент И-НЕ 57 и формирует сигнал "Запись", по которому в ячейку 1 блока 8 памяти заносится код, Одновременно с этим через элемент ИЛИ 15 выдается сигнал высокого уровня на выход 61 устройства, который сигнализирует о том, что запись кода в блок 8 памяти завершена и можно приступить к занесению следующего слова информации. Этот же сигнал через элемент 62 задержки сбрасывает регистры 25 и 26 и снимает предпосылки для огерации Запись По синхроимпульсу триггер 51 сбрасывается и устройство возвращается в исходное состояние. В случае если на К-и такте возникнут предпосылки как для выдачи готового к выполнению задания, так и для операции запись в блок 8 памяти, то на (К+1)-м такте по синхрок.пульсу триггер 48 перейдет в единичное состояние и запретит осуществление операции запись, Таким образом, разрешается конфликт при обращении к блоку.8 памяти и отдается .приоритет операции выдачи задания на выполнение, Аналогичным образом осуществляется модификация содержимого блоков 6 и 9 памяти. При этом приоритет отдается операции приема кода завершенного задания. Поскольку операция выдачи задания на выполнение протекает при участии блока 8 памяти, а в операции приема кода завершенного задания принимают участие блоки 6 и 9 памяти (как это будет описано ниже), то возможна параллельная модификация соцержимого блока 8 памяти и прием кода завершенного задания, а также параллельная выдача задания на выполнение и модификация содержимого блока 6 или 9 памяти.После занесения всей необходимой для выполнения программы информации на вход 42 устройства подается единичный импульсный сигнал, который переводит в единичное состояние триггеры 1 группы, соответствующие программе ш. Нулевые сигналы на инверсных выходах выбранных триггеров разрешают прохождение нулевых сигналов с выходов счетчиков 2 первой группы, 1462315Выдача готового к выполнению задания производится следующим образом,. Поскольку начальная вершина графапрограммы представляет собой, соглас 5но начальной разметке, готовое длявыполнения задание, то в соответствующий ей счетчик 2 занесен нулевойкод и на его выходе будет низкий уровень сигнала. В результате чего, навыходе одноименного элемента ИЛИ-НЕ: 4 сформируется единичный сигнал,который пройдет на выход элементаИЛИ 12 и разрешит прохождение синхроимпульса через элемент И 16. Поскольку в устройстве может быть заФиксировано несколько готовых к выполнению заданий, то приоритетныйшифратор 20 сформирует номер наиболее приоритетного задания, которыйпо заднему Фронту синхроимпульса будет занесен в регистр 22. Одновременно с этим будет установлен триггер48. Единичный сигнал с прямого выхода триггера 48 поступает на вход эле мента И 19 и разрешает прохождениесинхроимпульса, поступает на управляющий вход мультиплексора 31, а также поступает на. вход элемента ИЛИ-НЕ64 и Формирует разрешение доступа к 30блоку 8 памяти. Код номера готовогок выполнению задания с выходов регистра 22 поступает на информационныйвыход 30 устройства, а также черезмультиплексор 31 поступает на адресный вход блока 8 памяти, в результате чего на вь 1 ход блока 8 памяти выдается .код номера процессора, распределенного дпя выполнения данногозадания. По синхроимпульсу на выходеэлемента И 19 сформируется единичныйимпульсный сигнал, который поступаетна управляющий вход дешифратора 34 иразрешает Формирование сигнала сброса триггера 1 группы, соответствующего выдаваемому заданию, а такжепоступает на синхровход регистра 28и отрицательным фронтом заносит внего код номера выбранного процессора с выхода блока 8 памяти,По синхроимпульсу триггер 48 сбрасывается в исходное состояние, а навыходе дешифратора 35, соответствующему выбранному процессору, Формируется импульсный сигнал, который поступает на выход 59 группы. По этойкоманде выбранный процессор принимает с системной магистрали .код номе"ра, готового к выполнению задания. По синхроимлульсу регистр 22 и 28сбрасываются в исходное нулевое состояниее.Прием кода завершенного заданияосуществляется следующим образом,Процессор, завершивший выполнение э адания, выставляет единичный сигнална соответствующий вход 58 устройства, По очередному сикхроимпульсуэтот сигнал запоминается в регистре27, В результате на выходе приоритетного шифратора 21 формируется двоичный код номера процессора, завершившего выполнение задания, а на выходе элемента ИЛИ 14 Формируется единичный сигнал, который поступает наинформационный вход триггера 47.Если в системе имеется несколькопроцессоров, завершивших выполнениезаданий, то приоритетный шифратор 21Формирует номер наиболее приоритетного из них,По отрицательному Фронту очередного синхроимпульса триггер 47 переводится в единичное состояние, Единичный сигнал с прямого выхода триггера 47 поступает на управляющие входы мультиплексоров 32 и 33 и разрешает прохождение на их выходы сигналов,поступает на входы элементов И-ИЛИ-НЕ53 и 54 и разрешает прохождениесинхроимпульса, а также поступает науправляющий вход дешифратора 36, Навыходе дешифратора 36, соответствующем наиболее приоритетному процессору, Формируется единичный сигнал,который поступает на одноименныйсигнальный выход 60 группы Получивкоманду, выбранный процессор снимаетсигнал готовности, выдает на системную магистраль код завершенного задания, С системной магистрали код завершенного задания поступает на информационные входы 43 устройства идалее через мультиплексоры 32 и 33,на выходах элементов И-ИЛИ-НЕ 53 и 54Формируются нулевые импульсные сигналы, которые поступают на входы разрешения доступа блоков 6 и 9 памяти.В результате этого на выходах блокаб памяти Формируются единичные импульсные сигналы, которые поступаютна вычитающие входы одноименных счетчиков 2 первой группы и корректируют готовность заданий, На выходе блока 9 памяти соответствующем программе, к которой относится завершенноезадание, формируется единичный им"пульсный сигнал, который поступает на счетный вход одноименного счетчика 3 и корректирует степень выполнения программы. По синхроимпульсу триггер 47 сбрасывается в исходноенулевое состояние.Наличие в устройстве регистров 22 и 28 позволяет совместить в пределах одного такта операции по выдаче номера, готового к выполнению задания и приему кода завершенного задания.После пуска программы производится занесение управляющей информации и пуск следующих программ в пределах 15 количества, определяемого коэффициентом мультипрограммирования,После выполнения всех заданий, относящихся к программе, на выходе счетчика 3 второй группы, соответст О вующего программе, появляется нулевой сигнал, который поступает на одноименный выход б 3 группы и свидетельствует об окончании програмж.25Фо рмул а из о бр ет ения Устройство для распределения заданий процессорам, содержащее первую группу счетчиков, первый блок памя О ти, первый элемент ИЛИ четыре элемента И, группу элементов И, группу элементов ИЛИ-НЕ, причем первая группа кодовых входов устройства соединена с информационными входами и синхровходами одноименных счетчиков35 первой группы, выходы элементов ИЛИ-НЕ группы соединены с одноименными входами первого элемента ИЛИ, выход которого. соединен с первым входом 40 первого элемента И, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей за счет адаптации устройства к качественному составу поступающих заданий, 45оно содержит вторую группу счетчиков, второй, третий и четвертый блоки памяти, второй, третий и четвертый элементы ИЛИ, элемент ИЛИ-НЕ, первый второй и третий элементы И-НЕ 50 ,первый и второй элементы И-ИЛИ-НЕ, шесть триггеров, три мультиплексора, первый и второй приоритетные шифраторы, восемь регистров, три дешифратора, группу триггеров, элемент задержки и генератор тактовых импульсов, причем каждЫй выход первого блока памяти соединен с вычитающим . входом одноименного счетчика первой группы, сигнальный выход равенстванулю. которого соединен с первым входом одноименного элемента ИЛИ-НЕгруппы, выходы элементов ИПИ-НЕ группы соединены с входами первого приоритетного шифратора, выходы которогосоединены с группой информационныхвходов первого регистра, выходы первого регистра являются группой выходов номера задания устройства и соединены с группой информационных входов первого мультиплексора, а такжес группой входов первого дешифраторакаждый выход которого соединен с нулевым входом одноименного триггерагруппы, первая группа кодовых входов устройства соединена с группойинформационных вхоцов и синхровходомвторого регистра, выходы которогосоединены со старшими разрядами адреса второго блока памяти, втораягруппа кодовых входов устройствасоединена с группой информационныхвходов и синхровходом третьего регистра, выходы которого соединены смладшими разрядами входа адреса второго блока памяти, каждый выход которого соединен с первым входом одноименного элемента И группы, входсчитывания устройства соединен с вторыми входами элементов И группы, выходы которых соединены с единичнымивходами одноименных триггеров группы,инверсные выходы триггеров группысоединены с вторыми входами одньименных элементов ИЛИ-НЕ группы, третьягруппа кодовых входов устройствасоединена с группой информационныхвходов и синхровходом четвертого регистра, выходы которого соединены синформационными входами первого, третьего и четвертого блоков памяти, атакже с входами второго элемента ИЛИ,выход которого соединен с первыми входами второго и третьего элементов И,четвертая группа кодовых входов устройства соединена с группой информационных входов и синхровходом пятого регистра, выходы которого соединены с второй группой информационныхвходов первого и первыми информационными входами второго, третьего мультиплексоров, пятая группа кодовыхвходов устройства соединена с вторыми группами информационных входов второго и третьего мультиплексоров, входсброса устройства соединен с нулевымвходом первого триггера, вход запускаустройства соединен с единичным входом первого триггера, прямой выход которого соединен с входом запуска геНератора тактовых импульсов, первый выход которого соединен с вторым вхором первого элемента И и с синхровхо(ом второго триггера, выход первого эцемента И соединен с синхровходомервого регистра и с синхровходом тре 1 О .,ьего триггера, второй выход генерат ра импульсов соединен с вторыми одами второго и третьего элементовс первым входом четвертого злемен" тй И и с первыми входами первого и в орого элементов И-ИЛИ-НК, третийход генератора тактовых импульсов с единен с синхровходом шестого ре.г стра, с нулевыми входами второго и третьего триггеров, с первыми вход ми первого, второго и третьего э ементов И-НЕ и с управляющим входом в орого деширатора, четвертый выходнератора тактовых импульсов соеди" н н с входом сброса первого регист р , с нулевыми входами четвертого,того и шестого триггеров и с входом сброса седьмого регистра, шестая группа кодовых входов устройства соеданена с информационным входом и ЗО снхровходои восьмого регистра, вых 1 эды разрядов которого соединены соответственно с информационвлии входами четвертого, пятого и шестого триггеров группа сигнальных входов готОвности устройства соединена с группой входов шестого регистра, выходы которого соединен с входами второго приоритетного шифратора, выходы втор 6 го приоритетного шиФратора соединЕны с информационными входами третьегф дешифратора и с входами третьего элемента ИЛИ, выход которого соединЕн с ин 4 юркационным входом второго триггера, вход разрешения доступа второго блока памяти соединен с вхо- дами логического нуля устройства, выходы третьего блока памяти соединены с инфориациокными входами седьмого рЕгистра, выходы которого соединены с информационными входами второго дешифратора, выходы которого являются группой сигнальных выходов устройстве, прямой выход второго триггера соедйнен с управляющими входами второго и третьего мультиплексоров, с вторы 55 мй входами первого и второго элементов И-ИЛИ-НЕ и с управляющим входом третьего дешифратора, выходы которо торого соединен с входом раздостула третьего блока памяды первого, второго и третьентов И.-НЕ соединены соответс входами разрешения записи четвертого и третьего блоков выход к решения ги, вых о элеметвенноерво го ми четвертого эл и с вход ЛИ, выхо которого я вля ется ом записи устройства з эпемент задержки с етвертого и пятого реыход четвертого блока ментасигнали сое ным выход инеи чере сброса ч , каждый в вход гистро памяти именно соединен со счетным входом одноо счетчика второй группы, седьмаякодовых входов устройства соеди-,нформационными и синхровходамиов второй группы, выходы переполоторых являются группой информавыходов устройства,па иена с ет ени ионны го являются группой выходов прерывания устройства, инверсный выход второго триггера соединен с третьим входом второго элемента И, выход которого соединен с синхровходами четвертого и пятого триггеров, информационный вход третьего триггера соединен с выходом логической единицы устройства, инверсный выход третьего/ триггера соединен с третьим входом третьего элемента И выход которого соединен с синхровходом шестого триггера, прямой выход третьего триггера соединен с управляющим входом первого мультиплексора, с первым входом элемента ИЛИ-НЕ и с вторым входом четвертого элемента И, выход которого соединен с управляющим входом первого дешифратора и синхровходом седьмого регистра, выходы первого, второго и третьего мультиплексоров соединены соответственно с адресными входами третьего, первого и четвертого блоков памяти, прямой выход четвертого триггера соединен с вторым входом первого элемента И-НЕ и с третьим и четвертым входами первого элемента И-ИЛИ-НЕ, выход которого соединен с входом разрешения доступа первого блока памяти, прямой выход пятого триггера соединен с вторым входом второго элемента И-НЕ и с третьим и четвертым входами второго элемента И-ИЛИ-НЕ, выход которого соединен с входом разрешения доступа четвертого блока памяти, прямой выход шестого триггера соединен с вторым входом третьего элемента И-НЕ и с вторым входом элемента ИЛИ-НЕ, 14 б 23151462315 Составитель М.Кудряиев1 О.Середа Техред А.Кравчук Корректор Л. Патай а Производственно-иэдательсккй комбинат "Патент", г, Ужгород, ул. Гагарина,10 ЗакаВНИИПИ 3/47 Тираж 667осударственного комитета по изо 113035, Москва, Б, Р Подписноетениям и открытиям при ГКНТ ССакая наб д. 45