No Access

Improved Synthesis of Generalized Parallel Counters on FPGAs Using Only LUTs

Burhan Khurshid

Department of Computer Science and Engineering, NIT Srinagar, Srinagar, J&K, India

E-mail Address: burhan_07phd12@nitsri.net

https://doi.org/10.1142/S0218126618500020Cited by:1 (Source: Crossref)

Abstract

Generalized parallel counters (GPCs) are frequently used to construct high speed compressor trees on field programmable gate arrays (FPGAs). The introduction of fast carry-chain in FPGAs has greatly improved the performance of these elements. Evidently, a large number of GPCs have been proposed in literature that use a combination of look-up tables (LUTs) and carry-chains. In this paper, we take an alternate approach and try to eliminate the carry-chain from the GPC structure. We present a heuristic that aims at synthesizing GPCs on FPGAS using only the general LUT fabric. The resultant GPCs are then easily pipelined by placing registers at the output node of each LUT. We have used our heuristic on various GPCs reported in prior work. Our heuristic successfully eliminates the carry-chain from the GPC structure with an increase in LUT count in some GPCs. Experimentation using Xilinx FPGAs shows that filter systems constructed using our GPCs show an improvement in speed and power performance and a comparable area performance.

This paper was recommended by Regional Editor Emre Salman.

Keywords:

References

1. S. Mirzaei, A. Hosangadi and R. Kastner , High speed FIR filter implementation using add and shift method, Int. Conf. Computer Design, San Jose, CA, USA, 1–4 October, 2006, pp. 308–313. Google Scholar
2. C. Y. Chen, S. Y. Chien, Y. W. Huang, T. C. Chen, T. C. Wang and L. G. Chen , Analysis and architecture design of variable block-size motion estimation for H.264/AVC, IEEE Trans. Circuits Syst. I 53 (2006) 578–593. Crossref, Google Scholar
3. L. Dadda , Some schemes for parallel multipliers, Alta Freq. 34 (1965) 349–356. Google Scholar
4. O. Kwon, K. Nowka and Jr. Swartzlander , A 16-bit by 16-bit MAC design using fast 5:3 compressor cells, J. VLSI Signal Procses. 31 (2002) 77–89. Crossref, Web of Science, Google Scholar
5. H. Mora Mora, J. Mora Pascual, J. L. Sánchez Romero and F. Pujol López , Partial production reduction based on lookup tables, Int. Conf. VLSI Design, Hyderabad, India, 3–7 January, 2006, pp. 399–404 Google Scholar
6. J. Poldre and K. Tammemae , Reconfigurable multiplier for Virtex FPGA family, Int. Workshop Field-Programmable Logic and Applications, Glasgow, UK, 30 August–1 September, 1999, pp. 359–364. Google Scholar
7. C. S. Wallace , A suggestion for a fast multiplier, IEEE Trans. Electron. Comput. 13 (1964) 14–17. Crossref, Web of Science, Google Scholar
8. H. Parandeh-Afshar, A. Neogy, P. Brisk and P. Ienne , Compressor tree synthesis on commercial high-performance FPGAs, ACM Trans. Reconfig. Techn. Syst. 4 (2011) 1–19. Crossref, Web of Science, Google Scholar
9. H. Parandeh-Afshar, P. Brisk, and P. Ienne , Efficient Synthesis of Compressor Trees on FPGAs, Asia and South Pacific Design Automation Conf. (ASPDAC). IEEE, 2008, pp. 138–143. Google Scholar
10. H. Parandeh-Afshar, P. Brisk and P. Ienne , Exploiting fast carry-chains of FPGAs for designing compressor trees, Proc. 19th Int. Conf. Field Programmable Logic and Applications (Prague, Czech Republic, 2009), pp. 242–249. Google Scholar
11. H. Parandeh-Afshar, P. Brisk and P. Ienne , Improving synthesis of compressor trees on FPGAs via integer linear programming, Design, Automation and Test in Europe (DATE). IEEE, 2008, pp. 1256–1261. Google Scholar
12. T. Matsunaga, S. Kimura and Y. Matsunaga , Power and delay aware synthesis of multi-operand adders targeting LUT-based FPGAs, Int. Symp. Low Power Electronics and Design (ISLPED), 2011, pp. 217–222. Google Scholar
13. T. Matsunaga, S. Kimura and Y. Matsunaga , Multi-operand adder synthesis targeting FPGAs, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E94-A (2011) 2579–2586. Google Scholar
14. T. Matsunaga, S. Kimura and Y. Matsunaga , An exact approach for GPC-based compressor tree synthesis, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E96-A (2013) 2553–2560. Google Scholar
15. M. Kumm and P. Zipf, Efficient high speed compression trees on Xilinx FPGAs, Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen (2014). Google Scholar
16. M. Kumm and P. Zipf , Pipelined compressor tree optimization using integer linear programming, 24th Int. Conf. Field Programmable Logic and Applications (2014). Google Scholar
17. B. Khurshid and R. Naaz , High Efficiency Generalized Parallel Counters for Look-Up table based FPGAs, Int. J. Reconfig. Comput. 2015 (2015) 518272. Crossref, Google Scholar
18. B. Khurshid and R. Naaz , High efficiency generalized parallel counters for Xilinx FPGAs, 22nd IEEE Int. Conf. High Performance Computing, Bangalore, India, 16–19 December 2015. Google Scholar
19. K. K. Parhi , VLSI Digital Signal Processing Systems Design and Implementation (Wiley, 1999). Google Scholar
20. http://www.xilinx.com. Google Scholar
21. B. Khurshid and R. Naaz , Technology-dependent optimization of FIR filters based on carry-save multiplier and 4:2 compressor unit, Electron. J. 20 (2016) 43–54. Google Scholar