| """ rr graph library that is not tied to the underlying serialization format |
| and provides simple fast lookup required to build real FPGA rr graph fabrics. |
| """ |
| |
| from __future__ import print_function |
| from collections import namedtuple |
| from enum import Enum |
| from .tracks import Track |
| from lib.rr_graph import channel2 |
| from lib import progressbar_utils |
| |
| |
| class SwitchType(Enum): |
| """Enumeration of allowed VPR switch type |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-switches-switch |
| """ # noqa: E501 |
| INVALID_SWITCH_TYPE = 0 |
| MUX = 1 |
| TRISTATE = 2 |
| PASS_GATE = 3 |
| SHORT = 4 |
| BUFFER = 5 |
| |
| |
| class NodeType(Enum): |
| """VPR Node type. This is a superset of Type in channel.py |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-nodes-node |
| """ # noqa: E501 |
| INVALID_NODE_TYPE = 0 |
| CHANX = 1 |
| CHANY = 2 |
| SOURCE = 3 |
| SINK = 4 |
| OPIN = 5 |
| IPIN = 6 |
| |
| |
| class NodeDirection(Enum): |
| """VPR Node Direction. This is a superset of Direction in channel.py |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-nodes-node |
| """ # noqa: E501 |
| NO_DIR = 0 |
| INC_DIR = 1 |
| DEC_DIR = 2 |
| BI_DIR = 3 |
| |
| |
| class PinType(Enum): |
| """Enum for PinClass type |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-blocks-pin_class |
| """ # noqa: E501 |
| NONE = 0 |
| OPEN = 1 |
| OUTPUT = 2 |
| INPUT = 3 |
| |
| |
| class ChannelList(namedtuple('ChannelList', 'index info')): |
| """VPR `x_list` and `y_list` tags in the channels |
| """ |
| |
| |
| class Channels(namedtuple( |
| 'Channels', 'chan_width_max x_min y_min x_max y_max x_list y_list')): |
| """Encapsulation for VPR channels tag |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-channel-channel |
| """ # noqa: E501 |
| |
| |
| class SwitchTiming(namedtuple('SwitchTiming', |
| 'r c_in c_out c_internal t_del')): |
| """Encapsulation for timing attributes of a VPR switch |
| see: https://vtr-verilog-to-routing.readthedocs.io/en/latest/arch/reference.html#switches |
| """ |
| |
| |
| class SwitchSizing(namedtuple('SwitchSizing', 'mux_trans_size buf_size')): |
| """Encapsulation for sizing attributes of a VPR switch |
| see: https://vtr-verilog-to-routing.readthedocs.io/en/latest/arch/reference.html#switches |
| """ |
| |
| |
| class Switch(namedtuple('Switch', 'id name type timing sizing')): |
| """Encapsulate VPR switch tag. Contains SwitchTiming and SwitchSizing tuples. |
| see: https://vtr-verilog-to-routing.readthedocs.io/en/latest/arch/reference.html#switches |
| """ |
| |
| |
| class SegmentTiming(namedtuple('SegmentTiming', 'r_per_meter c_per_meter')): |
| """Encapsulation for timing attributes of a VPR segment. |
| see: https://vtr-verilog-to-routing.readthedocs.io/en/latest/arch/reference.html#wire-segments |
| """ |
| |
| |
| class Segment(namedtuple('Segment', 'id name timing')): |
| """Encapsulate VPR segment tag. Contains SegmentTiming to encapsulate the timing attributes |
| see: https://vtr-verilog-to-routing.readthedocs.io/en/latest/arch/reference.html#wire-segments |
| """ |
| |
| |
| class Pin(namedtuple('Pin', 'ptc name')): |
| """Encapsulation for VPR Pin tag |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-blocks-pin |
| """ # noqa: E501 |
| |
| |
| class PinClass(namedtuple('PinClass', 'type pin')): |
| """Encapsulation for VPR PinClass tag |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-blocks-pin_class |
| """ # noqa: E501 |
| |
| |
| class BlockType(namedtuple('BlockType', 'id name width height pin_class')): |
| """Encapsulation for VPR BlockType tag |
| See: https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-blocks-block_type |
| """ # noqa: E501 |
| |
| |
| class GridLoc(namedtuple('GridLoc', |
| 'x y block_type_id width_offset height_offset')): |
| """ |
| """ |
| |
| |
| class NodeTiming(namedtuple('NodeTiming', 'r c')): |
| """https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-nodes-timing |
| """ |
| |
| |
| class NodeLoc(namedtuple('NodeLoc', 'x_low y_low x_high y_high side ptc')): |
| """https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-nodes-loc |
| """ |
| |
| |
| class NodeMetadata(namedtuple('NodeMetadata', |
| 'name x_offset y_offset z_offset value')): |
| """https://vtr-verilog-to-routing.readthedocs.io/en/latest/arch/reference.html#architecture-metadata |
| """ |
| |
| |
| class NodeSegment(namedtuple('NodeSegment', 'segment_id')): |
| """https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-nodes-segment |
| """ |
| |
| |
| class Node(namedtuple( |
| 'Node', 'id type direction capacity loc timing metadata segment')): |
| """https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-nodes-node |
| """ |
| |
| |
| class Edge(namedtuple('Edge', 'src_node sink_node switch_id metadata')): |
| """https://vtr-verilog-to-routing.readthedocs.io/en/latest/vpr/file_formats.html#tag-edges-edge |
| """ |
| |
| |
| class GraphInput(namedtuple('GraphInput', |
| 'switches segments block_types grid')): |
| """Top level encapsulation of input Graph |
| """ |
| |
| |
| def process_track(track): |
| channel_model = channel2.Channel(track) |
| channel_model.pack_tracks() |
| |
| return channel_model |
| |
| |
| class Graph(object): |
| """ Simple object for working with VPR RR graph. |
| |
| This class does not handle serialization. A format specific class handles |
| serdes takes. |
| """ |
| |
| def __init__( |
| self, |
| switches, |
| segments, |
| block_types, |
| grid, |
| nodes, |
| edges=None, |
| build_pin_edges=True |
| ): |
| self.switches = switches |
| self.next_switch_id = max(switch.id for switch in self.switches) + 1 |
| |
| self.switch_name_map = {} |
| self.delayless_switch = None |
| |
| for idx, switch in enumerate(self.switches): |
| assert idx == switch.id |
| assert switch.name not in self.switch_name_map |
| self.switch_name_map[switch.name] = switch.id |
| |
| assert '__vpr_delayless_switch__' in self.switch_name_map, self.switch_name_map.keys( |
| ) |
| self.delayless_switch = self.switch_name_map['__vpr_delayless_switch__' |
| ] |
| |
| self.segments = segments |
| self.segment_name_map = {} |
| |
| for idx, segment in enumerate(self.segments): |
| assert idx == segment.id |
| assert segment.name not in self.segment_name_map |
| self.segment_name_map[segment.name] = segment.id |
| |
| self.block_types = block_types |
| self.grid = grid |
| |
| self.tracks = [] |
| self.nodes = nodes |
| self.nodes.sort(key=lambda node: node.id) |
| self.edges = edges if edges is not None else [] |
| |
| # Map of (x, y) to GridLoc definitions. |
| self.loc_map = {} |
| |
| # Maps grid location and pin class index to node index |
| # (x, y, pin class idx) -> node_idx |
| self.loc_pin_class_map = {} |
| |
| # Maps grid location and pin index to node index |
| # (x, y, pin idx) -> [(node_idx, side)] |
| self.loc_pin_map = {} |
| |
| # Maps pin name to block type id and pin idx. |
| # pin name -> block type id, pin class idx, pin idx |
| self.pin_name_map = {} |
| |
| self.pin_ptc_to_name_map = {} |
| |
| # Create pin_name_map and sanity check block_types. |
| for idx, block_type in enumerate(self.block_types): |
| assert idx == block_type.id |
| for pin_class_idx, pin_class in enumerate(block_type.pin_class): |
| for pin in pin_class.pin: |
| assert pin.name not in self.pin_name_map |
| self.pin_name_map[ |
| pin.name] = (block_type.id, pin_class_idx, pin.ptc) |
| self.pin_ptc_to_name_map[(block_type.id, |
| pin.ptc)] = pin.name |
| |
| # Create mapping from grid locations and pins to nodes. |
| for idx, node in enumerate(self.nodes): |
| assert node.id == idx, (idx, node) |
| |
| if node.type in ( |
| NodeType.IPIN, |
| NodeType.OPIN, |
| ): |
| key = (node.loc.x_low, node.loc.y_low, node.loc.ptc) |
| if key not in self.loc_pin_map: |
| self.loc_pin_map[key] = [] |
| self.loc_pin_map[key].append((node.id, node.loc.side)) |
| |
| if node.type in ( |
| NodeType.SOURCE, |
| NodeType.SINK, |
| ): |
| key = (node.loc.x_low, node.loc.y_low, node.loc.ptc) |
| assert key not in self.loc_pin_class_map, ( |
| node, self.loc_pin_class_map[key] |
| ) |
| self.loc_pin_class_map[key] = node.id |
| |
| # Rebuild initial edges of IPIN -> SINK and SOURCE -> OPIN. |
| for loc in grid: |
| assert loc.block_type_id >= 0 and loc.block_type_id <= len( |
| self.block_types |
| ), loc.block_type_id |
| block_type = self.block_types[loc.block_type_id] |
| |
| key = (loc.x, loc.y) |
| assert key not in self.loc_map |
| self.loc_map[key] = loc |
| |
| for pin_class_idx, pin_class in enumerate(block_type.pin_class): |
| pin_class_node = self.loc_pin_class_map[ |
| (loc.x, loc.y, pin_class_idx)] |
| |
| # Skip building IPIN -> SINK and OPIN -> SOURCE graph if edges |
| # are not required. |
| if not build_pin_edges: |
| continue |
| |
| for pin in pin_class.pin: |
| for pin_node, _ in self.loc_pin_map[(loc.x, loc.y, |
| pin.ptc)]: |
| if pin_class.type == PinType.OUTPUT: |
| self.add_edge( |
| src_node=pin_class_node, |
| sink_node=pin_node, |
| switch_id=self.delayless_switch |
| ) |
| elif pin_class.type == PinType.INPUT: |
| self.add_edge( |
| src_node=pin_node, |
| sink_node=pin_class_node, |
| switch_id=self.delayless_switch, |
| ) |
| else: |
| assert False, (loc, pin_class) |
| |
| def _create_node( |
| self, |
| type, |
| direction, |
| loc, |
| segment, |
| timing, |
| capacity=1, |
| metadata=None, |
| ): |
| |
| if timing is None: |
| if type in (NodeType.CHANX, NodeType.CHANY): |
| timing = NodeTiming(r=1, c=1) |
| else: |
| timing = NodeTiming(r=0, c=0) |
| |
| self.nodes.append( |
| Node( |
| id=len(self.nodes), |
| type=type, |
| direction=direction, |
| capacity=capacity, |
| loc=loc, |
| timing=timing, |
| metadata=metadata, |
| segment=segment, |
| ) |
| ) |
| |
| return self.nodes[-1].id |
| |
| def get_segment_id_from_name(self, segment_name): |
| return self.segment_name_map[segment_name] |
| |
| def get_delayless_switch_id(self): |
| return self.delayless_switch |
| |
| def add_track( |
| self, |
| track, |
| segment_id, |
| capacity=1, |
| timing=None, |
| name=None, |
| ptc=None, |
| direction=NodeDirection.BI_DIR, |
| ): |
| """Take a Track and add node to the graph with supplimental data""" |
| |
| if track.direction == 'X': |
| node_type = NodeType.CHANX |
| elif track.direction == 'Y': |
| node_type = NodeType.CHANY |
| else: |
| assert False, track |
| |
| if name is not None: |
| metadata = [ |
| NodeMetadata( |
| name=name, |
| x_offset=0, |
| y_offset=0, |
| z_offset=0, |
| value='', |
| ) |
| ] |
| else: |
| metadata = None |
| |
| self.tracks.append( |
| self._create_node( |
| type=node_type, |
| direction=direction, |
| capacity=capacity, |
| loc=NodeLoc( |
| x_low=track.x_low, |
| y_low=track.y_low, |
| x_high=track.x_high, |
| y_high=track.y_high, |
| side=None, |
| ptc=ptc, |
| ), |
| timing=timing, |
| segment=NodeSegment(segment_id=segment_id), |
| metadata=metadata, |
| ) |
| ) |
| |
| return self.tracks[-1] |
| |
| def create_pin_name_from_tile_type_and_pin( |
| self, tile_type, port_name, pin_idx=0 |
| ): |
| return '{}.{}[{}]'.format(tile_type, port_name, pin_idx) |
| |
| def create_pin_name_from_tile_type_sub_tile_num_and_pin( |
| self, tile_type, sub_tile_num, port_name, pin_idx=0 |
| ): |
| return '{}[{}].{}[{}]'.format( |
| tile_type, sub_tile_num, port_name, pin_idx |
| ) |
| |
| def get_nodes_for_pin(self, loc, pin_name): |
| block_type_id, pin_class_idx, pin_idx = self.pin_name_map[pin_name] |
| grid_loc = self.loc_map[loc] |
| assert grid_loc.block_type_id == block_type_id |
| |
| return self.loc_pin_map[(loc[0], loc[1], pin_idx)] |
| |
| def _create_edge( |
| self, src_node, sink_node, switch_id, name=None, value='' |
| ): |
| assert src_node >= 0 and src_node < len(self.nodes), src_node |
| assert sink_node >= 0 and sink_node < len(self.nodes), sink_node |
| assert switch_id >= 0 and switch_id < len(self.switches), switch_id |
| |
| if name is not None: |
| metadata = [ |
| NodeMetadata( |
| name=name, x_offset=0, y_offset=0, z_offset=0, value=value |
| ) |
| ] |
| else: |
| metadata = None |
| |
| return Edge( |
| src_node=src_node, |
| sink_node=sink_node, |
| switch_id=switch_id, |
| metadata=metadata |
| ) |
| |
| def add_edge(self, src_node, sink_node, switch_id, name=None, value=''): |
| """Add Edge to the graph |
| |
| Appends a new edge to the graph and retruns the index in the edges list |
| """ |
| self.edges.append( |
| self._create_edge( |
| src_node=src_node, |
| sink_node=sink_node, |
| switch_id=switch_id, |
| name=name, |
| value=value |
| ) |
| ) |
| |
| return len(self.edges) - 1 |
| |
| def add_switch(self, switch): |
| """ Inner add_switch method. Do not invoke directly. |
| |
| This method adds a switch into the graph model. This method should |
| not be invoked directly, instead invoke add_switch on the serialization |
| graph object (e.g. rr_graph_xml.graph2.add_switch, etc). |
| |
| """ |
| |
| switch_dict = switch._asdict() |
| switch_dict['id'] = self.next_switch_id |
| self.next_switch_id += 1 |
| |
| switch = Switch(**switch_dict) |
| |
| assert switch.name not in self.switch_name_map |
| self.switch_name_map[switch.name] = switch.id |
| self.switches.append(switch) |
| |
| return switch.id |
| |
| def check_ptc(self): |
| for node in self.nodes: |
| assert node.loc.ptc is not None, node |
| |
| def set_track_ptc(self, track, ptc): |
| node_d = self.nodes[track]._asdict() |
| loc_d = self.nodes[track].loc._asdict() |
| assert loc_d['ptc'] is None |
| loc_d['ptc'] = ptc |
| node_d['loc'] = NodeLoc(**loc_d) |
| |
| self.nodes[track] = Node(**node_d) |
| |
| def create_channels(self, pad_segment, pool=None): |
| """ Pack tracks into channels and return Channels definition for tracks.""" |
| assert len(self.tracks) > 0 |
| |
| xs = [] |
| ys = [] |
| |
| for track in self.tracks: |
| track_node = self.nodes[track] |
| |
| xs.append(track_node.loc.x_low) |
| xs.append(track_node.loc.x_high) |
| ys.append(track_node.loc.y_low) |
| ys.append(track_node.loc.y_high) |
| |
| x_tracks = {} |
| y_tracks = {} |
| |
| for track in self.tracks: |
| track_node = self.nodes[track] |
| |
| if track_node.type == NodeType.CHANX: |
| assert track_node.loc.y_low == track_node.loc.y_high |
| |
| x1, x2 = sorted((track_node.loc.x_low, track_node.loc.x_high)) |
| |
| if track_node.loc.y_low not in x_tracks: |
| x_tracks[track_node.loc.y_low] = [] |
| |
| x_tracks[track_node.loc.y_low].append((x1, x2, track)) |
| elif track_node.type == NodeType.CHANY: |
| assert track_node.loc.x_low == track_node.loc.x_high |
| |
| y1, y2 = sorted((track_node.loc.y_low, track_node.loc.y_high)) |
| |
| if track_node.loc.x_low not in y_tracks: |
| y_tracks[track_node.loc.x_low] = [] |
| |
| y_tracks[track_node.loc.x_low].append((y1, y2, track)) |
| else: |
| assert False, track_node |
| |
| x_list = [] |
| y_list = [] |
| |
| x_channel_models = {} |
| y_channel_models = {} |
| |
| if pool is not None: |
| for y in x_tracks: |
| x_channel_models[y] = pool.apply_async( |
| process_track, (x_tracks[y], ) |
| ) |
| |
| for x in y_tracks: |
| y_channel_models[x] = pool.apply_async( |
| process_track, (y_tracks[x], ) |
| ) |
| |
| for y in progressbar_utils.progressbar(range(max(x_tracks) + 1)): |
| if y in x_tracks: |
| if pool is None: |
| x_channel_models[y] = process_track(x_tracks[y]) |
| else: |
| x_channel_models[y] = x_channel_models[y].get() |
| |
| x_list.append(len(x_channel_models[y].trees)) |
| for idx, tree in enumerate(x_channel_models[y].trees): |
| for i in tree: |
| self.set_track_ptc(track=i[2], ptc=idx) |
| else: |
| x_list.append(0) |
| |
| for x in progressbar_utils.progressbar(range(max(y_tracks) + 1)): |
| if x in y_tracks: |
| if pool is None: |
| y_channel_models[x] = process_track(y_tracks[x]) |
| else: |
| y_channel_models[x] = y_channel_models[x].get() |
| |
| y_list.append(len(y_channel_models[x].trees)) |
| for idx, tree in enumerate(y_channel_models[x].trees): |
| for i in tree: |
| self.set_track_ptc(track=i[2], ptc=idx) |
| else: |
| y_list.append(0) |
| |
| x_min = min(xs) |
| y_min = min(ys) |
| x_max = max(xs) |
| y_max = max(ys) |
| |
| num_padding = 0 |
| for chan, channel_model in x_channel_models.items(): |
| for ptc, start, end in channel_model.fill_empty(max(x_min, 1), |
| x_max): |
| num_padding += 1 |
| self.add_track( |
| track=Track( |
| direction='X', |
| x_low=start, |
| y_low=chan, |
| x_high=end, |
| y_high=chan, |
| ), |
| segment_id=pad_segment, |
| capacity=0, |
| timing=None, |
| ptc=ptc |
| ) |
| |
| for chan, channel_model in y_channel_models.items(): |
| for ptc, start, end in channel_model.fill_empty(max(y_min, 1), |
| y_max): |
| num_padding += 1 |
| self.add_track( |
| track=Track( |
| direction='Y', |
| x_low=chan, |
| y_low=start, |
| x_high=chan, |
| y_high=end, |
| ), |
| segment_id=pad_segment, |
| capacity=0, |
| timing=None, |
| ptc=ptc |
| ) |
| |
| print('Number padding nodes {}'.format(num_padding)) |
| |
| return Channels( |
| chan_width_max=max(max(x_list), max(y_list)), |
| x_min=x_min, |
| y_min=y_min, |
| x_max=x_max, |
| y_max=y_max, |
| x_list=[ChannelList(idx, info) for idx, info in enumerate(x_list)], |
| y_list=[ChannelList(idx, info) for idx, info in enumerate(y_list)], |
| ) |
| |
| def block_type_at_loc(self, loc): |
| return self.block_types[self.loc_map[loc].block_type_id].name |
| |
| def get_switch_id(self, switch_name): |
| return self.switch_name_map[switch_name] |
| |
| def sort_nodes(self): |
| self.nodes.sort(key=lambda node: node.id) |
