Обчислювальна складність мережевої моделі сортування лінійного масиву чисел
Тетяна Мартинюк, Олександр Черняк, Богдан Круківський, Мохамед МохамедПри розробці розвиненого програмного та апаратного забезпечення для сучасних обчислювальних засобів інтерес представляють удосконалені методи асоціативної обробки інформації, а саме процедури сортування і вибору. Це забезпечує реалізацію ефективного пошуку потрібної інформації в масивах даних. Необхідність паралельної необчислювальної обробки великих масивів інформації потребує відповідну організацію асоціативної пам'яті, а також розробку і використання відповідних перспективних технічних засобів. Сортування вважається важливою процедурою в таких прикладних областях, як рішення економічних задач, управління базами даних (СУБД), сортування IP адрес в комп'ютерних мережах, обробка сигналів і зображень (наприклад, при нелінійній медіанній фільтрації зображень). Аналіз відомих методів сортування показав, що найбільш ефективним методом паралельного сортування з урахуванням його апаратної реалізації сортуючою мережею є метод попарного обміну. При цьому, ступінь паралелізму будь-якого методу сортування за його апаратної реалізації безпосередньо залежить від кількості схем порівняння, які спрацьовують паралельно при кожному перегляді. Для методу попарного обміну ступінь паралелізму визначається величиною ]n/2[, де n - кількість вхідних числових величин або розмірність вхідного лінійного масиву чисел. У статті проаналізовано способи реалізації алгоритму сортування методом попарного обміну з топологією зв'язків між елементами масиву чисел у вигляді «стрічки» і «кільця». Для прикладу описано паралельний алгоритм сортування методом попарного обміну. Моделювання алгоритму виконано на мові високого рівня С ++. Проаналізовано отримані статистичні та графічні результати моделювання. Аналіз графічних результатів моделювання свідчить про залежність виду O(n) між кількістю циклів сортування і розмірністю n вхідного масиву. Це підтверджує ефективність апаратної реалізації сортування попарним обміном на сортуючій мережі за рахунок регулярності структури і зв'язків в процесі сортування. Можливість статистично визначити не тільки кількість циклів сортування при заданій розмірності масиву чисел, але й відповідну кількість порівнянь і переміщень значно розширює можливості вдосконалення відомих і створення нових способів синхронного сортування елементів лінійного масиву апаратно у вигляді сортуючої мережі