ОБЧИСЛЮВАЛЬНА СКЛАДНІСТЬ МЕРЕЖЕВОЇ МОДЕЛІ СОРТУВАННЯ ЛІНІЙНОГО МАСИВУ ЧИСЕЛ
DOI:
https://doi.org/10.31649/1999-9941-2019-45-2-64-71Ключові слова:
обчислювальна складність, сортування, лінійний масив чиселАнотація
При розробці розвиненого програмного та апаратного забезпечення для сучасних обчислювальних засобів інтерес представляють удосконалені методи асоціативної обробки інформації, а саме процедури сортування і вибору. Це забезпечує реалізацію ефективного пошуку потрібної інформації в масивах даних. Необхідність паралельної необчислювальної обробки великих масивів інформації потребує відповідну організацію асоціативної пам'яті, а також розробку і використання відповідних перспективних технічних засобів. Сортування вважається важливою процедурою в таких прикладних областях, як рішення економічних задач, управління базами даних (СУБД), сортування IP адрес в комп'ютерних мережах, обробка сигналів і зображень (наприклад, при нелінійній медіанній фільтрації зображень). Аналіз відомих методів сортування показав, що найбільш ефективним методом паралельного сортування з урахуванням його апаратної реалізації сортуючою мережею є метод попарного обміну. При цьому, ступінь паралелізму будь-якого методу сортування за його апаратної реалізації безпосередньо залежить від кількості схем порівняння, які спрацьовують паралельно при кожному перегляді. Для методу попарного обміну ступінь паралелізму визначається величиною ]n/2[, де n - кількість вхідних числових величин або розмірність вхідного лінійного масиву чисел. У статті проаналізовано способи реалізації алгоритму сортування методом попарного обміну з топологією зв'язків між елементами масиву чисел у вигляді «стрічки» і «кільця». Для прикладу описано паралельний алгоритм сортування методом попарного обміну. Моделювання алгоритму виконано на мові високого рівня С ++. Проаналізовано отримані статистичні та графічні результати моделювання. Аналіз графічних результатів моделювання свідчить про залежність виду O(n) між кількістю циклів сортування і розмірністю n вхідного масиву. Це підтверджує ефективність апаратної реалізації сортування попарним обміном на сортуючій мережі за рахунок регулярності структури і зв'язків в процесі сортування. Можливість статистично визначити не тільки кількість циклів сортування при заданій розмірності масиву чисел, але й відповідну кількість порівнянь і переміщень значно розширює можливості вдосконалення відомих і створення нових способів синхронного сортування елементів лінійного масиву апаратно у вигляді сортуючої мережі.
Посилання
Д.Э.Кнут, Искусство программирования. Т.3. Сортировка и поиск. М., Россия: Издательский дом «Вильямс», 2003.
Е.А.Яценко, «Регулярные схемы алгоритмов адресной сортировки и поиска», Управляющие системы и машины, №5, с.61-66. 2004.
Однокристальный ассоциативный процессор САМ 2000, [Електронний ресурс]. Режим доступу: http://data.mf.grsu.by/citforum/htdocs/hardware/vich_sist/index.shtml Дата звернення: Травень. 15, 2019.
К.Дж.Тербер, Архитектура высокопроизводительных вычислительных систем. М., Россия: Гл.ред. физ-мат. Лит-ры, 1985.
В.П.Гергель, и Р.Г.Стронгин, Основы параллельных вычислений для многопроцессорных вычислительных систем. Нижний Новгород, Россия: Изд-во ННГУ им. Н.Лобачевского, 2003.
Е.Ф.Очин, Вычислительные системы обработки изображений. Л., Россия: Энергоатомиздат. Ленингр.отд-ние, 1989.
Хранение и сортировка адресов IP, [Електронний ресурс]. Режим доступу: http://www.compodoc.ru/sort/index.html Дата звернення: Травень. 17, 2019.
Алгоритмы. Сортировка и операции с упорядоченными последовательностями, [Електронний ресурс]. Режим доступу: http://alglib.chat.ru/sort/index.html Дата звернення: Травень. 10, 2019.
В.Р.Григорьев, «Нейросетевая организация алгоритмов сортировки на трехмерном оптическом нейрочипе», Автометрия, №3, с.28-37. 1993.
Г.Лорин, Сортировка и системы сортировки. М.,Россия: Мир, 1983.
В.Мдовгань, В.А.Титенко, С.В.Выдрина, и Б.В.Клюйков, «Устройство для сортировки чисел», Патент России G06F7/08. №2246750 МКИ (2005), 20.02.2005.
Т.Б.Мартинюк, і В.В.Хом’юк, «Оцінювання ефективності алгоритмів мультиобробки масивів даних», Вісник Вінницького політехнічого інституту, №5, с.76-82. 2005.
Т.Б.Мартинюк, А.В.Кожем’яко, А.І.Колівошко, і О.В.Карась, «Дослідження ефективності кільцевої сортувальної мережі», Інформаційні технологіїї та комп’ютерна інженерія, №1, с.68-71. 2015.
V.P.Kozhemyako, T.B.Martynyuk, R.A.Rasenko, and I.L.Pekhan, “Structure of Optoelectronic Sort-ing Memory”, Оптико-електронні інформаційно-енергетичні технології, №1(3), с. 26-29. 2002.
Т.Б.Мартинюк, Мохамед Салем Нассер Мохамед, і В.В.Власійчук, «Модель сортувальної мережі», Інформаційні технологіїї та комп’ютерна інженерія, №3, с.217-220. 2005.
Т.Б.Мартинюк, Л.В.Огороднійчук і Мохамед Салем Нассер Мохамед, «Оптимізований опис алгоритмів мультиобробки у базисі систем алгоритмічних алгебр Глушкова», Вісник Вінницького політехнічного інституту, №6, с.162-165. 2006.
В.П.Кожемяко, Т.Б.Мартынюк, и В.В.Хомюк, «Особенности структурного программирования синхронных алгоритмов», Кибернетика и системный анализ, №5, с.122-133. 2006.
Джесс. Либерти, С++ Энциклопедия. М.,Россия: Издательство ДиаСофт, 2000.
Р.Сэджвик, Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. СПб.,Россия: ООО «ДиаСофтЮП», 2002.
##submission.downloads##
-
PDF
Завантажень: 260
