You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
228 lines
7.2 KiB
228 lines
7.2 KiB
#include <iostream>
|
|
#include <cstdlib>
|
|
#include <random>
|
|
#include <vector>
|
|
#include <boost/thread.hpp>
|
|
#include <boost/bind.hpp>
|
|
#include <boost/chrono.hpp>
|
|
|
|
using namespace std;
|
|
namespace chrono = boost::chrono;
|
|
|
|
// Matrix structure to hold data and dimensions
|
|
struct Matrix {
|
|
int n;
|
|
double** data;
|
|
|
|
Matrix(int size) : n(size) {
|
|
data = new double*[n];
|
|
for (int i = 0; i < n; ++i) {
|
|
data[i] = new double[n](); // Initialize to zero
|
|
}
|
|
}
|
|
|
|
~Matrix() {
|
|
for (int i = 0; i < n; ++i) {
|
|
delete[] data[i];
|
|
}
|
|
delete[] data;
|
|
}
|
|
};
|
|
|
|
// Initialize matrix with random values
|
|
void init_matrix(Matrix& mat, bool zero = false) {
|
|
random_device rd;
|
|
mt19937 gen(rd());
|
|
uniform_real_distribution<double> dis(0.0, 1.0);
|
|
|
|
for (int i = 0; i < mat.n; ++i) {
|
|
for (int j = 0; j < mat.n; ++j) {
|
|
mat.data[i][j] = zero ? 0.0 : dis(gen);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Print matrix (for debugging)
|
|
void print_matrix(const Matrix& mat, const string& name) {
|
|
cout << name << ":\n";
|
|
for (int i = 0; i < mat.n; ++i) {
|
|
for (int j = 0; j < mat.n; ++j) {
|
|
cout << mat.data[i][j] << " ";
|
|
}
|
|
cout << endl;
|
|
}
|
|
cout << endl;
|
|
}
|
|
|
|
// Worker thread for Cannon's algorithm
|
|
class CannonWorker {
|
|
int block_size;
|
|
int grid_size;
|
|
int row, col;
|
|
Matrix& a;
|
|
Matrix& b;
|
|
Matrix& c;
|
|
boost::barrier& sync_barrier;
|
|
vector<boost::barrier*>& row_barriers;
|
|
vector<boost::barrier*>& col_barriers;
|
|
|
|
public:
|
|
CannonWorker(int bs, int gs, int r, int c, Matrix& ma, Matrix& mb, Matrix& mc,
|
|
boost::barrier& sb, vector<boost::barrier*>& rb, vector<boost::barrier*>& cb)
|
|
: block_size(bs), grid_size(gs), row(r), col(c),
|
|
a(ma), b(mb), c(mc), sync_barrier(sb), row_barriers(rb), col_barriers(cb) {}
|
|
|
|
void operator()() {
|
|
// Calculate block boundaries
|
|
int row_start = row * block_size;
|
|
int row_end = row_start + block_size;
|
|
int col_start = col * block_size;
|
|
int col_end = col_start + block_size;
|
|
|
|
// Initial skewing: A left by row, B up by column
|
|
// Shift A left by row positions
|
|
for (int shift = 0; shift < row; ++shift) {
|
|
for (int i = 0; i < block_size; ++i) {
|
|
double temp = a.data[row_start + i][col_start];
|
|
for (int j = 0; j < block_size - 1; ++j) {
|
|
a.data[row_start + i][col_start + j] = a.data[row_start + i][col_start + j + 1];
|
|
}
|
|
a.data[row_start + i][col_start + block_size - 1] = temp;
|
|
}
|
|
}
|
|
|
|
// Shift B up by column positions
|
|
for (int shift = 0; shift < col; ++shift) {
|
|
for (int j = 0; j < block_size; ++j) {
|
|
double temp = b.data[row_start][col_start + j];
|
|
for (int i = 0; i < block_size - 1; ++i) {
|
|
b.data[row_start + i][col_start + j] = b.data[row_start + i + 1][col_start + j];
|
|
}
|
|
b.data[row_start + block_size - 1][col_start + j] = temp;
|
|
}
|
|
}
|
|
|
|
// Synchronize all threads after initial skewing
|
|
sync_barrier.wait();
|
|
|
|
// Main computation loop
|
|
for (int step = 0; step < grid_size; ++step) {
|
|
// Local matrix multiplication
|
|
for (int i = 0; i < block_size; ++i) {
|
|
for (int j = 0; j < block_size; ++j) {
|
|
for (int k = 0; k < block_size; ++k) {
|
|
c.data[row_start + i][col_start + j] +=
|
|
a.data[row_start + i][(col_start + k) % a.n] *
|
|
b.data[(row_start + k) % b.n][col_start + j];
|
|
}
|
|
}
|
|
}
|
|
|
|
// Shift A left by 1
|
|
for (int i = 0; i < block_size; ++i) {
|
|
double temp = a.data[row_start + i][col_start];
|
|
for (int j = 0; j < block_size - 1; ++j) {
|
|
a.data[row_start + i][col_start + j] = a.data[row_start + i][col_start + j + 1];
|
|
}
|
|
a.data[row_start + i][col_start + block_size - 1] = temp;
|
|
}
|
|
|
|
// Shift B up by 1
|
|
for (int j = 0; j < block_size; ++j) {
|
|
double temp = b.data[row_start][col_start + j];
|
|
for (int i = 0; i < block_size - 1; ++i) {
|
|
b.data[row_start + i][col_start + j] = b.data[row_start + i + 1][col_start + j];
|
|
}
|
|
b.data[row_start + block_size - 1][col_start + j] = temp;
|
|
}
|
|
|
|
// Synchronize all threads before next step
|
|
sync_barrier.wait();
|
|
}
|
|
}
|
|
};
|
|
|
|
// Cannon's algorithm using Boost Threads
|
|
void cannon_multiply(Matrix& a, Matrix& b, Matrix& c, int grid_size) {
|
|
int block_size = a.n / grid_size;
|
|
|
|
// Create synchronization barriers
|
|
boost::barrier sync_barrier(grid_size * grid_size);
|
|
vector<boost::barrier*> row_barriers(grid_size);
|
|
vector<boost::barrier*> col_barriers(grid_size);
|
|
for (int i = 0; i < grid_size; ++i) {
|
|
row_barriers[i] = new boost::barrier(grid_size);
|
|
col_barriers[i] = new boost::barrier(grid_size);
|
|
}
|
|
|
|
// Create worker threads
|
|
boost::thread_group workers;
|
|
for (int i = 0; i < grid_size; ++i) {
|
|
for (int j = 0; j < grid_size; ++j) {
|
|
workers.create_thread(CannonWorker(block_size, grid_size, i, j,
|
|
a, b, c, sync_barrier, row_barriers, col_barriers));
|
|
}
|
|
}
|
|
|
|
// Wait for all threads to complete
|
|
workers.join_all();
|
|
|
|
// Clean up barriers
|
|
for (int i = 0; i < grid_size; ++i) {
|
|
delete row_barriers[i];
|
|
delete col_barriers[i];
|
|
}
|
|
}
|
|
|
|
int main(int argc, char** argv) {
|
|
if (argc != 3) {
|
|
cerr << "Usage: " << argv[0] << " <matrix_size> <grid_size>" << endl;
|
|
return 1;
|
|
}
|
|
|
|
int n = atoi(argv[1]);
|
|
int grid_size = atoi(argv[2]);
|
|
if (n <= 0 || grid_size <= 0) {
|
|
cerr << "Matrix size and grid size must be positive" << endl;
|
|
return 1;
|
|
}
|
|
if (n % grid_size != 0) {
|
|
cerr << "Matrix size must be divisible by grid size" << endl;
|
|
return 1;
|
|
}
|
|
|
|
chrono::system_clock::time_point setup_start, setup_end;
|
|
chrono::system_clock::time_point comp_start, comp_end;
|
|
|
|
setup_start = chrono::system_clock::now();
|
|
|
|
Matrix a(n), b(n), c(n);
|
|
init_matrix(a);
|
|
init_matrix(b);
|
|
init_matrix(c, true); // Initialize to zero
|
|
|
|
setup_end = chrono::system_clock::now();
|
|
|
|
if (n <= 8) {
|
|
print_matrix(a, "Matrix A");
|
|
print_matrix(b, "Matrix B");
|
|
}
|
|
|
|
comp_start = chrono::system_clock::now();
|
|
|
|
cannon_multiply(a, b, c, grid_size);
|
|
|
|
comp_end = chrono::system_clock::now();
|
|
|
|
if (n <= 8) {
|
|
print_matrix(c, "Result Matrix C");
|
|
}
|
|
|
|
auto setup_time = chrono::duration_cast<chrono::milliseconds>(setup_end - setup_start);
|
|
auto comp_time = chrono::duration_cast<chrono::milliseconds>(comp_end - comp_start);
|
|
|
|
cout << "n,grid_size,setup(ms),exec(ms)" << endl;
|
|
cout << n << "," << grid_size << "," << setup_time.count() << "," << comp_time.count() << endl;
|
|
|
|
return 0;
|
|
}
|