Bolsa-Problemas-2024

Primer Proyecto de Arquitectura de Computadoras.

Facultad de Matemática y Computación
Universidad de La Habana
Curso 2024

Consideraciones Generales

Este proyecto consiste en dar solución a problemas computacionales utilizando Máquinas de Estados Algorítmicas (ASM) empleando circuitos simulados en Logisim, y utilizando el Lenguaje Ensamblador NASM.

Según el ejercicio indiciado se debe hacer dos implementaciones:

• La primera consistirá en una ASM que se debe implmentar sobre la plantilla BigASM.

• La segunda implementación consiste en generar un archivo .asm con el código en ensamblador NASM que dé solución al problema.

Se deben tener en cuenta las consideraciones generales para Logisim y NASM dadas en este documento, y las consideraciones particulares por cada uno de los problemas.

IMPORTANTE: Por cada ejercicio debe entregar la solución en seudocódigo, la solución en Logisim (basado en la plantilla), y la solución en esnamblador (.asm). Sin embargo, puede incluir los diagramas de flujo de la Máquina de Estados Algorítmica, e incluso las Tablas de Asignaciones.

Logisim

Se dispondrá de una plantilla en Logisim para realizar la implemetación de la Máquina de Estados Algorítmica. Queda prohibida la modficación de cualquiera de los circuitos salvo BIG ASM, en cuyo caso sí se deben respetar las entradas y salidas dadas. Además NO puede utilizar las componentes RAM, ni ROM, así como los circuitos INPUT y MEMORY. Una vez que termine la ejecución del programa debe activar la salida END (como se explicará más adelante), y mantener dicho esta persistente hasta que se haga un reinicio manual.

Esta plantilla cuentas con 4 circuitos principales, y 3 secundarios que se explicarán a continuación.

Circuitos Principales

Los circuitos principales que se usarán para la implementación de la ASM son:

• INPUT: Una memoria de solo lectura con los datos de entrada para el circuito. Cada dirección de memoria indiza una palabra de tamaño de 4 bytes (32 bits). Las direcciones de memoria son de 24 bits; por lo tanto se tienen $2^{24}$ datos de 32 bits almacenados.

• MEMORY: Una memoria de lectura y escritura. Tiene las mismas características que la memoria INPUT, solo que también permite guardar información.

• BOARD BIG ASM: Circuito que integra las componentes INPUT, MEMORY, y BIG ASM, con una pantalla. En esta última se debe proyectar la salida de la Máquina de Estados Algorítmica que se implemente.

• BIG ASM: Circuito de la Máquina de Estado Algorítmica que se debe implementar. Solo tiene definida cada una de las entradas y salidas.

  • DIR INPUT: Salida de 24 bits. Dirección del dato de la Memoria INPUT que se desea leer.
  • DATA INPUT: Entrada de 32 bits. Dato en la dirección que indica DIR INPUT, almacenado en la Memoria INPUT.
  • DIR MEMORY: Salida de 24 bits. Dirección en la Memoria MEMORY, de la palabra en donde se desea escribir o se desea leer.
  • Write MEMORY: Salida de 1 bit. Indica si se desea escribir en MEMORY (1), o si se desea leer de MEMORY (0).
  • MEMORY OUT: Salida de 32 bits. Dato que se desea guardar en la dirección DIR MEMORY de MEMORY.
  • MEMORY IN: Entrada de 32 bits. Dato en la dirección que indica DIR INPUT, almacenado en MEMORY.
  • ASCII: Salida de 7 bits. Caracter del sistema ASCII que se desea imprimir por la pantalla.
  • Write ASCII: Salida de 1 bit. Indica si se desea escribir en pantalla en carcater que está en ASCII (1), o si no se desea imprimir nada (0).
  • END: Salida de 1 bit. Indica si el programa ya terminó (1), o si aún no lo ha hecho (0).
  • CLR: Entrada de 1 bit. Clásico Reset. Reinicia el sistema. Además mientras se mantenga en (1) no debe empezar la ejecución de la máquina. Cuando cambia a (0) debe comenzar la ejecución.
  • CLK: Entrada de 1 bit. Entrada del Reloj.

En INPUT siempre se dispondrá de los valores inciales, y se asegura que serán consistentes para cada problema. Debido a la estructura de INPUT, se añade la siguiente notación para hacer referencia a cada palabra en dicha memoria.

• $w_i$: indica la palabra (de tamaño 4 bytes), que se encuentra en la dirección $i$ de la memoria INPUT.
• $w_{i:j}$: indica el array de palabras que se encuentran desde la direccioón $i$ de INPUT, hasta la dirección $j$.

Por simplicidad, tanto INPUT como MEMORY no necesitan esperar ciclos de reloj para leer un dato particular. En el caso de la escritura en MEMORY, solo se necesita de un Rising Edge para guardar un dato en una dirección específica.

Circuitos Secundarios

Como es necesario imprimir en la pantalla proporcionada se brindan dos circuitos que facilitan la escritura de números enteros con signo (PRINT DEC) o sin signo (PRINT UDEC).

Estos circuitos son ASMs que reciben el número que se desea imprimir, y se activan con la entrada start. Cuando ambos inician se debe esperar a que termine la escritura en pantalla, que no es más que esperar a que la salida END de estos circuitos, se active. Se debe tener en cuenta que ambos circuitos están diseñados para mostrar su estado de finalización durante solamente un ciclo del reloj; por lo tanto preste atención a dicha salida.

Adicionalmente se dispone del circuito TEST PRINT para que pruebe y se familiarice con el funcionamiento de los circuitos PRINT DEC y PRINT UDEC.

NASM

Solo se permitirá utilizar las subrutinas y macros externas definidas en io.inc. Cualquier subrutina que emplee, debe ser implementada. En la section .data se pueden definir tantos valores constantes como se desee, pero debe agregar los nombres de constantes que se especifican en cada problema, ya que la entrada se dispondrá de dicha forma. Por lo tanto si un problema exige las entradas A (número) y el array lista, debe definir estas en dicha sección con dicho nombre.

En la sección .bss puede definir el espacio en memoria que necesite con algún fin específico. Sin embargo, se prefiere utilizar más la Pila, y solo cuando sea necesario, la sección .bss.

El código de la implementación se debe desarrollar en la sección .text. Para los llamados de subrutina se recomienda utilizar la convención de llamada cdecl (C declaration). Lo esencial de este convenio es que la función que realiza el llamado a la subrutina es la encargada de pasar los parámetros a la pila, y limpiarla al retorno. Implementar bien este convenio permite el llamado directo desde el lenguaje C y C++. Si lo desea puede implementar otro convenio como stdcall; pero debe saber explicar el convenio implementado.

Lista de Problemas

1. Problema 1 (N Perfectos)

2. Problema 2 (N Primos)

3. Problema 3 (I-ésimo Primo)

4. Problema 4 (I-ésimo Perfecto)

5. Problema 5 (Potencias de 2 en Intervalo)

6. Problema 6 (I-ésimo Término de Fibonacci)

7. Problema 7 (I-ésimo Término de Tribonacci)

8. Problema 8 (I,J-ésimo Término de Ackermann)

9. Problema 9 (I-ésimo Término de Collatz)

10. Problema 10 (Divisores Primos)

11. Problema 11 (Máximo Común Divisor)

12. Problema 12 (Mínimo Común Múltiplo)

13. Problema 13 (Simplificar Fracción)

14. Problema 14 (Suma de Fracciones)

15. Problema 15 (Decimal a Base A)

16. Problema 16 (Base A a Decimal)

17. Problema 17 (Divisibilidad)

18. Problema 18 (Mínimo de un array)

19. Problema 19 (Máximo de un array)

20. Problema 20 (Máximo de un array en intervalo)

21. Problema 21 (Mínimo de un array en intervalo)

22. Problema 22 (Insertion Sort A-Z)

23. Problema 23 (Bubble Sort A-Z)

24. Problema 24 (Media de un array)

25. Problema 25 (Varianza de un array)

26. Problema 26 (Moda de un array)

27. Problema 27 (Repeticiones en Array)

28. Problema 28 (Suma de n menores que x)

29. Problema 29 (Sumando y obteniendo x)

30. Problema 30 (Suma de nodos en arbol)

31. Problema 31 (Imprimir hojas)

32. Problema 32 (Devolver Padre)

33. Problema 33 (Actualizar Heap)

34. Problema 34 (Subconjunto)

35. Problema 35 (Igualdad de conjuntos)

36. Problema 36 (Partición de Conjuntos I)

37. Problema 37 (Partición de Conjuntos II)

38. Problema 38 (Partición de Conjuntos III)

39. Problema 39 (Múltiplicación de Matriz y Vector)

40. Problema 40 (Múltiplicación de Vectores)

41. Problema 41 (Suma de Matrices)

42. Problema 42 (Resta de Matrices)

43. Problema 43 (Matriz por una constante)

44. Problema 44 (Matriz Transpuesta)

45. Problema 45 (Suma de n mayores que x)

46. Problema 46 (Recorrido en Preorden)

47. Problema 47 (Recorrido en Inorden)

48. Problema 48 (Recorrido en Postorden)

49. Problema 49 (Build Heap)

50. Problema 50 (Insertar en ABB)

51. Problema 51 (Intersección de Conjuntos)

52. Problema 52 (Unión de Conjuntos)

53. Problema 53 (Diferencia de Conjuntos)

54. Problema 54 (Producto Vectorial)

55. Problema 55 (Norma de un Vector)

56. Problema 56 (Raíz de N)

57. Problema 57 (Rotar Matriz)

58. Problema 58 (Dentro de un Triángulo)

59. Problema 59 (Pertenece a la Recta)

60. Problema 60 (En qué lado de la Recta?)

61. Problema 61 (Factorial)

62. Problema 62 (Moda de un array)

63. Problema 63 (Polinomios)

64. Problema 64 (Palíndromos)

65. Problema 65 (Substring)

66. Problema 66 (Merge Sort)

67. Problema 67 (Ordenacion)

68. Problema 68 (Contando Bits)

69. Problema 69 (Contando Bits y Paridad)

70. Problema 70 (Alternando Bits)

71. Problema 71 (Daditos)

72. Problema 72 (Colitas)

73. Problema 73 (Nacimiento según CI)

74. Problema 74 (Género según CI)

75. Problema 75 (Fecha Válida)

76. Problema 76 (Altura Máxima)

77. Problema 77 (Suma y Resta en Árbol)

78. Problema 78 (Producto de Fracciones)

79. Problema 79 (Resta de Fracciones)

80. Problema 80 (División de Fracciones)

81. Problema 81 (Máximos por intervalos)

82. Problema 82 (Altura Mínima)

83. Problema 83 (Cantidad de Nodos)

84. Problema 84 (Ramita Fuerte)

85. Problema 85 (Triángulo Rectángulo)

86. Problema 86 (Cajero)

87. Problema 87 (Rectas que se cortan)

88. Problema 88 (Rectas que son paralelas)

89. Problema 89 (Circunferencia)

90. Problema 90 (Cubo)

91. Problema 91 (Cilindro)

92. Problema 92 (Pirámide)

93. Problema 93 (Esfera)

94. Problema 94 (Ortoedro)

95. Problema 95 (Insertion Sort++ Z-A)

96. Problema 96 (Mayor Substring)

97. Problema 97 (Paridad en un array)

98. Problema 98 (Bubble Sort++ Z-A)

99. Problema 99 (Array en Array)

100. Problema 100 (Mínima Transformación)