Модель паралельного сортувальника для асоціативного процесора

Abstract

Процес сортування та вибірки за ключем є основною процедурою у багатьох пошукових системах таких, як бази даних та пошукові системи в Інтернеті. Водночас сучасні обчислювальні засоби вимагають ефективних методів і засобів, пов'язаних з асоціативною обробкою інформації під час розроблення програмного та апаратного забезпечення. Тому виникає потреба у високошвидкісному необчислювальному (асоціативному) обробленні значних обсягів інформації, що вимагає відповідної організації та вдосконалення технічних засобів сортування. Відомі алгоритми та засоби сортування чисел дозволяють регулювати інтенсивність виконання цього процесу та підвищувати його ефективність, використовуючи паралельні пристрої, але вони вимагають значних апаратних витрат. Тому метою подальших досліджень є розробка нових та вдосконалення відомих методів сортування з орієнтацією на зменшення апаратних витрат та збільшення швидкості цього процесу. В роботі запропоновано структурну схему сортувальника як обчислювальної частини асоціативного процесора, яка має регулярну логічну структуру і паралельно-послідовні зв'язки між блоками обробки даних. Це значно спрощує «розміщення» сортувальника в мікросхемі програмованої логічної ІС (ПЛІС). Крім того, функціонально у сортувальнику реалізовано багатофункціональність обробки числових масивів даних завдяки формуванню рангів елементів вхідного масиву. Це дозволяє визначити не тільки екстремальні елементи числового масиву, але й елемент, що займає середнє значення у відсортованому масиві, що є необхідною умовою для швидкісної медіанної фільтрації зображень. В запропонованому сортувальнику в процесі сортування використовуються швидкісні операції інкременту/декременту на масивах лічильників замість витратної за часом операції попарного порівняння паралельно для всіх елементів масиву з подальшою їх перекомутацією.

The process of sorting and selecting by key is a basic procedure in many search systems such as databases and Inter-net search systems. At the same time, modern computing tools require efficient methods and tools which are connected with associative information processing in the development of software and hardware. Therefore, there is a need for high-speed non-computational (associative) processing of large amounts of information, which requires appropriate organization and improvement of technical means of sorting. The well-known algorithms and means for number sorting make it possible to regulate the intensity of this process and increase its efficiency using parallel devices, but they require significant hardware costs. Therefore, the purpose of further research is to develop new and improve known methods of sorting with an orienta-tion on reducing hardware costs and increasing the speed of this process. In this paper, there has been proposed a block diagram of a sorter as a computational part of an associative processor, which has a regular logical structure and parallel-serial connections between data processing units. This greatly simplifies the "placement" of the sorter in a programmable logic IS (FPGA) chip. In addition, the sorter functionally implements the multifunctionality of processing numerical data ar-rays due to the formation of the ranks of the input array of elements. This allows determining not only the extreme elements of the numeric array but also the element occupying the average value in the sorted array, which is a necessary condition for high-speed median filtering of images. In the proposed sorter, the sorting process uses fast increment/decrement opera-tions on the counter arrays instead of the time-consuming operation of pairwise comparison in parallel for all arrays of ele-ments with their subsequent re-commutation.

Процесс сортировки и выборки по ключу является основной процедурой во многих поисковых системах, таких как базы данных и поисковые системы в Интернете. В то же время современные вычислительные средства требуют эффективных методов и средств, связанных с ассоциативной обработкой информации при разработке программного и аппаратного обеспечения. Поэтому возникает необходимость в высокоскоростной невычислительной (ассоциативной) обработке больших объемов информации, что требует соответствующей организации и совершенствования технических средств сортировки. Известные алгоритмы и средства сортировки чисел позволяют регулировать интенсивность выполнения этого процесса и повышать его эффективность, используя параллельные устройства, однако они требуют значительных аппаратных затрат. Поэтому целью дальнейших исследований является разработка новых и усовершенствование известных методов сортировки с ориентацией на уменьшение аппаратных затрат и увеличение скорости этого процесса. В работе предложена структурная схема сортировщика как вычислительной части ассоциативного процессора, которая имеет регулярную логическую структуру и параллельно-последовательные связи между блоками обработки данных. Это значительно упрощает «размещение» сортировщика в микросхеме программируемой логической ИС (ПЛИС). Кроме того, функционально в сортировщике реализована многофункциональность обработки числовых массивов данных благодаря формированию рангов элементов входного массива. Это позволяет определить не только экстремальные элементы числового массива, но и элемент, занимающий среднее значение в отсортирован-ном массиве, что является необходимым условием при скоростной медианной фильтрации изображений. В предлагаемом сортировщике в процессе сортировки используются быстрые операции инкремента/декремента на массивах счетчиков вместо затратной по времени операции попарного сравнения параллельно для всех элементов массива с последующей их перекоммутацией.