Устройство для управления распределением задач Советский патент 1979 года по МПК G06F9/50 G06F15/163 

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

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

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

Предлагаемое устройство содержит матрицу 1 ячеек 2 памяти, блок 3 анализа строк-, содержащий приемный регистр 4, узел 5 опроса, регистр б назначений, шифратор 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, 34, 35, 36, 37, 38, 39, элементы НЕ 40 и 41. Ячейка 2 памяти содержит триггер 42, 43, 44, элементы ИЛИ 45, 46, 47 48, элементы И 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, элемент НЕ 60. .- длагаемое устройство работает coi c-iecTHo с ассоциативными процессо рами следующим образом. Пусть в оперативной памяти каждо го . i-ro процессора по адресу j{ J 1.., М) хранится полноразряднЪе число С|,-- коэффициент эффективности выполнения 1-м прибором j-и работы (табл. 1). Требуется получить оптимальное по критерию максимальной эффективно ти и максимального числа назначений распределение работ по приборам. Ё табл. 1 представлена матрица э фективностей выполнения М pab6t N приборами. Задача решается итерационно. Каж дая итерация состоит из двух этапов 1. Формирование в ассоциативных процессорах двоичной матрицы В выпол нимости работ приборами (табл. 2) п правилу: hf если j-я работа выполия ется i-M прибором с эффек/тивностью Ci-j С О, в про У тивном случае. критерий эффективности. где CK В табл. 2 представлены матрица вы полнимости работ приборами и запись матрицы В в триггеры 42 ячеек памяти 2 матрицы 1. 2. Определение плана однозначных распределений работ по прибЬрам по критерию максимального числа назначений. После выполнения каждой итерации сравнивается число вновь полученных назначений с полученными в предьщущей итерации и, если их не меньше, переходят к следующей итерации с изменением величины критерия эффективности . Решение задачи оканчивается, если назначений получилось меньше, чем в предшествующей итерации, результирующим считается план, полученный в предыдущей итерации. Работа устройства на К-й итерации. К1. Формирование матрицы выполнимости работ В. К1.1. Считывание из оперативной памяти каждого i-ro процессора на арифметико-логическое устройство по адресу i , хранящемуся на регистре ад реса, коэффициента Сц , соответствую щего назначению i-ro прибора на j-ю работу по результату (к-1)-й итерации. К1.2. Выполнение одновременно на арифметико-логических устройствах всех процессоров блока ассоциативных параллельных процессоров, по командам от блока единого управления, операции поиска максимального (минимального) числа в группе. Результатом опердции является выявление индикаторе одного из процессоров,3 котором хранится искомое число - Сц, и вывал Сц в блок единого управления на регистр признака опроса. Замечание. В первой итерации пункты 1.1 и 1.2 отсутствуют, а на регистре опроса блока единого управления процессорами устанавливается константа Cj . К1.3. Последовательное считывание из оперативной памяти по адресам от первого до М-ного коэффициента эффективности в арифметико-логическое устройство у всех процессоров и выполнение групповых операций ассобольшециативного сравнения на (или меньше) чисел в арифметикологических устройствах с числом С и индикация результатовсравнений в каждом процессоре на индикатор. К1.4. Последовательная перезапись результатов сравнения с индикаторов всех процессоров на первые триггера 42 ячеек 2 первого столбца матрицы 1 и последовательный сдвиг этих кодов до последнего столбца. Запись и сдвиг осуществляются по импульсам, передаваемым от блока единого управления ассоциативных процессоров. К2. Распределение работ по приборам . К2.1. Формирование и подача импульсов для анализа строк матрицы 1. По импульсу начала работы от блока ассоциативных процессоров устанавливаются в триггер 18 и через элемент ИЛИ 29 - триггер 19. Триггер 18 своим единичным выходом разрешает прохождение импульсов с единичного выхода генератора 14 через элемент И 36 на элемент И 30, а триггер 19 своим единичным выходом пропускает их через элемент И 30 на все ячейки 2 первого столбца матрицы 1 . Каждый импульс опроса поступает ячейку 2 на элементы И 58 и 59. Если на триггере 42 записан О о импульсы без задержки проходят ерез элемент и 58 и элемент ИЛИ 48 а вход следующей по строке ячейки . Если на триггере 42 записана 1 , то импульс опроса устанавлиает по заднему фронту триггер 44, синхронный со следующим импульсом проса импульс пройдет через элемент 57, открытый единичным выходом риггера 44, а затем через элемент ЛИ 48 поступит на вход следующей чейки 2. Таким образом, если в основном триггере ячейки 2 записана , импульс на ее выходе будет запаздывать на один период по отношению к импульсу, поступившему на вход.. Импульс опроса на выходе последней ячейки 2 строки, который будет запаздывать по отношению к первому импульсу опроса на столько периодов следования импульсов, сколько единиц записано в триггерах 42 ячеек 2 данной строки, установит в триггер, соответствующий этой строке, в регистре 4. К2.2. Подача импульса с запаздыва .нием на полпериода относительно первого импульса опроса строк на регист 4 для сброса и блокировки в нем триг геров, установленных в i по первому импульсу опроса. Тем самым исключаются из дальнейшего рассмотрения строки, в которых у всех ячеек основной триггер стоит а потому соответствующие им триггеры в регистре 4 встали в 1 ПО первому импульсу опроса. Первый импульс с единичного выхода генератора 14, проше,цший через элемент И 36, устанавливает в Ч триггер 20, который разрешает проход через элемент И 37 импульса с нулевого выхода генератора 14, который сдвинут на полпериода относительно первого импульса с единичного выхода генератора 14, Этот импульс проходит через элемент И 38,. открытый нулеввп выходом триггера 21, затем через элемент И 33, открытый триггером 19 на вход регистра 4. Кроме этого,этот импульс своим задним фронтом устанав ливает в Ч триггер 21/. который пропускает через элемент И 39 все импульсы с нулевого выкода генератора 14, начинай со второго от момент начала работы, на элемент И 32,, .открытый тригхером 19, а с элемента И 32 они поступают на onpot узла 5. Поэтому на узел 5 поступают импульсы с периодом следования, равны периоду следования импульсовопроса строк, но с запаздыванием на полпер ода относительно второго импульса опроса строк. К2.3. Установка узлом 5 в i триггера регистра 6, соответствующе го крайней строке с наименьшим числом находящихся в основных триггеров. Потенциал от этого триггера регистра б поступает в матрицу 1 на соответствующую ячейку 2, Прохождение сигнала наличия строки через элемент НЕ 41 на элемент ИЛИ. 29 на установку в О триггера 19. а через элемент ИЛИ 26 на установку в триггера 22 и окончание по не му подачи импульсов опроса строк. К2.4. Подача импульсов для анали за столбцов матрицы 1, Формирование мпульсов для опроса столбцов аналогично формированию импульсов для опроса, в данном случае прохождение их в блок 8 разрешается триггером 22 на элe лeнтax И 31, 34 и 35, Каждый импульс опроса столбца поступает в ячейку 2 (фиг. 2), в которой проходит через элементы И 52 и 53, элемент ИЛИ 46 и поступает на элементы И 54 и 55. Через элементы 52, 53, 46 импульс проходит в том случае, если на ячейку поступает потенциал из регистра 6 и триггер 42, а следовательно, iOKe и триггер 44 (по п« К,2,1) находятся в Тем самым анализируются лишь те ячейки, которые расположены в столбцах, пересекающих выбранную по п,К2,2. строку по первых триг1еров 42, Если на триггере 42 записан О, то импульс без задержки проходит через элемент И 55, элемент ИЛИ 47 и поступает на вход следующей по столбцу утчейки 2. Если на триггере 42 записана , то игшульс опроса устанавлива™ ет по заднему фронту в триггер 43, а синхронный со следующим иМ пульсом опроса импульс, разрешаемый единичньп выходом триггера 43, прой дет через элемент И 56, затем элемент ИЛИ 47 и поступит на вход сле д 1огн.ей по столбцу ячейки 2. Таким образом, если в триггере 42 яче.йки 2 записана , импульс на выходе ячейки будет запаздывать на О..ЦИН период по отношению к импульсу, поступившему на вход. Импульс опроса на выходе последней ячейки опрашиваемого столбца,который будет запаздывать по отношению к первому импульсу опроса столбцов на столько периодов .следования, , ско.пько единиц записано в триггерах 42 ячеек 2 этик столбцов, установит в триггер, соответствующий этому столбцу, в регистре 9. К2.5. Подача импульса с запазды ван.ием на полпериода относительно первого импу.льса опроса столбцов на регистр 9 для сброса и блокировки в нем триггеров, установленных в Ч по первому импульсу опроса столбцов через элемент И 34. Тем самым исключаются из дальнейшего рассмотрения столбцы, в которых у всех ячеек 2 триггер 42 стоит в О , а потому соответствующие им триггеры в регистре 9 встали в . по первому импульсу опроса столбцов. Подача через элемент и 35 импульсов с периодом следования, равным периоду следования импульсов опроса столбцов, и с запаздыванием на полпериода относительно второго импульса опроса столбцов. Установка узлом 10 в i тригг ра регистра 11, соответствующего крайнему из опрашиваемых столбцов с наименьшим числом, находящихся в триггеров 42. Потенциал от этого триггера реги стра 11 поступает в Матрицу 1 на вх ды ячеек 2 соответствующего ему . .ст.;:бца, .. охождение сигнала наличия столб ца через элемент НЕ 40, элемент ИЛИ 24 на установку в О триггера 20 для окончания подачи имлульсов опроса столбцов, на счетчик 15 - для увеличения его значения на единицу, передача значения номера, выбранной строки для разрешения записи адреса в вспомогательный регистр адреса того процессора, который соответствует выбранной строке, из регистра б через шифратор 7 и дешифратор номера процессора передача значения номера выбранного столбца, соответствуютего адресу оперативной памяти процессора, из регистра 11, через цшфратор :12 в вспомогательный регистр адреса выбранного процессора, и наконец, подача и-мпульса через элемент ИЛИ 23 на вход ячеек 2 для обнуления триггеров ячеек выбранной строки и выбранного столбца, установка в i триггера 21 и переход к П.К2Л до окончания итерации, К2.7, Постоянный счет импульсов опроса строк и столбцов на счетчике 16 до значения мах (М,м), а по достижении заданного значения - подача из счетчика 16 управляющего сигнала, по которому производится сравнение числа назначений с полученным в итерации на счетчике 15, с числом назначений на регистре 13 от (К-1)-й итерации на схеме сравнения 17 и выработка сигналов результата сравнения: меньше или равно на соответствующих выходах устройства, К2.8. По сигналу равно производятся следующие операции: а)перепись содержимого счетчика 15 в регистр 13; б)обнуление всех триггеров матрицы 1 в)/переход к (К-И)-й итерации, К2.9, По сигналу, показывающему, что число на счетчике назначений меньше, чем число на регистре 13, решение задачи о назначениях заканчивается. Результатом решения являются числа, записанные в регистрах адреса каждого процессора-, в (К-1)-й итерации. Они указывают на порядковый номер работы, назначенной прибору, соответствующему данному процессору, Использование предлагаемого изобретения позволит повысить производительность в Р раз, где (M,N), при решении многих задач линейного программирования, которые сводятся к задаче оптимального распределения. Таблица 1

Ячейки строк бло ка моделирования матрицгл 1

м

1М В23

B2f Формула изобретения 1. Устройство для управления распределением задач, содержащее матрицу ячеек памяти, блики анализа строк и столбцов, каждый из которых содержит приемный регистр, выходы которого через узел опроса соединены с входами регистра назначений, выходы которого соединены с шифратором, выходы которого соединены с соответствующей группой выходов устройства, выходы регистра назначений блока анализа строк соединены с первыми входами ячеек памяти соответствующих строк, выходы регистра назначений блока анализа столбцов соединены со Вторыми входами ячеек памяти соответствующих столбцов, первые выходы ячеек памяти последней строки соединены с соответствующими входами приемного регистра блока авали за столбцов,. вторые выходы ячеек памяти последнего столбца соединены с соответствующимивходами приемного регистра блока анализа строк,, регистр, генератор, отличающееся тем,что,с целью повышени производительности,в него введены счетчик назначений,счетчик, схема сравнения, пять триггеров, семь эле ментов ИЛИ, десять элементов И, два элемента НЕ, причем управляющий выход узла опроса блока анализа столб цов через первый элемент НЕ соединен с первым выходом устройства,вхо дом счетчика назначений, первыми входами четырех элементов ИЛИ, выходы счетчика назначений соединены со входами регистра и схемы сравнения, другие входы которой соединены с выходом регистра, первый управляю щий вход которого соединен с первым выходом схемы сравнения и вторым выходом устройства, третий выход ко торого соединен со вторым выходе схемы сравнения и вторым входом первого элемента ИЛИ, выход которого соединен с Третьим входсм всех ячеек памяти, четвертые и пятые входы которых соединены с выходами первого и второго элементов И и вхо дами пятого элемента ИЛИ, выход коПродолжение табл.2 торого через счетчик соединен со входами счетчика, вторым управляющим входом регистра, вторыми входами второго и третьего элементов ИЛИ, первым входом шестого элемента ИЛИ и первым входом первого триггера, второй вход которого соединен с первым входом устройства и первым входом седьмого элемента ИЛИ, выход которого соединен с первым входом второго триггера, выход которого соединен с первьми входами первого, третьего и четвертого элементов И, выход четвертого элемента И соединен с управляющим входом приемного регистра блока анализа строк, выход третьего элемента И соединен с управляющим входом узла опроса блока анализа строк, управляющий выход которого через второй элемент НЕ соединен со вторыми входами щестого и седьмого элементов ИЛИ и третьим входом второго элемента ИЛИ, выход которого соединен с первыми входами третьего и четвертого триггеров,входы пятого триггера соединены с выходами четвертого и шестого элементов ИЛИ, выход пятого триггера соединен с первыми входами второго, пятого и шестого элементов И, выходы пятого и шестого элементов И соединены с управляющими входами прием ного регистра и узла опроса блока анализа столбцов, выходы генератора соединены с первыми входами седьмого и восьмого элементов И, вторые входаа которых соединены с выходами первого и третьего триггеров, выход седьмого элемента И соединен со вторыми входами третьего триггера,первого и второго элементов И, выходы четвертого триггера соединены с первыми входами девятого и десятого элементов И, выходы которых соединены со вторыми входами соответствен|но четвертого, пятого и третьего, шестого элементов И, выход восьмого элемента И соединен со вторыми входами четвертого триггера, девятого и десятого элементов и, первый выход каждой ячейки памяти соединен с шестым входсяй соседней по столбцу ячейки памяти, второй и третий выхогщ каждой ячейки памяти соединены с

седьмым и восьмым входами соседней по строке ячейки памяти, девятые входы всех ячеек памяти соединены со вторым входом устройства, вось(1ые входы ячеек памяти первого столбца соединены с группой входов устройства, четвертый и седьмой входы ячеек памяти первого столбца объединены, ПЯ75|- У шестой входы ячеек памяти перв-,...; строки объединены,

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

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

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

первого триггера соединен со вторымвыходом ячейки и вторы1- и входами шестого и одиннадцатого элементов И, выход последнего соединен со вторым входом третьего триггера, второй выход первого триггера соединен со вторы1.1и входами седьмого и десятого элементов И.

Источники информации, принятые во внимание при экспертизе

2, Авторское свидетельство СССР № 200880, кл. G06 9/19, 1966,