RELATÓRIO DE IMPLEMENTAÇÃO DO ALGORITMO BUBBLESORT EM ASSEMBLY

Relatorio Implementação do algoritmo Bubble Sort em Assembly

Introdução

Neste relatório será demonstrado as modificações e otimização do tempo de execução no algoritmo bubble sort implementado em linguagem Assembly, fazendo as devidas comparações com a devida versão do algoritmo em C além de especificar as mudanças que ocorreram no algoritmo para que a melhora no tempo de execução fosse feita.

Modificações feitas no algoritmo

Como o intuito do algoritmo feito em assembly é a melhora no desempenho , algumas modificações foram feitas que possibilitou uma significativa melhora no tempo de execução do Bubble Sort.

        A primeira modificação foi que, as comparações entre os elementos que seriam ordenados , foi feita dentro dos registradores , assim como a troca de posição desses elementos , isso garantiu , que toda comparação fosse feita dentro do processador , eliminando o tempo que isso seria feito se os elementos fossem comparados na memória, Além disso, o processo de troca de elementos foi feito utilizando operações bit a bit entre os elementos, isso possibilitou que , com apenas 2 registradores , as trocas de elementos fossem feitas sem a necessidade de uma variável auxiliar para a realização da troca , influenciando ainda mais num ganho considerável de desempenho no algoritmo.

        A segunda modificação foi que, os elementos que se encontravam na memória, eram lidos e gravados em registradores, e após a realização da troca (ou não) desses elementos, os mesmos eram gravados novamente na memória. Inicialmente é obtido o valor do primeiro elemento através de passagem de parâmetros via ponteiros, após isso, somente um acesso à memória era necessário para pegar o próximo elemento a ser comparado e após essa comparação, o menor elemento é gravado na memória e é lido o próximo elemento. Importante relatar que, é utilizado um ponteiro para percorrei o vetor de elementos , de forma que, após fazer a comparação e se necessário a troca, o ponteiro avança sobre esse vetor , de forma a fazer a comparação sobre outro índice, dessa forma , será garantido que , ao final das iterações do algoritmo , o maior elemento seja colocado na última posição do vetor, garantindo que a última posição do vetor estará o maio elemento desse vetor, e como está sendo feito apenas acessos e escritas na memória que são necessárias para a ordenação ser feita corretamente, o tempo de execução também será diminuído.

        Vale ressaltar que, o registrador de topo de pilha (%esp) foi utilizado como ponteiro para percorrer o vetor de elementos, isso não trouxe implicações para o programa pois não foi utilizado a pilha para guardar variáveis locais, chamar funções auxiliares ou salvar estados de registradores. Os acessos à memória foram reduzidos de forma a obter o máximo de desempenho no algoritmo. Para garantir que não houvesse nenhum problema com chamada de funções ou que os valores guardados na pilha fossem perdidos, o registrador de base da pilha (%ebp) e estado de %esp inicial são salvos no início do programa e ao final são restaurados, dessa forma, o estado dos registradores e o fluxo de controle de outras funções não são alterados e ao final de uma chamada do programa, nenhuma outra função é prejudicada.

...