Partition and scheduling HW/SW help!

This is a discussion on Partition and scheduling HW/SW help! within the C++ Programming forums, part of the General Programming Boards category; Hi, I am working on my homework. But my result not correct. Please any one can help! I am programing ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    7

    Partition and scheduling HW/SW help!

    Hi, I am working on my homework. But my result not correct. Please any one can help!

    I am programing for DAG, to scheduling the running time for all task in DAG. Parent task needed to run, before children tasks can run. The siblings task can run parallel (1 one Hardware, one on software). The requirement is the running time is less than 12000, and the Hardware used limited in 50000.

    I have to get the result like this
    Task 0 runs on SW
    Start time: 0 End time: 250
    Task 1 runs on HW
    Start time: 250 End time: 1250 Transistor used: 10000
    Task 2 runs on SW
    Start time: 250 End time: 1750
    Task 3 runs on HW
    Start time: 1250 End time: 2250 Transistor used: 10000
    Task 4 runs on SW
    Start time: 1750 End time: 3250
    Task 5 runs on HW
    Start time: 3250 End time: 4250 Transistor used: 10000
    Task 6 runs on SW
    Start time: 3250 End time: 4750
    Task 7 runs on HW
    Start time: 4250 End time: 5250 Transistor used: 10000
    Task 8 runs on SW
    Start time: 4750 End time: 6250
    Task 9 runs on SW
    Start time: 6250 End time: 8850
    Task 10 runs on HW
    Start time: 8850 End time: 9350 Transistor used: 500
    Task 11 runs on HW
    Start time: 9350 End time: 11850 Transistor used: 9000

    The total time running is 11850 usec and total transistor used is 49500

    Here is my code:


    Code:
    #include <stdio.h>
    #include <math.h>
    
    #define MAX_PARENTS 10
    #define MAX_CHILDREN 10
    #define NONE -1
    #define MAX_TASKS 15
    #define SW 1
    #define HW 2
    
    #define HWLIMIT 50000 //the limit of the number of transistors allowed
    #define PERFORMANCELIMIT 12000 //the limit for performance (anything slower than this is no good!)
    
    struct task{
    
    	int parentArray[MAX_PARENTS];//an array of indeces representing the task's parents (ended with an entry NONE)
    	int childArray[MAX_CHILDREN];//an array of indeces representing the task's children (ended with an entry NONE)
    	int execTimeHW;//this task's execution time in hardware (usec)
    	int execTimeSW;//this task's execution time in software (usec)
    	int transistorCount;//this is the number of transistors required by the hardware implementation of this task
    	int currentMapping;//HW or SW (represents whether the task is currently mapped to software or hardware)
    	int scheduledStartTime; //record the time that this task will start execution (you may need this for scheduling)
    	int scheduledFinishTime; //record the time that this task will finish execution (you may need this for scheduling)
    	int statusTask; // show the status of the task, the task has already run or not
    };
    
    struct task JPEG[MAX_TASKS];//an array containing all of the tasks that need to be partitioned and then scheduled (tasks defined below)
    
    struct CPUEvent{  //an event on the CPU is when a task gets mapped there - it has a start time and an end time
    	int scheduledStartTime;//the scheduler will need to track this info in order to schedule the system properly
    	int scheduledEndTime;
    };
    
    struct CPUEvent CPU[MAX_TASKS]; //the array of CPU events (tracks when all SW scheduled tasks are executed on the processor)
    int CPUOpenSlot = 0; //this indicates the index in the CPU array that is empty
    
    // Find how many number elements in Arrays
    int ArraySize(struct task array[])
    {
        int i = 0;
        int element = 0;
        while(array[i].transistorCount > 0){
            i++;
            element++;
        }
        return element;
    }
    
    // Convert number to binary
    void task_binary(int rep[], int numberToConvert, int number)
    {
    	int i, x, y;
    	i = x = y = 0;
    	for(y = number-1 ; y >= 0; y--)
    	{	
    		x = numberToConvert / (1 << y); 
    		numberToConvert = numberToConvert - x*(1<<y); 
    		//printf("%d",x);
    		rep[i] = x;
    		i++;		
    	}
    }
    
    int NextTaskScheduling(int RunningTask[], int numberOfTask, int currentTask)
    {
    	int i,j;
    	int parentNeedtoRun = 0;
    	
    	// Changing the status of the already run task
    	for(i = 0; i < numberOfTask; i++)
    	{
    		if (RunningTask[i] == 1)
    			RunningTask[i] = 2;
    	}
    	
    	// Check for next task to be run
    	for(i = currentTask; i < numberOfTask; i++)
    	{
    		parentNeedtoRun = 0;
    		for(j = 0; j < numberOfTask; j++)
    		{
    			if(JPEG[i].parentArray[j] == NONE) break;
    			else if(RunningTask[JPEG[i].parentArray[j]]!= 2)
    				parentNeedtoRun = 1;
    		}
    		if(parentNeedtoRun == 0)
    			RunningTask[i] = 1;
    	}
    	
    	// Check if any task left (has not run)
    	for(i = 0; i < numberOfTask; i++)
    	{
    		if(RunningTask[i] == 0)
    			return 1;
    	}
    	return 0;
    }
    
    // initialize the data for task graph
    void initialize();
    
    int counter = 0;
    
    int main()
    {
    	struct task HW_Task[MAX_TASKS];
    	int rep_binary[MAX_TASKS];
    	int TaskTime[MAX_TASKS];
    
    	int nextTaskRunable[MAX_TASKS];
    	int numberOfTask;
    	int currentTime = 0;
    		    
        int HW_START_TIME = 0;
    	int Total_transistor = 0;
    	
    	int i,j,k;
    	int running_Task = 0;
    	int TaskRemaining = 0;
    	int currentTask = 0;
    	int statecount = 0;
    	
        //int actual_size_array = ArraySize(JPEG);
    	initialize();
    	numberOfTask = ArraySize(JPEG);
    	printf("\nThe number of task in DAG: %d\n\n", numberOfTask);
    	statecount = (int)pow(2,numberOfTask);
    	//printf("%d\n",statecount);
    	//partitioning and scheduling code here
    	//for(i = 0; i < statecount; i++)
    	i = 0;
    	while(i < statecount)
    	{
    		// Create the binary string represent the status of each task in graph for each trial
    		task_binary(&rep_binary, i ,numberOfTask);
    		rep_binary[0] = 1;
    		rep_binary[1] = 0;
    		rep_binary[2] = 1;
    		rep_binary[3] = 0;
    		rep_binary[4] = 1;
    		rep_binary[5] = 0;
    		rep_binary[6] = 1;
    		rep_binary[7] = 0;
    		rep_binary[8] = 1;
    		rep_binary[9] = 1;
    		rep_binary[10] = 0;
    		rep_binary[11] = 0;
    		
    		currentTime  = 0;
    		TaskRemaining = 1;
    		CPUOpenSlot = 0;
    		counter = 0;
    		running_Task = 0;
    		
    		for(j = 0; j < numberOfTask; j++)
    		{
    			CPU[j].scheduledStartTime = 0;
    			//printf("%d\n",CPU[j].scheduledStartTime);
    			CPU[j].scheduledEndTime = 0;
    			//printf("%d\n",CPU[j].scheduledEndTime);	
    		}
    		k = 0;
    		for(j = 0; j < numberOfTask; j++)
    		{
    			nextTaskRunable[j] = 0;
    			TaskTime[j] = 0;
    			if(rep_binary[j]==0)
    			{
    				TaskTime[j] = JPEG[j].execTimeHW;				
    				HW_Task[k] = JPEG[j]; 	
    				k++;
    			}
    								
    			else
    				TaskTime[j] = JPEG[j].execTimeSW;
    				
    			CPU[j].scheduledStartTime = 0;
    			//printf("%d\n",CPU[j].scheduledStartTime);
    			CPU[j].scheduledEndTime = 0;
    			//printf("%d\n",CPU[j].scheduledEndTime);			
    		}
    
    		/*for(j = 0; j < numberOfTask ; j++)
    		{
    			printf("%d",rep_binary[j]);
    		}
    		printf("\n");*/
    		
    		while(TaskRemaining == 1)
    		{
    			Total_transistor = 0;			
    			while(running_Task < numberOfTask)
    			{
    				TaskRemaining = NextTaskScheduling(&nextTaskRunable,numberOfTask,running_Task);
    				CPUOpenSlot = 0;
    				// Check how many task ready to run, stores in CPUOpenSlot
    				for (j = 0; j < numberOfTask; j++)
    				{
    					if(nextTaskRunable[j]==1)
    						CPUOpenSlot++;
    				}
    				// printf("CPUOpenSlot: %d\n",CPUOpenSlot);
    				// getch();
    				// Check how many task would run done
    				for(j = 0; j < numberOfTask; j++)
    				{
    					if(rep_binary[j] == 0 && nextTaskRunable[j] == 1)
    					{
    						Total_transistor += JPEG[running_Task].transistorCount;
    						CPU[j].scheduledStartTime = currentTime;
    						CPU[j].scheduledEndTime = TaskTime[j] + currentTime;
    						counter++;
    						//currentTime = TaskTime[j] + currentTime;
    						/*printf("Total Transistor: %d\n",Total_transistor);
    						printf("CPU start time: %d\n",CPU[j].scheduledStartTime);
    						printf("CPU end time: %d\n",CPU[j].scheduledEndTime);
    						printf("Counter: %d\n",counter);
    						getch();*/
    						if(CPUOpenSlot == 1)
    						{
    							currentTime = TaskTime[j] + currentTime;
    						}
    					}
    					else if (rep_binary[j] == 1 && nextTaskRunable[j] == 1)
    					{
    						CPU[j].scheduledStartTime = currentTime;
    						CPU[j].scheduledEndTime = TaskTime[j] + currentTime;
    						counter++;
    						currentTime = TaskTime[j] + currentTime;
    						/*printf("current time: %d\n",currentTime);
    						printf("CPU start time1: %d\n",CPU[j].scheduledStartTime);
    						printf("CPU end time1: %d\n",CPU[j].scheduledEndTime);
    						printf("Counter: %d\n",counter);
    						printf("current time1: %d\n",currentTime);
    						getch();*/
    					}
    				}
    				counter = 0;
    				running_Task += CPUOpenSlot;
    			}			
    		}
    		if(currentTime < PERFORMANCELIMIT && Total_transistor < HWLIMIT)
    		{
    			/*for(j = 0; j < numberOfTask; j++)
    				for(k = j+1; k < numberOfTask; k++)
    				{
    					if((rep_binary[j] == rep_binary[k]) && (CPU[j].scheduledStartTime == CPU[k].scheduledStartTime)) goto next;
    				}*/
    
    			for (j = 0 ; j < numberOfTask ; j++)
    			{
    				printf("\nTask %2d was running ",j);
    				if (rep_binary[j] == 0)
    					printf("HW. \nStart time: %5d. End Time: %5d.\n", CPU[j].scheduledStartTime, CPU[j].scheduledEndTime);
    				else if(rep_binary[j]==1)
    					printf("SW. \nStart time: %5d. End Time: %5d.\n", CPU[j].scheduledStartTime, CPU[j].scheduledEndTime);
    			}
    			printf("------------------------------------\n");
    			printf("\n\n********Total run time: %5d. Total transistors: %5d.********\n\n", currentTime, Total_transistor);	
    			//getch();			
    			break;
    		}
    		
    		next:	i++;
    
    	}
    	//after partitioning be sure to print out your HW/SW and scheduling results
    
    	return 0;
    }
    
    
    
    
    void initialize(){
    
    	//PRE-PROCESSING
    	JPEG[0].parentArray[0] = NONE;
    	JPEG[0].childArray[0] = 1;
    	JPEG[0].childArray[1] = 2;
    	JPEG[0].childArray[2] = 3;
    	JPEG[0].childArray[3] = 4;
    	JPEG[0].childArray[4] = NONE;
    	JPEG[0].execTimeHW = 100;
    	JPEG[0].execTimeSW = 250;
    	JPEG[0].transistorCount = 3500;
    
    	//VM1
    	JPEG[1].parentArray[0] = 0;
    	JPEG[1].parentArray[1] = NONE;
    	JPEG[1].childArray[0] = 5;
    	JPEG[1].childArray[1] = 6;
    	JPEG[1].childArray[2] = 7;
    	JPEG[1].childArray[3] = 8;
    	JPEG[1].childArray[4] = NONE;
    	JPEG[1].execTimeHW = 1000;
    	JPEG[1].execTimeSW = 1500;
    	JPEG[1].transistorCount = 10000;
    
    	//VM2
    	JPEG[2].parentArray[0] = 0;
    	JPEG[2].parentArray[1] = NONE;
    	JPEG[2].childArray[0] = 5;
    	JPEG[2].childArray[1] = 6;
    	JPEG[2].childArray[2] = 7;
    	JPEG[2].childArray[3] = 8;
    	JPEG[2].childArray[4] = NONE;
    	JPEG[2].execTimeHW = 1000;
    	JPEG[2].execTimeSW = 1500;
    	JPEG[2].transistorCount = 10000;
    
    	//VM3
    	JPEG[3].parentArray[0] = 0;
    	JPEG[3].parentArray[1] = NONE;
    	JPEG[3].childArray[0] = 5;
    	JPEG[3].childArray[1] = 6;
    	JPEG[3].childArray[2] = 7;
    	JPEG[3].childArray[3] = 8;
    	JPEG[3].childArray[4] = NONE;
    	JPEG[3].execTimeHW = 1000;
    	JPEG[3].execTimeSW = 1500;
    	JPEG[3].transistorCount = 10000;
    
    	//VM4
    	JPEG[4].parentArray[0] = 0;
    	JPEG[4].parentArray[1] = NONE;
    	JPEG[4].childArray[0] = 5;
    	JPEG[4].childArray[1] = 6;
    	JPEG[4].childArray[2] = 7;
    	JPEG[4].childArray[3] = 8;
    	JPEG[4].childArray[4] = NONE;
    	JPEG[4].execTimeHW = 1000;
    	JPEG[4].execTimeSW = 1500;
    	JPEG[4].transistorCount = 10000;
    
    	//VM5
    	JPEG[5].parentArray[0] = 1;
    	JPEG[5].parentArray[1] = 2;
    	JPEG[5].parentArray[2] = 3;
    	JPEG[5].parentArray[3] = 4;
    	JPEG[5].parentArray[4] = NONE;
    	JPEG[5].childArray[0] = 9;
    	JPEG[5].childArray[1] = NONE;
    	JPEG[5].execTimeHW = 1000;
    	JPEG[5].execTimeSW = 1500;
    	JPEG[5].transistorCount = 10000;
    
    	//VM6
    	JPEG[6].parentArray[0] = 1;
    	JPEG[6].parentArray[1] = 2;
    	JPEG[6].parentArray[2] = 3;
    	JPEG[6].parentArray[3] = 4;
    	JPEG[6].parentArray[4] = NONE;
    	JPEG[6].childArray[0] = 9;
    	JPEG[6].childArray[1] = NONE;
    	JPEG[6].execTimeHW = 1000;
    	JPEG[6].execTimeSW = 1500;
    	JPEG[6].transistorCount = 10000;
    
    	//VM7
    	JPEG[7].parentArray[0] = 1;
    	JPEG[7].parentArray[1] = 2;
    	JPEG[7].parentArray[2] = 3;
    	JPEG[7].parentArray[3] = 4;
    	JPEG[7].parentArray[4] = NONE;
    	JPEG[7].childArray[0] = 9;
    	JPEG[7].childArray[1] = NONE;
    	JPEG[7].execTimeHW = 1000;
    	JPEG[7].execTimeSW = 1500;
    	JPEG[7].transistorCount = 10000;
    
    	//VM8
    	JPEG[8].parentArray[0] = 1;
    	JPEG[8].parentArray[1] = 2;
    	JPEG[8].parentArray[2] = 3;
    	JPEG[8].parentArray[3] = 4;
    	JPEG[8].parentArray[4] = NONE;
    	JPEG[8].childArray[0] = 9;
    	JPEG[8].childArray[1] = NONE;
    	JPEG[8].execTimeHW = 1000;
    	JPEG[8].execTimeSW = 1500;
    	JPEG[8].transistorCount = 10000;
    
    	//QUANTIZATION
    	JPEG[9].parentArray[0] = 5;
    	JPEG[9].parentArray[1] = 6;
    	JPEG[9].parentArray[2] = 7;
    	JPEG[9].parentArray[3] = 8;
    	JPEG[9].parentArray[4] = NONE;
    	JPEG[9].childArray[0] = 10;
    	JPEG[9].childArray[1] = NONE;
    	JPEG[9].execTimeHW = 2500;
    	JPEG[9].execTimeSW = 2600;
    	JPEG[9].transistorCount = 6000;
    
    	//ZIG-ZAG
    	JPEG[10].parentArray[0] = 9;
    	JPEG[10].parentArray[1] = NONE;
    	JPEG[10].childArray[0] = 11;
    	JPEG[10].childArray[1] = NONE;
    	JPEG[10].execTimeHW = 500;
    	JPEG[10].execTimeSW = 2500;
    	JPEG[10].transistorCount = 500;
    
    	//RLE & HUFFMAN ENCODING
    	JPEG[11].parentArray[0] = 10;
    	JPEG[11].parentArray[1] = NONE;
    	JPEG[11].childArray[0] = NONE;
    	JPEG[11].execTimeHW = 2500;
    	JPEG[11].execTimeSW = 4000;
    	JPEG[11].transistorCount = 9000;
    
    
    }
    Attached Images Attached Images  
    Last edited by Salem; 11-01-2010 at 10:43 PM. Reason: Added [code][/code] tags - learn to read sticky threads

  2. #2
    Registered User
    Join Date
    Nov 2010
    Posts
    7
    thanks for fix my post.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,341
    So what do you want from us?

    Dumping a whole load of code, and not much explanation doesn't really work for us. Our time is limited, and we don't tend to spend it on single posts which might take several hours of effort only to discover something is missing.

    Some analysis on your part (well it does the first 5 iterations OK, and the 6th goes all weird (results attached)) would go a long way to convincing us that you've made an effort to figure some stuff out, and your results may at least give some clue as to where to start looking.


    > rep_binary[0] = 1;
    So why do you ignore the output of your first function and hard-code every single loop with the same data.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Posts
    7
    Thanks for your help! I really appreciate your help.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21