Автотьюнер та візуалізація для задачі метеорологічного прогнозування

Розглядається застосування техніки автотьюнінгу та розширення картографічного інструментарію Google Maps для комплексного розв’язання задачі короткотермінового моделювання циркуляції атмосфери. Наводяться чисельні показники швидкодії розробленого паралельного алгоритму....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Іваненко, П.А., Дорошенко, А.Ю., Овдій, О.М., Суслова, Л.М.
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2013
Schriftenreihe:	Проблеми програмування
Schlagworte:	Прикладні засоби програмування та програмне забезпечення
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/86694
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Автотьюнер та візуалізація для задачі метеорологічного прогнозування / П.А. Іваненко, А.Ю. Дорошенко, О.М. Овдій, Л.М. Суслова // Проблеми програмування. — 2013. — № 4. — С. 64-73. — Бібліогр.: 11 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-86694
record_format	dspace
spelling	irk-123456789-866942015-09-27T03:02:04Z Автотьюнер та візуалізація для задачі метеорологічного прогнозування Іваненко, П.А. Дорошенко, А.Ю. Овдій, О.М. Суслова, Л.М. Прикладні засоби програмування та програмне забезпечення Розглядається застосування техніки автотьюнінгу та розширення картографічного інструментарію Google Maps для комплексного розв’язання задачі короткотермінового моделювання циркуляції атмосфери. Наводяться чисельні показники швидкодії розробленого паралельного алгоритму. 2013 Автотьюнер та візуалізація для задачі метеорологічного прогнозування / П.А. Іваненко, А.Ю. Дорошенко, О.М. Овдій, Л.М. Суслова // Проблеми програмування. — 2013. — № 4. — С. 64-73. — Бібліогр.: 11 назв. — рос. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/86694 681.5 ru Проблеми програмування Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення
spellingShingle	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення Іваненко, П.А. Дорошенко, А.Ю. Овдій, О.М. Суслова, Л.М. Автотьюнер та візуалізація для задачі метеорологічного прогнозування Проблеми програмування
description	Розглядається застосування техніки автотьюнінгу та розширення картографічного інструментарію Google Maps для комплексного розв’язання задачі короткотермінового моделювання циркуляції атмосфери. Наводяться чисельні показники швидкодії розробленого паралельного алгоритму.
author	Іваненко, П.А. Дорошенко, А.Ю. Овдій, О.М. Суслова, Л.М.
author_facet	Іваненко, П.А. Дорошенко, А.Ю. Овдій, О.М. Суслова, Л.М.
author_sort	Іваненко, П.А.
title	Автотьюнер та візуалізація для задачі метеорологічного прогнозування
title_short	Автотьюнер та візуалізація для задачі метеорологічного прогнозування
title_full	Автотьюнер та візуалізація для задачі метеорологічного прогнозування
title_fullStr	Автотьюнер та візуалізація для задачі метеорологічного прогнозування
title_full_unstemmed	Автотьюнер та візуалізація для задачі метеорологічного прогнозування
title_sort	автотьюнер та візуалізація для задачі метеорологічного прогнозування
publisher	Інститут програмних систем НАН України
publishDate	2013
topic_facet	Прикладні засоби програмування та програмне забезпечення
url	http://dspace.nbuv.gov.ua/handle/123456789/86694
citation_txt	Автотьюнер та візуалізація для задачі метеорологічного прогнозування / П.А. Іваненко, А.Ю. Дорошенко, О.М. Овдій, Л.М. Суслова // Проблеми програмування. — 2013. — № 4. — С. 64-73. — Бібліогр.: 11 назв. — рос.
series	Проблеми програмування
work_keys_str_mv	AT ívanenkopa avtotʹûnertavízualízacíâdlâzadačímeteorologíčnogoprognozuvannâ AT dorošenkoaû avtotʹûnertavízualízacíâdlâzadačímeteorologíčnogoprognozuvannâ AT ovdíjom avtotʹûnertavízualízacíâdlâzadačímeteorologíčnogoprognozuvannâ AT suslovalm avtotʹûnertavízualízacíâdlâzadačímeteorologíčnogoprognozuvannâ
first_indexed	2025-07-06T14:14:01Z
last_indexed	2025-07-06T14:14:01Z
_version_	1836907226887880704
fulltext	Прикладні засоби програмування та програмне забезпечення © П.А. Іваненко, А.Ю. Дорошенко, О.М. Овдій, Л.М. Суслова, 2013 64 ISSN 1727-4907. Проблеми програмування. 2013. № 4 УДК 681.5. П.А. Іваненко, А.Ю. Дорошенко, О.М. Овдій, Л.М. Суслова АВТОТЬЮНЕР ТА ВІЗУАЛІЗАЦІЯ ДЛЯ ЗАДАЧІ МЕТЕОРОЛОГІЧНОГО ПРОГНОЗУВАННЯ Розглядається застосування техніки автотьюнінгу та розширення картографічного інструментарію Google Maps для комплексного розв’язання задачі короткотермінового моделювання циркуляції атмос- фери. Наводяться чисельні показники швидкодії розробленого паралельного алгоритму. Вступ Задача метеорологічного прогнозу- вання є типовим прикладом складної при- кладної обчислювальної задачі з високими вимогами до точності отриманих результа- тів та жорсткими часовими обмеженнями. Підвищення очікуваної межі точності розв’язку значно збільшує обсяг викону- ваних обчислень, що неухильно примно- жує часові витрати на розв’язання задачі тому оптимальний алгоритм вимагає від- шукання компромісу. Дана робота розглядає паралельну реалізацію моделі короткотермінового прогнозу метеорологічних умов, процес її оптимізації з використанням методології автотьюнінгу [1], а також візуалізацію ре- зультатів обчислень за допомогою картог- рафічного інструментарію Google Maps з використанням оригінального алгоритму побудови ізоліній. Робота продовжує дос- лідження, представлені у [2–4] й, зокрема, демонструє ефективність застосування розглянутих підходів для комплексного вирішення складної наукової задачі. Мета роботи – створення універ- сального й оптимального з точки зору швидкодії та точності паралельного алго- ритму. Під універсальністю розуміється вимога отримання максимально високих результатів швидкодії у будь-якому обчис- лювальному середовищі. Досягнення цієї мети значно спрощує використання мето- дології автотьюнінгу. Структура роботи є наступною: пе- рший розділ містить постановку задачі й опис математичної моделі; у розділі 2 роз- глянуто процес створення паралельного алгоритму що розв’язує поставлену за- дачу; третій розділ присвячено оптимізації побудованого алгоритму за допомогою автоматизованого інструментарію [3]. У розділах 4 і 5 представлені результати проведеної оптимізації та візуалізація ре- зультатів прогнозування відповідно. 1. Постановка задачі В роботі розглядається задача ди- намічної метеорології, а саме задача моде- лювання циркуляції атмосфери. Метою є побудова максимально ефективного алго- ритму реалізації моделі короткочасного (від години до декількох днів) прогнозу стану атмосфери а також візуалізація ре- зультатів обчислень. Процеси, що описує модель, класи- фікуються як макромасштабні − їхній ха- рактерний горизонтальний розмір знахо- диться в межах від кількох сотень до кіль- кох тисяч кілометрів. Як приклад макро- масштабних рухів можна навести синоп- тичні вихорі (циклони та антициклони, улоговини та гребні), поля хмар, довгі хвилі (хвилі Росбі [5]), пасатні та мусонні течії, західне та східне перенесення тощо. Розглянемо коротко основні харак- теристики математичної моделі. Деталь- ний опис можна знайти у [6]. Рельєф суттєво впливає на процеси та явища, що мають місце в нижній части- ні атмосфери. Розглянута модель враховує вплив рельєфу шляхом переходу до нової вертикальної координати, яка неявно пов’язана із орографією земної поверхні. Неявний зв’язок має місце в наслідок вибору вертикальною координатою нор- мованого тиску: 0pp , де 0p – призе- мний тиск. Прикладні засоби програмування та програмне забезпечення 65 Модель використовує сферичну си- стему координат (рис. 1). Введемо змінні що представляють географічні координа- ти точки: довгота  , широта  та висота над рівнем моря arz  , де r – відстань від центру Землі до поточної точки, мa 610373.6  – середній радіус Землі. Рис. 1. Неінерційна система відліку, що пов’язана із географічними координатами Розглядатимемо вектор швидкості  wvuV ,, , де wvu ,, є проекціями векто- ра V у локальній прямокутній системі координат. Вісі цієї системи такі: i – на- правлена по дотичній до широтного кола із заходу на схід, вісь i – по дотичній до меридіана від екватора до полюса, ri – по місцевій вертикалі догори. Невідомими величинами в нашій моделі є: вектор шви- дкості V , абсолютна температура середо- вища T та густина  повітря. Значення тиску p вважатимемо відомими, як і по- чатково-крайові умови впродовж усього часу розв’язання задачі. Модель складається із трьох ево- люційних рівнянь конвективної дифузії (1), (2) та (3) для визначення горизонта- льних складових вітру та температури відповідно формул:             z u w u a vu a u t u cos                        u a p a 2 cos 1 cos 1                      z u z u a z     11 2   , cos 2cossin          a u wv (1)             z v w v a vv a u t v cos                     v a p a 2 cos 11                      z v z v a z     11 2 ,sin cos 2 a wv a u u           (2) де  та z – коефіцієнти горизонталь- ного та вертикального турбулентних обмі- нів.                     T adt dT 2 cos 1 . 11 2                      z T z T a z     (3) Крайові умови забезпечуються ін- терполяцією за часом вхідних метеоро- логічних даних, що вже перетворені до потрібного просторового формату. Почат- ковими умовами є або результати попе- реднього часового кроку, або початкові умови задачі. Обчислення за діагностичними рів- няннями для знаходження вертикальної компоненти вектора V для визначення вертикальної складової вітру та густини повітря (рівняння Клапейрона) прово- дяться після визначення решти невідомих метеовеличин. Поле тиску у всій просторово- часовій області визначення задачі вважа- ється відомим. Для цього здійснюється часова інтерполяція метеоданих тиску. Для постановки початкових та крайових умов моделі використовувався електронний архів даних об’єктивного аналізу полів метеовеличин, що отрима- ний із регіонального центру прогнозу- вання погоди „Офенбах”. Формат цих ме- теорологічних даних є наступним: Прикладні засоби програмування та програмне забезпечення 66  вертикальна координата – тиск;  вертикальна протяжність від 1000 до 50 гПа;  просторова область 0° – 90° пвн. ш. та 0° – 90° сх. д.;  просторова дискретність 1.5° (за широтою та довготою);  часова дискретність 12 годин. 2. Паралельний алгоритм В межах цієї роботи розглядається спрощена двовимірна задача з обрахуван- ням тільки швидкості та напрямку вітру. Практично спрощена програма дозволяє отримати прогноз для одного горизонталь- ного рівня повної тривимірної моделі. Модель розпаралелюється на трьох рівнях – за еволюційними рівняннями, на рівні даних (геометричний паралелізм) та за допомогою модифікованого адитивно- усередненого методу розщеплення (далі МАУМ) [6–8]. Паралелізм за рівняннями. Роз- глянута модель дає можливість розв’язу- вати рівняння (1) та (2) незалежно. За ра- хунок цього так званого «високорівневого паралелізму» обмін результатами розв’яз- ків рівнянь виконується через вхідні данні на кожній ітерації (алгоритм є ітератив- ним). Метод розщеплення. Як вже було сказано раніше – загальна схема виконува- них обрахунків є ітеративною. Вхідні дан- ні задають стан атмосфери на момент часу 0t . Для отримання прогнозу на деякий мо- мент 0tT  часовий відрізок розбивається на n порівняно коротких відрізків протя- жністю t . Кожної ітерація обчислює стан атмосфери через час t і її вихідні дані стають вхідними (початковими) да- ними для наступної ітерації (рис. 2). Рис. 2. Ітеративна схема обчислень Збільшення кроку t призводить до зменшення кількості ітерацій а тому й загального обсягу обчислень, проте приз- водить до збільшення похибки прогнозу тому рекомендується при обрахунках оби- рати часовий крок у декілька десятків се- кунд. В межах кожної ітерації незалежно розв’язуються рівняння за кожним з коор- динатних напрямків після чого виконуєть- ся збір і обробка результатів, що вимагає синхронізації. Використання МАУМ до- зволяє поєднати декілька ітерації (позна- чимо їх кількість m ) в одну. В результаті збір та усереднення результатів викону- ється тільки в кінці такої «склейки», що зменшує часові затрати на синхронізацію обчислень. Слід зауважити, що збільшення значення параметра m також призводить до втрати точності розв’язку й рекомендо- ваний діапазон значень є ]10..1[m [6]. Оскільки для розв’язання рівнянь (1) – (3) використовується однаковий чи- сельний метод, то часові витрати у кожній гілці на протязі всього m -циклу є одна- кові, що дає можливість оптимально роз- поділити обчислення для паралельних обчислювачів з гомогенною архітекту- рою. Геометричний паралелізм. Окрім незалежного розв’язання кожного з рів- нянь моделі є можливість геометричної декомпозиції області обчислень за кож- ним координатним напрямком. Позначимо S кількість підоблас- тей. Тоді для проекції вектора швидкості u (1) у двовимірному варіанті задачі схе- ма обчислення для одного m -циклу буде виглядати наступним чином (рис. 3): Рис. 3. Схема розв’язання одного еволю- ційного рівняння протягом m -циклу Прикладні засоби програмування та програмне забезпечення 67 Як видно з діаграми, для кожного рівняння моделі декомпозиція області об- числень дозволяє створити S2 незалеж- них між собою підзадач. Програмна реалізація алгоритму метеопрогнозування виконана засобами Java. Вона розрахована на виконання на обчислювачі з моделлю спільної пам’яті й використовує засоби пакету Java concurrent для організації паралельних обчислень. Кожна підзадача виконується в окремо- му потоці. Кількість використовуваних по- токів є фіксованою. 3. Оптимізація розробленого алгоритму В попередньому розділі описана трирівнева схема виконуваних паралель- них обчислень. Розглянемо параметри, що впливають на загальну ефективність пара- лельної програми. Більшість паралельних алгоритмів, орієнтованих на геометричний паралелізм мають наступну схему розподілу часу об- числень (рис. 4): Рис. 4. Типовий розподіл часових витрат для геометричного паралелізму splitt та merget – час, затрачений на розпо- діл вхідних даних та поєднання резуль- татів відповідно. Протягом цих часових відрізків зазвичай виконується синхроні- зована секція, під час якої більша части- на обчислювальних ресурсів простоює. Під splitt розуміється час «чисто парале- льних» обчислень. Очевидним є те, що для досягнення максимальної ефектив- ності алгоритму необхідно мінімізувати час 0 mergesplit tt . Рис. 4 описує часові затрати для однієї ітерації обчислень нашого алго- ритму. Як вже зазначалось в попередньо- му розділі, застосування МАУМ дозволяє виконувати розподіл і збір результатів обчислень один раз на m ітерацій, що безумовно підвищує загальну ефектив- ність алгоритму за рахунок незначного збільшення похибки результату (за умо- ви утримання значення параметра m у рекомендованих межах). Параметр S геометричної деком- позиції впливає на обсяг обчислень в межах кожної підзадачі. Чим менше йо- го значення – тим крупніший «блок да- них» й довше паралельна секція, тобто parallelt merge splitt t . Якщо архітектура обчислювального середовища (далі ОС) є гомогенною, то природнім є прагнення підібрати таке значення S , при якому загальна кількість підобластей буде рівна кількості незалежних обчислювачів (процесорів/ядер) ОС. Нехай наше ОС здатне обрахову- вати одночасно N підзадач. Зважаючи на те, що розглянуте спрощення моделі складається з двох еволюційних рівнянь й обраховується прогноз для двовимір- ного простору, при значенні 4 N S  кіль- кість під задач буде достатньою щоб повністю завантажити всі наявні обчис- лювальні ресурси й розмір підзадач буде максимальним («крупнозерниста» деком- позиція). З іншого боку далеко не завжди 4N . В цьому випадку варто обрати 4NdivS  . Як відомо, швидкість доступу до даних процесорного кешу значно швид- ша за швидкість зчитування їх з операти- вної пам’яті. Як вже було вказано в пер- шому розділі – обрана модель характе- ризується невисоким обсягом вхідних даних. Тому теоретично існує таке зна- чення S , при якому всі дані підзадачі по- вністю помістяться в кеш процесора й на протязі всього m -циклу взаємодія з порів- няно повільною оперативною пам'яттю буде мінімальною. Підбір такого значен- ня S є нетривіальним, оскільки його ве- личина залежить не тільки від обсягу а й від стратегії роботи з кешем. Ці дві хара- ктеристики не завжди є відомими й, зва- жаючи на різноманіття архітектури су- Прикладні засоби програмування та програмне забезпечення 68 часних процесорів, сильно різняться для різних ОС. Також їх врахування усклад- нює структуру програми, а мануальний підбір емпіричним методом може зайня- ти багато часу. Оперування простим параметром S дозволяє значно спростити паралельний алгоритм за рахунок його абстрагування від характеристик архітектури ОС. Для підбору оптимального значення S скорис- таємося системою TuningGenie [3], яка є програмною реалізацією методології ав- тотьюнінга, який спирається на емпіричну оцінку різних варіантів оптимізовуваної програми. Його загальна схема є наступ- ною (рис. 5). Рис. 5. Типова схема автотьюнінга Система TuningGenie автоматично генерує автотьюнер для оптимізовуваної програми з використанням метаданих у вихідному коді. Практично достатньо ви- конати дві модифікації:  розмістити коментар над внут- рішньою змінною програми в якому зада- ються межі пошуку оптимального значен- ня, наприклад: //tuneAbleParam name=numSubTasks //start=1 stop=10 step=2 int numSubTasks = 1;  написати клас-обгортку, який буде запускати головну програму й давати якісну оцінку ефективності виконуваних нею обчислень (в нашому випадку вона залежить від часових витрати). TuningGenie в автоматизованому режимі емпірично підбере оптимальне значення S в заданих розробником ме- жах (в прикладі [1,10]snumSubTask  ). Знайдене значення S – оптимальне для всіх вхідних даних однакової розмірнос- ті доки архітектура ОС буде незмінною. Використання експертних знань ро- зробника суттєво звужує область пошуку оптимальної конфігурації а також звіль- няє систему автотьюнінга від необхіднос- ті аналізу й моделювання обчислень опти- мізовуваної програми. 4. Результати експерименту Дана робота не виконує досліджен- ня адекватності отриманого чисельного розв’язку щодо реальної метеорологічної ситуації. Акцент зроблено на кількісні по- казники швидкодії програмної реалізації за умови збереження точності розв’язку а також на застосуванні розробленого авто- матизованого інструментарію для оптимі- зації паралельного алгоритму та візуаліза- ції розв’язків. Експеримент виконувався у середовищі з наступними характеристи- ками (таблиця). Таблиця. Характеристики експеримента- льного середовища Операційна система: Scientific Linux 5 Тип системи 64-бітна ОС Процесори 2хIntel® Xeon® Processor E5405 Quad Core Кількість ядер процессора 4 Обсяг L2-кеша 12 Mb Обсяг оперативної пам’яті 16 Gb Для проведення експерименту вхід- ні дані інтерпольовані на більш густу сітку розмірністю 600х600. Часовий крок було обрано рівним 10 секундам. Наступ- ний графік зображує залежність часових затрат на обрахування прогнозу на 24 го- дини від значення параметра S – кількості підобластей геометричної декомпозиції (рис. 6). Прикладні засоби програмування та програмне забезпечення 69 Рис. 6. Результати чисельного експерименту Значення параметра МАУП покла- дено 10m . Варто зауважити що для пошуку оптимального значення параметра S не виконувалися повне обчислення про- гнозу на добу вперед. Для досягнення стабільних результатів замірів достатньо виконати декілька десятків ітерацій m - циклу, що скоротило загальний час авто- тьюнінгу до декількох годин. Як видно з рис. 6, оптимальна для тестового ОС величина 2S , що є цілком логічним, оскільки при такому значенні обчислення кожної ітерації розбиваються на 8 підзадач, що дорівнює загальній кіль- кості процесорів. За такої конфігурації програма показала мультипроцесорне прискорення 82.3)8( W й ефективність %75.47)8( E . Раніше висунуте припу- щення щодо можливого над-прискорення при розбитті на підзадачі невеликої розмі- рності для тестового ОС експериментально не підтвердилося. 5. Візуалізація результатів обчислень Для картографічного представлен- ня метеорологічних даних прогнозу за напрямком та силою вітру використано сервіс Google Maps [9], який на даний момент є найпоширенішим геосервісом у світі. Ця потужна платформа надає різноманітну функціональність та зручне API. Зокрема для реалізації використано Google Maps JavaScript API v3 [10] та скриптову мову програмування PHP: Hypertext Preprocessor. Реалізовано три представлення ме- теорологічних даних за напрямком та си- лою вітру:  за допомогою векторів вітру (рис. 7);  за допомогою ізоліній сили вітру (ізотах) (рис. 8);  за допомогою ізообластей сили вітру (рис. 9). Рис. 7. Картографічне представлення векторів вітру Прикладні засоби програмування та програмне забезпечення 70 Рис. 8. Картографічне представлення ізоліній сили вітру Рис. 9. Картографічне представлення ізообластей вітру Ці представлення можуть відобра- жатися як окремо так і одночасно. Для побудови ізоліній використано алгоритм Conrec [11], що є одним з най- більш популярних алгоритмів для обчис- лення контурних ліній. Поряд з тим був застосований власноруч розроблений алгоритм для Прикладні засоби програмування та програмне забезпечення 71 побудови ізоліній. Далі наведений опис даного алгоритму. Алгоритм побудови ізоліній. Вхі- дними даними для алгоритму є прямо- кутна таблиця розмірами MyMx зна- чень деякого параметра z , у даному випа- дку сили вітру. Представимо її як функ- цію ),( yxz , що визначена на прямокут- ній області ]1,0[]1,0[  yx MM , тоб- то jizjiz ,),(  , 1,...,0  xMi , ,...0j .1..., yM Множина точок ),( ji , ,...0i 1..., xM , 1,...,0  yMj , визначає на  сітку K з вузлами в цих точках. Ребрами сітки K назвемо відрізки, що поєднують вузли сітки. Коміркою сітки K назвемо сукупність кожних чотирьох сусідніх вуз- лів ),1(),1,1(),1,(),,( jijijiji  , які утворюють квадрат. Нехай тепер потрібно побудувати на  лінію рівня деякого значення Z фу- нкції ),( yxz . Визначимо сітку K структурою, що описує її як масив комірок (рис. 10), роз- мірністю ]2,0[]2,0[  yx MM , елемент якого включатиме у себе: координати ко- жної вершини комірки, значення парамет- ра в кожній із них та індикатор, що вказує чи проходить крізь дану комірку лінія шу- каного рівня. 1 2 34 1 0 3 2 k-1, l k, l k+1, l k, l+1 k, l-1 Рис. 10. Комірка, її складові та сусіди, що мають спільні ребра Для кожної комірки сітки необхідно визначити, чи перетинається вона шука- ною ізолінією, для цього порівнюються значення у вузлах, що є вершинами комір- ки, і з’єднуються ребром. Якщо значення у одному з вузлів виявилось більше Z , а у іншому – менше, то це значить, що лінія рівня перетинає це ребро. Комірка поміча- ється, якщо лінія рівня перетинає хоча б одне з її ребер. Якщо значення одного з вузлів реб- ра збігається із Z , то цю ситуацію можна вирішити наступним чином. Введемо по- няття початку та кінця ребра. Початком ребра вважатимемо той вузол, сума коор- динат якого менша. Тепер будемо вважати, що лінія перетинає ребро, якщо збігається із Z значення на початку ребра. Наступним етапом є розрахунок ко- ординат точки перетину та поєднання то- чок у послідовності. Опишемо алгоритм побудови послідовностей. Крок 1. Послідовно переглядаючи комірки сітки знаходиться комірка, що перетинається лінією шуканого рівня. Пе- ревіряється чи належить знайдена комір- ка до масиву вже пройдених для лінії шуканого рівня. Вибирається напрямок обходу ребер і згідно напрямку здійсню- ється пошук будь-якого ребра, що нале- жить до комірки і перетинається із ліні- єю шуканого рівня. Розраховуються ко- ординати точки перетину і дана точка іні- ціює послідовність керуючих точок. Ко- ординати точки перетину визначаються за допомогою інтерполяції функції ),( yxz вздовж ребра. Крок 2. Згідно із напрямком обхо- ду, розглядаються сусідні із поточною комірки на рахунок того, чи перетина- ються вони ізолінією. В залежності від місця положення наступної комірки від- носно поточної, можна сказати яке реб- ро поточної комірки перетне ізолінія да- лі. Розраховуються координати наступної точки і заносяться до масиву послідовно- сті керуючих точок. Пройдені комірки також заносяться до масиву. Комірка, що була знайдена як наступна оголошується поточною. Прикладні засоби програмування та програмне забезпечення 72 Крок 3. Якщо є сусідні комірки із помітками і поточна комірка не належить до масиву пройдених, то процедура по- шуку наступної точки (крок 2) визива- ється рекурсивно для даної комірки. Як- що немає сусідніх комірок із перетина- ми але залишились непройдені комірки перевіряємо чи є остання знайдена комір- ка сусідньою із першою, якщо так – пос- лідовність оголошується замкненою, як- що ні – незамкненою (рис. 11). Переходи- мо до кроку 1. Якщо немає сусідніх комі- рок із перетинами і всі комірки перегля- нуті, вважається, що ізолінію відслідко- вано повністю. Для згладжування форми ізоліній використовується кубічна крива Безьє. f(x, y) = Z1 f(x, y) = Z2 Рис. 11. Замкнена і незамкнена лінії та ко- мірки, які вони перетинають. Відповідні послідовності керуючих точок Висновки Розглянуто результати застосуван- ня оптимізаційної методології автотьюнін- гу до складної наукової задачі. Завдяки розробленому інструментарію значно спрощено і майже повністю автоматизо- вано етап оптимізації розробленого алго- ритму у цільовому обчислювальному сере- довищі. Досягнутий показник ефекти- вності алгоритму %75.47)8( E можна вважати задовільними, зважаючи на необ- хідність частої синхронізації проміжних результатів обчислень, що зумовлена хара- ктером математичної моделі. Загалом, ро- бота демонструє гнучкість автотьюнінгу й розробленого інструментарію Tuning- Genie, зокрема. Для візуалізації прогностичних да- них моделі розроблено розширення карто- графічного інструментарію Google Maps, а саме алгоритм генерації ізоліній. Дана робота розглядає повний цикл розробки програмного забезпечення для вирішення важливої наукової задачі, який вийшло значно спростити за допомогою продемонстрованих інструментальних за- собів. 1. Naono K., Teranishi K., Cavazos J., Suda R. Software Automatic Tuning From Concepts to State-of-the-Art Results, Springer; 1st edition, September 21, 2010. 2. Іваненко П.А., Дорошенко А.Ю. Засоби створення систем автоматичного настрою- вання для ефективного виконання прикла- дних паралельних програм // Інформаційні технології в освіті. – 2013. – № 14. – С. 17–21. 3. Ivanenko P. TuningGenie – an autotuning framework for optimization of parallel applications // Theoretical and Applied Aspects of Cybernetics. Proceedings of the 2nd International Scientific Conference of Students and Young Scientists. – Kyiv: Bukrek, 2012. – P. 27–30. 4. Іваненко П.А., Дорошенко А.Ю. Автомати- чна оптимізація виконання для задачі ме- теорологічного прогнозування // Проблеми програмування. – 2012. – № 2–3. – С. 426–434. 5. Атмосфера: справочник / [научн. редкол.: Ю.С. Седунов и др.] – Л.: Гидрометеоиз- дат, 1991. – 601 с. 6. Черниш Р.І. Модифіковане адитивно- усереднене розщеплення, його паралельна реалізація та застосування до задач метео- рології, дис. канд. техн. наук, Київський Національний університет імені Тараса Шевченка, Київ, 2010 р. 7. Прусов В.А., Дорошенко А.Е., Черныш Р.И. Выбор параметра модифицированного ад- дитивно-усредненного метода // Киберне- тика и системный анализ. – 2009. – № 4. – С. 98–105. Прикладні засоби програмування та програмне забезпечення 73 8. Прусов В.А., Дорошенко А.Е., Черныш Р.И. Метод численного решения многомерной задачи конвективной диффузии // Кибер- нетика и системный анализ. – 2009. – № 1. – С. 100–107. 9. http://maps.google.com/ електронний ре- сурс. 10. http://developers.google.com/maps/document ation/javascript/ електронний ресурс. 11. http://paulbourke.net/papers/conrec/ елект- ронний ресурс. Одержано 12.09.2013 Про авторів: Іваненко Павло Андрійович, молодший науковий співробітник, Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідуючий відділом теорії комп’ютерних обчислень, Овдій Ольга Михайлівна, молодший науковий співробітник, Суслова Лідія Миколаївна, аспірантка. Місце роботи авторів: Інститут програмних систем НАН України 03680, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 1538. E-mail: paiv@ukr.net, dor@isofts.kiev.ua, olga.ovdiy@gmail.com, 2cls87@gmail.com https://maps.google.com/ http://developers.google.com/maps/documentation/javascript/ http://developers.google.com/maps/documentation/javascript/ http://paulbourke.net/papers/conrec/ mailto:paiv@ukr.net mailto:dor@isofts.kiev.ua mailto:olga.ovdiy@gmail.com mailto:2cls87@gmail.com

Автотьюнер та візуалізація для задачі метеорологічного прогнозування

Institution

Ähnliche Einträge