Рис. 1. Обобщённая структура ВСРА (gif-анимация, 689 x 324 , 5 кадров, 5 циклов, размер 141 кб)
Актуальность: В настоящее время современной элементной базой являются микропроцессоры в сочетании с БИС памяти и программируемыми логическими интегральными схемами (ПЛИС) или Programmable Logic Devices (PLD), которые должны не только удовлетворять требованиям широкого круга пользователей, но и учитывать перспективу развития средств вычислительной техники. Технология ПЛИС позволяет за короткий промежуток времени, без использования финишных технологий, реализовать в кристалле практически любой проект цифрового устройства, имея в наличии лишь персональный компьютер и САПР ПЛИС [2]. Реконфигурируемые системы на базе ПЛИС широко используются во многих областях: реконфигурируемая обработка данных; цифровая обработка сигналов; обработка изображений; коммуникации; вычислительные устройства общего назначения; верификация. В том числе возможность обработки и сортировки данных. Поэтому создание перспективных средств вычислительной техники, не привязанных к технологическим линиям производства, с возможностью реконфигурируемости, на основе современных кристаллов ПЛИС представляет актуальную научно-техническую проблему.
Целью данной работы является разработка реконфигурируемой вычислительной системы для повышения скорости сортировки данных.
Основные задачи разработки и исследований. Для достижения поставленной цели необходимо:
Объект исследований: реконфигурируемые сисема на базе ПЛИС.
Предмет исследования: реализация сортировщика на основе реконфигурируемой системы.
Практическое значение полученных результатов содержится в разработке реконфигурируемой системы, которая будет применяться для сортировки данных. С помощью реализации данной идеи можно в десятки раз увеличить скорость обработки данных.
Основным отличием реконфигурируемой вычислительной системы от существующих вычислительных платформ является динамическое изменение конфигурации аппаратуры в процессе работы платформы, выполнения сложного динамического алгоритма.
На данный момент основным способом реализации сложных динамических алгоритмов является разработка комбинированных аппаратно-программных систем. Такие системы включают универсальное аппаратное обеспечение, построенное на базе технологий заказных интегральных схем, систем на стандартных элементах или базовых матричных кристаллах. Это аппаратное обеспечение предоставляет системный программный интерфейс, который используется мощным программным обеспечением, реализующим логику сложных динамических алгоритмов[1].
Реконфигурируемая вычислительная система имеет ряд преимуществ перед комбинированной вычислительной системой:
Основным логическим элементом реконфигурируемой вычислительной платформы является аппаратный вычислительный процесс, являющийся аналогом программного процесса. Реконфигурируемые системы на базе ПЛИС широко используются во многих областях:
ПЛИС - программируемая логическая интегральная схема, сочетающая регулярность структуры полупроводникового запоминающего устройства с универсальностью микропроцессора, позволяющая программно формировать внутренний специализированный процессор [5]. Структурно ПЛИС представляют собой однородную среду и обладают свойствами: однородности, реконфигурируемости и параллельности выполнения операций. Параллельность - повышение быстродействия, достигается за счет повышения тактовой частоты и за счет параллельного выполнения большого числа операций. Реконфигурируемость - надежность, гибкость и структурная универсальность (возможность создания для каждой задачи соответствующей структуры) обеспечиваются аппаратно за счет программного изменения связей между элементами и функций самих элементов. Однородность - простота технологии изготовления при использовании одинаковых элементов и однотипных связей между ними.
На сегодняшний день ПЛИС прошли путь от простых элементов ПЛМ (программируемые логические матрицы) до сложных ПЛИС - CPLD (Complex Programmable Logic Devices) и FPGA (Field Programmable Gate Array). Доступны кристаллы Virtex-II-Pro фирмы Xilinx емкостью до 10 миллионов системных вентилей, которые имеют огромное преимущество в логической емкости над предыдущими кристаллами FPGA. В течение ближайших трех - четырех лет будут предложены устройства с емкостью 50 миллионов системных вентилей - достаточную логику, чтобы формировать сложные, высокоэффективные системы на одном кристалле [7].
Существенным преимуществом ПЛИС является их универсальность и возможность быстрого программирования (конфигурирования) под заданный проект. Наличие исключительно удобных для разработчика средств автоматизации проектирования позволяет быстро и эффективно осуществить разработку, верификацию и отладку проекта на одном рабочем месте, используя в качестве основного технического средства PC или рабочую станцию.
Возможность многократного перепрограммирования (конфигурирования) позволяет вносить изменения в уже готовое, функционирующее изделие или использовать это изделие для выполнения различных функций в зависимости от загруженного проекта.
В настоящее время под руководством А.В. Палагина ведутся работы по созданию компьютерной системы с реконфигурируемой (виртуальной) архитектурой, которая представляет собой проблемно - ориентированные конфигурации применительно к каждой конкретной задаче[1]. Структура реконфигурируемой системы состоит из 2-х частей:
Оборудование V также подразделяется на две части: "стандартную" часть , которая подключается к F через стандартные шины host компьютера и представлена материнской платой с локальной внутренней шиной для подключения "нестандартной" части , представляющей собой широкий набор модулей расширения. Операции, выполняемые в каждой из частей, определяются следующими характеристиками: в F - временем вычислений и исходными данными; в V - также дополнительным оборудованием, необходимым для выполнения соответствующих операций, временем передачи информации между вычислительными модулями и временем реконфигурации системы (загрузки soft cores в кристаллы ПЛИС).
В данной системе конфигурация формируется таким образом, чтобы перенести основную работу с F - части системы на специализированные блоки (V - часть), которые представляют собой soft cores. Для строго сформулированной вычислительной задачи (где однозначно определены все численные процедуры) и описания характеристик операций для F и V требуется организовать общую структуру ( ) и распределить вычисления таким образом, чтобы минимизировать целевую функцию (сумма стоимостей реконфигурации и времени вычислений) [4].
Данная проблема является исключительно сложной, по существу это комбинаторная задача оптимального синтеза [4]. Ограничение, накладываемое конечным объемом реконфигурируемого оборудования, не позволяет получить приемлемый для практики однозначный метод нахождения оптимального решения. Поэтому, находится решение (близкое к оптимальному) методом последовательных приближений.
Реконфигурация структуры включает две фазы. В первой изменяется лишь часть , т.е. механическое изменение не допускается. Если не достигнут заданный критерий оптимизации, то есть часть не имеет достаточной логической мощности и памяти, либо специфических средств ввода-вывода информации, то осуществляется переход ко второй фазе. И дальнейшая реконфигурация системы выполняется также и механическим способом (путем установки модулей расширения в соответствующие разъемы - слоты локальной шины материнской платы).
Структурная организация реконфигурируемых процессоров. Реконфигурируемые процессоры (РП) представляют собой в минимальной конфигурации печатную плату с размещенными на ней одним или несколькими кристаллами пользовательских ПЛИС (ППЛИС), энергонезависимой памяти для хранения файлов конфигурации, элементами загрузки конфигурационного файла (файлов) и одним или несколькими разъемами для подключения внешних устройств (модулей расширения). Тип энергонезависимой памяти определяется областью применения РП: для динамического конфигурирования ППЛИС в процессе функционирования целесообразно использовать Flash - память, а при отсутствии такой необходимости - ППЗУ. Использование Flash - памяти предполагает наличие в составе РП блока управления этой памятью, реализующего загрузку этой памяти файлами конфигурации из внешнего источника, а также чтения с произвольной выборкой требуемого файла и его загрузки.
Под сортировкой понимается процесс перегруппировки заданного массива данных в некотором определенном порядке. В качестве меры эффективности реализации алгоритма сортировки обычно принимают число необходимых сравнений и число пересылок (перестановок) элементов. В общем случае, эти значения определяют функцию от N - числа сортируемых элементов, т.е. глубину массива. Прямые методы сортировки требуют порядка x'2 сравнений элементов. При аппаратной реализации алгоритмов сортировки на основе ПЛИС необходимо учитывать ограничения на логические ресурсы кристаллов для заданных параметров процесса сортировки. Есть два варианта ПЛИС - реализации сортировки - линейный сортировщик и сортировщик на основе памяти[1].
Известно, что наиболее быстродействующими реализациями алгоритмов являются табличные (на основе памяти). При этом необходимо задействовать большой объем памяти, что является основным ограничением для табличной реализации. Однако, наличие внутренней памяти в кристаллах ПЛИС, в рамках ограничений на имеющийся объем памяти, позволяет использовать эти кристаллы для таблично-алгоритмической реализации сортировки. Вариант реализации сортировки, основанный на использовании оперативной памяти (НАМ). Объем НАМ зависит от объема сортируемого массива, а затрачиваемые логические ресурсы блока управления - соответственно от объема КАМ.
Наличие в настоящее время недорогой НАМ достаточно больших объемов и с высоким быстродействием позволяет реализовать аппаратную сортировку для решения многих практических задач. При этом для ряда задач память и блок управления сортировкой могут быть размещены в том же кристалле ПЛИС, в котором находятся логические блоки, реализующие саму задачу [8]. Недостатком устройств сортировки, реализованных на основе памяти, является излишние аппаратные затраты на саму память, так как в процессе сортировки используется не полный объем памяти. Такие структуры являются довольно быстродействующими и не требуют сложных алгоритмических преобразований.
Время сортировки массивов на входном этапе определяется длиной массива, а на выходном, кроме непосредственно считывания выходного отсортированного массива, также временем холостого чтения памяти (ячеек, адреса которых соответствуют значениям элементов сортируемого массива, содержание которых пусто). Главным преимуществом таких ПЛИС - структур является возможность создавать специализированные структуры под конкретные требования и задачи за счет свойства реконфигурируемости.
Линейный сортировщик имеет постоянное время сортировки, определяемое длиной массива. Аппаратная реализация такого устройства оправдана в случае размещения в кристалле ПЛИС автономного устройства, либо в совокупности с другими устройствами.
Создание реконфигурируемых устройств на основе современных кристаллов ПЛИС для вычислительных систем с возможностью реконфигурируемости при наличии открытой библиотеки файлов конфигурации позволит за короткий промежуток времени реализовать в кристаллах новейшие разработки. Объектом исследования в данной области являются вычислительные системы с реконфигурируемой (программируемой) архитектурой, обеспечивающие:
Реконфигурируемые системы найдут широкое применение в следующих приложениях:
Реализация сортировщиков с помощью реконфигурируемых систем наиболее перспективная идея, которая позволит в десятки раз увеличить скорость обработки данных.