Abstract
Content
- Introduction
- 1. Actuality of theme
- 2. Aims and research tasks, planned results
- 3. Developming and research the iterative methods of composition
- 3.1. Raising of problem
- 3.2. Research of dignities and lacks of iteration algorithms on an two examples : the iterative algorithm of 4ur rulers and a modified algorithm.
- Conclusions
- List of sources
Introduction
Composition - one of obligatory procedures that is executed at the designer planning. In the process of composition electric a chart is broken up on the modules, modules on cells, et cetera. That as a result results in the receipt of presentation of electric chart such by character that is suitable to direct realization on the real components [20].
For the construction of formal mathematical model of layout tasks it comfortably to use the theory of the graphs. Thus electric a chart is interpreted by nondirectional multigraph in that a top is put in accordance every structural element(to the module) multigraph, and to electric connections of chart are its ribs. Then the task of composition is formulated as follows: the multigraph is set. It is required to "cut" him on separate pieces so that a number of ribs connecting these pieces was minimum. By main criteria for such breaking up are: a minimum of number of appearing sites, a minimum of number of межузловых connections or external conclusions on sites.
Known layout algorithms can be conditionally broken up on five groups: algorithms, using methods integer programming, successive algorithms, iteration algorithms, mixed algorithms, genetic algorithms.
Iteration algorithms serve for the improvement of some initial variant of composition in accordance with the accepted criterion. At the use of iteration algorithms at first count of chart break up on the certain number of parts by arbitrary character. For example, with a help successive algorithms.
Then on some rules transposition of tops is made from one part of count in other with an aim minimizations of number of external ribs.
1. Actuality of theme.
In connection with by a necessity to maintain the level of competition at the market of electronics producers are forced constantly to perfect an element base and to use microcircuits with the high degree of integration, that allows sharply to decrease the common amount of electronic components, and, and prime price prepared apparatus. Increase of integration of microcircuits induces to the search of new designer decisions in their composition.
Development microelectronic components constantly goes in the direction of increase to integration, productivity and functionality. This process is characterized by the increase of closeness of active elements on a crystal approximately on 75% in a year, and it, in turn, causes a necessity for the increase of amount of their conclusions on a corps on 40% in a year. Stipulated this, firstly, constantly growing demand on the new methods of composition, and secondly, increase of closeness of connections on PCB.
Master's degree work is sanctified to research of existent iteration methods of composition, in I will make an effort it work out the own iteration method of composition, partly getting rid from defects already known.
2. Aims and research tasks, planned results
During research of iteration algorithms it is planned to execute next tasks:
- To investigate defects and advantages of existent iteration methods
- To work out the structure of subsystem of realization of layout algorithms
- To work out the programs of a few existent iteration methods and own method.
During development planned:
- To find the effective method of acceleration of calculation of composition on the basis of iteration method
- To confirm theoretical letups by means of comparison of results and time of work of the created model programs.
- To create an user interface for work with the program
3. Development and research of iteration methods of composition.
3.1. Raising of problem
Composition - one of basic procedures that is executed at a designer planning РЕА [20]. It is a transition process from an electric chart to to structural distribution(to breaking up) of all elements on groups, in accordance with the construction of different levels, id est process of transformation behavioral description of apparatus in structural one.
The task of composition is scission of large chart, it can that be structural, functional, logical, electric fundamental, to pieces.
In successive algorithms at first the first top of count gets out and successive tacking to it other tops from a number undistributed (on condition of satisfaction to the set criteria) the first piece of count is formed. Then the second piece of count takes et cetera to the complete scission.
Iteration the algorithms of scission are used for the improvement of the initial composition got as a result of implementation of successive algorithms. In the count cut on subcolumns, pair transposition of elements of different subcounts is conducted with verification at every step increase of number of ribs that connect its pieces. Aim of iterations it is minimization of number of connecting ribs.
In given
algorithm it is necessary to find the pair of tops
Thus, matrix of Q
broken up on 2 submatrices
This algorithm easily enough to program,
but he has a substantial defect - in every loop it is necessary again
to expect
3.2. Research of dignities and defects an iteration algorithms on an example two: iteration algorithm of 4х governed and modified algorithm.
Iteration algorithm of 4х
rules it is far difficult to program,
what previous, he requires large
memory in the process of work, but has a substantial plus - in every loop
it is necessary to expect
In case
modified algorithm the matrix of Q at first is broken up on submatrices
We will mark that
at transposition of tops
Testing of algorithms was conducted by the hypergraph generated by chance with the amount of ribs and tops from 10 to 100. Thus the hypergraphs were "broken" up on 2 - 10, 15, 20, 30, 40 and 50 parts with the even amount of tops in each. Results of researches of dependence of time of calculation a few from algorithms from the size of matrix resulted in a table 1.
Table 1 it is Dependence of time of calculation of algorithms on the size of matrix of Q
|
|
Power of tops X |
Power ribs of Е |
Number of knots |
Time of calculation,sec. |
|
|
Method 1 |
Method 2 |
||||
|
1 |
20 |
20 |
2 |
0,165 |
0,055 |
|
2 |
40 |
40 |
2 |
0,934 |
0,22 |
|
3 |
80 |
80 |
2 |
4,286 |
0,495 |
|
4 |
100 |
100 |
2 |
10,165 |
0,989 |
|
5 |
100 |
100 |
3 |
48,297 |
5,275 |
|
6 |
100 |
100 |
4 |
51,978 |
5,934 |
|
7 |
100 |
100 |
5 |
91,319 |
12,365 |
|
8 |
100 |
100 |
10 |
110,275 |
20,275 |
|
9 |
100 |
100 |
20 |
39,725 |
8,846 |
|
10 |
100 |
100 |
50 |
16,648 |
4,066 |
On results the researches driven to the table. 1 it is possible to do conclusion, that fast-acting of algorithm 1 in relation to an algorithm 2 not linear and depends on many factors. A histogram over of speed of calculation is brought on pic.1.
Pic.1. Histogram of speed of calculations of algorithms that is investigated.
Chart of dependence of time of calculation column from the amount of sites in a chart at breaking up on 7 subcharts resulted on pic.2.
Pic.2. Chart of dependence of time of рассчета from the amount of sites of entrance count for two examined algorithms.
Amount of shots of animation : 7
Time of вdelay:2sec on every shot last - 4 secs. After 2 cut it maybe to estimate the scale of chart and her change. Last shot with text, a delay is higher therefore
Conclusions
A Hypercount model is the most comfortable form of presentation of electric charts in memory of computer. By means of it systems the offered layout algorithm was investigational.
On results research appeared, that the offered algorithm allows to arrange charts in 2-20 times quicker (what greater amount of tops in a column, the greater coefficient of efficiency of the offered algorithm relatively standard) what standard iteration algorithm of arrangement. And this on charts that contain to 100 sites. On the real charts, number of sites in that can arrive at hundreds of thousands or even millions, this index can considerably increase. Offered algorithm not requires large memory in the process of work what standard, and also does not yield effectiveness and reliability.
List of sources
- Dauber E., in Graph theory, ed. Harary ,Wesley A., 1969. — 172 p.
- Hendrickson B., Kolda T.G., "Graph partitioning models for parallel computing", Parallel Computing, 2000. — 16 p.
- Catalyurek, U.V.; Aykanat C., "Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", 1999. — 673 p.
- Hendrickson. "A multilevel algorithm for partitioning graphs", 1995. — 14 p.
- Miranda E.,"Composing with Computers,Algorithmic composition, Iterative systems", — 34 p.
- Sen Su, "Iterative selection algorithm for service composition in distributed environments", 2008. — 1841 p.
- Yin E., Osher S., "Iterative algorithms for minimization with applications to compressed sensing", — 26 p.
- Karypis G., "Multilevel hypergraph partitioning: applications in VLSI domain", 1999. — 69 p.
- Mohan K., "Iterative Reweighted Algorithms for Matrix Rank Minimization", — 34 p.
- Feldstein A., "A study of Ostrowski efficiency for composite iteration algorithms", 1969. — 147 p.
- Carrillo E., "Iterative algorithms for compressed sensing with partially known support", 2010. — 4 p.
- Bergmann S., "Iterative signature algorithm for the analysis of large-scale gene expression data", 2003. — 18 p.
- Goldberg, "Genetic Algorithms", 1989. — 412 p.
- Muehlenbein H., "Marginal Distributions in Evolutionary Algorithms", 1999. — 6 p.
- Rodriguez, "Schemata, Distributions and Graphical Models in Evolutionary Optimization, submitted for publication", 1999. — 34 p.
- Schwarz, "Genetic algorithm for partitioning circuits", 1998. — 126 p.
- Moon B.B., "Genetic Algorithm and Graph Partitioning", 1996. — 841 p.
- Croix V, "Graph partitioning using learning automata", 1996 — 195 p.
- Schwarz, "Hypergraph Partitioning Based on the Simple and Advanced Genetic Algorithm BMDA", 1999. — 130 p.
- Курейчик В.М., Математическое обеспечение конструкторского и технологического проектирования с применением САПР [Текст] / В. М. Курейчик. – М.: Радио и связь, 1990. – 352 c.
- Лебедев Б.К., Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография / Б. К. Лебедев. – Таганрог: изд-во ТРТУ, 2000. – 192 с.
- Алексеев О.В., Автоматизация проектирования радиоэлектронных средств: Учеб. пособие для радиотехн. спец. вузов [Текст] / Под ред. О.В. Алексеева. — М., 2000. — 479 с.
- Мироненко И.Г., Автоматизированное проектирование узлов и блоков РЭС средствами современных САПР: Учеб. пособие вузов / Под ред. И.Г. Мироненко. — М., 2002. — 391 с.
- Саломатин В.А., Итерационный алгоритм распределения конструктивных элементов при задании электрической схемы в виде гиперграфа [Текст] / В.А.Саломатин, В.Н.Струнилин // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика і обчислювальна техніка» (ІКОТ-2008). Випуск 9 (132). — Донецьк: ДоНТУ. — 2008. — 316 с.
- Белой О.И., Струнилин В.Н. Модифікація ітераційного алгоритму компонування на базі гіперграфової моделі електричної схеми. Матерiали мiжнародної науково-технiчної конференцiї студентiв, аспiрантiв та молодих вчених. — Донецьк, ДонНТУ — 2012