Design and implementation of counting networks

详细信息    查看全文

• 作者：Valery Sklyarov ; Iouliia Skliarova
• 关键词：Hamming weight counter/comparator ; Parallel circuits ; Performance analysis and design ; Pipeline ; FPGA ; 68W10 Parallel algorithms ; 68Q10 Modes of computation (nondeterministic ; interactive ; probabilistic ; etc.) ; 68M20 Performance evaluation ; quering ; scheduling ; 68P10 Searching and sorting
• 刊名：Computing
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：97
• 期：6
• 页码：557-577
• 全文大小：2,657 KB
• 参考文献：1.Bailey DG (2011) Design for embedded image processing on FPGAs. Wiley, New York
  2.Knuth DE (1973) The art of computer programming. Sorting and searching, vol 3. Addison-Wesley, USA
  3.Zakrevskij A, Pottoson Yu, Cheremisiniva L (2008) Combinatorial algorithms of discrete mathematics. TUT Press, Tallinn, Estonia
  4.Parhami B (2009) Efficient Hamming weight comparators for binary vectors based on accumulative and up/down parallel counters. IEEE Trans Circuits Syst II Express Briefs 56(2):167鈥?71
  5.Piestrak SJ (May 2007) Efficient hamming weight comparators of binary vectors. Electron Lett 43(11):611鈥?12
  6.Sklyarov V, Skliarova I, Mihhailov D, Sudnitson A (2011) Implementation in FPGA of Address-based Data Sorting. In: Proceedings of 21st International Conference on Field-Programmable Logic and Applications鈥擣PL鈥?1, pp 405鈥?10
  7.Barral C, Coron JS, Naccache D (2004) Externalized fingerprint matching. Lect Notes Comput Sci 3072:309鈥?15
  8.Asada K, Komatsu S, Ikeda M (1999) Associative memory with minimum Hamming distance detector and its application to bus data encoding. In: Proceedings of the IEEE Asia-Pacific ASIC Conference鈥?AP-ASIC鈥?9, p 282
  9.Nambiar VP, Balakrishnan S, Khalil-Hani M, Marsono MN (2013) HW/SW co-design of reconfigurable hardware-based genetic algorithm in FPGAs applicable to a variety of problems. Computing 1鈥?4
  10.Skliarova I, Ferrari AB (2003) The design and implementation of a reconfigurable processor for problems of combinatorial computation. J Syst Archit (Special Issue on Reconfigurable Systems) 49(4鈥?): 211鈥?26
  11.Mueller R, Teubner J, Alonso G (2012) Sorting networks on FPGAs. Int J Very Large Data Bases 21(1):1鈥?3
  12.Zuluada M, Milder P, Puschel M (2012) Computer generation of streaming sorting networks. Proceedings of the 49th design automation conference, 2012, pp 1245鈥?253
  13.Pedroni VA (Nov. 2003) Compact fixed-threshold and two-vector hamming comparators. Electron Lett 39(24):1705鈥?706
  14.Pedroni V (2004) Compact Hamming-comparator-based rank order filter for digital VLSI and FPGA implementations. Proceedings of the IEEE International Symposium on Circuits and Systems鈥擨SCAS鈥?004, pp 585鈥?88
  15.Wendt PD, Coyle EJ, Gallagher NC (Aug. 1986) Stack filters. IEEE Trans Acoust Speech Signal Process 34(4):898鈥?08
  16.Storace M, Poggi T (2011) Digital architectures realizing piecewise-linear multivariate functions: two FPGA implementations. Int J Circ Theor Appl 39:1鈥?5
  17.Sklyarov V, Skliarova I (2012) Data processing in FPGA-based systems. Tutorial, Proceedings 6th international conference on application of information and communication technologies鈥擜ICT, Oct 2012, pp 291鈥?95
  18.Xilinx, 7 Series DSP48E1 Slice User Guide, available at: http://鈥媤ww.鈥媥ilinx.鈥媍om/鈥媠upport/鈥媎ocumentation/鈥媢ser_鈥媑uides/鈥媢g479_鈥?Series_鈥婦SP48E1.鈥媝df
  19.Digilent boards, drivers, and VHDL modules, available at http://鈥媤ww.鈥媎igilentinc.鈥媍om/鈥?/span>
  20.Xillybus Lite for Zynq-7000: Easy FPGA registers with Linux. Available at http://鈥媥illybus.鈥媍om/鈥媥illybus-lite
  
• 作者单位：Valery Sklyarov (1)
  Iouliia Skliarova (1)
  
  1. Department of Electronics, Telecommunications and Informatics/IEETA, University of Aveiro, 3830-193聽, Aveiro, Portugal
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer Wien
• ISSN：1436-5057

文摘

The paper describes Hamming weight counters/comparators built on counting networks that incorporate two distinctive and important features. The counting networks are composed of simple logic (core) elements with incrementally reducing numbers of elements from the inputs to the outputs. This feature provides the same performance as the best known sorting networks with radically reduced complexity. Compared to a competitive design based on parallel counters, the propagation delays of signals passing through data independent segments within the circuit are shortened, which allows faster pipelined implementations. Several types of counting networks are elaborated, namely pure combinational, partially sequential with reusable fragments, and pipelined. The correctness of the proposed concept and scalability of the networks are proven. Formal expressions to estimate the complexity and throughput of the network are given. Finally, the results of extensive experiments, evaluations and comparisons are reported that demonstrate that the solutions proposed offer better characteristics than the best known alternatives.