КРОСС-КЛАСТЕРНАЯ КОММУТАЦИОННАЯ МАТРИЦА Российский патент 2011 года по МПК G06F7/00 

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

Известно устройство для осуществления перестановок с использованием команд, основанное на сети (коммутационной матрице) «butterfly» (см. патент US №6922472, МПК H04L 9/34).

Используя данное устройство, можно осуществлять кросс-кластерные перестановки входных данных, однако управление данным устройством осуществляется программно, что существенно увеличивает время обработки при частом изменении управляющих кодов. Под кросс-кластерными перестановками понимается преобразование перестановки элементов входных строк данных, при котором строки входных и выходных данных разбиваются в порядке следования на 2^u кластеров равного размера. Рассматриваются только перестановки, при которых элементы из одних входных кластеров попадают в другие выходные. Перестановки внутри кластеров не представляют интереса. Кросс-кластерная коммутационная матрица одновременно соединяет входы и выходы, принадлежащие различным кластерам. Под соединением входа и выхода или выхода и входа понимается условие, при котором если подать сигнал на вход, соединенный с выходом, или выход, соединенный с входом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал и, наоборот, если подать сигнал на выход, на входе через некоторую временную задержку, обусловленную временем распространения сигнала, появится выходной сигнал. При подаче на входы кросс-кластерной коммутационной матрицы сигналов на выходах образуется кросс-кластерная перестановка сигналов.

Известно устройство для осуществления перестановок с использованием команд, основанных на базе сетей омега (omega) и флип (flip) (см. патент US №6952478, МПК G06F 7/76; G06F 9/30). Предложены инструкции для осуществления перестановок, которые могут использоваться в программном обеспечении, выполненном в программируемом процессоре. Инструкции для осуществления перестановок основаны на сети омега-флип, включающей, по крайней мере, два уровня, каждый из которых может выполнить функцию или сети омега или флип. Начальная последовательность битов от исходного регистра преобразуется в промежуточные последовательности битов. Каждая промежуточная последовательность битов является входной для последующей инструкции перестановки. Инструкции перестановки определены для того, чтобы переставить начальную исходную последовательность битов в одну или более промежуточных последовательностей битов, пока не будет получена требуемая перестановка. Промежуточные последовательности битов определены битами конфигурации. Инструкции перестановки образуют последовательность инструкций перестановки, состоящую, по крайней мере, из одной инструкции. Последовательность инструкций перестановки максимального размера составляет 21r/m инструкций перестановки, где r - число переставляемых k-битных элементов, и m - число уровней сети, задействованных в одной инструкции. Инструкции перестановки могут использоваться, чтобы переставить k-битные элементы, упакованные в n-битное слово, где k может быть 1, 2…, n, и k·r=n.

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

Наиболее близким к заявляемому решению является коммутационная сеть (матрица) (см. патент US №5175539, МПК H04J 3/00).

Коммутационная сеть предназначена для избирательного одновременного соединения каждого из n входов с одним из n выходов. Она имеет входную часть, содержащую входы и имеющую, по крайней мере, k-1 (k=log₂n) последовательно соединенных уровней k-уровневой сети baseline, n выходов и выходную часть, в которой n входов соединены с n выходами входной части, включающую k-уровневую сеть baseline и n выходов, которые образуют выходы коммутационной сети.

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

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

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

Поставленная задача достигается тем, что в выходной части предлагаемого устройства используется k-u уровней преобразования, а во входной части k-1 уровень любой сети баньян-типа с минимальным количеством переключающих логических элементов (баньян переключателей 2×2), где k=log₂n, где n - число входов и выходов матрицы, u - неотрицательное целое число, меньшее k.

Согласно предлагаемому решению кросс-кластерная коммутационная матрица, предназначенная для одновременного соединения каждого из входов любого входного кластера с одним выходом любого выходного кластера, имеет n=2^k входов данных, разделенных по порядку номеров на 2^u кластеров, где u<k - неотрицательное целое число, n=2^k выходов данных, разделенных по порядку номеров на 2^u кластеров, входы управляющих кодов, при этом матрица состоит из входной и выходной частей, которые состоят из переключателей, имеющих 2 входа, 2 выхода и вход управляющего кода, расположенных по уровням - столбцам и линиям - строкам, причем входы управляющих кодов кросс-кластерной коммутационной матрицы образованы входами кодов переключателей, входы данных матрицы образованы входами переключателей первого уровня входной части матрицы, выходы данных матрицы образованы выходами переключателей последнего уровня, выходы переключателей предыдущего уровня соединены со входами переключателей следующего уровня, под соединением понимается условие, при котором если подать сигнал на вход, соединенный с выходом, или выход, соединенный с входом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал, и, наоборот, если подать сигнал на выход, на входе через некоторую временную задержку, обусловленную временем распространения сигнала, появится выходной сигнал.

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

Переключатели, составляющие входную часть, расположены в следующем порядке: по n/2-линиям - строкам и k-1 уровням - столбцам.

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

Один выход каждого переключателя, стоящего на линии i и уровне m входной или выходной части матрицы, соединен с одним входом переключателя, стоящего на следующем уровне m+1 и на линии h, причем ,

а второй выход каждого переключателя, стоящего на линии i и уровне m входной или выходной части матрицы, соединен с одним входом переключателя, стоящего на следующем уровне m+1 и на линии р, причем , при этом каждый вход каждого переключателя уровня m+1 соединен с одним выходом переключателя предыдущего уровня m, где int - функция выделения целой части, (j+2^k-m-1)modn - операция вычисления остатка от частного .

Переключатели любого уровня входной части матрицы разбиты на 2^m-1 групп по 2^k-m+1 переключателей, номер группы d_m определяется выражением

где i - номер линии, m - номер уровня переключателя, входящего в группу с номером d_m, при этом один из переключателей уровня m_m, входящих в группу с одинаковым номером d_m входной части матрицы, является неуправляемым.

Переключатели последнего уровня входной части матрицы, образующие выходы входной части матрицы, разделены на 2^r-1 групп по 2^k-r+1 переключателей, причем номер группы q_r, в которую входит переключатель, расположенный на линии номером i, определяется выражением

,

где r=().

Каждый переключатель первого уровня выходной части матрицы соединен своими входами с выходами переключателей последнего уровня входной части матрицы, входящих в группу с одинаковым номером q₁, переключатель любого уровня m, начиная со второго, выходной части матрицы может быть соединен своими входами с выходами переключателей последнего уровня входной части матрицы, входящих только в группу с одинаковым номером q_m-1 при любых комбинациях управляющих кодов в промежуточных переключателях выходной части матрицы, через которые проходит соединение.

Изобретение поясняется чертежами, где на фиг.1 приведена диаграмма орграфа, иллюстрирующая работу устройства для n=16, u=1, на фиг.2 приведена схема входной части кросс-кластерной коммутационной матрицы для случая n=16, k=4, u=1, на фиг.3 приведена схема выходной части кросс-кластерной коммутационной матрицы для случая n=16, k=4, u=1,

где F₁, F₂, F₃ - уровни коммутации входной части кросс-кластерной коммутационной матрицы;

G₁, G₂, G₃- уровни коммутации выходной части кросс-кластерной коммутационной матрицы;

S11, S12 - входы первого кластера матрицы;

S21, S22 - входы второго кластера матрицы;

S31, S32 - входы третьего кластера матрицы;

S41, S42 - входы четвертого кластера матрицы;

S51, S52 - входы пятого кластера матрицы;

S61, S62 - входы шестого кластера матрицы;

S71, S72 - входы седьмого кластера матрицы;

S81, S82 - входы восьмого кластера матрицы;

R11, R12 - выходы первого кластера матрицы;

R21, R22 - выходы второго кластера матрицы;

R31, R32 - выходы третьего кластера матрицы;

R41, R42 - выходы четвертого кластера матрицы;

R51, R52 - выходы пятого кластера матрицы;

R61, R62 - выходы шестого кластера матрицы;

R71, R72 - выходы седьмого кластера матрицы;

R81, R82 - выходы восьмого кластера матрицы;

А1-А16 - выходы входной части коммутационной матрицы;

входы выходной части коммутационной матрицы;

X1, Х2 - первый и второй входы переключателя кросс-кластерной коммутационной матрицы;

Y2, Y2 - первый и второй выходы переключателя кросс-кластерной коммутационной матрицы;

С - вход управляющего кода переключателя кросс-кластерной коммутационной матрицы.

Кросс-кластерная коммутационная матрица имеет n входов данных, n выходов данных, входы управляющих кодов и состоит из входной и выходной части. Входная часть состоит из управляемых и неуправляемых переключателей Т_ij, где k=log₂n. Выходная часть состоит из аналогичных управляемых переключателей V_sg, где u≤k. Каждый переключатель имеет два входа X1, Х2, два выхода Y1, Y2, причем управляемые переключатели имеют также вход управляющего кода С, который принимает значения логического нуля или единицы. Каждый переключатель может соединять либо первый вход с первым выходом, а второй вход с вторым выходом, либо первый вход с вторым выходом, а второй вход с первым выходом. Например, если сигнал на входе С управляемого переключателя имеет высокий логический уровень, то сигнал на первом выходе равен сигналу на втором входе Y1=X2, а сигнал на втором выходе равен сигналу на первом входе Y2=X1, переключатель осуществляет транспозицию сигналов на своих входах. Если сигнал на входе С имеет низкий логический уровень, то сигнал на первом выходе равен сигналу на первом входе Y1=X1, а сигнал на втором выходе равен сигналу на втором входе Y2=X2. Неуправляемые переключатели не имеют входа управляющего кода и осуществляют фиксированное соединение первого входа со вторым выходом, второго входа с первым выходом или первого входа с первым выходом, второго входа со вторым выходом.

Переключатели образуют входную часть матрицы с n/2-линиями и k-1 уровнями F₁,…,F_k-1, и выходную часть матрицы с n/2-линиями и k-u уровнями G₁,…,G_k-u. Входы управляющих кодов кросс-кластерной коммутационной матрицы образованы входами кодов переключателей С. Входы данных кросс-кластерной коммутационной матрицы образованы входами переключателей Т_i1 первого уровня. Выходы данных кросс-кластерной коммутационной матрицы образованы входами переключателей V_ik-u последнего уровня k-u выходной части матрицы. Каждый переключатель T_im уровня входной части кросс-кластерной коммутационной матрицы своими выходами соединен с входами данных переключателей V_hm+1, V_pm+1 уровня m+1. Каждый переключатель V_im уровня выходной части матрицы своими выходами соединен с входами данных переключателей V_hm+1, V_pm+1 уровня m+1. Причем где int - функция выделения целой части, (j+2^k-m-1-1)modn - операция вычисления остатка от частного

Переключатели любого уровня с номером m входной и выходной части кросс-кластерной коммутационной матрицы разбиты на 2^m-1 групп по 2^k-m+1 (k=log₂n) переключателей, номер группы d_m уровня m определяется выражением

,

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

На фиг.2 представлен вариант реализации входной части кросс-кластерной коммутационной матрицы, удовлетворяющей приведенным выше условиям для случая n=16. Входная часть кросс-кластерной коммутационной матрицы имеет три уровня F₁, F₂, F₃. Переключатели первого уровня одним выходом соединены с любым входом любого переключателя из верхней половины переключателей второго уровня, а вторым выходом соединены с любым входом любого переключателя из нижней половины переключателей второго уровня. Переключатели второго уровня одним выходом соединены с любым входом любого переключателя из верхней четверти переключателей третьего уровня, а вторым выходом соединены с любым входом любого переключателя из нижней четверти переключателей третьего уровня и т.д. На первом уровне неуправляемый один переключатель Т₃₁ из группы с номером d₁=1, на втором - два переключателя Т₄₂, из группы с номером d₂=1 и Т₅₂ из группы с номером d₂=2, на третьем - четыре переключателя Т₁₃ из группы с номером d₃=1, Т₃₃ из группы с номером d₃=2, Т₅₃ из группы с номером d₃=3 и Т₇₃ из группы с номером d₃=4.

Каждый вход переключателей m+1 уровня соединен с одним выходом переключателей m уровня. Каждый выход переключателей m уровня соединен с одним входом переключателей m+1 уровня.

На соединения переключателей последнего уровня входной части матрицы с переключателями первого уровня выходной части матрицы и переключателей выходной части матрицы накладывается ограничение. Переключатели последнего уровня, образующие выходы данных входной части матрицы, разделены на группы по 2,4,8…n/2 элементов. Номер группы q_m, в которую входит переключатель с номером i (номер линии, в которой стоит переключатель), определяется выражением , где .

Каждый переключатель первого уровня выходной части матрицы соединен своими входами с выходами переключателей последнего уровня входной части матрицы, входящих в группу с соответствующим номером q₁, переключатель любого уровня m, начиная со второго, выходной части матрицы может быть соединен своими входами с выходами переключателей последнего уровня входной части матрицы, входящих только в группу с одинаковым номером q_m-1, при любых комбинациях управляющих кодов в промежуточных переключателях выходной части матрицы, через которые проходит соединение.

На фиг.3 представлен вариант реализации выходной части кросс-кластерной коммутационной матрицы, удовлетворяющей приведенным выше условиям для случая n=16, u=1. Выходная часть кросс-кластерной коммутационной матрицы имеет три уровня G₁, G₂, G₃. Переключатели V₁₁, V₂₁ своими входами соединены с выходами переключателей Т₁₃, Т₂₃ последнего уровня входной части кросс-кластерной коммутационной матрицы, входящих в группу с номером q₁=1, переключатели V₃₁, V₄₁ своими входами соединены с выходами переключателей Т₃₃, Т₄₃ последнего уровня входной части матрицы, входящих в группу с номером q₁=2 и т.д. Переключатели V₁₂, V₈₂ своими входами соединены с выходами переключателей Т₃₃, Т₄₃ последнего уровня входной части матрицы, входящих в группу с номером q₁=2. Промежуточными переключателями, через которые проходят соединения, являются переключатели V₃₁, V₄₁. Каждый из переключателей уровня G₂ соединен с переключателями уровня F₃, входящими в группу q₁=1 или q₁=2 или q₁=3 или q₁=4. Переключатели уровня G₂ не могут быть соединены с переключателями уровня F₃, входящими в группы с разными номерами q₁. Переключатель V₁₃ своими входами может быть соединен с переключателями Т₅₃, Т₆₃, Т₇₃, Т₈₃, входящими в группу с номером q₂=2. Каждый из переключателей уровня G₃ может быть соединен с переключателями уровня F₃, входящими в группу с номерами q₂=2 или q₂=1. Переключатели уровня G₃ не могут быть соединены с переключателями уровня F₃, входящими в группы с разными номерами q₂. Таким образом, соединения переключателей выходной части матрицы удовлетворяют приведенным выше условиям.

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

На входы данных матрицы подаются входные сигналы. На первые 2^u входов поступают сигналы первого кластера, на следующие 2^u входов поступают сигналы второго кластера и т.д. На входы С подаются управляющие коды. Через время задержки преобразования τ·(u+log₂n-1), где τ - задержка на одном переключателе на выходах кросс-кластерной коммутационной матрицы, появляется кросс-кластерная перестановка входных сигналов. Первые 2^u выходов матрицы представляют собой первый кластер, следующие 2^u выходов матрицы представляют собой второй кластер и т.д. Каждый из сигналов входного кластера может попасть в любой выходной кластер. Если u=0 матрица осуществляет одновременное неблокирующее соединение каждого входа с одним из выбранных выходов, а каждый выход оказывается соединен с одним из входов. Число возможных различных перестановок входных сигналов в этом случае составляет n!.

Таким образом, кросс-кластерная перестановка входных данных осуществляется параллельно за один такт внешнего генератора тактовых импульсов. Время задержки преобразования τ·(2·log₂n-u-1), где τ - задержка на одном переключателе.

Число переключателей матрицы составляет n·(log₂(n)-u/2-1)+1 и растет практически линейно с ростом n, что делает технически возможным кросс-кластерную перестановку при больших значениях n. Число различных кросс-кластерных перестановок, осуществляемых данным устройством, .

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

Предложенная матрица позволяет параллельно осуществлять кросс-кластерную перестановку входных сигналов. Число уровней преобразования на u меньше, чем у существующих решений этой задачи. Соответственно на un/2 меньше количество переключателей и длина управляющего кода. Время задержки на преобразования также на u·τ меньше. Кроме этого в предложенной коммутационной матрице соединения между уровнями заданы не жестко, что дает возможность их изменения, например, для оптимизации топологии матрицы.

Устройство относится к области кодирования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является возможность осуществления высокоскоростной кросс-кластерной перестановки элементов данных или сигналов на входах с использованием управляющих кодов. Кросс-кластерная коммутационная матрица, предназначенная для одновременного соединения каждого из входов любого входного кластера с одним выходом любого выходного кластера, имеющая n=2k входов данных, разделенных по порядку номеров на 2u кластеров, где u<k - неотрицательное целое число, n=2k выходов данных, разделенных по порядку номеров на 2u кластеров, входы управляющих кодов, при этом матрица состоит из входной и выходной частей, которые состоят из переключателей, при этом переключатели входной части являются управляемыми и неуправляемыми, а переключатели выходной части являются управляемыми, неуправляемые переключатели имеют два входа, два выхода, а управляемые имеют дополнительно вход управляющего кода, переключатели расположены по уровням - столбцам и линиям - строкам. 7 з.п. ф-лы, 3 ил.

1. Кросс-кластерная коммутационная матрица, предназначенная для одновременного соединения каждого из входов любого входного кластера с одним выходом любого выходного кластера, имеющая n=2k входов данных, разделенных по порядку номеров на 2^u кластеров, где u<k неотрицательное целое число, n=2k выходов данных, разделенных по порядку номеров на 2^u кластеров, входы управляющих кодов, при этом матрица состоит из входной и выходной частей, которые состоят из переключателей, при этом переключатели входной части являются управляемыми и неуправляемыми, а переключатели выходной части являются управляемыми, неуправляемые переключатели имеют два входа, два выхода, а управляемые имеют дополнительно вход управляющего кода, переключатели расположены по уровням - столбцам и линиям - строкам, причем входы управляющих кодов кросс-кластерной коммутационной матрицы образованы входами кодов управляемых переключателей, входы данных матрицы образованы входами переключателей первого уровня входной части матрицы, выходы данных матрицы образованы выходами переключателей последнего уровня выходной части матрицы, выходы переключателей предыдущего уровня соединены со входами переключателей следующего уровня, под соединением понимается условие, при котором, если подать сигнал на вход, соединенный с выходом, или выход, соединенный с входом, на выходе, через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал, и, наоборот, если подать сигнал на выход, на входе, через некоторую временную задержку, обусловленную временем распространения сигнала, появится выходной сигнал.

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

3. Матрица по п.1, характеризующаяся тем, что переключатели, составляющие входную часть, расположены в следующем порядке: по n/2-линиям - строкам и k-1 уровням - столбцам.

4. Матрица по п.1, характеризующаяся тем, что переключатели, составляющие выходную часть матрицы, расположены в следующем порядке: по n/2-линиям и k-u уровням, причем выходы первого кластера матрицы образованы одним выходом первых 2^u переключателей, выходы второго кластера матрицы образованы вторым выходом первых 2u переключателей, выходы третьего кластера матрицы образованы одним выходом следующих 2u переключателей, выходы четвертого кластера матрицы образованы вторым выходом следующих 2u переключателей и т.д.

5. Матрица по п.3 или 4, характеризующаяся тем, что один выход каждого переключателя, стоящего на линии i и уровне m входной или выходной части матрицы, соединен с одним входом переключателя, стоящего на следующем уровне m+1 и на линии h, причем , а второй выход каждого переключателя, стоящего на линии i и уровне m входной или выходной части матрицы, соединен с одним входом переключателя, стоящего на следующем уровне m+1 и на линии р, причем , при этом каждый вход каждого переключателя уровня m+1 соединен с одним выходом переключателя предыдущего уровня m, где int - функция выделения целой части, (j+2^k-m-1)mod n - операция вычисления остатка от частного .

6. Матрица по п.3, характеризующаяся тем, что переключатели любого уровня входной части матрицы разбиты на 2^m-1 групп по 2^k-m+1 переключателей, номер группы d_m определяется выражением , где i - номер линии, m - номер уровня переключателя, входящего в группу с номером d_m, при этом один из переключателей уровня m, входящих в группу с одинаковым номером d_m входной части матрицы является неуправляемым.

7. Матрица по п.3, характеризующаяся тем, что переключатели последнего уровня входной части матрицы, образующие выходы входной части матрицы, разделены на 2^r-1 групп по 2^k-r-l переключателей, причем номер группы q_r, в которую входит переключатель расположенный на линии номером i определяется выражением , где r=().

8. Матрица по п.4, характеризующаяся тем, что каждый переключатель первого уровня выходной части матрицы соединен своими входами с выходами переключателей последнего уровня входной части матрицы, входящих в группу с одинаковым номером q₁, переключатель любого уровня m, начиная со второго, выходной части матрицы соединен своими входами с выходами переключателей последнего уровня входной части матрицы, входящих только в группу с одинаковым номером q_m-1 при любых комбинациях управляющих кодов в промежуточных переключателях выходной части матрицы, через которые проходит соединение.