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, ))
