bc.cu

#ifndef USE_OLD_ALG
	#define USE_OLD_ALG 0
#endif
#ifndef KERNEL_DEBUG
	#define KERNEL_DEBUG 0
#endif
#ifndef TEST
	#define TEST 0
#endif
//
// cluster or local?
//



#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>

#include <thrust/version.h>
#include <iostream>
using namespace std;


#include "machine_specific.h"
#include "cuds/cuds_common.h"
#include "cuds/EdgeList.h"
#include "cuds/AdjacencyLists.h"


#if USE_OLD_ALG
	#include "cuds/SSSP.cu"
	#include "cuds/APSP.cu"
#endif

#include "cuds/BCentrality.cu"





namespace cuds{


	#if USE_OLD_ALG
	
	void testSssp(const int nV){
		//cuds::sssp::runDummyKernel();
		//return;
		cuds::adjlists::AdjacencyLists g;
		g.generate(nV,5);
		g.print();
		////
		cuds::intDeviceVector vdPrev(nV);
		cuds::floatDeviceVector vdCost(nV);
		int src = 0;
		int dest = nV - 1;
		////
		printf("Entering Dijkstra\n");
		cuds::sssp::dijkstra(g,0, vdCost, vdPrev);
		////
		cuds::intHostVector vhPrev = vdPrev;
		cuds::floatHostVector vhCost = vdCost;
		printf("Final cost:\n");
		cuds::printDeviceArr<float>( thrust::raw_pointer_cast(vdCost.data()), nV );
		printf("Final predecessors:\n");
		cuds::printDeviceArr<int>( thrust::raw_pointer_cast(vdPrev.data()), nV );
		for(int i = 0; i < nV; i++){
			if( i == src ) {
				continue;
			}
			if( vhCost[i] == CUDS_INF ){
				// unreachable
				printf( "[%d unreachable from %d]\n", i, src);
			}
			else{
				printf("[");
				cuds::sssp::printPath(src,i,vhPrev);
				printf("] cost: %0.02f\n", vhCost[i]);
			}
		}
	}
	void testApspDijkstra(const int nV){
		const int nV2 = (int)(nV * nV);
		//cuds::sssp::runDummyKernel();
		//return;
		#define __CUDS_LOCATION_DEVICE__ 1		
		cuds::adjlists::AdjacencyLists g;
		g.generate(nV,5);
		g.print();
		////
		cuds::intDeviceVector vdPrev;
		cuds::floatDeviceVector vdCost;
		////
		printf("Entering Dijkstra\n");
		cuds::apsp::dijkstra(g, vdCost, vdPrev);
		////
		cuds::intHostVector vhPrev = vdPrev;
		cuds::floatHostVector vhCost = vdCost;
		for(int src = 0; src < nV; src++){
			int offset = src * nV;
			int srcIndex = offset + src;
			printf("\n----------\nAPSP source: %d\n----------\n", src);
			printf("Final cost:\n");
			cuds::printDeviceArr<float>( thrust::raw_pointer_cast(vdCost.data()) + offset, nV );
			printf("Final predecessors:\n");
			cuds::printDeviceArr<int>( thrust::raw_pointer_cast(vdPrev.data()) + offset, nV );
			for(int dest = 0; dest < nV; dest++){
				if( dest == src ) {
					continue;
				}
				int destIndex = offset + dest;
				if( vhCost[destIndex] == CUDS_INF ){
					// unreachable
					printf( "[%d unreachable from %d]\n", dest, src);
				}
				else{
					printf("[");
					cuds::sssp::printPath(src, dest, vhPrev, offset);
					printf("] cost: %0.02f\n", vhCost[destIndex]);
				}
			}
		}
	}
	void testBcDijkstra(const int nV){
		const int nV2 = (int)(nV * nV);
		//cuds::sssp::runDummyKernel();
		//return;
		cuds::adjlists::AdjacencyLists g;
		g.generate(nV,5);
		//#if __CUDS_VERBOSE__
		//g.print();
		//#endif
		////
		cuds::floatDeviceVector  vdCost, vdTime(1, 0);
		cuds::intDeviceVector vdBc, vdPred;
		float *pdTime = thrust::raw_pointer_cast(vdTime.data());
		////
		//printf("Entering BC_Dijkstra\n");
		cuds::bc::dijkstra::bc(g, vdBc, vdPred, vdCost, pdTime);
		//
		printf("\n####################\nBetweenness Centrality (APSP Dijkstra): \n####################\n");
		printf("GPU time (without host/device transfer):\n");
		cuds::printDeviceArr<float>(pdTime, 1, true);
		int* pdBc = thrust::raw_pointer_cast(vdBc.data());
		cuds::printDeviceArr<int>(pdBc, nV, true);
		cuds::floatHostVector vhCost = vdCost;
		cuds::intHostVector vhPred = vdPred;
		//
		for(int src = 0; src < nV; src++){
			int offset = src * nV;
			int srcIndex = offset + src;
			printf("\n----------\nAPSP source: %d\n----------\n", src);
			//printf("Final cost:\n");
			//cuds::printDeviceArr<float>( thrust::raw_pointer_cast(vdCost.data()) + offset, nV );
			//printf("Final predecessors:\n");
			//cuds::printDeviceArr<int>( thrust::raw_pointer_cast(vdPred.data()) + offset, nV );
			for(int dest = 0; dest < nV; dest++){
				if( dest == src ) {
					continue;
				}
				int destIndex = offset + dest;
				if( vhCost[destIndex] == CUDS_INF ){
					// unreachable
					//printf( "[%d unreachable from %d]\n", dest, src);
				}
				else{
					printf("[");
					cuds::sssp::printPath(src, dest, vhPred, offset);
					printf("] cost: %0.02f\n", vhCost[destIndex]);
				}
			}
		}
	}
	
	#endif
	
	void testGraph(const int nV){
		//cuds::adjlists::AdjacencyLists g, g2;
		cuds::edgelist::EdgeList g3;
		//g.generate(nV,5);
		//g.print();
		//g.write("/home/saad/cuda-projects/hw/g.txt");
		//printf("\n\nReading EdgeList into AdjacencyLists\n\n");
		//g2.read("/home/saad/cuda-projects/hw/g.txt");
		//g2.print();
		//
		//
		printf("\n\nReading EdgeList into EdgeArray\n\n");
		cuds::graph::read("/home/saad/cuda-projects/hw/g.txt", g3);
		g3.print();

	}
	
	bool testBcShi(const string inFile, int blockSize, 
		bool memcheckOnly, bool showOutput, int runNumber, string& csvLineString){
		printf("*** BC-Shi ***\n");
		printf("\nUsing input file: %s\n", inFile.c_str());
		//const int nV2 = (int)(nV * nV);
		//cuds::sssp::runDummyKernel();
		//return;
		cuds::edgelist::EdgeList g;		
		//
		// how many vertices and edges?
		//
		int n = 0,m = 0;
		if( cuds::graph::getGraphSize(inFile.c_str(), n, m) ){
			printf("nV: %d nE: %d\n", n, m);
			//string errorMessage;
			//if( !cuds::bc::checkMemoryRequirements(cuds::bc::BC_ALG_SRIRAM, n, m, errorMessage) ){
				//printf("Error: %s", errorMessage.c_str());
				//return;
			//}
			//else{
				//printf("[ok]\n");
			//}
		}else{
			printf("Error reading graph info (nV/nE) form file %s\n", inFile.c_str());
			g.clear();
			return false;
		}
		//
		// ok, now we can proceed
		//
		// read the graph
		//
		if(!cuds::graph::read(inFile.c_str(), g)){
			return false;
		}
		const int nV = g.nVertices();
		//#if __CUDS_VERBOSE__
		//g.print();
		//#endif
		////
		//cuds::floatDeviceVector vdTime(1, 0);
		cuds::floatDeviceVector vdBc;
		float timeInMilliSec = 0;
		//cuds::intDeviceVector vdPred;
		//////
		//
		//
		printf("\nEntering BC_Shi\n");
		string errorMessage;
		if(cuds::bc::shi::bc(g, vdBc, errorMessage, csvLineString, timeInMilliSec, inFile, blockSize,  memcheckOnly, runNumber) ){
			//
			//
			if( showOutput ){
				printf("\n####################\nBetweenness Centrality (Shi): \n####################\n");
				//printf("GPU time (without host/device transfer):\n");
				//cuds::printDeviceArr<float>(pdTime, 1, true);
				float* pdBc = thrust::raw_pointer_cast(vdBc.data());
				//float *pdTime = thrust::raw_pointer_cast(vdTime.data());
				cuds::printDeviceArr<float>(pdBc, nV, true);
			}
			printf("Kernel time: %f millisec\n", timeInMilliSec);
		}
		else{
			printf("Error: %s\n", errorMessage.c_str());
			g.clear();
			return false;
		}
		//
		// clean up
		//
		g.clear();
		return true;
	}
	bool testBcJia(const string inFile, bool memcheckOnly, bool showOutput, int runNumber, string& csvLineString){
		printf("*** BC-Jia ***\n");
		printf("\nUsing input file: %s\n", inFile.c_str());
		//const int nV2 = (int)(nV * nV);
		//cuds::sssp::runDummyKernel();
		//return;
		cuds::edgelist::EdgeList g;		
		//
		// how many vertices and edges?
		//
		int n = 0,m = 0;
		if( cuds::graph::getGraphSize(inFile.c_str(), n, m) ){
			printf("nV: %d nE: %d\n", n, m);
			//string errorMessage;
			//if( !cuds::bc::checkMemoryRequirements(cuds::bc::BC_ALG_SRIRAM, n, m, errorMessage) ){
				//printf("Error: %s", errorMessage.c_str());
				//return;
			//}
			//else{
				//printf("[ok]\n");
			//}
		}else{
			printf("Error reading graph info (nV/nE) form file %s\n", inFile.c_str());
			g.clear();
			return false;
		}
		//
		// ok, now we can proceed
		//
		// read the graph
		//
		if(!cuds::graph::read(inFile.c_str(), g)){
			g.clear();
			return false;
		}
		const int nV = g.nVertices();
		//#if __CUDS_VERBOSE__
		//g.print();
		//#endif
		////
		//cuds::floatDeviceVector vdTime(1, 0);
		cuds::floatDeviceVector vdBc;
		float timeInMilliSec = 0;
		//cuds::intDeviceVector vdPred;
		//////
		//
		//
		printf("\nEntering BC_Jia\n");
		string errorMessage;
		if(cuds::bc::jia::bc(g, vdBc, errorMessage, csvLineString, timeInMilliSec, inFile, memcheckOnly, runNumber) ){
			//
			//
			if( showOutput ){
				printf("\n####################\nBetweenness Centrality (Jia): \n####################\n");
				//printf("GPU time (without host/device transfer):\n");
				//cuds::printDeviceArr<float>(pdTime, 1, true);
				float* pdBc = thrust::raw_pointer_cast(vdBc.data());
				//float *pdTime = thrust::raw_pointer_cast(vdTime.data());
				cuds::printDeviceArr<float>(pdBc, nV, true);
			}
			printf("Kernel time: %f millisec\n", timeInMilliSec);
		}
		else{
			printf("Error: %s\n", errorMessage.c_str());
			return false;
		}
		//
		// clean up
		//
		g.clear();
		return true;
	}
	bool testBcSriram(const string inFile, bool useSuccessor, 
		bool memcheckOnly, bool showOutput, int runNumber, string& csvLineString){		
		printf("*** BC-Sriram ***\n");
		printf("\nUsing input file: %s\n", inFile.c_str());
		//const int nV2 = (int)(nV * nV);
		//cuds::sssp::runDummyKernel();
		//return;
		cuds::adjlists::AdjacencyLists g;		
		//
		// how many vertices and edges?
		//
		int n = 0,m = 0;
		if( cuds::graph::getGraphSize(inFile.c_str(), n, m) ){
			printf("nV: %d nE: %d\n", n, m);
			//string errorMessage;
			//if( !cuds::bc::checkMemoryRequirements(cuds::bc::BC_ALG_SRIRAM, n, m, errorMessage) ){
				//printf("Error: %s", errorMessage.c_str());
				//return;
			//}
			//else{
				//printf("[ok]\n");
			//}
		}else{
			printf("Error reading graph info (nV/nE) form file %s\n", inFile.c_str());
			g.clear();
			return false;
		}
		//
		// ok, now we can proceed
		//
		// read the graph
		//
		if(!cuds::graph::read(inFile.c_str(), g)){
			g.clear();
			return false;
		}
		//g.print();
		//
		//
		const int nV = g.nVertices();
		//#if __CUDS_VERBOSE__
		//g.print();
		//#endif
		////
		//cuds::floatDeviceVector vdTime(1, 0);
		cuds::floatDeviceVector vdBc;
		float timeInMilliSec = 0;
		//cuds::intDeviceVector vdPred;
		//////
		//
		//
		printf("\nEntering BC_Sriram\n");
		string errorMessage;
		if(cuds::bc::sriram::bc(g, useSuccessor, vdBc, 
			errorMessage, csvLineString, timeInMilliSec, inFile, memcheckOnly, runNumber) ){
			//
			//
			if( showOutput ){
				printf("\n####################\nBetweenness Centrality (Sriram): \n####################\n");
				//printf("GPU time (without host/device transfer):\n");
				//cuds::printDeviceArr<float>(pdTime, 1, true);
				float* pdBc = thrust::raw_pointer_cast(vdBc.data());
				//float *pdTime = thrust::raw_pointer_cast(vdTime.data());
				cuds::printDeviceArr<float>(pdBc, nV, true);
			}
			printf("Kernel time: %f millisec\n", timeInMilliSec);
		}
		else{
			printf("Error: %s\n", errorMessage.c_str());
			g.clear();
			return false;
		}
		//
		// clean up
		//
		g.clear();
		return true;
	}
	void testVector(){
		cuds::intDeviceVector vdA(1,19);
		cuds::intHostVector vhA(1,17);
		int* pdA = thrust::raw_pointer_cast(vdA.data() );
		int* phA = thrust::raw_pointer_cast(vhA.data() );
		cuds::boolDeviceVector vdB(1,true);
		cuds::boolHostVector vhB(1,true);
		bool* pdB = thrust::raw_pointer_cast(vdB.data() );
		bool* phB = thrust::raw_pointer_cast(vhB.data() );
		//
		int a = vdA[0];
		int b = vhA[0];
		printf("a: %d, b: %d\n", a, b); // 19, 17
		vdA[0] = 2;
		vhA[0] = 3;
		a = vdA[0];
		b = vhA[0];
		printf("%d, %d\n", a, b); // 2, 3
//		printf("%d, %d\n", vdA[0], vhA[0]); // 2, 3 will issue warning
		vhA = vdA;
		a = vdA[0];
		b = vhA[0];
		printf("%d, %d\n", a, b); // 2, 2
		thrust::copy(vdA.begin(), vdA.end(), vhA.begin());
		a = vdA[0];
		b = vhA[0];
		printf("%d, %d\n", a, b); // 2, 2
		vhA.clear();
		vhA.resize(1,4);
		a = vdA[0];
		b = vhA[0];
		printf("%d, %d\n", a, b); // 2, 4
		vdA[0] = 9;
		vhA[0] = 10;
		printf("%d, %d\n", (int)(vdA[0]), vhA[0]); // 9, 10
		vdA[0] = vdA[0] + 1;
		vhA[0] = vhA[0] + 1;
		printf("%d, %d\n", (int)(vdA[0]), vhA[0]); // 10, 11
		vdA[0]++;
		vhA[0]++;
		printf("%d, %d\n", (int)(vdA[0]), vhA[0]); // 11, 12
		phA[0]++;
		printf("%d, %d\n", (int)(vdA[0]), vhA[0]); // 11, 13
		vhA[0]++;
		printf("%d, %d\n", (int)(vdA[0]), phA[0]); // 11, 14
		vhB[0] = false;
		vdB[0] = true;
		printf("%d, %d\n", (bool)(vdB[0]), (bool)phB[0]); // 1, 0
	}



};




//
//
//
int main(int argc, char** argv){
	srand((unsigned int)time(NULL));
	
	
	//
	time_t rawtime;
	struct tm * timeinfo;

	time ( &rawtime );
	timeinfo = localtime ( &rawtime );
	printf("%sSaad Quader Betweenness Centrality\n", asctime (timeinfo));
	//
	// parse command line options
	//
    /* Flag set by ‘--verbose’. */
     static int noBitPredMatrixFlag = 0;
     static int shiFlag = 0;
     static int jiaFlag = 0;
     static int sriramFlag = 0;
     static int showOutputFlag = 0;
     static int memoryCheckOnly = 0;
     static int sriramUseSuccessorFlag = 0;
     static int shiBlockSize = 0;
     static int runNumber = 1;
     string inFile = "", outFile = "", configName = "";
     
       int c;
     
       while (1)
         {
           static struct option long_options[] =
             {
               /* These options set a flag. */
               {"nobitpred", no_argument,       &noBitPredMatrixFlag, 1},
               {"shi",   no_argument,       &shiFlag, 1},
               {"jia",   no_argument,       &jiaFlag, 1},
               {"sriram",   no_argument,       &sriramFlag, 1},
               {"memcheck",  no_argument, &memoryCheckOnly, 1},
               {"show",  no_argument, &showOutputFlag, 1},
               {"successor",  no_argument, &sriramUseSuccessorFlag, 1},
               /* These options don't set a flag.
                  We distinguish them by their indices. */
               {"shi-block-size", required_argument, 0, 's'}, // block size of shi
               {"input",  required_argument, 0, 'i'}, // input file
               {"output",  required_argument, 0, 'o'}, // output file for stats
               {"config",    required_argument, 0, 'c'}, // name of the configuration
               {"run",    required_argument, 0, 'r'}, // name of the configuration
               {0, 0, 0, 0}
             };
           /* getopt_long stores the option index here. */
           int option_index = 0;
     
           c = getopt_long (argc, argv, "s:i:o:c:r:",
                            long_options, &option_index);
     
           /* Detect the end of the options. */
           if (c == -1)
             break;
     
           switch (c)
             {
             case 0:
               /* If this option set a flag, do nothing else now. */
               if (long_options[option_index].flag != 0)
                 break;
               printf ("option %s", long_options[option_index].name);
               if (optarg)
                 printf (" with arg %s", optarg);
               printf ("\n");
               break;
                    
             case 's':
               printf ("option -s with value `%s'\n", optarg);
				shiBlockSize = atoi(optarg);
               break;
     
             case 'r':
               printf ("option -r with value `%s'\n", optarg);
				runNumber = atoi(optarg);
               break;
     
             case 'i':
               printf ("option -i with value `%s'\n", optarg);
               inFile = optarg;
               break;
     
             case 'o':
               printf ("option -o with value `%s'\n", optarg);
               outFile = optarg;
               break;
     
             case 'c':
               printf ("option -c with value `%s'\n", optarg);
               configName = optarg;
               break;
     
             case '?':
               /* getopt_long already printed an error message. */
               break;
     
             default:
               abort ();
             }
         }
     
       /* Instead of reporting ‘--verbose’
          and ‘--brief’ as they are encountered,
          we report the final status resulting from them. */
       if (noBitPredMatrixFlag)
         puts ("nobitpred flag is set");
       if (shiFlag)
         puts ("shi flag is set");
       if (jiaFlag)
         puts ("jia flag is set");
       if (sriramFlag)
         puts ("sriram flag is set");
       if (sriramUseSuccessorFlag)
         puts ("successor flag is set");
       if (memoryCheckOnly)
         puts ("memcheck flag is set");
     
       /* Print any remaining command line arguments (not options). */
       if (optind < argc)
         {
           printf ("non-option ARGV-elements: ");
           while (optind < argc)
             printf ("%s ", argv[optind++]);
           putchar ('\n');
         }
	//
	// resolve options dependency
	//
	if(!(shiFlag || jiaFlag || sriramFlag )){
		printf("No bc algorithm is mentioned. Set one of the flags {--shi, --jia, --sriram}\n");
		return 0;
	}
	if( (shiFlag && (sriramFlag || jiaFlag) ) ||
		(sriramFlag && (shiFlag || jiaFlag) ) ||
		(jiaFlag && (sriramFlag || shiFlag) ) ){
			printf("Options error: Only one of the flags {--shi, --jia, --sriram} can be set at a time.\n");
			return 0;
	}
	if( shiFlag && shiBlockSize < 0){
		printf("--shi-block-size: Block size must be non-negative (0 means maximum).\n");
		return 0;
	}
	if( sriramUseSuccessorFlag && !sriramFlag){
		printf("--successor: applies only to Sriram's algorithm (--sriram).\n");
		return 0;
	}
	if( inFile == "" ){
		printf("[Error] No input file specified.\n");
		return 0;
	}
	//
	// ready to go
	//
	printf("Done option parsing.\n");
	//return;
	//saad::testGraph();
	int cuda_major =  CUDA_VERSION / 1000;
	int cuda_minor = (CUDA_VERSION % 1000) / 10;

	int thrust_major = THRUST_MAJOR_VERSION;
	int thrust_minor = THRUST_MINOR_VERSION;

	std::cout << "CUDA   v" << cuda_major   << "." << cuda_minor   << std::endl;
	std::cout << "Thrust v" << thrust_major << "." << thrust_minor << std::endl;
	printf("sizeof int: %d float: %d bool: %d\n", sizeof(int), sizeof(float), sizeof(bool));
	//
	// call bc algorithm
	//
	string csvLineString = "";
	bool bcAlgStatus = false;
	if( shiFlag ){
		bcAlgStatus = cuds::testBcShi(inFile, shiBlockSize, (bool) memoryCheckOnly, (bool)showOutputFlag, runNumber, csvLineString);
	}
	else if( jiaFlag){
		bcAlgStatus = cuds::testBcJia(inFile, (bool) memoryCheckOnly, (bool) showOutputFlag, runNumber, csvLineString);
	}
	else if( sriramFlag){
		bcAlgStatus = cuds::testBcSriram(inFile, (bool) sriramUseSuccessorFlag, (bool) memoryCheckOnly, (bool) showOutputFlag, runNumber, csvLineString);
	}
	//
	// done algorithm
	//
	time ( &rawtime );
	timeinfo = localtime ( &rawtime );
	string csvFile = "";
	if( bcAlgStatus == false){
		csvFile = "output/bc-exp-fail.csv";
		char str[1000];
		memset(str, 0, 1000);
		sprintf(
			str,
			"%s\t%s\n",
			configName.c_str(),
			inFile.c_str()
		);
		csvLineString = str;
	}
	else{
		if(outFile == "" ){
			outFile = "output/bc-exp-outcome.csv";
		}
		csvFile = outFile;
	}
	if(csvLineString != "" ){
		printf("\nCSV output in %s:\n%s\n", csvFile.c_str(), csvLineString.c_str());
		//
		// write output in output file
		//
		int maxAttempts = 10;
		unsigned long backoff = 1 * 1000 * 1000; // in microseconds
		int iter = 1;
		bool done = false;
		do{
			FILE* fp = fopen(csvFile.c_str(), "a");
			if(fp == NULL){
				usleep(backoff * iter); // if the file is not availeble, backoff and then try again
				continue;
			}
			else{
				fprintf(fp, "%s", csvLineString.c_str() );
				done = true;
				fclose(fp);
			}
		}while(!done && maxAttempts-- > 0);
		if( done == false){
			printf("\nOutput Error: Failed to print the csv line in file %s\n", outFile.c_str());
		}
	}
	/*
	//
	//string inFile = "g8.txt"; // by default, read g8.txt	
	//if( argc > 1 ){
		//inFile = argv[1];
	//}
	//
	//int n = (int) pow(2.0f,5);
	//if( argc > 1 ){
		//n = (int) pow(2.0f, atoi(argv[1]));
	//}
	//
	//cuds::adjlists::AdjacencyLists g;
	//g.generate(4, 3);
	//g.write("g4.txt");
	//g.generate(8, 6);
	//g.write("g8.txt");
	//g.generate(16, 10);
	//g.write("g16.txt");
	//g.generate(32, 16);
	//g.write("g32.txt");
	//g.generate(64, 16);
	//g.write("g64.txt");
	//g.generate(128, 16);
	//g.write("g128.txt");
	//g.print();
	//
	//cuds::edgelist::EdgeList g2;
	//g2.read("g.txt");
	//g2.print();
	//
	//printf("nV = %d\n", n);
	//cuds::testVector();
	// saad::testSssp(n);
	//saad::testApspDijkstra(n);
	//cuds::testBcDijkstra(n);
	//cuds::testGraph(n);
	* */
	
	
	return 1;
}