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

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

Жабін Валерій Іванович

УДК 681.3

МЕТОДИ І ЗАСОБИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ

ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ РЕАЛЬНОГО ЧАСУ

Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі

А В Т О Р Е Ф Е Р А Т

дисертації на здобуття наукового ступеня

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

Київ - 2006 р.

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

Робота виконана в Національному технічному університеті України "Київський політехнічний інститут" Міністерства освіти і науки.

Науковий консультант - | доктор технічних наук, професор

Луцький Георгій Михайлович,

НТУУ "КПІ", завідувач кафедри обчислювальної техніки

Офіційні опоненти: | доктор технічних наук, професор

Додонов Олександр Георгійович,

Інститут проблем реєстрації інформації НАН України, заступник директора;

доктор технічних наук, професор

Погорілий Сергій Дем'янович,

Київський національний університет імені Т.Шевченка Міністерства освіти і науки України, заступник завідувача кафедри напівпровідникової електроніки;

доктор технічних наук, професор

Стасюк Олександр Іонович,

Київський університет економіки і технологій транспорту Міністерства освіти і науки України, завідувач кафедри інформаційних систем і технологій на залізничному транспорті.

Провідна установа | Інститут кібернетики ім. В.М.Глушкова НАН України, відділ логічного синтезу високопродуктивних машин, комплексів і систем спеціального призначення (відділ 125)

Захист відбудеться " 19 " червня 2006 р. о 14:30 на засіданні спеціалізованої ради Д 26.002.02 у НТУУ "КПІ" (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306).

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

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

Автореферат розісланий "_18_"__червня__ 2006 р.

Вчений секретар спеціалізованої ради, кандидат технічних наук, доцент |

М.М. Орлова

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

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

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

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

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

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

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

У той же час досягнення в області сучасної інтегральної технології дозволяють створювати на одному кристалі системи, що конфігуруються (CSoC – Configurable System on Chip). У загальному випадку мікросхеми містять обчислювальні ядра, пам'ять і програмувальну логіку (FPGA – Field Programmable Gate Arrays), Це дає потенційну можливість оптимально адаптувати апаратні засоби до конкретного застосування. Однак теоретичні основи побудови модульних систем з розподіленими апаратними засобами взаємодії, доступу до загального ресурсу, контролю і реконфігурації розроблені недостатньо.

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до планів науково-дослідних робіт кафедри обчислювальної техніки НТУУ "КПІ": НДР “Розробка обчислювальних засобів на базі мікропроцесорів для систем числового програмного управління”, № ДР 0183U078443, 1989-1993 рр. (автор – науковий керівник); НДР “Розробка багатофункціональної обчислювальної системі для СЧПУ”, № ДР 0195U027822, 1995-1997 рр. (автор – науковий керівник); НДР “Розробка високопродуктивних засобів для універсальної системи числового програмного управління”, № ДР 0196U022869, 1996-1997 рр. (автор – науковий керівник); НДР “Розробка високопродуктивних обчислювальних засобів для систем числового програмного управління”, № ДР 0197U017542, 1997-1998 рр. (автор – науковий керівник); НДР “Побудова високопродуктивних паралельних обчислювальних систем з архітектурою на основі розподіленої загальної пам’яті”, № ДР 0104U000356, 2004-2005 рр. (автор – виконавець).

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

Для досягнення даної мети необхідно вирішити наступні задачі:–

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отримані результати дозволяють:–

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

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

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

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

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

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

Теоретичні і практичні результати дисертаційної роботи впроваджені:–

у Державному науково-виробничому комплексі ”Курс” Виробничого об'єднання “Київський радіозавод” у багатопроцесорній системі числового програмного управління “Славутич МВС-01” для багатокоординатних високоточних верстатних комплексів і обробляючих центрів;–

у Державному науково-виробничому підприємстві ”Синтез” (м. Київ) у багатопроцесорній системі числового програмного управління “Славутич МВС-04” для багатокоординатних високоточних верстатних комплексів і обробляючих центрів;–

у Національному технічному університеті “Київський політехнічний інститут” на кафедрі обчислювальної техніки і на кафедрі спеціалізованих комп'ютерних систем у навчальний процес (використовуються при проведенні лекційних і лабораторних занять, при курсовому і дипломному проектуванні);–

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

Зазначені впровадження підтверджені відповідними актами.

Особистий внесок здобувача. Всі основні результати дисертації отримані здобувачем самостійно. У роботах, що опубліковані у співавторстві, здобувачеві належать: [6, 24, 27, 28, 34, 35] – методи підвищення ефективності обміну даними між процесорами в системах з неоднорідним доступом до пам’яті; [8, 9, 42] – ідея підвищення продуктивності паралельних систем за рахунок використання потокової моделі обчислень для виконання деяких функцій операційної системи; [16, 22] – запропоновано загальну концепцію автоматичного розподілу завдань між обчислювальними вузлами паралельної системи під управлінням потоку дескрипторів; [29, 40, 41] – загальна концепція підвищення ефективності потокових обчислювальних систем за рахунок підготовки даних і формування команд без застосування асоціативної пам’яті; [33, 36] – ідея забезпечення відмовостійкості потокових систем; [31, 37] – метод організації динамічних пріоритетів у розподілених арбітрах модульних обчислювальних систем; [2, 3, 14, 43] – концепція спрощення комунікаційного середовища обміну даними між операційними вузлами системи в інтегральному виконанні; [4, 25, 38] – ідея непрямого функціонального контролю операційних пристроїв в інтегральному виконанні; [23, 26, 30, 32] – концепція побудови програмно-апаратних засобів автоматичної реконфігурації та оновлення модульних паралельних систем.

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

1. Регіональний науково-технічний семінар “Мікропроцесори в системах контролю і управління” (жовтень 1989 р., Пенза, Росія).

2. Міжнародний симпозіум “Комп'ютери у Європі. Минуле, сучасне та майбутнє” (6-8 жовтня 1998 р., Київ, Україна).

3. Міжнародна науково-технічна конференція “Інтелектуальні багатопроцесорні системи – ІБС'99” (1-5 вересня 1999 р., Таганрог, Росія).

4. Міжнародна науково-практична конференція “Проблеми створення нових машин і технологій – 2000” (22-24 травня 2000 р., Кременчук, Украина).

5. Міжнародна науково-практична конференція “Штучний інтелект – ШІ’2002” (16-20 вересня 2002 р., Кацівелі, Крим, Україна).

6. Друга міжнародна науково-практична конференція “Сучасні інформаційні й електронні технологи – СІЕТ-2002” (13-17 травня 2002 р., Одеса, Україна).

7. Міжнародна науково-практична конференція “Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” (15-17 травня 2003 р., Хмельницький, Україна).

8. Міжнародна науково-технічна конференція “Інтелектуальні і багатопроцесорні системи – ІБС'2003” (22-27 вересня, 2003 р., Геленджик, Росія).

9. Міжнародна науково-технічна конференція “Scalable Systems and Computer Networks – SCALNET’2004” (28–30 вересня, 2004 р., Кременчуг, Україна).

10. Міжнародна науково-технічна конференція “Інтелектуальні та багатопроцесорні системи – ІБС’2005” (26 вересня - 1 жовтня 2005 р., Геленджик, Росія).

11. Міжнародна науково-технічна конференція "Advanced Computer Systems and Networks – ACSN-2005" (21–23 вересня 2005 р., Львів, Україна).

Публікації. За темою дисертації опубліковано 49 наукових праць, серед яких монографія, 21 наукова стаття в журналах та збірниках, 15 авторських свідоцтв і патентів, а також 12 публікацій за матеріалами конференцій. Основні результати опубліковані у фахових виданнях і охоплюють усі положення, що виносяться на захист.

Структура й обсяг дисертації. Дисертаційна робота складається із введення, восьми глав, виводів і додатків. Загальний обсяг роботи становить 397 сторінок друкованого тексту, 97 рисунків, 25 таблиць, і список використаної літератури з 257 найменувань.

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

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

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

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

Розглянуто способи опису архітектури і класифікація систем по різних ознаках. Відповідно до функціональної класифікації системи, що розглядаються, відносяться до класу MIMD (multiple instruction – multiple data). Показано, що одним з перспективних шляхів забезпечення вимог до систем РЧ є модульний принцип побудови, як апаратних, так і програмних засобів, що забезпечує створення типового ряду систем РЧ із різною продуктивністю і функціональними можливостями. Такий підхід дозволяє досить просто здійснювати резервування апаратури на рівні модулів для забезпечення заданої надійності й істотно прискорює процес адаптації систем до умов функціонування.

Розглянуто два основні різновиди систем класу MIMD, а саме: системи з загальною пам'яттю і системи з розподіленою пам'яттю. Показано, що в системах з розподіленою пам'яттю, до яких відносяться кластерна і масивно-паралельна архітектура (MPP – massive parallel processing), просто вирішується задача масштабування, але обмін інформацією здійснюється шляхом передачі повідомлень (пакетів), що часто не забезпечує необхідної реакції системи при управлінні швидкими процесами. Більш високу швидкість забезпечує механізм обміну даними через загальну пам'ять, що створює передумови для забезпечення максимальної реакції систем на зовнішні події. Крім того, конструктивні особливості побудови систем РЧ дозволяють створювати компактні вироби, що робить їх прийнятними при різних умовах експлуатації. Однак симетричні SMP-системи (SMP – symmetric multiprocessor) із загальною пам’яттю, що одержали широке поширення, мають істотний недолік, зв'язаний з обмеженими можливостями масштабування, що звужує область застосування таких систем.

Альтернативою розподіленим і симетричним системам є системи з неоднорідним доступом до пам'яті (NUMA – non uniform memory access). Сучасні NUMA-системи будуються на базі SMP-модулів, зв'язаних комунікаційним середовищем з пакетною передачею даних, тобто такі системи відповідають властивостям як розподілених систем, так і систем із загальною пам'яттю. Розшарування пам'яті знижує число конфліктів, що дозволяє збільшити максимальне число процесорів (наприклад, у системі IBM/Sequent NUMA-Q 2000 використовується до 256 процесорів). До основних недоліків архітектури NUMA варто віднести великий розкид часу доступу до різних розділів пам'яті (ефект неоднорідного доступу), що знижує продуктивність систем і створює проблеми розподілу структур даних у пам'яті при підготовці задач.

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

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

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

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

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

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

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

Зі збільшенням числа процесорів продуктивність систем також може збільшуватися, але залежність не є лінійної, оскільки збільшуються витрати часу на організацію спільної роботи процесорів. Ці витрати враховуються коефіцієнтом L, який можна розглядати як функцію де n – кількість процесорів; V – аргумент, що обумовлює втрати часу на організацію паралельної обробки інформації в процесорах; S – аргумент, що обумовлює втрати часу на обмін інформацією між пристроями системи

Показано, що на величину L впливають такі основні структурні ознаки:

- розподіл адресного простору процесорів;

- способи доступу до різних областей пам'яті процесорів;

- способи синхронізації процесів обміну інформацією.

На основі дослідження існуючих систем і тенденції їхнього розвитку в роботі запропонована класифікація систем, що враховує зазначені ознаки. Вона може бути корисна не тільки для характеристики систем, але й у процесі проектування, зокрема, на етапі вибору архітектури. Для наочного представлення конфігурації компонентів систем з обліком розглянутих класифікаційних ознак пропонується мова опису архітектури на функціональному рівні MSBС (master, slave, bus, control), що є розвитком графічних мов PMS (processor, memory, switch) і MSBI (master, slave, bus, interface), істотним недоліком яких є неможливість відображення управляючих потоків і розподілу адресного простору.

Архітектура представляється двійкою ,

де G – графічний опис з використанням уніфікованих функціональних позначень; K – карта розподілу адресного простору.

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

Графічний опис архітектури представляється орієнтованим (можливо зваженим) графом G=(E, C, F), де E – множина вершин, що відповідає компонентам архітектури; C – множина дуг, що відповідає напрямкові управляючих потоків; F – функціональні правила побудови графа.

З використанням функціональних елементів (рис. 1) на рис.2 показаний приклад опису системи.

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

Зокрема, моделі дають можливість:

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

- розробити способи доступу до загального системного ресурсу;

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

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

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

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

У якості базових розглядаються системи з локальною пам'яттю (система I), з комунікаційною пам'яттю (II) і з віконним доступом до пам'яті (III). Для порівняльної оцінки архітектур систем на функціональному рівні використовуються наступні характеристики:

- робочий обсяг пам'яті;

- час звертання до пам'яті;

- коефіцієнт ефективності використання комунікаційного середовища (системної магістралі).

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

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

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

tm – тривалість циклу звертання до модуля пам'яті (без обліку часу чекання доступу);

tal – час чекання доступу до локальної магістралі;

tag– час чекання доступу до системної магістралі;

tw – тривалість ініціалізації “вікна”.

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

Характерною рисою архітектури III є необхідність попередньої ініціалізації “вікна” при звертанні до локальної пам'яті інших процесорів. Якщо до "вікна" можуть звертатися кілька процесорів, то ініціалізація включає захоплення "вікна" (заборона доступу до ресурсу іншим процесорам) і його настроювання. Захоплення може бути здійснений з використанням семафорів у загальній пам'яті. Якщо "вікно" використовується іншими процесорами, то для перевірки семафора може знадобитися кілька спроб (максимальне значення кількості спроб позначене через P). Для розглянутих архітектур максимальні значення тимчасових характеристик приведені в табл. 2.

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

Для порівняльної оцінки ефективності використання системної магістралі в різних системах застосовується коефіцієнт KСМ, що визначається за формулою

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

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

Отримані аналогічним образом значення KСМ для різних архитектур при синхронізації процесів обміну по шинах даних зведені в табл. 3.

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

Проведений аналіз виявив “вузькі місця” відомих систем з неоднорідним доступом до пам'яті і показав необхідність підвищення ефективності обміну в централізованих системах, а також у децентралізованих системах з “віконним” доступом до пам'яті інших процесорів.

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

Показано можливість за рахунок використання ускладненого механізму “вікна” забезпечити трансляційний тип передач. Як випливає з графіка на рис. 3, величина співвідношення зі збільшенням M прагне до значення k, рівній кількості процесорів, яким передаються дані. З ростом M число звертань до системної магістралі в системах без апаратної підтримки трансляційних передач наближається до k, а системах з підтримкою – до одиниці.

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

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

Основною умовою функціонування систем є наявність загального адресного простору процесорів. Конфлікти при звертанні до загального адресного простору двох і більш процесорів дозволяються на апаратному рівні за допомогою арбітрів, що повинні надавати доступ до загального ресурсу тільки одному процесорові. Арбітр доступу до загального ресурсу є пристроєм, що транслює вектор запитів на доступ до ресурсу R={ ri | i= } у вектор сигналів надання доступу G= {gi | i= }.

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

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

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

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

Основна ідея методу полягає в автоматичному переносі початку ланцюжка по замкнутому контуру після чергового звертання до загального ресурсу з боку будь-якого процесора (рис. 4).

До складу кожного процесорного модуля ПМi (i=1,…,n) входить процесор Пi і блок арбітра БАi. Входи і виходи ланцюжка позначені відповідно через dii і doi. БАi може аналізувати стан лінії (вхід bsii) і змінювати його (вихід bsoi). У процесі роботи БАi може формувати сигнал sti початку пріоритетного ланцюжка.

Функціонування арбітра пояснюється графом автомата Мура на рис. 5.

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

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

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

СВП може виконувати спеціальні функції, наприклад, пов’язані із синхронізацією процесів.

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

Варіанти побудови потокових програм обслуговування запитів приведені на рис. 8. Вершини потокового графа відповідають акторам, а дуги – переданим токенам.

У вихідному стані вхідна дуга розмножувача (вершина 1) відзначена одиницею. Ця одиниця в процесі функціонування системи виконує функцію фішки.

Повторювач R у вершині 2 забезпечує просування фішки по кільцю, коли запити від процесів на доступ до ресурсу S відсутні. Для цього повторювач передає одиницю, одержувану від розмножувача, на дугу вентиля T/F.

Команда OUT повертає процесові дані, що передає йому вентиль T/F, за адресою, зазначеному в другому токені. Адреса відповіді визначається процесом.

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

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

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

- забезпечити автоматичне распараллеливание алгоритмів з "дрібнозернистою" структурою при наявності в складі спецвычислителя декількох обчислювальних модулів;

- реалізація деяких функцій операційної системи.

Таким чином, застосування потокового обчислювача створює передумови для