ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

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

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

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

1. Актуальність теми

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

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

2. Мета і задачі дослідження та заплановані результати

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

Основними завданнями дослідження ставляться:  

  1. Огляд різних існуючих методів планування завдань.  
  2. Аналіз та порівняльна оцінка найбільш перспективних алгоритмів.  
  3. Пошук і виявлення тих характеристик планувальників, що можуть бути покращені для отримання більш оптимальних результатів.  
  4. Симуляція модифікацій, побудова нових моделей. Проведення повторного порівняння. Виявлення позитивних (і негативних) змін в результатах планування.  
  5. Розробка і поліпшення найбільш ефективного з отриманих методів планування.

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

Предмет дослідження: поліпшення алгоритму планування для багатопроцесорних обчислювальних систем.

У рамках магістерської роботи планується отримання актуальних наукових результатів за наступними напрямками:  

1. Створення більш ефективного методу планування процесів.  

2. Визначення перспективних напрямів розвитку планувальників.  

3. Модифікація відомих алгоритмів планування завдань..

3. Огляд різних видів паралельних обчислювальних систем

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


3.1 Мультипроцесорна система

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

3.2 Мультікомпьютерная система

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

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

Відмінності в способах зберігання і роботи з даними в системах

Зображення 1. Відмінності в способах зберігання і роботи з даними в системах (5 кадрів, 5 циклів повторення, 61,8 Кбайт):

а) мультипроцесорна система з 12 процесорів, що використовують спільну пам'ять;

б) мультікомпьютерная система з 12 процесорів, кожний з яких має власну пам'ять

3.3 Розподілені системи

Розподіленою обчислювальною системою (РВС) можна вважати набір з'єднаних каналами зв'язку незалежних комп'ютерів, які для стороннього користувача є єдиним цілим [2]. РВС можна уявити, як кілька окремих персональних комп'ютерів або серверів, об'єднаних в єдину систему за допомогою мережі Інтернет. Природно, повідомлення даними через Інтернет, як і самі способи організації подібного повідомлення (обмін пакетами, маршрутизація та ін аспекти) між машинами, які у різних частинах земної кулі (фізично), не можна назвати стабільним і виразно швидким, а тому часові показники подібних систем досить низькі. Однак РВС відрізняються високою надійністю, з причини того, що вихід з ладу одного елемента або вузла мережі не грає особливої ​​ролі в її працездатності. До того ж, вони мають практично необмежений потенціал в плані нарощування продуктивності - чим більше комп'ютерів буде об'єднано цією структурою, тим вище буде їх загальна обчислювальна потужність.

Загальне подання розподіленої мережі (частина 1)

Загальне подання розподіленої мережі (частина 2)

Зображення 2. Загальне подання розподіленої мережі (системи)

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

4.1 Різні характеристики планувальників завдань

Спосіб вирішення питання про планування завдань істотно залежить від того, незалежні або залежні (пов'язані один з одним) процеси в списку, а тому їх можна в цілому розбити на дві великі категорії:

- Планування незалежних процесів;

- Планування залежних процесів.

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

Базова класифікація алгоритмів планування

Зображення 3. Базова класифікація алгоритмів планування

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

Процес, який вичерпав свій квант, переводиться в стан ГОТОВНІСТЬ і очікує, коли йому буде надано новий квант процесорного часу, а на виконання відповідно до певних правил вибирається новий процес з черги готових. Таким чином, жоден процес не займає процесор надовго, тому квантування широко використовується в системах поділу часу.

Самі кванти можуть відрізнятися для різних процесів або ж взагалі змінюватися з плином часу. Процеси, які не повністю використовували виділений їм для роботи час (наприклад, через відхід на виконання операцій введення-виведення), часто отримують в системі додаткові привілеї при наступному обслуговуванні. По-різному може бути організована і сама черга готових процесів: циклічно, за правилом "перший прийшов - перший обслужився" (FIFO), "останній прийшов - перший обслужився" (LIFO) або за допомогою іншого, більш складного методу.

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

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

Preemptive multitasking (витісняюча багатозадачність) - це такий спосіб, при якому рішення про переключення процесора з виконання одного процесу на виконання іншого процесу приймається планувальником, а не найактивнішим завданням.

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

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

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

4.2 Планувальники мультипроцесорних систем 

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

• який з готових до виконання процесів потрібно запустити в даний конкретний момент часу;

• на якому з процесорів потрібно запустити обраний процес.

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

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

Розглянута схема планування дозволяє:   

1. Забезпечити процесорам режим поділу часу;   

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

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

Дуже поширений алгоритм для зв'язкових процесів полягає в статичному розбитті всього безлічі доступних процесорів на підмножини і призначення кожного з них окремої групи зв'язкових процесів. Наприклад, є чотири групи пов'язаних процесів Q1-Q3, Q4-Q7, Q8-Q13 і Q14-Q20. Тоді, відповідно до цього алгоритмом, процеси першої групи повинні бути призначені першого підмножині процесорів (P1-P3), процеси другої групи - другому підмножині процесорів (P4-P7), і т.д. (Див. рис. 1).

Планування залежних процесів.

Зображення 4. Планування залежних процесів.

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

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

4.3 Планувальники мультікомп'ютерних систем

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

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

Детермінований графовий алгоритм [3]. Якщо відомі схеми обміну даними між процесами, то процеси призначаються ЦП таким чином, щоб мінімізувати мережевий трафік. Алгоритм: будується граф зв'язків між процесами, потім розбивається на підграфи так, щоб між ними було якнайменше зв'язків, отже, якомога менше етапів обміну даними.

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

Розподілений евристичний алгоритм, ініційований одержувачем. При завершенні процесу аналізується завантаженість даного процесора. Якщо він вільний, то шукає випадковим чином завантажений процесор і запитує процес з його черги на виконання [3].

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

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

4.4 Планувальники розподілених систем

Для розподілених систем часто використовують графові алгоритми, що більшою мірою обумовлено самою структурою таких РВС. З них можна виділити наступні великі групи алгоритмів:

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

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

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

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

5. Висновки

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

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

Подальші дослідження будуть спрямовані на:

  1.    Проведення аналізу та порівняльної оцінка найбільш перспективних алгоритмів.
  2.    Пошук і виявлення тих характеристик планувальників, що можуть бути покращені для отримання більш оптимальних результатів.
  3.    Симуляцію модифікацій, побудову нових моделей. Проведення повторного порівняння. Виявлення позитивних (і негативних) змін в результатах планування.
  4.    Розробку та поліпшення найбільш ефективних з отриманих методів планування.

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2013 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Перелік посилань

  1. Барський А.Б. Паралельні процеси в обчислювальних системах. Планування і організація / А.Б. Барський. - М.: Радіо і зв'язок, 1990. 256 с.
  2.     Таненбаум Е., ван Стеен М. Розподілені системи. Принципи та парадигми. - СПб.: Пітер, 2003. - 877 с.: Іл. - (Серія «Класика Computer Science») - ISBN 5-272-00053-6.
  3.    Таненбаум Е.: "Сучасні операційні системи", 3-е видання - СПб.: "Пітер", 2011. - 1115 с. 
  4.    Морев Н. В. Порівняння алгоритмів планування розподілу завдань для однорідних розподілених обчислювальних систем [Текст] / Н. В. Морев / / Інформаційні технології: Науково-технічний і науково-виробничий журнал. - 2010. - N 5. - С. 43-46
  5.     Афраймовіч Л.Г. Моделі і методи ефективного використання розподілених обчислювальних систем [Навчально-методичний посібник] - Нижній Новгород, 2012 - 17 с.
  6.    Принципи побудови паралельних обчислювальних систем. / Електронний ресурс. - Режим доступу: http://wiki.auditory.ru/Принципы_построения_параллельных_вычислительных_систем
  7.    Воронцов К. В. Лекції за алгоритмами кластеризації та багатовимірного шкалювання. / Електронний ресурс. - Режим доступу: http://www.ccas.ru/voron/download/Clustering.pdf