Экономика в промышленности Под редакцией профессора А. В. Ляшенко Саратов Издательство Саратовского университета 2015
Скачать 2.44 Mb.
|
Data Format Transformation Modules for Computer Facilities A. V. Lyashenko, V. N. Malyarchuk The methods for design high-performance data format transformation modules are considered. The devices with parallel data input which are carrying out transformation for one step of the external generator of clock impulses are investigated. Key words: format of data, information security, microprocessor. Особую роль в микропроцессорах играют преобразователи форматов представления данных машинного слова [1, 2]. Задача преобразования формата представления данных исходного упорядоченного бинарного множества часто возникает в системах управления базами данных, защиты информации и др. [3, 4]. С точки зрения вычислительной сложности эта задача достаточно трудоемкая. В связи с этим ряд работ авторов посвящен разработке аппаратных формирователей перестановок (FP), обзор которых можно найти в [5, 6]. В классификации FP различают генераторы перестановок и функциональные FP. В последних перестановках из N элементов это однозначно определяется натуральным числом FDj (где 1≤J≤N!), которое в дальнейшем будем называть дескриптором формата. На практике для ускорения преобразования и упрощения FP дескриптор формата FDj может иметь более сложную структуру. При этом мощность полного множества различных дескрипторов формата перестановки длиной N определяется |{FD}N|=N!. Работа функциональных FP основана на возможности факторизации представления чисел [7]. Функциональные FP строятся с использованием транспозиционных, сдвиговых и комбинированных алгоритмов, при этом преобразования выполняются за несколько раундов, а аппаратная сложность, исчисляемая в эквивалентных логических вентилях, растет приблизительно как N2. При разработке FP, предназначенных для преобразования форматов данных, необходимо учитывать, какой будет использоваться интерфейс передачи исходных данных, – последовательный или параллельный [8, 9]. В случае последовательной передачи данных временем преобразования исходного вектора данных длиной N будет время τp = Nτ, где – период следования тактовых импульсов внешнего генератора. В этом случае FP не будет задерживать поток данных, поступающих по последовательному каналу. В случае параллельной передачи данных наилучшим временем преобразования исходного вектора данных длиной N будет время τp = , и интерес представляют однотактные FP. Для аппаратных FP перспективным является метод разбиений исходного упорядоченного множества данных A = (a1, a2,…, aN) на подмножества, которые упорядочены между собой [10, 11]. Одним из наиболее эффективно реализуемых аппаратно является метод последовательного разбиения исходного множества на два равномощных подмножества A1 и A2 [12, 13]: A1 A2 = A&A1∩A2 = 0&|A1| = |A2|. Орграф, иллюстрирующий данный метод, представляет собой двоичное дерево. В каждом узле орграфа соответствующее подмножество исходного множества разбивается на два подмножества, из которых одно позиционируется перед другим. В результате выполнения преобразований на K = log2(N) уровнях узлов орграфа образуется перестановка исходного упорядоченного множества. Осуществляя различные разбиения в узлах орграфа, можно получить любую перестановку Р исходного множества. Действительно, число способов разбиений множества мощностью N на два подмножества мощностью  –  .Таким образом, число различных разбиений подмножеств в узлах орграфа составляет  Так как преобразования выполняются в различных узлах орграфа, процесс преобразования распараллеливается. Пользуясь данной методикой, можно разрабатывать универсальные и инволютивные преобразователи форматов данных [14, 15]. Функциональный FP, основанный на таком методе, предложен в [8]. Устройство формирует перестановку, определяемую дескриптором, состоящим из N уникальных бинарных строк длиной log2(N), и одновременно преобразует последовательный код исходных данных в параллельный. Однако из-за суммирования временных задержек на уровнях узлов дешифрации данный FP нельзя использовать для обеспечения обработки больших блоков данных со скоростью передачи более 1 Гбит/с [16]. Повышение производительности FP возможно за счет конвейерной обработки исходных данных. Схема FP для двух уровней узлов дешифрации, позволяющая выполнять перестановку вектора данных из четырех элементов, приведена на рис. 1. 1 D RD clk CS CP1 D RD clk CS CP D RD clk CS CP CP3 CP2 RD1 D1 D2 RD2 RD3 D3 D4 RD4 D RD BZY 2 2 0 clk D_OUT rd1 rd2 D_OUT rd1 rd2 D_OUT rd1 rd2 Рис. 1. Cхема FP для двух уровней узлов дешифрации Моделирование FP для двух уровней узлов дешифрации проводилось с использованием языка SystemC и пакета программ Synopsys System Studio [17, 18]. При этом использовалась методика, описанная в [19]. Перед началом преобразования в циклические сдвиговые регистры хранения кодов дешифрации заносятся управляющие коды дешифрации. Для этого управляющая ЭВМ устанавливает вход RD в состояние c низким логическим уровнем, подает на входы CP управляющие коды и записывает их в регистры по очередному импульсу clk, устанавливая для этого на входе CS состояние с высоким логическим уровнем. Для перестановки очередного вектора данных (a1, a2, a3, a4) вход CS устанавливается в состояние с низким логическим уровнем. На вход данных D элемента первого уровня дешифрации подается элемент a1 вектора данных. Вход RD устанавливается в состояние c высоким логическим уровнем и по очередному импульсу clk a1 записывается в элемент первого уровня дешифрации. По заднему фронту импульса clk в состоянии RD = 1, CS = 0 логическая схема этого элемента формирует сигналы на выходах разрешения записи rd1 = s, rd2 =  , где S – первый бит регистра кодов элемента первого уровня. После чего осуществляется циклический сдвиг битов управляющего кода регистра первого уровня, и управляющий бит S заменяется на следующий.По фронту следующего импульса clk данные из логического элемента первого уровня a1 переписываются в первый элемент второго уровня при rd1 = 1, rd2 = 0 или во второй элемент второго уровня при rd1 = 0, rd2 = 1, затем в элемент первого уровня записывается значение a2 вектора данных. Работа всех логических элементов узлов дешифратора осуществляется по одинаковому алгоритму. После загрузки текущего вектора данных в дешифратор без остановки загружается следующий. В результате через N = 4 тактовых импульсов clk элементы (a1, a2, a3, a4) записываются в двойной буферный регистр накопления и хранения форматированных данных в порядке, определяемом кодами дешифрации. При сигнале двойного буферного регистра RD = 0 перестановка вектора (a1, a2, a3, a4) в параллельном коде записывается во второй регистр и сигнал RD двойного буферного регистра накопления и хранения форматированных данных принимает высокий логический уровень. Если сигнал двойного буферного регистра RD = 1, формируется выходной сигнал BZY = 1, и процесс преобразования приостанавливается путем прекращения подачи тактовых импульсов clk до момента освобождения второго регистра. В общем случае FP с конвейерной обработкой состоит из К уровней узлов дешифрации, выполняющих функцию перестановки данных (a1, …, an) [20, 21]. Логические элементы узлов дешифратора имеют одинаковую структуру. Управление перестановкой осуществляется кодами, загружаемыми в циклические сдвиговые регистры логических элементов узлов дешифратора. Причем в логический элемент первого уровня 1 загружается N битов управляющих кодов, в логические элементы второго уровня 2 – N/2, а в логические элементы К-го уровня –  .Таким образом, за счет конвейерной обработки данных в узлах дешифрации удается сократить время выполнения перестановки примерно в K раз, так как общее время задержки определяется временем задержки на одном уровне узлов FP. Кроме того, число логических элементов узлов дешифрации составляет N – 1 и растет линейно с ростом N, что позволяет реализовать FP для перестановки больших блоков данных. Наибольшим быстродействием обладают функциональные FP, осуществляющие перестановку за один такт внешнего генератора тактовых импульсов. Задержка на преобразование определяется задержкой двух последовательно соединенных вентилей. Использование принципа двойной буферизации позволяет максимально увеличить производительность однотактных функциональных FP (OFFP). Процесс преобразования в OFFP можно разделить на две фазы: дешифрация и сборка. Модель OFFP иллюстрируется диаграммой, представленной на рис. 2, где осуществляется перестановка упорядоченного множества из 14 элементов. Сборка Дешифрация 14 13 12 11 10 9 8 7 6 5 4 3 2 1 5 4 7 9 8 1 11 6 12 10 2 13 14 3 Рис. 2. Диаграмма орграфа, иллюстрирующего работу OFFP Аппаратная сложность OFFP, исчисляемая в эквивалентных логических вентилях, растет как N2, однако, в отличие от функциональных FP, основанных на факторизации чисел, OFFP осуществляет перестановку не за N, а за один такт генератора тактовых импульсов. Блок-схема OFFP приведена на рис. 3, а на рис. 4 – логические схемы блоков 3–9. OFFP состоит из регистров исходной строки первой и второй групп (1, 2) дешифраторов битовой транспозиции первой и второй групп (3, 4), регистра кодов битовой транспозиции 5, блоков сборки битовой транспозиции второй и первой групп (6, 7), регистров результирующей строки второй и первой групп (8, 9). Управление OFFP осуществляется сигналами установки регистра исходной строки первой и второй групп РИС1, РИС2, сигналами разрешения установки регистра результирующей строки первой и второй групп РРС1, РРС2. На вход сlk подаются тактовые импульсы от внешнего генератора тактовых импульсов. 2 4 clk2 PPC2 5 clk1 PPC1 РИС2 РИС1 8 9 1 3 7 6 Рис. 3. Блок-схема OFFP c двойной буферизацией По сигналу РИС1 исходный вектор данных (a1, ….., ai, …. an) длиной N бит с внешней шины данных записывается в регистр 1. Независимо, по сигналу РИС2, с внешней шины данных в регистр 2 может быть записан следующий вектор данных. На один вход логических элементов 2И-НЕ, входящих в дешифратор битовой транспозиции 3, подается соответствующий бит вектора исходных данных (БИС1, …, БИСN) от регистра 1 (см. рис. 4). На второй вход этих логических элементов подается сигнал от регистров кодов 5. В результате на выходе элемента И-НЕ с N-входами появляется сигнал БИС с порядковым номером, соответствующим высокому логическому уровню сигнала соответствующего регистра кодов 5. Если сигнал РPC1 имеет высокий логический уровень, то по сигналу сlk инвертированная перестановка исходного вектора данных записывается в регистр 9. Сигнал РPC1 имеет высокий логический уровень в том случае, если предыдущая перестановка вектора исходных данных считана из регистра 9, и он готов к приему новой перестановки. Если сигнал РPC1 имеет низкий логический уровень, а регистр 8 готов к приему новой перестановки исходных данных, то сигнал РPC2 имеет высокий логический уровень и данные попадают в регистр 8. Если оба регистра результирующей строки оказываются заняты (РРС1 и РРС2 имеют низкий логический уровень), возникают пропуск тактовых импульсов сlk и задержка потока форматируемых данных. Работа второй группы блоков 2, 4, 6, 8 аналогична работе первой группы блоков 1, 3, 7, 9. Таким образом, перестановка выполняется за один такт внешнего генератора тактовых импульсов. Это дает возможность осуществить высокоскоростной обмен данными между внешними устройствами с одновременным выполнением управляемой кодом перестановки битов исходных векторов данных. Аппаратная сложность в виде условных вентилей, образующих OFFP согласно рис. 4 составляет WW2=2·N2+12·N, где 2·(N2+N) вентилей содержат дешифраторы битовой транспозиции первой и второй групп, а  вентилей – блоки сборки битовой транспозиции первой и второй групп. & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & БИС1 БИС2 БИСN 5 4 6 8 9 7 3 5 РРС2 РРС1 clk clk РРС2 РРС1 clk clk БИС1 БИС2 БИСN БИС1 БИС2 БИСN РРС2 РРС1 clk clk РРС2 РРС1 clk clk БИСN Рис. 4. Логическая схема OFFP c двойной буферизацией БИС2 БИС1 При отсутствии двойной буферизации число условных вентилей составит WW = N2+2N. Согласно логической схеме OFFP управляющие коды с модуля регистров кодов дешифрации поступают на входы блоков дешифраторов первой и второй групп 3, 4, причем в каждой группе значение логической единицы принимает только один вход, номер которого совпадает с номером транспонируемого бита исходного вектора данных. Таким образом, дескриптор формата представляет собой бинарную матрицу, в каждой строке которой содержится только один бит, имеющий единичный логический уровень:
До преобразований исходного кода на соответствующие группы входов подаются управляющие коды соответствующей строки матрицы дескриптора формата FDj . С точки зрения аппаратной реализации для хранения матрицы FDj требуется большой объем памяти N2 битов, что дополнительно усложняет техническую реализацию предлагаемого OFFP и предъявляет жесткие требования к запоминающему устройству (ЗУ) сервера форматирования, выполняющего преобразования данных [16]. Кроме того, следует заметить, что при использовании описанного OFFP необходимо применять дешифраторы битов управления, которые приводят к дополнительным задержкам и снижению быстродействия схемы [22, 23]. Снизить технические требования к ЗУ сервера форматирования и OFFP возможно путем включения в OFFP N дополнительных дешифраторов компактных дескрипторов формата, представляющих собой множество уникальных бинарных строк  , тогда
где K = log2(N). Дешифраторы дескрипторов преобразуют строки Sj в строки БИСj1–БИСjN матрицы (1). Схема дешифратора элемента дескриптора Sj для случая K = 4, N = 16 приведена на рис. 5. Дешифратор состоит из однотипных логических элементов, образующих двоичное дерево и реализующих логические формулы  – для первого элемента и  – для остальных элементов. Для дешифрации одной бинарной строки из Sj битов необходимо (N–1) элементов.Число условных вентилей дешифраторов дескриптора, необходимых в этом случае, равно N(N–1). При этом общее число вентилей OFFP составит
БИС01 БИС02 БИС03 БИС04 БИС05 БИС06 БИС07 БИС08 БИС09 БИС10 БИС11 БИС12 БИС13 БИС14 БИС15 БИС16 Sj X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2 X Y1 Y2 Рис. 5. Схема дешифратора дескрипторов OFFP В случае отсутствия двойной буферизации общее число вентилей OFFP составит
Сравнительная характеристика функциональных FP приведена в работе [4]. Одним из наиболее перспективных является FP, предложенный в [24]. Он выполняет перестановку исходного вектора данных за N тактов сlk и содержит около N2 условных вентилей. Таким образом, предложенный функциональный FP с последовательной загрузкой при той же производительности с учетом буферного регистра имеет 2N–1 условных вентилей, что дает возможность создания данного FP для перестановки больших блоков данных. Описанный выше OFFP при одинаковом росте аппаратной сложности (порядка N2) имеет производительность в N раз выше, так как осуществляет перестановку исходного вектора данных за один такт внешнего генератора тактовых импульсов. Исследование способов построения высокопроизводительной аппаратуры для обеспечения представлений структурных элементов данных в ЭВМ в процессе их хранения и оперативной обработки показало, что наибольшей производительностью обладают устройства с параллельным преобразованием. С точки зрения аппаратурной реализации наиболее эффективным оказывается предложенный алгоритм последовательного разбиения исходного множества на два подмножества. Установлено, что за счет конвейерной обработки данных в узлах дешифрации удается сократить время выполнения перестановки в несколько раз, так как общее время задержки определяется временем задержки на каждом уровне преобразования. Показано, что число логических элементов узлов дешифрации растет линейно с ростом длины преобразования N. Это позволяет реализовать устройства для перестановки больших блоков данных. Предложенные устройства преобразования форматов представления данных имеют преимущества по сравнению с существующими решениями, так как отличаются высокой производительностью, простотой аппаратурной реализации и масштабируемостью. В предложенных моделях соединения между элементами различных уровней коммутационных матриц заданы не жестко, что дает возможность их изменения для оптимизации топологии матрицы. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
УДК 531.38 |
.
m=n)},Похожие:
 | Решением Президиума вак министерства образования и науки РФ издание включено в Перечень ведущих рецензируемых изданий, в которых |  | К38 Неправомерные действия должностных лиц налоговых органов. Саратов: Изд-во Сарат ун-та, 2008 376 с.: ил. 978-5-292-03835-1 |
| Лингвометодические проблемы преподавания иностранных языков в высшей школе: Межвуз сб науч тр. / Под ред. Л. И. Со | | Лингвометодические проблемы преподавания иностранных языков в высшей школе: Межвуз сб науч тр. / Под ред. Л. И. Со |
| Экономика. Теория и практика: материалы III международной научно-практической конференции (16 июня 2015 г.). Отв ред. Зарайский А.... | | О. В. Бессчетнова : под ред. Г. В. Дыльнова. — Саратов : Научная книга, 2008. — 288 с |
| Для преподавателей, научных работников и студентов, обучающихся по специальности «Социально-культурный сервис и туризм» | | Для преподавателей, научных работников и студентов, обучающихся по специальности «Социально-культурный сервис и туризм» |
| «Педагогика и психология» Пензенского государственного технологического университета О. А. Вагаева | | «Педагогика и психология» Пензенского государственного технологического университета О. А. Вагаева |