Competition question 3: Introduction to FPGA process mapping algorithm and optimization
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 SIG2
Competition title Chair: Luo Guojie
1. Competition background
With the increasing complexity of chip design and the continuous development of advanced technology, as shown in Figure 1, FPGA (Field Programmable Gate Array) is increasingly used in chip prototype verification and embedded systems. FPGA process mapping is an essential process for mapping logic circuits to programmable logic lookup tables (LUTs), which is crucial to the performance, power consumption, and area (PPA) of FPGA designs. Figure 2 is the basic structure of FPGA.
However, as design sizes increase and performance requirements increase, traditional process mapping algorithms face challenges. These algorithms may have shortcomings in dealing with large search spaces, optimization of timing constraints, improvement of resource utilization, and reduction of power consumption. In order to improve the performance and resource utilization of FPGA design, it is necessary to optimize the FPGA process mapping algorithm.
2. Description of competition questions
2.1 Description
Figure 3 shows an overview of a traditional FPGA process mapping algorithm. The main process is to enumerate CUT groups for each node of the original circuit, then sort the CUT groups of each node by characteristics such as area and depth, and then select the optimal CUT on each node to achieve coverage of the entire circuit area. From the perspective of the process of the traditional algorithm, there are still many areas that can be further improved and optimized.
As shown in Figure 4, this competition question focuses on the design of process mapping algorithm based on intelligent CUT selection. The algorithm will utilize intelligent screening and priority cutting techniques to reduce unnecessary search space and improve the efficiency of process mapping. By analyzing the structure and characteristics of the logic circuit, the algorithm can intelligently select the optimal cut set (Cut Set) as a candidate mapping target. At the same time, the algorithm will also optimize the selection order of cut sets to further reduce the search space and improve the mapping effect.
The goal of this competition is to design an efficient intelligent screening-first-cut process mapping algorithm that can provide excellent PPA performance in large-scale and complex FPGA designs. The algorithm needs to consider multiple factors, such as the size of the logic circuit, timing requirements, resource constraints, and power consumption constraints. The design of the algorithm will make full use of intelligent screening and priority cutting technology, combined with advanced optimization methods, to achieve efficient process mapping and optimization.
2.2 Competition case
The input file of each case is a combinational logic circuit in AIG (And-Inverter Graph) format. Each basic gate in the AIG circuit is an AND gate or a NOT gate, as shown in Figure 5. The AND gate and NOT gate are logically complete groups that can represent all other basic gate units.
A typical input file is shown in Figure 5 (this competition question is only for combinational logic netlists, so the third item L is always 0):
2.3 Output requirements
The output file is a netlist composed of LUTs. A K-input LUT is essentially a single-output RAM with a K-bit address, which can implement any K-input Boolean logic by storing a truth table.
A typical output file is shown in Figure 7, where o0 = i0&i1&i2&i3&i4&i5; o1 = i0|i2|i4.
2.4 Competition environment
(1) Operating environment
Operating system: linux system;
Hardware environment: 64-bit x86 CPU, 128GB running memory, 1TB hard drive, NVIDIA-GPU;
Software environment: gcc7.5.0, g++7.5.0, glibc2.27, python3.7, cuda-driver.
(2) Reference tools
As shown in Figure 8, iMAP supports reading and writing of “.aig” files and writing of FPGA netlists. For participating teams, they only need to pay attention to the algorithm of the FPGA process mapping link.
3. Scoring criteria
(1) Necessary requirements: Pass the equivalence check. Ensure that the output FPGA netlist is logically equivalent to the original input AIG, otherwise this question will be scored 0 points.
(2) Weighted score: cost=50%*runtime+30%*delay + 20%*area. The lower the cost, the better the result quality, and the higher the score of the corresponding case.
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:
• Functional description
• Overall design framework
• Detailed design of functional modules
• Advantages and challenges of the solution
• Test results and data analysis
(2) The source code of the work must contain the following items:
• source code
• Compiled code binaries
• 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 3:https://atomgit.com/opendacs/competition-t3
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 Beijing Open Source Chip Research Institute, Shanghai Anlu Information Technology Co., Ltd., Pengcheng Laboratory, Peking University and other related units.
6. References
[1] S. Chatterjee, A. Mishchenko, R. Brayton, X. Wang and T. Kam, "Reducing structural bias in technology mapping", IEEE TCAD
2006.
[2] D. Chen and J. Cong, "DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs", ICCAD 2004.
[3] A. Mishchenko; S. Cho; S. Chatterjee; R. Brayton. Combinational and sequential mapping with priority cuts.”, ICCAD 2007.
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/
(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)