Устройство для распределения групповых заявок по процессорам Советский патент 1986 года по МПК G06F9/50 

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах.

Цель изобретения - повьшение быст- родействия.

На чертеже приведена структурная схема устройства.

Устройство содержит группу регистров 1 хранения, группу элементов 2, буферный регистр 3, группу дешифраторов 4, группу элементов ИЛИ 5, группу элементов И 6, шифратор 7, группу схем 8 сравнения, блоки элементов И 9 группы, регистр 10 сдвига блоки элементов И 11 группы, элемент ИПИ-НЕ 12, элемент ИЛИ-НЕ 13, группу элементов ИЛИ 14, группу элементов И 15, блоки элементов И 16 группы, регистр 17 готовности процессоров, генератор 18 импульсов, элемент И 19 триггер 20 запуска, группу элементов

И 21, элемент 22 задержки, элемент 23 задержки, элемент 24 задержки, триггер 25 управления сдвигом, элемент И 26, элемент И 27, элемент И 28,вход 29 запуска устройства, вход 30 сброса устройства, группу входов 31 заявок устройства, группу информационных выходов 32 устройства и группу информационных входов 33 устройства.

Устройство работает следующим образом,

Исходное состояние устройства характеризуется тем, что регистры 1, 3, 10, триггеры 20 и 25 установлены в состояние О (не показано).

Работа устройства состоит из трех этапов и начинается по сигналу запуска, поступакицему по входу 29 и устанавливающему триггер 20 в состояние ti 11 I «

На первом этапе формируется очередь заявок, поступаяяцих по входу 31 и заполнянщих регистры 1 хранения, ndica заявка из последнего регистра 1 не перепишется в буферный регистр 3,

На втором этапе производится выбор приоритетной заявки из группы, при- нятбй в регистр 3, и передача кода числа потребных процессоров приоритетной заявки в регистр 10 сдвига

На третьем этапе выполняется распределение процессоров приоритетной заявки и передача кода номера за/тачи свободным процессорам. После распределения процессоров приоритетной заявки производится гашение разрядов

распределенной заявки, а затем выбор очередной по приоритету заявки из группы в регистре 3 и распределение свободных процессоров. Этот этап про- должается, пока заявки группы не будут обсуждены. Завершением его является нулевое состояние регистра 3. После этого устройство переходит к выполнению первого этапа, на котором в регистр 1, принимается заявка по входу 31. Из последнего регистра 1 очередная заявка передается в регистр 3, чем начинается второй этап. В дальнейшем устройство работает аналогично .

Формирование очереди на первом этапе производится следукнцим образом.

По первому импульсу генератора 18 через элемент И 19, последний элемент И 21 группы, элемент 22 задержки и первый элемент И 21 группы заявка по входу 31 принимается в первый регистр 1. Элементы И 21 открыты по первым входам единичньм сигна- лом с выхода элементов ШШ-НЕ 12, так как регистр 3 находится в состоянии О.

Регистры 1 хранения и буферный регистр 3 имеют одинаковую структуру. Каждый из этих регистров для каждой

заявки в группе содержит 4 группы разрядов. В свою очередь, группа разрядов обеспечивает хранение кода числа потребных процессоров для решения задачи по данной заявке, кода приоритета заявки в группе и КОДА номера задачи. Таким образом, групповая заявка на входе 31 содержит коды числа потребных процессоров, коды приоритетов и коды номеров задачи..

Принятая в регистр 1 заявка при непрерывном потоке по тактовому сигналу генератора 18,поступающему через элементы И 21 на управлякшше входы регистров 4, продвигается по регистрам 1. По соответствующему тактовому сигналу первая заявка оказывается в последнем регистре 1, а по следующему сигналу она из последнего регистра 1 переписывается в буферньА регистр 3. Элемент 22 за- .держки необходим для обеспечения записи заявки в регистр 3 до того, как на входах регистра 1 появляется следующая заявка. Как только заявка оказывается в регистре 3 на выходе эле- ,мента ШШ-НЕ 12 единичный сигнал сни

мается, ,

3

при этом элемент И 21 закрывается, чем запрещается подача тактвых импульсов.

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

В регистрах 1 сформирована очере групповых заявок, на входе 31 сохраняется очередная групповая заявка, в регистре 3 находится первая заявк

Так как регистр сдвига находится состоянии О , на выходе элемента ИЛИ-НЕ 13 имеется единичный сигнал, которым открыт по второму входу элемент 27, а по инверсному - закрыт элемент И 26. Так как триггер 25 находится в состоянии О, то единичным сигналом с нулевого его выхода открыты по вторым входам элементы И 9.

На втором этапе посредством дешифраторов 4 двоичные коды приоритетов заявок преобразуются в однопозицион- ные. Наивысшему приоритету соответствует минимальный, отличный от нуля, код. Одноименные выходы дешифраторов 4 объединяются одноименньми элементами ИЛИ 5. При этом номер элемента ИЛ соответствует значению приоритетного кода. Посредством элементов И 6,вклю ченныхпо приоритетной схеме с Выходами элементов ИЛИ 5, осуществляется выбор наиболее приоритетного сигнала из совокупности возбужденных выходов элементов ИЛИ 5 так, что на входах шифратора 7 формируется унитарный код, содержащий единицу в определенной позиции. Номер этой позиции соответствует значению приоритетного кода. Сигналы двоичного кода с выхода шифратора 7 сравниваются с двоичными кодами приоритетов заявок в группе в соответствующих схемах 8 сравнения. При этом единичньй сигнал формируется только одной из схем 8 сравнения. Этим сигналом открываются элементы И 9 соответствующей группы,и код числа потребных процессоров приоритетно заявки передается в регистр сдвига.

Посредством элемента 23 задержки обеспечивается задержка импульса генератора 18 на единичном входе триггера 25 так, чтобы он появился после установления информации на выходах регистра 10.

После приема информации в регистр 10 сдвига снимается единичный сигнал р выхода элемента ШШ-НЕ 13, тем са

мым открывая ному входу.

элемент И 26 по инверсЗадержанным импульсом генератора 18 устанавливается в 1 триггер 25, При этом снимается единичный сигнал с вторых входов элементов И 9,блокируя тем самым передачу сигналов с их выходов в регистр 10 сдвига. Сигналом с единичного выхода триггера 25 управления сдвигом открывается элемент И 28 по первому входу, тем самым устройство переходит к выпол- ненгао третьего этапа.

Пусть в буферный регистр 3 принята групповая заявка, содержащая три запроса, которым установлены следук - щие двоичные коды приоритета: 3,1,2, причем для первого запроса требуется решить задачу с номером на трех процессорах, для второго - на одном процессоре, а для третьего - задачу на двух процессорах.

При этих условиях единичные сигналы кода приоритета после преобразования их дешифраторами 4 поступают на входы элементов ИЛИ 5 следующим образом: с третьего выхода дешифратора 4 на первый вход элемента ИЛИ 5д; с первого выхода дешифратора 4 J на второй вход элемента ШШ.5« ; с второго выхода дешифратора 4 на

2530 д 5

0 5

5

2третий вход элемента ИЛИ 5

Таким образом, на выходах элементов ИЛИ 5 формируется следующий код: 111...,0. Единичным сигналом с выхода элемента ИЛИ 5, закрываются по nepBim инверсньм входам все элементы И 6 при этом на входы шифратора 7 подается унитарный код следующего вида: 10000...О, т.е. имеющий единичное состояние на первом входе.Шифратор 7 преобразует его в двоичный код единицы, т.е. 0....1, поступающий на первые входы всех схем 8 сравнения . При этом сравнение происходит в схеме 8,,единичным сигналом с выхода которой код числа требуемых процессоров для второго запроса через элементы И 9 записываются в регистр 10 сдвига. Кроме того, единичным сигналом с выхода схемы 8 сравнения открываются элементы И„ и элемент И2 по первому входу.

На третьем этапе посредством импульсов генератора, поступающих через открытый элемент И 28 на вход сдвига регистра 10, производится поиск и

распределение свободных процессоров вbsбpaннo fз запросу

Пусть для указанного примера в системе имеется четыре процессора, причем от второго процессора во вто- ром разряде регистра 17 готовности процессоров принят сигнал готовности.

Так как число потребных процессоров в регистре 10 сдвига указывается наличием единиц в смежных младших его разрядах, то совпадение единиц в элементе И 15. происходит по пер- BOivry импульсу генератора 18, При этом единичным сигналом с выхода элемен- та И 15,2 открываются элементы И IS, через которые код номера задачи из буферного регистра 3 передается группе выходов 32 устройства. Единичным сигналом с выхода элемента РШИ 11 устанавливаются в состояние О вторые разряды регистров 10 и 11. После этого регистр 10 оказывается в состо- Ялчии и через элемент ЙЛЙ-НЕ 13 открываются по третьим входам элементы И 2, Задержанным импульсом элемента 24 задеряжи время которого определяется временем переходных процессов в регистре. 10 и элементе йЛИ-НЕ 13, устанавливается в О группа разря- дов регистра 3 второго запроса и триггер 25 управления сдвигом.

После этого производится выбор . очередного приоритетногоj третьего запроса указанным образом,

По заверЕгенйи распределения процес соров всем трем запросам регистр 3 оказывается в состоянии О, при этом на выходе элемента ИЛИ-НЕ 12 формируется единичный сигнал, открывающий элементыИ 21.По очередному тактовому сигналу генератора 18 производится сдвиг групповых заявок в регистрах 1 и передача очередной заявки для распределения процессоров. В дальнейшем работа устройства аналогична.

Формула изобретения

Устройство для распределения груп повых заявок по процессорам, содержащее регистр сдвига, группу регистров хранения, две группь элементов И nepBjTO группу элементов ИЛИ, первый элемент Hj регистр готовности процес соров, вьжодь которого соединены с первыми входами элементов И первой rpynnbis вторые входы которых соединены с группой, выходов регистра сдвига входы сброса которого соединены с соответствующими В:.,-ходами элементов ИЛИ первой группы, с соответствующими входами сброса регистра готовности процессоров, группа информационных входов первого регистра хранения группы является группой входов заявок устройства, тактовый вход каждого регистра хранения группы, кроме последнего, соединен с выходом соответствующего элемента И второй группы, грулпа информационных выходов каждого регистра хранения группы, кроме последнего, соединена с группой информационных входов следующего регистра хранения группы, вход сдвига регистра сдвига соединен с выходом первого элемента И, первый вход каждого элемента И второй группы, кроме первого и последнего g соединен с выходом предыдущего элемента И этой группы, второй вход каждого элемента И второй группы соединен с первым входом каждого последующего элемента И этой группы, о т - ,л,и чающееся тем, что, с целью повьшения быстродействия, в него введены третья и четвертая группы элементов И, три группы блоков элементов И, вторая группа элементов ИЛИ, три элемента задержки, группа дешифраторов, шифратор, группа схем сравнения. Два элемента ИЛИ-НЕ, второй, третий и четвертый элементы И, триггер запуска, триггер управления сдвигом, буферный регистр и генератор импульсов, выход которого соединен с первым входом второго элемента И, второй вход которого подключен к единичному выходу триггера запуска единичньш и нулевой входы которого являются управляющими входами запуска и сброса устройства соответственно, выход первого элемента И через первьй элемент задержки соединен с первым прямым входом третьего элемента И, и с первыми входами элементов И третьей группы, выход последнего элемента И второй группы соединен с тактовым входом буферного регистра и через второй элемент задержки - с вторым входом первого элемента И второй группы и с тактовым входом последнего регистра хранения группы, группа информационных выходов которого соединена с соответствующей группой информационных входов буферного регистра, выход i-ro

712544858

n, n - число заявок) раз- блоков элементов И первой группы соединены с информационными входами ре- ; регистра сдвига, выходы которого подключены к входам второго элемента ИЛИ-НЕ, 5 выход которого соединен с третьими входами элементов И третьей группы, с инверсным входом четвертого элемента И и с вторым входом третьего элемента И, выход третьего элемента И 10 соединен с,нулевым входом триггера управления сдвигом, единичный вход которого соединен с выходом четвертого элемента И, единичный выход триггера управления сдвигом соединен 15 с первым входом первого элемента И, выход каждого элемента И третьей группы соедине1Г с входом сброса разрядов одною4енной rpymnj буферного регистра, выкоды всех блоков элемен(1 1,...,

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

входом j-го (J 1,2,..., п) элемен- 20 тов И второй группы подключены к ин- та И четвертой группы, начиная с пер- ф(ч мационным входам блоков одноименвого, выходы элементов ИЛИ второй группы соединены с соответствующими инверсными входами всех последующих

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

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

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

элементов И первой группы подключенысоединены через третий элек нулевому выходу триггера управле-(мент задержки с выходом поения сдвигом и к первому прямому входУ45 леднего элемента И второй гручетвертого элемента И, выходы всехппы.

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислиIn ,, I ё йОу й| тельных системах. Цель изобретения - повышение й 1стродействия устройства. Новым в устройстве является использование двух триггеров, генератора импульсов, трех элементов задержки, буферного регистра,t -1 групп регист- ,ров хранения (Р - число заявок в группе), двух элементов ИЛИ-НЕ, двух групп элементов И, группы элементов ИЛИ, шифратора, группы схем сравнения, трех групп блоков элементов И, трех элементов И и связей указанных элементов и узлов, что обеспечивает достижение цели изобретения. 1 кп. (Л С

Редактор И. Касарда

Составитель М. Кудряшев

Техред И.Попович Корректор Л. Патай

Заказ 4722/53Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4