ДонНТУ   Портал магістрів
Магістр ДонНТУ Первусяк Олексій Игорович
Первусяк Олексій Игорович
Факультет комп'ютерних наук та технологій
Кафедра комп'ютерної інженерії
Спеціальність Комп'ютерні системи та мережі
Науковий керівник: д.т.н., проф. Святний Володимир Андрійович
Консультант: ст. викл. Іванов Олександр Юрійович
Дослідження моделі динамічної системи на багатоядерній SMP-платформі

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

Зміст

Вступ

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

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

Обчислювальний напрямок застосування комп'ютерів завжди залишався основним двигуном прогресу в комп'ютерних технологіях. Не дивно тому, що в якості основної характеристики комп'ютерів використовується такий показник, як продуктивність — величина, що показує, яка кількість арифметичних операцій він може виконати за одиницю часу. Саме цей показник з найбільшою очевидністю демонструє масштаби прогресу, досягнутого в комп'ютерних технологіях. Так, наприклад, продуктивність одного з найперших комп'ютерів EDSAC становила всього близько 100 операцій в секунду, тоді як пікова продуктивність такого суперкомп'ютера Earth Simulator оцінюється в 40 трильйонів операцій/сек. Тобто відбулося збільшення швидкодії в 400 мільярдів разів! Неможливо назвати іншу сферу людської діяльності, де прогрес був би настільки очевидний і так великий [1].

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

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

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

Обчислювальна техніка в своєму розвитку по шляху підвищення швидкодії ЕОМ наблизилася до фізичних меж. Час переключення електронних схем досягло часткою наносекунди, а швидкість поширення сигналів у лініях, що пов'язують елементи і вузли машини, обмежена значенням 30 см/нс (швидкістю світла). Тому подальше зменшення часу перемикання електронних схем не дозволить істотно підвищити продуктивність ЕОМ. У цих умовах вимоги практики (складні фізико-технічні розрахунки, багатовимірні економіко-математичні моделі та інші завдання) щодо подальшого підвищення швидкодії ЕОМ можуть бути задоволені тільки шляхом поширення принципу паралелізму на самі пристрої обробки інформації та створення багатомашинних і багатопроцесорних (мультипроцесорних) обчислювальних систем. Такі системи дозволяють распаралеліть виконання програми або одночасно виконувати декілька програм.

Однією з різновидів таких систем є SMP система. Характерною рисою багатопроцесорних систем SMP архітектури є те, що всі процесори мають прямий і рівноправний доступ до будь-якою точки загальної пам'яті. Перші SMP системи складалися з декількох однорідних процесорів і масиву загальної пам'яті, до якої процесори підключалися через загальну системну шину. Однак дуже скоро виявилося, що така архітектура непридатна для створення масштабних систем. Перша проблема, яка виникла — велика кількість конфліктів при зверненні до загальної шини. Гостроту цієї проблеми вдалося частково зняти поділом пам'яті на блоки, підключення до яких за допомогою комутаторів дозволило распаралеліть звернення від різних процесорів. Однак і в такому підході неприйнятно великими здавалися накладні витрати для систем більш ніж з 32-ма процесорами [1].

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

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

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

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

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

Об'єкт дослідження: складна динамічна система на багатоядерній SMP-платформі.

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

Наукова новизна полягає в синтезі та дослідженні циклічного часового розкладу для динамічних систем.

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

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

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

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

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

3.1 Огляд міжнародних джерел

Питаннями дослідження багатоядерної SMP платформи займалися безліч західних вчених.

Одна з провідних груп дослідників на території США складається з таких вчених: В.Ванга, П. Мішра і С. Ранка. Вони опублікували статтю «Динамічна реконфигурація кешу і розмітка з метою оптимізації енергоспоживання у багатоядерних системах реального часу» [7], яка присвячена багатоядерним архітектурам, особливо мультіпроцесорам. У даній статті розроблено підхід, який дозволяє за допомогою керованого розбиття загальної кеш-пам'яті зменшити кількість внутрішніх перешкод у кеші, так що і продуктивність, і енергоефективність поліпшуються.

Провідна європейська група іспанських дослідників опублікувала статтю «Аналіз локальності даних SPECfp95».[8] Автори цієї статті І. Санчез та А. Гонсалез. Ця стаття являє собою детальний аналіз локальності, який базується на наборі тестів SPECfp95, а також відображає основні типи інформації, які можуть знадобитися користувачу в цілях оптимізації програми.

3.2 Огляд національних та локальних джерел

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

Планування та синхронізація процесів інтенсивно вивчається д.т.н., професором Святного Володимиром Андрійовичем і його аспірантами. Активно цим питанням займається аспірант ДонНТУ Іванов Юрій Олександрович. Основні його аспекти він розкрив у своїй магістерській роботі [6].

Також серед викладачів ДонНТУ роботою з чисельними методами та рішенням ОДУ для паралельного моделювання займається доцент Дмитрієва Ольга Анатолієвна [10], яка опубліковала понад 30 статей в журналах «Математичне моделювання», «Електронне моделювання», збірниках факультету КНТ та інше. Для роботи над моїм дипломним проектом одним з основних посібників для рішення диференціальних рівнянь вважаю книгу "Чисельні методи в інформатиці" Фельдман Л.П., Дмітрієва О.А.

4. Дослідження кільцевого тесту на SMP-системі [5]

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

SMP — симетричне мультипроцесування. Існує два види архітектур реалізації такого виду систем. Для нашого дослідження була обрана архітектура багатопроцесорних комп'ютерів (рисунок 1), у якій два або більше однакових процесорів підключаються до загальної пам'яті. Характерною рисою таких систем є те, що всі процесори мають прямий і рівноправний доступ до будь-якою точки загальної пам'яті. Перша проблема, яка виникла — велика кількість конфліктів при зверненні до загальної шини. Тому існують альтернативи цієї системи — це MPP системи і системи з архітектурою NUMA (де віртуальна пам'ять ділиться на роздільні блоки).

Реалізація SMP-системи на архітектурі багатопроцесорних комп'ютерів

Рисунок 1 — Реалізація SMP-системи на архітектурі багатопроцесорних комп'ютерів

Гармонійний осцилятор — це система, яка при зміщенні з положення рівноваги відчуває дію повертання сили, пропорційної зміщенню, відповідно до закону Гука [3] : F = -k*x, де k — коефіцієнт жорсткості пружини. Механічними прикладами гармонійного осцилятора є математичний маятник (з малими кутами відхилення), вантаж на пружині, торсіонний маятник і акустичні системи.

Гармонійний осцилятор

Рисунок 2 — Гармонійний осцилятор

Рівняння руху грузу з координатою x, згідно з другим законом Ньютона може бути записано таким чином:

формула гармонійного осцилятора

Для створення програмної моделі ГО виконується чисельне інтегрування системи диференціальних рівнянь, отриманих пониженням порядку рівняння гармонічного осцилятора:

система диференційних рівняннь

Багаторівнева реалізація моделі гармонійного осцилятора

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

Чисельний метод Ейлера формула трапецій

Рисунок 3 — Чисельний метод Ейлера формула трапецій

Для дослідження кільцевого тесту в одній моделі були використані два гармонійних осцилятори з відмінними власними частотами. Була розроблена модель, до якої увійшли дві системи рівнянь, для вирішення яких було використано метод Ейлера. Програмна реалізація моделі виконана засобами MSVS C++. При цьому використані механізми роботи з потоками WinAPI. Кожен з осциляторів реалізований як окремий потік, запуск яких виконується в нескінченному циклі реального часу.

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

SMP реалізація моделі гармонійного осцилятора

При дослідженні SMP-систем[4], у якості інструменту використовувалася система з чотирьохядерним процесором Intel i7 3770-K. Для реалізації багатоядерній моделі використовувалися функції API для роботи з потоками. Додаткові обчислювальні ресурси при цьому не призводять до лінійного збільшення швидкодії для конкретного завдання.

Параметри функції CreateThread (): LpThreadAttributes — є покажчиком на структуру LPSECURITY_ATTRIBUTES. Для присвоєння атрибутів захисту за замовчуванням, передавайте в цьому параметрі NULL. DwStackSize — параметр визначає розмір стека, що виділяється для потоку із загального адресного простору процесу. При передачі 0 — розмір встановлюється в значення за замовчуванням. LpStartAddress — покажчик на адресу вхідний функції потоку. LpParameter — параметр, який буде передано всередину функції потоку. DwCreationFlags — приймає одне з двох значень: 0 — виконання починається негайно, або CREATE_SUSPENDED — виконання зупиняється до наступних вказівок. LpThreadId — Адреса змінної типу DWORD у якій функція повертає ідентифікатор, приписаний системою новому потоку. Завершувати потік досить закриттям Хендлу, створеного для даного потоку, використовуючи функцію CloseHandle ().

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

Результат аналізу Intel VTune Performance Analyzer 9.1

Рисунок 4 — Результат аналізу Intel VTune Performance Analyzer 9.1

Графік числа звертань до кешу

Рисунок 5 — Графік числа звертань до кешу
(анимація: 6 кадрів, 7 циклів повторення, 144 кілобайт)

Пояснення до графіку

Рисунок 6 — Пояснення до графіку

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

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

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

Висновки

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

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

  1. Аналіз математичного опису моделі динамічної системи.
  2. Аналітичне рішення системи диференційних рівнянь.
  3. Проведено ряд експериментів з дослідження роботи кільцевого тесту.
  4. Розглянуто та досліджено часові характеристики обчислень і обмінів стандартними засобами програмування.

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

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

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

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

  1. Букатов А.А., Дацюк В.Н., Жегуло А.И. "Программирование многопроцессорных вычислительных систем", Ростов-на-Дону, 2003 г.
  2. Беки Дж.А. Теория и применения гибридных вычислительных систем / Беки Дж.А., Карплюс У.Дж // Перевод с англ. под ред. д.т.н., проф. Б.Я. Когана – М.: Мир, – 1970. – 483 с.
  3. Материалы из свободной энциклопедии "Википедия" — Гармонический осциллятор [Электронный ресурс]. – Рeжим дoступa к ресурсу: http://ru.wikipedia.org/wiki/Гармонический_осциллятор.
  4. Эхтер Ш. Многоядерное программирование / Ш. Эхтер, Дж. Робертс – СПб.: Питер, 2010. – 316 с.
  5. Первусяк А.И., Иванов Ю.А. "Исследование кольцевого теста на SMP системе".
  6. Магистерская работа Ю.А. Иванова "Исследование и разработка алгоритмов планирования процессов реального времени моделирования сложных динамических систем".
  7. Ванг В., Мишр П. и Ранк С. "Динамическая реконфигурация кэша и разметка с целью оптимизации энергопотребления в многоядерных системах реального времени".
  8. Санчез И., Гонсалез А. "Анализ локальности данных SPECfp95".
  9. Иванов А.Ю. "Построение службы синхронизации процессов".
  10. Информация о преподавателе Дмитриевой О.А.[электронный ресурс] / Сайт кафедры прикладной математики и информатики ДонНТУ, - http://pmi.donntu.ru/text/prepod/dmitrieva.html
  Резюме | Біографія