Многоуровневая m-мерная матричная вычислительная структура вертикальной арифметики в.м. таранухи

Изобретение относится к области вычислительной техники, предназначено для параллельного вычисления разрядными срезами m-мерных массивов данных и может быть использовано для решения задач, связанных с обработкой m-мерных массивов данных. Техническим результатом является расширение функциональных возможностей, повышение быстродействия вычисления m-мерных массивов данных посредством образования иерархической многоуровневой матричной структуры. Многоуровневая m-мерная матричная вычислительная структура содержит m-мерные матричные вычислительные структуры с первого по m-й и уровень, образующие иерархическую многоуровневую вычислительную структуру вертикальной арифметики, представляющую регулярную, связанную по вертикали, иерархическую логарифмическую структуру с межуровневыми связями, по горизонтали m-мерные матричные структуры образуют иерархическую матричную структуру, в которой матричные структуры предыдущих уровней, объединенные связями, образуют матричную структуру следующего иерархического уровня многоуровневой m-мерной матричной структуры. 4 з.п. ф-лы, 14 ил.

 

Изобретение относится к области вычислительной техники, предназначено для параллельного вычисления разрядными срезами m-мерных массивов данных и может быть использовано для решения задач, связанных с обработкой m-мерных массивов данных (многомерные задачи матфизики, матстатистики, многомерные импульсные системы автоматического регулирования, многомерные преобразования Фурье, многомерные свертки, многомерные интегралы, многомерные дифференциалы и т.д.).

Известен динамический параллельный процессор для покомпонентного умножения двух векторов (Я.И.Фет. Параллельные процессоры для управляющих систем. - М.: Издательство «Энергоиздат», 1981, с.118, рис.45), состоящий из регистров массива множителей, регистров массива множимых, вертикального арифметического устройства, включающего одноразрядные сумматоры, регистров промежуточных результатов, элементов И.

Признаками аналога, совпадающими с признаками заявляемого изобретения, являются одноразрядные сумматоры, элементы И.

Недостатком является то, что в устройстве невозможно параллельно вычислять m-мерные массивы данных.

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

Известен также, специализированный процессор для вычисления массивов данных разрядными срезами с использованием таблиц хранения частичных результатов (Е.Ф.Очин. Вычислительные системы обработки изобретений. - Л.: Издательство «Энергоатомиздат», 1989, с.74, рис.4.5), содержащий регистры, регистры преобразования кодов, ПЗУ хранения частичных результатов, соответствующих разрядным срезам, мультиплексор адреса, сдвигатель-аккумулятор, содержащий одноразрядные сумматоры, блок управления.

Признаками аналога, совпадающими с существующими признаками заявляемого изобретения, являются одноразрядные сумматоры.

Недостатком является то, что в устройстве невозможно параллельно вычислять разрядными срезами m-мерные массивы данных.

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

Наиболее близким устройством является трехуровневая вычислительная структура вертикальной арифметики (В.М.Тарануха. Теоретические основы и принципы построения вычислительных средств параллельной вертикальной арифметики. Таганрог. Издательство «Таганрог», 1996, с.120-123, рис.23, 24), содержащая преобразователи кодов (узлы одноразрядного суммирования), первого, второго и третьего уровня, матричные умножители первой, второй группы, состоящие из элементов И (условно обозначены элементы И точками на рис.23, 24), при этом входы преобразователей первого уровня соединены с соответствующими группами информационных входов трехуровневой вычислительной структуры; выходы преобразователей первого уровня соединены с первыми входами матричных умножителей первой группы, вторые входы матричных умножителей первой группы соединены со вторыми информационными входами трехуровневой вычислительной структуры, выходы матричных умножителей первой группы соединены со входами соответствующего веса преобразователей кодов второго уровня, выходы преобразователей кодов второго уровня соединены с первыми входами матричных умножителей второй группы, вторые входы матричных умножителей второй группы соединены с третьими информационными входами трехуровневой вычислительной структуры, выходы матричных умножителей второй группы соединены со входами соответствующего веса преобразователей кодов третьего уровня, выходы преобразователей кодов третьего уровня соединены с выходами трехуровневой вычислительной структуры.

Признаками прототипа, совпадающими с существующими признаками заявляемого изобретения, являются узлы одноразрядного суммирования, матричные умножители, состоящие из элементов И.

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

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

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

Для достижения указанного технического результата в многоуровневую m-мерную матричную вычислительную структуру вертикальной арифметики, содержащую узлы одноразрядного суммирования, матричные умножители, состоящие из элементов И, введены m-мерные матричные вычислительные структуры первого, второго, третьего уровня, при этом m-мерные матричные структуры образуют иерархическую многоуровневую вычислительную структуру вертикальной арифметики, представляющую регулярную связанную по вертикали, иерархическую логарифмическую структуру с межуровневыми связями, причем первые входы матричных умножителей в одномерных матричных структурах первого уровня соединены с соответствующими группами информационных входов многоуровневой m-мерной матричной структуры. Вторые входы матричных умножителей одномерных матричных структур от первого до m-го уровня соединены соответственно соответствующим образом со вторыми, третьими, четвертыми и m-ми информационными входами многоуровневой m-мерной матричной вычислительной структуры. При этом равновесные входы (k_i+1) узлов одномерных матричных структур каждого последующего уровня соединены через элементы И матричных умножителей соответственно с выходами соответствующего веса N_i узлов одномерных матричных структур предыдущего уровня по вертикали, k_i=log₂N_i, i∈{i₁, i₂,..., i_m}, no горизонтали иерархическую матричную структуру, в которой матричные структуры предыдущих уровней, объединенные связями, образуют матричную структуру следующего иерархического уровня многоуровневой m-мерной матричной вычислительной структуры.

Кроме того, одномерная матричная вычислительная структура первого уровня содержит N₂ матричные умножители, n₂ группы N₂-входовых (k₁+1) узлов одноразрядного суммирования, k₁=log₂N₁. При этом одни входы N₂ матричных умножителей соединены с соответствующими группами (i₁i₂) информационных входов одномерной матричной структуры, , , вторые входы N₂ матричных умножителей соединены со вторыми входами одномерной матричной структуры. При этом равновесные входы N₂-входовых (k₁+1) узлов первой группы соединены соответственно с выходами выдачи весовых разрядных парных произведений первых вертикальных срезов N₂ матричных умножителей, равновесные входы N₂-входовых (k₁+1) узлов второй группы соединены соответственно с выходами выдачи весовых разрядных парных произведений вторых вертикальных срезов N₂ матричных умножителей и так до n₂ группы. Равновесные входы N₂-входовых (k₁+1) узлов последней n₂ группы соединены соответственно с выходами выдачи весовых разрядных парных произведений последних n₂ вертикальных срезов N₂ матричных умножителей. При этом выходы (k₁+1) узлов суммирования с первой до последней n₂ группы соединены с выходами одномерной матричной структуры.

Кроме того, двухмерная матричная вычислительная структура второго уровня содержит: N₃ одномерные матричные структуры первого уровня, N₃ группы, состоящие из n₂ подгрупп (k₁+1) узлов одномерных матричных структур второго уровня. При этом каждая одномерная матричная структура второго уровня содержит n₃ группы N₃-входовых (k₂+1) узлов одноразрядного суммирования, k₂=log₂N₂, и N₃ группы N₂ матричных умножителей. При этом первые входы N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня соединены с соответствующими группами (i₁i₂i₃) информационных первых входов двухмерной матричной структуры, , вторые входы N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня соединены с соответствующими информационными вторыми входами двухмерной матричной структуры. При этом равновесные входы N₂-входовых (k₁+1) узлов соединены соответственно с выходами N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня. Причем первые входы N₂ матричных умножителей (k₁+1) одномерных матричных структур второго уровня соединены соответственно с выходами соответствующего веса (k₁+1) узлов первой группы в N₃ одномерных матричных структурах первого уровня. При этом вторые входы матричных умножителей одномерных матричных структур второго уровня соединены с соответствующими информационными третьими входами двухмерной матричной структуры. При этом равновесные входы N₃-входовых (k₂+1) узлов третьего уровня соединены соответственно с выходами N₃ матричных умножителей в (k₁+1) одномерных матричных структурах второго уровня. При этом выходы (k₂+1) узлов (k₁+1) одномерных матричных структур второго уровня соединены с выходами двухмерной матричной структуры второго уровня.

Кроме того, трехмерная матричная вычислительная структура третьего уровня содержит: N₄ двухмерные матричные структуры второго уровня, N₄ группы, состоящие из n₃ подгрупп (k₂+1) одномерных матричных структур третьего уровня. Каждая одномерная матричная структура третьего уровня содержит: n₄ группы N₄-входовых (k₃+1) узлов одноразрядного суммирования, k₃=log₂N₃, N₄ матричных умножителей. Каждая одномерная матричная структура первого уровня трехмерной матричной структуры содержит N₄ группы N₃ одномерных матричных структур первого уровня.

При этом первые входы N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структур первого уровня соединены с соответствующими группами (i₁i₂i₃i₄), информационных первых входов трехмерной матричной структуры. Вторые входы N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структур первого уровня трехмерной матричной структуры соединены с соответствующими информационными вторыми входами трехмерной матричной структуры. При этом равновесные входы N₂-входовых (k₁+1) узлов первого уровня соединены соответственно с выходами N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структурах первого уровня. При этом первые входы матричных умножителей одномерных матричных структур второго уровня соединены с выходами соответствующего веса (k₁+1) узлов в N₄ группах N₃ одномерных матричных структурах первого уровня.

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

При этом равновесные входы N₃-входовых (k₂+1) узлов второго уровня соединены соответственно с выходами матричных умножителей в (k₁+1) одномерных матричных структурах второго уровня. Причем первые входы матричных умножителей (k₂+1) одномерных матричных структур третьего уровня соединены соответственно с выходами соответствующего веса (k₂+1) узлов в N₄ двухмерных матричных структурах второго уровня. Причем вторые входы матричных умножителей одномерных матричных структур третьего уровня соединены соответственно с соответствующими информационными четвертыми входами трехмерной матричной структуры.

При этом равновесные входы N₄-входовых (k₃+1) узлов третьего уровня соединены соответственно с выходами матричных умножителей в (k₂+1) одномерных матричных структурах третьего уровня. При этом, выходы (k₃+1) узлов (k₂+1) одномерных матричных структур третьего уровня соединены с выходами трехмерной матричной структуры.

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

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

В основу работы многоуровневой m-мерной матричной вычислительной структуры положен универсальный алгоритм параллельного вычисления суммы произведений М чисел k-ичными цифрами сжатых разрядных срезов:

где - весовые разряды р-тых сомножителей,

- весовые разрядные произведения р-тых сомножителей;

- размер массива равновесных разрядных произведений, представленного в виде подматриц размерностей N₁, N₂,... N_m m-мерной матрицы;

- размер (число разрядов) р-тых сомножителей;

- суммы равновесных разрядных произведений - цифры в k-ичных системах счисления с основанием

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

Здесь первые сомножители представлены в виде цифр Z₁P₁, Z₁∈{С₀С₁...C_k1}, представленных в k₁-ичной системе счисления с основанием , k₁=log₂N₁, это обусловлено организацией параллельных вычислений произведений М чисел (исключается макрооперация группового посрезного суммирования,

На первом уровне параллельно вычисляются суммы равновесных разрядных парных произведений, в виде цифр Z₂P₂:

представленные в k₁₂-ичной системе счисления с основанием k₂=log₂N₂.

При p=3 реализуется макрооперация вычисления суммы произведений 3-х чисел в виде

где k₃=log₂N₃.

На втором уровне параллельно вычисляются суммы равновесных разрядных произведений 3-х чисел, в виде цифр Z₃P₃:

представленных в k₁₂₃-ичной системе счисления с основанием

При р=4 реализуется макрооперация вычисления суммы произведений 4-х чисел, в виде

где k₄=log₂N₄.

На третьем уровне параллельно вычисляются суммы равновесных разрядных произведений 4-х чисел, в виде цифр Z₄P₄

представленные в k₁₂₃₄-ичной системе счисления с основанием

и т.д.

Сущность предлагаемого изобретения поясняется чертежами, где на фиг.1 изображена одномерная матричная структура первого уровня, на фиг.2 - матричный умножитель, на фиг.3 - одномерная матричная структура с наращиваемой архитектурой по горизонтали, т.е. наращивается по степени распараллеливания, на фиг.4 - двухмерная матричная структура второго уровня, на фиг.5 - первая одномерная матричная структура второго уровня первой группы первой подгруппы (5₁₁₁), на фиг.6 - (k₁+1) одномерная матричная структура второго уровня первой группы первой подгруппы на фиг.7 - первая одномерная матричная структура второго уровня N₃ группы n₂ подгруппы на фиг.8 - (k₁+1) одномерная матричная структура второго уровня N₃ группы n₂ подгруппы на фиг.9 - трехмерная матричная структура третьего уровня, на фиг.10 - первая одномерная матричная структура третьего уровня первой группы первой подгруппы (8₁₁₁), на фиг.11 - (k₁+1) одномерная матричная структура третьего уровня первой группы первой подгруппы на фиг.12 - первая одномерная матричная структура третьего уровня N₄ группы n₃ подгруппы на фиг.13 - (k₁+1) одномерная матричная структура третьего уровня N₄ группы n₃ подгруппы на фиг.14 - узел одноразрядного суммирования.

Одномерная матричная структура первого уровня (фиг.1) содержит: N₂ матричных умножителей n₂ группы N₂-входовых (k₁+1) узлов одноразрядного суммирования k₁=log₂N₁. При этом первые входы матричных умножителей соединены с соответствующими группами (i₁i₂) первых информационных входов одномерной матричной структуры первого уровня, , , вторые входы матричных умножителей соединены с соответствующими информационными вторыми входами одномерной матричной структуры. При этом равновесные входы N₂-входовых (k₁+1) узлов первой группы соединены соответственно с выходами выдачи весовых разрядных произведений первых вертикальных срезов N₂ матричных умножителей равновесные входы N₂-входовых (k₁+1) узлов второй группы соединены соответственно с выходами выдачи весовых разрядных произведений вторых вертикальных срезов N₂ матричных умножителей и так до n₂ группы; равновесные N₂-входы (k₁+1) узлов последней n₂ группы соединены соответственно с выходами выдачи весовых разрядных произведений n₂ вертикальных срезов N₂ матричных умножителей При этом выходы (k₁+1) узлов суммирования с первой до последней n₂ группы соединены соответственно с выходами

одномерной матричной структуры.

Степень распараллеливания одномерной матричной структуры составляет N₁N₂.

Степень сжатия одномерной матричной структуры составляет (1+k₂), k₂=log₂N₂.

Матричный умножитель (фиг.2) содержит:

Элементы И₁₁, И₂₁,..., И_N1 первой группы, элементы И₁₂, И₂₂,..., И_N2 второй группы, элементы n-ой группы. При этом первые входы первых элементов И₁₁, И₁₂,..., И_1n от первой до последней n группы, первые входы вторых элементов И₂₁, И₂₂,..., И_2n от первой до последней n группы и первые входы N-x элементов от первой до последней n группы соединены с соответствующими группами (i₁i₂i₃...) информационных первых входов , , матричного умножителя. Вторые входы элементов И₁₁, И₂₁,..., И_N1 от первого до N-го элемента в первой группе, вторые входы элементов И₁₂, И₂₂,..., И_N2 от первого до N-го элемента во второй группе и вторые входы элементов от первого до последнего N-го элемента в n-ой группе соединены с соответствующими информационными вторыми входами 2₁,...,2_ni матричного умножителя, i=2, 3,..., m, выходы элементов И₁₁, И₂₁,..., И_N1 первой группы соединены соответственно с первыми выходами выдачи весовых разрядных парных произведений первого среза матричного умножителя, выходы элементов последней n группы соединены соответственно с последними n выходами выдачи весовых разрядных парных произведений последнего среза матричного умножителя.

Одномерная матричная структура первого уровня наращивается по степени распараллеливания (фиг.3), в том числе:

- для двухмерной матричной структуры наращиваются N₃ одномерные матричные структуры . При этом первые входы матричных умножителей первого уровня соединены с соответствующими группами (i₁i₂i₃) информационных первых входов: двухмерной матричной структуры.

- для трехмерной матричной структуры наращиваются N₄ двухмерные матричные структуры, условно обозначенные на фиг.3 как (следует читать: как , или

При этом первые входы матричных умножителей (условно обозначены матричные умножители на фиг.3 как следует читать: как или ) соединены с соответствующими группами (i₁i₂i₃i₄) информационных первых входов, трехмерной матричной структуры, , условно обозначенных на фиг.3, как

(следует читать: как или

Двухмерная матричная структура второго уровня (фиг.4) содержит: N₃ одномерные матричные структуры первого уровня; N₃ группы, состоящие из n₂ подгрупп, (k₁+1) одномерных матричных структур второго уровня первой группы первой подгруппы; (k₁+1) одномерных матричных структур второго уровня последней N₃ группы последней n₂ подгруппы. Каждая одномерная матричная структура второго уровня (фиг.5-8) содержит n₃ группы N₃-входовых (k₂+1) узлов одноразрядного суммирования, N₃ матричных умножителей .

Каждая одномерная матричная структура первого уровня (фиг.3) двухмерной матричной структуры содержит N₃ группы N₂ матричных умножителей, обозначенных на фиг.3 как .

При этом первые входы N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня соединены с соответствующими группами (i₁i₂i₃) информационными первыми входами двухмерной матричной структуры второго уровня. Вторые входы N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня (фиг.3, 4) соединены с соответствующими информационными вторыми входами двухмерной матричной структуры (фиг.3, 4).

Равновесные входы N₂-входовых (k₁+1) узлов от первой до последней n₂ группы (фиг.3) соединены соответственно с выходами выдачи разрядных произведений соответствующего веса N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня (фиг.3, 4).

Первые входы и матричных умножителей (фиг.5, 6) (k₁+1) одномерных матричных структур второго уровня (фиг.4) первых групп первых подгрупп соединены соответственно с выходами соответствующего веса и (k₁+1) узлов первой группы в N₃ одномерных матричных структурах первого уровня (фиг.3, 4). Первые входы и матричных умножителей (фиг.7, 8) (k₁+1) одномерных матричных структур второго уровня (фиг.4) последних N₃ групп последних n₂ подгрупп соединены соответственно с выходами соответствующего веса и (k₁+1) узлов последней n₂ группы в N₃ одномерных матричных структурах первого уровня (фиг.3, 4).

Вторые входы матричных умножителей (фиг.5-8) одномерных матричных умножителей второго уровня (фиг.4) соединены с соответствующими информационными третьими входами двухмерной матричной структуры (фиг.4).

Равновесные входы

N₃-входовых (k₂+1) узлов от первой до последней n₃ группы (фиг.5-8) соединены соответственно с выходами выдачи разрядных произведений трех чисел соответствующего веса, N₃ матричных умножителей в (k₁+1) одномерных матричных структурах второго уровня (фиг.4) от первой до последней N₃ группы.

Выходы

(k₂+1) узлов узлов от первых до последних n₃ групп (фиг.5, 6) (k₁+1) одномерных матричных структур второго уровня (фиг.4), а также выходы

(k₂+1) узлов от первой до последней n₃ группы (фиг.7, 8) (k₁+1) одномерных матричных структур второго уровня последней N₃ группы последней n₂ подгруппы (фиг.4) соединены с выходами двухмерной матричной структуры второго уровня.

Степень распараллеливания двухмерной матричной структуры составляет N₁N₂N₃.

Степень сжатия двухмерной матричной структуры составляет (1+k₂)(1+k₃), k₃=log₂N₃.

Трехмерная матричная структура третьего уровня (фиг.9) содержит: N₄ двухмерные матричные структуры второго уровня; N₄ группы, состоящие из n₃ подгрупп (k₂+1) одномерных матричных структур третьего уровня первой группы, первой подгруппы; (k₂+1) одномерных матричных структур третьего уровня последней N₄ группы последней n₃ подгруппы.

Каждая одномерная матричная структура третьего уровня (фиг.10, 11) содержит: n₄ группы N₄-входовых (k₃+1) узлов одноразрядного суммирования, N₄ матричных умножителей

Каждая одномерная матричная структура первого уровня (фиг.3) трехмерной матричной структуры содержит N₄ группы N₃ подгруппы N₂ матричных умножителей, обозначенных на фиг.3 как (следует читать: как или

При этом первые входы N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структурах первого уровня соединены с соответствующими группами (i₁i₂i₃i₄), , информационными первыми входами, обозначенных на фиг.3 как

(следует читать: как или трехмерной матричной структуры.

Вторые входы N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структурах первого уровня (фиг.3, 4) соединены с соответствующими информационными вторыми входами трехмерной матричной структуры. Равновесные входы (фиг.3) N₂-входовых (k₁+1) узлов первого уровня от первой до последней n₂ группы соединены соответственно с выходами соответствующего веса N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структурах первого уровня.

Первые входы (фиг.5, 6) матричных умножителей одномерных матричных структур второго уровня (фиг.4) первых групп первых подгрупп соединены соответственно с выходами соответствующего веса (фиг.3) (k₁+1) узлов первой группы в N₄ группах N₃ одномерных матричных структурах первого уровня, условно обозначенных на фиг.3 как (следует читать: как или

Первые входы матричных умножителей (фиг.7, 8) (k₁+1) одномерных матричных структурах второго уровня (фиг.4) последних N₃ групп последних n₂ подгрупп соединены соответственно с выходами соответствующего веса (k₁+1) узлов последней n₂ группы в N₄ группах N₃ одномерных матричных структурах первого уровня (фиг.3).

Вторые входы матричных умножителей (фиг.5-8) одномерных матричных структур второго уровня (фиг.4) соединены с соответствующими информационными третьими входами трехмерной матричной структуры.

Равновесные входы

(фиг.5-8) N₃-входовых (k₂+1) узлов от первой до последней n₃ группы соединены соответственно с выходами соответствующего веса матричных умножителей в (k₁+1) одномерных матричных структурах второго уровня (фиг.4) от первой до последней N₃ группы.

Первые входы (фиг.10, 11) матричных умножителей (k₂+1) одномерных матричных структур третьего уровня (фиг.9) первых групп первых подгрупп соединены соответственно с выходами соответствующего веса (фиг.5) (k₂+1) узлов первой группы в N₄ двухмерных матричных структурах (фиг.9) второго уровня.

Первые входы

(фиг.12, 13) матричных умножителей (k₂+1) одномерных матричных структур третьего уровня (фиг.9) последних N₄ групп последних n₃ подгрупп соединены соответственно с выходами соответствующего веса

(фиг.8) (k₂+1) узлов последней n₃ группы в N₄ двухмерных матричных структурах (фиг.9) второго уровня.

Вторые входы матричных умножителей (фиг.10-13) (k₂+1) одномерных матричных структур третьего уровня (фиг.9) соединены с соответствующими информационными четвертыми входами трехмерной матричной структуры (фиг.9).

Равновесные входы N₄-входовых (k₃+1) узлов (фиг.10-13) от первых до последних n₄ групп соединены соответственно с выходами матричных умножителей в (k₂+1) одномерных матричных структурах третьего уровня (фиг.9) от первой до последней N₄ группы последней n₃ подгруппы.

Выходы

(k₃+1) узлов от первых до последних n₄ групп (фиг.10, 11) (k₂+1) одномерных матричных структур третьего уровня первых групп первых подгрупп (фиг.9), а также выходы

(k₃+1) узлов от первых до последних n₄ групп (фиг.12, 13) (k₂+1) одномерных матричных структур третьего уровня последних N₄ групп последних n₃ подгрупп (фиг.9) соединены с выходами трехмерной матричной структуры.

Степень распараллеливания трехмерной матричной структуры составляет N₁N₂N₃N₄.

Степень сжатия трехмерной матричной структуры составляет (l+k₂)(1+k₃)(1+k₄), k₄=log₂N₄.

Узел одноразрядного суммирования (фиг.14) состоит из четырехвходовых элементов суммирования 10, полусумматора 11, элемента ИЛИ 12, имеет входы 2^l, приема равновесных разрядов, выходы 2^l(С₀), 2^l+1(С₁), 2^l+2(C₂), 2^l+3(С₃), 2^l+4(C₄) выдачи результата вычисления разрядных сумм.

Узлы одноразрядного суммирования описаны (патент SU 1679483 A1, кл. G 06 F 7/50, 1995) или устройства для преобразования двоичного равновесного кода в позиционный код (Авт. свид. 1557684, БИ №14, 1990) с различным числом входов:

16-входовой одноразрядный сумматор (преобразователь кодов);

256-входовой одноразрядный сумматор (преобразователь кодов);

1024-входовой одноразрядный сумматор (преобразователь кодов).

Принцип работы многоуровневой m-мерной вычислительной структуры вертикальной арифметики поясним на примере двухмерной матричной структуры. Пусть на первые входы матричных умножителей (фиг.3, 4) двухмерной матричной структуры поступают параллельными кодами i₁-сомножители в виде k₁-ичных цифр , на вторые входы матричных умножителей поступают параллельными кодами i₂-сомножители

При этом на первом уровне в каждом из матричных умножителей двухмерной матричной структуры (фиг.3) умножаются весовые разряды k₁-ичных цифр на вектор-столбец весовых разрядов i₂-сомножителей, в соответствии с выражением

Согласно выражению (1) элементами И₁₁, И₂₁,..., И_N1 (фиг.2) (условно обозначены элементы И₁₁, И₂₁,..., И_N1 точками на фиг.1, 3) в каждом из матричных умножителей (N₃ группы N₂ матричных умножителя) двухмерной матричной структуры параллельно вычисляются на первом уровне весовые разрядные парные произведения в первых вертикальных срезах, в виде

Элементами И₁₂,И₂₂,...,И_N2 (фиг.1, 2, 3) во вторых вертикальных срезах в каждом из матричных умножителей двухмерной матричной структуры параллельно вычисляются весовые разрядные парные произведения, в виде

и так до последних n₂ вертикальных срезов.

Элементами (фиг.2, 3) в последних n₂ вертикальных срезах (при i=2) в каждом из матричных умножителей к двухмерной матричной структуры параллельно вычисляются весовые разрядные парные произведения, в виде

При этом в (k₁+1) узлах одноразрядного суммирования первой группы в каждой из одномерных матричных структур первого уровня двухмерной матричной структуры (фиг.1, 3) параллельно вычисляются суммы равновесных разрядных парных произведений первых вертикальных срезов N₂ матричных умножителей в N₃ группах в виде

...

где

Одновременно в (k₁+1) узлах одноразрядного суммирования (фиг.1, 3) второй группы на первом уровне параллельно вычисляются суммы равновесных разрядных парных произведений вторых вертикальных срезов N₂ матричных умножителей в N₃ группах в виде

и так до последней n₂ группы.

В (k₁+1) узлах одноразрядного суммирования (фиг.1, 3) последней n₂ группы на первом уровне параллельно вычисляются суммы равновесных разрядных парных произведений n₂ вертикальных срезов N₂ матричных умножителей в N₃ группах в виде

Таким образом, в (k₁+1) узлах одноразрядного суммирования (фиг.1, 3) от первой до последней группы на первом уровне параллельно вычисляются суммы равновесных разрядных парных произведений в каждой из одномерных матричных структур (фиг.1, 3, 4) двухмерной матричной структуры, в виде цифр Z₂P₂:

представленные в k₁₂-ичной системе счисления с основанием , k₂=log₂N₂.

Вычисление в узлах одноразрядного суммирования (фиг.1, 3) разрядные суммы являются элементами блочно-диагональных матриц k₁₂-ичных цифр, которые параллельно поступают из выходов одномерных матричных структур первого уровня (фиг.3, 4) на первые входы матричных умножителей (фиг.5-8) одномерных матричных структур второго уровня (фиг.4) соответственно.

На вторые входы (фиг.5-8) матричных умножителей параллельно поступают i₃-сомножители .

Рассмотрим принцип параллельных вычислений одномерных матричных структур (фиг.4) на втором уровне. В частности, на первые входы N₃ матричных умножителей (фиг.5) одномерной матричной структуры 5₁₁₁ второго уровня (фиг.4) параллельно поступают разрядные суммы k₁₂-ичных цифр из выходов узлов 4₁₁ (фиг.3, 4) N₃ одномерных матричных структур первого уровня, на вторые входы матричных умножителей (фиг.5) параллельно поступают i₃-сомножители .

При этом в N₃ матричных умножителях (фиг.5) одномерных матричных структур второго уровня 5₁₁₁ (фиг.4) параллельно умножаются разрядные суммы k₁₂-ичных цифр на вектор-столбец весовых разрядов i₃-сомножителей, в соответствии с выражением

При этом в (k₁+1) узлах одноразрядного суммирования (фиг.5) первой группы на втором уровне параллельно вычисляются суммы равновесных разрядных произведений трех чисел первых вертикальных срезов N₃ матричных умножителей , в виде

Одновременно в (k₁+1) узлах одноразрядного суммирования (фиг.5) второй группы на втором уровне параллельно вычисляются суммы равновесных разрядных произведений трех чисел вторых вертикальных срезов N₃ матричных умножителей в виде

и так до последней n₃ группы.

В (k₂+1) узлах одноразрядного суммирования (фиг.5) последней n₃ группы на втором уровне параллельно вычисляются суммы равновесных разрядных произведений трех чисел последних n₃ вертикальных срезов N₃ матричных умножителей , в виде

Таким образом, в (k₂+1) узлах одноразрядного суммирования (фиг.5) , от первой до последней n₃ группы первой одномерной матричной структуры второго уровня 5₁₁₁ (фиг.4) параллельно вычисляются суммы равновесных разрядных произведений и выдаются на выходы

в виде цифр

Аналогично осуществляется организация параллельного вычисления в (k₁+1) одномерной матричной структуре второго уровня (фиг.4).

При этом на первые входы матричных умножителей (фиг.6) одномерной матричной структуры второго уровня (фиг.4) параллельно поступают разрядные суммы k₁₂-ичных цифр из выходов узлов (фиг.3, 4) N₃ одномерных матричных структур первого уровня, на вторые входы матричных умножителей (фиг.6) параллельно поступают i₃-сомножители .

В N₃ матричных умножителях (фиг.6) одномерных матричных структур второго уровня (фиг.4, 6) параллельно умножаются разрядные суммы k₁₂-ичных цифр на вектор-столбец весовых разрядов i₃-сомножителей, в соответствии с выражением

При этом в (k₂+1) узлах одноразрядного суммирования (фиг.6) первой группы на втором параллельно вычисляются суммы равновесных разрядных произведений трех чисел первых вертикальных срезов N₃ матричных умножителей , в виде

и так до последней n₃ группы.

Одновременно в (k₂+1) узлах одноразрядного суммирования (фиг.6) последней n₃ группы на втором уровне параллельно вычисляются суммы равновесных разрядных произведений трех чисел последних n₃ вертикальных срезов N₃ матричных умножителей в виде

Таким образом, в (k₂+1) узлах одноразрядного суммирования (фиг.6) от первой до последней n₃ группы одномерной матричной структуры второго уровня (фиг.4) параллельно вычисляются суммы равновесных разрядных произведений трех чисел N₃ матричных умножителей и выдаются на выходы

в виде цифр

и так до последней одномерной матричной структуры второго уровня. В последней одномерной матричной структуре второго уровня (фиг.4) на первые входы N₃ матричных умножителей (фиг.8) параллельно поступают разрядные суммы k₁₂-ичных цифр из выходов узлов (фиг.3) N₃ одномерных матричных структур (фиг.3, 4) первого уровня, на вторые входы матричных умножителей параллельно поступают i₃-сомножители .

При этом в N₃ матричных умножителях (фиг.8) одномерной матричной структуры второго уровня (фиг.4, 8) параллельно умножаются разрядные суммы k₁₂-ичных цифр на вектор-столбец весовых разрядов i₃-сомножителей, в соответствии с выражением:

При этом в (k₂+1) узлах одноразрядного суммирования (фиг.8) первой группы на втором уровне параллельно вычисляются суммы равновесных разрядных произведений трех чисел первых вертикальных срезов N₃ матричных умножителей в виде

и так до последней n₃ группы.

В (k₂+1) узлах одноразрядного суммирования , (фиг.8) последней n₃ группы на втором уровне параллельно вычисляются суммы равновесных разрядных произведений трех чисел последних n₃ вертикальных срезов N₃ матричных умножителей в виде:

При этом в (k₂+1) узлах одноразрядного суммирования (фиг.8) от первой до последней n₃ группы одномерной матричной структуры второго уровня (фиг.4) параллельно вычисляются суммы равновесных разрядных произведений трех чисел N₃ матричных умножителей и выдаются на выходы

в виде цифр

Таким образом, в (k₁+1) одномерных матричных структурах второго уровня (фиг.4) от первой до последней N₃ группы параллельно вычисляются суммы равновесных разрядных произведений трех чисел и выдаются на выходы

в виде цифр Z₃P₃:

представленных в k₁₂₃-ичной системе счисления с основанием

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

Введение в устройство новых элементов - m-мерных матричных структур первого, второго, третьего уровней, соединенных соответствующим образом, позволяет создать сверхвысокопроизводительные вычислители нового поколения с регулярной наращиваемой структурой, ориентированных на современную микроэлектронную технологию СБИС или ПЛИС для параллельной обработки m-мерных массивов, что позволяет:

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

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

- расширить функциональные возможности вычислительной структуры вертикальной арифметики за счет регулярной наращиваемой многоуровневой матричной структуры.

1. Многоуровневая m-мерная матричная вычислительная структура вертикальной арифметики, содержащая m-мерные матричные вычислительные структуры с первого по m-ый уровень, при этом указанные матричные вычислительные структуры образуют иерархическую многоуровневую матричную вычислительную структуру вертикальной арифметики, представляющую регулярную, связанную по вертикали, иерархическую логарифмическую структуру с межуровневыми связями, причем первые входы матричных умножителей в одномерных матричных структурах первого уровня соединены с соответствующими группами информационных входов многоуровневой m-мерной матричной структуры, вторые входы матричных умножителей одномерных матричных структур с первого до m-го уровня соединены соответствующим образом с информационными входами со второго по (m+1)-ый многоуровневой m-мерной матричной вычислительной структуры, при этом равновесные входы (k_i+1) узлов одномерных матричных структур каждого последующего уровня соединены через элементы И матричных умножителей, входящих в состав одномерных матричных структур, соответственно с выходами соответствующего веса N_i узлов одномерных матричных структур предыдущего уровня по вертикали, k_i=log₂N_i, i∈{i₁i₂...i_m}, no горизонтали m-мерные матричные структуры образуют иерархическую матричную структуру, в которой матричные структуры предыдущих уровней, объединенные связями, образуют матричную структуру следующего иерархического уровня многоуровневой m-мерной матричной вычислительной структуры.

2. Многоуровневая m-мерная матричная вычислительная структура вертикальной арифметики по п.1, отличающаяся тем, что одномерная матричная вычислительная структура первого уровня содержит N₂ матричных умножителей, n₂ группы N₂-входовых (k₁+1) узлов одноразрядного суммирования, k₁=log₂N₁, при этом одни входы N₂ матричных умножителей соединены с соответствующими группами (i₁i₂) информационных входов одномерной матричной структуры, , , вторые входы N₂ матричных умножителей соединены со вторыми входами одномерной матричной структуры, при этом равновесные входы N₂-входовых (k₁+1) узлов первой группы соединены соответственно с выходами выдачи весовых разрядных парных произведений первых вертикальных срезов N₂ матричных умножителей, равновесные входы N₂-входовых (k₁+1) узлов второй группы соединены соответственно с выходами выдачи весовых разрядных парных произведений вторых вертикальных срезов N₂ матричных умножителей, и так до n₂ группы, равновесные входы N₂-входовых (k₁+1) узлов последней n₂ группы соединены соответственно с выходами выдачи весовых разрядных парных произведений последних n₂ вертикальных срезов N₂ матричных умножителей, при этом выходы (k₁+1) узлов суммирования с первой до последней n₂ группы соединены с выходами одномерной матричной структуры.

3. Многоуровневая m-мерная матричная вычислительная структура вертикальной арифметики по п.1, отличающаяся тем, что двумерная матричная вычислительная структура второго уровня содержит N₃ одномерные матричные структуры первого уровня, N₃ группы, состоящие из n₂ подгрупп (k_i+1) узлов одномерных матричных структур второго уровня, при этом каждая одномерная матричная структура второго уровня содержит n₃ группы N₃-входовых (k₂+1) узлов одноразрядного суммирования, k₂=log₂N₂, и N₃ группы N₂ матричных умножителей, при этом первые входы N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня соединены с соответствующими группами (i₁i₂i₃) информационных первых входов двумерной матричной структуры, , вторые входы N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня соединены с соответствующими информационными вторыми входами двумерной матричной структуры, при этом равновесные входы N₂-входовых (k₁+1) узлов соединены соответственно с выходами N₂ матричных умножителей в N₃ одномерных матричных структурах первого уровня, причем первые входы N₂ матричных умножителей (k₁+1) одномерных матричных структур второго уровня соединены соответственно с выходами соответствующего веса (k₁+1) узлов первой группы в N₃ одномерных матричных структурах первого уровня, при этом вторые входы матричных умножителей одномерных матричных структур второго уровня соединены с соответствующими информационными третьими входами двумерной матричной структуры, при этом равновесные входы N₃-входовых (k₂+1) узлов третьего уровня соединены соответственно с выходами N₃ матричных умножителей в (k₁+1) одномерных матричных структурах второго уровня, при этом выходы (k₂+1) узлов (k₁+1) одномерных матричных структур второго уровня соединены с выходами двумерной матричной структуры второго уровня.

4. Многоуровневая m-мерная матричная вычислительная структура вертикальной арифметики по п.1, отличающаяся тем, что трехмерная матричная вычислительная структура третьего уровня содержит N₄ двумерные матричные структуры второго уровня, N₄ группы, состоящие из n₃ подгрупп (k₂+1) одномерных матричных структур третьего уровня, каждая одномерная матричная структура третьего уровня содержит n₄ группы N₄-входовых (k₃+1) узлов одноразрядного суммирования, k₃=log₂N₃, N₄ матричные умножители, каждая одномерная матричная структура первого уровня трехмерной матричной структуры содержит N₄ группы N₃ одномерных матричных структур первого уровня, при этом первые входы N₂ матричных умножителей в N₄ группах N₃, одномерных матричных структурах первого уровня соединены с соответствующими группами (i₁i₂i₃i₄), информационных первых входов трехмерной матричной структуры, вторые входы N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структур первого уровня трехмерной матричной структуры соединены с соответствующими информационными вторыми входами трехмерной матричной структуры, при этом равновесные входы N₂-входовых (k₁+1) узлов первого уровня соединены соответственно с выходами N₂ матричных умножителей в N₄ группах N₃ одномерных матричных структурах первого уровня, при этом первые входы матричных умножителей одномерных матричных структур второго уровня соединены с выходами соответствующего веса (k₁+1) узлов в N₄ группах N₃ одномерных матричных структурах первого уровня, причем вторые входы матричных умножителей одномерных матричных структур второго уровня соединены с соответствующими информационными третьими входами трехмерной матричной структуры, при этом равновесные входы N₃-входовых (k₂+1) узлов второго уровня соединены соответственно с выходами матричных умножителей в (k₁+1) одномерных матричных структурах второго уровня, причем первые входы матричных умножителей (k₂+1) одномерных матричных структур третьего уровня соединены соответственно с выходами соответствующего веса (k₂+1) узлов в N₄ двумерных матричных структурах второго уровня, причем вторые входы матричных умножителей одномерных матричных структур третьего уровня соединены соответственно с соответствующими информационными четвертыми входами трехмерной матричной структуры, при этом равновесные входы N₄-входовых (k₃+1) узлов третьего уровня соединены соответственно с выходами матричных умножителей в (k₂+1) одномерных матричных структурах третьего уровня, при этом выходы (k₃+1) узлов (k₁+1) одномерных матричных структур третьего уровня соединены с выходами трехмерной матричной структуры.

5. Многоуровневая m-мерная матричная вычислительная структура вертикальной арифметики по п.1, отличающаяся тем, что матричный умножитель содержит n групп N элементов И, при этом первые входы первых элементов И от первой до последней n группы и первые входы последних N-ых элементов И от первой до последней n группы соединены с соответствующими группами информационных первых входов матричного умножителя, вторые входы элементов И от первого до N-го элемента в первой группе и вторые входы элементов И от первого до N-го элемента в n-ой группе соединены с соответствующими вторыми информационными входами матричного умножителя, выходы элементов И первой группы соединены соответственно с выходами выдачи весовых разрядных парных произведений первого среза матричного умножителя, выходы элементов И последней n-ой группы соединены соответственно с выходами выдачи весовых разрядных парных произведений n-го среза матричного умножителя.