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

Abstract

У даній роботі розглянуто сортування методом попарного обміну у вигляді сортувальної мережі типу «кільця». В такій сортувальній мережі формуються додаткові зв’язки між крайніми елементами масиву. Це, в свою чергу, свідчить про створення «кільцевої» структури зв’язків. Проведено імітаційне моделювання цього підходу, яке показало його ефективність через зменшення кількості циклів сортування у порівнянні із сортувальною мережею типу «стрічки». Формування «кільця» у непарних циклах сортування призводить до суттєвого зменшення кількості циклів у більшості випадків. Результати дослідження можуть бути використані при конкретній апаратній реалізації асоціативного процесора.

В данной работе рассмотрена сортировка методом парного обмена в виде сортирующей сети типа «кольца». В такой сортирующей сети формируются добавочные связи между крайними элементами массива. Это, в свою очередь, свидетельствует про образование «кольцевой» структуры связей. Проведено имитационное моделирование этого подхода, которое показало его эффективность из-за уменьшения количества циклов сортировки по сравнению с сортирующей сетью типа «ленты». Формирование «кольца» в нечётных циклах сортировки приводит к существенному уменьшению количества циклов в большинстве случаев. Результаты иследования могут быть использованы при конкретной аппаратной реализации ассоциативного процессора.

In this work reviewed the sorting by pairwise exchange as sorting networks of "ring" type.In such a sorting network generated more connections between the extreme elements of the array.This, in turn, suggests creating a "ring" structure of connections.A simulation of this approach, which showed its efficiency by reducing the number of sorting cycles compared to sorting network type "tape".Formation of the "ring"in odd sort leads to a significant reduction in the number of cycles in most cases. Results of the work can be used in a specific hardware implementation associative processor.