Universidad de Costa Rica. Escuela de Computación. CI-0117 Programación Paralela y Concurrente
2019b. Grupo 02. Examen 02 [13-Dic-2019]. Profesor Jeisson Hidalgo-Céspedes.
Área de nubes
Se requiere un software eficiente que pueda detectar nubes en imágenes satelitales. Para esta versión se requiere un programa en C o C++ que simplemente reporte cuántas nubes hay en una imagen, y el área de cada una de ellas. El programa recibe tres argumentos de línea de comandos: un nombre de archivo, y el valor mínimo y el valor máximo que definen una nube. Por ejemplo, la siguiente invocación solicita detectar las nubes en el archivo image001.bin, las cuales forman regiones de valores entre 0.8 y 1.0.
./clouds image001.bin 0.8 1.0El archivo se encuentra almacenado en memoria secundaria y es binario. Los primeros 8 bytes almacenan la cantidad de filas rows y los siguientes 8 bytes la cantidad de columnas cols, ambas como enteros sin signo (size_t) en little endian. Seguidamente vendrán rows * cols valores flotantes de doble precisión obtenidos por el satelite. Puede suponer que el archivo siempre es correcto. La Figura 1 muestra un ejemplo textual de uno de estos archivos. Para la parte en papel de esta evaluación puede suponer que los archivos son de texto como el de la Figura 1.
El programa debe reconocer las nubes que se encuentran en el archivo de datos y reportarlas una a una en el orden de aparición de izquierda-derecha y arriba-abajo. Para cada nube se reporta su número y su área, esta última medida como el número de celdas que la nube abarca. La Figura 2 muestra un ejemplo de salida.
Las nubes se pueden reconocer con un algoritmo de búsqueda en profundidad (DFS, Depth-First Search), que encuentra regiones dentro de una matriz. Si la imagen satelital se aloja en una matriz image de dimensiones rows * cols, el algoritmo serial de la Figura 3 reporta la cantidad de regiones con valores en el rango [a,b] y el área de cada una de ellas. Sugerencia: recorra el algoritmo de la Figura 3 con el ejemplo de la Figura 1.
El algoritmo usa una matriz espejo mirror, de rows * cols enteros, donde mirror[r][c] = 0 indica que la celda image[r][c] no ha sido visitada, un valor positivo mirror[r][c] = P indica que la celda image[r][c] forma parte de la región (nube) identificada con ese número P, y un valor negativo que la celda no forma parte de ninguna región (nube). El algoritmo guarda en una colección dinámica cloud_areas[] el área de cada región (nube) detectado, medida como la cantidad de celdas que abarca.
Dado que las imágenes producidas por el satélite son de tamaño considerable (ej.: 21000x21000), se requiere paralelizar el algoritmo de búsqueda de nubes de tal forma que pueda aprovechar eficientemente un clúster de computadoras. Implemente su solución en C o C++ usando distribución con MPI. Su solución debe ser correcta, de tal forma que produzca los mismos resultados que la versión serial. El control de concurrencia y la comunicación que realice para mantener la corrección y funcionalidad del algoritmo debe comprometer lo mínimo posible la eficiencia de su solución.
Opcional: Haga que su solución aproveche todos los núcleos disponibles del nodo donde se ejecute usando concurrencia híbrida con MPI y OpenMP.
11 8
0.1 0.2 0.4 0.6 0.8 0.7 0.4 0.0
0.0 0.3 0.5 0.7 0.9 0.6 0.3 0.5
0.7 0.2 0.7 0.9 0.8 0.8 0.5 0.8
0.8 0.6 0.7 0.9 1.0 0.9 0.7 0.8
0.9 0.8 0.7 0.8 1.0 0.9 0.8 0.6
0.7 0.5 0.6 0.7 0.8 0.9 0.7 0.4
0.4 0.6 0.7 0.8 0.7 1.0 0.8 0.5
0.7 0.8 0.7 0.7 0.8 0.8 0.6 0.2
1.0 0.9 0.7 0.6 0.8 0.7 0.3 0.0
0.7 1.0 0.7 0.6 0.7 0.5 0.2 0.1
0.7 0.9 1.0 0.8 0.6 0.4 0.1 0.01: 19
2: 2
3: 3
4: 1
5: 7main:
shared rows := read_integer()
shared cols := read_integer()
shared image[rows][cols] := read_real()[rows][cols]
shared mirror[rows][cols] := 0[rows][cols]
shared cloud_count := 0
shared cloud_areas[] := []
search_clouds()
print_clouds()
search_clouds:
for row := 0 to rows - 1 do
for col := 0 to cols - 1 do
if mirror[row][col] = 0 then
if a ≤ image[row][col] ≤ b then
++cloud_count
cloud_areas[clould_count] := 0
expand_cloud(row, col)
else
mirror[row][col] := -1
expand_cloud(row, col):
if not exists(row, col) then
return
if mirror[row][col] ≠ 0 then
return
if a <= image[row][col] ≤ b then
mirror[row][col] := cloud_count // cell belongs to cloud
++cloud_areas[cloud_count]
expand_cloud(row - 1, col + 0) // top
expand_cloud(row + 0, col - 1) // left
expand_cloud(row + 1, col + 0) // bottom
expand_cloud(row + 0, col + 1) // right
else
mirror[row][col] := -1
exists(row, col):
return row ≥ 0 and row < rows and col ≥ 0 and col < cols
print_clouds:
for index := 1 to cloud_count do
println(index, ": ", cloud_areas[index])
