Introducción a la simulación de sistemas distribuidos · Generación de eventos § Dirigidas por...

Post on 10-Jan-2020

4 views 0 download

Transcript of Introducción a la simulación de sistemas distribuidos · Generación de eventos § Dirigidas por...

Máster en Ciencia y Tecnología InformáticaCurso 2017-2018

Félix García CarballeiraGrupo de Arquitectura de Computadoresfelix.garcia@uc3m.es

Introducción a la simulación de sistemas distribuidos

¿Por qué es importante la simulación?

§ Conocer el comportamiento de un sistema cuando no se dispone de él bajo una determinada carga de trabajo

§ Ejemplos:q Conocer el comportamiento de un determinado algoritmo de

planificaciónq Comparar el funcionamiento de dos algoritmos de

distribución de cargaq Conocer el comportamiento de un sistema de ficheros

distribuido

•Félix García Carballeira •Introducción a la simulación •2

Contenido

§ Conceptos básicos sobre simulación§ Introducción a Simgrid§ Métricas de rendimiento§ Experimentos de simulación§ Estimación de errores§ Comparación de dos alternativas

•Félix García Carballeira •Introducción a la simulación •3

Ejemplo

•Félix García Carballeira •Introducción a la simulación •4

•trabajos

§ Al servidor llegan 5 tareas por hora. El tiempo entre llegadas sigue una distribución exponencial q Distribución exponencial de parámetro λ=5q Tiempo medio entre llegadas = 1/λ = 0.2 h = 12 minutos

§ El tiempo medio de ejecución de cada trabajo sigue una distribución exponencial q Tiempo medio = 1/µ = 0.1666 h = 10 minutosq Distribución exponencial de parámetro µ=6 (6 trabajos por hora)q El servidor ejecuta las tareas según política FCFS sin expulsión

§ ¿Cuál es el tiempo medio de ejecución de las tareas?

•servidor

Tiempo de ejecución de los trabajos

•Félix García Carballeira •Introducción a la simulación •5

F x( ) = 1− e−µx si x ≥ 00 si x < 0

#$%

&%

para µ = 5

Ejemplo

§ Queremos saber el comportamiento del sistema:q Tiempo medio de ejecución de las tareasq Número medio de tareas en la cola del servidor esperando

para su ejecución

•Félix García Carballeira •Introducción a la simulación •6

Enfoques de estudio

•Félix García Carballeira •Introducción a la simulación •7

sistema

Enfoques de estudio

•Félix García Carballeira •Introducción a la simulación •8

sistema

Experimentacióncon sistema

Enfoques de estudio

•Félix García Carballeira •Introducción a la simulación •9

sistema

Experimentacióncon sistema

Experimentacióncon un modelo

Enfoques de estudio

•Félix García Carballeira •Introducción a la simulación •10

sistema

Experimentacióncon sistema

Experimentacióncon un modelo

Modelo físico

Enfoques de estudio

•Félix García Carballeira •Introducción a la simulación •11

sistema

Experimentacióncon sistema

Experimentacióncon un modelo

Modelo físico Modelo matemático

Enfoques de estudio para el ejemplo

•Félix García Carballeira •Introducción a la simulación •12

sistema

Experimentacióncon sistema

Experimentacióncon un modelo

Modelo físico Modelo matemático

Solución analítica

Enfoques de estudio para el ejemplo

•Félix García Carballeira •Introducción a la simulación •13

sistema

Experimentacióncon sistema

Experimentacióncon un modelo

Modelo físico Modelo matemático

Solución analítica Simulación

Tipos de sistemas

§ Discretos: las variables de estado cambian de valor en instantes separados en el tiempoq El número de paquetes recibidos cambia cuando llega un

paqueteq El número de procesos en una cola de ejecución cambia

cuando llega un nuevo proceso para ejecutar§ Continuos: las variables de estado cambian de forma continua

con respecto al tiempoq La distancia recorrida por un avión cambia en cada instante

del tiempo

•Félix García Carballeira •Introducción a la simulación •14

Tipos de simulación

§ Emulación§ Simulación estática/dinámica§ Simulación determinista/estocástica§ Simulación de sistemas continuos/discretos§ Simulación de tiempo continuo/discreto

•Félix García Carballeira •Introducción a la simulación •15

Emulación

§ Un emulador es una combinación de HW/SW que el recrea el funcionamiento/comportamiento de otro sistema, es decir, ofrece el servicio que ofrece el sistema que está emulando

§ Enfoque experimental que permite la ejecución de aplicaciones reales sobre un entorno virtual

•Félix García Carballeira •Introducción a la simulación •16

Tipos de simulación: tiempo

§ Simulación estáticaq No utiliza como parámetro el tiempo. La simulación se

ejecuta hasta alcanzar un determinado equilibrioq Ejemplo: simulaciones de Monte Carlo

§ Simulación estática está dirigida por secuencias de números aleatorios

§ Simulación dinámicaq El estado del sistema varía con el tiempo

•Félix García Carballeira •Introducción a la simulación •17

Ejemplo de simulación de Monte Carlo

§ Estimar el valor del número π§ Se parte de un circulo con radio 1

•Félix García Carballeira •Introducción a la simulación •18

§ El área del cuadrado mostrado en la figura es 1

§ El área de la superficie inscrita en este cuadrado es A=πr2/4= π/4q El valor de π=4A

§ Objetivo: determinar A

Ejemplo de simulación de Monte Carlo

•Félix García Carballeira •Introducción a la simulación •19

§ Se generan N pares de valores aleatorios (x,y)

§ Se contabilizan cuantos caen dentro de arco Nc

§ La probabilidad de que el punto esté dentro del arco es proporcional al área A=(π × 12) / 4

§ π/4 = Nc/N§ Ejemplo:

q N=1000000q Nc=785581q π=3,1423

Tipos de simulación

§ Deterministaq No interviene ninguna variable aleatoriaq Salida=F(entrada, estado)q Ejemplo: ecuación diferencial que describe una reacción química

§ Estocásticaq Entradas y/o relaciones se modelan como variables aleatoriasq Las salidas de la simulación deben tratarse como variables

aleatoriasq Ejemplo: la llegada de peticiones a un servidor Web no es

determinista, sigue una determinada función de distribución

•Félix García Carballeira •Introducción a la simulación •20

Tipos de simulación

§ Simulación de sistemas continuosq Las variables de estado evolucionan de forma continua con

respecto al tiempoq Simulación de sistemas físicos

§ Simulación de sistemas discretosq Las variables de estado cambian de valor en momentos

instantáneos de tiempoq Ejemplo: el número de procesos en una cola cambia en el

momento en el que llega un nuevo trabajo

•Félix García Carballeira •Introducción a la simulación •21

Tipos de simulación

§ Simulación de tiempo continuoq Utilizan variables que cambian de forma continua con el

tiempoq Ejemplo: modelos basados en ecuaciones diferenciales

§ Simulación de tiempo discretoq Las variables cambian en un conjunto discreto/numerable

de instantes de tiempo

•Félix García Carballeira •Introducción a la simulación •22

Simulación de eventos discretos

§ Modela un sistema cuyo estado global cambia en función del tiempo

§ El estado global se actualiza cada vez que ocurre un evento§ Características

q Dinámicaq Estocásticaq Discretaq Tiempo discreto

•Félix García Carballeira •Introducción a la simulación •23

Eventos típicos

§ ei= evento del sistemaq ti = tiempo de llegada de una petición, tarea, trabajo, etc.q ci= ti+Di+Si= tiempo de servicio de una petición, tarea, etc

§ Ai = tj-ti = tiempo entre llegadas§ Si= tiempo de servicio para la petición, tarea, trabajo, etc.§ Di= tiempo en la cola del servidor que atiende peticiones, etc.

•Félix García Carballeira •Introducción a la simulación •24

•0 t1 t2 c1 t3 c2 tiempo

•e0 e1 e2 e3 e4 e5

•A1 A2 A3

• S1 S2

Algoritmo de simulación

Inicializar las variables de estado

Tiempo = 0

Obtener el primer evento

while ((no haya mas eventos) AND (tiempo < máximo)) {

avanzar el tiempo

Obtener/eliminar el siguiente evento de la lista

Procesar el evento {

Actualizar el estado global

Actualizar las estadísticas de la simulación

Generar nuevos eventos y añadirlos a la lista de eventos

}

}

Imprimir resultados

•Félix García Carballeira •Introducción a la simulación •25

Generación de eventos

§ Dirigidas por trazaq Se registran las trazas de eventos que ocurren en un sistema

real y se alimenta el simulador con las mismas§ Dirigidas por una distribución aleatoria

q Los eventos y entradas son generadas a partir de una determina función de distribución

q Ejemplo: la llegada de trabajos para su ejecución se puede modelar como la cantidad de tiempo que transcurre entre dos llegadas consecutivas. Esta cantidad se puede modelar con una función de distribución exponencial

•Félix García Carballeira •Introducción a la simulación •26

Ejemplo de traza

§ Traza independiente del tiempo

•Félix García Carballeira •Introducción a la simulación •27

•© G. Markomanolis•U. De Lyon, 2014

Generación de valores aleatorios

§ Un generador de números pseudoaleatorios genera una secuencia de valores zi, que se aproximan a la distribución U(0,1)

§ Los generadores de números pseudoaleatorios parten de una semilla inicial z0q Distintos valores de la semilla generan distintas secuencias

de números

•Félix García Carballeira •Introducción a la simulación •28

Requisitos de un generador de números pseudoaleatorios§ Aleatoriedad

q Muestras aproximadas a U(0,1)q Sin correlación entre las muestras

§ Eficienciaq Mide el tiempo y memoria necesaria para la generación

§ Periodo máximoq Número de muestras que se pueden obtener antes de repetir

la secuenciaq El generador Mersenne twister tiene un periodo de 219937 -1

§ Secuencia reproducibleq Para poder repetir exactamente la misma simulación

•Félix García Carballeira •Introducción a la simulación •29

Generación de variables aleatorias

§ ¿Cómo generar variables aleatorias de otras funciones de distribución a partir de una muestra de variables aleatorias con distribución U(0,1)?

§ Métodosq Método de la transformada inversaq Método de la composiciónq Método de la convoluciónq Método de aceptación-rechazo

•Félix García Carballeira •Introducción a la simulación •30

Método de la transformada inversa

§ Sea X una variable aleatoria con una función de distribución Fx

§ Para generar una variable aleatoria X ~ FX

q Se genera u ~ U(0,1)q Se devuelve x = F-1(u)

§ x es una muestra de una variable aleatoria con función de distribución Fx

§ F-1(U) siempre está definida porque 0£U£1 y F estácomprendida en [0,1]

•Félix García Carballeira •Introducción a la simulación •31

Método de la transformada inversa

•Félix García Carballeira •Introducción a la simulación •32

U

F(x)

xx = F-1 (U)

Dis

tribu

ción

uni

form

e

1

0

Ejemplo: función de distribución exponencial§ Si X es una variable aleatoria exponencial con parámetro l:§ Función de distribución:

§ Media y varianza

•Félix García Carballeira •Introducción a la simulación •33

( )îíì

<³-

=-

0 x si 00 xsi 1 xe

xFl

2

1)(1][ll

== XVXE

Ejemplo: función de distribución exponencial§ Si u es una muestra de una variable aleatoria U(0,1)§ Entonces:

§ x es una muestra de una variable aleatoria exponencial con parámetro l

•Félix García Carballeira •Introducción a la simulación •34

)1ln(1 ux --=l

Ejemplo

•Félix García Carballeira •Introducción a la simulación •35

F x( ) = 1− e−µx si x ≥ 00 si x < 0

#$%

&%

para µ = 5

Múltiples variables

§ En un programa de simulación puede haber muchas variables aleatorias

§ Los números pseudoaleatorios se generan bajo demanda, cada vez que se necesita uno

§ Si se usa la misma semilla para generarlas todas, las variables estarán correladasq Se elimina la hipótesis de que las variables aleatorias son

independientes§ Usar distintas semillas para generar cada una

•Félix García Carballeira •Introducción a la simulación •36

Entornos y lenguajes de simulación

§ OMNet++§ PARSEC§ Desmo-J§ JavaSim§ Adves§ OPNET§ Arena§ Simio§ Simscript§ Simulink§ Simgrid•Félix García Carballeira •Introducción a la simulación •37

Introducción a SIMGRID

§ SIMGRID: Versatile Simulation of Distributed Systems§ http://simgrid.gforge.inria.fr§ Permite la simulación de sistemas distribuidos de gran escala

q Grids, Clouds, HPC, P2P, aplicaciones MPI, …§ Instalación en :

q http://simgrid.gforge.inria.fr/download.html

•Félix García Carballeira •Introducción a la simulación •38

Introducción a SIMGRID

§ Ofrece un conjunto de funcionalidades para simular aplicaciones distribuidas en entornos distribuidos heterogéneos

q SimDag para grafos de aplicaciones paralelasq SMPI para código MPIq MSG en cualquier otro caso

•Félix García Carballeira •Introducción a la simulación •39

MSG

§ MSG: simulación de procesos secuenciales concurrentes§ Principales abstracciones:

q Agente: algún código, con datos, que ejecuta en un hostq Task: cantidad de trabajo a realizar y datos a intercambiarq Host: localización en la que ejecutan los agentesq Mailbox: lugar donde se envían los mensajes y reciben los

mensajes§ Independientes de la posición de la red§ Los mensajes se envía a un mailbox y se reciben de un mailbox§ Se identifican como strings

q Funcionamiento síncrono o asíncrono

•Félix García Carballeira •Introducción a la simulación •40

Ejemplo

•Félix García Carballeira •Introducción a la simulación •41

•host1 •host2

•100 MFLOPS •100 MFLOPS•Ancho de banda: 1 Gbps•Latencia: 10 ms

Ejemplo

•Félix García Carballeira •Introducción a la simulación •42

•host1 •host2

•100 MFLOPS •100 MFLOPS•Ancho de banda: 1 GBps•Latencia: 10 ms

•master •worker

•100 tareas§ Tamaño: 100000 bytes§ Duración del cálculo: 50 MFLOPS

(cantidad de procesamiento en flops)

Descripción de la plataformaplatform.xml?xml version='1.0'?><!DOCTYPE platform SYSTEM"http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd"><platform version=”4.1">

<AS id="AS0" routing="Full"><host id="host1" speed="1E8"/><host id="host2" speed="1E8"/>

<link id="link1" bandwidth=“1GBps" latency=”10ms"/>

<route src="host1" dst="host2"><link_ctn id="link1"/>

</route>

</AS></platform>

•Félix García Carballeira •Introducción a la simulación •43

Descripción del desplieguedeployment.xml<?xml version='1.0'?><!DOCTYPE platform SYSTEM"http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd"><platform version=”4.1">

<!-- The master process -->

<process host="host1" function="master"><argument value="100"/><!--argv[1]:#tasks--><argument value="1"/><!--argv[2]:#workers-->

</process>

<!-- The workers --><process host="host2" function="worker">

<argument value="0"/></process>

</platform>

Félix García Carballeira •Introducción a la simulación •44

Definición del master#define task_comp_size 50000000#define task_comm_size 100000

int master(int argc, char *argv[]) int i;char mailbox[256]; char buf[256];msg_task_t task = NULL;

number_of_jobs = atoi(argv[1]); number_of_workers = atoi(argv[2]);

for (i = 1; i <= number_of_jobs; i++) {// Round Robinsprintf(mailbox, "worker-%d", i % number_of_workers);sprintf(buf, "Task_%d", i);

task = MSG_task_create(buf, task_comp_size, task_comm_size, NULL);

MSG_task_send(task, mailbox);}for (i = 0; i < number_of_workers; i++) {

sprintf(mailbox, "worker-%d", i % number_of_workers);msg_task_t finalize = MSG_task_create("finalize", 0, 0, 0);MSG_task_send(finalize, mailbox);

}return 0;

}

•Félix García Carballeira •Introducción a la simulación •45

Definición del worker

int worker(int argc, char *argv[]) {msg_task_t task; int errcode;char mailbox[80];int id = atoi(argv[1]);

sprintf(mailbox,"worker-%d",id);while(1) {

errcode = MSG_task_receive(&task, mailbox);xbt_assert(errcode == MSG_OK, "MSG_task_get failed");

if (!strcmp(MSG_task_get_name(task),"finalize")) {MSG_task_destroy(task);break;

}XBT_INFO("Processing '%s'", MSG_task_get_name(task));MSG_task_execute(task);XBT_INFO("'%s' done", MSG_task_get_name(task));MSG_task_destroy(task);

}return 0;

}

•Félix García Carballeira •Introducción a la simulación •46

Función main()

/** Main function */int main(int argc, char *argv[]){

MSG_init(&argc,argv);

/* Declare all existing agent, binding their name to their function */MSG_function_register("master", &master);MSG_function_register("worker", &worker);

/* Load a platform instance */MSG_create_environment(argv[1]);

/* Load a deployment file */MSG_launch_application(argv[2]);

MSG_main();XBT_INFO("Simulation took %g seconds",MSG_get_clock());

}

•Félix García Carballeira •Introducción a la simulación •47

Modificación

•Félix García Carballeira •Introducción a la simulación •48

•host1

•host2

•master

•worker

•host3 •worker

•100 tareas distribuidas de forma cíclica entre los dos

Nueva plataforma

<?xml version='1.0'?><!DOCTYPE platform SYSTEM"http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd"><platform version=”4.1">

<AS id="AS0" routing="Full"><host id="host1" speed="1E8"/><host id="host2" speed="1E8"/><host id="host3" speed="1E8"/>

<link id="link1" bandwidth=”1GBps" latency=”10ms"/><link id="link2" bandwidth=“1GBps" latency=”10ms"/>

<route src="host1" dst="host2"><link_ctn id="link1"/>

</route>

<route src="host1" dst="host3"><link_ctn id="link2"/>

</route></AS></platform>

•Félix García Carballeira •Introducción a la simulación •49

Nuevo despliegue

<?xml version='1.0'?><!DOCTYPE platform SYSTEM"http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd"><platform version=”4.1">

<!-- The master process --><process host="host1" function="master">

<argument value="100"/><!--argv[1]:#tasks--><argument value="2"/><!--argv[2]:#workers-->

</process>

<!-- The workers --><process host="host2" function="worker">

<argument value="0"/></process><process host="host3" function="worker">

<argument value="1"/></process>

</platform>

•Félix García Carballeira •Introducción a la simulación •50

Código sin fichero de despliegueint main(int argc, char *argv[]){

MSG_init(&argc,argv);

MSG_function_register("master", &master);MSG_function_register("worker", &worker);

/* Load a platform instance */MSG_create_environment(argv[1]);

char**argv1=xbt_new(char*,4); argc = 3;argv1[0] = bprintf("%s","master");argv1[1] = bprintf("%d",100);argv1[2] = bprintf("%d",1);argv1[3] = NULL;

MSG_process_create_with_arguments("master", master, NULL, MSG_get_host_by_name("host1"), argc, argv1);

char**argv2=xbt_new(char*,2); argc = 2;argv2[0] = bprintf("%s","server");argv2[1] = bprintf("%d",0);argv2[2] = NULL;MSG_process_create_with_arguments("worker", worker, NULL,

MSG_get_host_by_name("host2"), argc, argv2);

MSG_main();XBT_INFO("Simulation took %g seconds",MSG_get_clock());

}

•Félix García Carballeira •Introducción a la simulación •51

Descripción de plataformas en SimGrid

§ Plataforma en SimGrid: archivo XML que describe:q Hosts con su potencia de cómputoq Enlaces con sus anchos de banda y latenciaq Rutas entre hosts

•Félix García Carballeira •Introducción a la simulación •52

Elementos que se pueden describir

§ AS (autonomous system): unidad que contiene recursos y que define el encaminamiento entre ellos

§ Recursos que incluye un AS:q Hostq Linkq Routerq Cluster: hosts interconectados por una red dedicada

•Félix García Carballeira •Introducción a la simulación •53

Especificación de un host

<host id="host1”

speed="1000000000”

[state=“ON”]

[availability_file=“host.trace”]

[cores=“4”]

§ id: identificador del host§ speed: potencia en Flops§ availability_file: ficher de traza asociado§ state: estado inicial del host (ON/OFF)§ cores: número de cores

•Félix García Carballeira •Introducción a la simulación •54

Fichero de disponibilidad

§ En el instante 0: el host proporciona 500 Mflops§ En el instante 11.0: entrega 250 Mflops§ En el instante 20.0: entrega el 80%, 400 Mflps§ El proceso se repite

•Félix García Carballeira •Introducción a la simulación •55

Energía

<host id=”host1" speed="100.0Mf,50.0Mf,20.0Mf" >

<prop id=”watt_per_state" value="95.0:200.0, 93.0:170.0, 90.0:150.0" />

</host>

§ Define tres valores de potencia: 100, 50 y 20 Mflops§ Para cada valor se define un par con el consumo de potencia en watios

cuando el procesador está libre y cuando está a maximo carga

•Félix García Carballeira •Introducción a la simulación •56

•#include "simgrid/plugins/energy.h”

•....•sg_host_energy_plugin_init();•...•sg_host_get_consumed_energy(host);

Enlaces de red

<link id=“enlace_1”

bandwidth=“125MBps”

latency=“0.01”

[sharing_policy=“SHARED”] />

§ id: identificador del enlace§ bandwidth: ancho de banda en bytes/s§ latency: laencia del enlace en segundo:§ sharing_policy_

q SHARED (por defecto): Los flujos comparten el ancho de banda disponible

q FATPIPE: Cada flujo obtiene todo el ancho de banda del enlace

•Félix García Carballeira •Introducción a la simulación •57

Rutas

<host id="host1" power=“1E8"/><host id="host2" power="1E8"/><link id="link1" bandwidth=”1Gbps" latency=”100us"/>

<route src="host1" dst="host2"><link_ctn id="link1"/>

</route>

•Félix García Carballeira •Introducción a la simulación •58

•Host1•link1

•Host 2

Rutas con múltiples saltos<host id="host1" power="1E8"/><host id="host2" power="1E8"/><host id="host2" power="1E8"/>

<link id="link1" bandwidth="1E6" latency=”100ms"/><link id="link2" bandwidth="1E6" latency=”500us"/><link id="link3" bandwidth=“2E6" latency=”150ms"/><link id="link4" bandwidth=“2E6" latency=”100ms"/>

<route src="host1" dst="host3"><link_ctn id="link1"/><link_ctn id="link3"/><link_ctn id="link4"/>

</route>

<route src="host2" dst="host3"><link_ctn id="link2"/><link_ctn id="link3"/><link_ctn id="link4"/>

</route>

•Félix García Carballeira •Introducción a la simulación •59

•Host1 •Host 3•link1

•link3•link4

•Host 2

•link2

Especificaciones de routers

<router id=”R1”>

<router id=”R2”>

<route src=“A” dest=”R1”>

<link_ctn id=“link1”/>

</route>

<route src=“R1” dest=”B”>

<link_ctn id=“link2”/>

</route>

<route src=“R1” dest=”C”>

<link_ctn id=“link3”/>

</route>

•Félix García Carballeira •Introducción a la simulación •60

Definición de clusters

•Félix García Carballeira •Introducción a la simulación •61

Definición de clusters

•Félix García Carballeira •Introducción a la simulación •62

•<AS id="AS0" routing="Full">• <cluster id="my_cluster_1" prefix="c-" suffix=".me" radical="0-9"

• speed="1Gf" bw="125MBps" lat="50us" bb_bw="2.25GBps"

• bb_lat="500us" />

• <cluster id="my_cluster_2" prefix="c-" suffix=".me" radical="10-19"

• speed="1Gf" bw="125MBps" lat="50us" bb_bw="2.25GBps"

• bb_lat="500us" />

• <link id="backbone" bandwidth="1.25GBps" latency="500us" />

• <ASroute src="my_cluster_1" dst="my_cluster_2"

•gw_src="c-my_cluster_1_router.me"• gw_dst="c-my_cluster_2_router.me">

• <link_ctn id="backbone" />

• </ASroute>

•</AS>

Modelización básica de la red

§ Modelo básico:

q Size: tamaño del mensaje a enviarq Li,j: latencia entre i y jq Bi,j: ancho de banda entre i y j

§ Diferentes flujos F comparten un conjunto de enlaces E§ Para todo enlace j

•Félix García Carballeira •Introducción a la simulación •63

Timei, j = Li, j +sizeBi, j

fiSiel flujoiusael enlace j

∑ ≤Cj

Tipos de comunicación

§ Comunicaciones síncrona:q Buzones síncronos (por defecto)

§ Emisor y recetor deben coincidir en el tiempoq Buzones asíncronos

§ MSG_mailbox_set_async(nombre);§ El emisor en el send espera a que el mensaje llegue al host

destino (hay tiempo de red) aunque no espera el proceso receptor§ Comunicación asíncrona (MSG_task_isend, MSG_task_ireceive)

q El emisor continua su ejecución (tiempo de ejecución 0)q El receptor continua su ejecución si no hay mensajes

•Félix García Carballeira •Introducción a la simulación •64

Modelización de redes

§ Permite modelar:q Redes single-hopq Redes multi-hop

§ Simula el uso de una red compartido por varios flujos sobre múltiples enlaces

•Félix García Carballeira •Introducción a la simulación •65

Modelización de la CPU

§ Una CPU tiene una potencia en flop/sec§ Una tarea requiere size flops§ El tiempo para ejecutar la tarea será:

•Félix García Carballeira •Introducción a la simulación •66

secpowsize

SimDag

§ Permite crear DAG de tareasq Vértices: tareasq Arcos: relaciones de precedencia entre tareas

•Félix García Carballeira •Introducción a la simulación •67

SimDag

§ Permite crear DAG de tareasq Vértices: tareasq Arcos: relaciones de precedencia entre tareas

§ Planificar la ejecución de las tareas en los recursos

•Félix García Carballeira •Introducción a la simulación •68

Grafos dirigidos acíclicos

§ DAG=(V,E)q V = {vi | i = 1, …, V}

§ Los vertices respresentan tareasq E={ei,j | (i,j) {1,…,V} x {1,…,V}

§ Los arcos representan restricciones de precedencia entre tareas y/o movimiento de datos entre tareas

•Félix García Carballeira •Introducción a la simulación •69

Ejemplo

§ DAG formado por:q Tres tareas secuencias:

§ c1 procesa 1e9 flops§ c2 proceso 5e9 flops§ c3 procesa 2e9 flops

q Una única transferencia§ t1 de 5e8 bytes entre c1 y c3

•Félix García Carballeira •Introducción a la simulación •70

Especificación del ejemplo

int main(int argc, char **argv) {SD_task_t c1, c2, c3, t1;

SD_init(&argc, argv);

c1 = SD_task_create_comp_seq("c1", NULL, 1E9);c2 = SD_task_create_comp_seq("c2", NULL, 5E9);c3 = SD_task_create_comp_seq("c3", NULL, 2E9);

t1 = SD_task_create_comm_e2e("t1", NULL, 5e8);

SD_task_dependency_add ("c1-t1", NULL, c1, t1);SD_task_dependency_add ("t1-c3", NULL, t1, c3);SD_task_dependency_add ("c2-c3", NULL, c2, c3);

SD_exit();return 0;

}

•Félix García Carballeira •Introducción a la simulación •71

SMPI

§ Permite la ejecución de aplicaciones MPI en SimGridq Permite la experimentación reproducible de código MPIq Probar código MPI sobre una plataforma simulada

•Félix García Carballeira •Introducción a la simulación •72

Gestión de array dinámicos en SimGrid

§ Dynars son vectores de tamaño dinámico que pueden contener cualquier tipo de datosq Tipo de datos: xbt dynar t

•Félix García Carballeira •Introducción a la simulación •73

Algunas funciones

§ my dynar = xbt dynar new (elm size, free method)

§ xbt dynar free container (&my dynar)q Libera el array pero no el contenido

§ xbt dynar push (my dynar, &element)

§ xbt dynar pop(my dynar, &element)q Extrae el último elemento

§ void xbt_dynar_shift(my dynar, &element)q Extrae el primer elemento

§ xbt dynar foreach(my dynar, ctr, element)q Permite iterar sobre los elementos

§ xbt dynar length(my dynar)

§ xbt dynar is empty(my dynar)

•Félix García Carballeira •Introducción a la simulación •74

Uso de algunas funciones

§ Dada una petición:struct ClientRequest {

int n_task;

double t_arrival; /* momento en el que llega */double t_service; /* tiempo de servicio asignado */

int priority;

. . . };

§ Una cola de peticiones vacía se crea:q xbt_dynar_t client_requests ; // cola de peticionesq client_requests = xbt_dynar_new(sizeof(struct ClientRequest), NULL);

§ Una nueva petición se inserta:q xbt_dynar_push(client_requests, (char *)&req);

§ El primer elemento se extrae:q xbt_dynar_shift(client_requests, (char *)&req);

§ El último elemento se extrae:q xbt_dynar_pop(client_requests, (char *)&req);

•Félix García Carballeira •Introducción a la simulación •75

Uso de algunas funciones

§ Ordenar la cola por tiempo de servicioq xbt_dynar_sort(client_requests, &sort_function);

§ Donde:static int sort_function(const void *e1, const void *e2){

struct ClientRequest *c1 = *(void **) e1;struct ClientRequest *c2 = *(void **) e2;

if (c1->t_service == c2->t_service)return 0;

else if (c1->t_service < c2->t_service)return -1;

else

return 1;}

•Félix García Carballeira •Introducción a la simulación •76

Escalabilidad

§ 500 000 procesos conectados por una red de 1 Gbpsq Paquete de 10000 bytes

§ Tiempo simulado: 2h 20 min.§ Tiempo de simulación: 51 s.§ Memoria: 8 GB

•Félix García Carballeira •Introducción a la simulación •77

•0•1

•2

•3

Ejemplo

•Félix García Carballeira •Introducción a la simulación •78

•trabajos

•servidor

Simulación en Simgrid

int client(int argc, char *argv[]);

int server(int argc, char *argv[]);

#define N_TASKS 10000

double uniform(void) {

return drand48();

}

double uniform_pos(void) {

double g;

g = uniform();

while (g == 0.0)

g = uniform();

return g;

}

•Félix García Carballeira •Introducción a la simulación •79

Simulación en Simgrid

double exponential(double landa) {

/* función de distribución con media 1/landa. */

double u = uniform_pos();

double mean = 1.0 / landa;

return -mean * log(1-u);

}

•Félix García Carballeira •Introducción a la simulación •80

)1ln(1 ux --=l

Código cliente (genera las peticiones)int client(int argc, char *argv[]){

int number_of_tasks = 100000;char sprintf_buffer[64]; msg_task_t task = NULL;double t_arrival;double t, *t_aux;

for (int i = 0; i < number_of_tasks; i++) {

MSG_process_sleep(exponential((double)5.0));t = MSG_get_clock();

sprintf(sprintf_buffer, "Task_%d", i);

task = MSG_task_create(sprintf_buffer, t_arrival,0 ,NULL);

t = (double *) malloc(sizeof(struct request)); *t_aux = t;

MSG_task_set_data(task, (void *) t_aux );

xbt_mutex_acquire(mutex);Nqueue++;xbt_mutex_release(mutex);MSG_task_isend(task, “ServerHost”);

}

msg_task_t finalize = MSG_task_create("finalize", 0, 0, FINALIZE);MSG_task_send(finalize, “ServerHost”);return 0;

}

•Félix García Carballeira •Introducción a la simulación •81

Código servidor (atiende peticiones)int server(int argc, char *argv[]) {

msg_task_t task = NULL; _XBT_GNUC_UNUSED int res;int Nqueue_avg= 0;int Ntaksks= 0; double t, service_time = 0.0; double *t_aux;

while (1) {res = MSG_task_receive(&(task),MSG_host_get_name(MSG_host_self()));if (!strcmp(MSG_task_get_name(task), "finalize")) {

MSG_task_destroy(task);break;

}t_aux = (double* ) MSG_task_get_data(task);Ntaksk++;

xbt_mutex_acquire(mutex);Nqueue--;Nqueue_avg = Nqueue_avg + Nqueue;xbt_mutex_release(mutex);

MSG_process_sleep(exponential((double)6.0));t = MSG_get_clock(); // fin de la tarea

service_time = service_time + (t – *t_aux);

free(t_aux);

MSG_task_destroy(task);

task = NULL;

•Félix García Carballeira •Introducción a la simulación •82

Código servidor (cont.)

}

printf("--------------------------------------- \n");printf("Tareas ejecutadas = %d\n", Ntasks);printf("Tamanio medio de la cola = %g\n”,(double) Nqueue_avg/ Ntasks);printf("Tiempo medio de servicio %g\n”, (double) service_time / Ntasks);printf("--------------------------------------- \n");

return 0;}

•Félix García Carballeira •Introducción a la simulación •83

main()

int main(int argc, char *argv[]) {msg_error_t res = MSG_OK;srand48((int) time(NULL));

MSG_init(&argc, argv);if (argc < 3) {

printf("Usage: %s platform_file deployment_file\n", argv[0]);exit(1);

}

mutex = xbt_mutex_init();MSG_create_environment(argv[1]);MSG_function_register("client", client);MSG_function_register("server", server);MSG_launch_application(argv[2]);

res = MSG_main();

printf("Simulation time %g", MSG_get_clock());

return 0;}

•Félix García Carballeira •Introducción a la simulación •84

Platform.xml

<platform version="3"><AS id="AS0" routing="Full">

<host id="ClientHost" speed="1000000"/><host id="ServerHost" speed="1000000"/>

<link id="1" bandwidth="1000000000" latency="0.0000000"/>

<route src="ClientHost" dst="ServerHost">

<link_ctn id="1"/></route>

</AS></platform>

•Félix García Carballeira •Introducción a la simulación •85

Deployment.xml

<platform version="3">

<process host="ClientHost" function="client"/>

<process host="ServerHost" function="server"/>

</platform>

•Félix García Carballeira •Introducción a la simulación •86

Resultados del ejemplo para diferentes semillas

•Félix García Carballeira •Introducción a la simulación •87

§ En cada realización de la simulación se obtiene un valor§ ¿Cómo estimar el valor?

Tiempomedioderespuesta(horas) Nºmediodetareasencola0,8960 3,65961,0300 4,41260,8780 3,50041,1649 5,02180,9697 4,01811,0380 4,35991,0219 4,18661,0173 4,2237

Métricas de rendimiento

§ Contador, número de veces que ocurre un determinado evento

§ Duración, de un determinado intervalo§ Tamaño de algún parámetro§ Un valor derivado de las anteriores medidas

•Félix García Carballeira •Introducción a la simulación •88

Características de una buena métrica

§ Lineal:q Si la métrica se incrementa x2, entonces las prestaciones se incrementan x2

§ Fiable:q Si (métrica A > métrica B) entonces

§ El rendimiento de A > rendimiento de B§ Reproducible

q Se obtiene el mismo valor en cada experimento (determinista)§ Fácil de usar y de obtener§ Consistente

q Unidades y definición se mantienen constantes en diferentes sistemas (MIPS, MFLOPS)

§ Independienteq De fabricantes y de presión por influir en la definición de una métrica

•Félix García Carballeira •Introducción a la simulación •89

Ejemplo 1: MIPS

§ Millones de instrucciones por segundo§ ¿Es una buena métrica?

q Lineal?q Fiable?q Reproducible?q Fácil de medir?q Consistente?q Independiente?

•Félix García Carballeira •Introducción a la simulación •90

Ejemplo 1: MIPS

§ Millones de instrucciones por segundo§ ¿Es una buena métrica?

q Lineal? noq Fiable?q Reproducible?q Fácil de medir?q Consistente?q Independiente?

•Félix García Carballeira •Introducción a la simulación •91

•Doblar el número de MIPS no permite•doblar el rendimiento. Hay otros factores •que afectan:§ Sistema de memoria§ E/S

Ejemplo 1: MIPS

§ Millones de instrucciones por segundo§ ¿Es una buena métrica?

q Lineal? q Fiable? noq Reproducible?q Fácil de medir?q Consistente?q Independiente?

•Félix García Carballeira •Introducción a la simulación •92

•Un procesador con 150 MIPS no •es más rápido que uno con 100 MIPS. •El rendimiento depende:§ El juego de instrucciones§ El compilador

Ejemplo 1: MIPS

§ Millones de instrucciones por segundo§ ¿Es una buena métrica?

q Lineal? q Fiable? q Reproducible? Si q Fácil de medir? Siq Consistente?q Independiente?

•Félix García Carballeira •Introducción a la simulación •93

Ejemplo 1: MIPS

§ Millones de instrucciones por segundo§ ¿Es una buena métrica?

q Lineal? q Fiable? q Reproducible?q Fácil de medir?q Consistente? noq Independiente?

•Félix García Carballeira •Introducción a la simulación •94

•No permite comparar el rendimiento de •diferentes sistemas

Ejemplo 1: MIPS

§ Millones de instrucciones por segundo§ ¿Es una buena métrica?

q Lineal? q Fiable? q Reproducible? q Fácil de medir? q Consistente? q Independiente? Si

•Félix García Carballeira •Introducción a la simulación •95

Ejemplo 2: tiempo de ejecución

§ ¿Es una buena métrica?q Lineal? Siq Fiable? Siq Reproducible? Si (aproximadamente)

§ Puede depender de la carga del sistema (SO, sistemas de tiempo compartido, memoria virtual, …)

q Fácil de medir? Siq Consistente? Siq Independiente? Si

•Félix García Carballeira •Introducción a la simulación •96

Características de una buena métrica

§ Lineal:q Si la métrica se incrementa x2, entonces las prestaciones se incrementan x2

§ Fiable:q Si (métrica A > métrica B) entonces

§ El rendimiento de A > rendimiento de B§ Reproducible

q Se obtiene el mismo valor en cada experimento (determinista)§ Fácil de usar y de obtener§ Consistente

q Unidades y definición se mantienen constantes en diferentes sistemas (MIPS, MFLOPS)

§ Independienteq De fabricantes y de presión por influir en la definición de una métrica

•Félix García Carballeira •Introducción a la simulación •97

Métricas más habituales

§ Tiempo de respuesta:q Tiempo necesario para completar una operación

§ Throughput:q Cantidad de trabajo completado por unidad de tiempo

§ Tareas ejecutadas por segundo, frames de video procesados por segundo, …

§ Ancho de banda:q Cantidad de información transmitida por unidad de tiempo

§ Bits por segundo

•Félix García Carballeira •Introducción a la simulación •98

Métrica de interés para el ejemplo

§ Tiempo medio de ejecución de los trabajos en el servidor§ Número medio de procesos en la cola del servidor esperando

para su ejecuciónq Tamaño medio de la cola del servidor

•Félix García Carballeira •Introducción a la simulación •99

•trabajos

•servidor

Resultados del ejemplo para diferentes semillas

•Félix García Carballeira •Introducción a la simulación •100

§ En cada realización de la simulación se obtiene un valor§ ¿Cómo estimar el valor?

Tiempomedioderespuesta(horas) Nºmediodetareasencola0,8960 3,65961,0300 4,41260,8780 3,50041,1649 5,02180,9697 4,01811,0380 4,35991,0219 4,18661,0173 4,2237

Experimentos de simulación

§ Un experimento de simulación debe implicar la ejecución de la simulación varias veces con distintas semillas de números aleatoriosq En cada realización se obtiene el valor de un parámetro de

interés en distintos instantes de tiempoq Por ejemplo: Ti podría ser el tiempo medio de ejecución

obtenido en la i-ésima realización del experimento§ Cuando se utilizan variables aleatorias como entrada, las

salidas T1, T2, … Tn son también variables aleatoriasq T1, T2, … Tn son observaciones independientes

q Se puede coger como valor de salida la media de las variables de salida de la simulación

•Félix García Carballeira •Introducción a la simulación •101

T = 1n

Tii=1

n

Determinar el periodo estable

•Félix García Carballeira •Introducción a la simulación •102

Muestras obtenidas

§ Si {x1, x2, … xn} son los valores de salida que se obtienen en cada experimento (con semillas diferentes)q {x1, x2, … xn} es un conjunto de variables aleatorias,

independientes e idénticamente distribuidas de una función de distribución con media µ y desviación estándar s desconocidas

§ La media y la desviación de la función de distribución de la variable de salida se pueden estimar como:

§ Según el teorema central del límite la variable aleatoria x sigue una distribución normal con media µ y desviación estándar s/√n

•Félix García Carballeira •Introducción a la simulación •103

x = xii=1

n

∑ s2 =(xi − x )

2

i=1

n∑

n−1

Error cometido en la obtención del valor medio

§ ¿Cuál es el error que se comete al estimar el valor medio?q ¿Cuál es la probabilidad de que el error cometido en la

estimación del valor medio sea menor de un determinado valor?

q ¿Cuántas repeticiones del experimento debemos realizar para que el error cometido sea menor que un cierto valor con una determinada probabilidad?

•Félix García Carballeira •Introducción a la simulación •104

Cuando el número de medidas es grande(n ≥30)§ Si{x1, x2, …, xn} son las muestras obtenidas para calcular x§ Si todas las muestras son independientes y proceden de una

determinada distribución con media µ y desviación estándar sq La media x sigue una distribución normal con media µ y

desviación estándar σ/√n

•Félix García Carballeira •Introducción a la simulación •105

n = número de medidas

x = media = xii=1

n

s = desviación estándar =(xi − x )2

i=1

n∑

n−1

Modelo de errores

§ Se emplean intervalos de confianza para encontrar un rango de valores que, con una cierta probabilidad incluyen a valor real

•Félix García Carballeira •Introducción a la simulación •106

Pr c1≤ x ≤ c2[ ] =1−α

Intervalo de confianza

§ La distribución sigue una distribución normal con

media 0 y desviación estándar 1.§ Aplicando el teorema central del límite

•Félix García Carballeira •Introducción a la simulación •107

z = x − xs / n

c1 = x − zα /2sn

c2 = x + zα /2sn

y Pr(c1 ≤ x ≤ c2 ) =1−α

Intervalo de confianza

§ El intervalo de confianza [c1, c2] para un valor medio y un nivel de confianza de (1-α) × 100 indica que la probabilidad de que el valor real que está siendo medido esté entre c1 y c2 es de (1-α)

§ Los valores z1-α/2 están tabulados

Siendo:1-α el nivel de confianza α el nivel de significación

•Félix García Carballeira •Introducción a la simulación •108

Cuando el número de medidas es pequeño (n <30)§ La distribución sigue una distribución t de Student

q Con (n-1) grados de libertadq Valores tabulados para t

•Félix García Carballeira •Introducción a la simulación •109

z = x − xs / n

Intervalo de confianza (n < 30)

•Félix García Carballeira •Introducción a la simulación •110

c1 = x − tα /2;n−1sn

c2 = x + tα /2;n−1sn

y Pr(c1 ≤ x ≤ c2 ) =1−α

Ejemplo

•Félix García Carballeira •Introducción a la simulación •111

Tiempomedioderespuesta(horas) Nºmediodetareasencola0,8960 3,65961,0300 4,41260,8780 3,50041,1649 5,02180,9697 4,01811,0380 4,35991,0219 4,18661,0173 4,2237

Ejemplo (para el tiempo medio de respuesta)

•Félix García Carballeira •Introducción a la simulación •112

§ Para un intervalo de confianza del 90%, el valor real se encuentra dentro del intervalo de confianza con una probabilidad del 90%

§ Para un intervalo de confianza del 90 %, 1-α=0,9 q 1-α/2=0.95, α/2 = 0.05q n=8, por tanto la distribución t de student tiene 7 grados de

libertad

x =xii=1

n∑n

=1, 001975

s = desviación estándar = 0, 0901

Intervalo de confianza del 90%

•Félix García Carballeira •Introducción a la simulación •113

α/2n 0,1 0,05 0,025… … … …5 1.476 2.015 2.5716 1.440 1.943 2.4477 1.415 1.895 2.365… … … …∞ 1.282 1.645 1.960

α / 2 = 0.95tα /2;n−1 = t0.05;7 =1.895

c1 =1.001975−1.895 ⋅0.09

8= 0.9416

c2 =1.001975+1.895 ⋅0.09

8=1.0622

c1 = x − tα /2;n−1sn

c2 = x + tα /2;n−1sn

y Pr(c1 ≤ x ≤ c2 ) =1−α

Interpretación

§ Intervalo de confianza del 90%= [0.9416, 1.0622]q El 90% de las veces el valor real se encuentra entre

0.9416 y 1.0622

•Félix García Carballeira •Introducción a la simulación •114

•9.4213 •9.7295

Ejemplo (número medio de tareas en la cola)§ El número medio de tareas:

§ Intervalo de confianza del 90%= [3.854, 4.485]q El 90% de las veces el valor real se encuentra entre

real value 3.854 y 4.485

•Félix García Carballeira •Introducción a la simulación •115

x =xii=1

n∑n

= 4,17

s = desviación estándar = 0, 471

Error cometido

•Félix García Carballeira •Introducción a la simulación •116

§ Intervalo de confianza del 90%= [3.854, 4.485]q Con una probabilidad de 0.9 el error cometido será

de e = 0.076, es decir, del 7.6%

¿Cuántos experimentos realizar?

§ ¿Cuántos experimentos n se deben realizar para cumplir un determinado nivel de confianza?

•Félix García Carballeira •Introducción a la simulación •117

c1,c2[ ] = x − zα /2sn

"

#$, x + zα /2

sn%

&'

= (1− e)x, (1+ e)x[ ]

zα /2sn= xe

n = zα /2sxe

(

)*

+

,-2

Ejemplo

§ Tiempo medio obtenido: 1.001975 h§ Desviación estándar: 0.0901§ ¿Cuántas medidas se necesitarían para que con un intervalo de

confianza del 90% el error cometido al estimar el tiempo medio de ejecución sea menor del 1%?

•Félix García Carballeira •Introducción a la simulación •118

Ejemplo

§ Tiempo medio obtenido: 1.001975 h§ Desviación estándar: 0.0901§ ¿Cuántas medidas se necesitarían para que con un intervalo de

confianza del 90% el error cometido al estimar el tiempo medio de ejecución sea menor del 1%?q 1-α=0.9 q α=0.1q α/2 = 0,05, Zα/2 = 1,645q Error = ± 1%q e=0.01

•Félix García Carballeira •Introducción a la simulación •119

Ejemplo

§ Hacen falta 220 medidas para que con una probabilidad del 90% el error cometido en la estimación del valor medio sea menor del 1%

•Félix García Carballeira •Introducción a la simulación •120

n = zα /2sxe

!

"#

$

%&2

=1.645 ⋅0.09011.001975 ⋅0.01!

"#

$

%&2

= 219,1

Solución analítica

•Félix García Carballeira •Introducción a la simulación •121

§ El sistema descrito se modela como una cola M/M/1

§ Tiempo entre llegadas con distribución exponencial (proceso de Poisson) de media 1/ λ

§ Tiempo de servicio con distribución exponencial de media 1/µ

Tasa de llegada cola Tasa de servicio

Teoría de colas

§ Estudia el comportamiento de sistemas donde existe un conjunto limitado de recursos para atender peticiones

§ Requiere:q Modelar el sistemaq Modelar el comportamiento aleatorio de las peticiones y

tiempos de servicio§ Existen modelos de colas con solución analítica conocida§ Los modelos sin solución analítica conocida han de resolverse

mediante técnicas de simulación

•Félix García Carballeira •Introducción a la simulación •122

Modelo de un sistema de colas

•Félix García Carballeira •Introducción a la simulación •123

Peticiones deServicio (usuarios, tareas, etc) cola

recursos

Especificación de un sistema de colas

§ A / B / m / K / N / Zq A: distribución de la variable aleatoria tiempo entre llegadasq B: distribución de la variable aleatoria tiempo de servicio

§ M: exponencial, U: uniforme, G: general (arbitraria)q m: número de recursos del sistemaq K: capacidad del sistema (máximo número de tareas que

pueden estar en el sistema al mismo tiempo)q N: tamaño de la poblaciónq Z: disciplina de la cola

§ FCFS, SJF, LCFS, RR, con expulsión, sin expulsión,…

•Félix García Carballeira •Introducción a la simulación •124

Ejemplo

•Félix García Carballeira •Introducción a la simulación •125

Solución analítica de una cola M/M/1

§ Cola MM1

•Félix García Carballeira •Introducción a la simulación •126

lµ -=

1T§ Tiempo medio de servicio

§ Tamaño medio de la cola

§ Tiempo medio de espera en la cola

§ Número medio de tareas en el sistema

µlr

rr

=-

= conQ1

2

W =ρ

µ ⋅ (1− ρ)con ρ =

λµ

N =ρ1− ρ

con ρ =λµ

Ejemplo

§ Solución analítica:q Tiempo medio de servicio =

q Tamaño medio de la cola =§

§ Solución obtenida mediante simulación:§ Tiempo medio de servicio = 1.001975 h§ Tamaño medio de la cola = 4,17

•Félix García Carballeira •Introducción a la simulación •127

T = 16− 5

=1h

Q =(5 / 6)2

1− 5 / 6= 4,16

Comparación entre dos alternativas

§ ¿Hay medidas significativas entre los valores obtenidos de dos sistemas diferentes?

q n1 medidas del sistema 1q n2 medidas del sistema 2

•Félix García Carballeira •Introducción a la simulación •128

Ejemplo

•Félix García Carballeira •Introducción a la simulación •129

•trabajos•dispatcher

•Cluster (100 nodos)

Ejemplo

§ Los trabajos a ejecutar tienenun tiempo de ejecución medio de 1 hora

§ El tiempo de ejecución sigue una distribución exponencialde media µ = 1 hora

•Félix García Carballeira •Introducción a la simulación •130

•μ = 1 hora

Ejemplo

§ Asumimos que cada nodo tiene una cola de procesos para ejecutar. Los procesos se ejecutan con política FCFS

§ Estamos interesados en evaluar dos técnicas distintas de distribución de los trabajos:q Shortest queue first: cuando se recibe un trabajo se envía al

nodo con la cola de procesos más pequeñaq The power of two random choice: cuando se recibe un

nuevo trabajo se eligen dos nodos de forma aleatoria y se envía al que tiene la cola de procesos más pequeña

•Félix García Carballeira •Introducción a la simulación •131

Ejemplo

§ Queremos saber el comportamiento de los dos algoritmos anteriores para una determinada tasa de llegada de trabajos

§ Tasa de llegada de trabajos: sigue una distribución exponencial de tasa λ = 90 trabajos por hora

§ Utilización de los servidores

•Félix García Carballeira •Introducción a la simulación •132

ρ =λn ⋅µ

= 0.9 <1

Ejemplo

§ Shortest queue firstq Tiempo medio: 1,067 hq Desviación: 0,267

§ The power of two random choiceq Tiempo medio: 2,6754 hq Desviación: 0,066

§ ¿Hay diferencias significativas?

•Félix García Carballeira •Introducción a la simulación •133

No siempre es obvio

•Félix García Carballeira •Introducción a la simulación •134

n1 = 8 medidasx1 =1046, 25 ss1 = 49, 25

n2 = 5 medidasx2 = 996, 6 ss2 = 78, 41

Intervalo de confianza para la diferencia de medias§ Se calculas las medias de las dos distribuciones§ Se calcula la diferencia de las medias§ Se calcula la desviación estándar de las diferencia de

las medias§ Se determina el intervalo de confianza para la

diferencia§ Si el intervalo incluye al 0: no hay diferencias

significativas entre los dos sistemas§ Si el intervalo no incluye al 0: sí hay diferencias

significativas entre los dos sistemas•Félix García Carballeira •Introducción a la simulación •135

Intervalo de confianza para la diferencia de medias

•Félix García Carballeira •Introducción a la simulación •136

diferencia de las medias:x = x1 − x2

desviación estándar la las diferencias

sx =s1

2

n1

+s2

2

n2

Si n1 > 30 y n2 > 30

•Félix García Carballeira •Introducción a la simulación •137

c1 = x − z1−α /2sxc2 = x + z1−α /2sx

§ Se obtiene el intervalo de confianza para la diferencia de las medias

§ Si el intervalo incluye al 0: no hay diferencias significativas entre los dos sistemas

§ Si el intervalo no incluye al 0: sí hay diferencias significativas entre los dos sistemas

Si n1 < 30 y n2 < 30

•Félix García Carballeira •Introducción a la simulación •138

ndf =

s12

n1+s22

n2

!

"#

$

%&

2

s12 n1( )

2

n1 −1+s22 n2( )

2

n2 −1

§ Se utiliza una t de Student con ndf grados de libertad

Para el ejemplo

•Félix García Carballeira •Introducción a la simulación •139

n1 = 8 medidasx1 =1046, 25 ss1 = 49, 25

n2 = 5 medidasx2 = 996, 6 ss2 = 78, 41

Ejemplo

•Félix García Carballeira •Introducción a la simulación •140

x = x1 − x2 =1046,25− 996 = 49,65

sx =49,252

8+78, 412

5= 39,15

ndf =

49,252

8+78, 412

5

"

#

$$$$

%

&

''''

2

49, 252 8( )2

8−1+78, 412 5( )

2

5−1

= 6,01

Ejemplo

§ Para un intervalo de confianza del 90%

§ Como el intervalo incluye al 0, estadísticamente, no hay diferencias significativas entre los dos sistemas

•Félix García Carballeira •Introducción a la simulación •141

c1 = x − tα /2;ndf sxc2 = x + tα /2;ndf sx

tα /2;ndf = t0,05;6 =1.943

c1 = 49,65−1.943(39,15) = −26, 42c2 = 49,65+1.943(39,15) =125, 7

Práctica

§ Se parte de un modelo M/M1

•Félix García Carballeira •Introducción a la simulación •142

Modelar

•Félix García Carballeira •Introducción a la simulación •143

•10 servidores

Estudiar

§ Política de reparto:q Round-robinq Aleatoriaq Shortest queue firstq Power of two choices

§ Parámetros a estudiarq Tiempo medio de servicioq Energía consumida en cada servidor

•Félix García Carballeira •Introducción a la simulación •144