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;


}

---

thanks for fix my post.

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.

Thanks for your help! I really appreciate your help.