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

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

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

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

Автореферат

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

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

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

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

Растгу Садег

Київ - 2009

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

Робота виконана на кафедрі обчислювальної техніки Національного технічного університету України “Київський політехнічний інститут” Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент

Корочкін Олександр Володимирович,

Національний технічний університет України “Київський

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

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

Зайцев Володимир Григорович,

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

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

Клименко Ірина Анатоліївна

Національний авіаційний університет, м. Київ, доцент кафедри комп'ютерних систем та мереж

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

Актуальність теми. Паралельні системи з кластерною архітектурою складають клас систем, які забезпечують побудову високопродуктивних обчислювальних систем, оптимальних за критерієм ціна/продуктивність. Поширення сфери їх використання (в останньому рейтингу ТОР500 представлені 425 кластерних систем, при цьому рейтинг очолює кластерна система Roadrunner-BladeCenter QS22/LS21 Cluster) ставить завдання вдосконалення структурної і програмної організації кластерних систем. Традиційно підвищення продуктивності кластерних систем (КС) пов'язано зі збільшенням кількості вузлів системи. Однак зростання кількості вузлів обмежено пропускною спроможністю системи зв'язків вузлів, яка базується на мережних технологіях. Другий шлях удосконалення КС пов'язаний з підвищенням обчислювальної потужності вузлів. Для цього вузли КС реалізуються за допомогою високопродуктивних богатопроцесорних робочих станцій. Поява мультиядерних процесорів відкриває нові можливості для підвищення обчислювальної потужності вузлів і кластерної системи в цілому.

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

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

Існуючі моделі паралельних обчислень (Ю.Капітонова, О.Летичевський, І.Сергієнко, Ч.Хоар, Р.Мільнер, Л.Лампорт, Г.Дегано, К.Петрі, Г. Кан, Дж.Деннис, В.Воеводин, В.Топорков, М.Єршов та інші) ставлять різні мети. З точки зору опису взаємодії процесів розвинутий математичний апарат представлений у теорії послідовних взаємодіючих процесів Ч.Хоара (CSP теорії). Однак використання CSP теорії потребує її подальший розвиток з урахуванням особливостей взаємодії процесів у КСМА, де використовуються дві моделі взаємодії, які основані на спільних змінних і передаванні повідомлень, в той час як у CSP теорії розглядається лише модель передавання повідомлень. Важливою особливістю моделей, створених на базі CSP теорії, є також спрощення їх реалізації за рахунок того, що більшість сучасних мов та бібліотек паралельного програмування базується на концепції послідовних взаємодіючих процесів.

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

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

- НДР № 0102U000333 "Побудова масштабованих ізоєфективних комп'ютерних систем", яка виконувалась на кафедрі обчислювальної техніки НТУУ "КПІ" у 2002-2006 рр.;

- НДР № 0201U006269 "Побудова високопродуктивних паралельних обчислювальних систем з архітектурою на основі розподіленої загальної пам'яті", яка виконувалась на кафедрі обчислювальної техніки НТУУ "КПІ" у 2004-2008 рр.

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

Для досягнення цієї мети в роботі були розв'язані наступні основні завдання:

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

- аналіз особливостей організації обчислювальних процесів у КСМА, які пов'язані з ускладненням структурної організації системи;

- класифікація методів організації взаємодії паралельних (розподілених) процесів;

- розробка моделей обчислень, які дозволяють описати поведінку і взаємодію процесів у КСМА на рівні вузлів системи при різноманітній організації системи зв'язку вузлів;

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

- розробка способу створення додатків для КСМА на основі запропонованих моделей обчислень;

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

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

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

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

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

При цьому отримано такі наукові результати:

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

2. Запропоновано та обґрунтовано поширення CSP теорії шляхом введення об'єктів комунікації та синхронізації, необхідних для опису і подальшого аналізу взаємодії процесів у КСМА.

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

4. Запропоновано і обґрунтовано аналіз коректності взаємодії процесів у КСМА, який ґрунтується на використанні запропонованих моделей обчислень, що дозволяє виявити помилки ще на етапі проектування програмних компонент.

5. Дістала подальший розвиток технологія створення програмних компонент КСМА на основі запропонованих моделей обчислень, яка дозволяє покращити якість програмного продукту та скоротити час його розробки.

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

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

Особистий внесок здобувача. Усі положення, що становлять суть дисертації, сформульовані та вирішені автором самостійно. В роботах, що були опубліковані у співавторстві, здобувачеві належить: [1] - модифікований механізм захищених модулів для вирішення задачі взаємодії процесів, [2] - спосіб використання механізму посилання повідомлень для симетричних мультипроцесорних систем, [5] - порівняльний аналіз засобів синхронізації для мультипроцесорних систем, [6] - математична модель для опису процесів у вузлах КСМА.

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

- Друга міжнародна конференція "Сучасні комп'ютерні системи та мережі: розробка та використання ACSN2007" (20-22 вересня 2007 р., м. Львів, Україна);

- Міжнародна науково-технічна конференція "Комп'ютерні системи і мережні технології" (17-19 березня 2008 р., м. Київ, Україна);

- IV Міжнародна науково-технічна конференція "Сучасні інформаційно-комунікаційні технології/COMINFI'2008" (15-19 вересня 2008 р., АР Крим, Ялта - Лівадія;

- наукові семінари кафедри обчислювальної техніки НТУУ “КПІ”.

Публікації. Основні результати дисертації викладені у 6 наукових публікаціях, з них 4 статті у фахових виданнях, що входять до переліку ВАК України (дві статті без співавторів ), та 2 - у матеріалах конференцій.

Структура то обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, списку використаних джерел, та додатків. Обсяг дисертаційної роботи становіть 146 сторінок, в тому числі 135 сторінок основного тексту, 40 рисунків, 9 таблиць, список використаної літератури із 74 найменувань.

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

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

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

У другому розділі запропонований підхід до вирішення завдання аналізу особливостей структурної організації КСМА з метою подальшої можливості ефективної організації обчислювальних процесів. Підхід базується на створенні математичних моделей обчислень, які дозволять представити КМСА як набір паралельних взаємодіючих об'єктів. Для створення математичної моделі використовувалась теорія взаємодіючих послідовних процесів (CSP теорія). На основі CSP теорії КСМА розглядалась як складана система, яка включає набір об'єктів, що функціонують паралельно і взаємодіють. Визначено два рівня КСМА: рівень вузлів системи (модель КСМА1) та рівень вузла системи (модель КСМА2), який побудований з використанням багатоядерних процесорів.

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

бС = { С.введення, С.виведення, С.прийняти.К_i,

С.передати.К_i С.обчислення },

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

Алфавіт клієнтського об'єкту включає події

бК_i = { К_i.прийняти.С, К_i.передати.С, К_i.обчислення ,

К_i.прийняти.К_j , К_i.передати.К_j },

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

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

для серверного об'єкту

С = ( С.введення С.передати.К_i С.обчислення

С.прйиняти.К_i С.виведення ),

для клієнтського об'єкту:

- при взаємодії виключно через серверний об'єкт

К_i =( К_i.прийняти.С К_i.обчислення К_i.передати.С ),

- при взаємодії з серверним об'єктом та з іншими клієнтським об'єктами

К_i =( К_i.прйиняти.С К_i.передати.К_j К_i.обчислення

К_i.прийняти.К_j К_i.передати.С ).

Модель обчислень першого рівня (КСМА1) реалізує паралельну поведінку сервера та множини клієнтів:

КЛІЄНТИ = ( К1 || К2 || . . .|| КР ) , СЕРВЕР = ( С )

КСМА1 = (СЕРВЕР || КЛІЄНТИ ).

Важливою частиною поведінки об'єктів у моделі КСМА1 є їх взаємодія. Для моделі КСМА1 ця взаємодія закладена у події Х.прийняти.Y та Х.передати.Y , де об'єкт Х передає (приймає) дані від об'єкту Y. У CSP теорії взаємодія розглядається як подія, в якій приймають участь два об'єкти і яка пов'язана з передаванням повідомлень. Для цього використовується поняття каналу, куди один процес записує дані, а другий - зчитує з каналу дані. При цьому процеси синхронізують свої дії, тобто передавання даних здійснюється тільки при одночасному зверненні процесів до каналу.

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

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

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

Алфавіт об'єкта комунікації включає події, які тепер пов'язані з передаванням та прийманням виклику об'єкту комунікації:

бОК = { ОК.передати, ОК.прийняти },

а процес, який описує поведінку об'єкту комунікації, задається рекурсивним співвідношенням

ОК = (( ОК.прийняти | ОК.передати ) ОК ).

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

Правіло 1. Визначає необхідну умову взаємодії процесів через ОК відносно алфавітів процесів: “Якщо Р і Q процеси, Z - об'єкт комунікації, то необхідною умовою взаємодії Р і Q через Z є виконання співвідношення бZ ( бP бQ ) “.

Правило 2. Визначає необхідну умову взаємодії процесів через ОК відносно поведінки цих процесів: “Якщо Р і Q процеси, Z - об'єкт комунікації, то необхідною умовою взаємодії Р і Q через Z є дії

Z = (( Z.прийняти | Z.передати ) Z )

P = (( Z.передати) P ) , Q = (( Z.прийняти) Q )

( Z // (P || Q ))”.

В роботі показано, що за допомогою математичної моделі КСМА1 має бути виконаний аналіз причин виникнення тупикових ситуацій при взаємодії об'єктів через ОК. Для об'єкту комунікації ОК( Д, Н, В, Б) тупикова ситуація може виникнути при взаємодії процесів P i Q у разі якщо:

- фактичні параметри для ОК.Д в процесах P i Q не відповідають значенню формальних параметрів у об'єкті ОК при динамічному формуванні параметрів;

- параметри ОК.Н не відповідають напрямку передавання (приймання ) даних, яке заплановано у об'єкті комунікації;

- має місце асинхронна взаємодія, яка пов'язана з прийманням даних;

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

У роботі також запропонована математична модель обчислень для другого рівня КСМА (модель КСМА2). Вузол розглядається як сукупність об'єктів майстер та робочий, які визначають дії, пов'язані з використанням у вузлі багатоядерного процесору. Об'єкт майстер (М) відповідає за зв'язок з іншими вузлами КСМА. Об'єкт майстер приймає вхідні дані від сервера КСМА, розподіляє їх по інших об'єктах у вузлі, збирає результати обчислень у вузлі та відсилає результат в серверний вузол КСМА. Об'єкт робочий (Р) приймає дані від об'єкта майстер, виконує обчислення та повертає результат об'єкту майстер.

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

Для розподіленої архітектури побудови зв'язку ядер набір подій, що пов'язані з об'єктом майстер i-го вузла (М_i), можна представити у вигляді

бМ_i = { М_i.передати.P_ij, М_i.обчислення, М_i.прийняти.P_ij }.

Набір подій, пов'язаних з об'єктом j-ий робочий i-го узла (P_ij) можна представить у вигляді

бP_ij = { P_ij.прийняти.Х_i , P_ij.передати.Х_i , P_ij.обчислення,

P_ij.прийняти.P_iк, P_ij.передати.P_iк}.

Поведінка майстер об'єкта М_i (процес майстер) при використанні алфавіту бМ_i :

М_i = ( М_i.передати.P_ij М_i.обчислення М_i.прийняти.P_ij ).

Поведінка об'єкту робочий P_ij (процес робочий):

P_ij = ( P_ij.прийняти.М_i P_ij.обчислення P_ij.передати.М_i ).

Модель обчислень другого рівня КСМА2 для i-го клієнтського вузла можна описати як паралельну комбінацію поведінки процесів М_i та P_ij :

МАЙСТЕР_i = (М_i), РОБОЧИЙ_i = (P_i1 || P_i2 || . . . || P_iк || )

ВУЗОЛ_i = ( М_i || РОБОЧІ_i ).

Система зв'язків ядер у сучасних багатоядерних процесорах побудована на використанні спільної пам'яті. При цьому можливо використання обох моделей взаємодії процесів - за допомогою спільних змінних або посиланням повідомлень. В CSP теорії взаємодія на основі спільних змінних не розглядається, тому що для взаємодії процесів прийнята тільки одна модель посилання повідомлень. У роботі запропоновано поширення засобів алгебри процесів Т.Хоара для опису взаємодії процесів через спільні змінні. Для цього виконано аналіз існуючих засобів роботи зі спільними змінними, на підставі якого введено поняття об'єкту синхронізації (ОС), який використовується процесами при взаємодії через спільну пам'ять. Виділено три види об'єктів синхронізації. Перший вид ОС.А пов'язаний з організацією неділимих операцій над змінними. Другий вид (складається з двох типів об'єктів синхронізації ОС.S та ОС.К ) дозволяє виконувати контроль процесів по використанню спільних змінних. Третій вид ОС.M базується на контролі безпосередньо спільних змінних.

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

бА = { А.опис(Т) }.

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

бS ={ S.встановлення_сгнл, S.перевірити, S.встановлення_несгнл }.

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

бК ={ К.захватити(Р) }.

Об'єкт синхронізації типа M. Алфавіт об'єкту визначає події, що пов'язані з контролем безпосереднє спільних змінних:

бМ ={ M.запис, M.читання, M.обчислення,

M.чекати, M.сигнал, М.несигн }.

У роботі розглянуто використання запропонованих об'єктів синхронізації для вирішення основних задач, що виникають при застосуванні моделі спільних змінних: задачі взаємного виключення та задачі синхронізації процесів. Процес об'єкта синхронізації OС розглядається як підлеглій процес (підпроцес) до процесу Х і має місце співвідношення ОС // Х = ( OС || X ) \ бOС. При цьому бОС бХ і б( ОС // Х ) = ( бOС - бX ).

При взаємодії процесів М і Р через іменований ОС а справедливо співвідношення ( а: ОС // (М || P )). Підпроцес а: ОС розглядається як ресурс, який поділяється процесами М і Р і використовується для взаємодії. Важливим моментом поведінки процесів М і Р є взаємовиключний доступ до а, тобто має місце чергування ( М ||| Р ).

Об'єкт ОС.А забезпечує рішення тільки завдання взаємного виключення по відношенню до спільного ресурсу Т. Процес, який описує поведінку об'єкту А, виконує необхідну операцію А.опис(Т), а потім веде себе як А:

А = ( А.опис(Т) А ).

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

Об'єкт ОС.S забезпечує рішення обох основних задач взаємодії процесів. Процес, який описує поведінку об'єкту S, пов'язаний з початковим встановленням об'єкту синхронізації S, а потім - виконання дій, яки пов'язані з перевіркою та зміною стану процесу :

S = ( ( S.встановлення_сгнл | S.встановлення_нсгнл )

( ( S.встановлення_сгнл | S.перевірити ) S ) ) ).

Звернення процесів до спільного ресурсу пов'язане з наступними подіями у об'єктах Х і Р:

Х: ( S.перевірити X.обчислення S.встановлення_сгнл),

Р: ( S.перевірити P.обчислення S.встановлення_сгнл).

При синхронізації процесів, коли об'єкт Х посилає сигнал об'єкту Р про подію, взаємодія пов'язана з наступними діями у процесах Х і Р:

Х: (S.перевірити), Р: (S.встановлення_сгнл).

Об'єкт ОС.К орієнтований виключно на вирішення задачі взаємного виключення:

К = ( К.захватити(Р) К ).

Параметр Р в ОС.К пов'язаний з дією ( Х.обчислення ) у процесі Х, яка виконується з використанням спільних змінних. Подія Х.обчислення є частиною дії К.захватити(Р), тобто К.захватити Х і Р = Х.обчислення. Відмінність об'єкту ОС.К від об'єкту ОС.S полягає у об'єднанні дій перевірити і встановлення_сгнл..

Об'єкт ОС.M дозволяє вирішення задачі взаємного виключення і синхронізації. Взаємне виключення: поведінка об'єкту М при вирішенні задачі взаємного виключення: М ( (М.запис | М.читання | М.обчислення ) М ). Звернення процесів до спільного ресурсу пов'язано з наступними подіями у опису поведінки об'єктів Х і Р:

Х: ( M.запис, M.читання, M.обчислення ),

Р: ( M.читання, M.запис, M.обчислення ).

Синхронізація процесів через ОС.M пов'язана з наступними діями у процесах Х і Р, якщо процес Х чекає на сигнал від процесу Р:

Х: ( М.сигнал ), Р: ( М.чекати ).

При цьому поведінка об'єкту ОС.M описується як

M = ( (М.несигн ) (( М.чекати | М.сигнал ) M ) ).

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

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

Застосування об'єкту ОС.S у задачах взаємного виключення та синхронізації пов'язано з операцією S.перевірити, яка потенційно є операцією, що блокує процес в залежності від виконання визначених умов. Розблокування процесу виконується іншим процесом за допомогою операції S.встановлення_сгнл. Тупикова ситуація виникає при виконанні процесом операції S.перевірити, якщо ОС.S має несигнальний стан і процес блокується. Існує дві причини, які викликають тупикову ситуацію для ОС.S. Перша пов'язана з встановленням початкового значення ОС.S, друга - з відсутністю дії S.встановлення_сгнл, або ії виконання відносно до іншого об'єкту синхронізації. Застосування об'єктів ОС.S пов'язане з встановленням початкового значення об'єкту синхронізації в залежності від типу задачі, що вирішується. В CSP теорії запропоновано поняття початкового меню процесу Х, яке є множина подій В, F(х) - вираз (функція), що визначає процес для всіх значень х з В: ( х : В F( х ) ).

Коректне використання об'єкту ОС.S повинно включати початкове меню у вигляді

- множина В : { S.встановлення_сгнл, S.встановлення_несгнл };

- функції F(х) : S.встановлення_сгнл при вирішенні задачі взаємного

виключення;

S.встановлення_несгнл для задачі синхронізації.

Об'єкт синхронізації ОС.К використовується виключно для вирішення задачі взаємного виключення. Тупикова ситуація може виникнути тільки у випадку, коли при створенні об'єкту синхронізації ОС.К він буде встановлений у блокований стан. На відміну від ОС.S зміна стану ОС.К є неможливою внаслідок об'єднання в дії К.захватити(Р) обох дій S.встановлення_сгнл та S.встановлення_несгнл. Для запобігання тупикової ситуації слід під час створення ОС.К автоматично встановити його стан як незайнятий.

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

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

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

В моделі КСМА1 взаємодія процесів пов'язана з передаванням даних між вузлами КСМА. Стандарт мови (Annex E “Distributed systems”) орієнтований на використання виклику віддалених процедур (RPC механізму). Реалізація об'єкту комунікації (ОК) через віддалену процедуру дозволяє описати специфікацію ОК за допомогою специфікації процедури, де визначаються кількість і тип параметрів, напрям передавання (in) або приймання (out): кластерний мультиядерний архітектура

package Data is

pragma Remote_Procedure_Call(Data);

procedure Обчислення (МА,МВ:in Матриця; МС: out Матриця);

procedure Передавання(МX :in Матриця; С : in Вектор);

pragma Asynchronous(Передавання);

end Data;

Об'єкт комунікації у цьому випадку має параметри, які представлені у табл.1. Видно, що RPC механізм дозволяє реалізувати всі параметри об'єкту комунікації крім ОК.Б.

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

Таблиця 1.

Параметри об'єктів комунікації :

Об'єкт комунікації (ОК)
Обчислення()	ОК.В	Синхронний - C
	ОК.Б	Небуферизований
	ОК.Д	ОК.Н
	МА	Матриця	in
	МВ	Матриця	in
	МС	Матриця	out
Об'єкт комунікації (ОК)
Передавання()	ОК.В	Асинхронний - A
	ОК.Б	Небуферизований
	ОК.Д	ОК.Н
	МX	Матриця	in
	C	Вектор	in

В моделі КСМА2 реалізація взаємодії процесів через об'єкти комунікації базується на використанні механізму рандеву. Основа механізму - оператор входу (entry), який дозволяє передавання даних між процесами. Реалізація об'єкту комунікації (ОК) через вхід дозволяє описати специфікацію ОК за допомогою специфікації входу, де визначаються кількість і тип параметрів, напрям передавання (in) або приймання (out): entry Данні(МВ: in Матриця; А : out Вектор). За допомогою оператора select можливе формування інших параметрів об'єкту комунікації, таких як ОК.Н та ОК.В.

Реалізація об'єктів синхронізації в мові Ада може бути здійснена кількома засобами. Об'єкт синхронізації типу ОС.А реалізується за допомогою атомік змінних, які описуються через прагми Atomic і Volatile. Два види прагм Atomic і Atomic_Component дозволяють забезпечити синхронізований (поділяємий) доступ до змінних по читанню та запису, а також виконанню дій зі змінними безпосередньо у пам'яті.

Об'єкт синхронізації типу ОС.S реалізується за допомогою механізму семафорів, який базується на пакеті Ada.Synchronous_Task_Control. Пакет визначає бінарний логічний тип для створення семафорного об'єкту (Suspension_Object), та операції (дії), необхідні при роботі з ОС.К:

S.встановлення_сгнл =>

procedure Set_True(S: inout Suspension_Object)

S.перевірити =>

procedure Suspend_Until_True(S: inout Suspension_Object)

S.встановлення_несгнл =>

procedure Set_False(S: inout Suspension_Object).

Реалізація об'єкту синхронізації типу ОС.К у мові не передбачена. Існує ефективна реалізація ОС.К у мовах програмування Java i C# через критичні секції і замки.

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

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

У четвертому розділі розглянуто питання використання запропонованих моделей обчислень для розробки програмного забезпечення для КСМА.

При проектуванні виконується аналіз структурної організації КСМА, обирається модель паралельного програмування і створюються моделі обчислень КСМА1 і КСМА2. Потім виконуються наступні кроки. Крок 1 пов'язаний з розробкою паралельного алгоритму вирішення задачі. Крок 2 визначає дії по формуванню алгоритмів процесів сервера і клієнтів, які пов'язані з передаванням даних і результатів, а також безпосередньо з обчисленнями. При цьому кроки цих алгоритмів описуються через алфавіти серверних і клієнтських об'єктів, що наведені у моделі КСМА1. Крок 3 пов'язаний з формуванням алгоритмів процесів об'єктів майстер і робочий, які описуються через алфавіти, що наведені у моделі КСМА2. Далі обираються конкретні види об'єктів комунікації та синхронізації, через які буде організована взаємодія процесів. Крок 4 пов'язаний з розробкою схем взаємодії процесів, де будуть використані обрані об'єкті комунікації і синхронізації. На рис. 1 представлена схема такої взаємодії. У якості об'єкту комунікації для взаємодії серверу і клієнтів обрані віддалені процедури ( процедура Скп()).

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

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

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

В роботі наведені результати експериментальних досліджень ефективності теоретичних результатів роботи при побудові реальної кластерної системи та розроблення для неї програмного забезпечення з використанням моделей КСМА1 і КСМА2.

У додатках наведено листінги програм для КСМА з різною структурною організацією.

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

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

1. На основі аналізу структурної організації сучасних КСМА визначені основні фактори, що впливають на ефективність організації обчислювальних процесів у КСМА.

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

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

4. Запропоновано і обґрунтовано вдосконалення CSP теорії шляхом введення поняття об'єктів комунікації та синхронізації, що дозволяє реалізувати складні види взаємодії процесів у КСМА.

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

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

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

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

1. Растгу Садег. Экспериментальный анализ эффективности языка Ада при программировании для СМП систем / Растгу Садег, Викаш Ровто, А.Корочкин // Вісник НТУУ “КПІ”: Інформатика, управління та обчислювальна техніка. - 2005. - № 43. - С. 32 - 41. (Здобувачу належить модифікований механізм захищених модулів для вирішення задачі взаємодії процесів).

2. Растгу Садег. Экспериментальный анализ эффективности механизма рандеву при программировании для СМП систем / Растгу Садег, С.Корочкин, А.Корочкин // Вісник НТУУ “КПІ”: Інформатика, управління та обчиcлювальна техніка. - 2006. - № 45. - С. 10 - 16. (Здобувачуем запропоновано і проаналізовано використання механізму посилання повідомлень для симетричних мультипроцесорних систем).

3. Растгу Садег. Способ управления трафиком в мобильных системх АТМ / Растгу Садег // Вісник НТУУ “КПІ”: Інформатика, управління та обчислювальна техніка. - 2007. - № 47. - С. 318-323.

4. Растгу Садег. Моделирование вычислительных процессов в кластерных системах с многоядерной архитектурой / Растгу Садег // Вісник НТУУ “КПІ”: Інформатика, управління та обчислювальна техніка. - 2008. - № 48. - С. 58 - 61.

5. Rаstgоо Sadegh. Experimental Performance Analysis of Shared Variable-based and Message-based Models in Prоgramming for SMP Systems / І.Zhukov, А. Mustafa, А.Korochkin, Rаstgоо Sadegh // Advanced Computer Systems and Networks: Design and Application (ACSN-2007): 3-th International Conference, 20 - 22 Sept., 2007: proceedings. - Lviv. - 2007. - pp. 60-64. (Здобувачем виконано порівняльний аналіз засобів синхронізації для мультипроцесорних систем).

6. Растгу Садег. Организация вычислений в кластерных системах с многоядерной архитектурой / Растгу Садег, С. Корочкин // Комп'ютерні системи та мережні технології: міжнар. наук. - технічн. конф., 17 - 19 берез. 2008 р.: збірник наукових праць. - 2008. - вип. 1 (23). - С. 143 - 146. (Здобувачу належіть математична модель для опису процесів у вузлах КСМА).

АНОТАЦІЯ

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

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

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

У дисертаційній роботі виконано аналіз структурної організації сучасних КСМА і особливостей організації обчислювальних процесів в таких системах. КСМА представляє собою складну систему з двома рівнями паралельної обробки інформації (між вузлами і всередині вузла) і тому організація обчислювальних процесів потребує попереднього аналізу системи. Такий аналіз можливий на основі побудови математичної моделі обчислень, яка відображає особливості структурної організації КСМА і створює основи для проектування процесів, їх аналізу, організації взаємодії процесів та наступної реалізації. Для реалізації таких моделей в роботі була використана теорія послідовних взаємодіючих процесів Ч.Хоара (CSP теорія), яка дозволила представити КСМА як набір об'єктів, які виконуються паралельно і взаємодіють. Для кожного рівня КСМА запропоновано математичні моделі обчислень (моделі КСМА1 і КСМА2), які дозволили описати особливості організації процесів на рівні вузлів і в середині вузлів. Основна увага при цьому приділена організації взаємодії процесів. Запропоновано удосконалення CSP теорії шляхом запровадження об'єктів комунікації і синхронізації, які дозволяють описати різні форми взаємодії процесів, що мають місце у КСМА. На підставі запропонованих моделей розглянуто можливість аналізу коректності взаємодії процесів на виникнення тупикових ситуацій. Визначені правила запобігання тупикових ситуацій при використанні моделей, які базуються на спільних змінних і посиланні повідомлень.

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

...