ILP Generation in racr-mquat

Form of the ILP for glpk

• ILP ::= "Minimize" SIMPLE-FORMULA "Subject To" CONSTRAINT+ "Bounds" BOUND* "Generals" VAR* "End"
• SIMPLE-FORMULA ::= [ NAME ":" ] (("+"|"-") [ NUMBER ] VAR)+
• CONSTRAINT ::= SIMPLE-FORMULAR ("<="|">="|"=") NUMBER
• BOUND ::= [ NUMBER "<=" ] VAR [ ("<="|"=") NUMBER ]
• NUMBER ::= ( "0" | "1" | … | "9" )+
• VAR ::= ( "#" | "/" | "(" | ")" | "~" | NAME )+
• NAME ::= ( "a" | … | "z" | "A" | … | "Z" | "_" | "-" | NUMBER )+

Eventually VAR and NAME is equal. At least the characters listed in VAR were found to be correctly parsed.

Generation recipe

• varname returns a suitable name for the applied fact
• objective-value returns the value of the objective function for the applied fact
• Assumption: Names of properties are unique, i.e. if referring both in SW-Comp C1, Resource R2 and Request R to the property 'energy', then they all refer to the same property
• Currently not clear, how properties of SW-Components modelled in Scheme

Objective

for-all implementations i
  for-all (modes-of i) m
    for-all PEs pe
      objective += (objective-value m-deployed-on-pe) (varname m-deployed-on-pe) "+"

Architectural Constraints

Introduce binary variables for "implementation i" chosen, additionally to the "implementation i deployed on pe" variables, greatly reducing the size of architectural constraints.

(1) Important question, where will the required components be declared – Comp, Impl or Mode. Here done at Impl-Level – inconsistent with the AST-rules.

for-all components c
  for-all (impls-of c) i
    constraint_i = "0" "=" "-" (varname i)
    for-all (modes-of i) m
      for-all PEs pe
        constraint_i +=  "+" (varname m-deployed-on-pe)
    for-all (req-comp i) rc									(1)
      constraint_rc = "0" "=" "-" (varname i)
      for-all (impls-of rc) rci
        constraint_rc = "+" (varname rci)
      constraints += constraint_rc
    constraints += constraint_i

And to ensure the selected component gets chosen (maybe even implicitly given?)

for-all top-level components tc:
  constraint_tc = "1" "="
  for-all (impls-of c) i
    constraint_tc += (varname i) "+"
  constraints += constraint_tc

In scheme: to-ilp auf impl gib ein paar zurück, so dass

• (car paar) = liste von '(varname m) +'
• (cadr paar) = liste mit constraints der form '0 = - {(varname i)}* {{+ (varname i-in-m-deployed-on-pe)}*}*'

Resource/Software NFP Negotiation

Problem with Maximum

Nicht so leicht abbildbar, wenn nicht nur nach der 'Direction' der Properties entschieden wird, sondern auch andere Arten von Constraints zugelassen werden, zB

• "impl1: val1 <= response-time <= val2"
• "impl2: response-time >= val3"

Maximum-Constraint überhaupt abbildbar mit "prop <= value * binVar"?

• bei Nicht-Auswahl der Impl ist die binVar = 0, und das Constraint ist effektiv prop <= 0 und gleichzeitig prop = X von der benötigten Komponente
• mögliche Lösung: Wenn Maximum der Property bekannt: Anstelle der tatsächlichen Werte wird (Maximum - Wert) benutzt, und statt "<=" nun ">="
  • prop hat Maximum 100
  • "prop <= 20 * impl1pe2"
  • "prop' >= 80 * impl1pe2" where prop' := 100 - prop

Problem with multiple constraint for same property

If two modes of different Impls (or even different Comps) require a certain property, just building the sum of those two requirements is wrong for the case both modes are chosen to be deployed. There need to be a categorization of properties, i.e. how to merge them, a few examples

• frequency: merge my taking maximum of required (minimum) values → use extra constraint per impl
• free memory: merge by summing up → put into sum as is

cpu1#freq >= 1400 b#comp1#impl1#mode1 + 1500 b#comp1#impl2#mode2

Those constraints should therefore be split up.

cpu1#freq >= 1400 b#comp1#impl1#mode1
cpu1#freq >= 1500 b#comp1#impl2#mode2

Properties unique for resources

Currently properties are assumed unique and will be considered equal, even if used for different resources.

cubie1: 0 <= server-load <= 0.4
cubie2: 0 <= server-load <= 0.6
constraint-1: server-load <= 0.5 b#comp1#impl1#mode1
constraint-2: server-load <= 0.2 b#comp1#impl1#mode2

Those properties should be named in a way, uniquely identifying a resource. Actually, there should be a new binary variable associated with the binary variables of deploying modes. Unfortunatly, this leads to k new constraints, where k is the number of binary variables for deploying modes on this resource.

bound-cubie1: 0 <= server-load-cubie1 <= 0.4
bound-cubie2: 0 <= server-load-cubie2 <= 0.6
constraint-1-cubie1: server-load-cubie1 <= 0.5 b#comp1#impl1#mode1
constraint-2-cubie1: server-load-cubie1 <= 0.2 b#comp1#impl1#mode2
constraint-1-cubie2: server-load-cubie2 <= 0.5 b#comp1#impl1#mode1
constraint-2-cubie2: server-load-cubie2 <= 0.2 b#comp1#impl1#mode2

Impl in Scheme

Init constraints[returntype_min-eq] to returntype ">="
Init constraints[returntype_max-eq] to returntype "<="
Init constraints[returntype-eq] to returntype "="
for-all PEs pe
  for-all modes m
    for-all clauses c in m
      (if c subtype? ProvClause
          constraints[returntype-eq] += c.value (varname m-deployed-on-pe) "+"
          (if c.comp eq? min-eq
              constraints[returntype_min-eq] += c.value (varname m-deployed-on-pe) "+"
              constraints[returntype_max-eq] += c.value (varname m-deployed-on-pe) "+"))

User request

for-all request-constraints-clause c
  constraints += (varname c.returntype) ("<="|">="|… according to c.comp) c.value

Bounds

for-all PEs pe
  for-all prov-clauses c in pe
    bounds += "0 <=" (varname c.returntype) "<=" c.value

Restrictions

General (integer)

None

Boolean

for-all implementations i
  binaries += (varname i)
  for-all (mode-of i) m
    binaries += (varname m-deployed-on-pe)