home   contact   中文   cas
About Us Research People International Cooperation News Education & Training Societies & Publications Papers Resources Links
Location: Home > News > Events
Optimization and Breakthrough of IECAS Large-scale FPGA Placement Algorithm, at the 13th International Conference on Field-Programmable Technology (ICFPT)
Update time: 2015-04-07
Text Size: A A A


 The 13th International Conference on Field-Programmable Technology (ICFPT) was held from 10 to 12 December, 2014 in Shanghai. This is one of the world’s largest international conferences for the fields of programmable technology, reconfigurable devices, and computational systems. The thesis “Size Aware Placement for Island Style FPGAs”, presented by the team of programmable chips and system research laboratory led by Yang Haigang, was included as an oral report at the ICFPT, and Huang Junying (a doctoral candidate and one of the thesis’s writers) participated in the conference. The ICFPT (2014) received a total of 121 contributions from 23 countries, among which, through selection of the technical program committee of the ICFPT, 23 contributions were included as oral reports (with an inclusion rate of 19%) and 24 as poster reports.

The ICFPT 2014 was held over a period of three days, and its topic reports originated from well-known companies and academic institutions related to programmable technology, including Synopsys, Microsoft and UCLA. Speech reports covered seven topics, with a total of 34 discussion sessions, such as programmable chip software tools and design productivity, financial application, programmable chip structure and real-time systems, digital circuits, hardware security, application and devices, along with special sessions for industrial circles. For programmable chip software tools and design productivity, there were three topics regarding research in high-level comprehensive fields, and two speech reports on research associated with FPGA placement algorithm. With an in-depth application of FPGA in the financial field, the ICFPT 2014 listed financial application as a single discussion session, including four speech reports. For programmable chip structure and real-time systems, there were four reports related to the reconfigurable processing units of coarse particle size, structure synthesis, storage access of heterogeneous systems, and FPGA soft-core processors. In addition, the speech reports on digital circuits discussed floating-point division of FPGA, effective FPGA achievement of digital parallel arithmetic operators, effective FPGA achievement of QR resolution, floating-point adders and multipliers of optimization areas, and floating-point matrix processors based on FPGA.

With the increasing integration level and complexity of FPGA chips, developing rapid and effective FPGA computer-aided design (CAD) algorithm has become a hot area of research. In the CAD compilation flow of FPGA, placement and routing are very important, because not only do they occupy most of the compilation time, they also directly affect the working frequency of the circuit. The traditional methods of improving the quality and runtime of FPGA placement and routing can be divided into two types, namely methods based on software and hardware. The methods based on software aim to improve the aspects of simulated annealing, such as optimized initial placement, directional movement replacing random movement, effective annealing table and multilevel strategy; the FPGA routing algorithm is based on the iterative mechanism, such as negotiatory crowd strategy, improved PathFinder routing algorithm, and timing-constrain routing algorithm. The methods based on hardware require more hardware to achieve the exchange of logical block and signal routing. However, the above studies did not fully consider the increasing chip size when discussing FPGA placement and routing.

This paper first explores the influences of FPGA size on the quality and runtime of placement and routing. The experimental results show that adopting small-size FPGA chips to create circuits may achieve superior performance and shorter times of placement and routing. When the area of chips expands by 100 times, there are increases of 103% in line length, 13% in the time delay of critical path after routing, 285% in the runtime of placement, and 15 times in the routing runtime.

To solve the performance degradation and long runtime resulting from the use of scale FPGA chips to achieve circuit, this paper proposes the Min-Size placement algorithm, which binds the logical block and IO in an array area. The IO is bound in the lower left of this array area, while the logical block is in the center of this area, as shown in Fig. 2. Furthermore, in order to reduce the runtime of placement and routing, the Min-Size algorithm builds only the time-delay array and routing resource graphs corresponding to the array area.

                Fig. 1 Diagram of traditional VPR placement algorithm

    Fig. 2 Diagram of Min-Size placement algorithm


To assess the Min-Size placement algorithm, this paper uses the experimental method to compare with VPR (the placement and routing tool widely studied by academic circles). As shown in Fig. 3, when the FPGA chip size increases by 10 times, the placement runtime, time of building routing resource graph, and time of calculating time-delay array in the Min-Size algorithm respectively expand by 3 times, 7.9 times and 106 times, compared to VPR; the routing runtime, time of building routing resource graph, and time of establishing signal routing respectively accelerate by 4 times, 7.7 times and 1.5 times; and the line length after routing and time delay of critical path respectively reduce by 41% and 5%. Meanwhile, research shows that the times for placement and routing of the Min-Size algorithm are merely associated with the applied circuit scale, without influence from chip size, thus when the FPGA chip size increases, the time will be enhanced significantly. (Room 11, Yin Tao)

     Fig. 3 Comparison of runtime and performance between Min-Size and VPR


<< >>
Copyright © 2002 - 2009 Institute Of Electronics Chinese Academy Of Scences Email: iecas@mail.ie.ac.cn