qsmatrix.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"
#include "tbb/parallel_sort.h"
#include "tbb/task_scheduler_init.h"
#include <math.h>
using namespace tbb;
using namespace std;

struct MatNode {
	size_t row;
	size_t col;
	size_t data;
	MatNode(int row_,int col_,int data_):
				row(row_),col(col_),
				data(data_){}
	MatNode(){}
	bool operator<(const MatNode &r)const{
		return (row<r.row ||(row==r.row&&col<r.col))?true:false;
	}
};

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 i,j,d;
	fscanf(fp,"%d %d %d",&i,&j,&d);
	while(i||j||d!=-1){
		buffer->push_back(MatNode(j,i,d));
		fscanf(fp,"%d %d %d",&i,&j,&d);
	}
	
	fclose(fp);
	
}
void Matrix::transpose()
{	int tmp=ROWMAX;
	ROWMAX=COLMAX;
	COLMAX=tmp;
printf("begin transpose\n");

tick_count t0 = tick_count::now( );

	parallel_sort(buffer->begin(),buffer->end());

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;
	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();
}