2023 openDACS Open EDA and Chip Design Competition-Topic 2

# Competition question 2: Incremental timing optimization algorithm

Sponsor: Ministry of Industry and Information Technology, Jiangsu Provincial People's Government, Hunan Provincial People's Government

Organizer: Open Atom Open Source Foundation, CCTV Network, Jiangsu Provincial Department of Industry and Information Technology, Wuxi Municipal People's Government, Jiangsu Software Industry Talent Development Foundation, Suzhou Industrial Park, Wuxi High-tech Zone, etc.

Co-organizer: openDACS Working Committee, Institute of Computing Technology, Chinese Academy of Sciences, Institute of Microelectronics, Chinese Academy of Sciences, Peking University, Fudan University, Tsinghua University, Beijing Open Source Chip Research Institute, Shenzhen Micro-Nano Research Institute, Shenzhen Huaqiu Electronics Co., Ltd.

This competition focuses on: The areas of digital design, analog design, chip manufacturing, chip packaging, processor design automation, and generative chip design in the integrated circuit industry are of great significance to promoting high-quality development of the industry.

This competition includes: There are a total of 10 questions in five directions.

Question issuing unit: Pengcheng Laboratory, openDACS Working Committee SIG3

Competition title Chair: Li Xingquan

Speakers: Huang Zhipeng

# 1. Competition background

Chips play a key role in electronic devices such as mobile phones, computers, and automobiles. The timing performance of the chip controls the data transmission speed and instruction execution time, ensuring the efficient operation of the device and the smooth user experience. This competition question is based on the performance requirements of chip design and focuses on incrementally reducing chip latency.

Timing optimization has always been an important issue in chip design. With the continuous improvement of chip integration, timing issues have become more and more complex and critical. The core of the timing optimization problem is how to reduce the chip delay to ensure the normal operation of the chip. Common techniques for timing optimization without changing the netlist include gate sizing and cell movement. Tradeoff the load capacitance of the unit's upstream and downstream to achieve latency reduction.

Gate sizing techniques can reduce delays along circuit paths by adjusting the size of logic gates. Specifically, increasing the gate size can drive larger loads, thereby reducing downstream latency. However, the increased gate size will cause the load on its driving unit to increase, thereby increasing the upstream delay; cell movement technology can improve circuit performance by rearranging the logic cells in the circuit. By placing related units close to each other, circuit path lengths can be reduced and latency reduced.

This competition question focuses on the cell distribution and routing after layout, and uses techniques such as gate size adjustment and cell movement to perform incremental timing optimization without changing the netlist. The participating teams are required to select appropriate algorithms and use parallel and other performance optimization methods as much as possible to provide high-performance timing optimization algorithms.

# 2. Description of competition questions

# 2.1 Description

In this competition, in order to simplify the problem, the chip area is divided into grids, and the coordinates and overlap of the cells in the grid are ignored. It is only necessary that the total area of ​​the cells in the grid does not exceed the specified maximum accommodation area. Similarly, when using a grid as a GCell, only two-dimensional wiring needs to be considered to ensure that the wire network is connected and that the wiring in each GCell does not exceed the specified wiring capacity. As shown in Figure 1.

The participating teams need to combine their understanding of timing optimization methods to design a C++ program. The program should be able to construct an appropriate data structure based on the analyzed data provided by the co-creator of the competition question, and complete the optimization of the layout through the timing optimization algorithm. The program output is the optimized placement and routing results. Figure 2 gives a simple example.

With the help of open source projects, the competition co-creators provide reference processes and file analysis, as shown in Figure 3 (the yellow part needs to be filled in and designed by the participating teams). The participating teams need to complete the following points:

(1) Construct an appropriate data structure based on the parsed data provided by the co-constructor of the competition question, taking into account both efficient storage and algorithm application.

(2) For the unit layout, it is required to optimize without changing the netlist. The gate size adjustment will provide a standard unit library. The unit library provides n sizes for the logic units of each function, that is, there are n different library units that implement the same combinational logic function. In order to ensure that the optimized netlist maintains its original logic functions, each unit can only be replaced with a library unit with the same combinational logic function.

(3) If the wiring needs to be updated after the unit is moved, the wiring demand must be less than the wiring capacity. The wiring demand is calculated as the number of complete tracks passing through the GCell. The wiring capacity is calculated as when a line completely passes through the GCell, a complete track will be used. If it does not pass through completely, it is simply calculated as 0.5 tracks. The competition co-creator will provide samples for comparison.

(4) On the basis of meeting the constraints of increasing the area, perform timing optimization and output the legal placement and routing results after timing optimization.

(5) Use the timing evaluation tool of the co-constructor of the competition to obtain the evaluation results. According to the routing conditions output by the participating teams, according to the line length and unit RC, the timing evaluation tool uses the nonlinear delay model (NLDM) and the interconnection line Elmore to calculate the worst/total negative margin.

This competition question allows participating teams to use up to 8 threads for parallel acceleration based on the specific needs of the algorithm.

# 2.2 Competition Case

The co-constructor of the competition topic provides the participating teams with the competition case and procedures for verifying and optimizing the design. Below is a simple example of the provided file.

(1) Netlist: netlist (.v file)

(2) Initial layout: GCell unit location information (.def file)

The specific unit descriptions are as follows:

• Cell

The unit under the corresponding process contains information such as shape (such as width, height), category tag (required for Gate Sizing), etc.

Data (information) acquisition interface:

int get_width() const; // Get the unit width
int get_height() const; // Get the height of the unit
equivCellType get_equiv_cell_type() const; // Get the category of the unit

• Instance

The unit instance used in the design file corresponds to the specific Cell; the pin points required for the connection relationship (Net) are marked, and an interface for obtaining and updating the position is provided.

Data (information) acquisition interface

Cell get_cell() const; // Get the corresponding cell under the process
Cellint get_coordi_x() const; // Get the abscissa of the lower left corner of Instance
int get_coordi_y() const; // Get the ordinate of the lower left corner of Instance
void update_location(Point);

global interface

vector `<Instance>` get_inst_list() const; // Get the collection of all units in the design
vector `<Net>` get_net_list() const; // Get the collection of all wire nets in the design
vector `<Cell>` obtain_equiv_cells(Cell* cur_cell); // Enter the current Cell and obtain a Cell collection of the same type (for Gate Sizing)

(3) Initial winding

• GCell

GCell is a rectangular grid. The layout is divided into multiple grids through GCell. The GCell specifications of each layer are the same, and their definition is as follows:

GCELLGRID [axis] [start] DO [scale_num] STEP [interval]

Among them, "GCELLGRID" is the starting field defined by GCell; "[axis]" is the axis direction to be described, X and Y; "[start]" is the coordinate where the axis starts; "[scale_num]" is the number of coordinates on the axis; "[interval]" is the interval between coordinates.

An example in def is as follows:

GCELLGRID X 1200 DO 2 STEP 500
GCELLGRID X 0 DO 5 STEP 300
GCELLGRID Y 1050 DO 2 STEP 50
GCELLGRID Y 150 DO 4 STEP 300
GCELLGRID Y 0 DO 2 STEP 150

The above GCellGrid definition is as follows on the layout (Die):

• Guide file

Guide is the result of routing. Its unit is a complete GCell. Guide only needs to describe the routing layer.

Taking net0 as an example, the wiring results are as follows in the guide file:

net0(
300 150 1200 450 M1
900 150 1200 1050 M2
900 750 1200 1050 M1)

The size distribution of GCell in each layer is consistent. By analyzing the guide, the wiring results of net0 are as follows:

• Open source process library (.tlef file, .lef file, .lib file)
• sdc file (.sdc file) defines the clock that needs to be optimized for timing.

# 2.3 Output files

This competition question requires the participating team's program to output the optimized unit layout and wiring results after completing timing optimization. The format of the output file should be consistent with the format input in the competition case provided by the competition co-creator.

# 2.4 Environment

It is recommended that participating teams use a C++ version compatible with C++20 for their development environment and operating environment, and develop under a Linux system environment. Reference methods are given below:

(1) Download from Dockerhub and use the compilation tools and dependent libraries provided by the image to build the project.

(2) Manually install dependencies and compile.

# 3. Scoring criteria

All test cases in the competition are divided into three categories: large, medium and small test cases according to the size of the netlist. The competition questions are selected from these three types of test cases and some cases are provided to participating teams to evaluate the quality of the algorithm; the remaining cases are only used for scoring purposes and are not open to participating teams.

Each test case has an independent score and follows the same scoring criteria:

(1) On the basis of limiting the increased area, compare the improvement of the worst/total negative margin. The larger the value, the higher the ranking. Take the top 10 teams, 10 points for the first place, 9 points for the second place, and so on.

(2) The output layout results need to meet the legality requirements (unit area within GCell, no overflow of wiring between GCells), and run under the given running time and memory limits, otherwise no points will be awarded.

(3) After scoring each case in the scoring case set, the total score is the weighted sum of the scores of individual cases, where the weight coefficient of a single case is positively related to the size of the case. The team with a higher total score will be ranked higher.

# 4. Requirements for entries

# 4.1 Preliminary entries

Participating teams (1 to 3 members) submit the design document and source code of the competition question.

(1) The design document is required to be a PDF document. The technical implementation details should be written clearly in the document and the test results on the test cases should be provided, including the following points:

• Function description
• overall design framework
• Function module detailed design
• Advantages and challenges of the program
• Test results and data analysis

(2) The source code of the work must contain the following items:

• source code
• Compiled code binary file
• readme (basic description of the final submission algorithm, including operation mode, input format description, etc.)
• Dependent third-party libraries (if any, they need to be provided together to prevent differences in results due to different versions)

# 4.2 Final works

The participating teams will further improve their works on the basis of the preliminary works, such as improving the performance of key algorithms, optimizing the implementation of the code, enhancing the readability of the code, complying with the standardization of open source code, etc., and submit the final source code and design documents to participate in the finals.

# 4.3 Work submission channel

Before submitting their work, participating teams must send the team leader’s registered email address, user name, name, mobile phone number and other information on the official website of the competition to the staff of this competition (contact email: Johnhw_2019@qq.com, the subject of the email is named: "Team Name" warehouse application). The staff will create a private warehouse for the team on AtomGit and add the team leader as the warehouse administrator. After the participating teams complete their work, they can submit the relevant documents and source code of the work to the warehouse. The naming method for submitted works is: competition title + team name + title of work.

AtomGit URL for question 2:https://atomgit.com/opendacs/competition-t2open in new window

# 5. Incentive Program

(1) One winner of the preliminary competition will be awarded a bonus of RMB 50,000; two winners of the Open Source EDA Rookie Award will be awarded RMB 5,000; each will be awarded a certificate.

(2) The winner of the preliminary competition will enter the finals of the open source EDA and chip competitions, and will have a finals road show in April 2024, with a chance to win the "openDACS Open Source Star" and an additional bonus of 20,000 yuan.

(3) Provide all Awards teams with internship opportunities at the Institute of Computing Technology of the Chinese Academy of Sciences, the Open Source Chip Research Institute, Pengcheng Laboratory, Zhongke Jianxin (Beijing) Technology Co., Ltd. and other units.

# 6. References

[1] S. Held and J. Hu, “Gate sizing,” in Electronic Design Automation for IC Implementation, Circuit Design, and Process Technology, L. Lavagno, I. L. Markov, G. Martin, and L. K. Scheffer, Eds. Boca Raton, FL, USA: CRC Press, 2016, pp. 245–260.

[2] Papa, David A., et al. "RUMBLE: an incremental, timing-driven, physical-synthesis optimization algorithm." Proceedings of the 2008 international symposium on Physical design. 2008.

[3] Held, Stephan. "Gate sizing for large cell-based designs." 2009 Design, Automation & Test in Europe Conference & Exhibition. IEEE, 2009.

[4] Li, Zhuo, and Weiping Shi. "An O (mn) time algorithm for optimal buffer insertion of nets with m sinks." Proceedings of the 2006 Asia and South Pacific Design Automation Conference. 2006.

[5] Papa, David A., and Igor L. Markov. Multi-Objective Optimization in Physical Synthesis of Integrated Circuits. Vol. 166. Springer Science & Business Media, 2012.

[6] Zou P, Cai Z, Lin Z, et al. Incremental 3D Global Routing Considering Cell Movement and Complex Routing Constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.

# Appendix 1: General introduction to the 10 competition questions

This competition includes a total of 10 questions in five directions, as follows:

# Digital chip EDA direction:

Competition question 1: Function vector sequential circuit fault simulator

Competition question 2: Incremental timing optimization algorithm

Competition question 3: FPGA process mapping algorithm and optimization

# Analog chip EDA direction:

Competition question 4: Analog circuit optimization algorithm

Question 5: Automated design of operational amplifier

# Chip manufacturing EDA direction:

Competition question 6: Device model reference based on BSIM-CMG model

# Processor design automation EDA direction:

Question 7: ASIP’s hardened IP design based on OpenHarmony soft bus characteristics

Competition question 8: Silicon substrate interconnection design based on open source PDK

# Generative chip design direction:

Competition question 9: Pipeline CPU design based on the automatic chip generation framework AutoChip (ChipGPT 2.0)

Competition question 10: AutoChip (ChipGPT 2.0) chip creative design

# Appendix 2: Competition format/schedule

# 1. Competition process

• 2023.09 -2023.11 Publish each competition question on the official website of the competition, openDACS official account, and CCF Integrated Circuit Design Committee official account
• 2023.09.30 - 2024.2.28 Participating teams register for the competition, submit their works, and will be coached and improved by the question maker
• 2023.10.15 Q&A on the competition questions at the open source EDA special forum of CCFDAC2023 conference
• 2023.10.15 - 2023.12.30 Arrange lectures at designated units (Chinese Academy of Sciences, Peking University, Fudan, Tsinghua, Wuhan University of Technology, Shenzhen University of Technology, etc.); arrange 1-2 online lectures on electronic enthusiast websites
• 2024.03.31 The preliminary round review will select the champions and rookie awards of each topic, and the question maker will guide the champion team to improve.
• 2024.04.01 - 2024.04.15 Final works submission
• 2024.04 Final review, the ten competition champions were collected and selected to select 3 openDACS Open Source Star Awards
• 2024.06 (tentative) Open Atom Developer Conference, announces Awards list and offline awards

# 2. Competition consultation

Please join the participating teams in this competition's WeChat exchange group "openDACS Open Source EDA and Chip Competition", the WeChat group QR code:

If the WeChat group QR code expires, you can directly contact the person in charge of this competition on WeChat: WinPolestar to apply to join the communication group.

After the participating teams register and submit their works, they can send their registration information and entries to
Johnhw_2019@qq.com.

# 3. Instructions for participating teams

The requirements for the official start of this competition are: the number of registered teams reaches at least 10, and the number of submitted works reaches at least 5. If the number of registered teams or submitted works is not met, this competition may be postponed or suspended. At that time, the co-organizers of this competition (Institute of Computing Technology, Chinese Academy of Sciences, Institute of Microelectronics, Chinese Academy of Sciences, Peking University, Fudan University, Tsinghua University, Beijing Open Source Chip Research Institute, Shenzhen Micro-Nano Research Institute, Shenzhen Huaqiu Electronics Co., Ltd.) will send you a written notice.

# Appendix 3: Work submission requirements

# 1. Content requirements for entries

For details on the specific work content requirements for each competition topic, please refer to the description of each competition topic in the "Competition Questions" column.

# 2. Specification requirements for entries

(1) Entries must meet the requirements and themes of this competition, and the title of the work should reflect the main features of the work.

(2) Entries must be original works and must not infringe on anyone else’s Patents rights, Books rights, trademark rights and other intellectual property rights, and must not violate relevant national laws and regulations.

(3) The work must be separable from the original development environment, have a demonstrable running environment, and be able to compile/run on the test account provided by the organizing committee or provide a compilation/run environment by yourself.

(4) The work is allowed to use other people's open source code, but the source and dependencies on other open source codes must be noted on the basis of maintaining the original copyright. When submitting a work, the role and proportion of other open source codes in the work must be clearly stated in the analysis and design document.

(5) The work should operate correctly and achieve expected results. The work should be consistent with the functions described in the design document. If it fails to achieve all the functions described in the design document, the unimplemented functions and their proportion and importance should be noted.

# 3. Submission requirements for entries

(1) Before submitting the work, the participating team must send the team leader’s registered email address, user name, name, mobile phone number and other information on the official website of the competition to the staff of this competition (contact email: Johnhw_2019@qq.com, the email subject is named: "Team Name" Warehouse Application), the staff will create a private warehouse for the team on AtomGit, and add the team leader as the warehouse administrator. After the participating teams complete their work, they can submit the relevant documents and source code of the work to the warehouse. The naming method for submitted works is: competition title + team name + title of work. AtomGit URL:https://atomgit.com/open in new window

(2) Participating teams can continue to promote iterative upgrades of their works without changing the name and main functions of the work. The last work submitted in the corresponding competition schedule will be the entry.

(3) During the review period, participating teams must submit additional materials related to their works in accordance with the requirements of the organizing committee.

(4) In principle, all submitted entries and related materials will not be returned.

# Appendix 4: Review rules and review expert panel

# 1. Evaluation rules

(1) For detailed evaluation rules for each competition question, please refer to the "Competition Questions" column and the acceptance criteria for each competition question.

(2) Complete the document description of the entry, the technical path of the document is feasible, and it will be approved after being reviewed by the direction experts.

(3) The code function completes the indicator requirements, and submits standardized code and detailed documentation. Finally, the code is reviewed and merged into the corresponding warehouse.

(4) Obtain corresponding awards according to the acceptance criteria stated in each competition question.

# 2. Review Expert Group

Li Huawei (team leader, director of the openDACS Working Committee and head of SIG1, researcher at the Institute of Computing Technology, Chinese Academy of Sciences, deputy director of the National Key Laboratory of Processor Chips, responsible for competition question 1)

He Junhong (co-leader, co-director and executive director of the openDACS Working Committee, responsible for the organization and operation of this competition, and participating in the selection of questions 7-10)

Li Xingquan (Associate Researcher at Pengcheng Laboratory. Responsible for question 2)

Luo Guojie (Head of SIG2 of the openDACS Working Committee, Permanent Associate Professor of the School of Information Science and Technology, Peking University, and Executive Director of the Center for Energy-Efficient Computing and Applications. Responsible for question 3)

Yang Fan (Head of SIG3 of the openDACS Working Committee, professor and doctoral supervisor at the School of Microelectronics, Fudan University. Participated in the selection of competition question 2)

Xie Biwei (Head of SIG4 of the openDACS Working Committee, Assistant Researcher at the Institute of Computing Technology of the Chinese Academy of Sciences and Pengcheng Laboratory, participated in and was responsible for projects such as "One Core for Life" and open source EDA. Participated in the selection of competition questions 2\3)

Ye Zuochang (Head of SIG7 of the openDACS Working Committee, associate researcher at the School of Integrated Circuits, Tsinghua University, responsible for questions 4 and 5)

Li Zhiqiang (Head of SIG5 of the openDACS Working Committee, researcher at the Institute of Microelectronics, Chinese Academy of Sciences, head of the EDA Center, responsible for competition question 6)

Liu Yongxin (Assistant Dean of Shenzhen Institute of Micro-Nano Integrated Circuits and System Applications, responsible for question 7)

Wang Yujie (Zhijiang Laboratory, research expert, responsible for computing core design, interconnection system design, EDA design, etc. of chiplet and other discrete design methods, responsible for competition question 8)

Fan Jiaqi (Huajin Semiconductor, packaging design manager, responsible for 2.5D/3D integrated packaging, wafer-level fan-out packaging, three-dimensional heterogeneous integration and other packaging design and simulation technology research. Responsible for competition question 8)

Wang Ying (head of SIG8 of the openDACS Working Committee, researcher at the Institute of Computing Technology, Chinese Academy of Sciences, responsible for questions 9-10)

Huang Yu (Huawei semiconductor scientist, chief architect of Shenzhen HiSilicon EDA and director of the EDA laboratory. Participated in the selection of competition topics on 1/4/8)

Yang Fan (Vice President of R&D of Shenzhen Guowicin Technology Co., Ltd., participated in the selection of question 2)

Liu Yong (Head of Community Operations of the Electronic Enthusiast Platform under Shenzhen Huaqiu Electronics Co., Ltd., responsible for online lectures and participating in the selection of questions 7-10)