next up previous contents Next: How to install ALIAS Up: ALIAS-C++ Previous: Parser, Generic Solver and

  • La page de J-P. Merlet
  • J-P. Merlet home page
  • La page Présentation de HEPHAISTOS
  • HEPHAISTOS home page
  • La page "Présentation" de l'INRIA
  • INRIA home page

    Subsections



    Parallel processing


    Parallelizing ALIAS programs

    Interval analysis has a structure that is appropriate for a distributed implementation. Indeed the principle of the algorithm is to process a list of boxes, the processing for a box being independent of the other boxes in the list (except that it may have be stopped). A classical distributed implementation will rely on the master/slave paradigm. A master computer will manage the list of boxes and monitor the activity of the slaves. As soon as a slave is free the master will send a box to this slave. The slave, which has its own list of boxes, will perform a few iteration of the solving algorithm and then send back to the master the remaining boxes to be processed in its list and eventually the solutions it has found. After receiving a signal from the slave the master will receive the boxes from the slave and append them to its list of boxes. This slave being now free the master will send him another box in its list.

    Hence most of the calculation will be performed by the slaves. It may happen however that at a given time all the slaves are busy processing boxes. The master itself may then start a few iteration of the solving algorithm on the current box of its list while carefully monitoring the activity of the slaves.

    The structure of the interval analysis algorithms is very convenient for using the above paradigm:

    The gain in computation time will in general be lower than the number of used slaves. This is due to

    Note however that in some cases the gain may be larger than the number of slaves. This is, for example, the case of the optimization algorithms as the independence of box processing is no more true: the discovery of a good optimum by a slave may leads to stop the processing of the other slaves.

    In any case a key point of a distributed implementation is to be able to


    Stopping a procedure and miscellaneous utilities

    There are different methods to stop the current bisection process:

    1. the number of boxes still to be processed is greater than a given threshold $N$: this is obtained by setting the global variable ALIAS_Parallel_Max_Bisection to $N-1$. . A safety procedure may be used as the number of bisection may be large before getting the right number of boxes (for example when using the single bisection mode): the maximal number of bisection may be indicated by setting the global variable ALIAS_Parallel_Max_Split and the procedure will return if this number is reached and the number of unprocessed boxes is lower than ALIAS_Parallel_Max_Bisection (otherwise the process will continue until this number is reached).
    2. the number of performed bisection is greater than a given threshold $M$: this is obtained by setting the global variable ALIAS_Parallel_Max_Bisection to $-M$
    3. the number of performed bisection is greater than a given threshold $M$ and the number of boxes still to be processed is lower than a given threshold $N$: this is obtained by setting the global variable ALIAS_Parallel_Max_Bisection to $-M$ and the global variable ALIAS_Parallel_Max_Box to $N$ . A safety mechanism is enforced in that case to avoid that only one of the slave computer will perform all the computation: if $M \times S$ bisections have been done the procedure will return the error code -1. The value of $S$ is given by the global variable ALIAS_Safety_Factor with a default value of 2
    4. if we are using the reverse storage mode we may indicate that the number of performed bisection must be greater than a given threshold $M$ and the number of boxes still to be processed is lower than a given threshold $N$: this is obtained by setting the global variable ALIAS_Parallel_Max_Bisection to $N$ and the global variable ALIAS_Parallel_Max_Reverse to $M$
    5. the slave computation time has exceeded a fixed amount of time, which probably indicate that it will be preferable to distribute the treatment of the processed box among different slaves. This could be done using the double ALIAS_TimeOut which indicates the maximum amount of time (in minutes) during which a slave may run (this amount will be respected only approximatively).
    The number of the box still to be processed may be determined from the integer array
    ALIAS_Parallel_Box. Let ALIAS_Parallel_Box[0]=$i$ and ALIAS_Parallel_Box[1]=$j$. If $i>j$, then no boxes remains to be processed otherwise the box numbers to be processed start at $i$ and finish at $j$ (hence there are $j-i+1$ boxes to be processed). The boxes are stored in the interval matrix array Box_Solve_General_Interval. If the system has $n$ unknowns, the box for each unknown in the box numbered $i$ are given by
    Box_Solve_General_Interval(i,1) $\ldots$ Box_Solve_General_Interval(i,n). For procedures involving the gradient of the functions you may retrieve the simplified gradient in the integer matrix
    Gradient_Solve_General_Interval while for the procedures involving the gradient and hessian of the functions the gradient may be retrieved in the interval matrix Gradient_Solve_JH_Interval. Note that this storage may not be available if you have set the flag ALIAS_Store_Gradient to 0 (its default value is 1).

    The variable ALIAS_Parallel_Slave should be set to 0 for a sequential use of the algorithm, to 1 if the algorithm is run by a master computer and to 2 if the algorithm is run by a slave computer.

    Using this stop criteria we may implement a parallel version of the ALIAS procedures, see the ALIAS-Maple manual.

    If the master/slave scheme is used the master may perform some steps of a solving algorithm but for efficiency purpose it is necessary that the master monitor the slaves to determine if one has completed its calculation. This is the role of the ALIAS_Slave_Returned procedure that stops the processing done by the master as soon as a slave is free. Such a procedure may be found in the lib_Slave.a library: it is based on the pvm message passing mechanism (see the ALIAS-Maple manual). For the non parallel processing the equivalent procedure may be found in the lib_No_Slave.a library. Hence according to a sequential or a parallel use one of this library has to be linked to the main program.

    For solving procedures involving the use of the gradient we may use two schemes:

    In the first case the transmission time of the gradient may be relatively large and the master may spend a large amount of time for this transmission while other slaves are currently free. Hence it may be interesting to have a flag which indicate which mode is used: this is the role of the integer ALIAS_Transmit_Gradient.

    The ALIAS-Maple library offers a parallel implementation of some solving algorithm. Communication between the slaves and the master is ensured by the message passing mechanism pvm. See the ALIAS-Maple manual for a detailed account of the distributed implementation.

    This implementation uses some specific C++ procedures.

     
    void ALIAS_Prepare_Buffer(int DimVar,INTERVAL_VECTOR &X,char *buffer)
    
    which put in the string buffer the lower and upper bounds of the DimVar ranges contained in the interval vector X.

    The master and slaves exchange strings and in the parallel implementation offered currently by ALIAS all data are contained in these strings (this may change in the near future as PVM offers other possibility). Each numerical data is introduced by few control character. The following control character are used:

    Using this convention we may used the following procedure to decode the string sent by the master or the slave:

     
    int ALIAS_Read_Buffer(char *mess,
              int Nb_Var, int Nb_Eq,INTERVAL_MATRIX &Box,int *Nb_Total,
              INTERVAL_MATRIX &Sol,int *Nb_Sol,int *Nb_Split,
              INTEGER_VECTOR &IPar,int *Nb_Ipar,
              VECTOR &FPar,int *Nb_Fpar,INTERVAL_MATRIX &BoxPar,
              int *Nb_BoxPar)
    
    where mess is the string and

    If is necessary we may transmit also the simplified jacobian associated to the boxes using the procedure:

     
    int ALIAS_Read_Buffer_Gradient(char *mess,
              int Nb_Var, int Nb_Eq,INTERVAL_MATRIX &Box,
              INTEGER_MATRIX &GBox,int *Nb_Total,
              INTERVAL_MATRIX &Sol,int *Nb_Sol,int *Nb_Split,
              INTEGER_VECTOR &IPar,int *Nb_Ipar,
              VECTOR &FPar,int *Nb_Fpar,INTERVAL_MATRIX &BoxPar,
              int *Nb_BoxPar)
    

    Here the boxes followed by the simplified jacobian GBox are introduced by the control character BG.

    If the true jacobian has to be transmitted we use:

     
    int ALIAS_Read_Buffer_Hessian(char *mess,
              int Nb_Var, int Nb_Eq,INTERVAL_MATRIX &Box,
              INTERVAL_MATRIX &GBox,int *Nb_Total,
              INTERVAL_MATRIX &Sol,INTEGER_VECTOR &Is_Kanto,
              int *Nb_Sol,int *Nb_Split,
              INTEGER_VECTOR &IPar,int *Nb_Ipar,
              VECTOR &FPar,int *Nb_Fpar,INTERVAL_MATRIX &BoxPar,
              int *Nb_BoxPar)
    
    Here the boxes followed by the jacobian GBox are introduced by the control character BG. Furthermore each solution is followed by an integer that indicates the type of the solution and can be accessed by Is_Kanto.


    next up previous contents Next: How to install ALIAS Up: ALIAS-C++ Previous: Parser, Generic Solver and
  • J-P. Merlet home page
  • La page Présentation de HEPHAISTOS
  • HEPHAISTOS home page
  • La page "Présentation" de l'INRIA
  • INRIA home page

    jean-pierre merlet
    2018-07-25