Global Sources
EE Times-India
EE Times-India > EDA/IP

Employ sort algorithms on DSPs

Posted: 24 Mar 2009     Print Version  Bookmark and Share

Keywords:sort algorithms  cycle counts  Blackfin processor 

In this article, we present the bubble sort and merge sort algorithms. We discuss the cycle counts of these algorithms on the Blackfin processor, and show how to reduce the cycle count of the bubble sort and merge sort algorithm. In addition we look at methods to accelerate the sorting of data that is wider than the register width of the processor.

Standard algorithm cookbooks provide dozens of number-sorting algorithms. Though the sorting algorithms are simple from a mathematical point of view, they can be time consuming to perform on DSPs due to their non-linear computational complexity and the presence of many control operations in their execution. Usually, we specify the complexity of an algorithm using the notation O(.), which indicate 'the order of'. For example, the complexity of sorting N numbers using the bubble sort method is O(N2) and using merge sort method is O(NlogN). This doesn't mean we consume N2 and NlogN processor clock cycles in executing those algorithms to perform sorting. However, we can say that we consume about xN2 and yNlogN cycles (excluding the overhead), where the efficiency factors x and y depend on the particular processor architecture, software code, algorithm flow, etc. used to execute the algorithm.

View the PDF document for more information.

Comment on "Employ sort algorithms on DSPs"
*  You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.


Go to top             Connect on Facebook      Follow us on Twitter      Follow us on Orkut

Back to Top