Бабков Віктор Світозарович. Ефективний метод реконструкції тривимірних моделей реальних об'єктів та його реалізація на паралельних комп'ютерних системах

Краткое описание

Бабков Віктор Світозарович. Ефективний метод реконструкції тривимірних моделей реальних об'єктів та його реалізація на паралельних комп'ютерних системах : Дис... канд. наук: 05.13.05 - 2009.

Бабков В.С. Ефективний метод реконструкції тривимірних моделей реальних об’єктів та його реалізація на паралельних комп’ютерних системах. Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 Комп’ютерні системи та компоненти. ДВНЗ „Донецький національний технічний університет”, Донецьк, 2009.
Дисертація присвячена розробці методів реконструкції моделей реальних тривимірних об’єктів за проекційними даними, які підвищують продуктивність обчислювальних систем комп’ютерної графіки
У дисертації запропоновано метод обчислення ізоповерхні у 3D-просторі за допомогою радіальних симетричних функцій на основі декомпозиції центрів інтерполяції на групи та ієрархічного обчислення інтерполянта. Для нового методу визначено оцінки складності. Досліджено вплив виду функції відстані на похибку при розрахунку інтерполянта і встановлено, що використання інверсного мультиквадрика забезпечує мінімальну похибку. Отримано відображення запропонованого методу на паралельні архітектури SIMD і MIMD. Отримано оцінки для часових витрат залежно від обсягу даних і кількості процесорних елементів. Запропоновано відображення паралельних реалізації нового методу на архітектуру графічного процесора.

Дослідження, проведені в дисертаційній роботі, є новим рішенням наукової задачі, що полягає в підвищенні продуктивності реконструкції ізоповерхневих моделей тривимірних об’єктів у системах комп’ютерної графіки та структурній і алгоритмічній організації паралельних обчислювальних процесів.
1. Отримано теоретичні оцінки часової та просторової складності існуючих методів реконструкції ізоповерхонь з використанням симетричних радіальних функцій.
2. Запропоновано паралельний ієрархічний метод реконструкції, який відрізняється від відомих незалежним обчисленням частин глобального інтерполянту, що дозволяє зменшити часові витрати на побудову моделі тривимірного об’єкту.
3. Подальшого розвитку отримав ієрархічний метод розрахунку поверхні двовимірного об’єкту за множиною проекційних точок, який відрізняється від відомого принципом декомпозиції простору на частини, що дозволяє використовувати метод у тривимірному просторі.
4. Досліджено можливість застосування запропонованого методу для просторів різної розмірності і запропоновано узагальнені алгоритми декомпозиції і обчислення інтерполянта. Для запропонованого методу визначено теоретичні оцінки часової складності.
5. Досліджено вплив виду функції відстані на похибку при розрахунку глобального інтерполянта запропонованим методом і встановлено, що використання інверсного мультиквадрика у якості функції відстані забезпечує мінімальну відносну похибку, яка у найгіршому випадку не перевищує 0.98%.
6. Отримано відображення запропонованого методу реконструкції на паралельні архітектури типу SIMD, MIMD UMA, MIMD NC-NUMA та запропоновано схеми організації обчислювального процесу для вищевказаних архітектур. Отримано теоретичні оцінки для часових витрат залежно від обсягу вхідних даних і кількості процесорних елементів. Також визначено максимальну кількість процесорних елементів, перевищення якої перестає зменшувати часові витрати на процедуру побудови ізоповерхні, її значення становитьдля SIMD тадля MIMD систем. Визначено дольову частку операцій пересилання та операцій процесорних елементів у часових витратах (54% на 46% - SIMD, 57% на 43% - MIMD UMA та 23% (глоб.), 45% (локал.) на 43% - MIMD NC-NUMA, відповідно).
7. Проаналізовано характеристики реалізацій методу на архітектурах SIMD і MIMD. Визначено, що SIMD-реалізація методу забезпечує прискорення,а MIMD-реалізація -. При цьому для великихефективність SIMD-реалізації спрямовується до 0.1, а MIMD-реалізації до 0.5.Отримано теоретичні оцінки для ступеню паралелізму SIMD і MIMD-реалізацій і визначено, що ступінь паралелізму для MIMD-реалізації перевищує ступінь паралелізму для SIMD-реалізації уразів (- максимальна кількість точок в одному піддомені після декомпозиції).
8. Експериментально визначено, що запропонований метод з точки зору часових витрат ефективніший за ієрархічний метод радіальних симетричних функцій в середньому на 57%. Підтверджено, що при малій кількості процесорних елементів () MIMD-реалізація має гірші часові характеристики порівняно з SIMD. Показано, що на практиці збільшення кількості процесорних елементів в MIMD-архітектурі з топологією „загальна шина” зменшує прискорення через вплив накладних витрат при роботі із загальної пам’яттю. Також визначено, що практичне прискорення паралельної реалізації запропонованого методу лежить у межах теоретичних оцінок і для SIMD-реалізації складає в середньому 3..15 разів. Доведено, що використання архітектури MIMD NC-NUMA замість MIMD UMA зменшує для даного типу графічного процесора та пам’яті час реконструкції в середньому на 30%.