Reviews for paper Sorting Networks on FPGAs, submitted to The VLDB Journal.

Overall rating: accept without further revisions

Dear Dr. Mueller,

I am pleased to inform you that Associate Editor Chris Jermaine has decided to accept your revised submission for publication in The VLDB Journal. I concur with that decision and congratulate you on having produced a high-quality paper.

The paper was accepted on August 10, 2010.

Thank you for submitting your work to the journal.

Kind regards,

Christian S. Jensen, Ph.D.
Editor-in-Chief
The VLDB Journal

Thanks for submitting your paper. As you will see, the reviews were very positive, so I will go ahead and accept the paper without further revisions.

That being stated, please look over the referee comments carefully and consider whether or not it is worthwhile to slightly revise the paper before submitting a final version for publishing. In particular, two of the reviewers who are recognized experts in FPGAs (as opposed to core database people) commented that there is a lot of introductory material on FPGAs, that is superfluous for those who know the area. As one of them states, "The paper is very well written for students. If it has to be targeted to more advanced readers then many unnecessary details should be removed and replaced with the relevant references." Since this is a paper about FPGAs targeted for a database journal, I can understand the desire to have this introductory material in the paper. But the authors should be aware that experts on FPGAs will find this material redundant, and the authors should consider very carefully the question of whether or not to keep it, as there is the possibility that including such tutorial material will obscure the contributions of the paper.

Overall though, this is a nice paper and easily clears the bar for VLDBJ. Congratulations!

I was really impressed by the paper. I think the authors did an outstanding job at treating the problem in great detail, provide nice solutions and give a nice perspective on the use of FPGAs in database research. The paper is so well written, I had trouble finding anything that needs fixing. As far as I am concerned, the paper is ready for publication as it is.

I found the extra material added on top of the conference version more than sufficient.

The paper describes FPGA-based implementations of sorting networks, presents the results of analysis of such networks and their comparisons with CPU-based implementations. Two use-cases were considered in detail to demonstrate capabilities of system integration. Generally there are four parts in the paper:

The paper is well written and easily understandable.

Comments:

Overall a good paper but very long for its content.

I am not sure Section 3 is needed, can be a reference to other, possibly web-based, work. Same for Section 4. Both of these could be summarized as they do not introduce any new material.

The evaluation of the sorting networks on FPGAs is thorough and well done. However, there are limitations that the authors do not specifically address and that can be hidden from the casual reader. These networks are optimal for sorting tuples whose size is a power of 2. Any other size would have to be "padded" to achieve the next power of two size. This is not accounted for when comparing with the software approaches.

Several small typos in the text (e.g. page 19, column 1, last paragraph, first sentence).

Letter from the Editor-in-Chief

Dear Dr. Mueller,

I am pleased to inform you that Associate Editor Chris Jermaine has decided to accept your revised submission for publication in The VLDB Journal. I concur with that decision and congratulate you on having produced a high-quality paper.

The paper was accepted on August 10, 2010.

Thank you for submitting your work to the journal.

Kind regards,

Christian S. Jensen, Ph.D.
Editor-in-Chief
The VLDB Journal

Letter from the Associate Editor

Thanks for submitting your paper. As you will see, the reviews were very positive, so I will go ahead and accept the paper without further revisions.

That being stated, please look over the referee comments carefully and consider whether or not it is worthwhile to slightly revise the paper before submitting a final version for publishing. In particular, two of the reviewers who are recognized experts in FPGAs (as opposed to core database people) commented that there is a lot of introductory material on FPGAs, that is superfluous for those who know the area. As one of them states, "The paper is very well written for students. If it has to be targeted to more advanced readers then many unnecessary details should be removed and replaced with the relevant references." Since this is a paper about FPGAs targeted for a database journal, I can understand the desire to have this introductory material in the paper. But the authors should be aware that experts on FPGAs will find this material redundant, and the authors should consider very carefully the question of whether or not to keep it, as there is the possibility that including such tutorial material will obscure the contributions of the paper.

Overall though, this is a nice paper and easily clears the bar for VLDBJ. Congratulations!

Reviewer 1

I was really impressed by the paper. I think the authors did an outstanding job at treating the problem in great detail, provide nice solutions and give a nice perspective on the use of FPGAs in database research. The paper is so well written, I had trouble finding anything that needs fixing. As far as I am concerned, the paper is ready for publication as it is.

I found the extra material added on top of the conference version more than sufficient.

Reviewer 2

The paper describes FPGA-based implementations of sorting networks, presents the results of analysis of such networks and their comparisons with CPU-based implementations. Two use-cases were considered in detail to demonstrate capabilities of system integration. Generally there are four parts in the paper:

1. Background of sorting networks and FPGA-based design (sections 1-4).
2. FPGA and CPU based implementations of sorting networks (section 5).
3. Evaluation of sorting networks and comparisons of FPGA and CPU based implementations (including comparisons with other well-known sorting algorithms (sections 6, 7.3, 8.3) ).
4. Two use cases: a streaming median operator (section 7); and a sorting co-processor (section 8).

The paper is well written and easily understandable.

Comments:

1. The paper includes many well-known and sometimes trivial descriptions and explanations, which might be omitted. Some examples are given below:
   1. Section 3 - Overview of FPGA presents FPGA architecture. On the one hand the given details are well known. On the other hand these details are not enough at all. Instead of this section a reference to the relevant Xilinx data sheet is sufficient.
   2. Figures 1 and 2 are unnecessary. Once again a reference to the relevant Xilinx data sheet is sufficient.
   3. VHDL code for a comparator on page 8 is absolutely trivial and well known. I am not sure if you should show this code in research paper.
   4. Other examples could be presented. I would recommend to revise the paper and to remove unnecessary details.
2. All the presented results of analysis and evaluation are targeted to the particular FPGA FX130T-2 of Xilinx. I am not sure is these results can be reused for other FPGAs, or, at least, I am not sure if these results can easily be reused. See, for example the upper part of right column on page 9, where Virtex-5 targeted evaluation is given (besides, there are many unnecessary well-known details in this column).
3. Figures 17 and 18 evaluate capabilities of FPGA FX130T for implementing relatively large sorting networks. It is not clear, however, how such networks can be used in system design. For example, in sections 7 and 8 just simple sorting networks were examined for use cases. Indeed, if N=64 (see page 14), m=32 there are lots of inputs and FPGA has a limited number of external pins. Perhaps, such cases (N=64, m=32) are valuable from theoretical point of view. But, it would be interesting also to know how to apply your results in practice?
4. I am not sure if Figure 25 is actually needed for the paper.
5. Execution time for the best cases (Core 2 Q6700 and FPGA) is almost not visible in Figure 26. Other cases (which are well visible) are not so interesting for comparison.
6. If I understand correctly the best result on page 20 permits to process 2 in power 26 32-bit data (i.e. 256MB) in 1.302 s. It means that the average performance is something like 20 ns per 32-bit data item. If this is correct, the speed is indeed good. It would be interesting to know how the results are changed if we increase m, for example, from 32 to 128. I am writing about this because it seems that FPGA would permit better speedup for large values of m comparing with CPU implementations due to possibility to process data items with arbitrary size. Your estimation or even opinion would be useful and sufficient.
7. Figure 29 demonstrates speedup of APU over traditional on chip sort. It would be also useful to show the required time per data item for different data sets.
8. There are many misprints in the paper. Some examples are given below:
   1. "External external I/O connectors" - end of subsection 3.2.
   2. "two two sorted sequences" - middle of subsection 4.2 on page 5.
   3. "in the in the combinatorial logic" - before subsection 5.2 on page 8.
   4. "until until output signals" - middle of right column on page 9.
   5. "slice slice as the logic" - middle of subsection 5.3 on page 10.
   6. "Now a complete N m-bit register" - left column on page 11 (it seems that word register should be plural).
   7. "as well ad" - middle of left column on page 18.
   8. I do not understand what is IPIF - left column on page 18.
   9. "data set we the hardware" - bottom of left column on page 19.
   10. "we implement the sorting core is implemented" - beginning of section 8.
   11. "where it is into the target register" - left column of page 22.
   12. "speedup for the when" - top of left column on page 23.

Reviewer 3

Overall a good paper but very long for its content.

I am not sure Section 3 is needed, can be a reference to other, possibly web-based, work. Same for Section 4. Both of these could be summarized as they do not introduce any new material.

The evaluation of the sorting networks on FPGAs is thorough and well done. However, there are limitations that the authors do not specifically address and that can be hidden from the casual reader. These networks are optimal for sorting tuples whose size is a power of 2. Any other size would have to be "padded" to achieve the next power of two size. This is not accounted for when comparing with the software approaches.

Several small typos in the text (e.g. page 19, column 1, last paragraph, first sentence).

Related Information

• submission (PDF)
• camera-ready paper (PDF)