xshortestpub.h

最短路径的并行算法 采用TBB 需要intel编译器 速度很快

/*/////////////////////////////////////////
// 版权所有(C)  2000-2008 邓辉           //
// Email：      [e-mail]  //
// 说明：       Intel线程优化大赛参赛作品//
/////////////////////////////////////////*/

#ifndef XSORTPUB_HEAD
#define XSORTPUB_HEAD

// 启用SSE4指令
#define XUSE_SSE4

#include <mathimf.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <string.h>
#include <omp.h>
#include <sys/types.h>
#include <sys/stat.h>

#include "tbb/tick_count.h" 
#include "tbb/scalable_allocator.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"
#include "tbb/parallel_while.h"
#include "tbb/parallel_sort.h"

#include <list>
#include <map>
#include <deque>
#include <vector>
#include <string>

using namespace std;
using namespace tbb;

#ifdef XUSE_SSE4
	#include <smmintrin.h> 
#else
	#include <tmmintrin.h> 
#endif

#ifdef XCODE_WIN
	// 链接tbb
	#ifdef _DEBUG
		#pragma comment(lib, "tbb_debug.lib")
		#pragma comment(lib, "tbbmalloc_debug.lib")
	#else
		#pragma comment(lib, "tbb.lib")
		#pragma comment(lib, "tbbmalloc.lib")
	#endif

	#include <ipp.h>
	// 链接ipp
	#pragma comment(lib, "ipps.lib")
	#define XMEMCOPY(Macro_Dst, Macro_Src, Macro_Size)	\
		ippsCopy_8u( (const Ipp8u*)(Macro_Src), (Ipp8u*)(Macro_Dst), (Macro_Size) );
#endif

#ifdef XCODE_LINUX
	#define XMEMCOPY(Macro_Dst, Macro_Src, Macro_Size)	\
		memcpy( (Macro_Dst), (Macro_Src), (Macro_Size) );
#endif

typedef int                 			BOOL;
typedef unsigned char       			BYTE;

#ifndef FALSE
	#define FALSE						0
#endif

#ifndef TRUE
	#define TRUE						1
#endif

#ifndef MAX_PATH
	#define MAX_PATH					256
#endif

#pragma warning( disable : 1786)
#pragma warning( disable : 1684)

typedef unsigned char	uint8;
typedef unsigned int	uint32;

#define  XNODE_NAME_SIZE				10
#define  XDISTANCE_INFINITY				0x3FFFFFFF

typedef map<string, uint32> XNameToIDMap;

// 节点
template<class Type>
struct XNode
{
	Type	xKey;					// 距离值
	int		nID;					// ID
};

// 边
template<class Type>
struct XEdge
{
	Type	xKey;					// 距离值
	int		nLink;					// 另外一个点的ID
	XEdge*	pNext;					// 下一条边
};

// 图
template<class Type>
struct XGraph
{
	int				nNode;			// 点的个数
	int				nAlign;			// 数据对齐后点的个数
	int				nEdge;			// 边的个数
	XEdge<Type>*	pEdge;			// 边数据空间
	XEdge<Type>**	pHead;			// 堆数据空间
	Type**			ppDistance;		// 存放每行距离的头指针
	Type*			pDistance;		// 距离空间
	vector<string>	xIDToNameTab;	// ID到名字的映射
};

// 错误处理
void		Error(char *);
// 警告处理
void		Warning(char *);

// 程序运行模式
enum enRunMode
{
	XRUN_AUTO_PARALLEL		= 0x00000001,	// 自动分析边与点的个数,选择并行Dijkstra或并行Floyed
	XRUN_AUTO_SERIAL		= 0x00000002,	// 自动分析边与点的个数,选择串行Dijkstra或串行Floyed
	XRUN_DIJKSTRA_PARALLEL	= 0x00000004,	// 并行Dijkstra
	XRUN_DIJKSTRA_SERIAL	= 0x00000008,	// 串行Dijkstra
	XRUN_FLOYED_PARALLEL	= 0x00000010,	// 并行Floyed
	XRUN_FLOYED_SERIAL		= 0x00000020,	// 串行Floyed
	XRUN_FORPGO				= 0x00000014,	// PGO
	XRUN_CREATETESTDATA		= 0x80000000,	// 创建测试数据
};

// 创建图
template <class Type>
XGraph<Type>* XGraphCreate(int nSize)
{
	XGraph<Type>* pGraph = new XGraph<Type>;

	if(pGraph == NULL) Error("No Memory!");

	// 数据对齐,便于使用SSE指令
	pGraph->nAlign = (nSize + 15) / 16 * 16;
	
	// 分配数据空间
	pGraph->pDistance	= (Type*)_mm_malloc(pGraph->nAlign * nSize * sizeof(Type), 16);
	pGraph->ppDistance	= (Type**)scalable_malloc(nSize * sizeof(Type*));
	pGraph->pHead		= (XEdge<Type>**)scalable_malloc(nSize * sizeof(XEdge<Type>*));
	pGraph->pEdge		= (XEdge<Type>*)scalable_malloc(nSize * 2 * sizeof(XEdge<Type>));
	pGraph->xIDToNameTab.clear();
	pGraph->xIDToNameTab.reserve(nSize);

	if(pGraph->pDistance == NULL || pGraph->ppDistance == NULL || 
		pGraph->pHead == NULL || pGraph->pEdge == NULL )
	{
		Error("No Memory!");
	}

	pGraph->nNode = nSize;
	pGraph->nEdge = 0;

	// 初始化距离为最大值XDISTANCE_INFINITY
#pragma omp parallel for
	for(int i = 0; i < nSize; ++i) 
	{
		pGraph->ppDistance[i] = pGraph->pDistance + i * pGraph->nAlign;
		Type* pDistance = pGraph->ppDistance[i];
		for(int j = 0; j < pGraph->nAlign; ++j) 
		{
			pDistance[j] = XDISTANCE_INFINITY;
		}
	}

	memset(pGraph->pHead, 0, nSize * sizeof(pGraph->pHead[0]));

	pGraph->pEdge->pNext = NULL;

	return pGraph;
}

// 释放图
template <class Type>
void XGraphDestroy(XGraph<Type>** ppGraph)
{
	if(ppGraph != NULL && *ppGraph != NULL)
	{
		XGraph<Type>* pGraph = *ppGraph;
		
		// 释放数据空间
		_mm_free(pGraph->pDistance);
		scalable_free(pGraph->ppDistance);
		scalable_free(pGraph->pHead);

		while(pGraph->pEdge != NULL)
		{
			XEdge<Type>* pNext = pGraph->pEdge->pNext;
			scalable_free(pGraph->pEdge);
			pGraph->pEdge = pNext;
		}

		*ppGraph = NULL;
	}
}

// 扩充Edge缓存空间
template <class Type>
void XGraphExtEdgeMemory(XGraph<Type>* pGraph)
{
	if(pGraph != NULL)
	{
		XEdge<Type>* pTmp = pGraph->pEdge;
		pGraph->pEdge = (XEdge<uint32>*)scalable_malloc(pGraph->nNode * 2 * sizeof(XEdge<uint32>));
		pGraph->pEdge->pNext = pTmp;
	}
}

// 加载测试数据
XGraph<uint32>* XDataFileRead(const char* szFile, uint32& nMode);

// 输出计算结果
void XDataFileSave(const char* szFile, XGraph<uint32>* pGraph);

// 创建测试数据
void XCreateTestData(const char* szFile, int nNode, double dDensity);

#endif