Iteration on tileconn, pruning approach seems to be working. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>
diff --git a/fuzzers/004-tileinfo/analyze_errors.py b/fuzzers/004-tileinfo/analyze_errors.py index 061c9e5..cbe55cc 100644 --- a/fuzzers/004-tileinfo/analyze_errors.py +++ b/fuzzers/004-tileinfo/analyze_errors.py
@@ -1,5 +1,6 @@ -import json import argparse +import json +import pprint def main(): @@ -33,7 +34,7 @@ combined_generated_nodes |= set(generated_node) # Make sure there are not extra wires in nodes. - assert error['raw_node'] == combined_generated_nodes, (node, error) + assert error['raw_node'] == combined_generated_nodes, pprint.pformat((node, error)) good_node = max(error['generated_nodes'], key=lambda x: len(x)) bad_nodes = error['generated_nodes'] - set((good_node, ))
diff --git a/fuzzers/004-tileinfo/generate_grid.py b/fuzzers/004-tileinfo/generate_grid.py index 911c30f..5235c6a 100644 --- a/fuzzers/004-tileinfo/generate_grid.py +++ b/fuzzers/004-tileinfo/generate_grid.py
@@ -10,11 +10,13 @@ import datetime import pickle import sys -import copy +from collections import namedtuple -from utils import util, lib +from utils import util, lib, tile_sizes, connections from utils.xjson import extract_numbers +TileConnection = namedtuple('TileConnection', 'grid_deltas tile_types wire_pair') + def get_tile_grid_info(fname): with open(fname, 'r') as f: @@ -232,12 +234,6 @@ node_tree, tiles, x_wires, y_wires, wires_in_node): """ Check if two wires are directly connected. """ - next_wire_in_dim = next_wire_in_dimension(wire1, tile1, wire2, tile2, - tiles, x_wires, y_wires, - wire_map, wires_in_node) - if next_wire_in_dim is not None: - return next_wire_in_dim - # Because there are multiple possible wire connections between these two # tiles, consult the node_tree to determine if the two wires are actually connected. # @@ -263,93 +259,10 @@ # The node_tree didn't specify these wires, and the wires are not # unambiguously connected. - return False + return None -def edge_overlap(low1, high1, low2, high2): - """ Returns true if two lines have >0 overlap - - >>> edge_overlap(0, 1, 1, 2) - False - >>> edge_overlap(0, 2, 1, 2) - True - >>> edge_overlap(1, 2, 1, 2) - True - >>> edge_overlap(1, 2, 0, 1) - False - >>> edge_overlap(1, 2, 0, 2) - True - >>> edge_overlap(0, 1, 0, 1) - True - """ - if low1 < low2: - return low2 < high1 - else: - return low1 < high2 - -def box_share_edge(box1, box2): - """ Return true if the two boxes share any edge. - - >>> box_share_edge(((0, 1), (0, 1)), ((0, 1), (1, 2))) - True - >>> box_share_edge(((0, 1), (0, 1)), ((1, 2), (1, 2))) - False - >>> box_share_edge(((0, 1), (0, 3)), ((1, 2), (2, 5))) - True - >>> box_share_edge(((0, 1), (0, 3)), ((1, 2), (3, 6))) - False - >>> box_share_edge(((0, 3), (0, 1)), ((2, 5), (1, 2))) - True - >>> box_share_edge(((0, 3), (0, 1)), ((3, 6), (1, 2))) - False - >>> box_share_edge(((0, 3), (0, 3)), ((0, 3), (3, 6))) - True - >>> box_share_edge(((0, 3), (0, 3)), ((3, 6), (0, 3))) - True - >>> box_share_edge(((0, 3), (0, 3)), ((3, 6), (3, 6))) - False - - """ - ((box1_xlow, box1_xhigh), (box1_ylow, box1_yhigh)) = box1 - ((box2_xlow, box2_xhigh), (box2_ylow, box2_yhigh)) = box2 - - if box1_xlow == box2_xhigh or box2_xlow == box1_xhigh: - # box 1 left edge may touch box 2 right edge - # or - # box 2 left edge may touch box 1 right edge - if edge_overlap(box1_ylow, box1_yhigh, box2_ylow, box2_yhigh): - return True - - if box1_ylow == box2_yhigh or box2_ylow == box1_yhigh: - # box 1 bottom edge may touch box 1 top edge - # or - # box 2 bottom edge may touch box 2 top edge - if edge_overlap(box1_xlow, box1_xhigh, box2_xlow, box2_xhigh): - return True - - return False - - -def tiles_are_adjcent(tile1, tile2, tile_type_sizes): - width1, height1 = tile_type_sizes[tile1['type']] - tile1_xlow = tile1['grid_x'] - tile1_ylow = tile1['grid_y'] - height1 - tile1_xhigh = tile1['grid_x'] + width1 - tile1_yhigh = tile1['grid_y'] - - width2, height2 = tile_type_sizes[tile2['type']] - tile2_xlow = tile2['grid_x'] - tile2_ylow = tile2['grid_y'] - height2 - tile2_xhigh = tile2['grid_x'] + width2 - tile2_yhigh = tile2['grid_y'] - - return box_share_edge( - ((tile1_xlow, tile1_xhigh), (tile1_ylow, tile1_yhigh)), - ((tile2_xlow, tile2_xhigh), (tile2_ylow, tile2_yhigh)), - ) - - -def process_node(tileconn, key_history, node, wire_map, node_tree, tiles, tile_type_sizes): +def process_node(tileconn, key_history, node, wire_map, node_tree, tiles, tile_type_sizes, revisit_list): wires = [wire['wire'] for wire in node['wires']] wires_in_tiles = {} @@ -389,14 +302,21 @@ tile1 = tiles[wire_info1['tile']] tile2 = tiles[wire_info2['tile']] - if not tiles_are_adjcent(tile1, tile2, tile_type_sizes): - continue - - if not is_connected(wire1, wire_info1['tile'], wire2, + result = is_connected(wire1, wire_info1['tile'], wire2, wire_info2['tile'], node, wires_in_tiles, wire_map, node_tree, tiles, x_wires, y_wires, - wires): - continue + wires) + if result is not None: + if not result: + continue + else: + # This wire is an unknown, come back to it + dx = tile2['grid_x'] - tile1['grid_x'] + dy = tile2['grid_y'] - tile1['grid_y'] + same_tile = dx == 0 and dy == 0 + if same_tile or tile_sizes.tiles_are_adjcent(tile1, tile2, tile_type_sizes): + revisit_list.append((wire1, wire2)) + continue update_tile_conn(tileconn, key_history, wire1, wire_info1, wire2, wire_info2, tiles) @@ -413,20 +333,20 @@ (wire2['type'], wire2['shortname'], tile2['grid_x'], tile2['grid_y'])): wire1, tile1, wire2, tile2 = wire2, tile2, wire1, tile1 - tileconn.append({ - "grid_deltas": [ + tileconn.append(TileConnection( + grid_deltas=( tile2['grid_x'] - tile1['grid_x'], tile2['grid_y'] - tile1['grid_y'], - ], - "tile_types": [ + ), + tile_types=( tile1['type'], tile2['type'], - ], - "wire_pair": [ + ), + wire_pair=( wire1['shortname'], wire2['shortname'], - ], - }) + ), + )) def flatten_tile_conn(tileconn): @@ -437,16 +357,16 @@ flat_tileconn = {} for conn in tileconn: - key = (tuple(conn['tile_types']), tuple(conn['grid_deltas'])) + key = (tuple(conn.tile_types), tuple(conn.grid_deltas)) if key not in flat_tileconn: flat_tileconn[key] = { - 'tile_types': conn['tile_types'], - 'grid_deltas': conn['grid_deltas'], + 'tile_types': conn.tile_types, + 'grid_deltas': conn.grid_deltas, 'wire_pairs': set() } - flat_tileconn[key]['wire_pairs'].add(tuple(conn['wire_pair'])) + flat_tileconn[key]['wire_pairs'].add(tuple(conn.wire_pair)) def inner(): for output in flat_tileconn.values(): @@ -528,43 +448,26 @@ def connect_wires(tiles, tileconn, wire_map): """ Connect individual wires into groups of wires called nodes. """ + # Map of tile type to list of wires in tile type + tile_wires = {} + for tile_info in tiles.values(): + tile_wires[tile_info['type']] = set() + + for wire, wire_info in wire_map.items(): + tile = tiles[wire_info['tile']] + tile_type = tile['type'] + tile_wires[tile_type].add(wire_info['shortname']) + # Initialize all nodes to originally only contain the wire by itself. wire_nodes = {} for wire in wire_map: wire_nodes[wire] = set([wire]) - wire_connection_map = {} - for conn in tileconn: - for idx, (wire1, wire2) in enumerate(conn['wire_pairs']): - key1 = (conn['tile_types'][0], wire1) - if key1 not in wire_connection_map: - wire_connection_map[key1] = [] - wire_connection_map[key1].append((conn, idx)) - - key2 = (conn['tile_types'][1], wire2) - if key2 not in wire_connection_map: - wire_connection_map[key2] = [] - wire_connection_map[key2].append((conn, idx)) - - coord_to_tile = create_coord_to_tile(tiles) - - for wire, wire_info in progressbar.progressbar(wire_map.items()): - key = (wire_info['type'], wire_info['shortname']) - if key not in wire_connection_map: - continue - - for conn, idx in wire_connection_map[key]: - for target_tile, target_wire in get_connections( - wire, wire_info, conn, idx, coord_to_tile, tiles): - - full_wire_name = coord_to_tile[target_tile] + '/' + target_wire - assert wire_map[full_wire_name]['shortname'] == target_wire, ( - target_tile, target_wire, wire, conn) - assert wire_map[full_wire_name]['tile'] == coord_to_tile[ - target_tile], (wire_map[full_wire_name]['tile'], - coord_to_tile[target_tile]) - - make_connection(wire_nodes, wire, full_wire_name) + conns = connections.Connections(tiles, tileconn, tile_wires) + for wire_a, wire_b in conns.get_connections(): + full_wire_a = wire_a.tile + '/' + wire_a.wire + full_wire_b = wire_b.tile + '/' + wire_b.wire + make_connection(wire_nodes, full_wire_a, full_wire_b) # Find unique nodes nodes = {} @@ -616,10 +519,144 @@ return grid, wire_map +def revisit_wires(tileconn, nodes, revisit_list, key_history, wire_map, grid): + interesting_wires = {} + + for wire1, wire2 in revisit_list: + wire_info1 = wire_map[wire1] + wire_info2 = wire_map[wire2] + + tile1 = grid[wire_info1['tile']] + tile2 = grid[wire_info2['tile']] + + interesting_wires[tile1['type'], wire_info1['shortname']] = set() + interesting_wires[tile2['type'], wire_info2['shortname']] = set() + + for conn in tileconn: + for idx, k in enumerate(zip(conn.tile_types, conn.wire_pair)): + k = tuple(k) + if k in interesting_wires: + if sum(map(abs, conn.grid_deltas)) != 1: + continue + + if idx == 0: + interesting_wires[k].add(conn.grid_deltas) + else: + interesting_wires[k].add((-conn.grid_deltas[0], -conn.grid_deltas[1])) + + print('{} 1. Remaining {} revisit pairs'.format(datetime.datetime.now(), len(revisit_list))) + revisit_list2 = [] + for wire1, wire2 in revisit_list: + wire_info1 = wire_map[wire1] + wire_info2 = wire_map[wire2] + + tile1 = grid[wire_info1['tile']] + tile2 = grid[wire_info2['tile']] + + key1 = tile1['type'], wire_info1['shortname'] + key2 = tile2['type'], wire_info2['shortname'] + + wire1_directions = interesting_wires[key1] + wire2_directions = interesting_wires[key2] + + dx = tile2['grid_x'] - tile1['grid_x'] + dy = tile2['grid_y'] - tile1['grid_y'] + + paired_wires = False + if (dx, dy) in wire1_directions and len(wire2_directions) == 0: + interesting_wires[key2].add((-dx, -dy)) + paired_wires = True + + if (-dx, -dy) in wire2_directions and len(wire1_directions) == 0: + interesting_wires[key1].add((dx, dy)) + paired_wires = True + + if (dx, dy) in wire1_directions and (-dx, -dy) in wire2_directions: + paired_wires = True + + if paired_wires: + update_tile_conn( + tileconn, key_history, + wire1, wire_info1, + wire2, wire_info2, + grid) + else: + revisit_list2.append((wire1, wire2)) + + + print('{} 2. Remaining {} revisit pairs'.format(datetime.datetime.now(), len(revisit_list2))) + + tileconn = list(set(tileconn)) + + print('{} Pruning bad connections, have {} connections'.format(datetime.datetime.now(), len(tileconn))) + + # Construct map from (tile_type, wire) -> list of tiles + tile_type_instances = {} + tile_at_loc = {} + for tile, gridinfo in grid.items(): + if gridinfo['type'] not in tile_type_instances: + tile_type_instances[gridinfo['type']] = [] + tile_type_instances[gridinfo['type']].append(tile) + + loc = gridinfo['grid_x'], gridinfo['grid_y'] + assert loc not in tile_at_loc + tile_at_loc[loc] = tile + + # Prune bad connections + bad_connections = set() + for idx, conn in enumerate(progressbar.progressbar(tileconn)): + tile1_type, tile2_type = conn.tile_types + wire1, wire2 = conn.wire_pair + + for tile1 in tile_type_instances[tile1_type]: + tile1_info = grid[tile1] + assert tile1_info['type'] == tile1_type + + dx, dy = conn.grid_deltas + tile2_grid_x = tile1_info['grid_x'] + dx + tile2_grid_y = tile1_info['grid_y'] + dy + + loc = tile2_grid_x, tile2_grid_y + if loc not in tile_at_loc: + continue + + tile2 = tile_at_loc[loc] + tile2_info = grid[tile2] + + if tile2_info['type'] != tile2_type: + continue + + fullwire1 = tile1 + '/' + wire1 + fullwire2 = tile2 + '/' + wire2 + + if fullwire1 not in nodes or fullwire2 not in nodes: + bad_connections.add(idx) + continue + + # tileconn says these two wires should form a node. If these wires + # are a node, they will have the same set object representing + # the node. + if nodes[fullwire1] is not nodes[fullwire2]: + bad_connections.add(idx) + + print('{} Found {} bad connections'.format(datetime.datetime.now(), len(bad_connections))) + + # Delete from highest index to lowest index to preverse deletion order + for idx in sorted(bad_connections, reverse=True): + del tileconn[idx] + + print('{} Removed {} bad connections'.format(datetime.datetime.now(), len(bad_connections))) + + return tileconn + + def generate_tileconn(pool, node_tree, nodes, wire_map, grid, tile_type_sizes): tileconn = [] key_history = {} raw_node_data = [] + revisit_list = [] + + wire_nodes = {} with progressbar.ProgressBar(max_value=len(nodes)) as bar: for idx, node in enumerate( pool.imap_unordered( @@ -630,167 +667,21 @@ bar.update(idx) raw_node_data.append(node) process_node(tileconn, key_history, node, wire_map, node_tree, - grid, tile_type_sizes) + grid, tile_type_sizes, revisit_list) bar.update(idx + 1) + node = set(wire['wire'] for wire in node['wires']) + for wire in node: + assert wire not in wire_nodes + wire_nodes[wire] = node + + tileconn = revisit_wires(tileconn, wire_nodes, revisit_list, key_history, wire_map, grid) + tileconn = flatten_tile_conn(tileconn) return tileconn, raw_node_data -def max_size_for_tile(tile, grid, tile_by_loc, rclk_rows): - """ Guess maximum size for a tile. """ - tile_type = grid[tile]['type'] - if tile_type== 'NULL': - return (1, 1) - - # Pos X, Neg Y - base_grid_x = grid[tile]['grid_x'] - base_grid_y = grid[tile]['grid_y'] - - # Walk up X - grid_x = base_grid_x - grid_y = base_grid_y - while True: - try: - next_tile = tile_by_loc[(grid_x+1, grid_y)] - except KeyError: - break - - if grid[next_tile]['type'] != 'NULL': - break - - grid_x += 1 - - max_grid_x = grid_x - - # Walk down Y - grid_x = base_grid_x - grid_y = base_grid_y - while True: - # Most tiles don't control the RCLK row, but a handful of tiles do! - if grid_y-1 in rclk_rows and tile_type not in [ - "CFRM_AMS_CFGIO", - "PSS_ALTO", - "CFG_CONFIG", - ]: - break - - try: - next_tile = tile_by_loc[(grid_x, grid_y-1)] - except KeyError: - break - - if grid[next_tile]['type'] != 'NULL': - break - - grid_y -= 1 - - max_grid_y = grid_y - - return (max_grid_x-base_grid_x+1), (base_grid_y-max_grid_y+1) - - -def generate_tile_type_sizes(grid): - """ Generate tile sizes for the given grid using max_size_for_tile. """ - tile_type_sizes = {} - - tile_by_loc = {} - - rclk_rows = set() - - for tile, gridinfo in grid.items(): - key = gridinfo['grid_x'], gridinfo['grid_y'] - assert key not in tile_by_loc - tile_by_loc[key] = tile - - if gridinfo['type'] in ['RCLK_INT_R', 'RCLK_INT_L']: - rclk_rows.add(gridinfo['grid_y']) - - for tile, gridinfo in grid.items(): - size_x, size_y = max_size_for_tile(tile, grid, tile_by_loc, rclk_rows) - if gridinfo['type'] not in tile_type_sizes: - tile_type_sizes[gridinfo['type']] = (size_x, size_y) - else: - old_size_x, old_size_y = tile_type_sizes[gridinfo['type']] - tile_type_sizes[gridinfo['type']] = ( - min(size_x, old_size_x), - min(size_y, old_size_y), - ) - - return tile_type_sizes - - -def commit_tile_type(grid, tile_type, size): - """ First verify that expanding the specified tile type by the size - specified works, then modify the tile grid to reflect the expanded sizes. - """ - gridinfo_by_loc = {} - locs = [] - for tile in grid: - gridinfo = grid[tile] - key = gridinfo['grid_x'], gridinfo['grid_y'] - assert key not in gridinfo_by_loc - gridinfo_by_loc[key] = gridinfo - - if gridinfo['type'] == tile_type: - locs.append(key) - - for loc in locs: - for dx in range(size[0]): - for dy in range(size[1]): - key = loc[0] + dx, loc[1] - dy - - if dx == 0 and dy == 0: - assert gridinfo_by_loc[key]['type'] == tile_type - else: - assert gridinfo_by_loc[key]['type'] == 'NULL', ( - loc, key, tile_type, gridinfo_by_loc[key]['type']) - - for loc in locs: - for dx in range(size[0]): - for dy in range(size[1]): - gridinfo_by_loc[key]['type'] = 'expanded_' + tile_type - - -def guess_tile_type_sizes(grid): - """ Guess tile type sizes by expanding, and then blocking by largest.""" - grid = copy.deepcopy(grid) - tile_type_sizes = generate_tile_type_sizes(grid) - commited_types = set() - - # Commit longest or widest tiles first - tile_type_by_size = sorted(tile_type_sizes, key=lambda k: max(tile_type_sizes[k][0],tile_type_sizes[k][1]), reverse=True) - for tile_type in tile_type_by_size: - if tile_type_sizes[tile_type] == (1, 1): - continue - - recompute_sizes = False - try: - # Attempt to commit this tile type - commit_tile_type(grid, tile_type, tile_type_sizes[tile_type]) - except AssertionError: - # Commit failed, try to recompute and then re-commit. - recompute_sizes = True - - if recompute_sizes: - new_tile_type_sizes = generate_tile_type_sizes(grid) - - for tile_type in new_tile_type_sizes: - if tile_type in commited_types: - continue - if tile_type.startswith('expanded_'): - continue - - tile_type_sizes[tile_type] = new_tile_type_sizes[tile_type] - - commit_tile_type(grid, tile_type, tile_type_sizes[tile_type]) - - commited_types.add(tile_type) - - return tile_type_sizes - - def main(): parser = argparse.ArgumentParser( description= @@ -846,7 +737,7 @@ with open(node_tree_file) as f: node_tree = json.load(f) - tile_type_sizes = guess_tile_type_sizes(grid) + tile_type_sizes = tile_sizes.guess_tile_type_sizes(grid) print('{} Creating tile connections'.format(datetime.datetime.now())) tileconn, raw_node_data = generate_tileconn(pool, node_tree, nodes,
diff --git a/utils/lib.py b/utils/lib.py index 94ada84..a8f421f 100644 --- a/utils/lib.py +++ b/utils/lib.py
@@ -1,6 +1,7 @@ import os.path import csv import pickle +import pprint import re from collections import namedtuple @@ -86,7 +87,7 @@ combined_generated_nodes |= set(generated_node) # Make sure there are not extra wires in nodes. - assert error['raw_node'] == combined_generated_nodes, (node, error) + assert error['raw_node'] == combined_generated_nodes, pprint.pformat((node, error)) good_node = max(error['generated_nodes'], key=lambda x: len(x)) bad_nodes = error['generated_nodes'] - set((good_node, ))