Model of the Month

We can update you automatically when this page changes.
To receive regular notification of updates to our Model of the Month section, click here.

HeapSortParallel

As promised last month, this month we look at the implementation of Williams’ heapsort algorithm in VHDL.

A heap is a data structure organised as a balanced binary tree. Each node in the tree represents an item in the list, and the tree is ordered so that the value of each node is greater than the values of both its children. (Alternatively the ordering could be reversed, so that the value of each node is less than the values of its children.)

A heap can be stored in an array, with the first element containing the root (or parent) of the tree, and subsequent adjacent pairs of elements containing siblings. The array index of the child of a given node is twice the array index of that node, assuming the indices are 1,2,3,...

A heap sort is a software algorithm to sort a list of items. The algorithm is in two parts: first, the list is structured as a heap, and secondly the heap is transformed into an ordered list. One feature of the heap sort algorithm is that no storage additional to the array is required, except when swapping values. The time to complete a sort is of the order Nlog2N, and the algorithm is particularly efficient for partially ordered lists.

HeapSortParallel is a VHDL design entity whose function is to sort a list of integers into a numerically ascending sequence using a heap sort. The unsorted and the sorted lists are input and output in parallel and the algorithm can be represented in pseudo-VHDL as follows:

CreateEmptyHeap;
for EachUnsortedItem loop
  InsertIntoHeap;
end loop;

while HeapNotEmpty loop
  RemoveBiggestHeapItem;
  RemakeHeap;
end loop;

Note that in HeapSortParallel the heap and the unsorted and sorted lists share the same array storage. (Note that you could describe the same algorithm in a software language, such as C or Pascal, in very much the same way.)

A couple of things to try...

• You might want to ponder on why the design entity HeapSortParallel is not synthesizable...
• You might also want to modify the heap sort entity to handle lists of unsorted data of arbitrary length. In a couple of months we’ll probably create a model to do just this — we can compare results!

You are welcome to use the source code we provide but you must keep the copyright notice with the code (see the Acknowledgements page for more details).

All of the VHDL required for simulating this month’s Model of the Month is available on this page.
This month, you don’t need to download the VFP files.

-- HeapSortParallel
--
-- +-----------------------------+
-- |    Copyright 1996 DOULOS    |
-- |        Library: Sort        |
-- |    designer : Mike Smith    |
-- +-----------------------------+
 
-- This design contains VHDL’93 code that is incompatible with VHDL’87

library IEEE;
use IEEE.Std_logic_1164.all;

package HeapType is

  subtype Key is Integer;
  type ListIndex is range 0 to Integer'High;
  type List is array (ListIndex range <>) of Key;

end package HeapType;

use Work.HeapType.all;

entity HeapSortParallel is
  port (Input: in List;
        Output: out List);
end entity HeapSortParallel;

architecture Algorithm of HeapSortParallel is

  -- A pure algorithm to input a list of numbers in parallel and output 
  -- the same values sorted.

  procedure Heapify (Heap: inout List; Start: ListIndex) is

    -- Percolate item in Start position down into the heap
    -- Assumes that the 2 sub-heaps are already valid heaps
    -- A heap is a binary tree with Parent > max(Children) at each level

    variable Parent: ListIndex := Start;
    variable Child: ListIndex := 2*Parent;
    variable NewComer: Key := Heap(Start);
  begin

    while Child <= Heap'Right loop
      if Child < Heap'Right then
        -- Pick the biggest child...
        if Heap(Child + 1) > Heap(Child) then
          Child := Child + 1;
        end if;
      end if;
      if Heap(Child) > NewComer then
        -- Percolate NewComer down heap
        Heap(Parent) := Heap(Child);
        Parent := Child;
        Child := 2*Parent;
      else
        exit;
      end if;
    end loop;
    -- Newby has reached his final resting place
    Heap(Parent) := NewComer;
  end procedure Heapify;

begin

  process (Input)

    -- Re-define the index constraint so we know for convenience that the 
    -- first element is numbered 1, and the range is ascending...

    variable Heap: List(1 to Input'Length);
    variable Biggest: Key;
  begin
    assert Input'Length = Output'Length 
      report "HeapSort input and output must be the same length";
    Heap := Input;

    -- Transform the list into a heap, bottom up...
    for J in Heap'Right / 2 downto 1 loop
      Heapify(Heap, J);
    end loop;

    -- Sort the heap into an ascending linear sequence
    for J in Heap'Right downto 2 loop
      -- Swap the item on the top (the biggest) to the "done" pile...
      Biggest := Heap(1);
      Heap(1) := Heap(J);
      Heap(J) := Biggest;
      -- Percolate the promoted item to re-form a valid heap...
      Heapify(Heap(1 to J-1), 1);
    end loop;

    -- Output the heap
    Output <= Heap;    
  end process;

end architecture Algorithm;

VHDL source code for other Models of the Month
can be downloaded from here.

Advanced VHDL Techniques
Doulos Training Courses

Doulos Home Page

Copyright 1995-1996 Doulos
This page was last updated 20^th October 1996.

We welcome your e-mail comments. Please contact us at: webmaster@doulos.co.uk