МОДЕЛЬ ПАРАЛЕЛЬНОГО СОРТУВАЛЬНИКА ДЛЯ АСОЦІАТИВНОГО ПРОЦЕСОРА
DOI:
https://doi.org/10.31649/1997-9266-2020-152-5-49-55Ключові слова:
сортувальник, медіанна фільтрація, асоціативний процесор, ранжуванняАнотація
Процес сортування та вибірки за ключем є основною процедурою у багатьох пошукових системах таких, як бази даних та пошукові системи в Інтернеті. Водночас сучасні обчислювальні засоби вимагають ефективних методів і засобів, пов'язаних з асоціативною обробкою інформації під час розроблення програмного та апаратного забезпечення. Тому виникає потреба у високошвидкісному необчислювальному (асоціативному) обробленні значних обсягів інформації, що вимагає відповідної організації та вдосконалення технічних засобів сортування. Відомі алгоритми та засоби сортування чисел дозволяють регулювати інтенсивність виконання цього процесу та підвищувати його ефективність, використовуючи паралельні пристрої, але вони вимагають значних апаратних витрат. Тому метою подальших досліджень є розробка нових та вдосконалення відомих методів сортування з орієнтацією на зменшення апаратних витрат та збільшення швидкості цього процесу. В роботі запропоновано структурну схему сортувальника як обчислювальної частини асоціативного процесора, яка має регулярну логічну структуру і паралельно-послідовні зв'язки між блоками обробки даних. Це значно спрощує «розміщення» сортувальника в мікросхемі програмованої логічної ІС (ПЛІС). Крім того, функціонально у сортувальнику реалізовано багатофункціональність обробки числових масивів даних завдяки формуванню рангів елементів вхідного масиву. Це дозволяє визначити не тільки екстремальні елементи числового масиву, але й елемент, що займає середнє значення у відсортованому масиві, що є необхідною умовою для швидкісної медіанної фільтрації зображень. В запропонованому сортувальнику в процесі сортування використовуються швидкісні операції інкременту/декременту на масивах лічильників замість витратної за часом операції попарного порівняння паралельно для всіх елементів масиву з подальшою їх перекомутацією.
Посилання
Г. Лорин, Сортировка и системы сортировки. Москва: Мир, 1983.
Д. Э. Кнут, Искусство программирования. Т.3. Сортировка и поиск. Москва, Россия: Изд. дом «Вильямс», 2003.
Ассоциативная обработка. [Электронный ресурс]. Режим доступа: http://www.ngpedia.ru/id97447pl.html. Дата обращения: февр. 20, 2020.
Т. Б. Мартинюк, О. І. Черняк, Б. І. Круківський, і Мохамед Салем Нассер Мохамед, «Обчислювальна складність мережевої моделі сортування лінійного масиву чисел,» Інформаційні технології та комп'ютерна інженерія, № 2, с. 64-71. 2019.
І. Г. Цмоць, Інформаційні технології та спеціалізовані засоби обробки сигналів і зображень у реальному часі. Львів, Україна: Видавництво УАД, 2005.
Т. Кохонен, Ассоциативные запоминающие устройства. Москва: Мир, 1982.
К. Дж. Тербер, Архитектура высокопроизводительных вычислительных систем. Москва: Гл. ред . физ -мат. лит-ры, 1985.
Я. И. Фет, Параллельные процессоры для управляющих систем. Москва: Энергоиздат, 1981.
В. В. Коваленко, і В. О. Гуменюк, «Аналіз найактуальніших серверних систем управління базами даних,» Вісник Національного університету "Львів. політехніка", № 603, с. 65-72, 2007.
А. В. Богданов, В. В. Корхов, В. В. Мареев, и Е. Н. Станкова, Архитектуры и топологии многопроцессорных вычислительных систем. Москва, Россия: ИНТУИТ.РУ, 2009.
У. Прэтт, Цифровая обробка изображений. Москва: Мир, 1982.
І. Г. Цмоць, і В. Я. Антонів, «Апаратні засоби сортування даних методом злиття в реальному часі,» Інформаційні системи та мережі, № 814, с. 171-185, 2015.
І. Г. Цмоць, і В. Я. Антонів, «Алгоритми та паралельні структури сортування даних методом вставки,» Науковий вісник НЛТУ України, вип. 26.1, с. 340-350, 2016.
Т. Б. Мартинюк, Н. О. Денисюк, і Б. І. Круківський, «Асоціативні процесори з паралельно-послідовною обробкою даних,» Інформаційні технології та комп'ютерна інженерія, № 1, с. 27-36, 2019.
Медианная фильтрация, [Электронный ресурс]. Режим доступа: https://ru.bmstu.wiki/Медианная_фильтрация. Дата обращения: март, 20, 2020.
Т. Б. Мартинюк, і Б. І. Круківський, «Пристрій для ранжування чисел,» Патент України G06F 7/06. № 139604 МПК (2008), 12.08.2019.
Т. Б. Мартинюк, Б. І. Круківський, і А. І. Друзюк, «Сортувальник з індикацією рангів елементів масиву,» на Шостій міжнарод. наук.-техн. конф. «Фотоніка ОДС – 2018», ВНТУ, 2-4 жовтня 2018 р., с. 30.
В. Б. Стешенко, ПЛИС фирмы «ALTERA»: элементная база, система проектирования и языки описания. Москва, Россия: Додека-ХХІ, 2002.
Микросхемы «Altera» [Электронный ресурс]. Режим доступа: http://altera.ru/Mikroshemi.html. Дата обращения: окт. 5, 2020.
##submission.downloads##
-
PDF
Завантажень: 96
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, згодні з такими умовами:
- Автори зберігають авторське право і надають журналу право першої публікації.
- Автори можуть укладати окремі, додаткові договірні угоди з неексклюзивного поширення опублікованої журналом версії статті (наприклад, розмістити її в інститутському репозиторії або опублікувати її в книзі), з визнанням її первісної публікації в цьому журналі.
- Авторам дозволяється і рекомендується розміщувати їхню роботу в Інтернеті (наприклад, в інституційних сховищах або на їхньому сайті) до і під час процесу подачі, так як це може привести до продуктивних обмінів, а також скорішого і ширшого цитування опублікованих робіт (див. вплив відкритого доступу).
