diff options
Diffstat (limited to 'opendc-simulator/opendc-simulator-compute/src')
14 files changed, 355 insertions, 291 deletions
diff --git a/opendc-simulator/opendc-simulator-compute/src/jmh/kotlin/org/opendc/simulator/compute/SimMachineBenchmarks.kt b/opendc-simulator/opendc-simulator-compute/src/jmh/kotlin/org/opendc/simulator/compute/SimMachineBenchmarks.kt index c3332d66..e862e4d1 100644 --- a/opendc-simulator/opendc-simulator-compute/src/jmh/kotlin/org/opendc/simulator/compute/SimMachineBenchmarks.kt +++ b/opendc-simulator/opendc-simulator-compute/src/jmh/kotlin/org/opendc/simulator/compute/SimMachineBenchmarks.kt @@ -87,7 +87,7 @@ class SimMachineBenchmarks { engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(engine, null, random) + val hypervisor = SimSpaceSharedHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } @@ -110,7 +110,7 @@ class SimMachineBenchmarks { engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimFairShareHypervisor(engine, null, random) + val hypervisor = SimFairShareHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } @@ -133,7 +133,7 @@ class SimMachineBenchmarks { engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimFairShareHypervisor(engine, null, random) + val hypervisor = SimFairShareHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt index 2cabeece..77088b74 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimAbstractHypervisor.kt @@ -25,7 +25,9 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.* import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor import org.opendc.simulator.compute.kernel.cpufreq.ScalingPolicy +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.compute.kernel.interference.VmInterferenceMember +import org.opendc.simulator.compute.kernel.interference.VmInterferenceProfile import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.model.ProcessingUnit import org.opendc.simulator.compute.workload.SimWorkload @@ -38,13 +40,15 @@ import kotlin.math.roundToLong * Abstract implementation of the [SimHypervisor] interface. * * @param engine The [FlowEngine] to drive the simulation. - * @param scalingGovernor The scaling governor to use for scaling the CPU frequency of the underlying hardware. * @param random A randomness generator for the interference calculations. + * @param scalingGovernor The scaling governor to use for scaling the CPU frequency of the underlying hardware. + * @param interferenceDomain The interference domain to which the hypervisor belongs. */ public abstract class SimAbstractHypervisor( protected val engine: FlowEngine, + private val random: SplittableRandom, private val scalingGovernor: ScalingGovernor?, - private val random: SplittableRandom + private val interferenceDomain: VmInterferenceDomain ) : SimHypervisor, FlowConvergenceListener { /** * The machine on which the hypervisor runs. @@ -94,9 +98,9 @@ public abstract class SimAbstractHypervisor( private val governors = mutableListOf<ScalingGovernor.Logic>() /* SimHypervisor */ - override fun newMachine(model: MachineModel, interferenceKey: VmInterferenceMember?): SimVirtualMachine { + override fun newMachine(model: MachineModel): SimVirtualMachine { require(canFit(model)) { "Machine does not fit" } - val vm = VirtualMachine(model, interferenceKey) + val vm = VirtualMachine(model) _vms.add(vm) return vm } @@ -164,12 +168,8 @@ public abstract class SimAbstractHypervisor( * A virtual machine running on the hypervisor. * * @param model The machine model of the virtual machine. - * @param interferenceKey The interference key of this virtual machine. */ - private inner class VirtualMachine( - model: MachineModel, - private val interferenceKey: VmInterferenceMember? = null - ) : SimAbstractMachine(engine, model), SimVirtualMachine, AutoCloseable { + private inner class VirtualMachine(model: MachineModel) : SimAbstractMachine(engine, model), SimVirtualMachine, AutoCloseable { /** * A flag to indicate that the machine is closed. */ @@ -185,7 +185,7 @@ public abstract class SimAbstractHypervisor( */ override val counters: SimHypervisorCounters get() = _counters - @JvmField val _counters = VmCountersImpl(cpus, interferenceKey) + @JvmField val _counters = VmCountersImpl(cpus, null) /** * The CPU capacity of the hypervisor in MHz. @@ -208,21 +208,27 @@ public abstract class SimAbstractHypervisor( override fun startWorkload(workload: SimWorkload, meta: Map<String, Any>): SimMachineContext { check(!isClosed) { "Machine is closed" } + val profile = meta["interference-profile"] as? VmInterferenceProfile + val interferenceMember = if (profile != null) interferenceDomain.join(profile) else null + + val counters = _counters + counters.member = interferenceMember + return super.startWorkload( object : SimWorkload { override fun onStart(ctx: SimMachineContext) { - val interferenceKey = interferenceKey try { - interferenceKey?.activate() + interferenceMember?.activate() workload.onStart(ctx) } catch (cause: Throwable) { - interferenceKey?.deactivate() + interferenceMember?.deactivate() throw cause } } override fun onStop(ctx: SimMachineContext) { - interferenceKey?.deactivate() + interferenceMember?.deactivate() + counters.member = null workload.onStop(ctx) } }, @@ -339,7 +345,7 @@ public abstract class SimAbstractHypervisor( */ private inner class VmCountersImpl( private val cpus: List<VCpu>, - private val key: VmInterferenceMember? + @JvmField var member: VmInterferenceMember? ) : SimHypervisorCounters { private val d = cpus.size / cpus.sumOf { it.model.frequency } * 1000 @@ -388,9 +394,9 @@ public abstract class SimAbstractHypervisor( cpuTime[2] += ((demandDelta - actualDelta) * d).roundToLong() // Compute the performance penalty due to flow interference - val key = key - if (key != null) { - val penalty = 1 - key.apply(random, load) + val member = member + if (member != null) { + val penalty = 1 - member.apply(random, load) val interference = (actualDelta * d * penalty).roundToLong() if (interference > 0) { diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt index 4435a422..fbee46da 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisor.kt @@ -24,6 +24,7 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.SimMachine import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.workload.SimWorkload import org.opendc.simulator.flow.FlowEngine @@ -35,15 +36,17 @@ import java.util.SplittableRandom * A [SimHypervisor] that distributes the computing requirements of multiple [SimWorkload]s on a single [SimMachine] * concurrently using weighted fair sharing. * - * @param engine The [FlowEngine] to manage the machine's resources. - * @param scalingGovernor The CPU frequency scaling governor to use for the hypervisor. + * @param engine The [FlowEngine] to drive the simulation. * @param random A randomness generator for the interference calculations. + * @param scalingGovernor The scaling governor to use for scaling the CPU frequency of the underlying hardware. + * @param interferenceDomain The interference domain to which the hypervisor belongs. */ public class SimFairShareHypervisor( engine: FlowEngine, + random: SplittableRandom, scalingGovernor: ScalingGovernor?, - random: SplittableRandom -) : SimAbstractHypervisor(engine, scalingGovernor, random) { + interferenceDomain: VmInterferenceDomain = VmInterferenceDomain() +) : SimAbstractHypervisor(engine, random, scalingGovernor, interferenceDomain) { /** * The multiplexer that distributes the computing capacity. */ diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt index c7008652..81dfc43d 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorProvider.kt @@ -23,6 +23,7 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.flow.FlowEngine import java.util.* @@ -36,5 +37,6 @@ public class SimFairShareHypervisorProvider : SimHypervisorProvider { engine: FlowEngine, random: SplittableRandom, scalingGovernor: ScalingGovernor?, - ): SimHypervisor = SimFairShareHypervisor(engine, scalingGovernor, random) + interferenceDomain: VmInterferenceDomain, + ): SimHypervisor = SimFairShareHypervisor(engine, random, scalingGovernor, interferenceDomain) } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt index f53d0c5d..d8e4e7cd 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisor.kt @@ -23,7 +23,6 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.SimMachine -import org.opendc.simulator.compute.kernel.interference.VmInterferenceMember import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.compute.workload.SimWorkload @@ -66,9 +65,8 @@ public interface SimHypervisor : SimWorkload { * Create a [SimMachine] instance on which users may run a [SimWorkload]. * * @param model The machine to create. - * @param interferenceKey The key of the machine in the interference model. */ - public fun newMachine(model: MachineModel, interferenceKey: VmInterferenceMember? = null): SimVirtualMachine + public fun newMachine(model: MachineModel): SimVirtualMachine /** * Remove the specified [machine] from the hypervisor. diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt index 020a2a60..2c86854e 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimHypervisorProvider.kt @@ -23,6 +23,7 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.flow.FlowEngine import java.util.SplittableRandom @@ -41,5 +42,10 @@ public interface SimHypervisorProvider { /** * Create a new [SimHypervisor] instance. */ - public fun create(engine: FlowEngine, random: SplittableRandom, scalingGovernor: ScalingGovernor? = null): SimHypervisor + public fun create( + engine: FlowEngine, + random: SplittableRandom, + scalingGovernor: ScalingGovernor? = null, + interferenceDomain: VmInterferenceDomain + ): SimHypervisor } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt index 51bf4ce5..c32dd027 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisor.kt @@ -23,6 +23,7 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.compute.model.MachineModel import org.opendc.simulator.flow.FlowEngine import org.opendc.simulator.flow.mux.FlowMultiplexer @@ -32,15 +33,17 @@ import java.util.SplittableRandom /** * A [SimHypervisor] that allocates its sub-resources exclusively for the virtual machine that it hosts. * - * @param engine The [FlowEngine] to manage the machine's resources. - * @param scalingGovernor The CPU frequency scaling governor to use for the hypervisor. + * @param engine The [FlowEngine] to drive the simulation. * @param random A randomness generator for the interference calculations. + * @param scalingGovernor The scaling governor to use for scaling the CPU frequency of the underlying hardware. + * @param interferenceDomain The interference domain to which the hypervisor belongs. */ public class SimSpaceSharedHypervisor( engine: FlowEngine, + random: SplittableRandom, scalingGovernor: ScalingGovernor?, - random: SplittableRandom -) : SimAbstractHypervisor(engine, scalingGovernor, random) { + interferenceDomain: VmInterferenceDomain = VmInterferenceDomain() +) : SimAbstractHypervisor(engine, random, scalingGovernor, interferenceDomain) { override val mux: FlowMultiplexer = ForwardingFlowMultiplexer(engine, this) override fun canFit(model: MachineModel): Boolean { diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt index 05c54528..cc303bbd 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorProvider.kt @@ -23,6 +23,7 @@ package org.opendc.simulator.compute.kernel import org.opendc.simulator.compute.kernel.cpufreq.ScalingGovernor +import org.opendc.simulator.compute.kernel.interference.VmInterferenceDomain import org.opendc.simulator.flow.FlowEngine import java.util.* @@ -36,5 +37,6 @@ public class SimSpaceSharedHypervisorProvider : SimHypervisorProvider { engine: FlowEngine, random: SplittableRandom, scalingGovernor: ScalingGovernor?, - ): SimHypervisor = SimSpaceSharedHypervisor(engine, scalingGovernor, random) + interferenceDomain: VmInterferenceDomain, + ): SimHypervisor = SimSpaceSharedHypervisor(engine, random, scalingGovernor, interferenceDomain) } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt index 3b355f1e..6861823b 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceDomain.kt @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 AtLarge Research + * Copyright (c) 2022 AtLarge Research * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -22,16 +22,110 @@ package org.opendc.simulator.compute.kernel.interference +import java.util.ArrayDeque +import java.util.ArrayList +import java.util.WeakHashMap + /** - * The interference domain of a hypervisor. + * A domain where virtual machines may incur performance variability due to operating on the same resource and + * therefore causing interference. */ -public interface VmInterferenceDomain { +public class VmInterferenceDomain { + /** + * A cache to maintain a mapping between the active profiles in this domain. + */ + private val cache = WeakHashMap<VmInterferenceProfile, VmInterferenceMember>() + + /** + * The set of members active in this domain. + */ + private val activeKeys = ArrayList<VmInterferenceMember>() + + /** + * Queue of participants that will be removed or added to the active groups. + */ + private val participants = ArrayDeque<VmInterferenceMember>() + + /** + * Join this interference domain with the specified [profile] and return the [VmInterferenceMember] associated with + * the profile. If the member does not exist, it will be created. + */ + public fun join(profile: VmInterferenceProfile): VmInterferenceMember { + return cache.computeIfAbsent(profile) { key -> key.newMember(this) } + } + + /** + * Mark the specified [member] as active in this interference domain. + */ + internal fun activate(member: VmInterferenceMember) { + val activeKeys = activeKeys + val pos = activeKeys.binarySearch(member) + if (pos < 0) { + activeKeys.add(-pos - 1, member) + } + + computeActiveGroups(activeKeys, member) + } + /** - * Return the [VmInterferenceMember] associated with the specified [id]. - * - * @param id The identifier of the virtual machine. - * @return A [VmInterferenceMember] representing the virtual machine as part of the interference domain. `null` if - * the virtual machine does not participate in the domain. + * Mark the specified [member] as inactive in this interference domain. */ - public fun getMember(id: String): VmInterferenceMember? + internal fun deactivate(member: VmInterferenceMember) { + val activeKeys = activeKeys + activeKeys.remove(member) + computeActiveGroups(activeKeys, member) + } + + /** + * (Re-)compute the active groups. + */ + private fun computeActiveGroups(activeKeys: ArrayList<VmInterferenceMember>, member: VmInterferenceMember) { + if (activeKeys.isEmpty()) { + return + } + + val groups = member.membership + val members = member.members + val participants = participants + + for (group in groups) { + val groupMembers = members[group] + + var i = 0 + var j = 0 + var intersection = 0 + + // Compute the intersection of the group members and the current active members + while (i < groupMembers.size && j < activeKeys.size) { + val l = groupMembers[i] + val rightEntry = activeKeys[j] + val r = rightEntry.id + + if (l < r) { + i++ + } else if (l > r) { + j++ + } else { + if (++intersection > 1) { + rightEntry.addGroup(group) + } else { + participants.add(rightEntry) + } + + i++ + j++ + } + } + + while (true) { + val participant = participants.poll() ?: break + + if (intersection <= 1) { + participant.removeGroup(group) + } else { + participant.addGroup(group) + } + } + } + } } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceMember.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceMember.kt index 04203c63..762bb568 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceMember.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceMember.kt @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 AtLarge Research + * Copyright (c) 2022 AtLarge Research * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -27,16 +27,43 @@ import java.util.* /** * A participant of an interference domain. */ -public interface VmInterferenceMember { +public class VmInterferenceMember( + private val domain: VmInterferenceDomain, + private val model: VmInterferenceModel, + @JvmField internal val id: Int, + @JvmField internal val membership: IntArray, + @JvmField internal val members: Array<IntArray>, + private val targets: DoubleArray, + private val scores: DoubleArray +) : Comparable<VmInterferenceMember> { + /** + * The active groups to which the key belongs. + */ + private var groups: IntArray = IntArray(2) + private var groupsSize: Int = 0 + + /** + * The number of users of the interference key. + */ + private var refCount: Int = 0 + /** * Mark this member as active in this interference domain. */ - public fun activate() + public fun activate() { + if (refCount++ <= 0) { + domain.activate(this) + } + } /** * Mark this member as inactive in this interference domain. */ - public fun deactivate() + public fun deactivate() { + if (--refCount <= 0) { + domain.deactivate(this) + } + } /** * Compute the performance score of the member in this interference domain. @@ -46,5 +73,91 @@ public interface VmInterferenceMember { * @return A score representing the performance score to be applied to the member, with 1 * meaning no influence, <1 means that performance degrades, and >1 means that performance improves. */ - public fun apply(random: SplittableRandom, load: Double): Double + public fun apply(random: SplittableRandom, load: Double): Double { + val groupsSize = groupsSize + + if (groupsSize == 0) { + return 1.0 + } + + val groups = groups + val targets = targets + + var low = 0 + var high = groupsSize - 1 + var group = -1 + + // Perform binary search over the groups based on target load + while (low <= high) { + val mid = low + high ushr 1 + val midGroup = groups[mid] + val target = targets[midGroup] + + if (target < load) { + low = mid + 1 + group = midGroup + } else if (target > load) { + high = mid - 1 + } else { + group = midGroup + break + } + } + + return if (group >= 0 && random.nextInt(members[group].size) == 0) { + scores[group] + } else { + 1.0 + } + } + + /** + * Add an active group to this member. + */ + internal fun addGroup(group: Int) { + var groups = groups + val groupsSize = groupsSize + val pos = groups.binarySearch(group, toIndex = groupsSize) + + if (pos >= 0) { + return + } + + val idx = -pos - 1 + + if (groups.size == groupsSize) { + val newSize = groupsSize + (groupsSize shr 1) + groups = groups.copyOf(newSize) + this.groups = groups + } + + groups.copyInto(groups, idx + 1, idx, groupsSize) + groups[idx] = group + this.groupsSize += 1 + } + + /** + * Remove an active group from this member. + */ + internal fun removeGroup(group: Int) { + val groups = groups + val groupsSize = groupsSize + val pos = groups.binarySearch(group, toIndex = groupsSize) + + if (pos < 0) { + return + } + + groups.copyInto(groups, pos, pos + 1, groupsSize) + this.groupsSize -= 1 + } + + override fun compareTo(other: VmInterferenceMember): Int { + val cmp = model.hashCode().compareTo(other.model.hashCode()) + if (cmp != 0) { + return cmp + } + + return id.compareTo(other.id) + } } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt index 3ea869d4..018c6e3d 100644 --- a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceModel.kt @@ -27,7 +27,7 @@ import java.util.* /** * An interference model that models the resource interference between virtual machines on a host. * - * @param targets The target load of each group. + * @param members The target load of each group. * @param scores The performance score of each group. * @param members The members belonging to each group. * @param membership The identifier of each key. @@ -42,9 +42,16 @@ public class VmInterferenceModel private constructor( private val size: Int ) { /** - * Construct a new [VmInterferenceDomain]. + * Return the [VmInterferenceProfile] associated with the specified [id]. + * + * @param id The identifier of the virtual machine. + * @return A [VmInterferenceProfile] representing the virtual machine as part of interference model or `null` if + * there is no profile for the virtual machine. */ - public fun newDomain(): VmInterferenceDomain = InterferenceDomainImpl(idMapping, members, membership, targets, scores) + public fun getProfile(id: String): VmInterferenceProfile? { + val intId = idMapping[id] ?: return null + return VmInterferenceProfile(this, intId, membership[intId], members, targets, scores) + } public companion object { /** @@ -112,8 +119,8 @@ public class VmInterferenceModel private constructor( val scores = _scores val members = _members - val indices = Array(size) { it } - indices.sortWith( + val indices = IntArray(size) { it } + indices.sortedWith( Comparator { l, r -> var cmp = targets[l].compareTo(targets[r]) // Order by target load if (cmp != 0) { @@ -179,224 +186,4 @@ public class VmInterferenceModel private constructor( const val INITIAL_CAPACITY = 256 } } - - /** - * Internal implementation of [VmInterferenceDomain]. - */ - private class InterferenceDomainImpl( - private val idMapping: Map<String, Int>, - private val members: Array<IntArray>, - private val membership: Array<IntArray>, - private val targets: DoubleArray, - private val scores: DoubleArray, - ) : VmInterferenceDomain { - /** - * Keys registered with this domain. - */ - private val keys = HashMap<Int, InterferenceMemberImpl>() - - /** - * The set of keys active in this domain. - */ - private val activeKeys = ArrayList<InterferenceMemberImpl>() - - /** - * Queue of participants that will be removed or added to the active groups. - */ - private val participants = ArrayDeque<InterferenceMemberImpl>() - - override fun getMember(id: String): VmInterferenceMember? { - val intId = idMapping[id] ?: return null - return keys.computeIfAbsent(intId) { InterferenceMemberImpl(it, this, membership[it], members, targets, scores) } - } - - override fun toString(): String = "VmInterferenceDomain" - - fun join(key: InterferenceMemberImpl) { - val activeKeys = activeKeys - val pos = activeKeys.binarySearch(key) - if (pos < 0) { - activeKeys.add(-pos - 1, key) - } - - computeActiveGroups(activeKeys, key) - } - - fun leave(key: InterferenceMemberImpl) { - val activeKeys = activeKeys - activeKeys.remove(key) - computeActiveGroups(activeKeys, key) - } - - /** - * (Re-)compute the active groups. - */ - private fun computeActiveGroups(activeKeys: ArrayList<InterferenceMemberImpl>, key: InterferenceMemberImpl) { - if (activeKeys.isEmpty()) { - return - } - - val groups = key.membership - val members = members - val participants = participants - - for (group in groups) { - val groupMembers = members[group] - - var i = 0 - var j = 0 - var intersection = 0 - - // Compute the intersection of the group members and the current active members - while (i < groupMembers.size && j < activeKeys.size) { - val l = groupMembers[i] - val rightEntry = activeKeys[j] - val r = rightEntry.id - - if (l < r) { - i++ - } else if (l > r) { - j++ - } else { - if (++intersection > 1) { - rightEntry.addGroup(group) - } else { - participants.add(rightEntry) - } - - i++ - j++ - } - } - - while (true) { - val participant = participants.poll() ?: break - - if (intersection <= 1) { - participant.removeGroup(group) - } else { - participant.addGroup(group) - } - } - } - } - } - - /** - * An interference key. - * - * @param id The identifier of the member. - */ - private class InterferenceMemberImpl( - @JvmField val id: Int, - private val domain: InterferenceDomainImpl, - @JvmField val membership: IntArray, - private val members: Array<IntArray>, - private val targets: DoubleArray, - private val scores: DoubleArray - ) : VmInterferenceMember, Comparable<InterferenceMemberImpl> { - /** - * The active groups to which the key belongs. - */ - private var groups: IntArray = IntArray(2) - private var groupsSize: Int = 0 - - /** - * The number of users of the interference key. - */ - private var refCount: Int = 0 - - override fun activate() { - if (refCount++ <= 0) { - domain.join(this) - } - } - - override fun deactivate() { - if (--refCount <= 0) { - domain.leave(this) - } - } - - override fun apply(random: SplittableRandom, load: Double): Double { - val groupsSize = groupsSize - - if (groupsSize == 0) { - return 1.0 - } - - val groups = groups - val targets = targets - - var low = 0 - var high = groupsSize - 1 - var group = -1 - - // Perform binary search over the groups based on target load - while (low <= high) { - val mid = low + high ushr 1 - val midGroup = groups[mid] - val target = targets[midGroup] - - if (target < load) { - low = mid + 1 - group = midGroup - } else if (target > load) { - high = mid - 1 - } else { - group = midGroup - break - } - } - - return if (group >= 0 && random.nextInt(members[group].size) == 0) { - scores[group] - } else { - 1.0 - } - } - - /** - * Add an active group to this member. - */ - fun addGroup(group: Int) { - var groups = groups - val groupsSize = groupsSize - val pos = groups.binarySearch(group, toIndex = groupsSize) - - if (pos >= 0) { - return - } - - val idx = -pos - 1 - - if (groups.size == groupsSize) { - val newSize = groupsSize + (groupsSize shr 1) - groups = groups.copyOf(newSize) - this.groups = groups - } - - groups.copyInto(groups, idx + 1, idx, groupsSize) - groups[idx] = group - this.groupsSize += 1 - } - - /** - * Remove an active group from this member. - */ - fun removeGroup(group: Int) { - val groups = groups - val groupsSize = groupsSize - val pos = groups.binarySearch(group, toIndex = groupsSize) - - if (pos < 0) { - return - } - - groups.copyInto(groups, pos, pos + 1, groupsSize) - this.groupsSize -= 1 - } - - override fun compareTo(other: InterferenceMemberImpl): Int = id.compareTo(other.id) - } } diff --git a/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceProfile.kt b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceProfile.kt new file mode 100644 index 00000000..004dbd07 --- /dev/null +++ b/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/kernel/interference/VmInterferenceProfile.kt @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2022 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.simulator.compute.kernel.interference + +/** + * A profile of a particular virtual machine describing its interference pattern with other virtual machines. + * + * @param model The model to which this profile belongs. + * @property id The identifier of the profile inside the model. + * @property membership The membership of the profile in the groups. + * @param members The members in the model. + * @param targets The targets in the model. + * @param scores The scores in the model. + */ +public class VmInterferenceProfile internal constructor( + private val model: VmInterferenceModel, + private val id: Int, + private val membership: IntArray, + private val members: Array<IntArray>, + private val targets: DoubleArray, + private val scores: DoubleArray +) { + /** + * Create a new [VmInterferenceMember] based on this profile for the specified [domain]. + */ + internal fun newMember(domain: VmInterferenceDomain): VmInterferenceMember { + return VmInterferenceMember(domain, model, id, membership, members, targets, scores) + } + + override fun toString(): String = "VmInterferenceProfile[id=$id]" +} diff --git a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorTest.kt b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorTest.kt index 23d832e8..d401f8b5 100644 --- a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorTest.kt +++ b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimFairShareHypervisorTest.kt @@ -79,7 +79,7 @@ internal class SimFairShareHypervisorTest { val platform = FlowEngine(coroutineContext, clock) val machine = SimBareMetalMachine(platform, model, SimplePowerDriver(ConstantPowerModel(0.0))) val random = SplittableRandom(1) - val hypervisor = SimFairShareHypervisor(platform, PerformanceScalingGovernor(), random) + val hypervisor = SimFairShareHypervisor(platform, random, PerformanceScalingGovernor()) launch { machine.runWorkload(hypervisor) @@ -131,7 +131,7 @@ internal class SimFairShareHypervisorTest { platform, model, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimFairShareHypervisor(platform, null, random) + val hypervisor = SimFairShareHypervisor(platform, random, null) launch { machine.runWorkload(hypervisor) @@ -171,7 +171,7 @@ internal class SimFairShareHypervisorTest { val platform = FlowEngine(coroutineContext, clock) val machine = SimBareMetalMachine(platform, model, SimplePowerDriver(ConstantPowerModel(0.0))) val random = SplittableRandom(1) - val hypervisor = SimFairShareHypervisor(platform, null, random) + val hypervisor = SimFairShareHypervisor(platform, random, null) assertDoesNotThrow { launch { @@ -195,14 +195,13 @@ internal class SimFairShareHypervisorTest { .addGroup(targetLoad = 0.0, score = 0.6, members = setOf("a", "c")) .addGroup(targetLoad = 0.1, score = 0.8, members = setOf("a", "n")) .build() - val interferenceDomain = interferenceModel.newDomain() - val platform = FlowEngine(coroutineContext, clock) + val engine = FlowEngine(coroutineContext, clock) val machine = SimBareMetalMachine( - platform, model, SimplePowerDriver(ConstantPowerModel(0.0)) + engine, model, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimFairShareHypervisor(platform, null, random) + val hypervisor = SimFairShareHypervisor(engine, random, null) val duration = 5 * 60L val workloadA = @@ -230,12 +229,12 @@ internal class SimFairShareHypervisorTest { coroutineScope { launch { - val vm = hypervisor.newMachine(model, interferenceDomain.getMember("a")) - vm.runWorkload(workloadA) + val vm = hypervisor.newMachine(model) + vm.runWorkload(workloadA, meta = mapOf("interference-model" to interferenceModel.getProfile("a")!!)) hypervisor.removeMachine(vm) } - val vm = hypervisor.newMachine(model, interferenceDomain.getMember("b")) - vm.runWorkload(workloadB) + val vm = hypervisor.newMachine(model) + vm.runWorkload(workloadB, meta = mapOf("interference-model" to interferenceModel.getProfile("b")!!)) hypervisor.removeMachine(vm) } diff --git a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorTest.kt b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorTest.kt index 9471f548..9b31acf4 100644 --- a/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorTest.kt +++ b/opendc-simulator/opendc-simulator-compute/src/test/kotlin/org/opendc/simulator/compute/kernel/SimSpaceSharedHypervisorTest.kt @@ -77,7 +77,7 @@ internal class SimSpaceSharedHypervisorTest { val engine = FlowEngine(coroutineContext, clock) val machine = SimBareMetalMachine(engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0))) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(engine, null, random) + val hypervisor = SimSpaceSharedHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } val vm = hypervisor.newMachine(machineModel) @@ -100,7 +100,7 @@ internal class SimSpaceSharedHypervisorTest { val engine = FlowEngine(coroutineContext, clock) val machine = SimBareMetalMachine(engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0))) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(engine, null, random) + val hypervisor = SimSpaceSharedHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } yield() @@ -125,7 +125,7 @@ internal class SimSpaceSharedHypervisorTest { engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(engine, null, random) + val hypervisor = SimSpaceSharedHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } yield() @@ -147,7 +147,7 @@ internal class SimSpaceSharedHypervisorTest { engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(engine, null, random) + val hypervisor = SimSpaceSharedHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } yield() @@ -175,7 +175,7 @@ internal class SimSpaceSharedHypervisorTest { val engine = FlowEngine(coroutineContext, clock) val machine = SimBareMetalMachine(engine, machineModel, SimplePowerDriver(ConstantPowerModel(0.0))) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(engine, null, random) + val hypervisor = SimSpaceSharedHypervisor(engine, random, null) launch { machine.runWorkload(hypervisor) } yield() @@ -200,7 +200,7 @@ internal class SimSpaceSharedHypervisorTest { interpreter, machineModel, SimplePowerDriver(ConstantPowerModel(0.0)) ) val random = SplittableRandom(1) - val hypervisor = SimSpaceSharedHypervisor(interpreter, null, random) + val hypervisor = SimSpaceSharedHypervisor(interpreter, random, null) launch { machine.runWorkload(hypervisor) } yield() |