Download Sin título de diapositiva - LIDeCC
Document related concepts
no text concepts found
Transcript
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