xsudoku.h

数独并行算法 intel 多线程优化大赛参赛作品

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

#ifndef XSUDOKU_HEAD
#define XSUDOKU_HEAD

#include <mathimf.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <smmintrin.h> 
#include <string.h>
#include <omp.h>
#include <mkl_vsl.h>
#include <stdarg.h>

#include "tbb/task_scheduler_init.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"
#include "tbb/tick_count.h" 
#include "tbb/scalable_allocator.h"
#include "tbb/task.h"
#include "tbb/mutex.h"

using namespace tbb;

#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

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

#ifndef MAX_PATH
#define MAX_PATH					256
#endif


#ifndef FALSE
#define FALSE						0
#endif

#ifndef TRUE
#define TRUE						1
#endif

typedef int							BOOL;

typedef unsigned char				uint8;
typedef unsigned short				uint16;
typedef unsigned int				uint32;

typedef uint8*						PUINT8;
typedef uint32*						PUINT32;

typedef const uint8*				PCUINT8;
typedef const uint32*				PCUINT32;


// 是否支持输出解的情况
// #define XOUT_SOLUTION

// 输出是否使用英语
// #define XUSE_ENGLISH

// 输出时间
// #define XOUT_TIME

// 填值失败
#define XFILL_INVALID				0x7FFFFFFF
// 已填值标记
#define XFILLEDMASK					0x8000

// 每个小块的宽度
#define XGRID_BW					3
// 每个小块的高度
#define XGRID_BH					2
// 每个小块的大小
#define XGRID_BSIZE					(XGRID_BW * XGRID_BH)
// 整个网格的大小
#define XGRID_AREA					(XGRID_BSIZE * XGRID_BSIZE)
// 整个网格的大小 SSE对齐
#define XGRID_AREASSE				((XGRID_AREA + 7) >> 3 << 3)
// 每个单元格关联的单元格数量
#define XGRID_MUTUALITY				(XGRID_BSIZE * 3 -  XGRID_BW - XGRID_BH - 1)
// 每个单元格关联的单元格数量 SSE对齐
#define XGRID_MUTUALITYSSE			((XGRID_MUTUALITY + 7) >> 3 << 3)
// 修改关联单元格的条件
#define XGRID_CHANGE_MUTUALITY_SIZE	(XGRID_AREA * 30 / 100)
// 堆栈的最大深度
#define XGRID_STACK_SIZE			(XGRID_AREA - XGRID_CHANGE_MUTUALITY_SIZE)

#if (XGRID_BSIZE >= 9) 
	#define XGRID_MUTUALITYSSE_CLEAR
#endif

// 用于保存单元格的值
typedef int XCells[XGRID_AREASSE];

// 用于保存网格的数据结构
typedef struct tagXGrid
{
	__declspec(align(16)) XCells xCells;										// 单元格的值
#ifdef XGRID_MUTUALITYSSE_CLEAR
	__declspec(align(16)) uint8  pMutuality[XGRID_AREA][XGRID_MUTUALITYSSE];	// 单元格的关联单元格索引数组
	__declspec(align(16)) uint8  nMutuality[XGRID_AREA];						// 单元格的关联单元格数量
#endif
	__declspec(align(16)) int	 pFilledPos[XGRID_AREA];						// 已经填充的单元格位置
	int	nFilled;																// 已填充的单元格个数
	int	*pRunMode,*pTotal;														// 运行模式和填充方案的数量
}XGrid;

// 运行模式
enum enXRunMode
{
	XRUN_FIND_FLAG	= 0x10000000,
	XRUN_FIND_ONE	= 0x00000001,
	XRUN_FIND_ALL	= 0x00000002,
	XRUN_PARALLEL	= 0x00000004,
	XRUN_SERIAL		= 0x00000008,
	XRUN_OUT_STD	= 0x00000010,
	XRUN_OUT_FILE	= 0x00000020,
};

// 初始化静态加速Tab
void	XInitTab();
// 计算数独的所有填值可能情况
int		XFindGrid(int nRunMode, const char* pInput);
// 错误处理	
void	Error(char *);
// 警告处理
void	Warning(char *);

#endif