[See also IZ615]

                     Complex Attribute Specification
                        
                            Stephan Grell
                          September 16, 2003


0. Introduction:
----------------

   The purpose of this document is to describe how the attributes in the
   new SGE V6.0 system. The behavior to the previous one has changed in some
   aspects. It also describes how the attributes can be used and which work
   packages are still pending. Therefor this document is under construction
   itself and will be changed while the work packages are implemented.

   Acknowledgements

   I gratefully acknowledge useful conversations and input in other 
   forms with Andre Alefeld, Ernst Bablick, Andreas Dorr, Fritz Ferstl, 
   Andreas Haas, Christian Reissmann, and Andy Schwierskott.

1. Attributes:
--------------

   - We have the possibility to specify attributes on global level, host level, 
     and queue level.
   - The values for an attribute can be fixed or changeable. 
   - The values can be a load value, custom defined or a resource limit. 
   - Resource limits exist only on queue level
   - Load values only on global or host level
   - The type of an attribute can be: string, host, cstring, int,double, 
     boolean, memory, and time. 
   - A consumable can have a default value, thus the user can, but does not 
     have to specify the attribute. 
   - An attribute can be requestable, has to be requested, or cannot be 
     requested at all.
   - An attribute can be build-in or a user defined.
   - Most load values and all of the resource limits are build in. 
   - A user can define consumables, load values, or fixed values.
   - An attribute has one of many relational operations:  ==, !=, >=, =<, >,<
   
   - An attribute can be a per job attribute or per slot attribute:
      - all load values and consumables are per job attributes except string, 
        cstring, host  values. They are per slot attributes. 
      - all resource limits and user defined fixed values are per slot 
        attributes.
      - An attribute can only be a job attribute or a slot attribute, but not 
        both.

   The user can change every aspect of an attribute at any time. The current 
   definition of an attribute looks like:
   - name
   - Short cut
   - Type
   - Consumable
   - Relational operator
   - Requestable
   - default value 

   Using per slot attributes:
   --------------------------

      All fixed values in the system are per slot attributes. This means, that
      a parallel job existing of 4 parallel tasks (needing 4 slots to run) 
      requires the attribute for each task. 

      Example E1:
         one job j1 requests t01 = 10 with 4 slots
         queue q1 has 5 slots and t01 is set to <=20
         j1 does fit on q1 since it has enough slots and t01 allows to run 
         jobs with t01 requests between 0 and 20.
         The configuration of q1 after j1 has started is slots = 1 and 
         t01 <= 20.

   Using per job attributes:
   -------------------------

      All changeable values in the system are per job attributes like the 
      "slots" attribute in E1. This means, that a parallel job requests a 
      resource n times (n is the number of slots it will use).

      Example E2:
         one job j2 requests t02 = 20 with 4 slots
         queue q2 offers 5 slots with t02 <= 40
         queue q3 offers 1 slot with t02 <= 40
         queue q4 offers 3 slots with t02 <= 40
      The system will start two instances of the job on q2, one on q3 and 
      one on q4
      The configuration of the queues afterwards looks like:
         q2 offers 3 slots with t02 <= 0 (q2.t02 - 2*j2.t02)
         q1 offers 0 slots with t02 <= 20 (q2.t02 - 1*j2.t02)
         q3 offers 2 slots with t02 <= 20(q2.t02 - 1*j2.t02)

      This example shows how consumables are handled. With load values is 
      will take some time, before they are updated, depending on the 
      load_value_report interval. 

      It is possible to override attributes on a lower level or on the same 
      level.  More about it later.

      The fact, that all consumables are per job attributes posses a problem, 
      when one wants to do licence managing with parallel jobs. Therefor it 
      would be nice to have it configurable if a consumable is a per job 
      attribute or per slot attribute.

      Wor kpackage:
         => Decide, what is the right way of doing it
         => Adding a flag which can be set by a user, if an attribute is a per 
            slot or perjob attribute.



2. Restrictions:
----------------

   Not all of the above described combinations make sense. Till now, there are 
   no restrictions on how an attribute is defined, but the code working on them 
   has the restrictions already build in. Therefore it will aid the user in 
   configuring SGE when the system allows only valid specifications:

   name 	     : has to be unique
   Short cu	  : has to be unique
   Type	     : every type from the list (string, host, cstring, int, double,
                                          boolean, memory, time, restring)
   Consumable : can only be defined for: int, double, memory, time
                If a consumable is not requestable, it has to have a default 
                value.
                If a consumable is forced, it must not have a default value.

   Relational operator:
      - for consumables:              only <=
      - for non consumables:
         - string, host, cstring:     only ==, !=
         - boolean:	                 only ==
         - int, double, memory, time: ==, !=, <=, <, =>, >

   Requestable	   : for all attribute
   default value 	: only for consumables

   The qmon interface should only provied valid options. The choice of the
   type limites the choice of operators and if it can be a consumable or not.
   Haveing a consumable also limites the relational operators to one. This
   makes it easier and more convieniend for the user to add new attributes.
   Default values can only be added, when it makes sense (for consumables).

Build in values:
----------------

   Besides the overall attribute restrictions, we have one additional one for
   the system build-in attributes. One can not change the type of a build in
   attribute. The system relies on the type and will not function anymore, if
   one changes the type. A build-in value can also not be deleted.

   The only exception are the strings. A string can be changed into a cstring
   or restring and back.

3. Overriding attributes:
-------------------------

   In general an attribute can be overridden on a lower level
   - global by hosts and queues
   - hosts by queues
   and load values or resource limits on the same level. Overriding a per slot 
   attribute with a per slot attribute and a per job attribute with an per slot 
   attribute is no problem. Based on the specification does a per job attribute 
   never be override with a per slot attribute. But a per job attribute can be 
   overridden with a per slot attribute. In this case the per slot attribute 
   changes into a  per job attribute. This happens, when a load value is 
   overridden with a fixed value. 

   We have one limitation for overriding attributes based on its relational 
   operator:
   - !=, == operators can only be overridden on the same level, but not on a 
   lower level
   - >=, >, <=, < operators can only be overridden, when the new value is more 
   restrictive than the old one.

   Examples:
   1. We have a load value arch on host level. One can override it in the host 
      definition with another value, but not in a queue.
   2. We have a load value mem_free with a relop <= on host level. One can 
      override it on host or queue level with a value, which is smaller than 
      the reported one. 
      mem_free: custom / load report / result:
               1 GB    /    4 GB     /    1 GB
               1 GB    /    0.9 GB   /    0.9 GB

   The reason why we have the override limitation is buried in the algorithm 
   how we match the job requests with available resources. The algorithm is 
   strict hierarchical, which means, if it finds a attribute on one level, 
   which does not match, the other levels are not further evaluated. It starts 
   with the global host and ends with a queue. When a  attribute is missing on 
   one level it will go one with the next levels. But an existing attribute, 
   which does not match results in an abort.  


4. Internal representation:
---------------------------

   One could say, that we have three different lists. which are used to match 
   the requests with the existing resources. These are:
   - the job request list (hart and soft)
   - the attribute configuration list
   - and the elements (of a list), which are generated for matching and output 
   purposes. It is generated from the first two lists.  All list entries share 
   the same CULL list structure, which is never fully used.
 
                        request list   /  configuration list    /    match list
   Name                   X            /            X           /         X
   Shortcut              ---           /            X           /        ---
   type                  ---           /            X           /         X
   val (as doulbe)       ---           /           ---          /         X
   val (as string)        X            /           ---          /         X
   relop                 ---           /            X           /         X  
   consumable            ---           /            X           /         X
   default               ---           /            X           /        ---
   dominant              ---           /           ---          /         X
   pj val (as double)    ---           /           ---          /         X
   pj val (as string)    ---           /           ---          /         X
   pj dominant           ---           /           ---          /         X
   requestable           ---           /           ---          /         X
   tagged                 X            /           ---          /        ---

   Splitting this one CULL definition into multiple ones will reduce the amount
   of used memory, the time for copying the lists ,and enhance the readability 
   within the source code. 
   Though the new structures will look like:

   RL_type:
   - RL_name            - name or shortcut
   - RL_stringval       - requested value 
   - RL_tagged          - matched a existing resource 
   (saving 11 elements)

   CL_type:
   - CE_name            - name
   - CE_shortcut        - short name
   - CE_type            - type (int, string, ....)
   - CE_relop           - relational operator (==, !=, ...)
   - CE_consumable      - boolean flag
   - CE_default         - default value, only consumables
   (saving 8 elements)

   CM_type:   
   - CE_name            - requested name (name or shortcut)
   - CE_valtype         - type
   - CE_doubleval       - fixed value 
   - CE_stringval       - fixed value as string
   - CE_relop           - relational operator 
   - CE_consumable      - is consumable?
   - CE_dominant        - from which level , of which type (fixed, ...)
   - CE_pj_stringval    - changeable value 
   - CE_pj_doubleval    - changeable value as string
   - CE_pj_dominant     - from which level , of which type (load, ...)
   - CE_requestable     - is it requestable
   (saving 3 elements)

   Work package:
      => Phase 1: changing the request matching structure (CM_type)
      => Phase 2: changing the job request structure (CL_type)
      => Phase 3: changing the attribute configuration structure (RL_type)


5. Scheduler attribute matching:
--------------------------------

   As written before, the matching of attribute requests by a job a matched in
   in a strict hierarchy. When a match fails, the underlying levels are not
   evaluated any further. Right now, this is done for every job, even so the
   jobs might be in the same job category, which means, that they have the same
   requests. 
   To speed up this process, one can store the information, which queue cannot 
   run which job category. When this is known, the jobs are only tested against 
   the queues, which were capable of running the jobs from the previous 
   dispatch cycle. List of queues to test will get shorter and shorter, while 
   jobs are dispatched.

   The same is true for soft requests. Once all queues are validated and the 
   number of mismatches are computed, they are the same for all other jobs in 
   the same job category.  This saves a lot of matching time with the soft 
   requests.


   String matching:
   ----------------
   
      The string matching has some specialties. A string can have one of three 
      different types:
         - plain string
         - caseless string
         - regular expression string

      1. Plain strings (STRING):
         Matches only, when the requested and the provided string are exactly 
         the same.

      2. Caseless strings (CSTRING):
         The upper- and lowercase of the characters in a string is ignored.

      3. Regular expression string (RESTRING):      
         The user can use a regular expression to ask for a resource. The 
         syntax follows the following rules:
         - "*"   : matches any character and any number of chars (between 0 
                   and inv).
         - "?"   : matches any character. It cannot be no character
         - "."   : is the character ".". It has no other meaning
         - "\"   : escape character. "\\" = "\", "\*" = "*", "\?" = "?"
         - "[xx]": specifies an array or a range of allowed characters
         - "|"   : logical "or". Can only be used on the highest level and 
                   cannot be escaped.
     
         Not supported:
         - "x+"      : to specify, that the character "x" has to appear at least 
                       once
         - "[xx|yy]" : to specify xx or yy
     
         Examples:
            -l arch="linux|solaris"    : results in "arch=linux" OR 
                                         "arch=solaris"
            -l arch="[linux|solaris]"  : results in "arch=[linux" OR 
                                         "arch=solaris]"

   Result caching:
   ---------------

   When ever resource matching is done with jobs, which have pre-calculated
   job categories, the matching results will be stored in the job categories. 
   This can be done because all jobs in the same category have the same requests,
   the same user, the same department,...

   What is cached depends on the job kind (if it is a job with only hard requests,
   or if its one with hard, soft, pe and other requests)

   Jobs with only hard requests:
      All queues and hosts on which the job cannot run are stored in the job
      category. This information is used to limit the possible target queues.

   other jobs:
      All unfitting queues and the soft violation results are stored in the job 
      category. This means, that the soft violations are only computed once and
      reused for all other jobs in the same category. The queue information
      limits the possible target queues.