pfqkmatrix.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> > 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];
}

struct transBody {
	Buffer &buffer;
	Buffer &dst;
	transBody(Buffer &buffer_, Buffer &dst_):buffer(buffer_),dst(dst_){}
	void operator( )( const blocked_range<size_t>& range ) const {
		MatNode *ptr;
		for(int i=range.begin(); i!=range.end( ); ++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;
		}
	}
};
void Matrix::transpose()
{
printf("begin transpose\n");
tick_count t0 = tick_count::now( );

	Buffer *dst=new Buffer(buffer->size());

	parallel_for(	blocked_range<size_t>(0,buffer->size()),
			transBody(*buffer,*dst),
			auto_partitioner()
			);

	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(){
        task_scheduler_init init(9);
	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();
}