دانلود رایگان مقاله طراحی و تحلیل الگوریتم بهینه سازی تکاملی برای تبدیل شناوری به نقطه ثابت

abstract

Hardware designs need to obey constraints of resource utilization, minimum clock frequency, power consumption, computation precision and data range, which are all affected by the data type representation. Floating and fixed-point representations are the most common data types to work with real numbers where arithmetic hardware units for fixed-point format can improve performance and reduce energy consumption when compared to floating point solution. However, the right bit-lengths estimation for fixed-point is a time-consuming task since it is a combinatorial optimization problem of minimizing the accumulative arithmetic computation error. This work proposes two evolutionary approaches to accelerate the process of converting algorithms from floating to fixed-point format. The first is based on a classic evolutionary algorithm and the second one introduces a compact genetic algorithm, with theoretical evidence that a near-optimal performance, to find a solution, has been reached. To validate the proposed approaches, they are applied to three computing intensive algorithms from the mobile robotic scenario, where data error accumulated during execution is influenced by sensor noise and navigation environment characteristics. The proposed compact genetic algorithm accelerates the conversion process up to 10.2× against the state of art methods reaching similar bit precision and robustness.

7. Conclusions

In this work, we presented EO and mo-cGAO as optimization methods to the bit-lengths estimation for a floating to fixed-point conversion as well as a systematic study to define parameter values for such methods. The bit-lengths estimation during the conversion from floating to fixed-point demand significant computational processing when dealing with unpredictable algorithms, commonly found in many fields of application as robotics. This is caused by the big training sets to estimate the error. Heuristics based on the error calculation have presented poor quality results that are achieved after a considerable computation time. Evolutionary approaches, on the other hand, are known for their exploration capability. They are usually able to return good solutions within a short computational time. The mo-cGAO propose in this paper is an estimation of distribution algorithm that integrates the exploration idea of Evolutionary approaches with the probability distribution of solutions in the search space. In the floating to fixed-point conversion, the application of the mo-cGAO accelerates the bit-lengths estimation. This improves project decisions related with the more appropriated data type to a given design. Furthermore, the reduced bit-lengths leads to a more compact hardware, with lower energy consumption and a possibly higher maximum frequency. The coherency of the theoretical results for the mo-cGAO parameters with the experimentally estimated ones, presented in Section 6.2, shows that the difficulty of the problem is correctly supposed to be between the BitInt and OneMax problems. Such theoretical model for the mo-cGAO indicates that no other evolutionary approach will have a better performance than the mo-cGAO adjusted according to the model without losing the confidence that the algorithm will find, if not the best, a near-optimal solution. As future work, we encourage research exploring different BBs sizes and its structures to further improve the bit estimation problem efficiency. The results in Table 6 shows that our proposed mo-cGAO find bounds comparable if not better than the formal approaches, which do not guarantee to find the best solution, but guarantee error obedience. On the other hand, our proposed approach cannot guarantee either error obedience or optimality, although we have theoretical evidence of near-optimal solutions as discussed before.