doc. Ing. Petr Fišer, Ph.D.

So called “approximate” logic circuits are one of contemporary mainstreams in logic design. Here the logic circuit needs not compute the desired function exactly, some error is tolerated. The main purpose of designing such circuits is a significantly reduced area and power consumption. Approximate circuits find application in image/audio processing and recognition, neural networks, data-mining, etc.

Testing of these circuits now becomes a new challenging task. Test generation for approximate circuits offers more degrees of freedom: the test needs not be complete, not all faults need to be tested in order to comply with the approximation demands. As a result, the test can be shorter.

The aim of the research will be to design novel Automated Test Patterns Generation (ATPG) algorithms for approximate circuits.

Algorithms used to design digital circuits (EDA algorithms) are usually of a greedy nature. Local decisions are made randomly, or based on topological structure, or by the algorithm designer’s experience. These decisions need not be well chosen, resulting in inferior result quality. To resolve this problem, AI strategies can be incorporated into EDA algorithms. Here the AI learns in the EDA process and then helps in the subsequent processing.

The aim of the research is to analyze possibilities of application of AI in logic synthesis algorithms and devise new AI-guided logic synthesis algorithms.

Contemporary logic synthesis and optimization tools (both commercial and academic) mostly emphasize computational speed, at expense of result quality. Our recent research has shown that these tools tend to get stuck in deep local optima, and therefore they often produce very inferior results (in terms of area and/or delay). One of the reasons for it is a deterministic nature of the algorithms. Randomization of the algorithms has been found to be a viable, but just partial solution to this problem [1], [2]. The second, and more important reason of failure is the lack of a global algorithm control. Most of present logic synthesis and optimization algorithms are of an iterative nature, whereas their individual parts (elementary operations) are executed essentially ad-hoc and speculatively. Implementation of efficient top-level algorithm control means should significantly improve performance of logic synthesis and optimization.

The aim of the research is to investigate the behavior of individual elementary synthesis steps (e.g., in the ABC synthesis tool [3]), determine their dependence and orthogonality, and devise an improved overall algorithm control.

• [1] P. Fišer and J. Schmidt, “Improving the Iterative Power of Resynthesis,” in Proc. of 15th IEEE Symposium on Design and Diagnostics of Electronic Systems (DDECS), Tallinn (Estonia), April 18-20, 2012, pp. 30-33.
• [2] P. Fišer and J. Schmidt, “On Using Permutation of Variables to Improve the Iterative Power of Resynthesis,” in Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), Freiberg (Germany), September 19-21, 2012, pp. 107-114.
• [3] Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification” [Online]. Available: http://www.eecs.berkeley.edu/alanmi/abc/.

Contemporary logic synthesis and optimization tools (both commercial and academic) mostly emphasize computational speed, at expense of result quality. Our recent research has shown that these tools tend to get stuck in deep local optima, and therefore they often produce very inferior results (in terms of area and/or delay). Randomized iterative algorithms seem to efficiently solve this problem [1], [2] – they offer a trade-off between the run-time and result quality.

Moreover, present studies have shown that most of logic synthesis and optimization tools are very sensitive to randomness accidently introduced “from outside”, by the designer itself [3], [4]. Synthesis then produces results significantly differing in quality, when only slight changes in the source circuit description are made. Such a behavior is highly unwanted. Thus, it is required to analyze this behavior, determine its reasons, and to suggest more efficient algorithms.

The aim of the research is to analyze selected logic synthesis and optimization algorithms [5], identify the reasons of the above-mentioned behavior, and identify points, where randomness can be introduced. The influence of randomness will be then analyzed and algorithms exploiting the randomness in a positive way will be devised [3], [4]. Next, new algorithms minimizing the sensitivity on the external randomness will be developed.

• [1] P. Fišer and J. Schmidt, “Improving the Iterative Power of Resynthesis,” in Proc. of 15th IEEE Symposium on Design and Diagnostics of Electronic Systems (DDECS), Tallinn (Estonia), April 18-20, 2012, pp. 30-33.
• [2] P. Fišer and J. Schmidt, “On Using Permutation of Variables to Improve the Iterative Power of Resynthesis,” in Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), Freiberg (Germany), September 19-21, 2012, pp. 107-114.
• [3] A. Puggelli, T. Welp, A. Kuehlmann, and A. Sangiovanni-Vincentelli, “Are Logic Synthesis Tools Robust?,” in Proc. of the 48th ACM/EDAC/IEEE Design Automation Conference (DAC), 5-9 June 2011, pp. 633-638.
• [4] P. Fišer, J. Schmidt, and J. Balcárek, “On Robustness of EDA Tools,” in Proc. of 17th Euromicro Conference on Digital Systems Design (DSD), Verona (Italy), August 27-29, 2014, pp. 427-434.
• [5] Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification” [Online]. Available: http://www.eecs.berkeley.edu/alanmi/abc/.

With the increasing complexity of presently manufactured chips, increasingly more data must be delivered to individual chip cores to test them. Compression of this data becomes now inevitable, because of the high cost of the ATE memory and test time expenses. The ratio of expenses spent by chip testing and its development is increasing. Therefore, test compression is and will increasingly be a hot topic. It is very challenging to contribute to the research in this area and to try to overcome established industrial tools in performance.

Different test compression mechanisms have been proposed, some of them are used in industry [1], [2]. Most of them rely on a combination of pseudo-random testing (and possibly BIST), which can be implemented on-chip as whole and does not need any data to be transmitted, and deterministic test. The deterministic test is algorithmically compressed, stored in the ATE memory, and decompressed on-chip.

The aim of the research is to design test compression/decompression methods based on advanced design-for-testability (DFT) architectures [3]. This will comprise of a design of possibly novel decompression architectures, algorithms for test compression for these architectures, and design of the overall HW architecture, where test decompression, BIST and various DFT features will be implemented.

This research will (can) follow up a successfully completed Ph.D. thesis [4], [5].

• [1] J. Rajski et al. “Embedded Deterministic Test”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no. 5, pp. 776-792, 2004.
• [2] Y. Huang, S. Milewski, J. Rajski, J. Tyszer and C. Wang, “Low Cost Hypercompression of Test Data,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 10, pp. 2964-2975, 2020.
• [3] R. Dorsch, H. Wunderlich, “Reusing Scan Chains for Test Pattern Decompression”, Journal of Electronic Testing: Theory and Applications, vol. 18, no. 2, pp. 231-240, 2002.
• [4] J. Balcárek, P. Fišer, and J. Schmidt, “Techniques for SAT-based Constrained Test Pattern Generation,” in Microprocessors and Microsystems, Elsevier, Vol. 37, Issue 2, March 2013, pp. 185-195. [5] J. Balcárek, „Implicit Representations in Testing and Dependability of Digital Circuits“, Ph.D. Thesis, CTU in Prague, 2016.
• [5] J. Balcárek, „Implicit Representations in Testing and Dependability of Digital Circuits“, Ph.D. Thesis, CTU in Prague, 2016.

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Software Engineering

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

The main objective of this thesis is to develop a web database of scientific conferences based on an existing solution that has been developed within several master's and bachelor's theses at FIT, CTU and FEL, CTU. At first, requirements analysis and domain model design were made. These analyses were followed by research of other possible solutions. The results showed that the best way to solve the problem may be extending a web database of publicatoins, which was developed within a master's thesis at FIT, CTU. When the extension of the web publication database was analysed and designed, the ER model was changed appropriately. Within the implementation process, large refactoring was applied to the whole application and new features were implemented. Usability testing was done on newly implemented features.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

Logic synthesis is an important topic in circuit domain. The ABC tool uses fully deterministic algorithms for logic synthesis. No random decisions are made in the process and for any input it returns the same output. Nonetheless algorithms are very sensitive to changes of variable ordering. Randomization of equal choices in the process may lead to find better results. In this thesis I successfully implemented randomization of balance and rewrite. Testing randomized rewrite ended as expected and its use in synthesis process may bring positive results. Nonetheless testing randomized balance generated worse results than deterministic one. So I reworked it many times to achieve algorithm which is able to compete that. I implemented semi-randomized balance. It generates better results on average than fully-randomized algorithm and it is worse than deterministic balance entirely by 0.09\%. This difference can be looked at just as statistical margin for error.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

This thesis analyses existing web application for managing publications and conferences, developed and used at the Faculty of Information Technology of Czech Technical University in Prague. In practical section, the application is further developed, main modifications are related to redesigning parts of user interface, in order to improve user friendliness. Other modifications concern search, unification of publications across the application, creating user help and authors' "profiles" linked to their publications, removing bugs and various small improvements.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

Ing. Robert Hülle

Department of Software Engineering

This thesis deals with the problematics of test pattern generation for circuits with RAS architecture. The thesis consists of a theoretical introduction, description and analysis of Minisat+ solver, its integration into LogSynth framework as a library and a creation of a test pattern generator base on a novel algorithm.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

Ing. Jaroslav Borecký, Ph.D.

Department of Theoretical Computer Science

The Bachelor thesis aims to design and implement a test compression algorithm based on the Illinois-Scan decompression architecture used for digital circuits. This is a method for a sequential logic testing, which converts sequential circuits in the connected combinational logic and flip-flops (DFFs), which are reordered in the chosen scan-chains. The test vectors are delivered to multiple scan-chains in parallel, which may cause the fault coverage loss. Therefore is very useful to find the configuration of the scan-chains, which maximizes the faults coverage and minimizes the test length. For this purpose, we use available test generation tools (ATPGs) - finally, I used ATPG Atalanta. The outcomes of the research are evaluated in the conclusion.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

Ing. Robert Hülle, Ph.D.

Department of Applied Mathematics

This thesis analyzes the possibility of using logic synthesis and optimization to speed up solving satisfiability problem (SAT) instances coming from both the standard benchmarks and different practical applications. Logic optimization, in principle, influences an instance in two main ways: (1) it reduces its size, and (2) structures making the instance difficult to solve could be dissolved. However, it is necessary to consider both times of synthesis and solving, as speed up in solving achieved by "stronger" synthesis could be outweighed by synthesis time, leading to an overall time increase. The efficiency of logic synthesis and optimization was evaluated using different instances and syntheses. It can both positively and negatively influence the overall time of solving, which mostly depends on the instance size and used synthesis. Based on the results, recommendations regarding the practical use of synthesis are made.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

This diploma thesis describes and analyzes the contemporary reference management software, which is currently utilized by a group of educators and students at CTU. Furthermore, comparison of the similar applications is made in this thesis - both the open-source ones and the commercial ones. A new application, which surpasses the flaws of the former application, is then designed, implemented and tested on the grounds of the before mentioned analysis. The new application is web based, built on modern technologies, fully responsive and interactive and is provided with many features which allow for example to add publications (including documents), to categorize them and finally to full-textually search in the added files. Yet another feature is the possibility to import to/export from the well-known reference formats such as BibTex, RefWorks and EndNote. Equally essential traits are also the categorization support, user and user-group administration and the interconnection with the third-party application Springer.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Digital Design

This thesis introduces the logic circuit division into appropriate parts, which are subsequently resynthesised in parallel. There is a purpose to get better final result than the whole circuit resynthesis. The own algorithm of circuit division is introduced. The results of both optimizing methods are compared by a large set of experiments. Time improving brought by division is also evaluated.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

The thesis presents extension of Web application for publication and conference management software used at the Faculty of Information Technology of Czech Technical University in Prague. The thesis describes and analyses the current application. On the basis of this analysis an extension of the application is designed. The revision improves user interface and implements possibility to add references and citations, their recognition, to keep a record of user's own publications, user's own tags for publications, possibility to add more ISBN/ISSN to journals, conference years and publications as well as additional minor modifications.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

Ing. Jaroslav Borecký, Ph.D.

Department of Software Engineering

This diploma thesis is about development of the educational application, which should help students to understand how a genetic algorithm works. A genetic algorithm is an optimization algorithm, which is inspired by biological evolution. Adjustable parameters and the visualisation of algorithm run as chart are the main instruments, which help students to deepen the knowledge in this field. Users can try to work on various problems. Problem instances could be created manually or automatically generated. The theoretical part analyses genetic algorithm strategies, which are later implemented. The practical part is about the application development. One application was created for three different optimization algorithms on request from the supervisor. The two other algorithms were implemented by my colleagues so my thesis focuses on genetic algorithm and developments parts I've been involved with. The new application is going to be used for teaching from next semester instead of old Java applets.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

Ing. Jiří Dostál, Ph.D.

Department of Software Engineering

This thesis is about creating an educational web application for demonstration of the simulated annealing algorithm. More precisly about analysis, design, implementation and testing of this application. I implemented multiple problems like travelling salesman problem and minimum vertex cover problem. I also created generators for each problem, that can generate instances of the problem based on input parameters.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

This thesis deals with design, implementation and user testing of application for demonstration of Tabu Search algorithm. Primary goal is to create a tool for students to help them understand how the algorithm works. Several problems are available and users can solve its instances. It is also possible to adjust algrithm parameters. Application offers progress visualisation and comparison of past runs. Instance generator is also available in the application.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

Ing. Jan Bělohoubek, Ph.D.

Department of Digital Design

This thesis deals with calculating of logical circuits diversity and dependency of such diversity with common-mode faults. Firstly we provide research of existing algorithms concerning graph diversity. Secondly we propose variant of existing algorithm to calculate diversity and thirdly we correlate outputs of said algorithm with simulated common-mode faults. The results are compared with results of the supervisor.

Thesis on DSpace

doc. Ing. Petr Fišer, Ph.D.

doc. Ing. Jan Schmidt, Ph.D.

Department of Software Engineering

This thesis analyses existing web application for managing publications and conferences, developed and used at the Faculty of Information Technology of Czech Technical University in Prague. In the thesis, application improvements are designed and implemented and also various bugs are removed. The improvements are mostly related to import and export of publications from the application and publication references management. Further development includes increasing application's user friendliness by extending tooltips and user documentation, bugfixes and other smaller improvements.

Thesis on DSpace