Курсовая работа: Використання функціонального підходу при програмуванні розподілених задач для кластеру на прикладі технології 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.

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

З переходом на архітектуру 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. Побудова і задіяння розподілених обчислювальних та інформаційних систем (кластерів робочих станцій, багатомашинних комплексів та ін.)

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

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.4 показано базову архітектуру програми що використовує SOA модель програмування.

Рис. 1. 4. Базова архітектура SOA програми.

Життєвий цикл роботи на кластері Windows HPC можна виділити три основні етапи:

1. Створення сесії клієнтом.

2. Планувальник завдань виділяє вузли і запускає сервіс, який завантажує служби динамічної бібліотеки (DLL-файли). Планувальник завдань виділяє вузол Брокер, щоб почати роботу WCF Брокера. Запускаються задачі на вузлах та на WCF брокері встановлюються endpoints (умови завершення задач).

3. Клієнт отримує повідомлення про стан виконання задач на кластері та WCF брокер слідкує за рівномірним навантаженням на вузли кластера.

Адміністратор може використовувати Windows HPC Server 2008 Administrator Console для моніторингу кластера та планувальник для слідкування за прогресом і виділеними ресурсами для кожної роботи.

Dryad - високопродуктивний двигун загального призначення для розподілених обчислень, для запуску розподілених програм на різних кластерних технологіях, у тому числі Windows HPC Server 2008. Dryad почали розробляти в Microsoft починаючи з 2006 року. Dryad спрощує завдання реалізації розподілених програм:

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

-  Dryad підтримує моделі програмування, яка призначені для програмування під кластер.

-  Dryad може оперувати великомасштабними об’ємами даних при паралельних обчисленнях.

dryadlinq програмування функціональний підхід

Для використання технології Dryad на кластерах Microsoft HPC створено розширення LINQ, що отримало назву DryadLinq. DryadLINQ - розширена версія мови інтегрованих запистів LINQ. Велика частина коду в типовому застосуванні DryadLINQ подібно до того, який використовується LinqToObject. DryadLinq використовують DryadLinq API; всі взаємодії програми з Dryad реалізуються через провайдер DryadLinq. Архітектуру DryadLinq можна представити у вигляді схеми зображеної на рис. 1. 5.

Рис. 1.5. Архітектура DryadLinq.

Application Layer (рівень програми). Програми на DryadLinq компілюються в проміжний код і використовують DryadLINQ API для частин програми що базуються на Dryad. Програми в основному пишуться на C#, проте можна використовувати інші середовища, що підтримують Linq, наприклад F#.

DryadLINQ API and provider. DryadLinq надає розширену версію LINQ API яку використовують програми для реалізації запитів. Провайдер DryadLinq конвертує запити в роботу Dryad і виконує роботу на кластері.

Dryad execution engine (виконавчий двигун Dryad). Виконавчий двигун Dryad керує виконанням кожної роботи Dryad на кластері.

Server cluster (кластер) На кластері роботи виконуються на певних вузлах. За виконанням робіт слідкує JobManager на головному вузлі кластера.

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

Рис. 1.6 Схема роботи простої розподіленої програми.

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

Вхідні дані розбиваються на виконавчі частини, і кожна частина копіюється в один з обчислювальних вузлів.

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

Всі обчислювальні вузли одночасно обробляють дані з своїх виконавчих частин.

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

Дана діаграма на рисунку в загальному демонструє роботу DryadLinq, проте якщо розглянути це більш детально, то DryadLinq використовує механізм схожий на "UNIX piping mechanism" для зв’язку між різними процесами Dryad. Виконавчий план роботи Dryad являє собою направлений ациклічний граф, вершинами якого є незалежні процеси що працюють з даними лише зі свого рівняю. Для нескладної задачі цей граф буде мати наступний вигляд:

Рис. 1.7. Виконавчий план роботи Dryad.

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

Розподілення вхідних даних (Input data partitions). Робота Dryad починається з колекцією вхідних даних, такі як log файл наприклад. Вхідні дані розбиваються на частини і копіюються на вузли кластера. (Дана версія DryadLinq не розбиває дані і не копіює їх на вузли, це необхідно робити окремо)

Рівень (Stage). Робота Dryad складається з одного або більше рівнів. Кожен рівень відповідає елементу основного плану виконання.

Вершина (Vertex). Кожен рівень складається з одного або більше однакових вершин. Кожна вершина є незалежним екземпляром коду обробки даних певного рівня, і використовує дані лише зі свого рівня. Вершини мають певні особливості:

-  Різні етапи можуть мати різне число вершин.

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

-  Певний тип вершини може бути використаний на декількох рівнях.

-  Для DryadLINQ, кожна вершина використовують методи Microsoft.net Framework.

-  Кожна вершина зазвичай виконується на окремому обчислювальному вузлі.

Канал (Channel). Дані на кожному наступному рівні беруться з попереднього за допомогою каналів. Для цього DryadLINQ використовує два механізма: файли та спільної пам'яті. Спільну пам'ять каналів іноді називають спільною пам'ятю FIFO каналів (перший увійшов, перший вийшов). Деякі вказівки:

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

-  вершина може мати канал для більш ніж однієї вершини в наступному рівні.

-  Різні види каналів можуть бути використані у різних частинах графу.

-  Канали підключаються до вершин, так що граф є ациклічним.

-  Канали працюють за принципом точка-точка. Вони пов'язують вихід з однієї вершини з входом іншої вершини.

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

На рис. 2. 1 представлена принципова схема, як Dryad виконує роботу.

Рис. 2.1. Схема виконання роботи Dryad.

Користувач запускає програму що використовує DryadLINQ з клієнтської робочої станції. Після створення виконавчого графу, менеджер робіт Dryad створює роботу з запитів DryadLINQ та запускає роботу в кластері Windows HPC. Менеджер робіт Dryad - задача Windows HPC на головному вузлі, яка керує виконанням відповідної роботи на кластері. Зокрема, робота менеджера породжує вершини, що є завданнями, які належать до однієї роботи на Windows HPC.

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

Кластерна програма на основі Dryad залежать від:

клієнтської робочої станції.

Обчислювальні вузли.

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

Все має бути правильно налаштовано для того щоб програма на Dryad нормально працювала.

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

Стандартні папки вводу виводу

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

-  DryadData - для розташування вхідних даних

-  XC - для збереження проміжних даних що створюються роботою Dryad

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

Кожен проект DryadLINQ повинен включати в себе файл конфігурації DryadLinqConfig. xml. Файли конфігурації поділяються на:

-  Глобальний DryadLinqConfig. xml - містить налаштування що не змінюються в залежності від проекту (наприклад ім’я головного вузла, стандартні папки вводу виводу). Він міститься в C: \Program Files\Microsoft Research DryadLINQ

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

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

<DryadLinqConfig>

<ClusterName>hnode</ClusterName>

<Cluster name="hnode"

schedulertype="Hpc"

partitionuncdir=" XC\output "

dryadoutputdir="file: // \\hnode\Userdata\tmaliarchuk\output" />

</DryadLinqConfig>

Розберемо по частинам:

-  hnode - ім’я головного вузла кластера

-  XC\output - папка для збереження проміжних даних що створюються роботою Dryad

-  file: // \\hnode\Userdata\tmaliarchuk\output - папка виводу результату

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

<DryadLinqConfig>

<DryadLinqRoot>

C: \Program Files\Microsoft Research DryadLINQ

</DryadLinqRoot>

</DryadLinqConfig>

За замовчуванням це C: \Program Files\Microsoft Research DryadLINQ.

Дані в роботі Dryad необхідно представити у вигляді колекції. Для звичайного запитів LinqToObject це тип IEnumerable<T>. Це так би мовити колекція даних типу Т над якою можна виконувати такі операції як сортування, видобуток та інші функції які доступні в бібліотеці System. Linq. Проте після перелічених операції робота Dryad повертає не об’єкт типу IEnumerable<T>, а IQueryable<T>. IQueryable<T> наслідує IEnumerable<T>, проте ці два типи колекцій працюють по різному:

IEnumerable<T> - представляється як ітератор по колекції даних, які знаходяться на комп’ютері. Під час виконання програми об’єкт колекції компілюються локальним.net JIT компілятором, і ітератори використовуються для покращення виконання програми локально.

IQueryable<T> - представляється як запит по колекції даних. Під час виконання програми об’єкт колекції передається провайдеру DryadLINQ що транслює запити в роботу Dryad і повертає вже оброблені дані до програми. Це використовується для розподілених програм на кластері.

Під час виконання роботи Dryad на кластері вхідні дані представляються у вигляді PartitionedTable<T>. PartitionedTable<T> наслідує IQueryable<T>, а отже наслідує і всі методи IQueryable<T>. PartitionedTable<T> представляє дані ніби вони знаходяться на одному вузлі, проте в реальності вони розділені на частини та знаходяться не на одному вузлі.

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

-  файл метаданих, який являться текстовим файлом що містить метадані які описують розподілені дані

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

Файл метеданих може приймати наступний вигляд (у випадку виконання роботи на 4 вузлах):

Файл метаданих має формат. pt і містить три розділи:

-  папка та ім’я файлу - перша строчка описує стандартну папку з відкритим доступом і стандартне ім’я для часткових даних. Кожен вузол в кластері має папку DryadData з відповідними правами доступу та кожна частина розподілених даних повинна міститися в цій папці на відповідних вузлах

-  кількість частин - друга строчка описує кількість частин розподілених даних. В даному випадку 4

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

У файлі метеданих не повинно бути жодних пробілів. Номер частин розподілених починається з 00000000. Розмір частини вказувати не обов’язково, тобто якщо при кожному новому виконанні роботи Dryad її розмір змінюється можна вказати нульовий розмір. Також певна чатина даних може не знаходитися в стандартній папці. У цьому випадку в рядку опису цієї частини після переліку вузлів де знаходиться ця частина необхідно поставити ": " та потім вказати ім’я папки та ім’я частини. Наприклад у випадку використання тільки однієї частини розподілених даних файл метаданих може бути наступним

Тут ми не вказуємо папку та ім’я за замовчуванням.

Також проект що використовує DryadLINQ необ хідно підключити дві бібліотеки LinqToDryad. dll та System. Threading. dll. LinqToDryad. dll містить клас бібліотек DryadLINQ та провайдер DryadLINQ. Розташування цієї бібліотеки за замовчуванням C: \Program Files\Microsoft Research DryadLINQ\lib де міститься версії цієї бібліотеки для відлагодження та для кінцевої версії проекту. System. Threading. dll стандартна бібліотека платформи.net 3. 5 необхідна для використання стандартних можливостей цієї платформи (наприклад WCF). Розташовується вона за замовчуванням в С: \Program Files\Microsoft Research DryadLINQ\Lib\Microsoft\Framework\v3. 5\

Для реалізації консольної програми обчислення інтегралу 1/х методом Монте-Карло на кластері Windows HPC 2008 з використанням DryadLINQ програма перед початком роботи генерує випадкові точки в певному діапазоні записує їх у декілька текстових файлів кожен з яких потім копіюється на відповідний вузол.

Розглянемо виконання роботи Dryad на прикладі запиту DryadLINQ

PartitionedTable<LineRecord> table = PartitionedTable. Get<LineRecord> (uri);

IQueryable<string> table1 = table

. Select (s => s. line)

. Where (s => (1/ (fun (s. Split (' ') [0]))) > fun (s. Split (' ') [1]));

double result = (1. 000000 * table1. Count () * (x2-x1) * (y2-y1)) /lenght;

Спочатку зчитується файл метаданих де вказується кількість та місце знаходження частин розподілених даних які попередньо були скопійовані на відповідні вузли. Далі представляється IQueryable<string> у вигляді PartitionedTable<string>. В запиті DryadLINQ реалізується вибірка тих текстових рядків в яких функція 1/x від першого числа більша за друге число. Тут використовується функція fun яка переводить string у double та функція Split з простору System. Text що розділяє стрічку на частини між якими був знак пробілу. Це реалізується двома методами Select та Where. Перший серед всієї сукупності вхідних діних виділяє рядок, а другий аналізує чи цей рядок задовольняє нашим умовам. Після цього підраховується кількість обраних рядків за допомогою методу Count.

Під час виконання роботи Dryad на консолі провайдер Dryad виводить наступне:

Рис. 2.2

Як видно з рисунка провайдер Dryad виводить:

-  шлях стандартної папки виводу

-  місце знаходження файлу метаданих

-  елементи кожного рівня виконавчого графа Dryad

-  інформація про стан підключення до кластера та погодження роботи на ньому

-  інформується чи робота виконується (running) чи вона поки що в черзі (queued)

Після завершення виконання роботи Dryad на кластері провайдер Dryad повертає оброблені дані до програми.

Дана програма обчислення інтегралу методом Монте-Карло була запущена на різній кількості вузлів: від одного до шести.

Рис. 2.3. Залежність часу виконання роботи Dryad від кількості задіяних вузлів.

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

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

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

1.  Windows® HPC Server 2008 Resource Kit: // http://resourcekit. windowshpc.net/home.php

2.  DryadLINQ - Microsoft Research Project Page // http://research. microsoft.com/en-us/projects/dryadlinq/

3.  Microsoft® Connect – Dryad // http://connect. microsoft.com/Dryad

4.  Dryad - Microsoft Research Project Page // http://research. microsoft.com/en-us/projects/dryad/

5.  Dryad and DryadLINQ for Data Intensive Research // http://research. microsoft.com/en-us/collaboration/tools/dryad. aspx

6.  Intel - HPC: архитектура суперкомпьютеров и разновидности // http://ru. intel.com/business/community/? automodule=blog&blogid=6276&showentry=888

7.  Russian Software Developer Network // http://www.rsdn.ru/

8.  Language-Integrated Query (LINQ) // http://msdn. microsoft.com/en-us/library/bb397926. aspx

9.  LINQ:.net Language-Integrated Query // http://msdn. microsoft.com/en-us/library/bb308959. aspx

10.  Dryad and DryadLINQ team blogs // http://blogs. msdn.com/b/dryad/

11.  Meijer E., Barga R. Introduction to Dryad and DryadLINQ // http://channel9. msdn.com/posts/Charles/Expert-to-Expert-Erik-Roger-Barga-Introduction-to-Dryad-and-DryadLINQ/

12.  Vert J. Data-Intensive Computing on Windows HPC Server with the DryadLINQ Framework // http://microsoftpdc.com/Sessions/SVR17

13.  Podwysocki M. Dryad/DryadLINQ and Project Trident Released

14.  // http://weblogs. asp.net/podwysocki/archive/2009/07/16/dryad-dryadlinq-and-project-trident-released. aspx

15.  Campbell D. Dryad and DryadLINQ: Academic Accelerators for Parallel Data Analysis // http://blogs. msdn.com/b/msr_er/archive/2010/02. aspx

16.  Colaci A. Dryad and DryadLINQ for Data Intensive Research // http://blogs. msdn.com/b/lchong/archive/2009/09/23/dryad-and-dryadlinq-for-data-intensive-research. aspx

17.  Chong L. Scaling out PLINQ: DryadLINQ at PDC09 and Supercomputing09 // http://blogs. msdn.com/b/pfxteam/archive/2009/11/11/9921066. aspx

Додаток А

Текст глобального файлу конфігурації

<DryadLinqConfig>

<ClusterName>hnode</ClusterName>

<Cluster name="hnode"

schedulertype="Hpc"

partitionuncdir=" XC\output "

dryadoutputdir="file: // \\hnode\Userdata\tmaliarchuk\output" />

</DryadLinqConfig>

Додаток Б

Текст локального файлу конфігурації

DryadLinqConfig>

<DryadLinqRoot>

C: \Program Files\Microsoft Research DryadLINQ

</DryadLinqRoot>

</DryadLinqConfig>

Додаток B

Текст файлу метаданих (у випадку чотирьох обчислювальних вузлів)

\DryadData\tmaliarchuk\mc

4

0,0,NODE05

1,0,NODE06

2,0,NODE10

3,0,NODE14

Додаток Г

Текст програми обрахунку інтегралу методом Монте-Карло

using System;

using System. IO;

using System. Collections. Generic;

using System. Text;

using System. Linq;

using LinqToDryad;

using System. Diagnostics;

public class MatchString2

{

public static double fun (string s)

{

int i, j = 1;

double ds = 0;

bool b = false;

for (i = 0; (i! = (s. Length)); i++)

{

if (s [i]! = ',')

if (! b) ds = ds*10 + ( (int) s [i] - 48);

else

{

j *= 10;

ds = ds + (1. 0000 * ( (int) s [i] - 48) / j);

}

else b = true;

}

return ds;

}

public static void create (int lenght, int x1, int x2, int y1, int y2, string source,string destination)

{

Console. WriteLine (source);

Random rnd = new Random ();

using (StreamWriter sw = new StreamWriter (source))

{

for (int i = 0; i < lenght / 2; i++)

{

sw. Write (Convert. ToString (x1 + (x2 - x1) * rnd. NextDouble ()));

sw. Write (' ');

sw. WriteLine (Convert. ToString (y1 + (y2 - y1) * rnd. NextDouble ()));

}

}

Console. WriteLine ("copying");

System. IO. File. Copy (source, destination, true);

}

static void Main (string [] args)

{

int lenght = 1000000;

int x1 = 1;

int x2 = 10;

int y1 = 0;

int y2 = 1;

create (lenght/4, x1, x2, y1, y2, @"D: \temp\mc. 00000000", "\\\\node05\\DryadData\\tmaliarchuk\\mc. 00000000");

create (lenght/4, x1, x2, y1, y2, @"D: \temp\mc. 00000001", "\\\\node06\\DryadData\\tmaliarchuk\\mc. 00000001");

create (lenght/4, x1, x2, y1, y2, @"D: \temp\mc. 00000002", "\\\\node10\\DryadData\\tmaliarchuk\\mc. 00000002");

create (lenght/4, x1, x2, y1, y2, @"D: \temp\mc. 00000003", "\\\\node14\\DryadData\\tmaliarchuk\\mc. 00000003");

string uri = DataPath. FileUriPrefix + Path.combine ("\\\\hnode\\UserData\\tmaliarchuk", "montecarlo. pt");

PartitionedTable<LineRecord> table = PartitionedTable. Get<LineRecord> (uri);

Stopwatch t = new Stopwatch ();

t. Start ();

IQueryable<string> table1 = table. Select (s => s. line)

. Where (s => (1/ (fun (s. Split (' ') [0]))) > fun (s. Split (' ') [1]));

double result = (1. 000000 * table1. Count () * (x2-x1) * (y2-y1)) /lenght;

t. Stop ();

Console. WriteLine (t. Elapsed);

Console. WriteLine (result);

Console. ReadKey ();

}

}