Нейромережна організація сортування масивів даних

Размещено на http://www.allbest.ru/

ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

УДК 681.325.5

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

НЕЙРОМЕРЕЖНА ОРГАНІЗАЦІЯ СОРТУВАННЯ МАСИВІВ ДАНИХ

Мохамед Салем Нассер Мохамед

Вінниця - 2009



Дисертацією є рукопис.

Робота виконана у Вінницькому національному технічному університеті Міністерства освіти і науки України

Науковий керівник: кандидат технічних наук, доцент Мартинюк Тетяна Борисівна, Вінницький національний технічний університет, доцент кафедри лазерної та оптоелектронної техніки

Офіційні опоненти: доктор технічних наук, професор Крилов Віктор Миколайович, Одеський національний політехнiчний університет, професор кафедри прикладної математики та інформаційних технологій в бізнесі

доктор технічних наук, професор Пєтух Анатолiй Михайлович, Вiнницкий нацiональний технiчний унiверситет, завiдувач кафедри програмного забезпечення

Захист відбудеться “ 19” 06 2009 р. О 1230 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95, ауд. 210, ГУК.

З дисертацією можна ознайомитись у бібліотеці Вінницького національного технічного університету за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

Автореферат розісланий “ 18 ” 05 2009 р.

Вчений секретар спеціалізованої вченої ради С.М. Захарченко



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Показником обчислювальної ефективності оптимізованих варіантів сортування, які використовуються в сортувальних мережах, є, в першу чергу, їх часові витрати. Відомо, що обчислювальна трудомісткість процедури впорядковування є достатньо високою і знаходиться в межах від О(n) до О(n2), де n - розмірність числового масиву. При цьому ефективними вважаються алгоритми зі збіжністю процесу сортування порядку О(n·log2n). Тому природним є прагнення досягти збіжності процесу сортування порядку О(n), що можливе при високому рівні паралелізму обробки, досяжному на сортувальних мережах.

Крім того, для аналізу й удосконалення відомих способів сортування з метою їх ефективної реалізації доцільно представляти їх у компактній і формалізованій формі, що може забезпечити використання базису систем алгоритмічних алгебр (САА) В.М. Глушкова для опису і моделювання алгоритмів сортування.

Значний внесок у розвиток наукового напряму, пов'язаного з розробкою і дослідженням методів і засобів асоціативної обробки даних і, зокрема, сортування масивів даних, а також способів їх універсального опису і математичного моделювання зробили такі вчені, як Д.Е. Кнут (Donald E. Knuth), Г. Лорин (Harold Lorin), Т. Кохонен (Teuvo Kohonen), К. Дж. Тербер (K.J. Thurber), К. Фостер (К. Foster), В.М. Глушков, Є.Л. Ющенко, М.М. Амосов, Г.Е. Цейтлін, Е.М. Куссуль, В.П. Кожем'яко та інші.

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

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційне дослідження проводилося відповідно до плану наукових досліджень Вінницького національного технічного університету і Міністерства освіти і науки України по держбюджетній темі 57-Д-300 “Оптико-електроннi паралельнi логiко-часовi iнформацiйно-енергетичнi середовища на базi образних комп'ютерiв ” (№ держ. реєстрації 0108U000662).

Мета і завдання дослідження

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

Об'єкт дослідження- процес сортування масивів даних.

Предмет дослідження- структурна організація сортувальної нейромережі.

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

Для досягнення поставленої мети необхідно виконати такі основні завдання: нейромережа сортувальний інформація числовий

1. Проаналізувати відомі методи сортування масивів даних і дослідити можливості апаратної реалізації алгоритмів сортування з використанням асоціативних запам'ятовувальних пристроїв (АЗП).

2. Розробити і дослідити моделі сортування методом попарного обміну у вигляді сортувальних мереж.

3. Розробити і дослідити сортувальну нейромережу для паралельного сортування масивів даних.

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

5. Виконати комп'ютерне моделювання процесу сортування попарним обміном з можливістю наочного відображення його основних параметрів.

6. Розрахувати і проаналізувати параметри сортувальної нейромережі при реалізації її базових вузлів на оптоелектронній елементній базі.

Наукова новизна отриманих результатів

1. Вперше розроблено моделі у вигляді сортувальної мережі для методу попарного обміну з введенням нових зв'язків між крайніми елементами масиву (у вигляді “кільця”) в парних або непарних циклах сортування. Це дозволяє перейти від процедури сортування з лінійною організацією масиву сортованих чисел до процесу сортування шляхом повного попарного аналізу масиву чисел з кільцевою організацією, що, в свою чергу, дозволяє апаратно реалізувати сортувальну нейромережу і забезпечити максимально можливий рівень паралельної обробки К=m/2, де m- розмірність масиву чисел.

2. Вперше запропоновано і досліджено представлення в модифікованій системі алгоритмічних алгебр (САА-М) В.М. Глушкова сортування масиву даних у вигляді “кільця”, що дозволяє формалізувати подання і забезпечити аналіз і вибір оптимального варіанта сортування для реалізації на сортувальній нейромережі, що дає можливість, у свою чергу, прискорити процес впорядкованої вибірки в найнесприятливішому випадку на відміну від сортування у вигляді “стрічки ” як мінімум на один цикл, а в порівнянні з класичним варіантом сортування як мінімум на два цикли.

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

Практичне значення отриманих результатів

1. Запропоновано і досліджено варіант реалізації сортувальної нейромережі на оптоелектронній елементній базі, а саме, на матрицях смарт-пікселів, що дозволяє усунути труднощі, пов'язані з організацією великої кількості міжз'єднань в нейромережі для паралельної передачі матриці рангів розмірністю елементів. Розрахунок швидкодії сортувальної нейромережі з урахуванням швидкодії оптоелектронних і оптичних ІС для її базових блоків показав, що сортування великих масивів чисел (розмірність масиву 32-1000 слів, розмірність чисел 8-32 біт) виконується в реальному часі (мілісекундний діапазон). Це дозволяє використовувати запропонований варіант оптоелектронної сортувальної нейромережі як спецпроцесор в системах для обробки сигналів і зображень в реальному часі.

2. Розроблено програми моделювання алгоритмів сортування на мові високого рівня (C++), які дозволяють визначити кількість циклів, порівнянь і перестановок для методу попарного обміну в класичному (лінійному) варіанті і при введенні мінімального / максимального елемента в мінімальну/максимальну позицію (в кільцевому варіанті) і представити результати в наочному графічному вигляді. Це дозволяє, у свою чергу, проаналізувати і обгрунтувати вибір оптимального варіанта сортування масиву чисел будь-якої розмірності методом попарного обміну.

3. Результати роботи використано в навчальному процесі у ВНТУ при вивченні дисциплін „Нові інформаційні технології обробки, аналізу та розпізнавання зображень” і „Архітектура і структурна організація нейрокомп'ютерів”.

Впровадження результатів підтверджується відповідними актами.

Особистий внесок здобувача. Всі основні результати дисертаційної роботи отримано автором особисто. В публікаціях, написаних у співавторстві, здобувачу належить: аналіз співвідношення надлишковості і контролездатності одиничних кодів [1]; обгрунтовування вибору методу сортування у вигляді попарного обміну для реалізації на сортувальній мережі [2]; аналіз особливостей опису синхронного алгоритму сортування в базисі САА В.М. Глушкова [3,11]; порівняльний аналіз нейромереж в контексті реалізації асоціативних операцій [4]; способи представлення початкових рангів елементів вхідного векторного масиву чисел [6]; аналіз особливостей нейромережі для паралельного сортування масиву чисел [7,8,10]; аналіз особливостей базису САА В.М. Глушкова [9]; реалізація матриці рангів [12]; кодування матриці рангів-вагових коефіцієнтів у сортувальній мережі [13,14].

Апробація результатів дисертації. Основні положення і наукові результати докладалися і обговорювалися на: восьмій науково-технічній конференції „Контроль і управління в складних системах (КУСС-2005)” (Вінниця, 2005); 3-ій міжнародній науково-технічній конференції “Оптоелектронні інформаційні технології. Фотоніка ОДС-2005” (Вінниця, 2005); 7-ій міжнародній науково-практичній конференції „Современные информационные и электронные технологии” (Одеса, 2006); 13-ій міжнародній конференції з автоматичного управління „Автоматика-2006” (Вінниця, 2006); I міжнародній науково-практичній конференції „Наука и технология: шаг в будущее-2006” (Белгород, 2006); III міжнародній науково-технічній конференції „Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування (СПРТП-2007)” (Вінниця, 2007); Першій міжнародній науково-практичній конференції „Методи та засоби кодування, захисту й ущільнення інформації” (Вінниця, 2007); 2-й міжнародній конференції „Теорія та методи обробки сигналів” (Київ, 2008); щорічних науково-технічних конференціях професорсько-викладацького складу, співробітників та студентів ВНТУ ( Вінниця, 2007,2008).

Публікації. За матеріалами дисертації опубліковано 14 друкованих праць, з яких 5 статей в провідних наукових фахових виданнях, 2 статті в збірках праць, 7 тез доповідей.

Обсяг і структура дисертації. Дисертаційна робота містить вступ, чотири розділи, основні висновки, список використаних джерел, три додатки. Загальний обсяг дисертації складає 223 сторінки, з яких основний зміст викладено на 145 сторінках друкованого тексту, дисертація містить 29 рисунків, 22 таблиці. Список використаних джерел містить 120 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

В першому розділі виконано аналіз методів і засобів сортування масивів даних, розглянуто особливості методу сортування попарним обміном.

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

Виконано аналіз існуючих нейромереж, який показав, що класичні нейромережі типу мережі Хеммінга, Хопфілда, МАХNЕТ можуть виконувати найпростіші асоціативні операції, наприклад, визначати співвідношення (>, <, =) і виділяти максимальний елемент векторного масиву вхідних сигналів. При цьому відомо, що асоціативні процесори (АП) можуть виконувати ряд операцій, що відносяться до таких асоціативних операцій, як: пошук за відповідністю, пошук найближчого знизу (зверху) значення, пошук максимального (мінімального) значення, пошук величин у заданих межах, пошук на базі булєвих функцій, впорядкована вибірка (сортування ). При цьому основним блоком АП є асоціативний ЗП (АЗП), в якому вибірка даних виконується за змістом.

Розглянуто системи алгоритмічних алгебр (САА) В.М.Глушкова. Аналіз способів опису алгоритмів мультиобробки і, зокрема, алгоритмів сортування показав, що найдоцільнішим є опис синхронного алгоритму сортування і формування його апаратної реалізації надалі саме в САА В.М. Глушкова. Опис процесів в базисі САА В.М. Глушкова із застосуванням операторних представлень є не тільки наочним і формалізованим, але й універсальним.

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

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

Виконано аналіз відомої нейромережі, що реалізує алгоритм сортування на 3-D оптичному нейрочипі. Дана нейромережа складається з двох частин: навчальної і обчислювальної частини. Мережа досягає стаціонарного стану за один крок (один такт) і містить n2 компараторів, n2 фотоприймачів, n2 електронних порогових елементів, а також два тонкоплівкові електрооптичні шари з пороговими модуляційними характеристиками. Недоліком даної нейромережі є надмірні апаратні витрати порядку О(n2), які пов'язані з реалізацією табличного методу порівнянь елементів вхідного вектора, і відсутність оптичних і оптоелектронних ІС, що промислово виробляються, для даної структури нейромережі.

В другому розділі виконано розробку моделей сортувальних мереж для методу сортування попарним обміном, а також розглянуто особливості сортування попарним обміном з ранжуванням елементів масиву.

Варіанти оптимізації процесу сортування попарним обміном можна отримати за рахунок створення нових зв'язків між крайніми елементами масиву (“замикання” масиву в “кільце”) в парних або непарних циклах. Тоді утворюється додаткова пара елементів, яка складається з елементів молодшої і старшої позицій в масиві, з урахуванням введення мінімального/максимального числа у мінімальну/максимальну позицію у разі, коли розмірність масиву чисел є непарною. Це дозволяє апаратно реалізувати спеціалізований пристрій сортування з регулярною розподіленою обробкою масивів чисел у вигляді сортувальної мережі.

На рис.1 приведено одну з моделей сортувальної мережі у вигляді “кільця”, а на рис.2 показано відповідну топологію з'єднань елементів в масиві, де прийнято такі позначення: x1,х2,..,хm - вхідний масив даних; x1s,x2s,….xms - відсортований масив даних при парній його розмірності m. Сортувальна мережа (рис.1) містить m регістрів відповідної розрядності і N груп схем, в яких виконується базова операція порівняння і перекомутації (compare-exchange), де N-кількість циклів сортування ((). Кількість схем порівняння і перекомутації в кожній групі дорівнює K, де K=m/2.

В роботі виконано аналіз часових параметрів моделей сортувальних мереж залежно від розмірності m вхідного масиву чисел. Результати аналізу приведені в табл.1 для моделей сортувальної мережі для методу попарного обміну в класичному вигляді, у вигляді “стрічки” (тобто без “замикання” масиву в “кільце” з одним перевірочним циклом) і для всіх восьми варіантів сортувальної мережі у вигляді “кільця”. Часові параметри у вигляді кількості циклів сортування розглянуто для двох випадків: загального і особливого, коли елементи початкового масиву чисел розташовані

в зворотному порядку (найгірший випадок сортування). Вісім варіантів сортувальної мережі у вигляді “кільця” отримано в результаті варіювання введенням додаткового (нульового або максимального) числа в додаткову (нульову або (m+1)-у) позицію масиву чисел при його непарній розмірності.

Таким чином, для варіантів 4 і 6 вдалося добитися зниження тривалості процесу сортування на два цикли при найнесприятливішому випадку в порівнянні з організацією сортувальної мережі у вигляді “стрічки” і на три цикли в порівнянні з класичним способом сортування.

З двох вибраних моделей швидкодійної сортувальної мережі у вигляді “кільця” більш прийнятною є модель для варіанта 4, оскільки тут вводиться мінімальний (нульовий) елемент у старшу позицію масиву, що рівносильно незаповненню останнього -го регістра при непарній розмірності вхідного масиву чисел для апаратної реалізації з постійною кількістю регістрів.

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

В третьому розділі розроблено засоби нейромережного сортування на базі сортувальних мереж і досліджено моделі сортувальних мереж в базисі модифікованої системи алгоритмічних алгебр (САА-М) В.М. Глушкова.

Для опису сортувальної мережі у вигляді “кільця” при непарній розмірності масиву чисел з урахуванням введення мінімального/максимального елемента у мінімальну/максимальну позицію в базисі САА В.М.Глушкова необхідне введення складового оператора , базисного оператора , складного оператора , ряда предикатів і операції, названої декомпозицією, що дозволяє описати паралельне формування і обробку всіх K пар елементів у всіх циклах сортування.

Принцип роботи сортувальної мережі у вигляді “кільця” можна представити в базисі модифікованої САА-М В.М. Глушкова у вигляді

(1)

де враховуються особливості топології з'єднань за умови парної () або непарної () розмірності вхідного масиву даних.

При цьому для “замикання” крайніх елементів масиву необхідно застосувати складовий оператор вигляду:

, (2)

де -оператори сортування, що застосовуються відовідно для (K-1) пар і крайньої K-ої пари елементів масиву K=m/2; - зона сортування розміром , тобто сусідніх лементів масиву. Отже, складовий оператор (2) забезпечує формування всіх К пар елементів масиву і виконує паралельно сортування (порівняння і транспозицію) у всіх (K-1) парах внутрішніх елементів масиву і в парі крайніх його елементів.

Тоді для оптимізованого варіанта 4 паралельного сортування попарним обміном можна записати оператори співвідношення (1) в компактній формі:

(3)

(4)

де СТРІЧКА - складовий оператора вигляду

(5)

ФІН- оператор завершення роботи.

Представлення в термінах регулярних схем САА-М В.М.Глушкова всіх восьми варіантів сортувальної мережі у вигляді “кільця” свідчить про те, що всі вони відрізняються незначним чином. Їхня загальна частина складається зі складового циклу, що містить черговість операторів і , і складного предикат тобто за умови виконання певних предикатів для операторів і , що входять до складового циклу.

Таким чином, моделювання в базисі САА-М В.М.Глушкова сортувальної мережі у вигляді “кільця” доводить ідентичність (схожість) регулярних схем, а відповідно й апаратної реалізації всіх восьми варіантів сортування попарним обміном, оскільки відмінності стосуються тільки способу формування зв'язків у процесі сортування (рис.1,2). Отже, вибір найоптимальнішого варіанта серед них можна зробити тільки в процесі сортування контрольних вибірок (масивів чисел) для загального і особливого випадків (табл. 1).

Розроблено і досліджено сортувальну нейромережу для реалізації сортування методом попарного обміну з ранжуванням, а також наведено функціональні схеми її основних блоків. На підставі вибору самого швидкодійного варіанта сортувальної мережі (варіант 4) і з урахуванням його опису в базисі САА-М В.М. Глушкова було розроблено структуру сортувальної нейромережі (рис.3).

Особливість функціонування сортувальної нейромережі (рис.3) полягає в наступному. Перед сортуванням на інформаційні входи пам'яті рангів ПР подається матриця розмірністю яка є початковою матрицею ваг G0={g011, …, g0mm} вигляду

G , (6)

тобто всім елементам вхідного вектора х даних надаються ранги, які відповідають номерам їх позицій у векторі, наприклад, є натуральним рядом чисел, записаних в одиничному позиційному коді (6). Матриця ваг G0 подається на адресні входи селектора кодів СК і на адресні входи комутатора К з виходів пам'яті рангів ПР.

Одночасно на інформаційні входи навчальної частини подається вхідний вектор даних вигляду х={х1, …, хі, …, хm}. З рис.4 видно, що вхідний масив x і матриця ваг G0 поступають на селектор кодів СК, де виконується селекція (вибірка) вигляду

xt Gt-1 (7) Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

де N- кількість циклів сортування, хti - i-й елемент поточного вектора хt, сформованого з елементів вхідного вектора х за адресою git-1 матриці ваг Gt-1 в t-му циклі

сортування.

Потім в аналізаторі реакцій АР реалізується порогова обробка елементів поточного вектора xt таким чином

Після цього в комутаторі K виконується перекомутація з урахуванням матриці ваг Gt-1 елементів вектора зв'язків qt і формування двох векторів інкремента/декремента рангів qt+= і qt- = за формулою:

qt+=qtGpt-1 ,

qt-=qtG, (9)

де Gt-1 -матрица ваг, яка формується в (t-1)-му циклі сортування; р, р+1- відповідно парні і непарні стовпці матриці ваг.

В пам'яті рангів ПР виконується формування поточної матриці ваг Gt шляхом зміни (налаштування) її елементів в процесі їх збільшення/зменшення на одиницю (інкремента/декремента) відповідно до елементів векторів qt+ і qt-.

Нарешті при наявності одиничного сигналу “Кінець” з виходу пам'яті рангів ПР зчитується вектор підстановки vj, який поступає на вихідний селектор кодів ВСК. У ВСК реалізується вибірка (формування) елементів результуючого вектора xN з елементів вхідного вектора x за адресою вектора підстановки vj, яку представляють вектор-стовпці матриці ваг GN (vij=gNij) вигляду

xx, (10)

де v=gNj;,.

Особливість даної сортувальної нейромережі полягає в такому.

1. Групу з К елементів порівняння у складі аналізатора реакцій АР можна розглядати як шар бінарних нейронів з пороговою функцією вигляду (8) за аналогією з нейромережею-прототипом. Цей шар у складі навчальної частини нейромережі формує вектор зв'язків qt, який бере участь у формуванні поточної матриці ваг Gt.

2. Етап навчання в даній сортувальній нейромережі полягає в налаштуванні матриці рангів Gt, яка в даному випадку розглядається як матриця ваг. Цей етап завершується за умови нульового значення всіх елементів поточного вектора зв'язків qt, тобто при формуванні сигналу “Кінець”.

3. На робочому етапі функціонування сортувальної нейомережі виконується видача відсортованого масиву чисел послідовно по його елементах xiN .

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

5. В обчислювальній частині нейромережі (рис.3) замість шару нейронів використовується просторово-розподілена пам'ять ПР, в якій формується матриця ваг- рангів Gt для навчальної частини.

При кодуванні вагових коефіцієнтів або рангів елементів масиву чисел x можливі два варіанти: з використанням двійкового або одиничного коду. В першому випадку масив рангів представляється вектором ваг gt, в другому випадку- матрицею ваг Gt. Саме в другому випадку для зберігання матриці ваг в сортувальній мережі використовується пам'ять рангів ПР не у вигляді реверсивних двійкових лічильників, а як просторово-розподілена пам'ять на зсувних регістрах. Це дозволяє спростити і як просторово-розподілена пам'ять на зсувних регістрах. Це дозволяє спростити і прискорити процес перетворення рангів, а також усунути дешифрацію адреси при зчитуванні результату.

В четвертому розділі виконано програмно-апаратну реалізацію нейромережного сортування попарним обміном.

Представлено алгоритми сортування за збільшенням методом попарного обміну з послідовним і паралельним способом формування пар елементів масиву чисел. Крім того, виконано моделювання сортування даним методом на мові високого рівня (С++) і отримано результати у вигляді таблиці і графіків. Це дозволяє проаналізувати і обгрунтувати вибір оптимального за часовими параметрами варіанта сортування масиву чисел будь-якої розмірності методом попарного обміну.

На рис. 5,6 показано “вікна” відповідно із статистичними і графічними результатами моделювання методу сортування попарним обміном .

Запропоновано виконання базових блоків сортувальної нейромережі на оптоелектронній елементній базі для реалізації в оптичному діапазоні зв'язку між пам'яттю рангів ПР, селектором кодів СК і комутатором К (рис. 3). Прикладом базової оптоелектронної ІС для нейромережі вибрано матрицю смарт-пікселів з високими комутаційними можливостями, для виготовлення якої використовують технологію "рідкий кристал на кремнії". Для такої матриці характерними є велика кількість оптичних входів/виходів (більше 105), незначна функціональна складність (не більше 50 транзисторів на канал) і продуктивність близько 100 Мбіт/с.

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

Виконано розрахунок швидкодії сортувальної нейромережі на оптичних і оптоелектронних ІС і ПЛІС. Відомо, що для будь-якого методу сортування можна розрахувати максимальний часовий параметр, отже, найбільш точно можна визначити максимальну кількість циклів Nmax. При цьому, з орієнтацією на розмірність фотоматричного асоціативного запам'ятовувального ЗП (ФМ АЗП) приймемо, що m=32 слова, n=8 біт, а Nmax=m-1=31.

Тоді (11)

де - час, який затрачується відповідно на зчитування слів з ФМ АЗП, обробку чисел в аналізаторі реакцій АР і ранжування в пам'яті рангів ПР; - час зчитування результату; - максимальна кількість циклів сортування.

Для селектора кодів СК і комутатора К, які реалізуються на оптичних ІС векторно-матричного множення, затримка складає нс. Аналізатор реакцій АР і вихідний селектор кодів ВСК реалізуються на ПЛІС, тому враховується максимальна затримка для ПЛІС, яка наприклад, для FLEX 10K10-3 складає 50 нс. Враховуючи конструктивні і технологічні особливості фотоматричного асоціативного ЗП (ФМ АЗП), час вибірки розрядних зрізів слів з нього дорівнює мкс. А для памяті рангів ПР на оптоелектронній ІС матриці смарт-пікселів характерним є час затримки в межах 1 нс.

Отже, з формули (11) випливає, що для великих масивів даних (1000 слів розрядністью 32 біта) максимальний час сортування знаходиться в межах мілісекундного діапазону, а це, у свою чергу, свідчить про можливість використання даної сортувальної нейромережі у складі систем, які працюють в реальному часі.



ОСНОВНІ ВИСНОВКИ І РЕЗУЛЬТАТИ РОБОТИ

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

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

2. Розроблено та досліджено моделі у вигляді сортувальних мереж для методу попарного обміну з введенням нових зв'язків між крайніми елементами масиву (у вигляді “кільця”) в парних або непарних циклах сортування. Це дозволяє перейти від процедури сортування з лінійною організацією масиву сортованих чисел до процесу сортування шляхом повного попарного аналізу масиву чисел з кільцевою організацією. А отже, апаратно реалізувати сортувальну нейромережу і забезпечити максимально можливий рівень паралельної обробки K=m/2, де m- розмірність масиву даних.

3. Запропоновано і досліджено преставлення в модифікованій системі алгоритмічних алгебр (САА-М) В.М. Глушкова сортування масиву даних у вигляді “кільця”. Це дозволяє формалізувати подання і забезпечити аналіз і вибір оптимального варіанта сортування для реалізації на сортувальній нейромережі, що дає можливість, у свою чергу, прискорити процес впорядкованої вибірки в найнесприятливішому випадку на відміну від сортування у вигляді “стрічки ” як мінімум на один цикл, а в порівнянні з класичним варіантом сортування як мінімум на два цикли.

4. Вдосконалено структурну організацію сортувальної нейромережі з використанням сортування масиву даних методом парного обміну з ранжуванням. Це забезпечує не тільки збіжність процесу за час О(m), де m-размерность вхідного масиву, але й скорочення тривалості кожного циклу сортування на два машинні такти за рахунок використання операції інкремента/ декремента для перетворення рангів елементів масиву чисел замість перестановки цих елементів в ЗП.

5. Досліджено використання одиничного позиційного коду для представлення величини рангу, який розглядається як адреса або індекс відповідного елемента у межах початкового масиву чисел. Це дозволяє спростити і прискорити процес перетворення рангів за рахунок специфічної реалізації операції інкремента/декремента, а також усунути дешифрацию адреси, оскільки ранг є просторово- розподіленою адресою (індексом) відповідного елемента векторного масиву. Таким чином, зміна рангів в процесі сортування є налаштуванням матриці вагових коефіцієнтів адаптивної сортувальної нейромережі.

6. Розроблено програми моделювання алгоритмів сортування на мові високого рівня (C++), які дозволяють визначити кількість циклів, порівнянь і перестановок для методу попарного обміну в класичному (лінійному) варіанті і при введенні мінімального/максимального елемента в мінімальну/максимальну позицію (в кільцевому варіанті) і представити результати в наочному графічному вигляді. Це дозволяє, у свою чергу, проаналізувати і обгрунтувати вибір оптимального варіанта сортування масиву чисел будь-якої розмірності методом попарного обміну. Крім того, аналіз графічних результатів моделювання свідчить про залежність вигляду О(m) між кількістю циклів сортування і розмірністю m вхідного масиву, що підтверджує ефективність апаратної реалізації сортування попарним обміном на сортувальній нейромережі.

7. Запропоновано і досліджено варіант реалізації сортувальної нейромережі на оптоелектронній елементній базі, а саме, на матрицях смарт-пікселів, що дозволяє усунути труднощі, пов'язані з організацією великої кількості міжз'єднань в нейромережі для паралельної передачі матриці рангів розмірністю елементів. Розрахунок швидкодії сортувальної нейромережі з урахуванням швидкодії оптоелектронних і оптичних ІС для її базових блоків показав, що сортування великих масивів чисел (розмірність масиву 32-1000 слів, розмірність чисел 8-32 біт) виконується в реальному часі (мілісекундний діапазон). Це дозволяє використовувати запропонований варіант оптоелектронної сортувальною нейромережі як спецпроцесор в системах для обробки сигналів і зображень в реальному часі.



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Мохамед Салем Нассер Мохамед. Аналіз можливостей одиничного кодування числової інформації/ Т.Б. Мартинюк, Мохамед Салем Нассер Мохамед, В.В. Власійчук, О.М. Наконечний // Оптико-електронні інформаційно-енергетичні технологїї.-2005.-№2(10).-С.39-44.

2. Мохамед Салем Нассер Мохамед. Модель сортувальної мережi/ Т.Б. Мартинюк, Мохамед Салем Нассер Мохамед, В.В.Власiйчук // Інформацiйнi технологiї та комп'ютерна iнженерія.-2005.-№3.-С.217-220.

3. Мохамед Салем Нассер Мохамед. Оптимiзований опис алгоритмiв мультиобробки у базисi систем алгоритмiчних алгебр Глушкова/ Т.Б.Мартинюк, Л.В. Огороднiйчук, Мохамед Салем Нассер Мохамед //Вiсник Вінницького політехнічного інституту.- 2006.-№6.-С.162-165.

4. Мохамед Салем Нассер Мохамед. Нейросети и ассоциативная обработка массива данных/ В.П.Кожемяко, Т.Б.Мартынюк, Мохамед Салем Нассер Мохамед // Оптико-електронні інформаційно-енергетичні технологїї.- 2007.-№2 (14).-С.72-79.

5. Мохамед Салем Нассер Мохамед. Сравнительный анализ методов сортировки / Мохамед Салем Нассер Мохамед // Оптико-електронні інформаційно-енергетичні технологїї.-2007.-№1 (13).-С.34-40.

6. Мохамед Салем Нассер Мохамед. Нейромережевий пiдхiд до сортування числового масиву/ Т.Б.Мартинюк, А.Г.Буда, В.В. Власійчук, Мохамед Салем Нассер Мохамед //Збiрник наукових праць Одеського ордена Ленiна iнституту Сухопутних вiйськ.- Вип.13.- Одеса: ООЛІСВ, 2007.-С.97-100.

7. Мохамед Салем Нассер Мохамед. Модель сортирующей сети/ Т.Б.Мартынюк, Мохамед Салем Нассер Мохамед, В.В. Власийчук // Контроль і управління в складних системах (КУСС-2005): восьма наук.- техн. конф., 24-27 жовтня 2005 р.: тези допов.- Вінниця: УНІВЕРСУМ- Вiнниця, 2005.-С.110.

8. Мохамед Салем Нассер Мохамед. Нейросетевой подход к сортировке числового массива/ Т.Б. Мартынюк, А.Г. Буда, В.В. Власийчук, Мохамед Салем Нассер Мохамед // Современные информационные и электронные технологии: 7-я междунар. науч.-практ. конф., 22-26 мая 2006 г.: труды. Т.1.-Одесса, 2006.-С.91.

9. Мохамед Салем Нассер Мохамед. Оптимiзований опис алгоритмiв мультиобробки у базисi САА Глушкова / Т.Б. Мартинюк, Л.В.Огороднiйчук, Мохамед Салем Нассер Мохамед // Автоматика-2006: 13-а мiжнар. конф. з автоматичного управлiння, 25-28 вересня 2006 р.: тези допов.- Вiнниця: УНІВЕРСУМ- Вiнниця, 2006.- С.193.

10. Мохамед Салем Нассер Мохамед. Модель сортувальної мережі/ Т.Б.Мартинюк, Ю.А. Пахомов, Мохамед Салем Нассер Мохамед // Теорія та методи обробки сигналів: 2-а мiжнар. наук. конф., 20-22 травня 2008 р.: тези допов. -Київ, 2008.-С.90.

11. Мохамед Салем Нассер Мохамед. Формалiзований опис паралельного алгоритму сортування за методом попарного обмiну/ Т.Б. Мартинюк, А.Г. Буда, В.В. Власійчук, Мохамед Салем Нассер Мохамед // Наука и технологии: шаг в будущее- 2006: I междунар. науч.- практ. конф., 20-31 марта 2006 г.: материалы. Т.26.- Белгород: Руснаучкнига, 2006.- С.8-10.

12. Мохамед Салем Нассер Мохамед. Особенности нейросетевой реализации сортировки массива чисел/ Т.Б. Мартынюк, Л.В.Огороднийчук, Мохамед Салем Нассер Мохамед // Сучаснi проблеми радiоелектронiки, телекомунiкацiй та приладобудування (СПРТП-2007): III мiжнар. наук.- техн. конф., 31 травня-2 червня 2007 р.: матеріали.- Вiнниця: УНІВЕРСУМ-Вiнниця, 2007.- С.184.

13. Мохамед Салем Нассер Мохамед. Кодирование весовых коэффициентов в сортирующей нейросети/ Т.Б.Мартынюк, Мохамед Салем Нассер Мохамед, Л.В.Огороднийчук // Методи та засоби кодування, захисту й ущiльнення iнформацiї: Перша мiжнар. наук.-практ. конф., 15-17 травня 2007 р.: тези допов.-Вiнниця: ВНТУ, 2007.- С.33-34.

14. Мохамед Салем Нассер Мохамед. Особливостi кодування i перетворення iнформацiї в сортуючiй мережi/ Т.Б.Мартинюк, Н.В.Фофанова, В.В.Власiйчук, Мохамед Салем Нассер Мохамед // Оптоелектроннi iнформацiйнi технологiї. Фотоніка ОДС-2005: 3-а мiжнар. наук.- техн. конф., 27-28 квітня 2005 р.: збірник тез допов.- Вiнниця: УНІВЕРСУМ - Вiнниця, 2005.- С.63.



АНОТАЦІЇ

Мохамед Салем Нассер Мохамед. Нейромережна організація сортування масивів даних.- Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спецiальнiстю 05.13.05-Комп'ютерні системи та компоненти.-Вінницький національний технічний університет, Вінниця, 2009.

В роботі розглянуті питання підвищення швидкодії сортування методом попарного обміну при реалізації його апаратним способом, тобто на сортувальній нейромережі. Показано, що процедура сортування застосовується в різних прикладних задачах, наприклад, для ефективного зберігання і впорядкування мережних адрес IP в додатках для мереж Web, використовуючих БД, у системах обробки сигналів і зображень для прискорення процедури фільтрації. Розроблено реалізацію методу сортування попарним обміном на такій перспективній структурі, як нейромережа із застосуванням оптоелектронної елементноі бази, що дозволяє усунути труднощі, які пов'язані з організацією великої кількості міжз'єднань у нейромережi при сортуванні масиву чисел. Показано доцільність представлення алгоритмів сортування в компактній і формалізованій формі із залученням модифікованої системи алгоритмічних алгебр (САА-М) В.М. Глушкова, оскільки застосування таких операторних представлень дозволяє формалізувати подання і забезпечити аналіз і вибір оптимального варианта сортування (впорядкованої вибірки). Виконано розрахунок швидкодіі розробленої сортувальної нейромережі показав, що вона є достатньою для обробки великих масивів даних (до 1000 слів розмірністю 32 біти), що дозволяє використати сортувальну нейромережу як спецпроцесор для систем, які працюють в реальному часі.

Ключовi слова: сортувальна нейромережа, попарний обмін з ранжуванням, сортування, швидкодія, оптоелектронна елементна база, система алгоритмічних алгебр (САА) В.М. Глушкова.

Mohamed Salem Nasser Mohamed. Neural network organization of data arrays sorting .- A manuscript.

Dissertation for the degree of candidate of science (eng.) on speciality 05.13.05- Computer systems and components.- Vinnytsia National Technical Uiversity, Vinnytsia, 2009.

The given research considers the problem of sorting rate enhancement applying the metod of pairwise exchange while its hardware realization, i.e on sorting neuro network. It is shown that the sorting procedure is used in various applied problems, for instance, for efficient storage an of arrangement network IP addresses in appendixes for Web networks, using DB, in system of signals and images processing for acceleration of filteration procedure.

Method of pairwise sorting realization is developed on the basis of neuro network, applying optoelectronic elment base, which enables to eliminate difficultly, connected with organization of a large number of interconnections in the network while number array sorting. The expediency of representation of sorting algorithms in compact and formalized form involving modified system of algorithmic algebral (SAA-M) by V.M. Glushkov is shown, since application of such operator representation allows to formalize and provide analysis and selection of optimum variant of sorting (arranged sample). Computation of fast-action of the elaborated sorting neuronetwork was performedthe calculation showed that the suggested neuro network is sufficient for processing of large data arrays (up to 1000 words of 32 bits dimension) that enubles to use sorting neuro network as spcial processor for the systems operating in real time scale.

Keywords: sorting network, pairwise exchange with ranking, sorting, performance, optoelectronic element base, system of algorithmic algebras (SAA).



Мохамед Салем Нассер Мохамед. Нейросетевая организация сортировки массивов данных.- Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05- Компьютерные системы и компоненты.- Винницкий национальный технический университет, Винница, 2009.

В работе рассмотрены вопросы повышения быстродействия сортировки методом парного обмена при реализации его аппаратным способом, т.е. на сортирующей нейросети. показано, что процедура сортировка применяется в разных прикладных задачах, например, для эффективного хранения и упорядочивания сетевых адресов IP в приложениях для сети Web, использующих БД, в системах обработки сигналов и изображений для ускорения процедуры фильтрации. Разработана и исследована реализация метода сортировки парнім обменом на такой перспективной структуре, как нейросеть с использованием оптоэлектронной элементной базы, что позволяет как нейросеть с использованием оптоэлектронной элементной базы, что позволяет устранить трудности, связанные с организацией большого количества межсоединений в нейросети при сортировке массива чисел.

Разработаны и исследованы модели сортирующей сети в виде “кольца” за счет введения дополнительного минимального/максимального элемента при нечетной размерности входного массива и формирования дополнительной пары элементов массива во всех нечетных или четных циклах сортировки.

Предложены и исследованы представлення в базисе САА-М В.М. Глушкова сортирующей сети в виде “кольца”. Для этого базис САА дополнен составным оператором , базисными операторами , сложным оператором , рядом предикатов и операцией, названной декомпозицией, что позволяет компактно описать и исследовать все способы параллельного формирования и обработку всех K пар элементов во всех циклах сортировки.

Разработана структура сортирующей нейросети и схематическая диаграмма ее функционирования.

Выполнен анализ особенностей ранжирования элементов массива при сортировке методом парного обмена, где выполняются непересекающиеся обмены чисел в парах и сохраняется их первоначальная запись в ЗУ. В результате достигается выигрыш по быстродействию в машинных тактах порядка , где N- количество циклов сортировки, поскольку в процессе попарного просмотра элементов массива выполняется изменение значений рангов соответствующих элементов на единицу (инкремент/декремент) за один такт вместо перемещения (транспозиции) элементов в парах, которое выполняется в ЗУ как минимум за три машинных такта.

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

Выполнен расчет быстродействия разработанной сортирующей нейросети для обработки больших массивов данных (до 1000 слов размерностью 32 бита) для использования в качестве спецпроцессора для систем, которые работают в реальном времени.

Ключевые слова: сортирующая нейросеть, парный обмен с ранжированием, сортировка, быстродействие, оптоэлектронная элементная база, система алгоритмических алгебр (САА) В.М. Глушкова.

Размещено на Allbest.ru

...