Экономика в промышленности Под редакцией профессора А. В. Ляшенко Саратов Издательство Саратовского университета 2015
Скачать 2.44 Mb.
|
Отношение смежности вершин di и tik
Для каждого значения n в первом столбце располагаются в порядке возрастания индексы вершин di. Во втором столбце – индексы смежных вершин tjk k-го уровня. Индексы во второй строке вычисляются по рекуррентным формулам. Смежные вершины задаются парами  ,  , …,  . Отношение смежности вершин di и tik, можно задать, не используя рекуррентные соотношения. Рассмотрим операторы преобразования индексов f·i ≡ 2i – 1, g·i ≡ 2i, причем для простоты записи будем считать, что если операнд справа от оператора отсутствует, то он равен 1: f ≡ f·1, g ≡ g·1. Тогда индексы смежных вершин tjk k-го уровня, расположенные во втором столбце таблицы, для случая n = 8 можно записать в виде  Пусть, в общем случае, ak–1, …, a1, a0 – представление индекса r ≤ n в двоичном виде, тогда  , где Рассмотрим способы преобразования формата исходной строки, связанной с вершинами S орграфа. Пусть  – простой путь от si к dj. Рассмотрим множество путей rij из S в D, не имеющих общих дуг  , .Значение R определяет биективное отображение TFD: S D. Пусть C1, C2 – разбиение вершин D, причем C1 = (d0, d1, d2, …, dp–1), C2 = (dp, dp+1, dP+2, …, dn–1),  . Таким образом,  ,  .Пометим произвольные p вершин множества S. Для всех помеченных вершин si существуют p различных путей rij R таких, что dj C1. Для формирования данных путей при переходе между уровнями орграфа G(S, D, T, Ă) будем выбирать дуги так, чтобы l/2 вершин подмножества уровня m соединялась с промежуточными вершинами верхнего подмножества уровня m + 1, а оставшиеся l/2 вершин подмножества уровня m соединялись с промежуточными вершинами нижнего подмножества уровня m + 1, где l – мощность подмножества уровня m. Если l нечетное, (l+1)/2 вершин подмножества уровня m соединяются с промежуточными вершинами верхнего подмножества уровня m + 1, а оставшиеся (l – 1)/2 вершин подмножества уровня m соединяются с промежуточными вершинами нижнего подмножества уровня m + 1. Такой выбор всегда можно осуществить, причем выбор участка пути одной из вершин каждого верхнего или нижнего промежуточного подмножества уровня m можно сделать произвольно. Таким образом, в рамках предложенной комбинаторной модели возможно осуществление любой кросс-кластерной перестановки исходной строки данных длиной n между кластерами длиной p и n – p. Аппаратная модель однотактного кросс-кластерного преобразователя Блок-схема однотактного кросс-кластерного преобразователя для n = 8 представлена на рис. 2. РИС ТМКП РРС D1–Dn S1–Sn clk РК С Рис. 2. Блок-схема кросс-кластерного транспозиционного преобразователя Преобразователь состоит из транспозиционной матрицы кросс-кластерного преобразования (ТМКП) входного регистра исходной строки (РИС) и выходного регистра результирующей строки (РРС), а также регистра управляющих кодов РК. Схема ТМКП представлена на рис. 3. F1 F2 F3 D S X1 Y1 X2 Y2 T11 X1 X2 Y1 Y2 T21 X1 X2 Y1 Y2 T31 X1 X2 Y1 Y2 T41 X1 X2 Y1 Y2 T42 Рис. 3. Схема транспозиционной матрицы кросс-кластерного преобразования s1 s2 s3 s4 s5 s6 s7 s8 d1 d2 d3 d4 d5 d6 d7 d8 X1 X2 Y1 Y2 T43 X1 X2 Y1 Y2 T33 X1 X2 Y1 Y2 T23 X1 Y1 X2 Y2 T32 X1 Y1 X2 Y2 T12 X1 X2 Y1 Y2 T313 X1 X2 Y1 Y2 T222 Матрица состоит из логических транспозиционных элементов Tij, имеющих два входа X1, X2 и два выхода Y1, Y2, а также битовый вход управляющего кода COD (на рис. 2 для простоты не указан). Каждый логический элемент осуществляет транспозицию данных Y1=X2, Y2=X1 при высоком логическом уровне на входе COD или передает данные без изменения Y1=X1, Y2=X2 при низком логическом уровне на входе COD. Таким образом, каждый логический элемент представляет собой 22 баньян-переключатель (Banyan switch):  , .Элементы  не управляемые, их можно исключить из схемы. Входы кодов ТМКП соединены с выходами РК. Соединения между элементами Tij, а также соединения Tij с регистрами исходной s и результирующей D строками определяются отношением смежности соответствующих вершин графа G (S, D, T, Ă).Моделирование преобразователя проводилось на уровне RTL (register-transfer level) с использованием языка SystemC [26–28]. Перед началом преобразования по переднему фронту тактового импульса clk в регистр управляющих кодов записываются управляющие коды дескриптора FDn, в регистр исходной строки данных s – n битов форматируемых данных, в регистр результирующей строки РРС – форматированная на предыдущем шаге строка данных. Каждый бит управляющих кодов, записанный в РК, подается на вход COD одного из транспозиционных элементов ТМКП. По переднему фронту следующего тактового импульса перестановленные элементы данных записываются в выходной регистр данных. Одновременно в РК заносятся новые коды дескриптора FDn, а в РС – n следующих элементов данных. Если в каждом из логических элементов реализовать обратную функцию преобразования  , ,то ТМКП выполняет обратное преобразование. Следовательно, для осуществления прямого и обратного кросс-кластерного преобразования данных эффективно использовать матрицы прямого и обратного преобразований. В этом случае дескриптор прямого преобразования бинарной строки также будет дескриптором обратного преобразования бинарной строки. Предложенное устройство дает возможность осуществления любого кросс-кластерного преобразования исходной строки данных длиной n элементов между двумя произвольно выбранными кластерами. Кросс-кластерная перестановка элементов входных данных осуществляется параллельно за один такт внешнего генератора тактовых импульсов, что обеспечивает высокую скорость преобразования. Время задержки преобразования ∙log2n, где – задержка на одном транспозиционном элементе. Число управляемых логических элементов транспозиционной матрицы составляет  и растет практически линейно с ростом n, что делает технически возможным кросс-кластерную перестановку больших блоков данных. Число различных кросс-кластерных перестановок, осуществляемых данным устройством,  . Максимальное число различных кросс-кластерных перестановок достигается при  . Композиция ТМКП для перестановки n элементов входных данных с двумя ТМКП для перестановки n/2 элементов входных данных позволяет осуществить любую перестановку между четырьмя кластерами. При этом входы матрицы преобразования n/2 элементов соединяются с выходами матрицы преобразования n элементов. Использование различных вариантов последовательного включения ТМКП дает возможность реализовать любую перестановку между кластерами Ci с размерами  , где  .БИБЛИОГРАФИЧЕСКИЙ СПИСОК
УДК 621.391.037 |
=
=
=
=
=
=
=
=
)=
Похожие:
 | Решением Президиума вак министерства образования и науки РФ издание включено в Перечень ведущих рецензируемых изданий, в которых |  | К38 Неправомерные действия должностных лиц налоговых органов. Саратов: Изд-во Сарат ун-та, 2008 376 с.: ил. 978-5-292-03835-1 |
| Лингвометодические проблемы преподавания иностранных языков в высшей школе: Межвуз сб науч тр. / Под ред. Л. И. Со | | Лингвометодические проблемы преподавания иностранных языков в высшей школе: Межвуз сб науч тр. / Под ред. Л. И. Со |
| Экономика. Теория и практика: материалы III международной научно-практической конференции (16 июня 2015 г.). Отв ред. Зарайский А.... | | О. В. Бессчетнова : под ред. Г. В. Дыльнова. — Саратов : Научная книга, 2008. — 288 с |
| Для преподавателей, научных работников и студентов, обучающихся по специальности «Социально-культурный сервис и туризм» | | Для преподавателей, научных работников и студентов, обучающихся по специальности «Социально-культурный сервис и туризм» |
| «Педагогика и психология» Пензенского государственного технологического университета О. А. Вагаева | | «Педагогика и психология» Пензенского государственного технологического университета О. А. Вагаева |