کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
393721 | 665661 | 2012 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of min–max sorting networks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper extends previous work on sorting networks (SNs) based on min/max circuits. In particular, we have identified the complexity of both min/max-based sorting and merging networks showing that, depending on design choice, the time complexity of this kind of SN ranges from O(1) to O(log (n)) and spatial complexity from O(n2n) to O(n2), respectively. Moreover, we show that both AT and AT2 metrics of the proposed SN are better than those of Batcher’s SNs also for SNs with several hundreds of inputs.In addition to these results we show how to design a fast digital, serial, pipelined sorting network using FPGA technology. As expected, FPGA synthesis results confirm our theoretical analysis.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 190, 1 May 2012, Pages 178–191
Journal: Information Sciences - Volume 190, 1 May 2012, Pages 178–191
نویسندگان
Giuseppe Campobello, Giuseppe Patanè, Marco Russo,