Цифровое вычислительное устройство гибридных вычислительных машин Советский патент 1988 года по МПК G06J3/00 

к

Ч

СО 00 4

рбйство, с целью повышения быстродействия и расширения функциональных возможностей за счет решения нелинейных и динамических задач, содержит генератор 1 тактовых сигналов:, блок 2 формирования реверса направления поиска, счетчик 3 направлений, блок 4 формирования направлений поиска, состоящий ИЗ триггера 5 реверса, узла 6 памяти, управляемого инвертора 7 направлений, блок 10 переключения поиска, К формирователей 11 компонент результирующего вектора, формирователь 12 признака максимального значения компоненты вектора, блок 13 управления, что позволяет после цикла покоординатного поиска осуществлять поиск по сформированному вектору результирующего направления. Тем самым ускоряется процесс поиска в случае нелинейных задач, характеризующихся овражным характером целевой функции, а также расширяются возможности решения нелинейных динамических задач 6 нл

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

1

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

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

На фиг. 1 показан пример реализации цифрового вычислительного устройства гибридных вычислительных машин; на фиг. 2 - граф работы блока формирования реверса и изменения направления поиска; на фиг. 3 - таблица программирования для узла1 6 памяти; на фиг. 4 - пример реализации переключения поиска; на фиг. 5 - пример реализации формирователя компоненты результирующего вектора; на фиг. 6 - пример реализации блока управления на ПЗУ, таблица программирования.

Цифровое вычислительное устройство гибридных вычислительных машин (фиг. 1) содержит генератор 1 тактовых сигналов, блок 2 формирования реверса и изменения направления поиска, счетчик 3 направлений, блок 4 формирования направлений поиска, триггер 5 реверса, узел 6 памяти, управляемый инвертор 7 направлений, информационные выходы 8(1),...,8(К) уст- ройства, информационный вход 9 устройства, блок 10 переключения поиска, формирователи 11 (1), ...,11(К) компонент результирующего вектора, формирователь 12 признака максимального значения компоненты вектора, блок 13 управления, выход 14 режима поиска устройства, 15(1),...,15(К) - компонент вектора результирующего направления устройства.

Генератор 1 тактовых сигналов предназначен для формирования двух стабильных последовательностей тактирующих сигналов: - на первом выходе и Сц - на втором выходе. Причем f-j. Сц- Генератор тактовых сигналов может быть выполнен по известным принципам на основе мультивибратора с кварцевой стабилизацией частоты генерации и последующего ее деления .

Блок 2 предназначен для формирования команд изменения направления поиска и реверса р движения в заданном направлении S в зависимости от входного сигнала G , знак которого соответствует знаку изменения целевой функции. Блок логики поиска может быть выполнен по известным принципам, а его работа может быть описана графом, приведенньм на фиг. 2, гце 5, G - входные сигналы; Р вырабатываемые команды в соответству- ющих состояниях.

Узел 6 памяти может быть выполнен в виде постоянного запоминаюодего устройства (ПЗУ) на К п-разрядных слов, предстарляюп их направления поиска S ( О,..., К-1), в качестве которых используется система функций Уолша-Адамара, обладагасцих взаимной ортогональностью. На фиг. 3 показана таблица программирования ПЗУ, например типа К155РЕЗ, для случая К п 8.

Управляемый инвертор 7 направлений предназначен для умножения компонент вектора S на сигнал знака движения в заданном направлении, поступающий на управляющий вход. Управляемый инвертор направлений может быть выполнен по, известной схеме из стандартных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, ко-20 выходы которых объединены с помощью

личество которых будет оответство- вать числу компонент вектора S .

Блок 10 предназначен для формирования сигнала д)-переключения процесса поиска в гибридной ЭВМ с записанных в узле памяти координатных направлений S на формируемое в результате цикла координатного поиска направле- ние S . На фиг. 4 приведен пример реализации блока 10. Он может быть выполнен по известным принципам и содержит D-триггер 16. Причем первьм входом блока 10 переключения поиска является J-вход JK-триггера 17, а вторым входом - тактовый С-вход D-триг- гера 16, выход которого соединен с R-входом JK-триггера. Входы S, С, К триггера 17 объединены и через резистор R соединены с шиной питания. Выходы Q и Q JK-триггера являются соответственно первым и вторым выходом блока 10 переключения поиска, причем выход Q соединен также с D-входом D-триггера.

Формирователи 11(1),...,11(п) компонент результирующего вектора предназначены для формирования компонент вектора 5. Каждый из них может быть выполнен по известному принципу, пример реализации которого приведен на фиг. 5. Формирователь компоненты реализующего вектора содержит коммутатор 18, реверсивный счетчик 19, регистр 20 сдвига. Выходы коммутатора 18 А1 и АО соединены соответственно с входами прямого и инверсного счета реверсивного счетчика 19, выход восьми старших разрядов которого соединены с соответствующими входами регистра 20 сдвига. Входы С и S1 регистра сдвига, а также вход R реверсивного счетчика 19 являются управляющими входами формирователя компоненты результирующего вектора, а выходами являются выходы регистра 20 сдвига. Причем входы S(, и R последнего через резисторы R соединены с шиной питания, а вход D - заземлен.

Формирователь 12 предназначен для

формирования флагового сигнала N, указывающего, что величина одной из компонент вектора s после сдвига приобрела максимально возможное значение . Формирователь флага может быть выполнен по известным принципам как -. в виде дешифратора на ПЗУ, так и в виде набора элементов ИСКЛЮЧАЮЩЕЕ ИЛИ,

0

5

схемы ИЛИ и являются выходом формирователя 12.

Блок 13 управления предназначен для формирования сигналов, поступа- 5 ющих на входы формирователей 11(1), . .., 11(п) компонент результирующего вектора. Блок управления может быть реализован по известным принципам на ПЗУ, например таблица программирования которого приведена на фиг. 6. Причем вход D1 микросхемы является . тактирующим входом, D2 - первь1м, а D3 - третьим входом схемы управления. Входы D4, D5, V заземлены, а выходы Q1, Q2, Q3 - являются соответственно С, S1, R - управляющими выходами блока 13 управления.

Предлагаемое цифровое вычислительное устройс тво гибридных вычислительных машин работает следующим образом.

В составе гибридной вычислительной машины цифровое вычислительное устройство управляет процессом отыскания значений переменных, которым соответствует минимальное значение некоторой целевой функции. С этой целью последняя строится по условиям задачи таким образом, чтобы ее минимумы соответствовали исковым решениям. Отыскиваемые минимумы могут иметь как локальный, так и глобальный характер, что и определяет соответственно момент нахождения локального или глобального решения исходной задачи.

Траектория движения точки поиска, а следовательно, и скорость отыскания решения, определяются видом целевой функции (ее овражностью), за- ;

0

5

0

5

5142

висящим от условий задачи, и алгоритм поиска. Реалиэуемьй устройством алгоритм представляет собой комбинацию уже упомянутого координатного поиска и ускоренного по направлению S«, которое определяется как вектор результирующего продвижения за цикл координатного поиска. Причем каждый цикл

координатного поиска в направлении S завершается изменением переменных в найденном результирующем направлении 8. Движение в направлении S , как и в направлении S , осуществляется до достижения минимума целевой функции. Совпадение результирующего продвижения S с осью оврага позволяет значительно повысить общую скорость движения точки поиска к искомому минимуму в случае овражного характера целевой функции.

Определение результирующего продвижения S (S,...,S) сводится к алгебраическому суммированию изменений отдельных переменных в каждом направлении S , т.е.

s

,

где ut - время движения в направле- НИИ S .

Указанное суммирование, учитывая постоянную скорость Vjj изменения переменных сводится к подсчету с помощью реверсивных счетчиков некоторых тактовых сигналов с равление счета определяется соответствующими компонентами Х;.

Рассмотрим более подробно работу цифрового вычислительного устройства гибридных вычислительных машин по функциональной схеме на фиг. 1.

Входной сигнал устройства (J содержит информацию об убывании ((j 0) или возрастании (0 1) во времени значения целевой функции при изменении переменных в вырабатыва:емых на

3Q Блок 13 управления в этом режиме по сигналам Т осуществляет перезапись информации с реверсивного счетчика 19 в регистр 20 сдвига.

После перебора всех К направлений

35 S на выходах сдвиговых регистров Причем нап- сформируются компоненты ( ...,п), величины которых пропорциональны результирующему изменению соответствующих переменных, а знак 40 равен знаку продвижения в заданном направлении. Далее счетчик 3 направлений по перепаду сигнала с высокого на низкий уровень, поступающему на первый вход блока 10 переключения по45 иска, взводит ее, в результате чего на выходе 14 появляется сигнал высокого уровня ей 1, одновременно поступающий на вход установки в нуль счетчика 3 направлений и удерживавыходах устройства направлениях S или S. Причем сигнал о на выходе

режима поиска устройства 14 определя- ющий его в исходном состоянии. Одно- ет режим поиска по выбранным S направлениям (со ° 0) на выходах 8(1), ...,8(п) или сформированному вектору S направления (СО 1) на выходах 15(1),...,15(п).

Блок 2 при возрастании целевой функции (G 1 - высокий уровень) по сигналам на тактовом входе формирует на своих выходах команды перевременно с сигналом высокого уровня на первом выходе блока 10 переключения поиска, на его втором выходе формируется инверсный сигнал низкого 55 уровня, поступающий на первый вход блока 13 управления. При этом по сигналам t g, на тактовом входе блок уп-. равления осуществляет управление нормализацией накопленных значений вехода на новое направление поиска 9 и реверса направлений р согласно приведенному на фиг. 2 графу. При убывании целевой функции (G О - низкий уровень) формирование команд и р не происходит и на выходах устройства 8(1),.,.,8(п) удерживается направление S .

В режиме поиска по координатным направлениям S ( 0) компоненты X ,.. f VI поступают на входы формирователей 11( 1),...,11(К) компонент результирующего вектора к осуществляют коммутацию сигналов Гц на вход прямого (Х-, 1) или инверсного (%; 0) счета реверсивного счетчика 19. Разрядность реверсивного счетчика выбирается исходя из максимально возможного изменения переменных д Х за цикл координатного поиска и числа сигналов которое соответствует этому изменению. Например, если изменение переменной за период следования с ц соI

ставляет 0,001 от числа машины, то достаточным является 10-11 разрядов, так как число в счетчике не может превысить 1000 при условии, что переменные не вышли за шкалу.

Блок 13 управления в этом режиме по сигналам Т осуществляет перезапись информации с реверсивного счетчика 19 в регистр 20 сдвига.

После перебора всех К направлений

ющий его в исходном состоянии. Одно-

временно с сигналом высокого уровня на первом выходе блока 10 переключения поиска, на его втором выходе формируется инверсный сигнал низкого 55 уровня, поступающий на первый вход блока 13 управления. При этом по сигналам t g, на тактовом входе блок уп-. равления осуществляет управление нормализацией накопленных значений величин , ...,, сформированных в соответствующих формирователях компонент результирующего вектора. На их входы подаются сигналы, осуществляющие левый сдвиг информации в сдвиговых регистрах 20 до тех пор, пока формирователь 12 вьщаст сигнал, указывающий что одна из компонент sV приняла максимально возможное значение sK Далее осуществляется хранение этих величин и одновременно подготавливается к новому циклу реверсивный счетчик 19, т.е. осуществляется его сброс.

Таким образом, на выходах устройства 15(1),...,15(п) будет сформирован п-компонентный векторный сигнал результирующего направления S (S,, ...,ЗД), каждая из компонент S,,..., ,5 - однобайтовая величи: а, задающая знак и величину скорости (с точностью до постоянного множителя) соответствующей переменной. Вектор S« удерзкивается на выходах устройства до тех пор, пока О не станет равной единице.

При возрастании целевой функции блок 2 по ближайщему сигналу „ сформирует сигнал , который задним фронтом сбросит блок 10 переключения поиска. При этом на счетчик 3 направлений поступит сигнал, разрешающий дальнейший счет команд - , а на управляющий выход 14 устройства - сигнал СО 0. На выходах 8( 1), ... ,8(п) устройства в это время будет сформирован вектор направлений S (v 0).

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

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

0

5

единен с тактовым входом блока формирования реверса и изменения направления поиска, вход которого являет- . ся информационным входом устройства, первый и второй выходы блока формирования реверса и изменения направления поиска соединены соответственно с входом блока формирования направлений поиска и со счетным входом счётчика направлений, выходы которого соединены с группой входов блока формирования направлений поиска, отличающееся тем, что, с це- 5 лью повьш1ения быстродействия и расширения функциональных возможностей за счет решения нелинейных и динамических задач, в него введены К формирователей компонент результирующего вектора (где К - количество компонент вектора) блок управления, формирователь признака максимального значения компоненты вектора, блок подключения поиска, первый вход которого соединен с выходом старшего разряда счетчика направлений, вход установки в О которого соединен с первым выходом блока переключения поиска и является выходом режима поиска устройства, второй выход блока подключения поиска соединен с первым входом блока управления, тактовый вход которого соединен с вторым тактовым выходом генератора тактовых сигнапов, первый тактовый выход которого соединен с тактовыми входами формирователей компонент результирующего вектора, К-й информационный выход группы устройства соединен с входом компоненты К-го формирователя компоненты результирующего вектора, выход которого соединен с К-м входом формирователя признака максимального значения компоненты вектора, выход кйторого соединен с вторым входом блока управления, выход которого соединен с входами установки режима формирователей компонент результирующего век тора, выходы которых являются выходами компонент вектора результирующего направления устройства. .

0

5

0

5

0

бТд,

Фиг,2

Фиъ. 3

фиг.

(г) (О

(3)