Research On The Floorplanning Algorithms In The Non-Manhattan Architecture

In the past years, non-Manhattan architecture has been paid great attentions in academic and industrial communities due to its great advantages such as reduction of the wirelength, improvement of the throughput and the chip performance. But few research works have been done on the floorplanning algorithms in the non-Manhattan architecture, which limits the full utilization of the advantages of non-Manhattan architecture. Aiming to solve these problems, three major works are done in this paper.Firstly, an extended sequence pair (ESP) representation for Hexagon/Triangle Placement (HTP) is proposed. A novel efficient HTP packing algorithm, called HTP-ESP, is presented based on the ESP representation. Experimental results show that the best results ever reported in the literature are obtained, and the runtime is competitive. In addition, two triangular coordinate systems suitable for the Y architecture are first presented.Secondly, we present an accurate and efficient wirelength estimation model called APWL-Y appropriate for the Y architecture. APWL-Y has linear time complexity. The average error of APWL-Y is 4.41% for 1.57 million nets from industrial circuits. Due to its high efficiency and good accuracy, APWL-Y is especially suitable to be used as wirelength estimator in a HTP floorplanner and placer. Moreover, we develop an efficient HTP algorithm with wirelength optimization driven by APWL-Y estimator. Compared to the HTP placer with only area optimization, our placer can reduce the wirelength by 54.3% with a small area overhead of 9.07% on average. In addition, we explore the half-perimeter wirelength estimation model in the Y architecture,and present the efficient method to compute the wirelength estimation. To the best of our knowledge, this paper is the first to present the HTP floorplanning/placement algorithm with interconnects optimization.Finally, we formulate the congestion estimation in the X architecture based on the liquid routing technique. Based on the probabilistic analysis of the routing demand, we present the first congestion estimation model in the X architecture considering liquid routing technique. An existing dynamic resource assignment (DRA) method is adopted in our model in order to obtain accurate congestion estimation. Experiments show that the congestion estimated by our model correlates well with post-routing congestion in the X architecture based on the liquid routing technique. The good accuracy and high efficiency shown by the experimental results make our model an ideal congestion predication tool to be used in a placer and floorplanner.