Київський національний університет імені Тараса Шевченка
Радіофізичний факультет
Кафедра комп’ютерної інженерії
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОГО ПІДХОДУ ПРИ ПРОГРАМУВАННІРОЗПОДІЛЕНИХ ЗАДАЧ ДЛЯ КЛАСТЕРУ НА ПРИКЛАДІ ТЕХНОЛОГІЇ DRYADLINQ
Київ 2010
/>Реферат
Випускна кваліфікаційна робота бакалавра ____с., 10 рис., 4 додатки,17 джерел.
Реалізовано обчислювальну задачу для кластера привикористанні функціонального підходу у програмуванні, а саме технології DryadLINQ.Попередньо встановлено на всіх вузлах кластера та на клієнтськіймашині DryadLinq Pack. Продемонстровано роботу DryadLINQ та описані її основні частини.Також проаналізовано ефективність роботи DryadLINQ на різній кількості вузлів кластерадля обчислення одної і тої ж задачі. В якості прикладу обчислювальної задачі обранообрахунок інтегралу методом Монте-Карло.
Ключові слова: WINDOWS HPC, LINQ, DRYADLINQ, LINQTOOBJECT, MPP, ФУНКЦІОНАЛЬНЕ ПРОГРАМУВАННЯ,ІМПЕРАТИВНЕ ПРОГРАМУВАННЯ, МЕНЕДЖЕР РОБІТ.
Зміст
Вступ
1. Огляд літератури
1.1 Поширення систем длявисокопродуктивних обчислень
1.2 Функціональне програмування
1.3 Microsoft HPC 2008
1.4 Технологія Dryad та DryadLinq як розширенняLinqToObject
2.Реалізації розподіленої програми з використанням DryadLINQ
2.1 Структура та налаштування кластерноїсистеми
2.2 Файликонфігурації
2.3 Представлення колекцій даних
2.4 Файлметаданих
2.5 Бібліотеки LinqToDryad. dll та System. Threading. dll
2.6Виконання роботи Dryad
Висновки
Перелікпосилань
Додатки/>Вступ
При програмуванні задач для паралельних обчислювальнихсистем виникають наступні складності урозробника: необхідно програму розбивати на потоки, контролювати їх виконання тазабезпечувати обмін між ними. При цьому код програми стає громіздким та тяжким длячитання. В цих умовах виникає необхідність простої та ефективної методикипрограмування задач для паралельних обчислювальних систем. Концепціяфункціонального програмування надає можливість позбавитися від вищезгаданих проблем.При використанні інструментальних засобів які будуть виконувати всі дії по розпаралеленнюпрограми, програмування для паралельних обчислювальних систем стає звичайною задачеюфункціонального програмування. Отже розробнику непотрібно замислюватися над особливістюпаралельних обчислювальних систем, а саме над розпаралеленням створюваної програми.Як наслідок є поява таких технологій як Dryad, Hadoop, MapReduce та інші. В данійроботі досліджується застосування платформи Dryad та технології DryadLINQ, побудованій на базі мови інтегрованих запитів LINQ в мові програмуванняC# для кластерних систем Microsoft Windows HPC.
/>1. Оглядлітератури 1.1 Поширення систем для високопродуктивних обчислень
Родоначальниками машин для високопродуктивних обчисленьбули системи, що використовували спеціальні процесори, складні комунікаційні рішення,що володіли великим енергоспоживанням і вартістю. Вартість обумовлювалась унікальністювстановлюваного обладнання, в першу чергу процесорів.
З переходом на архітектуру MPP (Massive ParallelProcessing) — масову паралельну обробку, де використовувалося велике число серійновипущених процесорів, вдалося помітно знизити витрати на створення суперкомп'ютерів,оскільки не використовувалися вже розроблені технології. Основна вартість і складністьтепер полягала у використанні спеціальних комунікаційних рішень для зв'язку цихпроцесорів.
«Беовульф», створений в 94-му році- обчислювальний комплекс (кластер) на основі звичайних комп'ютерів,об'єднаних мережею, з поширеною та доступною операційною системою (зазвичай Linux).Переваги очевидні — всі компоненти легко можна купити і зібрати, відсутність спеціалізованихрішень і компонент значно знизило витрати. Мінусом є більш низька швидкість обмінуданими між вузлами, з огляду на використання звичайної комп'ютерної мережі.
Реалізація проекту Беовульф призвела до виникненнявеликої кількості послідовників, бо вона заклала основу для значно більш низькихза вартістю високопродуктивних обчислень. Прикладом може стати система Авалон, якабула зібрана в 98-му році і містила до 140 процесорів Alpha 21164A 533МГц. Йоговартість становила приблизно 313 тисяч доларів, а продуктивність була на рівні суперкомп'ютераз 64-ма процесорами SGI Origon 2000, чия вартість була близько 1,8 мільйонів доларів.В 2000 році в top500 кількість кластерних рішень становило 2. 2%, в 2004 — 57,8%,а в 2009 — 81,2%. Динаміка розвитку представлена на Рис. 1. 1:
/>
Рис. 1.1. Динаміка розвитку супер ЕОМ.
Під кластером тут розуміється обчислювальна системана архітектурі MPP (Massive Parallel Processing) де засобами зв’язку між вузлами використовуєтьсяEthernet, Myrinet, InfiniBand або іншими відносно недорогими мережами. Як наслідок- повільний обмін між вузлами кластера. Тому в числі найважливіших робіт є розвитокпаралельних обчислювальних технологій, а саме:
1. Розпаралелювання обчислень, створення новихметодів та алгоритмів, орієнтованих на ефективне використання в багатопроцесорнихсистемах, а також модернізація існуючих з реалізацією можливостей широкого паралелізму.
2. Розробка систем паралельного програмування,мовних та інших засобів із збереженням наступності прикладних програмних комплексівпо відношенню до апаратних побудов розподіленої обчислювальної мережі.
3. Створення програмного забезпечення функціонуваннябагатопроцесорних систем, у тому числі комунікаційної мережі обчислювальних модулів(ОМ) і між ОМ і зовнішніми абонентами.
4. Розробка архітектур багатопроцесорних обчислювальнихсистем. Інженерне конструювання ОМ та обчислювального поля в цілому.
5. Побудова і задіяння розподілених обчислювальнихта інформаційних систем (кластерів робочих станцій, багатомашинних комплексів таін.) 1.2 Функціональне програмування
Функціональне програмування (далі ФП) — наступнийетап після імперативного програмування (ІП). Код написаний за допомогою ФП навідміну від ІП може звестися до декількох рядків, відповідно він легшечитається та відлагоджується. Тобто тут основний акцент робиться на функції. Функціональнеобчислення — функція (або якщо бути точніше — «чиста функція», pure function)- приймає вхідні аргументи на вході, робить певні обчислення і повертає деякий результат.При цьому функція не створює ніяких побічних ефектів. Під побічними ефектами розуміють:
- Змінювання глобальних (статичні в термінах C #) зміннихабо читати змінювані дані.
- Виклик інших функції які можуть створити побічний ефектабо повернути глобальні змінні дані.
- Займатися будь-яким введенням / виводом
- Посилати або приймати будь-які повідомлення.
Три останні в загальному це зміна стану або читаннязмінюваного стану за допомогою виклику. Загалом, функція не має право робити нічого,що могло б змінити стан, і покладатися на змінні (ззовні) дані. Все, що робить функція- це обчислення і видача результату. У такого підходу є одна особливість: функціязавжди повертає один і той же результат для одних і тих же аргументів. Це надаєтакі переваги:
- Легкість налагодження, адже функція залежить лише відпараметрів. Весь стан при функціональних обчисленнях розташовується в стеці, такщо його легко аналізувати, і навіть можна роботи покрокове скасування і повтор дій.
- Легкість розпаралелювання. Два виклики однієї і тієїж функції абсолютно незалежні і можуть виконуватися паралельно. Крім того, потенційновиконання функції може бути автоматично распаралелено компілятором.
- Висока повторна використовуваних функцій. Тобто функціюлегше використовувати в іншому місці програми (або в іншій програмі).
Фактично, відсутність побічних ефектів залежитьне тільки від функції, а й від виразів що містяться в ній, тобто в них також потрібноне допускати побічних ефектів. В C# ФП реалізується завдяки LINQ або, як ще можнаназвати, мова інтегрованих запитів. Ще одним з прийомів ФП (у порівнянні з ІП) єприйом передачі невеликого, так би мовити, уточнюючого, виразу в якусь універсальнуфункцію. C# (і більшість популярних.net-мов) не має конструкцій мови, що дозволяютьвідокремити чистий функціональний код від імперативного або змішаного.
Навіть старі імперативні мови,наприклад, C і Паскаль, підтримують базову ідею ФП — можливість маніпуляції функціями.Однак у більшості сучасних імперативних мовах реалізована ця можливість також погано.Зазвичай все обмежується можливістю передати вказівник на тіло функції. Скажімо,в С і C++ ім'я глобальної функції інтерпретується як вказівник на неї.
Функціональні мови (ФМ) розвивають цю ідею, зводячиїї у принцип — функція є в програмі таким же повноцінним об'єктом, як і примірникбудь-якого іншого типу (наприклад, екземпляр рядка). Її можна використовувати якзвичайний об’єкт. Наприклад, в С ми можемо передати вказівник на функцію іншої функції,але скласти (під час виконання) з двох функцій третю ми не в силах. Неможливо вС і оголосити функцію по місцю. У ФМ ж все це можливо. Маніпулювати функціями вФМ дуже просто і зручно. Для цього необхідний функціональний тип. Зазвичай він будеприймати вигляд string Function (int x, string y);
проте якщо замінити перечислення на "*",а для опису поверненого значення функції використати "->",тоді вищерозглянуту ф-ію можна описати: int * string — > string або int — > string — > string, отже функціяяка отримує int і повертає функцію, яка отримує string та повертає string. Даний вираз називається «лямбда виразом», та існує ціла теоріящо обґрунтовує це.
Другою особливістю ФП у порівнянні з ІП є роботазі списками. У ФП список зазвичай видається за допомогою структури даних, як однонаправленийзв’язний список (далі просто список). Особливістю цієї структури даних є те, щовона дозволяє створювати незмінні списки. При цьому список має ряд обмежень:
- Він допускає додавання елементів тільки в початок списку.
- Видалення елементів неможливо (але, як і будь-який іншийоб'єкт у.net, елементи звільняються автоматично, якщо на них немає інших посилань).
- Для зберігання кожного елемента створюється окремийоб'єкт.
- Доступ за індексом елемента можливий тільки перебором.
Дані обмеження роблять списки неефективними, якщоїх використовують в імперативній манері, але зручними і ефективними при програмуваннів функціональному стилі. На жаль, в.net немає реалізації однонаправленого пов'язаногосписку (клас LinkedList є реалізацією двонаправленого пов'язаного списку).Застосування списків у ФП виправдане ще й тим, що в основному списки реалізуютьсяв них у вигляді алгебраїчних типів даних. Це дозволяє здійснювати розбір списківз застосуванням зіставлення зі зразком. На жаль, поки немає ні одної імперативноїмови програмування, що володіє подібною можливістю, так що це перевага поки не єдоступною для тих, хто з тих чи інших причин не хоче скористатися функціональноюмовою програмування для реалізації своїх завдань.
Імперативний код (ІК) — обробка послідовностей(списків) як послідовність перетворень, як це прийнято в ФП, тобто ІК сукупністьциклів, та вся обробка послідовності це вмісти цих циклів. У ФП обробка списківрозбивається на кілька простих перетворень, які можна виконати послідовно. Так якна кожній стадії обробки виходить (фактично) нова послідовність, налагодження такогокоду стає вельми простим завданням у порівнянні з ІК. Крім того, читати такий кодзначно простіше.
Найчастіше у ФП використовуються наступні функціїроботи зі списками: Fold — згортка (тобто обчислення за списком деякого значення),Map — відображення одного списку в інший з використанням функції перетворення елементіві Filter — фільтрація списку. Тобто всі ці функції є аналогами циклів перебору кожногоелементу списку з виконанням певної дії. У функціональному коді ми висловлюємо тількивимоги, а отже він не може бути різним і робити те саме на відміну від ІК. Це робитьфункціональну запис більше простий у читанні і кодуванні.
В C # 3. 5 для вираження (і обробки) послідовностейвикористовується тип IEnumerable . Функції обробки послідовностей у виглядіметодів-розширень поміщені в бібліотеку System. Core. dll, яка поставляється разомз.net Framework 3. 5. Всі ці методи знаходяться в класі Enumerable з простору іменSystem. Linq. 1.3 Microsoft HPC 2008
Windows HPC Server 2008 — це нова версія платформивисокопродуктивних обчислювальних систем (HPC) корпорації Microsoft. Побудованийна базі 64-розрядної версії Windows Server 2008, продукт Windows HPC Server 2008(HPCS) може ефективно масштабуватися на тисячі процесорних ядер, надаючи потужніінструменти для створення високопродуктивної середовища HPC. HPCS легко інтегруєтьсяз іншими продуктами Microsoft такими як Microsoft Office SharePoint та Windows Workflow Foundation, що збільшує продуктивністьроботи користувачів та адміністраторів. Завдяки інтеграції з Windows CommunicationFoundation (WCF), Windows HPC Server2008 дозволяє розробникам додатків для архітектури Service-Oriented Architecture(SOA) використовувати всю міць паралельних обчислень, що надається рішеннями класуHPC. Windows HPC Server 2008 підтримує п'ять різних конфігурацій, що вимагаютьвід одного до трьох мережевих адаптерів на кожному вузлі кластеру та від одногодо трьох мережевих адаптерів на головному вузлі.
/>
Рис. 1.2. Топології кластерної мережі.
- Мережа загального користування (або мережа підприємства):необхідні для з'єднання з існуючою мережею
- Приватна мережа: необхідна для керування вузлами кластерата забезпечити мережевий трафік між вузлами
- Мережа MPI (мережа програм) — високошвидкісна мережадля забезпечення трафіку MPI
Всі топології крім 5 підтримують автоматичне розгортаннякластерної системи. Для топологій 1 і 3 вузли можна підключити до мережі загальногокористування з допомогою головного вузла або додаткового сервера.
Робота — виконання певної програми на кластері,що може складатися як з однієї задачі так і з багатьох. Задачі можуть виконуватисяпослідовно одна за одною, або паралельно — одночасно на декількох процесорах.
Основний принцип виконання роботи в Windows HPCServer 2008 спирається на три важливих поняття:
Представлення роботи
Планування роботи
Виконання завдань
Ці три поняття формують основну структуру циклуроботи в області високопродуктивних обчислень життя і є основою, на якій Microsoftінженерних Windows HPC Server. Кожного разу, коли користувач готує виконання завданняв кластері обчислення, робота проходить через три етапи. На рис. 1. 3 показані компонентикластера і як вони співвідносяться один з одним.
/>
Рис. 1.3. Взаємозв’язок компонентів кластера.
Головний вузол (проте їх може бути два якщо використовуємовідмовостійкість) — центральний вузол в кластері з допомогою якого можна адмініструвативсі інші вузли. Головний вузол розгортає обчислювальні вузли, запускає планувальникзавдань, стежить за роботою та станом кожного обчислювального вузла, проходить діагностикувузлів, а також надає звіти про роботу вузлів і видів діяльності. WCF Broker використовуютьсядля інтерактивних додатків SOA, створення інтерактивних сесій, які представляютьроботи планувальника роботи, балансування навантаження встановлених вузлів і, нарешті,повертає результати клієнту сесії. Обчислювальні вузли виконувати робочі завдання.
Коли користувач відправляє завдання на кластер,планувальник завдань перевіряє роботу властивостей і зберігає роботу в бази данихMicrosoft SQL Server. Якщо шаблон для роботи заданий, цей шаблон приймається абовикористовується шаблон за замовчуванням, і робота входить в чергу. При наявностіресурсів робота спрямовується до обчислювальних вузлів. Оскільки кластер знаходитьсяв домені, робота виконується з використаннямправ доступу користувача. У результаті зникає складність використання та синхронізаціїрізних облікових даних, і користувач не повинен піклуватися про методи обміну данимита права доступу між вузлами. Windows HPC Server 2008 забезпечує прозоре виконання,доступ до даних, а також вбудовані засоби безпеки.
На рис. 1.4 показано базову архітектуру програмищо використовує SOA модель програмування.