Русский   English
ДонНТУ   Портал магістрів

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

Зміст

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

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

2. Мета і задачі дослідження

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

Основні задачі дослідження:

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

3. Огляд досліджень та розробок за темою

Робота по дослідженню і розробці обчислювальних систем не припиняється: активно розробляються алгоритми поліпшення роботи обчислювальних систем, вирішуються проблеми балансування навантаження в мережі, планування, виявлення вузьких місць. У ДонНТУ за цим напрямком працюють:

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

Дана робота є продовженням розробок цих магістрантів. Новизна роботи полягає в тому, що попередні моделі обчислювальних систем були розраховані на роботу з одним класом завдань. Необхідно продовжити дослідження і побудувати дискретну Марковську модель кластера, розрахованого на роботу з декількома класами завдань. Ця робота проводиться спільно з магістром Іллею Володимировичем Бібіковим, Керівник: Фельдман Лев Петрович. Тема роботи: Оцінка продуктивності розподільних систем. Відмінність моделей полягає в тому, як обираються обмеження, які накладаються на модель. Модель, розглянута в цій роботі, матиме постійне число заявок, що обробляються в системі.

4 Загальні поняття

Обчислювальна система OC:

У вузькому сенсі під ОС розуміють сукупність технічних засобів, в яку входить не менше двох процесорів, пов'язаних загальною системою управління і використання загальносистемних ресурсів (пам'ять, периферійні пристрої, програмне забезпечення і тому подібне). У ширшому сенсі – це взаємозв'язана сукупність апаратних засобів обчислювальної техніки і програмного забезпечення, призначена для обробки інформації [1].

Кластер - група взаємно сполучених обчислювальних систем (вузлів),які працюють спільно і становлять єдиний обчислювальний ресурс, створюючи ілюзію наявності єдиної обчислювальної машини ОМ. Для зв'язку вузлів використовується одна із стандартних мережевих технологій (Fast/Gigabit Ethernet, Myrinet) на базі шинної архітектури або комутатора. Приклади кластерних обчислювальних систем : NT-кластер в NCSA, Beowulf-кластери.

В якості вузла кластера може виступати як однопроцесорна ОМ, так і ОС типу SMP (Симетрична мультипроцесорна система логічно представляється як єдина ОМ). Зазвичай, це не спеціалізовані пристрої, пристосовані під використання в обчислювальній системі, як в МРР(Системи с масовим паралелізмом), а обчислювальні машини і системи, що серійно випускаються. Ще одна особливість кластерної архітектури полягає в тому, що в єдину систему об'єднуються вузли різного типу, від персональних комп'ютерів до потужних ОС. Кластерні системи з однаковими вузлами називають гомогенними (однорідними) кластерами, а з різнотипними вузлами - гетерогенними (неоднорідними) кластерами [2]. Типовий однорідний кластер представлений на Рисунку 1.


Кластерна система

Рисунок 1 – Кластерна система

До складу кластеру входять:

4.1 Аналіз існуючих топологій багатоядерних комп'ютерів

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

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

MIMD-комп'ютери належать до комп'ютерів з розподіленою пам'яттю. А персональні комп'ютери і малі сервера, звичні простому користувачеві, належать до SIMD-систем із загальною пам'яттю [3].

4.2 Засоби розпаралелювання

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

Існує також немало інструментальних засобів, які спрощують проектування паралельних програм. Наприклад:

Досвід користувачів високошвидкісних кластерних систем показує, що найефективніше працюють програми, спеціально написані з урахуванням необхідності міжпроцесорної взаємодії. І навіть попри те, що програмувати на пакетах, які використовують shared memory interface або засоби автоматичного розпаралелювання, значно зручніше, найбільше поширені сьогодні бібліотеки MPI і PVM.

Комунікаційні бібліотеки стандарту MPI (MPICH2, Open MPI, Cray MPI та ін.) є основним засобом створення паралельних програм для розподілених обчислювальних систем (ОС). Основу цих бібліотек складають комунікаційні функції диференційованих (Point-to-point communications) і колективних операцій (Collective communications) обміну інформацією між гілками паралельних програм [5].

5. Методи аналізу кластерних систем. Модель однорідного кластеру

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

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

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

Розглянемо базову дискретну модель однорідного кластера із загальним використанням дискового простору (див. Рис. 2). Модель була побудована за допомогою методики [7]. У системі N однакових серверів, D дискових накопичувачів і керуючий сервер, КС. В мережі постійна кількість запитів M. Запити, що обслуговуються на сервері, поступають в обмежену чергу типу FIFO (first in – first out, Першим Прийшло – Першим Пішло).

Структурна схема Марковськой моделі однорідного кластера

Рисунок 2 – Структурна схема Марковськой моделі однорідного кластера
(анімація: 9 кадрів, 10 циклів повторення, 1 сек затримка, 79.1 кілобайт)

Введемо такі характеристики обслуговування програм пристрою:

5.1 Оцінка ефективності

Алгоритм, застосований в паралельній реалізації Марковських моделей [8], складається з двох частин: обчислень матриці перехідної імовірності і вектору стаціонарної імовірності.

Розрахунок стаціонарної імовірності реалізований з використанням ітераційного алгоритму, в якому як базовий використовується алгоритм множення матриці на вектор.

Для визначення вектору стаціонарної імовірності станів formula 1 необхідно вирішити систему лінійних алгебраїчних рівнянь (СЛАР), formula 2, що відповідає розглянутій моделі кластера.

Розрахунок перехідних ймовірностей. За стан системи приймемо розміщення М запитів по N вузлам formula 3, де mi  – кількість задач в i-ом вузлі. Необхідно визначити всі можливі стани. Безліч станів визначається :

Число станів системи для однієї і тієї ж кількості завдань formula 5 дорівнює числу розміщень j завдань по N вузлам і визначається по формулі formula 6 , загальна кількість станів розраховується так: formula 7

Вектор визначає кількість пристроїв в кожному вузлі ВС. Залежно від кількості завдань в системі розмірність отримуваних матриць може змінитися. Порядок виникаючих матриць - від декількох тисяч до мільйонів.

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

Стаціонарна імовірність дає можливість визначити середні величини тимчасових характеристик обслуговування і зайнятості приладів обчислювальної системи. Обчислення основних характеристик відбувається як [10]:

6 Заплановані результати

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

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

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

  1. Чекменев С. Е. Архитектура вычислительных систем. [Електронний ресурс]. – Режим доступа: http://stankin.ru/..
  2. Кластер // Словарь терминов в коллекции "Вычислительные системы" [Електронний ресурс]. – Режим доступа: http://www.nsc.ru/win/elbib/data/show_page.dhtml?77+858
  3. Чистяков А.В., Ислямова И.С. Метод и технологии параллельного программирования при решении прикладных задач / Инженерия программного обеспечения 2010 Том 3.
  4. Эффективные кластерные решения. [Електронний ресурс]. – Режим доступа: http://www.ixbt.com/cpu/clustering.shtml
  5. Курносов М.Г. MPIPerf: пакет оценки эффективности коммуникационных функций стандарта MPI // Труды международной научной конференции "Параллельные вычислительные технологии (ПаВТ-2012)". – Новосибирск, 2012. – С. 212-223.
  6. Клейнрок Л. Вычислительные системы с очередями. – М.: Мир, 1979.-600с.
  7. Фельдман Л.П., Малинская Э.Б. Аналитическое моделирование вычислительных систем с приоритетным обслуживанием программ. //Электронное моделирование. – К., 1985. – №6.– с. 78-82.
  8. Михайлова Т.В. Параллельный алгоритм построения дискретной модели Маркова // Искусственный интеллект. Интеллектуаьные и многопроцесорные системы. Материалы Международной научно-технической конференции, 25-30 сентября 2006г., Таганрог-Донецк-Минск, 2006.
  9. Мищук Ю.К., Фельдман Л.П. Моделирование параллельной реализации Марковских моделей в многопроцессорных вычислительных системах // Матеріали I всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 19-21 травня 2010р., Донецьк, ДонНТУ. – 2010. – с. 238-240Матеріали I всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 19-21 травня 2010р., Донецьк, ДонНТУ. – 2010. – с. 238-240 600с.
  10. Фельдман Л.П., Михайлова Т.В. Оценка эффективности кластерных систем с использованием моделей Маркова. //Известия ТРТУ. Тематический выпуск: Материалы Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности». – Таганрог: ТРТУ, 2002. – №2 (25). – С. 50-53.