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

Vista previa del material en texto

FACULTAD DE INGENIERÍA 1
Examen IV: Recorrido de matrices
Jorge Luis Téllez González, 315132726
Sistemas Distribuidos - Grupo: 01
Resumen—Este trabajo describe el análisis realizado sobre el
impacto que la reorganización de los bucles tiene en la eficiencia
del algoritmo de multiplicación de matrices por fuerza bruta,
considerando el orden Row-Major de almacenamiento de los
elementos de la matriz en memoria.
Index Terms—row, major, order, mejor, peor, rendimiento
I. INTRODUCCIÓN
UN a estructura de datos que permite almacenar y ma-nipular información en una tabla o matriz de dos o
más dimensiones se conoce como un arreglo multidimensio-
nal. Estas matrices pueden ser indexadas por posición única,
lo que permite representar y manipular datos complejos de
manera organizada y eficiente. En la computación cientı́fica,
los arreglos multidimensionales se utilizan para representar
datos de imágenes, videos, sonidos, simulaciones y modelos
matemáticos. En programación, se utilizan para almacenar
datos en matrices y tablas de múltiples dimensiones, lo que
facilita su procesamiento y análisis.
En el lenguaje de programación C, la forma en que se acceden
los vectores en caché se determina por la forma en que se
almacenan los elementos de la matriz en la memoria. En la
mayorı́a de las arquitecturas de computadoras modernas, los
elementos se almacenan en la memoria en el orden Row Major,
lo que significa que los elementos de cada fila de la matriz se
almacenan de manera contigua en la memoria y se acceden de
manera secuencial, seguidos de los elementos de la siguiente
fila.
Figura 1: Row Major Order vs Column Major Order.
El algoritmo más sencillo para multiplicar 2 matrices y guardar
su resultado en otra matriz utiliza tres ciclos ”for” anidados pa-
ra recorrer los elementos de las matrices de entrada y calcular
los elementos de la matriz resultante. Una gran desventaja se
encuentra en su tiempo de ejecución es del orden de O(n3),
debido a que el algoritmo no reutiliza los elementos de la
matriz que ya se encuentran en caché, sino que los lee varias
veces desde la memoria, lo que aumenta significativamente el
tiempo de ejecución.
for (int i = 0; i<n; i++)
for (int j = 0; j<n; j++)
for (int k = 0; k<n; k++)
C[i][j] += A[i][k] * B[k][j]
Es posible mejorar la eficiencia del algoritmo de multiplica-
ción de matrices por fuerza bruta y aprovechar la localidad
espacial de los datos reorganizando los bucles para acceder
a los elementos de la matriz de acuerdo con la forma en
que se almacenan en la memoria. Al hacer esto, se asegura
que los elementos accesados en un bucle estén cercanos en la
memoria caché, mejorando la localidad espacial de los datos
y reduciendo el número de accesos a la memoria principal.
A continuación, se analizará por qué las reorganizaciones de
bucles ikj y kij son más eficientes en comparación con las
combinaciones jki y kji, que por otro lado, son las más lentas
y de peor rendimiento de forma generalizada.
II. DESARROLLO
El orden Row-Major implica que los elementos de cada fila
de la matriz se almacenan consecutivamente en la memoria,
seguidos por los de la siguiente fila. Por lo tanto, aque-
llas combinaciones que favorezcan el acceso por filas a los
elementos de las matrices serán las que aprovechen mejor
la localidad espacial de los datos y, por ende, gozarán de
una mejor eficiencia. Para este análisis, se considera como
base el trabajo realizado de benchmarks de las diferentes
combinaciones de ı́ndices para establecer motivos certeros
acerca de los resultados obtenidos previamente en cuanto a
las mejores y las peores combinaciones.
II-A. Resultados
A continuación se presentan las 2 combinaciones más eficaces
y las 2 combinaciones más lentas de ı́ndices.
II-A1. ikj: La manera más eficiente de multiplicar matrices
es reorganizando los bucles mediante la combinación de
ı́ndices ikj, ya que de este modo se puede aprovechar mejor la
localidad espacial de los datos en la memoria cach accediendo
a los elementos de la matriz A en orden de filas en el bucle
externo, y en el bucle interno se recorre la matriz B por filas,
FACULTAD DE INGENIERÍA 2
de modo que se accede a elementos almacenados juntos en
la memoria caché, lo que mejora la localidad espacial de
los datos y disminuye la cantidad de accesos a la memoria
principal.
Figura 2: Orden de acceso a los ı́ndices con ikj.
II-A2. kij: La combinación kij también comparte el lugar con
la anterior, como las combinaciones de ı́ndices más eficientes
para recorrer las matrices en el algoritmo de multiplicación.
En esta, se recorren las matrices C y B por filas, mientras
que la matriz A se recorre por columnas; lo que impacta
en su capacidad de aprovechar el orden de almacenamiento
en memoria En cada iteración, se accede a elementos de la
matriz A que no están contiguos en la memoria, lo que puede
aumentar la cantidad de accesos a la memoria principal y
reducir el rendimiento del algoritmo.
Figura 3: Orden de acceso a los ı́ndices con kij.
II-A3. jki: La combinación de ı́ndices jki es la menos
eficiente para la multiplicación de matrices, principalmente a
que esta combinación de bucles no aprovecha de ningún modo
la localidad espacial de los datos, ya que todas las matrices se
recorren por columnas, lo que significa que en cada iteración
se accede a elementos que no están contiguos en la memoria.
En consecuencia, esto resulta en un mayor número de accesos
a la memoria principal y, por lo tanto, un impacto notable en
el rendimiento del algoritmo.
Figura 4: Orden de acceso a los ı́ndices con jki.
II-A4. kji: El arreglo de ı́ndices kji resulta ligeramente mejor
que la combinación de ı́ndices jki para la multiplicación de
matrices debido a que, aunque ambas combinaciones de bucles
no aprovechan bien la localidad espacial de los datos, la
combinación kji puede reducir el número de saltos de memoria
en comparación con la combinación jki, ya que la matriz B
se recorre por filas. El principal problema se encuentra en el
modo de acceso no contiguo por columnas en las matrices C
y A; hecho que impacta de forma notoria el rendimiento de
esta combinación.
Figura 5: Orden de acceso a los ı́ndices con kji.
III. CONCLUSIONES
La multiplicación de matrices es una operación fundamental
en muchas aplicaciones, pero puede ser muy costosa compu-
tacionalmente, especialmente para matrices grandes. Por lo
tanto, mejorar la eficiencia de los algoritmos de multiplicación
de matrices es importante para aumentar la velocidad de
procesamiento y reducir los costos de operación y el impacto
ambiental.
Los resultados muestran que las combinaciones de ı́ndices ikj
y kij son las más eficientes para la multiplicación de matrices,
ya que aprovechan bien la localidad espacial y minimizan
el número de saltos de memoria necesarios para acceder a
los elementos de la matriz. En cambio, las combinaciones de
ı́ndices kji y jki resultaron ser las menos eficientes debido a
un gran número de fallos de caché resultado de acceder en
forma de columnas a los elementos de las matrices.
Es importante tener en cuenta que la elección de la combina-
ción de ı́ndices adecuada depende del lenguaje de programa-
ción utilizado y cómo se almacenan los elementos de la matriz
en la memoria. Si el lenguaje de programación utiliza un orden
de almacenamiento de columna principal, como FORTRAN,
FACULTAD DE INGENIERÍA 3
entonces las combinaciones kji y jki serı́an las más eficientes,
mientras que ikj y kij serı́an las menos eficientes. En general,
es importante comprender cómo se almacenan los elementos
de la matriz en la memoria y elegir la combinación de ı́ndices
adecuada para mejorar la eficiencia de los algoritmos que
involucren matrices multidimensionales.
BIBLIOGRAFÍA
[1] J. Senning. “Matrix Multiplication.” (2020), dirección:
http : / / cps . gordon . edu / courses / cps343 / presentations /
Matrix Mult.pdf (visitado 08-04-2023).
[2] ScratchaPixel. “Row Major vs Column Major Vector.”
(),dirección: https : / / www. scratchapixel . com / lessons /
mathematics- physics- for- computer-graphics/geometry/
row - major - vs - column - major - vector . html (visitado
08-04-2023).
Los créditos de las fotografı́as pertenecen a sus autores. ©
http://cps.gordon.edu/courses/cps343/presentations/Matrix_Mult.pdf
http://cps.gordon.edu/courses/cps343/presentations/Matrix_Mult.pdf
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/geometry/row-major-vs-column-major-vector.html
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/geometry/row-major-vs-column-major-vector.html
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/geometry/row-major-vs-column-major-vector.html
	Introducción
	Desarrollo
	Resultados
	ikj
	kij
	jki
	kji
	Conclusiones