SD1-23-2-TéllezGonzálezJorgeLuis-Examen3

Vista previa del material en texto

FACULTAD DE INGENIERÍA 1
Examen 3: SAXPY
Jorge Luis Téllez González, 315132726
Sistemas Distribuidos - Grupo: 01
Resumen—En este trabajo se analiza el rendimiento de diferentes
ordenamientos de bucles anidados para la multiplicación de
matrices empleando la función SAPXY que forma parte de
la biblioteca BLAS. Se comparan los ordenamientos ijk, jik,
ikj, jki, kij y kji en términos de su eficiencia, junto a una
comparación entre 3 compiladores distintos y en ambientes
operativos diferentes con el objetivo de identificar diferencias
entre tiempos de ejecución.
Index Terms—SAXPY, BLAS, matrices, multiplicación, eficiencia,
memoria
I. INTRODUCCIÓN
SA XPY, acrónimo de Single-Precision A X Plus Y, esuna función de la biblioteca estándar de Basic Linear
Algebra Subroutines (BLAS). En términos generales, SAXPY
combina una multiplicación escalar y una suma de vectores.
La multiplicación de matrices es una de las operaciones más
importantes en diversas áreas de la ciencia y la ingenierı́a, y
por tanto, la eficiencia a la hora de su ejecución resulta crı́tica
para cumplir su propósito.
Los arreglos multidimensionales (o matrices) son una estruc-
tura de datos común en el cálculo cientı́fico para representar
datos con múltiples dimensiones, como imágenes, señales de
audio, volúmenes de datos, matrices de transformación, entre
otros. Su importancia radica en que permiten un acceso y
manipulación eficientes de los datos para realizar operaciones
y cálculos en el cálculo cientı́fico. Sin embargo, el acceso
ineficiente a los datos del arreglo puede ralentizar el procesa-
miento y limitar la capacidad de los algoritmos para manejar
grandes conjuntos de datos.
Una de las formas más sencillas de implementar un cálculo
matricial es observable en la Figura 1, la cual emplea tres ci-
clos for anidados.Una ventaja de este método es su simplicidad
y claridad; es fácil de entender y de implementar, lo que lo
hace una buena opción para matrices pequeñas. Sin embargo,
esta implementación no es eficiente para matrices grandes
debido a la cantidad de accesos a memoria que requiere. En
particular, la memoria caché no se utiliza de manera eficiente,
lo que puede causar retrasos significativos en la ejecución del
código.
Figura 1: Algoritmo de multiplicación de matrices en C.
El orden en que se recorren los vectores en el caché depende
del lenguaje de programación utilizado. Por ejemplo, en el
caso de C se utiliza el esquema de almacenamiento de matriz
de orden-fila (Row major order), donde las filas se almacenan
consecutivamente en la memoria. En cambio, Fortran utiliza
el esquema de almacenamiento de matriz de orden-columna
(Column major order), donde las columnas se almacenan
consecutivamente en las lı́neas de caché.
Figura 2: Row major order en C.
En el caso del algoritmo anterior, una posible forma de mejorar
la eficiencia de esta implementación es reordenando los bucles
para que se ajusten a la forma en que se almacenan los
elementos en la memoria caché. Al utilizar un orden de
recorrido de las matrices que aprovecha la localidad espacial,
se pueden reducir los tiempos de acceso a la memoria y, por lo
tanto, mejorar la eficiencia de la operación de multiplicación
de matrices.
En el siguiente trabajo se implementará un programa en C que
multiplique 2 matrices cuadradas y el resultado lo almacene
en una tercera matriz. Posteriormente, se variará el orden de
los bucles for para cronometrar el tiempo de ejecución entre
cada variación; empleando sistemas de 100x100, 500x500 y
1000x1000 en cada una de ellas. Ası́ mismo, se verificará si
existe alguna diferencia temporal al compilar empleando op-
ciones distintas (g++, icx y Clang) o en entornos de ejecución
distintos (Windows y Linux).
Se proporciona un código de apoyo para la elaboración de la
actividad, al cual se le han realizado ligeras modificaciones
para su ejecución en Windows. Se anexan al trabajo presente
los códigos empleados tanto en Windows como en ambientes
Linux.
FACULTAD DE INGENIERÍA 2
II. DESARROLLO
Para el desarrollo de las actividades solicitadas se generó un
programa que, a la entrada, pregunta el orden en que se desea
ejecutar el cálculo matricial. Posteriormente, solicita el tamaño
n de las matrices a multiplicar y, por último, arroja como
salida el tiempo de llenado de las matrices y el tiempo que
tomó realizar el cálculo matricial.
Figura 3: Ejecución del programa en Windows para el caso
ijk.
Para el caso particular de Windows, en lugar de utilizar la
biblioteca time se utiliza windows.h, la cual permite utilizar
la API de Windows para obtener timestamps con funciones
incorporadas al sistema operativo.
A continuación, se mostrarán las ejecuciones de los 3 tamaños
de matrices empleando los siguientes compiladores en el
entorno de Windows: g++, icx y clang.
Figura 4: Benchmarks de compiladores en Windows.
El primer compilador usado corresponde a g++, un derivado
de gdb que admite la compilación tanto de código C como de
C++. Para la ejecución, se utilizó el entorno de Visual Studio
Code.
Por otra parte, la segunda y tercera elección correspondieron
a ICX ( Intel® oneAPI DPC++/C++ Compiler, una versión
actualizada del Intel® C++ Compiler Classic (ICC)) y Clang,
un compilador multilenguaje pensado para su integración
mejorada con IDEs como Visual Studio. Se anexan capturas
para corroborar la instalación de estos compiladores en el
equipo local para la ejecución de las pruebas.
Figura 5: Instalación de g++.
Figura 6: Instalación de icx.
Figura 7: Instalación de Clang.
La elección de estos compiladores se debió a los siguientes
motivos:
g++ es un compilador moderno incluido en todas las
distribuciones estándar de Linux, de forma que no es
necesario hacer ninguna configuración adicional para
ejecutarlo en estos entornos. Por otra parte, su instala-
ción resulta sencilla en Windows por medio del entorno
MSYS2.
icx o icpx es una biblioteca de cómputo cientı́fico y de
alto rendimiento desarrollada por Intel, la cual incluye su
propio compilador para C y C++.
Clang es un compilador de C y C++ pensado para su
integración en IDEs en entornos productivos como VS
Code, y es la elección empleada en la academia de
Computación Gráfica de la FI UNAM para el desarrollo
de prácticas en OpenGL.
La elección de los ambientes Linux consistieron en las dis-
tribuciones de Linux Mint y Debian en sus versiones más
recientes, en donde igualmente se instaló el compilador icx
y Clang por medio de la consola. En las siguientes capturas
se muestran probatorios de la ejecución de estos sistemas
operativos por medio del software de virtualización VirtualBox
y los resultados de los benchmarks con los 3 compiladores en
ambos sistemas operativos Linux:
FACULTAD DE INGENIERÍA 3
Figura 8: Ejecución del programa en la consola de Mint.
Figura 9: Benchmarks de compiladores en Mint.
Figura 10: Compilación del programa en la consola de De-
bian.
A partir de los datos recopilados se generaron una serie de
gráficas comparativas en Excel de los 3 casos analizados:
n = 100, n = 500 y n = 1000. Con estos datos plasmados
gráficamente, se analizarán los resultados obtenidos para vi-
sualizar tanto las diferencias en el acceso de los ı́ndices como
en los entornos de ejecución y los compiladores utilizados para
realizar los cálculos matriciales.
Figura 11: Benchmarks de compiladores en Debian.
II-A. Resultados obtenidos
II-A1. Caso 1: A continuación se muestran los benchmarks
gráficos para el primer caso de estudio: n = 100.
Figura 12: Benchmark Caso 1.
ijk: el primer caso analizado no demuestra diferencias
significativas en tiempo de ejecución entre los distintos
sistemas operativos empleando g++. Al observar los
FACULTAD DE INGENIERÍA 4
resultados de icx se nota que el tiempo de ejecución se
reduce de forma notable por la naturaleza del compilador;
con W10 teniendo un tiempo de ejecución levemente
mayor. Por último, en el caso de Clang el entornode
W10 mostró una ligera ventaja frente a Debian; quedando
notablemente atrás el tiempo marcado para Mint.
ikj: g++ demuestra un ligero mejor rendimiento en W10,
quedando en empate ambos sistemas Linux. Icx nueva-
mente muestra un ligera ventaja para sistemas Linux,
mientras que nuevamente Clang supera a los entornos
Linux de forma notable. Este ordenamiento de ı́ndices
representa una mejora notable con respecto al anterior.
jik: en g++ Mint produce el resultado más lento, mientras
que en icx el panorama el resultado empeora con respecto
a su predecesor. Por último, se observa que Debian logra
ponerse a la par de W10 a la hora de ejecutar el programa
compilado con Clang. En general los resultados son
semejantes a los casos anteriores.
jki: g++ produce resultados similares a los vistos a jik,
mientras que en icx se observa un delay notable en
W10, cambiando las tablas y dejando a los sistemas
Linux prácticamente a la par. Por último, Clang no arroja
diferencias significativas con respecto a jik.
kij: g++ demuestra resultados notablemente superiores en
los 3 sistemas empleando esta forma de acceso; situación
que se repite de forma notable en icx; pero que no resulta
significativa en Clang. Mejora lo visto en ikj por cierto
margen.
kji: g++ muestra resultados ligeramente menores a los
primeros 4 casos, sin embargo, en icx obtiene malos
resultados como jki. En el caso de Clang no se observan
diferencias notables.
Es posible afirmar que, para un número n pequeño como
el empleado, las diferencias entre las formas de ordenar los
ı́ndices, si bien pueden tener un impacto en determinados
compiladores, en otros la diferencia no resultará demasiado
tangible; como lo demostró especı́ficamente Clang. Por otra
parte, icx fue el compilador más sensible a las modificaciones
en los accesos a los ı́ndices, en donde la combinación kij
resultó ser la más rápida seguida de ikj, y esto se debe a que se
ajusta de manera más efectiva a la forma en que la CPU accede
a las lı́neas de caché. Debido a que se acceden a los elementos
de una fila A y una columna B de manera consecutiva, este
arreglo garantiza que los datos contenidos en los ı́ndices ya
estén cargados en la caché, lo que disminuye la cantidad
de veces que se requiere acceder a la memoria principal
y, por lo tanto, aumenta el rendimiento de la operación de
multiplicación de matrices.
Por otra parte, jki y kji mostraron los peores resultados en
cuanto a ejecución empleando icx; el compilador con mejores
tiempos de respuesta. A partir de allı́, es posible observar que
iniciar los ciclos en j y k puede tener un notable impacto
en el acceso a memoria; siendo la peor combinación de todas
jki por su ineficiencia a la hora de recuperar los datos de la
memoria caché; generando en consecuencia un delay notable
en las operaciones debido a que los datos no se recuperan
eficientemente. Especı́ficamente, la recuperación secuencial de
los elementos de la matriz en forma columnar provoca que las
multiplicaciones no se puedan realizar en el momento debido a
que todavı́a no se encuentran en memoria los siguientes valores
para multiplicar.
Resulta llamativo mencionar que Mint sufrió un delay consi-
derable frente a sus competidores al ejecutar código compilado
con Clang; hecho visible en las gráficas anteriores, sin embar-
go, este comportamiento anómalo no se repitió conforme se
incrementaron las entradas.
Para los siguientes 2 casos se analizarán puntualmente los in-
sights obtenidos por compilador y las diferencias con respecto
al caso inicial.
II-A2. Caso 2: A continuación se muestran los benchmarks
gráficos para el segundo caso de estudio: n = 500.
Figura 13: Benchmark Caso 2.
FACULTAD DE INGENIERÍA 5
g++: Se obtiene una cota de ejecución superior a 0.6s. Las
primeras 3 combinaciones arrojan resultados semejantes
entre los 3 sistemas operativos, mientras que kij e ikj
nuevamente arrojan los tiempos de ejecución más bajos.
Por último, jki e kji arrojan los peores resultados. W10
se desempeñó peor en la mayor parte de casos, mientras
que en el mejor logró aventajar ligeramente a los sistemas
Linux.
icx: Se obtiene una cota de ejecución superior de
aproximadamente 0.24s; siendo el más rápido de los
3 compiladores. Las primeras 3 combinaciones arrojan
resultados nuevamente semejantes entre los 3 sistemas
operativos, mientras que kij obtiene tiempos de ejecución
extremadamente rápidos (4x veces con respecto a los
2 peores casos), quedando ligeramente por detrás ikj.
Las combinaciones jki e kji arrojan los peores resultados
nuevamente. Nuevamente W10 arrojó peores resultados
a excepción del mejor caso, en donde supera a sus
competidores Linux.
Clang: Se obtiene una cota de ejecución superior de apro-
ximadamente 0.45s; siendo ligeramente superior a g++
pero quedando notablemente atrás de icx. La tendencia
de g++ se repite en Clang, siendo kij e ikj los mejores
caso, ijk y jik los casos regulares y jki y kji los peores
casos. En este caso W10 lleva una ligera ventaja frente a
los sistemas Linux, los cuales entre sı́ arrojan resultados
muy semejantes.
II-A3. Caso 3: A continuación se muestran los benchmarks
gráficos para el último caso de estudio: n = 1000.
g++: es apreciable que g++ presenta el peor rendimiento
entre los 3 compiladores. Entre los sistemas operativos,
Debian mostró los resultados más lentos, mientras que
Windows 10 destacó como el SO más rápido al arrojar los
resultados. Se obtuvo una cota superior cercana a 5.5s. La
superioridad de ikj y kji resulta evidente, dejando atrás
al resto de combinaciones notablemente; patrón que se
repite en el resto de compiladores.
icx: Se obtiene una cota de ejecución superior de apro-
ximadamente 2.7s. Icx es aproximadamente 2 veces más
rápido frente a sus competidores. Aunque W10 obtiene
peores resultados en los casos regulares y malos, en el
mejor caso W10 superó por completo a los sistemas
Linux. Entre estos sistemas, Mint se desempeñó de mejor
forma.
Clang: Se obtiene una cota de ejecución superior de
aproximadamente 5s; repitiendo su ligera superioridad a
g++ pero quedando atrás de icx. W10 fue el mejor SO
empleando este compilador, mientras que Debian fue el
peor; quedando Mint en una posición intermedia.
III. CONCLUSIONES
1. Por medio de los resultados obtenidos es posible afirmar
que kij representa el mejor caso, ikj el segundo mejor
caso, ijk, y jik los casos regulares y jki y kji los
Figura 14: Benchmark Caso 3.
peores casos; tendencia que se hace más visible conforme
aumentan los tamaños de las matrices cuadradas.
2. W10 mostró resultados dispares: en los casos regulares y
malos tuvo un desempeño inferior frente a los sistemas
Linux, mientras que en el mejor caso logra igualar o
superar a sus competidores.
3. Mint mostró ser la mejor distribución Linux en cuanto
a desempeño conforme se aumentó el tamaño de las
matrices cuadradas, arrojando resultados consistentes que
le otorgaron el segundo lugar en diversos casos de prueba
en cuanto a rendimiento. En el primer caso de prueba
esta tendencia resultaba ser al revés: siendo más lento en
comparación a Debian y mostrando inconsistencias en el
caso inicial.
4. Debian fue el sistema operativo con tiempos de ejecución
más largos conforme se aumentaban los tamaños de las
matrices; únicamente mostrando superioridad frente a
FACULTAD DE INGENIERÍA 6
Mint y W10 en el caso n = 100 y quedando como el
SO más lento en n = 1000 empleando g++ y Clang;
siendo W10 el más lento por poco margen usando icx.
5. g++ fue el compilador con los peores resultados a
través de los 3 sistemas operativos, obteniendo resultados
dispares entre los 3 sistemas operativos conforme se
modificaba n.
6. icx es el compilador que tuve mejor desempeño en las
pruebas; especialmente en el mejor caso en donde obtenı́a
mejores de 2 a 4 veces con respecto a sus competidores.
En los tres sistemas operativos icx mejoró notablemente
los tiempos de ejecución.
7. Clang en general mostró cierta superioridadcon respecto
a g++ en todas las pruebas; quedando completamente
atrás de icx, sin embargo. Ası́ mismo, W10 resultó el
mejor SO para emplear este compilador, arrojando en
los 3 casos de prueba los mejores resultados por cada
combinación.
Los resultados indican que la forma en que se organizan los
bucles anidados puede tener un gran impacto en el rendimiento
de los algoritmos de multiplicación de matrices implementados
en C, ya que C utiliza el ordenamiento Row major order
para el acceso a los ı́ndices almacenados en memoria caché.
En particular, se encontró que la combinación kij es la más
eficiente para la multiplicación de matrices; hecho reflejado
en los sistemas operativos y los compiladores empleados. Este
resultado se encuentra acorde a lo referenciado por Bryant y
O’Hallaron, en donde se llegó a la misma conclusión en cuanto
a la eficiencia de kij e ikj.
Figura 15: Prueba con un Core i7.
Como se discutió previamente, esta combinación resulta ópti-
ma con respecto a la forma en que se almacenan los datos en
la memoria caché, lo que les permite acceder rápidamente a
los elementos de la matriz. Por otro lado, las combinaciones
de ı́ndices jki y kji resultaron ser las peores combinaciones
para la multiplicación de matrices, ya que resultaron en una
gran cantidad de delays que afectaron significativamente el
rendimiento del algoritmo.
Por último, es posible afirmar que las diferencia entre siste-
mas operativos no son determinantes cuando se ejecutan los
primeros 3 casos regulares, sin embargo, en el mejor caso y
los peores casos se observan diferencias significativas entre
sistemas operativos. Ası́ mismo, los resultados pueden variar
entre compiladores, de forma que si se obtuvo una tendencia
entre SO empleando g++, esta puede resultar completamente
distinta al utilizar otro compilador, por lo que es posible afir-
mar que el factor más determinante para el rendimiento de este
algoritmo se encuentra en el compilador, y no en el sistema
operativo. Cabe señalar que, en el último caso, se observan
las ineficiencias del algoritmo empleado, el cual al utilizar tres
ciclos for resulta en una complejidad computacional del orden
de O(n)3. Para mostrar esta ineficiencia, se ejecutó el mejor
caso con n = 10000, lo que arrojó los siguientes resultados:
Figura 16: Prueba con valores superiores.
En comparación con los cálculos, el rellenado inicial de las
matrices al ser de un orden inferior de O(n)2 no arrojó
resultados tan elevados, sin embargo, en la práctica siguen
siendo resultados pobres que, en presencia de cálculos de
aún mayor complejidad como los realizados en despliegues
gráficos, resultarı́an en tiempos de procesamiento demasiado
largos e ineficientes.
Finalmente, con los resultados obtenidos se hace patente la
necesidad de comprender los pormenores de la arquitectura
de los procesadores en cuanto a su manejo de la memoria y
cómo aprovecharla para mejorar la ejecución de determinados
algoritmos. Sin embargo, por más estrategias que se utilicen
en este sentido el resultado final lo determinará el propio al-
goritmo y su complejidad computacional. Combinando ambos
enfoques, es posible obtener soluciones a la medida y capaces
de tratar con grandes volúmenes de información sin retrasos
considerables de tiempo.
BIBLIOGRAFÍA
[1] Intel. “Get Started with the Intel oneAPI DPC++/C++
Compiler.” (), dirección: https://www.intel.com/content/
www/us/en/docs/dpcpp-cpp-compiler/get-started-guide/
2023-0/overview.html (visitado 18-03-2023).
[2] LLVM. “Getting Started: Building and Running Clang.”
(), dirección: https : / / clang . llvm . org / get started . html
(visitado 18-03-2023).
[3] D. Tarnoff. “CSCI 4717 - High Performance Counter.”
(), dirección: https://faculty.etsu.edu/tarnoff/labs4717/
performance/hpc.htm (visitado 18-03-2023).
https://www.intel.com/content/www/us/en/docs/dpcpp-cpp-compiler/get-started-guide/2023-0/overview.html
https://www.intel.com/content/www/us/en/docs/dpcpp-cpp-compiler/get-started-guide/2023-0/overview.html
https://www.intel.com/content/www/us/en/docs/dpcpp-cpp-compiler/get-started-guide/2023-0/overview.html
https://clang.llvm.org/get_started.html
https://faculty.etsu.edu/tarnoff/labs4717/performance/hpc.htm
https://faculty.etsu.edu/tarnoff/labs4717/performance/hpc.htm
FACULTAD DE INGENIERÍA 7
[4] R. E. Bryant y D. R. O’Hallaron. “Cache Memory and
Performance.” (2023), dirección: https: / /courses.cs .vt .
edu/cs2506/Spring2020/notes/L16 CacheAndCoding.pdf
(visitado 18-03-2023).
Los créditos de las fotografı́as pertenecen a sus autores. ©
https://courses.cs.vt.edu/cs2506/Spring2020/notes/L16_CacheAndCoding.pdf
https://courses.cs.vt.edu/cs2506/Spring2020/notes/L16_CacheAndCoding.pdf
	Introducción
	Desarrollo
	Resultados obtenidos
	Caso 1
	Caso 2
	Caso 3
	Conclusiones