sintonico - teoria del desarrollo psicosocial de erikson pdf
Fila mayor contra confusión principal de la columna (8)
Ok, entonces dado que la palabra "confusión" está literalmente en el título, puedo entender el nivel de ... confusión.
En primer lugar, esto es absolutamente un problema real
Nunca, CIERTAMENTE sucumbir a la idea de que "se usa pero ... la PC es hoy en día ..."
Los principales problemas aquí son: - -Cache eviction strategy (LRU, FIFO, etc.) as @YCJung was beginning to touch on -Branch prediction -Pipelining (it''s depth, etc) -Actual physical memory layout -Size of memory -Architecture of machine, (ARM, MIPS, Intel, AMD, Motorola, etc.)
Esta respuesta se centrará en la arquitectura de Harvard, la máquina Von Neumann, ya que es más aplicable a la PC actual.
La jerarquía de memoria:
https://en.wikipedia.org/wiki/File:ComputerMemoryHierarchy.svgis
Es una yuxtaposición de costo versus velocidad.
Para el sistema de PC estándar actual, esto sería algo así como: SIZE: 500GB HDD > 8GB RAM > L2 Cache > L1 Cache > Registers. SPEED: 500GB HDD < 8GB RAM < L2 Cache < L1 Cache < Registers. SIZE: 500GB HDD > 8GB RAM > L2 Cache > L1 Cache > Registers. SPEED: 500GB HDD < 8GB RAM < L2 Cache < L1 Cache < Registers.
Esto lleva a la idea de Localidad temporal y espacial. Uno significa cómo se organizan sus datos, (código, conjunto de trabajo, etc.), el otro significa físicamente donde sus datos están organizados en "memoria".
Dado que "la mayoría" de las PC actuales son máquinas little-endian (Intel) últimamente, colocan datos en la memoria en un orden específico little-endian. Difiere de big-endian, fundamentalmente.
https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html (lo cubre más bien ... swiftly ;))
(Por la simplicidad de este ejemplo, voy a ''decir'' que las cosas suceden en entradas individuales, esto es incorrecto, generalmente se accede a bloques enteros de caché y varían drásticamente mi fabricante, y mucho menos el modelo).
Entonces, ahora que tenemos ese problema, hipotéticamente su programa demandó 1GB of data from your 500GB HDD , cargados en sus 8GB of RAM, luego en la jerarquía de cache , luego eventualmente se registers , donde fue su programa y leyó el primera entrada desde su línea de caché más reciente solo para que su segunda entrada (en SU código) esté sentada en la next cache line, (es decir, el siguiente FILA en lugar de columna , tendría un caché MISS) .
Suponiendo que el caché está lleno, porque es pequeño , en caso de falla, según el esquema de desalojo, una línea sería desalojada para dejar espacio a la línea que ''tiene'' los próximos datos que necesita. Si este patrón se repite, ¡usted tendría un MISS en CADA intento de recuperación de datos!
Peor aún, estaría desalojando líneas que en realidad tienen datos válidos que está a punto de necesitar, por lo que tendrá que recuperarlos OTRA VEZ.
El término para esto se llama: thrashing
https://en.wikipedia.org/wiki/Thrashing_(computer_science) y puede bloquear un sistema mal escrito / propenso a errores. (Think windows BSOD ) ....
Por otro lado, si hubiera distribuido los datos correctamente (es decir, Row major) ... ¡ TODAVÍA tendría errores!
Pero estas fallas solo ocurrirían al final de cada recuperación, no en TODOS los intentos de recuperación. Esto da como resultado órdenes de magnitud de diferencia en el rendimiento del sistema y del programa.
Fragmento muy muy simple:
#include<stdio.h>
#define NUM_ROWS 1024
#define NUM_COLS 1024
int COL_MAJOR [NUM_ROWS][NUM_COLS];
int main (void){
int i=0, j=0;
for(i; i<NUM_ROWS; i++){
for(j; j<NUM_COLS; j++){
COL_MAJOR[j][i]=(i+j);//NOTE i,j order here!
}//end inner for
}//end outer for
return 0;
}//end main
Ahora compila con: gcc -g col_maj.c -o col.o
Ahora, ejecute con: time ./col.o real 0m0.009s user 0m0.003s sys 0m0.004s
Ahora repite para ROW major:
#include<stdio.h>
#define NUM_ROWS 1024
#define NUM_COLS 1024
int ROW_MAJOR [NUM_ROWS][NUM_COLS];
int main (void){
int i=0, j=0;
for(i; i<NUM_ROWS; i++){
for(j; j<NUM_COLS; j++){
ROW_MAJOR[i][j]=(i+j);//NOTE i,j order here!
}//end inner for
}//end outer for
return 0;
}//end main
Compilar: terminal4$ gcc -g row_maj.c -o row.o Ejecutar: time ./row.o real 0m0.005s user 0m0.001s sys 0m0.003s
Ahora, como pueden ver, el Mayor de Fila fue significativamente más rápido.
¿No convencido? Si desea ver un ejemplo más drástico: haga la matriz 1000000 x 1000000, inicialícela, transpósela e imprímala en stdout. `` `
(Tenga en cuenta que en un sistema * NIX, necesitará establecer ulimit ilimitado)
PROBLEMAS con mi respuesta: " -Optimizing compilers, they change a LOT of things! -Type of system -Please point any others out -This system has an Intel i5 processor -Optimizing compilers, they change a LOT of things! -Type of system -Please point any others out -This system has an Intel i5 processor
He leído mucho sobre esto, cuanto más leo, más confuso me siento.
Según tengo entendido, en la fila, las filas principales se almacenan contiguamente en la memoria, en columnas, las principales se almacenan contiguamente en la memoria. Entonces, si tenemos una secuencia de números [1, ..., 9] y queremos almacenarlos en una matriz principal, obtenemos:
|1, 2, 3|
|4, 5, 6|
|7, 8, 9|
mientras que la columna principal (corrígeme si estoy equivocado) es:
|1, 4, 7|
|2, 5, 8|
|3, 6, 9|
que es efectivamente la transposición de la matriz anterior.
Mi confusión: Bueno, no veo ninguna diferencia. Si iteramos en ambas matrices (por filas en la primera y por columnas en la segunda) cubriremos los mismos valores en el mismo orden: 1, 2, 3, ..., 9
Incluso la multiplicación de matrices es la misma, tomamos los primeros elementos contiguos y los multiplicamos con las segundas columnas de matriz. Entonces, digamos que tenemos la matriz M :
|1, 0, 4|
|5, 2, 7|
|6, 0, 0|
Si multiplicamos la matriz R mayor de la fila anterior por M , eso es R x M obtendremos:
|1*1 + 2*0 + 3*4, 1*5 + 2*2 + 3*7, etc|
|etc.. |
|etc.. |
Si multiplicamos la matriz C la columna principal por M , es decir, C x M tomando las columnas de C lugar de sus filas, obtendremos exactamente el mismo resultado de R x M
Estoy realmente confundido, si todo es lo mismo, ¿por qué existen estos dos términos? Quiero decir que incluso en la primera matriz R , podría mirar las filas y considerarlas columnas ...
¿Me estoy perdiendo de algo? ¿Qué implica row-major vs col-major en realidad en mi matriz matemática? Siempre aprendí en mis clases de álgebra lineal que multiplicamos filas de la primera matriz con columnas de la segunda, ¿cambia eso si la primera matriz estaba en la columna principal? ¿Ahora tenemos que multiplicar sus columnas con columnas de la segunda matriz como lo hice en mi ejemplo o fue simplemente malo?
¡Cualquier aclaración es realmente apreciada!
EDITAR: Una de las otras fuentes principales de confusión que estoy teniendo es GLM ... Así que me cierro sobre su tipo de matriz y presiono F12 para ver cómo se implementa, allí veo una matriz de vectores, así que si tenemos una matriz de 3x3, tener una matriz de 3 vectores. Al observar el tipo de esos vectores, vi ''col_type'', así que asumí que cada uno de esos vectores representa una columna, y así tenemos un sistema columna-mayor ¿verdad?
Bueno, no sé para ser honesto. Escribí esta función de impresión para comparar mi matriz de traducción con glm, veo el vector de traducción en glm en la última fila, y el mío está en la última columna ...
Esto no agrega más confusión. Puedes ver claramente que cada vector en la matriz glmTranslate representa una fila en la matriz. Entonces ... eso significa que la matriz es principal de fila ¿no? ¿Qué hay de mi matriz? (Estoy usando una matriz flotante [16]) los valores de traducción están en la última columna, ¿eso significa que mi matriz es columna mayor y ahora no? trata de evitar que la cabeza gire
Creo que mezclarás un detalle de implementación con el uso, si quieres.
Comencemos con una matriz bidimensional o matriz:
| 1 2 3 |
| 4 5 6 |
| 7 8 9 |
El problema es que la memoria de la computadora es una matriz unidimensional de bytes. Para hacer que nuestra discusión sea más fácil, vamos a agrupar los bytes individuales en grupos de cuatro, así tenemos algo parecido a esto, (cada uno, + - + representa un byte, cuatro bytes representa un valor entero (asumiendo sistemas operativos de 32 bits):
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| | | | | | | | |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
// / /
one byte one integer
low memory ------> high memory
Otra forma de representar
Entonces, la pregunta es cómo mapear una estructura bidimensional (nuestra matriz) en esta estructura unidimensional (es decir, la memoria). Hay dos formas de hacer esto.
Orden de filas mayores: en este orden, colocamos primero la primera fila en la memoria, luego la segunda, y así sucesivamente. Al hacer esto, tendríamos en memoria lo siguiente:
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Con este método, podemos encontrar un elemento dado de nuestra matriz mediante la realización de la siguiente aritmética. Supongamos que queremos acceder al elemento $ M_ {ij} $ de la matriz. Si suponemos que tenemos un puntero al primer elemento de la matriz, digamos ptr , y conocemos el número de columnas que dice nCol , podemos encontrar cualquier elemento por:
$M_{ij} = i*nCol + j$
Para ver cómo funciona esto, considere M_ {02} (es decir, primera fila, tercera columna: recuerde que C se basa en cero.
$M_{02} = 0*3 + 2 = 2
Entonces accedemos al tercer elemento de la matriz.
Orden de columnas principales: en este orden colocamos la primera columna en la memoria primero, y luego la segunda, y así o ... Al hacer esto, tendríamos en memoria lo siguiente:
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1 | 4 | 7 | 2 | 5 | 8 | 3 | 6 | 9 | -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ASÍ, la respuesta corta - el formato row-major y column-major describe cómo las dos matrices dimensionales (o superiores) se mapean en una matriz unidimensional de memoria.
Espero que esto ayude. T.
Tienes razón. no importa si un sistema almacena los datos en una estructura principal o una columna principal. Es como un protocolo. Computadora: "Oye, humano. Voy a almacenar tu matriz de esta manera. No hay problema, ¿eh?" Sin embargo, cuando se trata de rendimiento, importa. considere las siguientes tres cosas.
1. se accede a la mayoría de las matrices en orden de fila mayor.
2. Cuando accede a la memoria, no se lee directamente de la memoria. Primero almacena algunos bloques de datos de la memoria en la memoria caché, luego lees los datos de la memoria caché a tu procesador.
3. Si los datos que desea no existen en la memoria caché, la memoria caché debe recuperar los datos de la memoria
Cuando un caché recupera datos de la memoria, la localidad es importante. Es decir, si almacena datos escasamente en la memoria, su caché debería obtener datos de la memoria con más frecuencia. Esta acción daña el rendimiento de su programa porque acceder a la memoria es mucho más lento (más de 100 veces) y luego acceder a la memoria caché. Cuanto menos acceda a la memoria, más rápido será su programa. Por lo tanto, este conjunto principal de filas es más eficiente porque es más probable que el acceso a sus datos sea local.
No importa lo que uses: ¡sé constante!
Fila mayor o columna mayor es solo una convención. No importa C usa fila mayor, Fortran usa columna. Ambos trabajan. Use lo que es estándar en su lenguaje / entorno de programación.
No coinciden los dos!! @ # $ Cosas arriba
Si utiliza el direccionamiento principal de fila en una matriz almacenada en la columna principal, puede obtener el elemento incorrecto, leer el último extremo de la matriz, etc.
Row major: A(i,j) element is at A[j + i * n_columns]; <---- mixing these up will
Col major: A(i,j) element is at A[i + j * n_rows]; <---- make your code fubar
Es incorrecto decir que el código para hacer la multiplicación de la matriz es el mismo para la fila principal y la columna principal
(Por supuesto, la matemática de la multiplicación de matrices es la misma). Imagine que tiene dos matrices en la memoria:
X = [x1, x2, x3, x4] Y = [y1, y2, y3, y4]
Si las matrices se almacenan en la columna principal, entonces X, Y y X * Y son:
IF COL MAJOR: [x1, x3 * [y1, y3 = [x1y1+x3y2, x1y3+x3y4
x2, x4] y2, y4] x2y1+x4y2, x2y3+x4y4]
Si las matrices se almacenan en fila principal, entonces X, Y y X * Y son:
IF ROW MAJOR: [x1, x2 [y1, y2 = [x1y1+x2y3, x1y2+x2y4;
x3, x4] y3, y4] x3y1+x4y3, x3y2+x4y4];
X*Y in memory if COL major [x1y1+x3y2, x2y1+x4y2, x1y3+x3y4, x2y3+x4y4]
if ROW major [x1y1+x2y3, x1y2+x2y4, x3y1+x4y3, x3y2+x4y4]
No hay nada profundo pasando aquí. Solo son dos convenciones diferentes. Es como medir en millas o kilómetros. Cualquiera de los dos funciona, ¡no se puede pasar de uno a otro sin convertir!
Echemos un vistazo al álgebra primero; álgebra ni siquiera tiene una noción de "diseño de memoria" y esas cosas.
Desde un punto de vista algebraico, una matriz real MxN puede actuar sobre un vector | R ^ N en su lado derecho y producir un vector | R ^ M.
Por lo tanto, si estuviera sentado en un examen y le dieran una matriz MxN y un vector | R ^ N, con operaciones triviales podría multiplicarlos y obtener un resultado; si el resultado es correcto o incorrecto, no dependerá de si el software es su profesor. utiliza para verificar sus resultados internamente utiliza el diseño de columna principal o de fila principal; solo dependerá de si calculó correctamente la contracción de cada fila de la matriz con la (única) columna del vector.
Para producir un resultado correcto, el software, por cualquier medio, esencialmente tendrá que contratar cada fila de la matriz con el vector de columna, tal como lo hizo en el examen.
Por lo tanto, la diferencia entre el software que alinea column-major y el software que usa row-major-layout no es lo que calcula, sino cómo .
Para decirlo de manera más precisa, la diferencia entre esos diseños con respecto a la contracción de la fila única del topcial con el vector de columna es solo el medio para determinar
Where is the next element of the current row?
- Para un layout row-major es el elemento justo en el siguiente cubo en la memoria
- Para una columna-principal-disposición, es el elemento en el cubo M cubos de distancia.
Y eso es.
Para mostrarle cómo esa magia columna / fila se convoca en la práctica:
No ha etiquetado su pregunta con "c ++", pero como mencionó " glm ", supongo que puede llevarse bien con C ++.
En la biblioteca estándar de C ++ hay una infame bestia llamada valarray , que, además de otras características complicadas, tiene sobrecargas de operator [] , una de ellas puede tomar un std::slice (que es esencialmente algo muy aburrido, que consta de solo tres enteros). números de tipo).
Sin embargo, este pequeño trozo de rebanada tiene todo lo que uno necesitaría para tener acceso a una fila-major-storage en forma de columna o una columna-major-storage en fila -tiene inicio, longitud y paso largo- este último representa el " distancia al siguiente cubo "Mencioné.
Hoy no hay ninguna razón para usar otro orden que no sea column-major, hay varias bibliotecas que lo soportan en c / c ++ (eigen, armadillo, ...). Además, el orden de la columna principal es más natural, por ej. las imágenes con [x, y, z] se almacenan por corte en un archivo, este es el orden principal de la columna. Mientras que en dos dimensiones puede ser confuso elegir un orden mejor, en una dimensión más alta, está bastante claro que el orden de columna mayor es la única solución en muchas situaciones.
Los autores de C crearon el concepto de arreglos, pero tal vez no esperaban que alguien lo hubiera usado como matrices. Me sorprendería si viera cómo se usan las matrices en el lugar donde ya todo estaba compuesto en orden fortran y column-major. Creo que el orden mayor de fila es simplemente una alternativa al orden de columna mayor, pero solo en una situación en la que realmente se necesita (por ahora no sé nada).
Es extraño que todavía alguien crea una biblioteca con un orden de fila mayor. Es un desperdicio innecesario de energía y tiempo. Espero que algún día todo sea orden de columna mayor y que todas las confusiones simplemente desaparezcan.
Una breve adición a las respuestas anteriores. En términos de C, donde se accede a la memoria casi directamente, el orden row-major o column-major afecta tu programa de 2 maneras: 1. Afecta el diseño de tu matriz en la memoria 2. El orden de acceso al elemento que debe mantenerse - en forma de bucles de pedido.
- se explica completamente en las respuestas anteriores, por lo que añadiré a 2.
La respuesta de eulerworks señala que en su ejemplo, el uso de la matriz principal de filas provocó una desaceleración significativa en el cálculo. Bueno, él tiene razón, pero el resultado puede invertirse al mismo tiempo.
El orden de bucle era para (sobre filas) {para (sobre columnas) {hacer algo sobre una matriz}}. Lo que significa que el bucle doble accederá a los elementos en una fila y luego pasará a la siguiente fila. Por ejemplo, A (0,1) -> A (0,2) -> A (0,3) -> ... -> A (0, N_ROWS) -> A (1,0) -> .. .
En tal caso, si se almacenara A en el formato principal de fila, habría un mínimo de fallas de caché, ya que los elementos probablemente se alinearán linealmente en la memoria. De lo contrario, en formato de columna principal, el acceso a la memoria saltará utilizando N_ROWS como una zancada. Así que la fila mayor es más rápida en el caso.
Ahora, podemos cambiar el ciclo, de manera que lo haga para (sobre columnas) {para (sobre filas) {hacer algo sobre una matriz}}. Para este caso, el resultado será exactamente el opuesto. El cálculo principal de la columna será más rápido ya que el ciclo leerá elementos en columnas en forma lineal.
Por lo tanto, es mejor que recuerde esto: 1. Seleccionar el formato principal de fila o columna de almacenamiento depende de su gusto, a pesar de que la comunidad tradicional de programación en C parece preferir el formato de fila principal. 2. Aunque tiene la libertad de elegir lo que le guste, debe ser coherente con la noción de indexación. 3. Además, esto es bastante importante, tenga en cuenta que al escribir sus propios algoritmos, intente ordenar los bucles para que respeten el formato de almacenamiento de su elección. 4. Sea consistente.
Dadas las explicaciones anteriores, aquí hay un fragmento de código que demuestra el concepto.
//----------------------------------------------------------------------------------------
// A generalized example of row-major, index/coordinate conversion for
// one-/two-dimensional arrays.
// ex: data[i] <-> data[r][c]
//
// Sandboxed at: http://swift.sandbox.bluemix.net/#/repl/5a077c462e4189674bea0810
//
// -eholley
//----------------------------------------------------------------------------------------
// Algorithm
let numberOfRows = 3
let numberOfColumns = 5
let numberOfIndexes = numberOfRows * numberOfColumns
func index(row: Int, column: Int) -> Int {
return (row * numberOfColumns) + column
}
func rowColumn(index: Int) -> (row: Int, column: Int) {
return (index / numberOfColumns, index % numberOfColumns)
}
//----------------------------------------------------------------------------------------
// Testing
let oneDim = [
0, 1, 2, 3, 4,
5, 6, 7, 8, 9,
10, 11, 12, 13, 14,
]
let twoDim = [
[ 0, 1, 2, 3, 4 ],
[ 5, 6, 7, 8, 9 ],
[ 10, 11, 12, 13, 14 ],
]
for i1 in 0..<numberOfIndexes {
let v1 = oneDim[i1]
let rc = rowColumn(index: i1)
let i2 = index(row: rc.row, column: rc.column)
let v2 = oneDim[i2]
let v3 = twoDim[rc.row][rc.column]
print(i1, v1, i2, v2, v3, rc)
assert(i1 == i2)
assert(v1 == v2)
assert(v2 == v3)
}
/* Output:
0 0 0 0 0 (row: 0, column: 0)
1 1 1 1 1 (row: 0, column: 1)
2 2 2 2 2 (row: 0, column: 2)
3 3 3 3 3 (row: 0, column: 3)
4 4 4 4 4 (row: 0, column: 4)
5 5 5 5 5 (row: 1, column: 0)
6 6 6 6 6 (row: 1, column: 1)
7 7 7 7 7 (row: 1, column: 2)
8 8 8 8 8 (row: 1, column: 3)
9 9 9 9 9 (row: 1, column: 4)
10 10 10 10 10 (row: 2, column: 0)
11 11 11 11 11 (row: 2, column: 1)
12 12 12 12 12 (row: 2, column: 2)
13 13 13 13 13 (row: 2, column: 3)
14 14 14 14 14 (row: 2, column: 4)
*/