Модулярное устройство вычисления систем линейных алгебраических уравнений

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

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

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

Наиболее близкое по сущности технического решения заявленному устройству является устройство для решения систем линейных алгебраических уравнений [2], содержащее первый и второй блоки памяти, первый и второй регистры, первый и второй сдвигающие регистры, группу из n умножителей, где n - порядок решаемой системы линейных алгебраических уравнений, первый сумматор, первый коммутатор и блок управления, причем выход первого блока памяти подключен к информационному входу первого сдвигающего регистра, первый выход которого подключен к первым информационным входам умножителей группы, выходы которых подключены к информационным входам первого регистра, выход которого подключен к первому информационному входу первого "сумматора, выход которого подключен к первому информационному входу второго блока памяти, выход которого подключен к второму информационному входу первого сумматора и к информационному входу первого коммутатора, первый выход которого подключен к информационному входу второго сдвигающего регистра, выход второго регистра подключен к второму информационному входу второго блока памяти, выходы с первого по восьмой блока управления подключены соответственно к входу чтения первого блока памяти, к управляющему входу первого сдвигающего регистра, к входам синхронизации умножителей группы, к входу записи-считывания первого регистра, к входу синхронизации первого сумматора, к входу чтения-записи второго блока памяти, к управляющему входу первого коммутатора и к управляющему входу второго сдвигающего регистра, оно содержит второй и третий сумматоры, со второго по шестой коммутаторы, с третьего по пятый регистры, умножитель, делитель, счетчик, элемент ИЛИ, узел сравнения, генератор единиц, первый и второй элементы И, причем второй выход второго коммутатора подключен к информационному входу третьего регистра, выход которого подключен к первому информационному входу третьего сумматора, выход которого подключен к первому информационному входу второго коммутатора, выход которого подключен к первому информационному входу узла сравнения, первый выход которого подключен к первому входу первого элемента И, выход которого подключен к счетному входу счетчика, выход переполнения которого подключен к входу останова блока управления и к управляющему входу третьего коммутатора, первый выход которого подключен к выходу результата устройства и к вторым информационным входам умножителей группы, второй выход первого сдвигающего регистра подключен к первому входу элемента ИЛИ, выход которого подключен к первому информационному входу второго сумматора, выход которого подключен к информационному входу четвертого коммутатора, первый выход которого подключен к первому входу делителя, выход которого подключен к первому информационному входу умножителя, выход которого подключен к первому информационному входу пятого коммутатора, выход которого подключен к второму информационному входу узла сравнения, второй выход которого подключен к первому входу второго элемента И, выход которого подключен к входу записи-считывания четвертого регистра, выход которого подключен к информационному входу шестого коммутатора, первый, второй и третий выходы которого подключены соответственно к второму входу делителя, к второму информационному входу пятого коммутатора и к второму информационному входу второго сумматора, выход генератора единиц подключен к второму входу элемента ИЛИ, второй выход третьего коммутатора подключен к второму информационному входу третьего сумматора, второй и третий выходы четвертого коммутатора подключены соответственно к информационному входу четвертого регистра и к второму информационному входу второго коммутатора, выход второго сдвигающего регистра подключен к информационному входу третьего коммутатора, вход запуска и вход значения точности решения устройства подключены соответственно к входу запуска блока управления и к информационному входу пятого регистра, выход которого подключен к второму информационному входу умножителя, выходы с девятого по двадцать третий блока управления подключены соответственно к входу генератора единиц, к входам синхронизации умножителей группы, к входу записи-считывания второго регистра, к входу записи-считывания третьего регистра, к входу синхронизации третьего сумматора, к управляющему входу второго коммутатора, к управляющему входу пятого коммутатора, к входу синхронизации узла сравнения, к второму входу первого элемента И, к входу установки в «0» второго сумматора, к управляющему входу шестого коммутатора, к управляющему входу четвертого коммутатора, к второму входу второго элемента И, к входу синхронизации умножителя и к входу записи-считывания пятого регистра.

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

Цель - повышение быстродействия функционирования при реализации слабообусловленных систем линейных алгебраических уравнений (СЛАУ) и расширение функциональных возможностей устройства за счет обеспечения возможности контроля ошибок вычислений.

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

Исходная СЛАУ принимает вид:

тогда матрица значений коэффициентов при переменных СЛАУ:

вектор значений свободных коэффициентов СЛАУ:

вектор значений переменных:

Рассмотрим метод решения СЛАУ с использованием китайской теоремы об остатках [3], который включает следующие действия:

1. Определение наибольшего коэффициент:

2. Выбор составного модуля из условия:

где m_i - простые числа, m_i<m_i-1, i=1, 2, …, t+1.

3. Вычисление составных проверочных модулей и значений их обратных величин:

где ϕ(m_i) - функция Эйлера, i=1, 2, …, t+1.

4. Вычисление остатков коэффициентов матриц (2, 3) по модулям: m₁, m₂, …, m_t, m_t+l:

5. Вычисление обратных матриц для матриц (9) по модулям m₁, m₂, …, m_t, m_t+1:

6. Вычисление произведений соответствующих матриц (10) на матрицы (11):

где , i=1, 2, …, t+1.

7. Вычисление значений переменных СЛАУ по избыточным модулям: Вычисление значения x₁ для сочетаний простых модулей:

где - нет ошибки, в обратном случае - ошибка, j=1, 2, …, n.

Структурная схема предлагаемого устройства представлена на фиг. 1. Устройство содержит: 1 - первый блок памяти, который обеспечивает хранение значений матрицы (2); 2 - первый блок выбора максимального числового значения, который может быть выполнен на основе устройства [4] с включенным дополнительный регистр хранения промежуточных результатов вычислений и обеспечивает вычисление наибольшего коэффициента (5) путем попарного сравнения всех коэффициентов матриц (2, 3) за 2ⁿ+n-1 повторений; 3 - второй блок памяти, который обеспечивает хранение значений вектора (3); 4 - второй блок выбора максимального числового значения, который может быть также выполнен на основе устройства [4] и обеспечивает выбор по порядку возрастания из составных модулей первого большего M_t, (M_t>k_max>M_t-1), чем выбранный наибольший коэффициент (5); 5 - третий блок памяти, который обеспечивает хранение значений составных модулей (6); 6 - дешифратор, который формирует адрес ячеек памяти находящихся в четвертом, пятом и шестом блоках памяти, в которых хранятся соответственно значения простых модулей m₁, m₂, …, m_t+1, предвычисленных проверочных составных модулей и обратных величин , соответствующих значению составного модуля M_t+1; 7 - четвертый блок памяти, который обеспечивает хранение значений простых модулей m₁, m₂, …, m_s; 8 - первый блок формирования остатка по модулю, который может быть выполнен на основе [5] и обеспечивает представление значений матрицы (2) по каждому из простых модулей (9); 9 - пятый блок памяти, который обеспечивает хранение предвычисленных значений проверочных составных модулей (7); 10 - блок вычисления обратной матрицы, который может быть выполнен на основе [6] и обеспечивает вычисление обратных матриц (11); 11 - шестой блок памяти, который обеспечивает хранение предвычисленных значений обратных величин (8); 12 - второй блок формирования остатка по модулю, который может быть также выполнен на основе [5] и обеспечивает представление значений обратных матрицы по каждому из простых модулей (11); 13 - седьмой блок памяти, который обеспечивает хранение значений матриц (9); 14 - блок умножения матриц, который может быть выполнен на основе устройства [7] и выполняет умножение (12); 15 - восьмой блок памяти, который обеспечивает хранение значений векторов (10); 16 - третий блок формирования остатка по модулю, который может быть также выполнен на основе [5] и обеспечивает представление полученных значений вычисления в блоке умножения матриц 14 по каждому из простых модулей (12); 17 - девятый блок памяти, который обеспечивает хранение значений обратных матриц (11); 18 - блок многоразрядных умножителей, который включает n×s многоразрядных умножителей, обеспечивающих вычисление следующих произведений:

19 - блок многоразрядных сумматоров, который включает n×s многоразрядных сумматоров, обеспечивающих вычисление:

20 - четвертый блок формирования остатка по модулю, который может быть также выполнен на основе [5] и обеспечивает выполнение вычисление остатков по составным проверочным модулям (13); 21 - блок мажоритарных устройств, включающий n мажоритарных устройств, каждое из которых соответственно обеспечивает сравнение значений вычисления переменных СЛАУ, вычисленных по проверочным составным модулям, и выдачу наиболее вероятного результата из (13); 22 - десятый блок памяти, который обеспечивает хранение значений вычисления переменных СЛАУ (4); 23 - шину подачи коэффициентов СЛАУ (2, 3); 24 - шину выдачи значений результатов вычисления переменных СЛАУ (4).

Шина подачи значений коэффициентов СЛАУ 24 является входом устройства и подключена ко входу первого блока памяти 1 и второго блока памяти 3, первый блок выбора максимального числового значения 2, первый и второй входы которого подключены соответственно к выходам первого блока памяти 1 и второго блока памяти 3, выход которого подключен ко второму входу второго блока выбора максимального числового значения 4, первый вход которого подключен к выходу третьего блока памяти 5, а выход подключен к входу дешифратора 6, выход которого подключен к управляющему входу четвертого блока памяти 7, пятого блока памяти 9, шестого блока памяти 11, первый блок формирования остатка по модулю 8, первый и второй входы которого соответственно подключены к выходам первого блока памяти 1 и второго блоков памяти 3, а третий вход подключен к выходу четвертого блока памяти 7, а выход подключен ко входу седьмого блока памяти 13 и восьмого блока памяти 15, блок вычисления обратной матрицы 10, вход которого подключен к выходу седьмого блока памяти 13, а выход подключен ко второму входу второго блока формирования остатка по модулю 12, первый вход которого подключен к выходу четвертого блока памяти 7, а выход подключен ко входу девятого блока памяти 17, блок умножения матриц 14, первый вход которого подключен к выходу восьмого блока памяти 15, а второй вход подключен к выходу девятого блока памяти 17, а выход подключен ко входу третьего блока формирования остатка по модулю 16, второй вход которого подключен к выходу четвертого блока памяти 7, а выход подключен к третьему входу блока многоразрядных умножителей 18, первый вход которого подключен к выходу пятого блока памяти 9, второй вход которого подключен к выходу шестого блока памяти 11, а выход подключен ко входу блока многоразрядных сумматоров 19, выход которого подключен ко второму входу четвертого блока формирования остатка по модулю 20, первый вход которого подключен к выходу пятого блока памяти 9, а выход подключен ко входу блока мажоритарных устройств 21, выход которого подключен ко входу 10-го блока памяти 21, выход которого подключен к шине выдачи значений вычисления переменных СЛАУ 24, являющуюся выходом устройства.

Предлагаемое устройство функционирует следующим образом. В момент времени, соответствующий началу работы устройства в блоки памяти 1 и 2 выполняется запись коэффициентов СЛАУ (1), соответственно в первый блок памяти 1 выполняется запись значений (2) и во второй блок памяти 3 выполняется запись значений (3), далее из блоков памяти 1 и 2 значения коэффициентов поступают на входы первого блока выбора максимального числового значения 2, выполняющего выбор наибольшего числового значения (5), далее выбранное значение (5) поступает на второй вход второго блока выбора максимального числового значения 4, выполняющего выбор первого по порядку большего значения составного модуля M_t из значений поступающих на его первый вход с выхода третьего блока памяти 5, далее значение выбранного составного модуля M_t поступает на вход дешифратора 6, формирующего адрес ячеек памяти находящихся в четвертом блоке памяти 7, пятом блоке памяти 9 и шестом блоке памяти 11, в которых хранятся соответственно значения простых модулей m₁, m₂, …, m_t+1, предвычисленных проверочных составных модулей и обратных величин , соответствующих значению составного модуля M_t+1, далее в первом блоке формирования остатка по модулю 8 выполняется нахождение остатков от значений коэффициентов матриц (2, 3), поступающих на его первый и второй входы соответственно с выходов первого блока памяти 1 и второго блока памяти 3 по простым модулям (9, 10), значения которых поступают на его третий вход с выхода четвертого блока памяти 7, далее модулярные значения матриц (9, 10) поступают соответственно на входы седьмого блока памяти 15 и восьмого блока памяти 17, далее в блоке вычисления обратной матрицы 10 выполняется вычисление значений обратных матриц значениям матриц, поступающих на его вход с выхода седьмого блока памяти 13, которые поступают на второй вход второго блока формирования остатка по модулю 12, выполняющего представление значений обратных матрицы по каждому из простых модулей (11), значения которых поступают на его первый вход с выхода четвертого блока памяти 7, и полученные значения поступают на вход девятого блока памяти 17, далее в блоке умножения матриц 14 выполняется умножение значений модулярных векторов 10, поступающих на его первый вход с выхода восьмого блока памяти 15, на значения модулярных обратных матриц (11), поступающих на его второй вход с выхода девятого блока памяти 17, далее полученные результаты поступают на второй вход третьего блока формирования остатка по модулю 16, выполняющего вычисление значений векторов по простым модулям (12), значения которых поступают на его второй вход с выхода четвертого блока памяти 7, в блоке многоразрядных умножителей 18 выполняется вычисление произведений вида:

далее в блоке многоразрядных сумматоров 19 выполняется вычисление сумм вида:

после чего в четвертом блоке формирования остатка по модулю 20 выполняется вычисление остатков по проверочным составным модулям (13), поступающим на его первый вход с выхода пятого блока памяти 9, далее значения (13) поступают на блок мажоритарных устройств, включающий n мажоритарных устройств, каждое из которых соответственно обеспечивает сравнение значений вычисления переменных СЛАУ по проверочным составным модулям и выдачу наиболее вероятного результата из (13), которые далее поступают на вход десятого блока памяти 22 и далее поступают на вход шины выдачи значений вычисления переменных СЛАУ 24, которая является выходом устройства.

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

Литература

1. SU, №1411776, 1988.

2. SU, №1615738, 1990.

3. Бухштаб А.А. Теория чисел / А.А. Бухштаб. - М.: Просвещение, 1966. - 384 с. (С. 123, Теорема 143).

4. RU, №2262130, 2005.

5. RU, №2368942, 2009.

6. SU, №1211754,1986.

7. SU, №1779180, 1995.