Рис. 1. Узагальнена структура ВСРА (gif-анимацiя, 689 x 324 , 5 кадрiв, 5 циклiв, розмiр 141 кб)
Актуальність: у наш час сучасною елементною базою є мікропроцесори в поєднанні з БІС пам'яті і програмованими логічними інтегральними схемами (ПЛІС) або Programmable Logic Devices (PLD), які повинні не тільки задовольняти вимоги широкого кола користувачів, але і враховувати перспективу розвитку засобів обчислювальної техніки. Технологія ПЛІС дозволяє за малий проміжок часу, без використання завершальних технологій реалізувати на кристалі практично будь-який проект цифрового пристрою, маючи у наявності лише персональний комп'ютер та САПР ПЛІС [2]. Реконфігуровану систему на базі ПЛІС широко використовують в багатьох галузях: реконфігурована обробка даних; цифрова обробка сигналів; обробка зображень; комунікації; обчислювальні пристрої загального призначення; верифікація. У тому числі можливість обробки і сортування даних. Тому створення перспективних засобів обчислювальної техніки, не прив'язаних до технологічних ліній виробництва, з можливістю реконфігурованостi, на основі сучасних кристалів ПЛІС представляє актуальну науково-технічну проблему.
Метою даної роботи є розробка реконфігурованої обчислювальної системи для підвищення швидкості сортування даних.
Основні завдання розробки та досліджень. Для досягнення поставленої мети необхідно:
Об'єкт дослідження - реконфігурована сисема на базі ПЛИС.
Предмет дослідження - реалізація сортувальника на основі реконфігурованої системи.
Практичне значення отриманих результатів міститься у розробці реконфігурованої системи, яка буде застосовуватися для сортування даних. За допомогою реалізації даної ідеї можна в десятки разів збільшити швидкість обробки даних.
Основною відмінністю реконфігурованої обчислювальної системи від існуючих обчислювальних платформ є динамічна зміна конфігурації апаратури в процесі роботи платформи, виконання складного динамічного алгоритму. На даний момент основним способом реалізації складних динамічних алгоритмів є розробка комбінованих апаратно-програмних систем. Такі системи включають універсальне апаратне забезпечення, побудоване на базі технологій замовних інтегральних схем, систем на стандартних елементах або базових матричних кристалах. Це апаратне забезпечення надає системний програмний інтерфейс, який використовується потужним програмним забезпеченням, що реалізує логіку складних динамічних алгоритмів [1]. Реконфігурована обчислювальна система має ряд переваг перед комбінованою обчислювальною системою:
Основним логічним елементом реконфігурованої обчислювальної платформи є апаратний обчислювальний процес, що є аналогом програмного процесу. Реконфігурованi системи на базі ПЛИС широко використовуються в багатьох галузях:
ПЛІС - програмувальна логічна інтегральна схема, що поєднує регулярність структури напівпровідникового пристрою, що запам'ятовує з універсальністю мікропроцесора, що дозволяє програмно формувати внутрішній спеціалізований процесор [5]. Структурно ПЛІС являє собою однорідну середу і має властивості: однорідность, паралельность виконання операцій. Паралельність - підвищення швидкодії, досягається за рахунок підвищення тактової частоти і за рахунок паралельного виконання великої кількості операцій. Реконфігурованiсть - надійність, гнучкість і структурна універсальність (можливість створення для кожного завдання відповідної структури) забезпечується апаратно за рахунок програмної зміни зв'язків між елементами і функцій самих елементів. Однорідність - простота технології виготовлення при використанні однакових елементів і однотипних зв'язків між ними.
На сьогоднішній день ПЛІС пройшли шлях від простих елементів ПЛМ (програмовані логічні матриці) до складних ПЛІС - 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]. Обмеження, що накладаються кінцевим об'ємом реконфігурованого обладнання, що не дозволяє отримати прийнятний для практики метод знаходження оптимального рішення. Тому, на сьогодні вирішення (близьке до оптимального) методом послідовних наближень.
Реконфігурація структури включає дві фази. У першому змінюється лише частина, тобто механічне зміна не допускається. Якщо не досягнуто заданий критерій оптимізації, тобто частина не має достатньої логічної потужності та пам'яті, або специфічних засобів введення-виведення інформації, то здійснюється перехід до другої фази. І подальша реконфігурація системи виконується також і механічним способом (шляхом встановлення модулів розширення у відповідні роз'єми - слоти локальної шини материнської плати). Структурна організація реконфігуєму процесорів. Реконфігурованi процесори (РП) є в мінімальній конфігурації друковану плату з розміщеними на ній одним або декількома кристалами для користувача ПЛІС (ППЛІС), незалежної пам'яті для зберігання файлів конфігурації, елементами завантаження конфігураційного файлу (файлів) і одним або декількома роз'ємами для підключення зовнішніх пристроїв ( модулів розширення). Тип незалежній пам'яті визначається областю застосування РП: для динамічного конфігурування ППЛІС в процесі функціонування доцільно використовувати Flash - пам'ять, а за відсутності такої необхідності - ППЗУ. Використання Flash - пам'яті передбачає наявність у складі РП блоку управління цією пам'яттю, що реалізує завантаження цієї пам'яті файлами конфігурації з зовнішнього джерела, а також читання з довільною вибіркою необхідного файлу та його завантаження.
Під сортуванням розуміється процес перегрупування заданого масиву даних у деякому певному порядку. Як міру ефективності реалізації алгоритму сортування звичайно приймають число необхідних порівнянь і число пересилань (перестановок) елементів. У загальному випадку, ці значення визначають функцію від N - числа сортируемих елементів, тобто глибину масиву. Прямі методи сортування вимагають порядку x'2 порівнянь елементів. При апаратної реалізації алгоритмів сортування на основі ПЛИС необхідно враховувати обмеження на логічні ресурси кристалів для заданих параметрів процесу сортування. Є два варіанти ПЛІС - реалізації сортування - лінійний сортувальник і сортувальник на основі пам'яті [1].
Відомо, що найбільш швидкодіючими реалізаціями алгоритмів є табличні (на основі пам'яті). При цьому необхідно задіяти великий обсяг пам'яті, що є основним обмеженням для табличної реалізації. Проте, наявність внутрішньої пам'яті в кристалах ПЛИС, в рамках обмежень на наявний обсяг пам'яті, дозволяє використовувати ці кристали для таблично - алгоритмічної реалізації сортування. Варіант реалізації сортування, що базується на використанні оперативної пам'яті (НАМ). Обсяг НАМ залежить від обсягу сортіруемимі масиву, а витрачаються логічні ресурси блоку управління - відповідно від обсягу КАМ.
Наявність в даний час недорогий НАМ досить великих обсягів і з високою швидкодією дозволяє реалізувати апаратну сортування для вирішення багатьох практичних завдань. При цьому для ряду завдань пам'ять і блок управління сортуванням можуть бути розміщені в тому ж кристалі ПЛИС, в якому знаходяться логічні блоки, що реалізують саму задачу [8]. Недоліком пристроїв сортування, реалізованих на основі пам'яті, є зайві апаратні витрати на саму пам'ять, тому що в процесі сортування використовується не повний обсяг пам'яті. Такі структури є досить швидкодіючими і не потребують складних алгоритмічних перетворень.
Час сортування масивів на вхідному етапі визначається довжиною масиву, а на вихідний, крім безпосередньо зчитування вихідного відсортовані масиву, також часом холостого читання пам'яті (осередків, адреси яких відповідають значенням елементів сортіруемимі масиву, зміст яких пусто). Головною перевагою таких ПЛІС - структур є можливість створювати спеціалізовані структури під конкретні вимоги та завдання за рахунок властивості реконфігуєму.
Лінійний сортувальник має постійне час сортування, яке визначається довжиною масиву. Апаратна реалізація такого пристрою виправдана у разі розміщення у кристалі ПЛІС автономного пристрою, або в сукупності з іншими пристроями.
Створення реконфігурованих пристроїв на основі сучасних кристалів ПЛІС для обчислювальних систем з можливістю реконфігурованостi при наявності відкритої бібліотеки файлів конфігурації дозволить за короткий проміжок часу реалізувати в кристалах новітні розробки. Об'єктом дослідження в даній області є обчислювальні системи з реконфігурована (програмованої) архітектура, що забезпечуе:
Реконфігурованi системи знайдуть широке застосування в наступних програмах:
Реалізація сортувальників за допомогою реконфігурованих систем найбільш перспективна ідея, яка дозволить в десятки разів збільшити швидкість обробки даних.