Changes
Page history
More thoughts on constraints and their generation.
authored
Apr 30, 2015
by
René Schöne
Hide whitespace changes
Inline
Side-by-side
ILP-Generation.md
View page @
897c26f5
# ILP Generation in racr-mquat
## Form of the ILP for glpk
# Form of the ILP for glpk
-
ILP ::= "Minimize" SIMPLE-FORMULA "Subject To" CONSTRAINT+ "Bounds" BOUND
* "Generals" VAR*
"End"
-
SIMPLE-FORMULA ::=
\[
NAME ":"
\]
(("+"|"-")
\[
NUMBER
\]
VAR)+
...
...
@@ -12,7 +10,7 @@
Eventually VAR and NAME is equal. At least the characters listed in VAR were found to be correctly parsed.
#
# Generation recipe
# Generation recipe
-
`varname`
returns a suitable name for the applied fact
-
`objective-value`
returns the value of the objective function for the applied fact
...
...
@@ -20,7 +18,7 @@ Eventually VAR and NAME is equal. At least the characters listed in VAR were fou
property 'energy', then they all refer to the same property
-
Currently not clear, how properties of SW-Components modelled in Scheme
##
#
Objective
## Objective
```
for-all implementations i
...
...
@@ -29,7 +27,7 @@ for-all implementations i
objective += (objective-value m-deployed-on-pe) (varname m-deployed-on-pe) "+"
```
##
#
Architectural Constraints
## 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.
...
...
@@ -67,9 +65,9 @@ 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
## Resource/Software NFP Negotiation
###
#
Problem with Maximum
### 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
...
...
@@ -87,7 +85,7 @@ Maximum-Constraint überhaupt abbildbar mit "prop <= value * binVar"?
-
"prop <= 20
*
impl1pe2"
-
"prop' >= 80
*
impl1pe2" where prop' := 100 - prop
###
#
Problem with multiple constraint for same property
### 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
...
...
@@ -107,7 +105,7 @@ cpu1#freq >= 1400 b#comp1#impl1#mode1
cpu1#freq >= 1500 b#comp1#impl2#mode2
```
###
#
Properties unique for resources
### Properties unique for resources
Currently properties are assumed unique and will be considered equal, even if used for
different resources.
...
...
@@ -133,30 +131,68 @@ 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
### 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
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
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) "+"))
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)
```
### User request
-
(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
## Bounds
```
for-all PEs pe
...
...
@@ -164,13 +200,13 @@ for-all PEs pe
bounds += "0 <=" (varname c.returntype) "<=" c.value
```
##
#
Restrictions
## Restrictions
###
#
General (integer)
### General (integer)
*None*
###
#
Boolean
### Boolean
```
for-all implementations i
...
...
...
...