Source code for pypdevs.allocators.greedyAllocator
# Copyright 2014 Modelling, Simulation and Design Lab (MSDL) at
# McGill University and the University of Antwerp (http://msdl.cs.mcgill.ca/)
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from collections import defaultdict
[docs]class GreedyAllocator(object):
"""
Allocate all models in a greedy manner: make the most heavy link local and extend from there on until an average load is reached.
"""
[docs] def allocate(self, models, edges, nr_nodes, total_activities):
"""
Calculate allocations for the nodes, using the information provided.
:param models: the models to allocte
:param edges: the edges between the models
:param nr_nodes: the number of nodes to allocate over. Simply an upper bound!
:param total_activities: activity tracking information from each model
:returns: allocation that was found
"""
# Run over all edges to create the nodes and link in their edges
nodes = {}
remaining_edges = set()
to_alloc = set()
for source in edges:
for destination in edges[source]:
# A connection from 'source' to 'destination'
edge = edges[source][destination]
nodes.setdefault(source, []).append((edge, destination))
nodes.setdefault(destination, []).append((edge, source))
remaining_edges.add((edge, source, destination))
to_alloc.add(destination)
to_alloc.add(source)
# OK, nodes are constructed
# Allocate 1 node too much for spilling
nr_nodes += 1
# Find average activity (our target)
avg_activity = sum([total_activities[i] for i in total_activities]) / nr_nodes
# Get the strongest edge
alloc_node = 0
node_load = []
allocation = {}
allocation_rev = defaultdict(set)
while alloc_node < (nr_nodes - 1):
while remaining_edges:
max_edge = max(remaining_edges)
remaining_edges.remove(max_edge)
edge_weight, source, destination = max_edge
if source in to_alloc and destination in to_alloc:
break
else:
break
activity_source = total_activities[source.model_id]
activity_destination = total_activities[destination.model_id]
node_load.append(activity_source + activity_destination)
allocation[source.model_id] = alloc_node
allocation[destination.model_id] = alloc_node
allocation_rev[alloc_node].add(source)
allocation_rev[alloc_node].add(destination)
to_alloc.remove(source)
to_alloc.remove(destination)
while node_load[alloc_node] < average_activity:
edge_search = []
for edge in remaining_edges:
if ((edge[1] in allocation_rev[alloc_node] and
edge[2] in to_alloc) or
(edge[2] in allocation_rev[alloc_node] and
edge[1] in to_alloc)):
edge_search.append(edge)
if not edge_search:
break
# Allocate some more nodes
max_edge = max(edge_search)
remaining_edges.remove(max_edge)
edge_weight, source, destination = max_edge
# Ok, this is an unbound connection, so add it
if source in to_alloc:
to_alloc.remove(source)
allocation[source.model_id] = alloc_node
allocation_rev[alloc_node].add(source.model_id)
node_load[alloc_node] += total_activities[source.model_id]
if destination in to_alloc:
to_alloc.remove(destination)
allocation[destination.model_id] = alloc_node
allocation_rev[alloc_node].add(destination.model_id)
node_load[alloc_node] += total_activities[destination.model_id]
alloc_node += 1
# All unassigned nodes are for the spill node
# Undo our spilling node
while to_alloc:
changes = False
n = list(to_alloc)
for model in n:
options = set()
for oport in model.OPorts:
for oline, _ in oport.routing_outline:
location = oline.host_DEVS.location
if oline.host_DEVS.location is not None:
options.add((node_load[location], location))
for iport in model.IPorts:
for iline in oport.routing_inline:
location = iline.host_DEVS.location
if iline.host_DEVS.location is not None:
options.add((node_load[location], location))
if not options:
continue
# Get the best option
_, loc = min(options)
node_load[loc] += total_activities[model.model_id]
allocation[model.model_id] = loc
allocation_rev[loc].add(model.model_id)
to_alloc.remove(model)
if not changes:
# An iteration without changes, means that we loop forever
for m in to_alloc:
# Force an allocation to 0
allocation[m.model_id] = 0
# allocation_rev doesn't need to be updated
break
return allocation
[docs] def getTerminationTime(self):
"""
Returns the time it takes for the allocator to make an 'educated guess' of the advised allocation.
This time will not be used exactly, but as soon as the GVT passes over it. While this is not exactly
necessary, it avoids the overhead of putting such a test in frequently used code.
:returns: float -- the time at which to perform the allocations (and save them)
"""
return 10.0