distribucionDeDatosArreglos

Computación Distribuida
Distribución de datos para arreglos de dos dimensiones

Oscar Loor
Ingeniería en Sistemas
Escuela Politécnica Nacional
Quito, Ecuador
dwquito@hotmail.com

Resumen— Explicación sobre la distribución de datos para
arreglos de dos dimensiones, mediante el uso de la técnica
blockwise columnwise.
Palabras clave— blockwise; columnwise; distribución de datos;
arreglos de dosdimensiones

I. INTRODUCCIÓN
Cuando se trabaja con gran cantidad de datos, es necesario
utilizar técnicas que nos permitan obtener un mejor tiempo de
ejecución y obtener al mismo tiempo el resultado correcto.
Una alternativa es la de descomponer el arreglo en sub
arreglos y asignar estos sub arreglos a procesadores diferentes,
esta técnica se conoce como:
 Data distribution
 Data descomposition
Data partitioning

B. Procesador Uno
Comando: cat /proc/cpuinfo (1era Parte)
Datos obtenidos:
Tamaño de Cache: 4MB

La idea principal es que los procesadores trabajen al mismo
tiempo sobre diferentes lugares de los datos.
Esta técnica se puede utilizar en computadoras de los tipos:
 Distributed Memory Machines
 Shared Memory Machines
II. INFORMACIÓN SOBRE EL COMPUTADOR
Mediante el uso dealgunos comandos identificaremos los
elementos clave, los cuales nos permitirán identificar las
características de la computadora en la cual vamos a realizar
las pruebas.
A. Detalles sobre el computador
Comando: lscpu
Datos obtenidos:
Procesador de 32 bits
2 CPU
L1 data cache: 32KB
L1 instruction cache: 32KB
L2 cache: 4MB

C. Procesador Dos
Comando: cat /proc/cpuinfo (2da Parte)
Datos obtenidos:
Tamañode Cache: 4MB

D. Línea de cache procesador Uno
Comando: cat
/sys/devices/system/cpu/cpu0/cache/index0/coherenc
y_line_size
Datos obtenidos:
Tamaño de la línea de cache: 64KB
E. Línea de cache procesador Dos
Comando: cat
/sys/devices/system/cpu/cpu1/cache/index0/coherenc
y_line_size
Datos obtenidos:
Tamaño de la línea de cache: 64KB

III. DISTRIBUCIÓN DE DATOS PARA ARREGLOS DE DOS
DIMENSIONESEn este tipo de arreglos utilizamos combinaciones de:
 Blockwise data distribution
 Cyclic data distribution
 Block – cyclic data distribution
En solo una de las dimensiones o en ambas.

2) Codigo en C
Utilizando un archivo guardado en el computador el cual
contiene varios registros, el objetivo será calcular el número
de veces que aparece cada caracter, para facilidad utilizaremos
el valornumérico de cada carácter utilizando ASCII
a) Número de filas y espacio sobrante
Primero necesitaremos identificar el número de filas totales
que tendrá nuestro arreglo, para lo cual utilizaremos el tamaño
de la línea de cache (64KB) y el número de Bytes que
contiene el archivo.
Debemos tener en cuenta, que puede que el archivo no ocupe
exactamente la cantidad de columnas disponibles sino quesobren algunas.
El argumento [1], es el archivo que deseamos leer
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

struct stat stats;
stat (argv[1], &stats);
N = stats.st_size;
int tamanioDeCache;
tamanioDeCache = 64*1024;
numeroDeFilas = (int)ceil((float)N/(float)tamanioDeCache);
int existeSobrante = N%tamanioDeCache;
if(existeSobrante!=0){
//Si existe sobrante
}else{
//No existe sobrante
}b) Arreglos que contendran los puntos iniciales y finales
de cada fila para poder distribuir al procesador respectivo
Definición de una estructura de datos
0. typedef struct args {
17. int fd;
// descriptor del archivo
18. int ini;
// inicio del segmento de archivo
19. int fin;
// fin del segmento
20. } arg;

A. Distribuciones considerando una sola dimension
1) Blockwise columnwise (o rowwise)Construimos P bloques de columnas contiguas (o filas) de
igual tamaño y asignamos el bloque a cada procesador

Para poder recorrer todos los datos debemos realizar varias
pasadas y para esto declararemos dos arreglos los cuales nos
permitirán almacenar los datos para cada una.

Basándonos en la información obtenida conocemos que el
número de procesadores es 2 y el tamaño de línea de cache
65536....