ompqkmatrix.cpp

intel线程挑战赛 矩阵转置 快速转置 多线程 tbb 并行算法

#include <vector>
#include <cstdio>
#include <cassert>
#include "tbb/tick_count.h"
#include "tbb/scalable_allocator.h"
#include "tbb/cache_aligned_allocator.h"
using namespace tbb;
using namespace std;

struct MatNode {
	size_t row;
	size_t col;
	size_t idx;
	size_t data;
	MatNode(int row_,int col_,int data_,int idx_):
				row(row_),col(col_),
				data(data_),idx(idx_){}
	MatNode(){}
};

typedef vector< MatNode, cache_aligned_allocator<MatNode> > Buffer;

class Matrix{
private:
	Buffer *buffer;
	int ROWMAX;
	int COLMAX;
public:
	Matrix():buffer(0){
		buffer=new Buffer();
		assert(buffer);
	}
	~Matrix(){
		assert(buffer);
		delete buffer;
	}
	void transpose();
	void load(char *);
	void save();
	void display();
};

void Matrix::load(char *filename)
{
	FILE *fp=fopen(filename,"r");
	assert(fp>0);
	
	fscanf(fp,"%d %d",&ROWMAX,&COLMAX);
	int *col_num = new int[COLMAX];
	for (int i=0; i<COLMAX; i++)
		col_num[i]=0;
	
	int i,j,d;
	fscanf(fp,"%d %d %d",&i,&j,&d);
	while(i||j||d!=-1){
		buffer->push_back(MatNode(i,j,d,col_num[j]++));
		fscanf(fp,"%d %d %d",&i,&j,&d);
	}
	
	fclose(fp);
	
	int *col_pos = new int[COLMAX];
	col_pos[0]=0;
	for (int i=1; i<COLMAX; i++){
		col_pos[i]=col_pos[i-1]+col_num[i-1];
	}
	for (int i=0; i<buffer->size(); i++)
		(*buffer)[i].idx+=col_pos[(*buffer)[i].col];
}
void Matrix::transpose()
{
printf("begin transpose\n");
	Buffer *dst=new Buffer(buffer->size());
	MatNode *ptr;
	
	tick_count t0 = tick_count::now( );
	int size=buffer->size();
#pragma omp parallel for
	for(int i=0; i<size; i++){
		ptr=&(*buffer)[i];
		(*dst)[ptr->idx].row=ptr->col;
		(*dst)[ptr->idx].col=ptr->row;
		(*dst)[ptr->idx].data=ptr->data;
		(*dst)[ptr->idx].idx=i;
	}
	delete buffer;
	buffer = dst;	
	int tmp=ROWMAX;
	ROWMAX=COLMAX;
	COLMAX=tmp;

	tick_count t1 = tick_count::now( );
	printf("work took %g seconds\n",(t1-t0).seconds( ));

printf("end transpose\n");


}
void Matrix::save()
{	FILE *fp=fopen("output.txt","w");
	fprintf(fp,"%d %d\n",ROWMAX,COLMAX);
	for(int i=0; i<buffer->size();i++)
		fprintf(fp,"%d %d %d\n",(*buffer)[i].row,(*buffer)[i].col,(*buffer)[i].data);
	fprintf(fp,"%d %d %d\n",0,0,-1);
	fclose(fp);
		
}
void Matrix::display()
{
//	for(int i=0; i<buffer->size(); i++)
//		printf("%d,%d\t %d\t %d\n",(*buffer)[i].row,(*buffer)[i].col,(*buffer)[i].data,(*buffer)[i].idx);
//	for (int i=0; i<ROWMAX; i++)
//		printf("%d %d\n",i,col_pos[i]);
}
int main(){
	Matrix mat;
	mat.load("matrix.dat");
//tick_count t0 = tick_count::now( );
	for(int i=0; i<10; i++)
		mat.transpose();
//	mat.transpose();
//tick_count t1 = tick_count::now( );
//printf("work took %g seconds\n",(t1-t0).seconds( ));
	mat.save();
}