| #!/usr/bin/env python3 |
| """ Script for addressing CARRY4 output congestion in elaborated netlists. |
| |
| Usage: |
| |
| python3 fix_carry.py < input-netlist-json > output-netlist-json |
| |
| Description: |
| |
| In the 7-series SLICEL (and SLICEM) sites, there can be output congestion |
| if both the CO and O of the CARRY4 are used. This congestion can be |
| avoided by using a transparent/open latch or register on the output of the |
| CARRY4. |
| |
| VPR does not currently support either of those options, so for now, if |
| both CO and O are used, the CO output is converted into a LUT equation to |
| recompute the CO output from O, DI and S. See carry_map.v and |
| clean_carry_map.v for details. |
| |
| If VPR could emit the transparent/open latch on output congestion, this |
| would no longer be required. The major problem with transparent latch |
| support is that it requires constants to be routed to the G/GE/CLR/PRE |
| ports, which VPR cannot express as a result of packing. |
| |
| This script identifies CARRY4 chains in the netlist, identifies if there |
| is output congestion on the O and CO ports, and marks the congestion by |
| changing CARRY_CO_DIRECT (e.g. directly use the CO port) to CARRY_CO_LUT |
| (compute the CO value using a LUT equation). |
| |
| |
| Diagram showing one row of the 7-series CLE, focusing on O/CO congestion. |
| This diagram shows that if both the O and CO outputs are needed, once must |
| pass through the flip flop (xFF in the diagram). |
| |
| CLE Row |
| |
| +--------------------------------------------------------------------------+ |
| | | |
| | | |
| | +---+ | |
| | | + | |
| | | + | |
| | +-------->+ O + | |
| | CO CHAIN | | + | |
| | | | +---------------------> xMUX |
| | ^ | +---->+ CO + | |
| | | | | | + | |
| | | | | | + | |
| | +---------+----------+ | | | + | |
| | | | | | +---+ | |
| | | CARRY ROW | | | | |
| | +--->+ S O +--------+ | xOUTMUX | |
| | | | | | | |
| | | | + | | |
| | +--->+ DI CO +-------+o+--+ | |
| | | CI CHAIN | + | | |
| | | | | | | |
| | +---------+----------+ | | xFFMUX | |
| | ^ | | | |
| | | | | +---+ | |
| | + | | | + | |
| | | + | + +-----------+ | |
| | +--+o+--->+ O + | | | |
| | + | + | xFF | | |
| | | | +->--D---- Q +------> xQ |
| | | | + | | | |
| | +---->+ CO + | | | |
| | | + +-----------+ | |
| | | + | |
| | +---+ | |
| | | |
| | | |
| +--------------------------------------------------------------------------+ |
| |
| |
| This script operates on a slightly different cell structure than a plain CARRY4. |
| carry_map.v converts the CARRY4 into: |
| |
| +------------------+ +-----------------+ |
| | | | | |
| | CO3 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | DI3 | +-----------------+ |
| | | |
| | S3 O3 | |
| | | |
| | DI2 | +-----------------+ |
| | | | | |
| | S2 CO2 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | DI1 | +-----------------+ |
| | | |
| | S1 O2 | |
| | CARRY4 | |
| | DI0 (chained) | +-----------------+ |
| | | | | |
| | S0 CO1 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | CYINIT | +-----------------+ |
| | | |
| +-----------------+ | O1 | |
| | | | | |
| +->+ CARRY_COUT_PLUG +->+ CI | +-----------------+ |
| | | | | | | | |
| | +-----------------+ | CO0 +->+ CARRY_CO_DIRECT | |
| | | | | | |
| | | | +-----------------+ |
| +-------------------+ | | |
| | | O0 | |
| +------------------+ +-----------------+ | | | |
| | | | | | +------------------+ |
| | CO3 +->+ CARRY_CO_DIRECT +-+ |
| | | | | |
| | DI3 | +-----------------+ |
| | | |
| | S3 O3 | |
| | | |
| | DI2 | +-----------------+ |
| | | | | |
| | S2 CO2 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | DI1 | +-----------------+ |
| | | |
| | S1 O2 | |
| | CARRY4 | |
| | DI0 (root) | +-----------------+ |
| | | | | |
| | S0 CO1 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | CYINIT | +-----------------+ |
| | | |
| | O1 | |
| | | |
| | CI | +-----------------+ |
| | | | | |
| | CO0 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | | +-----------------+ |
| | | |
| | O0 | |
| | | |
| +------------------+ |
| |
| Each CARRY4 spans the 4 rows of the SLICEL/SLICEM. |
| Row 0 is the S0/DI0/O0/CO0 ports, row 1 is S1/DI1/O1/CO1 ports, etc. |
| |
| So there are five cases the script has to handle: |
| |
| - No congestion is present between O and CO -> |
| |
| Do nothing. |
| |
| - Congestion is present on rows 0-2 and row above is in use -> |
| |
| Change CARRY_CO_DIRECT to CARRY_CO_LUT. |
| |
| Routing and LUT delays are incurred in this case. |
| |
| - Congestion is present on rows 0-2 and row above is not in use -> |
| |
| Remap CO to O from the row above, and set S on the next row to 0 to |
| ensure O outputs CI from the row below. |
| |
| No additional delays for this change. |
| |
| - Congestion is present on row 3 and CO3 is not connected to another CARRY -> |
| |
| Change CARRY_CO_DIRECT to CARRY_CO_TOP_POP. This adds 1 dummy layer to |
| the carry chain to output the CO. |
| |
| No additional delays for this change. |
| |
| - Congestion is present on row 3 and CO3 is connected directly to another |
| CARRY4 -> |
| |
| Change CARRY_CO_DIRECT to CARRY_CO_LUT *and* change the chained |
| CARRY_COUT_PLUG to be directly connected to the previous CO3. |
| |
| Routing and LUT delays are incurred in this case. |
| |
| Diagram for this case: |
| |
| +-------------------+ +-----------------+ |
| | | | | |
| | CO3 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | DI3 | +-----------------+ |
| | | |
| | S3 O3 | |
| | | |
| | DI2 | +-----------------+ |
| | | | | |
| | S2 CO2 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | DI1 | +-----------------+ |
| | | |
| | S1 O2 | |
| | CARRY4 | |
| | DI0 (chained) | +-----------------+ |
| | | | | |
| | S0 CO1 +->+ CARRY_CO_DIRECT | |
| | | | | |
| | CYINIT | +-----------------+ |
| | | |
| +-----------------+ | O1 | |
| | | | | |
| +->+ CARRY_COUT_PLUG +--->+ CI | +-----------------+ |
| | | | | | | | |
| | +-----------------+ | CO0 +->+ CARRY_CO_DIRECT | |
| | | | | | |
| +-------------------+ | +-----------------+ | | +-----------------+ |
| | | | | | | | |
| | CO3 +--+->+ CARRY_CO_LUT +-+ | O0 | |
| | | | | | | | |
| | DI3 | +-----------------+ | +-------------------+ |
| | | | |
| | S3 O3 | +------> |
| | | |
| | DI2 | +-----------------+ |
| | | | | |
| | S2 CO2 +---->+ CARRY_CO_DIRECT | |
| | | | | |
| | DI1 | +-----------------+ |
| | | |
| | S1 O2 | |
| | CARRY4 | |
| | DI0 (root) | +-----------------+ |
| | | | | |
| | S0 CO1 +---->+ CARRY_CO_DIRECT | |
| | | | | |
| | CYINIT | +-----------------+ |
| | | |
| | O1 | |
| | | |
| | CI | +-----------------+ |
| | | | | |
| | CO0 +---->+ CARRY_CO_DIRECT | |
| | | | | |
| | | +-----------------+ |
| | | |
| | O0 | |
| | | |
| +-------------------+ |
| |
| After this script is run, clean_carry_map.v is used to convert CARRY_CO_DIRECT |
| into a direct connection, and CARRY_CO_LUT is mapped to a LUT to compute the |
| carry output. |
| |
| """ |
| import json |
| import sys |
| |
| |
| def find_top_module(design): |
| """ |
| Looks for the top-level module in the design. Returns its name. Throws |
| an exception if none was found. |
| """ |
| |
| for name, module in design["modules"].items(): |
| attrs = module["attributes"] |
| if "top" in attrs and int(attrs["top"]) == 1: |
| return name |
| |
| raise RuntimeError("No top-level module found in the design!") |
| |
| |
| def find_carry4_chains(design, top_module, bit_to_cells): |
| """ Identify CARRY4 carry chains starting from the root CARRY4. |
| |
| All non-root CARRY4 cells should end up as part of a chain, otherwise |
| an assertion is raised. |
| |
| Arguments: |
| design (dict) - "design" field from Yosys JSON format |
| top_module (str) - Name of top module. |
| bit_to_cells (dict) - Map of net bit identifier and cell information. |
| Computes in "create_bit_to_cell_map". |
| |
| Returns: |
| list of list of strings - List of CARRY4 chains. Each chain is a list |
| of cellnames. The cells are listed in chain order, starting from |
| the root. |
| |
| """ |
| cells = design["modules"][top_module]["cells"] |
| |
| used_carry4s = set() |
| root_carry4s = [] |
| nonroot_carry4s = {} |
| for cellname in cells: |
| cell = cells[cellname] |
| if cell["type"] != "CARRY4_VPR": |
| continue |
| connections = cell["connections"] |
| |
| if "CIN" in connections: |
| cin_connections = connections["CIN"] |
| assert len(cin_connections) == 1 |
| |
| # Goto driver of CIN, should be a CARRY_COUT_PLUG. |
| plug_cellname, port, bit_idx = bit_to_cells[cin_connections[0]][0] |
| plug_cell = cells[plug_cellname] |
| assert plug_cell["type"] == "CARRY_COUT_PLUG", plug_cellname |
| assert port == "COUT" |
| |
| plug_connections = plug_cell["connections"] |
| |
| cin_connections = plug_connections["CIN"] |
| assert len(cin_connections) == 1 |
| |
| # Goto driver of CIN, should be a CARRY_CO_DIRECT. |
| direct_cellname, port, bit_idx = bit_to_cells[cin_connections[0] |
| ][0] |
| direct_cell = cells[direct_cellname] |
| assert direct_cell["type"] == "CARRY_CO_DIRECT", direct_cellname |
| assert port == "OUT" |
| |
| direct_connections = direct_cell["connections"] |
| |
| co_connections = direct_connections["CO"] |
| assert len(co_connections) == 1 |
| |
| nonroot_carry4s[co_connections[0]] = cellname |
| else: |
| used_carry4s.add(cellname) |
| root_carry4s.append(cellname) |
| |
| # Walk from each root CARRY4 to each child CARRY4 module. |
| chains = [] |
| for cellname in root_carry4s: |
| chain = [cellname] |
| |
| while True: |
| # Follow CO3 to the next CARRY4, if any. |
| cell = cells[cellname] |
| connections = cell["connections"] |
| |
| co3_connections = connections.get("CO3", None) |
| if co3_connections is None: |
| # No next CARRY4, stop here. |
| break |
| |
| found_next_link = False |
| for connection in co3_connections: |
| next_cellname = nonroot_carry4s.get(connection, None) |
| if next_cellname is not None: |
| cellname = next_cellname |
| used_carry4s.add(cellname) |
| chain.append(cellname) |
| found_next_link = True |
| break |
| |
| if not found_next_link: |
| break |
| |
| chains.append(chain) |
| |
| # Make sure all non-root CARRY4's got used. |
| for bit, cellname in nonroot_carry4s.items(): |
| assert cellname in used_carry4s, (bit, cellname) |
| |
| return chains |
| |
| |
| def create_bit_to_cell_map(design, top_module): |
| """ Create map from net bit identifier to cell information. |
| |
| Arguments: |
| design (dict) - "design" field from Yosys JSON format |
| top_module (str) - Name of top module. |
| |
| Returns: |
| bit_to_cells (dict) - Map of net bit identifier and cell information. |
| |
| The map keys are the net bit identifier used to mark which net a cell port |
| is connected too. The map values are a list of cell ports that are in the |
| net. The first element of the list is the driver port, and the remaining |
| elements are sink ports. |
| |
| The list elements are 3-tuples with: |
| cellname (str) - The name of the cell this port belongs too |
| port (str) - The name of the port this element is connected too. |
| bit_idx (int) - For multi bit ports, a 0-based index into the port. |
| |
| """ |
| bit_to_cells = {} |
| |
| cells = design["modules"][top_module]["cells"] |
| |
| for cellname in cells: |
| cell = cells[cellname] |
| port_directions = cell["port_directions"] |
| for port, connections in cell["connections"].items(): |
| is_output = port_directions[port] == "output" |
| for bit_idx, bit in enumerate(connections): |
| |
| list_of_cells = bit_to_cells.get(bit, None) |
| if list_of_cells is None: |
| list_of_cells = [None] |
| bit_to_cells[bit] = list_of_cells |
| |
| if is_output: |
| # First element of list of cells is net driver. |
| assert list_of_cells[0] is None, ( |
| bit, list_of_cells[0], cellname |
| ) |
| list_of_cells[0] = (cellname, port, bit_idx) |
| else: |
| list_of_cells.append((cellname, port, bit_idx)) |
| |
| return bit_to_cells |
| |
| |
| def is_bit_used(bit_to_cells, bit): |
| """ Is the net bit specified used by any sinks? """ |
| list_of_cells = bit_to_cells[bit] |
| |
| return len(list_of_cells) > 1 |
| |
| |
| def is_bit_used_other_than_carry4_cin(design, top_module, bit, bit_to_cells): |
| """ Is the net bit specified used by any sinks other than a carry chain? """ |
| cells = design["modules"][top_module]["cells"] |
| list_of_cells = bit_to_cells[bit] |
| assert len(list_of_cells) == 2, bit |
| |
| direct_cellname, port, _ = list_of_cells[1] |
| direct_cell = cells[direct_cellname] |
| assert direct_cell['type'] == "CARRY_CO_DIRECT" |
| assert port == "CO" |
| |
| # Follow to output |
| connections = direct_cell["connections"]["OUT"] |
| assert len(connections) == 1 |
| |
| for cellname, port, bit_idx in bit_to_cells[connections[0]][1:]: |
| cell = cells[cellname] |
| if cell["type"] == "CARRY_COUT_PLUG" and port == "CIN": |
| continue |
| else: |
| return True, direct_cellname |
| |
| return False, direct_cellname |
| |
| |
| def create_bit_to_net_map(design, top_module): |
| """ Create map from net bit identifier to net information. |
| |
| Arguments: |
| design (dict) - "design" field from Yosys JSON format |
| top_module (str) - Name of top module. |
| |
| Returns: |
| bit_to_nets (dict) - Map of net bit identifier to net information. |
| """ |
| bit_to_nets = {} |
| |
| nets = design["modules"][top_module]["netnames"] |
| |
| for net in nets: |
| for bit_idx, bit in enumerate(nets[net]["bits"]): |
| bit_to_nets[bit] = (net, bit_idx) |
| |
| return bit_to_nets |
| |
| |
| def fixup_cin(design, top_module, bit_to_cells, co_bit, direct_cellname): |
| """ Move connection from CARRY_CO_LUT.OUT -> CARRY_COUT_PLUG.CIN to |
| directly to preceeding CARRY4. |
| """ |
| cells = design["modules"][top_module]["cells"] |
| |
| direct_cell = cells[direct_cellname] |
| assert direct_cell["type"] == "CARRY_CO_LUT" |
| |
| # Follow to output |
| connections = direct_cell["connections"]["OUT"] |
| assert len(connections) == 1 |
| |
| for cellname, port, bit_idx in bit_to_cells[connections[0]][1:]: |
| cell = cells[cellname] |
| if cell["type"] == "CARRY_COUT_PLUG" and port == "CIN": |
| assert bit_idx == 0 |
| |
| cells[cellname]["connections"]["CIN"][0] = co_bit |
| |
| |
| def fixup_congested_rows(design, top_module, bit_to_cells, bit_to_nets, chain): |
| """ Walk the specified carry chain, and identify if any outputs are congested. |
| |
| Arguments: |
| design (dict) - "design" field from Yosys JSON format |
| top_module (str) - Name of top module. |
| bit_to_cells (dict) - Map of net bit identifier and cell information. |
| Computes in "create_bit_to_cell_map". |
| bit_to_nets (dict) - Map of net bit identifier to net information. |
| Computes in "create_bit_to_net_map". |
| chain (list of str) - List of cells in the carry chain. |
| |
| """ |
| cells = design["modules"][top_module]["cells"] |
| |
| O_ports = ["O0", "O1", "O2", "O3"] |
| CO_ports = ["CO0", "CO1", "CO2", "CO3"] |
| |
| def check_if_rest_of_carry4_is_unused(cellname, cell_idx): |
| assert cell_idx < len(O_ports) |
| |
| cell = cells[cellname] |
| connections = cell["connections"] |
| |
| for o, co in zip(O_ports[cell_idx:], CO_ports[cell_idx:]): |
| o_conns = connections[o] |
| assert len(o_conns) == 1 |
| o_bit = o_conns[0] |
| if is_bit_used(bit_to_cells, o_bit): |
| return False |
| |
| co_conns = connections[co] |
| assert len(co_conns) == 1 |
| co_bit = co_conns[0] |
| if is_bit_used(bit_to_cells, co_bit): |
| return False |
| |
| return True |
| |
| # Carry chain is congested if both O and CO is used at the same level. |
| # CO to next element in the chain is fine. |
| for chain_idx, cellname in enumerate(chain): |
| cell = cells[cellname] |
| connections = cell["connections"] |
| for cell_idx, (o, co) in enumerate(zip(O_ports, CO_ports)): |
| o_conns = connections[o] |
| assert len(o_conns) == 1 |
| o_bit = o_conns[0] |
| |
| co_conns = connections[co] |
| assert len(co_conns) == 1 |
| co_bit = co_conns[0] |
| |
| is_o_used = is_bit_used(bit_to_cells, o_bit) |
| is_co_used, direct_cellname = is_bit_used_other_than_carry4_cin( |
| design, top_module, co_bit, bit_to_cells |
| ) |
| |
| if is_o_used and is_co_used: |
| # Output at this row is congested. |
| direct_cell = cells[direct_cellname] |
| |
| if co == 'CO3' and chain_idx == len(chain) - 1: |
| # This congestion is on the top of the carry chain, |
| # emit a dummy layer to the chain. |
| direct_cell["type"] = "CARRY_CO_TOP_POP" |
| assert int(direct_cell["parameters"]["TOP_OF_CHAIN"]) == 1 |
| # If this is the last CARRY4 in the chain, see if the |
| # remaining part of the chain is idle. |
| elif chain_idx == len(chain) - 1 and \ |
| check_if_rest_of_carry4_is_unused(cellname, cell_idx + 1): |
| |
| # Because the rest of the CARRY4 is idle, it is safe to |
| # use the next row up to output the top of the carry. |
| connections["S{}".format(cell_idx + 1)] = ["1'b0"] |
| |
| next_o_conns = connections[O_ports[cell_idx + 1]] |
| assert len(next_o_conns) == 1 |
| direct_cell["connections"]["CO"][0] = next_o_conns[0] |
| |
| netname, bit_idx = bit_to_nets[next_o_conns[0]] |
| assert bit_idx == 0 |
| |
| # Update annotation that this net is now in use. |
| net = design["module"][top_module]["netnames"][netname] |
| assert net["attributes"].get("unused_bits", None) == "0 " |
| del net["attributes"]["unused_bits"] |
| else: |
| # The previous two stragies (use another layer of carry) |
| # only work for the top of the chain. This appears to be |
| # in the middle of the chain, so just spill it out to a |
| # LUT, and fixup the direct carry chain (if any). |
| direct_cell["type"] = "CARRY_CO_LUT" |
| |
| fixup_cin( |
| design, top_module, bit_to_cells, co_bit, |
| direct_cellname |
| ) |
| |
| |
| def main(): |
| design = json.load(sys.stdin) |
| top_module = find_top_module(design) |
| |
| bit_to_cells = create_bit_to_cell_map(design, top_module) |
| bit_to_nets = create_bit_to_net_map(design, top_module) |
| |
| for chain in find_carry4_chains(design, top_module, bit_to_cells): |
| fixup_congested_rows( |
| design, top_module, bit_to_cells, bit_to_nets, chain |
| ) |
| |
| json.dump(design, sys.stdout, indent=2) |
| |
| |
| if __name__ == "__main__": |
| main() |
