A gradual neural network approach for FPGA segmented channel routing problems

Area of Science:

• Computer Engineering
• Artificial Intelligence
• VLSI Design

Background:

• Field-programmable gate arrays (FPGAs) utilize segmented channels for net routing.
• Interconnecting segments via programmable switches creates longer routes.
• The FPGA segmented channel routing problem is NP-complete, requiring efficient solutions.

Purpose of the Study:

• To introduce a novel neural network approach, the gradual neural network (GNN), for FPGA segmented channel routing.
• To address the NP-complete problem of finding conflict-free net routing with minimum cost.
• To develop a method that improves upon existing routing algorithms.

Main Methods:

• A gradual neural network (GNN) comprising NxM binary neurons is designed for the N-net-M-track problem.
• A gradual expansion scheme is employed to minimize routing cost by activating neurons incrementally.
• Novel energy functions and motion equations are defined using heuristic methods.

Main Results:

• The GNN successfully satisfies the constraints of the segmented channel routing problem.
• The gradual expansion scheme effectively minimizes routing costs.
• Performance evaluation on 30 instances showed GNN achieving superior solutions compared to existing algorithms within a fixed number of iterations.

Conclusions:

• The gradual neural network (GNN) presents a promising and effective solution for the NP-complete FPGA segmented channel routing problem.
• GNN demonstrates superior performance in finding optimal, conflict-free routes with reduced cost.
• The heuristic-based energy and motion definitions contribute to the algorithm's efficiency and effectiveness.