implementación secuencial y paralela de técnicas ... isabel dorta.pdf · dpto. estadística, i....

Dpt

o. E

stad

ístic

a, I.

O. y

Com

puta

ción

. U

. de

La L

agun

a

Implementación Secuencial y Paralela de Técnicas Algorítmicas: Aplicación a

Problemas de Optimización Combinatoria

Seminario Invitado: Dpto. de Métodos Cuantitativos en Economía y Gestión

Marzo 2007

Isabel Dorta, Coromoto León, Angélica Rojas

http://nereida.deioc.ull.es/

Seminario Invitado: Dpto Métodos Cuantitativos en Economía y Gestión

Implementación Secuencial y Paralela de Técnicas Algorítmicas: Aplicación a Problemas de Optimización Combinatoria

Mª Isabel Dorta González

Marzo, 2007

apartadosapartadosÍndice

1. Introducción

2. Interfaz de usuario de la librería MaLLBa

3. Implementación de Patrones de Resolución o Esqueletos Secuenciales

4. Implementación de Patrones de Resolución o Esqueletos Paralelos

5. Experimentos Computacionales

6. Conclusiones

subapartadossubapartados




Marzo, 2007

Introducción

Interfaz de Usuario de MaLLBa

Patrones Secuenciales

Patrones Paralelos

Experimentos Computacionales

Conclusiones

Apartado I: Introducción

1. Problema de optimización Combinatoria

2. Técnicas Algorítmicas

• Ramificación y Acotación

• Divide y Vencerás

3. Esqueletos Algorítmicos

4. Programación Paralela

• Herramienta MPI

• Herramienta OpenMP




Marzo, 2007

Optimización Combinatoria


Técnicas Algorítmicas

Esqueletos Algorítmicos

Definiciones sobre Programación

Paralela

Un problema de optimización combinatoria es una t-upla

∏=(I, S, f, g) donde:

• I es el conjunto de instancias de ∏. Si x ∈ I se dice que x es una instancia (o una entrada) de ∏

• Dada una instancia x ∈ I, S(x) denota el conjunto de soluciones factibles de x

• Dada una instancia x ∈ I y una solución factible σ ∈ S(x), f(x, σ) representa el costo de σ con respecto a ∏ y x. La función f se denomina función objetivo

• g ∈{max, min}. El objetivo de ∏ es encontrar una solución factible que optimice f en función de g: dado un valor x ∈ I, se trata de determinar una solución óptima σ´∈ S(x) tal que f(x, σ´) = g {f(x, σ) / σ ∈S(x)}.

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Caso de Estudio: El Problema de la Mochila 0/1

Definición:

“Se dispone de una mochila de capacidad C y de un conjunto de N objetos, siendo bk y pk el beneficio y el peso asociado al objeto k. Sin exceder la capacidad de la mochila, los objetos deben ser insertados en ésta proporcionando el máximo beneficio”

{ }{ }N,...,k

,x

Cxp:asujeto

xbmax

k

N

kkk

N

kkk

110

1

1

∈∀∈

≤∑

∑

=

=

Formulación como problema de Optimización





Paralela




Marzo, 2007


La capacidad C es 102 Los elementos N son 8

b = 15

p = 2

b = 100

p = 20

b = 90

p = 20b = 1

p = 10

b = 60

p = 30

b = 15

p = 30

b = 10

p = 60

b = 40

p = 40

C = 102

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007


Son técnicas de diseño de algoritmos, que se adaptan al problema particular que se desea resolver.

• Fuerza bruta

• Divide y Vencerás (Divide and Conquer)

• Búsqueda con retroceso (Backtracking)

• Ramificación y Acotación (Branch and Bound)

• Programación Dinámica

• …

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Ramificación y Acotación

• Árbol de búsqueda• Nodos:

• Vivo : no se han generado aún todos sus hijos

• Muerto: no se van a generar más hijos

• Actual: se están generando sus hijos

• Lista de Nodos vivos

☺

☺ ☺

☺

☺ ☺

☺

☺

☺

☺

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Ramificación y Acotación

• Paso 1: Si la lista de nodos vivos está vacía, terminar.

• Paso 2: Extraer un nodo vivo

• Paso 3: Calcular su coste esperado.

• Paso 4: Si el coste esperado es peor que el de la mejor solución hasta el momento, considerar ese nodo como nodo muerto y volver al paso 1.

• Paso 5: Si el coste esperado es mejor que el de la mejor solución actual pero no es solución factible, generar todos sus hijos y convertirlo en nodo muerto. Ir al paso 1.

• Paso 6: Si el coste esperado es mejor que el de la mejor solución actual y es solución factible, ésta pasa a ser la mejor solución. Ir al paso 1.

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


Espacio de búsqueda, organizado como un árbol

No Si

No Si No Si

SiNo

. . .

Cres = 102obj = 0pf = 0

Cres = 102obj = 1pf = 0

Cres = 82obj = 1

pf = 100

Cres = 90obj = 2pf = 30

Cres = 102obj = 2pf = 0

Cres = 82obj = 2

pf = 100

Cres = 52obj = 2

pf = 115

No Si

. . .. . . . . .





Paralela




Marzo, 2007

Problema de Ordenación

N

N

3

3

2

2

1

1

pb

...pb

pb

pb

≥≥≥≥

Beneficios bk= {15,100, 90, 60, 40, 15, 10, 1}Pesos pk= { 2, 20, 20, 30, 40, 30, 60, 10}

1 2 3 4 5 6 7 8

b = 15

p = 30

p = 2

b = 100

p = 20

b = 90

p = 20b = 1

p = 10

b = 60

p = 30

b = 15b = 10

b = 40

p = 60

p = 40

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Árbol de Búsqueda: Problema de la Mochila

No Si

No Si No Si

SiSi

No

Si

No

No

No

. . .Si

. . . No

Cres = 102obj = 0pf = 0

Cres = 102obj = 1pf = 0

Cres = 100obj = 1pf = 15

Cres = 82obj = 2

pf = 100

Cres = 102obj = 2pf = 0

Cres = 100obj = 2pf = 15

Cres = 80obj = 2

pf = 115

Cres = 60obj = 3

pf = 205

Cres = 30obj = 4

pf = 265

Cres = 30obj = 5

pf = 265

Cres = 0obj = 6

pf = 280

Cres = 0obj = 7

pf = 280

Cres = 80obj = 3

pf = 115

Cres = 30obj = 6

pf = 265

No Si

. . .

. . .

No

. . .

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Divide y Vencerás

• Descomponer el problema a resolver en un cierto número de subproblemas más pequeños que el original, pero con la misma estructura

• Resolver independientemente cada subproblema

• Combinar los resultados obtenidos para obtener la solución al problema original





ParalelaAplicar esta técnica recursivamente




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Divide y Vencerás

• Paso 1: Si x es suficientemente simple resolverlo, devolver la solución e ir al paso 6. En caso contrario ir al paso 2.

• Paso 2: descomponer x en casos más pequeños x1,x2,…,xk

• Paso 3: para i = 1, …, k aplicar el mismo procedimiento hasta obtener yi = Divide y Vencerás (xi)

• Paso 4: recombinar los yi, para obtener una solución yde x

• Paso 5: devolver y

• Paso 6: finalizar





Paralela




Marzo, 2007

1 0,1 5 2 7,5 4,5 0,1 0,5

1 0,1 5 2 7,5 4,5 0,1 0,5

1 0,1 5 2 7,5 4,5 0,1 0,5

Fase de división

Problema de Ordenación

N

N

pb

...pb

pb

>>>2

2

1

1

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

1 0,1 5 2 7,5 4,5 0,5 0,1

5 2 1 0,1 7,5 4,5 0,5 0,1

Fase de combinación

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela

7,5 5 4,5 2 1 0,5 0,1 0,1




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esqueletos

La definición que se da de esqueleto en el diccionario de la Lengua Española de la Real Academia es la que sigue:

“Anat. Conjunto de piezas duras y resistentes, por lo regular trabadas y articuladas entre sí, que da consistencia al cuerpo de los animales, sosteniendo o protegiendo sus partes blandas. Armazón que sostiene algo. Col., Cos. Rica, Guat., Méx., y Nic., Modelo o patrón



EsqueletosAlgorítmicos


Paralela impreso en el que se dejan blancos que se rellenan a mano.”




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esqueleto Algorítmico

Esqueleto algorítmico: conjunto de procedimientos que constituyen el armazón con el que desarrollar programas para resolver un problema dado utilizando una técnica particular.

Este software tiene algunos blancos que se han de rellenar para adaptarlo a la resolución de un problema concreto.



EsqueletosAlgorítmicos


Paralela




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Definiciones sobre Programación Paralela

Implementación Paralela

Modelo ImplementaciónSecuencialAlgoritmo

Herramientas:esqueletos

MPI,

Java Sockets,

OpenMP,





Paralela




Marzo, 2007


Multicomputador o

Modelo Multiprocesador con Paso de Mensaje

Procesador

Memoria

local

Red de interconección

Computadores

Mensajes

Herram

ienta

MPI

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela


Modelo Multiprocesador de Memoria Compartida

Red de interconección

Procesadores

Memoria compartida

Herram

ienta

OpenMP




Marzo, 2007


• Contenido

• Sobre

Mensaje

• Qué procesador envía el mensaje• Dónde están los datos en el procesador emisor• Qué clase de datos se están enviando y cuántos.• Qué procesador(es) tienen que recibir el mensaje.• Dónde se deben dejar los datos en el procesador receptor.• Cuántos datos debe estar el procesador receptor preparado para recibir

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Paralela




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Definiciones sobre Programación paralela

Tiempo de ejecución:

• programa secuencial t(n)

• programa paralelo t(n,p)= ta(n,p) + tc(n,p)

- ta(n,p) : suma de los tiempos de las distintas partes de computación

- tc(n,p) : suma de los tiempos de las distintas partes de comunicación

- Desbalanceo de la carga

Aceleración (Speed-up)

S(n,p) = t(n) / t(n,p)





Paralela




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Apartado II: Interfaz de Usuario

1. Interfaz de Usuario Genérica de MaLLBa

2. Interfaz de Usuario para Ramificación y Acotación

1. Clases Requeridas

2. Ejemplo: El Problema de la Mochila 0/1

3. Interfaz de Usuario para Divide y Vencerás

1. Clases requeridas

2. Ejemplo: Problema de Ordenación

4. Clases Proporcionadas




Marzo, 2007



Interfaz Ramificación y Acotación

Interfaz Divide y Vencerás

ClasesProporcionadas

Programador de Esqueletos

Programador de Soluciones

Usuario de Esqueletos

Combinador de Esqueletos

Las entidades de un esqueletoalgorítmico MaLLBa son:

• Programador de Esqueletos

• Programador de Soluciones

• Usuario de Esqueletos

• Combinador de Esqueletos

MaLLBa ofrece un conjunto de técnicas de resolución pararesolver problemas de Optimización Combinatoria. Cada técnica se encapsula en un “esqueleto”.

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007


Requeridas

Solution

Proporcionadas

Setup

Solver

Técnica.req.cc

Técnica.pro.cc

Técnica.hh

Solution

Problem

Setup

Solver

classes

Specific

Specific Classes

Setup

Solver

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones








Marzo, 2007

Interfaz de Usuario de MaLLBa::BnB: Esquema UML

Solution Problem Setup SubProblem

+ lower_bound()+ upper_bound()+ branch()

«interface»Solver

Solver_Lan Solver_SMSolver_Seq

Solver_Centralized Solver_Distributed

Requeridas

Proporcionadas

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones








Marzo, 2007

Clases Requeridas Esqueleto B&B

• Problem

• Solution

• SubProblem• initSubProblem• branch• lower_bound• upper_bound

Solution

Problem

SubProblem

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Ejemplo: EL Problema de la Mochila 0/1

requires class Problem {public:Number C, // Capacidad

N; // Número de objetosvector<Number> p, // beneficios

w; // pesosProblem ();~Problem ();inline Direction direction() const {return Maximize;};. . . friend opacket& operator<< (opacket& os, const Problem& pbm);friend ipacket& operator>> (ipacket& is, Problem& pbm);

};





requires class Solution {public:vector<bool> s;

Solution ();~Solution ();. . .friend opacket& operator<< (opacket& os, const Solution& sol);friend ipacket& operator>> (ipacket& is, Solution& sol);

}




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


requires class SubProblem {public:Number CRest, // capacidad actual

obj, // objeto siguienteprofit; // beneficio actual

Solution sol; // Solución actualSubProblem (); // constructor~SubProblem (); // destructor

...

friend opacket& operator<< (opacket& os, const SubProblem& sp);friend ipacket& operator>> (ipacket& is, SubProblem& sp);

void initSubProblem (const Problem& pbm);void branch (const Problem& pbm,

branchQueue<SubProblem>& subpbms);Bound upper_bound (const Problem& pbm, Solution& ls);Bound lower_bound (const Problem& pbm, Solution& us);

};








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


void SubProblem::initSubproblem (const Problem& pbm){

Crest = pbm.C;obj = 0;profit = 0;

}





void SubProblem::branch (const Problem& pbm,container<SubProblem>& subpbms)

{SubProblem spNO = SubProblem(CRest,obj+1,profit);subpbms.insert(spNO);Number newC = CRest - pbm.w[obj];if (newC >= 0) {SubProblem spYES = SubProblem (newC, obj+1, profit +

pbm.p[obj]);subpbms.insert(spYES);

}}




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


Bound Subproblem::upper_bound (const Problem& pbm, Solution& sl){

Bound upper, weigth, pft;Number i;

for (i = obj, weigth = 0, pft = profit; weigth <= CRest; i++){weigth += pbm.w[i];pft += pbm.p[i];

}i--;weigth -= pbm.w[i];pft -= pbm.p[i];

upper = pft + (Number)( (pbm.p[i] * (CRest - weigth)) / pbm.w[i] );return(upper);

}








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


Bound Subproblem::lower_bound (const Problem& pbm, Solution& us){Bound lower, weigth, pft;Number i, tmp;

us = sol;

for(i = obj, weigth = 0, pft = profit; weigth <= CRest; i++){weigth += pbm.w[i];pft += pbm.p[i];us.s.push_back(true);

}

i--;weigth -= pbm.w[i];pft -= pbm.p[i];us.s.pop_back();tmp = pbm.N - us.s.size();

for (Number j = 0; j < tmp; j++)us.s.push_back(false);

lower = pft;return(lower);

}








Marzo, 2007

Clases Requeridas Esqueleto D&C

• Problem• SubProblem

• initSubProblem• easy• solve• divide

• Solution• combine

• Auxiliar

Solution

Problem

AuxiliarSubProblem

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Ejemplo: Problema de Ordenación

void SubProblem::initSubProblem (const Problem& pbm) {for (unsigned i = 0; i < pbm.l.size(); i++)

l.push_back(pbm.l[i]);}

bool SubProblem::easy () {return (l.size() <= 1);

}

void SubProblem::solve (Solution& sol) {sol.l = l;

}








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


void SubProblem::divide (const Problem& pbm,vector<SubProblem>& subpbms,Auxiliar& aux){

SubProblem sp1, sp2;unsigned i, middle = l.size() / 2;

for (i = 0; i < middle; i++)sp1.l.push_back(l[i]);

for (i = middle; i < l.size(); i++)sp2.l.push_back(l[i]);

subpbms.push_back(sp1);subpbms.push_back(sp2);

}








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


void Solution::combine (const Problem& pbm, const Auxiliar& aux,const vector<Solution>& subsols)

{vector<int>::const_iterator i = subsols[0].l.begin();vector<int>::const_iterator j = subsols[1].l.begin();while ((i!=subsols[0].l.end()) &&

(j!=subsols[1].l.end())) {if (*i < *j) { l.push_back(*i); i++; }else { l.push_back(*j); j++; }

}while (i != subsols[0].l.end()) {

l.push_back(*i); i++; }while (j != subsols[1].l.end()) {

l.push_back(*j); j++; }}








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones





Clases Proporcionadas

• SetUp: por ej: tipo de búsqueda:• en profundidad, • en anchura,• primero-el mejor

• Solver: Implementala estrategia a seguir. Compuesta por ella y:• Solver_Seq

• Solver_Lan

• Solver_SM

Setup

Solver




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Apartado III: Patrones de Resolución Secuenciales

1. Patrón de Resolución Secuencial para la técnica Ramificación y Acotación

2. Patrón de Resolución Secuencial para la técnica Divide y Vencerás

3. Combinación de esqueletos




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Algoritmo Secuencial para el Esqueleto MaLLBa:BnB

SP

P N

SP

P N

SP

P N

SP

P N

SP

P N

SP

P N

SP

P N

BranchQueue Tail

BranchQueue Head

Estructu

ra de datos

Patrón de Resolución Ramificación y

Acotación Secuencial

Patrón de Resolución Divide y Vencerás

Secuencial

Combinación de Esqueletos




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Algoritmo Secuencial para el Esqueleto MaLLBa:BnB

1 Bound BB (const Problem& pbm, const SubProblem& sp, 2 Solution& sol) { 3 branchQueue<SubProblem> bqueue; 4 Solution sl; 5 Bound high, low; 6 SubProblem sp; 7 bqueue.insert(sp); 8 while (!bqueue.empty()) { 9 sp = bqueue.remove(); 10 high = sp.upper_bound (pbm, sl); 11 if (high > bestSol){ 12 low = sp.lower_bound(pbm, sl); 13 if (low > bestSol) { 14 bestSol = low; 15 sol = sl; 16 } 17 if (low != high) 18 sp.branch(pbm, bqueue); 19 } }20 return(bestSol); 21 }

Maximización




Secuencial





Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Algoritmo Secuencial para el Esqueleto MaLLBa:DnC

1 procedure DandC(pbm, sol) {2 Local DivQueue, ComQueue; 3

4 push(DivQueue, pbm); 5 while (not empty(DivQueue)) {6 subProblem = pop(DivQueue);7 if (easy(subProblem)) {8 solve(subProblem, subSol);9 push(ComQueue, subSol); 10 } else {11 divide(subProblem, subpbm);12 for i := 1 to numProblem() do13 push(DivQueue, subpbm[i]);14 } }15

16 while (not empty(ComQueue)) {17 for (int i=0; i<node.numSolution(); i++)18 subsol = pop(ComQueue);19 combine(subsol[i], sol);20 if (not root(node))21 push(ComQueue, sol);22}

/** Fase Combinación **/

/** Fase División **/




Secuencial





Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

N

N

3

3

2

2

1

1

wp

...wp

wp

wp

≥≥≥≥ Instanciación de los esqueletos

1 int main (int argc, char** argv) {2 Knapsack::Problem pbm;3 Knapsack::Solution ksol;4 Knapsack::Bound bs;5 ...6 Knapsack::Problem opbm; //ordered problem7 QuickSort::Solution ssol;8 ...9 QuickSort::Solver_Seq svs(pbm);10 svs.run();11 ssol = svs.solution();12 ...13 opbm.setN(pbm.N);14 opbm.setCapacity(pbm.C);15 for (Knapsack::Number i = 0; i < n ; i++) {16 opbm.setWeight(pbm.w[ssol.l[i]]);17 opbm.setProfit(pbm.p[ssol.l[i]]);18 }19 Knapsack::Solver_Seq svk(opbm, st);20 svk.run();21 bs = svk.bestSolution(); ksol = svk.solution(); . . . 22 }




Secuencial





Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Apartado IV: Patrones de Resolución Paralelos

1. Patrones de Resolución Paralelos para la técnica Ramificación y Acotación

a. Esquema Centralizado

b. Esquema Distribuido

c. Esquema para Memoria Compartida

2. Patrón de Resolución Paralelo para la técnica Divide y Vencerás




Marzo, 2007

Patrón B&B Paralelo Centralizado

Patrón B&B Paralelo Distribuido

Patrón B&B Memoria Compartida

Patrón D&C Paralelo

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esqueletos MaLLBa:BnB Paralelos

Maestro Esclavos

• Paso de Mensaje• Estrategia Maestro/Esclavo

• Maestro:• Tareas de Monitorización• Gestión de las Colas• Distribución de

subproblemas• Recepción de Mensajes

• Esclavo:• Recepción de mensajes• Trabajar en los procesos

propios de la técnica

• Esquema Centralizado• Esquema Distribuido

• Memoria Compartida




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esquema Paralelo Centralizado MaLLBa:BnB

Maestro Esclavos Maestro Esclavos








Marzo, 2007

Esquema Paralelo Centralizado de MaLLBa:BnB

Estructu

ra de datos

SP

P N

SP

P N

SP

P N

SP

P N

SP

P N

BranchQueue Tail

BranchQueue Head

Processor Master

SP

P N

SP

P N

SP

P N

Head

Tail

Processor slave

SP

P N

SP

P N

SP

P N

Head

Tail

Processor slave





Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Código MPI Centralizado de MaLLBa:BnB: Maestro

1 busy[0] = 1; for i = 1, nProcs { busy[i] = 0; }

2 idle = nProcs - 1;

3 auxbqueue; // queue of subproblems sent by the slave

4 bqueue.insertAtBack(sp); // Insert the subproblem into the queue

5 while ((!bqueue.empty()) || (idle < groupSize)) { // Stop condition

6 while ((!bqueue.empty()) && (idle > 0)) {

7 auxSp = bqueue.removeFromFront();

8 op.send(firstidle, auxSp, bestSol, sol);

9 idle--;

10 IDLE2WORKING(busy, lastIdle); mark slave as working

11 }

12 MLB_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, flag, status)

13 while (flag) {

14 if (MPI_SOLVE_TAG) {

15 ip.recv(source, bestSol, sol);

16 WORKING2IDLE(busy, source); // mark the slave as idle

17 }








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Código MPI Centralizado de MaLLBa:BnB: Maestro

18 if (MPI_BnB_TAG) {

19 ip.recv(source, bstemp, high); // Receive the best solution

20 if ( high > bestSol) {

21 bestSol = bstemp;

22 op << 1; // request the queue of the subproblems to the slave

23 op.send(source, MPI_QUEUEREQUEST_TAG);

24 ip.recv(source, auxbqueue); // receive the subproblems queue

25 }

26 else { // slave's subproblems queue must be deleted

27 op << 0;

28 op.send(source, MPI_QUEUEREQUEST_TAG);

29 }

30 WORKING2IDLE(busy, source); // mark the slave as idle

31 } } // final of while flag

32 bqueue.concatqueue(auxbqueue); // Link Master and slave queue

33 } // while

34 for i = 0; groupSize { op.send(i+1, MPI_END_TAG); } // ending message








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Código MPI Centralizado de MaLLBa:BnB: Esclavo

1 while (1) {

2 MLB_Probe(MASTER,MPI_ANY_TAG, flag, status)

3 if (flag) {

4 switch(status.MPI_TAG) {

5 if (END_TAG){ // Ending message

6 ip.recv(MASTER, MPI_END_TAG);

7 return;

8 }

9 if (PBM_TAG){ // Receive the problem to branch

10 ip.recv(MASTER, MPI_PBM_TAG, auxSp, bestSol, auxSol);

11 high = auxSp.upper_bound(pbm, auxSol);

12 if ( high > bestSol ) {

13 low = auxSp.lower_bound(pbm, auxSol);

14 if ( low > bestSol ) {

15 bestSol = low;

16 sol = auxSol;

17 } }








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Código MPI Centralizado de MaLLBa:BnB: Esclavo

18 if ( high = low ) {

19 // send best solution to Master

20 op.send(MASTER, MPI_SOLVE_TAG, bestSol);

21 }

22 else {

23 op.send(MASTER, MPI_BnB_TAG, bestSol, high);

24 }

25 // Receive from Master the indication to branch or not

26 ip.recv(MASTER, MPI_QUEUEREQUEST_TAG);

27 ip >> count;

28 if ( count = 1) { // to branch the subproblem

29 auxSp.branch(pbm, bqueue);

30 op.send(MASTER, bqueue);

31 }

32 bqueue.clean();

33 } } // switch

34 } } // while








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esquema Paralelo Distribuido de MaLLBa:BnB

Maestro Esclavos Maestro Esclavos








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esquema Paralelo Distribuido de MaLLBa:BnB

Estructu

ra de datos

SP

P N

BranchQueue Head

Processor 0: Master

SP

P N

SP

P N

SP

P N

Tail

Processor 1: slave

SP

P N

SP

P N

SP

P N

SP

P N

Tail

Processor 2: slave

SP

P N








Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Código MPI Distribuido de MaLLBa:BnB: Maestro

1 busy[0] = 1; for i = 1, nProcs { busy[i] = 0;}2 idle = nProcs - 1;3 // Send initial subproblem to first idle slave 4 auxSp = sp.initSubProblem();5 op.send(firstIdle, auxSp, bestSol, sol); 6 idle--;7 IDLE2WORKING(busy,firstIdle); // mark this slave like working 8 while (idle < (groupSize-1)) { // while there are working slaves9 recv(source, flag);10 while(flag) {11 if (SOLVE_TAG) { // receive the final solution12 ip.recv(source, bestSol, sol); 13 }14 if (BnB_TAG) { // receive a slave request

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 } 31 if (IDLE_TAG) { // receive the signal of an idle slave 32 ip.recv(source, IDLE);33 idle++;34 WORKING2IDLE(busy,source); // mark this slave like idle 35 } 36 recv(source, flag);37 } } // while (idle < (groupSize-1)) 38 // Send the ending message 39 for i = 1, groupSize { op.send(i, END); }








Marzo, 2007

Código MPI Distribuido de MaLLBa:BnB: Maestro

14 if (BnB_TAG) { // receive a slave request 15 ip.recv(source, 16 high, // upper bound associated to the problem17 nSlaves); // the number of required slaves 18 if ( high > bestSol) { // the problem must be branched19 total= ((nSlaves <= idle)? nSlaves:idle);20 for i = 1, total { 21 idle--; 22 IDLE2WORKING(busy,i); 23 }24 op.send (source,25 total, // number of assigned slaves26 bestSol, // best Solution27 1,..., total // slaves identifiers28 );29 }30 else { // the problem must be bounded31 op.send(source, DONE); 32 }33 }





Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Código MPI Distribuido de MaLLBa:BnB: Esclavo

1 while (1) {2 recv(source, flag);3 while (flag) { 4 if (END_TAG){ // receive the finishing message 5 ip.recv(MASTER, END); return;6 }7 if (PBM_TAG){ // receive the problem to be branched 8 ip.recv(source, // receive from a slave or the Master:9 auxSp, // the initial subproblem10 bestSol, // the best solution value 11 sol); // the current solution12 auxSol = sol; 13 bqueue.insert(auxSp); // insert it in the local queue14 while(!bqueue.empty()) {

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 } 38 op.send(MASTER, IDLE_TAG); // send the signal Idle39 } 40 recv(source, flag);41 } // while (flag)42 } // while(1)








Marzo, 2007

Código MPI Distribuido de MaLLBa:BnB: Esclavo

14 while(!bqueue.empty()) {15 auxSp = bqueue.remove(); // pop a problem from the local queue 16 high = auxSp.upper_bound(pbm,auxSol); 17 if ( high > bestSol ) {18 low = auxSp.lower_bound(pbm,auxSol); 19 if ( low > bestSol ) {20 bestSol = low;21 sol = auxSol;22 op.send(MASTER, SOLVE_TAG, bestSol, sol); 23 }24 if ( high != low ) {25 // the number of required slaves26 rSlaves = bqueue.getNumberOfNodes(); 27 op.send(MASTER, BnB_TAG, high, rSlaves);28 ip.recv(MASTER, nfSlaves, bestSol, rank {1,..., nfSlaves});29 if ( nfSlaves >= 0) {30 auxSp.branch(pbm,bqueue); //branch and save in the local queue 31 for i=0, nfSlaves{ // send subproblems to the assigned slaves 32 auxSp = bqueue.remove();33 // send to the slave:34 op.send(rank, PBM_TAG, auxSp, bestSol, sol);35 } 36 } // if nfSlaves == DONE the problem is bounded (cut) 37 } }





Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esquema para Memoria Compartida de MaLLBa:BnB

Procesadores Procesadores








Marzo, 2007

Esquema de MaLLBa:BnB para Memoria Compartida

Estructu

ra

de datos

BranchQueueTail

SPP N

BranchQueue Head

SP

P N

SP

P N

SP

P N

SP

P N

SP

P N

Threads

SPP N

SPP N

SPP N

SPP N

SPP N

SPP N

SPP N

SPP N





Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

1 // shared variables {bqueue, bstemp, soltemp, data} 2 // private variables {auxSol, high, low} 3 // the initial subproblem is inserted in the global shared queue 4 while(!bqueue.empty()) {5 nn = bqueue.getNumberOfNodes(); // the number of needed threads6 nt = (nn > maxthread)?maxthread:nn;7 data = new SubProblem[nt]; // compute the subproblem for each thread8 for (int j = 0; j < nt; j++)9 data[j] = bqueue.remove();

10 set.num.threads(nt); // establish the number of threads11 parallel forall (i = 0; i < nt; i++) {12 high = data[i].upper_bound(pbm,auxSol);13 if ( high > bstemp ) {14 if ( low > bstemp ) { // critical region15 // only one thread can change the value at any time16 bstemp = low; 17 soltemp = auxSol; 18 }19 if ( high != low ) { // critical region20 // just one thread can insert subproblems21 // in the queue at any time22 data[i].branch(pbm,bqueue); 23 } } } }24 bestSol = bstemp;25 sol = soltemp;

Pseudocódigo OpenMP para Solver_SM





Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Esquema Paralelo D&C

Fase de División








Marzo, 2007

Esquema Paralelo D&C





Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Fase de Combinación




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Apartado V: Experimentos Computacionales

• Descripción de las Máquinas

• Resultados Computacionales




Marzo, 2007

Descripción de las Máquinas

Resultados computacionales

Descripción de las Máquinas

• Sunfire 6800 SMP, con la siguiente configuración: • 24 procesadores 750 MHz UltraSPARC-III, • 48 Gbyte de memoria compartida cada uno y • 120 Gbyte de disco duro.

• Origin 3000, con la siguiente configuración:• 160 procesadores 600 MHz MIPS R14000,• 1 Gbyte de memoria• 900 Gbyte de disco

• Un heterogéneo Cluster de PCs, con la siguiente configuración • 2 Procesadores 750 MHz AMD Duron,• 4 Procesadores 800 MHz AMD Duron,• 7 Procesadores 500 MHz AMD-K6 3D,• 256 Mbyte de memoria,• 32 Gbyte de disco duro

EPCC (Edinburgh ParallelComputing Center)

CIEMAT (Centro de Investigaciones Energéticas, Medioambientales y Tecnológicas)

Cluster de PCs del Grupo de Paralelismo de la Universidad de La Laguna

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Resultados computationales

SIZE FIFO LIFO PRIORITY

1,000 0.181 0.072 0.100

1,500 0.073 0.103 0.131

5,000 2.533 3.326 3.441

10,000 2.109 5.491 5.566

50,000 128.980 391.767 389.987

100,000 652.969 1,780.297 1,793.152

Descrición de las Máquinas





Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


TAMAÑO FIFO LIFO TREESET

1,000 1.568 1.163 1.237

1,500 0.657 1.239 1.287

5,000 50.488 55.938 107.830

10,000 23.672 102.677 102.344

50,000 2,500.708 -- --






Marzo, 2007

FIFO LIFO PRIORITY

TAMAÑO N_GEN N_VISIT N_GEN N_VISIT N_GEN N_VISIT

1,000 21,824 11,620 12,402 11,520 20,858 10,857

1,500 5,161 3,106 9,877 8,587 4,724 2,823

5,000 93,589 58,444 166,333 159,712 113,886 79,293

10,000 37,886 22,108 135,372 128,002 38,303 22,266

50,000 404,802 202,617 2,172,245 2,137,110 406,361 203,513

100,000 1,158,033 608,696 4,750,148 4,680,425 1,140,929 599,641

Table 1. Número de nodos generados y visitados (prime 107)




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


KNP N = 50,000

0,00

1,00

2,00

3,00

4,00

5,00

6,00

7,00

2 3 4 8 16 24 32

Procesadores

Spee

dup Sunfire-NoSol

Origin-NoSolSunfire-SolOrigin-Sol






Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


KNP no Sol, Size = 100,000

0,00

1,00

2,00

3,00

4,00

5,00

6,00

7,00

2 3 4 8 16 24 32

Processors

Spe

edup

Sunfire 6800 Origin 3000 PC Cluster






Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


Sunfire vs. Origin

0,00

1,00

2,00

3,00

4,00

5,00

6,00

7,00

2 3 4 8 16 24 32

Procesadores

Spe

edup

Sunfire-100,000Origin-100,000Sunfire-50,000Origin-50,000Sunfire-10,000Origin-10,000

No solution vector






Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones


KNP no Sol, Size = 100,000

0,00

1,00

2,00

3,00

4,00

5,00

6,00

7,00

2 3 4 8 16 24 32

Procesadores

Spee

dup

Sunfire-MPI Origin-MPI Origin-OpenMP






Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Conclusiones

• Diseño de un nuevo esqueleto para la técnica de Ramificación y Acotación:

MaLLBa:BnB

• Diferentes implementaciones de resolutores:

• Uno Secuencial

• Dos resolutores usando Paso de Mensaje:• Centralizado• Distribuido

• Uno para Memoria Compartida




Marzo, 2007

Introducción

Interfaz de Usuario


Patrones Paralelos


Conclusiones

Conclusiones

• Metodología de trabajo para la resolución de Problemas de Optimización Combinatoriamediante la técnica de Ramificación y Acotación

• Implementación de problemas académicos: Mochila y TSP

• Resultados Computacionales• Supercomputadores• Redes de PC

implementación secuencial y paralela de técnicas ... isabel dorta.pdf · dpto. estadística, i....

Documents