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

Союз Советских Социалистических Республик(51) М )( 2 с присоединением заявки Ио 806 Г 15/20 Госуяарстаенный комитет СССР по делан нзобретений и открьпий(54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ РАСПРЕДЕЛЕНИЕМЗАДАЧ Изобретение относится к областивычислительной техники и предназначено для решения задачи линейногопрограммирования об оптимальных наэ 5иачениях.Изобретение может быть использовано в универсальных и специализированных вычислительных комплексахИзвестно устройство, содержащееассоциативную память, регистры строки столбцов, узлы опроса, триггеры,элементы И (1).Недостаток известного устройстванизкое быстродействие и ограниченныеФункциональные возможности,15Наиболее близким по техническойсущности является устройство, содержащее матрицу ячеек памяти, блокианализа строк и столбцов, каждый изкоторых содержит приемный регистр,выходы которого через узел опросасоединены с входами регистра назначений, выходы которого соединены с шиФратором, выходы которого соединеныс соответствующей группой выходовустройства, выходы регистра назначений блока анализа строк соединены спервыми входами ячеек памяти соответствующих строк, выходы регистра назначений блока анализа столбцов соедииены со вторыми входамиччеек памяти соответствующих сто. в .бпан, первые выходы ячеек памят,. последней строки соединены с соответствующими входами приемного регистра блока анализа столбцов, вторые выходы ячеек памяти последнего столбца соединены с соотнетстн.лопиь 1 и входами приемного регистра блока анализа строк, регистр, генератор (2).Недостаток известного устройства недостаточная производительность при распределении задач.Цель предлагаемого изобретения повышение производительности.Для этого н устройство ннедены счетчик назначений, счетчик, схема сравнения, пять триггеров, семь элементов ИЛИ, десять элементов И, дна элемента НЕ, При этом управляющий выход узла опроса блока анализа столбцов через первый элемент НЕ соединен с первым выходом устройства, входом счетчика назначений, первыми входами четырех элементов ИЛИ. Выходы счетчика назначений соединены со нходами регистра и схемы сравнения, другие входы которой соединены с выходом регистра, первый управляющий вход которого соединен с первым выходом схетый и седьмой входы ячеек памяти первого столбца объединены, Пятый и шестой входы ячеек памяти первой строки объединены. Ероме того, ячейка памяти матрицы содержит три триггера, четыре элемента ИЛИ, одиннадцать элементов И, элемент НЕ. Причем первый вход первого триггера через первый элемент И соединен с восьмым и девятым входами ячейки, Второй вход первого триггера через первый элемент ИЛИ соединен с выходами второго и третьего элементов И, первые входы которых соединены со вторым входом ячейки, третий вход которой соединен со вторым входом третьего элемента И, Первый вход ячейки соединен со вторым входом второго элемента И,первым входом четвертого элемента И и через элемент НЕ с первым входом пятого элемента И, Пятый вход ячейки соединен со вторыми входами четвертого и пятого элементов И, выходы которых через второй элемент ИЛИ соединены с первыми входами шестого иседьмого элементов И, выходы которыхсоединены соответственно с первым входом второго триггера и первым входом третьего элемента ИЛИ, второй вход которого через восьмой элемент И соединен с шестым входом ячейки и выходом второго триггера, второй вход которого соединен с выходом первого элемента ИЛИ и первым входом третьего триггера, выход которого соединен с третьим входом четвертого элемента И и первым входом девятого элемента И, второй вход и выход которого соединены соответственно с седьмым входом ячейки и первым входом четвертого элемента ИЛИ, второй вход и выход которого соединены соответственно свыходом десятого элемента И и третьим выходом ячейки, четвертый входкоторой соединен с первыми входамидесятого и одиннадцатого элементов И. Первый выход первого триггера соединен со вторым выходом ячейки и вторыми входами шестого и одиннадцатого элементов И, Выход последнего соединен со вторым входом третьего триггера. Второй выход первого триггера соединен со вторыми входами седьмого и десятого элементов И,На Фиг. 1 дана блок-схема устройства; на фиг, 2 " ячейка памяти матрицы,Предлагаемое устройство содержит матрицу 1 ячеек 2 памяти, блок 3 анализа строк, содержащий приемный регистр 4, узел 5 опроса, регистр б на"значений, шифратор 7; блок 8 анализастолбцов, содержащий приемный регистр 9, узел 10 опроса, регистр 11назначений, шиФратор 12; регистр 13,генератор 14, счетчик 15 назначений,счетчик 16, схему 17 сравнения, триггеры 18, 19, 20, 21, 22, элементы мы сравнения и вторым выходом устройства, третий выход которого соединен со вторым выходом схемы сравнения и вторым входом первого элемента ИЛИ, выход которого соединен с третьим Входом всех ячеек памяти, четвертыепятые входы которых соединены с выходами первого и второго элементов И и входами пятого элемента ИЛИ, выходкоторого через счетчик соединен со входами счетчика, вторым управляющим входом регистра, вторыми входами второго и третьего элементов ИЛИ,первым входом шестого элемента ИЛИ и первым входом первого триггера, второй вход которого соединен с первым входом устройства и первым входом седьмого элемента ИЛИ, выход которого соединен с первым входом второго . триггера, выход которого соединен с первыми входами первого, третьего и четвертого элементов И, Выход четвертого элемента И соединен с управляющим входом приемного регистра блока анализа строк, Выход третьего элемента И соединен с управляющим входом узла опроса блока анализа строк, управляющий выход которого через второй элемент НЕ соединен со вторыми входами шестого и седьмого элементов ИЛИ и третьим входом второго элемента ИЛИ, выход которого соединен с 30 первыми входами третьего и четвертого триггеров, Входы пятого триггера соединены с выходами четвертого и шестого элементов ИЛИ, Выход пятого триггера соединен с первыми входами 35 второго, пятого и шестого элементов И, Выходы пятого и шестого элементов И соединены с управляющими входами приемного регистра и узла опроса блока анализа столбцов, Выходы генерато Ора соединены с первыми входами седьмого и восьмого элементов И, вторые входы которых соединены с выходамипервого и третьего триггеров, Выходседьмого элемента И соединен со вторыми входами третьего триггера, первого и второго элементов И, Выходычетвертого триггера соединены с первыми входами девятого и десятого элементов И, выходы которых соединенысо вторыми входами соответственночетвертого, пятого и третьего, шестого элементов И, Выход восьмого элемента И соединен со вторыми входамичетвертого триггера, девятого и десятого элементов И. Первый выход каждой 55ячейки памяти соединен с шестым входом соседней по столбцу ячейки памяти. Второй и третий выходы каждойячейки памяти соединены с седьмым ивосьмым входами соседней по строке 6 Оячейки памяти. Девятые входы всехячеек памяти соединены со вторымвходом устройства. Восьмые входы ячеек памяти первого столбца соединеныс группой входов устройства. Четвергде С - критерий ЭФфективности.В табл, 2 представлены мполнимости работ приборамиматрицы В в триггеры 422 матрицы 1.2. Определение плана однозначныхраспределений работ по прибЬрам покритерию максимального числа назначений,После выполнения каждой итера исравнивается число вновь полученназначений с полученными в предыдущей итерации и, если их не меньпереходят к следующей итерациименением величины критерия эффености.Решение задачи оканчиназначений получилось мепредшествующей итерации,рующим считается план, ппредыдущей итерации,Работа устройства на атрица выи запись ячеек памяти циных ше,с изктиввается, если ныне, чем в результиолученный в К-й итерации,К 1. Формирование матрицы выполнимости работ В.К 1,1, Считывание из оперативнойпамяти каждого 1-го процессора наарифметико-логическое устройство поадресу , хранящемуся иа регистре адреса, коэФФициента С , соответствующего назначению 1 -го прибора на) -ю работу по результату (к)-йитерации,ИЛИ 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,.-.длагаемое устройство работает со.вместно с ассоциативными процессорами следующим образом,Пусть в оперативной памяти каждого 1-го процессора по адресу 3( 3 =1, , М) хранится полноразрядное число С - коэффициент эффективности выполнейия 1-м прибором-й работы (табл, 1),Требуется получить оптимальное по критерию максимальной эфективнос ти и максимального числа назначений распределение работ по приборам.В табл. 1 представлена матрица эфФективностей выполнения М рабб 1 И приборами.Задача решается итерационно. Каждая итерация состоит из двух этапов:1. Формирование в ассоциативных процессорах двоичной матрицы В выполнимости работ приборами (табл. 2) по правилу: 1, если 1"я работа выполняется (-м прибором с эффек" В 11 тивностью С 1 ) С О, в про.тивном случае,К 1.2. Выполнение одновременно наарифметико-логических устройствахвсех процессоров блока ассоциативныхпараллельных процессоров, по командамот блока единого управления, опера"5 ции поиска максимального (минимального) числа в группе. Результатои операции является выявление индикаторомодного из процессоров,з котором хранится искомое число - С, и выводо С в блок единого управления на регистр признака опроса,Замечание. В первой итерации пункты 1.1 и 1.2 отсутствуют, а на регистре опроса блока единого управления процессорами устанавливается константа С 1.К 1,3, Последовательное считываниеиз оперативной памяти по адресамот первого до М-ного коэффициентаэффективности в арифметико-логическое устройство у всех процессоров ивыполнение групповых операций ассоциативного сравнения на большеф(или поменьше) чисел в арифметикологических устройствах с числом С ки индикация результатов сравнений вкаждом процессоре на индикатор,К 1.4. Последовательная перезаписьрезультатов сравнения с индикатороввсех процессоров на первые триггера30 42 ячеек 2 первого столбца матрицы1 и последовательный сдвиг этих кодов до последнего столбца. Запись исдвиг осуществляются по импульсам,передаваемым от блока единого управ 35 ления ассоциативных процессоров,К 2, Распределение работ по приборам.К 2.1, Формирование и подача импульсов для анализа строк матрицы 1,40 По импульсу начала работы от блока ассоциативных процессоров устанавливаются в 1 триггер 18 и через элемент ИЛИ 29 - триггер 19.Триггер 18 своим единичным выходсм45 разрешает прохождение импульсов сединичного выхода генератора 14 через элемент И 36 на элемент И 30, атриггер 19 своим единичньм выходомпропускает их через элемент И 30 навсе ячейки 2 первого столбца матрицы 1,Каждый импульс опроса поступаетв ячейку 2 на элементы И 58 и 59.Если на триггере 42 записан 0то импульсы без задержки проходят55 через элемент И 58 и элемент ИЛИ 48на вход следующей по строке ячейки2, Если на триггере 42 записана1, то импульс опроса устанавливает по заднему фронту триггер 44,60 а синхронный со следующим импульсомопроса импульс пройдет через элементИ 57 открытый единичным выходомтриггера 44, а затем через элементИЛИ 48 поступит на вход следующей65 ячейки 2.Таким образом, если в основном триггере ячейки 2 записана 1,. импульс на ее выходе будет запаздывать на один период по отношению к импульсу, поступившему на вход.Импульс опроса на выходе последней ячейки 2 строки, который будет запаздывать по отношению к первому импульсу опроса на столько периодов следования импульсов, сколько единиц записано в триггерах 42 ячеек 2 данной строки, установит в 1 триггер, соответствующий этой строке, в регистре 4.К 2,2. Подача импульса с запаз,цывэ" нием на полпериода относительно первого импульса опроса строк на регистр 4 для сброса и блокировки в нем триггеров, установленных в "1 по первому импульсу опроса.Тем самым исключаются из дальней" щего рассмотрения строки, в которых у всех ячеек основной триггер стоит в О, а потому соответствующие им триггеры в регистре 4 встали в 1" попервому импульсу опроса.Первый импульс с единичного выхо да генератора 14, прошедший через элемент И 36, устанавливает в 1 триггер 20, который разрешает проход через элемент И 37 импульса с нулевого выхода генератора 14, который 30 сдвинут на полпериода относительно первого импульса с единичного выхода генератора 14. Этот импульс проходит через элемент И 38,.открытый нулевым выходом триггера 21, затем через элемент И 33, открытый триггером 19, на вход регистра 4. Кроме этого,этот импульс своим задним фронтом устэнавливает в ф 1" триггер 21 который пропускает через элемент Й 39 все п 1 импульсы с нулевого выхода генерэ.то: ра 14, начинай со второго от моментаначала работы, на элемент И 32, от"- крытый триггером 19, а с элемента И 32 они поступают на опрос узла 5. 45Поэтому на узел 5 поступают ймпульсы с периодом следования, равным периоду следования импульсов опросастрок, но с запаздыванием на полпериода относительно второго импульса 5 Оопроса строк.К 2.3. установка узлом 5 в 1триггера регистра 6, соответствующе.го крайней строке с наименьшим числом находящихся в 1 ф основныхтриггеров, Потенциал от этого триггера регистра 6 поступает в матрицу1 на соответствующую ячейку 2. Прохождение сигнала наличия строки через элемент НЕ 41 на элемент ИЛИ 29на установку в фОф 1 триггера 19. а через элемент ИЛИ 26 на установку в ф 1 ф триггера 22 и окончание по нему подачи импульсов опроса строк,К 2.4. Подача импульсов для анализа столбцов матрицы 1, формирование 65 импульсов для спроса столбцов аналогично Формированию импульсов для опроса, в данном случае прохождениеих в блок 8 разрешается триггером 22на элементах И 31, 34 и 35Каждый импульс опроса столбца поступает в ячейку 2 (Фиг. 2), в которой проходит через элементы И 52 и53, элемент ИЛИ 46 и поступает наэлементы И 54 и 55.Через элементы 52, 53, 46 импульспроходит в том случае, если на даннуюячейку поступает потенциал из регистра 6 и триггер 42, а следовательно, уже и триггер 44 (по и. К,2:1)находятся в 1Тем самым анализируются лишь теячейки, которые расположены в столбцах, пересекающих выбранную попК 2,2, строку по 1 первых триг"геров 42,Если на триггере 42 записан Ото импульс без задержки проходит через элемент И 55, элемент ИЛИ 47 ипоступает на вход следующей по столб"цу ячейки 2.Если на триггере 42 записана1", то импульс опроса устанавлива"ет по заднему Фронту в 1 триггер43, э. синхронный со следующим импульсом опроса импульс, разрешаемыйединичным выходом триггера 43 пройдет через элемент И 56, затем элемент ИЛИ 47 и поступит на вход следллцей по столбцу ячейки 2,Таким образом, если в триггере 42ячейки 2 записана ф 1 , импульс навыходе ячейки будет запаздывать наодин периоц по отношению к импульсу,поступившему на вход,Импульс опроса на выходе последней ячейки опрашиваемого столбца,который будет запаздывать по отношениюк первому импульсу опроса столбцовна столько периодов следования,сколько единиц записано в триггерах42 ячеек 2 этих столбцов, установитв 1 триггер, соответствующийэтому столбцу, в регистре 9.К 2,5. Подача импульса с запазды"ванием на полпериода относительнопервого импульса опроса столбцов нарегистр 9 для сброса и блокировки внем триггеров, установленных в 1 фпо первому импульсу опроса столбцовчерез элемент И 34.Тем самым исключаются из дальнейшего рассмотрения столбцы, в которыху всех ячеек 2 триггер 42 стоит вО, а потому соответствующие имтриггеры в регистре 9 встали в 1по первому иьнульсу опроса столбцов,Подача через элемент И 35 импульсов с периодом следования, равнымпериоду следования импульсов опросастолбцов, и с запаздыванием на полпериода относительно второго импульсаопроса столбцов, Установка узлом 10 в 1 триггера регистра 11, соответствующегокрайнему из опрашиваемых столбцов снаименьшим числом, находяшихся в1 триггеров 42.Потенциал от этого триггера регистра 11 поступает в матрицу 1 на входы ячеек 2 соответствующего емуст, -.б;.,а,;." схождение сигнала наличия столбца ч,рез элемент НЕ 40, элемент ИЛИ24 на установку в 0 триггера 20для окончания подачи импульсов опроса столбцов, на счетчик 15 - дляувеличения его значения на единицу,передача значения номера выбраннойстроки для разрешения записи адресав вспомогательный регистр адреса того процессора, который соответствует выбранной строке, - из регистра б,через шифратор 7 и дешифратор номерапроцессора; передача значения номера 2 Овыбранного столбца, соответствуюШего адресу оперативной памяти процессора, из регистра 11, через шифратор12 в вспомогательный регистр адресавыбранного процессора, и наконец, 25подача импульса через элемент ИЛИ 23на вход ячеек 2 для обнуления триггеров ячеек выбранной строки и выбранного столбца, установка втриггера 21 и переход к п.К 2,1 до 30окончания итерации,К 2,7. Постоянный счет импульсовопроса строк и столбцов на счетчике16 до значения мах (М,И), а по достижении заданного значения - подача иэ счетчика 1 б управляющего сигнала, по которому производится сравнение числа назначений с полученнымв К-й итерации на счетчике 15, счислом назначений на регистре 13 от(К)-й итерации на схеме сравнения17 и выработка сигналов результатасравнения: меньше или равнона соответствуюших выходах устройства,К 2,8, По сигналу равноф производятся следуюшие операции:а) перепись содержимого счетчика15 в регистр 13;б) обнуление всех триггеров матрицы 1;в) переход к (К+1)-й итерации.К 2.9, По сигналу, покаэываюшему,что число на счетчике назначенийменьше, чем число на регистре13 решение задачи о назначениях заканчивается,Результатом решения являются числа, записанные в регистрах адресакаждого процессора, в (К)-й итерации. Они указывают на порядковыйномер работы, назначенной прибору,соответствуюшему данному процессору.Использование предлагаемого изобретения позволит повысить производительность в Р раз, где Р=мах2(М,И), при решении многих задач линейного программирования, которыесводятся к задаче оптимального распределения,Таблица 169 б 471 12 Продолжение табл.2 Формула изобретения 1, Устройство для управления распределением задач, содержащее матрицу ячеек памяти, блОки анализа строк и столбцов, каждый из которых содержит приемный регистр, выходы которого через узел опроса соединены с входами регистра назначений, выходы которого соединены с шифратором, выходы которого соединены с соответствующей группой выходов. устройства, выходы регистра назначений блока анализа строк соединены с первыми входами ячеек памяти соответствующих строк, выходы регистра назначений блока анализа столбцов соединены со вторыми входами ячеек памяти соответствующих столбцов, первые выходы ячеек памяти последней строки соединены с соответствующими входами приемного регистра блока анали" за столбцоввторые выходы ячеек памяти последнего столбца соединены с соответствующимивходами приемного регистра блока анализа строк,. регистр, генератор, о т л и ч а ю щ е е с я тем,что,с целью повышения производительности,в него введены счетчик назначений, счетчик, схема сравнения, пять триггеров, семь эле" ментов ИЛЙ, десять элементов И, два элемента НЕ, причем управляющий выход узла опроса блока анализа столбцов через первый элемент НЕ соединен с первым выходом устройства,вхо" дом счетчика назначений, первыми входами четырех элементов ИЛИ, выходы счетчика назначений соединены со входами регистра и схемы сравнения, другие входы которой соединены с выходом регистра, первый управляющий вход которого соединен с первым выходом схемы сравнения и вторым выходом устройства, третий выход которого соединен со вторым выходом схемы сравнения и вторым входом первого элемента ИЛИ, выход которого соединен с третьим входом всех ячеек памяти, четвертые и пятые входы которых соединены с выходами первого и второго элементов И и вхо-. .дами пятого элемента ИЛИ, выход которого через счетчик соединен со 15 входами счетчика, вторым управляющимвходом регистра, вторыми входамивторого и третьего элементов ИЛИ,первым входом шестого элемента ИЛИи первым входом первого триггера, 2 О второй вход которого соединен с первым входом устройства и первым нходом седьмого элемента ИЛИ, выход которого соединен с первым входом второго триггера, выход которого соединен с первыми входами первого,третьего и четвертого элементов И,выход четвертого элемента И соединенс управляющим входом приемного реги"стра блока анализа строк, выходтретьего элемента И соединен с управляющим входом узла опроса блокаанализа строк, управляющий выход которого через второй элемент НЕ соединен со вторыми входами шестого иседьмого элементов ИЛИ и третьимвходом второго элемента ИЛИ, выходкоторого соединен с первыми входамитретьего и четвертого триггеров,входы пятого триггера соединены с выходами четвертого и шестого элемен О тов ИЛИ, выход пятого триггера соединен с первыми входами второго,пятого и шестого элементов И, выходы пятого и шестого элементов И соединены с управляющими входами прием ного регистра и узла опроса блокаанализа столбцов, выходы генераторасоединены с первыми входами седьмого и восьмого элементов И, вторыевходы которых соединены с выходами 5 О первого и третьего триггеров, выходседьмого элемента И соединен со вторыми входами третьего триггера,первого и второго элементов И, выходычетвертого триггера соединены с пер ными входами девятого и десятогоэлементов И, выходы которых соединены со вторыми входами соответственно четвертого, пятого и третьего,шестого элементов И, выход восьмого 60 элемента И соединен со втор входами четвертого триггера, девятогои десятого элементов И, первый выходкаждой ячейки памяти соединен с шестым входом соседней по столбцу ячейки памяти, второй и третий выходыкаждой ячейки памяти соединены сседьмым и восьмью входами соседнейпо строке ячейки памяти, девятыевходы всех ячеек памяти соединены совторым входом устройства, восьмыевходы ячеек памяти первого столбцасоединены с группой входов устройст"ва, четвертый и седьмой входы ячеекпамяти первого столбца объединены,пят. н шестой входы ячеек памятиперь строки объединены,2. устройство для управления распределением задач по пункту 1, о тл и ч а ю щ е е с я тем, что ячейка памяти матрицы содержит три триггера четыре элемента ИЛИ, одиннадцать элементов И, элемент ИЕ, причем первый вход первого триггера через первый элемент И соединен с восьмым и девятым входами ячейки, второй вход первого триггера чсрез первый элемент ИЛИ соединен с выходами второго и третьего элементов И, первые входы которых соединены со вторым входом ячейки, третий вход которой соединен со вторым входом третьего элемента И, первый вход ячейки соединен со вторьщ входом второго элемента И, первым входом четвертого элемента И и через элемент НЕ с первым входом пятого элемента И, пятый вход ячейки соединен со вторми входами четвертого и пятого элементов И, выходы которых через второй элемент ИЛИ соединены с первьпми входами шестого и седьмого элементов И, выходы которых соединены соответственно спервым входом второго триггера и первым входом третьего элемента ИЛИ,второй вход которого чсрез восьмойэлемент И соединен с шестым входомячейки и выходом второго триггера,второй вход которого соединен с выходом первого элемента ИЛИ и первымвходом третьего триггера, выход которого соединен с третьим входом четвертого элемента И и первым входомдевятого элемента И, второй вход ивыход которого соединены соответственно с седьмьм входом ячейки и первым входом четвертого элемента ИЛИ,второй вход и выход которого соединены соответственно с выходом десятогоэлемента И и третьим выходом ячейки,четвертый вход которой соединен спервыми входами десятого и одиннад 20цатого элементов И, первый выходпервого триггера соединен со вторым.выходом ячейки и вторыми входами шестого и одиннадцатого элементов И, выход последнего соединен со вторымвходом третьего триггера, второй выход первого триггера соединен совторыми входами седьмого и десятого элементов И.Источники информации,принятые во внимание при экспертизе1. Однородные ассоциативные процессоры. М Советское радио,1973 5 1 3 542, Авторское свидетельство СССРР 200880, кл, СО 6 Г 9/19, 1966, 696471Составитель Н. ПолоПавлов Тех е Н.Бабурка скаяКорректПодписиа СССРтийнаб Редакто каз 6769/50 Тираж 780ЦНИИПИ Государственного комитепо делам изобретений и откры113035 Л 1 осква ЖРа ская Филиал ПППфПатент , г. Ужгород, ул, Проектна