The PAGsuite project has been moved to https://gitlab.com/kumm/pagsuite, this is the old repository
Welcome to the PAGsuite project
About PAGsuite project
The suite contains optimization tools for the pipelined multiple constant multiplication (PMCM) problem, i.e., the multiplication of a single variable with multiple constants using bit-shifts, registered adders/subtractors and registers, such that a register is placed after each addition/subtraction and the pipeline is valid. Including the pipeline registers in the optimization is extremly usefull for FPGA-based designs but is also benefically for ASIC designs [1-3]. As PMCM is a generalization of the MCM problem (without pipelining), it can also be used to find MCM solutions with minimal adder depth.
Three algorithms are provided with PAGSuite, the heuristic RPAG, the optimal ILP-based tool OPAG and PAG fusion, which are briefly introduced in the following:
RPAG
RPAG solves the PMCM problem in a heuristic way. The algorithm was initially proposed in [2] where all fundamental ideas of the algorithm are presented. It is a heuristic approach that is based on a greedy search. Due to its fast implementation a second stage of optimization is possible to enhance the optimization results which are either based on random selection [2] or again a greedy search. It was later extended to include embedded FPGA multiplers for larger word sizes as needed for single precision floating point [4]. This work was outdated by [5] which can incoporate a given number of embedded multipliers of a given size for any word size. Applications are to reduce the number of embedded multipliers in large multipliers (e.g., as needed in floating point) or to compensate for a limited number of embedded multipliers in an efficient way.
A recent extension allows the usage of ternary adders, i.e., adders with three inputs as available on modern FPGAs of Xilinx and Altera [6].
OPAG
OPAG solves the PMCM problem exact using integer linear programming (ILP). The initial ILP formulation was presented in [7] but further extended by several alternative ILP formultaions to improve the speed/quality [1]. It uses Googles or-tools library (https://developers.google.com/optimization) which is used as a wrapper for different ILP solvers. Currenly, the solvers SCIP (http://scip.zib.de), CPLEX (http://www.ibm.com/software/commerce/optimization/cplex-optimizer) and Gurobi (http://www.gurobi.com) are supported and well tested.
The or-tools library is mandatory and has to be compiled with the ILP optimizers of choice. Paths to include file and libraries have to be provided in the qmake project file (opag.pro).
PAG fusion
PAG fusion solves the problem of finding run-time reconfigurable constant multipliers (RCMs). These are multiplication circuits in which the output constant can be chosen from a predefined set of constants during run-time. This is achieved by the insertion of multiplexers into constant multiplication circuits. Doing this a reduction in the required resources can be achieved by a reuse of redundant partial circuits. The problem which is solved is to find the best possible solution with a minimal fusing multiplexer overhead. An optimal approach was proposed in [8], but had to be supplemented by a heuristic and many other optimizations to enable RMCM generation for relevant problem sizes [9]. The benchmark coefficients used in this paper can be found in source:pagsuite/trunk/benchmarks/DAGfusionTest.csv and the output text files of DAG fusion can be downloaded within source:pagsuite/trunk/benchmarks/DAGfusionTestILPInput.zip.
Optimal Shift Reassignment
The Optimal Shift Reassignment (OSR) method is based on the idea that shifts can be allocated at different places along the circuit, while the calculated output constant stays the same. In the context of reconfigurable constant multiplication, this is new and differs from previous approaches, which were limited by the fact that all the constants within the constant multiplier were forced to be odd. However, the OSR method releases this restriction. As a result, the number of required multiplexers in the circuit can be reduced. This happens when the shift reassignment makes several inputs of a multiplexer correspond to the same shift of a certain signal. The source code can be found in pagsuite/trunk/pag_muxilp of the current release. The code is dependent on the PAGsuite libraries and on our ILP Wrapper project: https://digidev.digi.e-technik.uni-kassel.de/scalp. Integration into the PAGsuite make environment is planned. Information on the benchmarks to evaluate OSR performance can be found at the end of the last section (DAG fusion).
Selected References
[1] Martin Kumm, "Multiple Constant Multiplication Optimizations for Field Programmable Gate Arrays", Dissertation, Defended: 30.10.2015, Published: 02.05.2016, Springer Wiesbaden, ISBN: 978-3-658-13322-1, doi:10.1007/978-3-658-13323-8
[2] M. Kumm, P. Zipf, M. Faust, and C.-H. Chang, “Pipelined Adder Graph Optimization for High Speed Multiple Constant Multiplication,” IEEE International Symposium on Circuits and Systems (ISCAS), pp. 49–52, 2012.
[3] M. Kumm and P. Zipf, “High Speed Low Complexity FPGA-Based FIR Filters Using Pipelined Adder Graphs,” presented at the International Conference on Field-Programmable Technology (FPT), 2011, pp. 1–4.
[4] M. Kumm, K. Liebisch, and P. Zipf, “Reduced Complexity Single and Multiple Constant Multiplication in Floating Point Precision,” International Conference on Field Programmable Logic and Application (FPL), 2012.
[5] M. Kumm and P. Zipf, “Hybrid Multiple Constant Multiplication for FPGAs,” IEEE International Conference on Electronics, Circuits and Systems (ICECS), 2012, pp. 556–559.
[6] M. Kumm, M. Hardieck, J. Willkomm, P. Zipf, and U. Meyer-Baese, “Multiple Constant Multiplication with Ternary Adders,” International Conference on Field Programmable Logic and Application (FPL), 2013, pp. 1-8.
[7] M. Kumm, D. Fanghänel, K. Möller, P. Zipf & U. Meyer-Baese, “FIR Filter Optimization for Video Processing on FPGAs,” EURASIP Journal on Advances in Signal Processing (Springer), 2013, pp. 1-18.
[8] K. Möller, M. Kumm, M. Kleinlein, P.Zipf, "Pipelined Reconfigurable Multiplication with Constants on FPGAs," Field Programmable Logic and Applications (FPL), 2014 24th International Conference on, Munich, 2014, pp. 1-6.
[9] K. Möller, M. Kumm, M. Kleinlein, P.Zipf, "Reconfigurable Constant Multiplication for FPGAs", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol., no., pp., 2016
[10] M. Kumm, M. Hardieck, P. Zipf, "Optimization of Constant Matrix Multiplication with Low Power and High Throughput", IEEE Transactions on Computers, 66(12), 2072–2080, 2017
[10] K. Möller, M. Kumm, M. Garrido, P. Zipf, "Optimal Shift Reassignment in Reconfigurable Constant Multiplication Circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 37(3), 710–714, 2018
[12] M. Hardieck, M. Kumm, K. Möller, P. Zipf, "Constant Matrix Multiplication with Ternary Adders", IEEE International Conference on Electronics, Circuits and Systems (ICECS), 2018
Project Organisation
Project admins are
- Martin Kumm <kumm(at)uni-kassel.de>
- Konrad Möller <konrad.moeller(at)uni-kassel.de>
If you encounter problems using this system, please contact Daniel Bischof <bischof@…>.
PAGsuite source code
Subversion repository
https://digidev.digi.e-technik.uni-kassel.de/home/svn/pagsuite
An account of the Digital Technology Group of the University of Kassel is required to contribute. For all other users the repository is read-only. It is recommended to download a release as zip-file as described below.
Code as zip-file
The current release is version 1.80 and can be downloaded as source distribution below.
pagsuite_1_80.zip (released 19. June 2019)
Changelog
RPAG v1.30 (released 26. June 2013):
First public release containing support for pipelined adder graph optimization with common adders or ternary adders and the possibility to include embedded multipliers in the adder graphs.
RPAG v1.40 (released 15. May 2014):
Support for constant matrix multiplication (CMM).
Computation of the pipelined adder graph without additional matlab script (--show_adder_graph flag).
Cost models for minimum adder depth graphs (--cost_model=min_ad_hl_fpga and min_ad_ll_fpga cost models)
Note that the support for embedded multipliers was disabled in this version (--max_no_of_mult option).
PAGSuite v1.50 (released 01. Oct 2015):
OPAG included and renamed to PAGSuite
RPAG now supports ternary adders in the CMM optimization
PAGSuite v1.60 (released 02. March 2016):
pag fusion is included in PAGSuite
PAGSuite v1.70 (released 10. November 2017):
Minor bugfixes in RPAG Matlab code for CMM Problems
Added pag_muxilp, in which the Optimal Shift Reassignment approach is implemented (see comments above)
Added oscm, a tool to determine the optimal SCM solution (based on work of Gustafsson and data extracted from Hcub of the Spiral project (http://spiral.ece.cmu.edu/mcm/gen.html)
Added omcm, a novel tool to optimally solve MCM and SCM problems using ILP.
PAGSuite v1.80 (released 19. June 2019):
Cleanup of whole suite, programs removed that are no longer maintained or does not fit into the cmake flow (hopefully, those tools will be merged back at some point in time):
pag_fusion, pag_muxilp, pag_split removed, because not longer maintained
opag removed, because of old qmake built system and its dependency on or-tools
Benchmarks
To evaluate the tools, we used several benchmarks. The data can be found at our benchmarks site.
Acceptable Use and Privacy Policy
Please be aware of the Acceptable Use and Privacy Policy of this system.
