Heap Sort Parallel
Here 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.
You are welcome to use the source code we provide but you must keep the copyright notice with the code (see the Notices page for details).
All of the VHDL required for simulating this model is available on this page.
-- 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;
To download the VHDL source code, click here.
Your e-mail comments are welcome - send email
Copyright 1995-2014 Doulos