Методи і засоби підвищення ефективності реалізації дрібнозернистого паралелізму в системах реального часу

Размещено на http://www.allbest.ru/

78

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»

УДК 004.27

МЕТОДИ І ЗАСОБИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ РЕАЛІЗАЦІЇ ДРІБНОЗЕРНИСТОГО ПАРАЛЕЛІЗМУ В СИСТЕМАХ РЕАЛЬНОГО ЧАСУ

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

А В Т О Р Е Ф Е Р А Т дисертації на здобуття наукового ступеня

кандидата технічних наук

Жабіна Валентина Валеріївна

Київ 2011

Дисертацією є рукопис.

Робота виконана в Національному технічному університеті України «Київський політехнічний інститут» Міністерства освіти і науки, молоді та спорту України на кафедрі програмного забезпечення комп'ютерних систем.

Науковий керівник - доктор технічних наук, професор Дичка Іван Андрійович, Національний технічний університет України «Київський політехнічний інститут», завідувач кафедри програмного забезпечення комп'ютерних систем.

Офіційні опоненти: доктор технічних наук, професор Теленик Сергій Федорович, Національний технічний університет України «Київський політехнічний інститут», завідувач кафедри автоматики та управління в технічних системах;

доктор технічних наук, старший науковий співробітник Опанасенко Володимир Миколайович, Інститут кібернетики імені В.М. Глушкова НАН України, м. Київ, провідний науковий співробітник відділу мікропроцесорної техніки.

Захист відбудеться 20 червня 2011 р. о 16-00 годині на засіданні спеціалізованої вченої ради Д 26.002.02 у Національному технічному університеті України «Київський політехнічний інститут» (м. Київ, проспект Перемоги, 37, корп. 18, ауд. 516).

Відзиви на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 03056, м. Київ, проспект Перемоги, 37, вченому секретарю НТУУ «КПІ».

З дисертацією можна ознайомитись у бібліотеці Національного технічного університету України «Київський політехнічний інститут», м. Київ, проспект Перемоги, 37.

Автореферат розісланий « 18 » травня 2011 р.

Вчений секретар

спеціалізованої вченої ради

кандидат технічних наук, доцент М.М. Орлова

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Зростання складності задач реального часу пов'язане з постійним розширенням сфери застосування систем керування, що вимагає для підвищення реакції систем розпаралелювати обчислення на всіх рівнях обробки інформації. Велика кількість задач реального часу потребує високошвидкісної реалізації дрібнозернистих алгоритмів. Важливою проблемою є створення таких систем, які дозволяли б якнайефективніше забезпечувати реалізацію дрібнозернистого паралелізму з можливістю виявлення в динаміці прихованого паралелізму задач.

Необхідність розпаралелювання обчислень істотно збільшує трудомісткість розробки і налагодження програмного продукту, тому зусилля дослідників спрямовані на створення методів програмування та розвиток архітектури систем, що дозволяють істотно спростити і здешевити процес створення паралельних програм.

Велика увага приділяється розробці потокових систем з безпосередніми зв'язками між обчислювальними модулями. У таких системах на обмін даними між модулями витрачається менше часу, ніж в багатопроцесорних системах з передачею даних через пам'ять. Проте, для таких систем недостатньо досліджені методи обробки даних з плаваючою комою, а також можливості зменшення кількості зв'язків між модулями, що є важливим чинником при реалізації систем на основі надвеликих інтегральних схем.

Для реалізації дрібнозернистого паралелізму використовуються моделі обчислень, керованих потоком даних. Такий принцип обчислень дозволяє з мінімальними витратами системних ресурсів реалізовувати в динаміці дрібнозернистий паралелізм і водночас виконувати декілька програм, не витрачаючи ресурсів на синхронізацію процесів і розподіл пам'яті. Продуктивність таких систем обмежується часом формування команд унаслідок обмеженої пропускної спроможності пам'яті, на базі якої будується середовище формування команд. Крім того, недостатньо досліджені питання, пов'язані із забезпеченням відмовостійкості систем, що є необхідною умовою для одержання вірогідних результатів, особливо при розв'язуванні задач реального часу.

Таким чином, актуальною є науково-технічна задача підвищення продуктивності і забезпечення відмовостійкості систем реального часу, що реалізують дрібнозернистий паралелізм. Для досягнення цього необхідна розробка нових методів виконання операцій і організації систем з використанням сучасної елементної бази - програмованих логічних інтегральних схем (ПЛІС).

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до планів науково-дослідних робіт (НДР) Національного технічного університету України «Київський політехнічний інститут» по госпдоговірних темах:

НДР «Побудова високопродуктивних паралельних обчислювальних систем з архітектурою на основі розподіленої загальної пам'яті», № ДР 0205U006874, 2004-2005 рр.;

НДР «Побудова відмовостійких високопродуктивних кластерних систем із вузлами на основі реконфігурованих багатопроцесорних кристалів», № ДР 0207U008891, 2006-2007 рр.;

НДР «Методи та засоби підвищення інформаційної безпеки гетерогенних кластерних систем», № ДР 0108U000511, 2008-2010 рр.

У всіх темах автор є виконавцем.

Мета і завдання дослідження. Метою роботи є прискорення реалізації алгоритмів реального часу з дрібнозернистою структурою та забезпечення відмовостійкості обчислювальних систем, побудованих на базі надвеликих інтегральних схем.

Для досягнення даної мети необхідно:

- дослідити характеристики алгоритмів реального часу та сформулювати вимоги до обчислювальних систем, орієнтованих на їх виконання;

- дослідити можливості прискорення обробки послідовності залежних за даними операцій у неавтономному режимі шляхом паралельної обробки розрядів операндів та зменшення затримки формування проміжних результатів;

- розробити методику виконання операцій з плаваючою комою в потокових системах з безпосередніми зв'язками для збільшення точності обчислень при заданій довжині розрядної сітки;

- дослідити можливості підвищення продуктивності обчислювальних систем, керованих потоком даних, шляхом максимального завантаження обчислювальних засобів системи за рахунок прискорення процесів активізації акторів та паралельного формування команд;

- розробити механізм забезпечення відмовостійкості потокових систем шляхом динамічної реконфігурації для усунення помилок, спричинених відмовою обладнання, з метою збільшення достовірності результатів обчислень та прискорення процесу відновлення системи.

Об'єктом дослідження є процеси обробки інформації в паралельних обчислювальних системах реального часу, що пов'язані з підвищенням ефективності обробки даних шляхом зменшення часу отримання результатів та забезпечення відмовостійкості систем.

Предметом дослідження є методи та засоби прискорення обчислень в паралельних обчислювальних системах за рахунок динамічного розпаралелювання процесів на рівні обробки операндів та їх розрядів, а також забезпечення автоматичного відновлення працездатності систем при відмові апаратури. режим обробка операнд відмовостійкість

Методи досліджень. Для розробки та дослідження архітектури обчислювальних систем та методів організації паралельних обчислень використовуються положення теорії обчислювальних систем, елементи теорії інформації, графів та алгоритмів. Аналіз паралельних процесів та похибки обчислень здійснюється з застосуванням елементів математичного аналізу, теорії числових методів, імітаційного моделювання.

Наукова новизна одержаних результатів полягає у розробці нових методів та засобів прискорення розв'язання задач з явним та прихованим дрібнозернистим паралелізмом та забезпечення відмовостійкості потокових систем реального часу, реалізованих у відповідності з вимогами сучасної інтегральної технології.

Основні наукові результати, отримані особисто автором:

- розроблено новий метод виконання арифметичних операцій при порозрядному введенні та виведенні операндів, який за рахунок використання зміщеної надлишкової системи числення з великою основою дозволяє прискорити виконання послідовності залежних операцій у неавтономному режимі шляхом зменшення кількості циклів обчислень і скорочення тривалості циклів;

- вдосконалено метод обчислення функцій «цифра за цифрою» шляхом суміщення процесів порозрядного введення аргумента та порозрядного формування результату із застосуванням надлишкових систем числення, що дає можливість обчислювати функції у неавтономному режимі для прискорення виконання послідовності операцій, залежних за даними;

- запропоновано новий таблично-алгоритмічний метод неавтономного обчислення функцій у зміщених системах числення, який на відміну від відомих методів не потребує виконання операцій з від'ємними приростами, що дозволяє спростити апаратну реалізацію та зменшити час обчислень;

- розроблено новий метод обробки інформації в обчислювальних системах, керованих потоком даних, що дозволяє при реалізації дрібнозернистих алгоритмів зменшити час обчислень за рахунок динамічного формування паралельних потоків команд для більшого завантаження обчислювальних модулів;

- вдосконалено метод автоматичного відновлення систем, керованих потоком даних, при відмові обчислювальних модулів шляхом введення засобів контролю тривалості операцій та модернізації процедури реконфігурації, що дозволило зменшити час виявлення несправностей та прискорити процес відновлення працездатності системи.

Практичне значення одержаних результатів полягає у наступному.

Розроблена методика обчислень з плаваючою комою та засоби її реалізації дозволяють спростити та прискорити розробку потокових систем з безпосередніми зв'язками, оскільки не вимагають у статиці розв'язувати задачу синхронізації порозрядної передачі даних між обчислювальними модулями.

При порозрядному обміні даними скорочується необхідна кількість зв'язків між компонентами системи. Це дозволяє ефективніше використовувати ресурси ПЛІС, що створює передумови для підвищення надійності та зменшення вартості систем.

Запропоновані методи підготовки програм для систем, керованих потоком даних, не потребують врахування кількості обчислювальних модулів та кількості середовищ формування команд (СФК), що спрощує підготовку паралельних обчислень.

Розроблені програмні засоби моделювання можуть використовуватися як елемент комплексу автоматизації проектування систем, керованих потоком даних, із заданими характеристиками.

Результати дисертаційної роботи впроваджені у Національному технічному університеті України «Київський політехнічний інститут» на кафедрі програмного забезпечення комп'ютерних систем. Застосовуються в навчальному процесі при викладанні дисциплін «Комп'ютерна логіка» і «Комп'ютерна схемотехніка».

Особистий внесок здобувача. Всі основні результати дисертації отримані автором самостійно. У працях, опублікованих у співавторстві, автору належать: [1] - розробка методу множення чисел у зміщених надлишкових системах числення; [3, 6] - удосконалення алгоритму обчислення функцій методом «цифра за цифрою», що дозволяє суміщати введення аргументів та формування результатів; [4, 11] - спосіб формування таблиць приростів функцій для операційних пристроїв, що працюють у надлишкових системах числення; [7] - удосконалення методу реконфігурації потокових систем з середовищем формування команд на основі пам'яті з адресним доступом; [8, 15] - метод автоматичної ідентифікації акторів та даних для потокових систем з паралельним формуванням команд та алгоритм моделювання системи; [9] - обґрунтування можливості зменшення затримки формування результатів неавтономних обчислень за рахунок збільшення основи системи числення; [10] - дослідження характеристик систем числення, що забезпечують прискорення виконання операцій в неавтономному режимі.

Апробація результатів дисертації. За матеріалами дисертації були зроблені доповіді на наступних конференціях: Міжнародна науково-технічна конференція «Штучний інтелект. Інтелектуальні системи» (с. Кацивелі, АР Крим, 2008 р.; с. Кацивелі, АР Крим, 2010 р.); Міжнародна науково-практична конференція «Сучасні інформаційні та електронні технології» (Одеса, 2009 р.); Міжнародна наукова молодіжна школа «Системи і засоби штучного інтелекту» (с. Дивноморське, РФ, 2009 г.); Шістнадцята міжнародна конференція з автоматичного управління «Автоматика-2009» (Чернівці, 2009 р.); Міжнародна науково-технічна конференція «Сучасні комп'ютерні системи та мережі, розробка та використання» (Львів, 2009 р.); Наукова конференція магістрантів та аспірантів «Прикладна математика та комп'ютинг» (Київ, 2009 р., 2010 р.); Восьма міжнародна студентська наукова конференція з прикладної математики та інформатики (Львів, 2010 р.); Ювілейна міжнародна конференція «Розподілені комп'ютерні системи» (Київ, НУТУ «КПІ», 2010 р.).

Публікації. За темою дисертації опубліковано 18 наукових праць, серед яких 8 статей у наукових журналах та збірниках наукових праць, що входять до переліку ВАК, а також 10 публікацій за матеріалами конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається з вступу, п'яти розділів, висновків, які включають основні результати роботи, списку використаних джерел з 131 найменування, п'яти додатків. Повний обсяг дисертації становить 169 сторінок, з них 145 сторінок основного тексту, 34 рисунки, 8 таблиць.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертаційної роботи, сформульовано мету і основні задачі дослідження, визначено наукову новизну та практичну цінність одержаних результатів. Наведено дані про особистий внесок здобувача, відомості про апробацію та публікацію результатів дослідження.

У першому розділі дано основні визначення та загальні відомості про особливості обробки інформації в реальному часі, визначено структуру алгоритмів керування, сформульовано основні вимоги до програмних та апаратних засобів обчислювальних систем реального часу.

Аналіз особливостей роботи обчислювальних систем у контурі керування об'єктами і процесами, а також алгоритмів обробки даних дозволив сформулювати вимоги до класу систем реального часу, що розглядаються в дисертації. Такі системи повинні забезпечувати високу швидкість реалізації послідовно-паралельних алгоритмів з дрібнозернистою структурою, забезпечувати переважно диференціальний тип передач інформації між обчислювальними вузлами, паралельну обробку даних, в тому числі на рівні операндів і розрядів операндів. До систем реального часу пред'являються жорсткі вимоги щодо відмовостійкості та вірогідності результатів обчислень.

Використання сучасної технології проектування SoC (System on Chip - система на кристалі) дозволяє прискорити проектування систем на основі ПЛІС. Однак, з боку елементної бази накладається ряд обмежень, пов'язаних з кількістю виводів, числом функціональних вузлів і вбудованих пристроїв у ПЛІС.

Доведено, що для реалізації дрібнозернистих алгоритмів недоцільно використовувати класичні багатопроцесорні системи типу MIMD (Multiple Instruction - Multiple Data) за класифікацією Флінна, оскільки в них використовуються складні процедури обміну даними, що неприйнятно для обміну на рівні окремих слів. Крім того, для таких систем більш розвинені статичні засоби паралельного програмування, які визначають план виконання завдань за апріорними характеристиками. Основні задачі розпаралелювання вирішуються на етапі розробки програм, що не завжди дозволяє виявити прихований паралелізм задач через нестачу інформації про реальну тривалість процесів у системі.

Для реалізації дрібнозернистих алгоритмів більш ефективно використовувати потокові обчислювальні системи, у яких застосовуються динамічні засоби розпаралелювання обчислень на низькому рівні паралелізму. Наведено класифікацію таких систем та виділено два їх основні різновиди: потокові системи з безпосередніми зв'язками між компонентами (ПСБЗ) і системи, керовані потоком даних (СКПД), які реалізують відповідно моделі обчислень «data driven» та «data flow». Вихідною інформацією для підготовки завдань для обох різновидів систем є граф потоків даних (ГПД).

Досліджено відомі методи організації обчислень в потокових системах, та сформульовано напрямки підвищення ефективності використання ПСБЗ і СКПД.

Другий розділ присвячено підвищенню ефективності обчислень у ПСБЗ.

Запропоновано узагальнену функціональну модель систем типу ПСБЗ, яка враховує необхідні характеристики, особливості структурної організації системи, функціональні можливості компонентів і обмеження, що накладаються з боку елементної бази та форми подання чисел.

У ПСБЗ виходи одних обчислювальних модулів (ОМ) з'єднуються з входами інших відповідно до ГПД. У процесі обчислень дані пересилаються від одних модулів до інших, перетворюючись у кожному з них відповідно до заданої операції. ГПД послідовних і послідовно-паралельних алгоритмів мають гілки, на яких знаходяться залежні за даними операції. Ці операції не можна виконувати паралельно в часі, оскільки результати попередніх операцій є операндами для наступних. При використанні ОМ, які забезпечують суміщення процесів порозрядного введення операндів і порозрядного формування результату, виконання залежних операцій можна частково суміщувати в часі за допомогою ланцюжка ОМ, які працюють спільно (у неавтономному режимі, «on-line»). Суміщення в часі відбувається за рахунок реалізації паралелізму на розрядному рівні.

Обробку даних у неавтономному режимі зі старших розрядів операндів можна здійснювати лише в надлишкових системах числення, в яких відсутнє поширення переносів у старші розряди. Відомі методи неавтономних обчислень призначені для чисел з фіксованою комою в симетричних надлишкових системах числення, при цьому апаратна реалізація, як правило, пропонується для двійкової системи.

Обчислення з фіксованою комою мають наступні недоліки: обмеження на діапазон подання чисел; можливість втрати значимості результатів обчислень; складність синхронізації просування даних для забезпечення необхідного співвідношення їх величин у певному місці ланцюжка операцій (наприклад, при додаванні розряди, що підсумовуються, повинні мати однакову вагу).

Визначено недоліки симетричної системи числення: відмінність в алгоритмах формування перших і наступних цифр результату внаслідок розширення розрядної сітки; збільшення апаратурних витрат і тривалості циклу через необхідність роботи з від'ємними числами.

Для усунення недоліків, пов'язаних з симетричними системами, запропоновано метод множення модулів чисел у зміщених системах числення.

Розглядається функція , де - затримка початку формування розрядів результату. Операнди представлені -розрядами в позиційній надлишковій системі числення з основою , тобто,, де - цифри операндів. Результат формується порозрядно, починаючи зі старших розрядів. Після виконання циклів буде отримано результат .

Виконання в -му циклі умови (, і - коди, представлені старшими розрядами) забезпечує після циклів похибку результату, що не перевищує . Розроблено ітераційний алгоритм множення:

; (1)

; ;.

Початковими є значення

.

Ціла частина змінної є цифрою результату, а дробова - змінною , яка використовується в наступному циклі.

Для прискорення обчислень необхідно зменшувати затримку . Показано, що для систем з основою мінімальна затримка становить . Для систем з основою при певному діапазоні цифр можна одержати мінімальну величину затримки . Залежність між величинами і визначається співвідношенням .

Додавання чисел у неавтономному режимі може виконуватися в такій самій зміщеній системі числення, як і множення. Для порозрядного формування результату використовується алгоритм, аналогічний множенню, у якому вираз (1) для -го циклу виконання операції набуває вигляду

. (2)

Доведено, що для систем з основою можна забезпечити мінімальну затримку формування результату .

Аналогічним чином можна одержати алгоритми обчислення різних раціональних функцій. Наприклад, для множення з накопиченням проміжних результатів (операція використовується для цифрової обробки сигналів, обчислення поліномів за схемою Горнера, тощо) можна використовувати функцію . Формула (1) у цьому випадку має вигляд

.

Розглянуто операцію порівняння чисел у надлишкових системах числення, що дозволяє реалізувати алгоритми з розгалуженнями на підставі співвідношення двох чисел. Для порівняння чисел і в -му циклі використовується формула з початковим значенням . Остаточний результат порівняння може бути отриманий на будь-якому кроці при виконанні умови . Додатне значення різниці відповідає умові , від'ємне - умові , а нульове -.

З метою розширення функціональних можливостей ПСБЗ пристрої, що працюють у зміщених і симетричних системах числення, можна використовувати спільно для неавтономних обчислень. Показано способи перетворення чисел з однієї системи числення в іншу. За необхідності для передачі даних між пристроями включаються блоки узгодження форм подання чисел.

Запропоновано методику обробки даних у формі з плаваючою комою в неавтономному режимі. В надлишкових системах числення наявність значущого розряду мантиси праворуч від коми не означає, що мантиса є дробовим числом. Це вимагає спеціальних алгоритмів обробки чисел.

Числа з плаваючою комою мають вигляд , де порядок - ціле число в ненадлишковій системі, а мантиса представлена в надлишковому коді та перебуває в межах . Значення визначається основою системи числення та діапазоном значень цифр.

Для мантиси , де або , діапазон подання визначається співвідношенням

. (3)

Розглянуто можливі варіанти порушення нормалізації при виконанні основних арифметичних операцій. Мантиси добутку, частки і суми (різниці), виходячи з діапазону зміни мантис (3), перебувають відповідно в межах:

; ; .

На відміну від канонічних систем числення для всіх операцій можливе порушення нормалізації як вправо, так і вліво. З урахуванням цього розроблено алгоритми виконання основних операцій з плаваючою комою в надлишкових кодах. ОМ містять блоки для обробки мантис і порядків, які взаємодіють між собою. Цифри мантис вводяться в ОМ з попереднього модуля, починаючи зі старших розрядів, і порозрядно видаються в наступний. Порядки операндів можуть передаватися в ненадлишковій формі.

Запропоновано структури операційних пристроїв, що реалізують формули (1) і (2) за один такт. Апаратна реалізація неавтономних обчислень найбільш ефективна при використанні основи систем числення , де У цьому випадку для побудови ОМ використовуються типові цифрові вузли.

Збільшення величини основи дозволяє скоротити розрядність чисел, зберігаючи задану точність подання даних. Завдяки цьому скорочується загальна кількість циклів виконання операцій. На відміну від симетричних систем числення в зміщених системах не потрібно працювати з від'ємними приростами, що спрощує апаратну реалізацію і скорочує тривалість циклу. Порівняно із застосуванням паралельних пристроїв зменшується кількість зв'язків між ОМ, що відповідає вимогам інтегральної технології.

У третьому розділі досліджуються методи обчислення функцій, що придатні для обробки даних в неавтономному режимі.

Розглянуто метод «цифра за цифрою», який дозволяє формувати результат порозрядно. Однак для цього аргументи повинні бути представлені паралельним кодом. Для суміщення порозрядного введення і виведення інформації запропонована модифікація методів обчислення функцій і . При порозрядному введенні аргументів збіжність обчислень забезпечується повторенням циклів при виявленні розбіжності, яку неможливо виправити на наступному кроці. Недоліком такого підходу є неоднакова тривалість кроків обчислень, що ускладнює апаратну реалізацію.

Запропоновано таблично-алгоритмічний метод, який за формою подання чисел узгоджується з розробленими методами виконання арифметичних операцій, що забезпечує можливість їх спільного використання.

Розглядається неперервна функція , що задана в першому квадранті ( - затримка початку формування розрядів результату). Аргумент, що має розрядів, та функція представлені в надлишковій зміщеній системі числення з основою і цифрами .

У кожному -му циклі формується цифра значення функції відповідно до формул:

; ent ; rest ;

з початковим значенням .

Приріст , що залежить від аргумента, визначається за таблицею, яка формується в такий спосіб.

1. Будується ярусно-паралельний граф переходу значень аргумента. Кожна вершина графа -го ярусу з'єднується дугами з вершиною -го ярусу у відповідності зі значеннями цифр аргумента, які приписуються зазначеним дугам. Кожна вершина має позначення , де - номер ярусу, а - номер вершини на -му ярусі.

2. Кожній вершині -го ярусу надається вага .

3. Для ярусів з номерами ваги вершин визначаються за формулами

.

4. Для кожної дуги графа, що з'єднує вершину з вершиною, визначається приріст . Приростам -го ярусу надається вага .

При використанні ПЛІС таблиця може зберігатися у вбудованих блоках пам'яті. Для узгодження форми подання даних з іншими операціями використовується співвідношення, що дозволяє забезпечити необхідний діапазон значень цифр залежно від інших параметрів.

Четвертий розділ присвячено питанням прискорення паралельної обробки даних і забезпечення відмовостійкості СКПД.

На основі аналізу моделі обчислень, керованих потоком даних, розглянуто можливості скорочення часу реалізації дрібнозернистих алгоритмів. Підготовка завдань для СКПД здійснюється на основі графа , де - множина вершин, що відповідають операціям; - множина дуг, що відповідають потокам даних. Програма подається списком керуючих слів (акторів) і даних (токенов), з яких у середовищі формування команд (СФК) формуються команди для ОМ. За наявності декількох ОМ процес автоматично розпаралелюється.

Рис. 1 Структура системи, керованої потоком даних

Час обчислень у СКПД визначається рівнем завантаження ОМ. Сучасні технології дозволяють створювати швидкодіючі обчислювальні ядра в ПЛІС, внаслідок чого інтенсивність формування команд у СФК може бути недостатньою для максимального завантаження ОМ.

Для прискорення обчислень можна розпаралелити процеси активізації акторів з метою максимального завантаження ОМ. Однак просте дублювання СФК приводить до недоліків статичного планування обчислень, оскільки вимагає в ручному режимі розподіляти дані між ОМ.

У роботі запропоновано метод автоматичного динамічного формування паралельних потоків команд. Метод передбачає введення до складу системи декількох СФК (рис. 1), використання певних форматів акторів і даних, програмних засобів попередньої обробки даних, а також механізму динамічного розподілу акторів і даних між СФК.

Розглянуто два варіанти реалізації методу: перший для ГПД без розгалужень, другий - з розгалуженнями, в тому числі, з циклами.

У першому випадку актори і дані подаються відповідно кортежами:

, ,

де - ідентифікатор СФК, - ідентифікатор актора; - функція перетворення даних; - ім'я актора, для якого -й актор підготовлює операнд; - значення операнда; - сукупність ознак операнду.

Для алгоритмів з розгалуженням формати акторів і даних мають вигляд

, ,

де - кількість акторів, для яких -й актор формує операнд; - список імен цих акторів.

Розроблено алгоритми формування паралельних потоків команд.

При підготовці завдань для СКПД реальна кількість ОМ і СФК у системі не враховується. Компілятором завжди формується максимально можлива кількість паралельних потоків команд. Система може містити будь-яку кількість ОМ. Кількість СФК повинна відповідати формулі . За наявності СФК реально буде формуватися потоків команд. Механізм розподілу акторів і даних між СФК враховує тільки молодших розрядів двійкових кодів ідентифікаторів (]*[ - округлення до найближчого більшого цілого).

Запропонований метод дозволяє прискорити обчислення за рахунок збільшення інтенсивності потоку готових команд для ОМ.

Виконано аналіз відомих методів забезпечення відмовостійкості СКПД з різною архітектурою. Показана доцільність для систем реального часу використовувати динамічні методи відновлення.

Специфіка СКПД полягає в тому, що дані для обчислень готуються без урахування кількості ОМ і СФК. При використанні однотипових модулів є потенційна можливість при відмові пристроїв продовжувати обчислення, доки в системі залишається хоча б один працездатний модуль. Завдання полягає в збереженні команди або її компонентів для повторного виконання в працездатному ОМ. Зазвичай ОМ, у тому числі ті, що входять до складу ПЛІС, не мають засобів вбудованого контролю працездатності. Відомі способи визначення відмови ОМ за максимальним часом виконання команди з використанням для кожного ОМ свого таймера. Недоліком такого підходу є часова надлишковість визначення несправності, оскільки різні команди можуть мати різний час виконання, який може відрізнятися в кілька разів.

Запропоновано метод прискорення процесу реконфігурування СКПД, що відрізняється від відомих форматом акторів і механізмом реконфігурації. Метод може бути застосований як для систем з СФК на базі асоціативної пам'яті, так і для систем (рис. 2) на базі пам'яті з довільним доступом (ПДД).

Рис. 2 Структура відмовостійкої системи

Команди формуються в СФК і записуються в буферну пам'ять (БП) готових команд у форматі, де - необхідні для команди поля даних, - поля актора. До складу актора вводиться поле , що визначає максимальну тривалість даної команди. Команда, що надходить в ОМ, записується також у регістр команд (РК), частина якого виконана у вигляді таймера, який контролює час виконання команди. При відмові ОМ команда з РК записується в БП і буде повторно виконана в працездатному ОМ.

Запропонований підхід дозволяє прискорити процес реконфігурування систем за рахунок скорочення часу визначення несправності.

При побудові систем може бути використаний основний принцип побудови відмовостійких систем - принцип розширюваного ядра, захищеного апаратними методами підвищення надійності. У якості захищеного ядра може слугувати СФК, реалізоване на основі запам'ятовувальних пристроїв, для яких розвинено методи контролю і виправлення помилок.

У п'ятому розділі досліджується ефективність запропонованих методів і засобів реалізації дрібнозернистого паралелізму.

Розглянуто загальні питання організації ПСБЗ, які забезпечують паралельну обробку розрядів даних при виконанні послідовності залежних за даними операцій, які на рівні обробки машинних слів не можуть бути розпаралелені. Завдяки паралелізму на рівні обробки розрядів операндів операції виконуються в режимі суміщення, що створює передумови для прискорення обчислень. Для забезпечення обчислень у зазначеному режимі необхідно для кожного конкретного алгоритму створити структуру, що містить множину ОМ, з'єднаних між собою відповідно до ГПД.

Запропоновано структуру ОМ для виконання операцій з плаваючою комою в неавтономному режимі. Особливістю ОМ є автоматична нормалізація мантис і можливість обміну даними в асинхронному режимі. Істотно спрощуються функції керування обчисленнями, і розширюється діапазон подання чисел, що дозволяє підвищити точність обчислень.

Досліджено вплив величини основи надлишкових систем числення на час виконання операцій у неавтономному режимі.

Визначено тривалість циклу для пристроїв множення -розрядних чисел у надлишкових системах з основою і цифрами

,

де - розрядність чисел у двійковому еквіваленті; - затримка сигналів однорозрядним суматором.

Середній час виконання операції на позиції в послідовності залежних операцій визначається формулою

,

де - затримка в циклах початку формування розрядів результату.

Вплив величини основи системи числення на час виконання операції визначається коефіцієнтом відносного прискорення

, (4)

де - середній час виконання операції для ; а - для .

Для розрядності побудовано графік (рис. 3), з якого видно, що при множення можна прискорити, причому, при більших значеннях використовувати системи числення з основою недоцільно, тому що коефіцієнти прискорення для різних основ вирівнюються, а апаратні витрати з ростом величини основи збільшуються.

Аналогічні дослідження виконано для операції додавання. Як і при множенні, зі збільшенням перевагу слід віддати основі .

Рис. 3 Залежність коефіцієнта відносного прискорення від довжини послідовності операцій

Виконано порівняння ефективності обчислень за допомогою пропонованих методів і методів паралельної арифметики. В якості паралельного пристрою розглядається матрична схема множення з поширенням переносів по діагоналях матриці.

Рис. 4 Залежність коефіцієнта відносного прискорення від довжини послідовності операцій

Графік на рис. 4, побудований відповідно до (4) ( - час множення для паралельного матричного пристрою; - середній час множення в неавтономному режимі), показує, що пропонований підхід до виконання послідовності операцій дозволяє прискорити обчислення при певній довжині причому, зі зростанням виграш у часі зростає. Наприклад, для виграш у часі починається з порівняно невеликого значення . Пунктирною лінією на рис. 4 показано граничне значення прискорення для системи з основою . Таким чином, пропоновані методи теоретично дають можливість прискорити виконання послідовності залежних операцій.

Для дослідження СКПД з паралельним формуванням команд розроблено імітаційну модель, яка є комплексом програмних засобів, що дозволяють підготовлювати дані для завдання, виконувати моделювання ходу обчислень і формувати дані для його аналізу.

За допомогою моделі досліджено ефективність обчислень залежно від наступних параметрів: кількість ОМ, кількість СФК і тривалість виконання команд. Наведено оцінки середнього часу виконання команди , де - час виконання команди -го типу, а - частота появи команди в програмах.

Розглянуто два варіанти команд: короткі й довгі (з часовими параметрами відповідно команд додавання і множення). У якості тестової була використана задача, граф якої має послідовно-паралельну структуру у вигляді бінарного дерева із заданими частотами появи команд.

Вплив кількості СФК на час обчислень визначає коефіцієнт відносного прискорення (4), де - час обчислень з одним СФК, а - з кількома СФК.

Рис. 5 Залежність коефіцієнта відносного прискорення від кількості СФК і ОМ

З наведеного на рис. 5 графіка, отриманого для випадку відношення тривалості коротких і довгих команд як 1:2, видно, що використання двох СФК дозволило прискорити обчислення більш ніж на 40%, а чотирьох - майже на 60%.

Моделювання з використанням розробленого програмного середовища дозволяє для певного класу задач визначити параметри системи, які забезпечують ефективну реалізацію цільової функції. Може бути визначений час розв'язування задачі при різній кількості ОМ і СФК, що дає можливість у кожному конкретному випадку вибрати необхідну конфігурацію системи.

ВИСНОВКИ

В дисертаційній роботі виконано теоретичне обґрунтування та отримано нові рішення актуальної наукової задачі підвищення ефективності паралельних обчислень в системах реального часу, що дозволяють прискорити виконання дрібнозернистих алгоритмів та забезпечити відмовостійкість обчислювальних систем, орієнтованих на реалізацію у вигляді надвеликих інтегральних схем.

Основні наукові та практичні результати полягають у наступному.

1. Вперше запропоновано метод виконання арифметичних операцій у зміщених надлишкових системах числення з великою основою, що дозволяє суміщувати порозрядне введення, обробку та порозрядне виведення даних. Це дає можливість прискорити виконання послідовності залежних за даними операцій у неавтономному режимі за рахунок паралельної обробки розрядів операндів. Збільшення основи системи числення дозволяє зменшити загальну кількість циклів при заданій точності обчислень. На відміну від операцій в симетричних системах числення немає потреби обробляти від'ємні прирости, що скорочує тривалість циклів.

2. Вперше розроблено методику та запропоновано засоби виконання операцій з плаваючою комою в надлишкових системах числення з урахуванням особливостей порозрядної передачі інформації між компонентами системи, що дозволяють збільшити точність обчислень при заданій довжині розрядної сітки, забезпечити автоматичну нормалізацію проміжних результатів та прискорити обмін даними між вузлами системи за рахунок переходу від синхронної до асинхронної передачі даних.

3. Запропоновано новий таблично-алгоритмічний метод обчислення функцій при порозрядному введенні та виведенні інформації у зміщених системах числення, який на відміну від методів, що використовують симетричні системи, не потребує виконання операцій з від'ємними приростами, що дозволяє спростити апаратну реалізацію та зменшити час обчислень. Вдосконалено метод обчислення функцій «цифра за цифрою» для забезпечення суміщення порозрядного введення та виведення даних. Методи обчислення функцій можуть застосовуватися одночасно з методами виконання арифметичних операцій, що розширює можливості систем при реалізації неавтономних обчислень.

4. Розроблено новий метод обробки інформації в обчислювальних системах, керованих потоком даних, що дозволяє при реалізації дрібнозернистих алгоритмів прискорити обчислення за рахунок збільшення інтенсивності завантаження обчислювальних модулів шляхом динамічного формування паралельних потоків команд.

5. Удосконалено метод автоматичного відновлення працездатності систем, керованих потоком даних, при відмові обчислювальних модулів шляхом введення засобів контролю тривалості операцій та модернізації процедури реконфігурування, що дозволило зменшити час визначення несправності та прискорити процес відновлення системи.

6. Запропоновано способи реалізації операційних пристроїв, що реалізують розроблені методи обробки інформації в реальному часі та орієнтовані на використання сучасної елементної бази, у тому числі ПЛІС. На відміну від систем з паралельним обміном даними завдяки порозрядному обміну скорочується необхідне число зв'язків між компонентами системи, що дозволяє більш ефективно використовувати ресурси ПЛІС і створює передумови для підвищення надійності систем.

7. Створено інтерактивні програмні засоби моделювання обчислень на рівні паралельної обробки операндів, що дозволяють спростити і прискорити розробку та налагодження програм, а також визначати необхідні параметри систем, керованих потоком даних, для ефективної реалізації заданого класу задач.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Дичка И.А. Совмещение зависимых операций на уровне обработки разрядов операндов / И.А.Дичка, В.В.Жабина // Искусственный интеллект. 2008. №3. С. 649-654. Дисертантом запропоновано метод множення чисел в надлишковій системі числення з великою основою, що забезпечує зменшення затримки формування результату в неавтономному режимі обробки даних.

2. Жабина В.В. Повышение эффективности параллельной обработки данных на уровне операций в потокових системах/ В.В.Жабина // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. праць. К.: Век+. 2008. № 49. С. 112-116.

3. Макаров В.В. Вычисление логарифма при поразрядном вводе и выводе информации / В.В.Макаров, В.В.Жабина // Науковий вісник Чернівецького університету: Збірник наукових праць. Випуск 423: Фізика. Електроніка.: Тематичний випуск "Комп'ютернi системи та компоненти". Частина І. Чернівці: ЧНУ, 2008. С. 14-18. Дисертантом обґрунтована можливість удосконалення методу порозрядного формування результату обчислення логарифму при порозрядному введенні аргумента, визначена похибка обчислень.

4. Дичка И.А. Метод вычисления функций в неавтономном режиме / И.А.Дичка, В.В.Жабина // Искусственный интеллект. 2009. №4. С. 409-414. Дисертантом запропоновано спосіб формування таблиць приростів функцій для операційних пристроїв, що працюють в неавтономному режимі в надлишкових системах числення.

5. Жабина В.В. Параллельное формирование команд в потоковых системах / В.В.Жабина // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. праць. К.: Век+. 2009. № 50. С. 113-117.

6. Макаров В.В. Совмещение ввода и обработки операндов при вычислении некоторых функций / В.В.Макаров, В.В.Жабина // Науковий вiсник Чернiвецького унiверситету. Випуск 446: Комп'ютернi системи та компоненти. Чернівці: ЧНУ, 2009. С. 6-10. Дисертантом удосконалено алгоритм одночасного обчислення функцій sin і cos, що дозволяє суміщення процесів введення аргумента та формування результату.

7. Клименко И.А. Обеспечение отказоустойчивости потокових систем на однотипных вычислительных модулях / И.А.Клименко, В.В.Жабина // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. праць. К.: Век+. 2010. № 51. С. 166-171. Дисертантом розроблено метод забезпечення відмовостійкості потокових систем з середовищем формування команд на базі пам'яті с адресним доступом.

8. Жабина В.В. Модель потоковой системы с параллельным формированием команд / В.В.Жабина, И.В.Каспич // Проблеми інформатизації та управління: Зб. наук. праць. К.: Книжкове вид-во НАУ, 2010. Вип. 4 (22). С. 45-50. Дисертантом запропоновано метод автоматичної ідентифікації акторів та даних для потокових систем з паралельним формуванням команд.

9. Дичка И.А. Совмещение зависимых операций в неавтономном режиме / И.А.Дичка, В.В.Жабина // Материалы Международной научно-технической конференции «Искусственный интеллект - 2008. Интеллектуальные системы». Т.2. ТТИ, 2008. С. 307-311. Дисертантом обгрунтована можливість зменшення затримки формування результатів неавтономних обчислень за рахунок збільшення основи системи числення.

10. Дичка И.А. Выполнение операций в избыточных системах счисления / И.А.Дичка, В.В.Жабина // Тезисы МНПК «Современные информационные и электронные технологии». Одеса. 2009. С. 145. Дисертантом визначені характеристики надлишкових систем числення, які забезпечують прискорення виконання арифметичних та логічних операцій в неавтономному режимі.

11. Дичка И.А. Метод воспроизведения функций в неавтономном режиме / И.А.Дичка, В.В.Жабина // Системи та засоби штучного інтелекту: тези доповідей Міжнародної наукової молодіжної школи. Донецьк: ІПШІ «Наука і освіта», 2009. С. 77-80. Дисертантом розроблено спосіб прискорення обчислення функцій в неавтономному режимі за рахунок табличного формування розрядів результату.

12. Жабіна В.В. Порівняння чисел у надлишковому поданні / В.В.Жабіна // 16 міжнародна конференція з автоматичного управління «АВТОМАТИКА-200». Тези доповідей. Чернівці: Книги-ХХІ, 2009. С. 142-143.

13. Zhabina V.V. Parallel information processing effectiveness improvement in data-flow systems / V.V.Zhabina // Сучасні комп'ютерні системи та мережі розробка та використання: Матеріали 4-ї Міжнародної науково-технічної конференції ACSN-2009. Львів: НВФ «Українські технології», 2009. С. 62-64.

14. Жабіна В.В. Додавання чисел у зміщених надлишкових системах числення / В.В.Жабіна // I наукова конференція «Прикладна математика та комп'ютинг ПМК-2009». К.: НТУУ «КПІ», 2009. С. 142-146.

15. Каспіч І.В. Імітаційна модель потокової системи з паралельним формуванням команд / І.В.Каспіч, В.В.Жабіна // Тринадцята Всеукраїнська (Восьма Міжнародна) студентська наукова конференція з прикладної математики та інформатики СНКПМІ-2010. Тези доповідей. Львів: ЛНУ, 2010. C. 175-176. Дисертантом розроблені алгоритми паралельного формування команд в системах, що керуються потоком даних, на базі пам'яті з адресним доступом.

16. Жабина В.В. Совмещение операций в системах счисления с большим основанием / В.В.Жабина // Розподілені комп'ютерні системи. Т1. Збірник праць ювілейної міжнародної конференції РКС-2010. Київ, НУТУ «КПІ», 2010. С. 190-192.

17. Жабіна В.В. Метод паралельного формування команд в потокових системах / В.В.Жабіна // Друга наукова конференція магістрантів та аспірантів, присвячена 20-річчю факультету прикладної математики, «Прикладна математика та комп'ютинг ПМК-2010». К.: Просвіта, 2010. С. 234-238.

18. Жабіна В.В. Підвищення ефективності обчислень у відмовостійких потокових системах / В.В.Жабіна // Искусственный интеллект. Интеллектуальные системы: материалы Международной научно-технической конференции ИИ-2010. Донецк: ИПИИ «Наука і освіта», 2010. С. 125-130.

АНОТАЦІЯ

Жабіна В.В. Методи і засоби підвищення ефективності реалізації дрібнозернистого паралелізму в системах реального часу. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. Національний технічний університет України «Київський політехнічний інститут», м. Київ, 2011 р.

Дисертаційна робота присвячена проблемі прискорення виконання алгоритмів реального часу з дрібнозернистою структурою і забезпечення відмовостійкості обчислювальних систем, побудованих на базі надвеликих інтегральних схем.

Обґрунтована можливість прискорення виконання послідовності залежних за даними операцій у системах з безпосередніми зв'язками між обчислювальними модулями. Для цього операції пропонується виконувати в режимі суміщення за допомогою обчислювальних модулів, що здійснюють паралельну обробку розрядів операндів у надлишкових системах числення з великою основою.

Розроблено новий метод обробки інформації в обчислювальних системах, керованих потоком даних, що дозволяє прискорити обчислення за рахунок збільшення інтенсивності завантаження обчислювальних модулів шляхом динамічного формування паралельних потоків команд.

Показана можливість прискорення відновлення працездатності систем, керованих потоком даних, при відмові обчислювальних модулів шляхом вдосконалення засобів контролю тривалості операцій та автоматичної реконфігурації.

Ключові слова: потокові системи, неавтономні обчислення, суміщення операцій, дрібнозернистий паралелізм, надлишкові системи.

АННОТАЦИЯ

Жабина В.В. Методы и средства повышения эффективности реализации мелкозернистого параллелизма в системах реального времени. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. Национальный технический университет Украины «Киевский политехнический институт», г. Киев, 2011 г.

Диссертационная работа посвящена проблеме ускорения реализации алгоритмов реального времени с мелкозернистой структурой и обеспечения отказоустойчивости вычислительных систем, построенных на базе сверхбольших интегральных схем.

На основе анализа алгоритмов обработки информации в реальном времени сформулированы требования к вычислительным системам. Показано, что такие системы должны обеспечивать высокую скорость обработки последовательно-параллельных алгоритмов с мелкозернистой структурой, что может быть достигнуто путем динамического распараллеливания вычислений на уровне обработки операндов и их разрядов.

Показано, что для реализации мелкозернистых алгоритмов нецелесообразно использовать классические многопроцессорные системы, поскольку в них используются сложные процедуры обмена данными, которые неприемлемы для обмена на уровне отдельных слов. Для таких систем более развиты статические средства параллельного программирования, которые определяют план выполнения задач по априорным характеристикам. Основные задачи распараллеливания решаются на этапе разработки программ, что не всегда позволяет обнаружить скрытый параллелизм задач из-за недостатка информации о реальной продолжительности процессов в системе.

Показано, что для реализации мелкозернистых алгоритмов более эффективно использовать потоковые вычислительные системы, в которых применяются динамические средства распараллеливания вычислений на нижнем уровне параллелизма. Приведена классификация таких систем, и выделены две их основные разновидности: потоковые системы с непосредственными связями между компонентами и системы, управляемые потоком данных, которые реализуют модели вычислений «data driven» и «data flow» соответственно.

Использование современной технологии проектирования (System on Chip - система на кристалле) позволяет ускорить создание систем на базе ПЛИС. Однако, со стороны элементной базы накладывается ряд ограничений, в частности, связанных с числом выводов и функциональными возможностями устройств в ПЛИС, которые должны учитываться при разработке методов вычислений.

Впервые предложены методы выполнения арифметических операций в смещенных избыточных системах счисления с большим основанием, позволяющие ускорить выполнение последовательности зависимых по данным операций в неавтономном режиме за счет параллельной обработки разрядов операндов в цепочке операционных устройств с поразрядным обменом данными. Увеличение основания системы счисления позволяет уменьшить общее количество циклов при заданной точности вычислений, в отличие от операций в симметричных системах счисления не требуется обрабатывать отрицательные приращения, что сокращает длительность циклов.

Впервые разработана методика и предложены средства выполнения операций с плавающей запятой в избыточных системах счисления с учетом особенностей поразрядной передачи информации между компонентами систем с непосредственными связями, позволяющие повысить точность вычислений при заданной длине разрядной сетки, обеспечить автоматическую нормализацию промежуточных результатов и ускорить обмен данными между узлами системы за счет перехода от синхронной к асинхронной передаче данных.

Предложен новый таблично-алгоритмический метод вычисления функций при поразрядном вводе и выводе информации в смещенных системах счисления, который в отличие от методов, использующих симметричные системы, не требует выполнения операций с отрицательными приращениями, что позволяет упростить аппаратную реализацию и уменьшить время вычислений. Усовершенствован метод «цифра за цифрой» для вычисления ряда функций путем обеспечения поразрядного ввода аргументов. Вычисление функций в неавтономном режиме может осуществляться совместно с выполнением арифметических операций, что расширяет возможности систем с непосредственными связями между вычислительными модулями.

...