Skip to content

Latest commit

 

History

History
88 lines (70 loc) · 2.82 KB

README.md

File metadata and controls

88 lines (70 loc) · 2.82 KB

Maze Router

A Python implementation of a maze router, featuring multi-pin net routing with layer constraints, obstacle avoidance, and visualisation capabilities.

Features

  • Multi-layer routing (M0 and M1)
  • Layer-specific preferred directions (M0: horizontal, M1: vertical)
  • Multi-pin net routing
  • Obstacle avoidance
  • Configurable bend and via penalties
  • Automatic rip-up and reroute with randomization
  • Route visualization
  • Support for custom input specifications

Requirements

  • Python 3.7+
  • NumPy
  • MatPlotLib

Installation

  1. Clone the repository: 
    git clone https://github.com/omaranwar1/IC-NetRouter.git
cd IC-NetRouter 
cd src
  2. Install Packages 
    pip install matplotlib
pip install numpy

Usage

  1. Choose the test case, and add it to the main.py
  2. Run the program 
    python main.py

Implementation Details

Routing Algorithm

  • Uses a modified A* algorithm for pathfinding
  • Implements Steiner tree approach for multi-pin nets
  • Features rip-up and reroute with randomisation for handling routing conflicts
  • Employs layer-specific preferred directions to optimize routing by calculating the cost, and choosing the least costly path

Cost Model

  • Base cost for each grid cell movement; adds 1 to the total route cost
  • Additional penalties for:
    • Non-preferred direction movements
    • Via transitions between layers
    • Costs are predefined in the input file
  • Manhattan distance heuristic for A* pathfinding

Grid Management

  • Two-layer grid system (M0 and M1)
  • Tracks occupied cells and obstacles
  • Maintains net-specific routing information
  • Supports dynamic path clearing and updating

Output

  • The router generates an output file containing the routed paths for each net in the following format:
    • net1 (layer1,x1,y1) (layer2,x2,y2) ...
    • net2 (layer1,x1,y1) (layer2,x2,y2) ...

Contributions

  • Amal Fouda:
    • Router implementation to parse through input
    • Routing implementation using A* algorithm for single pin nets
    • Routing implementation to rip and reroute when the routing algorithm yields unsuccessful
  • Nour Selim
    • Grid implementation to get neighbours and adding obstacles
    • Grid implementation to check valid moves
    • Routing implementation to rip and reroute when the routing algorithm yields unsuccessful
  • Omar Saleh
    • Router implementation to use A* algorithm for multipin nets
    • Visualisation implementation
    • Routing implementation to rip and reroute when the routing algorithm yields unsuccessful

Challenges

  • Bug fixes for the visualisation tool
  • Implementing multipin routing without interferring with other nets
  • Dealing with failed attempts to route, and avoiding infinite loops in rerouting attempts
  • Efficiently connecting multiple pins while minimizing total wire length