Algoritmos paralelos de memoria compartida que determinan el menor tama˜no de un ´arbol binario al refinar un simplex regular

Algoritmos paralelos de memoria compartida que determinan el menor tama˜no de un ´arbol binario al refinar un simplex regular G. Aparicio1, J.M.G. Salmer´on1,L.G.Casado 1,R.Asenjo 2,I.Garc´ıa2y E.M.T. Hendrix2 Resumen —En el´ambito de la optimizaci´on global basada en t´ecnicas de ramificaci´on y acotaci´on, cuando el espacio de b´usqueda es un n-s´ımplex regular es habitual utilizar como regla de divisi´on la bisecci´on por el lado mayor, debido a que garantiza la convergencia del algoritmo. Cuando la dimensi´on del n-s´ımplex es mayor de 2 existen varios lados mayores que pueden utilizarse para realizar la bisecci´on. La elecci´on del lado mayor influye en el tama˜no del ´arbol binario completo que se genera. Una selecci´on eficiente del lado mayor puede reducir el coste computacional de los algoritmos de ramificaci´on y acotaci´on mencionados. En este estudio estamos interesados en conocer el tama˜no del ´arbol o ´arboles m´ınimo(s). Para obtener una soluci´on de las instancias m´as complejas del problema en un tiempo razonable es necesario el desarrollo de algoritmos paralelos. La complejidad del problema es debida a la necesidad de analizar todas y cada una de las posibles combinaciones de selecciones de los distintos lados mayores en el refinamiento. Aqu´ı se comparan la eficiencia de distintas propuestas de algoritmos paralelos para sistemas de memoria compartida. Palabras clave—S´ımplice, multicore, ´arbol binario, Pthreads, C++ threads, TBB. I. Introducci´ on LOS algoritmos de Ramificaci´on y Acotaci´on (del ingl´es Branch-and-Bound, (BnB) se aplican a la resoluci´on de problemas de optimizaci´on global mediante la realizaci´on de una b´usqueda exhaustiva del m´ınimo de una funci´on objetivo en un dominio dado. En este trabajo estamos interesados en problemas donde el espacio de b´usqueda est´a definido por un n-s´ımplex regular, definido en un espacio (n+1)- dimensional [1]. Los algoritmos de BnB est´an caracterizados por las reglas de Acotaci´on, Selecci´on, Divisi´on, Rechazo y Terminaci´on. Se pretende estudiar las caracter´ısticas del ´arbol de b´usqueda generado cuando solo se tienen en cuenta las reglas de Divisi´on y Terminaci´on, es decir, ning´un nodo del ´arbol es eliminado. Se usar´acomoregladedivisi´on la bisecci´on del lado mayor (BLM) [2], [3] y como regla de terminaci´on la longitud del lado mayor de un subproblema o nodo del ´arbol. Se ha encontrado una secuencia de lados mayores a dividir en el refinamiento de un 3-simplex regular 1Grupo de Investigaci´on TIC146: Supercomputaci´on– Algoritmos, Universidad de Almer´ıa (ceiA3), Espa˜na, e-mail: [email protected], [email protected], [email protected] 2Departamento de Arquitectura de Computadores, Universidad de M´alaga, Espa˜na, e-mail: [email protected], [email protected], [email protected] que genera el ´arbol de tama˜no m´ınimo [4]. El tener precomputada al secuencia de lados mayores a dividir permite la reducci´on del tiempo de c´omputo de algoritmos de Ramificaci´on y Acotaci´on sobre este espacio de b´usqueda. Para saber si una determinada secuencia genera un ´arbol de tama˜no m´ınimo es necesario conocer dicho tama˜no. En el c´alculo del tama˜no del ´arbol m´ınimo es necesario analizar los distintos arboles que se pueden obtener dependiendo del lado seleccionado a dividir en cada sub-s´ımplex. La combinaci´on de las distintas elecciones de lados mayores a dividir generar´a distintos ´arboles de b´usqueda. Por lo tanto, nos encontramos ante un problema combinatorio con una alta carga computacional que puede ser acelerado utilizando t´ecnicas de computaci´on paralela. El objetivo de este estudio es analizar la eficiencia de varios m´etodos de paralelizaci´on en sistemas de memoria compartida que resuelven este problema. En concreto, se estudian algoritmos paralelos que utilizan Posix Threads (Pthreads), Intel Threading Building Blocks (TBB) y Threads de C++ v11. En la secci´on II se describe el un algoritmo b´asico de Ramificaci´on y Acotaci´on sobre un dominio definido por un simplex regular. En la secci´on III se describe la bisecci´on por el lado mayor. En la secci´on IV se presenta el algoritmo secuencial que calcula el menor tama˜no de un ´arbol. Las distintas versiones paralelas se muestran en la secci´on V. La secci´on VI muestra una comparativa de la eficiencia de las versiones estudiadas y finalmente se concluye en la secci´on VII. II. Optimizaci´ on Global y Algoritmos BnB La resoluci´on de un problema de Optimizaci´on Global consiste en encontrar el valor m´ınimo o m´aximo de una funci´on objetivo f, satisfaciendo ciertas restricciones en el espacio de b´usqueda. Para problemas de minimizaci´on, el problema de Optimizaci´on Global puede escribirse como f∗=f(x∗)=m´ın x∈Sf(x).(1) Cuando se requiere una b´usqueda exhaustiva del m´ınimo global, se suelen utilizar algoritmos BnB. Un algoritmo BnB realiza una b´usqueda mediante la descomposici´on sucesiva del problema inicial en subproblemas de menor tama˜no hasta alcanzar la(s) soluci´on(es) final(es) o una aproximaci´on a ella(s). Esta aproximaci´on est´a determinada por la precisi´on XXVI EDICIÓN DE LAS JORNADAS DE PARALELISMO, JP 2015 387 requerida para la soluci´on. Esta descomposici´on genera un ´arbol de b´usqueda que se poda cuando se garantiza que un subproblema no contiene una soluci´on global. La poda o rechazo de un subproblema est´a normalmente basada en c´alculos de cotas de la funci´on objetivo para ese subproblema. Algoritmo 1 Ramificaci´on y Acotaci´on Require: S: simplex inicial, : precisi´on 1: Λ := {S1=S}Conjunto de trabajo 2: Ω := {} Conjunto final 3: ns := 1 N´umero de s´ımplices 4: while Λ=∅do 5: Selecciona Side Λ Regla de selecci´on 6: Eval´ua SiRegla de acotaci´on 7: if Sino puede ser eliminado then Regla de rechazo 8: if w(Si)≤then Regla de terminaci´on 9: Almacena Siin Ω 10: else 11: {S2i,S 2i+1}:= BLM(Si)Regla de divisi´on 12: Almacena S2i,S2i+1 en Λ 13: ns := ns +2 14: return Ωyf(x∗) El esquema b´asico de un algoritmos de BnB se muestra en el algoritmo 1. El comportamiento, y por tanto la eficiencia del algoritmo depender´adecomo se establezcan las reglas de Selecci´on, Acotaci´on, Rechazo, Divisi´on y Terminaci´on. En este estudio no estudiaremos las reglas de Acotaci´on, Rechazo ni de Selecci´on ya que solo estamos interesados en encontrar la regla de Divisi´on basada en la bisecci´on del lado mayor que genere un ´arbol de menor tama˜no. Porlotanto,noexistepodayel´arbol se generar´ıa completamente. Su tama˜no no solo depender´a del lado mayor elegido para ser dividido, sino tambi´en de la regla de terminaci´on usada. En nuestro caso, un simplex con un tama˜no de su lado mayor, o una anchura w(S), menor que un umbral no ser´anuevamente dividido. III. Particionamiento de un n-simplex regular En algunos problemas de Optimizaci´on Global es habitual el uso de un espacio de b´usqueda definido por un n-simplex regular. Por simplicidad y sin p´erdida de generalidad, en este estudio se va a hacer uso de un simplex regular con longitud de lado igual a 1, que se define como: S=⎧ ⎨ ⎩ x∈Rn+1 : n+1  j=1 xj=√2 2;xj≥0⎫ ⎬ ⎭ .(2) La figura 1 muestra un 2-simplex regular con lados de tama˜no unidad. La selecci´on de un lado mayor en un 2-simplex no es necesaria ya que o el lado mayor es ´unico o el subsimplex a dividir es regular. A partir de n=3s´ı existen varias opciones para elegir el lado mayor a dividir, como se muestra en la figura 2. x1 x2 x3 (√2 2,0,0) (0,√2 2,0) (0,0,√2 2) Fig. 1. Un 2-simplex regular con lados de longitud unidad. Lados mayores Fig. 2. Primera bisecci´on del lado mayor en un 3-simplex. IV. Algoritmo secuencial para determinar el tama˜ no de uno de los menores ´ arboles binarios El algoritmo secuencial debe chequear todas las opciones de divisi´on de lado mayor, para tener en cuenta solo aquellas que generan un ´arbol binario de menor tama˜no. Esto se puede hacer mediante un algoritmo recursivo. Los par´ametros iniciales del algoritmo 2 ser´ıan el n-simplex regular inicial, uno de sus lados (todos son iguales) y la precisi´on de refinamiento requerida . Algoritmo 2 Tama˜no´ Arbol (S,L,) Require: S:simplex,L: lado mayor, : precisi´on 1: if w(S)≤then 2: return 1 3: {S1,S 2}=DivideS´ımplice(S,L) 4: for cada lado mayor Lide S1do 5: r1i:= Tama˜no´ Arbol(S1,Li,) 6: for cada lado mayor Lide S2do 7: r2i:= Tama˜no´ Arbol(S2,Li,) 8: r1:= m´ıni{r1i} 9: r2:= m´ıni{r2i} 10: return 1+r1+r2 El algoritmo 2 realiza una b´usqueda en profundidad, lo que reduce los requerimientos de memoria. La figura 3 muestra la ejecuci´on del algoritmo 2 para un 2-simplex y =0,5. La figura 3 permite resaltar algunos aspectos que, para simplificar, no se han incluido en el algoritmo 2: Si los s´ımplices hermanos S1yS2son sim´etricos, 388 JP 2015 S1 S2S3 S4 S5S6 S7 S8S9S10 S11 Nivel 1 Nivel 2 Nivel 3 Nivel 4 Fig. 3. ´ Arbol binario para =0,5. ambos generan sub´arboles de igual tama˜no. Por lo tanto solo es necesario procesar uno de ellos. En ese caso se devuelve como resultado el doble del tama˜no del sub´arbol procesado. Por ejemplo, los s´ımplices S2yS3oS8yS9de la figura 3 son hermanos sim´etricos. Si el simplex es regular, solo hay que procesar un lado, ya que todos los lados son de igual tama˜no, produciendo adem´as hermanos sim´etricos. Por ejemplo, los s´ımplices S1,S4yS7de la figura 3 son regulares. En el algoritmo 2, ser´ıa conveniente poder determinar antes de su procesado parejas de hermanos resultado de la divisi´on de distintos lados mayores de un simplex que son parejas sim´etricas. De forma an˜naloga a simplices sim´etricos, solo ser´ıa necesario procesar una de las parejas. Esto se abordar´aentrabajos futuros. V. Versiones paralelas El paralelismo es f´acilmente aplicable en la construcci´on de ´arboles ya que las ramas del ´arbol pueden visitarse en paralelo. Una de las dificultades que pueden presentar los ´arboles, y que ocurre en los ´arboles de este estudio, es que pueden existir ramas con diferentes tama˜nos, tal como muestra la figura 3. Se ha observado experimentalmente que la diferencia de niveles entre ramas aumenta conforme lo hace n.Por lo tanto es necesario el uso de un balanceo de la carga que permita obtener una buena eficiencia en los algoritmos paralelos que recorren este tipo de ´arboles. El algoritmo 3 es una extensi´on simple del algoritmo 2 donde se crea una nueva hebra para procesar un sub´arbol. El n´umero de hebras no puede superar el umbral MaxHebras que se define como par´ametro de entrada. Cada hebra ejecuta el algoritmo secuencial con la posibilidad de crear una nueva hebra para procesar el trabajo pendiente. Una hebra que termina su trabajo, devuelve el resultado y muere, decrementando antes la variable MaxHebras, lo que permitir´ala generaci´on de otra hebra. En principio la primera hebra que acceda a la variable compartida NHebras y verifique que es menor que MaxHebras podr´a generar una nueva hebra. De esta forma, el balanceo de la Algoritmo 3 Tama˜no´ ArbolParalelo (S,L,) Require: S:simplex,L: lado mayor, : precisi´on, MaxHebras: m´aximo n´umero de hebras. 1: if w(S)≤then 2: return 1 3: {S1,S 2}=DivideS´ımplice(S,L) 4: for cada lado mayor Lide S1do 5: if NHebras <MaxHebras then 6: r1i:= CreaHebra(Tama˜no ´ Arbol(S1,Li,)) 7: else 8: r1i:= Tama˜no´ Arbol(S1,Li,) 9: for cada lado mayor Lide S2do 10: if NHebras <MaxHebras then 11: r2i:= CreaHebra(Tama˜no ´ Arbol(S2,Li,)) 12: else 13: r2i:= Tama˜no´ Arbol(S2,Li,) 14: Esperar resultados de las hebras creadas 15: r1:= m´ıni{r1i} 16: r2:= m´ıni{r2i} 17: return 1+r1+r2 carga es inherente a la creaci´on din´amica de hebras. Tomando como base el algoritmo anterior, se va ha estudiar el uso de diferentes librer´ıas para el desarrollo de algoritmos paralelos en sistemas multicore que resuelvan el problema de calcular el menor tama˜no de los posibles ´arboles binarios de b´usqueda. A. Posix Threads (Pthreads) POSIX son las siglas correspondientes a Portable Operating System Interface for Unix. Es un est´andar orientado a facilitar la creaci´on de aplicaciones portables y de confianza bajo entornos Unix. La mayor´ıa de las versiones populares de Unix como Linux o Mac OS X cumplen este est´andar en gran medida. La biblioteca para el manejo de hebras en POSIX es Pthread. En Pthreads la creaci´on, sincronizaci´on y destrucci´ondelashebrasesexpl´ıcita y controlada por el programador. Esto tiene sus ventajas e inconvenientes. Por un lado, permite un mayor control al programador, pero por otro lado es el programador el que debe garantizar la correcta utilizaci´on de la librer´ıa de una forma eficiente. B. Threads de C++ version 11 Una de las mejoras que incluye la versi´on 11 de C++ (C++11) es el soporte nativo de aplicaciones multihebradas. Para ello incluye la clase tipo hebra(std::thread). Su uso en la pr´actica es muy similar al de Pthreads. Sin embargo, hay que destacar las siguientes diferencias: Pthreads se encuentra disponible en multitud de plataformas siendo un sistema muy portable. C++11 no esta disponible para algunas plataformas. Pthreads es una librer´ıa de C y no fue dise˜nada teniendo en cuenta aspectos fundamentales de C++11 como la vida de un objeto o las excepciones. La funci´on pthread cancel, que cancela una hebra en Pthreads, no tiene su equivalente en C++11. Pthreads permite el control del tama˜no de la pila asociada a las hebras, mientras que C++11 XXVI EDICIÓN DE LAS JORNADAS DE PARALELISMO, JP 2015 389 no ofrece esta funcionalidad. C++11 proporciona la clase thread como una abstracci´on para una hebra en ejecuci´on. C++11 tiene varias clases y templates para realizar exclusi´on mutua, utilizar variables de condici´on y bloqueos. C++11 proporciona un sofisticado conjunto de funciones y templates para crear objetos y funciones an´onimas (expresiones lambda) en la clase thread. C. Intel Threading Building Blocks Threading Building Blocks (TBB) es una librer´ıa desarrollada en C++ por Intel para ayudar en la programaci´on paralela en procesadores multicore. La librer´ıa consiste en algoritmos y estructuras de datos que facilitan al programador la programaci´on con hebras. Por ejemplo, la ejecuci´on de un programa TBB crea, sincroniza y destruye grafos de dependencias entre tareas, que se ejecutan respecto a las dependencias en el grafo, lo que puede ser completamente transparente al programador. TBB realiza un balanceo de carga entre hebras mediante un m´etodo denominado robo de tareas (thread-stealing). Mediante este m´etodo, una hebra, que no tenga tareas para ejecutar en su cola de tareas, robar´ıa tareas de la colas de tareas de otra hebras. Este balanceo din´amico de la carga puede ser completamente transparente para el programador, lo que facilita el desarrollo de aplicaciones paralelas escalables. La versi´on TBB del algoritmo 3, en lugar de crear una hebra nueva que eval´ue el sub´arbol generado por la divisi´on de uno de los lados mayores (lineas 6 y 11), crea una nueva tarea por cada posible divisi´on de un simplex a evaluar. La tarea ser´a ejecutada por la hebra que la cre´o o por otra, dependiendo de la necesidad de realizar un balanceo de la carga. El n´umero de hebras lo determina el usuario y es fijo durante la ejecuci´on del algoritmo paralelo. VI. Resultados Los algoritmos se han compilado con gcc/g++ (GNU compiler Collection) versi´on 4.8.1 con la opci´on -O3, usando las librer´ıas de Pthreads,TBB y Threads de C++11. Los programas y se han ejecutado en un nodo de BullX-UAL con 16 cores y en la m´aquina multiprocesador Aloe con 32 cores. BullX consiste en dos procesadores Intel R Xeon R E5-2650 de 8 cores a 2,00 GHz y 64 GB de RAM. Aloe consiste en dos procesadores Intel R Xeon R E5-2698-V3 de 16 cores a 2,30 GHz y 256 GB de RAM. Los experimentos se han realizado para dos instancias del problema: I1: 3-simplex con una precisi´on de =0,01, I2: 4-simplex con una precisi´on de =0,125. No se han usado valores mayores de nni menores de ya que los tiempos de ejecuci´on de los algoritmos ser´ıan excesivos debido a la complejidad de optimizaci´on combinatoria que plantean. Como muestra el algoritmo 2, el problema a resolver presenta un bajo coste computacional por subsimplice, pero un alto coste de gesti´on din´amica de memoria para el recorrido del ´arbol, cuando tenga un gran n´umero de subsimplices a procesar. Por lo tanto el gestor de memoria din´amica juega un papel importante en el tiempo total de ejecuci´on de los algoritmos. El compilador gcc usa su propia librer´ıa de gesti´on din´amica de memoria. TBB tambi´en usa su propia librer´ıa llamada tbbmaloc proxy. Existe la posibilidad de usar otras librer´ıas de gesti´on din´amica de memoria, como por ejemplo tcmalloc de google performance tools o LLAlloc de Lockless Inc. TABLA I Tiempo de ejecuci´ on en segundos del algoritmo secuencial con diferentes gestores de memoria en la m´ aquina Bullx Instancia GCC TCMalloc TBBMalloc LLAlloc I1 1357.45s 1103.19s 1249.46s 698.26s I2 269.62s 223.11s 249.97s 152.71s La Tabla I muestra el tiempo de ejecuci´on en la m´aquina BullX de la versi´on secuencial del algoritmo usando las distintas librer´ıas de gesti´on din´amica de memoria. Puede observarse que el mejor gestor de memoria es LLAlloc. Los tiempos de la versi´on secuencial (tambi´en tomados en la m´aquina BullX) con LLAlloc han sido de 698.26s para I1 y de 152.71s para I2. Dichos tiempos han sido tomados como referencia para el c´alculo del speedup. Se ha observado experimenalmente que TBB con LLAlloc obtiene mejores tiempos de ejecuci´on que cuando usa su propio gestor de memoria TBBMalloc. TABLA II Tiempo de ejecuci´ on (T) y Speed-up (SP) para resolver I1 utilizando un n´ umero NT de hebras con Pthreads (PTH), TBB Y Threads de C++11 (TC11) en la m´ aquina Bullx NT T(PTH) SP(PTH) T(TC11) SP(TC11) T(TBB) SP(TBB) 1 699.90s 0.99 699.97s 0.99 783.20s 0.89 2 480.93s 1.45 480.31s 1.46 394.43s 1.77 4 256.88s 2.72 259.27s 2.70 193.32s 3.62 8 315.10s 2.22 272.66s 2.57 97.64s 7.16 16 294.97s 2.38 286.74s 2.44 48.90s 14.30 32 351.84s 1.98 342.58s 2.04 48.68s 14.37 Las tablas II y III muestran los tiempos de ejecuci´on y la ganancia en velocidad para distintos n´umeros de hebras en los algoritmos paralelos estudiados en la m´aquina BullX. La ganancia en velocidad se muestra tambi´en en las figuras 4 y 5. La librer´ıa TBB presenta los mejores resultados, con una ganancia en velocidad cercana a la lineal hasta 16 hebras, que es el n´umero de cores del sistema en el caso de la m´aquina BullX. Esto es debido a la buena gesti´on de lastareasenlascolasdela hebras, lo que permite evitar tiempos ociosos en los procesadores. Las versiones basadas en Pthreads y C++11 presentan una 390 JP 2015 0 5 10 15 20 25 30 35 numThreads 0 5 10 15 20 25 30 35 Speed up PThreads Threads C++11 TBB Lineal Fig. 4. Ganancia en velocidad para I1 en la m´aquina Bullx TABLA III Tiempo de ejecuci´ on (T) y Speed-up (SP) para resolver I2 utilizando un n´ umero NT de hebras con Pthreads (PTH), TBB Y Threads de C++11 (TC11) en la m´ aquina Bullx NT T(PTH) SP(PTH) T(TC11) SP(TC11) T(TBB) SP(TBB) 1 154.23s 0.99 154.42s 0.99 158.08s 0.97 2 120.81s 1.26 123.07s 1.24 78.40s 1.95 4 52.59s 2.90 53.52s 2.85 39.12s 3.93 8 39.85s 3.83 35.97s 4.25 19.80s 7.76 16 27.95s 5.46 27.89s 5.48 9.78s 15.71 32 30.82s 4.95 30.85s 4.95 9.87s 15.57 baja ganancia en velocidad. Esto es debido a que el modelo de hebras din´amico presentado en el algoritmo 3 tiene el inconveniente de que las hebras deben esperar la terminaci´on de las hebras que han creado (ver l´ınea 14). En las figuras 6 y 7 se observan los resultados de ejecutar las instancias del problema I1 e I2 en la m´aquina Aloe. Se corroboran los resultados obtenidos en la m´aquina BullX. La versi´on TBB es escalable y obtiene speedups cercanos al lineal. Sin embargo las ejecuciones utilizando Pthreads o Threads de C++ versi´on 11 tienen problemas de escalabilidad. Aun as´ı, estamos interesados en mejorar la versiones basadas en la generaci´on din´amica de hebras ya que esto permitir´a a la aplicaci´on paralela adaptarse a los recursos disponibles en el sistema en tiempo de ejecuci´on [5]. VII. Conclusiones y trabajo futuro Los algoritmos paralelos para determinar el menor tama˜no de un ´arbol binario generado en el refinamiento de un simplex regular mediante la bisecci´on de un lado mayor en sistemas multicore presentan un bajo coste computacional por subs´ımplice, para un 3-simplex y un 4-simplex, pero un alto coste en la gesti´on din´amica de memoria cuando el ´arbol a procesar es grande. Por lo tanto, el gestor de memoria usado juega un papel importante en el rendimiento final del algoritmo. Se han comparado los gestores de memoria de GNU gcc, Intel TBB, Google y Lockless 0 5 10 15 20 25 30 35 numThreads 0 5 10 15 20 25 30 35 Speed up PThreads Threads C++11 TBB Lineal Fig. 5. Ganancia en velocidad para I2 en la m´aquina Bullx 0 5 10 15 20 25 30 35 numThreads 0 5 10 15 20 25 30 35 Speed up PThreads Threads C++11 TBB Lineal Fig. 6. Ganancia en velocidad para I1 en aloe Inc., resultando este ´ultimo el m´as eficiente. En cuanto a las librer´ıas de desarrollo de aplicaciones multihebradas, todas han mejorado con el uso del gestor de memoria LLAlloc. TBB presenta la mejor eficiencia, cercana a la lineal, gracias a la gesti´on de las colas de tareas asociadas a las hebras en ejecuci´on. Debido a su facilidad de uso resulta la mejor opci´on. El modelo paralelo basado en la generaci´on din´amica de hebras con Pthread y C++11 presenta una baja ganancia en velocidad debido a que unas hebras deben esperar a la terminaci´on de otras. Estamos interesados en mejorar este modelo ya que permitir´a a la aplicaci´on multihebrada adaptar su nivel de paralelismo a los recursos disponibles en el sistema en tiempo de ejecuci´on. Agradecimientos Este trabajo ha sido subvencionado por el Ministerio de Ciencia e Innovaci´on (TIN2008-01117 y TIN2012-37483) y la Junta de Andaluc´ıa (P011TIC7176) y financiado en parte por el Fondo Europeo de Desarrollo Regional (ERDF). Referencias [1] L.G. Casado, I. Garc´ıa, B.G. T´oth, and E.M.T. Hendrix, “On determining the cover of a simplex by spheres centeXXVI EDICIÓN DE LAS JORNADAS DE PARALELISMO, JP 2015 391 0 5 10 15 20 25 30 35 numThreads 0 5 10 15 20 25 30 35 Speed up PThreads Threads C++11 TBB Lineal Fig. 7. Ganancia en velocidad para I2 en aloe red at its vertices,” Journal of Global Optimization,vol. 50, no. 4, pp. 645–655, 2011, DOI:10.1007/s10898-0109524-x. [2] Andrew Adler, “On the Bisection Method for Triangles,” Mathematics of Computation, vol. 40, no. 162, pp. 571– 574, 1983, DOI:10.1090/S0025-5718-1983-0689473-5. [3] R. Horst, “On generalized bisection of n-simplices,” Mathematics of Computation, vol. 66, no. 218, pp. 691–698, 1997, DOI:10.1090/S0025-5718-97-00809-0. [4] Guillermo Aparicio, Leocadio G. Casado, Bogl´arka GT´oth, Eligius M. T. Hendrix, and Inmaculada Garc´ıa, “On the minimim number of simplex shapes in longest edge bisection refinement of a regular nsimplex,” Informatica, vol. 26, no. 1, pp. 17–32, 2015, DOI:10.15388/Informatica.2015.36. [5] J.F. Sanjuan-Estrada, L.G. Casado, and I. Garc´ıa, “Adaptive parallel interval branch and bound algorithms based on their performance for multicore architectures,” Journal of Supercomputing, vol. 58, pp. 376–384, 2011, DOI: 10.1007/s11227-011-0594-4. 392 JP 2015