Proyecto Final

Proyecto final - Bubble Sort
Cristian Camilo Leon Bohorquez Luis Esteban Villamarin Tenjo Santiago Ospina Vargas
Pontificia Universidad Javeriana
Organización de Computadores
14 de mayo de 2020
Resumen
El presente informe condensa el diseño, resultados y análisis de simulación de un algoritmo de orde-
namiento tipo Bubble Sort implementado en el procesador PDUA descrito en VHDL, con el objetivo de
entender en detalle la microarquitectura de este procesador didáctico.
1. Introducción.
El procesador PDUA, implementado mediante la arquitectura Von Neumann, es un procesador de 8 bits,
con espacio de direccionamiento de 256Bytes (8 bits de dirección), con memoria y periféricos separados,
control microprogramado, manejo de interrupción externa y manejo de STACK, cuenta con cuatro unidades
principales (unidad de control, unidad operativa, banco de registros e interfaz con memoria), ha sido desa-
rrollado por la Universidad de los Andes con aportes de la Universidad Javeriana, en Bogotá, Colombia para
fines didácticos. [1] [2]
Por otro lado, el Bubble Sort¸o en español Ordenamiento de Burbuja, es un algoritmo sencillo de ordena-
miento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos
de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se
necesiten más intercambios, lo cual significa que la lista está ordenada. Viendo este algoritmo desde un alto
nivel se puede entender como dos for anidados. [3] [4] La figura 1 muestra una prueba de escritorio para este
algoritmo, en su primer paso, lo que se repite según el número de datos.
Figura 1: La primera pasada del algoritmo de Ordenamiento Burbuja, de [5]
1
En este documento se presenta el diseño (diagrama de flujo y código en lenguaje maquina) así como
la etapa de desarrollo (implementación microinstrucciones nuevas y código en lenguaje de ensamble del
algoritmo), y la etapa de análisis que condensa los resultados de simulación y las observaciones generales
sobre estos y el desarrollo completo del proyecto.
2. Diagrama de flujo Bubble Sort: considerando las restricciones y

características del PDUA.
La figura 2, muestra el diagrama de flujo para un ordenamiento por burbuja visto desde una implementa-
ción en alto nivel, sin embargo, el PDUA tiene restricciones de memoria (ROM) y no tiene microinstrucciones,
que, por ejemplo, permitieran hacer un ciclo “For” de la forma en que se muestra en dicha figura, por ello
es necesario realizar otros procesos dentro del algoritmo de ordenamiento que posibiliten, como se mencionó
previamente, ordenar 8 números de 8 bits con el procesador didáctico. El diagrama de flujo del Bubble Sort
para este procesador se muestra en las figuras 3 y 4 de este documento.
Figura 2: Diagrama de Flujo del método Bubble Sort - Alto nivel, de [6]
2
Figura 3: Diagrama de flujo Bubble Sort parte A
3
Figura 4: Diagrama de flujo Bubble Sort parte B
4
En la figura 3, parte A del diagrama de flujo, corresponde al proceso de guardar en Memoria RAM los
valores CTE que están en ROM para poder hacer el proceso de comparación y ordenamiento posterior. La
figura 4, parte A del diagrama de flujo, responde a la lógica que permite ordenar los números, mediante el
intercambio
3. Nuevas instrucciones: Justificación de cada instrucción. Mnemó-

nico y microprograma.
A continuación, se presentan las nuevas instrucciones requeridas para implementar el método de orde-
namiento. De manera particular, las instrucciones 3.1, 3.3, 3.4, 3.6 y 3.7 han sido construidas dadas las
limitaciones de espacio en la memoria ROM con el fin de hacer un algoritmo mas compacto en la memoria
mencionada. En cuanto a las instrucciones, 3.2, 3.5 y 3.8 han sido diseñadas dado que no se encontraban
en las predeterminadas del sistema y posibilitan la parte lógica que permite identificar cuando un numero
es mayor que el otro. Para las microinstrucciones 3.1, 3.3, 3.4, 3.6 y 3.7; que son las más recurrentes para
poder hacer los cambios de posición de los valores constantes que se desean ordenar. De forma que:
MOV [CTE], ACC: Permite asignar el valor de ACC a la dirección donde apunta CTE
MOV A, [CTE]: Asigna lo que esta apuntado en CTE a la variable A.
MOV ACC, [CTE]: Asigna lo que esta apuntado en CTE al acumulador.
MOV [CTE], A: Permite asignar el valor de la variable A a la dirección donde apunta CTE.
MOV [ACC], A: Permite asignar el valor de la variable A a la dirección donde apunta el acumulador.
En el caso de las instrucciones 3.2, 3.5 y 3.8, si tienen una justificación particular que responde al diseño
del logaritmo que posibilita la parte lógica del ordenamiento, de este modo:
RES ACC, A: Resta al acumulador el valor de la variable A, lo que permite identificar cual número es
mayor, según si es negativo o positivo el resultado (ACC = ACC – A).
INC [CTE]: Incrementa el valor de CTE, lo que permite llevar el control de los ciclos, aumentado i o j,
que corresponden al indicador de cada uno los ciclos “anidados” que recorren los números para compararlos
y ordenarlos.
JUMCOMP DIR: Esta microinstrucción complementa las dos anteriores y posibilita que el rango de
valores admitidos para ordenar este entre −12710 y 12710 , allí se realizan saltos según:
Si hay overflow negativo (sumar dos negativos), implica un salto para la instrucción. No intercambia.
Si no hay overflow y el resultado es negativo, implica un salto para la instrucción. No intercambia.
Si hay overflow positivo (sumar dos positivos), no implica un salto para la instrucción. Intercambia.
Si no hay overflow y el resultado es positivo no implica un salto para la instrucción. Intercambia.
En los numerales 3.1 a el 3.8, se muestran las microinstrucciones y más adelante los resultados de simu-
lación.
3.1. MOV [CTE], ACC

when "10000000" => UI <= "000000000XXX0100101000XXX"; -- MAR = PC, RD MREQ
when "10000001" => UI <= "0000110000001000101000XXX"; -- PC = PC + 1, RD MREQ
when "10000010" => UI <= "0000000000101010101000XXX"; -- DTPR = DATA, RD MREQ, Reset UPC
when "10000011" => UI <= "001000000XXX0100101000XXX"; -- MAR=DPTR
when "10000100" => UI <= "111100000XXX0011100000XXX"; -- MDR = ACC, WR MREQ, RST UPC
when "10000101" => UI <= "XXXXXXXXXXXXXXXXXXXXXXXXX";
5
3.2. RES ACC, A
when "10001000" => UI <= "0011111000111000001000XXX"; -- COMP A
when "10001001" => UI <= "1011101001111000000000XXX"; -- ACC = ACC + COMPA
3.3. MOV A, [CTE]

when "10010010" => UI <= "0000000000101010101000XXX"; -- DPTR = DATA, RD MREQ, Reset UPC
when "10010011" => UI <= "001000000XXX0100101000XXX"; -- MAR = DPTR, RD MREQ
when "10010100" => UI <= "0XXXXXXXX0111010100000XXX"; -- MDR=DEX,RD MREQ,A=MDR,RST UPC
3.4. MOV ACC, [CTE]

when "10111100" => UI <= "0XXXXXXXX1111010100000XXX"; -- MDR=DEX,RD MREQ,ACC=MDR,RST UPC
3.5. INC [CTE]

when "11000100" => UI <= "0XXXXXXXX1111010101000XXX"; -- MDR=DEX, RD MREQ, ACC=MDR, RST UPC
when "11000101" => UI <= "1111110001111000001000XXX";
when "11000111" => UI <= "111100000XXX0011100000XXX"; -- MDR = ACC, WR MREQ, RST UPC
3.6. MOV [ACC], A

when "11001000" => UI <= "1111000000101000001000XXX"; -- DPTR = ACC , Reset UPC
when "11001001" => UI <= "001000000XXX0100101000XXX";
when "11001010" => UI <= "101100000XXX0011100000XXX";
3.7. MOV [CTE], A

when "11010010" => UI <= "0000000000101010101000XXX"; -- DTPR = DATA, RD MREQ, Reset UPC
when "11010100" => UI <= "101100000XXX0011100000XXX"; -- MDR = A, WR MREQ, RST UPC
6
3.8. JUMCOMP DIR
when "11011000" => UI <= "0XXXXXXXXXXX0000001111011"; -- JO 011
when "11011001" => UI <= "0XXXXXXXXXXX0000001011100"; -- JN 100
when "11011010" => UI <= "0000110000001000000000XXX"; -- PC=PC+1,si intercambia
when "11011011" => UI <= "0XXXXXXXXXXX0000001011010"; -- JN 010
when "11011100" => UI <= "000000000XXX0100101000XXX"; -- MAR = PC,RD MREQ, no intercambia
when "11011101" => UI <= "0XXXXXXXX0001010100000XXX"; -- MDR=DEX,RD MREQ,PC=MDR,RST UPC
4. Simulación de las microinstrucciones

VHDL de Mover a memoria y traer de memoria con registros
when "0000000" => data <= "01010000"; -- JMP MAIN
when "0000001" => data <= "00000011"; -- MAIN
when "0000010" => data <= "00001000"; -- RAI Vector de Interrupcion
when "0000011" => data <= "00011000"; -- MOV ACC,CTE
when "0000100" => data <= "00000001"; -- (0x01)
when "0000101" => data <= "10000000"; -- MOV [CTE],ACC
when "0000110" => data <= "10000010"; -- (0x82)
when "0001000" => data <= "00000110"; -- (0x06)
when "0001010" => data <= "10000011"; -- (0x83)
when "0001011" => data <= "10111000"; -- MOV ACC,[CTE]
when "0001100" => data <= "10000010"; -- (0x82)
when "0001101" => data <= "10010000"; -- MOV A,[CTE]
when "0001110" => data <= "10000011"; -- (0x83)
when "0001111" => data <= "01001000"; -- ADD ACC,A
when "0010000" => data <= "01010000"; -- JMP DIR
when "0010001" => data <= "00010000"; -- (0x10)
when "0010010" => data <= "00000000"; --
when "0010011" => data <= "00000000"; --
Figura 5: Mover a memoria y traer de memoria con registros
7
La figura 5 nos permite observar los resultados de simulación para las microinstrucciones MOV [CTE],
ACC, MOV [CTE], A, MOV ACC, [CTE] y MOV A, [CTE]. Es posible observar, que, por ejemplo, en la
dirección 0x04, el acumulador (ACC) ha tomado el valor de la constante 0x01, según las indicaciones del
código de la ROM y que posteriormente ese valor es almacenado en la posición de memoria 0x82; cumpliendo
con la microinstrucción MOV[CTE], ACC. Así mismo, luego es asignado a CTE el valor de 0x06, que es mo-
vido ahora a la posición de memoria 0x83, para luego mover el valor de la dirección anterior al acumulador,
lo que ocurre cuando PC apunta a la dirección 0x09 de la ROM, cumpliendo con la microinstrucción MOV
ACC, [CTE]. Finalmente, en la dirección de la ROM 0x0D se observa como el valor que estaba contenido
en la posición de memoria 0x83 es ahora movido a la variable A, quedando esta última con el valor 0x06 y
cumpliendo la microinstrucción MOV A, [CTE].
VHDL de JUMCOMP DIR

when "0000001" => data <= "00000011"; -- MAIN
when "0000011" => data <= "00011000"; -- INICIO: MOV ACC,CTE
when "0000100" => data <= "01000110"; -- (0x46) 70
when "0000110" => data <= "10000010"; -- (0x82)
when "0001000" => data <= "01100100"; -- (0x64) 100
when "0001010" => data <= "10000011"; -- (0x83)
when "0001100" => data <= "11000000"; -- (0xC0) -64
when "0001110" => data <= "10000100"; -- (0x84)
when "0010000" => data <= "10000100"; -- (0x84) Carga -64
when "0010010" => data <= "10000010"; -- (0x82) Carga 70
when "0010011" => data <= "10001000"; -- RES ACC,A Overflow N
when "0010100" => data <= "11011000"; -- JUMCOMP DIR
when "0010101" => data <= "00100110"; -- DIR 1 (0x26)
when "0010110" => data <= "10111000"; -- DIR 2: MOV ACC,[CTE]
when "0010111" => data <= "10000010"; -- (0x82) Carga 70
when "0011001" => data <= "10000100"; -- (0x84) Carga -64
when "0011010" => data <= "10001000"; -- RES ACC,A Overflow P
when "0011100" => data <= "00000011"; -- INICIO
when "0011110" => data <= "10000011"; -- (0x83) Carga 100
when "0100000" => data <= "10000010"; -- (0x82) Carga 70
when "0100001" => data <= "10001000"; -- RES ACC,A Normal
when "0100011" => data <= "00000000"; -- INICIO
when "0100100" => data <= "01010000"; -- JMP DIR
when "0100101" => data <= "00101101"; -- FIN
when "0100110" => data <= "10111000"; -- DIR 1: MOV ACC,[CTE]
8
when "0100111" => data <= "10000010"; -- (0x82) Carga 70
when "0101001" => data <= "10000011"; -- (0x83) Carga 100
when "0101010" => data <= "10001000"; -- RES ACC,A Negativa
when "0101100" => data <= "00010110"; -- DIR 2 (0x16)
when "0101101" => data <= "00000000"; -- FIN
when "0101110" => data <= "00000000"; --
Figura 6: Cargar datos
Para revisar en detalle que la microinstrucción JMPCOMP DIR funciona correctamente, es necesario
hacer un algoritmo en la ROM mas extenso que en los casos anteriores y revisar casos particulares. Primero
es importante realizar una asignación de valores constantes a direcciones de la memoria RAM, eso ocurre en
las primeras líneas de código de la ROM, de forma que en la dir 0x0F los valores ya están cargados en las
posiciones 0x82,0x83 y 0x84 con los valores 70, 100 y -64, respectiva; como se puede ver en la figura 6.
Figura 7: Overflow negativo
9
La figura 7, muestra el caso en el que ocurre un overflow negativo, esto es sumar dos valores negativos
y para ello se carga el -64 en el ACC y el 70 en A, se realiza la microinstrucción RES ACC, A; obteniendo
un 122 cargado al ACC, que es un resultado positivo, por lo que el overflow representado en la variable O es
un 1 y la bandera de negativos es un 0. Hasta ahora se ha comprobado que las banderas N (indica resultado
negativo), que 0 (si hay overflow o no) y que, la microinstrucción de RES ACC, A; realiza su función.
Figura 8: Operación normal resultado negativo
La figura 8, muestra, con el mismo procedimiento anterior, con la salvedad de que ahora el 70 es cargado
en el ACC y el -64 en A, se usa RES ACC, A; obteniendo un -122, ahora los dos números son positivos,
la respuesta es negativa y hay overflow como lo muestran las banderas N y O, mencionadas en el párrafo
anterior.
Figura 9: Overflow positivo
Finalmente, la figura 9 presenta un caso normal, es decir, donde no se activan las banderas N ni O y el
resultado de RES ACC, A es positivo, en este caso 3010 , para unos valores cargados previamente de A igual
a 70 y ACC a 100.
10
Figura 10: Operación normal resultado positivo
El análisis anterior da cuenta del funcionamiento de la microinstrucción RES ACC, A y de JMPCOMP

DIR, con la particularidad en esta última de que muestra los cuatro casos mencionados en la justificación
de dicha microinstrucción.
VHDL de MOV[ACC],A

when "0000001" => data <= "00000011"; -- MAIN
when "0000100" => data <= "10000000"; -- (0x80)
when "0000110" => data <= "10000001"; -- (0x81)
when "0001000" => data <= "00000011"; -- (0x03)
when "0001010" => data <= "10000010"; -- (0x82)
when "0001100" => data <= "10000001"; -- (0x81)
when "0001110" => data <= "10000010"; -- (0x82)
when "0001111" => data <= "01001000"; -- ADD ACC,A
when "0010000" => data <= "11001000"; -- MOV [ACC],A
when "0010001" => data <= "10010000"; -- JMP DIR
when "0010010" => data <= "00010001"; -- (0x11)
11
Figura 11: MOV [ACC],A
La figura 11 , permite ver el proceso de prueba de la microinstrucción MOV [ACC], A. En esta figura,
primero se ve la asignación de la constante 0x80 al ACC para luego moverla a la posición de memoria 0x81,
y de la misma forma la constante 0x03 a la posición 0x82; con dichas asignaciones que ocurren hasta llegar
al dir 0x0A, se asigna al acumulador el valor contenido en la dirección 0x81, en este caso un −12810 , luego,
es movido el valor contenido en la dirección 0x82, en este caso un 310 a A, para ser sumado al ACC en la dir
0x0F(obteniendo un 0x83), evidenciando en la dirección 0x11, que ya ha sido asignado el valor de A (0x03)
en la dirección de memoria según el nuevo ACC (0x83); cumpliendo con la microinstrucción MOV [ACC],A.
VHDL de Incrementar [CTE]

when "0000001" => data <= "00000011"; -- MAIN
when "0000100" => data <= "01000110"; -- (0x46) 70
when "0000110" => data <= "10000010"; -- (0x82)
when "0000111" => data <= "11000000"; -- INC [CTE]
when "0001000" => data <= "10000010"; -- (0x82)
when "0001001" => data <= "01010000"; -- JMP DIR
when "0001010" => data <= "00001001"; -- (0x09)
when "0001011" => data <= "00000000"; --
when "0001100" => data <= "00000000"; --
12
Figura 12: Incrementar [CTE]
En la figura 12 podemos observar el resultado de implementar el código ROM de prueba para la micro-
instrucción. Allí se puede observar que luego de asignar un valor de 7010 en la posición de memoria 0x82,
se usa la microinstrucción en la dirección de la ROM 0x07, para aumentar lo que está en la dirección de
memoria mencionada, el resultado exitoso de este proceso se ve después del que el dir se encuentra en 0x02.
5. Código en lenguaje de ensamble y máquina del algoritmo Bubble

Sort: debidamente comentado.
when "0000001" => data <= "00001011"; --MAIN
when "0000010" => data <= "00001000"; --RAI Vector de Interrupcion
when "0000011" => data <= "01100101"; --CTE0(0x65) 101
when "0000100" => data <= "11010001"; --CTE1(0xD1) -47
when "0000101" => data <= "01101000"; --CTE2(0x68) 104
when "0000110" => data <= "01100000"; --CTE3(0x60) 96
when "0000111" => data <= "11011001"; --CTE4(0xD9) -39
when "0001000" => data <= "01110111"; --CTE5(0x77) 119
when "0001001" => data <= "11000000"; --CTE6(0xC0) -64
when "0001010" => data <= "11001010"; --CTE7(0xCA) -54
when "0001011" => data <= "00011000"; --MOV ACC,CTE
when "0001100" => data <= "00000000"; --(0x00)
when "0001101" => data <= "10000000"; --MOV [CTE],ACC
when "0001110" => data <= "10000001"; --(0x81)
when "0010000" => data <= "00000001"; --(0x01)
when "0010010" => data <= "10000010"; --(0x82)
when "0010100" => data <= "00001000"; --(0x08)
when "0010110" => data <= "10000011"; --(0x83)
13
when "0011000" => data <= "00000011"; --(0x03)
when "0011001" => data <= "01110000"; --CALL
when "0011010" => data <= "01110011"; --(0x73)
when "0011100" => data <= "10000110"; --(0x86)
when "0011101" => data <= "10010000"; --MOV A,[CTE]
when "0011110" => data <= "10000001"; --(0x81)
when "0011111" => data <= "01001000"; --ADD ACC,A
when "0100001" => data <= "10000100"; --(0x84)
when "0100010" => data <= "11001000"; --MOV [ACC],A
when "0100011" => data <= "11000000"; --INC [CTE]
when "0100100" => data <= "10000001"; --(0x81)
when "0100101" => data <= "00100000"; --MOV ACC,[DPTR]
when "0100111" => data <= "10000011"; --(0x83)
when "0101000" => data <= "10001000"; --RES ACC,A
when "0101001" => data <= "01100000"; --JN DIR
when "0101010" => data <= "00010111"; --(0x17)
when "0101100" => data <= "00000000"; --(0x00)
when "0101110" => data <= "10000001"; --(0x81)
when "0110000" => data <= "10000110"; --(0x86)
when "0110001" => data <= "01110000"; --CALL
when "0110010" => data <= "01110011"; --(0x73)
when "0110100" => data <= "10000110"; --(0x86)
when "0110110" => data <= "10000010"; --(0x82)
when "0111000" => data <= "00101000"; --MOV DPTR,ACC
when "0111011" => data <= "10000101"; --(0x85)
when "0111100" => data <= "10111000"; --MOV ACC,[CTE]
when "0111101" => data <= "10000100"; --(0x84)
when "0111111" => data <= "10000101"; --(0x85)
when "1000001" => data <= "11011000"; --JUMCOMP DIR
when "1000010" => data <= "01011010"; --(0x5A)
when "1000100" => data <= "10000100"; --(0x84)
when "1000110" => data <= "10000101"; --(0x85)
when "1000111" => data <= "00110000"; --MOV [DPTR],ACC
when "1001000" => data <= "11010000"; --MOV [CTE],A
when "1001001" => data <= "10000100"; --(0x84)
14
when "1001011" => data <= "10000110"; --(0x86)
when "1001101" => data <= "10000001"; --(0x81)
when "1010000" => data <= "10000100"; --(0x84)
when "1010011" => data <= "10000110"; --(0x86)
when "1010101" => data <= "10000010"; --(0x82)
when "1011000" => data <= "10000101"; --(0x85)
when "1011010" => data <= "11000000"; --INC [CTE]
when "1011011" => data <= "10000010"; --(0x82)
when "1011110" => data <= "10000011"; --(0x83)
when "1100000" => data <= "01100000"; --JN DIR
when "1100001" => data <= "00110011"; --(0x33)
when "1100010" => data <= "11000000"; --INC [CTE]----> I
when "1100011" => data <= "10000001"; --(0x81)
when "1100101" => data <= "10000001"; --(0x81)
when "1100111" => data <= "10000010"; --(0x82)
when "1101000" => data <= "11000000"; --INC [CTE]----> J
when "1101001" => data <= "10000010"; --(0x82)
when "1101011" => data <= "10000010"; --(0x82)
when "1101101" => data <= "10000011"; --(0x83)
when "1101111" => data <= "01100000"; --JN DIR
when "1110000" => data <= "00101111"; --(0x2F)
when "1110001" => data <= "01010000"; -- JMP DIR
when "1110010" => data <= "01110001"; --(0x71)
when "1110100" => data <= "10000001"; --(0x81)
when "1110110" => data <= "00101000"; --MOV DPTR,ACC
when "1111001" => data <= "10000100"; --(0x84)
when "1111010" => data <= "01111000"; --RET
when "1111011" => data <= "00000000"; --
when "1111100" => data <= "00000000"; --
when "1111101" => data <= "00000000"; --
15
when "1111110" => data <= "00000000"; --
when "1111111" => data <= "00000000"; --
6. Simulaciones del algoritmo Bubble Sort y análisis de resultados.

A continuación se mostrara el resultado de la simulaciones usando el método de Bubble Sort
Figura 13: Inicialización
En la figura 13 podemos observar cómo se inicializan las variables I, J y N* donde I toma un valor de
0 en la posición del DPTR en ese instante tiene un valor de 0x81 de la misma manera se inicializa J con
un valor inicial de 1 en el espacio de memoria 0x82 y N* un valor de 8 en la posición 0x83, como se ve
mas adelante se carga el primer dato de CTE que se va a guardar en la RAM para después ser organizados
usando el método “Bubble Sort”
Figura 14: Guarda el valor de CTE
En la figura 14 podemos observar la variable A contiene un valor de 10110 y procederá a guardar en otro
espacio de la RAM los valores escritos en la ROM entre las direcciones 0x86 a 0x8D, después de guardado
el valor en su posición correspondiente aumentamos el valor de I para así ir llamando las contantes e ir
guardándolas en la RAM
16
Figura 15: Guarda el segundo valor
En la figura 15 podemos observar la variable A contiene un valor de 10110 y procederá a mirar que valor
esta guardado en 0x87( −4710 ) y procederá a ser guardado en la posición 0x85 (variable B)
Figura 16: A mayor a B
En la figura 16 podemos observar la variable A contiene un valor de 10110 y la variable B un valor de

−4710 , en esta parte de la simulación se resta A con B, como B tiene un valor negativo se realiza la suma y
se mira si se necesita hacer el cambio entre A y B como si se tiene que hacer el cambio por que A es mayor
a B se van a invertir los valores donde A toma el valor de B y de la misma manera B toma el valor de A y
a continuación se agrega en la primera posición 0x86 donde se van a ir guardando y acomodando.
17
Figura 17: A menor a B
En la figura 17 podemos observar la variable A contiene un valor de −4710 y la variable B un valor de

9610 , en esta parte de la simulación se resta A con B, debido a esto el ACC toma un valor negativo y se
activa la Bandera N y no hay un carry eso indica que el valor de A es menor que B entonces no se tiene que
hacer cambio; se procede a aumentar J y llamar el siguiente valor.
Figura 18: Aumenta el valor de I
En la figura 18 podemos observar la variable I aumenta y J de la misma manera aumenta comparando

en la siguiente posición este proceso se realiza cada vez que A compara con todos los valores que toma B.
18
Figura 19: Ordenados
En la figura 19 podemos observar como se agrega el ultimo dato y dando como resultado todos los Datos
están organizados de mayor a menor entre 0x86 a 0x8D
Como se puede observar, este proceso de ordenamiento tarda alrededor Como se puede observar, todo el
proceso tarda alrededor de unos 7.2ms, y es un tiempo constante i
7. Conclusiones
Las características y/o limitaciones del PDUA propone la simplicidad o reducción de las líneas de código
de la ROM, en este caso motivo la creación de otras microinstrucciones que se podían implementar con
las predeterminadas, pero que superaban las (1111111)2 instrucciones que soporta en su arquitectura.
Debido a que PDUA trabaja con complemento a2 y el método utilizado para determinar la posición
era con el negativo, fue necesario implementar una microinstrucción que permitiera “tomar decisiones”
de acuerdo con cada uno de los casos posibles de overflow, como se mencionó en la justificación de la
microinstrucción JMPCOMP DIR.
Se cumplió con el objetivo de ordenar 8 números de 8 bits, en el rango de −12710 a 12710 , e implico la
implementación de 7 nuevas microinstrucciones.
Referencias
[1] J. P. Contreras Franco, «Modelado y Verificación de Hardware Usando Tipos Abstractos de Datos,»
Universidad De Los Andes, Bogotá, 2009.
[2] P ontif iciaU niversidadJaveriana, DiapositivasP rocesadorP DU A, Bogot, 2020.

[3] EcuRed, ´ECU RED, ˇ2012.[Enlnea].Available : https : //www.ecured.cu/Ordenamientod eb urbuja
[4] GeeksF orGeeks, ´GeeksF orGeeks, ˇ[Enlnea].Available : https : //www.geeksf orgeeks.org/bubble −
sort/.
[5] RunestoneAcademy, ´RunestoneAcademy, ˇ[Enlnea].Available : https :

//runestone.academy/runestone/static/pythoned/SortSearch/ElOrdenamientoBurbuja.html.
19
[6] Developer0 sAdda, ´Developer0 sAdda, ˇAgosto2016.[Enlnea].Available : https :
//developersadda.wordpress.com/bubble − sort/.
20

Proyecto Final

Cargado por

Copyright:

Formatos disponibles

Proyecto Final

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Proyecto Final

Cargado por

Copyright:

Formatos disponibles

Proyecto final - Bubble Sort

Figura 1: La primera pasada del algoritmo de Ordenamiento Burbuja, de [5]

2. Diagrama de flujo Bubble Sort: considerando las restricciones y

3. Nuevas instrucciones: Justificación de cada instrucción. Mnemó-

3.1. MOV [CTE], ACC

3.3. MOV A, [CTE]

3.4. MOV ACC, [CTE]

3.5. INC [CTE]

3.6. MOV [ACC], A

3.7. MOV [CTE], A

4. Simulación de las microinstrucciones

Figura 5: Mover a memoria y traer de memoria con registros

VHDL de JUMCOMP DIR

when "0000000" => data <= "01010000"; -- JMP MAIN

Figura 6: Cargar datos

Figura 7: Overflow negativo

Figura 8: Operación normal resultado negativo

Figura 9: Overflow positivo

El análisis anterior da cuenta del funcionamiento de la microinstrucción RES ACC, A y de JMPCOMP

when "0000000" => data <= "01010000"; -- JMP MAIN

VHDL de Incrementar [CTE]

when "0000000" => data <= "01010000"; -- JMP MAIN

5. Código en lenguaje de ensamble y máquina del algoritmo Bubble

6. Simulaciones del algoritmo Bubble Sort y análisis de resultados.

Figura 13: Inicialización

Figura 14: Guarda el valor de CTE

Figura 16: A mayor a B

En la figura 16 podemos observar la variable A contiene un valor de 10110 y la variable B un valor de

En la figura 17 podemos observar la variable A contiene un valor de −4710 y la variable B un valor de

Figura 18: Aumenta el valor de I

En la figura 18 podemos observar la variable I aumenta y J de la misma manera aumenta comparando

[2] P ontif iciaU niversidadJaveriana, DiapositivasP rocesadorP DU A, Bogot, 2020.

[5] RunestoneAcademy, ´RunestoneAcademy, ˇ[Enlnea].Available : https :

También podría gustarte