Цифровое вычислительное устройство гибридных вычислительных машин

 

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

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

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

РЕСПУБЛИК

А1 (19) (11) ш 4 G 06 F 1 5 / 332

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

В(1) (к) Фиг.1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4130308/24-24 (22) 08.10.86 (46) 30.09.88. Бюл. Р 36 (71) Институт проблем моделирования в энергетике АН УССР (72) К.И. Гищак и Н.M. Лещенко (53) 681.325 (088.8) (56) Растриган Л.А., Сытенко Л.В.

Многоканальные статические оптимизаторы. М.: Энергия, 1973, с. 42.

Грездов Г.И. Теория и применение гибридных моделей. Киев: Наукова думка, 1975, с. 48-51, рис. 20. (54) ЦИФРОВОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ГИБРИДНЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН (57) Устройство относится к вычислительной технике, в частности к гибридным вычислительным машинам, управ ляющим процессом решения — отыскания минимума некоторой целевой функции, и может быть использовано в различ.ных областях народного хозяйства для решения динамических задач нелинейного программирования, например при управлении технологическими процессами или автоматизации экспериментов. Уст14273 рбйство, с целью повышения быстродействия и расширения функциональных возможностей за счет решения нелинейных и динамических задач, содержит генератор 1 тактовых сигналов блок 2 формирования реверса направления поиска, счетчик 3 направлений, блок 4 формирования направлений поиска, состоящий иэ триггера 5 реверса,, узла 6 памяти, управляемого инвертора 7 направлений, блок 10 переключения поиска, К формирователей 11 ком84 понент результирующего вектора, формирователь 12 признака максимального значения компоненты вектора, блок 13 управления, что позволяет после цикла покоординатного поиска осуществлять поиск по сформированному вектору результирующего направления. Тем самым ускоряется процесс поиска в случае нелинейных задач, характеризующихся овражным характером целевой функции, а также расширяются возможности решения нелинейных динамических задач 6 ил °

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

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

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

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

13 управления, выход 14 режима поиска устройства, 15(1),...,15(К) — компонент вектора результирующего направления устройства.

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

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

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

14273

Узел 6 памяти может быть выполнен в виде постоянного запоминающего устройства (ПЗУ) на К и-разрядных слов, представляющих направления поиска

S (4 = О,..., К-1), в качестве которых используется система функций

Уолша-Адамара, обладающих взаимной ортогональностью. На фиг. 3 показана таблица программирования ПЗУ, íà- ip пример типа К155РЕЗ, для случая К =

= n = 8.

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

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

R-входом JK-триггера, Входы S, С, К триггера 17 объединены и через резистор R соединены с шиной питания.

Выходы Я и Q JK-триггера являются со- 4р ответственно первым и вторым выходом блока 10 переключения поиска, причем выход Q соединен также с D-входом

D-триггера.

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

55 счета реверсивного счетчика 19, выходы восьми старших разрядов которого соединены с соответствующими входами ре84

4 гистра 20 сдвига. Входы С и Si регистра сдвига, а также вход R ренесинного счетчика 19 являются управляющими входами формирователя компоненты результирующего вектора, а выходами являются выходы регистра 20 сдвига ° Причем входы S и R последнего через резисторы R соединены с шиной питания, а вход D — заземлен °

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

Блок 13 управления предназначен для формирования сигналов, поступающих на входы формирователей 11(1), ...,11(п) компонент результирующего вектора. Блок упранления может быть реализован по известным принципам на ПЗУ, например таблица программирования которого приведена на фиг. 6, Причем вход П1 микросхемы янляется тактирующим входом, 02 — первым, а

D3 — третьим входом схемы управления.

Входы D4, D5, V — эаэеьлены, а выходы Q1, Q2, Q3 — являются соответственно С, S1, R — управляющими выходами блока 13 управления.

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

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

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

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

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

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

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

1 направлении S „ т.е. ь

Е о 1 я

Ч= где дс — время движения в направле- нии S

Указанное суммирование, учитывая постоянную скорость V изменения переменных сводится к подсчету с помощью реверсивных счетчиков некоторых тактовых сигналов с,„, Причем нап/

35 равление счета определяется соответствующими компонентами Х;.

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

Входной сигнал устройства 5 содержит информацию об убывании (G = О) или возрастании (G = 1) во времени значения целевой функции при изменении переменных в вырабатываемых на выходах устройства направлениях S или S . Причем сигнал у на выходе режима поиска устройства 14 определя50 ет режим поиска по выбранным S направлениям ((д О) на выходах 8(1), ...,8(n) или сформированному вектору

S направления (Q = 1) на выходах

15 (1),..., 15 (n) .

Блок 2 при возрастании целевой функции (6 = 1 — высокий уровень) по сигналам на тактовом входе формирует на своих выходах команды пере84 ь хода на новое направление поиска и реверса направлений р согласно приведенному на фиг. 2 графу. При убывании целевой функции (6 = Π— низкий уровень) формирование команд и р не происходит и на выходах устройства 8(1).. .8(n) удерживается направление S

В режиме поиска по координатным .направлениям Б (= О) компоненты

)(,,...,Х > поступают на входы формирователей 11(1),...,11(К) компонент результирующего вектора н осуществляют коммутацию сигналов „ на вход прямого (Ц= 1) или инверсного (Х;= О) счета реверсивного счетчика 19, Раэрядность реверсивного счетчика выбирается исходя из максимально возможного изменения переменных д Х за цикл координатного поиска и числа сигналов которое соответствует этому изменению. Например, если изменение переменной за период следования с со-! и ставляет 0,001 от числа машины, то достаточным является 10-11 разрядов, так как число в счетчике не может превысить 1000 при условии, что переменные не вышли за шкалу.

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

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

S на выходах сдвиговых регистров сформируются компоненты $ (i ...,n) величины которых пропорциональны результирующему изменению соответствующих переменных, а знак— равен знаку продвижения в заданном направлении. Далее счетчик 3 направлений по перепаду сигнала с высокого на низкий уровень, поступающему на первый вход блока 10 переключения поиска, взводит ее, в результате чего на выходе 14 появляется сигнал высокого уровня и = 1, одновременно поступающий на вход установки в нуль счетчика 3 направлений и удерживающий его в исходном состоянии. Одновременно с сигналом высокого уровня на первом выходе блока 10 переключения поиска, на его втором выходе формируется инверсный сигнал низкого уровня, поступающий на первый вход блока 13 управления. При этом по сигналам с на тактовом входе блок уп-. равления осуществляет управление нормализацией накопленных значений ве7

Ф

14273 личин S,...,S>, сформированных в соответствующих формирователях компонент результирующего вектора. На их входы подаются сигналы, осуществляю5 щие левый сдвиг информации в сдвиговых регистрах 20 до тех пор, пока формирователь 12 выдаст сигнал, указывающий что одна из компонент S

% приняла максимально возможное значение S?. Далее осуществляется хранение этих величин и одновременно подготавливается к новому циклу реверсивный счетчик 19, т.е. осуществляется его сброс. 15

Таким образом, на выходах устройства 15 (1),..., 15 (и) буде- сформирован и-компонентный векторный сигнал результирующего направления S = (S, 1 ...,Я„), каждая из компонент S ° ° ° °, Ф 5

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

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

Q = О. На выходах 8(1),...,8(n) уст35 ройства в это время будет сформирован вектор направлений S (= О).

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

Цифровое вычислительное устройство гибридных вычислительных машин, содержащее генератор тактовых сигналов, блок формирования реверса и изменения направления поиска, счетчик направлений, блок формирования направлений поиска, выходы которого являются группой информационных выходов устройства, первый тактовый выход генератора тактовых сигналов со84 единен с тактовым входом блока формирования реверса и изменения направления поиска, вход которого является информационным входом устройства,, первый и второй выходы блока формирования реверса и изменения направления поиска соединены соответственно с входом блока формирования направлений поиска и со счетным входом счетчика направлений, выходы которого соединены с группой входов блока формирования направлений поиска, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и расширенйя функциональных возможностей за счет решения нелинейных и динамических задач, в него введены К формирователей компонент результирующего вектора (где К вЂ” количество компонент вектора) блок управления, формирователь признака максимального значения компоненты вектора, блок подключения поиска, первый вход которого соединен с выходом старшего разряда счетчика направлений, вход установки в "О" которого соединен с первым выходом блока переключения поиска и является выходом режима поиска устройства, второй выход блока подключения поиска соединен с первым входом блока управления, тактовый вход которого соединен с вторым тактовым выходом генератора тактовых сигналов, первый тактовый выход которого соединен с тактовыми входами формирователей компонент результирующего вектора, К-й информационный выход группы устройства соединен с входом компоненты

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

1427384

1427384

Риг.5

Cue,6

Корректор Э. Лончакова

Редактор О. Спесивых

Подписное

Тираж 704

Заказ 5434

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 (2} (t) (3) Составитель А. Пак

Техред М.Моprентал

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

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

С й