| 1 | package de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.impl; |
| 2 | |
| 3 | import java.awt.image.ReplicateScaleFilter; |
| 4 | import java.util.ArrayList; |
| 5 | import java.util.Collection; |
| 6 | import java.util.LinkedList; |
| 7 | import java.util.List; |
| 8 | import java.util.Random; |
| 9 | |
| 10 | import org.eclipse.emf.ecore.EObject; |
| 11 | import org.opt4j.core.problem.Genotype; |
| 12 | import org.opt4j.operator.copy.Copy; |
| 13 | |
| 14 | import de.uka.ipd.sdq.dsexplore.helper.EMFHelper; |
| 15 | import de.uka.ipd.sdq.dsexplore.launch.DSEWorkflowConfiguration; |
| 16 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.AbstractTactic; |
| 17 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.TacticsResultCandidate; |
| 18 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.UtilisationResultCacheAndHelper; |
| 19 | import de.uka.ipd.sdq.dsexplore.opt4j.representation.DSEIndividual; |
| 20 | import de.uka.ipd.sdq.dsexplore.opt4j.representation.DSEIndividualBuilder; |
| 21 | import de.uka.ipd.sdq.dsexplore.qml.handling.QMLConstantsContainer; |
| 22 | import de.uka.ipd.sdq.pcm.designdecision.AllocationDegree; |
| 23 | import de.uka.ipd.sdq.pcm.designdecision.Choice; |
| 24 | import de.uka.ipd.sdq.pcm.designdecision.ClassChoice; |
| 25 | import de.uka.ipd.sdq.pcm.designdecision.ClassDegree; |
| 26 | import de.uka.ipd.sdq.pcm.designdecision.DiscreteRangeChoice; |
| 27 | import de.uka.ipd.sdq.pcm.designdecision.ResourceContainerReplicationDegree; |
| 28 | import de.uka.ipd.sdq.pcm.resourceenvironment.ProcessingResourceSpecification; |
| 29 | import de.uka.ipd.sdq.pcm.resourceenvironment.ResourceContainer; |
| 30 | import de.uka.ipd.sdq.pcm.resultdecorator.resourceenvironmentdecorator.ProcessingResourceSpecificationResult; |
| 31 | import de.uka.ipd.sdq.pcm.resultdecorator.resourceenvironmentdecorator.UtilisationResult; |
| 32 | import de.uka.ipd.sdq.pcm.resultdecorator.resourceenvironmentdecorator.impl.ProcessingResourceSpecificationResultImpl; |
| 33 | |
| 34 | /** |
| 35 | * Implements a server expansion heuristic. This heuristic finds a |
| 36 | * highly utilised resource container, creates a new resource container and reallocates |
| 37 | * components to this new resource container |
| 38 | * @author martens, Tom Beyer |
| 39 | */ |
| 40 | public class ServerExpansionImpl extends AbstractTactic { |
| 41 | /** |
| 42 | * Maximum number of components reallocated from selected resource container |
| 43 | * to a new resource container |
| 44 | */ |
| 45 | private int maxNumberOfReplacements; |
| 46 | /** |
| 47 | * If utilisation is larger than this double it will be considered |
| 48 | * a high utilisation |
| 49 | */ |
| 50 | private double thresholdHighUtilisation; |
| 51 | |
| 52 | private Random generator = new Random(); |
| 53 | |
| 54 | |
| 55 | private UtilisationResultCacheAndHelper resultInterpretationHelper = new UtilisationResultCacheAndHelper(); |
| 56 | |
| 57 | /** |
| 58 | * @param copy Used to copy genotype |
| 59 | * @param individualBuilder Used to build individual |
| 60 | */ |
| 61 | public ServerExpansionImpl(Copy<Genotype> copy, |
| 62 | DSEIndividualBuilder individualBuilder, DSEWorkflowConfiguration configuration) { |
| 63 | super(copy, individualBuilder, configuration, |
| 64 | new String[] { |
| 65 | QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_RESPONSETIME_DEFINITION_PATH, |
| 66 | QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_THROUGHPUT_DEFINITION_PATH, |
| 67 | QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_MAX_UTIL_DEFINITION_PATH}); |
| 68 | // set config |
| 69 | setHeuristicWeight(configuration.getServerExpansionWeight()); |
| 70 | maxNumberOfReplacements = configuration.getServerExpansionMaxNumberOfReplacements(); |
| 71 | thresholdHighUtilisation = configuration.getServerExpansionThresholdHighUtilisation(); |
| 72 | } |
| 73 | |
| 74 | /** |
| 75 | * Check whether there is a resource container that has a |
| 76 | * utilisation >= THRESHOLD_HIGH_UTILISATION and is not null |
| 77 | * @param individual |
| 78 | * @return |
| 79 | */ |
| 80 | private boolean doesMatchHighUtilisation(DSEIndividual individual) { |
| 81 | ProcessingResourceSpecificationResult maxUtilisationResult = this.resultInterpretationHelper |
| 82 | .getMaxProcUtilisationResult(individual); |
| 83 | return maxUtilisationResult != null && |
| 84 | maxUtilisationResult.getResourceUtilisation() >= thresholdHighUtilisation; |
| 85 | } |
| 86 | |
| 87 | /** |
| 88 | * Check whether there is a resource container that has a |
| 89 | * utilisation >= THRESHOLD_HIGH_UTILISATION and there is a least one |
| 90 | * unused resource container (unused means no allocated components) |
| 91 | * @param individual |
| 92 | * @return |
| 93 | */ |
| 94 | public boolean doesMatchPrecondition(DSEIndividual individual) { |
| 95 | return doesMatchHighUtilisation(individual) && !resultInterpretationHelper.getUnusedAvailableResourceContainers(individual).isEmpty(); |
| 96 | } |
| 97 | |
| 98 | /** |
| 99 | * Generates collection of candidates by applying the server consolidation heuristic |
| 100 | * @param individual Individual which the heuristic should be applied to |
| 101 | */ |
| 102 | public List<TacticsResultCandidate> getHeuristicCandidates(DSEIndividual individual, UtilisationResultCacheAndHelper resultsHelper) { |
| 103 | this.resultInterpretationHelper = resultsHelper; |
| 104 | |
| 105 | List<TacticsResultCandidate> candidates = new ArrayList<TacticsResultCandidate>(); |
| 106 | if (doesMatchPrecondition(individual)) { |
| 107 | /* |
| 108 | * 1. Find max utilised resource |
| 109 | * 2. copy genotype |
| 110 | * 3. If increasing of the server multiplicity is allowed: |
| 111 | * - increase server multiplicity |
| 112 | * else classic expansion |
| 113 | * - Get a new (unused) target resource container |
| 114 | * - Reallocate components to target resource container |
| 115 | */ |
| 116 | // 1. Find max utilised resource |
| 117 | ProcessingResourceSpecificationResult maxUtilisationResult = this.resultInterpretationHelper.getMaxProcUtilisationResult(individual); |
| 118 | // 2. copy genotype |
| 119 | ProcessingResourceSpecification maxProcessingResourceSpec = ((ProcessingResourceSpecificationResultImpl) maxUtilisationResult) |
| 120 | .getProcessingResourceSpecification_ProcessingResourceSpecificationResult(); |
| 121 | ResourceContainer resourceContainer = ((ResourceContainer) maxProcessingResourceSpec.eContainer()); |
| 122 | |
| 123 | // server multiplicity |
| 124 | createServerMultiplicityExpansionCandidates(individual, candidates, |
| 125 | maxUtilisationResult, resourceContainer); |
| 126 | |
| 127 | // classic expansion |
| 128 | createClassicServerExpansionCandidates(individual, candidates, |
| 129 | maxUtilisationResult, resourceContainer); |
| 130 | |
| 131 | |
| 132 | } |
| 133 | return candidates; |
| 134 | } |
| 135 | |
| 136 | private void createServerMultiplicityExpansionCandidates( |
| 137 | DSEIndividual individual, List<TacticsResultCandidate> candidates, |
| 138 | ProcessingResourceSpecificationResult maxUtilisationResult, |
| 139 | ResourceContainer resourceContainer) { |
| 140 | |
| 141 | TacticsResultCandidate candidate = individualBuilder.buildCandidate(copy.copy(individual.getGenotype()), individual); |
| 142 | |
| 143 | |
| 144 | // check whether changing the multiplicity is allowed |
| 145 | for (Choice choice : candidate.getGenotype()){ |
| 146 | if (choice instanceof DiscreteRangeChoice && choice.getDegreeOfFreedomInstance() instanceof ResourceContainerReplicationDegree){ |
| 147 | ResourceContainerReplicationDegree replDegree = (ResourceContainerReplicationDegree)choice.getDegreeOfFreedomInstance(); |
| 148 | if (EMFHelper.checkIdentity(replDegree.getPrimaryChanged(), resourceContainer)){ |
| 149 | // replChoice is the choice of the server multiplicity for this resourceContainer |
| 150 | |
| 151 | DiscreteRangeChoice discreteChoice = (DiscreteRangeChoice)choice; |
| 152 | // check whether more replicas are allowed |
| 153 | if (discreteChoice.getChosenValue() < (replDegree.isUpperBoundIncluded() ? replDegree.getTo() : replDegree.getTo() - 1)){ |
| 154 | |
| 155 | discreteChoice.setChosenValue(discreteChoice.getChosenValue() + 1); |
| 156 | |
| 157 | candidate.setCandidateWeight(getCandidateWeight(maxUtilisationResult)); |
| 158 | candidate.setHeuristic(this); |
| 159 | candidates.add(candidate); |
| 160 | increaseCounterOfGeneratedCandidates(); |
| 161 | |
| 162 | } |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | |
| 168 | |
| 169 | // change multiplicity |
| 170 | |
| 171 | } |
| 172 | |
| 173 | private void createClassicServerExpansionCandidates( |
| 174 | DSEIndividual individual, List<TacticsResultCandidate> candidates, |
| 175 | ProcessingResourceSpecificationResult maxUtilisationResult, |
| 176 | ResourceContainer resourceContainer) { |
| 177 | |
| 178 | TacticsResultCandidate candidate = individualBuilder.buildCandidate(copy.copy(individual.getGenotype()), individual); |
| 179 | |
| 180 | // 3. Get a new (unused) target resource container |
| 181 | // TODO: Must be one that some components of the current container can actually be moved to. This is |
| 182 | // not considered yet, and in these cases the generated candidate will be identical to its parent. |
| 183 | ResourceContainer targetResourceContainer = getRandomUnusedResourceContainer(individual); |
| 184 | |
| 185 | // 4. reallocate components |
| 186 | // 4a Iterate through AllocationDegrees and find the choices for this container |
| 187 | List<ClassChoice> componentsAllocatedHere = new LinkedList<ClassChoice>(); |
| 188 | for (Choice choice : candidate.getGenotype()) { |
| 189 | if (choice instanceof ClassChoice) { |
| 190 | ClassChoice ClassChoice = (ClassChoice)choice; |
| 191 | if (ClassChoice.getDegreeOfFreedomInstance() instanceof AllocationDegree) { |
| 192 | if (EMFHelper.checkIdentity(ClassChoice.getChosenValue(), resourceContainer)) { |
| 193 | componentsAllocatedHere.add(ClassChoice); |
| 194 | |
| 195 | } |
| 196 | } |
| 197 | } |
| 198 | } |
| 199 | |
| 200 | // 4b reallocate half of the found components, but not more than this.maxNumberOfReplacements |
| 201 | int halfOfFoundComponents = componentsAllocatedHere.size() / 2; |
| 202 | int reallocateAtMost = halfOfFoundComponents > maxNumberOfReplacements ? maxNumberOfReplacements : halfOfFoundComponents; |
| 203 | for (int i = 0; i < reallocateAtMost && componentsAllocatedHere.size() > 0; i++){ |
| 204 | ClassChoice classChoice = componentsAllocatedHere.get(this.generator.nextInt(componentsAllocatedHere.size())); |
| 205 | // Reallocate this component to target resource container |
| 206 | EObject targetResourceContainerInMemory = EMFHelper.retrieveEntityByID(((ClassDegree)classChoice.getDegreeOfFreedomInstance()).getClassDesignOptions(), targetResourceContainer); |
| 207 | if (targetResourceContainerInMemory != null){ |
| 208 | classChoice.setChosenValue(targetResourceContainerInMemory); |
| 209 | } else { |
| 210 | i--; // cannot loop endlessly as the list componentsAllocatedHere is reduced, too |
| 211 | } |
| 212 | |
| 213 | componentsAllocatedHere.remove(classChoice); |
| 214 | } |
| 215 | |
| 216 | candidate.setCandidateWeight(getCandidateWeight(maxUtilisationResult)); |
| 217 | candidate.setHeuristic(this); |
| 218 | candidates.add(candidate); |
| 219 | increaseCounterOfGeneratedCandidates(); |
| 220 | } |
| 221 | |
| 222 | |
| 223 | /** |
| 224 | * Calculates weight based on the following scheme: if utilisation equals THRESHOLD_HIGH_UTLISATION |
| 225 | * then it will return 0, if utilisation equals 1 it will return 1. Values in between are linearly |
| 226 | * extrapolated. Return values will always be >= 0. |
| 227 | * @param utilisationResult |
| 228 | * @return Weight based on utilisationResult's utilisation |
| 229 | */ |
| 230 | private double getCandidateWeight(UtilisationResult utilisationResult) { |
| 231 | return Math.min(1, Math.max(utilisationResult.getResourceUtilisation()/(1.0 - thresholdHighUtilisation) - thresholdHighUtilisation/(1.0 - thresholdHighUtilisation), |
| 232 | 0)); |
| 233 | } |
| 234 | |
| 235 | /** |
| 236 | * Get a random resource containers that has no allocated components |
| 237 | * @param individual |
| 238 | * @return |
| 239 | */ |
| 240 | private ResourceContainer getRandomUnusedResourceContainer(DSEIndividual individual) { |
| 241 | Random random = new Random(); |
| 242 | Collection<ResourceContainer> resourceContainers = resultInterpretationHelper.getUnusedAvailableResourceContainers(individual); |
| 243 | int randomInt = random.nextInt(resourceContainers.size()); |
| 244 | int n = 0; |
| 245 | for (ResourceContainer container : resourceContainers ) { |
| 246 | if (n == randomInt) { |
| 247 | return container; |
| 248 | } |
| 249 | n++; |
| 250 | } |
| 251 | // wont be executed unless resourceContainers is empty |
| 252 | return null; |
| 253 | } |
| 254 | |
| 255 | |
| 256 | |
| 257 | } |