VLSI design using self organizing systems | |
| Author | Shrestha, Amarottam |
| Call Number | AIT Diss. no.CS-95-3 |
| Subject(s) | System design Integrated circuits--Very large scale integration |
| Note | A dissertation submitted in partial fulfillment of the requirements for the degree of Doctoral of Engineering |
| Publisher | Asian Institute of Technology |
| Abstract | The Self-Organization in the Artificial Neural Networks has shown to be effective in modelling a variety of problems. The self-organization process centers around the idea that a system representing network of neurons with an appropriately structured distribution of signals and interconnection weights can form, by self-organimtion, a topological map appropriate to the input signals. The idea has a wide range of significance both for solution of combinatorial optimization problems (usually NP-hard) and also for insight on parallel and distributed computing. The VLSI (Very Large Scale Integration) design is a complex process. Behavioral, structural and physical designs are three aspects of the design. Layout design (physical design) problems as a whole are invariably NP-hard. The designers usually resort to the heuristic methods. One such method is to break up the problem into sub-problems -- placement, global routing, topological compaction and detailed routing. Almost always, the sub-problems thus achieved are also NP-hard. In this research, we look into the placement problem, i.e. the placement of circuit components (cells) in the two dimensional plane, from a new angle. Utilizing the features of self- organizing Neural Networks, we develop a framework for the solution of the placement problem. An algorithm based on Self-Organizing Feature Maps is developed for the placement process. The interconnection information and the connection density, or, the net-list of the placement problem is used to construct Connectivity Matrix. Each column of the connectivity matrix constitute an input vector associated with one placement unit for the algorithm. The self- organimtion process maps these vectors onto the output neurons. It is found that similar vectors (i.e. densely connected placement tmits) are mapped to output neurons which are topological neighbours. The topological positions ofthe output neurons are, in physical terms, the placement of the input placement units. Usefulness ofthe algorithm is shown by solutions of the example problems with various number of cells for placement. Though the framework we developed is using massively parallel structure of processing units (neurons), the algorithm on the whole is essentially a serial one. We consider only one cell for placement at a time followed by the other cells in a sequential manner. Like in any other serial analytical algorithm, this algorithm also has a tendency to suffer from the problem size growth. One of the theoretically simple but practically not so simple method to overcome this situation is the use of“divide and conquer" technique. ln this particular problem, an ideal "divide and conquer" case is to divide a large problem into a number of smaller problems and place them separately as independent problems in parallel. This division is a difficult problem on itself as the divided sub-problems should be groups of cohesive cells within the sub-problem. More over these sub-problems should have as less coupling as possible between themselves. In the second part of the research, we concentrate on development of an algorithm for input space division (i.er division of large problem into smaller ones). The process of input space division must consider characteristics of all the cells to fulfill requirements on cohesiveness and coupling. An algorithm based on the Adaptive Resonance Theory (ARTI) is developed. The Adaptive Resonance Theory (ARTI) is a self-organizing neural network for classification or clustering applications. The ARTl’s capabilities: i) to store a number of dissimilar inputs patterns in its neurons, and, ii) to cluster incoming pattern to one of the stored patterns if the patterns under consideration are sufficiently similar to each other, are utilized to develop an algorithm for the input space division. This is made possible by devising an innovative way to transform the characteristic information of input cells into a string of binary numbers which could be used by the ARTI for similarity matching purposes. The strings of binary numbers thus achieved are used as input vectors to the ART network. Now, the problem of the input space division is reduced to classifying these inputs into number of classes using vigilance parameter and similarity criteria appropriately defined. Once all the inputs are classified into different classes, the input space division process is complete. The cells in each class correspond to a sub-group of cells in the placement problem. There are two modifications made in the standard ARTl algorithm for its adaptation to the placement problem nature. The modifications made are very essential and crucial for the satisfactory operation of the input space division process. The first one is the Similarity Criteria used for testing whether the incoming characteristic vector is Similar enough to the template characteristic vector already coded in the concerned neuron in the recognition layer. The modified similarity criteria takes care of the coupling effect between the different sub-groups, simultaneously maintaining the cohesiveness. The second modification is on the me/hod of updating of the Top-Down Weights. The standard ART] finally give the top-down weight as the logical-ANDing of all the characteristic vectors matched to that particular node. This is not favorable for the case of input space division in the cell placement problem. Therefore, we update the top-down weights only the first time an incoming characteristic vector is matched to an uncommitted node. The usefulness and validity of the algorithms are shown by results of the number of example problems of different sizes. The global placement results achieved with input space division are compared with the placement results of the same problems without input space division, and, the fomler process is found to be superior. |
| Year | 1995 |
| Type | Dissertation |
| School | School of Engineering and Technology (SET) |
| Department | Department of Information and Communications Technologies (DICT) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Sadananda, R. |
| Examination Committee(s) | Murai, S.;Battanov, D. N.;Abu-Mostafa, Yaser S. |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 1995 |