Дослідження паралельного алгоритму побудови діаграми Вороного на площині
Зпропонована маштабована паралельна реалізація алгоритму побудови діаграми Вороного на площині. Описано процес розробки алгоритму та програмування з використанням бібліотеки Intel Threading Building Blocks (TBB). Проведене дослідження продуктивності та наведені результати експериментів.---------- Пр...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут програмних систем НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/2915 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Дослідження паралельного алгоритму побудови діаграми Вороного на площині / К.А. Березовський // Пробл. програмув. — 2009. — № 1. — С.28-35. — Бібліогр.: 15 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860004625033199616 |
|---|---|
| author | Березовський, К.А. |
| author_facet | Березовський, К.А. |
| citation_txt | Дослідження паралельного алгоритму побудови діаграми Вороного на площині / К.А. Березовський // Пробл. програмув. — 2009. — № 1. — С.28-35. — Бібліогр.: 15 назв. — укр. |
| collection | DSpace DC |
| description | Зпропонована маштабована паралельна реалізація алгоритму побудови діаграми Вороного на площині. Описано процес розробки алгоритму та програмування з використанням бібліотеки Intel Threading Building Blocks (TBB). Проведене дослідження продуктивності та наведені результати експериментів.----------
Предложена масштабируемая параллельная реализация алгоритма построения диаграммы Вороного на плоскости. Описан процесс раз-работки алгоритма и приграммирования с ис-пользованием библиотеки Intel Threading Building Blocks (TBB). Произведено исследо-вание продуктивности и приведены результаты экспериментов.----------
It is offered a scalable implementation of 2D Voronoi diagram constructing algorithm. Intel Threading Building Blocks (TBB) programming features and the algorithm developing process are described. Experimental results of performance research are presented.
|
| first_indexed | 2025-12-07T16:38:42Z |
| format | Article |
| fulltext |
Моделі та засоби паралельних і розподілених програм
© К.А. Березовський, 2009
28 ISSN 1727-4907. Проблеми програмування. 2009. № 1
УДК 681.3
К.А. Березовський
ДОСЛІДЖЕННЯ ПАРАЛЕЛЬНОГО АЛГОРИТМУ ПОБУДОВИ
ДІАГРАМИ ВОРОНОГО НА ПЛОЩИНІ
Зпропонована маштабована паралельна реалізація алгоритму побудови діаграми Вороного на площині.
Описано процес розробки алгоритму та програмування з використанням бібліотеки Intel Threading
Building Blocks (TBB). Проведене дослідження продуктивності та наведені результати експериментів.
Вступ
Діаграми Вороного [1], отримали
свою назву в честь українського математи-
ка Георгія Феодосійовича Вороного (1868-
1908), що досліджував загальний n-
вимірний випадок побудови таких об`єктів
[2]. Можна нарахувати немало предметних
областей, у яких зазвичай використовують
такі конструкції [3], наприклад, в астроно-
мії – ідентифікація скупчень зірок та гала-
ктик; в біології, екології, та лісництві –
моделювання та аналіз конкуренції рос-
лин; у картографії – інтеграція знімків
зроблених супутником тощо.
До поняття діаграми Вороного на-
водять багато прикладних задач, напри-
клад, наступна: нехай маємо двовимірну
електронну карту міста, причому кожній
будівлі ставиться у відповідність адреса у
традиційній формі (вулиця, номер будин-
ку) і пара координат ),( yx . Правопорядок
у місті забезпечують N патрулів, які май-
же весь час перебувають у русі. Роботу ко-
ординує диспетчерська служба, яка має
інформацію щодо їхнього положення. До
обов`язків диспетчерів входить:
• прийняття звернень від громадян,
які надають адресу інциденту в тра-
диційній формі;
• надання відповідних вказівок мі-
ліціонерам.
Необхідно розробити механізм, за яким
диспетчерська служба могла б швидко да-
вати доручення лише тим міліціонерам, які
знаходяться найближче до місця інциден-
ту. Математично суть задачі можна пред-
ставити таким чином. Маємо площину.
Нехай S – множина її точок, в яких знахо-
дяться патрулі у деякий момент часу (рис.
1, а), i – точка, в якій стався інцидент.
Наша мета полягає у тому, щоб знайти
таку точку Sa ∈ , що =),( aidist
= ),(min bidistSb∈ , тобто визначити міліціо-
нерів, які зможуть прибути на місце рані-
ше за інших. Періодично диспетчерська
служба визначає координати патрулів (ко-
ординати точок множини S ). За точками
цієї множини будується діаграма Вороного
)(SVor (рис. 1, б). Коли надходить інфор-
мація про інцидент, то вона трансформу-
ється з традиційної форми (вулиця, номер
будинку) у координатну (точка i ). При
цьому визначається, якому многокутнику
Вороного із побудованої діаграми нале-
жить i , відповідний екіпаж (точка a )
отримує доручення.
Можливий випадок коли i лежить
на ребрі діаграми, таким чином „найближ-
чими” до i є одразу декілька патрулів (не
більше ніж три [1]). У такому разі система
обирає одну з них. Діаграма Вороного для
розв`язання зазначеної задачі може мати
досить великі розміри. Крім того вона не є
статичною. У загальному випадку, патрулі
постійно знаходяться у русі, тому через
невеликі проміжки часу слід перебудову-
вати діаграму, враховуючи зміни. Саме
тому для досягнення необхідної ефектив-
ності слід розробляти паралельні алгорит-
ми побудови діаграми Вороного, що до-
зволяє розв`язувати задачу в реальному
часі.
З геометричних міркувань на мно-
жину точок S зазвичай [1] накладається
обмеження, що жодні чотири її точки не
лежать на одному колі. Це забезпечує, що
у будь-якій вершині діаграми Вороного
перетинається рівно три ребра, і гарантує
існування єдиного центра описаного кола,
Моделі та засоби паралельних і розподілених програм
29
що проходить через відповідні точки S .
Зазначена умова є основною для перевірки
допустимості вхідних даних. При її пору-
шенні побудова діаграми не є можливою
[1].
1. Алгоритм побудови діаграми
Вороного
У роботі [1] наведено послідовний
алгоритм, що є гарною основою для побу-
дови його паралельного аналога. Нехай N
– множина натуральних чисел, {} – поро-
жня множина, S – множина точок площи-
ни, елементами якої є упорядковані пари
( )yxp , , де ., Nyx ∈ Відношення лінійного
порядку R на S введемо так:
нехай )','(' yxp S∈ , )","(" yxp S∈ , тоді
"' Rpp якщо
<=
<
"',"'
"'
yyxx
xx
. Нагадаємо,
що згідно означення [4] відношення R має
такі властивості:
• рефлексивність – )( pRpp∀ ;
• антисиметричність –
)( 21122121 ppRppRpppp =⇒∧∀∀ ;
• транзитивність –
)( 313221321 RppRppRppppp ⇒∧∀∀∀ ;
• порівнюваність –
)( 122121 RppRpppp ∨∀∀ .
Тепер маємо змогу виконати розріз
множини S на дві підмножини 1S та 2S .
Причому SSS =∪ 21 , {}21 =∩ SS ,
),( 21221121 RppSpSppp ⇒∈∈∀∀ . Викори-
ставши підхід „розподіляй і володарюй”
[5], отримаємо наступний послідовний
алгоритм.
Вхід. Множина S , що складається з точок
площини.
Вихід. Множина многокутників Вороного.
Крок 1. Розділити множину S на дві при-
близно рівні підмножини 1S та 2S ,
{}21 =∩ SS .
Крок 2. Рекурсивно побудувати )( 1SVor та
)( 2SVor .
Крок 3. Побудувати ламану d („розділяю-
чий ланцюг”), що розділяє 1S та 2S .
Крок 4. Вилучити всі ребра діаграми
)( 2SVor , що розташовані зліва від d , та
всі ребра )( 1SVor , що розташовані справа
від d . Отримаємо )(SVor – діаграму Во-
роного для множини S .
Зазначимо, що початкове розбиття
S , може бути виконане за час )(NO (за
допомогою алгоритма пошуку медіани).
Крок 4 може бути виконаний за час
)()( 21 NOSSO =+ . Часова склад-
а б
Рис. 1, а) схематичне зображення положення патрулів; б) діаграма Вороного )(SVor
Моделі та засоби паралельних і розподілених програм
30
ність послідовного алгоритму становить
)log( nnO .
1.1. Паралельний алгоритм побудови
діаграми Вороного
Розділимо множину точок S ліній-
но на частини. Кількість груп точок дорів-
нює кількості вузлів обчислювальної сис-
теми, що виділені для виконання задачі.
Паралельний алгоритм має вигляд:
Вхід. Множина S , що складається з точок
площини.
Вихід. Множина многокутників Вороного.
Крок 1. Визначити кількість наявний вуз-
лів ,P )2( ≥P . Розділити множину S на
P приблизно рівних підмножин
PSSS ,..., 21 , причому {}=∩ ji SS , Pi ,1= ,
Pj ,1= , ji ≠ .
Крок 2. Паралельно і рекурсивно побуду-
вати )(),...(),( 21 PSVorSVorSVor .
Крок 3. PI =: . Виконати K разів, де
{ }
{ }
≠+
=
=
0log,1log
0log,log
22
22
PP
PP
K .
Крок 3, а) паралельно побудувати
2
I
ламаних (розділяючих ланцюгів), що ле-
жать між 1−iS та iS для
=
2
*2,2
I
i ;
Крок 3, б) паралельно вилучити всі ребра
діаграми )( 1−iSVor , розташовані зправа
відповідної ламаної, та всі ребра діаграми
)( iSVor , розташовані зліва відповідної ла-
маної, для
=
2
,2
I
i , отримати діаграму
)( jSVor , для
+
= )2,mod(
2
,1 I
I
j ,
)2,mod(
2
: I
I
I +
= .
У роботі [6] показано, що на моделі
абстрактної паралельної машини CREW
PRAM [7], часова складність даного алго-
ритму становить )(log2 nO .
2. Аналіз вимог до засобів
розробки
Першим кроком у реалізації пара-
лельного алгоритму є вибір мови програ-
мування та бібліотеки високорівневих ін-
струментів (якщо вона існує). Програмні
засоби мають задовольняти таким голо-
вним вимогам:
• швидкодія результуючого (викону-
ваного) коду;
• якомога вищій рівень абстракції,
що сприятиме збільшенню швидкості про-
грамування, а також дозволить розробнику
мислити категоріями задач, а не потоків;
• можливість роботи на різних архі-
тектурах та платформах;
• маштабованість, тобто автоматичне
визначення кількості ядер процесора, та
їхнє ефективне використання.
Для eкспериментальної побудови
паралельної реалізації алгоритму в даній
роботі прийнята широковідома платформа
Intel Threading Building Blocks (TBB) [8].
Було вирішено порівняти деякі аспекти
цього прикладного програмного інтерфей-
су (API) з іншими засобами організації ба-
гатопотокової роботи, а саме: OpenMP [9]
та потоками операційної системи (ОС).
Якщо розглянути ці альтернативи із
позиції складності розробки, можемо кон-
статувати, що використання вбудованих
потоків ОС є складнішим, у порівнянні з
TBB та OpenMP. Одна із причин полягає у
тому, що зазначені бібліотеки створюють
так званий „пул потоків”, і за його допомо-
гою відбувається автоматична синхроніза-
ція та планування роботи, що приведена в
таблиці.
Взявши до уваги мову програму-
вання, що буде використовуватися, маємо
такі попередні висновки. Для розробки на
C або Fortran краще використати OpenMP,
адже цей API зручніший для структурного
програмування, що може суттєво зменши-
ти витрати часу на розробку для не громіз-
дких проектів. З тих же причин варто зу-
пинити свій вибір на OpenMP, якщо пла-
Моделі та засоби паралельних і розподілених програм
31
Таблиця 1. Порівняння можливостей альтернатив за деякими критеріями
нується програмування на C++ і передба-
чаються численні операції обробки маси-
вів. Якщо планується широке використан-
ня об`єктно-орієнтованого підходу, ша-
блонів C++, то варто обрати TBB. Склад-
ність моделей програмування із вбудова-
ними потоками операційної системи, для
мов C та C++, приблизно однакова. Але
той факт, що розбиття на потоки має бути
описане у функціональному стилі, зумов-
лює використання мови C для програму-
вання потоків ОС, більш природнім. У
C++-програмах, орієнтованих на роботу з
об`єктами, використання вбудованих по-
токів операційної системи може порушити
стиль програмування та іти у розріз із про-
ектним рішенням.
Для TBB та потоків ОС підтримка
певного компілятора не є необхідною, на
відміну від OpenMP. Для роботи із цим
API слід використати компілятор, що роз-
пізнає pragma-директиви, процедури та
змінні оточення OpenMP [9]. Але варто за-
значити, що розробники багатьох сторон-
ніх компіляторів вже забезпечують деяку
підтримку цього API.
Код, що містить компоненти
OpenMP або TBB може працювати під різ-
ними ОС, водночас як реалізація на основі
вбудованих потоків, потребуватиме пере-
робки під конкретну систему. Особливі
незручності виникають якщо слід перено-
сити код між системами Windows (викори-
стовуються Windows-потоки) і Unix (Posix-
потоки) [10].
API TBB грунтується на парадигмі
так званого „узагальненого програмуван-
ня” [11], тому слід використовувати його
шаблони паралелізму тоді, коли необхідно
працювати з ітераційним простором, що
визначив користувач, або переслідується
мета отримання результатів складних опе-
рацій редукції [8].
Вкладенний паралелізм може бути
реалізований за допомогою вбудованих
потоків та OpenMP. Варто пам`ятати, що
розповсюдженою проблемою є занадто ін-
тенсивне використання ресурсів. Розроб-
ники TBB декларують, що підтримці реку-
рсивного та вкладеного паралелізму була
приділена особлива увага. Зокрема зазна-
чається алгоритм динамічного балансу-
вання навантаження та метод захоплення
задач, що реалізовані у планувальнику за-
дач TBB [8].
OpenMP розроблений для роботи у
багатопроцесорних системах із розподіле-
ною пам`яттю [9]. TBB – для реалізації ба-
гатопотоковості [12]. В обох випадках за
мету ставилося досягнення продуктивнос-
ті. Конструктивні елементи цих API були
розроблені, безпосередньо, для паралель-
ного розбиття маштабованих даних. За
умови інтенсивних обчислювальних нава-
нтажень, актуальність їхнього використан-
ня збільшується. При роботі із вбудовани-
Критерій TBB OpenMP Потоки
ОС
Організація паралелізму на рівні задач Так Так Ні
Підтримка декомпозиції даних Так Так Ні
Складені шаблони паралельної обробки Так Ні Ні
Узагальнені шаблони паралельної обробки Так Ні Ні
Підтримка маштабованого вкладеного паралелізму Так Ні Ні
Інтегроване розподілення навантаження Так Так Ні
Статичне розподілення Ні Так Ні
Паралельні структури даних Так Ні Ні
Маштабоване розподілення пам`яті Так Ні Ні
Задачі орієнтовані на ввід/вивід Ні Ні Так
Елементи синхронізації на рівні користувача Так Так Ні
Не вимагається підтримка певного компілятора Так Ні Так
Підтримка у різноманітних ОС Так Так Ні
Моделі та засоби паралельних і розподілених програм
32
ми потоками розробнику доведеться само-
стійно реалізовувати деякі алгоритми, що
користувачі OpenMP або TBB мають у го-
товому вигляді. У такому випадку слід бі
льше уваги приділити тестуваню, аби уни-
ктнути появи помилок взаємного блоку-
вання, або змагання потоків за час проце-
сора. Але у деяких випадках вбудовані по
токи ОС є беззаперечно кращим варіантом.
Наприклад, коли йдеться про створення
паралельного виконання на основі подій
або вводу-виводу.
Як OpenMP, так і TBB задовольня-
ють принциповим вимогам, що були по-
ставлені на початку розділу. Зважаючи на
більшу привабливість поєднання TBB з
підходом об`єктно-орієнтованого програ-
мування, було прийнято рішення зупинити
свій вибір на цьому API.
3. Прикладний програмний інтерфейс
для TBB та його використання
TBB, як засіб забезпечення високо-
рівневого паралелізму містить набір ком-
понентів для досягнення швидкодії циклів
з наперед заданою кількістю ітерацій, цик-
лів з редукцією, передумовою. Також до
складу прикладного програмного інтер-
фейсу входять контейнери для паралельно-
го програмування, специфічні засоби роз-
поділу пам`яті, примітиви синхронізації.
Повертаючись до контейнерів, зазначимо,
що вони аналогічні тим, що використову-
ються в Standard Template Library (STL)
[13], але розробники TBB стверджують,
що „накладні витрати” у них менші [8].
Для компіляції програм, які викори-
стовують TBB необхідно інсталювати па-
кет, що містить відповідні класи та функ-
ції. Для виконання програм під операцій-
ною системою користувача достатньо мати
динамічну бібліотеку для даної ОС. Як
правило вона входить до складу пакета.
До основних алгоритмів API
TBB належать:
parallel_for,
parallel_reduce,
parallel_scan,
parallel_while,
parallel_do,
pipeline,
parallel_sort.
Контейнери:
concurrent_queue,
concurrent_vector,
concurrent_hash_map.
Засоби для маштабованого виділення
пам`яті:
scalable_malloc,
scalable_free,
scalable_realloc,
scalable_calloc,
scalable_allocator,
cache_aligned_allocator.
Семафори для синхронізації потоків, що
виконуються одночасно:
mutex,
spin_mutex,
queuing_mutex,
spin_rw_mutex,
queuing_rw_mutex,
recursive mutex.
Атомарні (нероздільні на дрібніші) опера-
ції:
fetch_and_add,
fetch_and_increment,
fetch_and_decrement,
compare_and_swap,
fetch_and_store.
Синхронізація потоків із використанням
глобальних міток часу (time stamp) та пла-
нувальник задач, що має безпосередній до-
ступ до їхнього створення, активації та ко-
нтролю.
Спеціалісти компанії Intel наголо-
шують [14] на можливості роботи бібліо-
теки сумісно з потоками ОС Microsoft
Windows, Posix-потоками, та API OpenMP.
На сьогодні доступні реалізації TBB для
операційних систем Linux, Solaris, Mac OS,
Windows.
4. Розробка паралельної реалізації
Діаграма статичної структури роз-
роблюваної програми мовою UML [15] по-
казана на рис. 2. Вона містить класи,
зв`язки між ними, їхні атрибути, методи.
Перелічені типи Type, Direction слу-
гують для характеристики орієнтації пря-
мої на площині з прямокутною системою
координат.
LineFunc – клас, що описує пряму
(промінь, відрізок) на площині. Він містить
Моделі та засоби паралельних і розподілених програм
33
коефіцієнти рівнянь як загального вигляду
)0( =++ cbyax , так і часткових випад-
ків (наприклад, bkxy += ). Має мето-
ди визначення відстані від точки площи-
ни до прямої, променя або відрізку
(get_dist()), знаходження перпендикуляра
(get_perpend_lf()), обчислення значення
відповідної функції у точці (value()), зна-
ходження точки перетину прямих, проме-
нів, відрізків (get_intesect()). Цей клас є ос-
новою для побудови реберного списку із
подвійними зв`язками (Rsds), оскільки за
допомогою його методів визначаються ве-
ршини багатокутників діаграми Вороного.
Рис. 2. Діаграма класів
Клас List реалізує основні операції
над елементами списків та здійснює гене-
рацію точок площини (generate()).
QuickBall – клас, що реалізує алго-
ритм побудови опуклої оболонки „Quick-
Ball” [1] (compute()).
Клас ConvexHull відповідальний за
організацію побудов опуклих оболонок та
збереження їхніх результатів (Con-
vexHull()).
Клас VoronoiDiagram керує підгото-
вкою вхідних даних, їхньою перевіркою,
побудовою діаграми, визначенням розді-
ляючого ланцюга, виправленням можливих
помилок.
Клас Main реалізує інтерфейс для
порівняння інших програм з реалізацією
VoronoiDiagram. Далі наведено фрагмент
коду методa main():
...
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/blocked_range.h"
...
using namespace tbb;
using namespace std;
...
static const size_t chunk_st=1000;
static const size_t min_x=-20000;
static const size_t min_y=-20000;
static const size_t max_x=20000;
static const size_t max_y=20000;
...
int main(int argc, char *argv[]) {
...
task_scheduler_init init;
tick_count begin_tc, end_tc, serial_tc,
parallel_tc;
size_t pnt_nbr;
List s_list;
//ініціалізація множини S;
pnt_nbr = get_p_n();
s_list = new List();
Моделі та засоби паралельних і розподілених програм
34
s_list.generate(min_x, min_y, max_x,
max_y)
//виконання паралельної програми;
begin_tc = tick_count::now();
paral-
lel_for(blocked_range<Node*>(0,
s_list.size(),chunk_st 100), Voron-
oiDiagram(s_list));
end_tc = tick_count::now();
parallel_tc = end_tc-begin_tc;
//виконання послідовної програми;
begin_tc = tick_count::now();
SerialVoronoiDiagram(s_list)
end_tc = tick_count::now();
parallel_tc = end_tc-begin_tc;
...}
...
5. Експерименти
Для експериментальної перевірки
ефективності розпаралелювання було ви-
конано наступні кроки:
1) розробити послідовну програму;
2) провести її тестування;
3) частину коду, що має виконуватися,
паралельно переписати із використанням
компонентів TBB.
Під час виконання (п. 3), автор пе-
реконався в недоліку проектування. Оскі-
льки раніше розроблений код не відповідав
STL-стилю компонентів TBB, що призвело
до виконання деякого обсягу надлишкової
роботи. Експерименти з дослідження
швидкодії роботи програм здійснювалися
на машинах з різними процесорами: Intel
Pentium III 400 МГц, та двоядерному Intel
Core 2 Duo 2,53 ГГц.
Таким чином, завдяки використан-
ню паралельної програми, на двоядерному
процесорі вдалося досягти збільшення
швидкості в 1,792 рази (у середньому для
10 експериментів (рис. 3)) щодо швидкості
роботи послідовної програми. Крім того
отримано несподіваний результат на одно-
ядерному „повільному” процесорі. Вияви-
лося, що паралельна версія програми пра-
цює в 1,18 (у середньому для 10 експери-
ментів) рази повільніше ніж послідовна.
Звісно, зменшення швидкості очікувалося,
оскільки воно зумовлене використанням
шаблонів TBB, але не передбачалося, що
втрати швидкодії будуть настільки суттє-
вими.
Висновки
У роботі запропонована маштабо-
вана паралельна реалізація алгоритму по-
будови діаграми Вороного на площині.
Сформульована низка вимог до програм-
них засобів забезпечення високорівневого
паралелізму на багатоядерних однопроце-
сорних системах. Внаслідок аналізу функ-
ціональності трьох прикладів таких засобів
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
1 2 3 4 5 6 7 8 9 10
Точок (*50000)
Ч
а
с
(с
е
к
у
н
д
и
)
TBB, двоядерний процесор
Послідовна програма,
двоядерний процесор
Послідовна програма,
одноядерний процесор
TBB, одноядерний процесор
Моделі та засоби паралельних і розподілених програм
35
було зроблено висновок, що Intel Threading
Building Blocks (TBB) найбільш повно від-
повідає поставленим вимогам. Розглянуто
компоненти цього прикладного програм-
ного інтерфейсу, використавши які, було
виконано паралельну реалізацію алгоритму
побудови діаграми Вороного. Представле-
но результати експерименту для визначен-
ня ефективності роботи реалізацій послі-
довного та паралельного алгоритмів на од-
ноядерному та двоядерному процесорах.
1. Препарата Ф., Шеймос М. Вычислитель-
ная геометрия: Введение: Пер. с англ. –
М.: Мир, 1989. – 478 с.
2. Вороний Георгій Феодосійович. –
http://uk.wikipedia.org/wiki/Вороний_Геор
гій_Феодосійович
3. Drysdale S. Voronoi Diagrams: Applications
from Archeology to Zoology. –
http://www.ics.uci.edu/~eppstein/gina/scot.d
rysdale.html
4. Верещагин Н., Шень А. Лекции по мате-
матической логике и теории алгоритмов.
–
ftp://ftp.mccme.ru/users/shen/logic/sets/part1
pdf.zip
5. Ахо А., Хопкрофт Дж., Ульман Дж. По-
строение и анализ вычислительных алго-
ритмов: Пер. с англ. – М.: Мир, 1979. –
536 с.
6. Aggarwal A., Chazelle B., Guibas L.,
O`Dunlaing C., Yap C. Parallel Geometry. –
Algorithmica, 1998. – 328 p.
7. Parallel Random Access Machine. –
http://en.wikipedia.org/wiki/Parallel_Rando
m_Access_Machine
8. Reinders J. Intel Threading Building Blocks:
Outfitting C++ for Multi-core Processor
Parallelism. – O’Reilly Media, 2007. –
303 p.
9. OpenMP. –
https://computing.llnl.gov/tutorials/openMP/
10. Posix. – http://en.wikipedia.org/wiki/Posix
11. Standard Template Library.
http://en.wikipedia.org/wiki/Standard_Templ
ate_Library
12. Intel Threading Building Blocks. –
http://en.wikipedia.org/wiki/TBB
13. Дейтел П.Дж., Дейтел Х.М. Как програ-
ммировать на С++: Пер. с англ. – 5-е
изд., – М.: Бином пресс, 2008. –1454 с.
14. Threading Building Blocks 2.1. –
http://www.intel.com/cd/software/products/a
smo-na/eng/294797.htm
15. Буч Г., Рамбо Д., Джекобсон А. Язык
UML. Руководство пользователя: Пер. с
англ. – 2-е изд., стер. – М.: Питер ДМК,
2004. – 429 с.
Отримано 04.12.2008
Про автора:
Березовський Костянтин Анатолійович,
студент 2-го курсу, факультету кібернети-
ки Київського національного університету
імені Тараса Шевченка,
Проспект Академіка Глушкова 2, корп. 6 ,
Тел.: 521 3554
8 – (097) 173 6420
e-mail: kos:berezovskyi@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-2915 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:38:42Z |
| publishDate | 2009 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Березовський, К.А. 2009-05-22T13:16:33Z 2009-05-22T13:16:33Z 2009 Дослідження паралельного алгоритму побудови діаграми Вороного на площині / К.А. Березовський // Пробл. програмув. — 2009. — № 1. — С.28-35. — Бібліогр.: 15 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2915 681.3 Зпропонована маштабована паралельна реалізація алгоритму побудови діаграми Вороного на площині. Описано процес розробки алгоритму та програмування з використанням бібліотеки Intel Threading Building Blocks (TBB). Проведене дослідження продуктивності та наведені результати експериментів.---------- Предложена масштабируемая параллельная реализация алгоритма построения диаграммы Вороного на плоскости. Описан процесс раз-работки алгоритма и приграммирования с ис-пользованием библиотеки Intel Threading Building Blocks (TBB). Произведено исследо-вание продуктивности и приведены результаты экспериментов.---------- It is offered a scalable implementation of 2D Voronoi diagram constructing algorithm. Intel Threading Building Blocks (TBB) programming features and the algorithm developing process are described. Experimental results of performance research are presented. uk Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Дослідження паралельного алгоритму побудови діаграми Вороного на площині Analysis of parallel algorithm for construct-ing 2D Voronoi diagram Исследование параллельного алгоритма построения диаграммы Вороного на плоскости Article published earlier |
| spellingShingle | Дослідження паралельного алгоритму побудови діаграми Вороного на площині Березовський, К.А. Теоретичні та методологічні основи програмування |
| title | Дослідження паралельного алгоритму побудови діаграми Вороного на площині |
| title_alt | Analysis of parallel algorithm for construct-ing 2D Voronoi diagram Исследование параллельного алгоритма построения диаграммы Вороного на плоскости |
| title_full | Дослідження паралельного алгоритму побудови діаграми Вороного на площині |
| title_fullStr | Дослідження паралельного алгоритму побудови діаграми Вороного на площині |
| title_full_unstemmed | Дослідження паралельного алгоритму побудови діаграми Вороного на площині |
| title_short | Дослідження паралельного алгоритму побудови діаграми Вороного на площині |
| title_sort | дослідження паралельного алгоритму побудови діаграми вороного на площині |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/2915 |
| work_keys_str_mv | AT berezovsʹkiika doslídžennâparalelʹnogoalgoritmupobudovidíagramivoronogonaploŝiní AT berezovsʹkiika analysisofparallelalgorithmforconstructing2dvoronoidiagram AT berezovsʹkiika issledovanieparallelʹnogoalgoritmapostroeniâdiagrammyvoronogonaploskosti |