summaryrefslogtreecommitdiff
path: root/mpi
diff options
context:
space:
mode:
Diffstat (limited to 'mpi')
-rw-r--r--mpi/Makefile21
-rw-r--r--mpi/build/.gitignore2
-rwxr-xr-xmpi/golbin0 -> 155352 bytes
-rw-r--r--mpi/include/create_grid.h12
-rw-r--r--mpi/include/file.h11
-rw-r--r--mpi/include/game.h19
-rw-r--r--mpi/output/.gitignore2
-rw-r--r--mpi/src/create_grid.c38
-rw-r--r--mpi/src/file.c17
-rw-r--r--mpi/src/game.c56
-rw-r--r--mpi/src/main.c220
11 files changed, 398 insertions, 0 deletions
diff --git a/mpi/Makefile b/mpi/Makefile
new file mode 100644
index 0000000..0a464a4
--- /dev/null
+++ b/mpi/Makefile
@@ -0,0 +1,21 @@
+.DEFAULT_GOAL := all
+
+INCLUDES = -I include/
+FLAGS= -std=c99
+
+game.o: include/game.h src/game.c
+ mpicc -c src/game.c $(INCLUDES) $(FLAGS) -o build/game.o
+
+file.o: game.o include/file.h src/file.c
+ mpicc -c src/file.c $(INCLUDES) $(FLAGS) -o build/file.o
+
+create_grid.o: file.o game.o include/create_grid.h src/create_grid.c
+ mpicc -c src/create_grid.c $(INCLUDES) $(FLAGS) -o build/create_grid.o
+
+gol: game.o file.o create_grid.o
+ mpicc $(INCLUDES) $(FLAGS) -o gol build/game.o build/file.o build/create_grid.o src/main.c
+
+clean:
+ $(RM) build/*.o gol output/*.bin
+
+all: gol
diff --git a/mpi/build/.gitignore b/mpi/build/.gitignore
new file mode 100644
index 0000000..d6b7ef3
--- /dev/null
+++ b/mpi/build/.gitignore
@@ -0,0 +1,2 @@
+*
+!.gitignore
diff --git a/mpi/gol b/mpi/gol
new file mode 100755
index 0000000..f7d934c
--- /dev/null
+++ b/mpi/gol
Binary files differ
diff --git a/mpi/include/create_grid.h b/mpi/include/create_grid.h
new file mode 100644
index 0000000..45ac891
--- /dev/null
+++ b/mpi/include/create_grid.h
@@ -0,0 +1,12 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "file.h"
+#include "game.h"
+
+#ifndef CREATE_GRID_H
+#define CREATE_GRID_H
+
+void print_grid(struct GAME* game);
+void create_grid(int argc, char** argv);
+
+#endif // CREATE_GRID_H
diff --git a/mpi/include/file.h b/mpi/include/file.h
new file mode 100644
index 0000000..b2db380
--- /dev/null
+++ b/mpi/include/file.h
@@ -0,0 +1,11 @@
+#include "game.h"
+#include <stdlib.h>
+#include <stdio.h>
+
+#ifndef FILE_H
+#define FILE_H
+
+void read_in(char* filename, struct GAME* game);
+void write_out(char* filename, struct GAME* game);
+
+#endif //FILE_H
diff --git a/mpi/include/game.h b/mpi/include/game.h
new file mode 100644
index 0000000..135fd8a
--- /dev/null
+++ b/mpi/include/game.h
@@ -0,0 +1,19 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#ifndef GAME_H
+#define GAME_H
+
+struct GAME {
+ unsigned char* grid;
+ int padding;
+ int width;
+ int height;
+};
+
+int neighbors(struct GAME* game, int x, int y, unsigned char* halo_above, unsigned char* halo_below);
+void next(struct GAME* game, unsigned char* halo_above, unsigned char* halo_below);
+void randomize(struct GAME* game);
+
+#endif // GAME_H
diff --git a/mpi/output/.gitignore b/mpi/output/.gitignore
new file mode 100644
index 0000000..d6b7ef3
--- /dev/null
+++ b/mpi/output/.gitignore
@@ -0,0 +1,2 @@
+*
+!.gitignore
diff --git a/mpi/src/create_grid.c b/mpi/src/create_grid.c
new file mode 100644
index 0000000..b89d077
--- /dev/null
+++ b/mpi/src/create_grid.c
@@ -0,0 +1,38 @@
+#include "create_grid.h"
+
+void print_grid(struct GAME* game) {
+ printf("\n===GRID===\n");
+ for (int y = 0; y < game->height; y++) {
+ for (int x = 0; x < game->width; x++) {
+ printf("%i ", game->grid[y*(game->width+game->padding*2) + x]);
+ }
+ printf("\n");
+ }
+}
+
+void create_grid(int argc, char** argv) {
+ char* filename;
+ struct GAME game;
+ game.padding = 0;
+ if (argc == 5) {
+ game.width = atoi(argv[2]);
+ game.height = atoi(argv[3]);
+ filename = argv[4];
+ } else {
+ printf("Usage: ./gol create-grid <width> <height> <filename>\n");
+ exit(1);
+ }
+
+ int size = (game.width+game.padding*2) * (game.height+game.padding*2);
+ unsigned char* grid = (unsigned char*)malloc(sizeof(unsigned char) * size);
+ for (int y = 0; y < game.height; y++) {
+ printf("Row %i: ", y);
+ for (int x = 0; x < game.width; x++) {
+ char temp;
+ scanf("%i%c", (unsigned int*)&game.grid[y*(game.width+game.padding*2) + x],&temp);
+ }
+ }
+ game.grid = grid;
+ write_out(filename, &game);
+ print_grid(&game);
+}
diff --git a/mpi/src/file.c b/mpi/src/file.c
new file mode 100644
index 0000000..46ba46a
--- /dev/null
+++ b/mpi/src/file.c
@@ -0,0 +1,17 @@
+#include "file.h"
+
+void read_in(char* filename, struct GAME* game) {
+ FILE* file = fopen(filename, "rb");
+ for (int i = game->padding; i < game->height+game->padding; i++) {
+ fread(&game->grid[i*(game->width + 2*game->padding) + game->padding], sizeof(unsigned char), game->width, file);
+ }
+ fclose(file);
+}
+
+void write_out(char* filename, struct GAME* game) {
+ FILE* file = fopen(filename, "w+");
+ for (int i = game->padding; i < game->height+game->padding; i++) {
+ fwrite(&game->grid[i*(game->width + 2*game->padding) + game->padding], sizeof(unsigned char), game->width, file);
+ }
+ fclose(file);
+}
diff --git a/mpi/src/game.c b/mpi/src/game.c
new file mode 100644
index 0000000..de73f67
--- /dev/null
+++ b/mpi/src/game.c
@@ -0,0 +1,56 @@
+#include "game.h"
+
+int neighbors(struct GAME* game, int x, int y, unsigned char* halo_above, unsigned char* halo_below) {
+ int n = 0;
+
+ for (int dy = -1; dy <= 1; dy++) {
+ for (int dx = -1; dx <= 1; dx++) {
+ if (!(dx == 0 && dy == 0) && (x+dx) > 0 && (x+dx) < game->width+(game->padding*2)) {
+ if (y+dy == -1 && halo_above != NULL) {
+ if (halo_above[x+dx]) {
+ n++;
+ }
+ } else if (y+dy == game->height && halo_below != NULL) {
+ if (halo_below[x+dx]) {
+ n++;
+ }
+ } else if (game->grid[(y+dy) * (game->width+game->padding*2) + (x+dx)]) {
+ n++;
+ }
+ }
+ }
+ }
+ return n;
+}
+
+void next(struct GAME* game, unsigned char* halo_above, unsigned char* halo_below) {
+ unsigned char* newGrid = malloc(sizeof(unsigned char) * game->height * (game->width + 2*game->padding));
+ for (int y = 0; y < game->height; y++) {
+ for (int x = 0; x < game->width + 2*game->padding; x++) {
+ int my_neighbors = neighbors(game, x, y, halo_above, halo_below);
+ int my_coord = y * (game->width+game->padding*2) + x;
+ newGrid[my_coord] = 0; // It's possible that there are artifacts from the last iteration
+ if (game->grid[my_coord]) {
+ if (my_neighbors < 2 || my_neighbors > 3) {
+ newGrid[my_coord] = 0;
+ } else {
+ newGrid[my_coord] = 1;
+ }
+ } else {
+ if (my_neighbors == 3) {
+ newGrid[my_coord] = 1;
+ }
+ }
+ }
+ }
+ free(game->grid);
+ game->grid = newGrid;
+}
+
+void randomize(struct GAME* game) {
+ for (int y = game->padding; y < game->height+game->padding; y++) {
+ for (int x = game->padding; x < game->width+game->padding; x++) {
+ game->grid[y*(game->width+game->padding*2) + x] = (unsigned char) rand() & 1;
+ }
+ }
+}
diff --git a/mpi/src/main.c b/mpi/src/main.c
new file mode 100644
index 0000000..9fed89e
--- /dev/null
+++ b/mpi/src/main.c
@@ -0,0 +1,220 @@
+#include <stdlib.h>
+#include <time.h>
+#include <stdio.h>
+#include <string.h>
+#include <mpi.h>
+
+#include "file.h"
+#include "game.h"
+#include "create_grid.h"
+
+/*
+ Rules for life:
+ Any live cell with fewer than two live neighbors dies (underpopulation).
+ Any live cell with two or three live neighbors continues to live.
+ Any live cell with more than three live neighbors dies (overpopulation).
+ Any dead cell with exactly three live neighbors becomes a live cell (reproduction).
+ */
+#define PADDING 16
+//#define VERBOSE 1
+#define SEED 100
+
+struct Args {
+ int process_count;
+ int iterations;
+ int log_each_step;
+ int width;
+ int height;
+ int padding;
+ int rows_per_proc;
+ int data_per_proc;
+};
+
+void broadcast_and_receive_input(MPI_Comm comm, struct Args* args) {
+ int blocks[8] = {1,1,1,1,1,1,1,1};
+ MPI_Aint displacements[8];
+ MPI_Datatype types[8] = {MPI_INT, MPI_INT, MPI_INT, MPI_INT, MPI_INT, MPI_INT, MPI_INT, MPI_INT};
+ MPI_Datatype arg_t;
+
+ displacements[0] = offsetof(struct Args, process_count);
+ displacements[1] = offsetof(struct Args, iterations);
+ displacements[2] = offsetof(struct Args, log_each_step);
+ displacements[3] = offsetof(struct Args, width);
+ displacements[4] = offsetof(struct Args, height);
+ displacements[5] = offsetof(struct Args, padding);
+ displacements[6] = offsetof(struct Args, rows_per_proc);
+ displacements[7] = offsetof(struct Args, data_per_proc);
+
+ MPI_Type_create_struct(8, blocks, displacements, types, &arg_t);
+ MPI_Type_commit(&arg_t);
+ MPI_Bcast(args, 1, arg_t, 0, comm);
+}
+
+void scatter_data(MPI_Comm comm, struct Args* args, unsigned char* local_data, int rank, int* data_counts, int* displacements, char* filename) {
+ unsigned char* data;
+
+ int grid_size = (args->height + args->padding*2)*(args->width + args->padding*2);
+ if (rank == 0) {
+ struct GAME game;
+ game.width = args->width;
+ game.height = args->height;
+ game.padding = args->padding;
+ int size = sizeof(unsigned char)*grid_size;
+ data = malloc(size);
+ memset(data, 0, size);
+ game.grid = data;
+ if (strcmp(filename, "random") == 0) {
+ randomize(&game);
+ } else {
+ read_in(filename, &game);
+ }
+ }
+ MPI_Scatterv(data, data_counts, displacements, MPI_UNSIGNED_CHAR, local_data, data_counts[rank], MPI_UNSIGNED_CHAR, 0, comm);
+
+ if (rank == 0) {
+ free(data);
+ }
+}
+
+
+void simulate(int argc, char** argv) {
+ srand(SEED);
+ double totalStart = MPI_Wtime();
+ struct Args args;
+ args.padding = PADDING;
+
+ int rank, process_count;
+ MPI_Comm comm;
+ MPI_Init(&argc, &argv);
+ comm = MPI_COMM_WORLD;
+ MPI_Comm_rank(comm, &rank);
+ MPI_Comm_size(comm, &args.process_count);
+
+ char* filename;
+ if (rank == 0) {
+ if (argc == 7) {
+ filename = argv[2];
+ args.width = atoi(argv[3]);
+ args.height = atoi(argv[4]);
+ args.iterations = atoi(argv[5]);
+ args.log_each_step = atoi(argv[6]);
+ } else {
+ printf("Usage: ./gol simulate <filename | random> <width> <height> <iterations> <log-each-step?1:0> <block-size>\n");
+ filename = "random";
+ args.height = 5;
+ args.width = 5;
+ args.iterations = 5;
+ args.log_each_step = 0;
+ }
+
+ args.rows_per_proc = (args.height + args.padding*2)/args.process_count;
+ args.data_per_proc = args.rows_per_proc * (args.width + args.padding*2);
+ }
+
+ broadcast_and_receive_input(comm, &args);
+
+ int grid_size = ((args.width + args.padding*2)*(args.height + args.padding*2));
+ int* data_counts = malloc(sizeof(int) * args.process_count);
+ int* displacements = malloc(sizeof(int) * args.process_count);
+ for (int i = 0; i < args.process_count; i++) {
+ data_counts[i] = args.data_per_proc;
+ displacements[i] = args.data_per_proc*sizeof(unsigned char)*i;
+ }
+ data_counts[args.process_count-1] += grid_size % (args.data_per_proc * args.process_count);
+ unsigned char* local_data = malloc(data_counts[rank]*sizeof(unsigned char));
+ memset(local_data, 0, sizeof(unsigned char) * data_counts[rank]);
+ scatter_data(comm, &args, local_data, rank, data_counts, displacements, filename);
+
+ // Allocate space for current grid (1 byte per tile)
+ char iteration_file[1024];
+
+ double timeComputingLife = 0;
+ float localTime = 0;
+
+ struct GAME local_game;
+ local_game.grid = local_data;
+ local_game.width = args.width;
+ local_game.height = data_counts[rank] / (args.width + args.padding*2);
+ local_game.padding = args.padding;
+ unsigned char* halo_above = NULL;
+ unsigned char* halo_below = NULL;
+ if (rank > 0) {
+ halo_above = (unsigned char*)malloc(sizeof(unsigned char) * (args.width + args.padding*2));
+ memset(halo_above, 0, sizeof(unsigned char) * (args.width + args.padding*2));
+ }
+ if (rank < args.process_count-1) {
+ halo_below = (unsigned char*)malloc(sizeof(unsigned char) * (args.width + args.padding*2));
+ memset(halo_below, 0, sizeof(unsigned char) * (args.width + args.padding*2));
+ }
+
+ unsigned char* global_data;
+
+ for (int i = 0; i <= args.iterations; i++) {
+ if (i > 0) {
+ int total_width = args.width + args.padding*2;
+ if (rank < args.process_count - 1) {
+ MPI_Send(&local_game.grid[(local_game.height-1) * total_width], total_width, MPI_UNSIGNED_CHAR, rank+1, 1, comm);
+ }
+ if (rank > 0) {
+ MPI_Recv(halo_above, total_width, MPI_UNSIGNED_CHAR, rank-1, 1, comm, NULL);
+ MPI_Send(&local_game.grid[0], total_width, MPI_UNSIGNED_CHAR, rank-1, 0, comm);
+ }
+ if (rank < args.process_count - 1) {
+ MPI_Recv(halo_below, total_width, MPI_UNSIGNED_CHAR, rank+1, 0, comm, NULL);
+ }
+ MPI_Barrier(comm);
+ next(&local_game, halo_above, halo_below);
+ }
+ if (args.log_each_step) {
+ if (rank == 0) {
+ global_data = malloc(sizeof(unsigned char) * grid_size);
+ memset(global_data, 0, sizeof(unsigned char) * grid_size);
+ }
+ MPI_Gatherv(local_game.grid, data_counts[rank], MPI_UNSIGNED_CHAR, global_data, data_counts, displacements, MPI_UNSIGNED_CHAR, 0, comm);
+ if (rank == 0) {
+ #ifdef VERBOSE
+ printf("\n===Iteration %i===\n", i);
+ for (int y = args.padding; y < args.height+args.padding; y++) {
+ for (int x = args.padding; x < args.width+args.padding; x++) {
+ printf("%s ", global_data[y*(args.width+2*args.padding) + x] ? "X" : " ");
+ }
+ printf("\n");
+ }
+ printf("===End iteration %i===\n", i);
+ #endif
+
+ struct GAME global_game;
+ global_game.grid = global_data;
+ global_game.width = args.width;
+ global_game.height = args.height;
+ global_game.padding = args.padding;
+ sprintf(iteration_file, "output/iteration-%07d.bin", i);
+ write_out(iteration_file, &global_game);
+ }
+ }
+ }
+
+ double totalEnd = MPI_Wtime();
+ MPI_Finalize();
+ if (rank == 0) {
+ printf("\n===Timing===\nTime computing life: %f\nClock time: %f\n", timeComputingLife, (totalEnd - totalStart));
+ }
+
+}
+
+int main(int argc, char** argv) {
+ if (argc >= 2) {
+ if (strcmp(argv[1], "simulate") == 0) {
+ simulate(argc, argv);
+ } else if (strcmp(argv[1], "create-grid") == 0) {
+ create_grid(argc, argv);
+ } else {
+ printf("Unknown input: %s\n", argv[1]);
+ exit(1);
+ }
+ } else {
+ printf("Usage: ./gol <simulate | create-grid>\n");
+ exit(1);
+ }
+ return 0;
+}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-20 22:47:21 +0000