I'm working on a mini project where I'm implementing the Matrix Chain Multiplication.My implementation is building a tree where the nodes are defined as
struct Node
{
char* seq;
Node* left;
Node* right;
};
where seq is a sequence of numbers to indicate the chain of matrices to compute. Another part is having a struct called matrix defined as
struct matrix
{
std::tuple<int, int> dimension;
std::vector<std::vector<int>> values;
};
where I use a 2D vector to store values.
The overall idea is I'll create a dictionary where its {"char" : matrix} where the char is a numerical value and store this dictionary into a class.
The following code snippet shows me creating the matrices
matrix *A1 = new matrix;
matrix *A2 = new matrix;
A1->dimension = std::make_tuple(4,10);
A2->dimension = std::make_tuple(10,3);
setValues(A1, 1);
setValues(A2, 2);
Node *n = new Node;
n->left = nullptr;
n->right = nullptr;
n->seq = static_cast<char*>(malloc(3 * sizeof(char)));
n->seq[0] = '0' + 1;
n->seq[1] = '0' + 2;
n->seq[2] = '\0';
where setValue is defined as
void setValues(matrix *x,int value)
{
int row = std::get<0>(x->dimension);
int col = std::get<1>(x->dimension);
x->values.resize(row);
for (int i = 0; i < row; ++i)
{
x->values[i].resize(col);
}
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
x->values[i][j] = value;
}
}
}
I then create an unordered map of <char, matrix*>
std::unordered_map<char, matrix*> dict;
dict['1'] = A1;
dict['2'] = A2;
After this I call my constructor function for the class Sequence which is defined as
class Sequence
{
private:
Node root;
std::vector<std::vector<int>> s_table;
std::unordered_map<char,matrix*> str_matrix_dict;
public:
Sequence(std::vector<std::vector<int>> temp_table, std::unordered_map<char,matrix*> &str_matrix_dict);
matrix* compute(Node* n);
}
where the constructor is defined as
Sequence::Sequence(
std::vector<std::vector<int>> temp_table,
std::unordered_map<char,matrix*> &temp_dict) : s_table(temp_table), str_matrix_dict(temp_dict)
{
and call the constructor like
Sequence seq(s_table, dict);
where s_table is a 2d vector. Where my issue is inside of one of the class function called compute(Node* n) and defined as followed
matrix* Sequence::compute(Node* n)
{
/*
code before
*/
if(n->left == nullptr && n->right == nullptr && n->seq[2] == '\0')
{
matrix* matrix_A = str_matrix_dict[n->seq[0]];
matrix* matrix_B = str_matrix_dict[n->seq[1]];
matrix* matrix_C = new matrix;
int m = std::get<0>(matrix_A->dimension);
int n = std::get<1>(matrix_B->dimension);
int z = std::get<1>(matrix_A->dimension);
matrix_C->dimension = std::make_tuple(m,n);
matrix_C->values.resize(m);
for (int i = 0; i < m; ++i)
{
matrix_C->values[i].resize(n);
}
matrix_mult(matrix_A,matrix_B,matrix_C,m,n,x);
return matrix_C;
}
matrix* left_res = compute(n->left);
matrix* right_res = compute(n->right);
//code after (same computation as above)
The idea is recursively go through the binary tree and computing each side of a node matrice and returning it to the parent node to compute.
I get a seg fault in matrix_mult which is defined as
void Sequence::matrix_mult(matrix *a, matrix *b, matrix *c, int x, int y, int z)
{
std::cout << "calculating " << std::endl;
for(int row = 0; row < x; x++)
{
for(int col = 0; row < y; y++)
{
for(int k = 0; k < z; k++)
{
c->values[row][col] += (a->values[row][k] * b->values[k][col]);
}
}
}
}
I seg fault on the 1st pass of the triple for loop. Inside of 'compute' when I try to print out values of the matrices I get no values. I'm guessing it has to do with how I'm passing by reference and dereferencing but not exactly sure. Reason I'm using pointers is I heard it's good practice to pass matrices by reference as it saves space and time rather than passing by value especially when working with very large matrices. I thought it would be straight forward on storing the matrices in a dictionary then store the dictionary in the class private variable to access within the function compute(which is a class function). Thank you for any advice/guidance.
This is also my compiler. I'm using nvcc as a part of this mini project is to incorporate gpu computation.
CXX = nvcc
CPP = gcc
CFLAGS = -std=c++11 -g
LDFLAGS = -lcudart -lcudadevrt
main: main.o sequence.o
$(CXX) $(CFLAGS) -o main main.o sequence.o $(LDFLAGS)
main.o: main.cu
$(CXX) $(CFLAGS) -c main.cu
sequence.o: sequence.cpp
$(CXX) $(CFLAGS) -c sequence.cpp
clean:
rm -f main main.o sequence.o
The way you provided the code makes it diffcult to pinpoint the issue, but the matrix_mult function clearly has some potential issues:
void Sequence::matrix_mult(matrix *a, matrix *b, matrix *c, int x, int y, int z)
{
std::cout << "calculating " << std::endl;
for(int row = 0; row < x; x++)
{
for(int col = 0; row < y; y++)
{
for(int k = 0; k < z; k++)
{
c->values[row][col] += (a->values[row][k] * b->values[k][col]);
}
}
}
In the first loop, you are checking that row is less than x, then you are incrementing x instead of row. This will causes an infinite loop if the initial value of x is >= 0
The same issue applies to the second loop, the one iterating over y.
Finally, and this is just an observation, there is only one possible cause of segfault in that function, and that is an access to a matrix index that is out of bound. Since row and col are always 0, I would guess that at some point you are accessing a->values[0][k] or b->values[k][0] with a k that is out of range.
You can get detailed information on the cause of your segfault if you compile your code using gcc, and the flags -fsanitize=address -g3. You can find more informations here
https://www.cse.unsw.edu.au/%7Elearn/debugging/modules/asan/