Устройство для решения целочисленных задач математического программирования

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 15/20

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

К А STOPCHOMV СВИДЕТЕЛЬСТВУ

1о

ГОСУДАРСТВЕННЫЙ КОМИТЕТ пО иЗОБРетенийм и ОчнРытийм

ПРИ ГКНТ СССР (?i) 4621097/24 (22) 16.12.88 (46) 28..02.91.Бюл. У 8 (72) АЯ.Веревкин и И.Н.Иаркова (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 1180925, кл. G 06 F 15/20, 1984.

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

И 1534468, кл. G 06 F 15/36, 1988.

„„SU„„1631552 А 1

2 (54)> УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЦЕПОЧИСЛЕННЫХ ЗКЦАЧ ИАТЕИАТНЧЕСКОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится к вычислительной технике и может быть исполь-зовано для решения целочисленных за-дач математического программирования, Целью изобретения является повьппеяие быстродействия за счет исключения из

1631552

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

Пель изобретения — повышение быстродействия за счет исключения из рассмотрения заведомо непригЬдных комбинаций с сохранением полноты пере- бора.

На фиг.1 изображена структурная схема устройства; на фиг.2 — структурная схема блока анализа; на

25 фиг.3 — структурная схема узла суммирования; на фиг.4 — траектория движения при решении трехмерной задачи.

Устройство содержит регистр 1, схему 2 сравнения, узел 3 суммирования, элемент И 4, группу регистров 5, 30 коммутаторы 6, блоки 7 анализа, триггеры Я, селекторы 9, счетчики 10, тактовй вход 11, информационные вы-ходы 12 и выход 13 окончания решения задачи. 35

Узлы 5 — 10 со своими связями образуют блоки 14 и 15 формирования комбинаций. Блок 7 анализа содержит элементы И 16-18, триггер 19s элементы ИЛИ 20 и 21, элемент 22 неравнозначности, информационный вход 23, тактовый вход 24, управляющие входы 25-27 и выходы ?8 и 29.

Узел 3 сУммиРования содержит ком- 45 бинационный сумматор 30, регистр 31, информационньпЪ вход 32, выход 33 первого знакового разряда, выход 34 старших разрядов, выход 35 младших разрядов, выход 36 второго знакового разряда и управляющий вход 37.

Устройство предназначено для решения задач, математическая постановка которых имеет следующий вид: найти a,,ь. 1,...,Т, удовлетворяющие условию: 0 с- о Ъ «с6, gV, Т

= V - a, v,, 0 (а N;, a; — целое.

1=! мирования 3, элемент И 4, группы из

Т регистров 5 (где Т вЂ” размерность задачи), Т коммутаторов 6, Т блоков анализа 7, Т-1 триггеров 8,,Т селекторов 9 и T счетчиков 10 введены новые связи между блоками. 4 ил.

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

В исходном состоянии все счетчики 10 обнулены, в регистры 5 записаны значения v, в регистр 1 — Д, в узел 3 суммирования — V, триггеры

19 находятся в нулевом состоянии (запрета изменения содержимого счетчика 10 нет), триггеры 8 — в нулевом состоянии (режим суммирования).

Устройство работает в три этапа. Первьп этап происходит по переднему фронту тактового импульса. При этом изменяется (на единицу) одно из а и соответствующее v в соот-! ветствующем коде подается на вход узла 3 суммирования. При возникновении переносов изменяются режимы работы блоков 15 (+ или -), т.е. триггеры 8 перебрасываются. На втором этапе происходит формирование очередного значения gV,на комбинационном сумматоре 30, а необходимые признаки подаются на входы блоков

7 анализа. На третьем этапе по заднему фронту тактового импульса происходит запись нового значения и U в регистр 31 и оценка в узлах 2 и 4 полученного значения. Кроме того, в необходимое состояние устанавливаются триггеры 19. которые определяют, какой из а будет изменяться на следующем шаге.

Рассмотрим работу устройства на примере решения трехмерной задачи (Т=З) со с едующими начальными условиями: v<- =ч„= v> = 1, N1 = N< =

= N g = 4, V = 4,5, Ь = 0,25. Данная задача является вырожденной и ее

Решения не существует. На ней удобно продемонстрировать все основные режимы работы устройства.

В начальный момент а = а = а =

= 0 траектория движения находится в начале координат (фиг.4). Триггер 19

1631552 первого блока 7 анализа обнулен, поэтому первый тактовый импульс ьп

Ю (передний фронт) поступает через первый коммутатор 6 на вход первого счетчика 10,Вузле Зсуммирования записано положительное число 7 =,на выходах 33 и 36 знаковых разрядов— ноль. Поэтому сигнал с выхода 33 устанавливает суммируюций режим работы счетчика 10 и обеспечивает передачу

v. на вход узла 3 суммирования в обратном коде. Таким образом, по ьп содержимое первого счетчика 10 увеличивается на единицу, первьпi селектор

9 подключается к входу 32 узла суммирования и на комбинационном сумматоре

30 начинается формирование величины

3V1 = V — v1. В результате осуществил ся переход в точку 1 фиг.4. Поскольку смены знака 3 V не произошло, то на выходе элемента 22 неравнозначности в первом блоке 7 анализа — ноль, элемент И 16 закрыт. По заднему фронту тактового импульса ь gV1 записывается в регистр 31 и появляется на выходах 33 - 35. Если в некоторый момент оказалось, что получено значение $V (на выходе 33 — нуль), в .старших разрядах gV — нули (на выходах 34 — нули), а величина, записан ная в младших разрядах (выход 35), меньше, то на выходе схемы 2 сравнения и элемента И 4 появляются единицы. Последняя свидетельствует о том что решение найдено — выход 13. Поскольку после первого тактового импульса условия не изменились, то второй тактовый импульс выполняет те же действия с той лишь разницей, что в первом счетчике 10 оказывается двойка а в узле 3 суммирования — величина

3V< = U — ч „- v < (точка 2,фиг.4).

Аналогичное увеличение а продолжается до тех пор, пока по очередному ь в первом счетчике 10 не окакется а = М» . При этом, поскольку f V ) О, на выходе элемента И 18 первого блока анализа 7 появляется единица, свидетельствующая о том, что первый счетчик 10 не может выполнить операцию увеличения своего содержимого.

Этот сигнал, пройдя элементы ИЛИ 21 и 20, поступает на установочный вход триггера 19 первого блока анализа 7 и .по g> поступающему с входа 24,и .

/1 устанавливает триггер 19 в единичное состояние. При этом в узле 3 суммирования накоплено значение E V =

= V — N, v, (точка 4, фиг. 4), Следующий тактовый импульс, не и меняя а, проходит через первый коммутатор

6. поступает на второй блок 15 и по д выполняет те же действия, но с величинами а и v . На втором этапе во втором счетчике (а ) оказывается единица, в регистре 31 — g V p 0 а на выходе комбинационного сумматора 30 — о V с О (точка 5 фиг.4).

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

15 на то, что произошла смена знака gV и на выходе элемента 22 неравнозначности первого блока 7 анализа имеется единица, но из-за отсутствия тактового сигнала на входе 27 первого блока 7 анализа, на выходе И 16 прил сутствует ноль. В результате по триггер 19 первого блока анализа вновь устанавливается в нулевое сос-. тояние, а в регистр 31 записывается дч — ц дч = о V+- v (О. Сигнал с выхода

33 устанавливает вычитающий режим работы первого счетчика 10 и режим передачи через первый селектор 9 в прямом коде. Следующий тактовый импульс вычитает единицу из а и формирует

Ь = V — N v — v + v )О (точка 6). (Происходит смена знака V, на выходе элемента 22 неравнозначности первого блока 7 анализа появляется еди- . ница, а поскольку это изменение было связано с величиной а1 — на входе 27 первого блока 7 анализа присутствует тактовый сигнал, то на выходе элемента И 16 появляется единица, кото40 рая, пройдя элемент ИЛИ 20, по сз л устанавливает триггер 19 в единичное состояние. По следующему тактовому импульсу изменяется а и происходит

-переход в точку 7 и т.д. Наконец на

45 12-м шаге (фиг.4) оказывается, что а — — N< а„= О, à kVr0. На выходе элементов Й 16 и 17 первого блока 7 анализа имеются единицы, следовательно, триггер 19 по 2 ока50 зывается в единичном состоянии и в следующем такте а не изменяется. Во втором блоке анализа на выходе элемента И 1,8 имеется единица, поскольку режим работы вто55 рого счетчика 10 — суммирующий (состояние первого.триггера 8)>, а а = N<, Поэтому по триггер 19 оказывается

A в едйничном состоянии и обеспечивает прохождение следуюцего тактового им1631552 пульса к следующему блоку 15 (а ) °

Тринадцатый тактовый импульс, пройдя первый и второй коммутаторы, по перебрасывает первый триггер 8

Д и переводит блок 15 в вычитающий режим работы счетчика 10 и в режим передачи прямым кодом V» через второй селектор 9.Поступив на второй блок 15, 10 тактовый импульс увеличивает на еди.ницу а> и формирует сумму О Ч (О (фиг.4). Так как 3Ч с О, а = О, то по с единица с выхода элемента И 17 устанавливает триггер 19 первого блока анализа в единицу, запретив изменение а на 14-м шаге. Вычитающий режим первого блока 15 (состояние триггера 8) и в Ч С О приводят к тому, что.на выходе элемента 22 20 неравнозначности и элемента И 16, а также на выходе элемента И 18 второго блока 7 анализа присутствуют нули, поэтому триггер 19 оказывается в нулевом состоянии и на 14-м шаге 25 происходит уменьшение а (точка 14), По С этого импульса разрешается изменение а 1 и происходит процесс, аналогичныи описанному.

Наконец, последний вариант ре- 30 жима работы устройства возникает на

29-м шаге, при котором а = О, а (И, фс О и происходит смена знака gV.

При этом по a из-за единицы на выходе элемента И 18 первого блока 7 анализа триггер 19 запрещает изменение а . Единица с выхода 29 первого блока 7 анализа поступает на вход 27 второго блока 7 анализа. Реж м работы блока 15 - суммирующий (на выходе,40 триггера 8 ноль), а если 1 Ч О то на выходе элемента 22 неравнозначности и элемента И 16 второго блока анализа 7 появялется единица, которая устанавливает триггер 19 в ноль и 45 запрещает изменение а . Таким образом, увеличение а до достижения Ng (а это в данном случае нецелесообразно) не происходит. с

Остальная процедура поиска решения происходит аналогично.

Признаками окончания работы устройства являются либо появление признака нахождения решения с выхода 13, либо возникновение переноса из старшего блока 15, свидетельствующего об отсутствии решения при заданных условиях.

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

Устройство для решения целочисленных задач математического программирования, содержащее регистр, схему сравнения, узел суммирования, элемент

И, группу из Т регистров (где Т— размерность задачи), Т коммутаторов, Т блоков анализа, Т-1 триггеров, Т селекторов и Т счетчиков, причем счетный вход К-го (К =1,...,Т) счетчика соединен с первым входом К-го коммутатора, информационный выход К-го счетчика подключен к информационному входу К-го блока анализа и является

К-м информационным выходом. устройства, выход К-го регистра группы соединен с информационным входом К-го селектора, выход которого подключен к информационному входу узла суммирования, тактовый вход первого блока анализа соединен с управляющим входом узла суммирования и является тактовым входом устройства, выход млад— них разрядов узла суммирования подключен к первому входу схемы сравнения, управляющий вход М-го (M=2....,Т) селектора соединен с выходом (M-1)-го триггера, выход регистра подключен к второму входу схемы сравнения, выход которой соединен с первым входом элемента И, выход старших разрядов и выход первого знакового разряда узла суммирования подключены соответственно к второму и третьему входам элемента И, выход которого является выходом окончания решения задачи устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия за счет исключения из рассмотрения заведомо непригодных комбинаций при сохранении полноты перебора, выход второго знакового разряда узла суммирования соединен с первым управляющим входом K-го блока анализа, первый выход которого подключен к управляющему входу К-ro коммутатора, первый выход К-го коммутатора соединен с входом подключения К-го селектора, второй выход Н-ro (Н=1,..., Т-1) коммутатора соединен с информационным входом (Н+1)-ro коммутатора и тактовым входом (Н+1)-ro блока анализа, выход первого знакового разряда узла суммирования подключен к управляющему входу пррвого селектора, управляющему входу первого счетчика и второму управляющему входу первого

1631552

)о блока анализа, третий управляющий вход которого соединен с первым выходом первого коммутатора, информационный вход первого коммутатора подключен к тактовому входу первого блока анализа, второй выход Н-ro блока анализа соединен с третьим управ27 ляющим i входом (Н+1)-ro блока анализа, второй выход М-ro коммутатора подключен к счетному входу (И-1)-го

5 триггера, выход которого соединен с управляющим входом M-го счетчика и, вторым управляющим входом М-го блока анализа.

1631552

Составитель В.Есипов

Редактор Л.Пчолинская Техред Л.Сердюкова

Корректор М.Иаксимишинец

Заказ 547 Тираж ч02 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж"35, Раушская наб., д, 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101