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

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

Київський національний університет імені Тараса Шевченка

Радіофізичний факультет

Кафедра комп’ютерної інженерії

ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОГО ПІДХОДУ ПРИ ПРОГРАМУВАННІ РОЗПОДІЛЕНИХ ЗАДАЧ ДЛЯ КЛАСТЕРУ НА ПРИКЛАДІ ТЕХНОЛОГІЇ 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 Parallel Processing) - масову паралельну обробку, де використовувалося велике число серійно випущених процесорів, вдалося помітно знизити витрати на створення суперкомп'ютерів, оскільки не використовувалися вже розроблені технології. Основна вартість і складність тепер полягала у використанні спеціальних комунікаційних рішень для зв'язку цих процесорів.

"Беовульф", створений в 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 <Of> є реалізацією двонаправленого пов'язаного списку). Застосування списків у ФП виправдане ще й тим, що в основному списки реалізуються в них у вигляді алгебраїчних типів даних. Це дозволяє здійснювати розбір списків з застосуванням зіставлення зі зразком. На жаль, поки немає ні одної імперативної мови програмування, що володіє подібною можливістю, так що це перевага поки не є доступною для тих, хто з тих чи інших причин не хоче скористатися функціональною мовою програмування для реалізації своїх завдань.

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

Найчастіше у ФП використовуються наступні функції роботи зі списками: Fold - згортка (тобто обчислення за списком деякого значення), Map - відображення одного списку в інший з використанням функції перетворення елементів і Filter - фільтрація списку. Тобто всі ці функції є аналогами циклів перебору кожного елементу списку з виконанням певної дії. У функціональному коді ми висловлюємо тільки вимоги, а отже він не може бути різним і робити те саме на відміну від ІК. Це робить функціональну запис більше простий у читанні і кодуванні.

В C # 3. 5 для вираження (і обробки) послідовностей використовується тип IEnumerable <T>. Функції обробки послідовностей у вигляді методів-розширень поміщені в бібліотеку 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 Communication Foundation (WCF), Windows HPC Server 2008 дозволяє розробникам додатків для архітектури Service-Oriented Architecture (SOA) використовувати всю міць паралельних обчислень, що надається рішеннями класу HPC. Windows HPC Server 2008 підтримує п'ять різних конфігурацій, що вимагають від одного до трьох мережевих адаптерів на кожному вузлі кластеру та від одного до трьох мережевих адаптерів на головному вузлі.

Рис. 1.2. Топології кластерної мережі.

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

-  Приватна мережа: необхідна для керування вузлами кластера та забезпечити мережевий трафік між вузлами

-  Мережа MPI (мережа програм) - високошвидкісна мережа для забезпечення трафіку MPI

Всі топології крім 5 підтримують автоматичне розгортання кластерної системи. Для топологій 1 і 3 вузли можна підключити до мережі загального користування з допомогою головного вузла або додаткового сервера.

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

Основний принцип виконання роботи в Windows HPC Server 2008 спирається на три важливих поняття:

Представлення роботи

Планування роботи

Виконання завдань

Ці три поняття формують основну структуру циклу роботи в області високопродуктивних обчислень життя і є основою, на якій Microsoft інженерних Windows HPC Server. Кожного разу, коли користувач готує виконання завдання в кластері обчислення, робота проходить через три етапи. На рис. 1. 3 показані компоненти кластера і як вони співвідносяться один з одним.

Рис. 1.3. Взаємозв’язок компонентів кластера.

Головний вузол (проте їх може бути два якщо використовуємо відмовостійкість) - центральний вузол в кластері з допомогою якого можна адмініструвати всі інші вузли. Головний вузол розгортає обчислювальні вузли, запускає планувальник завдань, стежить за роботою та станом кожного обчислювального вузла, проходить діагностику вузлів, а також надає звіти про роботу вузлів і видів діяльності. WCF Broker використовуються для інтерактивних додатків SOA, створення інтерактивних сесій, які представляють роботи планувальника роботи, балансування навантаження встановлених вузлів і, нарешті, повертає результати клієнту сесії. Обчислювальні вузли виконувати робочі завдання.

Коли користувач відправляє завдання на кластер, планувальник завдань перевіряє роботу властивостей і зберігає роботу в бази даних Microsoft SQL Server. Якщо шаблон для роботи заданий, цей шаблон приймається або використовується шаблон за замовчуванням, і робота входить в чергу. При наявності ресурсів робота спрямовується до обчислювальних вузлів. Оскільки кластер знаходиться в домені, робота виконується з використанням прав доступу користувача. У результаті зникає складність використання та синхронізації різних облікових даних, і користувач не повинен піклуватися про методи обміну даними та права доступу між вузлами. Windows HPC Server 2008 забезпечує прозоре виконання, доступ до даних, а також вбудовані засоби безпеки.

Страницы: 1, 2