Ìàãèñòåðñêîå è ïîñëåâóçîâñêîå îáðàçîâàíèå

Mathematical models and methods in VLSI design

Scientific supervisor: doctor of physical-and-mathematical sciences Lozhkin Sergey Andreevich

Curricular coursers and annotation.

1. Ñomplexity of combinatorial algorithms. General models and statements about the complexity of combinatorial tasks, methods for development of fast algorithms (method of dynamic programming, ?divide and conquer?, ?method of model extension?) are considered. Examples of applications of these methods and bounds on complexity are shown. Main complexity classes and examples of complete problems are given.

2. Additional questions of structural theory of circuits. Methods of synthesis and obtaining lower bounds on complexity for certain functions used in applications are considered. Additional tasks for synthesis related to studying of Shannon function behavior on the level of high accuracy asymptotic bounds as well as tasks for synthesis of functions from special classes are solved. The questions of geometrical implementation of circuits are studied.

3. Mathematical models and methods of VLSI design. Key questions of logical and topological synthesis of VLSI are studied. Mathematical models of contemporary electronic circuits are considered and basic approaches to solving task of logic synthesis, as well as tasks of VLSI modules placement and interconnection routing are described.

4. Languages for description of circuits. Verification problems. Basic languages for formal description of electronic circuits (VHDL, Verilog) are considered. Key questions related to logical analysis and verification of circuits on the basis of corresponding descriptions are studied.

5. Mathematical models of physical microchip design tasks. Mathematical models of microelectronic devices in the form of circuits with concentrated parameters are studied. Target setting, generation and solving methods of differential-algebraic equations corresponding to conditional potentials are described. The presentation is oriented on high dimensional tasks obtained using extraction of parameters of microchips.

6. Theory of control and reliability of circuits. Methods for generating tests. Some probabilistic models of reliability of circuits functioning are supposed and bounds on unreliability of circuits are proven in the course. Methods for synthesis of circuits with small unreliability and self-correcting circuits from certain classes are given. Bounds on Shannon function for complexity of these circuits are shown. Methods for generating optimal and near to optimal tests for a number of classes of control systems and sources of faults are considered and methods for obtaining lower and upper bounds on the lengths of tests are studied. Results for behavior of Shannon function for tests lengths and lengths of minimal tests for almost all functions are provided.

7. Additional questions of graph theory and combinatorial calculus. Course consists of three sections: methods of linear algebra in graph theory, enumerations of graphs and algorithms on graphs used in VLSI design. The first section covers various applications of methods of linear algebra in graph theory. Kirchhoff theorem for trees, statements about revealing certain properties of graph from its adjacency, incidence matrix and spectrum of adjacency matrix are proven. In second section the most attention is paid to applications of generating functions in estimating numbers of graphs of various types. Generating functions for labeled and unlabeled graphs, oriented graphs, connected graphs, blocks and trees are studied. In third section a number of algorithms on graphs used in VLSI design are provided.

8. Computational linear algebra for tasks of high dimension. The survey of numerical methods of linear algebra used in solving high dimensional tasks is given.

9. Solving Boolean equations and satisfiability problem. Methods for solving Boolean equations become more and more essential in synthesis of digital control systems. At the same time curricular courses and tutorials fully covering these questions are absent. Given course is called to fill the specified gap. Theoretical questions of Boolean algebra, modern theories of Boolean functions, including Boolean differential and integral calculus, various approaches to the solution of Boolean equations of different types and applications of the results to synthesis of digital circuits are considered. Contemporary methods for solving minimization tasks of Boolean functions, normal forms synthesis and satisfiability tasks are provided in the course. Ordered binary decision diagrams, formal verification, Nelson?s method of multiplication, building DNF with small number of 0 are studied in details. A special attention is paid to effective numerical implementation of combinatorial algorithms on computing devices.