Registration Number
2119U010900, Article
popup.category
Стаття
Title
Computational complexity of the network model of sorting of a linear number array
popup.author
Мартинюк Т. Б.
Черняк О. І.
Круківський Б. І.
Мохамед Салем Нассер Мохамед
Martyniuk T. B.
Chernyak O. I.
Krukivskyi B. I.
Mohamed Salem Nasser Mohamed
Мартынюк Т. Б.
Черняк А. И.
Круковский Б. И.
Martyniuk T. B.
Chernyak O. I.
Krukivskyi B. I.
Mohamed Salem Nasser Mohamed
popup.publication
01-01-2019
popup.source_user
Вінницький національний технічний університет
popup.source
http://ir.lib.vntu.edu.ua/handle/123456789/30531
popup.publisher
Вінницький національний технічний університет
Description
При розробці розвиненого програмного та апаратного забезпечення для сучасних обчислювальних засобів інтерес представляють удосконалені методи асоціативної обробки інформації, а саме процедури сортування і вибору. Це забезпечує реалізацію ефективного пошуку потрібної інформації в масивах даних. Необхідність паралельної необчислювальної обробки великих масивів інформації потребує відповідну організацію асоціативної пам'яті, а також розробку і використання відповідних перспективних технічних засобів. Сортування вважається важливою процедурою в таких прикладних областях, як рішення економічних задач, управління базами даних (СУБД), сортування IP адрес в комп'ютерних мережах, обробка сигналів і зображень (наприклад, при нелінійній медіанній фільтрації зображень). Аналіз відомих методів сортування показав, що найбільш ефективним методом паралельного сортування з урахуванням його апаратної реалізації сортуючою мережею є метод попарного обміну. При цьому, ступінь паралелізму будь-якого методу сортування за його апаратної реалізації безпосередньо залежить від кількості схем порівняння, які спрацьовують паралельно при кожному перегляді. Для методу попарного обміну ступінь паралелізму визначається величиною ]n/2[, де n - кількість вхідних числових величин або розмірність вхідного лінійного масиву чисел. У статті проаналізовано способи реалізації алгоритму сортування методом попарного обміну з топологією зв'язків між елементами масиву чисел у вигляді «стрічки» і «кільця». Для прикладу описано паралельний алгоритм сортування методом попарного обміну. Моделювання алгоритму виконано на мові високого рівня С ++. Проаналізовано отримані статистичні та графічні результати моделювання. Аналіз графічних результатів моделювання свідчить про залежність виду O(n) між кількістю циклів сортування і розмірністю n вхідного масиву. Це підтверджує ефективність апаратної реалізації сортування попарним обміном на сортуючій мережі за рахунок регулярності структури і зв'язків в процесі сортування. Можливість статистично визначити не тільки кількість циклів сортування при заданій розмірності масиву чисел, але й відповідну кількість порівнянь і переміщень значно розширює можливості вдосконалення відомих і створення нових способів синхронного сортування елементів лінійного масиву апаратно у вигляді сортуючої мережі.
popup.nrat_date
2026-11-04