1library ieee;
2use ieee.std_logic_1164.all;
3use ieee.numeric_std.all;
4
5package bitonic_sort_pkg is
6-- Generic for the number of elements to sort (must be a power of 2).
7-- For example, N=8 means sorting 8 elements.
8constant N : integer := 8;
9
10-- Type for the data elements being sorted.
11-- Assuming unsigned integers for simplicity.
12subtype data_t is unsigned(31 downto 0);
13
14-- Type for the array of data elements.
15subtype data_array_t is data_t array(0 to N-1) of data_t;
16
17-- Component for a single compare-and-swap unit.
18-- Inputs a and b are compared. If dir = '1', a is swapped with b if a > b.
19-- If dir = '0', a is swapped with b if a < b.
20component compare_swap
21generic (
22DATA_WIDTH : integer
23);
24port (
25a   : in  unsigned(DATA_WIDTH-1 downto 0);
26b   : in  unsigned(DATA_WIDTH-1 downto 0);
27dir : in  std_logic;
28y1  : out unsigned(DATA_WIDTH-1 downto 0);
29y2  : out unsigned(DATA_WIDTH-1 downto 0)
30);
31end component;
32
33-- Generates a bitonic sort network for N elements.
34-- The network sorts the input array in ascending order if dir = '1'.
35-- If dir = '0', it sorts in descending order.
36procedure generate_bitonic_sort_network (
37signal input_data  : in  data_array_t;
38signal output_data : out data_array_t;
39input dir          : std_logic -- '1' for ascending, '0' for descending
40);
41
42-- Helper procedure to generate a bitonic merge stage.
43-- Merges two bitonic sequences of size k into a single bitonic sequence of size 2k.
44procedure generate_bitonic_merge (
45signal input_data  : in  data_array_t;
46signal output_data : out data_array_t;
47input k            : integer; -- Size of sub-sequences
48input dir          : std_logic -- Sort direction
49);
50
51-- Helper procedure to generate a bitonic sequence.
52-- Creates a bitonic sequence from an unsorted array of size k.
53procedure generate_bitonic_sequence (
54signal input_data  : in  data_array_t;
55signal output_data : out data_array_t;
56input k            : integer; -- Size of the sequence to create
57input dir          : std_logic -- Sort direction
58);
59
60end package bitonic_sort_pkg;
61
62package body bitonic_sort_pkg is
63
64-- Implementation of the compare_swap component
65component compare_swap
66generic (
67DATA_WIDTH : integer
68);
69port (
70a   : in  unsigned(DATA_WIDTH-1 downto 0);
71b   : in  unsigned(DATA_WIDTH-1 downto 0);
72dir : in  std_logic;
73y1  : out unsigned(DATA_WIDTH-1 downto 0);
74y2  : out unsigned(DATA_WIDTH-1 downto 0)
75);
76end component;
77
78-- Procedure to generate a single compare-and-swap unit.
79procedure compare_swap_unit (
80signal a   : in  unsigned(DATA_WIDTH-1 downto 0);
81signal b   : in  unsigned(DATA_WIDTH-1 downto 0);
82input dir  : std_logic;
83signal y1  : out unsigned(DATA_WIDTH-1 downto 0);
84signal y2  : out unsigned(DATA_WIDTH-1 downto 0)
85)
86is
87begin
88if dir = '1' then -- Ascending sort
89if a > b then
90y1 <= b;
91y2 <= a;
92else
93y1 <= a;
94y2 <= b;
95end if;
96else -- Descending sort
97if a < b then
98y1 <= b;
99y2 <= a;
100else
101y1 <= a;
102y2 <= b;
103end if;
104end if;
105end procedure;
106
107-- Instantiate the compare_swap component
108component compare_swap
109generic (
110DATA_WIDTH : integer := 32
111);
112port (
113a   : in  unsigned(DATA_WIDTH-1 downto 0);
114b   : in  unsigned(DATA_WIDTH-1 downto 0);
115dir : in  std_logic;
116y1  : out unsigned(DATA_WIDTH-1 downto 0);
117y2  : out unsigned(DATA_WIDTH-1 downto 0)
118);
119end component;
120
121-- Helper procedure to generate a bitonic merge stage.
122-- Merges two bitonic sequences of size k into a single bitonic sequence of size 2k.
123procedure generate_bitonic_merge (
124signal input_data  : in  data_array_t;
125signal output_data : out data_array_t;
126input k            : integer; -- Size of sub-sequences
127input dir          : std_logic -- Sort direction
128)
129is
130-- Temporary array to hold intermediate results for this merge stage.
131variable temp_merge_array : data_array_t;
132-- Number of elements in the current merge stage.
133constant current_size : integer := 2 * k;
134begin
135-- Initialize temp array with input data for this stage.
136-- The input_data to this procedure is already structured for merging.
137for i in 0 to current_size - 1 loop
138temp_merge_array(i) := input_data(i);
139end loop;
140
141-- Perform compare-and-swap operations.
142-- For each element i, compare it with element i+k (or i-k depending on direction).
143-- The distance between compared elements decreases as we move through the stage.
144for j in 0 to k - 1 loop
145-- The distance between elements to compare is k.
146-- The indices are i and i+k for ascending, and i and i-k for descending.
147-- We need to be careful with index calculations to ensure we cover all pairs.
148-- The logic for bitonic merge is that element i is compared with element i+k.
149-- The indices for comparison are (i) and (i+k) for the first half, and
150-- (i+k) and (i) for the second half, but this is handled by the loop structure.
151-- The core idea is that for each pair (x, y) where y is k positions away from x,
152-- they are compared and swapped based on the direction.
153-- For a bitonic merge of size 2k, we have two bitonic sequences of size k.
154-- The first sequence is indices 0 to k-1, the second is k to 2k-1.
155-- We compare element i with element i+k.
156-- The loop for j iterates through the first half of the elements.
157-- The compare_swap operation is applied to pairs (temp_merge_array(j), temp_merge_array(j+k)).
158declare
159signal cs_y1, cs_y2 : data_t;
160begin
161compare_swap_unit(
162a   => temp_merge_array(j),
163b   => temp_merge_array(j+k),
164dir => dir,
165y1  => cs_y1,
166y2  => cs_y2
167);
168temp_merge_array(j)   <= cs_y1;
169temp_merge_array(j+k) <= cs_y2;
170end;
171end loop;
172
173-- The result of the merge stage is now in temp_merge_array.
174-- Assign it to the output_data.
175for i in 0 to current_size - 1 loop
176output_data(i) <= temp_merge_array(i);
177end loop;
178
179end procedure generate_bitonic_merge;
180
181-- Helper procedure to generate a bitonic sequence.
182-- Creates a bitonic sequence from an unsorted array of size k.
183procedure generate_bitonic_sequence (
184signal input_data  : in  data_array_t;
185signal output_data : out data_array_t;
186input k            : integer; -- Size of the sequence to create
187input dir          : std_logic -- Sort direction
188)
189is
190-- Temporary array to hold intermediate results.
191variable temp_seq_array : data_array_t;
192-- Half the size of the current sequence.
193constant half_k : integer := k / 2;
194begin
195-- Base case: If k is 2, we just need to compare and swap the two elements.
196if k = 2 then
197declare
198signal cs_y1, cs_y2 : data_t;
199begin
200compare_swap_unit(
201a   => input_data(0),
202b   => input_data(1),
203dir => dir,
204y1  => cs_y1,
205y2  => cs_y2
206);
207output_data(0) <= cs_y1;
208output_data(1) <= cs_y2;
209end;
210else
211-- Recursive step: Create two bitonic sequences of size k/2.
212-- The first sequence is sorted in the same direction 'dir'.
213-- The second sequence is sorted in the opposite direction.
214-- This creates a bitonic sequence when concatenated.
215
216-- Initialize temp_seq_array with the first k elements of input_data.
217for i in 0 to k-1 loop
218temp_seq_array(i) := input_data(i);
219end loop;
220
221-- Recursively generate the first bitonic sequence (ascending).
222generate_bitonic_sequence(
223input_data  => temp_seq_array,
224output_data => temp_seq_array, -- Output to same temp array for now
225k           => half_k,
226dir         => dir
227);
228
229-- Recursively generate the second bitonic sequence (descending).
230-- The second sequence starts from index half_k.
231-- We need to pass a view or slice of the array, or manage indices carefully.
232-- For simplicity, we'll create a temporary sub-array for the second sequence.
233variable second_half_input : data_array_t;
234for i in 0 to half_k - 1 loop
235second_half_input(i) := temp_seq_array(i + half_k);
236end loop;
237
238variable second_half_output : data_array_t;
239generate_bitonic_sequence(
240input_data  => second_half_input,
241output_data => second_half_output,
242k           => half_k,
243dir         => not dir -- Opposite direction
244);
245
246-- Combine the two generated sequences back into temp_seq_array.
247for i in 0 to half_k - 1 loop
248temp_seq_array(i) := second_half_output(i);
249end loop;
250
251-- Now, temp_seq_array contains a bitonic sequence of size k.
252-- We need to merge these two halves.
253-- The generate_bitonic_merge procedure takes the first 2*half_k elements
254-- and merges them. Since temp_seq_array now holds the bitonic sequence,
255-- we can pass it to merge.
256generate_bitonic_merge(
257input_data  => temp_seq_array,
258output_data => temp_seq_array, -- Merge into the same temp array
259k           => half_k,
260dir         => dir
261);
262
263-- Finally, copy the result to the output_data.
264for i in 0 to k - 1 loop
265output_data(i) := temp_seq_array(i);
266end loop;
267end if;
268end procedure generate_bitonic_sequence;
269
270-- Main procedure to generate the complete bitonic sort network.
271procedure generate_bitonic_sort_network (
272signal input_data  : in  data_array_t;
273signal output_data : out data_array_t;
274input dir          : std_logic -- '1' for ascending, '0' for descending
275)
276is
277-- Temporary array to hold intermediate sorted stages.
278variable temp_sort_array : data_array_t;
279begin
280-- The overall sorting process involves creating a bitonic sequence first,
281-- and then repeatedly merging stages until the entire array is sorted.
282-- The generate_bitonic_sequence procedure effectively does the first part.
283-- The subsequent merges are handled by calling generate_bitonic_merge iteratively.
284
285-- Step 1: Create a bitonic sequence from the input data.
286generate_bitonic_sequence(
287input_data  => input_data,
288output_data => temp_sort_array,
289k           => N,
290dir         => dir
291);
292
293-- Step 2: Perform subsequent merge stages to sort the entire array.
294-- The size of the sequences being merged doubles in each stage.
295-- We start with sequences of size 2, then 4, 8, ..., up to N.
296variable current_merge_size : integer := 2;
297while current_merge_size <= N loop
298-- For each merge size, we perform multiple merges across the array.
299-- The number of merges is N / current_merge_size.
300-- Each merge operation combines two bitonic sequences of size current_merge_size/2.
301-- The direction of merge alternates based on the overall sort direction.
302-- The logic here is that we are merging pairs of bitonic sequences.
303-- The distance between elements being compared in a merge stage is current_merge_size/2.
304-- The overall sort direction 'dir' determines the final sort order.
305-- Within each merge stage, the direction of comparison for pairs depends on their position.
306-- For a bitonic sort, the direction of merge alternates.
307-- The outer loop iterates through the merge stage size (2, 4, 8, ... N).
308-- The inner loop iterates through the starting index of each merge operation.
309-- The distance for comparison is half the current merge size.
310for i in 0 to N - 1 loop
311-- This loop structure is a bit tricky. It's not a direct loop over merge operations.
312-- Instead, it's about applying the compare-swap logic across the entire array
313-- for a given stage size.
314-- The bitonic sort network structure implies that for a given stage size 's',
315-- elements at index 'j' and 'j+s' are compared and swapped.
316-- The direction of swap depends on 'dir' and the position within the stage.
317-- The 'dir' parameter to generate_bitonic_merge dictates the sort order for that specific merge.
318-- For the overall network, the direction of merge alternates.
319-- The 'dir' parameter passed to generate_bitonic_merge should be 'dir' for the first half
320-- of the elements and 'not dir' for the second half, or vice versa.
321-- The standard bitonic sort network structure implies that for a merge stage of size 's',
322-- we compare element 'i' with element 'i+s'.
323-- The direction of comparison for element 'i' depends on whether 'i' is in the first or second half
324-- of the overall bitonic sequence being formed.
325-- A simpler way to think about it is that we are applying the merge logic.
326-- The generate_bitonic_merge procedure takes a bitonic sequence and merges it.
327-- Here, we are applying it iteratively.
328-- The 'dir' parameter for generate_bitonic_merge should be 'dir' if the element pair
329-- is part of an ascending sub-sequence, and 'not dir' if it's part of a descending sub-sequence.
330-- This is implicitly handled by the structure of the bitonic sort network.
331-- The key is that the 'generate_bitonic_merge' procedure is called with the correct 'k' and 'dir'.
332-- The 'k' parameter is half the size of the current merge stage.
333-- The 'dir' parameter for the merge depends on the overall sort direction 'dir'.
334-- For a bitonic sort network, the direction of comparison alternates.
335-- The loop for 'i' here is not directly for calling generate_bitonic_merge.
336-- It's more about how the compare-swap operations are distributed.
337-- Let's rethink the structure of the merge stages.
338-- After creating the initial bitonic sequence, we have N/2 merge operations of size 2.
339-- Then N/4 merge operations of size 4, and so on.
340-- The procedure generate_bitonic_merge merges two bitonic sequences of size k.
341-- So, to sort N elements, we call generate_bitonic_merge with k = N/2, then k = N/4, etc.
342-- The 'dir' parameter for generate_bitonic_merge needs to be correctly determined.
343-- For the first merge stage (k=N/2), we merge two bitonic sequences of size N/2.
344-- The direction of the merge for each pair depends on its position.
345-- The overall sort direction is 'dir'.
346-- The standard bitonic sort network structure implies that for a merge stage of size 's',
347-- the direction of comparison for element 'i' and 'i+s' depends on the bit pattern of 'i' and 's'.
348-- A common way to implement this is to have the 'dir' parameter for merge alternate.
349-- However, the 'generate_bitonic_merge' procedure itself takes a 'dir' parameter.
350-- The 'dir' parameter passed to generate_bitonic_merge should be the overall sort direction.
351-- The internal logic of generate_bitonic_merge handles the pairing correctly.
352-- The loop structure for 'i' should be over the number of merge operations at each stage.
353-- For a merge stage of size 'current_merge_size', there are N / current_merge_size merge operations.
354-- Each merge operation operates on a block of size 'current_merge_size'.
355-- The 'k' for generate_bitonic_merge is 'current_merge_size / 2'.
356-- The 'dir' for generate_bitonic_merge is 'dir'.
357-- The input to generate_bitonic_merge is the current state of temp_sort_array.
358-- The output is also to temp_sort_array.
359-- The loop for 'i' should iterate through the starting indices of these merge blocks.
360-- For a merge stage of size 'current_merge_size', the starting indices are 0, current_merge_size, 2*current_merge_size, etc.
361-- Let's restructure this loop.
362null;
363end loop;
364
365-- Corrected loop for merge stages:
366-- Iterate through the size of the sub-sequences being merged.
367-- This size doubles in each iteration of the outer loop.
368-- The 'k' for generate_bitonic_merge is half the current_merge_size.
369-- The 'dir' parameter for generate_bitonic_merge is the overall sort direction.
370-- The number of merge operations at this stage is N / current_merge_size.
371-- The starting index of each merge operation is 'm * current_merge_size'.
372for m in 0 to (N / current_merge_size) - 1 loop
373-- We need to pass a view or slice of temp_sort_array to generate_bitonic_merge.
374-- VHDL doesn't directly support array slicing for procedure arguments in this way.
375-- We need to copy the relevant portion to a temporary array.
376variable merge_input_block : data_array_t;
377variable merge_output_block : data_array_t;
378constant block_start_index : integer := m * current_merge_size;
379
380-- Copy the block to be merged into merge_input_block.
381for i in 0 to current_merge_size - 1 loop
382merge_input_block(i) := temp_sort_array(block_start_index + i);
383end loop;
384
385-- Perform the merge operation on this block.
386generate_bitonic_merge(
387input_data  => merge_input_block,
388output_data => merge_output_block,
389k           => current_merge_size / 2,
390dir         => dir
391);
392
393-- Copy the merged block back into temp_sort_array.
394for i in 0 to current_merge_size - 1 loop
395temp_sort_array(block_start_index + i) := merge_output_block(i);
396end loop;
397end loop;
398
399current_merge_size := current_merge_size * 2;
400end loop;
401
402-- After all merge stages, temp_sort_array contains the sorted data.
403output_data <= temp_sort_array;
404
405end procedure generate_bitonic_sort_network;
406
407end package body bitonic_sort_pkg;