Національний Технічний Університет України «Київський Політехнічний Інститут»
Фізико-Технічний Інститут
Фізико-Технічний Інститут
А.В. Луньов, 11 клас, Черкаський фізико-математичний ліцей, м.Черкаси
Науковий керівник: О.О. Богатирьов
Педагогічний керівник: О.О. Богатирьов
Як відомо, закон Мура стверджує, що обчислювальна потужність мікропроцесорів подвоюється кожні 18–24 місяці. Очевидно, що в деякий момент часу одного процесора для розв’язування задач не вистачатиме, тому збільшення потужності здійснюється за рахунок нарощування кількості ядер. Разом з цим постає проблема – звичайна програма виконується лише одним із ядер, а не всіма. Тому на сьогоднішній день набуває актуальності питання паралелізму, тобто, можливості компонентів програми діяти незалежно один від одного, виконуючись паралельно. Для цього були розроблені спеціальні інструменти типу бібліотеки OpenMP, MPI, тощо. Але можливості традиційного імперативного програмування щодо паралелізму доволі обмежені: програмні блоки бувають настільки залежними один від одного по пам’яті, що звичайну програму треба змінювати майже повністю, що спричиняє втрати часу і призводить до збільшення часу розробки програми. Набагато доцільніше для цього підходить функціональне програмування – своєрідний «паттерн» програмування, у якому основною задачею є обчислення математичних функцій. Очевидно, що функції менш залежні по даним, оскільки вони працюють не з пам’яттю, а лише з даними, не змінюючи їх та запобігаючи колізіям операторів. Крім того, програму, написану у функціональному стилі, простіше розбити на незалежні блоки. Одними з функціональних мов програмування є мова F# – мова, створена корпорацією Microsoft, та мова Haskell — чисто функціональна мова програмування, названа в честь засновника функціонального програмування Хаскелла Каррі.
Метою даної роботи є розгляд функціональної парадигми програмування, мов F# та Haskell в цілому та в плані паралелізму, наведення прикладів з метою показати перевагу функціонального програмування над імперативним в області паралелізму.
Наукова новизна роботи полягає у тому, що функціональне програмування є принципово новим підходом до розв’язання проблеми паралелізму, оскільки для паралельного програмування зазвичай використовують традиційні імперативні мови та розроблені для них інструменти для розпаралелювання програм типу OpenMP, MPI, тощо.
У ході виконання роботи було проведено порівняльний аналіз імперативної та функціональної парадигм програмування. Було встановлено, що функціональне програмування володіє низкою переваг над іншими парадигмами, а саме:
Розглянуто можливості мови F# для розпаралелювання програм: асинхронні робочі потоки, Task Parallel Library та Parallel LINQ.
Розглянуто можливості мови Haskell для розпаралелювання програм, а саме модуль Control.Parallel.Strategies.
Розроблено послідовні та паралельні алгоритми пошуку суми простих чисел у проміжку від 1 до n та матричного множення мовами C++, F# та Haskell. Для написання програм мовою C++ використовувалась технологія OpenMP, мовою F# – інструменти Task Parallel Library та Parallel LINQ, а мовою Haskell – модуль Control.Parallel.Stategies.
Проведені обчислювальні експерименти свідчать, що паралельні програми, написані на мовах F# та Haskell, дають аналогічне прискорення у порівнянні з їх імперативними аналогами, але програють у ефективності при розв’язуванні певної множини задач, яка передбачає використання змінних структур даних великого розміру, що, натомість, не впливає на ефективність розпаралелювання. Отже, функціональне програмування, в цілому, ефективно розв’язує проблему розпаралелювання.
Перелік посилань:
Сошніков Д.В. Программирование на F#, 2011. – 192 с.
Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем, 2010. – 559 с.
Pickering R. Beginning F#, 2009. – 427 c.
Pickering R. Expert F#, 2010. – 596 c.
Petricek T., Skeet J. Real World Functional Programming, 2010. – 563 p.
Simon Marlow Parallel and Concurrent Programming in Haskell — 322 p.