Л О Губачева, В Е Глущенко, Ю В Глущенко - Классификация на основе слабостохастического ранжирования - страница 1

Страницы:
1 

ranking and when in particular = I, every minimum chi-square ranking minimizes the violations of observed outcomes. Moreover, the branch and bound algorithm can be used for estimating the mint-mum chi-square rankings.

Lite ratu re

1. Глущенко В.Е., Глущенко Ю.В. Концептуальные вопросы построения интеллектуальных систем защиты от несанкционированного доступа. // ВістникСхідноукраїнського національного університету ім. Володимира Даля. - 2006. - № 5 [111] - с.48-53.

2. DeCani J.S. A branch and bound algorithm for maximum paired comparison ranking. Biomelrika 1972. № 59, pp. 131-135.

3. Thompson W.A. and Remage R. Rankings from paired comparisons. Ann. Math. Statist. 1984, .№35, pp. 739-747.

Надійшла в редколегію 21.06.2011

Рецензент: Губачева Л.О. проф., д.т.н., декан факультету комп'ютерних наук і технологій Східноукраїнського національного університета ім. В. Даля.

Глущенко В.Е., Глущенко Ю.В.

КЛАССИФИКАЦИЯ НА ОСНОВЕ СЛАБОСТОХАСТИЧЕСКОГО РАНЖИРОВАНИЯ

В статье рассматривается свойства слабостохастического chi-ранжирования и алгоритм классификации образов на их основе.

Глущенко В.Е., Глущенко Ю.В

КЛАСИФІКАЦІЯ НА ОСНОВІ СЛАБОСТОХАСТИЧНОГО РАНЖИРУВАННЯ

У статті розглядається властивості слабостохастичного chi-ранжирування і алгоритм класифікації образів на їх основі.

***

УДК 519.6

Дегтярьова Л.М., Гудино О.Є., Собко М.Ю.

Східноукраїнський національний університет ім. В. Даля, м. Луганськ

ПРИСКОРЕННЯ ОБЧИСЛЕННЯ ДИСКРЕТНИХ ПЕРЕТВОРЕНЬ ФУР'Є ЗА РАХУНОК РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ

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

Постановка проблеми

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

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

Мета статті

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

Основна частина

Фур'є аналіз на сьогоднішній день, без сумніву є найпоширенішим інструментом аналізу, який застосовується в усіх галузях науки і техніки. Подвійну спіраль ДНК, цикли сонячної активності і складні електронні сигнали математично можна представити у вигляді ряду хвилеподібних кривих. Ця ідея лежить в основі потужного аналітичного інструменту, назва якого - перетворення Фур'є. Слід зазначити, що до появи комп'ютерів дискретне перетворення Фур'є використовувалося рідко, оскільки обчислення з використанням цього інструментарію, яке складається з 32 відліків вимагає 1024 операції комплексного множення і додавання, що в ручному режимі призводить до досить довго розрахунку.

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

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

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

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

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

Дискретне перетворення Фур'є широко застосовується при аналізі дискретних

Вісник Східноукраїнського національного університету ім. В. Даля, №7 (161), 2011, Ч. 1. 267сигналів для виділення з них основний інформаційної частини. Подібна обробка необхідна для процесів стиснення і відновлення інформації при передачі аудіо-та відео-сигналів на великі відстані, а також при аналізі томографічної інформації тощо, тобто там де потрібно застосовувати швидкі методи її обробки, зважаючи на надзвичайно великий обсяг подібної інформації. Основна ідея для використання дискретного перетворення Фур'є - в одноразовій обробці однакових виразів, які часто зустрічаються в перетворенні; ця ідея реалізується відповідної угрупованням висловів та правильної послідовності їх обчислення. Саме цей метод допускає ефективне розпаралелювання, а, отже, - ефективну реалізацію на паралельних обчислювальних системах.

Розглянемо звичайний процес Анализа спектра сигналузадопомогою швидкого перетворення Фур'є.

Алгоритм Cooley - Tukey розбиває вхідну послідовність точок на дві рівні підмножини (розмір вхідних даних повинен бути ступенем двійки). Кожне з підмножин знову ділиться на 2 частини і т.д. Над кожним з отриманих множин виконується швидке перетворення Фур'є. Обчислення можна виконувати незалежно, цей факт використаний при реалізації паралельної версії.

Рис. 1 - стандартна реалізація швидкого перетворення Фур'є із 16 точками

Алгоритм Cooley - Tukey складається із двох етапів:

1. Перетворення вхідного масиву даних ( біт-реверсування ).

2. Обчислення швидкого перетворення Фур'є.

На Рис.1 приведена стандартна реалізація швидкого перетворення Фур'є із 16 точками з алгоритмом по основі 2, після того як вхідний потік був побитно реверсований.Таким чином, ми можемо розбити швидке перетворення Фур'є, як мінімум, на чотири паралельні процеси.

Рис. 1 підтверджує, що це може бути зробленеоб'єднанням у блоки по чотири точки:

1 блок + {x(0),x(8),x(4),x(12)} 3 блок + {x(1),x(9),x(5),x(13)}

2 блок + {x(2),x(10), x(6),x(14)} 4 блок + {x(3),x(11),x(7),x(15)}

Ці групи не мають взаємних залежностей і обробляються паралельно на перших двох етапах швидкого перетворення Фур'є.

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

1 блок + {x(0), x(2), x(1), x(3)}

2 блок + {x(8), x(10), x(9), x(11)}

3 блок + {x(4), x(6), x(5), x(7)}

4 блок + {x(12), x(14), x(13), x(15)}

Для показового відображення часу роботи алгоритму в паралельному й послідовному режимах була проведена реалізація алгоритму в середовищі MS Visual Studio 2010 на мовах С\С++ з використанням бібліотеки MPI, інтерфейс для відображення результатів реалізрваний на мові С# (Рис.2).Були проведені дослідження з розрахунками швидкого перетворення Фур'є для псевдовипадкової послідовності комплексних чисел вказанної розмірності та для матриці спектрального відображдення wav-файлу. Трансляція wav-файлу була реалізована у середовищі Matlab 7.5 на мові Matlab

Розрахунки

Порівняємо час роботи послідовного й паралельного способів обчислень псевдовипадкової послідовності розмірністю 4096 елементів.Середній час роботи після п'яти запусків: 0.021 секунда для послідовного й 0.012 секунда для паралельного (2 процесора) способу.Тобто отримуємо майже 50% прискорення розрахунків. При подальшому збільшенні кількості процесорів спостерігаємо таку картину: 3 - 0.01с, 4 -0.008с, 5 - 0.007с, 6 - 0.007с, 7 - 0.007с. Для заданої кількості комплексних чисел продуктивність паралельного алгоритму найбільш висока при 5 процесорах, подальше збільшення потужностей відчутного результат не приносить.

Продемонструємо більш практичне застосування алгоритмів. Застосуємо швидкого перетворення Фур'є до матриці спектру wav-файлу, що містить 131072 елемента.Час роботи: 0.899 секунди (Рис.3) для послідовного й 0.512 секунди (Рис.3) для паралельного (2 процесора) способу.

Вісник Східноукраїнського національного університету ім. В. Даля, №7 (161), 2011, Ч. 1.

Рис.3 - Робота послідовного алгоритму

Рис.4 - Робота параллельного алгоритму

При подальшому збільшенні кількості процесорів спостерігаємо таку картину:

3 - 0.39 сек., 4 - 0.303 сек., 5 - 0.273 сек., 6 - 0.244 сек., 7 - 0.233 сек., 8 - 0.207 сек.,

9 - 0.201 сек, 10 - 0.2 сек.

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

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

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

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

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

270      Висновки

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

Література

1. Преобразование Фурье Рональд Н. Брейсуэлл // В мире науки - № 8 август 1989. -С. 48-56

2. Воєводин В.В, Воеводин Вл. В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

3. Говидараю Н.К. Высокопроизводительные дискретные преобразования Фурье на графических процесорах. // Говидараю Н.К., Ллойд Б., Доценко Ю., Смит Б., Манферделли Д. -http://download.microsoft.com/download

4. Афонский А. А., Дьяконов В. П. Цифровые анализаторы спектра, сигналов и логики. Под ред. проф. В. П. Дьяконова. М: СОЛОН-Пресс, 2009. — С. 248.

5. Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток. - М.: Издательство «Радио и связь», 1985. - 248 с.

6. Залманзон Л.А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. - М.:Наука, 1989. - 496 с.

7. Сергиенко А. Б. Цифровая обработка сигналов. — 2-е. — Спб: Питер, 2006. — С. 751.

Надійшла в редколегію 23.08.2011 Дегтярьова Л.Н., Гудино О.Е., Собко М.Ю.

УСКОРЕНИЕ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ     ЗА     СЧЕТ     РАСПАРАЛЛЕЛИВАНИЯ ВЫЧИСЛЕНИЙ

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

Degtyareva L.N., Houdino O.E., Sobko M.Y.

ACCELERATION OF COMPUTING THE DISCRETE FOURIER TRANSFORM BY PARALLELIZATION

This paper describes the possibility of accelerating the design process using the discrete Fourier transform. We propose a software implementation of performance analysis of parallel computations over the sequential execution of calculations. The basic advantage of parallel computing process using the discrete Fourier transform.

***

Вісник Східноукраїнського національного університету ім. В. Даля, №7 (161), 2011, Ч. 1.

Страницы:
1 


Похожие статьи

Л О Губачева, В Е Глущенко, Ю В Глущенко - Классификация на основе слабостохастического ранжирования