clustering.py

import os
import time
import shutil
import sys
sys.path.append('./utils')
sys.path.append('../../FormatTranslators/src')

from math import sqrt
from FormatTranslators import Port
from FormatTranslators import Macro
from FormatTranslators import MacroPin
import collections
import sortedcontainers

class Vertex:
    def __init__(self, vertex_id, name, type, x, y, width, height):
        self.vertex_id = vertex_id
        self.name = name
        self.type = type
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.orient = "N"
        self.group_id = -1
        self.fanouts = set()
        self.macro_pins = set()  # only for macros
        self.group_fanouts = sortedcontainers.SortedSet()

class Clustering:
    def __init__(self, design, src_dir, fixed_file, n_cols = 27, n_rows = 23,
                 global_net_threshold = 500,
                 Nparts = 500, setup_file = "setup.tcl",
                 openroad_exe = "openroad"):
        """
        parameter: design,  help="design_name: ariane, MegaBoom_x2 ", type = str
        parameter: src_dir, help="directory for source codes", type = str
        parameter: fixed_file, help="fixed file generated by grouping", type = str
        parameter: global_net_threshold, help="large net threshold", type = int
        parameter: n_cols, n_rows from Gridding codes
        parameter: Nparts,  help = "number of clusters (only for hmetis, default  = 500)", type = int
        parameter: setup_file, help = "setup file for openroad (default = setup.tcl)", type = str
        """
        # initialize parameters
        self.design = design
        self.src_dir = src_dir
        self.fixed_file = fixed_file
        self.merge_threshold = 0.0
        self.breakup_threshold = 0.0
        self.closeness = 0.0
        self.global_net_threshold = global_net_threshold
        self.Nparts = Nparts
        self.setup_file = setup_file
        self.n_cols = n_cols
        self.n_rows = n_rows
        self.soft_macro_width = 0.0
        self.floorplan_width = 0.0
        self.floorplan_height = 0.0

        # Specify the location of hmetis exe and openroad exe and other utilities
        self.hmetis_exe = src_dir + "/utils/hmetis"
        self.openroad_exe = openroad_exe
        self.extract_hypergraph_file  = src_dir + "/utils/extract_hypergraph.tcl"

        # set up temp report directory
        rpt_dir = os.getcwd() + "/rtl_mp"
        self.hypergraph_file = rpt_dir + "/" + design + ".hgr"
        self.instance_name_file = self.hypergraph_file + ".vertex"
        self.outline_file = self.hypergraph_file + ".outline"
        self.pb_netlist_file = os.getcwd() + "/" + design + ".pb.txt"
        self.plc_file = os.getcwd() + "/" + design + ".plc"

        self.vertices = []
        self.hyperedges = []

        self.fixed_group_id = 0
        self.group_id_list = []
        self.group_id = 0

        # read the netlist information
        self.GenerateHypergraph() # Extract netlist information from lef/def/v
        self.hMetisPartitioner()  # Partition the hypergraph
        self.BreakClusters()  # Break clusters spreading apart
        while not self.MergeClusters():  # Merge clusters
            pass
        print("[INFO] After merge :  num_clusters = ", len(self.group_id_list))
        self.GenerateProtocolBufferNetlist()
        self.WritePlacementFile()

    def AddMacroPinToMacro(self, macro_pin_vertex_id):
        if (self.vertices[macro_pin_vertex_id].type != "macro_pin"):
            return

        macro_name = ""
        items = self.vertices[macro_pin_vertex_id].name.split('/')
        for i in range(len(items) - 1):
            macro_name += items[i] + '/'
        macro_name = macro_name[:-1]

        for vertex in self.vertices:
            if (vertex.name == macro_name):
                vertex.fanouts.add(macro_pin_vertex_id)
                return

    def GenerateHypergraph(self):
        # Extract hypergraph from netlist
        temp_file = os.getcwd() + "/extract_hypergraph.tcl"
        cmd = "cp " + self.setup_file + " " + temp_file
        os.system(cmd)

        with open(self.extract_hypergraph_file) as f:
            content = f.read().splitlines()
        f.close()

        f = open(temp_file, "a")
        f.write("\n")
        for line in content:
            f.write(line + "\n")
        f.close()

        cmd = self.openroad_exe + " " + temp_file
        os.system(cmd)

        cmd = "rm " + temp_file
        os.system(cmd)

        # read vertices
        with open(self.instance_name_file) as f:
            content = f.read().splitlines()
        f.close()

        for i in range(len(content)):
            items = content[i].split()
            self.vertices.append(Vertex(i, items[0], items[1], float(items[2]), float(items[3]), float(items[4]), float(items[5])))
            if (self.vertices[-1].type == "macro"):
                self.vertices[-1].orient = items[6]

        # read hyperedges
        with open(self.hypergraph_file) as f:
            content = f.read().splitlines()
        f.close()

        items = content[0].split()
        num_hyperedges = int(items[0])
        num_vertices   = int(items[1])

        for i in range(num_hyperedges):
            items = content[i+1].split()
            # ignore all the global nets
            if (len(items) > self.global_net_threshold or len(items) == 1):
                continue
            hyperedge = [int(item) - 1 for item in items]
            self.hyperedges.append(hyperedge)
            self.AddMacroPinToMacro(hyperedge[0])
            for i in range(1, len(hyperedge)):
                self.vertices[hyperedge[0]].fanouts.add(hyperedge[i])

        f = open(self.hypergraph_file, "w")
        line = str(len(self.hyperedges)) + " " + str(len(self.vertices)) + "\n"
        f.write(line)
        for hyperedge in self.hyperedges:
            line = ""
            for vertex in hyperedge:
                line += str(vertex + 1) + " "
            f.write(line + "\n")
        f.close()

        # read boundary information
        with open(self.outline_file) as f:
            content = f.read().splitlines()
        f.close()

        items = content[0].split()
        floorplan_lx = float(items[0])
        floorplan_ly = float(items[1])
        floorplan_ux = float(items[2])
        floorplan_uy = float(items[3])

        canvas_width = floorplan_ux - floorplan_lx
        canvas_height = floorplan_uy - floorplan_ly
        self.floorplan_width = canvas_width
        self.floorplan_height = canvas_height

        self.breakup_threshold = sqrt(canvas_width * canvas_height / 16.0)
        self.closeness = self.breakup_threshold / 2.0
        self.soft_macro_width = canvas_width / self.n_cols

        self.fixed_group_id = -1
        with open(self.fixed_file) as f:
            content = f.read().splitlines()
        f.close()

        for i in range(len(content)):
            group_id = int(content[i])
            self.fixed_group_id = max(self.fixed_group_id, group_id)
            self.vertices[i].group_id = group_id

        self.fixed_group_id += 1
        self.Nparts += self.fixed_group_id

        print("[INFO] Breakup threshold : ", self.breakup_threshold)
        print("[INFO] Merge closeness : ", self.closeness)

    def hMetisPartitioner(self):
        # Partitioning the hypergraph using hmetis
        # The parameter configuration is the same as Google Brain paper
        # UBfactor = 5
        # Nruns    = 10
        # CType    = 5
        # RType    = 3
        # Vcycle   = 3
        # The random seed is 0 by default (in our implementation)
        # We use the hMetis C++ API to implement hMetis
        cmd = self.hmetis_exe + " " + self.hypergraph_file + " "
        cmd += self.fixed_file + " "
        cmd += str(self.Nparts) + " 5 10 5 3 3 0 0"
        os.system(cmd)

        solution_file = self.hypergraph_file + ".part." + str(self.Nparts)
        # read solution vector
        with open(solution_file) as f:
            content = f.read().splitlines()
        f.close()

        for i in range(len(self.vertices)):
            if (self.vertices[i].group_id > -1):
                continue
            group_id = int(content[i]) + self.fixed_group_id
            self.vertices[i].group_id = group_id

        for vertex in self.vertices:
            group_id = vertex.group_id
            self.group_id = max(self.group_id, group_id)
            if group_id not in self.group_id_list:
                self.group_id_list.append(group_id)

        self.merge_threshold = len(self.vertices) // len(self.group_id_list) // 4
        print("[INFO] Merge threshold : ", self.merge_threshold)


    def GetBoundingBox(self, group_id):
        lx = 1e9
        ly = 1e9
        ux = -1e9
        uy = -1e9

        for vertex in self.vertices:
            if (vertex.group_id == group_id):
                lx = min(lx, vertex.x)
                ly = min(ly, vertex.y)
                ux = max(ux, vertex.x)
                uy = max(uy, vertex.y)

        return [lx, ly, ux, uy]


    def GetWeightedCenter(self, group_id):
        x_weighted_sum = 0.0
        y_weighted_sum = 0.0
        divisor = 0.0
        for vertex in self.vertices:
            if (vertex.group_id == group_id):
                if (vertex.type != "stdcell"):
                    continue

                area = vertex.width * vertex.height
                x_weighted_sum += vertex.x * area
                y_weighted_sum += vertex.y * area
                divisor += area

        if divisor == 0.0:
            return 0.0, 0.0

        return x_weighted_sum / divisor, y_weighted_sum / divisor

    def Bucket(self, x, threshold, center, min_x, max_x):
        if (max_x - min_x < threshold):
            return 0

        if x > center:
            return int(0.5 + (x - center) / threshold)
        else:
            return int(-0.5 + (x - center) / threshold)


    def BreakClusters(self):
        # In this step, we break clusters which spread around the canvas.
        self.group_vertices = {  }
        for i in range(len(self.vertices)):
            group_id = self.vertices[i].group_id
            if group_id not in self.group_vertices:
                self.group_vertices[group_id] = [i]
            else:
                self.group_vertices[group_id].append(i)

        self.breakup_threshold = 400.006
        self.group_id_list.sort()
        for group_id in self.group_id_list:
            gcell_vs_group_id = {  }
            group_box = self.GetBoundingBox(group_id)
            if (group_box[2] - group_box[0] > self.breakup_threshold or
                    group_box[3] - group_box[1] > self.breakup_threshold):
                group_x, group_y = self.GetWeightedCenter(group_id)
                for vertex_id in self.group_vertices[group_id]:
                    vertex = self.vertices[vertex_id]
                    xb = self.Bucket(vertex.x, self.breakup_threshold, group_x, group_box[0], group_box[2])
                    yb = self.Bucket(vertex.y, self.breakup_threshold, group_y, group_box[1], group_box[3])

                    if xb == 0 and yb == 0:
                        continue

                    if (xb, yb) not in gcell_vs_group_id:
                        self.group_id += 1
                        gcell_vs_group_id[(xb, yb)] = self.group_id

                    self.vertices[vertex_id].group_id = gcell_vs_group_id[(xb, yb)]


        self.group_id_list = []
        for vertex in self.vertices:
            if vertex.group_id not in self.group_id_list:
                self.group_id_list.append(vertex.group_id)

        print("After break up clusters : ", len(self.group_id_list))


    def IsClose(self, group_loc_a, group_loc_b):
        dist = abs(group_loc_a[0] - group_loc_b[0])
        dist += abs(group_loc_a[1] - group_loc_b[1])
        return dist <= self.closeness



    def MergeClusters(self):
        # In this step, we merge small groups to the most adjacent group if they are
        # with a certain distance
        # self.merge_threshold is the minimum number of vertices in a group
        # self.closeness is the distance used to determine if two vertices are close or not
        adj_matrix = [0] * (self.group_id + 1) * (self.group_id + 1)
        for vertex in self.vertices:
            groups = set()
            groups.add(vertex.group_id)
            for vertex_id in vertex.fanouts:
                groups.add(self.vertices[vertex_id].group_id)
            for i in groups:
                for j in groups:
                    if i == j:
                        continue
                    adj_matrix[i * (self.group_id + 1) + j] += 1

        group_locs = [None] * (self.group_id + 1)
        for group_id in self.group_id_list:
            group_x, group_y = self.GetWeightedCenter(group_id)
            group_locs[group_id] = [group_x, group_y]

        group_size = [0] * (self.group_id + 1)
        for vertex in self.vertices:
            group_size[vertex.group_id] += 1


        group_vertices = [ [] for i in range(self.group_id + 1) ]
        for i in range(len(self.vertices)):
            group_vertices[self.vertices[i].group_id].append(i)

        finished = True
        # Going through the small clusters, find the highest adjacency group
        # within the self.closeness
        self.group_id_list.sort()
        for group_id in self.group_id_list:
            if (group_size[group_id] > self.merge_threshold):
                continue

            max_adj_grp = -1
            max_adj = 0
            for i in self.group_id_list:
                if (group_id == i):
                    continue
                # get number of connections
                adj = adj_matrix[i * (self.group_id + 1) + group_id]
                # check if connected
                if (adj == 0):
                    continue

                # check if close to each other
                if (self.IsClose(group_locs[group_id], group_locs[i]) == True and max_adj < adj):
                    max_adj = adj
                    max_adj_grp = i

            if (max_adj_grp > -1):
                for vertex_id in group_vertices[group_id]:
                    self.vertices[vertex_id].group_id = max_adj_grp
                    group_vertices[max_adj_grp].append(vertex_id)
                    group_size[max_adj_grp] += 1

                group_size[group_id] = 0
                group_vertices[group_id] = [  ]
                if (group_size[max_adj_grp] <= self.merge_threshold):
                    finished = False

        self.group_id_list = []
        for vertex in self.vertices:
            if vertex.group_id not in self.group_id_list:
                self.group_id_list.append(vertex.group_id)


        return finished




    def AddMacroPins(self, macro_pin_vertex_id):
        if (self.vertices[macro_pin_vertex_id].type != "macro_pin"):
            return

        macro_name = ""
        items = self.vertices[macro_pin_vertex_id].name.split('/')
        for i in range(len(items) - 1):
            macro_name += items[i] + '/'
        macro_name = macro_name[:-1]

        for vertex in self.vertices:
            if (vertex.name == macro_name):
                vertex.macro_pins.add(macro_pin_vertex_id)
                return

    def GenerateProtocolBufferNetlist(self):
        self.soft_macro_area_bloating_ratio = 2.0
        # Get the bounding box first
        die_lx = 1e9
        die_ly = 1e9
        die_ux = 0.0
        die_uy = 0.0

        for vertex in self.vertices:
            die_lx = min(die_lx, vertex.x)
            die_ly = min(die_ly, vertex.y)
            die_ux = max(die_ux, vertex.x)
            die_uy = max(die_uy, vertex.y)
            self.AddMacroPins(vertex.vertex_id)

        # check all the ports
        self.ports = []
        self.macros = []
        for vertex in self.vertices:
            if vertex.type != "port":
                continue

            side = "NONE"
            if (vertex.x == die_lx):
                side = "LEFT"
            elif (vertex.x == die_ux):
                side = "RIGHT"
            elif (vertex.y == die_ly):
                side = "BOTTOM"
            else:
                side = "TOP"

            sinks = set()
            for vertex_id in vertex.fanouts:
                if (self.vertices[vertex_id].type != "stdcell"):
                    continue
                sinks.add("Grp_" + str(self.vertices[vertex_id].group_id) + "/Pinput")

            self.ports.append(Port(vertex.name, vertex.x, vertex.y, side))
            self.ports[-1].AddSinks(sinks)

        # check each hard macro and its macro pins
        for vertex in self.vertices:
            if vertex.type != "macro":
                continue

            macro_x = vertex.x
            macro_y = vertex.y
            macro_name = vertex.name
            self.macros.append(Macro(vertex.name, vertex.width, vertex.height, macro_x, macro_y, vertex.orient))

            # check all the macro pins
            for macro_pin_id in vertex.macro_pins:
                pin_vertex = self.vertices[macro_pin_id]
                macro_pin = MacroPin(pin_vertex.name, macro_name, pin_vertex.x - vertex.x, pin_vertex.y - vertex.y, "MACRO", pin_vertex.x, pin_vertex.y)
                sinks = set()
                for vertex_id in pin_vertex.fanouts:
                    if (self.vertices[vertex_id].type != "stdcell"):
                        continue
                    sinks.add("Grp_" + str(self.vertices[vertex_id].group_id) + "/Pinput")
                macro_pin.AddSinks(sinks)
                self.macros[-1].AddOutputPin(macro_pin)


        self.soft_macros = []
        # check all the soft macros
        std_cell_groups = {  }
        for vertex in self.vertices:
            if vertex.type != "stdcell":
                continue
            if vertex.group_id not in std_cell_groups:
                std_cell_groups[vertex.group_id] = [vertex.vertex_id]
            else:
                std_cell_groups[vertex.group_id].append(vertex.vertex_id)

        std_cell_groups = dict(sorted(std_cell_groups.items()))

        # convert the fanouts into group fanouts
        for vertex in self.vertices:
            if (vertex.type != "stdcell"):
                continue
            for vertex_id in vertex.fanouts:
                if (self.vertices[vertex_id].type != "stdcell"):
                    vertex.group_fanouts.add(self.vertices[vertex_id].name)
                elif (self.vertices[vertex_id].group_id != vertex.group_id):
                    vertex.group_fanouts.add("Grp_" + str(self.vertices[vertex_id].group_id) + "/Pinput")

        for group_id, vertices_list in std_cell_groups.items():
            group_x, group_y = self.GetWeightedCenter(group_id)
            macro_name = 'Grp_' + str(group_id)
            area = 0.0
            for vertex_id in vertices_list:
                area += self.vertices[vertex_id].width * self.vertices[vertex_id].height
            area *= self.soft_macro_area_bloating_ratio
            macro_height = area / self.soft_macro_width
            self.soft_macros.append(Macro(macro_name, self.soft_macro_width, macro_height, group_x, group_y))
            self.soft_macros[-1].IsSoft()  # set to soft macro
            # add the input pins
            self.soft_macros[-1].AddInputPin(MacroPin(macro_name + "/Pinput", macro_name, 0.0, 0.0, "macro", group_x, group_y))
            # add output pins based on weight
            single_sink = sortedcontainers.SortedDict()
            p_index = 0
            for vertex_id in vertices_list:
                group_fanouts = self.vertices[vertex_id].group_fanouts
                if (len(group_fanouts) == 0):
                    continue
                elif (len(group_fanouts) == 1):
                    fanout = list(group_fanouts)[0]
                    if fanout not in single_sink:
                        single_sink[fanout] = 1
                    else:
                        single_sink[fanout] += 1
                else:
                    pin_name = "Grp_" + str(group_id) + "/Poutput_multi_" + str(p_index)
                    p_index += 1
                    macro_pin = MacroPin(pin_name, macro_name, 0.0, 0.0, "macro", group_x, group_y)
                    macro_pin.AddSinks(group_fanouts)
                    self.soft_macros[-1].AddOutputPin(macro_pin)

            p_index = 0
            single_sinks = dict(sorted(single_sink.items(), reverse = True))
            for pin, weight in single_sink.items():
                pin_name = "Grp_" + str(group_id) + "/Poutput_single_" + str(p_index)
                p_index += 1
                macro_pin = MacroPin(pin_name, macro_name, 0.0, 0.0, "macro", group_x, group_y)
                macro_pin.AddSink(pin)
                macro_pin.SpecifyWeight(weight)
                self.soft_macros[-1].AddOutputPin(macro_pin)

        self.WriteProtocolBufferNetlist()

    def WriteProtocolBufferNetlist(self):
        f = open(self.pb_netlist_file, "w")
        line  = "node {\n"
        line += '  name: "__metadata__"\n'
        line += '  attr {\n'
        line += '    key: "soft_macro_area_bloating_ratio"\n'
        line += '    value {\n'
        line += '      f: ' + str(self.soft_macro_area_bloating_ratio) + '\n'
        line += '    }\n'
        line += '  }\n'
        line += '}\n'
        f.write(line)
        for port in self.ports:
            f.write(str(port))

        for macro in self.macros:
            f.write(str(macro))
            for macro_pin in macro.GetPins():
                f.write(str(macro_pin))

        for macro in self.soft_macros:
            f.write(str(macro))
            for macro_pin in macro.GetOutputPins():
                f.write(str(macro_pin))
            for macro_pin in macro.GetInputPins():
                f.write(str(macro_pin))

        f.close()

    def WritePlacementFile(self):
        f = open(self.plc_file, "w")
        line = "# Columns : " + str(self.n_cols) + "  Rows : " + str(self.n_rows)  + "\n"
        line += "# Width : " + str(round(self.floorplan_width, 2)) + "  Height : " + str(round(self.floorplan_height, 2)) + "\n"
        line += "# Area : " + str(round(self.floorplan_width * self.floorplan_height, 2)) + "\n"
        f.write(line)


        node_index = 0
        line = "# node_index x y orientation fixed\n"
        for port in self.ports:
            line += str(node_index) + " " + str(round(port.x, 2)) + " " + str(round(port.y, 2)) + " - 0\n"
            node_index += 1
        num_hard_macro_pins = 0
        for macro in self.macros:
            line += str(node_index) + " " + str(round(macro.x, 2)) + " " + str(round(macro.y, 2)) + " " + macro.orientation + " 0\n"
            node_index += 1
            for pin in macro.GetPins():
                node_index += 1
                num_hard_macro_pins += 1

        num_soft_macro_pins = 0
        for macro in self.soft_macros:
            line += str(node_index) + " " + str(round(macro.x, 2)) + " " + str(round(macro.y, 2)) + " " + macro.orientation + " 0\n"
            node_index += 1
            for pin in macro.GetPins():
                node_index += 1
                num_soft_macro_pins += 1
        f.write("# Counts of node types:\n")
        f.write("# HARD_MACROs     :       " + str(len(self.macros)) + "\n")
        f.write("# HARD_MACRO_PINs :       " + str(num_hard_macro_pins) + "\n")
        f.write("# MACROs          :       " + str(len(self.macros) + len(self.soft_macros)) + "\n")
        f.write("# MACRO_PINs      :       " + str(num_hard_macro_pins + num_soft_macro_pins) + "\n")
        f.write("# PORTs           :       " + str(len(self.ports)) + "\n")
        f.write("# SOFT_MACROs     :       " + str(len(self.soft_macros)) + "\n")
        f.write("# SOFT_MACRO_PINs :       " + str(num_soft_macro_pins)  + "\n")
        f.write("# STDCELLs        :        0\n")
        f.write(line)
        f.close()