Parallel buble sorter

Function Description

A ordenação de números em hardware é um processo interessante que pode se tornar extremamente útil, pois a maioria dos algoritmos necessita de dados ordenados.
Este circuito realiza o buble sort de forma paralela utilizando registradores e comparadores, além de algumas portas lógicas.
O dispositivo em escada, inicialmente proposto por Leiserson, implementa uma fila de prioridade em hardware. Nesta, o tempo de ordenação é constituido do tempo de entrada dos elementos e da imediata saída destes ordenados.


(fig. 1)

As linhas diagonais na fig. 1 representam os comparadores e as caixas são os valores a serem ordenados (registradores por exemplo).


(fig. 2)


A fig. 2 exemplifica o que é feito dependendo dos resultados das comparações.
 

Vale lembrar para ordenar n números de b bits, precisamos de 2 n "caixas"  de b bits cada.

Outros detalhes de implementação devem ser observados em outras fontes bibliográficas.

Existe ainda uma proposta de implementação "bit slice", onde cada uma dessas caixinhas (de b bits cada) seria implementada com caixinhas menores de 1 bit, fazendo com que o circuito se torne tão expansível quanto quisermos (bastaria adicionar mais caixinhas de 1 bit).
 
 

Implementação na placa Altera
 

Para ser possível a implementação na placa altera, temos as seguintes considerações: