Устройство для решения систем линейных алгебраических уравнений
Изобретение относится к цифровой вычислительной технике и может быть использовано для быстрого решения систем линейных алгебраических уравнений . Цель изобретения - повьшение производительности устройства. Устройство содержит матрицу пхп умножителей , п регистров, п сумматоров, п блоков приоритетного формирования нулей и элементов задержки, п элементов сравнения, элемент И, элемент ИЛИ, элемент НЕ, два одновибратора. Увеличение производительности устройства обеспечивается в результате уменьшения интервала времени между двумя последовательными записями приближений в регистр за счет определения моментов окончания формирова- 1НИЯ результатов. 2 ил. i (Л tc СП 4 сл
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51) 4 G 06 F 15/324
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К д ВТОРСНОМУ СВИДЕТЕЛЬСТВУ 1 С!
: 2
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3830248/24-24 (22) 25.12.84 (46) 30.08.86. Бюл. У 32 (71) Институт проблем моделирования в энергетике АН УССР (72) В.Н. Белецкий, М.Н. Кулик, А.А. Чемерис, Г.П. Карась, A.Ï. Павлусенко и С.Ф. Семенов (53) 681.32(088.8) (56) Пухов Г.Е. Структурно-аналоговые цифровые вычислительные системы.
Электроника и моделирование. Киев:
Наукова думка, 1975, вып.7, с.50.
Алексеенко А.Г., Шагурин И.И. Микросхемотехника. М.: Радио и связь, 1982, с.416.
Карцев M.À, Брик В.А. Вычислительные системы и синхронная арифметика, М.: Радио и связь, 1981, с.316.
„„SU» 1254504 А1 (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ
ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано для быстрого решения систем линейных алгебраических уравнений. Цель изобретения — повьппение производительности устройства. Устройство содержит матрицу пхп умножителей, и регистров, и сумматоров, и блоков приоритетного формирования нулей и элементов задержки, и элементов сравнения, элемент И, элемент
ИЛИ, элемент НЕ, два одновибратора.
Увеличение производительности устройства обеспечивается в:результате уменьшения интервала времени между двумя последовательными записями приближений в регистр за счет определения моментов окончания формирования результатов. 2 ил.
1254504
inax (! b„ l)
<Х хоx; 1= 1 гх
t1 т {à,;", L i х, i} х1 J i имеем
Изобретение относится к цифровой вычислительной технике и может быть использовано в составе универсальных или специализированных машин, а также автономно для быстрого решения системы линейных алгебраических уравнений (СЛАУ).
Цель изобретения — повышение производительности устройства., На фиг.1 представлена блок-схема устройства для решения СЛАУ порядка два; на фиг." — схема одного разряда блока приоритетного формирования нулеи.
Устройство содержит первый и второй регистры 1.1 и 1.2, умножители
2.1.1, 2.1.2, 2.2. I 2.2.2 матрицы умножителей, первый и второй сумматоры 3.1 и 3.2, первый и второй блоки 4.1 и 4.2 приоритетного формирования нулей, первый и второй элементы 5.1 и 5.2 задержки, первый и Второй элементы 6.1 и 6.2 сравнения, элемент ИЛИ 7 первый и второй одноВибратор 8, элемент HE 9„ элемент
И 10. одно?1ибратор 1 1, входы 12-15 задания коэффициентсв уравнений, Входы 16 и 17 задания Величин пра.зых частей уравнений, вход 18 зат1уска устройства, Выходы 19 и 20 результата устройства, Выход 21 сигнала окончания решения. Блок приоритетного формирования нулей содержит m идентичных схем, где Ql = разрядность устройства каждая из которых содержит одковибратор 22, элемент 23 заэлемент И 24, вход 25, ход 26.
Устройство работает образом. !
В блоке приоритетного формирования нулей в стационарном режиме "О" или "1" на входе 25 повторяется на его выходе 26. При перек1почении "1" в "0" на входе ?5 одновибратора 22 последний запускавтсн и на его Выходе имеет место "1", на выходе 26 формируется. 0". При переключе?п1и
"О" в "1" на Входе 25 одновибратор
22 запускается. На его выходе формируется отрицательный импульс длительностью, после Окончания которого на Выходе 26 формируется значение " 1". Таким обоазом значение " 1" ня Выходе устрОйcvB=; формируется с задержкой на регулируемое время 7 в то время, хак значение "О" сразу же поступает на Выход.
Перед началом решения в исходной
СЛАУ Ах=Ь осуществляется замена переменной
x = Z — х гпа х
5 где х — вектор компоненты которо àõ
Э го положительные и не меньше максимального по модулю решения х. СЛАУ
12
Ах = Ь, такой, что выполняются неравенства
1О ОЫ =Ах +ЫЕ =А й, ?па х
В результате приходим к СЛАУ.вида
AZ= f решение которой неотрицательное, так как
Z = х +х >О
4? àÕ
Указанное преобразование осуществляется, если компоненты матрицы А удовлетворяют условиям
О а„; 1, а, (О, à,. >+}а;„l
9 ei
В этом случае значение х . долж од но удовлетворять неравенству где тах11Ь1 - наибольшая по модулю компонента вектора Ь.
Из перавенств х1
0 i,j Поскольку О а.. <1, a,. .О, то 13. (А-.E) Z О и, следовательно (А — Е)? =(А-Е) (х +х ) =Ах +Ь вЂ” (х + + Îx " о х åõ +.х ), откуда f = Ax +Ьсх +х = А (Ах +Ъ) =Af = Z", Далее СЛАУ преобразуется к виду 50 Z = Z I(AZ f) p=2" целое число, так, чтобы при Z< > Z 2 выполнялось Z — 1" (AZ — f ) > Z "1 -ti(A? — f) . На входы 12-17 задаются соответственно значения компонент 55 (1-Ра„„), Ра,, Чр, (1-Р,), РЯх, )if .На вход 18 поступает сигнал пуска устройства, по которому запускается одновибратор 11, на выходе кото>04 4 Таким образом, в устройстве имеет место вычислительный процесс, обеспечивающий монотонную сходимость т последовательности Z у к решению Z СЛАУ вида А f = Z. Сигнал готовности на выходе 21 формируется следующим образом, При запуске одновибратора 8 на его выходе формируется импульс, длительность которого не меньшая, чем максимальное время задержки информации в каждой строке от входа регистра до выхода элемента сравнения. При записи любого последовательного приближения в регистры 1 по сигналу от элемента сравнения одновременно повторно запускается одновибратор 8, импульс на выходе которого длится до тех пор, пока в регистрах не устанавливается решение (повторные запуски прекращаются и на выходе 21 формируется единичный сигнал, указывающий на то, что решение найдено) . Элемент НЕ 9 необходим для того, чтобы блокировать сигнал готовности на время запуска одновибратора. После формирования сигнала готовности определяется решение х системы Ах = Ь по формуле х = Z+ — х 1 аX Увеличение производительности устройства обеспечивается в результате уменьшения интервала времени между двумя последовательными заййсями приближений в регистр за счет определения с помощью элементов сравнения моментов окончания формирования результатов. Формула и э о б р е т е н и я Устройство для решения систем линейных алгебраических уравнений, содержащее и регистров, матрицу и х и умножителей, п сумматоров, выход i-ro регистра (i=1„...,п) подключен к входу первого сомножителя умножителей i-ro столбца матрицы, входы второго сомножителя умножителей матрицы подключены к входам задания коэффициентов уравнений устройства, выходы ;х ()=1,..., n) умножителей i-й строки матрицы умножителей подключены к j-м информационным входам i-го сумматора, (n+1)-е информационные входы сумматоров подключены к входам задания величин правых частей уравнений устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения произвоZ Н- = 1 (AZ (11 -f ) т 1 т -1 откуда Z = А f. Запись значения Z (" 1 > Z невозможна, так как Z ("1=Z — p (AZ -f) = 2 3 1 3., рого формируется короткий отрицатель ный импульс, поступающий на R-входы регистров 1. В результате значения на выходах регистров обнуляются, на выходах сумматоров 3 формируются значения (111, и (llf, которые .через 1 1 2 устройства приоритетного формирования нулей и элементы задержки поступают на D-входы регистров 1 и по сигналу от элемента сравнения записываются в регистры. Таким образом устанавливаются значения компонент вектора начального приближения Z =yf, В дальнейшем на выходе сумматора 3.1 будет формироваться значение Z = Z -p(a Z +а Z -f ), 1 1 1 12 2 1 а на выходе сумматора второй строки — значение 20 а1 Время задержки включения 1 в i-м (i=1,2) устройстве приоритетного формирования нулей не меньше значения О шах (10)11 (о )1 (10) 2 (01)12 25 где („).,1, — наибольшее и наимень(О1)1,( шее время переключения значения разрядов из 11 1 11 llpll ltplt 1 на ход умножите 30 ля i é строки j-ro столбца. Это обеспечивает формирование на выходе i ãî устройства приоритетного формирования нулей значения у, 1 35 удовлетворяющего неравенству у, а Е. — р (а Z +а Z — f ), 1 11 1 И 2 1 i = 1,2. Поступление информации с выхода устройств приоритетного формирования 40 нулей на D-входы регистров через линии задержки исключает возможность записи значений, которые меньше значений, хранимых регистрами, во время отключения сигналов записи в регистр, 45 формируемых элементами сравнения. В последующие моменты времени T„, Т,..., Tä в силу изотонности отоб-. 2У э ражения Z — - p (AZ-f) в регистры будут записываться значения последовательных приближений 50 т т т Z = Z < Z o — t" (AZ o-f ), Z«Z2 Z, — Р(АК -й) т т т т 254504 Щг.2 Составитель В. Смирнов Техред И.Попович Редактор И. Касарда Корректор Е. Сирохман Заказ 4723/54 . Тираж 671 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Подписное Производственно-полиграфическое предприяти е, r. жгород, ул. Проектная, 4 3 1 дительности устройства, оно содержит и блоков приоритетного формирования нулей, и элементов задержки, и элементов сравнения, элемент ИЛИ, элемент И, элемент НЕ, первый и второй одновибраторы, выход i-го сумматора подключен к информационному вхоgy i-ro блока приоритетного формирования нулей, выход которого подключен к первому входу i-го элемента сравнения и входу i-ro элемента задержки, второй вход i-го элемента сравнения подключен к выходу i-ro регистра, выход i-ro элемента сравнения подключен к входу считывания i-ro регистра и к i-му входу элемента ИЛИ, выход i- ro элемента задержки подключен к информационному входу i-ro регистра, выход элемента ИЛИ подключен к входу первого одновибратора и входу элемента НЕ, выходы первого одновибратора и элемента НЕ подключены соответственно к первому Ь и второму входам элемента И, выход которого подключен к выходу сигнала окончания решения уравнения устройства, вход запуска устройства подключен к входу второго одновибратора, выход которого подключен к входам установки в "0" и регистров, выходы которых подключены к выходам результата устройства, при этом блок npu1ð оритетного формирования нулей содержит m одновибраторов (m — оазрядность устройства), m элементов И,, m элементов задержки, вход k-го (k=1,...,m) разряда блока приори1 тетного формирования нулей подключен к информационному входу k-го одновибратора и входу k — ro элемента задержки, выходы К-х одновибратора и элемента задержки подключены соот2б ветственно к первому и второму входам k-ro элемента И, выход которого подключен к выходу k-ro разряда блока приоритетного формирования нулей.
