hardware_sorters.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A Tale of Two Hardware Sorters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There was a recent [Hackaday article](http://hackaday.com/2016/01/20/a-linear-time-sorting-algorithm-for-fpgas/) on a *hardware sorter* that could accept an unsorted list of numbers and return that list in sorted order.\n",
    "This is a subject near and dear to my heart since I built a sorter chip in my first VLSI design class back in 1983.\n",
    "So I thought I'd compare the Hackaday implementation with mine as follows:\n",
    "\n",
    "* Code each sorter in [MyHDL](http://www.myhdl.org/) and simulate its operation.\n",
    "* Build each sorter with an FPGA to gauge how much hardware it takes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preliminary Setup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before implementing each sorter, I need to setup my environment.\n",
    "\n",
    "First, I'll need the `myhdl` package that augments Python with the capability to simulate digital hardware."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from myhdl import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, I'll define the size of the numbers that the sorters will handle.\n",
    "(In this case, the numbers will be *unsigned*, but that's easily changed by making `HS_MIN` a negative number.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "HS_WIDTH = 16\n",
    "HS_MIN = 0\n",
    "HS_MAX = 2**HS_WIDTH"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each sorter will be built as a *stack* of *cells* that will respond to the following set of commands:\n",
    "\n",
    "* `RESET`: Reset all the cells in the stack to `HS_MIN`.\n",
    "* `PUSH`: Enter a new number into the stack.\n",
    "* `POP`: Remove a number from the stack.\n",
    "* `NOP`: Don't do anything; the stack contents remain unchanged."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Cmd = enum('RESET', 'PUSH', 'POP', 'NOP', encoding='binary')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll also define a Python list that will be used to show the contents of the stack as the sorting proceeds.\n",
    "(This is only used during the simulation and doesn't have any effect on the implementation in the FPGA.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "stack = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, setup is done. Now let's build some sorters!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Hackaday Hardware Sorter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The operation of the Hackaday hardware sorter is simple:\n",
    "\n",
    "* The sorter is implemented as a stack of cells, each one storing a single number. An unsorted list of numbers is pushed into the stack, and then a sorted list is read out by popping the stack.\n",
    "* At all times, the numbers in the stack are in order with the largest number near the top of the stack (TOS) and the smallest number deepest within the stack.\n",
    "* When a number is pushed into the stack, it is globally broadcast to each cell. Any cell with a number that is less than the broadcast number will push its number to its neighboring cell on the right. Because the numbers in the stack are always sorted, all the cells that follow a pushed cell will also be pushed because their numbers are also less than the global number. The broadcast number is stored in the left-most pushed cell because that cell is now empty.\n",
    "* When extracting the sorted list, the number in each cell moves leftward to the next cell just like a regular stack.\n",
    "\n",
    "For those who like a more graphical representation of the sorter's operations, here's a pretty picture that shows the broadcast-push-insert-pop operations. Note how the stack contents are always in order.\n",
    "\n",
    "![had_sorter_steps](had_sorter_steps.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Basic Sorting Cell"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Building the Hackaday sorter is done by designing its basic sorting cell and then stacking them together.\n",
    "\n",
    "Here's the I/O needed for the cell:\n",
    "\n",
    "* `clk_i`: The global clock signal that synchronizes the operation of all the cells in the stack.\n",
    "* `cmd_i`: The global bus that carries the current command to all the cells (PUSH, POP, RESET, NOP).\n",
    "* `input_i`: The global bus that carries the number being pushed into the stack.\n",
    "* `shft_i`: The input that tells this cell if the cell to the left is sending its number here.\n",
    "* `left_i`: The input that accepts the number from the cell on the left.\n",
    "* `left_o`: The output that sends the number from this cell to the cell on the right.\n",
    "* `right_i`: The input that accepts the number from the cell on the right.\n",
    "* `right_o`: The output that sends the number from this cell to the one on the right.\n",
    "* `shft_o`: The output that indicates this cell is sending its number to the cell on the right.\n",
    "\n",
    "![Hackaday Sorter Cell](had_sorter_cell.png)\n",
    "\n",
    "The MyHDL code for the basic cell of the Hackaday sorter stack is shown below.\n",
    "There are three code blocks that define the operation of the cell:\n",
    "\n",
    "* A combinational logic block that compares the number stored in the cell with\n",
    "  whatever value is broadcast on the global input bus.\n",
    "* A sequential logic block that updates the cell's number on every rising\n",
    "  clock edge based on the operation being performed (PUSH, POP or RESET).\n",
    "* A final combinational logic block that always outputs the number in the cell\n",
    "  to the cells on either side and also tells the cell on the right when\n",
    "  data is being shifted over to it.\n",
    "  \n",
    "There is a final block of code that's only used during simulation. It copies the number from\n",
    "a cell in the stack into the equivalent position in a global array. The global array is used\n",
    "to observe the contents of the stack as the sorting proceeds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def had_hs_cell(clk_i, cmd_i, input_i, shft_i, left_i, left_o, right_i, right_o, shft_o, index):\n",
    "    '''Basic cell for Hackaday hardware sorter:\n",
    "            clk_i: The global clock signal.\n",
    "            cmd_i: The current command to be executed.\n",
    "            input_i: The global bus with the number being pushed into the stack.\n",
    "            shft_i: This input is true if the cell to the left is sending its number here.\n",
    "            left_i: The input that accepts the number from the cell on the left.\n",
    "            left_o: The output that sends the register contents from this cell to the one on the left.\n",
    "            right_i: The input that accepts the number from the cell on the right.\n",
    "            right_o: The output that sends the register contents from this cell to the one on the right.\n",
    "            shft_o: This output is true if this cell is sending its register contents to the right.\n",
    "            index: The position of this cell in the stack. (Used only during simulation.)\n",
    "    '''\n",
    "\n",
    "    a = Signal(intbv(0,HS_MIN,HS_MAX))  # This register holds the number in the cell.\n",
    "    a_lt_input = Signal(bool(0))  # This signal is true if the register contents are less than the input number.\n",
    "    \n",
    "    # This combinational logic block continually compares the contents \n",
    "    # of the cell register to the number on the global input bus.\n",
    "    @always_comb\n",
    "    def compare_a_input():\n",
    "        a_lt_input.next = (a < input_i)\n",
    "    \n",
    "    # This sequential logic block updates the value in the cell register\n",
    "    # on the rising edge of the clock signal.\n",
    "    @always_seq(clk_i.posedge, reset=None)\n",
    "    def update_a():\n",
    "        if cmd_i == Cmd.RESET:\n",
    "            a.next = HS_MIN  # Upon reset, set the cell register to the minimum possible value.\n",
    "        elif cmd_i == Cmd.PUSH:\n",
    "            # Handle pushing of data into the cell stack.\n",
    "            if shft_i:\n",
    "                # If the cell to the left is outputing its value, then this cell has to take it.\n",
    "                a.next = left_i\n",
    "            elif a_lt_input:\n",
    "                # If the global input number is greater than the number in this cell\n",
    "                # but the cell to the left isn't outputing its number, then\n",
    "                # load the global input number into this cell register.\n",
    "                a.next = input_i\n",
    "        elif cmd_i == Cmd.POP:\n",
    "            # When popping data from the stack, always accept the number from the cell on the immediate right.\n",
    "            a.next = right_i\n",
    "    \n",
    "    # This combinational logic block controls the outputs from this cell.\n",
    "    @always_comb\n",
    "    def output_l_r():\n",
    "        # The register contents are always made available to the cells on the right and left.\n",
    "        right_o.next = a\n",
    "        left_o.next = a\n",
    "        # Tell the next cell on the right that data is coming if the number in this cell \n",
    "        # is less than the number on the global bus.\n",
    "        shft_o.next = a_lt_input or shft_i\n",
    "\n",
    "    # This combinational block is only used during simulation. It places the number in the\n",
    "    # cell register into the stack list at the index of this cell.\n",
    "    if observe:\n",
    "        global stack  # For showing the stack contents during simulation.\n",
    "\n",
    "        @always_comb\n",
    "        def observe_a_b():\n",
    "            stack[index] = (int(a.val),)\n",
    "            \n",
    "    return instances()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stacking the Cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The stack for the Hackaday sorter is built by concatenating the basic cells as shown below.\n",
    "\n",
    "![Hackaday sorter stack connections](had_sorter_stack.png)\n",
    "\n",
    "The signals that go in to and out of the stack are:\n",
    "\n",
    "* `clk_i`: The global clock signal.\n",
    "* `cmd_i`: The current command to be executed.\n",
    "* `unsorted_i`: The input bus for entering unsorted data.\n",
    "* `sorted_o`: The output bus for reading the sorted data.\n",
    "\n",
    "The MyHDL code for connecting the basic sorting cells is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def had_hs(clk_i, cmd_i, unsorted_i, sorted_o, n_cells):\n",
    "    '''Hackaday hardware sorter stack:\n",
    "            clk_i: The global clock signal.\n",
    "            cmd_i: The current command to be executed.\n",
    "            unsorted_i: The input bus for entering unsorted data.\n",
    "            sorted_o: The output bus for reading the sorted data.\n",
    "            n_cells: The number of cells to include in the stack.\n",
    "    '''\n",
    "    \n",
    "    # These are the buses that take data from the cell on the left to the one on the right.\n",
    "    l2r = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(0,n_cells+1)]\n",
    "    # These are the buses that take data from the cell on the right to the one on the left.\n",
    "    r2l = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(0,n_cells+1)]\n",
    "    \n",
    "    # These signals tell the cell on the right when they must accept data from the cell on the left.\n",
    "    shft = [Signal(bool(0)) for _ in range(0,n_cells+1)]\n",
    "    \n",
    "    # No cell exists before the left-most cell, so inactivate the left-most shift input.\n",
    "    shft[0] = bool(0)\n",
    "    l2r[0] = 0\n",
    "\n",
    "    # No cell exists after the right-most cell, so shift in the minimal value from the right.\n",
    "    r2l[n_cells] = HS_MIN\n",
    "\n",
    "    # The sorted output from the stack comes from the output of the left-most cell.\n",
    "    r2l[0] = sorted_o\n",
    "    \n",
    "    # Connect each cell to its left and right neighbors and to the global input bus.\n",
    "    cells = []\n",
    "    for i in range(0, n_cells):\n",
    "        cell = had_hs_cell(clk_i, cmd_i, unsorted_i, shft[i], l2r[i], r2l[i],\n",
    "                            r2l[i+1], l2r[i+1], shft[i+1], i)\n",
    "        cells.append(cell)\n",
    "    \n",
    "    return cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Simulation Testbench"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that the sorter is assembled, I need something to drive it during simulation to see if it works correctly. The following *testbench* does that like so:\n",
    "\n",
    "1. It first instantiates the hardware sorter module and connects signals to its I/O ports.\n",
    "2. Then the sorter is reset.\n",
    "3. The numbers from an unsorted list are pushed into the stack through a series of clock pulses.\n",
    "   The number stored in each cell is printed after each clock pulse so I can watch the progress of the sorter.\n",
    "4. The sorted list is popped from the stack in a similar manner.\n",
    "5. The unsorted and sorted lists are printed for comparison.\n",
    "6. The built-in Python `sort()` function is used to sort the original list of numbers and then compare them to the\n",
    "   output from the hardware sorter to verify that it operated correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hs_tb(hdw_sorter, unsorted_list, n_cells):\n",
    "    '''Hardware sorter testbench:\n",
    "            hdw_sorter: The name of the hardware sorter to be tested.\n",
    "            unsorted_list: An unsorted list of numbers.\n",
    "            n_cells: The number of cells to include in the hardware sorter.\n",
    "    '''\n",
    "    \n",
    "    # Declare some signals that interface to the hardware sorter.\n",
    "    clk = Signal(bool(0))\n",
    "    cmd = Signal(Cmd.RESET)\n",
    "    in_bus, out_bus = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(2)]\n",
    "    \n",
    "    # Instantiate the hardware sorter with the connections declared above.\n",
    "    hs_inst = hdw_sorter(clk, cmd, in_bus, out_bus, n_cells)\n",
    "\n",
    "    # The interface signals are driven in this block.\n",
    "    @instance\n",
    "    def tb():\n",
    "        \n",
    "        # A subroutine for showing the contents of the sorter cell registers.\n",
    "        def show_stack(dir_arrow):\n",
    "            s = ''\n",
    "            for cell in stack:\n",
    "                s += ' {} ( '.format(dir_arrow)\n",
    "                for reg in cell:\n",
    "                    s += '{:>5d} '.format(reg)\n",
    "                s += ')'\n",
    "            return s\n",
    "        \n",
    "        # Initialize the global list for recording the cell register contents in the stack.\n",
    "        global stack\n",
    "        stack = [0] * n_cells\n",
    "        \n",
    "        # Reset the hardware sorter.\n",
    "        print('\\nRESET:')\n",
    "        cmd.next = Cmd.RESET  # Set the command input.\n",
    "        # Pulse the clock low and then high.\n",
    "        clk.next = 0\n",
    "        yield(delay(1))\n",
    "        clk.next = 1\n",
    "        yield(delay(1))\n",
    "        # Print the state of the cell registers after reset.\n",
    "        print '     ', show_stack('  ')\n",
    "        \n",
    "        # Push the unsorted numbers into the sorter.\n",
    "        print('\\nPUSH:')\n",
    "        cmd.next = Cmd.PUSH  # Set the command input.\n",
    "        for num in unsorted_list:\n",
    "            # Print the state of the cell registers and the current input number.\n",
    "            print '{:>5d}'.format(num), show_stack('=>')\n",
    "            # Send in the next number from the unsorted list.\n",
    "            in_bus.next = num\n",
    "            # Pulse the clock.\n",
    "            clk.next = 0\n",
    "            yield(delay(1))\n",
    "            clk.next = 1\n",
    "            yield(delay(1))\n",
    "\n",
    "        # Print the state of the cell registers after the unsorted list has been pushed in.\n",
    "        print '     ', show_stack('  ')\n",
    "            \n",
    "        # Pop the sorted numbers out of the sorter.\n",
    "        print('\\nPOP:')\n",
    "        sorted_list = []  # Clear the list that will hold the sorted numbers.\n",
    "        cmd.next = Cmd.POP  # Set the command input.\n",
    "        for _ in unsorted_list:\n",
    "            # Grab the current output from the sorter.\n",
    "            sorted_list.append(int(out_bus.val))\n",
    "            # Pulse the clock.\n",
    "            clk.next = 0\n",
    "            yield(delay(1))\n",
    "            clk.next = 1\n",
    "            yield(delay(1))\n",
    "            # Print the state of the cell registers and the current output number.\n",
    "            print '{:>5d}'.format(sorted_list[-1]), show_stack('<=')\n",
    "            \n",
    "        # The testbench simulation is done at this point.\n",
    "        # Now just display and verify the results.\n",
    "\n",
    "        # A subroutine for printing lists of numbers.\n",
    "        def print_list(l):\n",
    "            for i, n in enumerate(l,1):\n",
    "                print('{:>7d}'.format(n)),\n",
    "                if i%10 == 0:\n",
    "                    print('')\n",
    "            print('\\n')\n",
    " \n",
    "        # Print the original unsorted list and the sorted list from the sorter.\n",
    "        print('')\n",
    "        print('Unsorted list:')\n",
    "        print_list(unsorted_list)\n",
    "        print('Sorted list:')\n",
    "        print_list(sorted_list)\n",
    "        \n",
    "        # Use Python sort() function to sort the unsorted list and compare it to the\n",
    "        # output list from the sorter.\n",
    "        verify_list = unsorted_list[:]\n",
    "        verify_list.sort()\n",
    "        if sorted_list == verify_list[::-1]:\n",
    "            print('SUCCESS: List is correctly sorted!')\n",
    "        else:\n",
    "            print('ERROR: list is not correctly sorted!')\n",
    "            \n",
    "    return instances()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulation Results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I'll create a list of unsorted numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random # Python package for generating random numbers.\n",
    "LIST_LEN = 8\n",
    "unsorted_list = [random.randrange(HS_MIN, HS_MAX) for _ in range(LIST_LEN)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then I can pass the unsorted numbers to the testbench along with the Hackaday sorter\n",
    "and see the results of the simulation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "RESET:\n",
      "          (     0 )    (     0 )    (     0 )    (     0 )    (     0 )    (     0 )    (     0 )    (     0 )\n",
      "\n",
      "PUSH:\n",
      "51275  => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 )\n",
      " 9085  => ( 51275 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 )\n",
      "49041  => ( 51275 ) => (  9085 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 )\n",
      "44215  => ( 51275 ) => ( 49041 ) => (  9085 ) => (     0 ) => (     0 ) => (     0 ) => (     0 ) => (     0 )\n",
      "46660  => ( 51275 ) => ( 49041 ) => ( 44215 ) => (  9085 ) => (     0 ) => (     0 ) => (     0 ) => (     0 )\n",
      "19190  => ( 51275 ) => ( 49041 ) => ( 46660 ) => ( 44215 ) => (  9085 ) => (     0 ) => (     0 ) => (     0 )\n",
      " 8925  => ( 51275 ) => ( 49041 ) => ( 46660 ) => ( 44215 ) => ( 19190 ) => (  9085 ) => (     0 ) => (     0 )\n",
      "28920  => ( 51275 ) => ( 49041 ) => ( 46660 ) => ( 44215 ) => ( 19190 ) => (  9085 ) => (  8925 ) => (     0 )\n",
      "          ( 51275 )    ( 49041 )    ( 46660 )    ( 44215 )    ( 28920 )    ( 19190 )    (  9085 )    (  8925 )\n",
      "\n",
      "POP:\n",
      "51275  <= ( 49041 ) <= ( 46660 ) <= ( 44215 ) <= ( 28920 ) <= ( 19190 ) <= (  9085 ) <= (  8925 ) <= (     0 )\n",
      "49041  <= ( 46660 ) <= ( 44215 ) <= ( 28920 ) <= ( 19190 ) <= (  9085 ) <= (  8925 ) <= (     0 ) <= (     0 )\n",
      "46660  <= ( 44215 ) <= ( 28920 ) <= ( 19190 ) <= (  9085 ) <= (  8925 ) <= (     0 ) <= (     0 ) <= (     0 )\n",
      "44215  <= ( 28920 ) <= ( 19190 ) <= (  9085 ) <= (  8925 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 )\n",
      "28920  <= ( 19190 ) <= (  9085 ) <= (  8925 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 )\n",
      "19190  <= (  9085 ) <= (  8925 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 )\n",
      " 9085  <= (  8925 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 )\n",
      " 8925  <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 ) <= (     0 )\n",
      "\n",
      "Unsorted list:\n",
      "  51275    9085   49041   44215   46660   19190    8925   28920 \n",
      "\n",
      "Sorted list:\n",
      "  51275   49041   46660   44215   28920   19190    9085    8925 \n",
      "\n",
      "SUCCESS: List is correctly sorted!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<class 'myhdl.StopSimulation'>: No more events\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "observe = True\n",
    "Simulation(hs_tb(had_hs, unsorted_list, LIST_LEN)).run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the printed results, you can see where new numbers are inserted into the stack during the PUSH phase, and that the stack contents are always in descending order.\n",
    "Then, removing the sorted list is just a matter of repeatedly popping the stack during the POP phase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FPGA Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After all the work of simulating the Hackaday sorter, creating the Verilog code for it is surprisingly easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "// File: had_hs.v\n",
      "// Generated by MyHDL 1.0dev\n",
      "// Date: Wed Feb 24 22:35:25 2016\n",
      "\n",
      "\n",
      "`timescale 1ns/10ps\n",
      "\n",
      "module had_hs (\n",
      "    clk_i,\n",
      "    cmd_i,\n",
      "    unsorted_i,\n",
      "    sorted_o\n",
      ");\n",
      "// Hackaday hardware sorter stack:\n",
      "// clk_i: The global clock signal.\n",
      "// cmd_i: The current command to be executed.\n",
      "// unsorted_i: The input bus for entering unsorted data.\n",
      "// sorted_o: The output bus for reading the sorted data.\n",
      "// n_cells: The number of cells to include in the stack.\n",
      "\n",
      "input clk_i;\n",
      "input [1:0] cmd_i;\n",
      "input [15:0] unsorted_i;\n",
      "output [15:0] sorted_o;\n",
      "wire [15:0] sorted_o;\n",
      "\n",
      "reg [15:0] cell_a;\n",
      "wire [15:0] cell_left_o;\n",
      "wire [15:0] cell_left_i;\n",
      "wire [15:0] cell_right_o;\n",
      "wire cell_shft_o;\n",
      "wire cell_a_lt_input;\n",
      "wire cell_shft_i;\n",
      "reg [15:0] cells_6_a;\n",
      "wire [15:0] cells_6_left_o;\n",
      "wire [15:0] cells_6_left_i;\n",
      "wire cells_6_a_lt_input;\n",
      "wire cells_6_shft_i;\n",
      "reg [15:0] cells_5_a;\n",
      "wire [15:0] cells_5_left_o;\n",
      "wire [15:0] cells_5_left_i;\n",
      "wire cells_5_a_lt_input;\n",
      "wire cells_5_shft_i;\n",
      "reg [15:0] cells_4_a;\n",
      "wire [15:0] cells_4_left_o;\n",
      "wire [15:0] cells_4_left_i;\n",
      "wire cells_4_a_lt_input;\n",
      "wire cells_4_shft_i;\n",
      "reg [15:0] cells_3_a;\n",
      "wire [15:0] cells_3_left_o;\n",
      "wire [15:0] cells_3_left_i;\n",
      "wire cells_3_a_lt_input;\n",
      "wire cells_3_shft_i;\n",
      "reg [15:0] cells_2_a;\n",
      "wire [15:0] cells_2_left_o;\n",
      "wire [15:0] cells_2_left_i;\n",
      "wire cells_2_a_lt_input;\n",
      "wire cells_2_shft_i;\n",
      "reg [15:0] cells_1_a;\n",
      "wire [15:0] cells_1_left_o;\n",
      "wire [15:0] cells_1_left_i;\n",
      "wire cells_1_a_lt_input;\n",
      "wire cells_1_shft_i;\n",
      "reg [15:0] cells_0_a;\n",
      "wire cells_0_a_lt_input;\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_0_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_0_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (1'b0) begin\n",
      "                cells_0_a <= 0;\n",
      "            end\n",
      "            else if (cells_0_a_lt_input) begin\n",
      "                cells_0_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_0_a <= cells_1_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_0_a_lt_input = (cells_0_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cells_1_left_i = cells_0_a;\n",
      "assign sorted_o = cells_0_a;\n",
      "assign cells_1_shft_i = (cells_0_a_lt_input || 1'b0);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_1_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_1_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_1_shft_i) begin\n",
      "                cells_1_a <= cells_1_left_i;\n",
      "            end\n",
      "            else if (cells_1_a_lt_input) begin\n",
      "                cells_1_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_1_a <= cells_2_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_1_a_lt_input = (cells_1_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cells_2_left_i = cells_1_a;\n",
      "assign cells_1_left_o = cells_1_a;\n",
      "assign cells_2_shft_i = (cells_1_a_lt_input || cells_1_shft_i);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_2_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_2_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_2_shft_i) begin\n",
      "                cells_2_a <= cells_2_left_i;\n",
      "            end\n",
      "            else if (cells_2_a_lt_input) begin\n",
      "                cells_2_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_2_a <= cells_3_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_2_a_lt_input = (cells_2_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cells_3_left_i = cells_2_a;\n",
      "assign cells_2_left_o = cells_2_a;\n",
      "assign cells_3_shft_i = (cells_2_a_lt_input || cells_2_shft_i);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_3_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_3_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_3_shft_i) begin\n",
      "                cells_3_a <= cells_3_left_i;\n",
      "            end\n",
      "            else if (cells_3_a_lt_input) begin\n",
      "                cells_3_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_3_a <= cells_4_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_3_a_lt_input = (cells_3_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cells_4_left_i = cells_3_a;\n",
      "assign cells_3_left_o = cells_3_a;\n",
      "assign cells_4_shft_i = (cells_3_a_lt_input || cells_3_shft_i);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_4_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_4_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_4_shft_i) begin\n",
      "                cells_4_a <= cells_4_left_i;\n",
      "            end\n",
      "            else if (cells_4_a_lt_input) begin\n",
      "                cells_4_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_4_a <= cells_5_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_4_a_lt_input = (cells_4_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cells_5_left_i = cells_4_a;\n",
      "assign cells_4_left_o = cells_4_a;\n",
      "assign cells_5_shft_i = (cells_4_a_lt_input || cells_4_shft_i);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_5_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_5_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_5_shft_i) begin\n",
      "                cells_5_a <= cells_5_left_i;\n",
      "            end\n",
      "            else if (cells_5_a_lt_input) begin\n",
      "                cells_5_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_5_a <= cells_6_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_5_a_lt_input = (cells_5_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cells_6_left_i = cells_5_a;\n",
      "assign cells_5_left_o = cells_5_a;\n",
      "assign cells_6_shft_i = (cells_5_a_lt_input || cells_5_shft_i);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELLS_6_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_6_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_6_shft_i) begin\n",
      "                cells_6_a <= cells_6_left_i;\n",
      "            end\n",
      "            else if (cells_6_a_lt_input) begin\n",
      "                cells_6_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cells_6_a <= cell_left_o;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_6_a_lt_input = (cells_6_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cell_left_i = cells_6_a;\n",
      "assign cells_6_left_o = cells_6_a;\n",
      "assign cell_shft_i = (cells_6_a_lt_input || cells_6_shft_i);\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: HAD_HS_CELL_UPDATE_A\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cell_a <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cell_shft_i) begin\n",
      "                cell_a <= cell_left_i;\n",
      "            end\n",
      "            else if (cell_a_lt_input) begin\n",
      "                cell_a <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            cell_a <= 0;\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cell_a_lt_input = (cell_a < unsorted_i);\n",
      "\n",
      "\n",
      "\n",
      "assign cell_right_o = cell_a;\n",
      "assign cell_left_o = cell_a;\n",
      "assign cell_shft_o = (cell_a_lt_input || cell_shft_i);\n",
      "\n",
      "endmodule\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "** ToVerilogWarning: Signal is driven but not read: cell_right_o\n",
      "** ToVerilogWarning: Signal is driven but not read: cell_shft_o\n"
     ]
    }
   ],
   "source": [
    "# Turn off the section of code that's only used during simulation.\n",
    "observe = False\n",
    "\n",
    "# Create the connecting buses for the sorter.\n",
    "clk = Signal(bool(0))\n",
    "cmd = Signal(Cmd.RESET)\n",
    "unsorted_bus, sorted_bus = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(2)]\n",
    "\n",
    "# Create the Verilog code for the sorter.\n",
    "LIST_LEN = 8\n",
    "toVerilog(had_hs, clk, cmd, unsorted_bus, sorted_bus, LIST_LEN)\n",
    "\n",
    "# Show the Verilog file for the implementation and store it in another\n",
    "# Verilog file with the size of the list it can sort.\n",
    "with open('had_hs.v') as fr:\n",
    "    verilog_src = fr.read()\n",
    "    print(verilog_src)\n",
    "    fw = open('had_hs_{}.v'.format(LIST_LEN), 'w')\n",
    "    fw.write(verilog_src)\n",
    "    fw.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The IBM Hardware Sorter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The hardware sorter I built back in 1983 was based on an [IBM design](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.5786&rep=rep1&type=pdf).\n",
    "It's similar to the Hackaday sorter with a few differences:\n",
    "\n",
    "* The sorter is implemented as a stack of cells with *two numbers* stored in each cell. An unsorted list of numbers is \n",
    "  pushed into the stack, and then a sorted list is read out by popping the stack.\n",
    "* When a number is pushed into the stack, it is sent only to the left-most cell. That cell sends the smaller \n",
    "  of the two numbers it stores to the next cell on the right while storing the incoming value in the vacated spot. The cell on the right does the same procedure,\n",
    "  and so on through the entire stack. The net effect is that the smaller numbers propagate rightward through the stack, but\n",
    "  the stack doesn't necessarilty have all the numbers correctly sorted at any time.\n",
    "* When extracting the sorted list, the left-most cell outputs the larger of its two numbers. That number is replaced with\n",
    "  the larger of the two numbers from the next cell on the right. This process repeats throughout the entire stack with \n",
    "  the net effect that the larger numbers propagate leftward through the stack.\n",
    "\n",
    "It's not immediately obvious that the procedure described above will result in a sorted list being popped from the stack.\n",
    "You can get a better feel for how the IBM sorter works by looking at the simulation output below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Basic Sorting Cell"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic cell for the IBM sorter has I/O signals similar to the Hackaday cell minus the\n",
    "global input number bus and the shift signals.\n",
    "\n",
    "![IBM Sorter Cell](ibm_sorter_cell.png)\n",
    "\n",
    "The MyHDL code for the basic cell of the IBM sorter stack is shown below.\n",
    "There are three code blocks that define the operation of the cell:\n",
    "\n",
    "* A combinational logic block that compares the two numbers stored in the cell.\n",
    "* A sequential logic block that updates the two numbers on every rising\n",
    "  clock edge based on the operation being performed (PUSH, POP or RESET).\n",
    "* A final combinational logic block that always outputs the larger number in the cell\n",
    "  to the left and the smaller number to the right.\n",
    "  \n",
    "As with the Hackaday sorter, there's a final block of code that's only used during simulation\n",
    "to observe the contents of the stack as the sorting proceeds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ibm_hs_cell(clk_i, cmd_i, left_i, left_o, right_i, right_o, index):\n",
    "    '''Basic cell for IBM hardware sorter:\n",
    "            clk_i: The global clock signal.\n",
    "            cmd_i: The current command to be executed.\n",
    "            left_i: The input that accepts the number from the cell on the left.\n",
    "            left_o: The output that sends a number from this cell to the one on the left.\n",
    "            right_i: The input that accepts the number from the cell on the right.\n",
    "            right_o: The output that sends a number from this cell to the one on the right.\n",
    "            index: This is the position of this cell in the stack. (Used only during simulation.)\n",
    "    '''\n",
    "    \n",
    "    global stack  # For showing the stack contents during simulation.\n",
    "    \n",
    "    a, b = [Signal(intbv(0, HS_MIN, HS_MAX)) for _ in range(2)]  # Two registers for storing numbers.\n",
    "    a_lt_b = Signal(bool(0))  # True if number in register a is less than number in register b.\n",
    "    \n",
    "    # This combinational logic block continually compares the contents \n",
    "    # of cell register a to the contents of cell register b.\n",
    "    @always_comb\n",
    "    def compare_a_b():\n",
    "        a_lt_b.next = (a < b)\n",
    "    \n",
    "    # This sequential logic block updates the value in the cell registers\n",
    "    # on the rising edge of the clock signal.\n",
    "    @always_seq(clk_i.posedge, reset=None)\n",
    "    def update_a_b():\n",
    "        if cmd_i == Cmd.RESET:\n",
    "            # Upon reset, set the registers to their minimum possible values.\n",
    "            a.next = HS_MIN\n",
    "            b.next = HS_MIN\n",
    "        elif cmd_i == Cmd.PUSH:\n",
    "            # When pushing data into the cell, place the number entering from\n",
    "            # the left into the register containing the smallest number since\n",
    "            # that number will be sent to the cell on the right.\n",
    "            if a_lt_b:\n",
    "                a.next = left_i\n",
    "            else:\n",
    "                b.next = left_i\n",
    "        elif cmd_i == Cmd.POP:\n",
    "            # When popping data from the cell, place the number entering from\n",
    "            # the right into the register containing the largest number since\n",
    "            # that number will be sent to the cell on the left.\n",
    "            if a_lt_b:\n",
    "                b.next = right_i\n",
    "            else:\n",
    "                a.next = right_i\n",
    "\n",
    "    # This combinational logic block continually outputs:\n",
    "    #   1) the smaller of the a or b registers goes to the right,\n",
    "    #   2) the larger of the a or b registers goes to the left.\n",
    "    @always_comb\n",
    "    def output_l_r():\n",
    "        if a_lt_b:\n",
    "            left_o.next = b\n",
    "            right_o.next = a\n",
    "        else:\n",
    "            left_o.next = a\n",
    "            right_o.next = b\n",
    "\n",
    "    # This combinational block is only used during simulation. It places the numbers\n",
    "    # in the cell registers into the stack list at the index of this cell.\n",
    "    if observe:\n",
    "        @always_comb\n",
    "        def observe_a_b():\n",
    "            stack[index] = (int(a.val),int(b.val))\n",
    "            \n",
    "    return instances()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stacking the Cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The stack for the IBM sorter is built by concatenating the basic cells as shown below.\n",
    "\n",
    "![IBM sorter stack connections](ibm_sorter_stack.png)\n",
    "\n",
    "The I/O signals for the stack are the same as for the Hackaday sorter stack:\n",
    "\n",
    "* `clk_i`: The global clock signal.\n",
    "* `cmd_i`: The current command to be executed.\n",
    "* `unsorted_i`: The input bus for entering unsorted data.\n",
    "* `sorted_o`: The output bus for reading the sorted data.\n",
    "\n",
    "The MyHDL code for connecting the basic sorting cells is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ibm_hs(clk_i, cmd_i, unsorted_i, sorted_o, n_cells):\n",
    "    '''IBM hardware sorter stack:\n",
    "            clk_i: The global clock signal.\n",
    "            cmd_i: The current command to be executed.\n",
    "            unsorted_i: The input bus for entering unsorted data.\n",
    "            sorted_o: The output bus for reading the sorted data.\n",
    "            n_cells: The number of cells to include in the stack.\n",
    "    '''\n",
    "\n",
    "    # These are the buses that take data from the cell on the left to the one on the right.\n",
    "    l2r = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(0,n_cells+1)]\n",
    "    # These are the buses that take data from the cell on the right to the one on the left.\n",
    "    r2l = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(0,n_cells+1)]\n",
    "\n",
    "    # The unsorted input to the stack goes into the left-most cell.\n",
    "    l2r[0] = unsorted_i\n",
    "\n",
    "    # The unsorted output from the stack comes from the output of the left-most cell.\n",
    "    r2l[0] = sorted_o\n",
    "    \n",
    "    # No cell exists after the right-most cell, so shift in the minimal value from the right.\n",
    "    r2l[n_cells] = HS_MIN\n",
    "    \n",
    "    # Connect each cell to the buses of its left and right neighbors.\n",
    "    cells = []\n",
    "    for i in range(0, n_cells):\n",
    "        cell = ibm_hs_cell(clk_i, cmd_i, l2r[i], r2l[i], r2l[i+1], l2r[i+1], i)\n",
    "        cells.append(cell)\n",
    "    \n",
    "    return cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulation Results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just as I did for the Hackaday sorter, I can pass the IBM sorter to the testbench along with the list of unsorted numbers and see what happens. (For the IBM sorter, the number of sorter cells is only half the size of the list since each cell stores two numbers.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "RESET:\n",
      "          (     0     0 )    (     0     0 )    (     0     0 )    (     0     0 )\n",
      "\n",
      "PUSH:\n",
      "51275  => (     0     0 ) => (     0     0 ) => (     0     0 ) => (     0     0 )\n",
      " 9085  => (     0 51275 ) => (     0     0 ) => (     0     0 ) => (     0     0 )\n",
      "49041  => (  9085 51275 ) => (     0     0 ) => (     0     0 ) => (     0     0 )\n",
      "44215  => ( 49041 51275 ) => (     0  9085 ) => (     0     0 ) => (     0     0 )\n",
      "46660  => ( 44215 51275 ) => ( 49041  9085 ) => (     0     0 ) => (     0     0 )\n",
      "19190  => ( 46660 51275 ) => ( 49041 44215 ) => (     0  9085 ) => (     0     0 )\n",
      " 8925  => ( 19190 51275 ) => ( 49041 46660 ) => ( 44215  9085 ) => (     0     0 )\n",
      "28920  => (  8925 51275 ) => ( 49041 19190 ) => ( 44215 46660 ) => (     0  9085 )\n",
      "          ( 28920 51275 )    ( 49041  8925 )    ( 19190 46660 )    ( 44215  9085 )\n",
      "\n",
      "POP:\n",
      "51275  <= ( 28920 49041 ) <= ( 46660  8925 ) <= ( 19190 44215 ) <= (     0  9085 )\n",
      "49041  <= ( 28920 46660 ) <= ( 44215  8925 ) <= ( 19190  9085 ) <= (     0     0 )\n",
      "46660  <= ( 28920 44215 ) <= ( 19190  8925 ) <= (     0  9085 ) <= (     0     0 )\n",
      "44215  <= ( 28920 19190 ) <= (  9085  8925 ) <= (     0     0 ) <= (     0     0 )\n",
      "28920  <= (  9085 19190 ) <= (     0  8925 ) <= (     0     0 ) <= (     0     0 )\n",
      "19190  <= (  9085  8925 ) <= (     0     0 ) <= (     0     0 ) <= (     0     0 )\n",
      " 9085  <= (     0  8925 ) <= (     0     0 ) <= (     0     0 ) <= (     0     0 )\n",
      " 8925  <= (     0     0 ) <= (     0     0 ) <= (     0     0 ) <= (     0     0 )\n",
      "\n",
      "Unsorted list:\n",
      "  51275    9085   49041   44215   46660   19190    8925   28920 \n",
      "\n",
      "Sorted list:\n",
      "  51275   49041   46660   44215   28920   19190    9085    8925 \n",
      "\n",
      "SUCCESS: List is correctly sorted!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<class 'myhdl.StopSimulation'>: No more events\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "observe = True\n",
    "Simulation(hs_tb(ibm_hs, unsorted_list, len(unsorted_list)/2)).run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By looking at the stack contents above, you can see the smaller of the two numbers in each cell is propagated rightward\n",
    "during the PUSH phase, while the larger number moves leftward during the POP phase.\n",
    "At no time does the stack contain a strictly sorted list (unless the original list of numbers was sorted to begin with)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FPGA Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I can create the Verilog code for the IBM sorter like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "// File: ibm_hs.v\n",
      "// Generated by MyHDL 1.0dev\n",
      "// Date: Wed Feb 24 22:35:25 2016\n",
      "\n",
      "\n",
      "`timescale 1ns/10ps\n",
      "\n",
      "module ibm_hs (\n",
      "    clk_i,\n",
      "    cmd_i,\n",
      "    unsorted_i,\n",
      "    sorted_o\n",
      ");\n",
      "// IBM hardware sorter stack:\n",
      "// clk_i: The global clock signal.\n",
      "// cmd_i: The current command to be executed.\n",
      "// unsorted_i: The input bus for entering unsorted data.\n",
      "// sorted_o: The output bus for reading the sorted data.\n",
      "// n_cells: The number of cells to include in the stack.\n",
      "\n",
      "input clk_i;\n",
      "input [1:0] cmd_i;\n",
      "input [15:0] unsorted_i;\n",
      "output [15:0] sorted_o;\n",
      "reg [15:0] sorted_o;\n",
      "\n",
      "reg [15:0] cell_a;\n",
      "reg [15:0] cell_left_o;\n",
      "wire cell_a_lt_b;\n",
      "reg [15:0] cell_right_o;\n",
      "reg [15:0] cell_b;\n",
      "reg [15:0] cell_left_i;\n",
      "reg [15:0] cells_0_a;\n",
      "wire cells_0_a_lt_b;\n",
      "reg [15:0] cells_0_b;\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: IBM_HS_CELLS_0_UPDATE_A_B\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cells_0_a <= 0;\n",
      "            cells_0_b <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cells_0_a_lt_b) begin\n",
      "                cells_0_a <= unsorted_i;\n",
      "            end\n",
      "            else begin\n",
      "                cells_0_b <= unsorted_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            if (cells_0_a_lt_b) begin\n",
      "                cells_0_b <= cell_left_o;\n",
      "            end\n",
      "            else begin\n",
      "                cells_0_a <= cell_left_o;\n",
      "            end\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cells_0_a_lt_b = (cells_0_a < cells_0_b);\n",
      "\n",
      "\n",
      "always @(cells_0_a, cells_0_b, cells_0_a_lt_b) begin: IBM_HS_CELLS_0_OUTPUT_L_R\n",
      "    if (cells_0_a_lt_b) begin\n",
      "        sorted_o = cells_0_b;\n",
      "        cell_left_i = cells_0_a;\n",
      "    end\n",
      "    else begin\n",
      "        sorted_o = cells_0_a;\n",
      "        cell_left_i = cells_0_b;\n",
      "    end\n",
      "end\n",
      "\n",
      "\n",
      "always @(posedge clk_i) begin: IBM_HS_CELL_UPDATE_A_B\n",
      "    case (cmd_i)\n",
      "        2'b00: begin\n",
      "            cell_a <= 0;\n",
      "            cell_b <= 0;\n",
      "        end\n",
      "        2'b01: begin\n",
      "            if (cell_a_lt_b) begin\n",
      "                cell_a <= cell_left_i;\n",
      "            end\n",
      "            else begin\n",
      "                cell_b <= cell_left_i;\n",
      "            end\n",
      "        end\n",
      "        2'b10: begin\n",
      "            if (cell_a_lt_b) begin\n",
      "                cell_b <= 0;\n",
      "            end\n",
      "            else begin\n",
      "                cell_a <= 0;\n",
      "            end\n",
      "        end\n",
      "    endcase\n",
      "end\n",
      "\n",
      "\n",
      "\n",
      "assign cell_a_lt_b = (cell_a < cell_b);\n",
      "\n",
      "\n",
      "always @(cell_a, cell_b, cell_a_lt_b) begin: IBM_HS_CELL_OUTPUT_L_R\n",
      "    if (cell_a_lt_b) begin\n",
      "        cell_left_o = cell_b;\n",
      "        cell_right_o = cell_a;\n",
      "    end\n",
      "    else begin\n",
      "        cell_left_o = cell_a;\n",
      "        cell_right_o = cell_b;\n",
      "    end\n",
      "end\n",
      "\n",
      "endmodule\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Turn off the section of code that's only used during simulation.\n",
    "observe = False\n",
    "\n",
    "# Create the connecting buses for the sorter.\n",
    "clk = Signal(bool(0))\n",
    "cmd = Signal(Cmd.RESET)\n",
    "unsorted_bus, sorted_bus = [Signal(intbv(0,HS_MIN,HS_MAX)) for _ in range(2)]\n",
    "\n",
    "# Create the Verilog code for the sorter.\n",
    "LIST_LEN = 4\n",
    "toVerilog(ibm_hs, clk, cmd, unsorted_bus, sorted_bus, LIST_LEN/2)\n",
    "\n",
    "# Show the Verilog file for the implementation and store it in another\n",
    "# Verilog file with the size of the list it can sort.\n",
    "with open('ibm_hs.v') as fr:\n",
    "    verilog_src = fr.read()\n",
    "    print(verilog_src)\n",
    "    fw = open('ibm_hs_{}.v'.format(LIST_LEN), 'w')\n",
    "    fw.write(verilog_src)\n",
    "    fw.close()    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## FPGA Resource Usage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to test the efficiency of each hardware sorter, I generated Verilog source files for several\n",
    "list lengths and then compiled them for a Lattice ICE40HX8K FPGA with their iCEcube2 design tool\n",
    "(version 2015.08.27744).\n",
    "\n",
    "Here are the results for the Hackaday sorter:\n",
    "\n",
    "List Size  | #LUTs | #DFFs | #Carrys  | $F_{max}$ (MHz)\n",
    "----------:|------:|------:|---------:|---------------:\n",
    "4          | 175   | 64    | 64       | 103            \n",
    "8          | 388   | 128   | 128      | 92             \n",
    "16         | 835   | 256   | 256      | 83             \n",
    "32         | 1918  | 512   | 512      | 68             \n",
    "64         | 3596  | 1024  | 1024     | 55             \n",
    "112        | 5892  | 1792  | 1792     | 46             \n",
    "116        | 6168  | 1856  | 1856     | 42             \n",
    "124        | 6432  | 1984  | 1984     | 43             \n",
    "\n",
    "And these are the results for the IBM sorter:\n",
    "\n",
    "List Size  | #LUTs | #DFFs | #Carrys  | $F_{max}$ (MHz)\n",
    "----------:|------:|------:|---------:|---------------:\n",
    "4          | 135   | 64    | 32       | 126\n",
    "8          | 397   | 128   | 64       | 115\n",
    "16         | 921   | 256   | 128      | 104\n",
    "32         | 1969  | 512   | 256      | 96\n",
    "64         | 4065  | 1024  | 512      | 92\n",
    "112        | 7209  | 1792  | 896      | 79\n",
    "116        | --    | --    | --       | --\n",
    "124        | --    | --    | --       | --\n",
    "\n",
    "The Hackaday sorter can handle slightly larger lists than the IBM sorter even though\n",
    "it requires more carry blocks (since it requires a comparator for every number while\n",
    "the IBM sorter only needs a comparator for every two numbers).\n",
    "However, the multiplexing between the registers in each IBM sorter cell appears to\n",
    "consume more lookup tables (LUTs) and this overshadows the effect of the carry cells.\n",
    "\n",
    "The IBM sorter has a higher $F_{max}$ than the Hackaday sorter, so it can sort a list faster.\n",
    "However, both sorters show a decrease in $F_{max}$ as the list size grows.\n",
    "Since the critical path in both routers shouldn't increase with the list size, the\n",
    "decrease in $F_{max}$ may be related to routing delays incurred while packing the\n",
    "logic into the LUTs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Is It Worth It?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probably not.\n",
    "\n",
    "Trying to increase the speed of a microprocessor by hanging a hardware sorter off its external\n",
    "bus is futile.\n",
    "The time spent doing the I/O to/from the sorter would swamp any savings in sorting time for\n",
    "the small lists these sorters can handle.\n",
    "But if you had a processor in an FPGA and there was room for it, a hardware sorter might provide\n",
    "some advantage due to the faster internal bus speeds.\n",
    "That is, if you needed to do *a lot* of sorting.\n",
    "\n",
    "But what is \"worth it\" is the use of MyHDL to explore these hardware sorters.\n",
    "In 1983, it took me three months to design the VLSI chip for the IBM sorter, and then I waited\n",
    "another six months to get a prototype.\n",
    "Here, it took me five hours to design, simulate and implement the same sorter in a $10 FPGA.\n",
    "(And much of that time was spent trying to gather and nicely format the simulator output for this notebook.)\n",
    "\n",
    "In addition, this notebook is an *active carrier* of these designs. While the current document may be a static image if you're looking at it from my Github repository,\n",
    "you can interact with it and try different approaches with the hardware sorters if you have a [Python environment](https://www.continuum.io/downloads) on your computer.\n",
    "Just install MyHDL using either `pip install myhdl` or `easy_install myhdl` and you're ready to go!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}