REASIGNACIÓN DE TAREAS EN UN SISTEMA DISTRIBUIDO UTILIZANDO ALGORITMO GENETJCO

Mario Farias1 y Guillermo Morales

1

Laboratorio del Centro de Investigación, Universidad La Salle

Beamin Franklin 47 , Col Hipódromo-Condesa México DF 06170 ematl mfarias@ci .ulsa.mx Sección de Computación, Departamento de Ingeniería Eléctrica, CINVESTAV-IPN

RESUMEN

Una de las características que debe tener un sistema distribuido es la capacidad de recuperación ante una eventualidad. Una falla de un procesador es una eventualídad de la cual el sistema debe de recuperarse lo más rápido posible y de manera satisfactoria, reasignanando las tareas de este procesador en los procesadores restantes . En la actualidad los métodos clásicos, como recocido simulado, son lentos para este tipo de situaciones . En este trabajo se muestra la utilización de la técnica de algoritmos genélicos para resolver el problema de reasignación de tareas, de tal forma que se obtiene como resultado una asignación que mantenga una carga de trabajo equilibrada entre los procesadores involucrados, así como una respuesta en un tiempo mucho menor que los métodos clásicos.

ABSTRACT

A characteristic that a distributed system should have is the ability of recovery afler failure. A failure of one processor requires a fast and reliable recovery to reallocate the tasks enqueued into the failing processor among the remaining processors. The classic methods, as simulated annealing, are very slow to salve this problems. In this paper we introduce a solution for the task allocation problem by using genetic algorithms. We get as a result the task reallocation where the load is balanced among the processors with better time response that with the classic methods.

INTRODUCCIÓN

Uno de los primeros problemas encontrados en la operación de un sistema distribuido es la asignación de las tareas en los procesadores involucrados (1). El encontrar la mejor asignación de las tareas en los procesadores de un sistema distribuido puede ser formulado como un problema de optimización.

Los problemas de asignación se resuelven,por lo general,por un procedimiento de costo eficiente que encuentre la asignación óptima para instancias específicas del problema. Como una regla, los problemas de asignación tienden a ser computacionalmente intensos, es decir, muy tardados cuando se requiere de una respuesta rápida

En este trabajo , utilizamos la técnica de algoritmos genéticos para la reasignación de las tareas inmediatamente después de que ocurra una falla en algún procesador.

Rev. Centro lnv IMexj Vof.3 Núm . 11 (1998l

También se debe de tomar en cuenta que el desequilibrio de las cargas de trabajo en los procesadores afecta directamente el rendimiento del sistema (2).

DESARROLLO

El sistema consiste de m procesadores idénticos que ejecutan n tareas. Cada tarea posee rcopias, o réplicas,cada una ejecutada por un procesador distinto. Cada procesador puede tener asignadas varias tareas, las cuales las atiende en diferentes segmentos de tiempo Llamemos frecuencia de una tarea en un procesador al número de veces que el procesador pasa a atender esa tarea . Llamemos densidad de la tarea en el procesador al máximo número de instrucciones propias de esa tarea que ejecuta el procesador en los segmentos de tiempo que le asigna a esa tarea. Para cada tarea , sus frecuencias y densidades en los procesadores determinan un «peso especifico de esa tarea » que en este contexto se llama

3 41

utilización de la tarea. Denotemos por u1 a la utilización de la j-ésima tarea.

Una asignación particular queda descrita par

una matriz V = ( ) s-. ni de orden m x n .con

1

entradas O ó 1. De hecho, para cada i y cadaj,se tiene V,¡= 1 si la j-ésima tarea está asignada al i­ ésimo procesador, y V1rO en otro caso. En estas condiciones la ecuación (Ec. 1) representa la carga de trabajo del -ésimo procesador bajo la asignación V:

U j es la utilización de la tarea j, y

a.b son ponderaciones a los sumandos de la función E" en la (Ec. 4).

.Puede verse que el primer términode la función E* en la (Ec. 4) está motivado por el número de réplicas para cada tarea. Este término alcanza un mínimo si cada tarea es ejecutada exactamente por r procesadores . El segundo término, por otro lado, representa a la función de costo. que como ya se mencionó antes, es una medida del desequilibrio de las cargas de los procesadores.

(Ec. 1)

La técnica de recocido simulado (simulated

anneafing) es un procedimiento de optimización que

De acuerdo co (3), minimizar la suma de

todos los valores p, minimiza también la varianza estadística de los p/s, el cua! viene a ser una medida del desequilibrio en las cargas de los procesadores. Es bien sabido que un desequilibrio de cargas afecta directamente el rendimiento del sistema .

Tomando en cuenta lo anterior y la (Ec. 1). el problema puede definirse como la minimización de:

(Ec. 2)

restringido a:

produce aproximaciones a valores óptimos, dada una función objetivo. Veamos la manera en que procede:

Procedimiento RS: Dado un punto inicial en el espacio de búsqueda con su respectivo valor para la función objetivo, a éste se le considera como punto actual. En cada it eración de este procedimiento, se busca un vecino en forma aleatoria, sí dicho vecino genera un valor en la función objetivo menor al del punto inicial,éste nuevo vecino toma el lugar del punto inicial,en caso contrario se obtiene un valor de cambio basado en el exponente de la va riación y se

genera en forma aleatoria una probabilidad. sí el cambio es mayor a la probabilidad, el punto vecino se convierte en el punto inicial. Esto se

repite en tanto no se arribe a condiciones

1-I

V;¡ = r

't:/ l ::;; j s; n

(Ec. 3)

terminales.

El problema de asignación de tareas puede modelarse por una ecuación que es la suma de las ecuaciones (Ec. 2) y (Ec. 3} quedando como:

donde los parámetros involucrados tienen los significados descritos a continuación:

n es el número de tareas existentes,

m es el número de procesadores disponibles,

r es el número de réplicas de cada tarea,

VÍJ es el valor de asignación de la j-ésíma tarea al i-ésimo procesador, es decir,

La técnica de algoritmos genéticos (genetic afgorilhms) es un procedimiento, que en este caso,

se utiliza para optimización que produce aproximaciones a valores óptimos, con una

probabilidad alta de que las aproximaciones sean, en efecto, los óptimos globales. Dada una función, llamada objetivo, busca el valor mínimo de esa función (4). A grandes rasgos la forma en que procede es:

Procedimiento AG: Dado un conjunto de puntos en el espacio de búsqueda, llamado semínaf, se evalúa la función objetivo en ellos y se escoge los puntos correspondientes a los

mejores valores. Estos puntos forman una muestra de mejores individuos a

«reproducirse», es decir forman una clase de

padres. En un proceso de entre-cruzamiento

342

1 O en otro ca50

para generar hijos, se obtiene a estos últimos

Rev Centro lnv. (Méx) Vol 1Niim 11 !1998)

,}...\,

de los padres. A los hijos se les muta con probabilidades determinadas y se actualiza el conjunto seminal considerando padres e hijos. Se repite este ciclo «selección entrecruzamiento - mutación» hasta obtener

de orden m x n con entradas ceros o unos. Sea

A EJ/

=>'if k.,I :

ya sea el valor mínimo de la función o bien

. rakl

si (k ,t ) (i,J )

hasta un número fijo de generaciones (5).

En la Figura 1 se muestra la forma en que se programó el algoritmo.

a' k 1 l

= l-

ª u

si (k ,l ) = ( i,j )

(Ec. 5)

Como se ve, este procedimiento tiene varias particularidades. Criterios específicos para realizar las operaciones de selección, de entrecruzamiento y de mutación, asi como para detener el procedimiento, dan algoritmos genéticos con comportamien tos diversos. En un problema particular. la fijación de esos criterios es un factor importantísimo para resolver eficientemente el problema con estos algoritmos.

Posteriormente se realiza una búsqueda por vecinos. Esto es debido a que los Algoritmos Genéticos y el Recocido Simulado son algoritmos de aproximación y muchas veces no alcanzan el valor óptimoglobal. una forma de alcanzar el valor óptimo es realizando una búsqueda por vecinos.

Para ello considérese la matriz V = ( v:J:.' .:

El algoritmo procede como sigue:

Procedimiento BV: Dado un punto inicial en el espacio de búsqueda con su respectivo valor para la función objetivo, a éste se le considera como punto actual. En cada iteración de este procedimiento, se busca entre los posibles vecinos del punto actual a un vecino cuyo valor en la función objetivo sea menor al del actual. si se localiza a tal vecino a éste se le considera como el punto actual con fines de una nueva iteración. Esto se repite en tanto no se llegue a condiciones terminales.

También en este caso. las particularidades que determinan a un algoritmo específico enesta clase están dadas por la noción de vecind ad de un punto, por la selección de un buen vecino y por las condiciones de terminación .

Figura 1. Esquema del Algoritmo Genético.

Rev Centro lm (Mex) Vol 3 Ni.1m 11 ¡1998; 343

J ,_

Entrada: func

Ainí

: Función objetivo

: Matriz inicial

Salida: Algoritmo:

{

V

Anueva = Aini;

: Matriz de asignación

Vini = func(Aini);

Anueva = MayorVariacion(Aini); Vnueva = func(Anueva) ;

while (Vnueva < Vini) {

Vini = Vnueva ;

Anueva = MayorVariacion(Aíni);

Vnueva = func(Anueva);

}

}

Figura 2. Esquema de la búsqueda por vecinos

344

En nuestro problema de asignación el espacio de búsqueda está conformado por las matrices de orden m x n , con entradas O o 1. Para el procedimiento AG hacemos la selección evaluando la función objetivo en las malnces seminales, y para un numero K prefijado de padres, elegimos aquellas K matrices que den los valores mínimos En nuestro caso K=4. En el entrecruzamiento se parte cada matriz padre en n bloques de m entradas contíguas porrenglones. Obtenemos pues K ·n bloques. A la nueva generación de matrices la obtenemos recombinando estos bloques en posiciones correspondientes, es decir. si un bloque aparece en la posición k , en una matriz padre, ha de aparecer en esa misma posición cuando aparezca

en un h1¡0. Esto genera K " matrices hijas. Finalmente, parala mutación, se hace un cambio encadaentrada de las matrices hijas por suvalor complementario, pero sólo en cierto porcentaje de tas entradas totales de la población.

Ahora bien. en el procedimiento BV. teniendo una matriz actual,para obtener una matriz vecina se copia la matriz actualy sólo en una entrada se

le asigna el valor complementano. Este se realiza para cada entrada de la matriz. y aquella que dé la mayor d1ferenc1a en el valor de la función objetwo es la que se selecciona como la matríz vecina.

El e spacio de búsqueda posee 2"'x" elementos , que para numeras m= 7 y n= 14, utilizados en nuestras prácticas, es sumamente grande. De manera típica, uestro PS cedimiento AG uhlrza un con¡unto seminalde 2 matrices y calcula 40 generaciones. En un sistema SPARC

de 50 MHz. el tiempo de cálculo rondaba los 75 minutos, tomando en cuenta que la probabilidad de mutación varía desde 0.05 hasta 0 .95 en incrementos de 0.05, y en cada probabilidad se calculan 40 generaciones.

Una característica que nos es importante en nuestra plataforma de experimentación es la

«estabilidad del problema». Así, nos interesa calcular asignaciones óptimas habiendo perturbado los parámetros del problema, particularmente el vector de «utilizaciones», partiendo de la solución óptima del problema sin perturbaciones. De manera que no nos alejásemos mucho de los óptimos calculados. procedimos por el algoritmo BV para calcular los óptimos correspondientes a los problemas perturbados.

Un factor importante que se observó es que la probabilidad de mutación que dio mejores resultados fue de 0.35.

RESULTADOS

A continuación se presentan los resultados de algunas simulaciones realizadas, tanto con AG como con RS. Para cada simulación se mantienen algunos parámetros fijos. con el fin de poder comparar los resultados y los tiempos de ejecución.

Los valores que se mantienen para todas las simulaciones son:

No. de réplicas (r) = 3 No. de tareas (n) = 14

R ev. C en f m f nv (Méx) Vo l .:1 Ntím 11 (1998)

No. de procesadores (m) = 7

Ponderaciones de: a= 1200; b=200

Probabilidad de mutación (probmut}=0.35

Máximo de generaciones (maxgen)=40 No. de padres (np)=4

No. de entrecruzamientos (nc)=6 Pnmera Simulación

Vector de utilización:

u = { 0 . 8 4 9 3 9 6 , 0 . 8 2 2 2 3 2 ,0 . 6 3 2 7 6 9 ,

0 . 8 2 2 2 7 8 . 0 . 3 9 1 8 9 9 , 0 .6 3 0 8 3 6 ,

0 . 9 0 2 2 7 9 , 0 . 3 4 8 1 1 7 , 0 . 5 4 0 7 0 6 ,

0 . 3 6 5 6 8 4 . 0 .9 5 8 8 7 6 , 0 .6 9 2 8 8 8 ,

0.319022,0.0528932}

Matriz de asignación por RS:

o J o J o o o o 1 o o 1 1 1

1 o l 1 ) o o o 1 o o o l o

J o o o o 1 o 1 o 1 l o l o

1 o 1 1 1 o o o o o o o o

1 o o o o o o 1 1 o 1 o 1

1 o o o o o 1 1 1 o o 1 o 1

V = 0 0 1 1 0 0 1 0 1 0 0 0 1 1

o o o 1 1 1 o 1 o 1 o 1 1 o

o o 1 o o 1 1 1 o o 1 o o o

o 1 1 o 1 o o o o 1 1 o 1 o

Evaluando la función objetivo (Ec. 4) con la matr iz obtenida tenemos :

E "'- = 17713.651138

Segunda Simulación Vector de utilización:

u 2 = { o .3 18 3 18 .o . 8 17 7 7 3 ,o .9 04 4 8 6 ,

0 .7 6 3 6 8 8 , 0 .4 3 9 4 1 1 , 0 .6 7 3 2 5 4 ,

0 . 13 9 0 5 0 , 0 .6 5 3 115 , 0 .0 2 9 4 7 8 5 ,

0 .6 5 3 4 8 8 , 0 . 1 4 16 8 3 .0 . 3 7 8 8 2 3 ,

-} \.

V = u o o o o o J 1 J l o 1 o o o l 1 o l l o o o o 1 o o 1 o o 1 J o o l o o o o 1 o o

l l O O l l O l O I O O O l

Evaluando la función objetivo (Ec. 4) con la matriz obtenida tenemos :

I'= 17768.5 14870

Matriz de asignación por AG

o 1 o 1 1 1 1 o o 1 1 o o

o 1 o o o o o o 1 o 1 o o

1 o o o 1 o 1 1 1 o ·1 1 1

V = o 1 1 1 o 1 1 o o o 1 o

o o o 1 1 1 o 1 1 1 o 1 1 o

o o 1 o 1 1 1 1 o o 1 1 o o

o 1 1 o 1 1 o 1 1 1 1 1 o

0.489752,0.443381}

Los demás parámetros son iguales alejemplo anterior.

Matriz de asginación por RS:

1 o l o o o l o o l o 1 l 1 o 1 o J l J o o o o u o o J l I O J O O L O l l O I O O

V = 0 1 0 0 1 1 0 0 1 0 1 0 1 0

o o 1 o o o o l J l o o 1 o

O O L O O I J L O O l 1 0 0

J o o 1 J o o 1 o o J o o J

Evaluando la función objetivo (Ec. 4) con la matriz obtenida tenemos:

E * = 12133.658048

Se obtiene una matriz de asignación por AG

Posteriormente a dicha matriz se le aplicó el

algoritmo de búsqueda por vecinos, dando como resultado la matriz:

Rev Centro lnv (Mex) Vo/.J Num. / 1 ¡1998}

o 1 o o o o 1 o 1 1 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 1 1 0

1 1 1 o o o 1 o o 1 o o 1

V = 1 1 0 1 1 1 0 0 0 0 0 1 0

o 1 1 1 1 1 1 1 o 1 1 1 1 1

1 o o o o o o 1 o 1 1 o o 1

1 1 o 1 1 1 o o o o i 1 o o

345

•