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

(9)4 006 Р ПИСАНИЕ ИЗОБРЕТЕНИ ЬСТВ ТОРСМОМУ СВИД854 ерОСУДАРСТВЕККЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЭОБРЕТЕКИЙ И ОТКРЬ( )(57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ, соджащее регистр готовности процессоров,элемент ИЛИ, п блоков элементов И,где п - число процессоров, группуэлементов И, элемент И и группу ре"гистров хранения, причем первая группа информационных входов первого регистра хранения группы является первойгруппой информационных входов устройства, вторая группа информационных входов первого регистра хранения группыявляется второй группой информационныхвходов устройства, управляющий входкаждого регистра хранения группы соединен с выходом соответствующего эле"мента И группы, первая и вторая группы выходов каждого регистра хранениягруппы, кроме последнего, соединенысоответственно с первой и второйгруппами информационных входов последующего регистра хранения группы,первая группа выходов последнегорегистра хранения группы соединенас группой информационных входов каждого блока элементов И, группа выходов каждого блока элементов И подключена к одноименной группе информационных выходов устройства, группа информационных входов регистра готовности процессоров соединена с группой сигнальных входов устройства,первые входы элементов И группы обьеди-, нены между собой, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия устройства за счет организации параллельного распределения задач между процессорами, в него введены коммутатор, элемент ИЛИ-НЕ, формирователь импульсов, причем группа информационных входов коммутатора подключена к группе выходов последнего регистра. хранения группы, группа управляющих входов коммутатора под- Я ключена к группе выходов регистра готовности процессоров и входам элемен. та ИЛИ, каждый выход первой группы выходов коммутатора подключен к соответствующему входу группы обнуляющих Ф входов регистра готовности процессоров и к. управляющему входу соответствующего блока элементов И, вторая группа выходов коммутатора подключена к входам элемента ИЛИ-НЕ,. выход которого подключен к управляющему входу регйстра готовности процессоров и первому входу последнего элемента И группы,.второй вход которого подключен к выходу элемента ИПИ, а выход - к первому входу элемента И, второй вход.которбго подключен к выходу младшего разряда последнего ) регистра хранения группы, а выходк входу формирователя импульсов, выход которого подключен к последнему входу элемента ИЛИ-НЕ, выход каждого элемента И группы, начиная с последнего, подключен к второму входу предыдущего элемента И группы.117179Изобретение относится к областивычислительной техники и предназначено для распределения задач междупроцессорами в мультипроцессорныхсистемах. 5Цель изобретения - повышениебыстродействия устройства за счеторганизации;параллельного распределения задач между процессорами.На чертеже представлена структур; 10ная схема предлагаемого устройства,Устройство содержит первую группу информационных входов 1 устройства, вторую группу информационныхвходов 2 устройстве, группу регистров. 3 хранения, группу элементов И4, коммутатор 5, группу информационных входов б коммутатора 5, группувходов 7 коммутатора 5, первую группу выходов 8 коммутатора 5, вторую 2 Огруппу выходов 9 коммутатора 5, элемент ИЛИ-НЕ 10, элемент ИЛИ 11 регистр 12 готовности процессоров,блок элементов И 13,группы информационных выходов 14 устройства, 25группу сигнальных входов 15 устройства.Устройство работает следующимобразом,В исходном состоянии информацияо задачах на группах информационныхвходов 1 и 2 устройства отсутствует,Регистры 3 хранения группы обнулены,на входах 6 и выходах 8 и 9 коммутатора 5действуют нулевые сигналы. Поскольку на35выходах 8 коммутатора 5 нулевая информация, то нулевые сигналы действуют на управляющих входах блоковэлементов И 13 и на группе входовсброса регистра 12 готовности про Оцессоров. Так как .все процессорысвободны, то регистр 12 готовностипроцессоров заполнен нулями и нагруппе его выходов, следовательно,на входах элемента ИЛИ 11 и на груп пе входов 7 коммутатора 5 действуютединичные сигналы. Единичный сигналс выхода элемента ИЛИ 11 поступаетна второй вход последнего элементаИ 4, на первом входе которого, а так Оже на первых входах остальных элементов И 4, действует единичный сигналс выхода элемента ИЛИ-НЕ 10, таккак на всех его входах действуютнулевые сигналы. 55 Единичный сигнал с выхода последнего элемента И 4 поступает на управляющий вход последнего регистра 3 хранения группы, на первый вход элемента И 15 и на второй вход предпоследнего элемента И 4, с выхода которого единичный сигнал поступает науправляющий вход предпоследнего регистра 3 хранения и на второй входпредыдущего элемента И 4 и т.д.,кроме первого элемента И 4,с выхода которого единичный сигнал поступает только на управляющий вход первогорегистра 3 хранения группы. На второмвходе элемента И 15 действует нулевойсигнал с выхода 6 младшего разрядапоследнего регистра 3 хранения группы.Нулевой сигнал с выхода элемента И 15поступает на вход формирователя 16,с выхода которого нулевой сигнал пода.ется на последний вход элемента ИЛИНЕ 10. Нулевые сигналы с первой группы входов последнего регистра 3 хранения группы поступают на группыинформационных, входов каждого блокаэлементов И 13 группы и на группувыходов 14. Программа "Планировщик операционной системы" (ЭПП ОС) строит упоря- доченный по приоритетам список задач и выдает информацию о задачах на первую и вторую группу информационных входов 1 и 2 устройства, причем на первую группу выдается номер задачи, а на вторую - количество потребных для ее решения процессоров в позиционном коде. Так как на управляющих входах регистров 3 хранения действуют единичные сигналы с выходов соответствующих элементов И, то информация о задачах последовательно переписывается с регистра на регистр, Первая задача, поступающая в устройство для распределения, записывается в последний регистр 3 хранения, предпоследняя - в первый регистр хранения, а последняя остается на первой и второй группах информационных входов 1 и 2 устройства.Первая задача, поступающая на распределение по процессорам, записывается в последний регистр 3 хранения группы, на первой группе выходов которого выделяется номер задачи, а на второй - количество потребных для ее решения процессоров.Код номера задачи с первой группы выходов регистра хранения поступает .на группы информационных входов каждого блока элементов И 13, которые находятся в закрытом состоянии. По117 10 20 3зиционный код количества потребных для решения задачи процессоров с второй группы выходов последнего регистра 3 хранения подается на группу информационных входов 6 коммутатора 5, Так как для решения задачи всегда требуется минимум один процессор, то на выходе младшего разряда последнего регистра 3 хранения и, следовательно, на входе 6 коммутатора 5 при поступлении на распределение любой задачи всегда будет единичный сигнал, который поступает на второй вход элемента И 15, на первом входе которого действует единичный сигнал с выхода элемента И 4, единичный сигнал с выхода элемента И 15 подается на вход формирователя 16. Единичный сигнал с выхода .формирователя 16 поступает на последний вход элемента ИЛИ-НЕ 10, На выходе элемента ИЛИ-НЕ 10 устанавливается нулевой сигнал, который подается25 на первые входы всех элементов И 4, закрывая их, Нулевые сигналы с выходов элементов И 4 поступают на управ ляющие входы соответствующих регистров 3 хранения, блокируя дальнейший сдвиг информации по регистрам. Одно 30 временно нулевой сигнал с выхода элемента ИЛИ-НЕ 10 подается на управ,ляющий вход регистра 12 готовности процессоров, с выхода которого инфор" мация о наличии свободных процессоров, выдаваемая в позиционном коде, поступает на группу входов 7 коммутатора 5 и на входы элемента ИЛИ 11.Единичные сигналы с выходов 8 коммутатора 5 поступают на управляю щий вход соответствующего блока элементов И 13 и на информационные входы триггеров регистра 12 готовности процессоров, соответствующих назначенным на решение задачи процессорам, 45 Блоки элементов И 13, соответствующие назначенным на решение задачи процессорам, открываются и код номера задачи с первой группы выходов последнего регистра 3 хранения поступает в назначенные процессоры, которые начинают решение задачи.По окончании цикла распределения единичный сигнал с выхода формирователя 16 снимается и, если требования задачи полностью удовлетворе" ны, т.е. нет единичных сигналов на выходах 9 коммутатора 5, на выходе 1791 4элемента ИЛИ-НЕ 1 О появляется единичный сигнал, который подается на С-входы триггеров регистра 12 готов ности процессоров и на первые входы элементов И 4. По фронту этого сиг" нала триггеры, на информационных входах которых действуют единичные сигналы, соответствующие назначенным для решения задачи процессорам, устанавливаются в единичное состояние, единичные сигналы с инверсных выходов этих триггеров и, следовательно, с соответствующих входов элемента ИЛИ 11,.снимаются, Если в .процессе распределения окажутся назначенными все процессоры, то на вы" ходе элемента ИЛИ 11 устанавливается нулевой сигнал, который блокирует поступление новых задач на распределение до момента освобождения хотя бы одного процессора. Таким образом после окончания цикла распределения на всех входах последнего элемента И 4 действуют единичные сигналы.Единичный сигнал с выхода элемента И 4 поступает на управляющий вход последнего регистра 3 хранения, осуществляя сброс информации, и одновременно подается на второй вход предпоследнего элемента И 4, на первом входе которого действует единичный сигнал с выхода элемента ИЛИ-НЕ 10. Единичный сигнал с выхода элемен" та И 4 поступает на управляющий вход предпоследнего регистра 3, осуществляя перепись его содержимого в последний регистр 3 хранения, и на второй вход предыдущего элемента И 4, единичный. сигнал с выхода которого разрешает перепись информации предпоследнего регистра 3 хранения, вы" полняя описанные действия, и т.д.Таким образом, реализуются операции сдвига информации о задачах по регистрам хранения и поступления на распределение очередной задачи. Следовательно, необходимыми достаточным условием для поступления на распределение новой задачи является окончание цикла распределения и наличие хотя бы одного процессора, т.е. наличие единичных сигналов на обоих входах последнего элемента И 4.Если по окончании времени цикла распределения формируемым Формирователем 16 задача не полностью распре" делена по процессорам, о чем свидетельствует наличие единичных сигналов1171791 оставитель М.Кудряшевехред Л.Мартяшова орректор Л.Пилипенк едактор Л, Гратилл Тираж 710осударственного комитета ССам изобретений и открытийсква, Ж, Раушская наб.,Заказ 48 б 4/41ВНИИПИ Подпис по дел13335, М 4/"Патент", г.ужгород, ул.Проект Фили на каком-либо выходе 9 коммутатора 5, на выходе элемента ИЛИ-НЕ 10 будет нулевой сигнал, который подается на первый вход последнего элемента И 4, блокируя поступление на распределение следующей задачи. Так как мультипроцессорная система загружается задачами различной временной степени трудности поочередно, то процессоры закан О чивают решение задач динамично. После окончания решения какой-либо задачипроцессор выставляет единйчный сигнал готовности, который с группы входов 15 подается на соответствующий вход группы входов регистра 12 готовности процессоров. Единичный сигнал с выхода последнего поступает на вход 7распределяющего блока 5 и на входэлемента ИЛИ 11, с выхода которогоон подается на второй вход последнего элемента И 4. Наличие единичногосигнала на входе 7 позволяет назначить освободившийся процессор на решение перераспределенной задачи. Назначение производится описанным образом.По окончании распределения всего списка заданий устройство возвращается висходное состояние. Применение предлагаемого изобретения позволяет повысить быстродействие устройства.