• Author / Uploaded
• Adrian Cheje Apaza

Citation preview

Capítulo 6: Vectoriales 1 (Ejercicios de clase) La memoria principal de un procesador vectorial con capacidad de 16 Mpalabras se encuentra distribuida entre 8 módulos utilizando entrelazado de memoria de orden inferior y acceso de tipo S. Suponiendo que el compilador ha almacenado en memoria, por filas, una matriz 4x4, obtenga: (a) Las posiciones de memoria en las que se sitúa la segunda columna de la matriz teniendo en cuenta que la matriz comienza a partir de la posición A6BBh. (b) ¿Puede el procesador leer la segunda columna realizando un único acceso a memoria? ¿Por qué? Solución. (a) Puesto que la memoria tiene 16 Mpalabras, las direcciones serán de 24 bits, y como se encuentra distribuida en 8 módulos con entrelazado de orden inferior, los 3 bits (23=8 módulos) menos significativos de la dirección indican el módulo en que se encuentra la palabra direccionada. Así pues, la dirección de inicio de la matriz 4x4, A6BBh = 0000 0000 1010 0110 1011 1011 se encuentra en el módulo 3 (011), y dentro de ese módulo en la posición (los restantes 21 bits más significativos de la dirección): 0000 0000 1010 0110 1011 1 Según esto, y teniendo en cuenta está almacenada por filas, la matriz se situará en la memoria según se indica en la siguiente tabla, donde se indican en gris las posiciones donde están los elementos de la columna 2 Dirección en el módulo

Módulos

0 1 2 3 (000) (001) (010) (011) 0000 0000 1010 0110 1011 1 (1,1) 0000 0000 1010 0110 1100 0 (2,2) (2,3) (2,4) (3,1) 0000 0000 1010 0110 1100 1 (4,2) (4,3) (4,4)

4 (100) (1,2) (3,2)

5 (101) (1,3) (3,3)

6 (110) (1,4) (3,4)

7 (111) (2,1) (4,1)

Esto quiere decir que las direcciones de los elementos son (uniendo los 21 bits más significativos que indican la profundidad dentro del módulo en la primera columna de la tabla, con los bits que indican el módulo en la columna correspondiente): (1,2) 0A6BCh (2,2) 0A6C0h (3,2) 0A6C4h (4,2) 0A6C8h

(b) puesto que las posiciones de los elementos de la columna están en tres profundidades diferentes y el acceso es de tipo S, en el que se pueden leer en el mismo acceso las palabras que estén a la misma profundidad, se necesitarán tres accesos a memoria. No se puede acceder a la comuna en un sólo acceso.

2 (Ejercicios de clase) En la situación del problema anterior, obtenga el tiempo mínimo que necesitaría el procesador vectorial para acceder a la segunda columna de la matriz suponiendo una frecuencia de 100 Mhz y un tiempo de acceso a memoria Ta=8t, donde t es el tiempo de ciclo del procesador. Solución. Teniendo en cuenta que el acceso es de tipo S y los elementos de la columna están a tres profundidades diferentes, se necesitarán tres accesos. Considerando que se desea acceder a los elementos de la columna de forma ordenada, en el primer acceso se podrá leer el elemento (1,2) necesitándose un tiempo Ta. Mientras se lee el elemento del búfer correspondiente se realiza el segundo acceso para leer los elementos (2,2) y (3,2). Finalmente, mientras se extraen esos elementos de los correspondientes búferes, se realiza el tercer acceso para leer el elemento (4,2). Al terminar el acceso, hay que extraer el elemento (4,2) del búfer, necesitándose un tiempo t. En la Figura 5.7 se esquematiza la secuencia de accesos a memoria.

t

(1,2)

Ta

t t (2,2) (3,2) t (4,2)

Ta Ta Figura 5.7 Secuencia de accesos a memoria para leer la columna 2 de la matriz Por lo tanto el tiempo total para acceder a la columna es: Tcolumna(2) = 3*Ta +t = 3*(8*t)+t = 25*t Teniendo en cuente que la frecuencia es de 100 MHz, t= 10 ns, y el tiempo será Tcolumna(2) = 25*10 = 250 ns

3 (Examen septiembre 2005) Se dispone de una memoria de 8 Mbytes con entrelazado de orden inferior y acceso de tipo S (simultáneo) distribuida en módulos de 256 Kbytes. Se ha almacenado un vector de 138 componentes en posiciones de memoria consecutivas a partir de la posición 34BC5h. ¿Cuántos accesos se necesitan para leer el vector completo? ¿Y si el entrelazado fuera de orden superior (manteniendo el acceso de tipo S)?

Solución. El primer paso para resolver este problema es ver cómo se encuentran repartidos los elementos del vector entre los módulos de memoria. Tenemos una memoria de 8 MB = 223 Bytes, repartida en módulos de 256 KB = 218 Bytes, lo que quiere decir que tendremos un total de 25 = 32 módulos de memoria. Si se utiliza entrelazado inferior y acceso tipo S para acceder a ellos, las posiciones de memoria consecutivas se encontrarán en módulos de memoria consecutivos, y como hay 32 módulos, en el módulo 0 estarán todas las direcciones múltiplo de 32, 0x20 en hexadecimal. Teniendo esto en cuenta, y que el mayor múltiplo de 0x20 por debajo de 0x34BC5 es 0x34BC0, los datos estarán colocados en las posiciones de memoria sombreadas de la siguiente figura: Direcció 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 00 n 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 0x34BC0 0x34BE0 0x34C00 0x34C20 0x34C40

Con lo que para acceder a todos los datos del vector tendremos que generar las 5 direcciones de la primera columna de la tabla anterior, es decir, que son necesarios 5 accesos a memoria. En el caso de que se utilizara entrelazado superior, las posiciones de memoria consecutivas se encontrarían en el mismo módulo. Tanto la dirección de comienzo como la de final del vector se encontrarían en el módulo de memoria 0, que contendría las posiciones de memoria desde la dirección 0x000000 a la 0x40000, con lo que harían falta 138 accesos a memoria, tantos como componentes, para leer el vector.

4 (Examen septiembre 2006) Se dispone de una memoria de 16 Mbytes con entrelazado de orden inferior y acceso de tipo S (simultáneo) distribuida en módulos de 512 Kbytes. Se ha almacenado un vector de 113 componentes en posiciones de memoria consecutivas a partir de la posición 21BC5h. ¿Cuántos accesos se necesitan para leer el vector completo? ¿Y si el entrelazado fuera de orden superior (manteniendo el acceso de tipo S)? Solución. El primer paso para resolver este problema es ver cómo se encuentran repartidos los elementos del vector entre los módulos de memoria. Tenemos una memoria de 16 MB = 224 Bytes, repartida en módulos de 512 KB = 219 Bytes, lo que quiere decir que tendremos un total de 25 = 32 módulos de memoria. Si se utiliza entrelazado inferior y acceso tipo S para acceder a ellos, las posiciones de memoria consecutivas se encontrarán en módulos de memoria consecutivos, y como hay 32 módulos, en el módulo 0 estarán todas las direcciones múltiplo de 32, 0x20 en hexadecimal. Teniendo esto en cuenta, y que el mayor múltiplo de 0x20 por debajo de 0x021BC5 es 0x034BC0 (escribimos las direcciones con 6 dígitos para hacer hincapié en que la memoria tiene 16 MB, y que por tanto, se direcciona con direcciones de 24 bits o 6 dígitos hexadecimales), los datos estarán colocados en las posiciones de memoria sombreadas de la siguiente figura:

Dirección 00

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F

0x021BC0 0x021BE0 0x021C00 0x021C20

Con lo que para acceder a todos los datos del vector tendremos que generar las 4 direcciones de la primera columna de la tabla anterior, es decir, que son necesarios 4 accesos a memoria. En el caso de que se utilizara entrelazado superior, las posiciones de memoria consecutivas se encontrarían en el mismo módulo. Tanto la dirección de comienzo como la de final del vector se encontrarían en el módulo de memoria 0, que contendría las posiciones de memoria desde la dirección 0x0000000 a la 0x03FFFF (2 19 – 1), con lo que harían falta 113 accesos a memoria, tantos como componentes, para leer el vector.

5 (Ejercicios de clase) Un procesador vectorial con registros vectoriales de 8 elementos tiene una memoria de 1 Mpalabra distribuida entre 8 módulos con entrelazado de orden superior y acceso de tipo C. Suponiendo que la primera componente se encuentra en la posición AA012h, ¿en qué posiciones situaría los restantes 7 componentes para que el acceso a dicho vector sea lo más rápido posible? Solución. Teniendo en cuenta que la memoria tiene una capacidad de 1 Mpalabra la dirección de palabra consta de 20 bits, y como está distribuida en 8 módulos con entrelazado superior, la dirección de módulo corresponde a los 3 bits más significativos. En la Figura 5.6 se muestra la distribución de bits de direcciones y la estructura de interconexión para el acceso tipo C. a19 a17 a16

a0

módulo posición en el módulo

R/W

Señales Ocupado/ Completo

M7

M6

M0 Registros de Direcciones y control

Controlador de Memoria a19 a18 a17 a16 a0

decod

a[16:0] Entrelazado Superior y Acceso C

Figura 5.6 Direcciones y estructura para el acceso C

La dirección del primer elemento a cargar en memoria es: AA012h = 1010 1010 0000 0001 0010 Por lo que los tres bits más significativos son 101, indicando que se encuentra en el módulo 5 (101) a la profundidad 0 1010 0000 0001 0010 Para que el acceso sea lo más rápido posible, teniendo en cuenta que el acceso es tipo C, la única restricción es que las direcciones de los demás elementos se encuentren en módulos de memoria diferentes. Además, aunque es lógico considerar que los 8 elementos 0,1,2,..,7 del vector se encuentren en direcciones crecientes de memoria, esto es contradictorio con la necesidad de que el acceso sea lo más rápido posible ya que al utilizarse entrelazado superior posiciones de memoria consecutivas estarán en el mismo módulo. Una forma posible para situarlas es que estén en profundidades consecutivas Según esto, las direcciones serían: Componente 0 Componente 1 Componente 2 Componente 3 Componente 4 Componente 5 Componente 6 Componente 7

       

AA012h

=

1010 1010 0000 0001 0010 1100 1010 0000 0001 0010 = CA012h 1110 1010 0000 0001 0010 = EA012h 0000 1010 0000 0001 0011 = 0A013h 0010 1010 0000 0001 0011 = 2A013h 0100 1010 0000 0001 0011 = 4A013h 0110 1010 0000 0001 0011 = 6A013h 1000 1010 0000 0001 0011 = 8A013h

Con lo que se han introducido las componentes del vector en los 8 módulos y a dos profundidades distintas (la 0 1010 0000 0001 0011 y la 0 1010 0000 0001 0010. El tiempo de acceso a la línea será Ta+8 es decir, el tiempo de acceso a memoria para captar la primera palabra, más un tiempo  necesario para extraer la componente leída desde los circuitos de acceso a memoria.

6 (Examen diciembre 2004) En un procesador vectorial a 2 GHz, con registros vectoriales de 8 componentes, una única unidad de carga/almacenamiento de memoria (LV/SV), un único multiplicador y un único sumador, se ejecuta el bucle: for (i = 0 ; i < n ; i++) Y [i] = a*X [i][0] + b; donde Y es un vector de n elementos y X es una matriz de n filas por 6 columnas almacenada por filas. Si la memoria de este computador está separada físicamente en 8 módulos accedidos con entrelazado inferior, (a) Determine en qué posición de cada módulo de memoria estará colocada cada componente de la primera columna de X si X[0][0] está colocado en la posición 0x00120 y n = 8. (b) Con esta colocación de los

elementos de X en memoria, ¿cuál sería el tiempo de latencia inicial (TLI) y el tiempo por componente (TPC) para la lectura de la primera columna de X si el acceso a memoria es de tipo C y el tiempo de acceso para cada módulo es Ta = 8 ciclos? Solución. Para responder al primer apartado, dibujaremos el contenido de la memoria desde la posición 0x00120, en la que se encuentra X[0][0], hasta la posición 0x0014F, en la que se encuentra X[7][5], ya que X es una matriz de 6 columnas por 8 filas (n = 8).

0x00120 0x00128 0x00130 0x00138 0x00140 0x00148

0

1

2

3

4

5

6

7

X00 X12 X24 X40 X52 X64

X01 X13 X25 X41 X53 X75

X02 X14 X30 X42 X54 X70

X03 X15 X31 X43 X55 X71

X04 X20 X32 X44 X60 X72

X05 X21 X33 X45 X61 X73

X10 X22 X34 X50 X62 X74

X11 X23 X35 X51 X63 X75

Con esta colocación de los elementos, un acceso a memoria concurrente (tipo C) no podrá servirnos la primera columna de X a un ritmo de una componente por ciclo, ya que se puede comprobar que tenemos contención de memoria en los módulos 0, 2, 4 y 6. Por tanto, se podrán solapar las cuatro primeras lecturas, pero las cuatro siguientes se tendrán que retrasar hasta que terminen las primeras, gráficamente Módulo 0 (Ta = 8) X00 Módulo 6 (Ta = 8) X10 Módulo 4 (Ta = 8) X20 Módulo 2 (Ta = 8) X30 Módulo 0 (Ta = 8) X40 X50 Módulo 6 (Ta = 8) Módulo 4 (Ta = 8) X60 Módulo 2 (Ta = 8) X70 Módulo 0 (Ta = 8) 8

Contención

Contención

En consecuencia, podemos concluir que debido a la colocación de los datos en memoria, para acceder a la primera columna de X tendremos un TLI = 8 (igual al tiempo de acceso a memoria) y un TPC = 2, ya que para cada cuatro datos empleamos cuatro ciclos en su lectura más otros cuatro ciclos de contención, por tanto, para leer n datos colocados en memoria de esta forma emplearíamos: T(n) = TLI + n · TPC = 8 + 2n ciclos

7 (Ejercicios de clase) Suponiendo que el tiempo de latencia de inicio (start-up), TLI, para una multiplicación vectorial es de 10 ciclos de reloj y que después, el tiempo por resultado, TPC, es de 1 ciclo de reloj. ¿Cuál es el número de ciclos de reloj por resultado, CPR, para un vector de 64 componentes?

Solución. Aplicando la expresión del tiempo de cálculo vectorial TCV TC V  TLI  K *TPC se tiene que TCV = 10 + 64*1 = 74 ciclos, y por lo tanto el número de ciclos por resultado es C PR 

TCV 74   1 .1 5 6 K 64

Por lo tanto, cada operación de multiplicación de un componente de cada vector consume un promedio de 1.156 ciclos.

8 (Ejercicios de clase) Si el tiempo de latencia de inicio (TLI) para una operación en un cauce vectorial es (4/3)T, siendo T el tiempo de ejecución de dicha operación sobre un cauce escalar, y el cauce vectorial genera un resultado cada T/3. ¿Cuál es el valor de Nv (número de componentes que debe tener un vector para hacer que el modo vectorial sea más rápido que el escalar) para dicho cauce? Solución. En la operación vectorial se tiene que TCV = TLI + K*TPC = (4/3)T + K (1/3)T = (T/3) (4+K) El tiempo de ejecución de la operación en modo escalar (TCE) es igual al tiempo de ejecución de la operación (T) multiplicado por el número de operaciones realizadas (K). Se pide el valor de Nv, es decir el valor de K para el que TCE ≤ TCV: T*Nv ≥ (T/3)(4+Nv) de donde (4/3) ≤ (2/3)Nv

→

Nv ≥ 2

Es decir, que a partir de dos componentes, el modo vectorial es más rápido que el escalar. Esta situación es ideal para un procesador vectorial puesto que el número de componentes a partir del que interesa realizar la operaciones sobre un conjunto de números como operación vectorial es el menor posible (dos, es decir más de una operación a realizar). Las razones de esta situación se pueden encontrar es que el tiempo de latencia de inicio no es mucho mayor que el tiempo de operación secuencial y el TPC es reducido (tres veces menor que el tiempo secuencial).

9 (Ejercicios de clase) Para un valor de TLI fijo, ¿es cierto que, a medida que TPC aumenta, disminuye la longitud mínima del vector a la que el valor de TLI no es mayor que una fracción de TCV dada? Solución. En el problema se indica que el tiempo de latencia TLI no debe ser mayor que una fracción dada de TCV, por lo tanto se tiene que: TLI TLI   C onst TC V TLI  K *TPC donde Const es una constante (TLI es una fracción constante de TCV). La igualdad anterior se puede expresar como: K *TPC 

T L I * (1  C o n s t ) C o n st

Como además, se indica que TLI se mantiene constante, también se mantendrá invariante la parte derecha de la igualdad anterior: T L I * (1  C o n s t )  c C on st donde c se mantiene constante también. Por consiguiente, si K*TPC = c cuando TPC crece, K decrece; y si TPC decrece, K crece, como se quería demostrar. Lo que se ha demostrado significa que, para un valor de TLI dado, a medida que el cauce es más rápido (es decir, TPC es más pequeño), aumenta la longitud de los operadores vectoriales necesaria para que el TLI sea un porcentaje prefijado del tiempo de procesamiento total. Dicho de otra manera, cuanto más rápido genera resultados un cauce vectorial, más largos tendrán que ser los vectores para hacer despreciable el valor del tiempo de latencia inicial.

10 (Ejercicios de clase) Si para un cauce el tiempo de latencia de inicio, TLI, es de 6 ciclos, y el tiempo por resultado, TPC, es 1 ciclo.¿Cuál ha de ser la longitud mínima del vector que procese ese cauce para que el TLI no representa más de un 5% del total del procesamiento? Solución. Teniendo en cuenta que TLI =6 y TPC=1, se cumple que

TCV = TLI + K*TPC = 6 + K Si el tiempo de latencia de inicio no puede ser mayor que el 5% del tiempo total se tiene que TLI ≤ 0.05 * TCV

→

6 ≤ 0.05 * (6+K)

y despejando, 0.95*6 ≤ 0.05*K

→

K ≥ (5.7/0.05) = 114

Es decir que, para vectores mayores de 114 componentes se tendrá que el tiempo de latencia de inicio es menor del 5% del tiempo de cómputo total. Para que este resultado sea correcto debe cumplirse que el número de componentes de los registros vectoriales del procesador vectorial sea mayor que 114 (un valor posible y realista en ciertos procesadores, sobre todo de fabricantes japoneses puede ser 128). Si el tamaño de los registros vectoriales es menor que 114 (MVL ≤ 114) entonces hay que explicar la expresión del tiempo de procesamiento para el caso de troceado de vector:  K  T L I  0 .0 5 * ( T B A S E   * (T BUCLE  T L I )  K * T P C  M V L  Para poder determinar explícitamente K, habría que conocer los valores de MVL, TBUCLE, y TBASE. Supondremos valores típicos para ellos, utilizados en problemas anteriores: MVL =64

TBUCLE=15

TBASE=10

y sustituyendo  K 6  0 .0 5 * ( 1 0   64

  * 2 1  K )

Para determinar K: - Si se supone K ≤ 64 : Al despejar K de la expresión anterior se tiene que K>89, y no es coherente con la suposición. - Si se supone 64 < K ≤ 128: Al despejar K de la expresión anterior se tiene que K ≥ 68, que es coherente con la suposición. Es lógico que ahora el valor de K sea menor que en el cálculo anterior (68, en lugar de 114) dado que el tiempo de cálculo aumenta al incluirse los tiempos TBUCLE y TBASE.

11 (Ejercicios de clase) Calcule los valores de Rinf y N1/2 para la secuencia de instrucciones de la figura 5.3 suponiendo que se encuentran dentro de un bucle como resultado de aplicar la técnica

de troceado de vector ('strip minning'). La secuencia de instrucciones tarda un tiempo TCV=241 ciclos, TPC=3 ciclos, la frecuencia de reloj es de 80 Mhz, y el tamaño de los registros vectoriales es de 64 componentes. Los valores de los tiempos TLI se dan en la Tabla 1, TBASE=10, y TBUCLE=15. TABLA 1 Operación TLI Operación LV V1,Rx MULTV a,V1 LV V2,Ry

Suma Vectorial 6

Mult. Vectorial 7

Comienza (Ciclo) 0 12+1=13 76+1=77

División Vect. 20

Carga Vectorial 12

Termina (Ciclo) 12+64=76 13+7+64=84 77+12+64=153

Comentario Latencia simple Encadenada a LV Comienza después del primer LV realizado (contención de mmoria) ADDV V3,V2,V1 77+1+12=90 90+6+64=160 Encadenada a MULTV y LV SV Ry,V3 160+1+4=165 165+12+64=241 Debe esperar en ADDV; no encadenada (contención de memoria) Figura 5.3 Distribución temporal de operaciones Solución. Para resolver el problema se parte de la expresión del tiempo de cálculo vectorial cuando se aplica troceado del vector.  n  Tn  T BASE   * (T BU CLE  T L I )  n * T P C  M V L  donde, para determinar los parámetros que se necesitan, se tiene en cuenta el tiempo de procesamiento que se proporciona en la Figura 5.3 para vectores de 64 componentes (caben en los registros vectoriales del procesador): TCV=241 ciclos Utilizando el modelo de prestaciones del cauce que definen las operaciones vectoriales realizadas, TCV=TLI+k*TPC, donde k≤MVL. En este caso MVL=64, y k=64 (Figura 5.3), y como en el enunciado se indica que TPC=3 se puede despejar TLI: 241 = TLI + 64*3

→

TLI = 241 – 64*3 = 49

Aunque en el enunciado se proporciona explícitamente el valor de TPC para facilitar la obtención de TLI, ambos parámetros se pueden obtener a partir de la distribución temporal de operaciones que se muestra en la Figura 5.3 del enunciado. Esto se puede hacer a partir del esquema que se muestra en la Figura 5.4 (que no es más que una representación gráfica de los datos de la Figura 5.3).

12

64

1+12+1

6

64

1+4+12

64

TCV = (12+1+12+1+6+1+4+12)+3*64 TLI=49 TPC=3 Figura 5.4 Secuencia de operaciones vectoriales (encadenamientos y concurrencia) Utilizando, además, que TBUCLE=15, TBASE=10, y MVL=64, se tiene que  n Tn  1 0   64

  n * ( 1 5  4 9 )  3 * n  1 0    6 4

  * 6 4  3 * n

Como el número de operaciones vectoriales que se realiza es 2 (MULTSV y ADDV), y teniendo en cuenta que la frecuencia del procesador es de 80 MHz, se tiene que Rn 

O p e r a c .V e c t o r .* n * f r e c u e n c i a  T n ( c ic lo s )

2 * n *80 M FLO PS  n  10  64 *    3* n 64 

Para determinar el valor de Rinf hay que obtener el límite de Rn. Esto se puede realizar teniendo en cuenta que se pueden establecer las cotas 2 * n *80 2 * n *80  Rn  n n 10  (  1) * 6 4  3n 10  ( )* 64  3* n 64 64 y si se aplican los límites al infinito a la cota inferior y superior, ambas convergen a (160*n)/(4*n), con lo que Rinf = 40 MFLOPS Para calcular N1/2 se tiene en cuenta que 1 R 2

in f

 20 

2 * n *80  n  10   * 64  3* n 64 

y para despejar n, en primer lugar supondremos que n