https://github.com/coloquinte/amaranth
Exact placement tool based on branch-and-bound
Science Score: 13.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
○DOI references
-
○Academic publication links
-
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (6.1%) to scientific vocabulary
Repository
Exact placement tool based on branch-and-bound
Basic Info
- Host: GitHub
- Owner: Coloquinte
- License: unlicense
- Language: C++
- Default Branch: master
- Size: 39.1 KB
Statistics
- Stars: 1
- Watchers: 2
- Forks: 0
- Open Issues: 0
- Releases: 0
Metadata Files
README.md
Amaranth
Amaranth is an algorithm to optimize 2D rectangle placement for electronic design. It is a branch-and-bound algorithm based on a minimum-cost-flow relaxation, intended to solve the leaf case for the Coriolis/Coloquinte placer.
Principle
The wirelength minimization problem can be expressed as the dual of a minimum-cost-flow problem, where new constraints are equivalent to added new edges to the graph. Amaranth solves the problem like a branch-and-bound ILP solver with dual simplex: at each node, it branches on the placement constraint between two rectangles (left/right/below/above) by adding an edge to the graph and updating the min-cost-flow solution.
Experiments
At the time, I compared it against several ILP formulations for standard cell placement. I used CBC and GLPK; although it did better than all of them, it was worse than published results with Gurobi/CPLEX. However, it can handle arbitrary rectangles, while those algorithms need to use a grid with rectangles of small integer sizes.
License
The code and the ideas are placed in the public domain - although I'd be interested to know if someone uses either!
Owner
- Name: Gabriel Gouvine
- Login: Coloquinte
- Kind: user
- Location: Edinburgh
- Company: AMD
- Repositories: 36
- Profile: https://github.com/Coloquinte
GitHub Events
Total
Last Year
Issues and Pull Requests
Last synced: about 1 year ago
All Time
- Total issues: 0
- Total pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Total issue authors: 0
- Total pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0