<commit_before># Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012, 2013 ETH Zurich.

# Import graphviz
import sys
sys.path.append('..')
sys.path.append('/usr/lib/graphviz/python/')
sys.path.append('/usr/lib64/graphviz/python/')
import gv
import logging

# Import pygraph
from pygraph.classes.graph import graph
from pygraph.classes.digraph import digraph
from pygraph.algorithms.searching import breadth_first_search
from pygraph.readwrite.dot import write
from pygraph.algorithms.minmax import shortest_path
from pygraph.algorithms.minmax import minimal_spanning_tree

# Import own code
import evaluate
import model
import helpers
from algorithms import binary_tree, sequential, merge_graphs
import overlay

class Cluster(overlay.Overlay):
    """
    Build a cluster topology for a model

    """
    
    def __init__(self, mod):
        """
        Initialize the clustering algorithm
        """
        super(Cluster, self).__init__(mod)
        
    def get_name(self):
        return "cluster"

    def _build_tree(self, g):
        """
        Algorithm to build the cluster tree.
        This algorithm uses the list of coordinators for :py:func:`overlay.get_coordinators`

        :param graph g: Graph for which to build the cluster tree.

        """
        coords = self.get_coordinators()

        # Build NUMA node graph with weights first
        g_numa = digraph()
        for c in coords:
            g_numa.add_node(c)
            for co in self.get_coordinators():
                if co<c:
                    weight = self.mod.get_graph().edge_weight((c, co))
                    g_numa.add_edge((c, co), weight)
                    logging.info(("Adding edge to NUMA node %d %d, "
                                  "with weight %d") % (c, co, weight))

        # Print graph
        helpers.output_graph(g_numa, 'cluster_numa', 'dot')

        # Now: find a tree for this graph
        # Observation: Machines today typically don't have more than 8 nodes
        # core 0 sends one message "across" the machine, all others: MST

        # max-hops: 3
        # core 0 histogram (question: why would we start at 0?)
        # - 1 hops: 2
        # - 2 hops: 2
        # - 3 hops: 3
        # core 2 histogram
        # - 1 hops: 4
        # - 2 hops: 2
        # - 3 hops: 1

        # might be able to do some clustering: split up nodes such
        # that half of them are in one cluster afterwards, the the
        # other half in another. Split them up such that the number of
        # links connecting the two clusters is minimal. Trying this
        # bruteforce would require n! / ((n/2)!) I think .. 

        # I think it might be best to cust construct a binary-tree!
        # except for contention
        # but if we send a message far away, with many hops, that is kind of stupid (or is it?)

        g_outer = binary_tree(g_numa)
        
        for c in self.get_coordinators():
            numa_node = [ n for n in self.mod.get_numa_node(c) if n in g.nodes() ]
            g_simple = sequential(self.mod.get_graph(), numa_node, c)
            g_outer = merge_graphs(g_simple, g_outer)
            print "%s" % str(numa_node)

        helpers.output_graph(g_outer, 'cluster_outer_bin', 'neato')
        return g_outer<commit_msg>cluster: keep cross-NUMA edges first when merging graphs<commit_after># Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012, 2013 ETH Zurich.

# Import graphviz
import sys
sys.path.append('..')
sys.path.append('/usr/lib/graphviz/python/')
sys.path.append('/usr/lib64/graphviz/python/')
import gv
import logging

# Import pygraph
from pygraph.classes.graph import graph
from pygraph.classes.digraph import digraph
from pygraph.algorithms.searching import breadth_first_search
from pygraph.readwrite.dot import write
from pygraph.algorithms.minmax import shortest_path
from pygraph.algorithms.minmax import minimal_spanning_tree

# Import own code
import evaluate
import model
import helpers
from algorithms import binary_tree, sequential, merge_graphs
import overlay

class Cluster(overlay.Overlay):
    """
    Build a cluster topology for a model

    """
    
    def __init__(self, mod):
        """
        Initialize the clustering algorithm
        """
        super(Cluster, self).__init__(mod)
        
    def get_name(self):
        return "cluster"

    def _build_tree(self, g):
        """
        Algorithm to build the cluster tree.
        This algorithm uses the list of coordinators for :py:func:`overlay.get_coordinators`

        :param graph g: Graph for which to build the cluster tree.

        """

        print '--------------------------------------------------'
        print '-- BUILD CLUSTER TOPLOGY'
        print '--------------------------------------------------'

        coords = self.get_coordinators()

        # Build NUMA node graph with weights first
        g_numa = digraph()
        for c in coords:
            g_numa.add_node(c)
            for co in coords:
                if co<c:
                    weight = self.mod.get_graph().edge_weight((c, co))
                    g_numa.add_edge((c, co), weight)
                    logging.info(("Adding edge to NUMA node %d %d, "
                                  "with weight %d") % (c, co, weight))

        # Print graph
        helpers.output_graph(g_numa, 'cluster_numa', 'dot')

        # Outer NUMA graph
        g_outer = binary_tree(g_numa)

        for c in self.get_coordinators():
            numa_node = [ n for n in self.mod.get_numa_node(c) if n in g.nodes() ]
            g_simple = sequential(self.mod.get_graph(), numa_node, c)
            g_outer = merge_graphs(g_outer, g_simple)
            print "%s" % str(numa_node)

        helpers.output_graph(g_outer, 'cluster_outer_bin', 'neato')
        return g_outer
{'fraction_non_alphanumeric': 0.10602659298912105, 'fraction_numerical': 0.013641858055603523, 'mean_word_length': 2.1512513601741023, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2161255', 'n_tokens_mistral': 1815, 'n_tokens_neox': 1661, 'n_words': 547}