Інформаційні технології та комп'ютерна техніка

МОДЕЛЬ ПАРАЛЕЛЬНОГО СОРТУВАЛЬНИКА ДЛЯ АСОЦІАТИВНОГО ПРОЦЕСОРА

Автор(и)

Т. Б. Мартинюк
Вінницький національний технічний університет ROR
Б. І. Круківський
Вінницький національний технічний університет ROR
DOI https://doi.org/10.31649/1997-9266-2020-152-5-49-55

Ключові слова

сортувальник медіанна фільтрація асоціативний процесор ранжування

Анотація

Процес сортування та вибірки за ключем є основною процедурою у багатьох пошукових системах таких, як бази даних та пошукові системи в Інтернеті. Водночас сучасні обчислювальні засоби вимагають ефективних методів і засобів, пов'язаних з асоціативною обробкою інформації під час розроблення програмного та апаратного забезпечення. Тому виникає потреба у високошвидкісному необчислювальному (асоціативному) обробленні значних обсягів інформації, що вимагає відповідної організації та вдосконалення технічних засобів сортування. Відомі алгоритми та засоби сортування чисел дозволяють регулювати інтенсивність виконання цього процесу та підвищувати його ефективність, використовуючи паралельні пристрої, але вони вимагають значних апаратних витрат. Тому метою подальших досліджень є розробка нових та вдосконалення відомих методів сортування з орієнтацією на зменшення апаратних витрат та збільшення швидкості цього процесу. В роботі запропоновано структурну схему сортувальника як обчислювальної частини асоціативного процесора, яка має регулярну логічну структуру і паралельно-послідовні зв'язки між блоками обробки даних. Це значно спрощує «розміщення» сортувальника в мікросхемі програмованої логічної ІС (ПЛІС). Крім того, функціонально у сортувальнику реалізовано багатофункціональність обробки числових масивів даних завдяки формуванню рангів елементів вхідного масиву. Це дозволяє визначити не тільки екстремальні елементи числового масиву, але й елемент, що займає середнє значення у відсортованому масиві, що є необхідною умовою для швидкісної медіанної фільтрації зображень. В запропонованому сортувальнику в процесі сортування використовуються швидкісні операції інкременту/декременту на масивах лічильників замість витратної за часом операції попарного порівняння паралельно для всіх елементів масиву з подальшою їх перекомутацією.

571 136

Як цитувати

[1]
«МОДЕЛЬ ПАРАЛЕЛЬНОГО СОРТУВАЛЬНИКА ДЛЯ АСОЦІАТИВНОГО ПРОЦЕСОРА», Вісник ВПІ, вип. 5, с. 49–55, Лис 2020, doi: 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.

Статті цього автора (цих авторів), які найбільше читають

1 2 > >>