Developing a combinatorial model for the multiple constant multiplication

  • Authors

    • Firas Ali Jawad Al-Hasani Embedded Engineer at TracMap company
    2015-09-15
    https://doi.org/10.14419/ijet.v4i4.5132
  • Multiple Constant Multiplication (MCM) Operation, Demand Graph, Dynamic Capacitated Arc Routing Problem, Ant Colony Optimization (ACO) Metaheuristics, Common Subexpression Elimination (CSE) Heuristics, A−operation Decomposition.

  • Abstract

    A combinatoric model for the multiple constant multiplication (MCM) operation is developed. The model is found by decomposing each coefficient using the A−operation into two subexpressions. The constituted subexpressions are, in turn, decomposed using the A−operation. Connecting all of the decompositions results the decomposition graph which represents the solution space. The decomposition graph itself is not feasible for routing to find the minimum solutions. Therefore, a transformation on the A−operation is proposed to make the decomposition graph routable. In this case, the A−operation is transformed into a subexpression operation by replacing the shift information attached to the arcs by the other subexpression information which is called the demand. A demand that attached to an arc will represent its cost. The resulting transformed graph is called the demand graph. The demand graph is augmented with deadheading arcs to make it routable. Deadheading arcs are with zero demand. Similarly, traversing an arc with synthesized demand is of zero cost. Enumerating all of the routes that start from the signal vertex and visit all the coefficients gives all the solutions of the MCM problem. The routing technique requires redirecting the route when encountering an unsynthesized demand. The route in this case backtrack to the first encountered synthesized ancestors for this demand. This routing style analogous to the dynamic capacitated arc routing. To prevent exhaust routing, ant colony optimization (ACO) meta-heuristics is proposed to traverse the augmented demand graph. The solution space contains all the possible solutions that can be obtained from using both of the common subexpression elimination (CSE) and graph dependent heuristics that traditionally used to solve the MCM operation.

  • References

    1. [1] Levent Aksoy, Eduardo Costa, Paulo Flores, and José Monteiro. Optimization of Gate-Level Area in High Throughput Multiple Constant Multiplications. 20th European Conference on Circuit Theory and Design, ECCTD 2011, pages 588–591, Aug. 2011.

      [2] Levent Aksoy, Eduardo Costa, Paulo Flores, and José Monteiro. Optimization Algorithms for the Multiplierless Realization of Linear Transforms. ACM Transactions on Design Automation of Electronic Systems, 17(1), Jan. 2012.

      [3] Levent Aksoy, Ece Olcay GÜnes, and Paulo Flores. Search Algorithms for the Multiple Constant Multiplications Problem: Exact and Approximate. Microprocessors and Microsystems, 34(5):151–162, Aug. 2010.

      [4] F. Al-Hasani, M. Hayes, and A. Bainbridge-Smith. A New Subexpression Elimination Algorithm Using ZeroDominant Set. In Proceedings - 2011 6th IEEE International Symposium on Electronic Design, Test and Application, DELTA 2011, pages 45–50, Jan. 2011.

      [5] F. Al-Hasani, M.P. Hayes, and A. Bainbridge-Smith. A Common Subexpression Elimination Tree Algorithm. IEEE Transactions on Circuits and Systems I: Regular Papers, 60(9):2389–2400, Sept. 2013.

      [6] Tetsuo Asano, Naoki Katoh, and Kazuhiro Kawashima. A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree. Journal of Combinatorial Optimization, 5:213231, June 2001.

      [7] M.H. Abolhasani Ashkezari, N. Shahsavari Pour, and H. Mohammadi Andargoli. An ant colony system for solving fuzzy flow shop scheduling problem. International Journal of Engineering and Technology, 1(2):44–57, Apr. 2012.

      [8] Nilanjan Banerjee, Jung Hwan Choi, and Kaushik Roy. A Process Variation Aware Low Power Synthesis Methodology for Fixed-Point FIR Filters. In Proceedings of the International Symposium on Low Power Electronics and Design, pages 147–152, Aug. 2007.

      [9] D.R. Bull and D.H. Horrocks. Primitive operator digital filters. IEE Proceedings, Part G: Circuits, Devices and Systems, 138(3):401–412, June 1991.

      [10] Alberto Colorni, Marco Dorigo, and Vittorio Maniezzo. Distributed Optimization by Ant Colonies. European Conference on Artificial Life, pages 134–142, 1991.

      [11] Kenneth De Jong. Evolutionary computation: A unified approach. MIT Press, 1 edition, 2006.

      [12] A.G. Dempster, M.D. Macleod, and O. Gustafsson. Comparison of Graphical and Subexpression Elimination Methods for Design of Efficient Multipliers. Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, 1:72–76, Nov. 2004.

      [13] Andrew G. Dempster and Malcolm D. Macleod. Use of Minimum-Adder Multiplier Blocks in FIR Digital Filters. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 42(9):569–577, Sep. 1995.

      [14] K.F. Doerner, R.F. Hartl, G. Kiechle, M. Lucka, and M. Reimann. Parallel Ant Systems for the Capacitated Vehicle Routing Problem. Evolutionary Computation in Combinatorial Optimization: Lecture Notes in Computer Science, 3004:72–83, 2004.

      [15] Marco Dorigo and Thomas StÃœtzlea. Ant Colony Optimization. MIT Press, 1 edition, 2004.

      [16] Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine. Parallel boost graph library, 2009.

      [17] H.A. Eiselt, Michel Gendreau, and Gilbert Laporte. Arc Routing Problems, Part I: The Chinese Postman Problem. Operation Research, 43(2):231–242, March-April 1995.

      [18] H.A. Eiselt, Michel Gendreau, and Gilbert Laporte. Arc Routing Problems, Part II: The Rural Postman Problem. Operation Research, 43(3):399–414, May-June 1995.

      [19] James R. Evans and Edward Minieka. Optimization Algorithms for Networks and Graphs. Maecel Dekker Inc., 2 edition, 1992.

      [20] M.A. Farahani, E.C. Guerra, and B.G. Colpitts. Efficient Implementation of FIR Filters Based on a Novel Common Subexpression Elimination Algorithm. Canadian Conference on Electrical and Computer Engineering, pages 1–4, May 2010.

      [21] Mathias Faust and Chip-Hong Chang. Minimal Logic Depth Adder Tree Optimization for Multiple Constant Multiplication . 2010 IEEE International Symposium on Circuits and Systems: Nano-Bio Circuit Fabrics and Systems, ISCAS 2010, pages 457–460, May 2010.

      [22] Free Software. Eigen 3.2.0, 2013.

      [23] Oscar Gustafsson. A Difference Based Adder Graph Heuristic for Multiple Constant Multiplication Problems. In Proceedings - IEEE International Symposium on Circuits and Systems, pages 1097–1100, May 2007.

      [24] Oscar Gustafsson. Lower Bounds for Constant Multiplication Problems. IEEE Transactions on Circuits and Systems-II: Express Briefs, 54(11):974–978, Nov. 2007.

      [25] Oscar Gustafsson. Towards Optimal Multiple Constant Multiplication: A Hypergraph Approach. Asilomar Conference on Signals, Systems and Computers, pages 1805–1809, Oct. 2008.

      [26] Oscar Gustafsson, Andrew G. Dempster, Kenny Johansson, Malcolm D. Macleod, and Lars Wanhammar. Simplified Design of Constant Coefficient Multipliers. Circuits, Systems, and Signal Processing, 25(2):225–251, April 2006.

      [27] Hisashi Handa, Lee Chapman, and Xin Yao. Dynamic Salting Route Optimisation Using Evolutionary Computation. 2005 IEEE Congress on Evolutionary Computation, IEEE CEC 2005, pages 158–165, Sep. 2005.

      [28] Richard I. Hartley. Optimization of Canonic Signed Digit Multipliers for Filter Design. In Proceedings - IEEE International Symposium on Circuits and Systems, volume 4, pages 1992–1995, June 1991.

      [29] Yuen-Hong Alvin Ho, Chi-Un Lei, Hing-Kit Kwan, and Ngai Wong. Optimal Common Subexpression Elimination of Multiple Constant Multiplications with A Logic Depth Constraint. IEICE Trans. Fundamentals, E91-A(12):3568–3575, Dec. 2008.

      [30] William Kamp. Alternate Number Systems for Optimizing DSP Performance in FPGA. PhD thesis, Canterbury University, 2010.

      [31] Leon Y. Li and Richard W. Eglese. An Interactive Algorithm for Vehicle Routeing for Winter-Gritting. Journal of the Operational Research Society, 47(2):217–228, Feb. 1996.

      [32] Yong Ching Lim and Sydney R. Parker. Discrete Coefficient FIR Digital Filter Design Based Upon An LMS Criteria. IEEE Transactions on Circuits and Systems, CAS-30(10):723–739, Oct. 1983.

      [33] R. Mahesh and A.P. Vinod. A New Common Subexpression Elimination Algorithm for Realizing LowComplexity Higher Order Digital Filters. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(2):217–229, Feb. 2008.

      [34] R. Montemann, L.M. Gambardella, A.E. Rizzoli, and A.V. Donati. Ant Colony System for a Dynamic Vehicle Routing Problem. Journal of Combinatorial Optimization, 10:327343, Aug. 2005.

      [35] L.M. Moreira, J.F. Oliveira, A.M. Gomes, and J.S. Ferreira. Heuristics for a Dynamic Rural Postman Problem. Computers and Operations Research, 34(11):3281–3294, Nov. 2007.

      [36] Martín Pedemonte, Sergio Nesmachnow, and Héctor Cancela. A Survey on Parallel Ant Colony Optimization. Applied Soft Computing Journal, 11(8):5181–5197, Dec. 2011.

      [37] Miodrag Potkonjak, Mani B. Srivastava, and Anantha P. Chandrakasan. Multiple Constant Multiplications: Efficient and Versatile Framework and Algorithms for Exploring Common Subexpression Elimination. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(2):151–165, Feb. 1996.

      [38] A.E. Rizzoli, F. Oliverio, R. Montemanni, and L.M. Gambardella. Ant Colony Optimization for Real-World Vehicle Routing Problems: From Theory to Applications. Dalle Molle Institute for Artificial Intelligence Research, IDSIA, pages 1–50, 2004.

      [39] Henry Samueli. An Improved Search Algorithm for the Design of Multiplierless FIR Filters with Powers-of-Two Coefficients. IEEE Transactions on Circuits and Systems, 36(7):1044–1047, July 1989.

      [40] Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 1 edition, 2002.

      [41] Software and Hardware Generation for DSP algorithms. Multiplier block generator, 2009.

      [42] T. StÃœetzle and H. Hoos. The Max-Min Ant System and Local Search for Combinatorial Optimization Problems. 2nd International conference on metaheuritics - MIC 97, July 1997.

      [43] Jason Thong and Nicola Nicolici. Time-Efficient Single Constant Multiplication Based on Overlapping Digit Patterns . IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 17(9):1353–1357, Sep. 2009.

      [44] Jason Thong and Nicola Nicolici. An Optimal and Practical Approach to Single Constant Multiplication. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 30(9):1373–1386, Sep. 2011.

      [45] A.P. Vinod and Edmund M-K Lia. On the Implementation of Efficient Channel Filters for Wideband Receivers by Optimizing Common Subexpression Elimination Methods. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(2):295–304, Feb. 2005.

      [46] Yevgen Voronenko and Markus Püschel. Multiplierless Multiple Constant Multiplication. ACM Transactions on Algorithms, 3(2), May 2007.

      [47] Chia-Yu Yao, Hsin-Horng Chen, Tsuan-Fan Lin, Chiang-Ju Chien, and Chun-Te Hsu. A Novel Common Subexpression Elimination Method for Synthesizing Fixed-Point FIR Filters. IEEE Transactions on Circuits and Systems-I: Regular Papers, 51(11):2215–2221, Nov. 2004.

      [48] B. Yu, Z.-Z. Yang, and J.-X. Xie. A Parallel Improved Ant Colony Optimization for Multi-Depot Vehicle Routing Problem. Journal of the Operational Research Society, 62(1):183–188, Jan. 2011.

  • Downloads

    Additional Files

  • How to Cite

    Al-Hasani, F. A. J. (2015). Developing a combinatorial model for the multiple constant multiplication. International Journal of Engineering & Technology, 4(4), 472-488. https://doi.org/10.14419/ijet.v4i4.5132

    Received date: 2015-07-31

    Accepted date: 2015-09-08

    Published date: 2015-09-15