Implementation of Feautriers method for scheduling

• scheduler/schedule.cc
• scheduler/proto_s.cc
• scheduler/equation.cc
• scheduler/dual_m.cc
• scheduler/calcsche.cc
• scheduler/scanpars.cc
• scheduler/pip.cc
• scheduler/p_sched.cc

//-----------------------------------------------------------------------------
// function   : compute_affin_schedule  
// description: This function performs the process of computing the affin
//              schedules for each statement of a given source code as it is
//              described in the paper of Feautrier.
//----------------------------------------------------------------------------- 
void compute_affin_schedule( Source_code *source )
{
        cout << SCHEDULER_START;
        Eq_system *system_of_equations;
        Ineq_system *system_of_inequalities;

        // build the prototype schedules for each statement
        create_prototype_schedules( source );
        // create the system of equations resulting from Farka's lemma
        system_of_equations = create_system_of_equations( source );
        // create the system of inequalities from this equation system
        system_of_inequalities = create_system_of_inequalities( source,
                                                      system_of_equations );
        // shrink this system
        shrink_inequation_system( source, system_of_inequalities );
        // test if the inequation system is feasible
        if ( lexmin( system_of_inequalities, NULL, TempDir ) != NULL )
        {
                // apply the dual method to minimizing problem of this
                // inequality system
                apply_dual_method( source, system_of_inequalities );
                // insert the objective function
                insert_objective_function( source );
                // since PIP computes only the lexicographic minimum and the
                // result of the dual method is a maximizing problem, one has
                // to perform a transformation which yields a minimizing pro-
                // blem with the same solution
                transform_to_minimizing_problem( source );
                // create PIP input files and call PIP
                solve_with_pip( source );
                // read the results calculated by PIP
                call_pip_parser( source );
                // evaluate the PIP quasts to affin functions
                calculate_schedules_from_pip_output( source );
                // print the results
                source->print_schedules();
                // save the results
                source->save_schedules();
        }
        else
                cout << "No one dimensional schedule found!\n";
}

create_prototype_schedules( source );

This function creates the prototypes of all statements inspecting the inequalities describing the indexspace of each statement. The corresponding functions can be found in the file scheduler/proto_s.cc. Since there is a class defining a prototype (defined in scheduler/commonschedal/classdef.h), see also the file scheduler/p_sched.cc, that contains the corresponding member functions.

system_of_equations = create_system_of_equations( source );

This function constructs the equation systems for each statement. Since this construction can be made very easy for uniform dependences between the same statement, this optimization has also been integrated. This is all done in the file scheduler/equation.cc. After this construction is also the point, where another programm than the later used PIP (Parametric Integer Programming) can be inserted, if this programm allows a parametric optimization function (here the prototypes) and equation systems to give the constraints for the variables of the problem (here the Farkas-multipliers). If the last property is not given, i.e. if the constraints have to be given by sets of inequalities, the following step helps:

system_of_inequalities = create_system_of_inequalities( source,
                                                      system_of_equations );

This step forms an inequality system from the given equality system by a kind of gauss jordan algorithm. The corresponding function is also located in scheduler/equation.cc. Now the optimization problems for each statement are described by their prototypes as optimization function and the system_of_inequalities as the constraints for all problems. To use PIP for solving them, forces a translation of each problem in a different form with the same solution, which can be passed through PIP. This in done by applying the duality theorem. This theorem can only be applied, if the given constraints system is feasible. So test this, by calculating the lexicographic minimum of all solutions:

if ( lexmin( system_of_inequalities, NULL, TempDir ) != NULL )

Test if there is a solution by calculating the lexicographic minimum of all solutions. This is done with the function lexmin, which is part of the mathematical library. You can find its implementation in general/pipsolver.cc.

apply_dual_method( source, system_of_inequalities );

If there is a solution we can go on, else there is no one-dimensional schedule. So apply the duality theorem implemented in scheduler/dual_m.cc. The result is a set of inequalities, that describes now a maximizing problem for each statement. This set is stored in the statements in the entry max_ineqs (See the file scheduler/commonschedal/classdef.h for the definition of classes).

insert_objective_function( source );

Since PIP does not support objective functions, this has to be included in the inequations system of each statement by an implicit equality, as described in the master thesis. For the implementation see also scheduler/dual_m.cc.

transform_to_minimizing_problem( source );

The constraints formulate a maximizing problems, but PIP calculates the lexicographic minimum. So transform the problems by rotating the corresponding polyherdas and a translation with an additional parameter. See therefor scheduler/pip.cc.

solve_with_pip( source );

Now call PIP to solve each problem, in scheduler/scanpars.cc.

call_pip_parser( source );

and read the output of PIP, which is a so-called quast. For a description of quasts refer to the files general/lmaths.h and general/quast.cc.

calculate_schedules_from_pip_output( source );

Although the quasts already are a representation for the schedule, we transform them in piecewise affin functions, because this representation would be a little cryptically. See therefor scheduler/calcsched.cc.