In [2]:
from IPython.display import display, Image
import pandas as pd
import numpy as np
from cyplace_experiments.data import get_data_directory

Arrival time calculation using structured parallel primitives

TODO

  • Write textual description of algorithm.

In [3]:
from thrust_timing.adjacency_list import NetAdjacencyList
from thrust_timing.delay_model import DelayModel

netlist_h5f = pd.HDFStore(str(get_data_directory().joinpath('netlists.h5')),
                          'r')
[n for n in netlist_h5f.root.netlists._v_children]


Out[3]:
['clma',
 'seq',
 'b18_1_new_mapped-1x4lut',
 'tseng',
 'b18_new_mapped-1x4lut',
 'diffeq',
 'apex2',
 'apex4',
 'elliptic',
 'frisc',
 'leon3mp_low_fanout_latch-1x4lut',
 'misex3',
 's38584.1',
 's38417',
 'b19_1_new_mapped-1x4lut',
 'bigkey',
 's298',
 'netcard_low_fanout_latch-1x4lut',
 'leon2_low_fanout_latch-1x4lut',
 'spla',
 'ex5p',
 'dsip',
 'ex1010',
 'des',
 'uoft_raytracer_low_fanout_latch-1x4lut',
 'alu4',
 'pdc',
 'b17_1_new_mapped-1x4lut']

In [4]:
# netlist_namebase = 'clma'
netlist_namebase = 'ex5p'
# netlist_namebase = 'uoft_raytracer_low_fanout_latch-1x4lut'
netlist_group = getattr(netlist_h5f.root.netlists, netlist_namebase)
adjacency_list = NetAdjacencyList.from_hdf_group(netlist_group)
delay_model = DelayModel(adjacency_list)
arrival_times = delay_model.compute_arrival_times()
required_times, required_connections = delay_model.compute_required_times()
pd.Series(required_times).describe()


Out[4]:
count    1135.000000
mean        4.094273
std         1.751521
min         0.000000
25%         3.000000
50%         4.000000
75%         5.000000
max         8.000000
dtype: float64

In [5]:
import matplotlib.pyplot as plt
from matplotlib.gridspec import GridSpec

def plot_arrival_times(netlist_namebase='ex5p'):
    netlist_group = getattr(netlist_h5f.root.netlists, netlist_namebase)
    adjacency_list = NetAdjacencyList.from_hdf_group(netlist_group)
    delay_model = DelayModel(adjacency_list)
    arrival_times = delay_model.compute_arrival_times()
    fig = plt.figure(figsize=(15, 6))
    grid = GridSpec(1, 2)
    axis = {'hist': fig.add_subplot(grid[0, 0]), 'box': fig.add_subplot(grid[0, 1])}
    axis['hist'].hist(delay_model.arrival_times)
    axis['box'].boxplot(delay_model.arrival_times)
    axis['hist'].set_title(netlist_namebase)

In [4]:
Image('https://lh4.googleusercontent.com/-Ux_y9hnBWmo/U1unDIdMU6I/AAAAAAAAEpY/X1jkLUUn-VQ/w1532-h787-no/IMG_20140426_080649.jpg')


Out[4]:

In [6]:
connections = pd.DataFrame(np.array([[0, 0, 0],
                                     [1, 1, 0],
                                     [2, 2, 0],
                                     [3, 0, 0],
                                     [3, 1, 1],
                                     [3, 3, 4],
                                     [4, 0, 0],
                                     [4, 2, 1],
                                     [4, 4, 4],
#                                      [4, 8, 5],
                                     [5, 1, 0],
                                     [5, 3, 1],
                                     [5, 5, 4],
#                                      [6, 8, 5],
                                     [6, 1, 0],
                                     [6, 5, 1],
                                     [6, 6, 4],
                                     [7, 4, 0],
                                     [7, 6, 1],
                                     [7, 7, 4],
                                     [8, 7, 0]]),
                           columns=['block_key', 'net_key', 'pin_key'])
connections['block_type'] = '.clb'
connections['block_type'][:3] = '.input'
connections['block_type'][-1:] = '.output'
block_count = len(connections['block_key'].unique())
net_count = len(connections['net_key'].unique())

adjacency_list = NetAdjacencyList(net_count, block_count, connections)
delay_model = DelayModel(adjacency_list)
delay_model.compute_arrival_times()


Out[6]:
array([ 0.,  0.,  0.,  1.,  1.,  2.,  3.,  4.,  5.], dtype=float32)

In [7]:
%matplotlib inline

In [8]:
delay_model.compute_required_times()


Out[8]:
(array([ 0.,  0.,  2.,  1.,  3.,  2.,  3.,  4.,  5.], dtype=float32),
 Empty DataFrame
 Columns: [block_key, net_key, pin_key, block_type, net_driver_block_key, delay, sink_required_time, required_time]
 Index: []
 
 [0 rows x 8 columns])

In [9]:
delay_model.arrival_times


Out[9]:
array([ 0.,  0.,  0.,  1.,  1.,  2.,  3.,  4.,  5.], dtype=float32)

In [10]:
from itertools import izip

import networkx as nx


def plot_net_list(adjacency_list, delay_model, axis=None,
                  time_key='required_time', f='min', spread=1,
                  randomize=False, node_size=10, alpha=0.4):
    connections = adjacency_list.sink_connections.copy()
    connections['net_driver_block_key'] = (delay_model.net_drivers
                                           [connections['net_key'].tolist()])
    connections['delay'] = [1 for a, b in izip(connections['block_key'],
                                               connections
                                               ['net_driver_block_key'])]
    connections['arrival_time']= (delay_model.arrival_times
                                  [connections['net_driver_block_key']
                                   .tolist()])
    connections['required_time']= (delay_model.required_times
                                   [connections['block_key'].tolist()])
    connections['slack'] = (connections['required_time'] - 
                            connections['arrival_time'] -
                            connections['delay'])
    connections['slack'][connections['slack'] < 0] = 0.

#     net_list_connections = nx.DiGraph()
    net_list_connections = nx.Graph()
    net_list_connections.add_nodes_from(adjacency_list
                                        .connections['block_key']
                                        .unique())
    edge_labels = dict([((b1, b2), n) for i, (n, b1, b2) in
                        enumerate(connections[['net_key',
                                               'net_driver_block_key',
                                               'block_key']].as_matrix())])
    net_list_connections.add_edges_from(connections
                                        [['net_driver_block_key',
                                          'block_key']].as_matrix())
    agg_funcs = {'min': (np.min, 0),
                 'max': (np.max, connections[time_key].max() + 1)}
    sink_block_levels = (connections.groupby('block_key')
                         .agg({time_key: agg_funcs[f][0]}))
    block_levels = np.empty(adjacency_list.block_count, dtype='int32')

    if time_key == 'arrival_time':
        block_levels[:] = -1
    else:
        block_levels[:] = 0
    block_levels[adjacency_list.connections[adjacency_list.connections
                                            ['block_type'] == '.output']
                 ['block_key'].unique()] = (delay_model.arrival_times.max() + 1)
    block_levels[sink_block_levels.index] = sink_block_levels[time_key]
    if time_key == 'arrival_time':
        block_levels[:] += 1
    block_positions = pd.DataFrame(np.empty((adjacency_list.block_count, 2), dtype='int32'),
                                   columns=['level', 'index'])
    type_colors = {'.clb': '#88bde6',
                   '.input': '#90cd97',
                   '.output': '#f07e6e'}
    block_types = (adjacency_list.connections.groupby(['block_key'])
                   .agg({'block_type': np.max}))['block_type']
    block_colors = np.array([type_colors[t] for t in block_types])
    block_colors[adjacency_list.clocked_driver_block_keys] = '#eddd46'
    block_positions['level'] = block_levels
    max_level_count = block_positions.groupby('level')['level'].count().max()
        
    # Assign a row to each block in a delay level, to remove overlap
    # when drawing each delay level as a column of blocks.
    if randomize:
        # Randomize order of blocks in each level column.
        assign_rows = (lambda x: np.random.choice(spread * np.arange(max_level_count).astype(int), len(x),
                                                  replace=False))
    else:
        # Draw blocks in order, from top to bottom, in each level column.
        assign_rows = lambda x: xrange(len(x) - 1, -1, -1)

    block_positions['index'] = (block_positions.groupby('level')
                                ['level'].transform(assign_rows))
    nx.draw_networkx_nodes(net_list_connections,
            pos=block_positions.as_matrix(),
            node_color=block_colors,
            node_shape='s', ax=axis, alpha=alpha,
            node_size=node_size)
    nx.draw_networkx_edges(net_list_connections,
            pos=block_positions.as_matrix(),
            ax=axis, alpha=.1)
    return block_positions

In [19]:
from IPython.html.widgets import interact
import matplotlib.pyplot as plt


def interactive_net_list(time_key='arrival_time', f='max',
                         seed=14, spread=10., randomize=True,
                         node_size=60, alpha=1.):
    np.random.seed(seed)
    fig = plt.figure(figsize=(10, 6))
    axis = fig.add_subplot(111, frameon=False)
    block_positions = plot_net_list(adjacency_list, delay_model,
                                    time_key=time_key, f=f,
                                    spread=spread,
                                    randomize=randomize,
                                    axis=axis,
                                    node_size=node_size,
                                    alpha=alpha)
    axis.yaxis.grid()
    axis.set_yticks([])
    axis.set_xlim(-.5, delay_model.max_arrival_time + .5)
    axis.set_ylim(block_positions['index'].min(),
                  block_positions['index'].max())
    axis.set_xlabel('%s %s' % (f, time_key))

In [20]:
interact(interactive_net_list, time_key=('required_time', 'arrival_time'),
         f=('min', 'max'), seed=(0, 30), spread=(0.1, 2000.),
         node_size=(10, 100), alpha=(0.1, 1.))



In [15]:
interact(interactive_net_list, time_key=('required_time', 'arrival_time'),
         f=('min', 'max'), seed=(0, 30))



In [104]:
Image('https://lh4.googleusercontent.com/-Ux_y9hnBWmo/U1unDIdMU6I/AAAAAAAAEpY/X1jkLUUn-VQ/w1532-h787-no/IMG_20140426_080649.jpg')


Out[104]:

In [13]:
from cyplace_experiments.data import get_net_list_connection_counts

Block arrival times for MCNC net-lists

The following plots show the unit-delay arrival times for the MCNC net-lists.

TODO

  • Calculate the slack of each connection.

In [14]:
for n in get_net_list_connection_counts()[:20]['name']:
    plot_arrival_times(n)