Retiming is a transformation which can be applied to digital filter blocks that can increase the clock frequency. This transformation requires computation of critical path and shortest path at various stages. In literature, this problem is addressed at multiple points. However, very little attention is given to path solver blocks in retiming transformation algorithm which takes up most of the computation time. In this paper, we address the problem of optimizing the speed of path solvers in retiming transformation by introducing high level synthesis of path solver algorithm architectures on FPGA and a computer aided design tool. Filters have their combination blocks as adders, multipliers, and delay elements. Avoiding costly multipliers is very much needed for filter hardware implementation. This can be achieved efficiently by using multiplierless MCM technique. In the present work, retiming which is a high level synthesis optimization method is combined with multiplierless filter implementations using MCM algorithm. It is seen that retiming multiplierless designs gives better performance in terms of operating frequency. This paper also compares various retiming techniques for multiplierless digital filter design with respect to VLSI performance metrics such as area, speed, and power. 1. Introduction High level synthesis is the process of converting behavioral description or an algorithm to structural level specification. In behavior description or an algorithm, the input and output behavior is described in terms of data transfers and operations without any implementation details. Structural description maps this data transfers and operations into combinational functional units and registers on to hardware. High level synthesis of DSP algorithms is very much useful as it reduces time to market window. Various optimization methods are available in literature for sequential synthesis [1]. Though synthesis of combinational logic has attained a significant level of maturity, sequential circuit synthesis has been lagging behind [2] in terms of frequency performance. DSP algorithms are repetitive and periodically iterations must be repeated to execute the computations [3]. Here, iteration period is the minimum time needed for computation and this is limited by critical path. Critical path can be altered by redistributing the delays such that functionality is preserved. Retiming algorithm [4] is used to redistribute the delays without altering [5] the functionality. A great amount of research has been done on retiming [5, 6]. The retiming technique is the
References
[1]
C. Soviani, O. Tardieu, and S. A. Edwards, “Optimizing sequential cycles through shannon decomposition and retiming,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 3, pp. 456–467, 2007.
[2]
S. Bommu, N. O'Neill, and M. Ciesielski, “Retiming-based factorization for sequential logic optimization,” ACM Transactions on Design Automation of Electronic Systems, vol. 5, no. 3, pp. 373–398, 2000.
[3]
K. K. Parhi, “A systematic approach for design of digit-serial signal processing architectures,” IEEE Transactions on Circuits and Systems, vol. 38, no. 4, pp. 358–375, 1991.
[4]
D. Yagain, A. V. Krishna, and S. Chennapnoor, “Design optimization platform for synthesizable high speed digital filters using retiming technique,” in Proceedings of the 10th IEEE International Conference on Semiconductor Electronics (ICSE '12), pp. 551–555, Kuala Lumpur, Malaysia, September 2012.
[5]
N. Shenoy, “Retiming: theory and practice,” Integration, the VLSI Journal, vol. 22, no. 1-2, pp. 1–21, 1997.
[6]
C. E. Leiserson and J. B. Saxe, “Retiming synchronous circuitry,” Algorithmica, vol. 6, no. 1–6, pp. 5–35, 1991.
[7]
Y. Tsao and K. Choi, “Area-efficient VLSI implementation for parallel linear-phase FIR digital filters of odd length based on fast FIR algorithm,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 59, no. 6, pp. 371–375, 2012.
[8]
K. K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation, John Wiley & Sons, 2007.
[9]
K. K. Parhi, “Hierarchical folding and synthesis of iterative data flow graphs,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 60, no. 9, pp. 597–601, 2013.
[10]
X. Zhu, T. Basten, M. Geilen, and S. Stuijk, “Efficient retiming of multirate DSP algorithms,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 6, pp. 831–844, 2012.
[11]
N. Liveris, C. Lin, J. Wang, H. Zhou, and P. Banerjee, “Retiming for synchronous data flow graphs,” in Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC '07), vol. 7, pp. 480–485, Yokohama, Japan, January 2007.
[12]
N. L. Passos, E. H. Sha, and S. C. Bass, “Optimizing DSP flow graphs via schedule-based multidimensional retiming,” IEEE Transactions on Signal Processing, vol. 44, no. 1, pp. 150–155, 1996.
[13]
J. R. Jiang and R. K. Brayton, “Retiming and resynthesis: a complexity perspective,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 12, pp. 2674–2686, 2006.
[14]
N. Maheshwari and S. Sapatnekar, “Efficient retiming of large circuits,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 6, no. 1, pp. 74–83, 1998.
[15]
D. Yagain and A. Vijaya Krishna, “High speed digital filter design using register minimization retiming & parallel prefix adders,” in Proceedings of the 3rd International Conference on Emerging Applications of Information Technology (EAIT '12), pp. 449–453, Kolkata, India, December 2012.
[16]
J. Cong and C. Wu, “An efficient algorithm for performance-optimal FPGA technology mapping with retiming,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 9, pp. 738–748, 1998.
[17]
D. Yagain, A. Vijayakrishna, P. Nikhil, A. Adarsh, and S. Karthikeyan, “FPGA based path solvers for DFGs in high level synthesis,” in Proceedings of the 2nd International Conference on Advances in Computational Tools for Engineering Applications (ACTEA '12), pp. 273–278, IEEE, Beirut, Lebanon, December 2012.
[18]
Y. Voronenko and M. Püschel, “Multiplierless multiple constant multiplication,” ACM Transactions on Algorithms, vol. 3, no. 2, article 11, Article ID 1240234, 2007.
[19]
K. Johansson, O. Gustafsson, and L. Wanhammar, “Multiple constant multiplication for digit-serial implementation of low power FIR filters,” WSEAS Transactions on Circuits and Systems, vol. 5, no. 7, pp. 1001–1008, 2006.
[20]
A. Baliga, “Design of high-speed adders for efficient digital design blocks,” ISRN Electronics, vol. 2012, Article ID 253742, 9 pages, 2012.
[21]
H. D. Tiwari, G. Gankhuyag, C. M. Kim, and Y. B. Cho, “Multiplier design based on ancient indian vedic mathematics,” in Proceedings of the International SoC Design Conference (ISOCC '08), vol. 2, pp. II65–II68, Busan, Republic of Korea, November 2008.
[22]
G. Dimitrakopoulos and D. Nikolos, “High-speed parallel-prefix VLSI ling adders,” IEEE Transactions on Computers, vol. 54, no. 2, pp. 225–231, 2005.
[23]
L. Aksoy, E. da Costa, P. Flores, and J. Monteiro, “Exact and approximate algorithms for the optimization of area and delay in multiple constant multiplications,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 6, pp. 1013–1026, 2008.
[24]
M. N. Mneimneh, K. A. Sakallah, and J. Moondanos, “Preserving synchronizing sequences of sequential circuits after retiming,” in Proceedings of the Asia and South Pacifi c Design Automation Conference, pp. 579–584, IEEE Press, 2004.
[25]
D. Yagain and K. A. Vijaya, “Fir filter design based on retiming and automation using vlsi design metrics,” in Proceedings of the International Conference on Technology, Informatics, Management, Engineering, and Environment (TIME-E '13), pp. 17–22, IEEE, 2013.
