The article discusses one of the stages of creating a microcircuit physical (topological) design. At this stage, two main operations are: placing cells on the field of the base matrix crystal and tracing these elements. To create a high-quality microcircuit, it is necessary to follow certain design rules and carefully check the criteria for optimal placement. The basic rule for microcircuits: minimum power consumption with high speed and small area. The article presents a brief analysis of some disadvantages of the main techniques for placing elements on the field of the base matrix crystal. In addition, the main options for calculating the lengths of connections between the elements are considered, which also affects the accuracy of evaluating the parameters of the microcircuit. At present, in Russia, attention is increasing to the modification and improvement of domestic computer-aided design systems. In this regard, the most promising direction for further research was selected, as well as the main goals and objectives were formulated.
Microcircuit design is a complex and lengthy process. It includes a wide range of
different tasks. The complexity and degree of integration of large integrated circuits
(LSI) is growing every year. Specialized microcircuits for sensors of various purposes
[
Thus, at present, one of the priority directions in the manufacture of domestic LSI is the improvement of computer-aided design (CAD) tools, including subsystems responsible for the most optimal placement and routing of elements on the substrate. It is necessary to automate the design process of microcircuits, because, due to the increase in the number of elements that make up modern microcircuits, their routing and placement even on powerful computers in automatic mode can take a significant amount of time. 2
Basically, the analysis and work with the subject area was carried out on the basis of progress not only in the field of microelectronics and CAD, but also on the basis of the current development and widespread introduction of artificial intelligence (AI) and machine learning (ML) systems in various areas of modern science and life.
The article by M. Makushin and A. Fomina "Artificial Intelligence and
Profitability as Driving Factors of CAD Development" (DOI:
10.22184/19924178.2019.185.4.90.100) [
In addition, the possibilities of using AI as such in CAD systems are discussed in
the book Ibrahim (Abe) M. Elfadel, Duane S. Boning Xin Li "Machine Learning in
VLSI Computer-Aided Design" (DOI: 10.1007 / 978-3-030- 04666-8) [
General algorithms for working with ML, AI and deep learning were mastered on
such books as: Andrew W. Trask "grokking Deep Learning" (ISBN
978-5-44611334-7) [
Currently, many large firms are working on solutions in the field of CAD
improvement, in particular Google [
Over time, developers strive to make microcircuits more and more compact, but at
the same time high-speed and low power consumption. This was mainly achieved by
reducing the size of the transistor. In addition, the materials from which it was made,
the geometry, and the technological process changed. Based on empirical observation
of the development of microcircuits, Gordon Moore predicted that the number of
transistors placed on an integrated circuit chip would double every 24 months. The
main problems faced by the developers are the increase in power consumption and
overheating of microcircuits due to current leakage through the dielectric layer. Since
many solutions for improving transistors are currently in the development stage, many
scientists believe that reaching the threshold of silicon technology is approaching [
Due to a decreasing the size of transistors and the distance between elements on microcircuits, the number of transistors on microcircuit increases, and therefore the number of elements that must be placed and connected during development (fig. 1). The graph shows that the number of transistors actually doubled approximately every 2 years.
To create high-quality microcircuits, in particular, it is necessary to optimally place the elements on the substrate. The way in which the elements are placed and connected can directly affect both the time and power characteristics, and the stability of the microcircuit.
Despite many years of research in the field of creating and improving algorithms and placement technologies, the optimization problem is still relevant. Often, with a large number of elements, placement and tracing algorithms work for an unacceptably long time - from several hours to several days. Thus, for most formulations of the problem of placing and tracing elements, there are no sufficiently effective algorithms that can find the optimal solution in an acceptable time. That is because the majority of algorithms are modifications of the algorithm for full enumeration of placements. In this regard, it is important to develop algorithms that find solutions close to optimal in a limited time.
The purpose of this article is to analyze the criteria for the optimal placement of elements and consider the main existing methods for placing elements in the process of developing microcircuits in the interests of the subsequent search for ways to optimize the placement of elements in designing microcircuits. 4
When creating a microcircuit, it goes through a number of stages. The main route for
the design of microcircuits combines the following stages proposed by the
ScientificManufacturing Complex "Technological Center" [
- logical design - a structural description of the circuit is generated, consists of logical gates and their connections (list of connections), logical synthesis, functionallogical modeling (FLM) is carried out;
- physical (topological) design - the placement of cells on the field of the basic matrix crystal (BMC) is carried out, the synthesis of the topology taking into account the circuits, the calculation of the circuit delays of the LSI topology, the stability of the LSI design is estimated under various external influences, the influence of the topology parameters on the correct functioning and stability is analyzed project; - production of LSI; - testing LSI in wafers and body composition; - LSI qualification tests - tests for reliability, radiation resistance, etc; - testing LSI as part of the customer's equipment.
Thus, by the time the elements are placed and traced on the substrate, the requirements for the microcircuit, the technology, the functional library of cells are already known, the list of connections has been created and the simulation has been carried out. 5
The smallest LSI in CAD “Kovcheg” is the 5503 family: 576 to 5478 gates and 28
- 64 pins [
The standard procedure for placing elements on the BMK: 1) arrangement of the periphery in accordance with the statement of work and / or the direction of information (current);
2) possible placement of some elements manually - triggers, memory elements, etc. Possible layout (color) of the arrangement of blocks and subcircuits (inside them, triggers, buffers, etc. can also be pre-assigned before the automatic mode); 3) the rest of the elements are placed automatically according to the algorithms of the selected CAD; 4) correcting the position of individual elements, if necessary; 5) trace the elements; 6) if the routing did not work out (the connections did not go through), then return to placement, making edits or scattering elements from scratch (paragraph 4) or 2)). 6
Important indicators for the development of a high-quality microcircuit are power, frequency and area. This is reflected in the requirements for LSI: energy consumption, speed and dimensions. Thus, to create a microcircuit, it is necessary to minimize power consumption, increase performance and reduce size. This means that a highquality microcircuit should be as small as possible in size, consume as little energy as possible, and work as quickly as possible.
The minimum placement criterion currently used in CAD "Kovcheg" of the 5503 family is the total length of connections between elements. This is due to the fact that, mainly because of this characteristic, it is possible to increase performance, minimize area and reduce energy consumption. In this case, it is necessary to observe certain restrictions on minimizing the connections, since with a short length of connections, their density increases, which leads not only to difficulties for their implementation, but also to a possible increase in cross-talk between connections. In this regard, a criterion for the possibility of laying connections is usually introduced - congestion, or density. Algorithms that take this criterion into account try to distribute all the elements evenly throughout the microcircuit.
In addition, performance metrics such as latency and power consumption are
evaluated. All data streams are split into parts using triggers. Between two triggers, the
signal must pass within a certain time - a period. However, the greater the distance
between the elements, the longer the signal goes, that is, the capacity increases. This
is the delay [
For the case of the criterion for minimizing the length of joints, the problem statement is as follows.
Let the elements of the microcircuit be given to place e1, e2, …, en …, eN. To determine the connections of elements, you can set, for example, an adjacency matrix, since in the general case, connected elements can be represented in the form of a graph. In addition, a plan is set on the microcircuit - a fixed set of positions in which the elements P1, P2, …, Pm, …, PM should be placed, and the sum of N elements in area cannot exceed the area of the microcircuit (1):
So there are M!/(M-N)! options for the placement of elements, when calculating which it is necessary to take into account rn,m- the distance between the centers of positions Pn and Pm of elements. After moving any element en to a new position Pm, the change in the contribution of the distance between this and the elements connected to it in the total amount of distances is estimated (2):
To create a high-quality microcircuit, in particular to achieve high performance, it is necessary to find such an optimal arrangement, at which the minimum amount of distances will be ensured (3): 7
When placing the elements in the BMC field, it is necessary to approximately calculate the distance between the elements, evaluating the length of the connection obtained with this formulation of the element, as well as its contribution to the total sum of the length of the microcircuit connections.
The most effective and widely used method in practice is the semi-perimeter method, bordering the connection of a rectangle. In practice, the method allows a fairly accurate estimate of the length of the connection between two or three elements, however, if there are more elements, then the method gives an underestimate. In this case, there are several options for the bordering rectangle itself (fig. 3). In the figure, the (1) (2) (3) element to be placed is highlighted in yellow with a dot, and the elements already placed are presented in the form of schematic cells of the BMC.
Fig. 3. Options for the bordering rectangle: a) the bordering rectangle covers the contacts entirely; b) the centers of the elements are covered; c) the part of contacts that would be captured when constructing the Steiner tree is covered; d) the bordering rectangle is drawn through the lower left corners of the elements
The most commonly used methods are b) and c). Of these, method c) estimates the
distance between the connected elements most accurately, and method b) is the easiest
to implement. In CAD Kovcheg, for example, variant b) of the bordering rectangle is
used [
The calculation of the total contribution to the connections from the movement of the cell is carried out with the help of bordering rectangles for groups of elements. The diagram shows an example of calculation for several groups of interconnected elements and an external contact of the circuit - a peripheral cell (light green element 3). The field with cells for placing the main elements (1, 2, 4-8) is a schematic field of the BMC used for the production of LSI, where one cell contains four unconnected transistors, forming one conditional gate. In this case, the amount consists of several components, including distances between elements 2 and 3 (green bordering rectangle) and the distance between the five elements 4 - 8 (blue bordering rectangle). Further, the distances from the semi-perimeter rectangles (black lines) to the element being placed (purple rectangle) are added to the sum of these semi-perimeters. Thus, it can be concluded that the total length of the connections decreases or increases. 8
Basically, the following methods are distinguished when placing elements. 1. The first method was the simulated annealing method. With regard to the placement problem, the initial placement of elements is taken, which, by means of permutations of elements, attempts are made to improve by accepting or rejecting transformations in accordance with the optimization criteria. The permutation element is selected based on the selected probability distribution. Most often, for minimization, they are guided by the total approximate length of the connections from the bordering rectangle. The disadvantages of this method are the significance of the time spent on its operation, since the annealing method, which consists in enumerating all possible combinations, most often works until the sum becomes close to the specified one, since with a large number of elements it can minimize the sum to infinity even when using parallelism technologies. Accordingly, the judgment about the optimality of the resulting placement is subjective. However, in comparison with genetic algorithms, according to Ingberg, the method does not lose in most problems, and even wins in many problems.
2. Various genetic algorithms were applied in a similar manner. Most often they
were used with parallelism, i.e. using the capabilities of the computer to perform
several operations at the same time, since they were too slow. The advantage of genetic
algorithms is that they are relatively resistant to hits in local optima. However, due to
this, they find even an approximate global optimum much more slowly. In the 2000s,
there is a surge of interest in this topic, attention is paid to improving the algorithm
and techniques for its parallelization (for example, [
3. Iterative or dichotomous approach - methods based on a gradual decrease in the dimension of the problem. At each iteration, the set of micro-circuit elements is split into several subsets, each of which is split again, and so on. Among the general drawbacks of algorithms of this type, they are distinguished by their relatively high complexity of constructing an optimal partitioning tree of a scheme (the problem of balanced partitioning of a graph is NP-complete, therefore, heuristic algorithms that are not guaranteed to be accurate or optimal are used to solve it) and a simplified estimate connections. In addition, the use of heuristic algorithms does not guarantee finding the correct solution and finding a solution in principle, even if it exists, which, together with the time spent on the operation of the algorithm with a large number of placed elements, makes it undesirable for use without modifications and improvements.
4. The so-called forceful or analytical methods. Their peculiarity lies in the fact
that the placement problem is formulated as a mathematical problem or a problem in
mechanics. In the first case, a mathematical programming problem with a quadratic
cost function is presented. In the second, the laws of physics are applied. The more
weight the connection has, the stronger the connected elements should attract and the
closer they should be. In addition, additional forces are added to compensate for the
attraction and prevent all elements from being grouped in the center of the
microcircuit. The simplest case is when a force is introduced that is inversely proportional to
the distance. Sometimes peripheral cells or input-output cells are used as such forces
[
Thus, since each approach has certain drawbacks, in particular, associated with the complexity of the microcircuit, the number of elements and imposed restrictions, it seems appropriate to use neural networks in the analysis of microcircuit designs to select the most suitable method for placement. Genetic algorithms are mainly used with parallelization, therefore, their use, which directly depends on the processor power, is not suitable for speeding up placement. Another option for solving this problem is the placement of elements based on an innovative method of reinforcement learning - a new section of AI, since this option can be much faster than standard algorithms. 9
The proposed method should help to reduce the time of placement and routing of LSI elements at the stage of topological design. Reinforcement learning will allow, based on the use of an agent, to train a neural network to simulate the decisions of developers, both separately taken and several.
In addition, the created neural network can be trained during operation, allowing you to adapt the placement for a particular developer.
The main direction of further research will be related to the choice of technology, architecture, teaching methods and the choice of technology for imitation in the choice of a specialist. 10
At the present time in Russia there is a growing interest in specialized
microcircuits [
In order to achieve the set goals, it is necessary to solve the following tasks. 1. Analyze the existing techniques for tracing elements on a micro-circuit substrate in order to identify the most costly stages of techniques for improving them or creating your own method.
2. To develop a methodology and algorithms for placing and tracing elements on a microcircuit substrate that implement it to reduce the resource intensity of the topological design stage based on the identified bottlenecks in the stages of other methods using deep learning [26 – 28] or reinforcement learning [29 – 32].
3. Substantiate and prove the advantage of the new method in comparison with the used ones. 11
Conclusions 1. The main disadvantages of the existing methods for placing microcircuit elements are high time costs, especially when placing a large number of elements, as well as low flexibility in solving problems with varying degrees of complexity, which indicates the need to develop a new, more efficient solution.
2. Based on the analysis of the main approaches to solving the problem of placing microcircuit elements during design and due to the lack of worthy domestic analogues of such algorithms, as well as the high cost of foreign software, which does not always fully correspond to the design routes of domestic LSIs, the need to create our own innovative methodology to solve the problem was identified.
3. The goals and objectives for the subsequent research aimed at improving the methods of placing and tracing elements on the microcircuit substrate and creating a new technique using AI - reinforcement learning - are formulated. 26. Brenton Smith, Rasit Abay, Joshua Abbey, Sudantha Balage, Melrose Brown, Russell Boyce Propulsionless planar phasing of multiple satellites usingdeep reinforcement learning // Advances in Space Research. - 2020. – 16 p. 27. Notsu A., Yasuda K., Ubukata S. Online state space generation by a growing selforganizing map and differential learning for reinforcement learning // AppliedSoftComputingJournal. - 2020. - 9 p. 28. Javier García, Rubén Majadas, Fernando Fernández Learning adversarial attack policies through multi-objective reinforcement learning // Engineering Applications of Artificial Intelligence. - 2020. - №96. - 11 p. 29. Madhu S. Advani, Andrew M. Saxe, Haim Sompolinsky High-dimensional dynamics of generalization error in neural networks // NeuralNetworks. - 2020. - №132. - P. 428-446. 30. Humphrey Adun, Ifeoluwa Wole-Osho, Eric C. Okonkwo, Olusola Bamisile, Mustafa Dagbasi, Serkan Abbasoglu A neural network-based predictive model for the thermal conductivity of hybrid nanofluids // International Communications in Heat and Mass Transfer. - 2020. - №119. - 14 p. 31. Rok Pahič, Barry Ridge, Andrej Gams, Jun Morimoto, Aleš Ude Trainingofdeepneuralnetworksforthegenerationofdynamicmovementprimitives // NeuralNetworks. - 2020. - №127. - P. 121-131. 32. Bister T., Erdmann M., Glombitza J., Langner N., Schulte J., Wirtz M. Identification of Patterns in Cosmic-Ray Arrival Directions usingDynamic Graph Convolutional Neural Networks // Astroparticle Physics. Journal Pre-proof. - 2020. – 17 p.