Update log: 2024/11/2 23:51 GMT-4: Update QA about placement row
2024 11/6 11:42 GMT+8: Update QA, update evaluator
2024 11/6 20:58 GMT+8: Update Evaluator (Runnable on mseda01) & QA session
2024 11/9 11:31 GMT+8: Update Report requirement
2024 11/10 8:03 GMT+8: Update QA for server loading & useful tools to monitor the server resource on Q5
2024 11/11 18:58 GMT+8: Update Evaluator (output precision)!
2024 11/12 15:38 GMT+8: Update Evaluator (check the startX of placementrow)
2024 11/15 18:38 GMT+8: Please implement make clean
in your Makefle
2024 11/16 16:26 GMT+8: Upload a hellish testcase.
2024 11/20 00:56 GMT+8 Should be the last announcement, no late submission is available. If your submit files have wrong folder structure, you should get 0 point for this lab ofc. Keep working!!
Table of Content
As mentioned earlier, many optimization techniques can result in cell overlap, leading to illegal placement. Therefore, a fast algorithm is needed to perform local legalization rather than full-chip legalization and determine whether the optimization is feasible at that moment. Consequently, a quick API for the legalizer is necessary so that the optimizer can frequently check whether the optimization is easy to legalize.
For example:
Given a legalized placement and a set of cells to be inserted into the placement, implement an efficient local legalizer that legalizes the cells in into one by one. The local legalizer should aim to:
Focus on designing a method that prioritizes local adjustments during the legalization process.
For example:
To avoid full-chip legalization using well-known algorithms like Tetris Legalization [Hill, Patent 2002] or Abacus Legalization [Spindler et al., ISPD’08], a special weighted cost function is implemented to evaluate the quality of your results.
Given a legalized placement and a set of cells to be inserted into the placement. where
Given a legalized placement P
and a set of cells C
to be inserted into the placement, implement an efficient local legalizer that legalizes the cells in C
into P
one by one. Specifically:
cell_i
from C
, it should be added to the placement P
.P
after adding cell_i
should maintain legality, i.e., P <= P + cell_i
.C
until all cells are legalized.The goal is to minimize disturbance to the existing placement and ensure efficient execution, especially for large sets of cells in C
.
Disclaimer: Most of the testcase will be modified from 2024 ICCAD Problem B. Thanks for (Synopsys, Inc) to release the benchmark.
In this section we will define each syntax for data input. Most of the syntaxes are the floating point numbers and we expect students to take care of the data range within DBL_MAX.
Weight factors of the cost metrixs: , values are given out as Alpha, Beta, respectively.
DieSize describes the dimension of the die, namely the placement area of the design.
Cell attribute and legalized coordinate. For fix cell, you are not allowed to move when you try to legalize the placement later.
Note that to simplify the problem, the siteWidth should always be 1 in this assignment. This means the minimum precision of the cell coordinates should be at least 1 unit in the placement.
Figure 4 in 2024 ICCAD Problem B. An example to illustrate what placing on-site means. We define on-site as cells with their bottom-left corner aligning to the site grid given from the PlacementRows from the design data input. The 4 green cells on the left part of the figure are placed on-site as their bottom-left corners are aligning with the site grids of the PlacementRows; the 5 red cells on the right side of the figure are not placed on-site as none of the cells have their bottom-left corner placed on the site grid.
Optimize Step Finally, here is the optimizer output, which aims to merge multiple flip-flops into multi-bit flip-flops. Students are expected to remove the list of flip-flops to be banked in the legalized placement , and add the new multi-bit flip-flop into the legalized placement without overlapping other cells, while also minimizing the given cost function.
Please note that the merged cell coordinates might not be legalized. Find a space to place them on the placement row without overlapping with other cells.
In conclusion, there are two files per testcase: the legalized placement information will be stored in the *.lg file, and the optimizer step will be stored in the *.opt file.
For each optimization step, please output the legalized cell for the given merged flip-flop (FF), as well as all the cells that were moved during the legalization of this merged FF.
Runtime limit is 30 minutes for each case in our server. The hidden cases will be in the same scale as public cases. We would like to introduce the runtime factor in this homework to encourage the ideas with faster turnaround-time.
Your program should be executed by:
After program finish, we expect a *_post.lg to show all info required for each optimized step.
For example:
Please write a quick report explaining how your algorithm works, including:
We expect your file can be executed after
Please submit your tar file to e3 by 11/15
Stackoverflow static linking: https://stackoverflow.com/questions/26103966/how-can-i-statically-link-standard-library-to-my-c-program
Sorry, the evaluator is still being tested. You're welcome to use the beta version, and you can report any bugs via Gmail. We'll fix them as soon as possible!
If you see the following pretty table, then you pass for this testcase!
(Just a bad output, don't compare your result with this…)
There will be 3 public test cases and 1 hidden test case. You can get at least 20% * 0.7 = 14% if you are able to produce a legal result. The remaining 6% will depend on the quality and runtime of your solution. Another 20% comes from the report. As an engineer, not only is coding important, but proper and concise documentation of the algorithm is also crucial. Please try to demonstrate to the TA how great your algorithm is.
Please note that for the public test cases, TA reserves right to change the testcase based on the feedback and difficulty! Please do check the version of your local testcase by:
In EDA-related projects, it is good practice to visualize your results. Some well-known methods for doing this include using Python libraries like matplotlib
or seaborn
, and tools such as gnuplot
. Visualizing your data helps in identifying trends, verifying correctness, and presenting your findings clearly. We might release a binary tool for plotting in the future, depending on available time…
Before Banking
After Banking
Some useful packages to plot efficiently:
All test case updates and new versions of the evaluator will be uploaded through GitHub. We will provide notifications and make announcements in the E3. Please pull the latest test cases and evaluator to evaluate your binary.
Github Link: https://github.com/coherent17/Optimizer-and-Legalizer-Co-optimization
Note that third-party placers or legalizers are not allowed in this project. You must implement the local legalizer yourself. However, data structures or algorithm-based packages are welcome. If you're unsure whether something is allowed, please contact the TA. Cheating or plagiarism will result in a score of 0 for this lab.
This is the placeholder to discuss with the students.
Q1: Attribute of placement row?
To simplfy the problem, we can make below assumption on placement row:
Q2: Attribute of the cell in *.lg file
The given cell in the lg file should gaurantee to be on site.
Q3: Evaluator is not runnable in the given server.(FATAL: kernel too old, Abort)
Solve this problem, please git pull to get the latest binary file of evaluator!
Q4: Are the new banked FFs fixed in the subsequent optimization steps?
No, they can be moved to make space for the new block! The cell with prefix FF_ can be moved, the cell with C_ can't be moved.
Q5: Server loading and paralyzing
Please try not to overuse server resources. Close the IDE window if you are not actively using it. For programs that continually allocate memory on the heap, please implement garbage collection to manage memory. We've received some queries about OS memory abortion errors. Apologies for any inconvenience, and please note that an LSF job scheduler is currently unavailable. We hope everyone can be considerate and avoid actions that could paralyze the server or continuously occupy resources.
Here is a script to help you install some useful tools for working more efficiently and monitoring server resource usage.
For those who keep occupying resources excessively, TAs have permission to terminate your job, apply a score penalty to your Lab3 grade, and report the issue to the professor.
Please note that you should send your requests or questions to both TAs; otherwise, the TAs will not reply. Additionally, the TAs will update all Q&A in the session above to ensure fairness to all students. We will try to answer your questions within one day. Please be patient. Thank you!