#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int argc, char* argv[]) {
int N
= atoi(argv
[1]); // Matrix size from command line int rank, size;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
double *A, *B, *C_seq, *C_par;
if (rank == 0) {
A
= (double*)malloc(N
* N
* sizeof(double)); B
= (double*)malloc(N
* N
* sizeof(double)); C_seq
= (double*)malloc(N
* N
* sizeof(double)); C_par
= (double*)malloc(N
* N
* sizeof(double));
// Initialize matrices A and B with values for testing
for (int i = 0; i < N * N; i++) {
A[i] = 1.0;
B[i] = 1.0;
}
// Sequential matrix multiplication
clock_t start_seq
= clock(); for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
C_seq[i * N + j] = 0;
for (int k = 0; k < N; k++) {
C_seq[i * N + j] += A[i * N + k] * B[k * N + j];
}
}
}
clock_t end_seq
= clock(); double time_seq = (double)(end_seq - start_seq) / CLOCKS_PER_SEC;
printf("Sequential time for %d x %d matrix: %f seconds\n", N
, N
, time_seq
); }
// Parallel matrix multiplication
int rowsPerProcess = N / size;
double *localA
= (double*)malloc(rowsPerProcess
* N
* sizeof(double)); double *localC
= (double*)malloc(rowsPerProcess
* N
* sizeof(double));
MPI_Scatter(A, rowsPerProcess * N, MPI_DOUBLE, localA, rowsPerProcess * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(B, N * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
double start_par = MPI_Wtime();
for (int i = 0; i < rowsPerProcess; i++) {
for (int j = 0; j < N; j++) {
localC[i * N + j] = 0;
for (int k = 0; k < N; k++) {
localC[i * N + j] += localA[i * N + k] * B[k * N + j];
}
}
}
double end_par = MPI_Wtime();
double localTime = end_par - start_par;
double maxTime;
MPI_Reduce(&localTime, &maxTime, 1, MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD);
MPI_Gather(localC, rowsPerProcess * N, MPI_DOUBLE, C_par, rowsPerProcess * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
if (rank == 0) {
printf("Parallel time for %d x %d matrix with %d processors: %f seconds\n", N
, N
, size
, maxTime
);
// Calculate speedup and efficiency
double speedup = time_seq / maxTime;
double efficiency = speedup / size;
printf("Speedup: %f\n", speedup
); printf("Efficiency: %f\n", efficiency
);
// Cleanup
}
MPI_Finalize();
return 0;
}
I2luY2x1ZGUgPG1waS5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8dGltZS5oPgoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqIGFyZ3ZbXSkgewogICAgaW50IE4gPSBhdG9pKGFyZ3ZbMV0pOyAgLy8gTWF0cml4IHNpemUgZnJvbSBjb21tYW5kIGxpbmUKICAgIGludCByYW5rLCBzaXplOwogICAgTVBJX0luaXQoJmFyZ2MsICZhcmd2KTsKICAgIE1QSV9Db21tX3JhbmsoTVBJX0NPTU1fV09STEQsICZyYW5rKTsKICAgIE1QSV9Db21tX3NpemUoTVBJX0NPTU1fV09STEQsICZzaXplKTsKCiAgICBkb3VibGUgKkEsICpCLCAqQ19zZXEsICpDX3BhcjsKICAgIGlmIChyYW5rID09IDApIHsKICAgICAgICBBID0gKGRvdWJsZSopbWFsbG9jKE4gKiBOICogc2l6ZW9mKGRvdWJsZSkpOwogICAgICAgIEIgPSAoZG91YmxlKiltYWxsb2MoTiAqIE4gKiBzaXplb2YoZG91YmxlKSk7CiAgICAgICAgQ19zZXEgPSAoZG91YmxlKiltYWxsb2MoTiAqIE4gKiBzaXplb2YoZG91YmxlKSk7CiAgICAgICAgQ19wYXIgPSAoZG91YmxlKiltYWxsb2MoTiAqIE4gKiBzaXplb2YoZG91YmxlKSk7CgogICAgICAgIC8vIEluaXRpYWxpemUgbWF0cmljZXMgQSBhbmQgQiB3aXRoIHZhbHVlcyBmb3IgdGVzdGluZwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTiAqIE47IGkrKykgewogICAgICAgICAgICBBW2ldID0gMS4wOwogICAgICAgICAgICBCW2ldID0gMS4wOwogICAgICAgIH0KCiAgICAgICAgLy8gU2VxdWVudGlhbCBtYXRyaXggbXVsdGlwbGljYXRpb24KICAgICAgICBjbG9ja190IHN0YXJ0X3NlcSA9IGNsb2NrKCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBOOyBqKyspIHsKICAgICAgICAgICAgICAgIENfc2VxW2kgKiBOICsgal0gPSAwOwogICAgICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCBOOyBrKyspIHsKICAgICAgICAgICAgICAgICAgICBDX3NlcVtpICogTiArIGpdICs9IEFbaSAqIE4gKyBrXSAqIEJbayAqIE4gKyBqXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjbG9ja190IGVuZF9zZXEgPSBjbG9jaygpOwogICAgICAgIGRvdWJsZSB0aW1lX3NlcSA9IChkb3VibGUpKGVuZF9zZXEgLSBzdGFydF9zZXEpIC8gQ0xPQ0tTX1BFUl9TRUM7CiAgICAgICAgcHJpbnRmKCJTZXF1ZW50aWFsIHRpbWUgZm9yICVkIHggJWQgbWF0cml4OiAlZiBzZWNvbmRzXG4iLCBOLCBOLCB0aW1lX3NlcSk7CiAgICB9CgogICAgLy8gUGFyYWxsZWwgbWF0cml4IG11bHRpcGxpY2F0aW9uCiAgICBpbnQgcm93c1BlclByb2Nlc3MgPSBOIC8gc2l6ZTsKICAgIGRvdWJsZSAqbG9jYWxBID0gKGRvdWJsZSopbWFsbG9jKHJvd3NQZXJQcm9jZXNzICogTiAqIHNpemVvZihkb3VibGUpKTsKICAgIGRvdWJsZSAqbG9jYWxDID0gKGRvdWJsZSopbWFsbG9jKHJvd3NQZXJQcm9jZXNzICogTiAqIHNpemVvZihkb3VibGUpKTsKCiAgICBNUElfU2NhdHRlcihBLCByb3dzUGVyUHJvY2VzcyAqIE4sIE1QSV9ET1VCTEUsIGxvY2FsQSwgcm93c1BlclByb2Nlc3MgKiBOLCBNUElfRE9VQkxFLCAwLCBNUElfQ09NTV9XT1JMRCk7CiAgICBNUElfQmNhc3QoQiwgTiAqIE4sIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKCiAgICBkb3VibGUgc3RhcnRfcGFyID0gTVBJX1d0aW1lKCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHJvd3NQZXJQcm9jZXNzOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IE47IGorKykgewogICAgICAgICAgICBsb2NhbENbaSAqIE4gKyBqXSA9IDA7CiAgICAgICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgTjsgaysrKSB7CiAgICAgICAgICAgICAgICBsb2NhbENbaSAqIE4gKyBqXSArPSBsb2NhbEFbaSAqIE4gKyBrXSAqIEJbayAqIE4gKyBqXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGRvdWJsZSBlbmRfcGFyID0gTVBJX1d0aW1lKCk7CiAgICBkb3VibGUgbG9jYWxUaW1lID0gZW5kX3BhciAtIHN0YXJ0X3BhcjsKCiAgICBkb3VibGUgbWF4VGltZTsKICAgIE1QSV9SZWR1Y2UoJmxvY2FsVGltZSwgJm1heFRpbWUsIDEsIE1QSV9ET1VCTEUsIE1QSV9NQVgsIDAsIE1QSV9DT01NX1dPUkxEKTsKCiAgICBNUElfR2F0aGVyKGxvY2FsQywgcm93c1BlclByb2Nlc3MgKiBOLCBNUElfRE9VQkxFLCBDX3Bhciwgcm93c1BlclByb2Nlc3MgKiBOLCBNUElfRE9VQkxFLCAwLCBNUElfQ09NTV9XT1JMRCk7CgogICAgaWYgKHJhbmsgPT0gMCkgewogICAgICAgIHByaW50ZigiUGFyYWxsZWwgdGltZSBmb3IgJWQgeCAlZCBtYXRyaXggd2l0aCAlZCBwcm9jZXNzb3JzOiAlZiBzZWNvbmRzXG4iLCBOLCBOLCBzaXplLCBtYXhUaW1lKTsKCiAgICAgICAgLy8gQ2FsY3VsYXRlIHNwZWVkdXAgYW5kIGVmZmljaWVuY3kKICAgICAgICBkb3VibGUgc3BlZWR1cCA9IHRpbWVfc2VxIC8gbWF4VGltZTsKICAgICAgICBkb3VibGUgZWZmaWNpZW5jeSA9IHNwZWVkdXAgLyBzaXplOwogICAgICAgIHByaW50ZigiU3BlZWR1cDogJWZcbiIsIHNwZWVkdXApOwogICAgICAgIHByaW50ZigiRWZmaWNpZW5jeTogJWZcbiIsIGVmZmljaWVuY3kpOwoKICAgICAgICAvLyBDbGVhbnVwCiAgICAgICAgZnJlZShBKTsKICAgICAgICBmcmVlKEIpOwogICAgICAgIGZyZWUoQ19zZXEpOwogICAgICAgIGZyZWUoQ19wYXIpOwogICAgfQoKICAgIGZyZWUobG9jYWxBKTsKICAgIGZyZWUobG9jYWxDKTsKICAgIE1QSV9GaW5hbGl6ZSgpOwogICAgcmV0dXJuIDA7Cn0K