Вычислительное устройство для решения задачи выправки железнодорожного пути

 

. ен р» " 4И" >1 ° ° т, ° ою ф

ИЗОБРЕТЕН ИЯ

Союз Советсник

Социалистических

Респубики

>708355

К АВТОРСКОМУ СВЙДЕТЕЛЬСТВУ (6E ) Дополнительное к авт. свнд-ву— (22) Заявлено 21.07.77 (21) 2511 304/18-24 (Я ) М. Кл.

G 06 F 15/20 с присоединением заявки РЙ тввударвтввииый квиитвт

СССР ав делам извбретеиий н открытий (23) Приоритет

Опубликовано 05.01.80. Бюллетень М 1

Дата опубликования описания 07.01.80 (53) УДК 681.322 (088.8 ) (72) . Авторы изобретения

Ю. В. Власенко, E. A. Проскурин и Э. 3. Трайнин

Ордена Ленина институт кибернетики AH Украинской CCP (71) Заявитель (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

ЗАДАЧИ ВЫПРАВКИ ЖЕЛЕЗНОДОРОЖНОГО ПУТИ

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

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

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

Работа прототипа заключается в выполнении программы, реелиэируюшей градиент5 ный метод решения задачи путем сведения ее к итерапионной задаче минимизации суммы модулей неизвестных (управляемого вектора сдвигов g ) за счет изменето ния в допускаемых пределах управляющего вектора повязок 2,.

При этом на каждой итерации неизвестные сдвиги вычисляются по рекурентной формуле.

1 = (,2,. ° .,>1> где В1 — величины, определяемые разностью натурных стрел в двух соседних точках пути;

Z. — невязки, которые могут изменяться в пределах з

Каждая составляющая вектора Х прове- этому ограничению. П ряется на допустимость по ограничениям значения невязок испо сверху и снизу, т.е. проверяется справед- лении нового вектора ливость неравенства: (1«+ 1 ) -ой интераци и. где

Р1 =Х1(P

5 где - P 1 P ограничения на сдвиг Х 1 °

Абсолютные значения вычисленных ( суммируются. Накопленная сумма модулей

И1 1О сдвигов д= ; (y „! хранится в специальной . 1=1 ячейке блока памяти 2 и используется в дальнейшем при расчете нового вектора невязок, который выполняется, если

t5 хотя бы одна составляющая )(„вектора сдвигов X не удовлетворяет своим ог« раничениям.

Новые невязки вычисляются по формуле, ) !« 20 „= Z, Н вЂ” (г:; ()

М

az1

- градиентный множитель, значение которого определяется сле-. дящим выражением: ах"

30 частные производные„вектора X е по « -ым приращениям вектора Z которые вычисляются по формулам; х )«hl-1 (1 УИ ir, .;- (4)

1 б I

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

Частные яровавоввые {граяаевты ) то

%7 1 вычисляются дважды на каждой интерации.

Первый раз - для получения суммы квадратов этих градиентов и градиентов множения Н)«по формуле (3). Е)торой раз эти частные производные вычисляются с целью определния приращений невязок (Н вЂ” р- ) а еовыя евеееявй вевявоя.

М 9 о

1 ! . л

)«+1 ")(ф,+4» 1« "(«Q ir (5)

1 1 1 1 .Я Хе !

Эти новые значения нввязок проверяются на допустимость по ограничениям на невязки, т.е. проверяются условии,"

55 1+4 — «! с у. с{!{

Если какая либо невязка превыша! ет свое ограничение, она приравнивается олученные новые льзуются при вычиссдвигов X. на

")«+ 4

Процесс минимизации вектора Х длится до тех пор, пока не будет найдено первое решение, удовлетворяющее заданной системе неравенств.

ПРототипу присущ следующий недоста ток: большие затраты времени на решение задачи нелинейного программирования с двусторонним ограничениями на зависимые и независимые переменные, вызванные нее обходимостью многократно (на каждой итерации) проверять каждую вычисленную переменную>ее допустимость по ограничениям сверху и снизу.

Целью предлагаемого изобретения является повышение быстродействия устройства.

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

:ключен к выходу регистра-маски, выход группы элементов И через элемент ИЛИ подключен к первому входу триггера, второй вход которого соединен с выходом блока управления, первый выход триггера подключен к первому управляющему входу регистра ограничения невязок, второй вход триггера соединен со вторым управляющим входом арифметического блока, второй выход которого подклюЧен ко второму входу регистра ограничения невязок и к первому входу сдвигово»

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

На чертеже представлена схема устройства. Она содержит: арифметический блок1, блок памяти 2, блок ввода«вывода 3, блок управления 4, регистр ограничения невязок 5, регистр-маску 6, группу элементов И 7, элемент ИЛИ 8, триггер 9, сдвиговый регистр 10, дополнительный блок памяти 1 1.

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

В процессе ввода в регистры блока памяти 2 из блока ввода-вывода 3 зано708355

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

В регистр ограничения 5 заносится код, соответствующий абсолютной величине ограничения на невязки Z. системы линейных неравенств. о

В регистр-маску 6 заносится код, содержащий нули в младших разрядах; число таких разрядов обусловлено максимально допустимым значением невязок, определенньгми условиями решаемой задачи. В остальные разряды регистра»маски 6 заносятся единицы.

Выходы регистра-маски 6 заведены на вторые входы группы элементов И 7, первые входы которых соединены с соответствующими выходами арифметического блока 1. Таким образом, регистр-маска

6 маскирует нулями некоторое множество младших разрядов арифметического блока 1.

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

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

1 появится единица, которая пройдет на вход элемента И ПИ 8. На выходе этой схемы о появится управляющий сигнал, который переключает триггер 9 в единичное состояние. При этом информация об абсолютном значении невязки поступит в блок памяти 2 из регистре ограничения невяз45 ки 5. Информаш я о знаке невязки „поступает на вход знакового разряда регистра 5 непосредственно с выхода знакового разряда арифметического блока l.

Тр птер 9 перед началом вычисления оче50 редной невязки предварительно устанавливается в состояние 0 управлянхцим сигналом на соответствующем выходе блока управления 4.

По завершении процесса ввода инфор55 мации начинается вычисление вектора сдвигов X = F (Х„L ).При этом начальное о значение вектора невязок Х принимается равным нулю. о

В процессе вычисления сдвигов Х„в соответствующей ячейке блока памяти 2 накапливается сумма модулей величины

X.„,a информация о знаках величин Х1 заносится в сдвиговый регистр знаков 10.

Эта информация используется в дальнейшем при вычислении нового вектора невязок Z. Каждый вычислительный сдвиг Х1 проверяется на допустимость по ограничениям сверху и снизу путем последовательного сравнения вычисленной величины

Х„. с числами, расположенными в соответствующих регистрах блока памяти 2. При получении первого значения 5 < не удог влетворяющего заданным ограничениям, проверка последующих Х„. не производится, а по окончании вычисления всего век k тора Х и накопления суммы модулей Х начинается процесс вычисления нового вектора невязок Z +" как функции от знаков величины сдвигов, хранящихся в сдвиговом регистре 10. Введение сдвигового регистра 10 позволяет значительно ускорить процесс вычисления невязок, значения знаков сдвигов поступают с выхода сдвигового регистра 10 синхронно с выдачей из дополнительного блока памяти

11 коэффициентов формулы для вычисления.

Невязки Z. вычисляк,.: .я как функции от суммы коэффициентов г,,; > абсолютные значения которых хранят;я в дополнительном блоке памяти ll и от суммы модулей сдвигов 1 Знаки коэффициентов L „ определяются знаками сдвигов )(., хранящихся в сдвиговом регистре 10. Значения невязок,, лежащих в рамках выбранных ограничений, поступают в блок памяти 2 из арифметического блока 1. Если же значение какой-либо невязки пре.вышает ограничение, то в блок памяти 2 записывается код, зафиксированный в регистре ограничения невязок 5.

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

708355

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

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

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

Источники информации, принятыв во внимание при экспертизе

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

М 410409, кл. С 06 С 7/122, 1974.

2. Майоров С. A., Íîâèêîâ Г. И. Принцип организации цифровых машин - Л., Машиностроение, 1974 (прототип).

БНИИПИ Заказ 8489/44 Тираж 751 Подписное

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4