URL
https://opencores.org/ocsvn/heap_sorter/heap_sorter/trunk
Subversion Repositories heap_sorter
Compare Revisions
- This comparison shows the changes necessary to convert path
/
- from Rev 7 to Rev 8
- ↔ Reverse comparison
Rev 7 → Rev 8
/heap_sorter/trunk/HLS_implementation/Fig2/README
0,0 → 1,?rev2len?
The simplest (and inefficient) implementation (Figure 2 in the article) |
/heap_sorter/trunk/HLS_implementation/Fig2/wz_hsort.cc
0,0 → 1,49
#include <stdint.h> |
#include <stdio.h> |
#include <string.h> |
#include "wz_hsort.h" |
|
sort_data sort_mem[SORT_LEN]; |
sort_data heap_sort (sort_data val) |
{ |
sort_data res; |
sort_data cur = val; |
int lev, offs, top, left, right; |
cur = sort_mem[1]; |
if (val.key <= cur.key) |
return val; //No need to update the heap |
else |
{ |
res = cur; |
cur = val; |
offs = 0; |
for (lev = 1; lev <= NM; lev++) |
{ |
top = (1 << (lev - 1)) + offs; |
left = (2 << (lev - 1)) + offs; |
right = (3 << (lev - 1)) + offs; |
if ((lev == NM) || |
((cur.key <= sort_mem[left].key) && |
(cur.key <= sort_mem[right].key))) |
{ |
sort_mem[top] = cur; |
break; |
} |
else if ((sort_mem[left].key < cur.key) && |
(sort_mem[left].key <= sort_mem[right].key)) |
{ |
sort_mem[top] = sort_mem[left]; |
} |
else if (sort_mem[right].key < cur.key) |
{ |
sort_mem[top] = sort_mem[right]; |
offs += (1 << (lev - 1)); |
} |
else |
{ |
printf ("impossible!!!\n"); |
} |
} |
} |
return res; |
} |
/heap_sorter/trunk/HLS_implementation/Fig2/wz_hsort.h
0,0 → 1,11
typedef struct{ |
short int key; |
char payload[4]; |
} sort_data; |
|
#define NM 11 |
#define SORT_LEN (1<<NM) |
#define MAX_DEL (SORT_LEN) |
#define TEST_LEN (MAX_DEL*10) |
extern sort_data sort_mem[SORT_LEN]; |
sort_data heap_sort (sort_data val); |
/heap_sorter/trunk/HLS_implementation/Fig3/README
0,0 → 1,11
Code with partitioned memory (Figure 3 in the article) |
/heap_sorter/trunk/HLS_implementation/Fig3/test_srt.py
0,0 → 1,12
#!/usr/bin/python |
import sys |
fi=open(sys.argv[1],'r') |
v1=int(fi.readline()) |
for ln1 in fi.readlines(): |
v2=int(ln1) |
diff=(v2-v1) & 0xffff |
if diff >= 0x8000: |
raise(Exception("Error:"+str(v2)+" after "+str(v1))) |
v1=v2 |
|
|
heap_sorter/trunk/HLS_implementation/Fig3/test_srt.py
Property changes :
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: heap_sorter/trunk/HLS_implementation/Fig3/wz_hsort.cc
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig3/wz_hsort.cc (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig3/wz_hsort.cc (revision 8)
@@ -0,0 +1,55 @@
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+sort_data sort_mem[NM][SORT_LEN];
+sort_data heap_sort (sort_data val)
+{
+#pragma HLS PIPELINE II=2
+#pragma HLS INTERFACE ap_hs port=val
+#pragma HLS DATA_PACK variable=val
+#pragma HLS INTERFACE ap_ctrl_hs port=return
+#pragma HLS DATA_PACK variable=return
+#pragma HLS ARRAY_PARTITION variable=sort_mem dim=1
+ sort_data res;
+ sort_data cur = val;
+ int lev, offs, top, left, right;
+ cur = sort_mem[0][0];
+ if (val.key <= cur.key)
+ return val; //No need to update the heap
+ else
+ {
+ res = cur;
+ cur = val;
+ offs = 0;
+ for (lev = 1; lev <= NM; lev++)
+ {
+ top = offs;
+ left = offs;
+ right = (1 << (lev - 1)) + offs;
+ if ((lev == NM) ||
+ ((cur.key <= sort_mem[lev][left].key) &&
+ (cur.key <= sort_mem[lev][right].key)))
+ {
+ sort_mem[lev-1][top] = cur;
+ break;
+ }
+ else if ((sort_mem[lev][left].key < cur.key) &&
+ (sort_mem[lev][left].key <= sort_mem[lev][right].key))
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][left];
+ }
+ else if (sort_mem[lev][right].key < cur.key)
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][right];
+ offs += (1 << (lev - 1));
+ }
+ else
+ {
+ printf ("impossible!!!\n");
+ }
+ }
+ }
+ return res;
+}
Index: heap_sorter/trunk/HLS_implementation/Fig3/wz_hsort.h
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig3/wz_hsort.h (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig3/wz_hsort.h (revision 8)
@@ -0,0 +1,11 @@
+typedef struct{
+ short int key;
+ char payload[4];
+} sort_data;
+
+#define NM 11
+#define SORT_LEN (1<
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+/* How we assign memory address to each level?
+ N - level
+ NM - max level
+ SORT_LEN = 2^(NM+1)
+ base address
+ How we calculate the address of the node?
+ 2^N - base address which is also the "LEFT" address
+ 2^N + 2^(N-1) - "RIGHT" address
+ How we create the "offset"? - we simply collect the bits from
+ the previous "left<->right" decisions.
+
+ */
+
+
+
+int main()
+{
+ int i,j;
+ for(i=0;i= 0x8000:
+ raise(Exception("Error:"+str(v2)+" after "+str(v1)))
+ v1=v2
+
+
heap_sorter/trunk/HLS_implementation/Fig4/test_srt.py
Property changes :
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: heap_sorter/trunk/HLS_implementation/Fig4/wz_hsort.cc
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig4/wz_hsort.cc (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig4/wz_hsort.cc (revision 8)
@@ -0,0 +1,58 @@
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+sort_data sort_mem[NM][SORT_LEN];
+sort_data heap_sort (sort_data val)
+{
+#pragma HLS PIPELINE II=2
+#pragma HLS INTERFACE ap_hs port=val
+#pragma HLS DATA_PACK variable=val
+#pragma HLS INTERFACE ap_ctrl_hs port=return
+#pragma HLS DATA_PACK variable=return
+#pragma HLS ARRAY_PARTITION variable=sort_mem dim=1
+ sort_data res;
+ sort_data cur = val;
+ int lev, offs, top, left, right, enable;
+ cur = sort_mem[0][0];
+ if (val.key <= cur.key)
+ return val; //No need to update the heap
+ else
+ {
+ res = cur;
+ cur = val;
+ offs = 0;
+ enable = 1;
+ for (lev = 1; lev <= NM; lev++)
+ {
+ top = offs;
+ left = offs;
+ right = (1 << (lev - 1)) + offs;
+ if(enable){
+ if ((lev == NM) ||
+ ((cur.key <= sort_mem[lev][left].key) &&
+ (cur.key <= sort_mem[lev][right].key)))
+ {
+ sort_mem[lev-1][top] = cur;
+ enable=0;
+ }
+ else if ((sort_mem[lev][left].key < cur.key) &&
+ (sort_mem[lev][left].key <= sort_mem[lev][right].key))
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][left];
+ }
+ else if (sort_mem[lev][right].key < cur.key)
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][right];
+ offs += (1 << (lev - 1));
+ }
+ else
+ {
+ printf ("impossible!!!\n");
+ }
+ }
+ }
+ }
+ return res;
+}
Index: heap_sorter/trunk/HLS_implementation/Fig4/wz_hsort.h
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig4/wz_hsort.h (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig4/wz_hsort.h (revision 8)
@@ -0,0 +1,11 @@
+typedef struct{
+ short int key;
+ char payload[4];
+} sort_data;
+
+#define NM 11
+#define SORT_LEN (1<
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+/* How we assign memory address to each level?
+ N - level
+ NM - max level
+ SORT_LEN = 2^(NM+1)
+ base address
+ How we calculate the address of the node?
+ 2^N - base address which is also the "LEFT" address
+ 2^N + 2^(N-1) - "RIGHT" address
+ How we create the "offset"? - we simply collect the bits from
+ the previous "left<->right" decisions.
+
+ */
+
+
+
+int main()
+{
+ int i,j;
+ for(i=0;i= 0x8000:
+ raise(Exception("Error:"+str(v2)+" after "+str(v1)))
+ v1=v2
+
+
heap_sorter/trunk/HLS_implementation/Fig5/test_srt.py
Property changes :
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: heap_sorter/trunk/HLS_implementation/Fig5/wz_hsort.cc
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig5/wz_hsort.cc (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig5/wz_hsort.cc (revision 8)
@@ -0,0 +1,58 @@
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+sort_data sort_mem[NM][SORT_LEN];
+sort_data heap_sort (sort_data val)
+{
+#pragma HLS PIPELINE II=2
+#pragma HLS INTERFACE ap_hs port=val
+#pragma HLS DATA_PACK variable=val
+#pragma HLS INTERFACE ap_ctrl_hs port=return
+#pragma HLS DATA_PACK variable=return
+#pragma HLS ARRAY_PARTITION variable=sort_mem dim=1
+ sort_data res;
+ sort_data cur = val;
+ int lev, offs, top, left, right, enable;
+ cur = sort_mem[0][0];
+ if (kcmp(val.key,cur.key) <= 0)
+ return val; //No need to update the heap
+ else
+ {
+ res = cur;
+ cur = val;
+ offs = 0;
+ enable = 1;
+ for (lev = 1; lev <= NM; lev++)
+ {
+ top = offs;
+ left = offs;
+ right = (1 << (lev - 1)) + offs;
+ if(enable){
+ if ((lev == NM) ||
+ ((kcmp(cur.key,sort_mem[lev][left].key) <= 0) &&
+ (kcmp(cur.key,sort_mem[lev][right].key) <= 0)))
+ {
+ sort_mem[lev-1][top] = cur;
+ enable=0;
+ }
+ else if ((kcmp(sort_mem[lev][left].key,cur.key) < 0) &&
+ (kcmp(sort_mem[lev][left].key,sort_mem[lev][right].key) <= 0))
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][left];
+ }
+ else if (kcmp(sort_mem[lev][right].key,cur.key)<0)
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][right];
+ offs += (1 << (lev - 1));
+ }
+ else
+ {
+ printf ("impossible!!!\n");
+ }
+ }
+ }
+ }
+ return res;
+}
Index: heap_sorter/trunk/HLS_implementation/Fig5/wz_hsort.h
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig5/wz_hsort.h (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig5/wz_hsort.h (revision 8)
@@ -0,0 +1,19 @@
+typedef struct{
+ short unsigned int key;
+ char payload[4];
+} sort_data;
+
+int inline kcmp(short unsigned int v1, short unsigned int v2)
+{
+#pragma HLS LATENCY min=0 max=0
+ if(v1==v2) return 0;
+ if((v1-v2) & (1<<15)) return -1;
+ return 1;
+}
+
+#define NM 11
+#define SORT_LEN (1<
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+/* How we assign memory address to each level?
+ N - level
+ NM - max level
+ SORT_LEN = 2^(NM+1)
+ base address
+ How we calculate the address of the node?
+ 2^N - base address which is also the "LEFT" address
+ 2^N + 2^(N-1) - "RIGHT" address
+ How we create the "offset"? - we simply collect the bits from
+ the previous "left<->right" decisions.
+
+ */
+
+
+
+int main()
+{
+ int i,j;
+ for(i=0;i
+#include
+#include
+#include "wz_hsort.h"
+
+sort_data sort_mem[NM][SORT_LEN];
+sort_data heap_sort (sort_data val)
+{
+#pragma HLS PIPELINE II=2
+#pragma HLS INTERFACE ap_hs port=val
+#pragma HLS DATA_PACK variable=val
+#pragma HLS INTERFACE ap_ctrl_hs port=return
+#pragma HLS DATA_PACK variable=return
+#pragma HLS ARRAY_PARTITION variable=sort_mem dim=1
+#pragma HLS DATA_PACK variable=sort_mem
+ sort_data res;
+ sort_data cur = val;
+ int lev, offs, top, left, right, enable;
+ cur = sort_mem[0][0];
+ if (kle(val.key,cur.key))
+ return val; //No need to update the heap
+ else
+ {
+ res = cur;
+ cur = val;
+ offs = 0;
+ enable = 1;
+ for (lev = 1; lev <= NM; lev++)
+ {
+ top = offs;
+ left = offs;
+ right = (1 << (lev - 1)) + offs;
+ if(enable){
+ if ((lev == NM) ||
+ (kle(cur.key,sort_mem[lev][left].key) &&
+ kle(cur.key,sort_mem[lev][right].key)))
+ {
+ sort_mem[lev-1][top] = cur;
+ enable=0;
+ }
+ else if (klt(sort_mem[lev][left].key,cur.key) &&
+ kle(sort_mem[lev][left].key,sort_mem[lev][right].key))
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][left];
+ }
+ else if (klt(sort_mem[lev][right].key,cur.key))
+ {
+ sort_mem[lev-1][top] = sort_mem[lev][right];
+ offs += (1 << (lev - 1));
+ }
+ else
+ {
+ printf ("impossible!!!\n");
+ }
+ }
+ }
+ }
+ return res;
+}
Index: heap_sorter/trunk/HLS_implementation/Fig6/wz_hsort.h
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig6/wz_hsort.h (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig6/wz_hsort.h (revision 8)
@@ -0,0 +1,14 @@
+typedef struct{
+ short unsigned int key;
+ char payload[4];
+} sort_data;
+
+#define klt(v1,v2) ((v1-v2) & 0x8000)
+#define kle(v1,v2) (((v2-v1) & 0x8000)==0)
+
+#define NM 11
+#define SORT_LEN (1<
+#include
+#include
+#include
+#include "wz_hsort.h"
+
+/* How we assign memory address to each level?
+ N - level
+ NM - max level
+ SORT_LEN = 2^(NM+1)
+ base address
+ How we calculate the address of the node?
+ 2^N - base address which is also the "LEFT" address
+ 2^N + 2^(N-1) - "RIGHT" address
+ How we create the "offset"? - we simply collect the bits from
+ the previous "left<->right" decisions.
+
+ */
+
+
+
+int main()
+{
+ int i,j;
+ for(i=0;i
+#include
+#include
+#include "wz_hsort.h"
+
+sort_data l_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)
+{
+#pragma HLS INTERFACE ap_hs port=val
+#pragma HSL INTERFACE ap_hs port=return
+#pragma HLS DATA_PACK variable=val
+#pragma HLS DATA_PACK variable=return
+#pragma HLS DATA_PACK variable=l_smem
+#pragma HLS DATA_PACK variable=r_smem
+//#pragma HLS RESOURCE variable=l_smem core=RAM_2P
+//#pragma HLS RESOURCE variable=r_smem core=RAM_2P
+
+ //#pragma HLS DATAFLOW
+#pragma HLS PIPELINE II=2
+#pragma HLS ARRAY_PARTITION variable=l_smem complete dim=1
+#pragma HLS ARRAY_PARTITION variable=r_smem complete dim=1
+#pragma HLS UNROLL
+ sort_data res;
+ sort_data cur = val;
+ int tmp;
+ int pos;
+ int lev;
+ int shift;
+ int offs = 0;
+ int active;
+ //We compare the input value with the memory on the top
+ cur = r_smem[0][0];
+ if (kle (val.key, cur.key))
+ return val;
+ else
+ { //We start the update process
+ res = cur;
+ cur = val;
+ pos = 0;
+ active = 1;
+ for (lev = 1; lev <= NM; lev++)
+ {
+ shift = 0;
+ if (lev >= 2)
+ shift = 1 << (lev - 2);
+ if (active)
+ {
+ if ((lev == NM)
+ || (kle (cur.key, l_smem[lev][pos].key)
+ && kle (cur.key, r_smem[lev][pos].key)))
+ {
+ if (pos < shift)
+ l_smem[lev - 1][pos] = cur;
+ else
+ r_smem[lev - 1][pos - shift] = cur;
+ active = 0;
+ }
+ else if (active
+ && klt (l_smem[lev][pos].key, cur.key)
+ && kle (l_smem[lev][pos].key, r_smem[lev][pos].key))
+ {
+ if (pos < shift)
+ l_smem[lev - 1][pos] = l_smem[lev][pos];
+ else
+ r_smem[lev - 1][pos - shift] = l_smem[lev][pos];
+ }
+ else if (klt (r_smem[lev][pos].key, cur.key))
+ {
+ if (pos < shift)
+ l_smem[lev - 1][pos] = r_smem[lev][pos];
+ else
+ r_smem[lev - 1][pos - shift] = r_smem[lev][pos];
+ pos += (1 << (lev - 1));
+ }
+ else
+ {
+ printf ("impossible!!!\n");
+ }
+ }
+ }
+ }
+ return res;
+}
Index: heap_sorter/trunk/HLS_implementation/Fig7/wz_hsort.h
===================================================================
--- heap_sorter/trunk/HLS_implementation/Fig7/wz_hsort.h (nonexistent)
+++ heap_sorter/trunk/HLS_implementation/Fig7/wz_hsort.h (revision 8)
@@ -0,0 +1,16 @@
+typedef struct
+{
+ short unsigned int key;
+ char payload[4];
+} sort_data;
+
+#define klt(v1,v2) ((v1-v2) & 0x8000)
+#define kle(v1,v2) (((v2-v1) & 0x8000)==0)
+
+#define NM 11
+#define SORT_LEN (1<
+#include
+#include
+#include "wz_hsort.h"
+
+/* How we assign memory address to each level?
+ N - level
+ NM - max level
+ SORT_LEN = 2^(NM+1)
+ base address
+ How we calculate the address of the node?
+ 2^N - base address which is also the "LEFT" address
+ 2^N + 2^(N-1) - "RIGHT" address
+ How we create the "offset"? - we simply collect the bits from
+ the previous "left<->right" decisions.
+
+*/
+
+
+
+int main()
+{
+ int i,j;
+ for(i=0;i