In this podcast series, discussion on VLSI and its related fields is presented, focusing on recent developments and advancements in the industry. Topics such as the latest trends and innovations in semiconductor technology are explored, offering insights into the evolving landscape.
Career guidance is shared, providing practical advice for navigating the field, along with success stories that highlight the journeys of professionals who have made their mark in VLSI. Whether for students, professionals, or those interested in the subject, valuable knowledge is offered to help stay informed and succeed in this dynamic area.
"From Research to Entrepreneurship" perfectly sums up today’s guest, Dr. Meri Helle’s journey! ⚡🔬 A passionate technologist and physics enthusiast, she blends scientific curiosity with business acumen, successfully commercializing products from small to medium-scale fabrication units. With rare experience in running a thriving wafer processing business alongside a team of like-minded technical experts, her path has been anything but ordinary.
But it wasn’t always smooth sailing! 🌊 She once had to forgo a postdoctoral opportunity at a prestigious university. Yet, she embraced family life and motherhood with unwavering determination and her ever-optimistic spirit. 👩👧✨ Dr. Helle finds opportunities in every challenge and gracefully normalizes tough situations with her signature phrase: "It is what it is." 😊 A truly inspiring and joyful person to talk to—her energy is contagious! 🚀💡
Every entrepreneur has a unique story, and in this podcast, we uncover the fascinating journeys of trailblazers in VLSI, semiconductor fabrication, and photonics. 🌍✨
Join us as we explore:
🔬 The transition from research to entrepreneurship—what drives innovators to take the leap?
💡 The challenges faced, including gender bias, funding struggles, and the professional journey in wafer preparation.
⚡ The journey of turning research into production—bridging academia and industry.
📈 Emerging trends like More-than-Moore, and AI’s impact on fabrication.
🛠️ How semiconductor professionals can upskill for the future of AI-driven manufacturing.
🌍 Global collaboration—insights into the Nordic semiconductor landscape and Europe’s new policies.
🌿 The importance of sabbaticals and personal growth beyond work.
Whether you're a VLSI enthusiast, an aspiring entrepreneur, or just curious about the future of semiconductor tech, this podcast delivers insights, inspiration, and expert advice. 🎧💭
Stay tuned for deep dives into the world of chips, circuits, and cutting-edge innovation! 🔍🚀
Guest : Dr. Meri Helle
Dr. Meri Helle has been a semiconductor entrepreneur since 2015. Summa Semiconductor, founded in 2015, was pioneering in small-scale manufacturing services utilising a shared, open-access cleanroom in Finland. A joint-venture company, OneFab Finland, prepared a €100 million fab investment plan in 2019. Third company, OneFab Nordic Oy, was registered in January 2025. With a group of ten founding partners, OneFab is going to have a significant impact on semiconductor manufacturing restructuring in the coming years. Dr. Helle holds a doctoral degree from Helsinki University of Technology in quantum physics (2006). Before moving to industry, she was working with superconducting nano-electronics as a postdoc in Low Temperature Laboratory, Aalto University, Finland (2007-2010). Dr. Helle joined Nokia Research Centre 2010 and 2011 silicon wafer manufacturing company Okmetic. After completing the first year at Okmetic as a Process Engineer, Dr. Helle moved to Okmetic’c sales team as a Customer Support Engineer. Her main responsibilities were in Taiwan, Singapore, Malaysia as well as supportive role in Europe and the USA.
In this insightful episode of The Semiconductor Podcast (TSP), we sit down with industry veteran ET Tan to explore the incredible 30-year evolution of the semiconductor industry in Penang 🏭💡. From the early economic shifts 💰 to the initial reactions of job seekers 👨🎓➡️👨🏭, we dive deep into how skill development 🛠️ and university involvement 🎓 have shaped Malaysia’s tech ecosystem.
We also discuss whether Penang is outsourcing its workload 🌍, how semiconductors have fueled Malaysia’s economy post-independence 🇲🇾, and the key factors that will define the next decade of the global semiconductor industry 🚀📡.
Wrapping up, ET Tan shares invaluable career advice for young engineers 🔧📖—how to stay technically relevant and future-proof in this ever-evolving field.
📢 Don’t miss this power-packed discussion on one of Asia’s most dynamic semiconductor hubs! Tune in now! 🎧✨
🔹 Key Discussion Points:
📈 The evolution of Penang’s semiconductor industry over the last three decades.
💰 The economic shifts in Malaysia when the semiconductor industry began.
👨💼 The initial reaction of job seekers to semiconductor opportunities.
🛠️ Advancements in skill development for semiconductor professionals.
🎓 The increasing role of universities in shaping the semiconductor ecosystem.
🌍 The trend of outsourcing semiconductor workload from Penang to other regions.
🇲🇾 The semiconductor industry's contribution to Malaysia’s economy post-independence.
🚀 Key factors that will drive the global semiconductor industry over the next 10 years.
🔧 Expert career advice for young engineers on staying technically relevant and future-ready.
🎧 Tune in now to gain expert insights into Penang’s semiconductor journey and its future! 🚀
In this podcast series, discussion on VLSI and its related fields is presented, focusing on recent developments and advancements in the industry. Topics such as the latest trends and innovations in semiconductor technology are explored, offering insights into the evolving landscape.
Career guidance is shared, providing practical advice for navigating the field, along with success stories that highlight the journeys of professionals who have made their mark in VLSI. Whether for students, professionals, or those interested in the subject, valuable knowledge is offered to help stay informed and succeed in this dynamic area.
Watch the podcast here.
Guest : ET Tan
ET Tan is a technology veteran with over 35 years of experience in innovation and
commercialization. He began his career in Silicon Valley and Silicon Glen, working with HP
and Seagate on product development and market-entry strategies for leading-edge
technologies. Returning to Malaysia, he served in leadership roles including VP of Strategic
Management at Silterra, CEO of Penang Skills Development Centre (PSDC), and Board
Member of MIMOS, Malaysia's applied research and development centre. Now, as MD of ET
Partners, he helps organizations build technology roadmaps that capitalise on opportunities
in chip design, advanced packaging, and manufacturing. With an BSc(Hon) from Imperial
College London and an executive MBA from Cranfield, Mr. Tan brings deep technical and
strategic expertise to discussions on how companies in Asia can unlock their semiconductor
potential in the race to a $1 trillion industry by 2030.
Credits :
Image by Lucas Wendt from Pixabay
In this podcast series, discussion on VLSI and its related fields is presented, focusing on recent developments and advancements in the industry. Topics such as the latest trends and innovations in semiconductor technology are explored, offering insights into the evolving landscape.
Career guidance is shared, providing practical advice for navigating the field, along with success stories that highlight the journeys of professionals who have made their mark in VLSI. Whether for students, professionals, or those interested in the subject, valuable knowledge is offered to help stay informed and succeed in this dynamic area.
Join us for an insightful conversation with an industry leader who transitioned from an instrumentation engineer to a firmware expert and now runs a cutting-edge tech company! 🌍💡
🔹 Discover the journey of building Indisemic and how it navigates the dynamic world of IoT, asset tracking, and smart devices.
🔹 Learn about the technology behind their advanced multi-RF modules, dual-band Wi-Fi, and satellite-based tracking 🌐📡.
🔹 Explore how international collaborations with Nordic Semiconductor and Japanese firms fuel innovation. 🇮🇳🤝🌏
🔹 Understand the role of IoT security, smart medical devices, and the future of connected systems 🏥🔒.
🔹 Get expert insights on business challenges, government policies, and opportunities for students & entrepreneurs 📈🎓.
Whether you're an engineering student, an aspiring entrepreneur, or an IoT enthusiast, this episode is packed with valuable takeaways! 🚀🔧
Tune in now! 🎧✨
Guest - Nikul Shah
Founder | Innovator | Semiconductor Expert
Nikul Shah is the founder of Indiesemic Private Limited, a pioneering semiconductor product company, designing cutting-edge RF modules based on BLE, wifi, zigbee, NFC, lora etc and multi core ASICs, and RISC-V-based solutions to power the future of IoT, smart homes, automotive, and more. With 12+ years of experience in system design, FPGA design, verification, and RTL architecture verification, Nikul has worked on projects with global leaders like Intel, Honeywell, NXP, and Qualcomm.
In this podcast series, discussion on VLSI and its related fields is presented, focusing on recent developments and advancements in the industry. Topics such as the latest trends and innovations in semiconductor technology are explored, offering insights into the evolving landscape.
Career guidance is shared, providing practical advice for navigating the field, along with success stories that highlight the journeys of professionals who have made their mark in VLSI. Whether for students, professionals, or those interested in the subject, valuable knowledge is offered to help stay informed and succeed in this dynamic area.
🎙️ In this podcast episode, we sit down with Chandan Raj, an entrepreneur from Bihar. He left home after 12th grade for higher studies and eventually carved a niche in VLSI and semiconductor design. From navigating career choices between Embedded Systems, Telecommunication, and VLSI to founding Schip Semi, a startup based in Bihar, this conversation offers valuable insights into the challenges and opportunities in the semiconductor industry. Tune in to hear about his journey, the lessons learned from working across different countries, and the evolving tech landscape in Bihar.🌍💡
✅ Career Journey: The shift from student life to VLSI
✅ Cultural & Global Insights: The challenges and lessons from working across Noida, Bengaluru, Penang, Tel Aviv, and China 🌏
✅ The entrepreneurial leap—why Bihar over traditional tech hubs? 🤔
✅ Building a Startup: The challenges faced and the impact of being outside well-established tech ecosystems 🏗️
✅ Overcoming ground-level hurdles while building a startup 🚀
✅ The future of VLSI and Embedded Systems in India 🔬
✅ How students and budding entrepreneurs can seize emerging opportunities 🎓✨
✅ The need for stronger industry connections and awareness programs in India 🏗️
✅ Opportunities in VLSI: How students can tap into the growing demand for VLSI and Embedded Systems jobs 🎓📈
Join us as we explore the evolving startup ecosystem in Bihar, the power of innovation, and how the next generation can drive change in the semiconductor industry! 💡⚡
🎧 Tune in now and get inspired! 🚀 #VLSI#StartupIndia#Entrepreneurship#Semiconductor
This conversation offers practical insights into entrepreneurship, the semiconductor industry, and the evolving tech landscape in Bihar. 🎧 Tune in to learn more!
Guest : Chandan Raj
Watch the Podcast here :
Chandan Raj, born and raised in a middle-class family in Muzaffarpur, Bihar, completed his schooling (10th and 12th) under the CBSE Board before earning a B.Tech in Electronics and Telecommunication from Biju Patnaik University of Technology, Odisha. With 15+ years of experience in the VLSI domain, he has worked across India, Malaysia, Romania, Israel, and China, gaining expertise in ASIC, FPGA, and mixed-signal design, SoC/IP verification, and semiconductor architecture. In 2020, he founded SURESH Chips and Semiconductor, which has grown into a major semiconductor firm in eastern India under his leadership. His technical expertise spans Power-Aware Verification, Gate-Level Simulation, SoC/IP Verification, PCIe Gen4, USB 3.0, 5G ASIC/FPGA Verification, and RTL Design, along with hands-on experience in PCIe VIP development using SV/UVM. Now, in 2025, he is focused on expanding his business globally, driving innovation and excellence in semiconductor technology.
In this article, we dive deep into the world of global routing and the crucial design flow behind it. We begin with an introduction to essential routing terminology and explore the concept of a switchbox in routing. Learn how optimization goals play a vital role in global routing and how routing regions are represented for effective design. We’ll take you through the global routing flow, covering topics like single-net routing, global routing in connectivity graphs, and the key algorithms used for finding the shortest path—Dijkstra’s Algorithm and A* Search. The video also explores the full netlist routing process and the role of a global router. We then discuss optimization techniques for different design types: full custom designs, standard cell designs, and gate array designs. This article offers a comprehensive understanding of global routing, its flow, and optimization strategies, making it a must-read for anyone interested in VLSI design and routing techniques.
Design Flow & Global Routing:
In VLSI , routing is a crucial step that connects the various components like logic gates, transistors, and memory cells on a chip. It involves determining the paths for electrical connections, which are implemented through metal layers on the chip.
Routing is divided into three major stages:
(i) Global, (ii) Detailed & (iii) Specialized Routing.
Global Routing: Initial stage of the routing process, where the chip's overall routing framework is determined. It defines the general paths for each connection/net without focusing on precise details. The goal of global routing is to create an approximate plan for how the nets will be routed across the chip.
Key Aspects of Global Routing:
(i) Calculates approximate net paths and assigns them to regions or grids within the chip.
(ii) Allocates appropriate metal layers for detailed routing without specifying exact geometry.
(iii) Prevents congestion by ensuring sufficient routing space for all nets.
(iv) Divides the chip into grids, systematically determining regions for each net.
(v) Focuses on optimizing overall interconnection layout rather than precise routing geometry.
Detailed & Specialized Routing:
Detailed Routing:
This stage refines global routing into precise, manufacturable paths, finalizing the layout of electrical interconnections for fabrication.
Key Aspects of Detailed Routing:
Detailed routing defines precise wire paths while adhering to design rules, including spacing, width, via placement, and metal layer usage. It optimizes vias, ensures signal integrity by minimizing RC delay and crosstalk, and resolves congestion by redistributing wires or using alternative layers. Special attention is given to power and ground routing to guarantee reliable voltage delivery across the chip.
Specialized Routing:
Specialized routing handles nets with specific requirements, such as clocks, power networks, and high-speed signals, ensuring they meet performance constraints.
Key Aspects of Specialized Routing:
Specialized routing includes critical net and clock routing, ensuring precise timing and reliability. It also covers power and ground distribution, high-speed signal routing and shielding for noise reduction. These ensure optimal performance and signal integrity in complex designs.
Essential Terminology for Global Routing:
1. Routing Track :A routing track represents a horizontal or vertical wiring path that facilitates the routing of signals. Signal nets traverse these paths by alternating between horizontal tracks and vertical columns, connected using inter-layer vias.
2. Routing Region : A routing region is a defined area containing routing tracks or columns. It serves as the guide for allocating wiring paths to connect signal nets efficiently.
3. Uniform Routing Region: These regions consist of evenly spaced horizontal and vertical grid lines, forming what’s known as a "global grid" or "grid." The grid comprises unit cells called "global cells" (gcells). Typically, the spacing between grid lines ranges from 7 to 40 routing tracks, balancing the complexities of chip-scale global routing and detailed routing tasks.
4. Non-Uniform Routing Region:Unlike their uniform counterparts, non-uniform regions are defined by boundaries aligned with external pin connections or macro-cell edges. That regions include channels and switch boxes of varying dimensions.
5. Channel : A channel is a rectangular routing region designed to connect pins located on its two opposite sides, while the other two sides remain pin-free. Channels are further classified as:
(a) Horizontal Channel:Features pins along the top and bottom boundaries.
(b) Vertical Channel: Features pins along the left and right boundaries.
6. Gcells (Global Cells) :Global cells, or gcells, are the fundamental units within a global grid. They serve as the basic building blocks for defining paths in routing regions and are instrumental in the routing process.
What is SwitchBox in Routing?
Switchbox :
A switchbox is a square or rectangular region where multiple channels intersect. These critical structures enable connections between different routing tracks or columns, enhancing the routing network's flexibility.
2-D Switchbox : A 2-D switchbox exists in a single plane and connects horizontal and vertical routing channels within a single metal layer. It serves as a connection hub, enabling routing paths to switch directions (e.g., horizontal to vertical or vice versa) within a specific routing layer. Frequently used in PCB design or simpler VLSI designs where inter-layer routing is minimal or non-existent. The region typically resembles a rectangular or square grid with intersection points for connecting different channels.
3-D Switchbox : A 3-D switchbox incorporates connections across multiple layers of a chip, often through inter-layer vias. It facilitates interconnections not only between horizontal and vertical tracks but also between different metal layers. This capability is crucial for modern multi-layered Ics. Widely used in advanced VLSI designs where chips have multiple layers of metal routing, such as in 3D ICs or multi-layer ASICs. Extends the concept of the 2-D switchbox to include vertical pathways, allowing signals to traverse different physical planes within the chip.
Optimization Goals in Global Routing :
1. Minimizing Total Wire length :Wire length minimization is a fundamental goal in global routing. Reducing the total wire length enhances performance. Shorter wires reduce signal propagation delays, leading to faster circuits. Less wire length means reduced capacitance and, consequently, lower power dissipation. Shorter interconnects decrease the chances of defects and increase manufacturability.
2. Managing Routing Congestion : Congestion arises when multiple signal nets compete for the same routing resources. Effective congestion management ensures efficient resource utilization, prevents overloading specific regions while under utilizing others, avoids unnecessary detours that can increase wire length and delays. Reduces the risk of violating constraints such as spacing between wires.
3. Maximizing Timing Slack : Timing slack refers to the difference between the required arrival time and the actual arrival time of a signal. Maximizing timing slack is crucial for meeting timing constraints. That ensures that all signals arrive within their designated time windows. Provides a buffer against variations in manufacturing or operational conditions.
4. Balancing Via Usage : Vias connect different metal layers in a chip’s layout. Excessive via usage can increase manufacturing costs, lead to reliability issues due to thermal stress, add delays by introducing additional resistance and capacitance. Balancing via usage is therefore vital for cost-efficient and reliable designs.
5. Optimizing for Power Efficiency : Power optimization is critical, especially for portable devices and data centers. Efficient global routing minimizes dynamic power by reducing switching activity and interconnect capacitance, minimizes static power through efficient use of routing resources to minimize leakage.
6. Adapting to Design Constraints : Modern VLSI designs face constraints like fixed-die boundaries, specific routing resources, and pre-defined placement. Optimization ensures that these constraints are respected without compromising the overall design quality.
Representing Routing Regions:
In Global routing channels and switch boxes are represented as graph, where nodes represent routing regions and edges represent adjoining regions.There are 3 graph techniques :
(i) Grid Graph :
Also defined a s Global Grid/ggrid . A uniform grid overlays the chip layout. It consists of horizontal and vertical grid lines that divide the chip into smaller cells, known as global cells (gcells). Grid lines are spaced at regular intervals to balance global and detailed routing complexity.
(ii) Channel connectivity graph :
G = (V,E), where the nodes v ∈ V represent channels, and the edges E represent adjacency of the channels. Capacity of each channel is represented in its respective graph node.
(iii) Switchbox connectivity graph :
G = (V, E), where the nodes v ∈ V represent switch boxes and an edge exists between two nodes if the corresponding switch boxes are on opposite sides of the same channel .
Global Routing Flow :
1. Defining The Routing Regions:
- Partition the layout area into routing regions.
- Allow nets to be routed over standard cells in some cases.
- Structure the routing regions as 2D/3D channels, switch boxes, or other region types.
- Represent the regions, along with their capacities and connections, as a graph.
2. Mapping Nets to the Routing Regions:
- Provisionally assign each net in the design to one or more routing regions to connect all its pins.
- Ensure the number of nets passing through a routing region does not exceed its routing capacity.
- Consider timing and congestion as factors influencing the path selection for each net.
3. Assigning Cross points:
- Assign routes to specific spots/cross points, along the edges of routing areas.
- Align crosspoints to simplify handling designs with millions of cells.
- Enable faster processing through parallel and distributed methods by allowing independent work on each routing area.
- Analyze the dependencies between net connections and the order of routing channels to optimize cross point assignments.
Single Net Routing:
A set of pins that electrically connected is called net. A single-net routing task deals with routing one such net at a time, ensuring it adheres to design rules while optimizing for factors such as wire length, timing, and congestion. For a two-pin net, the task is relatively straightforward, requiring a path between the two pins. For a multi-pin net, the net is decomposed into smaller two-pin sub nets before routing.
Objectives of Single-Net Routing:
1. Minimize Wire length: Reducing the total length of the wire connecting pins minimizes delays and power consumption.
2. Adhere to Design Rules: Ensure the route meets constraints like spacing, via limits, and layer assignments.
3. Avoid Obstacles: Navigate around fixed blocks, macros, and other routed nets.
4. Optimize Timing: Critical nets must be routed with minimal delay to meet performance requirements.
Techniques for Single-Net Routing:
1. Rectilinear spanning tree:
A rectilinear spanning tree connects all terminals (pins) using only direct pin-to-pin connections with vertical and horizontal segments. These connections are restricted to meeting exclusively at pins, meaning that “crossing” edges do not intersect, and no additional junction points (Steiner points) are introduced. When the total length of the segments is minimized, it is called a rectilinear minimum spanning tree (RMST).
2. Rectilinear Steiner tree (RST):
A rectilinear Steiner tree (RST) connects all pin locations and may include additional locations known as Steiner points. While any rectilinear spanning tree for a p-pin net qualifies as an RST, introducing strategically placed Steiner points can often reduce the total net length. An RST becomes a rectilinear Steiner minimum tree (RSMT) when the total length of the segments used to connect all pins is minimized.
Global Routing in Connectivity Graph:
Global Routing in connectivity graph is done in following
sequence steps.
(a) Defining the Routing Regions :
The vertical and horizontal routing regions are formed by stretching the bounding box of cells in each direction until a cell or chip boundary is reached.
(b) Defining the Connectivity Graph:
In the connectivity graph, nodes represent routing regions, edges indicate their continuity, and each node stores the horizontal and vertical capacities of its region.
(c) Determining the Net Order :
The order of net processing can be set before or during routing, based on factors like criticality, pin count, bounding box size (larger gets higher priority), or electrical properties. Some algorithms adjust dynamically based on layout characteristics observed during routing.
(d) Assigning Tracks for all pin Connections :
A horizontal and vertical track are reserved in each pin's routing region to ensure connectivity.
(e) Global Routing of all Nets :
Each net is processed sequentially, involving steps such as net or sub-net ordering, track assignment using a maze-routing algorithm, and capacity updates in the connectivity graph.
Finding Shortest Path by Dijkstra’s Algorithm :
Finds shortest paths from a source node to all other nodes in a graph. Works with graphs that have non-negative edge weights. Commonly used in maze routing and shortest path problems.
Input Parameters :
1. Graph (G(V, E)) with non-negative edge weights (W).
2. Source node (s) as the starting point.
3. Target node (f) as the destination.
Node Groups :
1. Group 1/Unvisited Nodes – Nodes have not been visited.
2. Group 2/Considered Nodes – Nodes visited but shortest
path cost not finalized.
3. Group 3/Known Nodes– Nodes for which the shortest
2. The cost of reaching each node is set to infinity (∞) except
for the source node, which has cost 0.
3. Parent of each node is initially unknown.
4. The source node (s) is moved to Group 3 as the first known node.
Algorithm Execution :
While the target node (f) is not reached -
1. Compute the cost of reaching neighboring nodes from the current node.
2. If a node is in Group 1, record its cost and update its parent.
3. If a node is already in Group 2, compare and update its cost if a better (lower-cost) path is found.
4. Select the lowest-cost node in Group 2 and move it to Group 3.
5. Repeat until the target node(f) is added to Group 3.
Path Reconstruction :
Once f is found, back trace from f to s using parent nodes to determine the shortest path.
Efficiency Considerations : Each iteration only considers neighbors of the most recently added node (curr_node), reducing redundant calculations. Nodes move sequentially into Group 3 based on the increasing order of their shortest-path cost. The algorithm stops once the target node (f) is added to Group 3, ensuring an optimal path.
Handling Node Costs : When nodes have traversal costs, each node is replaced by a d-clique (a complete sub-graph of d nodes). Clique edges have weights equal to the original node cost. The original d incident edges are connected to different clique nodes. This transformation ensures that path traversal accounts for node traversal costs efficiently.
Finding Shortest Path : A* Search :
Similar to Dijkstra’s algorithm but extends the cost function. Includes an estimated distance from the current node to the target. Guarantees the shortest path if a path exists. The estimated distance should never exceed the actual distance (admissibility criterion). Efficiency Compared to Dijkstra’s Algorithm Expands only the most promising nodes (best-first search). Reduces the solution space compared to Dijkstra’s algorithm. A tight lower bound estimate can significantly improve runtime. Can be derived from Dijkstra’s algorithm by adding distance-to-target estimates.
Node priority is determined by the sum of:
- Cost from the start node (like Dijkstra’s label).
- Estimated remaining distance to the target.
- Bidirectional A* Search is a variant. Expands nodes from both source and target until regions meet. Reduces the number of nodes considered slightly. However, tracking the order of visited nodes, along with the complexity of implementing an efficient solution, poses significant challenges. In practice, these difficulties can outweigh the potential benefits of bidirectional search.
Methods of Full Netlist Routing:
1. Integer Linear programming:
A linear program (LP) is a mathematical problem that includes a set of conditions (called constraints) and an optional goal/objective function to maximize or minimize. Both the constraints and the objective function must be written as linear equations or inequalities. If all variables in a linear program only take whole number values, it is called an integer linear program (ILP). When these variables are restricted to only 0 or 1, it is referred to as a 0-1 ILP. There are various software tools, like GLPK, CPLEX, and MOSEK, that can solve (integer) linear programs.
The ILP takes 3 inputs :
(1) an W × H routing grid G,
(2) routing edge capacities, and
(3) the netlist Netlist.
The ILP uses 2 sets of variables. The first set includes k Boolean variables, each representing an indicator for one of k specific paths or routes for a net in the Netlist.
- The second set contains k real variables, each of which represents a net weight for a specific route for a net in Netlist.
Rip-Up & ReRoute(RRR):
Modern ILP solvers can handle hundreds of thousands of routes efficiently, but commercial EDA tools require faster and more scalable methods. The rip-up and reroute (RRR) framework addresses this by focusing on problematic nets. When a net faces obstacles or interference, RRR temporarily allows violations, routes all nets, then iteratively removes and reroutes some to reduce conflicts. Alternatively, push-and-shove strategies move existing nets to new positions to resolve congestion or make unroutable nets feasible. A greedy routing approach avoids violations but often causes large detours. In contrast, RRR permits temporary over-capacity routing to optimize overall paths. Allowing violations and rerouting enables more efficient routing with fewer detours than strictly violation-free methods. In the RRR framework, not all violating nets are ripped up, reducing runtime significantly with only a small increase in wire length.
Global Router:
A global router first divides multi-pin nets into two-pin subnets and generates an initial routing solution on a 2D grid. If there are no violations, it assigns layers by mapping the 2D routes onto a 3D grid. If violations occur, problematic nets are ripped up and rerouted iteratively until the design is violation-free or a stopping condition, such as a CPU limit, is reached. Some routers include an optional cleanup pass to minimize wire length after rip-up. Alternatively, some global routers route directly on the 3D grid, which can improve wire length but is slower and may fail to complete routing. Nets are routed using maze and pattern routing, with negotiated congestion routing managing costs. A global router determines paths for two-pin nets while adhering to capacity constraints, prioritizing minimal wire length. It employs maze routing methods like Dijkstra's or A* search to ensure the shortest path between points. However, these methods can be excessively slow, especially when topologies involve edges requiring minimal vias.
Modern routers implement RRR (Rip-up and Reroute) using negotiated congestion routing. In this approach, each edge is assigned a cost or value that represents the demand for that edge. Higher costs discourage nets from utilizing heavily used edges, indirectly encouraging them to explore alternative, less congested paths.
Optimization for Different Design Types :
1. Full Custom Design:
A full custom design features a layout dominated by macro cells with irregular, non-uniform routing regions. Key initial tasks include channel definition and channel ordering. Channel definition partitions the global routing area into routing channels and switchboxes. Channel ordering is determined using floorplan tree. If a part of floorplan cannot be represented using horizontal and vertical cuts atleast one switchbox is used along with channels. Once all of the regions, channels and switchboxes are determined the ents canm be routed. Steiner tree routing and Minimum Spanning tree routing are two methods used. Shortest path is determined by Dijkstra’s algorithm.
Standard Cell Design :
In standard cell design, when the number of metal layers is limited, feedthrough cells are used to route a net across multiple cell rows. If the cell rows and netlist are fixed, the number of unoccupied sites within the cell rows is also fixed, which restricts the number of possible feedthroughs. As a result, standard cell global routing aims to (1) ensure the design is routable and (2) identify a low-congestion solution that minimizes the total wirelength.
Gate Array Design :
In gate array design, the cell sizes and the routing region sizes—i.e., the routing capacities—are fixed. Since adding extra routing resources is not an option to ensure routability, key tasks involve assessing the placement’s routability and finding a feasible routing solution. Additional optimization objectives include minimizing the total routed wire length and reducing the length of the longest timing path.