INVESTIGACION
INDICE
1.-Diagrama de entidad de relación
2.-Normalización
3.-Optimización
INTRODUCCIÓN.-Generalmente, el termino aplicación de base de datos se
refiere a una base de datos en particular (por ejemplo la base de datos BANCO
que mantiene las cuentas de ahorro de sus clientes) y a los programas
asociados, que implementan las consultas y actualizaciones de la base de datos
(por ejemplo, programas que implementan actualizaciones de la base de datos
correspondientes a los depósitos y reintegros de clientes). Por lo tanto, parte
de la aplicación de base de datos requeriría el diseño, ˜ implementación y
prueba de estos programas de aplicación, pero también requiere el diseño, ˜
implementación y prueba de la base de datos en sí misma. Tradicionalmente, se
ha considerado que el diseño˜ y prueba de los programas de aplicación pertenece
más al dominio de la ingeniería del software que al de las bases de datos. Sin
embargo, cada vez es más obvio que existe algo en común entre las metodologías
de diseño˜ de bases de datos y las de ingeniería del software. Es cierto que
esas características comunes aumentaran, ya que las metodologías de diseño˜ de
base de datos tratan incluir conceptos de especificación de operaciones sobre
objetos de base de datos, y que las metodologías de ingeniería del software
especifican con más detalle la estructura de la base de datos. Pero en este
curso nos centraremos en las estructuras de bases de datos y en las
restricciones durante el diseño˜ de la base de datos.
DIAGRAMAS DE ENTIDAD DE RELACIÓN
Denominado por sus siglas como: E-R; Este
modelo representa a la realidad a través de un Esquema gráfico empleando los
terminología de Entidades, que son objetos que existen y son los principales
que se identifican en el problema a resolver con el diagramado y se distinguen
de otros por sus características particulares denominadas Atributos, el enlace
que rige la unión de las entidades está representada por la relación del
modelo.
En un DER, cada entidad se representa
mediante un rectángulo, cada relación mediante un rombo y cada dominio
(conjunto donde toma valores el atributo) mediante un círculo. Mediante líneas
se conectan las entidades con las relaciones, igual que las entidades con los
dominios, representando a los atributos. Los Atributos Llaves se representan
subrayando el correspondiente conjunto de valores.
En ocasiones, una entidad no puede ser
identificada únicamente por el valor de sus propios atributos. En estos casos,
se utilizan conjuntamente las relaciones con los atributos para lograr la
requerida identificación unívoca. Estas entidades reciben el nombre de
entidades débiles y se representan en el DER con un doble rectángulo. El MER
restringe las relaciones a usar para identificar las entidades débiles a
relaciones binarias del tipo 1: N. Así, por ejemplo, una ocurrencia de
"trabajador" puede tener N ocurrencias
"persona-dependiente" asociadas, donde además, la existencia de las
ocurrencias en la segunda entidad depende de la existencia de una ocurrencia
que le corresponda en la primera entidad. Por ejemplo, en el modelo habrá
personas dependientes de un trabajador sólo si ese trabajador existe. Para
indicar esa dependencia en la existencia se usa una saeta en el DER. La llave
de una entidad débil se forma combinando la llave de la entidad regular que la
determina con algún otro atributo que defina unívocamente cada entidad débil
asociada a una entidad regular dada. (Una entidad se denomina regular si no es
débil).
En una
relación, la llave es la combinación de las llaves de todas las entidades
asociadas. Para cada relación se determina su tipo (simple o complejo) y en el
DER se escribe el tipo de correspondencia. Por ejemplo, una empresa puede tener
varios (n) trabajadores asociados y un trabajador pertenece a una sola empresa
(1). En la relación Trabajador-Máquina-Pieza, un trabajador puede trabajar en n
máquinas, produciendo p piezas, o una pieza puede ser producida por m
trabajadores en n máquinas. Aquí, m, n y p no identifican un número específico,
sino solamente el tipo de correspondencia que se establece en la relación.
Los diagramas ER son un lenguaje gráfico
para describir conceptos. Informalmente, son simples dibujos o gráficos que
describen información que trata un sistema de información y el software que lo
automatiza.
Entidad
Las entidades son el fundamento del modelo
entidad relación. Podemos adoptar como definición de entidad cualquier cosa o
parte del mundo que es distinguible del resto. Por ejemplo, en un sistema
bancario, las personas y las cuentas bancarias se podrían interpretar como
entidades. Las entidades pueden representar entes concretos, como una persona o
un avión, o abstractas, como por ejemplo un préstamo o una reserva.
Atributo
Se representan mediante un círculo o elipse
etiquetado mediante un nombre en su interior. Cuando un atributo es
identificativo de la entidad se suele subrayar dicha etiqueta.
Relaciones
Se representa mediante un rombo etiquetado
en su interior con un verbo. Este rombo se debe unir mediante líneas con las
entidades (rectángulos) que relaciona.
Por motivos de legibilidad, los atributos
no suelen representarse en un diagrama entidad-relación, sino que se describen
textualmente en otros documentos adjuntos.
Representación del
Objeto de Estudio en el Mundo de los Datos
• Entidades.
• Atributos de las Entidades.
• Atributo llave.
• Relaciones entre las Entidades.
• Modelo gráfico de las Entidades y sus
Relaciones. (Diagrama Entidad Relación)
• Modelo Lógico de los Datos.
Obtención del Diagrama Entidad Relación
Componentes y Diagrama E-R
Entidad Regular: Una Entidad fuerte (también conocida como entidad
regular es aquella que sí puede ser identificada unívocamente. En los casos en
que se requiera, se puede dar que una entidad fuerte "preste" algunos
de sus Atributos a una entidad débil para que, esta última, se pueda
identificar.
Entidad débil: Es aquella que no puede existir sin participar en la
relación, es decir, aquella que no puede ser unívocamente identificada
solamente por sus atributos como Clave.
Relaciones: La relación existente entre las entidades. Inscriben a
cada entidad en un Conjunto de entidades. Un conjunto de entidades dentro de una entidad, tiene
valores específicos asignados para cada uno de sus atributos, de esta forma, es
posible su identificación unívoca.
Ejemplos:
A la colección de entidades Alumnos, con el
siguiente conjunto de atributos en común, (id, nombre, edad, semestre),
pertenecen las entidades: (1, Sofía, 18 años, 2) (2, Josefa, 19 años, 5) (3,
Gabriela, 20 años, 2.
Conector: Separador Una Clave principal se utiliza para
relacionar una tabla con claves externas de otras tablas.) Consta de dos
campos: las claves externas Clave externa: uno o más campos de tabla (columnas)
que hacen referencia al campo o campos de clave principal de otra tabla. Una
Clave externa indica cómo están relacionadas las tablas.) De las Tablas A y B.
Una relación de Varios a varios no es sino dos relaciones de Uno a varios con
una tercera tabla. Por ejemplo, la tabla Pedidos y la tabla Productos tienen
una relación de Varios a varios que se define mediante la creación de dos relaciones
de Uno a varios con la tabla Detalles de pedidos. Un pedido puede incluir
muchos productos, y cada producto puede aparecer en muchos pedidos. Ejemplo:
personas y viviendas.
Pasos a seguir para el Diagrama Entidad
Relación
1. Una entidad se relaciona con otra
entidad con una línea continua, ya que no lleva flechas, es solo una dirección
continua. 2. Toda relación debe de llevar una cardinalidad (determina el nivel
de cardinalidad). 3. Una relación entre dos entidades siempre se va a dar por
medio de un rombo (si tienes una entidad alumno, otra materia, se traza una
línea en el medio de la línea se pone un rombo, dentro del rombo se pone
"el alumno se inscribe", el nivel seria uno a muchos ya que el alumno
se inscribe a varias materias). 4. Cada entidad deberá tener sus elementos.
Operaciones sobre objetos gráficos del
diagrama Entidad Relación
Generalización/Especialización: Permite formar una nueva entidad, mediante la unión de
otras entidades. El proceso inverso se denomina especialización.
Agregación: Permite formar una nueva entidad, sobre la base de una
relación.
Agrupamiento: Define una nueva entidad, donde cada ocurrencia es un
grupo de ocurrencias de la entidad fuente.
La Generalización y especialización Es el resultado de la unión de 2 o más conjuntos de
entidades (de bajo nivel) para producir un conjunto de entidades de más alto
nivel. La generalización se usa para hacer resaltar los parecidos entre tipos
de entidades de nivel más bajo y ocultar sus diferencias.
La generalización consiste en identificar
todos aquellos atributos iguales de un conjunto de entidades para formar una
entidad(es) global(es) con dichos atributos semejantes, dicha entidad(es)
global(es) quedara a un nivel más alto al de las entidades origen.
La agregación surge de la limitación que
existe en el modelado de E-R, al no permitir expresar las relaciones entre
relaciones de un modelo E-R en el caso de que una relación X se quiera unir con
una entidad cualquiera para formar otra relación
--------------------------------------------------------------------------------------------------------------------------
INTRODUCCION.- Uno de los factores más importantes en la creación de
páginas web dinámicas es el diseño de las Bases de Datos (BD). Si tus tablas no
están correctamente diseñadas, te pueden causar un montón de dolores de cabeza
cuando tengas de realizar complicadísimas llamadas SQL en el código PHP para
extraer los datos que necesitas. Si conoces como establecer las relaciones
entre los datos y la normalización de estos, estarás preparado para comenzar a
desarrollar tu aplicación en PHP. Si trabajas con MySQL o con Oracle, debes
conocer los métodos de normalización del diseño de las tablas en tu sistema de
BD relacional. Estos métodos pueden ayudarte a hacer tu código PHP más fácil de
comprender, ampliar, y en determinados casos, incluso hacer tu aplicación más
rápida. Básicamente, las reglas de Normalización están encaminadas a eliminar
redundancias e inconsistencias de dependencia en el diseño de las tablas.
NORMALIZACIÓN
Los datos redundantes desperdician el espacio de disco y crean problemas de mantenimiento. Si hay que cambiar datos que existen en más de un lugar, se deben cambiar de la misma forma exactamente en todas sus ubicaciones. Un cambio en la dirección de un cliente es mucho más fácil de implementar si los datos sólo se almacenan en la tabla Clientes y no en algún otro lugar de la base de datos.
¿Qué es una "dependencia incoherente"? Aunque es intuitivo para un usuario mirar en la tabla Clientes para buscar la dirección de un cliente en particular, puede no tener sentido mirar allí el salario del empleado que llama a ese cliente. El salario del empleado está relacionado con el empleado, o depende de él, y por lo tanto se debería pasar a la tabla Empleados. Las dependencias incoherentes pueden dificultar el acceso porque la ruta para encontrar los datos puede no estar o estar interrumpida.
Hay algunas reglas en la normalización de una base de datos. Cada regla se denomina una "forma normal". Si se cumple la primera regla, se dice que la base de datos está en la "primera forma normal". Si se cumplen las tres primeras reglas, la base de datos se considera que está en la "tercera forma normal". Aunque son posibles otros niveles de normalización, la tercera forma normal se considera el máximo nivel necesario para la mayor parte de las aplicaciones.
Al igual que con otras muchas reglas y especificaciones formales, en los escenarios reales no siempre se cumplen los estándares de forma perfecta. En general, la normalización requiere tablas adicionales y algunos clientes consideran éste un trabajo considerable. Si decide infringir una de las tres primeras reglas de la normalización, asegúrese de que su aplicación se anticipa a los problemas que puedan aparecer, como la existencia de datos redundantes y de dependencias incoherentes.
En las descripciones siguientes se incluyen
ejemplos.
Primera forma normal
· Elimine
los grupos repetidos de las tablas individuales.
· Cree
una tabla independiente para cada conjunto de datos relacionados.
· Identifique
cada conjunto de datos relacionados con una clave principal.
No use varios campos en una sola tabla para
almacenar datos similares. Por ejemplo, para realizar el seguimiento de un
elemento del inventario que proviene de dos orígenes posibles, un registro del
inventario puede contener campos para el Código de proveedor 1 y para el Código
de proveedor 2.
¿Qué ocurre cuando se agrega un tercer proveedor? Agregar un campo no es la respuesta, requiere modificaciones en las tablas y el programa, y no admite fácilmente un número variable de proveedores. En su lugar, coloque toda la información de los proveedores en una tabla independiente denominada Proveedores y después vincule el inventario a los proveedores con el número de elemento como clave, o los proveedores al inventario con el código de proveedor como clave.
¿Qué ocurre cuando se agrega un tercer proveedor? Agregar un campo no es la respuesta, requiere modificaciones en las tablas y el programa, y no admite fácilmente un número variable de proveedores. En su lugar, coloque toda la información de los proveedores en una tabla independiente denominada Proveedores y después vincule el inventario a los proveedores con el número de elemento como clave, o los proveedores al inventario con el código de proveedor como clave.
Segunda forma normal
· Cree
tablas independientes para conjuntos de valores que se apliquen a varios
registros.
· Relacione
estas tablas con una clave externa.
Los registros no deben depender de nada que
no sea una clave principal de una tabla, una clave compuesta si es necesario.
Por ejemplo, considere la dirección de un cliente en un sistema de
contabilidad. La dirección se necesita en la tabla Clientes, pero también en
las tablas Pedidos, Envíos, Facturas, Cuentas por cobrar y Colecciones. En
lugar de almacenar la dirección de un cliente como una entrada independiente en
cada una de estas tablas, almacénela en un lugar, ya sea en la tabla Clientes o
en una tabla Direcciones independiente.
Tercera forma normal
· Elimine
los campos que no dependan de la clave.
Los valores de un registro que no sean
parte de la clave de ese registro no pertenecen a la tabla. En general, siempre
que el contenido de un grupo de campos pueda aplicarse a más de un único registro
de la tabla, considere colocar estos campos en una tabla independiente. Por
ejemplo, en una tabla Contratación de empleados, puede incluirse el nombre de
la universidad y la dirección de un candidato. Pero necesita una lista completa
de universidades para enviar mensajes de correo electrónico en grupo. Si la
información de las universidades se almacena en la tabla Candidatos, no hay
forma de enumerar las universidades que no tengan candidatos en ese momento.
Cree una tabla Universidades independiente y vincúlela a la tabla Candidatos
con el código de universidad como clave.
EXCEPCIÓN: cumplir la tercera forma normal, aunque en teoría es deseable, no siempre es práctico. Si tiene una tabla Clientes y desea eliminar todas las dependencias posibles entre los campos, debe crear tablas independientes para las ciudades, códigos postales, representantes de venta, clases de clientes y cualquier otro factor que pueda estar duplicado en varios registros. En teoría, la normalización merece el trabajo que supone. Sin embargo, muchas tablas pequeñas pueden degradar el rendimiento o superar la capacidad de memoria o de archivos abiertos.
Puede ser más factible aplicar la tercera forma normal sólo a los datos que cambian con frecuencia. Si quedan
EXCEPCIÓN: cumplir la tercera forma normal, aunque en teoría es deseable, no siempre es práctico. Si tiene una tabla Clientes y desea eliminar todas las dependencias posibles entre los campos, debe crear tablas independientes para las ciudades, códigos postales, representantes de venta, clases de clientes y cualquier otro factor que pueda estar duplicado en varios registros. En teoría, la normalización merece el trabajo que supone. Sin embargo, muchas tablas pequeñas pueden degradar el rendimiento o superar la capacidad de memoria o de archivos abiertos.
Puede ser más factible aplicar la tercera forma normal sólo a los datos que cambian con frecuencia. Si quedan
algunos campos dependientes, diseñe la
aplicación para que pida al usuario que compruebe todos los campos relacionados
cuando cambie alguno.
Otras formas de normalización
La cuarta forma normal, también llamada
Forma normal de Boyce Codd (BCNF, Boyce Codd Normal Form), y la quinta forma
normal existen, pero rara vez se consideran en un diseño real. Si no se aplican
estas reglas, el diseño de la base de datos puede ser menos perfecto, pero no
debería afectar a la funcionalidad.
Normalizar una tabla de ejemplo
Estos pasos demuestran el proceso de
normalización de una tabla de alumnos ficticia.
1. Tabla
sin normalizar:
|
Nº alumno
|
Tutor
|
Despacho-Tut
|
Clase1
|
Clase2
|
Clase3
|
|
1022
|
García
|
412
|
101-07
|
143-01
|
159-02
|
|
4123
|
Díaz
|
216
|
201-01
|
211-02
|
214-01
|
2. Primera
forma normal: no hay grupos repetidos
Las tablas sólo deben tener dos dimensiones. Puesto que un alumno tiene varias clases, estas clases deben aparecer en una tabla independiente. Los campos Clase1, Clase2 y Clase3 de los registros anteriores son indicativos de un problema de diseño.
Las hojas de cálculo suelen usar la tercera dimensión, pero las tablas no deberían hacerlo. Otra forma de considerar ese problema es con una relación de uno a varios y poner el lado de uno y el lado de varios en tablas distintas. En su lugar, cree otra tabla en la primera forma normal eliminando el grupo repetido (Nº clase), según se muestra a continuación:
Las tablas sólo deben tener dos dimensiones. Puesto que un alumno tiene varias clases, estas clases deben aparecer en una tabla independiente. Los campos Clase1, Clase2 y Clase3 de los registros anteriores son indicativos de un problema de diseño.
Las hojas de cálculo suelen usar la tercera dimensión, pero las tablas no deberían hacerlo. Otra forma de considerar ese problema es con una relación de uno a varios y poner el lado de uno y el lado de varios en tablas distintas. En su lugar, cree otra tabla en la primera forma normal eliminando el grupo repetido (Nº clase), según se muestra a continuación:
|
Nº alumno
|
Tutor
|
Despacho-Tut
|
Nº clase
|
|
1022
|
García
|
412
|
101-07
|
|
1022
|
García
|
412
|
143-01
|
|
1022
|
García
|
412
|
159-02
|
|
4123
|
Díaz
|
216
|
201-01
|
|
4123
|
Díaz
|
216
|
211-02
|
|
4123
|
Díaz
|
216
|
214-01
|
3. Segunda
forma normal: eliminar los datos redundantes
Observe los diversos valores de Nº clase para cada valor de Nº alumno en la tabla anterior. Nº clase no depende funcionalmente de Nº alumno (la clave principal), de modo que la relación no cumple la segunda forma normal.
Las dos tablas siguientes demuestran la segunda forma normal:
Alumnos:
Observe los diversos valores de Nº clase para cada valor de Nº alumno en la tabla anterior. Nº clase no depende funcionalmente de Nº alumno (la clave principal), de modo que la relación no cumple la segunda forma normal.
Las dos tablas siguientes demuestran la segunda forma normal:
Alumnos:
|
Nº alumno
|
Tutor
|
Despacho-Tut
|
|
1022
|
García
|
412
|
|
4123
|
Díaz
|
216
|
4.
Registro:
Registro:
|
Nº alumno
|
Nº clase
|
|
1022
|
101-07
|
|
1022
|
143-01
|
|
1022
|
159-02
|
|
4123
|
201-01
|
|
4123
|
211-02
|
|
4123
|
214-01
|
5. Tercera
forma normal: eliminar los datos no dependientes de la clave
En el último ejemplo, Despacho-Tut (el número de despacho del tutor) es funcionalmente dependiente del atributo Tutor. La solución es pasar ese atributo de la tabla Alumnos a la tabla Personal, según se muestra a continuación:
Alumnos:
En el último ejemplo, Despacho-Tut (el número de despacho del tutor) es funcionalmente dependiente del atributo Tutor. La solución es pasar ese atributo de la tabla Alumnos a la tabla Personal, según se muestra a continuación:
Alumnos:
|
Nº alumno
|
Tutor
|
|
1022
|
García
|
|
4123
|
Díaz
|
6.
Personal:
Personal:
|
Nombre
|
Habitación
|
Dept
|
|
García
|
412
|
42
|
|
Díaz
|
216
|
42
|
--------------------------------------------------------------------------------------------------------------------------
INTRODUCCION.- Idealmente, los compiladores deberían producir código
objeto que fuera tan bueno como si estuviera escrito directamente por un buen
programador. La realidad es que esto es difícil de conseguir y muy pocas veces
se alcanza esa meta. Sin embargo, el código generado por el compilador puede
ser mejorado por medio de unas transformaciones que se han denominado
tradicionalmente optimizaciones, aunque el término optimización es impropio ya
que raramente se consigue que el código generado sea el mejor posible. El
objetivo de las técnicas de optimización es mejorar el programa objeto para que
nos dé un rendimiento mayor. La mayoría de estas técnicas vienen a compensar
ciertas ineficiencias que aparecen en el lenguaje fuente, ineficiencias que son
inherentes al concepto de lenguaje de alto nivel, el cual suprime detalles de
la máquina objeto para facilitar la tarea de implementar un algoritmo. Las
distintas técnicas de optimización se pueden clasificar o dividir de diversas
formas. Por una parte podemos hablar de aquellas técnicas que son dependientes
de la máquina, y aquellas que son independientes de la máquina (o sea, técnicas
que sólo se pueden aplicar a una determinada máquina objeto y técnicas que son
aplicables a cualquier máquina objeto). Por otra parte, las técnicas de
optimización se dividen también en locales y globales. Las técnicas de
optimización locales analizarán sólo pequeñas porciones de código y en ellas
realizarán mejoras, mientras que para la aplicación de las técnicas globales
será necesario el análisis de todo el código. Cada optimización está basada en
una función de coste y en una transformación que preserve el significado del
programa. Mediante la función de coste queremos evaluar la mejora que hemos
obtenido con esa optimización y si compensa con el esfuerzo que el compilador
realiza para poder llevarla a cabo. Los criterios más comunes que se suelen
emplear son el ahorro en el tamaño del código, la reducción del tiempo de
ejecución y la mejora de las necesidades del espacio para los datos del
programa. En cuanto a preservar el significado del programa, es lógico que no
tendría sentido realizar optimizaciones que modificaran el comportamiento del
programa. Aunque parezca evidente, puede haber complicadas optimizaciones que
fallen en ese aspecto. Por último, comentar que por muchas optimizaciones que
se hayan realizado para mejorar el rendimiento de un programa, siempre se
obtendrá un mejor rendimiento si se utiliza un algoritmo mejor. Por todo ello,
para obtener un buen programa lo primero es ver qué algoritmo utilizamos y si
no es posible desarrollar otro más eficiente. Una vez implementado el mejor
algoritmo, ya se puede entonces optimizar el código obtenido a partir de él
para mejorar el rendimiento del programa.
TIPOS DE OPTIMIZACIÓN
Existen diversas técnicas de optimización
que se aplican al código generado para un programa sencillo. Por programa
sencillo entendemos aquel que se reduce a un sólo procedimiento o subrutina.
Las técnicas de optimización a través de varios procedimientos se reducen a
aplicar las vistas aquí a cada uno de los procedimientos y después realizar un
análisis interprocedural. Este último tipo de análisis no lo vamos a
desarrollar en este artículo. Partiendo de un programa sencillo, obtenemos
código intermedio de tres direcciones [AHO77], pues es una representación
adecuada del programa sobre la que emplear las diversas técnicas de
optimización. A partir de aquí dividimos el programa en bloques básicos
[AHO86], o secuencia de sentencias en las cuales el flujo de control empieza al
principio y acaba al final, sin posibilidad de parar o de tener saltos. Las
sentencias de un bloque básico constituyen una unidad sobre la cual se aplican
las optimizaciones locales. Estas optimizaciones se pueden dividir en: a)
Optimizaciones que no modifican la estructura. Son: 1. Eliminación de
sub-expresiones comunes. 2. Eliminación de código muerto. 3. Renombrar
variables temporales. 4. Intercambio de sentencias independientes adyacentes.
b) Transformaciones algebraicas. Son aquellas transformaciones que simplifican
expresiones y/o reemplazan operaciones costosas de la máquina por otras menos
costosas. Además de este tipo de optimizaciones locales a un bloque básico,
existe otro tipo de optimizaciones aún más locales, pues su ámbito se reduce a
una breve secuencia de instrucciones. A este tipo de optimización local se le
llama optimización peephole, e intenta mejorar el rendimiento del programa por
medio de reemplazar esa breve secuencia de instrucciones objeto por otra
secuencia más corta y/o más rápida. Hay varios tipos de optimización peephole,
siendo los más usuales los siguientes: 1. Eliminación de instrucciones
redundantes. 2. Optimizaciones en el flujo de control. 3. Simplificaciones
algebraicas. 4. Uso de instrucciones máquina específicas. Debido a la
naturaleza de este tipo de optimización, su salida es susceptible de ser
optimizada de nuevo, con lo que serán necesarias varias pasadas para lograr la
máxima optimización. Una aplicación de este tipo de optimización se puede
encontrar en el kit ACK desarrollado por Tanembaum [Tane82], donde se describen
123 combinaciones distintas de sentencias de código intermedio con sus
correspondientes equivalencias. Las técnicas de optimización global se basan
todos ellos en el análisis global de flujo de datos. Este análisis se realiza
para el código de todo el programa, es decir, a lo largo de los distintos
bloques básicos que forman el código del programa. Suponiendo que tenemos la
información que nos proporciona este análisis, que lo veremos en el siguiente
apartado, hay dos tipos de optimizaciones importantes que se realizan: la
localización y la asignación global de registros para las variables, y las
optimizaciones que se realizan en los bucles. a) Localización y asignación de
registros.- Para una máquina con registros -lo común en los procesadores
actuales- las instrucciones cuyos operandos están en los registros de la
máquina son más cortas y más rápidas que aquellas que tratan con operandos que
están en la memoria. Es por tanto importante decidir qué variables se deben
almacenar en los registros (localización) y en qué registro se debe almacenar
cada variable (asignación). Existen diversas estrategias para la localización y
asignación de los registros. Es frecuente asignar algún número fijo de
registros que contengan las variables más usadas en un bucle interno, sirviendo
los registros restantes para las variables locales a cada bloque básico. Un
método sencillo para determinar la ganancia que obtenemos por almacenar la
variable "x" durante el bucle L es el siguiente: 1. Contaremos un
ahorro de una unidad por cada referencia a x en el bucle si x está en un
registro y no está precedida por una asignación a x en el mismo bloque básico
(debido a la naturaleza del algoritmo que empleamos para generar código -ver
[AHO86]-). 2. Contaremos un ahorro de dos unidades si x es una variable viva a
la salida de un bloque básico en el cual se le ha asignado un valor a x, debido
a que evitamos almacenar el valor de x a la salida de ese bloque. Entonces, una
fórmula aproximada para calcular el beneficio obtenido por colocar la variable
x en un registro en el bucle L es: Σ ( use(x,B) + 2*live(x,B) ) bloques B en L
donde use(x,B) es el número de veces que x es usada en B antes de que sea
definida, y live(x,B) es 1 si x está viva a la salida de B y se le asigna un
valor en B, y 0 en cualquier otro caso. El cálculo de use(x,B) y live(x,B) se
realiza gracias al análisis global del flujo de datos. b) Optimizaciones en
bucles. Habitualmente, un programa pasa la mayor parte del tiempo de la
ejecución en un trozo de código pequeño. A este fenómeno se le conoce como la
regla 90-10, queriendo decir que el 90% del tiempo es pasado en el 10% del
código. Este 10% del código suele estar constituido por bucles, y de ahí la importancia
de una correcta optimización del código que forma parte de los bucles. Las
principales optimizaciones que se realizan en los bucles son las siguientes: 1.
Movimiento de código. 2. Eliminación de variables inducidas. 3. Sustitución de
variables costosas por otras menos costosas. Y también se suelen aplicar
(aunque con menor importancia): 4. Expansión de código (loop unrolling). 5.
Unión de bucles (loop jamming).
CONCLUSION.- Una vez presentados los diversos tipos de optimización
que se pueden presentar en un compilador, se ha dedicado una especial atención
al análisis global de las ecuaciones de flujo de datos. Dentro de este análisis
global, se ha desarrollado con atención el denominado análisis ud
(uso-definición), mostrando las ecuaciones y los posibles tipos de optimización
a que da lugar este análisis de un programa.
FUENTES:
No hay comentarios:
Publicar un comentario