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;
}
