Download Sin título de diapositiva - LIDeCC

Simulación
Dr. Ignacio Ponzoni
Clase XXI: Simulación de Sistemas de Computación
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Año 2005
Simulación de Sistemas
de Computación
•
•
•
Los sistemas de cómputo poseen un alto nivel de complejidad.
Por un lado, la cantidad y variedad de componentes que
conforman estos sistemas es abrumadora.
 Basta con pensar que tan sólo en un único chip es posible
integrar alrededor de 10 millones de transistores.
Por otra parte, el comportamiento dinámico de estos sistema
requiere trabajar con diferentes escalas de tiempo que hacen
más difícil su modelado.

En un extremo tenemos el tiempo que insume a un
transistor cambiar de estado (10-11 segundos), y en otro las
operaciones que requieren interacción humana (del orden
de varios segundos o minutos).
Simulación
2
Prof. Dr. Ignacio Ponzoni
Sistemas de Computación
Niveles de Abstracción
•A
fin de poder manejar esta complejidad, los
sistemas de computación pueden ser analizados de
manera jerárquica y composicional, lográndose
así distintos niveles de abstracción.
• De
este modo el sistema es visto a través de
diferentes capas, haciendo una descomposición en
subsistemas cada vez más pequeños.
Simulación
3
Prof. Dr. Ignacio Ponzoni
Sistemas de Computación
Niveles de Abstracción
Simulación
4
Prof. Dr. Ignacio Ponzoni
Componentes de los Niveles
•
•
La simulación puede ser usada para estudiar el desempeño
del sistema en los diferentes niveles.
En cada caso, tendremos distintos componentes:
• a nivel del sistema: estaciones de trabajo, tareas que circulan
por el sistema, colas de servicios pendientes, etc.
• a nivel del procesador: CPU, cache, memoria principal,
registros, bus, etc.
• a nivel de CPU: unidad de interface de memoria, unidad
aritmético-lógica, etc.
• a nivel de compuertas: componentes eléctricas, señales
débiles, etc.
Simulación
5
Prof. Dr. Ignacio Ponzoni
Estudios de Simulación en
distintos Niveles de Abstracción
• Bajo nivel: se simulan y estudian propiedades físicas
•
específicas de hardware:
 niveles eléctricos,
 comportamiento lógico del diseño, etc.
Alto nivel: se modela y simula el sistema ante
diferentes condiciones de operación:
 respuesta
del sistema ante procesos con
determinas demandas de recursos,
 comportamiento de sistemas de I/O, etc.
Simulación
6
Prof. Dr. Ignacio Ponzoni
Herramientas para Simular
Sistemas de Computación
• La selección del software a utilizar para simular un
sistema de computación depende de:
 El nivel de abstracción,
 Las características intrínsecas del sistema:
• arquitectura, distribuido, paralelo, plataformas,
tipo de red y conexión, etc.
 El tipo de estudio de simulación a realizar:
• Evaluación de desempeño,
• Diseño de nuevos sistemas.
Simulación
7
Prof. Dr. Ignacio Ponzoni
Herramientas para Simular
Sistemas de Computación
Alto Nivel de Abstracción
• Paquetes de Simulación tipo VIMS:


Estos paquetes permiten describir la topología de un
sistema formado por varias estaciones de trabajo
interconectadas en red.
Ejemplo: Network.II.
Este software de la compañía CACI fue desarrollado
en SimScript II y es un ejemplo de simulador basado
en procesos para redes de computación.
Simulación
8
Prof. Dr. Ignacio Ponzoni
Herramientas para Simular
Sistemas de Computación
Niveles Bajos de Abstracción
•
Para los tres niveles más bajos de abstracción, es posible
utilizar el lenguaje VHDL (Very High Speed Integrated
Circuit Hardware Description Language).
•
VDHL surgió en los 80 como un estándar para la
especificación de sistemas eléctricos digitales.
•
•
Este lenguaje permite especificar de forma separada la
topología del sistema de su comportamiento.
Desventajas, es un lenguaje complejo, difícil de dominar
debido a la gran cantidad de constructores que brinda, y los
compiladores comerciales poseen un costo muy elevado.
Simulación
9
Prof. Dr. Ignacio Ponzoni
Herramientas para Simular
Sistemas de Computación
Otras Alternativas
• Programación
utilizando lenguajes de alto nivel
extendidos con librerías para simulación:

SimPack, C++SIM, CSIM, Awesime, SSF.
• Estas herramientas definen objetos y librerías para
ser usadas en C, C++ y Java.
• El comportamiento del modelo se expresa como un
programa que manipula los objetos predefinidos y
que extiende las clases bases.
Simulación
10
Prof. Dr. Ignacio Ponzoni
Simulación de Sistemas de Cómputo
Modelado de los Datos de Entrada
• Entradas generadas de forma estocástica:


son útiles en modelos de mayor abstracción.
permiten estudiar un sistema ante diversos
escenarios (sólo ajustando los parámetros del
modelo de entrada).
• Datos muestrados:


Simulación
aplicables en simulaciones de bajo nivel.
permite comparar modelos que implementan
distintas políticas (usando el mismo set de datos)
11
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
• Concepto de memoria virtual:



Un proceso puede direccionar más memoria RAM
que la disponible físicamente.
Por tal motivo, el Sistema Operativo organiza la
memoria requerida por el código y datos de un
programa en páginas de igual tamaño.
Luego, las distintas páginas son traídas a
memoria principal por el SO a medida que van
siendo referenciadas por el proceso en ejecución.
Simulación
12
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
page 0
page 1
page 2
page 0
page 1
page 2
page f
page n
Memoria física
del sistema (RAM)
Memoria secundaria
del sistema (HD)
Memoria virtual de un proceso
Simulación
13
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
• Localidad de referencia:
• Las páginas que fueron referenciadas en el pasado
más cercano tienen mayor probabilidad de ser
referenciadas en el futuro más inminente.
• Working sets:
• Representan el conjunto de páginas referenciadas en
las últimas n referencias a memoria.
• Este
conjunto se utiliza para decidir la política de
reemplazo cuando se producen page fault.
Simulación
14
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
• Objetivo
•
•
de los estudios de simulación en estos
problemas es evaluar el desempeño de distintas
políticas para gestionar el working set a fin de
reducir la cantidad de page faults.
En estos casos, el comportamiento de un programa
puede modelarse como una secuencia de fases,
donde en cada una de ellas se hace referencia a un
working set.
Cuando se produce una modificación en el working
set, se cambia de fase.
Simulación
15
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
• Datos de entrada de la simulación:

Referencias a páginas de memoria.
• Formas de modelar la entrada:

Referencias generadas aleatoriamente.

Referencias generadas mediante archivos de
muestreo obtenido de programas.

Simulación
Referencias generadas dinámicamente mediante
muestreo de programas ejecutados en forma
simultanea con la simulación.
16
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
Modelo estocástico para generación de referencias
• Se define un working set inicial elegido aleatoriamente.
• Se asigna una probabilidad baja p a la posibilidad de
•
•
que una nueva referencia a memoria esté fuera del
working set actual, y 1-p a la posibilidad de que la
nueva referencia esté dentro del working set actual.
Se generan dos números aleatorios r1 y r2. Con r1 se
decide si hay un cambio de fase o no, y con r2 cual es la
página referenciada.
Distintos escenarios pueden ser simulados ajustando
las probabilidades.
Simulación
17
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
Referencias generadas mediante archivos de muestreo
obtenido de programas
• Se obtienen muestras de las referencias a memoria
realizadas por distintos programas reales.
• Estas secuencias de referencias se almacenan en
archivos que luego alimentan al simulador.
• Desventaja: el conjunto de referencias muestradas
puede ser muy grande y requerir gran cantidad de
almacenamiento.
Simulación
18
Prof. Dr. Ignacio Ponzoni
Caso de Estudio de Modelado de la Entrada
Referencias a Memoria Virtual
Referencias generadas mediante muestreo dinámico
•
•
Se generan los datos y se
realiza la simulación al mismo
tiempo.
Ventaja: se evita la necesidad
de muestrear y almacenar gran
cantidad de datos.
Simulación
19
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de Sistema
Simulación Sistema Servidor WWW
Se desea estudiar el desempeño
de un sistema de computación
para un portal de servicios web.
El router distribuye los
requerimientos provenientes de
los usuarios del portal entre los
servidores web.
Los servidores web manejan la
interacción de las aplicaciones
con la WWW (motores de
búsqueda, etc.).
Los servidores de datos reciben
requerimientos de los servidores
de aplicación.
Simulación
20
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de Sistema
Simulación Sistema Servidor WWW
•
•
•
•
Tipo de Simulación: Eventos Discretos (Sistema de Colas).
Datos de entrada: requerimientos (Tasks).
Entidades y Recursos:

Router, Servidores,

Requerimientos y Discos.
Actividades:



Arribos de Requerimientos al Router (Eventos Exógenos),
Generación de Requerimientos por parte de los Servidores
(Eventos Endógenos),
Inicio y Fin de Servicios del Router y Servidores.
Simulación
21
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de Sistema
Simulación Sistema Servidor WWW
•
Especificación de Subsistemas:




•
Router: política de balanceo de carga, tiempos de ejecución, etc.
Servidores Web: cantidad, disciplina de colas, tiempos de
ejecución, etc.
Servidores de Aplicación: cantidad, disciplina de colas,
características de las aplicaciones, comportamiento, tiempos de
ejecución, etc.
Servidores de Datos: cantidad, número de discos, disciplina de
colas, política de memoria, tiempos de acceso a disco, etc.
Variables de decisión: todas las vinculadas a la parametrización de
los subsistemas que sean controlables por el modelador.
Simulación
22
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de CPU
Simulación de Pipelines
• Potenciales objetivos para estudios de simulación:
• Como acelerar la ejecución de instrucciones en la CPU a
través de un aumento del nivel de concurrencia mediante
la comparación de distintas técnicas de pipelining.
• Tipo de Simulación: Eventos Discretos.
• Datos de entrada: secuencias de instrucciones.
• Entidades y Recursos:
• Instrucciones,
• Registros de almacenamiento utilizados por la CPU.
• Actividades:
• Las distintas etapas en que el pipeling subdivide la
ejecución de una instrucción.
Simulación
23
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de CPU
Simulación de Pipelines
• Implementación del avance de tiempo:
• Basado en procesos: cada proceso corresponde al ciclo
de vida de una instrucción. La interacción está dada por
el acceso a los registros de almacenamiento.
• Método de las Tres Fases o Planificación de Eventos:
cada vez que una instrucción culmina una etapa se
genera un nuevo evento para la etapa siguiente.
• Barrido de actividades: en cada ciclo de CPU (j) se
examina/n la/s instrucciones activas y se determinan que
actividades asociadas pueden realizarse en el ciclo j+1
Simulación
24
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de Procesador
Simulación de Jerarquía de Memorias
•
Potenciales objetivos para estudios de simulación:
• Como reducir el gap entre la velocidad de operación de la
CPU y la memoria principal.
• Estos estudios requieren construir modelos de simulación
que reflejen la interacción entre las distintas jerarquías
de memorias: cache L1, cache L2 y memoria principal.
• Objetivo en término de variables de salida: maximizar el
hit ratio de cada nivel del cache.
•
Forma más utilizada para generar los datos de entrada para
estas simulaciones es la ejecución directa.
Simulación
25
Prof. Dr. Ignacio Ponzoni
Caso de Estudio a Nivel de Procesador
Simulación de Jerarquía de Memorias
• Variables de decisión para el diseño de experimentos:



Empleo de diferentes políticas para asegurar la
consistencia entre los datos almacenados en
distintos niveles de la jerarquía de memoria. Por
ejemplo: write-through o write-back.
Empleo de diferentes algoritmos de reemplazo para
decidir que páginas remover del cache. Por
ejemplo: Algoritmo LRU (Least-recently-used).
Definir distintos tamaños para los cache.
Simulación
26
Prof. Dr. Ignacio Ponzoni
Recomendaciones
• Lectura sugerida:

Capítulo 14 del libro Discrete-Event System
Simulation de Banks, Carson, Nelson y Nicol.
• Próxima clase:

Simulación
Presentación de Network.II.
27
Prof. Dr. Ignacio Ponzoni