МЕТОД ОПТИМІЗАЦІЇ АЛГОРИТМУ ШВИДКОГО СОРТУВАННЯ ДЛЯ СИСТЕМ НА ПЛІС

Abstract

Задача сортування та алгоритми, що можуть бути застосовані для її вирішення, є загальновідомою і розглядається у великій кількості фундаментальних джерел. Деякі із зазначених алгоритмів застосовуються частіше за інші і їх оптимізація стала темою для відомих робіт в області комп’ютерних алгоритмів. Використовувані натепер реалізації цих алгоритмів рідко потребують подальшої програмної оптимізації. Але залишається можливість їх апаратної оптимізації, особливо, у разі використання таких алгоритмів у системах на програмованих кристалах. Такі системи вирізняються наявністю апаратних ресурсів, що можуть видозмінюватися за потребою розробника системи. У даній статті запропоновано та досліджено метод оптимізації загальновідомого алгоритму швидкого сортування із використанням апаратних ресурсів ПЛІС FPGA для застосування в рамках розгорнутої на ній системи на ПЛІС.The sorting problem and its solutions are well-known and considered in a number of fundamental sources. Some of appropriate algorithms are used more frequently then others. But still there is a possibility of optimizing these algorithms by the use of hardware, especially, when we use the FPGAs. Such systems allow a designer to configure hardware in accordance with his demands. In this article we propose an optimization method for the well-known quick sort algorithm. This method is based on the usage of FPGA’s reconfigurable resources. It is applicable for modern SoPC which are deployed on these FPGAs.