Feautriers Extension to multi-dimensional Placements

• allocator/mainalloc.cc
• allocator/allocat.cc
• allocator/rank_dep.cc
• allocator/proto_p.cc
• allocator/eq_place.cc
• allocator/place_al.cc
• allocator/multialloc.cc
• allocator/p_constr.cc
• allocator/p_place.cc

All of these files use functions and objects, which are defined in the mathematical library and in the fil e scheduler/commonschedal/classdef.h. The evaluation of parameters given to the binary allocator/allocator and the initialization is done in allocator/mainalloc.cc. The main file for the algorithm is allocator/allocat.cc. This file contains after the calculation of the maximum possible placement dimension for a program (routines therefor in allocator/multialloc.cc) the following code:

        // build the prototype placements for each statement
        create_prototype_placements( source );
        // rank the dependences
        int *ordered_dependences = rank_dependences( source );
        // build the placement equations
        Eq_system *placement_equations = create_placement_equations( source,
                                                         ordered_dependences );
        // apply the placement algorithm to these equations
       Solution_package *sol_pack = apply_placement_algorithm( source,
                                         placement_equations, alloc_dim );
        // construct the placements from these coefficients
        Matrix sol_vector = construct_placements_from_coefficients( source,
                                                sol_pack, alloc_dim );
        // count the number of cut edges
        count_cut_dependences( source, placement_equations, sol_pack,
                                sol_vector, ordered_dependences );
        // print the placements
        source->print_placements();
        // save the placements to file
        source->save_placements();

create_prototype_placements

Here the prototypes for the placement of each statement are created. The implementation is in allocator/proto_p.cc. This part uses also objects of type Prototype_placement, whose member functions are in allocator/p_place.cc (class definintion in scheduler/commonschedal/classdef.h).

rank_dependences

To eliminate the "big" communications the dependences are ranked by their communication volume. The result is the ordered list of dependence numbers. See the file allocator/rank_dep.cc for the implementation.

create_placement_equations

After this we construct the placement equations in allocator/eq_place.cc, which yields an equation system.

apply_placement_algorithm

This is the application of the placement algorithm, which performs substitution of placement coefficients as long this ensures the required placement dimension. This is done in allocator/place_al.cc. The result is a solution package consisting of a matrix, that gives by line the additive combination of free coefficients for a not free coefficient. The second part is a boolean array, that stores if a coefficient is free or not.

construct_placements_from_coefficients

The solution package contains all information about the placement coefficients needed to construct the corresponding placement functions. See the file allocator/p_constr.cc.

count_cut_dependences

This step (implemented in allocator/place_al.cc) is only made, to give a measure of the quality of the calculated placement. It tests, how many placement equations are fullfilled by the placements, and outputs their number.