|
|
# 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
|
... | ... | |