Layout Algorithm Based On Optimization Of Spatial Characteristics

As development of semiconductor process technology, IC designers can integrate more and more complex circuit functions into a single silicon wafer, and ultimately the SoC (System on Chip) was developed in the 20th century. SoC represents the development of integrated circuits. However, as the number of IP core of SoC increased to more than thousands, bus-based SoC communication technology faces enormous challenges in performance, power consumption, delay, and reliability. In order to solve problems complex SoC faced, in 2001, some research institutions refer to the traditional network and propose a integrated method of complex SoC that focus on communication. It is NoC (Network on Chip).My research focuses on following aspects, first of all some technology was presented,such as the current routing algorithm, switching technology, the frame transmission technology, network topology, mapping and layout. Secondly, a mapping algorithms based on greedy was proposed in the paper. Several common data structures were compared in the paper.such as O-tree, B* tree, queue structure, Map structure. With the type of application module constantly increasing, O-tree and B* tree structure can't express the irregular application module and non-unicom application module. So the algorithm uses a more flexible queue structure to express application module. when the queue structure was used, the time complexity of moving the module is O (1) in the algorithm, rotating the module is O (n), Calculating the quality of the layout is O (a3). If the Map structure were used for assisting my algorithm, the time complexity of Calculating the quality of the layout reduces to O (a2).In addition, some new techniques were introduced to improve efficiency of this algorithm, such as:Marker bit method, dynamical selection and weight matrix, Initialize the layout. In order to solving overlapping and connection problems,Marker bit method is proposed in this paper to merge and separate different modules. Through the dynamical selection, Greedy has an ability of global selection which avoid to get local solution. Initial layout optimization and weight matrix make Greedy more efficient. From the experiments and comparison with Simulated Annealing algorithm, the running time reduce about 70%,the quality of solution increases about 7%.on the other hand, through tracking those algorithm,improved Greedy algorithm shows better stability and accuracy.