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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относитсяк области вычислительной техники, может быть использовано fi качестве специализированного вычислителя для решения задачи назначения в системах распределенной обработки АСУ и позволяет решить задачу назначения методом максимального столбца (строки). Для этого на группу информационных входов устройства последовательно подают столбцы (строки) матрицы. Блок сравнения чисел, входящий в состав устройства , выбирает максимальное из чисел столбца и отключает соответствующий его положению информационный вход устройства, при этом позиционный код максимального числа запоминается в блоке памяти. В каждой последующей операции выбора максимального числа будут участвовать только те элементы столбца (строки), которые не были отключены по результатам предыдущих операций выбора. 2 ил. W

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

4241 А1 (19) (11) (51)4 G 06 F 15/20

ВСЕ(.())(. ) Н Ц,", КБЛИ; ;;

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Й ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ.(21 ) 4107088/24-24 (22) 11.08.86 (46) 15.02.88. Бюл. К 6 (72) А.Ф. Андреев и В.Е.. Козлов (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 1206792, кл. G 06 F 15/20, 1985.

Авторское свидетельство СССР

У 752326, кл. С 06 F 7/02, 1979. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ

НАЗНАЧЕНИЯ (57) Изобретение относится к области вычислительной техники, может быть использовано и качестве специализированного вычислителя для решения задачи назначения в системах распределенной обработки АСУ и позволяет е решить задачу назначения методом максимального столбца (строки). Для это,го на группу информационных входов устройства последовательно подают столбцы (строки) матрицы. Блок сравнения чисел, входящий в состав устройства, выбирает максимальное из чисел столбца и отключает соответст- вующий его положению информационный вход устройства, при этом позиционный код максимального числа запоминается в блоке памяти. В калщой последующей операции выбора максимального числа будут участвовать только те элементы столбца (строки), кото-. рые не были отключены по результатам предыдущих операций выбора.- 2 ил.

1 137424

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

Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи назначения методом максимального элемента столбца (строки) матрицы стоимости.

На фиг. 1 изображена функциональная схема примера реализации устрой- 15 ства; на фиг. 2 — пример решения задачи назначения для матрицы размерности Р=4.

Устройство содержит P регистров, выполненных на триггерах 1„, (M=1, 20 ...,Т; К1, ..., Р, где Т вЂ количество разрядов в двоичном представлении кода числа), ТхР узлов 2 „, анализа, каждый из которых содержит элементы

И 3-5, группу из Т элементов ИЛИ 6, 25 группу из Р элементов ИЛИ 7,,P триггеров 8, группу из Т элементов И-HE 9, группу .из Т элементов ИЛИ 10, группу из Т элементов И 11, вход 12 управления, информационные входы 13, входы ЗО

14 управления P триггеров 15, P триггеров 16 P-1 элемент И 17, блок 18 памяти, счетчик 19, элемент 20 задержки, входы 21 установки в "0", .входы

22 установки в "1", входы 23 строба,. входы 24 чтения, входы 25 сброса, выход 26 конца выбора, выход 27 конца решения, выход 28 информации.

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

В исходном состоянии в блоке 18 памяти записаны нули. Счетчик 19 устанавливается в нулевое состояние сигналом, подаваемым на вход 25.

Триггеры 15 и 16 устанавливаются со- 45 ответственно в нулевое и единичное состояние сигналами, подаваемыми на входы 21 и 22. При подаче на вход

23 строба выходными сигналами с прямых выходов триггеров 16 устанавливаются в единичное состояние триггеры 8. Одновременно с выполнением этих операций в регистры 1 устройства принимаются коды элементов первого столбца матрицы стоимости. Устройство готово к работе.

При подаче на вход 12 сигнала единичного уровня производится пораз, рядный анализ сравниваемых чисел.

1 2

Если в первом разряде чисел имеются и нули и единицы, то через элементы

И 3 и 4 узлов 2„„ на группу элементов ИЛИ 10, и 6, поступают сигналы единичного уровня. На выходе элемента И-НЕ 9, будет сформирован сигнал нулевого уровня, закрывающий элемент

И 11, ° Через элементы И 5 узлов 2,„ анализа и элемент ИЛИ 7, относящиеся к тем регистрам, в первом разрядекоторых записан "0", сигнал единичного уровня поступает на входы установки в нулевое состояние соответствующих триггеров 8„. Соответствующие числа исключаются из дальнейшего сравнения. Элементы И 3 и 4 соответствующих узлов 2 анапиза закрываются, и сигнал единичного уровня будет только на выходе элемента ИЛИ 10,. На выходе элемента И-НЕ 9 формируется сигнал единичного уровня, по которому открывается элемент И 11,. Далее аналогично производится анализ следующего разряда оставшихся сравниваемых чисел.

Если в разряде сравниваемых чисел содержатся только нули или только единицы, то на выходе элемента И-НЕ 9 установится сигнал единичного уровня, открывающий элемент И 11. Производится анализ следующего разряда.

После того, как все разряды сравниваемых чисел будут проанализированы, на выходе элемента И 11 формируется сигнал единичного уровня. При этом на выходах 13,, ..., 13., содержится код экстремального числа, а на выхо,дах 14,. .. 14 — позиционный код номеров регистров, содержащих экс.тремальное число .

Для рассматриваемого примера (фиг. 3) при P=4 по окончании первого цикла в единичном состоянии останутся триггеры 8, и 8 . Сигнал нулевого уровня с инверсного выхода триггера 8, поступая на первый вход элемента И 17,, закрывает цепь дальнейшего прохождения сигнала, посту- пающего с выхода элемента И 11 на второй вход элемента И 17,. Этот же сигнал поступает на вход синхронизации триггера 15„ и вызывает появление на.его прямом выходе сигнала единичного уровня. Сигнал с прямого выхода триггера 15> поступает на вход установки в нулевое состояние триггера 16„. Состояние остальных триггеров

3 137424

16 не изменится. На шинах входной информации блока 18 будет информация

1,0,0,0. Счетчик 19 устанавливается в "1" сигналом с выхода элемента

И 11 . Под действием задержанного

5 элементом 20 сигнала, подаваемого на вход записи, производится запись информации в блок 18 памяти. Подачей сигнала на вход 23 обеспечивается передача содержимого триггеров 16 (0, 1, 1, 1j в триггеры 8 (из сравнения исключено первое число). По сигналу с выхода элемента И 11, поступающему на выход 26 конца выбора, в ре,гистры устройства принимаются коды элементов второго столбца матрицы стоимости. На этом первый цикл работы устройства заканчивается. Второйцикл начинается с установки в нуле- 2р вое состояние триггеров 15 сигналом, подаваемым на вход 21. Подачей сигнала на вход 12 начинается сравнение оставшихся элементов второго столбца. В результате сравнения в 25 единичном состоянии остается триггер 8. На первых выходах элементов И

171 172 и 173 будут сигналы единичного уровня с инверсных выходов триггеров 8,, 8 и 8 . Сигнал еди- 30 ничного уровня с выхода элемента

И 11 добавляет единицу в счетчик 19 и поступает на второй вход элемента

И 17 и вход синхронизации триггера

15, (состояние триггера при этом не меняется). На выходе элемента И 17, появляется сигнал единичного уровня, поступающий на вход синхронизации триггера 15 (состояние триггера также не изменяется) и второй вход 4р элемента И 17 . На выходе этого элемента имеется сигнал единичного уровня, поступающий на вход синхронизации триггера 15З (состояние триггера не изменяется) и второй вход эле- 45 мента И 17з. IIo сигналу с выхода элемента И 171 устанавливается триггер

15 в единичное состояние. На шинах входной информации набор (0,0,0,1, который запишется в блок 18 памяти, стробирующий сигнал на входе 23 обеспечивает передачу в триггеры 8 содержимого триггеров 16 (0,1,1,0 ). Из сравнения исключения первое и четвертое число.

Аналогично устройство работает в следующих циклах. После выполнения последнего цикла на выходе 27 появляется сигнал конца работы устройства.

В ЗУ содержится матрицы назначения.

Чтение из ЗУ можно выполнить по окончании или в процессе работы устройства (во время сравнения).

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

Устройство для решения задачи назначения, содержащее группу из P регистров, где P — порядок анализируемой матрицы, и блок сравнения чисел, вход пуска которого является тактовым входом устройства, а информационный выход — информационным выходом устройства, причем К-й информационный вход устройства (К=1,...,P) подключен к входу К-го регистра группы, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи назначения методом максимального элемента столбца (строки) матрицы, в него введены группа иэ P ключей, блок памяти, блок синхрониэации и счетчик, причем выход К-го регистра группы подключен к информационному входу К-ro ключа группы, выход которого подключен к К-му информационному входу блока сравнения чисел, К-й выход признака "Наибольшее число" подключен к К-му разряду информационного входа блока памяти и к управляющему входу К-ro ключа группы, выход признака окончания операции сравнения блока сравнения чисел подключен к тактовому входу блока синхронизации,первый выход синхронизации которого подключен к суммирующему входу счетчика, информационный выход которого подключен к адресному входу блока памяти, второй выход синхронизации блока синхронизации подключен к входу признака записи блока памяти, вход признака чтения которого является входом опроса устройства, а выход — вторым информационным выходом устройства.

1374241

Составитель А. Мишин

Редактор Е. Копча Техред Л.Сердюкова Корректор И. Шароши

Заказ 604/46 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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