Defining Sorting Algorithm : Using Content Adressable Memory and Parallel Comparisons

A sorting algorithm is an algorithm that puts elements of a list in a certain order.The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:

-The output is in non decreasing order (each element is no smaller than the previous element according to the desired total order);

-The output is a permutation (reordering) of the input.

-Sorting is one of the key functions
required for many applications such as decoders for digital communication, digital signal processing, VLSI CAD etc. As a consequence,there is tremendous interest in speeding up sorting in software as well as hardware.

-The time taken in the sorting depends on number of words in case of software algorithms The improvement we’re trying to make in this project is to make the time dependent upon the number of bits per word k and not the number of words

This algorithm implements sorting using a Content Addressable Memory (CAM).

Let us consider a content addressable memory having word length k+log2n.

Here k is the number of bits which contain a binary word and n is the number of words to be sorted. These binary words having a k bit representation are sorted. Along with the k bits representing the word, log2n bits store the rank of each word in the sorted pool of data. These log2n bits are the bits by which words may be accessed in order of their ranks.

1. Out of the n words to be sorted, each word is compared with the remaining n-1 words. This would require nC2 k bit comparators.

2. For each word ai>aj (0aj Di gets an input 1 from Cij ,and,Dj gets an input 0 from Cij.

3. The combinational circuit Di adds the total number of 1’s entering it and gives an output corresponding to it.This output can have a maximum value of n. Thus this output needs a binary representation of log2n bits as mentioned earlier.

4. The output of Di is the rank of the unsigned binary word ai.A word ai is higher than a word aj in rank if and only if ai>aj.

5. Each word may be accessed with reference to its rank by using the rank field associated with the word as the search parameter in the CAM.

-This algorithm implements sorting of unsigned binary numbers using a Content Addressable memory in tandem with a combinational circuit and k bit comparators. As a result of using comparators and combinational circuits Di for processing,, the circuit completes the process of sorting in 1 clock cycle. It may be mentioned that the clock cycle is subject to timing constraints due to the non-ideal nature of the logic circuitry used

Presented here, is the simulation of the entire sorting machine designed to implement the algorithm. It may be seen that the RTL Schematic shows the comparator stages followed by the rank calculators followed by the MUX to select the rank to be displayed. The main module ,on each high level of the clock input, takes in 8 inputs and stores them in the memory. Then, the rank of each data element is computed and fed back to the rank fields in the memory used. The tool used to simulate the behavioural model of the circuit was Isim bundled with Xilinx ISE 13.2.