TESIS Jose Carlos Cano Lorente
TESIS Jose Carlos Cano Lorente
TESIS Jose Carlos Cano Lorente
¡Gracias a todos!
Índice general
1 Introducción 5
1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Modelado, análisis y simulación de sistemas mecánicos . . 10
1.2.2 Simuladores para la dinámica de sistemas mecánicos . . . . 15
1.2.3 Arquitecturas de hardware paralelo . . . . . . . . . . . . . 23
1.2.4 Programación paralela . . . . . . . . . . . . . . . . . . . . 25
1.2.5 Librerı́as de álgebra lineal . . . . . . . . . . . . . . . . . . 28
1.2.6 Paralelismo en simuladores de sistemas mecánicos . . . . . 30
1.2.7 Autooptimización . . . . . . . . . . . . . . . . . . . . . . . 35
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.4 Metodologı́a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.5 Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.6 Estructura de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . 41
i
Índice general
3 Herramientas computacionales 71
3.1 Herramientas hardware . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2 Herramientas software . . . . . . . . . . . . . . . . . . . . . . . . 80
3.2.1 Compiladores . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.2.2 Librerı́as de álgebra lineal . . . . . . . . . . . . . . . . . . 81
3.2.3 Componentes auxiliares . . . . . . . . . . . . . . . . . . . 86
3.3 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4 Optimización y Autooptimización 89
4.1 Ideas generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2 Optimización de software cientı́fico . . . . . . . . . . . . . . . . . 90
4.2.1 Supervisión de rendimientos . . . . . . . . . . . . . . . . . 91
4.2.2 Modelado de rendimientos . . . . . . . . . . . . . . . . . . 93
4.2.3 Optimización . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2.3.1 Optimización a nivel de aplicaciones . . . . . . . 94
4.2.3.2 Optimización de compilación . . . . . . . . . . . 95
4.2.3.3 Datos históricos como fuente de información . . . 97
4.2.3.4 Parámetros ajustables y espacios de búsqueda . . 98
4.2.3.5 Algoritmos de búsqueda . . . . . . . . . . . . . . 99
4.2.4 Autooptimización de rutinas paralelas de álgebra lineal . . 99
4.2.5 Ejemplo de aplicación: optimización de un modelo de pre-
dicción climático . . . . . . . . . . . . . . . . . . . . . . . 101
4.3 Optimización de códigos de simulación de sistemas multicuerpo . 103
4.3.1 Caracterı́sticas de los algoritmos . . . . . . . . . . . . . . . 103
4.3.2 Autooptimización en el simulador . . . . . . . . . . . . . . 104
4.4 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
ii
Índice general
5 Simulador 107
5.1 Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.2 Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2.1 Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.2.2 Rutinas de usuario . . . . . . . . . . . . . . . . . . . . . . 116
5.2.3 Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2.4 Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.2.5 Parámetros . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.6 Escenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.7 Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.2.8 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3 Rutas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.4 Base de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.5 Árbol de rutas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.5.1 Propiedades del árbol de rutas definido en el simulador . . 139
5.5.2 Generación del árbol de rutas . . . . . . . . . . . . . . . . 142
5.5.3 Tiempo de ejecución de una ruta . . . . . . . . . . . . . . 147
5.5.4 Estimación de tiempos . . . . . . . . . . . . . . . . . . . . 149
5.5.4.1 Estimación del tiempo de ejecución de un nodo
con parámetros algorı́tmicos preestablecidos . . . 152
5.5.4.2 Estimación del tiempo de ejecución de un nodo
con autooptimización de parámetros algorı́tmicos 158
5.6 Simulación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.6.1 Configuración del simulador . . . . . . . . . . . . . . . . . 164
5.6.2 Modos de simulación . . . . . . . . . . . . . . . . . . . . . 167
5.6.2.1 Modo de entrenamiento . . . . . . . . . . . . . . 168
5.6.2.2 Modo simple . . . . . . . . . . . . . . . . . . . . 170
5.6.2.3 Modo múltiple . . . . . . . . . . . . . . . . . . . 171
5.6.2.4 Modo autooptimizado . . . . . . . . . . . . . . . 173
5.6.3 Informe de ejecución . . . . . . . . . . . . . . . . . . . . . 174
5.7 Herramientas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.7.1 Análisis de resultados: vista tabular . . . . . . . . . . . . . 176
5.7.2 Análisis de resultados: vista gráfica . . . . . . . . . . . . . 177
iii
Índice general
6 Experimentos 187
6.1 Aplicación del simulador al análisis cinemático de sistemas multi-
cuerpo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
6.1.1 Plataforma de Stewart . . . . . . . . . . . . . . . . . . . . 188
6.1.1.1 Plataforma de Stewart: resolución secuencial . . . 194
6.1.1.2 Plataforma de Stewart: solución global . . . . . . 205
6.1.1.3 Plataforma de Stewart: resolución paralela . . . . 208
6.1.1.4 Plataforma de Stewart: ejecución autooptimizada 212
6.1.2 Modelo de suspensión de un camión . . . . . . . . . . . . . 218
6.1.2.1 Suspensión de un camión: resolución secuencial . 221
6.1.2.2 Suspensión de un camión: resolución paralela . . 224
6.1.2.3 Suspensión de un camión: escalado a un modelo
multieje . . . . . . . . . . . . . . . . . . . . . . . 228
6.2 Aplicación del simulador a la optimización de rutinas de álgebra
lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
6.2.1 Multiplicación de matrices por bloques . . . . . . . . . . . 234
6.2.1.1 Experimentos en sistemas con CPU multicore . . 236
6.2.1.2 Experimentos en sistemas multiGPU . . . . . . . 242
6.2.2 Multiplicación de matrices: algoritmo de Strassen . . . . . 245
6.2.2.1 Experimentos en sistema con CPU monocore . . 250
6.2.2.2 Experimentos en sistema con CPU multicore . . . 255
6.3 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
iv
Índice general
v
Índice general
vi
Índice general
Bibliografı́a 365
vii
Índice general
viii
Índice de Tablas
2.1 Grados de libertad que eliminan los pares cinemáticos que forman
los eslabones del sistema mecánico según su grado k. . . . . . . . 50
ix
Índice de Tablas
x
Índice de Tablas
xi
Índice de Tablas
xii
Índice de Tablas
xiii
Índice de Tablas
xiv
Índice de Tablas
xv
Índice de Tablas
xvi
Índice de Tablas
xvii
Índice de Tablas
xviii
Índice de figuras
xix
Índice de figuras
xx
Índice de figuras
xxi
Índice de figuras
xxii
Índice de figuras
xxiii
Índice de figuras
xxiv
Índice de figuras
xxv
Índice de figuras
xxvi
Índice de figuras
xxvii
Índice de figuras
xxviii
Índice de figuras
xxix
Índice de figuras
xxx
Índice de figuras
xxxi
Índice de figuras
xxxii
Índice de algoritmos
xxxiii
Índice de algoritmos
xxxiv
Índice de Listados
xxxv
Índice de Listados
xxxvi
Resumen
1
Las plataformas de hardware actuales incorporan más de una unidad de proce-
samiento, bien integrando varios procesadores en sus CPUs, bien añadiendo otras
unidades de arquitectura masivamente paralela, como las GPUs, para conformar
nodos de computación hı́bridos. La existencia de este tipo de hardware paralelo
motiva el interés en explotar la ejecución simultánea de cálculos, con la consiguien-
te reducción de los tiempos de resolución de modelos complejos. Ahora bien, una
aplicación óptima de técnicas paralelas requiere de un conocimiento profundo del
hardware y de las librerı́as de cómputo disponibles, muchas de las cuales requie-
ren un ajuste mediante parámetros para aprovechar todo su potencial. Por este
motivo, no es frecuente que investigadores en áreas cientı́ficas concretas sean a
la vez expertos conocedores de los diversos paradigmas de programación paralela
existentes.
2
Abstract
Modeling is the discipline that allows the analysis and simulation of the beha-
vior of a certain system through the numerical representation of its properties.
Applications include among others the study of natural, climatic, population or
mechanical systems. The modeling techniques available nowadays make it pos-
sible to afford the study of increasingly complex systems, usually requering the
efficient use of computer systems to obtain its numerical resolution in times wit-
hin the limits fixed by the computer resources. For this reason, scientists develop
these models focusing on its subsequent translation into algorithms that can be
executed in a computer. For example, in the field of engineering that studies
multibody systems, a topological formulation facilitates automatic modeling and
allows the efficient computational resolution of the system kinematics. The in-
formation obtained from this process can be applied afterwards to the design of
new mechanisms, and covers aspects such as the analysis of the position of the
elements that make up the system and the range of movement of the moving
parts.
3
The new hardware platforms incorporate more than one processing unit, eit-
her by integrating several processors in their CPUs, or by adding other units of
massively parallel architecture, such as GPUs, or a combination of them, to make
up hybrid computing nodes. The availability of this type of parallel hardware
leads to an interest in exploiting the execution of simultaneous calculations, get-
ting the benefit in the reduction of execution times. However, the optimal fit of
parallel techniques requires a wide knowledge of the hardware and the available
software libraries, many of which require the adjustment of a set of parameters
for high performance. For this reason, it is not common for expert researchers in
a specific scientific area to also be knowledgeable of the various existing parallel
programming paradigms.
This thesis focuses on covering the gap between the discipline of mechani-
cal engineering and computing, providing to non expert users in parallelism a
simulator that includes the analysis and optimization of algorithms through the
appropriate selection and configuration of libraries. Based on the model of a multi-
body system in the form of a graph that collects the calculations (basically matrix
algebra operations) and their dependencies, this software lets the user to adjust
the parallelism and librarie’s parameters and then to carry out simulations to
analyze the influence of this adjustment on the execution times. A self-optimized
execution will also find the most efficient way to group the calculations, as well
as the appropriate library to be used and the optimal settings that should be
applied in each resolution stage of the algorithm.
Additionally, this thesis shows how this methodology can be applied to other
disciplines outside the mechanical engineering field, specifically to those where
problems can be posed with a similar approach, that is, as groupings of calcula-
tions consisting on matrix operations performed in a certain sequence. An exam-
ple is the application to some basic linear algebra routines, such as the matrix
multiplication.
4
Capı́tulo 1
Introducción
En este capı́tulo inicial de la tesis se ofrece una visión general del contenido y
estructura del presente documento. Se describe el contexto en el que se enmarca la
investigación realizada, introduciendo para ello los conceptos teóricos necesarios,
y llevando a cabo un repaso general del estado del arte en las áreas objeto de
estudio. A continuación se presenta el objetivo principal de la tesis y su desglose
en objetivos especı́ficos, ası́ como la metodologı́a empleada en la consecución de
los mismos. Por último se enumeran las contribuciones realizadas a raı́z de este
trabajo, y se explica la estructura de la tesis con un breve extracto del contenido
de cada capı́tulo.
1.1 Contexto
5
Capı́tulo 1: Introducción
Sin embargo, a pesar del avance en las prestaciones y en los recursos de las
plataformas computacionales, incluidas las de coste medio-bajo utilizadas nor-
malmente por los investigadores y diseñadores en general, las herramientas que
se utilizan para la simulación y diseño de máquinas apenas explotan un porcen-
taje muy reducido de su potencial de cómputo; en la mayorı́a de los casos, los
desarrolladores de software propio centran sus esfuerzos en mejorar las técnicas
de modelado y las formulaciones cinemáticas y dinámicas en las que se basa la
simulación, mientras que los diseñadores que utilizan software comercial, simple-
mente delegan en él su capacidad de explotar los recursos computacionales de
forma eficiente.
6
1.1. Contexto
Las principales motivaciones que nos han llevado a emprender este estudio
son las siguientes:
7
Capı́tulo 1: Introducción
8
1.2. Estado del arte
En esta sección se ofrece una recopilación de los últimos avances en las áreas de
conocimiento relacionadas con la elaboración de esta tesis, en concreto el mode-
lado y simulación de sistemas mecánicos, las arquitecturas de hardware paralelas
y su programación, las librerı́as de álgebra lineal y, por último, las estrategias de
autooptimización de software.
9
Capı́tulo 1: Introducción
10
1.2. Estado del arte
11
Capı́tulo 1: Introducción
Los problemas de análisis dinámico son mucho más complejos de resolver que
los cinemáticos, que deben resolverse previamente (o simultáneamente) [189, 268].
Los problemas dinámicos involucran a las fuerzas que actúan sobre el sistema y,
además, la masa, el tensor de inercia y la posición del centro de masas de todos
los eslabones que lo forman. Los problemas más relevantes de ı́ndole dinámica
que aborda esta disciplina son los siguientes:
12
1.2. Estado del arte
13
Capı́tulo 1: Introducción
MODELO FORMAL
...
3
�x3 � xD �2 � � y3 � y D �2 � L23 � 0
�x2 � x1 �� �x3 � xD � � � y2 � y1 �� � y3 � yD � � 0
...
Ajuste
Modelo 4 6
computerizado
PREDICCION
OBSERVACION
del comportamiento
del comportamiento
(SIMULACION) 5
Diferencia
observación vs
predicción
14
1.2. Estado del arte
Por otro lado, existen herramientas más generales que permiten modelar cual-
quier tipo de mecanismo, añadiendo sólidos al sistema y especificando las juntas
que representan las uniones de dichos sólidos con el resto de componentes. La
15
Capı́tulo 1: Introducción
16
1.2. Estado del arte
V-REP puede trabajar con una API estándar que ofrece más de 500 fun-
ciones programadas en C++ y LUA [187] desde las que se pueden controlar
la escena y los modelos. Además, incorpora APIs externas con cerca de 100
funciones que permiten enlazar la simulación con otras librerı́as. Admite
programación en C/C++, Phyton, Java, MATLAB, Octave [163] y LUA.
17
Capı́tulo 1: Introducción
Este software se ofrece con licencia comercial, con una modalidad gratuita
con fines educativos. En el año 2019, V-REP ha sido mejorado y renombrado
como CoppeliaSim.
18
1.2. Estado del arte
19
Capı́tulo 1: Introducción
20
1.2. Estado del arte
21
Capı́tulo 1: Introducción
Del estudio de las herramientas anteriormente citadas se observa que las más
avanzadas (Ansys, Adams, SOLIDWORKS, SolidEdge, Abaqus) facilitan la crea-
ción y representación de sistemas mecánicos de carácter general (lazos abiertos /
cerrados) con sólidos rı́gidos o flexibles y mediante interfaces de usuario muy bien
desarrolladas. Resuelven bastante bien la cinemática y la dinámica de sistemas
no demasiado complejos y generan informes de resultados de gran calidad para
uso académico y comercial. Tienen un gran público, ya que integran varias fases
del desarrollo del producto, desde su modelado hasta su fabricación en máquinas
de control numérico. Sin embargo, estas aplicaciones son comerciales, con licen-
cias costosas solo al alcance de empresas con suficiente facturación en diseño de
maquinaria. Son herramientas cerradas con las que no se puede interactuar pa-
ra mejorar un motor de cálculo o incorporar nuevas funcionalidades, como por
ejemplo optimización o sı́ntesis cinemática.
22
1.2. Estado del arte
23
Capı́tulo 1: Introducción
vez más finas. Por otro lado, a medida que aumenta el número de transistores en
el chip y la frecuencia a la que trabajan, también crece la potencia que necesitan
y el calor que deben disipar. A raı́z de estas consideraciones, se han producido
estudios tendentes a revisar el fin de la validez de esta ley [188, 264, 285].
Por otro lado, la llegada de las tarjetas gráficas o GPUs [169, 237] ha permitido
el uso de sus coprocesadores, originariamente optimizados para el procesamiento
gráfico, para realizar tareas más generales en el ámbito del álgebra lineal, ope-
raciones con matrices y, en general, en áreas dominadas por operaciones sobre
datos en paralelo. Por este motivo se han convertido en lo que actualmente se
denominan como GPUs de propósito general, o GPGPUs. Además, es posible la
virtualización de GPUs [272], de manera que varias máquinas virtuales pueden
acceder directamente a la capacidad de procesamiento de gráficos de una única
GPU fı́sica.
24
1.2. Estado del arte
25
Capı́tulo 1: Introducción
Para sistemas con memoria distribuida encontramos las librerı́as PVM [123] y
MPI [238, 274]. Este último proporciona el estándar actual para la programación
mediante paso de mensajes y de él existen múltiples implementaciones, siendo
OpenMPI [231] la más difundida. Este método de programación paralela permite
la portabilidad a una gran variedad de sistemas, desde máquinas con memoria
compartida hasta redes de estaciones de trabajo. A cada nodo de procesamien-
to se le asigna un número de identificación único, denominado rango. Todos los
nodos tienen una copia del mismo programa, pero cada proceso ejecuta distin-
tas sentencias del código según bifurcaciones introducidas que hacen referencia
al rango. Este modelo presenta particularidades adicionales según la rutina de
comunicación utilizada, pudiendo tener escenarios donde el transmisor y el re-
ceptor necesiten estar on-line para que un proceso espere respuesta del otro o,
por el contrario, es posible que el emisor envı́e la información a un buffer para su
entrega posterior, permitiendo que el emisor pueda seguir ejecutando código sin
preocuparse de si el receptor ha recibido o no los datos.
26
1.2. Estado del arte
27
Capı́tulo 1: Introducción
28
1.2. Estado del arte
ScaLAPACK [35, 184], con el apoyo de BLACS para las operaciones de comuni-
cación, ofreciendo un rendimiento optimizado en este tipo de plataformas. Esto
último se consigue básicamente al minimizar los movimientos de datos gracias a
la implementación de algoritmos que trabajan por bloques.
PBLAS
Direccionamiento global
Direccionamiento local
LAPACK BLACS
Primitivas de paso de
mensajes
BLAS (MPI, PVM, etc)
Dependiente de la plataforma
29
Capı́tulo 1: Introducción
30
1.2. Estado del arte
31
Capı́tulo 1: Introducción
Ansys ofrece el paquete Ansys HPC [16], High Performance Computing, que
incluye paralelismo tanto en su resolutor disperso directo como en el de ecua-
ciones iterativas, y Adams incorpora en su módulo de análisis estructural MSC
Nastran [215] técnicas de paralelización, tanto de memoria compartida como dis-
tribuida. Por contra, los algoritmos usados por SOLIDWORKS y por SolidEdge
no incorporan en este momento técnicas de paralelismo.
32
1.2. Estado del arte
Un análisis más exhaustivo del uso de diferentes librerı́as de álgebra lineal pa-
ra matrices densas y dispersas combinadas con paralelismo basado en OpenMP
se puede encontrar en [130]. Los autores prefieren OpenMP a MPI por ser me-
nos intrusivo a la hora de su aplicación a código propio desarrollado por otros
grupos de investigación. Experimentos aplicando un determinado tipo de formula-
ción dinámica a cuadriláteros escalables con tamaños de problema de 100 a 4000
variables y matrices con diferentes porcentajes de dispersión permiten concluir
que los speed-ups que se pueden conseguir dependen principalmente del tipo de
problema, de la formulación y de la librerı́a empleada.
33
Capı́tulo 1: Introducción
34
1.2. Estado del arte
1.2.7 Autooptimización
35
Capı́tulo 1: Introducción
1.3 Objetivos
36
1.3. Objetivos
37
Capı́tulo 1: Introducción
Estos aspectos deben ser tenidos en cuenta para el desarrollo del simulador.
Este software será un producto final que nos ayudará a realizar algunos de los
análisis planteados para los sistemas multicuerpo y a estudiar su posible extensión
a otros ámbitos de aplicación. Por este motivo constituirá una parte fundamental
del trabajo a desarrollar en esta tesis, y deberá incorporar las siguientes funcio-
nalidades:
38
1.4. Metodologı́a
1.4 Metodologı́a
39
Capı́tulo 1: Introducción
40
1.5. Contribuciones
1.5 Contribuciones
41
Capı́tulo 1: Introducción
42
Capı́tulo 2
Cinemática computacional de
sistemas multicuerpo
43
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
necesario crear un prototipo real una vez que las simulaciones han encontrado la
solución óptima. Todo ello lleva emparejado un enorme ahorro de costes de dise-
ño, producción, e incluso posventa. Igualmente ocurre a la hora de implementar
sistemas de control de mecanismos y máquinas. En estos casos se simulan modelos
que deben recibir señales de sensores externos y recalcular, en tiempo real, los
controles a ejercer sobre sus actuadores para corregir las mı́nimas desviaciones
que se hayan podido encontrar en el sistema real.
44
2.1. Modelado de sistemas multicuerpo
45
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
Par cinemático es un conjunto formado por dos eslabones de tal forma que
entre ellos exista la posibilidad de movimiento relativo.
Para describir este concepto se presenta el ejemplo ilustrado en la figura
2.1(a). Se trata de un mecanismo real en el que una biela (2) se encarga de
transmitir el movimiento de un pistón (1) que circula dentro de un cilindro
por lo que únicamente puede ser un desplazamiento longitudinal (L), a un
cigüeñal (3) cuyo movimiento es rotatorio (R). La figura 2.1(b) representa
una vista simplificada del mismo sistema, con objeto de facilitar su estudio.
En este mecanismo es posible identificar cuatro parejas de eslabones, como
muestra la figura 2.2(a): 0 - 1, 0 - 3, 1 - 2 y 2 - 3. Estos pares representan
las conexiones de miembros entre los que puede haber algún tipo de movi-
mientos relativo (figura 2.2(b)). Si tomamos como ejemplo el par 2 - 3 y
establecemos que el elemento 2 quede fijo, vemos que el único movimiento
posible es el de rotación alrededor suyo.
46
2.1. Modelado de sistemas multicuerpo
0
0
1 1
L C
C
2 2
3
A
B 3
A B
R 0
(a) Diseño del sistema. (b) Diagrama simplificado.
{0–1}
0
0
1
C {1–2}
1 1
2 2
{2–3} 2
3 3 3
A B
{0–3}
0
0 {0–3} {2–3} {1–2} {0–1}
(a) Proceso de selección de pares. (b) Detalle de los pares encontrados.
47
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
Por tanto, el hecho de estar unidos los dos eslabones limita el movimiento de
uno de ellos respecto al otro. Estas limitaciones se denominan condiciones de
enlaces, y su formulación analı́tica se conoce como ecuaciones de restricción.
Los pares se pueden clasificar atendiendo al grado del par. Se define el grado
de un par cinemático como el número de grados de libertad que permite el
par, es decir, el número de movimientos independientes que un eslabón tiene
respecto al otro. Como vimos en el ejemplo anterior del mecanismo biela-
cigüeñal, el procedimiento para identificar el grado de un par consiste en
separar los eslabones del resto del mecanismo y estudiar su movimiento
relativo fijando uno de ellos. El número de movimientos independientes
que tenga el eslabón móvil respecto al que se considera fijo establece el
grado k del par, siendo ek el número de grados de libertad que restringe
la unión entre los dos sólidos del par. Dado que ek 6= 0 se entiende que, en
mecanismos planos, los pares cinemáticos solo pueden ser de grado k = 1, 2
y en mecanismos espaciales, de grado k = 1, ..., 5. En la literatura se pueden
consultar tablas que muestran todos los tipos de pares cinemáticos que
forman los eslabones de mecanismos planos y espaciales [176].
Figura 2.3: Tipos de cadenas cinemáticas en función de la unión entre sus esla-
bones.
48
2.1. Modelado de sistemas multicuerpo
49
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
B−1
L = BNm − ∑ ek Pk (2.1)
k=1
k ek (2D) ek (3D)
1 2 5
2 1 4
3 - 3
4 - 2
5 - 1
Tabla 2.1: Grados de libertad que eliminan los pares cinemáticos que forman los
eslabones del sistema mecánico según su grado k.
Dado que las coordenadas dependientes son las más utilizadas en el modelado
de los sistemas multicuerpo, es de interés realizar una breve descripción de los
tres tipos que existen: relativas, de punto de referencia y naturales.
50
2.1. Modelado de sistemas multicuerpo
Las coordenadas relativas sitúan cada elemento del mecanismo con respecto
al anterior en la cadena cinemática. Las ecuaciones de restricción procederán de
las condiciones de cierre de los lazos que componen el mecanismo. En la figura 2.5
observamos un solo lazo.
s
C
B L2
α2 L3
L1
α1
A D
L4
Figura 2.5: Modelado empleando coordenadas relativas.
~ + BC
AB ~ + CD
~ + DA
~ = ~0
π
L1 cos α1 + s cos(α1 + α2 − π) + L3 cos(α1 + α2 + ) − L4 = 0
2
π
L1 sen α1 + s sen(α1 + α2 − π) − L3 cos(α1 + α2 + ) = 0
2
51
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
L1
(x1 − xA ) − cos α1 = 0
2
L1
(y1 − yA ) − sen α1 = 0
2
L1 L2
x1 + cos α1 − x2 − cos α2 = 0
2 2
L1 L2
y1 + sen α1 − y2 − sen α2 = 0
2 2
π
α3 − α2 + =0
2
L3
(x2 − x3 ) cos α3 + (y2 − y3 ) sen α3 − =0
2
L3
(x3 − xD ) − cos α3 = 0
2
L3
(y3 − yD ) − sen α3 = 0
2
52
2.1. Modelado de sistemas multicuerpo
C
B (x2,y2) α2
L2
α1 (x ,y ) α3
(x1,y1) 3 3
L1 L3
A D
Figura 2.6: Modelado empleando coordenadas de punto de referencia.
Al igual que las anteriores, las coordenadas naturales también sitúan cada
elemento con independencia de los demás. Es una evolución de las coordenadas
de punto de referencia, donde los puntos emigran a los pares, contribuyendo a
la definición simultánea de los dos elementos que se unen en el par. Por tanto
ya no son necesarias variables de tipo angular para definir la orientación de cada
elemento. Observamos este proceso de emigración en la figura 2.7.
(x2,y2)
L2
(x1,y1) (x3,y3)
L1 L3
53
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
Las tres primeras son condiciones de distancia constante entre puntos, para
asegurar el carácter rı́gido de las barras móviles:
(x1 − xA )2 + (y1 − yA )2 − L1 2 = 0
(x2 − x1 )2 + (y2 − y1 )2 − L2 2 = 0
(x3 − xD )2 + (y3 − yD )2 − L3 2 = 0
α3 α4
α5
α2
α7
α1
α6
Σ7
Σ0
Figura 2.8: Ejemplo de sistema multicuerpo en 3 dimensiones.
54
2.2. Análisis estructural de sistemas multicuerpo
GE-IV H
GE-III
H G I
F
7 6 E
8
3 C 5 C GE-II
B F GE-I B
G I
2 E
4
A D
A D
1 1
(a) Mecanismo articulado de 8 barras. (b) Descomposición del mecanismo en
tres grupos estructurales de cuatro tipos
diferentes.
55
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
Cada nodo del grafo representa un eslabón. Estos nodos se etiquetan con
un número que corresponde con el del eslabón.
Si dos eslabones forman par, se trazan entre ellos tantas lı́neas de trazo fino
como grado tenga el par.
56
2.2. Análisis estructural de sistemas multicuerpo
3
2 4
α32 α43
α41
1 α21 1
1 2
q
α41 α32
4 3
α43
Figura 2.11: Análisis de un cuadrilátero articulado: grafo estructural.
57
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
Sc − nc = B (P − Nm )
donde:
• 2D: Sc = 1 · P1 + 2 · P2
• 3D: Sc = 1 · P1 + 2 · P2 + 3 · P3 + 4 · P4 + 5 · P5
58
2.2. Análisis estructural de sistemas multicuerpo
q
1 2
4 3
59
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
0 1,1 2,0
60
2.3. Cinemática computacional de sistemas multicuerpo
Φ(q, t) = 0 (2.2)
Cada análisis de posición exige, fijados unos valores de las coordenadas inde-
pendientes, resolver el sistema no lineal de ecuaciones (ec. 2.2), para lo que se
puede recurrir al método iterativo de Newton-Raphson:
61
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
∂ F1 ∂ F1 ∂ F1
∂ qd1 ∂ qd2
··· ∂ qdm
∂ F2 ∂ F2 ∂ F2
∂ Φ(q,t) ∂ qd1 ∂ qd2
···
∂ qdm
= = (2.4)
Φqd d
∂q
··· ··· ··· ···
∂ Fr ∂ Fr ∂ Fr
∂ qd1 ∂ qd
··· ∂ qdm
2 r×m
m
Res = ∑ Φ j < tol (2.5)
j=1
Φq q̇ = 0 (2.6)
62
2.3. Cinemática computacional de sistemas multicuerpo
∂ F1 ∂ F1 ∂ Fn
∂ qi1 ∂ qi2
··· ∂ qik
∂ F2 ∂ F2
∂ Fn
∂ Φ(q,t) ∂ qi1 ∂ qi2
···
∂ qik
Φqi = = (2.8)
∂q i ···
··· ··· ···
∂ Fn ∂ Fn ∂ Fn
∂ qi1 ∂ qi
· · · ∂ qi
2 k n×k
Para poder resolver el sistema (ec. 2.7), la matriz Jacobiana Φqd debe ser
cuadrada. Para ello, el número de ecuaciones de restricción debe ser igual al de
variables dependientes: r = m. En caso de no ser ası́, existen r − m ecuaciones
redundantes y la solución se puede plantear con dos estrategias: una consiste en
identificar y eliminar las ecuaciones redundantes, y otra en utilizar una solución
basada en mı́nimos cuadrados [120].
63
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
Φq q̈ + Φ̇q q̇ = 0 (2.9)
que representa un sistema lineal de ecuaciones que permite determinar las acele-
raciones de las coordenadas dependientes buscadas.
64
2.3. Cinemática computacional de sistemas multicuerpo
12 end
13 % % II. Problema de velocidad %
14 CALL fJacob()
15 Extrae Φdq /* Jacobiana dependientes */
16 Extrae Φqi /* Jacobiana independientes */
17 solve: Φqd q̇d = −(Φqi q̇i + Φt )
18 % % III. Problema de aceleraciones %
19 CALL Fiqpqp() /* Evalúa Φ̇q q̇ */
20
d i
solve: Φqd q̈ = −(Φqi q̈ + Φ̇q q̇ + Φ̇t )
21 end
65
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
66
2.3. Cinemática computacional de sistemas multicuerpo
C
C B
3 B
B
SG II
SG I
2
4
θ1
θ1 A D
1 A D
(a) Cuadrilátero articulado con (b) División del cuadrilátero en grupos es-
grado de libertad controlado θ1 . tructurales SG-I y SG-II.
Figura 2.14: Mecanismo cuadrilátero articulado usado para mostrar las rutinas
de análisis cinemático basado en análisis de grupo.
" #
xB − AB cos θ1
Φ= = [0]2×1 (2.11)
yB − AB sin θ1
Para este grupo, la solución a las posiciones se obtiene por resolución directa
de (ec. 2.11) y la solución a velocidades y aceleraciones, por derivación temporal
directa de esas expresiones, como se muestra en (ec. 2.12) para la coordenada
dependiente xB :
67
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
2
" #
rTBC rBC − BC
Φ= 2 = [0]2×1 (2.13)
rTCD rCD − CD
rTBC es la traspuesta del vector rBC y se utiliza como notación compacta para
2
la restricción constante entre dos puntos del modelo: rTBC rBC − BC es lo mismo
que ((XC − XB)2 + (YC −Y B)2 − L2 = 0.
Las matrices necesarias para el análisis del grupo SG-II: Φqd , Φqi , Φ̇q q̇, son
fáciles de obtener y se pueden almacenar en una rutina especı́fica de solución
de este grupo. Los valores de las coordenadas dependientes se pueden calcular
aplicando el método iterativo de Newton-Raphson (ec. 2.3) y los problemas de
velocidades y aceleraciones se pueden formular de forma análoga al caso general
(ecs. 2.7 y 2.10), teniendo en cuenta que, en muchos casos, la inversa de la matriz
Jacobiana Φqd se puede obtener de forma analı́tica, lo que permite su reutilización
en la resolución de todos los sistemas de ecuaciones.
Una vez obtenida la información de los grupos estructurales en que está di-
vidido el sistema multicuerpo (la estructura cinemática), el programa principal
(algoritmo 2) se encarga de la rutina de análisis cinemático basado en ecuaciones
de grupo mediante la ejecución de dos bucles anidados. El primero es el bucle de
tiempos, en el que se incrementan los valores de los grados de libertad de todo
el sistema. Para cada instante de tiempo, el segundo bucle llama a cada uno de
los grupos estructurales que forman el sistema multicuerpo, en el orden definido
en la estructura cinemática, y dentro de este bucle se identifica a qué rutina de
solución debe llamar, dependiendo del tipo de grupo estructural que corresponda.
68
2.4. Conclusiones
1 for t = t0 : timeStep : t f do
2 q̈i (t); q̇i (q̈i , q̇i0 ); qi (q̈i , q̇i0 , qi0 ) /* Evalúa coord. indep. */
3 for ng = 2 : length(MGrupos) do
/* Resuelve todos los grupos estructurales */
4 switch MGroups(ng).kind do
5 case MGrupos(ng).kind == 1RSG do
6 CALL Solve_1RSG(*ARGS)
7 case MGrupos(ng).kind == 3RSG do
8 CALL Solve_3RSG(*ARGS)
9 case MGrupos(ng).kind == . . . do
10 CALL ...
11
12 end
13 end
14 end
1RSG y 3RSG son identificadores que se han dado a dos grupos estructurales
para llamar a las correspondientes rutinas de su análisis cinemático. La notación
es 1R o 3R dependiendo del número (1 o 3) de pares de rotación (R) del grupo
y ’SG’ se refiere a Structural Group. De este modo, 1RSG se refiere a un grupo
estructural con un par de rotación; por ejemplo una manivela con giro controlado
(SG I en la figura 2.14(b)) y 3RSG se refiere a un grupo estructural con tres pares
de rotación (SG II en la figura 2.14(b)).
2.4 Conclusiones
69
Capı́tulo 2: Cinemática computacional de sistemas multicuerpo
70
Capı́tulo 3
Herramientas computacionales
71
Capı́tulo 3: Herramientas computacionales
CPU
Core 1 Core 2
CPU ALU FPU CPU ALU FPU
L1 cache L1 cache
L2 cache
L1 cache L1 cache
MEMORY CONTROLLER
MAIN MEMORY
72
3.1. Herramientas hardware
Interconnection network
Processor 1 Processor 2
CPU ALU FPU CPU ALU FPU
Intercomms Intercomms
bridge bridge
Cache Cache
73
Capı́tulo 3: Herramientas computacionales
CPU CPU
Core 1 Core 2 Core 1 Core 2
CPU ALU FPU CPU ALU FPU CPU ALU FPU CPU ALU FPU
L2 cache L2 cache
CPU ALU FPU CPU ALU FPU CPU ALU FPU CPU ALU FPU
Core 3 Core 4 Core 3 Core 4
MEMORY CONTROLLERS
MAIN MEMORY
74
3.1. Herramientas hardware
SM SM SM
Register Register Register
SP SP SP SP SP SP
SP SP SP SP SP SP
...
SP SP SP SP SP SP
SP SP SP SP SP SP
Constant Cache
Texture Cache
Device memory
75
Capı́tulo 3: Herramientas computacionales
Host
Grid
Block Block Block
(0,0) (0,1) (0,2)
Kernel1
Block Block Block
(1,0) (1,1) (1,2)
76
3.1. Herramientas hardware
77
Capı́tulo 3: Herramientas computacionales
78
Nodo Marte Mercurio Saturno Jupiter Venus
CPU
Phenom II Phenom II Xeon Xeon Xeon
Procesadores
X6 1075T X6 1075T E7530 E5-2620 E5-2620
Fabricante/Arquitect. AMD/x86-64 AMD/x86-64 Intel/x86-64 Intel/x86-64 Intel/x86-64
Reloj 800 MHz 800 MHz 1.87 GHz 2.00 GHz 2.40 GHz
Cores por CPU 6 6 6 6 6
CPU por nodo 1 1 4 2 2
Cores fı́sicos/lógicos 6/6 6/6 24 / 48 12 / 24 12 /12
Memoria RAM 16 GB 16 GB 32 GB 32 GB 64 GB
Cache L1 64 KB 64 KB 32 KB 32 KB 32 KB
Cache L2 512 KB 512 KB 256 KB 256 KB 256 KB
Cache L3 6 MB 6 MB 12 MB 15 MB 15 MB
GPU
79
GeForce GeForce GeForce GeForce
Procesador NVIDIA Tesla K20c Tesla C2075
GTX 480 GTX 480 GTX 590 GT 640
Arquitectura Fermi Fermi Kepler Fermi Fermi Kepler
GPU por nodo 1 1 1 2 4 1
Reloj 1401 MHz 1401 MHz 706 MHz 574 MHz 608 MHz 902 MHz
Memoria 1536 MB 1536 MB 4800 MB 5375 MB 1536 MB 1024 MB
Streaming MultiProcs. 15 15 13 14 16 2
Streaming Processors 32 32 192 32 32 192
CUDA cores 480 480 2496 448 512 384
Xeon Phi
Modelo/Memoria RAM 3120A/6 GB
Unidades por Nodo 2
Cores fı́sicos/lógicos 57 / 114
3.1. Herramientas hardware
3.2.1 Compiladores
Una parte importante del trabajo realizado en esta tesis ha sido la construc-
ción de un simulador el cual, partiendo de un problema representado en forma de
grafo, identifica los parámetros algorı́tmicos óptimos que minimizan los tiempos
de ejecución aplicados a la resolución del problema, proponiendo ejecuciones pa-
ralelas cuando se identifican cálculos independientes, y seleccionando la librerı́a
de álgebra lineal que ofrece mejor rendimiento de acuerdo a las dimensiones del
problema.
JAVA [235]: Hemos seleccionado este lenguaje para el desarrollo del inter-
faz gráfico del simulador. El motivo ha sido la disponibilidad de librerı́as
que implementan funcionalidades esenciales, tales como la edición de grafos
(necesario para representar tanto el algoritmo a resolver como el árbol de
soluciones), y las herramientas de representación gráfica y tabular para el
análisis de los resultados obtenidos. Otro factor que nos ha hecho decidir-
nos por este lenguaje ha sido la portabilidad a diversos sistemas operativos,
habiéndose probado con éxito tanto en entornos Windows [208] como Li-
nux [185]. Para el desarrollo se ha usado el JDK (Java Development Kit)
en su versión 8.
80
3.2. Herramientas software
81
Capı́tulo 3: Herramientas computacionales
MKL [150] (Math Kernel Library) es una librerı́a desarrollada por Intel
c y
está optimizada para su familia de microprocesadores. Incorpora rutinas
BLAS [37], tanto para tipos de datos complejos como reales de simple y
doble precisión. Incorpora también funciones de LAPACK [38], como son
las factorizaciones LU, Cholesky y QR, usadas para la resolución de sistemas
de ecuaciones. MKL permite paralelismo implı́cito, siendo posible indicar
en tiempo de ejecución el número de threads a utilizar, o dejar a la propia
librerı́a esta elección.
82
3.2. Herramientas software
83
Capı́tulo 3: Herramientas computacionales
0 6 0 0 1
Los arrays almacenarán los siguientes valores:
A = 2 3 4 6 1 5 1
IRN = 0 0 1 1 2 2 4
ICN = 0 1 2 4 2 3 4
84
3.2. Herramientas software
85
Capı́tulo 3: Herramientas computacionales
0 1 0 0 2
PT R = 0 2 5 7 8 9
ROW = 0 1 1 2 4 2 3 3 4
VAL = −3 1 4 1 1 3 2 4 2
86
3.3. Conclusiones
3.3 Conclusiones
Por otro lado, son igualmente relevantes las librerı́as de cómputo cientı́fico,
en especial las librerı́as de álgebra lineal necesarias para resolver los problemas
de análisis cinemático de sistemas multicuerpo tratados en este trabajo. Hemos
presentado alguna de estas librerı́as, las cuales están incorporadas en el simula-
dor. Esto nos permite usarlas y estudiar los rendimientos que ofrecen al operar
87
Capı́tulo 3: Herramientas computacionales
sobre diferentes tipos y tamaños de matrices. Esta información será utilizada pos-
teriormente a la hora de proponer el uso de una u otra librerı́a en la resolución de
determinados problemas que incorporen en sus algoritmos operaciones de álgebra
lineal, bien en áreas de la ingenierı́a mecánica, o en otras disciplinas cientı́ficas.
El proceso de autooptimización también hará uso de esta información para se-
leccionar, en cada etapa de resolución de un problema, la mejor librerı́a y los
parámetros de paralelismo, combinación que vendrá determinada por el hardwa-
re disponible y por el número y tipo de cálculos que se puedan realizar de manera
simultánea.
88
Capı́tulo 4
Optimización y Autooptimización
89
Capı́tulo 4: Optimización y Autooptimización
90
4.2. Optimización de software cientı́fico
91
Capı́tulo 4: Optimización y Autooptimización
92
4.2. Optimización de software cientı́fico
4.2.3 Optimización
93
Capı́tulo 4: Optimización y Autooptimización
94
4.2. Optimización de software cientı́fico
En [58] los autores emplean una serie de ejecuciones cortas para evaluar los
aspectos de la aplicación que se ven influenciados por la elección de los parámetros
de entrada. Los autores utilizan su algoritmo de búsqueda (una modificación de
la búsqueda Nelder-Mead [221]) para navegar por el espacio de parámetros de en-
trada. De esta manera evitan el costoso proceso de realizar ejecuciones completas
de la aplicación en la búsqueda del ajuste de los parámetros.
Con carácter general, las decisiones de optimización tomadas por los compi-
ladores tienden a ser de propósito general y conservadoras. Por lo tanto, para dar
a los programadores más flexibilidad a la hora de tomar decisiones que afectan a
la optimización de códigos complejos, se han propuesto una variedad de marcos
de autooptimización que facilitan la exploración de un gran espacio de posibles
opciones del compilador y sus valores. Existen también herramientas de autoop-
timización que centran su esfuerzo en la fase de compilación del software, gene-
ralmente mediante la gestión de un conjunto de implementaciones alternativas de
un determinado cálculo en base al estudio del hardware subyacente [55, 126].
95
Capı́tulo 4: Optimización y Autooptimización
96
4.2. Optimización de software cientı́fico
97
Capı́tulo 4: Optimización y Autooptimización
98
4.2. Optimización de software cientı́fico
99
Capı́tulo 4: Optimización y Autooptimización
100
4.2. Optimización de software cientı́fico
Desde el año 1983, en que se creó la primera versión de CCSM, este software
ha venido siendo objeto de constante evolución tendente a mejorar su rendimien-
to, con un enfoque especial en la comunicación entre procesos, equilibrio de cargas
y algoritmos paralelos. La concurrencia de los componentes de CCSM no es per-
fecta, ya que hay dependencias temporales entre algunos de ellos, lo que limita
la fracción de tiempo en el que sus componentes se pueden ejecutar simultánea-
mente. Por ejemplo, el modelo de atmósfera, tierra y hielo marino se pueden
ejecutar en un conjunto común de procesadores, mientras que el modelo oceánico
se ejecuta simultáneamente en un conjunto separado de procesadores.
101
Capı́tulo 4: Optimización y Autooptimización
Con la versión CCSM4 [219], publicada en mayo de 2010, todos los componen-
tes implementan códigos paralelos hı́bridos, que usan MPI para definir y coordinar
el paralelismo de memoria distribuida, y OpenMP para el paralelismo de memo-
ria compartida. Cada modelo de componente tiene sus propias caracterı́sticas de
rendimiento, y la integración entre ellos se suma a la complejidad a la hora de
caracterizar el rendimiento [96]. El autor de este análisis resalta las técnicas que
se han empleado con buenos resultados en la mejora de rendimientos del modelo
CCSM [302]:
102
4.3. Optimización de códigos de simulación de sistemas multicuerpo
Por tanto, una optimización de este tipo de códigos puede enfocarse en varias
áreas:
103
Capı́tulo 4: Optimización y Autooptimización
En el caso del simulador desarrollado junto a esta tesis, los parámetros algorı́t-
micos considerados contemplan el número de threads del primer nivel (paralelismo
explı́cito OpenMP), los threads del segundo nivel (aplicables al paralelismo in-
terno de las rutinas de las librerı́as), la cantidad de GPUs y el identificador de
la librerı́a. Todos ellos son de naturaleza discreta, por lo que se pueden repre-
sentar mediante números enteros especificados individualmente o como un rango
definido entre un valor mı́nimo y un valor máximo.
104
4.3. Optimización de códigos de simulación de sistemas multicuerpo
105
Capı́tulo 4: Optimización y Autooptimización
4.4 Conclusiones
En este capı́tulo se han descrito los conceptos más importantes que se aplican
en el área de la optimización de aplicaciones cientı́ficas, y se han presentado
los recientes avances en herramientas y metodologı́as disponibles en este campo.
Además, se ha mostrado la aplicación de alguna de estas técnicas al campo de
la optimización de librerı́as de álgebra matricial y a aplicaciones cientı́ficas más
generales y de alto coste computacional, como es el caso de un modelo climático
global.
106
Capı́tulo 5
Simulador
107
Capı́tulo 5: Simulador
5.1 Motivación
2
4
1
5
3
108
5.2. Conceptos básicos
El simulador aquı́ presentado tiene como objetivo facilitar dicha tarea de bús-
queda, ofreciendo un interfaz gráfico que permite guiar a un usuario no experto en
paralelismo en la selección de la mejor implementación de su código, y conseguir
de ese modo el aprovechamiento óptimo de una plataforma hardware concreta.
109
Capı́tulo 5: Simulador
5.2.1 Funciones
110
5.2. Conceptos básicos
La tabla 5.1 muestra las librerı́as incorporadas en la versión actual del simu-
lador. Junto a ellas se relacionan las funciones y el tipo de matrices que manejan.
Cada librerı́a se identifica de manera única mediante un identificador, Id. El Id
‘0’ corresponde a las funciones implementadas en PARCSIM. El resto son librerı́as
de terceros cuyos detalles se pueden consultar en la sección 3.2.2.
111
Capı́tulo 5: Simulador
functionParameters =
(
{Name=”inMatrixA ”; D i r e c t i o n =”i ”; Type=”Mf ”; } ,
{Name=”inMatrixB ”; D i r e c t i o n =”i ”; Type=”Mf ”; } ,
{Name=”outMatrixC ”; D i r e c t i o n =”o ”; Type=”Mf ”; }
);
parametersValidations =
(
{
c o n d i t i o n =”R1=R2 ”;
e r r o r t e x t =”The m a t r i c e s must have t h e same number o f rows ”;
},
{
c o n d i t i o n =”R2=R3 ”;
e r r o r t e x t =”The m a t r i c e s must have t h e same number o f rows ”;
},
{
c o n d i t i o n =”C1=C2 ”;
e r r o r t e x t =”The m a t r i c e s must have t h e same number o f columns ”;
},
{
c o n d i t i o n =”C2=C3 ”;
e r r o r t e x t =”The m a t r i c e s must have t h e same number o f columns ”;
}
);
functionPackages =
(
{ packageName=”PARCSIM ”;
p a c k a g e I d =0;
p a c k a g e F u n c t i o n I d =3010;
packageMultiThread =0;
packageMatrixFormat =1;}
);
}
...
112
5.2. Conceptos básicos
Id Función
1 DGETRF
2 DGETRS
3 SOLVESYS
4 MATMUL
5 MATADD
6 MATSUB
7 MATCHG
8 MATTRN
9 NORMA
10 RESHAP
113
Capı́tulo 5: Simulador
114
5.2. Conceptos básicos
Para ilustrar la relación que existe entre las funciones y las librerı́as en el fiche-
ro functions.fun podemos fijarnos en la suma de matrices MATADD. Actual-
mente esta función está implementada únicamente en el simulador, por lo que en
la sección functionPackages del listado 5.1 solo hay una entrada, la referida
al propio simulador. Por el contrario, la función SOLVESYS tiene implementa-
ciones en todas las librerı́as, motivo por el que la sección functionPackages
muestra varias entradas, como queda reflejado en el listado 5.2.
115
Capı́tulo 5: Simulador
Como ejemplo, la figura 5.2(a) muestra la rutina simple R1 con un diseño que
contiene tres funciones: f1 , f2 y f3 que se ejecutan en secuencia. Sin embargo, si
observamos la figura 5.2(b), la rutina anidada R2 se compone de tres funciones
y una referencia a la rutina R1 : f1 , R1 , f2 y f4 . La ejecución de R2 comienza
desglosando la rutina R1 en sus funciones componentes e insertándolas en el lugar
que ocupa R1 dentro de R2 .
R1
f 1( … )
f 1( … )
f 1( … ) R2
f 2( … ) f 2( … ) f 1( … )
f1 ( … )
f 3( … ) R1 f 2( … )
f 3( … )
f2 ( … )
f 4( … ) f 3( … )
f 2( … )
f 4( … )
Figura 5.2: Ejemplo de dos rutinas de usuario que ilustran el concepto de rutina
simple (compuesta únicamente por funciones) y rutina anidada (compuesta por
funciones y por otras rutinas). En tiempo de ejecución la rutina anidada aporta
a la secuencia de cálculos las funciones que la forman.
116
5.2. Conceptos básicos
117
Capı́tulo 5: Simulador
118
5.2. Conceptos básicos
R RADDMUL R RSYSADDMUL
f SOLVESYS f 3( … )
R
f MATADD f 5( … )
f MATADD f 5( … )
RADDMUL
f MATMUL f 4( … )
f MATMUL f 4( … )
(a) Rutina compuesta por una su- (b) Rutina RSYSADDMUL com-
ma y una multiplicación de ma- puesta por una función de resolu-
trices. El nombre RADDMUL es ción de sistemas de ecuaciones y
un acrónimo que hace referen- por una rutina que incluye una su-
cia a R-utina, ADD-ition y MUL- ma y una multiplicación de matri-
tiplication. ces.
Figura 5.3: Rutinas de ejemplo usadas para ilustrar el modo en el que se repre-
sentan en el fichero routines.rou.
119
Capı́tulo 5: Simulador
5.2.3 Modelos
120
5.2. Conceptos básicos
Gr1
f5( … ) Gr3
f4( … ) f 5( … )
Start
Gr2 Gr5
f3( … ) f6( … ) End
Gr4
f4( … )
Figura 5.4: Modelo de ejemplo formado por siete grupos. En cada grupo se mues-
tran las instrucciones o funciones, ya desglosadas, a partir de las rutinas que
definen la solución del subsistema o grupo al que representan. Las lı́neas dirigidas
indican las dependencias entre los grupos.
5.2.4 Grupos
121
Capı́tulo 5: Simulador
122
5.2. Conceptos básicos
123
Capı́tulo 5: Simulador
5.2.5 Parámetros
f MATMUL f4 ( … )
functionId: 4 functionName: MATMUL
functionParameters
4 5 6
Name inMatrixA inMatrixB outMatrixC
Direction (i) nput (i) nput (o) utput
Type float float float
124
5.2. Conceptos básicos
En la figura vemos una representación del grupo Gr1 que forma parte del
modelo que se describió en la figura 5.4. Dicho grupo ejecuta la rutina RADDMUL
compuesta por una función suma MATADD y una función multiplicación MATMUL.
Cada una de estas funciones requiere dos parámetros de entrada y uno de salida.
Como consecuencia, el usuario debe asignar a RADDMUL, o bien seis parámetros a
Gr1 , o bien modificar la definición de la rutina para establecer una relación entre
los parámetros de entrada de una función y el parámetro de salida de alguna otra,
permitiendo de esta manera la comunicación de información entre funciones. Este
método se describe en la sección A.8.26.1 del anexo.
5.2.6 Escenarios
valor descripción
0 matriz no simétrica
1 matriz banda (con valores no nulos cercanos a la diagonal)
2 matriz simétrica con valores no nulos distribuidos aleatoriamente
125
Capı́tulo 5: Simulador
Listado 5.6 Extracto del fichero que describe uno de los escenarios que
se emplearán para simular el modelo de la figura 5.4. Se muestra
información de las dos variables que corresponden a las matrices con
identificadores 1 y 2.
...
,
s c e n a r i o L i s t =(
{
scenarioName =”E s c e n a r i o 2 0 ”;
scenarioModelName =”ModeloEjemplo ”;
s c e n a r i o M o d e l I d =4;
s c e n a r i o M a t r i c e s L i s t =(
{
s c e n a r i o M a t r i x I d =1;
s c e n a r i o M a t r i x R o w s =20;
s c e n a r i o M a t r i x C o l s =20;
s c e n a r i o M a t r i x T y p e =1;
s c e n a r i o M a t r i x S p a r s i t y =10;
scenarioCreateRandom =1;
m a t r i x F i l e L o c a t i o n = ””;
s c e n a r i o r e u s e I f E x i s t =0;
},
{
s c e n a r i o M a t r i x I d =2;
s c e n a r i o M a t r i x R o w s =20;
s c e n a r i o M a t r i x C o l s =20;
s c e n a r i o M a t r i x T y p e =1;
s c e n a r i o M a t r i x S p a r s i t y =10;
scenarioCreateRandom =1;
m a t r i x F i l e L o c a t i o n = ””;
s c e n a r i o r e u s e I f E x i s t =0;
}
,
...
126
5.2. Conceptos básicos
127
Capı́tulo 5: Simulador
5.2.7 Scripts
128
5.2. Conceptos básicos
129
Capı́tulo 5: Simulador
5.2.8 Resumen
...
1
SCRIPTS
4
2
Ejecución
2
1
ESCENARIOS
1
20%
15%
5%
10x10
10x15
10x15
...
V1
V2
Vv
VARIABLES
Vv
Gr4
f2( p1, …, pnf2 )
Gr7
R2
Diseño
R2
Rr
Gr6
Gr5
R3
fn( p1, …, pnfn )
f1( p1, …, pnf1 )
R1
Gr4
RUTINAS
Gr2
Gr3
FUNCIONES
MODELO
Gr1
130
5.3. Rutas
5.3 Rutas
Gr1
Gr3
Start Gr2
Gr5 End
Gr4
131
Capı́tulo 5: Simulador
e1 e2 e3 e4 e5 e6
Gr2
Gr4
132
5.3. Rutas
Start
Gr1
Gr2
Gr1
Gr2
Gr4
Gr1
Gr4
Gr1
Gr2
Gr2
Gr2
Gr4
Gr3
Gr3
Gr4
Gr3
Gr4
Gr4 Gr3
Gr3 Gr5
Gr3 Gr5
Gr3 Gr5
Gr5 Gr5
Gr5
Gr5
1 2 3 4 5 6 7
Figura 5.10: Árbol que muestra las secuencias de cálculo válidas para el problema
de la figura 5.7. Cada rama es una ruta que representa un modo de ordenar los
cálculos capaz de resolver el sistema en su totalidad. Los nodos del árbol que
contienen más de un grupo suponen la resolución simultánea de dichos grupos.
Una vez creado el árbol de rutas, su estructura se recoge en una nueva sección,
branches, en el mismo fichero que almacena los grupos descritos en 5.2.4. El
listado 5.8 muestra la estructura de dicha sección.
133
Capı́tulo 5: Simulador
Start
Gr4
Gr1
Gr2
1 - 4 - 2+3 - 5 - 6 -7
Grupo2
Grupo4
Grupo2
6
Gr3
Start
Gr4
End
Gr1
Gr2
Gr3
Gr5
+
Gr5
5 6 7
134
5.4. Base de datos
Scenario: Contiene los campos que describen el escenario (el tamaño, tipo
y dispersión de las matrices).
135
Capı́tulo 5: Simulador
Heading
Model
Scenario
id (unique identifier) modelname CHAR(50) scenarioname CHAR(50)
executionmode INTEGER branchid INTEGER matrixtype INTEGER
hardware TEXT branchpad TEXT matrixsparsity INTEGER
start CHAR(19) matrixrows INTEGER
end CHAR(19) matrixcols INTEGER
Level of information
Execution time
Algoritmic parameters
Tabla 5.4: Regla para determinar mediante los campos modelId, groupId y
functionId en la base de datos PARCSIM.db el nivel (modelo, grupo o función)
en el que se ha medido el tiempo de ejecución almacenado en un registro.
136
5.5. Árbol de rutas
137
Capı́tulo 5: Simulador
4t
t1 t2 t3 t4 t5 t6
1 thread Gr1
1 thread Gr2
1 thread Gr3
Figura 5.13: Resolución simultánea de tres grupos con diferente carga computacio-
nal asignando un thread a cada grupo. El tiempo total de ejecución corresponde
al retraso provocado por el grupo Gr3 , de cuatro unidades de tiempo.
3t
t1 t2 t3 t4 t5 t6
2 threads
Gr1
1 thread Gr2
3 threads Gr3
138
5.5. Árbol de rutas
1. Cada rama está compuesta por una serie de nodos ordenados, donde cada
uno representa la resolución de uno o más grupos. El orden en el que se
resuelven los grupos debe ser tal que se respete el orden de precedencia que
refleja el grafo del sistema a resolver.
2. El árbol contiene solo una rama por cada agrupación de rutinas y tamaño
de matrices. Ilustraremos esta propiedad mediante el modelo representado
en la figura 5.15 que contiene tres grupos que ejecutan sumas de matrices.
Figura 5.15: Modelo con cinco grupos, donde Gr1 , Gr2 y Gr3 contienen la misma
rutina para resolver una suma de matrices.
139
Capı́tulo 5: Simulador
Start
Gr1
Gr2
Gr3
Parámetros Tamaños
Gr1
Gr3
Gr1
Gr2
Gr1 A1, A2, A3 100x100 Gr2
Gr2
Gr3
Gr2 B1, B2, B3 200x200
Gr3 C1, C2, C3 300x300 Gr3
1 2 3 4 5
Figura 5.16: Árbol de rutas que permiten resolver el modelo de la figura 5.15
cuando los grupos Gr1 , Gr2 y Gr3 operan sobre matrices de diferentes tamaños,
de 100 × 100, 200 × 200 y 300 × 300.
Start
Parámetros Tamaños
Gr1
Gr3
Gr1
Gr2
Gr2
Gr1 A1, A2, A3 100x100
Gr2
Gr3
1 2 3 4 5
Figura 5.17: Árbol de rutas que permiten resolver el modelo de la figura 5.15 en
un escenario en el que los grupos Gr1 y Gr3 operan sobre matrices de tamaños
100 × 100, mientras que el Gr2 lo hace sobre matrices 200 × 200. La rama 4 puede
eliminarse, pues es equivalente a la rama 2.
140
5.5. Árbol de rutas
Start
Gr1
Gr2
Gr3
Parámetros Tamaños Gr1
Gr3
Gr1
Gr2
Gr1 A1, A2, A3 100x100 Gr2
Gr2
Gr3
1 2 3 4 5
Figura 5.18: Árbol de rutas que permiten resolver el modelo de la figura 5.15
en un escenario en el que los grupos Gr1 , Gr2 y Gr3 operan sobre matrices de
tamaños 100 × 100. Las ramas 3 y 4 pueden eliminarse por ser equivalentes a la
rama 2.
141
Capı́tulo 5: Simulador
142
5.5. Árbol de rutas
Paso 1: Se crea el nodo raı́z para contener al grupo Start, que es el inicial
en el modelo (lı́nea 3 del algoritmo 3).
Paso 2: Se selecciona un nodo sin hijos (lı́nea 8), que en esta etapa inicial
solo puede ser el nodo raı́z. Buscamos los nodos que se han calculado en la
misma rama donde se encuentra el nodo seleccionado (lı́nea 9) y se buscan
los grupos no resueltos en dichos nodos (lı́nea 10). En esta primera iteración,
dado que solo se ha calculado el grupo Start, quedarı́an por resolver todos
los demás : Gr1 , Gr2 , Gr3 , Gr4 , Gr5 y End, en total seis grupos. Esta lista
se asigna inicialmente a remainingGroups[ ].
En la lı́nea 11 se ejecuta el algoritmo 4, encargado de eliminar de entre esos
seis grupos a aquéllos que tienen una dependencia de otros aún no calculados
en esta misma rama. Para ello, se recorre remainingGroups[ ] (lı́nea 3) y, para
cada grupo, se almacena en precedents[ ] la lista de sus precedentes según lo
reflejen las dependencias del modelo MODEL (lı́nea 4). Todos los elementos
de dicha lista deben estar en algún nodo de la rama que se está analizando.
En caso contrario, se descarta como candidato a formar parte de un nuevo
nodo en esta etapa y se elimina de remainingGroups[ ] (lı́nea 6). Esto ocurre
en el ejemplo de la figura 5.7 con los grupos Gr3 , Gr5 y End, por lo que la
lista inicial de seis grupos queda reducida a la formada por Gr1 , Gr2 y Gr4 .
143
Capı́tulo 5: Simulador
144
5.5. Árbol de rutas
En este paso 2 algunos nodos válidos serı́an los que contienen las siguientes
combinaciones de grupos [{Gr1 },{Gr2 },{Gr4 }; {Gr1 , Gr2 }; {Gr1 , Gr2 , Gr4 }],
como muestra la figura 5.19.
Start
Gr1
Gr2
Gr4
Figura 5.19: Búsqueda de nodos hijo para el nodo raı́z que contiene al grupo
Start. La zona sombreada muestra algunos de los nodos añadidos al árbol. En esta
figura los nodos que contienen a Gr3 y a Gr5 son ejemplos de algunos nodos que
se descartan por no considerarse válidos (necesitan que otros grupos se resuelvan
antes que ellos).
145
Capı́tulo 5: Simulador
Paso 3: Se recorre al árbol para buscar un nuevo nodo sin hijos (lı́nea 8
del algoritmo 3). En el ejemplo, se selecciona el que contiene al {Gr1 }, y se
procede igual que en el paso 2. Los grupos que quedan por resolver serán
(lı́nea 10 del algoritmo 3): Gr2 , Gr3 , Gr4 , Gr5 y End. En la figura 5.20 ob-
servamos que, entre otros, los nodos formados por el grupo {Gr2 } y por el
par {Gr2 , Gr4 } se consideran válidos y se añaden como dos nuevos nodos.
Sin embargo, los que contienen a {Gr3 } y {Gr5 } se descartan porque de-
penden de grupos no calculados. Por ejemplo, Gr3 necesita que Gr1 y Gr2
se hayan calculado con anterioridad, pero en la rama en la que se encuentra
el algoritmo en este momento están el nodo raı́z (con el grupo {Start}) y el
nodo que contiene a {Gr1 }, pero ninguno con el grupo Gr2 , lo que significa
que aún no se ha resuelto. Lo mismo ocurre con el Gr5 , que depende de Gr3
y de Gr4 , ninguno de los cuales se encuentran en esta rama.
Start
... ...
Gr1
Gr2
Gr1
Gr2
Gr2 Gr4
Gr3 Gr5
Gr2
Gr4
Figura 5.20: Búsqueda de nodos hijo para el nodo que contiene al grupo Gr1 . Se
descartan nodos que no cumplen con las precedencias del grafo del modelo.
Paso 4: El siguiente nodo sin hijos es el que contiene al grupo Gr2 , como
refleja la figura 5.21. Procedemos de nuevo como en el paso 2.
Start
Gr1
...
Gr2
Gr4
Gr1
Gr2
Gr4
Gr2
Gr1
Gr2
Gr2 Gr4
Figura 5.21: Búsqueda de nodos hijo para el nodo que contiene al grupo Gr2 . El
nodo que contiene al Gr5 no es válido pues dicho grupo necesita que se hayan
resuelto antes Gr3 y Gr4 en esta rama.
146
5.5. Árbol de rutas
Este proceso se repite hasta que todos los nodos tengan descendientes, ex-
cepto el nodo End, que marca el fin del algoritmo y que por tanto estará
como último nodo en todas las ramas. El árbol obtenido, y que cumple con
las propiedades descritas en la sección 5.5.1, se mostró en la figura 5.10.
Como vimos en 5.2.2, las funciones que forman parte de una rutina se ejecutan
de manera secuencial, por lo que el tiempo de resolución de un grupo i que contiene
k funciones, será la suma del tiempo de ejecución de todas las funciones fik , por
tanto T (Gri ) = ∑kj=1 T ( fi j ). Por otro lado, por el método descrito en 5.5.2 para
construir el árbol de rutas, los n grupos contenidos en un nodo se ejecutarán en
paralelo, por lo que el tiempo necesario para realizar los cálculos de un nodo N
será igual al mayor de los tiempos necesarios para resolver los grupos que contiene,
es decir, T (N) = máx T (Gri ) .
Gri ∈N
Con todo ello, el tiempo total necesario para resolver el problema siguiendo
una determinada ruta R formada por x nodos será la suma de tiempos consumidos
en los nodos que la forman:
147
Capı́tulo 5: Simulador
N1 N2 N3 N4
Gr3
f31( … )
El nodo N2 contiene los grupos {Gr2 , Gr3 }, que ejecutan rutinas que incluyen
las funciones { f21 , f22 } y { f31 } respectivamente.
148
5.5. Árbol de rutas
niveles(R) niveles(R)
T (R, AP, SCN) = ∑ T (Ni , AP, SCN) = ∑ máx T (Gr j , AP, SCN)
i=1 i=1 Gr j ∈Ni
niveles(R) f unciones(Gr j )
T (R, AP, SCN) = ∑ máx ∑ T ( f jk , AP, SCN) (5.2)
i=1 Gr j ∈Ni k=1
149
Capı́tulo 5: Simulador
ng ≤ th.omp1 (5.4)
150
5.5. Árbol de rutas
Una vez obtenido el coste, y con objeto de no repetir los cálculos, la función
COPY COSTS (lı́nea 12) busca a lo largo del árbol otros nodos que contengan
grupos con la misma rutina y el mismo tipo de datos (mismo tamaño y tipo de
las matrices). En este caso, el tiempo necesario para resolver ambos nodos se
considera que es el mismo y se copia el coste obtenido a todos ellos.
151
Capı́tulo 5: Simulador
152
5.5. Árbol de rutas
Gr1
f5( … ) Gr3
f4( … ) f 5( … )
Start
Gr2 Gr5
f3( … ) f6( … ) End
Gr4
f4( … )
Figura 5.23: Modelo formado por siete grupos con las funciones ya desglosadas a
partir de las rutinas que definen la solución de cada grupo.
153
Capı́tulo 5: Simulador
Start
Gr3
f5( … )
Gr5
f 6( … )
End
th.omp1 = 1, th.omp2 = 1, ng = 0 y l = 1
En este supuesto el número de grupos que contiene el nodo (tres) es mayor que
el número de threads reservados para el paralelismo de grupos (uno). Por tanto,
según la lı́nea 4 del algoritmo 7, se asigna un coste ∞ al nodo, lo que hace que
dicha ruta se descarte como válida para este juego de AP, independientemente
del escenario SCN.
th.omp1 = 3, th.omp2 = 2, ng = 1 y l = 1
Como esta vez th.omp1 = 3, es posible calcular en paralelo los tres grupos, y
la lı́nea 9 del algoritmo 7 recorre todas las combinaciones que utilizan un máximo
154
5.5. Árbol de rutas
de ng = 1 GPUs, obteniendo el coste del nodo asociado a cada una de ellas. Las
combinaciones posibles son {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)}. Los tres valores en
cada combinación indican la cantidad de GPUs asignadas a cada uno de los tres
grupos. Ahora bien, la librerı́a que corresponde con l = 1, según la tabla 5.1, es
MKL. Esta librerı́a no admite el uso de GPUs, por lo que la única combinación
válida es (0, 0, 0), y la función GET NODE COST llamada en la lı́nea 10 se
va a ejecutar solo una vez para obtener el tiempo de ejecución de las funciones
cuando se asignan los parámetros th.omp2 = 2, ng = 0 y l = 1 y se manejan las
matrices definidas en el escenario SCN.
T (Gr1 , AP, SCN) = T ( f5 , AP, SCN) + T ( f4 , AP, SCN) = 0.2 + 0.7 = 0.9;
T (Gr2 , AP, SCN) = T ( f3 , AP, SCN) = 0.5;
T (Gr4 , AP, SCN) = T ( f4 , AP, SCN) = 0.7;
T (N, AP, SCN) = máx{0.9, 0.5, 0.7} = 0.9
155
Capı́tulo 5: Simulador
156
5.5. Árbol de rutas
AP SCN Cost
function th.omp2 gpu size sparsity type execution time in seconds
f3 2 0 100 × 100 50 2 0.5
f4 2 0 100 × 100 50 2 0.7
f5 2 0 100 × 100 50 2 0.2
AP SCN Cost
function th.omp2 gpu size sparsity type execution time in seconds
f3 2 0 50 × 50 50 2 0.3
f4 2 0 50 × 50 50 2 0.5
f5 2 0 50 × 50 50 2 0.1
f3 2 0 200 × 200 50 2 1.5
f4 2 0 200 × 200 50 2 2.0
f5 2 0 200 × 200 50 2 0.5
50 − 100 2
d(SCN, SCN50×50 ) = = 0.25;
100
200 − 100 2
d(SCN, SCN200×200 ) = = 1;
100
157
Capı́tulo 5: Simulador
Por este criterio, el escenario más próximo a 100 × 100 es 50 × 50, con una dis-
tancia de 0.25. El coste (tiempo de ejecución estimado) del nodo para SCN nearest
será:
158
5.5. Árbol de rutas
159
Capı́tulo 5: Simulador
En el caso de que las rutinas que se ejecutan en cada grupo sean diferentes,
no existe a priori un reparto de recursos óptimo, en cuyo caso la función
GET ROUTINE BEST PARAMETERS buscará los mejores, pudien-
do darse el caso de que encuentre unos AP cuya suma exceda el lı́mite del
número de cores y GPUs que impone el hardware (lı́nea 21 del algoritmo 9).
Si los AP están dentro de los lı́mites, entonces habremos encontrado también
el coste teórico que se consigue aplicando dichos AP, y que resultará ser el
menor tiempo de ejecución.
160
5.5. Árbol de rutas
161
Capı́tulo 5: Simulador
AP SCN Cost
function library th.omp2 gpu size sparsity type exec. time in seconds
f3 1 2 0 100 × 100 50 2 0.5
f3 3 1 0 100 × 100 50 2 0.1
f4 1 1 0 100 × 100 50 2 1.0
f4 1 2 0 100 × 100 50 2 0.9
f4 2 1 0 100 × 100 50 2 1.5
f4 1 3 0 100 × 100 50 2 0.7
f5 7 1 1 100 × 100 50 2 0.3
f5 1 1 1 100 × 100 50 2 1.1
f5 2 1 1 100 × 100 50 2 1.4
f5 1 2 0 100 × 100 50 2 0.8
Por tanto, el mejor tiempo de ejecución para este nodo, en función de los datos
de entrenamiento, es de 1 segundo.
162
5.5. Árbol de rutas
alternativa es buscar entre todas las combinaciones de cores y GPUs que respetan
las limitaciones, e identificar la que ofrece un mejor rendimiento.
(1, 1, 2): Esta terna impone la limitación de 1 core para resolver el grupo
Gr1 , aplicable a las funciones f4 y f5 que componen su rutina. El mejor
tiempo de entrenamiento para la función f4 usando un core y ninguna GPU
es 1.0 segundos mediante la librerı́a 1 (MKL). En el caso de f5 , el tiempo
es de 1.1, también con MKL. Por tanto el grupo tiene un tiempo estimado
de resolución de 1.0 + 1.1 = 2.1 segundos. De igual manera se obtienen los
tiempos para el Gr2 , para el que sigue siendo válida la opción de usar la
librerı́a 3 (MA27), con 0.1 segundos. El Gr2 también mantiene su asignación
de dos cores, con un tiempo de 0.7 segundos usando MKL. El coste total
del nodo para la combinación (1, 1, 2) es, por tanto, de 2.1 segundos, que
corresponde con el mayor de los tiempos de resolución de sus grupos.
163
Capı́tulo 5: Simulador
5.6 Simulación
164
5.6. Simulación
simulatorExeDirectory = ”. . / . . / . . . ”;
simulatorExecutionDirectory = ”. . / . . / . . . ”;
simulatorDatabaseDirectory = ”. . / . . / . . . ”;
H i s t o r y =1;
ExecutionType =3;
B r a n c h S e l e c t i o n =1;
hardwareName=”HWTest ”;
L i s t O f M o d e l s =(
{
m o d e l F i l e =”S t r a s s e n 1 . mdl ”;
modelName=”ModeloEjemplo ”;
modelId =4;
}
);
THREADSLEVEL1=4;
THREADSLEVEL2=4;
LIBRARY=1;
NUMGPU=1;
CORES=4;
GPUS=3;
logFILE: Contiene una cadena de texto que almacena los primeros carac-
teres del nombre de los archivos de registro que el simulador genera durante
su ejecución, y que recogen información relevante para el usuario. El soft-
ware concatena el contenido del campo logFILE con el nombre del modelo
y la descripción del escenario que se ejecuta en cada momento para crear el
nombre del archivo.
165
Capı́tulo 5: Simulador
166
5.6. Simulación
NUMGPU: Contiene el número de GPUs que se van a poder utilizar para los
cálculos. Aplicable en el modo de simulación Simple (sección 5.6.2.2).
Entrenamiento
Simple
Múltiple
Autooptimizado
167
Capı́tulo 5: Simulador
Este modo se emplea para obtener los tiempos de ejecución de las funciones
incorporadas en el simulador, y está diseñado para realizar ejecuciones en batch
recorriendo un conjunto de parámetros algorı́tmicos, AP, y juegos de datos, SCN,
con los que interesa obtener información experimental del rendimiento de las fun-
ciones. El usuario especifica mediante una herramienta gráfica los mencionados AP
y SCN los cuales, una vez almacenados en sus correspondientes ficheros, pueden
ser usados posteriormente durante la ejecución.
scriptTraining: Toma el valor 1, para indicar que este script será usado
únicamente en las ejecuciones cuyo objetivo sea entrenar el sistema.
168
5.6. Simulación
Start
Select first AP
Apply AP
Select first fi
Execute function fi
Remaining fn?
No
Yes
Remaining SCN?
No
End
Figura 5.25: Algoritmo de ejecución del simulador en el modo de entrenamien-
to. Se miden los tiempos de ejecución de todas las funciones para una serie de
escenarios SCN y parámetros algorı́tmicos AP especificados por el usuario.
169
Capı́tulo 5: Simulador
Start
Apply AP
Select next SCN
Select next route Rx Execute Route Rx
Store execution
times
End
170
5.6. Simulación
Como vimos en la sección 5.3, un modelo puede ser resuelto siguiendo diferen-
tes estrategias de ordenación y agrupación de cálculos, cada una de las cuales se
denominada ruta. En el modo simple PARCSIM puede realizar la simulación si-
guiendo una determinada ruta seleccionada por el usuario, o un conjunto de ellas,
en cuyo caso se puede realizar una comparación empı́rica del rendimiento de cada
una. Pero también es posible indicar al simulador que seleccione automáticamen-
te la mejor ruta teórica en función de los AP, SCN y los tiempos de ejecución
de las funciones obtenidos en el modo de entrenamiento, como se describió en la
sección 5.5.4.
171
Capı́tulo 5: Simulador
Start
Select first AP
Execute Route Rx
Select
Select next
next route
route Rx
Rx
Store execution
times
Yes Remaining
Remaining
routes?
routes?
Yes No
No Yes
Remaining SCN? Remaining AP?
No
Execution report
End
Figura 5.27: Algoritmo de ejecución del simulador en el modo múltiple, con eje-
cuciones sobre un conjunto de escenarios SCN y con parámetros algorı́tmicos AP
generados a partir de los ficheros de scripts.
172
5.6. Simulación
Start
Apply AP
Execute Route Rx
Select next SCN
Store execution
times
Yes
Remaining SCN?
No
Execution report
End
Figura 5.28: Algoritmo de ejecución del simulador en el modo autooptimizado,
donde el software calcula los parámetros algorı́tmicos AP y la ruta Rx que mejor
se adaptan al hardware disponible.
173
Capı́tulo 5: Simulador
4 Las rutas con las que se han conseguido dichos tiempos. Se muestran los
identificadores de los grupos dentro de una cadena que representa un orden
de ejecución de los cálculos. Esta cadena sigue la codificación descrita en la
sección 5.3, y que recordamos a continuación:
174
5.6. Simulación
4
3
5
2
1
Figura 5.29: Información producida por el software durante la simulación, con los
tiempos de ejecución ordenados de menor a mayor.
175
Capı́tulo 5: Simulador
5.7 Herramientas
El interfaz gráfico del simulador ofrece una herramienta visual para acceder a
los tiempos de ejecución almacenados en la base de datos y mostrar los registros
en formato de tabla, como se muestra en la figura 5.30. Es posible seleccionar
la información referida a un modo de simulación o un modelo concreto. Para
ello se usan controles de selección desplegables donde se muestran los modos de
simulación descritos en 5.6.2 y los modelos de los que hay información disponible.
Una vez mostrados los datos, se pueden aplicar filtros adicionales sobre la
información incluida en cada columna. Para ello se usan los campos de selección
que aparecen debajo de la cabecera de la tabla, como muestra la figura 5.31.
176
5.7. Herramientas
El software permite generar gráficos de lı́neas que se pueden usar para compa-
rar los tiempos de ejecución obtenidos con diferentes parámetros algorı́tmicos para
un determinado tipo de matrices y hardware seleccionados por el usuario median-
te los correspondientes controles desplegables. Como se observa en la figura 5.32,
se muestra una serie gráfica para cada conjunto de parámetros algorı́tmicos. El
eje X representa los tamaños de las matrices y el eje Y los tiempos de ejecución.
Al seleccionar cualquiera de las series se muestra un grafo que representa la ruta
de ejecución empleada en la obtención del dato escogido.
177
Capı́tulo 5: Simulador
178
5.7. Herramientas
179
Capı́tulo 5: Simulador
(a) Vista del modelo, con dos grupos (b) Vista del árbol de rutas.
MM1 y MM2, cada uno de los cuales in- El nodo 2 propone la ejecu-
cluye una rutina de usuario RMM con una ción simultánea de MM1 y
multiplicación de matrices. MM2.
Figura 5.34: Representación en la interfaz gráfica GUI del simulador de una reso-
lución de dos multiplicaciones de matrices.
180
5.7. Herramientas
Además del modelo, es necesario indicar el tamaño y tipo de las matrices que
se van a multiplicar en los grupos MM1 y MM2. En PARCSIM esta información se
denomina escenario. Es posible crear más de un escenario para cada modelo, y
estos se pueden visualizar en el visor gráfico, como se muestra en la figura 5.35,
donde se observan tres escenarios con diferentes tamaños de matrices.
Figura 5.35: Vista del modelo de la figura 5.34(a) incluyendo información de los
escenarios.
Una vez creado el árbol de rutas y uno o más escenarios, es posible ejecutar la
herramienta interactiva de autooptimización, donde se debe indicar un escenario
concreto y el número de cores y GPUs que configuran la plataforma hardware.
En la figura 5.36 se observa la selección de dos cores y ninguna GPU. El campo
Number of Paths se usa para indicar a PARCSIM el número de rutas que
queremos obtener. El software lista las que pueda encontrar, comenzando por la
mejor de ellas (la que ofrece el menor tiempo de ejecución).
181
Capı́tulo 5: Simulador
Figura 5.37: Herramienta de autooptimización: las dos mejores rutas para una
plataforma con dos cores y un escenario seleccionado.
182
5.8. Arquitectura del software
Mediante esta utilidad, modificando los valores que representan las configura-
ciones del hardware y el tamaño del problema, un usuario puede obtener dinámi-
camente un análisis de la mejor asignación de cálculos a las unidades de cómputo,
y de la librerı́a que ofrece un mejor rendimiento en cada situación.
183
Capı́tulo 5: Simulador
RUN-IO
Acceso al sistema de ficheros y Base de Datos
RUN-PATHS RUN-SIM
Búsqueda de rutas Ejecución de cálculos
184
5.9. Conclusiones
• RUN-PATHS: Elaboración, a partir del grafo del modelo, del árbol que
representa las diferentes rutas que resuelven el problema. Incluye el
proceso de estimación incluido en la herramienta de autooptimización
que selecciona la ruta y los valores de los parámetros algorı́tmicos que
ofrecen el menor tiempo de ejecución.
5.9 Conclusiones
185
Capı́tulo 5: Simulador
186
Capı́tulo 6
Experimentos
187
Capı́tulo 6: Experimentos
188
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
2
2, 0
{3, 4}
2, 0
8 6 {5, 6}
10 4
7 5 14 2, 0
12 {7, 8}
0 1, 6
2, 0 {2}
9 3 {9, 10}
2, 0
11 {11, 12}
13
2, 0
1 {13, 14}
(a) Modelo en tres dimensiones del (b) Diagrama estructural que indica el
sistema mecánico a analizar. orden de resolución de los grupos.
Dado que se trata de un robot de cinemática paralela, cada uno de los con-
juntos manivela-barra presenta la misma topologı́a y, por tanto, se resuelve de la
misma manera. Por consiguiente, para su implementación en el simulador nece-
sitamos dos tipos de rutinas de análisis, la que permite resolver el terminal y la
que resuelve los grupos manivela-barra.
La figura 6.2 muestra una rutina para resolver un grupo compuesto por una
junta de rotación, una esférica y una cardan, y que corresponde con la estructura
que forman los grupos manivela-barra. Cabe indicar aquı́ que, para resolver la
cinemática de este grupo, cada barra unida mediante juntas esféricas al terminal
y a la manivela introduce un grado de libertad redundante que se ha eliminado
bloqueando uno de los giros relativos entre la propia barra y el terminal, lo que
equivale a modelar esa unión como una junta cardan.
189
Capı́tulo 6: Experimentos
Una vez resultas las posiciones, se ejecuta la rutina SG_VEL, que formula
la solución de las velocidades.
190
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Una vez creadas las rutinas, se pueden introducir en el simulador todos los
grupos que forman el modelo de la plataforma de Stewart, al que hemos nombrado
como MBS-STEWART y que se encuentra representado en la figura 6.4. En el grafo
se observan las mismas dependencias que las mostradas en el diagrama estructural
de la figura 6.1(b), en el que los pares manivela-barra de aquel corresponden a
los grupos SG_MB_1 al SG_MB_6 del modelo.
191
Capı́tulo 6: Experimentos
192
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Figura 6.5: Árbol de rutas que representa las alternativas de ordenación y agru-
pación de cálculos para resolver una plataforma de Stewart como la representada
en el modelo de la figura 6.4.
193
Capı́tulo 6: Experimentos
Figura 6.6: Ruta que resuelve de manera secuencial todos los grupos en los que
se descompone una plataforma de Stewart como la representada en el modelo de
la figura 6.4.
194
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
195
Capı́tulo 6: Experimentos
ción A.8.17, seleccionaremos la ruta mostrada en la figura 6.6. Una vez grabada,
la información de dicha ruta queda asociada al modelo y será utilizada en la
próxima ejecución del simulador.
Tabla 6.2: Script definido para guiar el primer experimento de simulación de una
plataforma de Stewart. Se asigna un único thread al primer nivel de paralelismo
OpenMP al tratarse de una ejecución en secuencia de los grupos estructurales.
El número de threads que se pone a disposición de la librerı́a MKL se limita al
número de cores fı́sicos en JUPITER (12).
Una vez iniciada la simulación, el software realiza una ejecución por cada com-
binación de parámetros algorı́tmicos generada a partir de los valores especificados
en el script. Los cálculos se realizan de acuerdo a la ruta preseleccionada (en este
caso la que ejecuta los grupos en secuencia). La figura 6.7 muestra un extracto
de la información mostrada por consola al finalizar el proceso de simulación (en
concreto la simulación del escenario que contiene matrices de tamaño 3000 × 3000
y dispersión del 80 %).
196
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Figura 6.7: Información obtenida por consola al finalizar las simulaciones en JU-
PITER, con tamaños de matrices (nEQ_MB) de 3000 × 3000 y variando el número
de hilos asignados a MKL. El informe ordena de menor a mayor los tiempos de
ejecución obtenidos.
197
Capı́tulo 6: Experimentos
Parámetro Valores
Modelo a simular { MBS-STEWART }
Modo de ejecución Múltiple
Ruta Preseleccionada
Tabla 6.3: Configuración aplicable a una ejecución del simulador para el modelo de
la plataforma de Stewart. El modo de ejecución múltiple genera varias ejecuciones
en función del contenido del script. En este experimento la ruta preseleccionada
es la que realiza la ejecución en secuencia de los grupos.
En la tabla 6.4 se pueden consultar los datos obtenidos en este primer experi-
mento, con una única ejecución. En ella se comprueba la mejora de rendimiento
debida a la paralelización de los cálculos matriciales de la librerı́a MKL, siendo
esta más significativa conforme aumenta el tamaño de las matrices.
nEQ_MB MKL sq MKL th2 MKL th3 MKL th4 MKL th6 MKL th10 MKL th12
15 0.02341 0.02104 0.02110 0.02071 0.02081 0.02074 0.02103
30 0.02675 0.02679 0.02687 0.02670 0.02712 0.02685 0.02689
60 0.03471 0.04294 0.03999 0.03473 0.03452 0.03455 0.03481
120 0.06726 0.10049 0.07207 0.07473 0.07823 0.05967 0.07464
360 0.39681 1.05925 0.28366 0.27418 0.23914 0.23340 0.26520
1000 5.95198 4.38516 3.52734 2.83227 2.38782 2.08138 2.19284
2000 41.76047 25.11993 18.19453 15.12859 12.38607 10.85181 10.37525
3000 134.09300 74.81839 58.91036 50.78470 35.87525 27.17892 26.61387
198
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
199
Capı́tulo 6: Experimentos
JUPITER SATURNO
7 7
MKL th2 MKL th2
MKL th3 MKL th3
MKL th4 MKL th4
6 MKL th6 6 MKL th8
MKL th10 MKL th16
MKL th12 MKL th24
5 5
4 4
Speed-up
Speed-up
3 3
2 2
1 1
0 0
102 103 102 103
Tamaños de matriz nEQ_MB en SG_KINEM_REC (escala logarı́tmica) Tamaños de matriz nEQ_MB en SG_KINEM_REC (escala logarı́tmica)
Los resultados obtenidos quedan recogidos en la tabla 6.8. Se observa que los
tiempos de ejecución que ofrece PARDISO son mejores que los de MKL cuando
se manipulan matrices de dimensiones mayores de 1000 × 1000. Y esto ocurre
incluso sin paralelismo implı́cito y asignaciones de pocos threads (entre 2 y 4), lo
que muestra la optimización de esta librerı́a para trabajar con matrices dispersas.
200
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
nEQ_MB PARD sq PARD th2 PARD th3 PARD th4 PARD th6 PARD th10 PARD th12
15 0.05032 0.06894 0.06295 0.06030 0.06359 0.06603 0.06801
30 0.06695 0.07506 0.08771 0.07662 0.07535 0.07837 0.07823
60 0.10100 0.11465 0.11430 0.10663 0.10976 0.11188 0.12063
120 0.16289 0.15360 0.15905 0.15021 0.14795 0.14796 0.15325
360 0.80643 0.64377 0.67087 0.65297 0.62256 0.64153 0.75040
1000 5.64075 4.03294 4.08755 3.66894 3.49814 3.54498 3.56475
2000 28.13423 19.39484 18.97692 16.27576 15.75483 15.46708 15.76543
3000 66.10252 47.47523 47.01676 38.71151 37.18689 36.11017 36.64083
1.4
Speed-up
1.3
1.2
1.1
0.9
0.8
102 103
Tamaño matriz nEQ_MB en SG_KINEM_REC (escala logarı́tmica)
201
Capı́tulo 6: Experimentos
nEQ_MB PARD sq PARD th2 PARD th3 PARD th4 PARD th8 PARD th16 PARD th24
15 0.09151 0.10337 0.08323 0.09135 0.09367 0.09726 0.26302
30 0.10585 0.14141 0.13922 0.12336 0.11769 0.12869 0.25693
60 0.18529 0.18099 0.16894 0.13405 0.13973 0.18451 0.24645
120 0.30323 0.20309 0.19795 0.18121 0.19396 0.20614 0.28493
360 1.29694 1.03466 1.05293 1.01746 0.95169 1.14638 1.19874
1000 9.85990 7.05615 6.81412 6.26378 6.15644 6.66125 6.86684
2000 52.31130 34.74005 34.35743 30.21676 29.54983 28.93482 32.56781
3000 135.98866 90.65479 89.67818 72.70068 68.38662 69.85470 75.42628
Tabla 6.10: Script definido para guiar el experimento de simulación del modelo
de Stewart con todas las librerı́as incluidas en la versión actual del simulador.
Se reserva un único thread al primer nivel de paralelismo OpenMP al tratarse
de una ejecución en secuencia de los grupos estructurales. Se habilita una GPU
para ser usada por la librerı́a MAGMA (valor 1) y se desactiva el segundo nivel
de paralelismo del resto de librerı́as (valor 1).
202
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Los resultados, mostrados en la tabla 6.11 reflejan que, para matrices grandes
(tamaños 3000 × 3000), la librerı́a MAGMA presenta el mejor rendimiento por
su aprovechamiento de la capacidad de cómputo de la GPU. Sin embargo, con
matrices de menor tamaño los tiempos necesarios para el movimiento de informa-
ción entre la memoria de la CPU y la GPU penalizan el uso de estos dispositivos.
En ausencia de una GPU, los mejores resultados con matrices grandes los ofrece
MA86, que muestran el mejor comportamiento para tamaños desde 1000 × 1000
en adelante.
203
Capı́tulo 6: Experimentos
Los resultados obtenidos, recogidos en la tabla 6.13, comparados con los ob-
tenidos con matrices con una dispersión del 80 % (tabla 6.11) nos muestran que
MKL y MAGMA ofrecen el mismo nivel de rendimiento en ambos experimen-
tos, lo cual es debido a que ambas librerı́as implementan métodos para matrices
densas. El resto de librerı́as, especializadas en el manejo de matrices dispersas,
muestran un rendimiento notablemente peor en este escenario de matrices menos
dispersas.
204
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
205
Capı́tulo 6: Experimentos
Dado que este sistema consta de seis manivelas, los tamaños de las matrices
se calcularán como: nEQ_Global = 6 nEQ_MB+nEQ_T.
La tabla 6.14 recoge los escenarios que se usarán en los experimentos. Los
tamaños de las matrices se muestran en la columna nEQ_Global. Se incluyen
las columnas nEQ_T y nEQ_MB para reflejar su correspondencia con los tamaños
derivados de la formulación basada en ecuaciones de grupo.
206
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Tabla 6.15: Script definido para guiar el experimento de simulación de una pla-
taforma de Stewart siguiendo una formulación global usando 4 cores de la plata-
forma JUPITER.
207
Capı́tulo 6: Experimentos
30 MKL seq
MKL th2
MKL th4
25
20
Speed-up 15
10
102 103
Tamaño matriz nEQ_Global en SG_KINEM_REC (escala logarı́tmica)
208
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Debemos, por tanto, repetir los experimentos fijando una de esas rutas de eje-
cución paralela en el simulador. Siguiendo los pasos descritos en la sección A.8.17,
seleccionamos la ruta mostrada en la figura 6.12 y grabamos dicho cambio. Esta
selección queda almacenada junto al resto de información del modelo y será usada
en las siguientes simulaciones.
Tabla 6.17: Script definido para guiar la simulación del modelo de Stewart usando
las librerı́as MKL y PARDISO. Se asignan tres threads al primer nivel de para-
lelismo para permitir la resolución simultánea de tres grupos estructurales. El
número de threads que se pone a disposición de las librerı́as se limita al número
de cores fı́sicos de JUPITER (12).
209
Capı́tulo 6: Experimentos
210
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
30 × 30 3000 × 3000
th.Nivel 1 × th.Nivel 2 MKL PARDISO MA27 MKL PARDISO MA27
3×1 0.02907 0.06886 0.02459 134.64927 49.81405 76.11744
3×2 0.06895 0.10432 84.95055 42.49332
3×3 0.05890 0.09414 81.48293 43.77798
3×4 0.03320 0.08114 50.86890 35.39894
3×8 0.11703 0.08498 48.29932 34.66773
seq 0.06112 0.10585 0.04969 326.49321 135.98866 184.53877
1×2 0.04946 0.14141 191.43740 90.65479
1×3 0.06585 0.13922 136.85202 89.67818
1×4 0.04007 0.12336 114.41497 72.70068
1×8 0.04721 0.11769 88.09155 68.38662
1 × 16 0.07527 0.12869 61.94333 69.85470
1 × 24 0.10122 0.25693 60.30540 75.42628
Tabla 6.20: Comparación de los tiempos de ejecución obtenidos con MKL, PAR-
DISO y MA27 en SATURNO con 24 cores, para matrices simétricas de tamaños
30 × 30 y 3000 × 3000 y un factor de dispersión del 80 %. Se muestran todas las
combinaciones de threads asignados al primer y segundo nivel de paralelismo.
211
Capı́tulo 6: Experimentos
212
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Tabla 6.21: Script definido para guiar la construcción del conjunto de entrena-
miento en la plataforma hardware SATURNO. Se obtendrán datos de ejecución
con las siete librerı́as incluidas en el simulador, con asignaciones de threads desde
1 (sin paralelismo implı́cito) hasta 24 (cores fı́sicos de la plataforma SATURNO).
Tabla 6.22: Escenarios definidos para usar durante el entrenamiento de las funcio-
nes. Se definen la tipologı́a de las matrices, su factor de dispersión y los tamaños
de las matrices, nEQ.
213
Capı́tulo 6: Experimentos
Parámetro Valores
Hardware SATURNO
Modelo a simular { MBS-STEWART }
Modo de ejecución Training
Parámetro Valores
Hardware SATURNO
Modelo a simular { MBS-STEWART }
Modo de ejecución Autotuning
Number of cores 24
Number of GPUs 1
Cuando iniciamos la ejecución, el simulador recorre uno por uno cada uno
de los escenarios mostrados en la tabla 6.1. En cada caso, el software calcula la
ruta y los parámetros algorı́tmicos asociados que suponen el tiempo de ejecución
teórico más reducido, y resuelve el modelo siguiendo dicha ruta.
214
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
215
Capı́tulo 6: Experimentos
Experimentos Autooptimizada
3×8 2 × 12 4×6 6×4
MKL PARD MKL PARD MKL PARD PARD
48.29932 34.66773 38.08665 43.07153 35.43077 30.14942 31.436998
216
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
217
Capı́tulo 6: Experimentos
2, 0
{8-6}
2, 0
0 4, 2 {10-11}
{2-3-4-5} 2, 0
{12-13}
2, 0
{7-9}
(a) Elementos que forman el mecanismo co- (b) Diagrama estructural que muestra
rrespondiente a un eje de un camión. los grupos estructurales identificados
y las dependencias entre los mismos.
Una vez creadas las rutinas, se pueden introducir en el simulador todos los
grupos que forman el modelo de la suspensión, al que hemos llamado MBS-TRUCK
(figura 6.16). El nombre _SG_2C3E1R hace referencia a un grupo estructural con
dos juntas cardan, tres esféricas y una de rotación.
218
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
219
Capı́tulo 6: Experimentos
Figura 6.17: Árbol de rutas que representa las alternativas de ordenación y agru-
pación de cálculos para resolver un sistema mecánico de suspensión de un eje de
un camión como el representado en el modelo de la figura 6.16.
220
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Figura 6.18: Ruta que resuelve en secuencia todos los grupos en los que se des-
compone el modelo de la suspensión de un eje de un camión como el representado
en la figura 6.16.
De cara a los experimentos, los escenarios que representan los datos nece-
sarios para resolver los grupos estructurales serán similares a los definidos en la
sección 6.1.1.1 para la simulación de la plataforma de Stewart. Partiendo de matri-
ces de tamaño 37 × 37, llegaremos hasta tamaños de 3000 × 3000 para representar
grupos más complejos con cada vez mayor número de coordenadas. Al obtenerse
el modelo mediante una formulación basada en ecuaciones de grupo, las matrices
obtenidas son simétricas con un factor de dispersión del 80 % y los valores no nulos
situados alrededor de la diagonal. Con todo ello podemos crear un conjunto de
escenarios que nombraremos desde MBS-TRUCK1-80 hasta MBS-TRUCK7-80,
cuyo detalle se puede consultar en la tabla 6.26.
221
Capı́tulo 6: Experimentos
Parámetro Valores
Modelo a simular { MBS-TRUCK }
Modo de ejecución Múltiple
Ruta Preseleccionada
Tabla 6.28: Configuración del simulador para la ejecución del modelo de la sus-
pensión de un camión en modo múltiple y con una ruta preseleccionada.
222
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
La simulación obtiene los resultados mostrados en las tablas 6.29 y 6.30, donde
se observan las mejoras de rendimiento al paralelizar los cálculos matriciales de
las librerı́as MKL y PARDISO respectivamente.
nEQ MKL sq MKL th2 MKL th3 MKL th4 MKL th8 MKL th16 MKL th24
37 0.05891 0.06130 0.06021 0.05963 0.04973 0.08738 0.06907
60 0.08139 0.08459 0.07112 0.08652 0.06713 0.07123 0.06858
120 0.11569 0.10540 0.08769 0.08719 0.08732 0.12637 0.09976
360 0.74432 0.52438 0.42205 0.42033 0.34809 0.35174 0.43335
1000 12.16384 7.65464 6.00778 5.12701 3.70253 3.06832 3.20775
2000 84.39074 49.59199 36.00251 28.36838 20.62638 18.56056 18.10030
3000 263.40308 149.52103 106.81606 86.59923 52.73259 51.17312 49.33507
nEQ PARD sq PARD th2 PARD th3 PARD th4 PARD th8 PARD th16 PARD th24
37 0.10518 0.09204 0.09451 0.09214 0.09932 0.10330 0.11242
60 0.14430 0.13272 0.15599 0.14020 0.15992 0.14654 0.17051
120 0.19471 0.15493 0.16133 0.16742 0.16930 0.19899 0.22135
360 1.09878 0.86491 0.87407 0.85483 0.80201 0.79954 0.93228
1000 8.06686 5.92144 6.14033 5.30444 4.66469 4.73366 4.56816
2000 40.34643 28.23735 28.44071 23.60055 21.53056 21.03959 22.99616
3000 98.10715 75.53687 73.53182 60.32187 53.17042 51.20848 56.99657
223
Capı́tulo 6: Experimentos
Esta sección aborda la simulación del modelo de la suspensión del camión in-
troduciendo paralelismo explı́cito en la solución de grupos. La figura 6.19 muestra
dos posibles rutas que proponen la resolución simultánea de grupos:
224
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Nuestro análisis pretende mostrar la utilidad del software para simular varias
rutas preseleccionadas por el usuario de la aplicación, y con ello encontrar la que
ofrece mejor rendimiento. En este caso observamos que la primera ruta seleccio-
nada resuelve en paralelo grupos que ejecutan la misma rutina, por lo que el coste
computacional es similar a igualdad de escenarios. Sin embargo, la segunda ruta
ejecuta de manera simultánea grupos que contienen rutinas diferentes.
Tabla 6.32: Script creado para la simulación del modelo de la suspensión em-
pleando las librerı́as MKL y PARDISO. Se asignan dos threads al primer nivel
de paralelismo para permitir la resolución simultánea de dos grupos. El número
de threads que se pone a disposición del paralelismo implı́cito de las librerı́as se
limita al número de cores fı́sicos de SATURNO (24).
El simulador realiza los cálculos en cada una de las rutas aplicando todas
las combinaciones de parámetros algorı́tmicos que se derivan de la información
almacenada en el script. Una consulta en la base de datos permite elaborar la ta-
bla 6.33 que muestra, para cada dimensión de las matrices, los tiempos obtenidos
al ejecutar en paralelo dos grupos estructurales conforme aumentamos los threads
asignados a las librerı́as hasta alcanzar el máximo de los 24 cores disponibles en
SATURNO (combinaciones 2 × 1, 2 × 2, 2 × 3, 2 × 4, 2 × 8 y 2 × 12). Se incluyen
dos columnas para mostrar los mejores tiempos obtenidos en la sección anterior
en una ejecución en secuencia de todos los grupos, y las asignaciones de threads
correspondientes en cada caso.
225
Capı́tulo 6: Experimentos
226
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
227
Capı́tulo 6: Experimentos
228
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
La solución del sistema que engloba los tres ejes se puede abordar de varias
formas. La figura 6.22 muestra resaltada la ruta que calcula en secuencia cada
eje por separado. Sin embargo, la mostrada en la figura 6.23 supone la resolución
simultánea de los tres ejes.
Figura 6.22: Ruta para la resolución en secuencia de los tres ejes de un sistema
de suspensión multieje.
Figura 6.23: Ruta para la resolución simultánea de los tres ejes de un sistema de
suspensión multieje.
229
Capı́tulo 6: Experimentos
Cálculo de los tres ejes en secuencia: En este caso todos los recursos de un
sistema multicore se pueden asignar a la resolución de cada eje. De acuerdo
a las conclusiones obtenidas en la sección anterior (6.1.2.2), la resolución en
paralelo de los grupos que forman el modelo de un eje es más rápida que la
ejecución secuencial. Por tanto, para resolver el modelo multieje completo
interesa introducir algún tipo de paralelismo de grupos al resolver los ejes
que lo componen. La tabla 6.35 muestra los mejores tiempos que se habı́an
obtenido con MKL en la plataforma SATURNO con 24 cores y diversas
opciones de paralelismo.
230
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Figura 6.24: Ruta de solución en secuencia del modelo de tres ejes, resolviendo
en paralelo los cuatro componentes paralelizables de cada eje.
231
Capı́tulo 6: Experimentos
Figura 6.25: Ruta de solución en secuencia del modelo de tres ejes, resolviendo
en paralelo bloques de dos grupos dentro de cada eje.
Cálculo de los tres ejes de manera simultánea: En este caso los 24 cores de
SATURNO se deben repartir, siendo una posible asignación la reserva de
ocho cores a la resolución de cada eje. Para encontrar la mejor ruta que
resuelva un solo eje de acuerdo a la nueva restricción de recursos consulta-
mos las combinaciones de ocho o menos threads reflejadas en la tabla 6.36.
Las columnas 2 × 3 y 2 × 4 son las mejores combinaciones mostradas en la
tabla 6.33 cuando se resuelven dos grupos en paralelo. Las columnas 4 × 1 y
4 × 2 contienen los tiempos de ejecución recogidos en la tabla 6.34 obtenidos
en la resolución simultánea de cuatro grupos.
Observamos que en todos los tamaños de matrices el mejor rendimiento se
obtiene resolviendo simultáneamente dos grupos, asignando tres threads a
MKL (2 × 3) en el caso de 37 × 37, y cuatro (2 × 4) en el resto de tamaños.
232
6.1. Aplicación del simulador al análisis cinemático de sistemas multicuerpo
Figura 6.26: Ruta de solución en paralelo del modelo de tres ejes, resolviendo en
paralelo grupos de dos componentes de cada eje.
En casos donde el reparto de recursos no sea tan claro como el presentado (24
cores entre 3 ejes), se deberı́a realizar un conjunto adicional de diferentes pruebas.
233
Capı́tulo 6: Experimentos
En la disciplina del álgebra lineal existen rutinas en las que el enfoque estándar
de resolución puede no ser el óptimo en términos de tiempo de computación.
Un ejemplo es la multiplicación de matrices, que presenta un interés especial
por su uso en la resolución de problemas cientı́ficos y de ingenierı́a, y por estar
incluida en el cálculo de numerosas rutinas de álgebra lineal. Además del algoritmo
de resolución tradicional basado en tres bucles, se han desarrollado otros como
son la multiplicación por bloques, o el algoritmo de Strassen. En estos casos el
simulador puede ayudar a encontrar los mejores parámetros algorı́tmicos, librerı́as
y asignación de operaciones a unidades de cómputo. El resultado obtenido puede
ayudar al desarrollo óptimo de rutinas de nivel jerárquico superior que hagan uso
de las rutinas básicas.
234
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
A x B = C
A1 A 1B
A2
x B = A 2B
A x B1 B2 = AB1 AB2
A1
A2
x B1 B2 = A1 B 1 + A 2B 2
Para comprobar mediante el uso del simulador las mejoras obtenidas en los
tiempos de ejecución que se consiguen con este algoritmo de multiplicación de
matrices creamos inicialmente un modelo básico que resuelve una multiplicación
de dos matrices con sus tamaños originales. El tiempo de resolución de dicho
modelo con varios tamaños de matrices nos servirá de base con la que comparar
posteriores ejecuciones donde aplicaremos divisiones por bloques.
235
Capı́tulo 6: Experimentos
nROWS MKL th1 MKL th2 MKL th4 MKL th8 MKL th10 MKL th12
100 0.00030 0.00045 0.00039 0.00028 0.00029 0.00029
500 0.01780 0.01248 0.00519 0.00363 0.00417 0.00496
1000 0.13394 0.06613 0.03401 0.02176 0.02452 0.03260
2000 0.84583 0.44830 0.24137 0.14324 0.11863 0.16818
3000 2.82709 1.46063 0.77464 0.42583 0.41011 0.30510
236
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
nROWS MKL th1 MKL th2 MKL th4 MKL th8 MKL th10 MKL th24
100 0.00080 0.00096 0.00043 0.00069 0.00076 0.00252
500 0.03816 0.02386 0.01099 0.01003 0.00875 0.01221
1000 0.28872 0.14988 0.09032 0.04769 0.04291 0.06681
2000 2.27098 1.15297 0.60477 0.38777 0.37256 0.24645
3000 7.64038 3.88234 1.96197 1.16516 0.82309 0.75068
JUPITER SATURNO
10 11
MKL th2 MKL th2
MKL th4 MKL th4
9 MKL th8 10 MKL th8
MKL th10 MKL th10
MKL th12 9 MKL th24
8
8
7
7
6
Speed-up
Speed-up
6
5
5
4
4
3
3
2
2
1 1
0 0
200
400
600
800
1000
1200
1400
1600
1800
2000
2200
2400
2600
2800
3000
200
400
600
800
1000
1200
1400
1600
1800
2000
2200
2400
2600
2800
3000
237
Capı́tulo 6: Experimentos
Este modelo permite resolver las dos multiplicaciones necesarias tras dividir
por columnas la matriz B en dos bloques de igual tamaño. Como vimos en las
secciones anteriores, dado un modelo, el simulador puede elaborar las rutas que
permiten resolverlo. En la figura 6.31 se observan las que se originan en el caso
de dos grupos.
238
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
Los nuevos modelos pueden resolverse siguiendo tantas estrategias como in-
diquen sus árboles de rutas. Para los experimentos siguientes vamos a considerar
aquellas ejecuciones que resuelven de manera simultánea todos los grupos que
componen los modelos, y compararemos los rendimientos con la versión que rea-
liza la multiplicación sin descomposición por bloques. Dichas rutas se muestran
en las figuras 6.34, 6.35 y 6.36.
239
Capı́tulo 6: Experimentos
Figura 6.34: Selección de la ruta que aplica paralelismo de grupos para resolver
una multiplicación de matrices por bloques mediante el modelo de la figura 6.30.
Figura 6.35: Selección de la ruta que aplica paralelismo de grupos para resolver
una multiplicación de matrices por bloques mediante el modelo de la figura 6.32.
Figura 6.36: Selección de la ruta que aplica paralelismo de grupos para resolver
una multiplicación de matrices por bloques mediante el modelo de la figura 6.33.
240
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
Parámetro Valores
Modelos a simular { MATMULT_COLS_50,MATMULT_COLS_35,MATMULT_COLS_20 }
Modo de ejecución Múltiple
Ruta Preseleccionada
241
Capı́tulo 6: Experimentos
242
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
OpenMP t h r e a d s 1 2 .
MKL 2 0 1 7 . 0 . 1 ,
MKL t h r e a d s 1 2 .
F r i Jan 15 1 8 : 4 7 : 5 1 2021
243
Capı́tulo 6: Experimentos
MKL MAGMA
nROWS 3×1 3×2 3×3 3×4 3 GPUs
500 0.01019 0.00635 0.00350 0.00403 0.01055
1000 0.05926 0.02977 0.03592 0.02950 0.01796
2000 0.36205 0.16690 0.12079 0.13858 0.07952
3000 1.09032 0.86692 0.72478 0.58676 0.22992
244
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
MKL MAGMA
nROWS 3×1 3×2 3×3 3×4 3 GPUs
2000 0.36205 0.16690 0.12079 0.13858 0.07952
G5 0.36173 0.16156 0.11757 0.09029 0.07550
G6 0.35431 0.16166 0.12054 0.11709 0.04293
G7 0.32139 0.13978 0.10287 0.08498 0.07027
3000 1.09032 0.86692 0.72478 0.58676 0.22992
G5 1.08003 0.86657 0.71487 0.29032 0.20032
G6 1.07855 0.53282 0.72442 0.57703 0.13511
G7 0.88808 0.79364 0.32048 0.32993 0.22352
Tabla 6.44: Desglose por grupos de los tiempos de ejecución del modelo de la
multiplicación de matrices por bloques (MATMULT_COLS_35) en JUPITER con
varios tamaños de matrices (nROWS×nCOLS), variando el número de hilos asig-
nados a MKL y con tres GPUs explotadas con MAGMA.
245
Capı́tulo 6: Experimentos
mos incluso más eficientes para la multiplicación de matrices [166, 183], e incluso
adaptaciones del algoritmo tradicional a los nuevos sistemas computacionales. La
inclusión en esta sección de experimentos del algoritmo de Strassen en concreto
viene motivada por su idoneidad para ser representado como un modelo compues-
to por grupos de operaciones que pueden ser resueltos en paralelo y ser asignados
a las diferentes unidades de computación disponibles.
246
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
C1,1 = M1 + M4 − M5 + M7
C1,2 = M3 + M5
C2,1 = M2 + M4
C2,2 = M1 − M2 + M3 + M6
M1
M2
C2,1
M3 C1,1
C2,2
C1,2 M4
M5
M6
M7
RCombine: Ejecuta las operaciones suma y resta para obtener las Ci, j fina-
les.
247
Capı́tulo 6: Experimentos
Estas rutinas permiten crear en el simulador todos los grupos que forman el
modelo del algoritmo de Strassen, al que hemos nombrado como STRASSEN, y
que se encuentra representado en la figura 6.39.
En la figura 6.40 se observan todas las posibilidades para la resolución del al-
goritmo de Strassen sin recursión, es decir, sin que ninguna de las multiplicaciones
de matrices presentes en el algoritmo se resuelvan a su vez mediante Strassen.
248
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
Figura 6.40: Árbol de rutas que representa las alternativas de ordenación y agru-
pación de cálculos para resolver una multiplicación de matrices mediante el algo-
ritmo de Strassen como el representado en el modelo de la figura 6.39.
249
Capı́tulo 6: Experimentos
250
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
Parámetro Valores
Modelos a simular { STRASSEN }
Modo de ejecución Simple
Ruta Preseleccionada
Número de threads de primer nivel (OpenMP) {1}
Número de threads de segundo nivel (MKL) {1}
Número de GPUs {0}
Librerı́a {1 : MKL}
JUPITER SATURNO
nROWS×nCOLS MATMUL STRASSEN MATMUL STRASSEN
6000 × 6000 22.56067 21.20005 54.36038 50.13080
8000 × 8000 53.34177 47.80797 130.18680 114.81141
12000 × 12000 179.10999 160.26036 428.79211 379.44492
251
Capı́tulo 6: Experimentos
Parámetro Valores
Modelos a simular { MATMUL, STRASSEN }
Modo de ejecución Simple
Ruta Preseleccionada
Número de threads de primer nivel (OpenMP) {1}
Número de GPUs {1}
Librerı́a {7 : MAGMA}
JUPITER SATURNO
nROWS×nCOLS MATMUL STRASSEN MATMUL STRASSEN
6000 × 6000 1.82795 3.36921 1.48523 4.14287
8000 × 8000 4.10491 5.56739 3.35258 6.47299
12000 × 12000 12.82721 16.04158 6.74356 16.88393
Tabla 6.48: Tiempos de ejecución (en segundos) obtenidos con el simulador en una
multiplicación sin bloques (modelo MATMUL) y mediante el algoritmo de Strassen
(modelo STRASSEN). Plataformas JUPITER y SATURNO empleando una GPU
mediante la librerı́a MAGMA.
252
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
Dado que el modelo embebido puede ser resuelto a su vez siguiendo varias
rutas, debemos indicar al simulador cual de ellas debe ejecutar. En el presente
experimento, con un sistema monocore, no se puede usar paralelismo de grupos.
Por este motivo la figura 6.42 muestra que los grupos {MM1 . . . MM7} ejecutarán en
secuencia todos los grupos heredados del modelo de Strassen importado.
253
Capı́tulo 6: Experimentos
254
6.2. Aplicación del simulador a la optimización de rutinas de álgebra lineal
JUPITER SATURNO
STRASSEN STRASSEN
nROWS MATMUL R0 R1 MATMUL R0 R1
6000 22.56067 21.20005 22.179228 54.36038 50.13080 58.838894
8000 53.34177 47.80797 48.730221 130.18680 114.81141 122.493195
12000 179.10999 160.26036 157.767395 428.79211 379.44492 410.243134
Tabla 6.49: Tiempos de ejecución (en segundos) obtenidos con el simulador en una
multiplicación tradicional (modelo MATMUL) y mediante el algoritmo de Strassen
sin recursión (R0) y con un nivel de recursión (R1). Matrices cuadradas con dis-
persión del 30 % en las plataformas hardware JUPITER y SATURNO empleando
un único core.
Parámetro Valores
Modelos a simular { STRASSEN }
Modo de ejecución Simple
Ruta Preseleccionada
Número de threads de primer nivel (OpenMP) {1}
Número de threads de segundo nivel (MKL) { 2, 3 }
Número de GPUs {0}
Librerı́a {1 : MKL}
255
Capı́tulo 6: Experimentos
La tabla 6.51 muestra los resultados de los experimentos con los nuevos pará-
metros algorı́tmicos aplicados a la ejecución de los modelos MATMUL y STRASSEN
en la plataforma SATURNO. Observamos que las reducciones de los tiempos de
ejecución que se obtenı́an con el algoritmo de Strassen frente a una multiplica-
ción convencional en sistemas monocore, que se vieron en la sección anterior,
son menores conforme aumentamos el número de threads de dos a tres. Asignar
tres threads el algoritmo de Strassen ya no ofrece ventajas, salvo para tamaños
grandes.
2 threads 3 threads
nROWS×nCOLS MATMUL STRASSEN % MATMUL STRASSEN %
6000 × 6000 29.24644 26.59713 9.1 19.22396 19.84433 -3.2
8000 × 8000 70.83429 66.17148 6.6 44.32339 45.53305 -2.7
12000 × 12000 224.74800 205.56395 8.5 147.06793 143.12148 2.7
Tabla 6.51: Tiempos de ejecución (en segundos) obtenidos con el simulador pa-
ra una multiplicación tradicional sin bloques (modelo MATMUL) y mediante el
algoritmo de Strassen (modelo STRASSEN). Plataforma hardware SATURNO,
asignando dos y tres threads.
De igual modo ocurre en JUPITER (tabla 6.52), donde los resultados muestran
un porcentaje de mejora que se reduce conforme se produce un incremento en el
número de threads, que en el caso de matrices 12000 × 12000 pasa del 9.2 % con
dos threads a 5.8 % con tres threads, cuando en sistemas con un solo thread la
ventaja del algoritmo de Strassen estaba en el 10.5 %.
2 threads 3 threads
nROWS×nCOLS MATMUL STRASSEN % MATMUL STRASSEN %
6000 × 6000 11.31462 10.67342 5.7 7.69943 7.40049 3.9
8000 × 8000 26.73003 24.68509 7.7 18.07492 17.12385 5.3
12000 × 12000 89.84947 81.57596 9.2 70.71327 66.61833 5.8
Tabla 6.52: Tiempos de ejecución (en segundos) obtenidos con el simulador en una
multiplicación tradicional sin bloques (modelo MATMUL) y mediante el algoritmo
de Strassen (modelo STRASSEN). Plataforma hardware JUPITER, asignando dos
y tres threads.
256
6.3. Conclusiones
6.3 Conclusiones
En los ejemplos mostrados dentro del área de los sistemas multicuerpo hemos
visto cómo la información obtenida permite a un experto en mecanismos conocer
cuál es la forma más adecuada de plantear su algoritmo de resolución, ya que el
simulador aporta indicaciones de en qué momento debe incluir paralelismo y qué
librerı́a se comporta mejor.
257
Capı́tulo 6: Experimentos
Tabla 6.53: Tabla que recoge las mejores configuraciones de ejecución de una ruti-
na que resuelve tres grupos para varios tamaños de matrices y factores de disper-
sión, obtenidas por medio de simulaciones usando las librerı́as MKL y PARDISO.
Este supuesto teórico hace referencia a una rutina que se resuelve mediante
tres grupos, G1, G2 y G3. La tabla permite determinar, para cada tamaño de
matrices y factor de dispersión, la mejor opción de ordenación de los cálculos
(ruta), el número de threads OpenMP, la mejor librerı́a y los threads asignados
al paralelismo implı́cito. La cantidad de parámetros que se deben determinar
dependerá del tipo de rutina y del hardware. Por ejemplo, en el caso de rutinas
anidadas el nivel de recursión es otro factor que debe determinarse, y en el caso
de plataformas con GPUs, habrı́a que contemplar el número de GPUs asignadas
a la resolución de cada grupo.
258
Capı́tulo 7
7.1 Conclusiones
259
Capı́tulo 7: Conclusiones, trabajo futuro y contribuciones
260
7.1. Conclusiones
de entre las disponibles, proponiendo en cada nodo la librerı́a que ofrece mejor
rendimiento teórico y los parámetros algorı́tmicos requeridos para ello. La ruta
óptima se considera teórica en cuanto que toma como base los tiempos de ejecu-
ción de las librerı́as en simulaciones aisladas variando los parámetros algorı́tmicos
dentro de un conjunto de entrenamiento preestablecido.
261
Capı́tulo 7: Conclusiones, trabajo futuro y contribuciones
262
7.2. Trabajo futuro
263
Capı́tulo 7: Conclusiones, trabajo futuro y contribuciones
264
7.2. Trabajo futuro
265
Capı́tulo 7: Conclusiones, trabajo futuro y contribuciones
266
7.3. Difusión
7.3 Difusión
267
Capı́tulo 7: Conclusiones, trabajo futuro y contribuciones
268
7.3. Difusión
269
Capı́tulo 7: Conclusiones, trabajo futuro y contribuciones
270
Anexo A
Este anexo está dirigido a usuarios nuevos de PARCSIM e incluye una guı́a
práctica de formación con indicaciones paso a paso del uso del software, desde
la captura del problema a estudiar hasta el proceso de simulación y posterior
análisis de resultados.
A.1.1 Funciones
271
Capı́tulo A: Simulador: Manual de uso
mediante una clave (como por ejemplo MATADD, MATTRN, MATMUL y DGETRF,
en el caso de las mencionadas).
A.1.3 Modelos
A.1.4 Grupos
Los Grupos en el simulador son los diferentes subsistemas o módulos en los que
se divide un algoritmo. El usuario define los cálculos que se deben ejecutar para
resolver cada uno de dichos grupos, lo cual se realiza por medio de la asignación de
una rutina de usuario. Por ejemplo, un problema que suma y multiplica dos con-
juntos de matrices se podrı́a representar por medio de dos grupos que contengan
la rutina ADDMUL, cada una de ellos operando sobre uno de los conjuntos.
272
A.1. Conceptos básicos
A.1.5 Variables
Las Variables se usan para identificar a las matrices que se usarán como ar-
gumentos o parámetros de las funciones que el usuario utiliza en PARCSIM para
simular un determinado modelo. Las variables no hacen referencia al tamaño o
formato de dichas matrices.
A.1.6 Escenarios
A.1.7 Scripts
A.1.8 Rutas
273
Capı́tulo A: Simulador: Manual de uso
274
A.4. Interfaz gráfico de PARCSIM-MB: vista general
PARCSIM-MB 1 - X
6 6a 6b
Figura A.1: Vista esquemática del interfaz gráfico que ofrece PARCSIM-MB (Mo-
del Builder).
2 Una barra de menús con los accesos a las funcionalidades del software. Está
organizada en submenús, como se verá en detalle en la sección A.5.
3 Un cuadro de texto que muestra el nombre del modelo que se está editando.
Al inicio de la aplicación, o cuando no hay ningún modelo activo, se muestra
el mensaje No model selected.
275
Capı́tulo A: Simulador: Manual de uso
4 Una barra de herramientas que contiene una selección de los accesos directos
a las utilidades usadas más habitualmente por un usuario.
6a) Una barra de herramientas que contiene accesos directos a las uti-
lidades que permiten modificar la visualización del grafo, como por
ejemplo girarlo o cambiar su tamaño. Las funcionalidades incluidas en
estos accesos directos se pueden consultar en detalle en la sección A.7.
7 Una barra de estado que muestra información del hardware y del sistema
operativo sobre el que se está ejecutando PARCSIM-MB. Incluye informa-
ción sobre la memoria consumida por el software.
Contiene utilidades que permiten trabajar con los ficheros que almacenan los
modelos de usuario. Incluye la creación, borrado y actualización de los mismos,
ası́ como un enlace para el cierre de la aplicación:
276
A.5. Barra de menús
277
Capı́tulo A: Simulador: Manual de uso
Este submenú incluye acciones que tienen efecto sobre el modelo activo:
278
A.5. Barra de menús
Details: Este modo usa toda la ventana de la aplicación para mostrar los
detalles del modelo, los grupos que lo forman, los escenarios, los scripts y
los parámetros de configuración del simulador.
279
Capı́tulo A: Simulador: Manual de uso
El área de trabajo es la sección del interfaz gráfico donde el usuario crea los
modelos, los escenarios y los scripts, y donde se pueden ajustar los parámetros
que configuran el simulador. Está organizada mediante pestañas que facilitan la
agrupación y el acceso a los diferentes elementos que se pueden modificar. A
continuación se describen las diferentes vistas que se activan al seleccionar cada
una de dichas pestañas, y la información contenida en todas ellas.
280
A.6. Área de trabajo
Size variables Delete unused Model variables Select All None Alternate
Cols
4 Apply
2 1 3
281
Capı́tulo A: Simulador: Manual de uso
Group name Delete Group Parameters Delete unused Delete all Routine/Model
Routine Clone Group F(x) Parameter Variable name
2 Model Add a child
Branch
Successors
Group Name
Delete
4
3 Delete
5
Add
282
A.6. Área de trabajo
Add a child : Crea un nuevo grupo como hijo del grupo seleccionado y añade
automáticamente la unión entre ambos. El sistema propone como nombre
del nuevo grupo la letra G seguida de un número entero secuencial, y solicita
al usuario que modifique o confirme dicho nombre mediante una ventana de
diálogo.
New final group : Esta utilidad crea un nodo que actuará como cierre del
algoritmo, por lo que todos los grupos que en este momento no tengan
sucesor añaden al nuevo grupo como tal. El sistema propone como nombre
del nuevo grupo la letra G seguida de un número entero secuencial, y espera
a que el usuario modifique o confirme dicho nombre. El grupo recién creado,
al ser el final del algoritmo, no tendrá sucesores.
En 4 se indican los argumentos que usarán las funciones que se van a ejecutar
en cada grupo. Se seleccionan mediante un desplegable que muestra todas las
variables que se han creado en el correspondiente editor, como se describió en la
sección A.6.1. El sistema solicita tantos como requieran las funciones incluidas
en la rutina o modelo del grupo activo. Se añaden los botones Deleted unused y
Delete all que permiten borrar los que no se vayan a usar, o todos ellos.
283
Capı́tulo A: Simulador: Manual de uso
Size variables Matrix Types Sparsity Random All None Delete Scenario
Name Value Var Name Rows Cols Random Reuse Matrix file folder
Create Open View
2 3 4 Create Open
5 View
284
A.6. Área de trabajo
Routine name
Component Iter
Delete
2 Delete
Add
En 2 se añaden los cálculos que contiene dicha rutina (el editor les denomina
Components). El desplegable muestra las funciones incorporadas en el simulador
y las rutinas previamente creadas. Una vez seleccionada una función o una rutina,
se añaden mediante el botón Add . Es posible añadir la misma función o rutina
más de una vez. Para cambiar el orden en el que se ejecutan los componentes se
usan los botones ↑ y ↓ . En el campo Iter se indica cuántas iteraciones/veces
hay que repetir un determinado componente (función o rutina anidada). Esta
operación permite simular procesos iterativos como el de Newton-Raphson. El
área etiquetada con 3 muestra un grafo actualizado con las funciones que forman
la rutina y su ordenación.
285
Capı́tulo A: Simulador: Manual de uso
Los scripts son los grupos de parámetros algorı́tmicos usados durante la si-
mulación. Incluyen el número de threads de primer y segundo nivel, el número
de GPUs y el tipo de librerı́a a emplear. El simulador ejecutará el modelo para
cada combinación de parámetros algorı́tmicos. El primer nivel de paralelismo se
usa para la paralelización explı́cita (solución simultánea de grupos) y el segundo
nivel para la implı́cita (para ejecución de cálculos en librerı́as que lo permiten).
Se podrı́a utilizar el paralelismo explı́cito para dividir, además de la ejecución de
grupos en paralelo, la resolución de un problema en diferentes tramos. Por ejem-
plo, para resolver la cinemática de un cuadrilátero articulado, cuando la manivela
gira desde 0o hasta 360o en tramos entre 0-90o , 90-180o , 180-270o y 270-360o .
El usuario puede crear cualquier número de scripts por medio del correspon-
diente botón New Script del interfaz gráfico mostrado en la figura A.7. El sistema
propone por defecto un nuevo nombre compuesto por la letra S seguida de un
número secuencial que se muestra al usuario en una ventana de diálogo, donde
puede ser modificado.
3 5
Delete Delete Delete Delete
286
A.6. Área de trabajo
La información que incluye cada script define el conjunto de valores que pueden
adoptar los parámetros algorı́tmicos. Estos se pueden introducir en dos formatos:
287
Capı́tulo A: Simulador: Manual de uso
Library
2 Simulation mode
4 5 6
Simulator paths
PARCSIM-RUN executable Open
Figura A.8: Vista del editor de las opciones de configuración del simulador.
288
A.6. Área de trabajo
• Número de cores.
289
Capı́tulo A: Simulador: Manual de uso
La zona inferior del interfaz del editor incluye un visor donde se muestra el
grafo del modelo, que es actualizado dinámicamente conforme el usuario modifica
los grupos o los escenarios. Para cada grupo se visualizan su nombre y la rutina que
resuelve. El visor incluye una barra de botones con funcionalidades que modifican
y permiten ajustar el aspecto del grafo:
La casilla Show params se usa para hacer que el grafo muestre en cada
nodo las funciones, todos sus parámetros y los tamaños de las matrices para
cada escenario asociado al modelo activo.
290
A.8. Lección paso a paso
Esta sección está planteada como una guı́a práctica para el uso del simulador
PARCSCIM. En ella se describen todos los pasos que se siguen desde la construc-
ción de un modelo hasta su simulación. Por último, se realiza una introducción a
la herramienta de análisis de los tiempos de ejecución obtenidos en simulaciones
empleando diferentes tamaños de problema, parámetros de paralelismo y librerı́a
de cómputo.
A1 A2 A3 B1 B2
...
...
...
291
Capı́tulo A: Simulador: Manual de uso
Inicio
Inicio
C ← A1+A2 1
C ← A1+A2
X1 ← C-1 B1
X1 ← C-1 B1
2
X2 ← A2 B2 -1 X2 ← A2-1 B2
4
T ← A3T
D ← X1+X2 3
D ← X1+X2
T ← A3T
5
R ← T-1 D R ← T-1 D
Fin Fin
(a) Secuencial (b) Basado en grupos
292
A.8. Lección paso a paso
La figura A.12 muestra las opciones del menú que se encuentran activas en
este estado, sin ningún modelo activo.
293
Capı́tulo A: Simulador: Manual de uso
Teclear nombre
Aceptar
Tras ello, los enlaces a las zonas del área de trabajo para la creación de va-
riables, grupos, escenarios, rutinas y scripts quedan habilitados, y las etiquetas
nos indican que el modelo aún está vacı́o y que por tanto contiene 0 grupos, 0
escenarios y 0 scripts (figura A.14).
294
A.8. Lección paso a paso
295
Capı́tulo A: Simulador: Manual de uso
En caso de tener que cambiar el nombre del grupo, basta con editarlo en la caja
de texto etiquetada como “Group Name”. El grafo se actualizará automáticamente
al acabar la modificación para mostrar el nuevo nombre.
296
A.8. Lección paso a paso
A diferencia del grupo Inicio, el Grupo1 realiza dos operaciones, una suma
de matrices y una resolución de un sistema de ecuaciones. En PARSCIM, la
manera de informar al simulador de los cálculos que debe realizar un grupo es
asociarle una rutina.
Para crear una rutina debemos tener acceso a la vista de gestión de rutinas
haciendo clic sobre la etiqueta “Routines”, como se muestra en la figura A.19. El
número entre paréntesis junto al texto Routines nos indica el número de rutinas
creadas hasta este momento. Las rutinas no están asociadas a un modelo concreto.
Por tanto, éstas pueden ser reutilizadas en la resolución de otros problemas que
se introduzcan en el simulador posteriormente.
297
Capı́tulo A: Simulador: Manual de uso
Para incluir las funciones que se ejecutan en esta rutina seguiremos los pasos
que se detallan a continuación, y que están reflejados en la figura A.21. En primer
lugar añadimos la función suma de matrices, que en el simulador tiene el nombre
MADADD:
298
A.8. Lección paso a paso
2 Se hace clic sobre la función MADADD, que quedará seleccionada para ser
añadida a la rutina.
1
4
2 3
Este proceso puede repetirse tantas veces como sea necesario. Junto al nombre
de la función se muestran los botones Delete , ↑ y ↓ , que permiten eliminar la
función de esta rutina y modificar el orden en el que se ejecuta.
Del mismo modo que hemos añadido la función MADADD, añadimos la función
SOLVESYS. Una vez realizado, la rutina contendrá las dos funciones requeridas,
como muestra la figura A.22. Se observa a la derecha de la imagen el gráfico de
las funciones y la relación entre ellas.
Figura A.22: Interfaz gráfico actualizado para mostrar la rutina ADD_SYS que
incluye a las funciones MATADD y SOLVESYS.
299
Capı́tulo A: Simulador: Manual de uso
2 3
4
2 Seleccionamos el grupo al que le vamos asociar una rutina. Para ello po-
demos hacer clic en el desplegable de grupos, o directamente sobre el nodo
representado en la ventana del grafo.
4 Se hace clic sobre la rutina que queremos asociar al Grupo1 (en este caso
ADD_SYS).
300
A.8. Lección paso a paso
Figura A.24: Interfaz gráfico donde se muestra un grupo con una rutina asignada,
detalle de las funciones asociadas y el grafo que muestra la secuencia de cálculos.
Una vez creados los dos primeros grupos ya podemos indicarle al simulador
que el Grupo1 se debe ejecutar después del grupo Inicio. Para crear esta
dependencia es necesario seguir los pasos que se detallan a continuación, y que se
pueden consultar también en la figura A.25:
301
Capı́tulo A: Simulador: Manual de uso
4
3
2
302
A.8. Lección paso a paso
Para conocer el motivo del error podemos hacer clic sobre el icono de
la barra de herramientas o navegar al menú Model→ . Con ello
obtenemos un mensaje del software con una descripción del motivo del error.
Como vemos en la figura A.27, PARCSIM informa de que no existe en el modelo
un grupo “Final”, un grupo de cierre del algoritmo. Como veremos después, para
indicar que un determinado grupo es el último del algoritmo, se le asigna un
sucesor ficticio, un grupo denominado DUMMY, que es creado automáticamente
por el software.
303
Capı́tulo A: Simulador: Manual de uso
: Esta utilidad permite crear un nuevo grupo como hijo del grupo
seleccionado, generando automáticamente la dependencia entre ambos. El
sistema propone como nombre del nuevo grupo la letra G seguida de un
número entero secuencial y espera que el usuario modifique o confirme dicho
nombre mediante una ventana de diálogo.
En esta ocasión vamos a clonar el Grupo1, creando dos nuevos grupos que se
encuentran al mismo nivel (que tienen el mismo predecesor). Para ello debemos
proceder como indica la figura A.28:
1 Seleccionar el grupo que queremos clonar, por ejemplo haciendo clic sobre
el Grupo1 en la ventana del grafo.
3 Indicar el número de copias a realizar (en este ejemplo queremos crear dos)
y desmarcar la opción de copiar los sucesores, manteniendo marcada la de
predecesores (únicamente queremos que dependan del mismo grupo).
1 2
3
Figura A.28: Creación de grupos mediante el procedimiento de clonado.
Este proceso habrá creado dos nuevos grupos G3 y G4. Una vez creados,
podemos modificar lo que sea necesario. Por ejemplo, el recién creado G3 lo re-
nombraremos como Grupo2. Además, como el proceso de clonado crea los grupos
con la misma rutina que el grupo original, en el caso del Grupo2 esta deberá ser
modificada. Como en este momento aún no hemos creado su rutina, simplemente
le quitaremos la incorrecta. Posteriormente crearemos la suya y se la asignare-
mos. Para realizar estos cambios seguimos los siguientes pasos que muestra la
figura A.29:
304
A.8. Lección paso a paso
1 Seleccionamos el grupo que queremos editar (en este momento el G3) ha-
ciendo clic sobre él en la ventana del grafo.
2
3
1 Modificar el nombre
propuesto por defecto
Aceptar
305
Capı́tulo A: Simulador: Manual de uso
Una vez creado el Grupo3, como sucesor del Grupo1, ya estamos en dispo-
sición de poder añadirlo también como sucesor del Grupo2. Procedemos de un
modo similar a como se describió en la sección A.8.7. El G4 se renombra también,
en este caso como Grupo4, y se eliminan las rutinas que se han clonado. Como
resultado, el grafo del modelo quedará como el que muestra la figura A.31.
Figura A.31: Grafo que muestra un modelo aún incompleto del algoritmo mos-
trado en la figura A.10(b).
Con las herramientas incluidas en PARCSIM para crear grupos descritas en las
secciones precedentes es posible crear el resto de grupos necesarios para completar
el algoritmo descrito en la figura A.10(b) y obtener un grafo como el mostrado
en la figura A.32.
306
A.8. Lección paso a paso
Figura A.32: Grafo con todos los grupos que componen el modelo del ejemplo de
la figura A.10(b), a falta de la creación de un grupo final.
Queda pendiente añadir el grupo que completa el algoritmo, que será un gru-
po final, sin sucesores. El modo de indicar que un grupo no tiene sucesores es
asignarle un sucesor ficticio denominado DUMMY, un grupo que el simulador tiene
implementado por defecto. Sin embargo, una opción más directa es utilizar la
herramienta para crear grupos finales, como se muestra en la figura A.33:
1
2 3
Modificar el nombre
Aceptar
propuesto por defecto
1 Haciendo clic en New Final Group se crea un grupo final y se hace que
todos los grupos que en ese momento no tienen sucesor añadan al nuevo
grupo como tal.
La figura A.34 muestra el grafo de nuestro modelo con todos los grupos re-
queridos en nuestro algoritmo.
307
Capı́tulo A: Simulador: Manual de uso
Figura A.34: Grafo completo con todos los grupos que componen el modelo del
algoritmo de la figura A.10(b).
Para poder completar la creación del modelo que representa nuestro algorit-
mo debemos crear las rutinas que se deben asignar a los grupos que están aún
incompletos:
El grupo Grupo3, que resuelve una suma de matrices: Crearemos una rutina
a la que le daremos el nombre ADD.
Una vez creadas todas las rutinas siguiendo los mismos pasos que en la sec-
ción A.8.5, podemos asignarlas a los grupos correspondiente como hicimos en la
sección A.8.6. Una vez completado este ejercicio, nuestro modelo tendrá el aspecto
mostrado en la figura A.35.
308
A.8. Lección paso a paso
Figura A.35: Grafo con todos los grupos y las rutinas que componen el modelo
del ejemplo.
referentes a la estructura del modelo. Esto es debido a que está bien construido,
pues todos los grupos tienen un sucesor y existe un grupo que marca el fin del
algoritmo. Sin embargo obtenemos nuevos avisos. En el ejemplo de la figura A.36 el
software nos recuerda que la rutina ADD_SYS asociada al grupo Grupo1 no tienen
definidos todos los valores de sus parámetros (los argumentos de las funciones que
lo componen).
Figura A.36: Error obtenido al comprobar los argumentos de las funciones que se
ejecutan en los grupos.
309
Capı́tulo A: Simulador: Manual de uso
Figura A.37: Visor del grafo ampliado que permite visualizar los parámetros de
las funciones.
310
A.8. Lección paso a paso
Se crea una
2 Click en la línea libre 3 Teclear nombre 4 Pulsar “ENTER” 5 nueva línea libre
Repetimos este proceso para crear el resto de variables que representan a las
matrices {A2, A3,C, T } y a los vectores {B1, B2, X1, X2, D, R}. Observamos cómo
el sistema añade las variables a la lista en orden alfabético.
Para editar una variable ya creada, se puede hacer doble-clic sobre su identi-
ficador para activar el modo de edición.
311
Capı́tulo A: Simulador: Manual de uso
Filas(A1)i = xi ∀i
Filas(A2)i = xi ∀i
Filas(C)i = xi ∀i
Columnas(A1)i = xi ∀i
Columnas(A2)i = xi ∀i
Columnas(C)i = xi ∀i
Sin embargo, podrı́amos crear una variable t y realizar las siguientes asignaciones:
Filas(A1) = t
Filas(A2) = t
Filas(C) = t
Columnas(A1) = t
Columnas(A2) = t
Columnas(C) = t
Si analizamos los cálculos que se realizan usando las matrices en el modelo del
ejemplo, como hemos hecho con A1, B2 y C, observamos que podemos especificar
los tamaños con tan solo dos variables de tamaño. Podemos llamar a estas varia-
bles sizeMat y sizeOne. En la tabla A.1 se muestran las variables del modelo y
312
A.8. Lección paso a paso
las variables de tamaño que sirven para establecer su número de filas y columnas.
Se muestran dos posibles escenarios (Escenario-1 y Escenario-2) donde,
variando únicamente el valor de una variable de tamaño, se establece el formato
de todas las matrices.
Escenario-1 Escenario-2
Variable sizeMat= 20 sizeMat= 100
Filas Columnas
del modelo sizeOne= 1 sizeOne= 1
A1 sizeMat sizeMat 20 × 20 100 × 100
A2 sizeMat sizeMat 20 × 20 100 × 100
A3 sizeMat sizeMat 20 × 20 100 × 100
B1 sizeMat sizeOne 20 × 1 100 × 1
B2 sizeMat sizeOne 20 × 1 100 × 1
C sizeMat sizeMat 20 × 20 100 × 100
D sizeMat sizeOne 20 × 1 100 × 1
R sizeMat sizeOne 20 × 1 100 × 1
T sizeMat sizeMat 20 × 20 100 × 100
X1 sizeMat sizeOne 20 × 1 100 × 1
X2 sizeMat sizeOne 20 × 1 100 × 1
Tabla A.1: Variables del modelo para el algoritmo de la figura A.10(b). Dos va-
riables de tamaño (sizeMat y sizeOne) son suficientes para establecer las
dimensiones de las matrices. Se muestran dos escenarios con diferentes valores de
sizeMat.
313
Capı́tulo A: Simulador: Manual de uso
5 Automáticamente se crea una nueva lı́nea en blanco que nos permite conti-
nuar añadiendo variables.
Se crea una
2 Click en la línea libre 3 Teclear nombre 4 Pulsar “ENTER” 5 nueva línea libre
Repetimos este proceso para crear la variable sizeOne. Para editar una va-
riable ya creada, se puede hacer doble-clic sobre su identificador para activar el
modo de edición.
SizeMat SizeMat
SizeMat
SizeOne
SizeMat
Asistente
314
A.8. Lección paso a paso
1
2 3
4
315
Capı́tulo A: Simulador: Manual de uso
Una vez creadas todas nuestras variables, ya podemos asignarlas como argu-
mentos a las funciones que se van a ejecutar en nuestro modelo. La asignación en
PARCSIM-MB se realiza mediante controles desplegables que muestran la lista
de variables de modelo disponibles (figura A.43).
Variables disponibles
316
A.8. Lección paso a paso
1 2 3
Repitiendo el proceso hasta completar todos los parámetros del grupo Grupo1,
con la casilla etiquetada como Show params. marcada, obtenemos el resultado
que se muestra en la figura A.45.
317
Capı́tulo A: Simulador: Manual de uso
Figura A.46: Mensaje de error por falta de parámetros en la rutina que ejecuta
el Grupo2.
Una vez capturados los parámetros en todos los grupos que forman el modelo,
cuando verificamos el modelo obtendremos un mensaje de ausencia de errores,
como el que se muestra la figura A.47.
Figura A.47: Modelo completo donde todas las funciones tienen asignados sus
argumentos.
A.8.17 Rutas
318
A.8. Lección paso a paso
6 7
2 3 4 5
1
Figura A.48: Rutas de resolución para el modelo de la figura A.10(b). Se ha
resaltado la ruta 2, que incluye el cálculo simultáneo de los grupos Grupo3 y
Grupo4.
319
Capı́tulo A: Simulador: Manual de uso
: Ajusta el tamaño del árbol de manera que todos los nodos sean
visibles.
320
A.8. Lección paso a paso
321
Capı́tulo A: Simulador: Manual de uso
El número entre paréntesis en la etiqueta indica los escenarios que hay defini-
dos para este modelo en este momento.
4
1
3
322
A.8. Lección paso a paso
Figura A.52: Vista del grafo del modelo que muestra el escenario recién creado.
Editar el valor
5
1
4
3
2
5 6 7 8
Figura A.53: Edición de los valores de un escenario.
323
Capı́tulo A: Simulador: Manual de uso
324
A.8. Lección paso a paso
325
Capı́tulo A: Simulador: Manual de uso
326
A.8. Lección paso a paso
otro de su elección (el software comprobará que no haya sido usado anteriormente
en el mismo modelo). En este ejemplo escribimos ScriptTutorial1 y pulsamos
Aceptar , como vemos en la figura A.57.
Teclear nombre
Aceptar
Figura A.57: Captura del nombre de un nuevo script durante su proceso de crea-
ción.
1
2
3 4
5 7
6 8
327
Capı́tulo A: Simulador: Manual de uso
1
La introducción de rangos La introducción de valores
deshabilita la captura de individuales deshabilita la
valores individuales captura de rangos
2
328
A.8. Lección paso a paso
Parámetro
Ejecución OMP1 OMP2
1 1 1
2 1 3
3 2 1
4 2 3
5 3 1
6 3 3
7 4 1
8 4 3
PARCSIM permite acotar las combinaciones para que cumplan una determi-
nada condición. Por ejemplo, en el caso de disponer de un máximo de 4 cores,
los pares de threads OMP1 × OMP2 {2, 3}, {3, 3} y {4, 3} crearı́an un número de
threads superior a ese valor de 4. Para validar las combinaciones de parámetros
podemos crear una formula que exprese una condición. En este caso particular
serı́a:
329
Capı́tulo A: Simulador: Manual de uso
DobleClick en DobleClick
1 la línea libre 2 Escribir nombre 3 en el valor 4 Escribir valor
1 Hacemos doble clic sobre la lı́nea en blanco para iniciar el modo de edición.
3 Hacemos doble clic sobre el campo del valor para iniciar el modo de edición.
Una vez creada una constante, la podemos usar en nuestra fórmula. La figu-
ra A.61 muestra una ecuación que relaciona dicha constante con el número total
de threads activos, obtenidos al combinar los de primer nivel (según indica el pa-
rámetro OMP1) y los de segundo nivel de paralelismo (parámetro OMP2). También
se puede usar el parámetro del número de GPUs para crear reglas en referencia
al número de GPUs instaladas.
330
A.8. Lección paso a paso
Figura A.61: Validación de los valores de los scripts mediante fórmulas. El número
de threads combinados a partir de los del primer nivel (valor de OMP1) y del
segundo nivel (valor de OMP2) se limitan al valor 4 de la constante maxthreads.
331
Capı́tulo A: Simulador: Manual de uso
1
4
2
3
Figura A.63: Selección del directorio de ubicación del ejecutable del simulador.
332
A.8. Lección paso a paso
Como paso previo adicional antes de lanzar una simulación, existen tres pará-
metros que se deben establecer y que son accesibles en la vista de configuración,
como vemos en la figura A.64:
1
2 3
Figura A.64: Selección de los parámetros que determinan la ejecución del simu-
lador.
333
Capı́tulo A: Simulador: Manual de uso
En este modo se ejecutan de manera individual todas las funciones que es-
tán definidas en el simulador, o una selección de ellas. Los cálculos se repiten
para todos los escenarios y scripts de entrenamiento, y los resultados quedan
almacenados en la base de datos de autooptimización. El modo se selecciona
haciendo clic sobre el desplegable etiquetado como “Simulation mode” y seleccio-
nando la opción Training mode. El conjunto de scripts y escenarios de entre-
namiento se capturan en una vista especial a la que se accede haciendo clic en
Training→ . La figura A.65 muestra la información gestionada
en esta vista:
334
A.8. Lección paso a paso
2 3
Teclear un número
1
Figura A.66: Proceso de captura de un nuevo escenario de entrenamiento.
335
Capı́tulo A: Simulador: Manual de uso
4 Haciendo clic sobre este icono se mostrarán los valores de una matriz alma-
cenados en un archivo binario dentro de la carpeta de ejecución del simu-
lador, y que corresponda a las dimensiones, tipologı́a y factor de dispersión
del escenario correspondiente a la lı́nea del icono.
336
A.8. Lección paso a paso
En este modo el software usa unos valores especı́ficos de los parámetros algo-
rı́tmicos, que es necesario capturar en la pantalla de configuración como muestra
la figura A.68:
1 2 3
4
Figura A.68: Captura de la configuración y los parámetros algorı́tmicos aplicables
al modo de simulación simple.
En este modo el simulador accede a los ficheros de scripts creados por el usuario
para obtener de ellos los valores de los parámetros algorı́tmicos, y ejecuta los
cálculos con todas las combinaciones que genera a partir de ellos. En la tabla A.2
337
Capı́tulo A: Simulador: Manual de uso
vimos un ejemplo de pares obtenidos con los valores {1, . . . , 4} del parámetro
threads OMP1 y los valores {1, 3} del parámetro threads OMP2.
2
3
338
A.8. Lección paso a paso
A.8.25 Simulación
1 4
2
3
339
Capı́tulo A: Simulador: Manual de uso
5 Haciendo clic sobre dicho botón comienza la ejecución, y el visor muestra los
mensajes que el software genera para informar del estado de la simulación.
2 1
340
A.8. Lección paso a paso
1 2
3 4
341
Capı́tulo A: Simulador: Manual de uso
Figura A.73: Datos del script para una simulación en Multiple mode.
Por último, y dado que queremos simular el modelo sobre una ruta de-
terminada seleccionada por nosotros, debemos ir de nuevo al modelo para
asegurarnos de que dicha ruta está preseleccionada. Para ello seguimos los
pasos descritos en la sección A.8.17, como muestra la figura A.74.
Figura A.74: Selección de una ruta para una simulación en Multiple mode.
342
A.8. Lección paso a paso
1 2 3
343
Capı́tulo A: Simulador: Manual de uso
1 2
3 Seleccionamos el modelo.
Como vemos en la figura A.77, el software muestra una tabla con los registros
que satisfacen los filtros aplicados. Esta información se organiza en cuatro grandes
bloques:
344
A.8. Lección paso a paso
Tiempo de ejecución
Parámetros
1 Modelo y ruta 2 Escenario 3 algorítmicos 4 desglosado por
grupos y funciones
1 Información sobre la ruta usada por el simulador, y que muestra todos los
grupos del modelo con la siguiente codificación:
Signo + que separa los códigos de los grupos que se han calculado en
paralelo, en una misma etapa de tiempo.
Signo - separa etapas de tiempo.
Se pueden aplicar filtros sobre los valores de una o varias columnas de la tabla.
La figura A.78 muestra el modo de activarlos:
345
Capı́tulo A: Simulador: Manual de uso
1
2 Restablecer filtro
3 Celdas vacías
4 Selección de valores
2 En caso de que hubiera una selección anterior, esta opción permite resta-
blecerla.
4 Aquı́ vemos la lista de todos los valores de dicha columna, y nos permite
mostrar únicamente los registros que contienen un cierto valor.
3 Obtenemos una gráfica con los valores medios, para cada tamaño de las ma-
trices. Dado que hemos simulado solo un escenario, obtenemos solo un con-
junto de puntos, que representan los tiempos de ejecución para el
Escenario-1, con tamaño de matrices de 20 × 20.
346
A.8. Lección paso a paso
5 Se incluye una tabla que muestra, además del valor medio mostrado en la
gráfica, los valores mı́nimos y máximos.
3
4
5
7
6
Figura A.79: Consulta gráfica de los tiempos de ejecución en función de los pa-
rámetros algorı́tmicos. Se muestran datos obtenidos en la primera simulación en
modo múltiple.
347
Capı́tulo A: Simulador: Manual de uso
antes de proceder a realizar los cálculos. Este proceso de estimación, que fue
descrito en la sección 5.5.4, necesita disponer de los tiempos de entrenamiento de
las funciones implementadas en el simulador. La obtención de dichos tiempos se
realiza ejecutando el simulador en el modo de entrenamiento.
348
A.8. Lección paso a paso
1
2 3 2 3
Figura A.83: Resultados obtenidos en una simulación múltiple con selección au-
tomática de rutas. El software ha detectado tres posibles rutas en relación con
los parámetros algorı́tmicos aplicados.
De entre todas las obtenidas, la ruta que supone un menor tiempo de eje-
cución es la que ejecuta en paralelo los grupos {Grupo1, Grupo2} y los grupos
{Grupo3, Grupo4} en la etapa siguiente, con asignación de 3 threads al primer ni-
vel de paralelismo usando la librerı́a con identificador 1 (que corresponde a MKL,
como indica la tabla 5.1).
349
Capı́tulo A: Simulador: Manual de uso
350
A.8. Lección paso a paso
Figura A.86: Obtención de las tres rutas teóricamente más eficientes. El cuadro
de texto ofrecido en el visor de rutas muestra los tiempos obtenidas con cada
ruta, ordenados de menor a mayor, y las diferencias entre ellas.
351
Capı́tulo A: Simulador: Manual de uso
En las rutinas es posible indicar el modo en el que los valores de los argumentos
de salida de unas funciones pueden asignarse a argumentos de entrada de otras
funciones que se ejecutan posteriormente en la misma rutina. Para mostrarlo
partimos de una sencilla rutina creada a modo de ejemplo, que se muestra en la
figura A.87.
Del mismo modo que hemos creado el enlace anterior, podemos crear otro más
para obtener un resultado como el de la figura A.89.
352
A.8. Lección paso a paso
Figura A.89: Rutina de ejemplo que muestra dos enlaces entre parámetros.
En este apartado mostramos un ejemplo de una rutina anidada que hace uso
de la que hemos creado en la sección anterior para mostrar el modo de esta-
blecer enlaces entre los parámetros. En el grafo de la figura A.90 se encuentran
representados todos los elementos que componen esta nueva rutina: las funciones
MATADD, MATTRN y SOLVESYS, y la rutina Demo que se usa en tres ocasiones.
Las funciones se representan mediante bloques bordeados con una lı́nea continua.
Las rutinas lo hacen con lı́neas discontinuas. El enlace entre los parámetros se
indica mediante lı́neas dirigidas de color verde cuando corresponden a la rutina
anidada, y en color rojo si son enlaces creados para la rutina en curso.
353
Capı́tulo A: Simulador: Manual de uso
Parámetros Parámetros
enlazados en la enlazados en la
rutina principal rutina anidada
Figura A.90: Ejemplo de rutina anidada con enlace entre argumentos propios y
heredados de la rutina anidada.
354
A.8. Lección paso a paso
355
Capı́tulo A: Simulador: Manual de uso
Figura A.93: Modificación del modelo Tutorial que incluye un nuevo Grupo6
que resuelve una multiplicación de matrices.
356
A.8. Lección paso a paso
1
2
Figura A.95: Interfaz que muestra el modelo MATMUL_COLS50_G1 para ser eje-
cutado en el Grupo6.
357
Capı́tulo A: Simulador: Manual de uso
La selección de una rama modifica de nuevo el grafo para reflejar esta infor-
mación (figura A.97).
Figura A.97: Grafo del modelo Tutorial con el Grupo6 ejecutando una rama
del modelo MATMUL_COLS50_G1.
358
A.8. Lección paso a paso
Figura A.98: Arbol de rutas del modelo Tutorial con el Grupo6 ejecutando el
modelo MATMUL_COLS50_G1.
359
Capı́tulo A: Simulador: Manual de uso
¿Cómo debo copiar los modelos que he creado cuando quiero usarlos
en otro ordenador?
Los modelos creados en PARCSIM se almacenan en varios archivos de texto.
Todos ellos comienzan con el nombre del modelo y con una extensión que
indica el contenido:
Un archivo ModeloAnexo.mdl.
360
A.10. Software de terceros
• jgraph: Es una librerı́a Open Source para JAVA que permite crear
diagramas como los que utiliza el simulador poara mostrar los modelos
y el árbol de rutas. Web: https://github.com/jgraph/jgraphx
361
Capı́tulo A: Simulador: Manual de uso
362
A.11. Datos de contacto
363
Capı́tulo A: Simulador: Manual de uso
364
Bibliografı́a
[4] Emmanuel Agullo, Cédric Augonnet, Jack Dongarra, Hatem Ltaief, Ray-
mond Namyst, Samuel Thibault, and Stanimire Tomov. Faster, Cheaper,
Better - a Hybridization Methodology to Develop Linear Algebra Software
for GPUs. In GPU Computing Gems, volume 2. Morgan Kaufmann, 2010.
[5] Emmanuel Agullo, Jim Demmel, Jack Dongarra, Bilel Hadri, Jakub Kurzak,
Julien Langou, Hatem Ltaief, Piotr Luszczek, and Stanimire Tomov. Nume-
rical linear algebra on emerging architectures: The PLASMA and MAGMA
projects. Journal of Physics: Conference Series, 180(1):012037, 08 2009.
[7] Francisco Almeida, Domingo Giménez, José Miguel Mantas, and Antonio
Vidal. Introducción a la Programación Paralela. Paraninfo, 2008.
365
Bibliografı́a
[8] Pedro Alonso, Ravi Reddy, and Alexey Lastovetsky. Experimental Study
of Six Different Implementations of Parallel Matrix Multiplication on He-
terogeneous Computational Clusters of Multicore Processors. In 18th Eu-
romicro Conference on Parallel, Distributed and Network-based Processing,
pages 263–270, 2010.
[15] K.S. Anderson and S. Duan. A hybrid parallelizable low-order algorithm for
dynamics of multi-rigid-body systems: Part I, chain systems. Mathematical
and Computer Modelling, 30(9):193 – 215, 1999.
366
Bibliografı́a
[22] M. Asch, Terry Moore, Rosa M. Badia, Micah Beck, Peter H. Beckman,
T. Bidot, François Bodin, Franck Cappello, Alok N. Choudhary, Bronis R.
de Supinski, Ewa Deelman, Jack J. Dongarra, Anshu Dubey, Geoffrey C.
Fox, H. Fu, Sergi Girona, William Gropp, Michael A. Heroux, Yutaka Is-
hikawa, Katarzyna Keahey, David E. Keyes, Bill Kramer, J.-F. Lavignon,
Y. Lu, Satoshi Matsuoka, Bernd Mohr, Daniel A. Reed, S. Requena, Joel H.
Saltz, Thomas C. Schulthess, Rick L. Stevens, D. Martin Swany, Alexan-
der S. Szalay, William M. Tang, G. Varoquaux, Jean-Pierre Vilotte, Ro-
bert W. Wisniewski, Z. Xu, and Igor Zacharov. Big data and extreme-scale
computing. Int. J. High Perform. Comput. Appl., 32(4):435–479, 2018.
[23] Amir H. Ashouri, William Killian, John Cavazos, Gianluca Palermo, and
Cristina Silvano. A Survey on Compiler Autotuning using Machine Lear-
ning. ACM Computing Surveys, 51:96:1–96:42, 09 2018.
367
Bibliografı́a
[27] David Bailey, Robert Lucas, and Samuel Williams. Performance Tuning of
Scientific Applications. Chapman & Hall/CRC computational science, 11
2010.
[28] Gregory Baker, John Gunnels, Greg Morrow, Béatrice Rivière, and Robert
van de Geijn. PLAPACK: High Performance through High-Level Abstrac-
tion. In ICPP ’98, pages 414–422, 01 1998.
[30] Marcos Barreto, Murilo Boratto, Pedro Alonso, and Domingo Giménez.
Automatic routine tuning to represent landform attributes on multicore
and multi-GPU systems. The Journal of Supercomputing, 70(2):733–745,
03 2014.
[31] Tal Ben-Nun and Torsten Hoefler. Demystifying Parallel and Distributed
Deep Learning: An In-Depth Concurrency Analysis. ACM Comput. Surv.,
52(4), August 2019.
[32] Gregorio Bernabé, Raúl Hernández, and Manuel E. Acacio. Parallel imple-
mentations of the 3D fast wavelet transform on a raspberry pi 2 cluster. J.
Supercomput., 74(4):1765–1778, 2018.
[33] Jeff Bilmes, Krste Asanovic, Chee-Whye Chin, and Jim Demmel. Optimi-
zing matrix multiply using PHiPAC: A portable high-performance ANSI C
coding methodology. Proceedings of the International Conference on Su-
percomputing, pages 253–260, 07 1997.
368
Bibliografı́a
[37] BLAS Legacy Website. BLAS (Basic Linear Algebra Subprograms). http:
//www.netlib.org/blas/. Online; accedido 19-04-2020.
[40] BLAS Legacy Website. PBLAS: Parallel Basic Linear Algebra Subpro-
grams. http://www.netlib.org/scalapack/pblas qref.html. Online; accedido
19-04-2020.
[41] Blender Foundation. Blender: Free and Open Source 3D Creation Suite.
https://www.blender.org/. Online; accedido 13-04-2020.
[43] Murilo Boratto, Pedro Alonso, Domingo Giménez, and Alexey Lastovetsky.
Automatic tuning to performance modelling of matrix polynomials on mul-
ticore and multi-GPU systems. The Journal of Supercomputing, 73(1):227–
239, 01 2017.
369
Bibliografı́a
[47] Phillips C. and R. Harbor. Feedback Control Systems. Third Edition. Pren-
tice Hall, New Jersey, 1996.
[48] Jesús Cámara, Javier Cuenca, and Domingo Giménez. Integrating software
and hardware hierarchies in an autotuning method for parallel routines in
heterogeneous clusters. The Journal of Supercomputing, 76:9922–9941, 12
2020.
[51] Adrián Castelló, Rafael Mayo, Judit Planas, and Enrique S. Quintana-Ortı́.
Exploiting Task-Parallelism on GPU Clusters via OmpSs and rCUDA Vir-
tualization. In IEEE Trustcom/BigDataSE/ISPA, volume 3, pages 160–165,
2015.
[53] Rohit Chandra, Ramesh Menon, Leo Dagum, David Kohr, Dror Maydan,
and Jeff McDonald. Parallel Programming in OpenMP. Morgan Kauffman,
2001.
370
Bibliografı́a
[55] C. Chen, J. Chame, and M. Hall. Combining models and guided empirical
search to optimize for multiple levels of the memory hierarchy. In Interna-
tional Symposium on Code Generation and Optimization, pages 111–122,
2005.
[57] Jaeyoung Choi, Jack Dongarra, Susan Ostrouchov, Antoine Petitet, David
Walker, and R. Clinton Whaley. A proposal for a set of parallel basic linear
algebra subprograms. Technical Report CS-95-292, Computer Science Dept.
University of Tennesee, 05 1995.
371
Bibliografı́a
[64] Keith Cooper, Devika Subramanian, and Linda Torczon. Adaptive opti-
mizing compilers for the 21st century. The Journal of Supercomputing,
23(1):7–22, 08 2002.
372
Bibliografı́a
[72] Javier Cuenca, Luis Garcı́a, Domingo Giménez, and Jack Dongarra. Proces-
ses Distribution of Homogeneous Parallel Linear Algebra Routines on He-
terogeneous Clusters. In IEEE International Conference on Cluster Com-
puting, pages 1–10, 2005.
[73] Javier Cuenca, Luis-Pedro Garcı́a, and Domingo Giménez. A proposal for
autotuning linear algebra routines on multicore platforms. Procedia Com-
puter Science, 1:515–523, 05 2010.
[74] Javier Cuenca, Luis-Pedro Garcı́a, and Domingo Giménez. Improving Li-
near Algebra Computation on NUMA Platforms through Auto-tuned Nes-
ted Parallelism. In 20th Euromicro International Conference on Parallel,
Distributed and Network-Based Processing, pages 66–73, 2012.
[75] Javier Cuenca, Luis-Pedro Garcı́a, Domingo Giménez, José González, and
Antonio Vidal. Empirical Modelling of Parallel Linear Algebra Routines.
In 5th International Conference on Parallel Processing and Applied Mathe-
matics, volume 3019, pages 169–174, 2003.
[78] Javier Cuenca, Domingo Giménez, and José González. Modeling the beha-
viour of linear algebra algorithms with message-passing. In 9th Euromicro
Workshop on Parallel and Distributed Processing, pages 282–289, 2001.
373
Bibliografı́a
[80] Javier Cuenca, Domingo Giménez, José González, Jack Dongarra, and Ken-
neth Roche. Automatic Optimisation of Parallel Linear Algebra Routines
in Systems with Variable Load. In 11th Euromicro Conference on Parallel,
Distributed and Network-Based Processing, pages 409–416, 2003.
[88] James Dinan, Pavan Balaji, Darius Buntinas, David Goodell, William
Gropp, and Rajeev Thakur. An implementation and evaluation of the MPI
3.0 one-sided communication interface. Concurrency and Computation:
Practice and Experience, 28(17):4385–4404, 12 2016.
374
Bibliografı́a
[91] Jack Dongarra, Ian Foster, Geoffrey Fox, William Gropp, Ken Kennedy,
Linda Torczon, and Andy White. Sourcebook of Parallel Computing. Mor-
gan Kaufmann Publishers, 2003.
[92] Jack Dongarra, Mark Gates, Azzam Haidar, Yulu Jia, Khairul Kabir,
Piotr Luszczek, and Stanimire Tomov. HPC Programming on Intel Many-
Integrated-Core Hardware with MAGMA Port to Xeon Phi. In 10th In-
ternational Conference on Parallel Processing and Applied Mathematics,
PPAM, pages 571–581, 2013.
[93] Jack Dongarra and Piotr Luszczek. ScaLAPACK, pages 1773–1775. Sprin-
ger US, Boston, MA, 2011.
[94] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling, and Richard J. Han-
son. An Extended Set of FORTRAN Basic Linear Algebra Subprograms.
ACM Transactions on Mathematical Software, 14(1):1–17, 03 1988.
[95] Jack J. Dongarra and R. Clint Whaley. A User’s Guide to the BLACS
v1.0. Technical Report CS-95-292, Dept. of Computer Sciences, University
of Tennessee, Knoxville, TN 37996, 05 1997.
[96] John Drake, Philip Jones, Mariana Vertenstein, James White, and Patrick
Worley. Software Design for Petascale Climate Science, pages 125–146.
Chapman and Hall/CRC, 01 2008.
[97] José Duato, Antonio J Peña, Federico Silla, Rafael Mayo, and Enrique S.
Quintana-Ortı́. rCUDA: Reducing the number of GPU-based accelerators
in high performance clusters. In International Conference on High Perfor-
mance Computing and Simulation, HPCS, pages 224–231, 2010.
[98] Nicolas Dupin and El-Ghazali Talbi. Parallel matheuristics for the discrete
unit commitment problem with min-stop ramping constraints. Int. Trans.
Oper. Res., 27(1):219–244, 2020.
375
Bibliografı́a
[101] Stéphane Eranian. The perfmon2 interface specification. In 7th Linux Sym-
posium, 2005.
[102] Mokhtar Essaid, Lhassane Idoumghar, Julien Lepagnot, and Mathieu Bré-
villiers. GPU parallelization strategies for metaheuristics: a survey. In-
ternational Journal of Parallel, Emergent and Distributed Systems, pages
1–26, 01 2018.
[105] Jianbin Fang, Ana Lucia Varbanescu, Baldomero Imbernón, José-Marı́a Ce-
cilia, and Horacio Emilio Pérez Sánchez. Parallel Computation of Non-
Bonded Interactions in Drug Discovery: Nvidia GPUs vs. Intel Xeon Phi.
In 2nd International Conference on Bioinformatics and Biomedical Engi-
neering, pages 579–588, 2014.
376
Bibliografı́a
[109] Len Freeman and Chris Phillips. Parallel Numerical Algorithms. Prentice
Hall, 1992.
[110] Marc Freese, Surya Singh, Fumio Ozaki, and Nobuto Matsuhira. Virtual
Robot Experimentation Platform V-REP: A Versatile 3D Robot Simula-
tor. In Proceedings of the Second International Conference on Simulation,
Modeling, and Programming for Autonomous Robots, page 51–62. Springer-
Verlag, 2010.
[112] Matteo Frigo and Steven Johnson. FFTW: An adaptive software architectu-
re for the FFT. In Proceedings of the 1998 IEEE International Conference
on Acoustics, Speech and Signal Processing, volume 3, pages 1381–1384,
1998.
[113] Matteo Frigo and Steven G. Johnson. The design and implementation of
FFTW3. Proc. IEEE, 93(2):216–231, 2005.
[114] Grigori Fursin, Yuriy Kashnikov, Abdul Wahid Memon, Zbigniew Chams-
ki, Olivier Temam, Mircea Namolaru, Elad Yom-Tov, Bilha Mendelson,
Ayal Zaks, Eric Courtois, François Bodin, Phil Barnard, Elton Ashton, Ed-
win V. Bonilla, John Thomson, Christopher K. I. Williams, and Michael
F. P. O’Boyle. MILEPOST GCC: Machine Learning Enabled Self-tuning
Compiler. Int. J. Parallel Program., 39(3):296–327, 2011.
[115] Kyle Gallivan, William Jalby, Allen Malony, and Harry Wijshoff. Perfor-
mance Prediction for Parallel Numerical Algorithms. International Journal
of High Speed Computing, 1(3):31–62, 03 1991.
[117] Luis-Pedro Garcı́a, Javier Cuenca, and Domingo Giménez. Including Im-
provement of the Execution Time in a Software Architecture of Libraries
377
Bibliografı́a
[118] Luis-Pedro Garcı́a, Javier Cuenca, and Domingo Giménez. Using Expe-
rimental Data to Improve the Performance Modelling of Parallel Linear
Algebra Routines. In 7th International Conference on Parallel Processing
and Applied Mathematics, page 1150–1159, 2007.
[120] Javier Garcı́a de Jalón and Eduardo Bayo. Kinematic and Dynamic Simu-
lation of Multibody Systems: The Real Time Challenge. Springer-Verlag,
New York (USA), 1994.
[123] Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Man-
chek, and Vaidy Sunderam. PVM 3 User’s Guide and Reference Manual.
Technical Report ORNL/TM-12187, Mathematical Sciences Section, Oak
Ridge National Laboratory, Oak Ridge, TN 37831, 11 1995.
[124] Georgia Tech and Carnegie Mellon University. Dynamic Animation and
Robotics Toolkit. https://dartsim.github.io/. Online; accedido 13-04-2020.
[126] Sylvain Girbal, Nicolas Vasilache, Cédric Bastoul, Albert Cohen, David Pa-
rello, Marc Sigler, and Olivier Temam. Semi-automatic composition of loop
transformations for deep parallelism and memory hierarchies. International
Journal of Parallel Programming, 34:261–317, 06 2006.
378
Bibliografı́a
[127] Gene H. Golub and Charles F. Van Loan. Matrix Computations (Fourth
Edition). The John Hopkins University Press, 2013.
[128] Óscar Gómez, José-Juan López-Espı́n, and Antonio Peñalver Benavent. Pa-
rallel algorithm for prediction of variables in simultaneous equation models.
In 17th International Conference on High Performance Computing & Si-
mulation, HPCS 2019, Dublin, Ireland, July 15-19, 2019, pages 1032–1035.
IEEE, 2019.
[129] Martı́n González, Jose-Juan López-Espı́n, Juan Aparicio, and Domingo Gi-
ménez. A parallel application of matheuristics in data envelopment analysis.
In Fernando de la Prieta, Sigeru Omatu, and Antonio Fernández-Caballero,
editors, Distributed Computing and Artificial Intelligence, 15th Internatio-
nal Conference, DCAI 2018, Toledo, Spain, 20-22 June 2018, volume 800 of
Advances in Intelligent Systems and Computing, pages 172–179. Springer,
2018.
[131] Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta. Intro-
duction to Parallel Computing (Second Edition). Addison-Wesley, 2003.
[134] Jianyu Huang, Tyler Smith, Greg Henry, and Robert van de Geijn. Stras-
sen’s Algorithm Reloaded. In SC’16 - International Conference for High
Performance Computing, pages 690–701, 2016.
[135] Jianyu Huang, Chenhan D. Yu, and Robert A. van de Geijn. Implementing
Strassen’s Algorithm with CUTLASS on NVIDIA Volta GPUs. ArXiv,
abs/1808.07984, 08 2018.
379
Bibliografı́a
[138] Sascha Hunold and Thomas Rauber. Automatic tuning of pdgemm towards
optimal performance. In Euro-Par 2005 Parallel Processing, pages 837–846,
2005.
[139] I-Hsin Chung and J. K. Hollingsworth. Using information from prior runs
to improve automated tuning systems. In SC ’04: Proceedings of the 2004
ACM/IEEE Conference on Supercomputing, page 30, 2004.
[140] I-Hsin Chung and J. K. Hollingsworth. Using information from prior runs
to improve automated tuning systems. In SC ’04: Proceedings of the 2004
ACM/IEEE Conference on Supercomputing, pages 30–30, 2004.
[142] ICL Team. Chameleon: A Dense Linear Algebra Software for Heteroge-
neous Architectures. https://gitlab.inria.fr/solverstack/chameleon. Online;
accedido 20-03-2020.
[145] Baldomero Imbernón, Javier Prades, Domingo Giménez, José Cecilia, and
Federico Silla. Enhancing large-scale docking simulation on heterogeneous
systems: An MPI vs rCUDA study. Future Generation Computer Systems,
79:26–37, 02 2018.
380
Bibliografı́a
[151] Intel Corporation. Intel MKL PARDISO - Parallel Direct Sparse Solver
Interface. https://software.intel.com/en-us/node/470282. Online; accedido
16-05-2020.
[152] Intel
.
c Atom Processors Family. https://www.intel.com/content/www/
us/en/products/processors/atom.html. Online; accedido 18-04-2020.
[153] Intel
.
c Hyper-Threading Technology. https://www.intel.com/
content/www/us/en/architecture-and-technology/hyper-threading/hyper-
threading-technology.html. Online; accedido 18-04-2020.
[154] Intel
.
c Intel
Many
c Integrated Core Architecture (Intel
MIC
c Ar-
chitecture). https://www.intel.com/content/www/us/en/architecture-
and-technology/many-integrated-core/intel-many-integrated-core-
architecture.html. Online; accedido 18-04-2020.
[155] Intel
.
c Intel
c Thread Affinity Control. https://software.intel.com/en-
us/articles/openmp-thread-affinity-control. Online; accedido 18-04-2020.
381
Bibliografı́a
[156] Intel
.
c Intel
Xeon
c Phi Processors. https://ark.intel.com/content/www/
us/en/ark.html#@PanelLabel75557. Online; accedido 18-04-2020.
[157] Intel
.
c Legacy Intel
c CoreTM 2 Processor. https://ark.intel.com/content/
www/us/en/ark/products/series/79666/legacy-intel-core-processors.html,
2017. Online; accedido 18-04-2020.
[160] Muhammad Ali Ismail, S. Mirza, Talat Altaf, Dr. Mirza, and Dr. Altaf.
Concurrent Matrix Multiplication on Multi-Core Processors. International
Journal of Computer Science and Security, 5:208–220, 05 2011.
[161] Jack Dongarra. List of Freely Available Software for Linear Algebra on the
Web. http://www.netlib.org/utk/people/JackDongarra/la-sw.html. Onli-
ne; accedido 20-03-2020.
[162] Jaeyoung Choi and J. J. Dongarra. Scalable linear algebra software libra-
ries for distributed memory concurrent computers. In Proceedings of the
Fifth IEEE Computer Society Workshop on Future Trends of Distributed
Computing Systems, pages 170–177, 1995.
[164] Julio Jerez and Alain Suero. Newton Dynamics, a Cross-platform Life-like
Physics Simulation Library. http://newtondynamics.com/forum/newton.
php/. Online; accedido 17-04-2020.
382
Bibliografı́a
[166] Elaye Karstadt and Oded Schwartz. Matrix Multiplication, a Little Faster.
In 29th ACM Symposium on Parallelism in Algorithms and Architectures,
page 101–110, 2017.
[168] Takahiro Katagiri, Kenji Kise, Hiroki Honda, and Toshitsugu Yuba. Ef-
fect of auto-tuning with user’s knowledge for numerical software. In 1st
Conference on Computing Frontiers, pages 12–25, 2004.
[169] Stephen Keckler, William Dally, Brucek Khailany, Michael Garland, and
David Glasco. GPUs and the Future of Parallel Computing. IEEE Micro,
31(5):7–17, 11 2011.
[170] Khronos Group. The Industry’s Foundation for High Performance Graphics.
https://www.opengl.org/. Online; accedido 18-04-2020.
[171] Khronos Group. The Open Standard for Parallel Programming of Hete-
rogeneous Systems. https://www.khronos.org/opencl/. Online; accedido
18-04-2020.
[172] Ayca Kirimtat, Ondrej Krejcar, Rafael Dolezal, and Ali Selamat. A mini re-
view on parallel processing of brain magnetic resonance imaging. In Ignacio
Rojas, Olga Valenzuela, Fernando Rojas, Luis Javier Herrera, and Francisco
M. Ortuño Guzmán, editors, Bioinformatics and Biomedical Engineering -
8th International Work-Conference, IWBBIO 2020, Granada, Spain, May
6-8, 2020, Proceedings, volume 12108 of Lecture Notes in Computer Science,
pages 482–493. Springer, 2020.
[173] David Kirk and Hwu Wen-Mei. Programming Massively Parallel Processors:
A Hands-on Approach. Morgan Kaufmann, 2016.
[174] Tobias Klein, Peter Mindek, Ludovic Autin, David S. Goodsell, Arthur J.
Olson, M. Eduard Gröller, and Ivan Viola. Parallel generation and visuali-
zation of bacterial genome structures. Comput. Graph. Forum, 38(7):57–68,
2019.
383
Bibliografı́a
[175] Tamara G. Kolda, Robert Michael Lewis, and Virginia Torczon. Optimi-
zation by direct search: New perspectives on some classical and modern
methods. SIAM Review, 45:385–482, 2003.
[177] Branko Kolundzija, Dragan Olcan, Dusan Zoric, and Sladjana Maric. Acce-
lerating WIPL-D numerical EM kernel by using graphics processing units.
In 10th International Conference on Telecommunication in Modern Sate-
llite Cable and Broadcasting Services, TELSIKS, volume 2, pages 413–419,
2011.
[180] Prasad Kulkarni, Wankang Zhao, Hwashin Moon, Kyunghwan Cho, David
Whalley, Jack Davidson, Mark Bailey, Yunheung Paek, and Kyle Gallivan.
Finding effective optimization phase sequences. In Proceedings of the 2003
ACM SIGPLAN Conference on Language, Compiler, and Tool for Embed-
ded Systems, pages 12––23, 2003.
[181] Jakub Kurzak, Stanimire Tomov, and Jack Dongarra. Autotuning GEMM
kernels for the Fermi GPU. IEEE Transactions on Parallel and Distributed
Systems, 23(11):2045–2057, 01 2012.
[182] Alexey Lastovetsky and Ravi Reddy. A Novel Algorithm of Optimal Matrix
Partitioning for Parallel Dense Factorization on Heterogeneous Processors.
In Lecture Notes in Computer Science, volume 4671, pages 261–275, 2007.
384
Bibliografı́a
[190] Subhendu Maity, Subbareddy Bonthu, Kaushik Sasmal, and Hari Warrior.
Role of parallel computing in numerical weather forecasting models. In-
ternational Journal of Computer Applications, CCSN2012(4):975–8887, 03
2013.
385
Bibliografı́a
[203] Simon McIntosh-Smith, James Price, Richard Sessions, and Amaurys Iba-
rra. High performance in silico virtual drug screening on many-core proces-
sors. The International Journal of High Performance Computing Applica-
tions, 29(2):119–134, 05 2015.
[204] Everton Mendonça, Marcos Barreto, Vinı́cius Guimarães, Nelci Santos, Sa-
muel Pita, and Murilo Boratto. Accelerating docking simulation using mul-
ticore and GPU systems. In Osvaldo Gervasi, Beniamino Murgante, Sanjay
Misra, Giuseppe Borruso, Carmelo Maria Torre, Ana Maria A. C. Rocha,
David Taniar, Bernady O. Apduhan, Elena N. Stankova, and Alfredo Cuz-
zocrea, editors, Computational Science and Its Applications - ICCSA 2017
- 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings,
Part I, volume 10404 of Lecture Notes in Computer Science, pages 439–451.
Springer, 2017.
386
Bibliografı́a
[210] Gordon Moore. Cramming more components onto integrated circuits, Re-
printed from Electronics, volume 38, number 8, April 19, 1965, pp.114 ff.
Solid-State Circuits Newsletter, IEEE, 11:33–35, 10 2006.
[213] MPI Forum. Forum for the Message Passing Interface. https://www.mpi-
forum.org/. Online; accedido 20-03-2020.
[217] Ken Naono, Keita Teranishi, John Cavazos, and Reiji Suda. Software Au-
tomatic Tuning. From Concepts to State-of-the-Art Results. Springer, 2010.
387
Bibliografı́a
[218] Rajib Nath, Stanimire Tomov, and Jack Dongarra. An Improved Magma
Gemm For Fermi Graphics Processing Units. International Journal of High
Performance Computing Applications, 24(4):511–515, 11 2010.
[222] Yiinju Nelson, Bhupesh Bansal, Mary Hall, Aiichiro Nakano, and Kristina
Lerman. Model-guided performance tuning of parameter values: A case
study with molecular dynamics visualization. In Parallel and Distributed
Processing Symposium, International, pages 1–8, 04 2008.
[223] Bradford Nichols, Dick Buttlar, and Jacqueline Farrel. Pthreads Program-
ming: A Posix Standard For Better Multiprocessing. O’Reilly, 1996.
[224] John Nickolls, Ian Buck, Michael Garland, and Kevin Skadron. Scalable
Parallel Programming with CUDA. Queue, 6(2):40–53, 03 2008.
388
Bibliografı́a
[230] Satoshi Ohshima, Kenji Kise, Takahiro Katagiri, and Toshitsugu Yuba. Pa-
rallel processing of matrix multiplication in a CPU and GPU heterogeneous
environment. In Lecture Notes in Computer Science, Proceedings of the 7th
International Conference on High-Performance Computing for Computatio-
nal Science, volume 4395, pages 305–318, 2007.
[231] Open MPI Project. Open MPI: Open Source High-Performance Computing.
https://www.open-mpi.org/. Online; accedido 20-03-2020.
[233] OpenMP Architecture Review Board. The OpenMP API Specification for
Parallel Programming. https://www.openmp.org/. Online; accedido 20-03-
2020.
[237] John Owens, Mike Houston, David Luebke, Simon Green, John Stone, and
James Phillips. GPU computing. Proceedings of the IEEE, 96:879–899, 05
2008.
[238] Peter Pacheco. Parallel Programming with MPI. Morgan Kaufmann Pu-
blishers, 1997.
[240] Antoine Petitet, L. Blackford, Jack Dongarra, Brett Ellis, Graham Fagg,
Kenneth Roche, and Sathish Vadhiyar. Numerical Libraries and the
Grid. International Journal of High Performance Computing Applications,
15(4):359–374, 01 2001.
389
Bibliografı́a
[242] Markus Püschel, José M. F. Moura, Bryan Singer, Jianxin Xiong, Jeremy R.
Johnson, David A. Padua, Manuela M. Veloso, and Robert W. Johnson.
Spiral: A generator for platform-adapted libraries of signal processing alo-
gorithms. Int. J. High Perform. Comput. Appl., 18(1):21–45, 2004.
[244] Apan Qasem and Ken Kennedy. Profitable loop fusion and tiling using
model-driven empirical search. In Proceedings of the International Confe-
rence on Supercomputing, pages 249–258, 01 2006.
[245] Apan Qasem and Ken Kennedy. Model-guided empirical tuning of loop
fusion. Int. J. High Perform. Syst. Archit., 1(3):183–198, 2008.
[246] Yutong Qin, Jianbiao Lin, and Xiang Huang. Massively parallel ray tracing
algorithm using GPU. CoRR, abs/1504.03151, 2015.
[248] Michael Quinn. Parallel Programming in C with MPI and OpenMP. Mc-
Graw Hill, 2004.
[249] Ari Rasch, Michael Haidl, and Sergei Gorlatch. ATF: A Generic Auto-
Tuning Framework. In 2017 IEEE 19th International Conference on High
Performance Computing and Communications, pages 64–71, 12 2017.
[250] Thomas Rauber and Gudula Rünger. Parallel Programming: for Multicore
and Cluster Systems. Springer, 2012.
390
Bibliografı́a
[252] Daniel Reed and Jack Dongarra. Exascale Computing and Big Data. Com-
munications of the ACM, 58(7):56–68, 07 2015.
[258] Takao Sakurai, Takahiro Katagiri, Hisayasu Kuroda, Ken Naono, Mitsu-
yoshi Igai, and Satoshi Ohshima. A Sparse Matrix Library with Automa-
tic Selection of Iterative Solvers and Preconditioners. Procedia Computer
Science, 18:1332–1341, 12 2013.
[259] Takao Sakurai, Takahiro Katagiri, Hisayasu Kuroda, Ken Naono, Mitsu-
yoshi Igai, and Satoshi Ohshima. A sparse matrix library with automatic
selection of iterative solvers and preconditioners. In Vassil N. Alexandrov,
Michael Lees, Valeria V. Krzhizhanovskaya, Jack J. Dongarra, and Peter
M. A. Sloot, editors, Proceedings of the International Conference on Compu-
tational Science, ICCS 2013, Barcelona, Spain, 5-7 June, 2013, volume 18
of Procedia Computer Science, pages 1332–1341. Elsevier, 2013.
391
Bibliografı́a
[264] Robert R. Schaller. Moore’s law: past, present, and future. IEEE Spectrum,
34(6):52–59, 06 1997.
[265] Ridgway Scott, Terry Clark, and Babak Bagheri. Scientific Parallel Com-
puting. Princeton University Press, 2005.
[267] Jesús Pérez Serrano, E. Sandes, A. Melo, and M. Ujaldón. DNA sequences
alignment in multi-GPUs: acceleration and energy payoff. BMC Bioinfor-
matics, 19(421), 2018.
[268] A. A. Shabana. Dynamics of multibody systems. John Wiley & Sons, 2nd
edition, 1998.
[269] Ronald Shonkwiler and Lew Lefton. An Introduction to Parallel and Vector
Scientific Computation. Cambridge University Press, 2006.
392
Bibliografı́a
[272] Federico Silla, Javier Prades, Sergio Iserte, and Carlos Reaño. Remote GPU
Virtualization: Is It Useful? In 2016 2nd IEEE International Workshop on
High-Performance Interconnection Networks in the Exascale and Big-Data
Era (HiPINEB), Barcelona, pages 41–48, 2016.
[274] Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack
Dongarra. MPI. The Complete Reference (Second Edition). The MIT Press,
1998.
[276] Source Forge. Open Source Performance Analysis Environment for Linux.
http://perfsuite.sourceforge.net/. Online; accedido 23-05-2020.
[280] John Stone, David Gohara, and Guochun Shi. OpenCL: A Parallel Pro-
gramming Standard for Heterogeneous Computing Systems. Computing in
Science & Engineering, 12(1-3):66–72, 05 2010.
393
Bibliografı́a
[285] T. N. Theis and H.-S. Philip Wong. The End of Moore’s Law: A New Be-
ginning for Information Technology. Computing in Science & Engineering,
19(2):41–50, 03 2017.
[290] Robert A. van de Geijn. Using PLAPACK: Parallel Linear Algebra Package.
The MIT Press, 1997.
[291] Richard Vuduc, James Demmel, and Jeff Bilmes. Statistical Models for
Automatic Performance Tuning. In International Conference on Compu-
tational Science, volume 18, pages 117–126, 2001.
394
Bibliografı́a
[292] Richard Vuduc, James Demmel, and Katherine Yelick. Oski: A library of
automatically tuned sparse matrix kernels. Journal of Physics Conference
Series, 16:521–530, 01 2005.
[293] Feng Wang, Can-Qun Yang, Yun-Fei Du, Juan Chen, Hui-Zhan Yi, and Wei-
Xia Xu. Optimizing Linpack Benchmark on GPU-Accelerated Petascale
Supercomputer. Journal of Computer Science and Technology, 26(5):854–
865, 09 2011.
[294] Hao Wang, Sreeram Potluri, Miao Luo, Ashish Singh, Sayantan Sur, and
D.K. Panda. MVAPICH2GPU: optimized GPU to GPU communication
for InfiniBand clusters. Computer Science - Research and Development,
26(3-4):257–266, 06 2011.
[297] R. Whaley, Antoine Petitet, and Jack Dongarra. Automated empirical op-
timizations of software and the ATLAS project. Parallel Computing, 27(1-
2):3–35, 01 2001.
[299] Felix Wolf, Brian Wylie, Erika Ábrahám, Daniel Becker, Wolfgang Frings,
Karl Fürlinger, Markus Geimer, Marc-André Hermanns, Bernd Mohr, Shir-
ley Moore, Matthias Pfeifer, and Zoltán Szebenyi. Usage of the SCALASCA
toolset for scalable performance analysis of large-scale parallel applications.
In Proceedings of the 2nd International Workshop on Parallel Tools for High
Performance Computing, pages 157–167, 01 2008.
395
Bibliografı́a
[300] Dong Hyuk Woo, Joshua B. Fryman, Allan D. Knies, and Hsien-Hsin S.
Lee. Chameleon: Virtualizing idle acceleration cores of a heterogeneous
multicore processor for caching and prefetching. ACM Trans. Archit. Code
Optim., 7(1), 5 2010.
[301] World Wide Web Consortium (W3C) . Scalable Vector Graphics (SVG).
https://www.w3.org/Graphics/SVG/. Online; accedido 13-04-2020.
[302] Patrick Worley, Arthur Mirin, Anthony Craig, Mark Taylor, John Dennis,
and Mariana Vertenstein. Performance of the community earth system
model. In Proceedings of 2011 SC - International Conference for High
Performance Computing, Networking, Storage and Analysis, page 54, 11
2011.
[303] Xingfu Wu, Valerie E. Taylor, Shane Garrick, Dazhi Yu, and Jacques Ri-
chard. Performance Analysis, Modeling and Prediction of a Parallel Mul-
tiblock Lattice Boltzmann Application Using Prophesy System. In Procee-
dings of the 2006 IEEE International Conference on Cluster Computing,
September 25-28, 2006, Barcelona, Spain, pages 1–8. IEEE Computer So-
ciety, 2006.
396