Обчислювальна складність мережевої моделі сортування лінійного масиву чисел

Abstract

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

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

In the development of advanced software and hardware for modern computing, the interest is the improvement of methods of associative processing of information such as procedures of sorting and selection. That ensures the realization of effective search for the required information in the data arrays. The need for parallel non-processing of large amounts of information entails the appropriate organization of associative memory, as well as the development and using of perspective technical devices. The sorting is important procedure in such application areas as solving economic problems, managing databases, sorting of IP addresses in computer networks, processing signals and images (for example, in nonlinear median image filtering). The analysis of known sorting methods have shown that the most effective method of parallel sorting, taking into account its hardware implementation by the sorting network, is the pairwise exchange. At the same time, the degree of parallelism of any sorting method for its hardware implementation directly depends on the number of comparison schemes that work in parallel in each view. For a pairwise exchange method, the degree of parallelism is determined by the value ]n/2[, where n is the number of input numerical values or the dimension of the input linear number array. In this article methods of implementing of the sorting algorithm by the method of pairwise exchange with the link topology between elements of the number array in the form of "tape" and "ring" are analyzed. For example, the parallel sorting algorithm using the pairwise exchange method is described. The simulation at a high-level C ++ language is done. The obtained statistical and graphic results of modeling are analyzed. The analysis of graphical modeling results shows the dependence of the form O(n) between the number of sort cycles and the dimensionality n of the input array. That confirms the effectiveness of the hardware implementation of sorting by pairwise exchange on the sorting network due to the regularity of the structure and connections in the sorting process. The ability to statistically determine not only the number of sorting cycles with a given dimension of the number array, but also the corresponding number of comparisons and transposition greatly extends the possibilities of improving the known and creating new ways of synchronous sorting of elements of a linear array by hardware in the form of a sorting network.