VHDL як алгоритмічна мова для опису паралельних алгоритмів
Опубліковано в ж. Електронне Моделювання. 2009 р.
А.М.Сергієнко, канд. техн. наук,
Національний технічний університет України “КПІ”, Київ,
03056, пр.Перемоги, 37
тел.: 4549337
E-mail: aser@comsys.kpi.ua
Анотація
В статті розглянуті основні властивості мови VHDL з точки зору її придатності для опису паралельних алгоритмів для їх подальшого відображення в паралельні обчислювальні системи.
1. Вступ
Звичайна мова програмування це послідовна мова. Вона відображає, по-перше, послідовний порядок виконання операцій у звичайній ЕОМ, по-друге, послідовний характер мислення програміста, який нею користується. Разом з розвитком паралельних обчислювальних систем (ОС) широкого призначення розвивались і універсальні мови програмування, такі як Сі, Фортран, Паскаль, Кобол в напрямку появи паралельних версій. Так, мова Fortran була розширені до мов Fortran D, Vienna Fortran, High Performance Fortran (HPF) і остання мова стала стандартом мови паралельного програмування.
Розширення мови Фортран велось в напрямку декларування типів даних і вказівок компілятору, які спрощували і підвищували ефективність розпаралелювання програми. При цьому програміст повинен в переважній більшості випадків використовувати модель SPMD (Single Program – Multiple Data), коли один і той самий фрагмент програми розміщений в кожному процесорному вузлі, а компілятор повинен вирішити задачу забезпечення обміну даними між цими вузлами.
При паралельній реалізації алгоритму він розділяється на підзадачі, які виконуються паралельно і через деякі проміжки часу обмінюються даними. Середня довжина цього проміжку часу називається зернистістю паралелізма виконання алгоритму. Якщо обмін даними між підзадачами виникає досить рідко (приблизно менше ніж один раз на 10000 виконаних команд), то це грубозернистий паралелізм, а якщо часто (один раз на 1-100 виконаних команд) – то це вважається дрібнозернистим паралелізмом. Існує велика множина алгоритмів, які для свого ефективного паралельного виконання потребують саме дрібнозернистий паралелізм. Це насамперед періодичні алгоритми зі щільними міжітерацийними зв’язками, до яких відносяться алгоритми обробки сигналів, зображень, вирішення задач з частковими похідними тощо.
Всі версії паралельного Фортрану використовують гнізда циклів для неявного задання паралелізму задачі. При цьому компілятор повинен вирішити складну задачу виявлення можливості паралельного обчислення ітерацій циклів і розподілити ці ітерації по процесорах ОС. Більшість спланованих компілятором міжпроцесорних обмінів є обміном повідомленнями, або обміном через загальні змінні. Застосування, написані на паралельному Фортрані, найбільш ефективно виконуються зараз на симетричних мультипроцесорах і кластерах таких процесорів, в яких обмін через загальні змінні виконується за 50,…,500 і більше тактів процесора, тобто в ОС виконується середнє- та грубозернистий паралелізм.
Як результат, програмування паралельних алгоритмів ( внаслідок того, що паралелізм заданий неявно ) приводить до невисокої завантаженості процесорних елементів у випадку дрібнозернистого паралелізму.
Мова Ада була розроблена в 1983 році спеціально для програмування паралельних задач. Але за різних причин, ці властивості паралельного програмування ніколи не були широко застосовані на практиці. Це було пов’язано з тим, що Ада вимагала великих накладних витрат на обробку переривань, за допомогою яких підзадачі обмінювались даними, особливо у випадку доступу до загальних ресурсів. Покращання, впроваджені в Аді 95, дозволили розробляти застосування від простих періодичних алгоритмів до складних керуючих надійних систем, таких як, системи керування польотами, залізничним транспортом, ракетами. Але все ще високі накладні витрати по організації керування доступом до загальних змінних не дозволяють використовувати Аду для програмування обчислень з дрібнозернистим паралелізмом, на які мають бути орієнтовані ОС. Наприклад, для задач мультимедіа.
У зв’язку з вищесказаним, є важливим впровадження нових ефективних мов паралельного програмування, які б у більшій мірі відображали особливості предметної галузі. Їхні конструкції повинні мати ефективне відображення в архітектуру ОС. Також ці мови повинні забезпечувати переносимість створюваного матзабезпечення.
Мова паралельного програмування повинна, з одного боку, забезпечувати користувача-програміста звичною і зручною програмною моделлю, з другого боку, алгоритм, описаний цією мовою повинен мати нескладне і ефективне відображення в архітектуру цільової ОС і мати властивість переносимості між ОС з неоднаковою архітектурою. З цієї точки зору перспективною моделлю ОС є модель з віртуальною топологією. Застосовуючи таку модель, програміст складає програму для віртуальної структури ОС, а компілятор відображає цю програму, в якій явно задана віртуальна структура, в структуру конкретної ОС.
Останнім часом набуває поширення розробка ОС з програмованою архітектурою (Configurable Computer). Поява програмованих логічних інтегральних схем (ПЛІС) з об’ємом до 1 млн. вентилів і більше ( таких як Xilinx Virtex ) дала потужний поштовх для розвитку цього напрямку. Слід зауважити, що ОС з програмованою архітектурою найбільш відповідає задачі відображення програм для віртуальної топології.
Мова VHDL була розроблена в Міністерстві оборони США на початку вісімдесятих років як мова для опису моделей апаратних засобів обчислювальної техніки (Hardware Description Language). В середині вісімдесятих років виробився особливий стиль написання програм, так званий стиль синтезу. Алгоритм, описаний стилем синтезу може бути відображений в конкретну логічну схему за допомогою компілятора-синтезатора логічних схем. Такі компілятори-синтезатори набули широкого розповсюдження в наш час як невід’ємна складова САПР для ПЛІС та замовлених НВІС. Найбільш відомими компіляторами – синтезаторами є Synopsys фірми Synopsys, Synplify фірми Synplicity, Leonardo фірми Exemplar, Metamor фірми Metalogic.
Відображення алгоритму на VHDL в логічну схему є взаємно однозначним і ін’єктивним, причому досягається найбільш високий ступінь розпаралелювання обчислень. Крім того, алгоритм на VHDL може відображати всі тонкі властивості обчислювального алгоритму, такі, як точно задана розрядність вхідних і проміжних даних, пряма логічна обробка бітів операндів, які неможливо безпосередньо відобразити засобами інших алгоритмічних мов. Це означає, що структура, одержана в результаті синтезу відображає всі особливості початкового паралельного алгоритму.
Особливістю алгоритму, описаному на VHDL стилем для синтезу є те, що він, як правило, може бути без змін відображений в декілька різних програмованих обчислювальних середовищ – ними є ПЛІС, які мають різну технологію і архітектуру. Таким чином, алгоритм на VHDL є переносимим між різними обчислювальними середовищами.
Основою технології програмування ОС з програмованою архітектурою є відображення алгоритмів на мові VHDL в логічну структуру, яка занурюється в ПЛІС. В той час, коли більшість сучасних паралельних ОС не забезпечують гідної реалізації дрібнозернистого паралелізму періодичних алгоритмів з локальними зв’язками, застосування з програмованою ОС може бути ефективним вирішенням проблеми реалізації дрібнозернистого паралелізму.
З вищесказаного можна зробити висновок, що мову VHDL слід вивчити з точки зору застосування для опису і відображення періодичних алгоритмів з локальними зв’язками. При цьому властивості мови VHDL, які відображають особливості моделювання в часі дискретних об’єктів, розглядатися не будуть.
2. Послідовні оператори в VHDL
Як в будь-якій алгоритмічній мові, обчислення, які виконуються в послідовному порядку, в VHDL задаються ланцюгом послідовних операторів. Найбільш поширеним оператором є оператор присвоювання. Цей оператор присвоює змінній значення виразу, який є операцією над групою інших змінних, а також констант, наприклад:
z:= y+1.97*yn.
Існує велика кількість наперед визначених типів змінних і констант, таких, як скаларні типи: біт, ціле, дійсне, множина; структурні типи: вектор, масив, запис; динамічні типи. Є великі можливості встановлення типів і підтипів користувача.
Зміна послідовності виконання операторів виконується операторами керування. До них відносяться логічні оператори if-then-elsif-else; оператор вибору case; оператори циклу loop, while-loop, for-loop, та інші. Особливим оператором, який нічого не виконує, але необхідний для встановлення синхронізації є оператор null. Відсутність операторів типу go-to сприяє широкому застосуванню структурного стилю програмування мовою VHDL.
Як і в будь-якій мові, процедура є важливим елементом мови VHDL. Дозволяється будь-який ступінь вкладеності процедур, які оперують змінними. Параметри процедури можуть бути як фактичними, так і побічними.
Широке застосування в VHDL знайшла функція, як особливий тип процедури, призначеної для обчислення одного значення. Взаємне перетворення типів змінних виконується, в основному, за допомогою функції. Функції використовуються як узагальнена форма операторів над змінними. Широко розповсюджене перекриття операторів, функцій і процедур (overloading) коли визначена тепер функція виконується замість визначеної раніше функції (оператора, процедури), яка має ту саму назву.
3. Процес як основна одиниця паралельних обчислень
Всі ланцюжки послідовних операторів в VHDL згруповані в процеси. Процеси можуть виконуватись незалежно і паралельно. Кожен ланцюжок операторів в процесі, як правило, закінчується операторами очікування wait на зовнішню подію. Таким чином, в процесі виконуються послідовно всі оператори і виконання закінчується на операторі wait. Як тільки зовнішня подія, яку визначає оператор wait, відбудеться, виконання операторів в процесі продовжується і після останнього оператора виконується перший оператор процесу.
Процес можна уявити як аналог процедури. При цьому подія, яку фіксує оператор wait, виконує виклик такої процедури. Але на відміну від процедури, викликаний процес виконується паралельно з програмою, яка його викликала.
Події в алгоритмі, описаному на VHDL, переносяться за допомогою сигналів. В мовах паралельного програмування сигналом є такий примітив, який використовується одним процесом для повідомлення іншому процесу факту здійснення деякої події. Для роботи з сигналами використовують дві операції: послати сигнал і чекати сигнал. Сигнал відрізняється від семафора тим, що семафор використовується для реалізації взаємного виключення роботи кількох процесів (наприклад, які потребують доступ до одного ресурса), а сигнал використовується для синхронізації двох процесів, які виконуються один за одним.
На відміну від інших мов, в VHDL сигнал використовується не тільки як засіб синхронізації процесів, а і для визначення і передачі початкових даних для процесу. Операція послати сигнал нагадує операцію присвоєння змінної, наприклад:
signal 1 <= signal 2;
а операцію чекати сигнал виконує оператор wait. Оператор
wait on S1, S2,….. ;
дозволяє продовжити виконання процесу при появі одного з сигналів S1, S2,… . Оператор
wait until S = const;
визиває продовження процесу при справдженні логічного виразу від сигналу S. Розглянемо наступний приклад фрагменту програми для складання чотирьох чисел.
signal init: boolean:
signal a1, a2, a3, a4, S1, S2, S: integer;
shared variable v1, v2, v3, v4: integer;
begin
p1: process is
a1 <= v1; a2 <= v2; a3 <= v3; a4 <= v4;
wait on init;
end process p1;
p2: process is
S1 <= a1+a2;
wait on a1, a2;
end process p2;
p3: process is
S2 <= a3+a4;
wait on a3, a4;
end process p3;
p4: process is
S <= S1+S2;
wait on S1, S2;
end process p4;
end;
Згідно з програмою, в перший момент часу всі чотири процеси виконуються одночасно і зупиняються на операторах wait. При цьому процеси p2, p3, p4 виконують початкову непродуктивну роботу. В наступний момент часу, через дельта-затримку процеси p2, p3 одержують сигнали a1, a2, a3, a4 і виконуються. Ще через дельта-затримку процес p4 одержує сигнали S1, S2 і обчислює результуючий сигнал S. Виконання програми кожен раз повторюється при одержанні процесом p1 сигналу init. При цьому процес p4 буде кожен раз видавати сигнал S, який дорівнює сумі загальних змінних v1, v2, v3, v4.
Алгоритм, записаний на мові VHDL, представляє собою опис деякого обчислювального процесу, заданого на математичній моделі обчислювальної системи. Такою моделлю ОС виступає багатопроцесорна система, яка складається з процесорних елементів (ПЕ), кожен з яких виконує окремий процес, і ліній зв’язку, по яких сигнали передаються між процесами. Граф структури ОС для алгоритму, наведеному в прикладі, показаний на рисунку 1.
Граф структури ОС, яка виконує алгоритм на мові VHDL представляє собою граф потоків даних, так як він показує напрям потоків даних, представлених сигналами, при періодичному виконанні алгоритму. На цьому графі структури можна виділити вершини ПЕ, які обробляють в деякий момент часу t групу сигналів, які відносяться до однієї групи вхідних даних. Через ці вершини проходить фронт хвилі обчислень. Через проміжок часу дельта цей фронт переміщується на іншу групу вершин ПЕ.
Таким чином, програму на VHDL можна вважати програмою для деякої моделі хвилевого процесора, структура якого показана графом алгоритму на рівні процесів.
4. Блочна структура програм VHDL
У великій кількості мов програмування застосовуються блоки, як відносно незалежні частини програми. При цьому застосовуються такі основні властивості блока, як можливість створення локальної пам’яті для змінних блока, яка може бути легко назначатись і вивільнятись, а також введення відокремленої області дії цих змінних, тобто ці змінні невидимі для зовнішніх ( відносно даного блока ) частин програми.
В мові VHDL блок представляє деяку множину процесів. Як і конструкція програми, так і конструкція блока розділена на дві частини: специфікація даних і специфікація дій з даними. В описі блока специфікацію даних визначають: оператор generic, який описує загальні константи блока, оператор generic map, який описує список присвоювання констант із зовнішнього середовища загальним константам блока, оператор port, який описує вхідні і вихідні сигнали блока і оператор port map, який задає список ідентифікації зовнішніх і вхідних-вихідних сигналів блока. Окремий і необов’язковий стримувальний логічний оператор після ключового слова block задає спеціальний сигнал guard, який дозволяє, або відміняє (стримує) виконання операторів присвоювання сигналів з умовою guard. Також до специфікації даних відносяться декларації констант, сигналів, процедур і функцій, які використовуються всередині блока.
Специфікацію дій блока складають процеси, які описані між ключовими словами begin-end.
Як і в інших мовах програмування, блоки в VHDL також виконують дві основні функції: створення локальної пам’яті для змінних і сигналів блока та введення обокремленої області дії цих змінних і сигналів. Також, як і в інших мовах, блоки в VHDL можуть мати ієрархічну будову, тобто блоки можуть застосовуватися в блоках на більш вищому рівні ієрархії.
Розглянемо опис алгоритму, приведеного в попередньому прикладі, з застосуванням блоків, які складаються з одного процесу. Фрагмент такої програми виглядає наступним чином.
signal init: boolean:
signal b1, b2, b3, b4, C1, C2, C: integer
shared variable v1, v2, v3, v4: integer
Begin
B1: block is
port (init: in boolean;
a1, a2, a3, a4: out integer);
port map (init=>init;a1=>b1; a2=>b2; a3=>b3; a4=>b4);
Begin
p1: process is
a1 <= v1; a2 <= v2; a3 <= v3; a4 <= v4;
wait on init;
end process p1;
end block B1;
B2: block is
port (a1, a2: in integer; S1; out integer);
port map (a1 => b1; a2 => b2; S1 => C1);
begin
p2: process is
S1 <= a1+a2;
wait on a1, a2;
end process p1;
end block B2;
B3: block is
port (a3, a4: in integer; S2; out integer);
port map (a3 => b3; a4 => b4; S2 => C2);
begin
p3: process is
S2 <= a3+a4;
wait on a3, a4;
end process p3;
end block B3;
B4: block is
port (S1, S2: in integer; S; out integer);
port map (S1 => C1; S2 => C2; S => C);
begin
p4: process is
S <= S1+S2;
wait on S1, S2;
end process p4;
end block B4;
end ;
На рисунку 2 показаний граф моделі структури ОС, яка відповідає цій програмі.
Сигнали всередині блоків B2, B3, B4 невидимі для зовнішнього відносно цих блоків середовища. Тому їх можна перейменувати, наприклад, в блоці B3 змінні a3, a4, S2 замінити на a1, a2, S1.
Тоді блоки B2 і B3 відрізнятимуться тільки оператором port map. Таким чином, виникає думка, що блоки B2 і B3, а також B4, які виникають однакові процеси можна замінити уніфікованим блоком. Такий блок дістав назву компонента (сomponent). Як компонент використовується деякий програмний модуль з одноіменною назвою, який з странсльований раніше, або береться з бібліотеки компонентів, що називається пакетом (package). В результаті компіляції при підстановці компонента в даний програмний модуль він розкривається і представляється у вигляді блока.
Специфікація компонента в програмному модулі має дві частини: декларацію компонента (declaration) і його настройку (instantiation).
Декларація компонента виконується один раз і включає в себе назву компонента, оператор generic, який описує загальні константи компонента і оператор port, який описує вхідні і вихідні сигнали компонента. Настройка компонента з’являється стільки разів, скільки блоків в програмі замінено даним компонентом. Настройка включає мітку компонента, яка відрізняє даний екземпляр компонента від інших, ім’я компонента, оператори generic map і port map, які мають те саме значення, як і відповідні оператори блока.
Попередній приклад можна переписати з застосуванням компонента add наступним чином.
signal init: boolean:
signal b1, b2, b3, b4, C1, C2, C: integer
shared variable v1, v2, v3, v4: integer
Component add is
port (a1, a2; in integer; S; out integer)
end component adder
begin
B1: block is
port (init; in boolean;
a1, a2, a3, a4: out integer);
port map (init => init; a1 => b1; a2 => b2; a3 => b3; a4 => b4);
begin
p1: process is
a1 <= v1; a2 <= v2; a3 <= v3; a4 <= v4
wait on init;
end process p1;
end block B1;
U1: component add
port map (a1 => b1; a2 => b2; S => C1);
U2: component add
port map (a1 => b3; a2 => b4; S => C2);
U3: component add
port map (a1 => C1; a2 => C2; S => C3);
end;
На рисунку 3 представлений граф моделі структури ОС, який відповідає цьому фрагменту програми.
Таким чином, третьою основною функцією блоків в мові VHDL є взаємно-однозначна заміна їх програмними одиницями, які називаються компонентами.
В мовах, де застосовуються сигнали, один сигнал, як правило, має один процес-джерело сигналу і один або декілька процесів-приймальників цього сигналу. В вище приведених прикладах мови VHDL також сигнали мають по одному джерелу. Така властивість синхронізації процесів сигналами дуже звужує множину застосувань програмування паралельних алгоритмів за допомогою процесів. В цьому плані загально прийнята модель мультипроцесора з розділеними (shared) змінними має бесперечну перевагу, завдяки якій вона знайшла найбільше поширення. В мові VHDL також допускаються глобальні розподілені змінні. Так, в вище приведених прикладах за допомогою цих змінних процес P1 одержує початкові дані. Однак у всіх відомих реалізаціях мови VHDL порядок записів в одну розділену зміну з декількох процесів є непередбаченим, тобто в цьому випадку порушується загальне правило послідовної узгодженості операцій з розділеними змінними. Таким чином, в мові VHDL безпечним є застосування розподілених змінних тільки у випадку передачі інформації, яка не залежить від порядку доступу до неї, наприклад, при роздачі процесам початкових даних для обчислень з одного джерела.
В реальних застосуваннях часто виникає ситуація, коли декілька паралельних процесів повинні звертатися до одного загального процесу, наприклад, завідуючого загальним ресурсом. Таке застосування важко програмувати використовуючи сигнали з одним джерелом. Для спрощення програмування таких задач в VHDL використовуються оператори генерації вихідних сигналів блоків зі стримуванням (guarded), наприклад, блок
B1: block (sel = ”1”) is port (a; in integer; b: out integer bus) begin b <= guarded a; end block B1;
видає в загальну шину сигналу b ціле значення при умові рівності одиниці керуючого сигналу sel (коли сигнал guard <= (sel = ”1”) дорівнює true). Завдяки конструкції стримування один сигнал, може мати декілька джерел – виходів блоків. При цьому правильне обслуговування цього сигналу полягає в виборці не більше одного джерела сигналу одночасно. У випадку, коли не вибране жодне джерело, сигнал приймає попереднє значення, якщо його джерела типу register, або попередньо задане значення, якщо джерела типу bus. Таким чином четвертою основною функцією блоків в VHDL є організація декількох джерел для одного сигналу.
5. Структура програмних модулів і пакетів
Особливістю мови VHDL, як і мови паралельного програмування Ада, від якої він походить, є спосіб розділеного задання специфікацій пакетів, програмних модулів окремо від їхніх тіл. Ця можливість дозволяє повністю задати специфікацію структури задачі до вирішення будь-яких дрібних деталей її реалізації. Також ця особливість дозволяє виконувати роздільну компіляцію програмних модулів пакетів, що дозволяє будувати великі програми або методом згори вниз, або знизу вгору.
Проект VHDL представляє собою робочу бібліотеку з програмних модулів і пакетів. Загальні типи даних, константи, процедури і функції збираються в програмний пакет (package). Стандартизовані типи, процедури і функції також зібрані в стандартні пакети. Одного разу скомпільований пакет не потребує подальшої компіляції при його застосуванні різними програмами. Окрема від тіла специфікація пакета дозволяє користувачу швидко знайти опис інтерфейсу необхідних для застосування типів, процедур і функцій.
Програмним модулем в VHDL виступає об’єкт (entity). Об’єкт складається з специфікації даних і тіла, які відокремлені один від одного. Специфікацію даних визначають оператор generic, який описує загальні константи об’єкта, і оператор port, який описує вхідні і вихідні сигнали об’єкта, а також декларації констант, сигналів, процедур і функцій, які використовуються в об’єкті. Тіло, або специфікація дій об’єкта представляє його архітектура (architecture). В свою чергу архітектура складається зі специфікації архітектури і тіла архітектури, які описують її виконання. Специфікація архітектури включає опис констант, сигналів, процедур і функцій, а також специфікації компонентів, які застосовуються в архітектурі. Тіло архітектури складається з компонентів, блоків і процесів, які з’єднані між собою сигналами, описаними в специфікації архітектури і в специфікації об’єкта. Модульність мови VHDL проявляється в тому, що будь-який складний паралельний процес може бути оформленим у вигляді об’єкта з фіксованим ім’ям. Один і той же об’єкт може бути описаний у вигляді архітектур з різними іменами. Ці архітектури є взаємозамінні, так як відповідають одній і тій же специфікації об’єкта. Складний об’єкт, а саме його архітектура, може бути описана з використанням простіших об’єктів, які входять до опису архітектури як компоненти.
entity sum is port (v1, v2, v3, v4; in integer; S: out integer) end entity sum
Його архітектурою буде наступна:
architecture tree of sum is
component add
port (a1, a2; in integer;
S: out integer)
end component add;
signal C1, C2: integer;
begin
U1: add port map (a1 => v1; a2 => v2; S => C1);
U2: add port map (a1 => v3; a2 => v4; S => C2);
U3: add port map (a1 => C1; a2 => C2; S => S);
end architecture;
В свою чергу, компонент add описується як наступний об’єкт.
entity add is
port (a1, a2: in integer;
S: out integer)
end entity;
architecture add of add
begin add: process begin
S <= a1+a2;
wait on a1, a2;
end process add;
end architecture;
Для об’єкта sum може бути розроблена інша архітектура, яка виконує таку саму функцію, наприклад, наступна
architecture chain of sum is
component add port (a1, a2; in integer
S: out integer);
signal C1, C2: integer;
begin
U1: add port map (a1 => v1; a2 => v2; S => C1);
U2: add port map (a1 => C1; a2 => v3; S => C2);
U3: add port map (a1 => C2; a2 => v4; S => S);
end architecture;
Таким чином, даний приклад показує ієрархічність і модульність мови VHDL.
6. Можливості мови VHDL по скороченню опису паралельних алгоритмів
Ієрархічна і модульна будова програм VHDL дозволяє скоротити опис алгоритму вирішення задачі, а також проводити розробку застосування колективом програмістів. В даному параграфі розглянуті інші можливості алгоритмістів.
Процес із списком чутливості заміняє процес з операторами wait. Наприклад, процес ad в попередньому параграфі можна записати як
ad: process (a1, a2)
begin S <= a1+a2;
end process ad;
де список чутливості заданий в дужках.
Процес, в якому тільки один вихідний сигнал і всі вхідні сигнали входять в список чутливості можна замінити паралельним або умовним призначенням сигналу. Наприклад, приведений вище процес ad можна записати наступним чином
S <= a1+a2.
Процес, який повторюється, можна замінити викликом процедури. Така процедура має бути паралельною, тобто виклик такої процедури еквівалентний підстановці паралельного процесу.
Наприклад, тіло вищепоказаної архітектури chain може бути описане, наступним чином:
begin
add (v1; v2; C1);
add (C1; v3; C2);
add (C2; v4; S);
end;
де процедура add описана, як
procedure add (a1, a2, v3, v4; in integer;
S: out integer)
begin ad: process begin
S <= a1+a2; wait on a1, a2;
end process ad;
end procedure add;
При трансляції програми замість виклику add буде підставлено відповідний процес ad. Оскільки ця процедура паралельна її не можна робити ні вкладеною, ні вставляти в гніздо циклів.
Для опису множини паралельних процесів, які мають регулярне повторення, в VHDL використовується оператор розмноження паралельних процесів generate.
Оператор generate для деякого наперед заданого діапазону зміни ідентифікатора розмножує відповідну кількість разів тіло оператора. В тілі оператора може, бути процес, виклик процедури з процесом, блок, компонент. Також в тілі оператора може бути ще оператор generate, тобто оператори generate можуть бути вкладеними один в один. Таким чином, оператор розмноження процесів нагадує оператор циклу, але на відміну від нього він повинен мати відомий діапазон зміни ідентифікатора перед початком компіляції, наприклад, цей діапазон може бути заданий як загальна константа типу generic. В деяких випадках оператор generiate можна виконувати рекурсивно .
Розглянемо приклад розробки програми яка відповідає двомірній решітці процесорних елементів (ПЕ). Нехай в кожному ПЕ виконується деякий обчислювальний процес, заданий наступним компонентом
component PU is port (LI, RI, VI, DI: in, real; LO, RO, UO, DO: out, real);
в якому LI, RI, VI, DI, LO, RO, UO, DO – порти вводу і виводу, які повинні з’єднуватись з відповідними портами сусідніх вершин ПЕ.
Вершини з’єднуються сигналами a(i,j),b(i,j),c(i,j),d(i,j), де - i, j ∈ (0, n) означають координати вершини. Тоді структуру решітки можна задати наступним фрагментом програми
rows: for i in 1 to n generate
begin
columns: for i in 1 to n generate
begin
UPU: component PU
port map (LI => a(i,j-1); LO => b(i, j-1);
RI => a(i, j); RO => b(i,j);
UI => c(i-1, j); UO => d(i-1,j);
DI => c(i,j); DO => d(i,j))
end generate columns;
end generate rows;
Наступні оператори програмують значення для вхідних сигналів, які приходять на границі структури
for i in 0 to n generate
begin
a(i, 0) <= 0;
b(i, n) <= 0;
end generate ;
for j in 0 to n generate
c(0, j) <= 0;
b(n, j) <= 0;
end generate;
Одержана запрограмована структура віртуального обчислювача для n = 3 показана на рисунку 4.
З цього прикладу видно, що мова VHDL пристосована для задання регулярних алгоритмів з локальними зв’язками. Так, одержана структура відповідає деякій систолічній обчислювальній схемі.
7. Висновки: Можливості використання мови VHDL для програмування паралельних ОС.
З вищесказаного видно, що у мови VHDL великі можливості по програмуванню паралельних алгоритмів. Розповсюджені мови паралельного програмування використовують паралельні версії мов для послідовних обчислень такі, як Фортран, Сі, Паскаль. Тому часто в програмах на цих мовах паралелізм заданий неявно і потрібні серйозні зусилля розпаралелюючого компілятора для розкриття цього паралелізму.
Так, максимальний ступінь паралелізму виражений в гніздах циклів, але по-перше потрібне вирішення важкої задачі аналізу на незалежність ітерацій, по-друге, вирішення задачі відображення цих ітерацій і зв’язків між ними на структуру існуючої ОС. При цьому, сучасні ОС не підтримують дрібнозернистий паралелізм на рівні апаратури, притаманний гніздам циклів. Найчастіше в паралельних мовах, наприклад HPF, паралелізм виражений у вигляді явно заданих векторів даних і векторних операцій. Це обумовлене широким використанням в недалекому минулому векторно-конвеєрних ОС, які в теперішній час втрачають свою популярність на користь ОС з пам'яттю, яка розділяється.
В той же час в мові VHDL паралелізм принципово задається явно. VHDL є похідною мовою від мови Ада, яка вважається теж надійною і зручною мовою паралельного програмування. Але на відміну від Ади, VHDL має ряд корисних властивостей, які можуть бути розвинуті і широко використані в теперішній час.
Рівень паралелізму в мові VHDL має широкий діапазон від дрібнозернистого паралелізму до грубозернистого. Програмна модель відноситься до прогресивних моделей з віртуальною топологією. Сучасні компілятори-синтезатори забезпечують взаємно однозначне відображення цієї віртуальної моделі в конкретну реальну модель. Це є основою сучасної технології програмування ПЛІС.
Якраз в такій взаємній однозначності відображення і полягають недоліки цих компіляторів. Мається на увазі відсутність масштабування при відображенні в структуру. VHDL підтримує масштабування в напрямку зміни розрядності даних, їх кількості. Але результатом відображення є структура з максимальним паралелізмом. Слід розвивати напрямок компіляторів, які б робили відображення з заданим рівнем паралелізма. Якщо граф потоків даних, описаний на VHDL відображається в структуру, яка його виконує з періодом один такт, то користувачі зацікавлені, щоб цей граф відображався в структуру, яка працює з заданим періодом 2, 3,… n тактів, але б мала значно менші апаратурні витрати. Одним з напрямків побудови таких компіляторів може бути використання методу синтезу систолічних процесорів з обмеженим рівнем паралелізма. Також з тією ж метою можна використати методи відображення періодичних алгоритмів в спеціалізовані конвеєрні пристрої .
Слід також згадати таку мову паралельного програмування, як Оккам. Ця мова широко застосовується для програмування трансп’ютерних систем. Основою цієї мови є також процеси, які виконуються паралельно. Ці процеси обмінюються даними за допомогою лінків, які грають таку ж саму роль, як сигнали в VHDL. Таким чином, Оккам і VHDL можна вважати дещо спорідненими мовами. За час свого існування Оккам підтвердив свою ефективність як мова паралельного програмування задач різної складності. Але нажаль, вона втратила свою популярність разом з трансп’ютерними системами.
Таким чином, мова VHDL може бути використана не тільки для моделювання дискретних систем і взаємно однозначного опису цифрової апаратури на логічному рівні і рівні регістрових передач, а також і для опису більш складних суттєвостей, таких як паралельні алгоритми і обчислювальні схеми. Розвиток цього напрямку дає можливість автоматичного відображення паралельних алгоритмів в високопродуктивні паралельні ОС з дрібнозернистим паралелізмом, якими є ОС з програмованою архітектурою. Але для цього необхідні значні зусилля науковців і системних програмістів.
Література
1. Zima H.P., Vjaldon M., Zapata E.L., Charman B. Vienna-Fortran/HPF Extensions for Sparse and Irregular Problems and their Compilation //IEEE Trans. Parallel and Distributed Systems. -1997, -V8, -N10, -p.1068-1083.
2. Carter J.R., Sanden B.I. Practical Use of Ada 95's Concurrency Features //IEEE Concurrency. -1998, -N6, -p. 47-56.
3. Waingold E., Taylor M., Srikrishna P., et al. Baring it all to Software: Raw Machines.//Computer.-V. 30.-1997.-N9.-P. 86-93.
4. Villasenor J., Mangone-Smith W.H. Configurable Computing// http//www.sciam.com/0697issue10697villasenor.html
5. Янг С. Алгоритмические языки реального времени. Конструирование и разработка.-М.: Мир.-1985.-40 с.
6. Ashenden P. The Designer’s Guide to VHDL. Morgan Kaufman Publishers, Inc. San Francisco, CA. -1996. -688 p.