Manu Manuel, M.Sc.

Multi-objective Optimization (MOO) is well-known for trade-off analysis between objectives in many real-world problems including embedded systems design, for example [1]. The MOO results in the formation of  Pareto Optimal points that allows the decision-maker to select the points based on his desired trade-off in an application. One typical example for MOO is a Genetic Algorithm based on NSGA selection [2]. However, NSGA algorithms often lead to the exploration and optimization of the entire design space in each objective dimension. This is not necessary for many applications and a significant computational effort is wasting for regions outside the threshold values in the decision maker's mind. 

This seminar aims to summarize different multi-objective optimization approaches which form Pareto Optimal solutions based on the preference given by the designer (e.g. [3]). Besides, comparisons between each method and the benefits and drawbacks of these methods in real-world applications also need to be investigated.

[1] Manu Manuel, Arne Kreddig, Simon Conrady, Nguyen Anh Vu Doan, Walter Stechele: Model-Based Design Space Exploration for Approximate Image Processing on FPGA. 2020 IEEE Nordic Circuits and Systems Conference (NorCAS), 2020.

[2] K. Deb, S. Agrawal, A. Pratap and T. Meyarivan, "A Fast Elitist Nondominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II", Parallel Problem Solving from Nature PPSN VI ser. Lecture Notes in Computer Science, pp. 849-858, 2000.

[3] Kalyanmoy Deb and J. Sundar. Reference point based multi-objective optimization using evolutionary algorithms. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO ‘06, 635–642. New York, NY, USA, 2006.

manu.manuel@tum.de

In image processing, non-linear transfer functions, such as sigmoid- or logarithm-shaped functions, are being used for mapping the input into different domains. For dedicated FPGA implementation of general image processing pipelines, these transfer functions are usually implemented by LUTs (Lookup Tables). Although the LUT-based method is more concise than some approximate direct implementation, it consumes a lot of resources. To save FPGA resources, sparse LUTs can be used, but it is to be noticed that the matching accuracy is then approximated to a certain acceptable range.

To further reduce the resource consumption, while maintaining or even improving the output accuracy, we propose a dynamic loading mechanism. In order to make full use of the resources on the chip, instead of placing one sparse LUT on chip, two function-wise complemented memory blocks shall be implemented in the data path of the processing pipeline. One of the memory blocks shall be filled only with the data points that fit the local range of current input data stream. Another one works as a general ultra-sparse LUT to map the input data into the inaccurate global range. In summary, a permanent memory block of very sparse/inaccurate data points should be kept on FPGA, which is then complemented by a memory block of accurate data points which are dynamically swapped in and out from an off-chip memory (DRAM). Based on this proposal, we need to investigate a dynamic loading mechanism for that accurate memory block, such that the input will fall into the local range with rational high probability.

In this work, a prototype of a sparse LUT with a dynamic precision adaptation mechanism should be developed on FPGA. In this thesis, several questions should be answered:

• How does the architecture of the implementation look like?

• What memory configuration should be used?

• How to determine when to load new data for the accurate memory block?

• What is the trade-off between accuracy and resource consumption?

Approximate computing provides a new design paradigm by performing inexact calculations instead of the actual one at the expense of output application quality. As a result, fewer resources are used, more functions can be implemented, and the energy efficiency of the calculations is improved. However, the output quality is preserved above a certain threshold. Cartesian Genetic Programming(CGP) is an evolutionary approach that is employed in digital circuit design and optimization.

This research work aims to bring the CGP together with AC and evaluate the effect of CGP in the optimization of the approximated digital circuits.