#include <stdlib.h>
|
#include <stdlib.h>
|
#include <stdio.h>
|
#include <stdio.h>
|
#include <string.h>
|
#include <string.h>
|
#include "wz_hsort.h"
|
#include "wz_hsort.h"
|
|
|
sort_data l_smem[NM][SORT_LEN / 2] = { 0, };
|
sort_data l_smem[NM][SORT_LEN / 2] = { 0, };
|
sort_data r_smem[NM][SORT_LEN / 2] = { 0, };
|
sort_data r_smem[NM][SORT_LEN / 2] = { 0, };
|
|
|
//Each level occupies the memory from
|
sort_data heap_sort (sort_data val)
|
sort_data
|
|
heap_sort (sort_data val)
|
|
{
|
{
|
#pragma HLS INTERFACE ap_hs port=val
|
#pragma HLS INTERFACE ap_hs port=val
|
#pragma HSL INTERFACE ap_hs port=return
|
#pragma HSL INTERFACE ap_hs port=return
|
#pragma HLS DATA_PACK variable=val
|
#pragma HLS DATA_PACK variable=val
|
#pragma HLS DATA_PACK variable=return
|
#pragma HLS DATA_PACK variable=return
|
#pragma HLS DATA_PACK variable=l_smem
|
#pragma HLS DATA_PACK variable=l_smem
|
#pragma HLS DATA_PACK variable=r_smem
|
#pragma HLS DATA_PACK variable=r_smem
|
//#pragma HLS RESOURCE variable=l_smem core=RAM_2P
|
//#pragma HLS RESOURCE variable=l_smem core=RAM_2P
|
//#pragma HLS RESOURCE variable=r_smem core=RAM_2P
|
//#pragma HLS RESOURCE variable=r_smem core=RAM_2P
|
|
|
//#pragma HLS DATAFLOW
|
//#pragma HLS DATAFLOW
|
#pragma HLS PIPELINE II=2
|
#pragma HLS PIPELINE II=2
|
#pragma HLS ARRAY_PARTITION variable=l_smem complete dim=1
|
#pragma HLS ARRAY_PARTITION variable=l_smem complete dim=1
|
#pragma HLS ARRAY_PARTITION variable=r_smem complete dim=1
|
#pragma HLS ARRAY_PARTITION variable=r_smem complete dim=1
|
#pragma HLS UNROLL
|
#pragma HLS UNROLL
|
sort_data res;
|
sort_data res;
|
sort_data cur = val;
|
sort_data cur = val;
|
int tmp;
|
int tmp;
|
int pos;
|
int pos;
|
int lev;
|
int lev;
|
int shift;
|
int shift;
|
int offs = 0;
|
int offs = 0;
|
int active;
|
int active;
|
//We compare the input value with the memory on the top
|
//We compare the input value with the memory on the top
|
cur = r_smem[0][0];
|
cur = r_smem[0][0];
|
if (kle (val.key, cur.key))
|
if (kle (val.key, cur.key))
|
return val;
|
return val;
|
else
|
else
|
{ //We start the update process
|
{ //We start the update process
|
res = cur;
|
res = cur;
|
cur = val;
|
cur = val;
|
pos = 0;
|
pos = 0;
|
active = 1;
|
active = 1;
|
for (lev = 1; lev <= NM; lev++)
|
for (lev = 1; lev <= NM; lev++)
|
{
|
{
|
shift = 0;
|
shift = 0;
|
if (lev >= 2)
|
if (lev >= 2)
|
shift = 1 << (lev - 2);
|
shift = 1 << (lev - 2);
|
if (active)
|
if (active)
|
{
|
{
|
if ((lev == NM)
|
if ((lev == NM)
|
|| (kle (cur.key, l_smem[lev][pos].key)
|
|| (kle (cur.key, l_smem[lev][pos].key)
|
&& kle (cur.key, r_smem[lev][pos].key)))
|
&& kle (cur.key, r_smem[lev][pos].key)))
|
{
|
{
|
if (pos < shift)
|
if (pos < shift)
|
l_smem[lev - 1][pos] = cur;
|
l_smem[lev - 1][pos] = cur;
|
else
|
else
|
r_smem[lev - 1][pos - shift] = cur;
|
r_smem[lev - 1][pos - shift] = cur;
|
active = 0;
|
active = 0;
|
}
|
}
|
else if (active
|
else if (active
|
&& klt (l_smem[lev][pos].key, cur.key)
|
&& klt (l_smem[lev][pos].key, cur.key)
|
&& kle (l_smem[lev][pos].key, r_smem[lev][pos].key))
|
&& kle (l_smem[lev][pos].key, r_smem[lev][pos].key))
|
{
|
{
|
if (pos < shift)
|
if (pos < shift)
|
l_smem[lev - 1][pos] = l_smem[lev][pos];
|
l_smem[lev - 1][pos] = l_smem[lev][pos];
|
else
|
else
|
r_smem[lev - 1][pos - shift] = l_smem[lev][pos];
|
r_smem[lev - 1][pos - shift] = l_smem[lev][pos];
|
}
|
}
|
else if (klt (r_smem[lev][pos].key, cur.key))
|
else if (klt (r_smem[lev][pos].key, cur.key))
|
{
|
{
|
if (pos < shift)
|
if (pos < shift)
|
l_smem[lev - 1][pos] = r_smem[lev][pos];
|
l_smem[lev - 1][pos] = r_smem[lev][pos];
|
else
|
else
|
r_smem[lev - 1][pos - shift] = r_smem[lev][pos];
|
r_smem[lev - 1][pos - shift] = r_smem[lev][pos];
|
pos += (1 << (lev - 1));
|
pos += (1 << (lev - 1));
|
}
|
}
|
else
|
else
|
{
|
{
|
printf ("impossible!!!\n");
|
printf ("impossible!!!\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
return res;
|
return res;
|
}
|
}
|
|
|