Skip to content
Snippets Groups Projects

ILP Generation

Last edited by rschoene

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 components comp
  for-all modes m
    for-all clauses c in m
      (if c subtype? ProvClause
        for-all PEs pe ; prov-clause
          constraints[comp][returntype][eq] += c.value (varname m-deployed-on-pe) "+"
        for-all PEs pe ; req-clause
  	      (if c.comp eq? min-eq
            constraints[comp][returntype][min-eq] += "+" c.value (varname m-deployed-on-pe)
            constraints[comp][returntype][max-eq] += "+" c.value (varname m-deployed-on-pe)))
  constraints += constraints[comp]

New try. Hardware properties:

create "right-hand-side–templates" for each resource-type (e.g. Cubieboard), property and comp
  if comp=max, apply 'maximum inversion'
  example: 0.5 1a-RES + 0.8 1b-RES + 0 1c-RES
  creating template_type,comp,property
for-each Resource pe, Property prop, Comp c and Comparator comparator
   constraints += (eval prop-on-pe) (comp->string comparator) (deploy template_(type-of pe),c,prop pe)
  • (eval prop pe) evalutates the property on the resource
  • (comp->string comparator) gets a string representation of the comparator
  • (deploy template pe) instantiates the template on the resource
  • only add constraint, if template exists, template is not empty and property exists on pe

Software properties:

for-all comp c
  for-all (req-comp-map c) (reqC,impls) ; impls, that require the component reqC
    constraint = (list)
    for-all (impls-of reqC) rci → for-all (mode-of rci) rcm → for-all (res-types) type
      constraint += "+" (eval prop rcm type) (varname rcm-on-type)
    constraint += ">="|"="
    for-all impls i → for-all (mode-of i) m  → for-all pe
      constraint += "+" (eval (req-clause m prop)) (varname m-deployed-on-pe)
    constraints += constraint
  • (eval prop m type) evaluates the property for the Mode m on the ResourceType type
  • (eval cl) evaluates the Clause cl
  • (req-clause m prop) returns the ReqClause in Mode m for the Property prop

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)

Comments

    Please register or sign in to add a comment.