| 1 | package de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.impl; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collection; |
| 5 | import java.util.Collections; |
| 6 | import java.util.List; |
| 7 | |
| 8 | import org.apache.log4j.Logger; |
| 9 | import org.eclipse.emf.ecore.util.EcoreUtil; |
| 10 | import org.opt4j.core.Objective; |
| 11 | import org.opt4j.core.problem.Genotype; |
| 12 | import org.opt4j.operator.copy.Copy; |
| 13 | |
| 14 | import de.uka.ipd.sdq.context.aggregatedUsageContext.AggregatedCommunication; |
| 15 | import de.uka.ipd.sdq.context.aggregatedUsageContext.ComputedAggregatedUsage; |
| 16 | import de.uka.ipd.sdq.context.aggregatedUsageContext.ServiceExecutionContext; |
| 17 | import de.uka.ipd.sdq.dsexplore.helper.EMFHelper; |
| 18 | import de.uka.ipd.sdq.dsexplore.helper.Pair; |
| 19 | import de.uka.ipd.sdq.dsexplore.launch.DSEWorkflowConfiguration; |
| 20 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.AbstractTactic; |
| 21 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.TacticsResultCandidate; |
| 22 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.operators.UtilisationResultCacheAndHelper; |
| 23 | import de.uka.ipd.sdq.dsexplore.opt4j.representation.DSEIndividual; |
| 24 | import de.uka.ipd.sdq.dsexplore.opt4j.representation.DSEIndividualBuilder; |
| 25 | import de.uka.ipd.sdq.dsexplore.opt4j.start.Opt4JStarter; |
| 26 | import de.uka.ipd.sdq.dsexplore.qml.handling.QMLConstantsContainer; |
| 27 | import de.uka.ipd.sdq.dsexplore.qml.reader.QMLDimensionReader; |
| 28 | import de.uka.ipd.sdq.pcm.allocation.AllocationContext; |
| 29 | import de.uka.ipd.sdq.pcm.designdecision.AllocationDegree; |
| 30 | import de.uka.ipd.sdq.pcm.designdecision.Choice; |
| 31 | import de.uka.ipd.sdq.pcm.designdecision.DegreeOfFreedomInstance; |
| 32 | import de.uka.ipd.sdq.pcm.designdecision.ClassChoice; |
| 33 | import de.uka.ipd.sdq.pcm.designdecision.ClassDegree; |
| 34 | import de.uka.ipd.sdq.pcm.resourceenvironment.ResourceContainer; |
| 35 | import de.uka.ipd.sdq.pcm.resultdecorator.ResultDecoratorRepository; |
| 36 | import de.uka.ipd.sdq.pcm.resultdecorator.repositorydecorator.AllocationServiceResult; |
| 37 | import de.uka.ipd.sdq.pcm.resultdecorator.repositorydecorator.ServiceResult; |
| 38 | import de.uka.ipd.sdq.pcm.resultdecorator.resourceenvironmentdecorator.LinkingResourceResults; |
| 39 | |
| 40 | public class ReallocateForReduceLinkUsage extends AbstractTactic { |
| 41 | |
| 42 | private double thresholdUtilisation; |
| 43 | private Objective performance; |
| 44 | |
| 45 | protected static Logger logger = Logger.getLogger(ReallocateForReduceLinkUsage.class.getName()); |
| 46 | |
| 47 | |
| 48 | public ReallocateForReduceLinkUsage(Copy<Genotype> copy, |
| 49 | DSEIndividualBuilder individualBuilder, |
| 50 | DSEWorkflowConfiguration configuration) { |
| 51 | super(copy, individualBuilder, configuration, new String[] {QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_RESPONSETIME_DEFINITION_PATH, |
| 52 | QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_THROUGHPUT_DEFINITION_PATH}); |
| 53 | |
| 54 | //setHeuristicWeight(configuration.getReallocationForLinkWeight()); |
| 55 | setHeuristicWeight(1); |
| 56 | //thresholdUtilisation = configuration.getReallocationForLinkUtilisationThreshold(); |
| 57 | thresholdUtilisation = 0.8; |
| 58 | |
| 59 | try { |
| 60 | Collection<Objective> objectives = Opt4JStarter.getDSEEvaluator() |
| 61 | .getObjectives(); |
| 62 | for (Objective objective : objectives) { |
| 63 | //XXX: Read the dimension name from definition rather than the constants container |
| 64 | if (objective.getName().contains( |
| 65 | new QMLDimensionReader().getDimension(QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_RESPONSETIME_DEFINITION_PATH).getEntityName()) |
| 66 | || objective.getName().contains( |
| 67 | new QMLDimensionReader().getDimension(QMLConstantsContainer.QUALITY_ATTRIBUTE_DIMENSION_THROUGHPUT_DEFINITION_PATH).getEntityName())) { |
| 68 | //DSEConstantsContainer.MEAN_RESPONSE_TIME_QUALITY)) { |
| 69 | this.performance = objective; |
| 70 | break; |
| 71 | } |
| 72 | } |
| 73 | } catch (Exception e) { |
| 74 | // TODO: handle exception |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | @Override |
| 79 | public List<TacticsResultCandidate> getHeuristicCandidates(DSEIndividual individual, |
| 80 | UtilisationResultCacheAndHelper resultsCache) { |
| 81 | if (performance != null && individual.getObjectives().getResultDecoratorFor(this.performance) != null) { |
| 82 | |
| 83 | ResultDecoratorRepository resultRepo = individual.getObjectives().getResultDecoratorFor(this.performance); |
| 84 | |
| 85 | // 1. check whether a link is used beyond the threshold. |
| 86 | // find Linking Resource with highest Utilisation to move components along it. |
| 87 | LinkingResourceResults linkWithHighestUtil = resultsCache.getMaxLinkUtilisationResult(individual); |
| 88 | |
| 89 | // check if there is a link with highest util, maybe this candidate does not use any link |
| 90 | if (linkWithHighestUtil != null){ |
| 91 | List<ResourceContainer> connectedContainers = linkWithHighestUtil.getLinkingResource_LinkingResourceResults().getConnectedResourceContainers_LinkingResource(); |
| 92 | |
| 93 | if (linkWithHighestUtil.getResourceUtilisation() > thresholdUtilisation){ |
| 94 | |
| 95 | // group service results by component |
| 96 | List<ServiceResult> serviceResultList = resultRepo.getServiceResult_ResultDecoratorRepository(); |
| 97 | |
| 98 | if (serviceResultList.size() == 0){ |
| 99 | /* Does not matter at this time because this tactics does not yet use the information |
| 100 | * about service response time and throughput (could use that to compare with demanded time somehow). |
| 101 | * logger.warn("No service results found for candidate "+individual.getNumericID()+". " + |
| 102 | "Cannot apply "+this.getClass().getName()+" tactic. Note that the service result " + |
| 103 | "data is not available for results that have been read in from a predefined population file."); |
| 104 | */ |
| 105 | } |
| 106 | |
| 107 | List<ComponentAndServiceResult> componentsAndServices = new ArrayList<ComponentAndServiceResult>(); |
| 108 | for (ServiceResult serviceResult : serviceResultList) { |
| 109 | if (serviceResult instanceof AllocationServiceResult){ |
| 110 | |
| 111 | AllocationServiceResult allocServiceResult = (AllocationServiceResult)serviceResult; |
| 112 | AllocationContext component = allocServiceResult.getAllocationContext_AllocationServiceResult(); |
| 113 | |
| 114 | // check whether this is the result for a component. |
| 115 | // if it is the result of e.g. a usage scenario, then the component is null. |
| 116 | if (component != null){ |
| 117 | |
| 118 | ComponentAndServiceResult compReslt = null; |
| 119 | for (ComponentAndServiceResult componentAndServiceResult : componentsAndServices) { |
| 120 | if (EMFHelper.checkIdentity(componentAndServiceResult.getComponent(),component)){ |
| 121 | compReslt = componentAndServiceResult; |
| 122 | break; |
| 123 | } |
| 124 | } |
| 125 | if (compReslt == null){ |
| 126 | compReslt = new ComponentAndServiceResult(component, individual); |
| 127 | } |
| 128 | compReslt.addAllocationServiceResult(allocServiceResult); |
| 129 | } |
| 130 | } else { |
| 131 | logger.error("An unknown type of service results has been encountered, expected "+AllocationServiceResult.class.getName()+" only. Encountered type is "+serviceResult.getClass().getName()); |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | // group service dependency solver results by component |
| 136 | // results for the services |
| 137 | ComputedAggregatedUsage computedUsage = individual.getObjectives().getComputedAggregatedUsageFor(this.performance); |
| 138 | |
| 139 | if (computedUsage != null){ |
| 140 | List<ServiceExecutionContext> serviceContexts = computedUsage.getServiceExecutionContexts_ComputedAggregatedUsage(); |
| 141 | for (ServiceExecutionContext serviceExecutionContext : serviceContexts) { |
| 142 | AllocationContext component = serviceExecutionContext.getAllocationContext_ServiceExecutionContext(); |
| 143 | |
| 144 | ComponentAndServiceResult compReslt = null; |
| 145 | for (ComponentAndServiceResult componentAndServiceResult : componentsAndServices) { |
| 146 | if (EMFHelper.checkIdentity(componentAndServiceResult.getComponent(),component)){ |
| 147 | compReslt = componentAndServiceResult; |
| 148 | break; |
| 149 | } |
| 150 | } |
| 151 | if (compReslt == null){ |
| 152 | compReslt = new ComponentAndServiceResult(component, individual); |
| 153 | componentsAndServices.add(compReslt); |
| 154 | } |
| 155 | compReslt.addServiceExecutionContext(serviceExecutionContext); |
| 156 | } |
| 157 | |
| 158 | // count the remote and local calls of each component. |
| 159 | for (ComponentAndServiceResult componentAndServiceResult : componentsAndServices) { |
| 160 | componentAndServiceResult.countCalls(); |
| 161 | } |
| 162 | |
| 163 | // get the component that has the highest ratio of calls to one remote server compared to its local calls. |
| 164 | Pair<ComponentAndServiceResult, ResourceContainerWithDoubleValue> componentWithTargetContainer = |
| 165 | getComponentWithHighestRatioToOneOfContainers(componentsAndServices, connectedContainers); |
| 166 | |
| 167 | return createCandidate(componentWithTargetContainer, individual, linkWithHighestUtil.getResourceUtilisation()); |
| 168 | } else { |
| 169 | logger.warn("No ComputedUsage found for candidate "+individual.getNumericID()+" , cannot apply linking resource tactic."); |
| 170 | } |
| 171 | } |
| 172 | } |
| 173 | } |
| 174 | return Collections.emptyList(); |
| 175 | } |
| 176 | |
| 177 | private List<TacticsResultCandidate> createCandidate( |
| 178 | Pair<ComponentAndServiceResult, ResourceContainerWithDoubleValue> componentWithTargetContainer, |
| 179 | DSEIndividual individual , double highestUtil) { |
| 180 | if (componentWithTargetContainer == null |
| 181 | || componentWithTargetContainer.getFirst() == null |
| 182 | || componentWithTargetContainer.getSecond() == null){ |
| 183 | return Collections.emptyList(); |
| 184 | } |
| 185 | double candidateWeight = Math.max(1, componentWithTargetContainer.getSecond().getSecond() * ((highestUtil - thresholdUtilisation) / (1-thresholdUtilisation))); |
| 186 | |
| 187 | |
| 188 | List<TacticsResultCandidate> result = new ArrayList<TacticsResultCandidate>(1); |
| 189 | |
| 190 | TacticsResultCandidate candidate = individualBuilder.buildCandidate(copy.copy(individual.getGenotype()), individual); |
| 191 | candidate.setHeuristic(this); |
| 192 | candidate.setCandidateWeight(candidateWeight); |
| 193 | // find choice for the reallocated components degree |
| 194 | for (Choice choice : candidate.getGenotype()) { |
| 195 | if (choice instanceof ClassChoice |
| 196 | && EcoreUtil.equals(choice.getDegreeOfFreedomInstance(), |
| 197 | componentWithTargetContainer.getFirst().getAllocationDegree())){ |
| 198 | ((ClassChoice)choice).setChosenValue( |
| 199 | EMFHelper.retrieveEntityByID( |
| 200 | ((ClassDegree)choice.getDegreeOfFreedomInstance()).getClassDesignOptions(), |
| 201 | componentWithTargetContainer.getSecond().getFirst())); |
| 202 | result.add(candidate); |
| 203 | break; |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | return result; |
| 208 | } |
| 209 | |
| 210 | /** |
| 211 | * @param componentsAndServices |
| 212 | * @param connectedContainers |
| 213 | * @return May be null or may contain null values if no matching component is found. |
| 214 | */ |
| 215 | private Pair<ComponentAndServiceResult, ResourceContainerWithDoubleValue> getComponentWithHighestRatioToOneOfContainers( |
| 216 | List<ComponentAndServiceResult> componentsAndServices, |
| 217 | List<ResourceContainer> connectedContainers) { |
| 218 | |
| 219 | Pair<ComponentAndServiceResult, ResourceContainerWithDoubleValue> componentWithTargetContainer = null; |
| 220 | |
| 221 | for (ComponentAndServiceResult componentResult : componentsAndServices) { |
| 222 | // get the ratio of remote calls to the most promising server vs local calls of this component. |
| 223 | // the maxContainerOfComponent.getSecond() denotes this ratio. It should be larger than 0.5 for the reallocation to be useful. |
| 224 | ResourceContainerWithDoubleValue maxContainerOfComponent = componentResult.getMostPromisingContainerToReallocateTo(connectedContainers); |
| 225 | if (maxContainerOfComponent != null && maxContainerOfComponent.getSecond() > 0.5 && |
| 226 | ( componentWithTargetContainer == null |
| 227 | || ( maxContainerOfComponent.getSecond() > componentWithTargetContainer.getSecond().getSecond()))){ |
| 228 | //XXX: If two components have the same ratio, we could look at the demanded time and the container utilisation here and decide |
| 229 | // to either reallocate a "small" component or a "large" component |
| 230 | //XXX: Maybe do not always return the best, but vary a bit randomly? Weighted based on ratio (if > 0.5?) |
| 231 | componentWithTargetContainer = new Pair<ComponentAndServiceResult, ResourceContainerWithDoubleValue>( |
| 232 | componentResult, |
| 233 | maxContainerOfComponent); |
| 234 | } |
| 235 | } |
| 236 | |
| 237 | |
| 238 | return componentWithTargetContainer; |
| 239 | |
| 240 | } |
| 241 | |
| 242 | } |
| 243 | |
| 244 | class ComponentAndServiceResult { |
| 245 | |
| 246 | private AllocationContext allocationContextOfComponent; |
| 247 | private List<AllocationServiceResult> allocationServiceResultList = new ArrayList<AllocationServiceResult>(); |
| 248 | private List<ServiceExecutionContext> serviceExecutionContextList = new ArrayList<ServiceExecutionContext>(); |
| 249 | |
| 250 | private double frequencyLocalCalls = 0; |
| 251 | |
| 252 | private List<ResourceContainerWithDoubleValue> frequencyRemoteCalls = new ArrayList<ResourceContainerWithDoubleValue>(); |
| 253 | private List<ResourceContainerWithDoubleValue> ratioRemoteCalls = new ArrayList<ResourceContainerWithDoubleValue>(); |
| 254 | private AllocationDegree allocationDoF; |
| 255 | private ClassChoice allocationChoice; |
| 256 | |
| 257 | public ComponentAndServiceResult(AllocationContext component, DSEIndividual individual) { |
| 258 | super(); |
| 259 | this.allocationContextOfComponent = component; |
| 260 | this.allocationDoF = determineAllocationDoF(); |
| 261 | this.allocationChoice = determineAllocationChoice(individual); |
| 262 | } |
| 263 | |
| 264 | public AllocationContext getComponent() { |
| 265 | return allocationContextOfComponent; |
| 266 | } |
| 267 | |
| 268 | public AllocationDegree getAllocationDegree() { |
| 269 | return this.allocationDoF; |
| 270 | } |
| 271 | |
| 272 | /** |
| 273 | * Return the {@link ResourceContainerWithDoubleValue} from the internal list of |
| 274 | * frequency ratios that has the highest value among the containers that this component |
| 275 | * could be deployed to. |
| 276 | * |
| 277 | * This means that the internal list is filtered for the passed resource container list |
| 278 | * and filtered for the containers that this component may be allocated to |
| 279 | * according to the design decisions. |
| 280 | * |
| 281 | * @param candidateContainers |
| 282 | * @return The most promising resource container of the passed containers |
| 283 | * to reallocate this component to. |
| 284 | * Can be null if this component must not be reallocated or cannot be |
| 285 | * reallocated to any of the passed candidateContainers. |
| 286 | */ |
| 287 | public ResourceContainerWithDoubleValue getMostPromisingContainerToReallocateTo( |
| 288 | List<ResourceContainer> candidateContainers) { |
| 289 | |
| 290 | // filter and retain only the containers to which this component can be allocated. |
| 291 | List<ResourceContainer> filteredCandidateContainers = new ArrayList<ResourceContainer>(candidateContainers.size()); |
| 292 | filteredCandidateContainers.addAll(candidateContainers); |
| 293 | EMFHelper.retainAll(filteredCandidateContainers, this.allocationDoF.getClassDesignOptions()); |
| 294 | |
| 295 | ResourceContainerWithDoubleValue maxRatioContainer = null; |
| 296 | for (ResourceContainerWithDoubleValue resourceContainer : this.ratioRemoteCalls) { |
| 297 | if (EMFHelper.contains(filteredCandidateContainers, resourceContainer.getFirst()) |
| 298 | && ( maxRatioContainer == null |
| 299 | || resourceContainer.getSecond() > maxRatioContainer.getSecond())){ |
| 300 | maxRatioContainer = resourceContainer; |
| 301 | } |
| 302 | } |
| 303 | return maxRatioContainer; |
| 304 | } |
| 305 | |
| 306 | public void addServiceExecutionContext(ServiceExecutionContext serviceExecutionContext) { |
| 307 | this.serviceExecutionContextList.add(serviceExecutionContext); |
| 308 | } |
| 309 | |
| 310 | public void countCalls() { |
| 311 | |
| 312 | for (ServiceExecutionContext serviceExecutionContext : this.serviceExecutionContextList) { |
| 313 | List<AggregatedCommunication> senderCommunication = serviceExecutionContext.getSentAggregatedCommunications_ServiceExecutionContext(); |
| 314 | List<AggregatedCommunication> receiverCommunication = serviceExecutionContext.getReceivedAggregatedCommunication_AggregatedCommunication(); |
| 315 | countCallsOfCommunications(senderCommunication); |
| 316 | countCallsOfCommunications(receiverCommunication); |
| 317 | } |
| 318 | |
| 319 | for (ResourceContainerWithDoubleValue rcv : this.frequencyRemoteCalls) { |
| 320 | ResourceContainerWithDoubleValue rcRatio = new ResourceContainerWithDoubleValue(rcv.getFirst(), new Double(rcv.getSecond() / (rcv.getSecond() + this.frequencyLocalCalls))); |
| 321 | this.ratioRemoteCalls.add(rcRatio); |
| 322 | } |
| 323 | |
| 324 | // TODO: nur f�r remote calls �ber den Link of interest!! |
| 325 | // TODO: calculate overall local vs remote ratio? No, sort these objects by which pair of component / RC has the highest ratio. Or any? |
| 326 | |
| 327 | } |
| 328 | |
| 329 | private void countCallsOfCommunications(List<AggregatedCommunication> senderCommunication) { |
| 330 | for (AggregatedCommunication aggregatedCommunication : senderCommunication) { |
| 331 | ResourceContainer receivingContainer = aggregatedCommunication.getReceiver_AggregatedCommunication().getAllocationContext_ServiceExecutionContext().getResourceContainer_AllocationContext(); |
| 332 | |
| 333 | // must not access this.allocationContextOfComponent.getResourceContainer_AllocationContext() because the PCM instance may have been manipulated in the mean time. |
| 334 | //Check genome instead. If the component cannot be reallocated (no design decision for it, then we can abort anyway) |
| 335 | if (!EMFHelper.checkIdentity(receivingContainer, this.allocationChoice.getChosenValue())){ |
| 336 | ResourceContainerWithDoubleValue remoteContainer = createOrReuseResourceContainerEntryInList(receivingContainer); |
| 337 | remoteContainer.setSecond(remoteContainer.getSecond()+aggregatedCommunication.getAverageMessageFrequency()); |
| 338 | } else { |
| 339 | this.frequencyLocalCalls += aggregatedCommunication.getAverageMessageFrequency(); |
| 340 | } |
| 341 | |
| 342 | } |
| 343 | } |
| 344 | |
| 345 | private ResourceContainerWithDoubleValue createOrReuseResourceContainerEntryInList( |
| 346 | ResourceContainer receivingContainer) { |
| 347 | for (ResourceContainerWithDoubleValue resourceContainerEntry : this.frequencyRemoteCalls) { |
| 348 | if (EMFHelper.checkIdentity(resourceContainerEntry.getFirst(), receivingContainer)){ |
| 349 | return resourceContainerEntry; |
| 350 | } |
| 351 | } |
| 352 | ResourceContainerWithDoubleValue rcf = new ResourceContainerWithDoubleValue(receivingContainer, new Double(0)); |
| 353 | this.frequencyRemoteCalls.add(rcf); |
| 354 | return rcf; |
| 355 | } |
| 356 | |
| 357 | public List<AllocationServiceResult> getResult() { |
| 358 | return allocationServiceResultList; |
| 359 | } |
| 360 | |
| 361 | private AllocationDegree determineAllocationDoF() { |
| 362 | List<DegreeOfFreedomInstance> dof = Opt4JStarter.getProblem().getDesignDecisions(); |
| 363 | for (DegreeOfFreedomInstance DegreeOfFreedomInstance : dof) { |
| 364 | if (DegreeOfFreedomInstance instanceof AllocationDegree){ |
| 365 | AllocationDegree allocDof = (AllocationDegree)DegreeOfFreedomInstance; |
| 366 | if (EMFHelper.checkIdentity(allocDof.getPrimaryChanged(), this.allocationContextOfComponent)){ |
| 367 | // this is the degree |
| 368 | return allocDof; |
| 369 | } |
| 370 | } |
| 371 | } |
| 372 | return null; |
| 373 | } |
| 374 | |
| 375 | private ClassChoice determineAllocationChoice(DSEIndividual individual) { |
| 376 | for (Choice choice : individual.getGenotype()) { |
| 377 | if (EcoreUtil.equals(choice.getDegreeOfFreedomInstance(), this.allocationDoF)){ |
| 378 | return (ClassChoice) choice; |
| 379 | } |
| 380 | } |
| 381 | return null; |
| 382 | } |
| 383 | |
| 384 | public void addAllocationServiceResult(AllocationServiceResult result){ |
| 385 | this.allocationServiceResultList.add(result); |
| 386 | } |
| 387 | |
| 388 | @Override |
| 389 | public boolean equals(Object o){ |
| 390 | if (o instanceof ComponentAndServiceResult){ |
| 391 | return EMFHelper.checkIdentity(this.allocationContextOfComponent,((ComponentAndServiceResult) o).getComponent()); |
| 392 | } |
| 393 | return false; |
| 394 | } |
| 395 | |
| 396 | @Override |
| 397 | public int hashCode(){ |
| 398 | return this.allocationContextOfComponent.getId().hashCode(); |
| 399 | |
| 400 | } |
| 401 | } |
| 402 | |
| 403 | class ResourceContainerWithDoubleValue extends Pair<ResourceContainer, Double> { |
| 404 | |
| 405 | public ResourceContainerWithDoubleValue(ResourceContainer receivingContainer, |
| 406 | Double double1) { |
| 407 | super(receivingContainer, double1); |
| 408 | }} |