Changes
Page history
More thoughts on constraints and their generation.
authored
Apr 30, 2015
by
René Schöne
Show 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"
-
ILP ::= "Minimize" SIMPLE-FORMULA "Subject To" CONSTRAINT+ "Bounds" BOUND
* "Generals" VAR*
"End"
-
SIMPLE-FORMULA ::=
\[
NAME ":"
\]
(("+"|"-")
\[
NUMBER
\]
VAR)+
-
SIMPLE-FORMULA ::=
\[
NAME ":"
\]
(("+"|"-")
\[
NUMBER
\]
VAR)+
...
@@ -12,7 +10,7 @@
...
@@ -12,7 +10,7 @@
Eventually VAR and NAME is equal. At least the characters listed in VAR were found to be correctly parsed.
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
-
`varname`
returns a suitable name for the applied fact
-
`objective-value`
returns the value of the objective function 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
...
@@ -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
property 'energy', then they all refer to the same property
-
Currently not clear, how properties of SW-Components modelled in Scheme
-
Currently not clear, how properties of SW-Components modelled in Scheme
##
#
Objective
## Objective
```
```
for-all implementations i
for-all implementations i
...
@@ -29,7 +27,7 @@ for-all implementations i
...
@@ -29,7 +27,7 @@ for-all implementations i
objective += (objective-value m-deployed-on-pe) (varname m-deployed-on-pe) "+"
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
Introduce binary variables for "implementation i" chosen, additionally to the
"implementation i deployed on pe" variables, greatly reducing the size of architectural constraints.
"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
...
@@ -67,9 +65,9 @@ In scheme: to-ilp auf impl gib ein paar zurück, so dass
-
(car paar) = liste von '(varname m) +'
-
(car paar) = liste von '(varname m) +'
-
(cadr paar) = liste mit constraints der form '0 = - {(varname i)}
\*
{{+ (varname i-in-m-deployed-on-pe)}
\*
}
\*
'
-
(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
Nicht so leicht abbildbar, wenn nicht nur nach der 'Direction' der Properties
entschieden wird, sondern auch andere Arten von Constraints zugelassen werden, zB
entschieden wird, sondern auch andere Arten von Constraints zugelassen werden, zB
...
@@ -87,7 +85,7 @@ Maximum-Constraint überhaupt abbildbar mit "prop <= value * binVar"?
...
@@ -87,7 +85,7 @@ Maximum-Constraint überhaupt abbildbar mit "prop <= value * binVar"?
-
"prop <= 20
*
impl1pe2"
-
"prop <= 20
*
impl1pe2"
-
"prop' >= 80
*
impl1pe2" where prop' := 100 - prop
-
"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
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
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
...
@@ -107,7 +105,7 @@ cpu1#freq >= 1400 b#comp1#impl1#mode1
cpu1#freq >= 1500 b#comp1#impl2#mode2
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
Currently properties are assumed unique and will be considered equal, even if used for
different resources.
different resources.
...
@@ -133,30 +131,68 @@ constraint-1-cubie2: server-load-cubie2 <= 0.5 b#comp1#impl1#mode1
...
@@ -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
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][min-eq] to returntype ">="
Init constraints[returntype_max-eq] to returntype "<="
Init constraints[*][returntype][max-eq] to returntype "<="
Init constraints[returntype-eq] to returntype "="
Init constraints[*][returntype][eq] to returntype "="
for-all PEs pe
for-all components comp
for-all modes m
for-all modes m
for-all clauses c in m
for-all clauses c in m
(if c subtype? ProvClause
(if c subtype? ProvClause
constraints[returntype-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
(if c.comp eq? min-eq
constraints[returntype_min-eq] += c.value (varname m-deployed-on-pe) "+"
constraints[comp][returntype][min-eq] += "+" c.value (varname m-deployed-on-pe)
constraints[returntype_max-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
for-all request-constraints-clause c
constraints += (varname c.returntype) ("<="|">="|… according to c.comp) c.value
constraints += (varname c.returntype) ("<="|">="|… according to c.comp) c.value
```
```
##
#
Bounds
## Bounds
```
```
for-all PEs pe
for-all PEs pe
...
@@ -164,13 +200,13 @@ for-all PEs pe
...
@@ -164,13 +200,13 @@ for-all PEs pe
bounds += "0 <=" (varname c.returntype) "<=" c.value
bounds += "0 <=" (varname c.returntype) "<=" c.value
```
```
##
#
Restrictions
## Restrictions
###
#
General (integer)
### General (integer)
*None*
*None*
###
#
Boolean
### Boolean
```
```
for-all implementations i
for-all implementations i
...
...
...
...