xsudokumain.cpp

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

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

#include "XSudoku.h"
#include "XFileMap.h"

void Error (char *s)
{
	fprintf(stderr, "ERROR: %s\n",s);
	exit(1);
}

void Warning (char *s)
{
	fprintf(stderr, "WARNING: %s\n",s);
}

void Usage(void)
{
	printf("Usage: XSudoku.exe <file name> [op|ap|os|as] [none|std|file]\n");
	printf("Usage: op = Find One Use Parallel Mode\n");
	printf("Usage: os = Find One Use Serial Mode\n");
	printf("Usage: ap = Find All Use Parallel Mode\n");
	printf("Usage: as = Find All Use Serial Mode\n\n");
	printf("Usage: none = Output None\n");
	printf("Usage: std  = Output Print Std\n");
	printf("Usage: file = Output Print File\n");
}

// 统计输出数字占用的空间
unsigned int XGetNumSize(int nCount)
{
	unsigned int nNum  = 1000000000;
	unsigned int nChar = 10;
	unsigned int nRet = 0;

	while(nCount < nNum)
	{
		nNum /= 10;
		--nChar;
	}

	nRet += (nCount + 1 - nNum) * nChar;
	nNum /= 10;
	--nChar;

	while(nNum > 0)
	{
		nRet += (nNum * 9) * nChar;
		nNum /= 10;
		--nChar;
	}

	return nRet;
}

// 保存一个数字
#define XSAVENUM(pSave, nSave)													\
{																				\
	char  pBuffer[16];															\
	char* pBufferPtr = pBuffer;													\
	while(nSave >= 10)															\
	{																			\
		*pBufferPtr++ = (nSave % 10) + '0';										\
		nSave /= 10;															\
	}																			\
	*pBufferPtr = (nSave % 10) + '0';											\
	while(pBufferPtr >= pBuffer) { *pSave++ = *pBufferPtr--;}					\
}

// 保存一个字符串
#define XSAVESTR(pSave, pStr)													\
{																				\
	char* pTmp = pStr;															\
	while(*pTmp != '\0') *pSave++ = *pTmp++;									\
}

//主函数
int main(int argc, char* argv[])
{	
	tick_count nBeg, nEnd;
	tick_count nBegAll, nEndAll;
	tbb::task_scheduler_init init;

	char szInput[MAX_PATH] = {0};

	int  nRunMode = XRUN_FIND_ONE | XRUN_PARALLEL;

	switch(argc)
	{
	case 1:
		strcpy(szInput, "tdat.txt");
		break;
	case 2:
		strcpy(szInput, argv[1]);
		break;
	case 3:
		strcpy(szInput, argv[1]);
		if(strcmp(argv[2], "as") == 0) { nRunMode = XRUN_FIND_ALL | XRUN_SERIAL; }
		else if(strcmp(argv[2], "ap") == 0) { nRunMode = XRUN_FIND_ALL | XRUN_PARALLEL; }
		else if(strcmp(argv[2], "os") == 0) { nRunMode = XRUN_FIND_ONE | XRUN_SERIAL; }
		else { nRunMode = XRUN_FIND_ONE | XRUN_PARALLEL; }
		break;
	case 4:
		strcpy(szInput, argv[1]);
		if(strcmp(argv[2], "as") == 0) { nRunMode = XRUN_FIND_ALL | XRUN_SERIAL; }
		else if(strcmp(argv[2], "ap") == 0) { nRunMode = XRUN_FIND_ALL | XRUN_PARALLEL; }
		else if(strcmp(argv[2], "os") == 0) { nRunMode = XRUN_FIND_ONE | XRUN_SERIAL; }
		else { nRunMode = XRUN_FIND_ONE | XRUN_PARALLEL; }

		if(strcmp(argv[3], "std") == 0) { nRunMode |= XRUN_OUT_STD; }
		else if(strcmp(argv[3], "file") == 0) { nRunMode |= XRUN_OUT_FILE; }
		break;
	default:
		Usage();
		exit(0);
		break;
	}

	nRunMode |= XRUN_FIND_FLAG;

	nBeg = nBegAll = tick_count::now();

	XInitTab();

	// 用文件映射打开输入文件
	unsigned int nFileSize  = 0;

	XFILEMAPHANDLE hFileMap = XFileMapOpen(szInput, XFILEMAP_READONLY, nFileSize);
	if(hFileMap == XFILEMAPINVALID) Error("XFileMapOpen Error!");

	const char* pInput = (const char*) XFileMapView(hFileMap, XFILEMAP_READONLY, 0, nFileSize);
	if(pInput == XMAPMEMINVALID) Error("XFileMapView Error!");

	
	// 统计每行输入占用的字符数量
	int nLineSize = 0;
	while(pInput[nLineSize] != '\r' && pInput[nLineSize] != '\n') ++nLineSize;
	while(pInput[nLineSize] == '\r' || pInput[nLineSize] == '\n') ++nLineSize;

	// 分配用于保存结果的内存空间
	int nCount = (nFileSize + 1) / nLineSize;
	int* pTotal = (int*)scalable_malloc(sizeof(int) * nCount);
	if(pTotal == NULL) Error("scalable_malloc Error!");

	if(nRunMode & XRUN_PARALLEL)
	{	// 并行模式
#pragma omp parallel for schedule(guided, 1)
		for(int i = 0; i < nCount; ++i)
		{
			pTotal[i] = XFindGrid(nRunMode, pInput + i * nLineSize);
		}
	}
	else
	{	// 	串行模式
		for(int i = 0; i < nCount; ++i)
		{
			pTotal[i] = XFindGrid(nRunMode, pInput + i * nLineSize);
		}
	}

	// 关闭输入文件映射
	XFileMapUnView((void*)pInput, nFileSize);
	XFileMapClose(&hFileMap);

#ifdef XOUT_TIME
	nEnd = tick_count::now(); 
	printf("计算时间:%f秒\n", (nEnd - nBeg).seconds());
	nBeg = tick_count::now();
#endif
	
	// 输出结果
	if(nRunMode & XRUN_FIND_ONE)
	{	
#ifdef XUSE_ENGLISH
		__declspec(align(16)) char  szHead[16] = "Puzzle # ";
		__declspec(align(16)) char  szTail[][32] = { " has NO solution\n", " has a UNIQUE solution\n",  " has MULTIPLE solutions\n"};
#else
		__declspec(align(16)) char  szHead[16] = "谜题 # ";
		__declspec(align(16)) char  szTail[][32] = { " 无解\n", " 有唯一解\n",  " 有多解\n"};
#endif		
		int   nBuffer = nCount * sizeof(char) * 36;
		if(nBuffer >  2 * 1024 * 1024) nBuffer = 2 * 1024 * 1024;
		char* pBuffer = (char*)scalable_malloc(sizeof(char) * nBuffer);
		if(pBuffer == NULL) Error("scalable_malloc Error!");
		char* pCur = pBuffer;
		char* pEnd = pBuffer + nBuffer - 64;
		for(int i = 0; i < nCount; ++i)
		{
			int nTmp = i + 1;

			XSAVESTR(pCur, szHead);
			XSAVENUM(pCur, nTmp);
			XSAVESTR(pCur, szTail[pTotal[i]]);

			if(pCur > pEnd)
			{
				fwrite(pBuffer, pCur - pBuffer, 1, stdout);
				pCur = pBuffer;
			}
		}

		if(pCur != pBuffer)
		{
			fwrite(pBuffer, pCur - pBuffer, 1, stdout);
		}

		scalable_free(pBuffer);

		// 估算文件大小
		/*int   nTail[3];
		int	  nHead = strlen(szHead);
		nTail[0] = strlen(szTail[0]);
		nTail[1] = strlen(szTail[1]);
		nTail[2] = strlen(szTail[2]);

		nFileSize = nHead * nCount + XGetNumSize(nCount);

#pragma omp parallel for reduction(+: nFileSize)
		for(int i = 0; i < nCount; ++i)
		{
			nFileSize += nTail[pTotal[i]];
		}
		
		// 打开输出文件映射
		hFileMap = XFileMapOpen("ret.txt", XFILEMAP_WRITE, nFileSize);
		if(hFileMap == XFILEMAPINVALID) Error("XFileMapOpen Error!");

		char* pOutput = (char*) XFileMapView(hFileMap, XFILEMAP_WRITE, 0, nFileSize);
		if(pOutput == XMAPMEMINVALID) Error("XFileMapView Error!");

		// 输出文件
		for(int i = 0; i < nCount; ++i)
		{	
			int nTmp = i + 1;
			XSAVESTR(pOutput, szHead);
			XSAVENUM(pOutput, nTmp);
			XSAVESTR(pOutput, szTail[pTotal[i]]);
		}
		
		// 关闭输出文件映射
		XFileMapUnView((void*)pOutput, nFileSize);
		XFileMapClose(&hFileMap);*/
	}
	else
	{	// 输出填值方案的数量
		for(int i = 0; i < nCount; ++i)
		{
			fprintf(stdout, "Puzzle #  %d has %d solutions\n", i, pTotal[i]);
		}
	}

	scalable_free(pTotal);

#ifdef XOUT_TIME
	nEnd = tick_count::now(); 
	printf("输出时间:%f秒\n", (nEnd - nBeg).seconds());

	nEndAll = tick_count::now(); 
	printf("总时间:%f秒\n", (nEndAll - nBegAll).seconds());
#endif

	return 0;
}