Scheduling algorithm

This is an implementation of ASAP scheduling algorithm, ALAP scheduling algorithm and LIST_L scheduling algorithm.

It is assumed that:
    + ALU will do the arithmetical operations: +, -, >,<, etc.
    + Multiplier: *
    + Divisor: /

LIST_L scheduling algorithm: (adjusted from the book: Synthesis and Optimizations of Digital Circuits by Giovanni De Micheli)

{

            Repeat until all vertices determined {

                        Determined the distance label between vertex V_i and sink;

             }

Repeat until all non-leaf vertices are scheduled: {

                        Repeat for each source type

                          {

                                      Determine ready vertices U;

                                      Determine unfinished vertices T;

                                      Select S Є U;

                                      Schedule S at clock cycle l;

                           }

                            l = l + 1;

            }                                           

            return (t);

}

ALAP scheduling algorithm:
(adjusted from the book: Synthesis and Optimizations of Digital Circuits by Giovanni De Micheli)

ALAP_Algorithm(DFG(V,E), λ)

{

            Repeat until all leaf vertices are scheduled:

            {

                        Schedule a leaf vertex V_i by setting t_i = λ + 1 - d_i;

                        Set the status of leaf vertex t_i as scheduled;

             }

Repeat until all non-leaf vertices are scheduled:

            {

                        Schedule vertex V_j whose successors are all scheduled;

                        Set t_j = Min{t_i - d_j}; //V_j is a successor vertex of V_i

            }                                            //d_j is execution delay of V_j

            return (t);

}

ASAP scheduling algorithm: (adjusted from the book: Synthesis and Optimizations of Digital Circuits by Giovanni De Micheli)

ASAP_Algorithm(DFG(V,E))

{

Schedule all root vertices and set the start time to t_o = 1;

Repeat until all non-root vertices are scheduled;

            {

                        Schedule vertex V_i whose predecessors are scheduled;

                        Set t_i = Max{t_j + d_j}; //V_j is a predecessor vertex of V_i

            }                                            //d_j is execution delay of V_j

            return (t);

}

The input of this program is the text file which contains information of data flow graph.

For the data flow graph as below:

Above DFG will be mapped into the text file as following:

If the third value, resource constraint, is -1, then there is no resource constraint for that functional unit.
For example:
(ALU,1,-1) : ALU operation's execution delay is 1 clock cycle, no resource constraints.

Anyway, this tool assumes that ASAP and ALAP have no resource constraint which means that the third parameter in [Functional Unit Attribute] will be ignored for these 2 algorithms. It just affects the LIST_L algorithm.

Below is the interface of the program, and the result:

Running for ASAP scheduling algorithm:

For LIST_L algorithm: