pompqkmatrix.cpp

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

#include <vector>
#include <cstdio>
#include <cassert>
#include "tbb/tick_count.h"
#include "tbb/scalable_allocator.h"
#include "tbb/parallel_for.h"
#include "tbb/cache_aligned_allocator.h"
#include "tbb/blocked_range.h"
#include "tbb/task_scheduler_init.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*> > PtrBuffer;
typedef vector< MatNode, cache_aligned_allocator<MatNode> > Buffer;
class Matrix{
private:
	Buffer buffer;
	PtrBuffer *ptrbuffer;
	int ROWMAX;
	int COLMAX;
public:
	Matrix(){
		ptrbuffer=new PtrBuffer();
		assert(ptrbuffer);
	}
	~Matrix(){
		assert(ptrbuffer);
		delete ptrbuffer;
	}
	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++){
		ptrbuffer->push_back(&(buffer[i]));
		(*ptrbuffer)[i]->idx=col_pos[(*ptrbuffer)[i]->col]+(*ptrbuffer)[i]->idx;
	}
	assert(buffer.size()==ptrbuffer->size());
	printf("load ok\n");
}
/*
struct transBody {
	PtrBuffer &ptrbuffer;
	PtrBuffer &ptrdst;
	transBody(PtrBuffer &ptrbuffer_, PtrBuffer &ptrdst_):ptrbuffer(ptrbuffer_),ptrdst(ptrdst_){}
	void operator( )( const blocked_range<size_t>& range ) const {
		MatNode *ptr;
		int tmp;
		for(int i=range.begin(); i!=range.end( ); ++i){
			ptr=ptrbuffer[i];
			tmp=ptr->row;
			ptr->row=ptr->col;
			ptr->col=tmp;
			ptrdst[ptr->idx]=ptr;
			ptr->idx=i;
		}
	}
};
*/
void Matrix::transpose()
{
printf("begin transpose\n");
tick_count t0 = tick_count::now( );

	PtrBuffer *ptrdst=new PtrBuffer(ptrbuffer->size());

/*	parallel_for(	blocked_range<size_t>(0,ptrbuffer->size()),
			transBody(*ptrbuffer,*ptrdst),
			auto_partitioner()
			);
*/
	MatNode *ptr;
	int tmp;
	int size=ptrbuffer->size();
#pragma omp parallel for
	for(int i=0; i<size; ++i){
		ptr=(*ptrbuffer)[i];
		tmp=ptr->row;
		ptr->row=ptr->col;
		ptr->col=tmp;
		(*ptrdst)[ptr->idx]=ptr;
		ptr->idx=i;
	}
	delete ptrbuffer;
	ptrbuffer = ptrdst;	
	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<ptrbuffer->size();i++)
		fprintf(fp,"%d %d %d\n",(*ptrbuffer)[i]->row,(*ptrbuffer)[i]->col,(*ptrbuffer)[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(){
	task_scheduler_init init;
	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();
}