Análisis y Diseño de Algoritmos
Prof:
Ing. Victor Garro
Asistente: Marco Elizondo
Vargas
PROGRAMACION
EN C++
Capitulo
0 El sistema de computo
Este capítulo describe los componentes básicos
de un equipo de cómputo, la CPU, la memoria, mecanismos de Entrada/Salida y el
bus que los interconecta. Es importante hacer notar el uso de ciertas palabras
tomadas del inglés y cuya traducción al español puede dar como resultado cierto
grado de confusión, irónicamente existen conceptos que se entienden mejor
utilizando las palabras inglesas, tal es el caso de CPU y bus, si
el caso lo amerita, incluiré la traducción entre paréntesis pero siempre
buscando la forma que resulte más clara para explicar los conceptos
involucrados.
Componentes
básicos
Al
diseño operacional básico de un equipo de cómputo se le conoce como su arquitectura.
A John Von Neumann, un pionero en diseño de computadoras, se le
considera como el arquitecto de los sistemas de cómputo actuales, incluyendo a
las máquinas que utilizan procesadores 80x86 de la familia Intel. Un típico
sistema Von Neumann
consiste en tres componentes principales, la Unidad Central de Procesamiento
(ó CPU), memoria y Entrada/Salida (E/S). En las máquinas de
arquitectura Von Neumann
toda la acción se lleva a cabo dentro del CPU, los datos y las instrucciones
para el CPU residen en memoria hasta que son requeridas por el CPU, para éste,
la mayoría de los dispositivos de Entrada/Salida aparecen como memoria porque
el CPU puede escribir datos en los dispositivos de salida y leer datos de los
dispositivos de entrada, la principal diferencia entre la memoria y los
dispositivos de E/S es que éstos últimos por lo general tienen conexión con el
mundo exterior.
El bus del
sistema
El bus del sistema conecta a los elementos que
forman una computadora Von Neumann,
en una máquina Intel 80x86 existen tres buses principales: el bus de datos,
el bus de direcciones y el bus de control. Un bus es un conjunto
de alambres por los cuales pasan señales eléctricas entre los componentes de un
sistema, éstos buses varían de procesador en procesador, sin embargo cada bus
transporta información equivalente para todos los procesadores. Un típico
componente de un sistema 80x86 utiliza niveles TTL estándar de señal, esto
significa que cada alambre en un bus utiliza un nivel de voltaje estándar para
representar los niveles lógicos de 1 y 0.
El bus de
datos
Los procesadores 80x86 utilizan el bus de
datos para intercambiar información entre los diferentes componentes del
sistema. El tamaño de éstos buses es variable dependiendo del tipo de
procesador, por esta razón es común pensar en el tamaño del bus como una medida
del "tamaño" del procesador, puede haber buses de datos de 8 (8088,
80188), 16 (8086, 80186, 80286), 32 (80386, 80486) ó 64 líneas (Pentium,
Pentium Pro). En cada línea del bus de datos se transmite un bit de información pero un sistema no está limitado a
manejar información de acuerdo al tamaño del bus de datos, es decir, un bus de
32 bits no está limitado a trabajar con tipos de datos máximos de 32 bits. El
tamaño del bus de datos por otro lado si limita el número de bits que el
sistema puede manejar por cada ciclo de memoria de tal manera que un sistema de
16 bits necesita dos ciclos de memoria para manejar un tipo de dato de 32 bits,
naturalmente pero no necesariamente, un sistema de 32 bits es el doble de
rápido que un sistema de 16 bits, la limitación es porque existen otros
factores que influyen en el rendimiento de un sistema.
El bus de
direcciones
El bus de direcciones es el encargado de
diferenciar las ubicaciones físicas de cada elemento de un sistema de cómputo,
sea memoria ó elemento de E/S, cuando un programa necesita tener acceso a un
elemento determinado del sistema coloca su dirección en el bus de direcciones,
los circuitos electrónicos asociados sea con la memoria ó con un dispositivo de
E/S son los encargados de reconocer ésta dirección y consecuentemente colocar
los datos correspondientes en el bus de datos. Con una sola línea de dirección
es posible tener acceso a dos elementos diferentes, con n líneas de
dirección se puede acceder a 2n direcciones diferentes, por
lo tanto el número de bits de un bus de direcciones determina la cantidad
máxima de direcciones de memoria que un sistema puede acceder. Un procesador
Pentium tiene un bus de direcciones de 32 bits por lo que su capacidad física
real de direccionamiento de memoria de de 4 Gigabytes,
utilizando la técnica de segmentación éstos procesadores pueden acceder
a un mayor número de direcciones de memoria.
El bus de
control
El bus de control es una colección de líneas
que transportan un conjunto de señales cuyo propósito es la sincronía de todas
las operaciones efectuadas por el CPU con los diferentes subsistemas de un
equipo de cómputo, destacan las líneas para escritura (write)
y lectura (read) de datos, el reloj del
sistema, líneas de interrupción, líneas de estado, etc. El uso de éstas líneas
se comprenderá mejor conforme se avance en éste curso. Los procesadores de la
familia 80x86 proveen dos espacios diferentes de direccionamiento, uno para la
memoria y otro para la E/S, mientras que el direccionamiento de memoria varía
según el procesador, las líneas de E/S son siempre de 16 bits, lo que permite direccionar 65,536 localidades diferentes. Algunas líneas
de control son las encargadas de decidir qué direcciones son para memoria y
cuáles son para E/S.
El subsistema
de memoria
Los procesadores 80x86 soportan memoria direccionable por bytes, por
lo tanto, la unidad básica de memoria es el byte, así
que con 20, 24 ó 32 líneas de direccionamiento los procesadores 80x86 pueden
acceder a 1 Megabyte, 16 Megabytes
ó 4 Gigabytes de memoria, respectivamente. Piense en
la memoria como un arreglo lineal de bytes, la
dirección del primer byte es 0 y la del último es 2n-1.
Para ejecutar una pseudo-instrucción como memoria[125]=10;
el CPU coloca el valor de 10 en el bus de datos, la dirección 125 en el bus de
direcciones y por último valida la línea de control write.
Esto solo se aplica en el caso en que se accede a un byte
de memoria, entonces, ¿Qué sucede cuando se trata de acceder a una palabra ó
una palabra doble? Los sistemas basados en procesadores 80x86 resuelven éste
problema colocando el byte de orden bajo en la
dirección especificada y el byte de orden alto en la
dirección inmediata a la especificada. Por lo tanto una palabra consume dos
direcciones de memoria y una palabra doble consume cuatro direcciones de
memoria, de aquí se deduce que el tamaño del bus de datos determina el número
de direcciones de memoria necesarias para trabajar con palabras ó con palabras
dobles, un procesador con un bus de datos de 32 bits puede manejar una palabra
doble en una sola ubicación de memoria. En los equipos con procesador 80x88 el
bus de datos es de solo 8 bits por lo que resulta muy conveniente el manejo de
direcciones de memoria con respecto a datos de un byte,
para trabajar con palabras (2 bytes) ó con palabras
dobles (4 bytes) sencillamente se ocupaban
direcciones de memoria adyacentes. Con la llegada de procesadores con bus de
datos de 16, 32 ó 64 bytes surge un pequeño problema
que el programador debe tener en cuenta al momento de asignar direcciones de
memoria. Para empezar, éstos procesadores trabajan solamente con direcciones de
memoria de orden par, dividiendo el bus de datos en bancos de 8 bits cada uno,
por ejemplo, un bus de datos de 32 bits está ordenado en cuatro bancos de 8
bits siendo el primero de éstos (D0 ~ D7) el que corresponde al byte de orden bajo de la ubicación de memoria dada. Por
ésta razón se recomienda asignar direcciones de memoria de orden par para el
caso de las palabras, y direcciones de orden par divisibles entre cuatro para
palabras dobles, ésto con el objeto de evitar que el
procesador consuma direcciones de memoria en forma inútil en el proceso de
adaptar datos con direcciones de orden impar a los bancos de memoria que están
todos ordenados en direcciones de orden par, esto es importante, en buses de
datos superiores a 16 bits no existen direcciones de memoria de orden impar.
El subsistema
de E/S
Además de las líneas de dirección de 20, 24 ó
32 bits, un sistema basado en la familia 80x86 provee un bus de direcciones par
E/S de 16 bits, algunas líneas en el bus de control son las encargadas de
diferenciar si se trata de operaciones relacionadas con la memoria ó bién con E/S, por lo tanto la memoria y los dispositivos de
E/S comparten el mismo bus de datos y los 16 bits de orden bajo del bus de
direcciones. Existen tres limitaciones en el subsistema de E/S de las computadoras
IBM y compatibles, primero, los procesadores 80x86 requieren instrucciones
especiales para acceder a los dispositivos de E/S, segundo, los diseñadores de
la IBM-PC se reservaron para sí las "mejores" direcciones para sus
propios propósitos forzando a los diseñadores de equipo independientes a
utilizar direcciones menos accesibles, y tercero, los sistemas 80x86 solamente
pueden acceder a no más de 65,536 direcciones de E/S. Para resolver éstas
limitaciones, los diseñadores de equipo frecuentemente mapean
las direcciones de memoria de los dispositivos de E/S hacia otras ubicaciones
de memoria por encima de los 65,536 bytes utilizando
hardware.
Temporización
En máquinas de arquitectura Von Neumann la mayoría de las
operaciones son serializadas, esto significa
que la computadora ejecuta los comandos en un orden preestablecido. Para
asegurarnos de que todas las operaciones ocurren justo en el tiempo adecuado,
las máquinas 80x86 utilizan una señal alternante llamada el reloj del
sistema.
En su forma básica, el reloj del sistema
maneja toda la sincronización de un sistema de cómputo. El reloj del sistema es
una señal eléctrica en el bus de control que alterna entre los valores de cero
y uno a una tasa dada. La frecuencia en la cual el reloj del sistema alterna
entre cero y uno es llamada frecuencia del reloj de sistema. El timepo que toma para cambiar de cero a uno y luego volver a
cero se le llama periodo de reloj, también llamado ciclo de reloj.
La frecuencia del reloj es simplemente el número de ciclos de reloj que ocurren
en un segundo, en sistemas actuales, éste valor excede los 200 ciclos por
segundo, siendo ya común frecuencias del orden de los 366 Mhz.
(MegaHertz, que equivale a un millón de ciclos por
segundo). Observe que el periodo de reloj es el valor inverso de la frecuencia,
por lo tanto, para un sistema de 200 Mhz el periodo
es igual a 5 nanosegundos. Para asegurar la
sincronización, el CPU inicia una operación ya sea en el flanco ascendente
(cuando la señal cambia de cero a uno) ó en el descendente (cuando la señal
cambia de uno a cero). Como todas las operaciones de un CPU están sincronizadas
en torno a su reloj, un CPU no puede ejecutar operaciones más rápido que la
velocidad del reloj.
Acceso a
memoria y el reloj del sistema
El acceso a memoria es probablemente la
actividad más común de un CPU, se trata en definitiva de una operación
sincronizada al reloj del sistema, esto es, la lectura o escritura no puede ser
más rápida que un ciclo de reloj, de hecho, en muchos sistemas 80x86 el acceso
a memoria toma varios ciclos de reloj. El tiempo de acceso a memoria es
el número de ciclos de reloj que el sistema necesita para acceder a una
ubicación de memoria, este es un valor importante ya que a mayor número de
ciclos menor desempeño. El tiempo de acceso a memoria es la cantidad de tiempo
que transcurre desde que se solicita una operación (sea de lectura ó escritura)
y el tiempo en que la memoria completa dicha operación. En procesadores de 5 Mhz (80x88, 80x86) el tiempo de acceso a memoria es de
aproximadamente 800 ns. (nanosegundos),
en cambio, un procesador de 50 Mhz (80x486) el tiempo
es de aproximadamente 20 ns. El tiempo de acceso a
memoria en el procesador 80x486 es casi 40 veces más rápido que en el caso del
procesador 80x86 porque éste último consume más ciclos de reloj para el acceso
a memoria además del incremento en la velocidad de reloj.
Los dispositivos de memoria presentan varias
características pero las principales son su capacidad de almacenamiento y el
tiempo de acceso. Una memoria de acceso aleatorio (RAM) típica tiene una
capacidad de 16 ó más megabytes y un tiempo de acceso
de 70 nanosegundos ó menos, con estos datos
seguramente se estará preguntando cómo es posible que éstas memorias
relativamente lentas trabajan en procesadores mucho más rápidos. La respuesta
son los estados de espera. Un estado de espera es una señal que se
coloca en el bus de control por parte del dispositivo de memoria para detener
temporalmente el trabajo realizado por el CPU, como consecuencia utilizar uno o
más estados de espera tiene el mismo efecto que reducir proporcionalmente la
velocidad de reloj, obviamente introducir estados de espera no es una opción
deseable por la reducción en el desempeño del sistema. Los diseñadores de
hardware han encontrado un mecanismo que tiene un efecto similar a introducir
estados de espera pero sin afectar notablemente el rendimiento de la
computadora, a este mecanismo se le llama memoria cache
( se pronuncia "cash").
Una memoria cache es
un dispositivo sin estados de espera que se encuentra construida como parte
integral del CPU, físicamente se encuentra entre el CPU y los módulos de
memoria RAM, su función es evitar la generación de estados de espera por parte
de los módulos de memoria RAM y así aprovechar al máximo el rendimiento
esperado por el CPU, sin embargo la memoria cache no
es un dispositivo perfecto pues hay ocasiones en que no es posible colocar en
memoria cache los datos que requiere el programa para
ejecutarse forzando al sistema a leer dichos datos directamente de los módulos
de memoria RAM y por lo tanto generando estados de espera, cuando ocurre éste
fenómeno se le llama pérdida cache (cache miss), cuando tienen éxito las operaciones en memoria
cache se le llama éxito cache
(cache hit). Por lo general el radio entre éxito y
pérdida en memoria cache está entre 85 y 90%. Este
rendimiento disminuye al aumentar la cantidad de memoria cache
y por esta razón la memoria cache es relativamente
pequeña, sus valores de almacenamiento oscilan entre 256 y 512 Kb.
