ОБЧИСЛЮВАЛЬНА СКЛАДНІСТЬ МЕРЕЖЕВОЇ МОДЕЛІ СОРТУВАННЯ ЛІНІЙНОГО МАСИВУ ЧИСЕЛ

Автор(и)

  • Тетяна Борисівна Мартинюк Вінницький національний технічний університет
  • Олександр Іванович Черняк Вінницький національний технічний університет
  • Богдан Ігорович Круківський Вінницький національний технічний університет
  • Салем Нассер Мохамед Мохамед Аденський університет

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##

Переглядів анотації: 339

Опубліковано

2019-10-15

Як цитувати

[1]
Т. Б. Мартинюк, О. І. Черняк, Б. І. Круківський, і С. Н. М. Мохамед, «ОБЧИСЛЮВАЛЬНА СКЛАДНІСТЬ МЕРЕЖЕВОЇ МОДЕЛІ СОРТУВАННЯ ЛІНІЙНОГО МАСИВУ ЧИСЕЛ», ІТКІ, вип. 45, вип. 2, с. 64–71, Жов 2019.

Номер

Розділ

Математичне моделювання та обчислювальні методи

Метрики

Завантаження

Дані завантаження ще не доступні.

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

1 2 3 > >>