Математическая морфология.
Электронный математический и
медико-биологический журнал. - Т. 9. -
Вып. 4. - 2010. - URL:
http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM
http://www.smolensk.ru/user/sgma/MMORPH/N-28-html/TITL-28.htm
http://www.smolensk.ru/user/sgma/MMORPH/N-28-html/cont.htm
УДК 681.322
РЕАЛИЗАЦИЯ
МНОГОКООРДИНАТНОЙ АССОЦИАТИВНОЙ СРЕДЫ НА ОСНОВЕ ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ СХЕМ
Ó 2010 г. Борисов
В. В., Полячков А. В.
В
работе проведен анализ структур многокоординатной ассоциативной среды (МКАС) и
программируемых логических схем типа Field-Programmable Gate
Array (FPGA). Для
оптимального размещения структуры МКАС на матрице FPGA предложено выполнить декомпозицию ассоциативных ячеек МКАС
на элементы, позволяющие оптимально использовать структуру FPGA. Такая структура имеет большую регулярность за счет использования
элементов одной сложности.
Ключевые слова: многокоординатная ассоциативная среда, программируемая логическая
схема
Возможности совершенствования
вычислительной техники и систем обработки информации, базирующиеся, во многом,
на основополагающих принципах, предложенных Ч. Бэббиджем и Дж. фон Нейманом,
практически исчерпаны. Причем, проблемы, возникшие вследствие заложенных еще на
ранних этапах развития вычислительной техники противоречий, характерны как для
отдельных вычислительных машин, так и для распределенных вычислительных комплексов,
сетей и систем. К данным противоречиям относится, во-первых, разделение функций
управления, хранения и обработки информации, во-вторых, иерархичность
построения отдельных компонентов и систем в целом. Неизбежным следствием этого
является расходование значительных вычислительных и коммуникационных ресурсов
на информационный обмен между элементами систем.
Одним из направлений развития средств
вычислительной техники можно считать использование ассоциативных методов и
средств коллективного доступа к информации с совмещением функций хранения и
обработки информации. К таким подходам относится использование ассоциативных
сред и, прежде всего, многокоординатных ассоциативных сред (МКАС) [1]. Преимущества
ассоциативных сред проявятся только при ее аппаратной реализации.
Известно,
что одним из способов реализации высокоэффективных вычислительных устройств и
систем является применение методов и средств программируемой логики, матричных
программируемых схем – Field-Programmable Gate Array (FPGA). На основе FPGA можно реализовать вычислительное устройство практически
любой сложности. Однако существует проблема рационального использования ресурсов
FPGA для достижения высокого быстродействия.
Поэтому
реализация МКАС на основе программируемых логических интегральных схем (ПЛИС)
требует проведения исследований, на основании которых следует определить
оптимальное сочетание возможностей FPGA и потенциала MKAC.
Очевидно,
что структура МКАС и структура ПЛИС не эквивалентны друг другу:
·
емкость логических элементов
и структур FPGA и МКАС различная;
·
схемотехника элементов,
составляющих МКАС и FPGA, также не соответствуют друг
другу;
·
топология размещения и
сопряжения элементов их структур может различаться.
Рассмотрим
особенности структур и элементов FPGA и МКАС.
В
настоящее время основными производителями FPGA
являются фирмы XILINX [2] и ALTARA [3]. И, если на первом
этапе развития программируемых схем структуры FPGA
обоих производителей сильно отличались, то в настоящее время в результате
эволюции, когда в структуры вносились изменения, подтвержденные практикой их
применения, имеется больше сходных структурных и функциональных решений, чем
оригинальных.
Структура
современной FPGA (см. рисунок 1) представляет собой матрицу программируемых
логических элементов, окруженную по периферии элементами ввода-вывода.
Программируемая
матрица состоит из программируемых логических элементов, организованных в
логические блоки. Эти блоки соединяются между собой и элементами ввода-вывода
матрицей соединений (коммутационной матрицей).
У
каждого из производителей собственная схемотехника логических блоков. Матрицы
соединений также имеют различия в назначении, числе линий, способах коммутаций.
Однако эти различия в настоящее время уже не являются принципиальными с точки
зрения реализации ассоциативной среды.
У фирмы XILINX основной элемент матрицы – конфигурируемый
логический блок (КЛБ) (Configurable Logic Blocks – CLB) (см. рисунок 2).
Блок КЛБ состоит из двух секций (Slices), одна из которых базовая, а
другая – с расширенными возможностями в виде одного из 2-х вариантов: с
возможностью каскадирования с соседними частями и коммутации этих соединений; с
возможностью конфигурирования в блок памяти емкостью 64 бит.
Возможностью конфигурации в блоки памяти обладают не все секции, а
только часть из них.
В новых разработках добавлены секции, которые имеют реализованные
умножители, и предназначенные для использования при проектировании устройств
цифровой обработки сигналов (DSP Slice).
Переключение в один из возможных режимов обеспечено за счет настройки
(конфигурирования) встроенных в секции КЛБ узлов, называемых Logic-function generators (или look-up tables, LUTs), представляющих собой несколько
вариантов реализации схемотехники логических узлов, заданных в форме таблиц или
логических карт.
Такое
кажущееся усложнение схемотехнических решений вызвано потребностью минимизации
количества элементов настройки FPGA путем использования «заготовок» схемотехнических узлов,
оптимизированных под конкретные реализации. Из таких «кубиков», путем их
настройки и коммутирования между собой и с матрицей соединений FPGA, проектируется требуемое устройство.
Фирма ALTERA называет
основной структурный элемент логической матрицы блоком (Logic Array Block – LAB) (см. рисунок 3).
ALM
Каждый из
логических блоков матрицы состоит из 10 адаптивных логических модулей (Adaptive Logic Modules – ALMs). Каждый модуль имеет 8 входов
и один функциональный выход. Такой логический модуль также содержит конфигурируемые
узлы (LUTs). У этого
производителя также существуют типовые настройки блоков, а часть блоков может
конфигурироваться в блоки памяти. Такие блоки именуются как блоки памяти MLAB.
Как можно
заметить, основные структурные составляющие логической матрицы FPGA разных
производителей имеют и отличия в конкретных реализациях, называемых секциями
или модулями. По своим функциональным возможностям, относительно применению
FPGA для реализации ассоциативной среды все структуры можно считать схожими.
Что
касается периферийных элементов ввода-вывода, то их структура диктуется общими
принципами организации интерфейсов вычислительных систем. Поэтому часть элементов
ввода-вывода может конфигурироваться для дискретных связей, а часть отводится
под высокопроизводительные интерфейсы. Имеются готовые контроллеры этих интерфейсов,
реализованные как встроенные блоки в структуре FPGA.
Под
МКАС понимается определенным образом организованная совокупность множеств
упорядоченных ассоциативных ячеек в многокоординатном пространстве, обладающих
свойствами накопления, хранения, анализа, преобразования и обмена информацией.
Основным
элементом МКАС является ассоциативная ячейка (АЯ). Ассоциативные ячейки группируются
в многокоординатном пространстве в зависимости от топологии и направлений
доступа для реализации различных операций. Пространство МКАС может быть 2-мерным,
3-х мерным, а также эмулировать большее число измерений за счет числа
направлений доступа к АЯ при выполнении ассоциативных преобразований. В [1]
подробно рассматриваются различные варианты структур МКАС.
Для
размещения МКАС на FPGA требуется:
·
реализовать АЯ в блоках FPGA;
·
отобразить сложную структуру
МКАС на двумерную структуру FPGA.
На рисунке 4 представлена
структура базовой ассоциативной ячейки многокоординатной ассоциативной среды.
Она состоит из элемента анализа входной информации (ЭВХ); элемента памяти (ЭП);
элемента взаимодействия хранимой и поступающей в ячейку информации (ЭВЗ); элементов
ассоциативного сравнения (ЭС1, …, ЭСL, L определяется числом возможных направлений ассоциативного
доступа); элемента фиксации результатов ассоциативного сравнения (ЭФ); элементов
управления записью (ЭУЗ), хранением (ЭУХ), взаимодействием хранимой и
поступающей в ячейку информации (ЭУВ), ассоциативным сравнением (ЭУС). На схеме
показаны сигналы: информационные входы – Dвх;
информационные выходы – Dвых; группа синархических входов – DCвх; синархические выходы – DСвых;
входы групп ассоциативного сравнения – AСвх;
выходы групп ассоциативного сравнения – AСвых;
входы управления –Упр.
Такая ассоциативная ячейка
может выполнять функции: записи, хранения и считывания информации; различные
режимы ассоциативного опроса, поиска и сравнения, как в сложно организованном
пространстве ассоциативной среды.
Элемент памяти базовой
ассоциативной ячейки предназначен для хранения информации. Его разрядность может
выбираться достаточно большой. Увеличение разрядности позволяет наращивать
функциональные возможности обработки информации внутри ячейки. Тем не менее,
представляется предпочтительным ограничить функциональные и вычислительные возможности
отдельных ассоциативных ячеек. В этом случае предполагается использование
ассоциативной среды, состоящей из относительно простых по структуре элементов,
имеющих в своем составе элементы памяти с относительно малой разрядностью.
Элемент анализа входной
информации обеспечивает запись данных в элемент памяти ячейки. Это может быть традиционная
запись либо реализация различных гибких правил записи. В данном случае
предполагается реализация относительно простых правил управления записью.
Узел взаимодействия
хранимой и поступающей в ячейку информации позволяет выполнять различные вычислительные
и нечисловые операции.
Элементы сравнения
предназначены для сравнения хранимой и поступающей в ассоциативную ячейку
информации в соответствии с заданным критерием, например, по критерию «равно».
Внутренние обратные связи
ячейки позволяют говорить о наличии устойчивых состояний ячейки в целом. Однако
их использование при функционировании требует дополнительных мер по
синхронизации работы элементов и исследования процесса «гонок» в ассоциативной
среде.
Анализ структурных и
функциональных особенностей ассоциативной среды, организованной из рассмотренных
ассоциативных ячеек, позволяет сформулировать ряд проблем, возникающих при ее
реализации на основе FPGA.
1) Непосредственная
реализация ассоциативных ячеек требует использования практически целиком
логических блоков, а не отдельных логических элементов FPGA.
2) Внешнее управление
режимами работы ассоциативных ячеек требует дополнительных ресурсов для его
осуществления.
3) Связи между ассоциативными
ячейками среды являются фиксированными и обусловлены топологией среды и направлениями
ассоциативного доступа.
4) Наличие отдельных
функциональных узлов и внутренних обратных связей в ассоциативных ячейках усложняет
процесс переключений состояний и приводит к проблеме несинхронности при выполнении
различных режимов.
5) Для каждого из функциональных
узлов ассоциативной ячейки локальные сигналы управления формируются индивидуальными
элементами управления, число которых избыточно.
Для решения указанных
проблем предлагается способ организации ассоциативной среды на основе принципа
декомпозиции ассоциативной среды, состоящей из ассоциативных ячеек, до уровня элементов
ячеек, выполняющих отдельные функции. На данном уровне декомпозиции ассоциативной среды выделяются элементы памяти (ЭП), взаимодействия (ЭВЗ), сравнения
(ЭС).
Данные
элементы ячеек среды могут быть объединены в отдельные блоки, а именно, в блоки
памяти (БП), взаимодействия (БВЗ) и сравнения (БС), соответственно.
Могут
быть предложены различные правила объединения соответствующих элементов
ассоциативных ячеек в указанные выше блоки, например, правила объединения соответствующих
элементов в зависимости от:
·
«смежности» элементов;
·
направлений параллельного
доступа с элементам;
·
взаимосвязей между
ассоциируемыми информационными объектами.
На рисунке 5
представлен пример объединения элементов взаимодействия ассоциативных ячеек
среды в блок взаимодействия в зависимости от «смежности» элементов.
В ассоциативной среде также
можно осуществить декомпозицию взаимосвязей между ассоциативными ячейками на
взаимосвязи между их элементами, после чего выполнить их группировку в
зависимости от:
·
источников формирования
сигналов;
·
приемников сигналов.
Таким образом, в
ассоциативной среде можно выделить «группировки» не только ассоциативных ячеек,
но и составляющих их элементов (как однородных, так и разнородных), гибко
объединяемых и настраиваемых для решения конкретных задач.
На рисунке 6 приведен пример
организации ассоциативной среды с поэлементной детализацией ассоциативных ячеек.
Следует отметить, что подобная организация ассоциативной среды сохраняет
представление среды как упорядоченных совокупностей ассоциативных ячеек, так и
в виде наборов блоков (БП, БВЗ, БС), состоящих из совокупностей соответствующих
элементов и «коммуникаций» между этими элементами (наборы линий ассоциативного
сравнения (АС); информационных сигналов (DC)).
Особенностью предлагаемой
декомпозиции ассоциативной среды является ее соответствие представлению уровню
логических элементов FPGA (CLB
и ALM), при этом сохраняются особенности организации и функционирования
ассоциативной среды в виде совокупностей ассоциативных ячеек. В дополнение к
этому, структура ассоциативной среды относительно элементов ассоциативных ячеек
является однородной. По сложности реализации один элемент ассоциативной ячейки приблизительно
соответствует одному элементу CLB FPGA фирмы XILINX и двум ALM FPGA фирмы ALTERA. А при усложнении организации структуры ассоциативной
среды (усложнения взаимосвязей между ячейками) элементы памяти будут составлять
меньшую долю по сравнению с элементами сравнения, что приведет к уменьшению
требуемого ресурса матрицы FPGA.
За рамками данной статьи остаются вопросы отображения
ассоциативной среды различной организации (пространства среды и правил взаимодействия
между ассоциативными ячейками) на несколько матриц FPGA в единой системе.
Другой важной задачей является организация
сопряжения ассоциативной среды, реализованной на FPGA, с различными вычислительными системами.
Для этого могут использоваться встроенные в FPGA контроллеры типовых интерфейсов. Варианты
решений по сопряжению должны рассматриваться с учетом особенностей задач, решаемых
в ассоциативной среде.
литература
1. Огнев И.В., Борисов В.В. Ассоциативные
среды. – М.: Радио и связь, 2000.
2. www.xilinx.com официальный сайт XILINX
3. www.altera.com официальный сайт ALTERA
REALIZATION OF MULTI-COORDINATE ASSOCIATIVE MEDIUM ON
THE BASE OF PROGRAMMED LOGIC SCHEMES
Borisov V.V., Polyachkov A.V.
The analysis of structures of
Multi-Coordinate Associative Medium (MCAM) and programmed logic schemes of type
FPGA (Field-Programmable Gate Array) is implemented. For optimum placing of
structure MCAM on matrix FPGA it is offered to divide associative cell МCАM into components. The components
of an associative cell named an associative element, allow to use structure
FPGA optimum. Such structure has the big regularity at the expense of use of elements
of one complexity.
Key words:
Multi-Coordinate
Associative Medium, programmed logic scheme.
Борисов Вадим Владимирович,
д.т.н., профессор,
vborisov@etna-it.ru
Полячков Александр Владимирович,
к.т.н., доцент,
polyachkov.sml@mail.ru
Кафедра вычислительной техники
Филиал ГОУ ВПО «МЭИ (ТУ)» в г. Смоленске
Smolensk Branch of a Moscow Power
Engineering Institute (Technical University)
Поступила в редакцию 27.11.2010.