Устройство для решения целочисленных задач математического программирования Советский патент 1991 года по МПК G06F15/20 

рассмотрения заведомо непригодных комбинаций при сохранении полноты перебора. Поставленная цель достигается тем, что в устройство для решения целочисленных задач математического программирования, содержащее регистр 1, схему сравнения 2, узел суммирования 3, элемент И 4, группы из Т регистров 5 (где Т - размерность задачи), Т коммутаторов 6, Т блоков анализа 7, Т-1 триггеров 8, Т селекторов 9 и Т счетчиков 10, введены новые связи между блоками. 4 ил.

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

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

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

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

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

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

Устройство предназначено для решения задач, математическая постановка которых имеет следующий вид: найти а| ,i -1,...,, удовлетворяющие условию: ,oV,

V ,v;, , a; i

- целое.

5

0

5

0

5

0

5

0

5

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

Б исходном состоянии все счетчики 10 обнулены, в регистры 5 записаны значения v;, в регистр 1 - Д , в узел 3 суммирования - V, триггеры 19 находятся в нулевом состоянии (запрета изменения содержимого счетчика 10 нет), триггеры 8 - в нулевом состоянии (режим суммирования).

Устройство работает в три этапа. Первый этап происходит по переднему фронту тактового импульса. При этом изменяется (на единицу) одно из а и соответствующее vj в соответствующем коде подается на вход узла 3 суммирования. При возникновении переносов изменяются режимы работы блоков 15 (+ или -), т.е. триггеры 8 перебрасываются. На втором этапе происходит формирование очередного значения о.на комбинационном сумматоре 30, а необходимые признаки подаются на входы блоков 7 анализа. На третьем этапе по заднему фронту тактового импульса ПРОИСХОДИТ запись нового значения о V в регистр 31 и оценка в узлах 2 и 4 полученного значения. Кроме того, в необходимое состояние устанавливаются триггеры 19. которые определяют, какой из аЈ будет изменяться на следующем шаге.

Рассмотрим работу устройства на примере решения трехмерной задачи () со следующими начальными условиями: V VЈ V -э 1 , N { NЈ

N3 4, V 4,5, Д 0,25. Данная задача является вырожденной и ее решения не существует. На ней удобно продемонстрировать все основные режимы работы устройства.

В начальный момент a 0 траектория движения находится в начале координат (фиг.4). Триггер 19

первого блока 7 анализа обнулен, поэтому первый тактовый импульс с/п (передний фронт) поступает через первый коммутатор 6 на вход первого счетчика 10. В узле 3 суммирования записано положительное число V QV0 ,на выходах 33 и 36 знаковых разрядов - ноль. Поэтому сигнал с выхода 33 устанавливает суммирующий режим работы счетчика 10 и обеспечивает передачу v | на вход узла 3 суммирования в обратном коде. Таким образом, по 5П содержимое первого счетчика 10 увеличивается на единицу, первый селектор 9 подключается к входу 32 узла суммирования и на комбинационном сумматоре 30 начинается формирование величины &Vf V - vj. Б результате осуществил V - (точка 4, фиг.4). Следующий тактовый импульс, не изменяя

11

проходит через первый коммутатор 6. поступает на второй блок 15 и по $п выполняет те же действия, но с

величинами а

и V

На

во втором счетчике (аг.)

втором этапе оказывается

единица.

в регистре 31 - (.

10 а на выходе комбинационного суммато: Ј 0 (точка 5 фиг.4).

ра 30 - ЈУ

Последнее приводит к тому, что на выходе элемента И 18 первого блока анализа 7 оказывается ноль. Несмотря 15 на то, что произошла смена знака $V и на выходе элемента 22 неравнозначности первого блока 7 анализа имеется единица, но из-за отсутствия тактового сигнала на входе 27 первого ся переход в точку 1 фиг.4. Поскольку 20 блока 7 анализа, на выходе И 16 присмены знака и V не произошло, то на выходе элемента 22 неравнозначности в первом блоке 7 анализа - ноль, закрыт

элемент И 16

По заднему фронЛ

25

ту тактового импульса t Cv j записывается в регистр 31 и появляется на выходах 33 - 35. Если в некоторый момент оказалось, что получено значение &V (на выходе 33 - нуль), в старших разрядах $v - нули (на вы- 30 ходах 34 - нули), а величина, записанная в младших разрядах (выход 35), меньше Д , то на выходе схемы 2 сравнения и элемента И 4 появляются единицы. Последняя свидетельствует о том,35 что решение найдено - выход 13. Поскольку после первого тактового импульса условия не изменились, то второй тактовый импульс выполняет те же действия с той лишь разницей, что в 40 первом счетчике 10 оказывается двойка, а в узле 3 суммирования - величина oVg. V - Vj- v, (точка 2,фиг.4). Аналогичное увеличение а продолсутстйует ноль. В результате по Ј $ триггер 19 первого блока анализа вновь устанавливается в нулевое состояние, а в регистр 31 записывается oVj $V v2 0. Сигнал с выхода 33 устанавливает вычитающий режим работы первого счетчика 10 и режим передачи через первый селектор 9 в прямом коде. Следующий тактовый импульс вычитает единицу из а и формирует $V V - v, 0 (точка 6). Происходит смена знака fV5 на выходе элемента 22 неравнозначности первого блока 7 анализа появляется единица, а поскольку это изменение было связано с величиной а - на входе 27 первого блока 7 анализа присутствует тактовый сигнал, то на выходе элемента И 16 появляется единица, которая, пройдя элемент ИЛИ 20, по 23 устанавливает триггер 19 в единичное состояние. По следующему тактовому импульсу изменяется а и происходит переход в точку 7 и т.д. Наконец на 12-м шаге (фиг.4) оказывается, что aj Ne, a,, 0, a . На выходе элементов И 16 и 17 первого блока 7 анализа имеются единицы, следовательно, триггер 19 по Јэ оказывается в единичном состоянии и в следующем такте а не изменяется. Во втором блоке анализа на выходе элемента И 1.8 имеется единица, поскольку режим работы второго счетчика 10 - суммирующий (состояние первого триггера 8),, а а. N2. Поэтому по 3 триггер 19 оказывается в единичном состоянии и обеспечивает прохождение следующего тактового имжается до тех пор, пока по очередному 1/пв первом счетчике 10 не окахется

а, NJ. При этом, поскольку , на выходе элемента И 18 первого блока анализа 7 появляется единица, свидетельствующая о том, что первый счетчик 10 не может выполнить операцию увеличения своего содержимого. Этот сигнал, пройдя элементы ИЛИ 21 и 20, поступает на установочный вход триггера 19 первого блока анализа 7 и по {} g , поступающему с входа 24, и устанавливает триггер 19 в единичное состояние. При этом в узле 3 суммирования накоплено значение g V ч

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

11

проходит через первый коммутатор 6. поступает на второй блок 15 и по $п выполняет те же действия, но с

величинами а

и V

На

во втором счетчике (аг.)

втором этапе оказывается

единица.

в регистре 31 - (.

а на выходе комбинационного сумматора 30 - ЈУ

: Ј 0 (точка 5 фиг.4).

Последнее приводит к тому, что на выходе элемента И 18 первого блока анализа 7 оказывается ноль. Несмотря 5 на то, что произошла смена знака $V и на выходе элемента 22 неравнозначности первого блока 7 анализа имеется единица, но из-за отсутствия тактового сигнала на входе 27 первого 0 блока 7 анализа, на выходе И 16 при5

0 5 0

5

0

5

сутстйует ноль. В результате по Ј $ триггер 19 первого блока анализа вновь устанавливается в нулевое состояние, а в регистр 31 записывается oVj $V v2 0. Сигнал с выхода 33 устанавливает вычитающий режим работы первого счетчика 10 и режим передачи через первый селектор 9 в прямом коде. Следующий тактовый импульс вычитает единицу из а и формирует $V V - v, 0 (точка 6). Происходит смена знака fV5 на выходе элемента 22 неравнозначности первого блока 7 анализа появляется единица, а поскольку это изменение было связано с величиной а - на входе 27 первого блока 7 анализа присутствует тактовый сигнал, то на выходе элемента И 16 появляется единица, которая, пройдя элемент ИЛИ 20, по 23 устанавливает триггер 19 в единичное состояние. По следующему тактовому импульсу изменяется а и происходит переход в точку 7 и т.д. Наконец на 12-м шаге (фиг.4) оказывается, что aj Ne, a,, 0, a . На выходе элементов И 16 и 17 первого блока 7 анализа имеются единицы, следовательно, триггер 19 по Јэ оказывается в единичном состоянии и в следующем такте а не изменяется. Во втором блоке анализа на выходе элемента И 1.8 имеется единица, поскольку режим работы второго счетчика 10 - суммирующий (состояние первого триггера 8),, а а. N2. Поэтому по 3 триггер 19 оказывается в единичном состоянии и обеспечивает прохождение следующего тактового импульса к следующему блоку 15 (а).

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

Наконец, последний вариант ре- жима работы устройства возникает на 29-м шаге, при котором а 0, 0 и происходит смена знака V. При этом по з из-за единицы на выходе элемента И 18 первого блока 7 анализа триггер 19 запрещает изменение ац. Единица с выхода 29 первого блока 7 анализа поступает на вход 27 второго блока 7 анализа. Режим работы блока 15 - суммирующий (на выходе триггера 8 ноль), а если о то на выходе элемента 22 неравнозначности и элемента И 16 второго блока анализа 7 появляется единица, которая

устанавливает триггер 19 в ноль и запрещает изменение а. Таким образом, увеличение а до достижения NЈ (а это в данном случае нецелесообразно) не происходит.

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

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

д 0 5

0 5 0

5

0

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

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

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

&л

.-ff

j