fft_permute.py

from __future__ import print_function
from __future__ import division

import os
from random import randint
from math import log
from pprint import pprint
from collections import OrderedDict
import pickle
from datetime import datetime
dtnow = datetime.now

import numpy as np
from myhdl import *

import gizflo as gf


# ####################################################################
def fft_permute(bank_i, bank_o, clock, stage):
    """
    This module does the FFT 

    Ports
    -----
      bank_i: list of signals input
      bank_o: list of signals output

    Example    
          input  out   out  
      stage 0     1     2
            0 --> 2 --> 1 
            1 --> 3 --> 0
            2 --> 0 --> 3
            3 --> 2 --> 2
    """

    N = len(bank_i)
    butterflies = int(log(N, 2)) # stages
    permutations = np.zeros((butterflies, N), dtype='int64')

    # a neat trick to compute the permutations 
    for n in range(butterflies):
        permutations[n, :] = np.bitwise_xor(np.arange(0, N),
                                            2**(butterflies - n -1))

    #print(permutations)
    rom_map = [None for _ in range(butterflies*N)]

    # in elaboration create a look-up table for the index swap
    for s in range(butterflies):  
        for n in range(N):
            rom_map[s*N + n] = permutations[s, n]
    rom_map = tuple(map(int, rom_map))

    # debugging / manual verification
    #print(rom_map)
    #for ii in range(butterflies):
    #    for n in range(N):
    #        print("[{:4}]: bank_o[{}] = bank_i[{}]".format(
    #            ii, n, rom_map[ii*N + n]))

    # all of the work has been done in elaboration, here we update
    # the output with the signals swapped
    off_map = tuple(range(butterflies))
    @always(clock.posedge)
    def rtl_permute():
        for ii in range(N):
            off = off_map[stage-1]
            idx = rom_map[off + ii]
            bank_o[ii].next = bank_i[idx]

    return rtl_permute


# ####################################################################
def test(N=8, stage=1):
    assert stage > 0 and stage <= log(N, 2)
    bank_i = [Signal(intbv(n, min=-128, max=128)) for n in range(N)]
    bank_o = [Signal(intbv(0, min=-128, max=128)) for n in range(N)]
    clock = Signal(bool(0))

    g = fft_permute(bank_i, bank_o, clock, stage=stage)

    return g


# ####################################################################
def fft_permute_top(clock, sdi, sdo, stage, N=8, W=8):
    
    bcnt =  Signal(intbv(0, min=0, max=W))
    lcnt =  Signal(intbv(0, min=0, max=N))
    wmax = 2**(W-1)  # signed max is half
    wipi = Signal(intbv(0, min=-wmax, max=wmax))
    wipo = Signal(intbv(0, min=-wmax, max=wmax))
    bank_i = [Signal(wipi.val) for _ in range(N)]
    bank_o = [Signal(wipo.val) for _ in range(N)]

    # this doesn't functionally work, would need a second 
    # bank (of inputs or outputs) to hold while getting ...
    @always(clock.posedge)
    def rtl_s2p():
        wipi.next[bcnt] = sdi
        sdo.next = wipo[bcnt]
        if bcnt == W-1:
            bcnt.next = 0
            bank_i[lcnt].next = wipi
            wipo.next = bank_o[lcnt]
            if lcnt == N-1:
                lcnt.next = 0
            else:
                lcnt.next = lcnt + 1
        else:
            bcnt.next = bcnt + 1

    bfly_inst = fft_permute(bank_i, bank_o, clock, stage)

    return rtl_s2p, bfly_inst
    

# ####################################################################
def test_top(N=8, W=8):
    clock = Signal(bool(0))
    sdi = Signal(bool(0))
    sdo = Signal(bool(0))    
    stage = Signal(intbv(0, min=0, max=int(log(N, 2)) ))
    
    def _test_top_stim():
        tbdut = fft_permute_top(clock, sdi, sdo, stage, N=N, W=W)

        @always(delay(5))
        def tbclk():
            clock.next = not clock

        @instance
        def tbstim():            
            for ii in range(N*W*2):
                sdi.next = randint(0, 1)
                yield clock.posedge

            raise StopSimulation
            
        return tbdut, tbclk, tbstim

    if os.path.isfile('_test_top_stim.vcd'):
        os.remove('_test_top_stim.vcd')
    g = traceSignals(_test_top_stim)
    Simulation(g).run()

    toVerilog.directory = 'generated'
    toVerilog(fft_permute_top, clock, sdi, sdo, stage, N=N, W=W)
    toVHDL.directory = 'generated'
    toVHDL(fft_permute_top, clock, sdi, sdo, stage, N=N, W=W)
    

# ####################################################################
def build():
    all_info = OrderedDict()
    for N in [2**ii for ii in range(1,5)]:       #2,8
        for W in [2**ii for ii in range(3, 5)]:  #3,7
            for fpga in ('A', 'X'):
                print("*"*64)
                print("build N={} and W={}".format(N, W))
                ts = dtnow()
                
                # different board names and port names for A vs X
                bname = 'de0nano' if fpga == 'A' else 'xula2'
                port = 'gpio' if fpga == 'A' else 'chan'

                # get a board and map the ports
                brd = gf.get_board(bname)
                brd.add_port_name('sdi', port, 0)
                brd.add_port_name('sdo', port, 1)
                brd.add_port_name('stage', port, slice(2, 2+int(log(N, 2))))

                # set the top-level, get the flow for the board and run
                brd.set_top(top=fft_permute_top, N=N, W=W)
                flow = brd.get_flow()
                try:
                    flow.run()

                    # get the utilization information from the fun
                    info = flow.get_utilization()
                    pprint(info)
                except Exception, err:
                    print("@E: build failed {}".format(err))
                    info = dict(fmax=-1, syn=dict(lut=(0,0,0), 
                                                  reg=(0,0,0), 
                                                  dsp=(0,0,0)))
                # capture the time to build ...
                build_time = dtnow()-ts
                info['build_time'] = build_time

                # save the info/results
                key = "{}.N{}W{}".format(fpga, N, W)
                all_info[key] = info
                print("{} took {} to build".format(key, build_time))
                print("*"*64)

    # Dump the results from all the builds
    pprint(all_info)
    fp = open('build_results.pkl', 'w')
    pickle.dump(all_info, fp)


# ####################################################################
if __name__ == '__main__':
    #test_top(N=8, W=8)
    build()