Устройство для решения систем линейных алгебраических уравнений Советский патент 1985 года по МПК G06F17/10 G06F17/12 

Изобретение относится к вычислительной технике и может быть применено при построении специализирован ных и проблемно-ориентированных про цессоров для решения систем линейны алгебраических у| авнений (СЛАУ) в двоичной системе счисления. Цель изобретения - увеличение быс тродействия. Алгоритм для решения СЛАУ вида 1)j,i l,n .21 а;; V: ом представляется по методу цифра за цифрой следующим образом: 1 С« м-1-Чп(еГ)) H.)Jo. М при i-j. .К40 сС f-b;,;cb, или для непосредственной структурн реализации в предлагаемом устройст в виде

,)j4(-sign()) О, если ст.разр.

.«10 Г

1, если ст.разр.

при

(3)

°гЕ-;г- .

(6)

tj -ё If 2-«, к-о

Xpexi Z-V

J krO J

i jHTn, . bVGfO,l$,

xl. е{1, 0 (7) Условием перехода на (К+1)-й шаг является вьшолнение соотношения .,5|е, . . (4) Таким образом, переход на следующий шаг осзтцествляется, если на данном шаге значение каддой невязки уменьшается как минимум в два раза, т.е. обнуляется старший разряд в регистрах свободных членов. Гарантией поразрядного уменьшения невязок СЛАУ является соблюдение условия сходимости, которое для итера ционных процессов оценивается следующим соотношением «м. а; Oj.i Верность получаемых на каждом шаге цифр в значениях корней гарантируется условием (5). Все козффициенты, свободные члены и искомые корни для СЛАУ ввда (1) представляются правильными дробями и задаются в позиционной системе счисления с основанием 2 р-разрядньми симметричными коцамй в виде

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕ- , НИИ, содержащее матрицу размером ПП регистров коэффициентов, м сдвиговых регистров неизвестных, ц сдвиговых регистров свободных членов, П сумматоров (п - порядок системы линейных алгебраических уравнений) и генератор, тактовых импульсов, отличающееся тем, что, с целью увеличения быстродействия, в него введены первая и вторая матрицы размером И- И групп элементов И и счетчик, причем первые входы элементов И и счетчик, причем первые входы элементов И (А ,р-ых групп первой и второй матриц соединены соответственно, с прямыми и инверсными выходами (.1,)-го регистра коэффициентов матрицы, 4 tj-i t информационный вход -го сдвигового регистра свободных членов соединен с выходом 1-го сумматора, i 1,п , входы -го сумматора соединены с информационным входом i-ro сдвигового регистра свободных членов и с соответствующими выходами элементов И групп t-ых строк первой и второй матриц, выход старшего разряда -го сдвигового регистра свободных членов соединен с входом первого младшего разряда i -го сдвигового регистра неизвестных и с вторыми входами элементов И групп t -ых столбцов первой и второй матриц, прямой выход знакового разряда п-го сдвигового регистра свободных членов соединен с третьими входами элементов И групп 1 -ых столбцов первой (Л матрицы, инверсный выход знакового С разряда -ГС сдвигового регистра свободных членов соединен с входом второго младшего разряда i -го сдвигового регистра неизвестных и третьими входами элементов И групп -ых столбцов второй матрицы, прямой выг ход генератора тактовых импульсов . соединен с входами записи сдвиговых М регистров свободных членов и с входами сдвига сдвиговых регистров неизвестных, инверсный выход генератора тактовых импульсов соединен с входами сдвига сдвиговых регистров свободных членов и со счетным входом счетчика, выход переполнения которого соединен с входом останова генератора тактовых импульсов.

b; - в регистры свободных членов

На чертеже представлена структур-h сдвиговых регистров 3 свободных

ная схема устройства.55членов, п сумматоров 4, генератор 5

Устройство содержит матрицу разме-тактовых импульсов, шины 6 записи

ром п-п регистров 1 коэффициентов,. коэффициентов, шины 7 записи свободп сдвиговых регистров 2 неизвестных,ных членов, выходные шины 8, первую и вторую матрицу размером п. п групп элементов И соответственно 9 и 10, с Гетчик 11, шину 12 начальной установки. Так как записываемая в регистры 2 на каждом шаге информация (а именно, разряды неизвестных) имеет знак, а кодирование знаков в двоичной системе счисления осуществляется следующим образом: - - 0; + - 1, то отличительной чертой этих регистров от остальных является лишь увеличенная вдвое разрядность. Сумматор 4 конструктивно выполнен по комбинационной схеме и имеет (п+ +1) р-разрядных входов. Вычисление значений корней СЛАУ с необходимой точностью (р разрядов) в устройстве производится до появления сигнала переноса счетчика 11. Этот сигнал при достижении счетчиком значения р блокирует работу генератора тактовых импульсов 5. Емкость счетчика таким образом однозначно оп ределяет точность (количество вычисляемых разрядов в значениях корней). Устройство работает следующим образом. После записи в регистры 1 по ши нам б коэффициентов решаемой СЛАУ и установки на шинах 7 ее свободных членов сигналом по шине 12 обнуляется счетчик 11, т.е. переходит в состояние О выход переноса. Это позволяет запуститься генератору тактовых, сов 5. . Первым положительным фронтом им.пульса с прямого выхода генератора синхронизируется запись с шин 7 в ре гистры 3 свободных членов и производится пустой сдвиг в регистрах 2, поскольку до начала работы регистры 3 были пусты, т.е.-старший значащий разряд находился в состоянии О, Это нулевое состояние обеспечивается и без предварительного обнуления, так как после окончания решения в устройстве любой предыдущей СЛАУ по условию (4) старпшй разряд обнулен. Первым положительным фронтом импульса с инверсного выхода генератора 5 осуществляется сдвиг значений свободных членов на один разряд влево, тем самым в старшие значащие разряды регистров поступают первые разряды свободных членов для анализа, установки на входах регистров 2, управления соответствующими группами элементов И 9 и 10. НД протяжении всего пр.оцссса вычислений за время которое проходит между появлением положительных фронтов с прямого выхода генератора 5, происходит запись в регистры 3, сдвиг в регистрах 2, а через равные длительности положительного импульса с прямого выхода генератора тактовых импульсов - сдвиг в регистрах 3. За время между положительными фронтами с инверсного и прямого выходов гарантированно появляется результат на вькодах сумматоров 4. Кроме того, положительные фронтом с инверсного выхода генератора 5, подключенного к счетному входу суммирующего счетчика 11, прибавляется 1 к его содержимому. После появления 1 на выходе переноса счетчика 11 работа генератора тактовых импульсов блокируется. Время вычисления корней СЛАУ п-го порядка с р значащими двоичными цифрами определяется следующим образом: C.Cj-.p,