Manufacturing Constraints Validation for EDA Layouts
Overview
Narrow spacing detection identifies regions where geometric features are closer than manufacturing tolerances allow. This algorithm is essential for design rule checking (DRC) and ensuring fabrication reliability in advanced semiconductor processes.
Problem Definition
Manufacturing Challenges
- Etching Resolution: Features too close may merge during etching
- Lithography Limits: Optical resolution constraints in photolithography
- Process Variations: Manufacturing tolerances require minimum separations
- Electrical Issues: Parasitic coupling and crosstalk
Mathematical Foundation
For two line segments or polygon edges:
minimum_distance = min(point_to_line_distance(p1, segment2),
point_to_line_distance(p2, segment1),
segment_to_segment_distance(segment1, segment2))
Core Algorithm
Approach 1: Brute Force O(n²)
class NarrowSpacingDetector {
public:
struct SpacingViolation {
Point point1, point2;
double distance;
int polygon1_id, polygon2_id;
};
std::vector<SpacingViolation> detectNarrowSpacing(
const std::vector<Polygon>& polygons,
double min_spacing = 0.1
) {
std::vector<SpacingViolation> violations;
for (size_t i = 0; i < polygons.size(); ++i) {
for (size_t j = i + 1; j < polygons.size(); ++j) {
auto poly_violations = checkPolygonPair(
polygons[i], polygons[j], min_spacing, i, j
);
violations.insert(violations.end(),
poly_violations.begin(),
poly_violations.end());
}
}
return violations;
}
private:
std::vector<SpacingViolation> checkPolygonPair(
const Polygon& poly1, const Polygon& poly2,
double min_spacing, int id1, int id2
) {
std::vector<SpacingViolation> violations;
auto edges1 = poly1.edges();
auto edges2 = poly2.edges();
for (const auto& edge1 : edges1) {
for (const auto& edge2 : edges2) {
double dist = segmentToSegmentDistance(
edge1.first, edge1.second,
edge2.first, edge2.second
);
if (dist < min_spacing) {
auto closest_points = findClosestPoints(edge1, edge2);
violations.push_back({
closest_points.first,
closest_points.second,
dist, id1, id2
});
}
}
}
return violations;
}
double segmentToSegmentDistance(
const Point& p1, const Point& p2,
const Point& p3, const Point& p4
) {
return calculateMinimumDistance(p1, p2, p3, p4);
}
};
Approach 2: Spatial Index Optimization O(n log n)
class OptimizedSpacingDetector:
def __init__(self, world_bounds):
self.polygon_cache = {}
def detect_narrow_spacing(self, polygons, min_spacing=0.1):
"""Optimized spacing detection using spatial indexing."""
violations = []
for poly_id, polygon in enumerate(polygons):
bbox = polygon.bounding_box()
expanded_bbox = bbox.expand(min_spacing)
self.spatial_index.insert(expanded_bbox, poly_id)
self.polygon_cache[poly_id] = polygon
checked_pairs = set()
for poly_id, polygon in enumerate(polygons):
bbox = polygon.bounding_box()
search_bbox = bbox.expand(min_spacing * 1.5)
nearby_ids = self.spatial_index.query_range(search_bbox)
for nearby_id in nearby_ids:
if nearby_id != poly_id:
pair = tuple(sorted([poly_id, nearby_id]))
if pair not in checked_pairs:
checked_pairs.add(pair)
nearby_polygon = self.polygon_cache[nearby_id]
pair_violations = self._check_polygon_pair(
polygon, nearby_polygon,
min_spacing, poly_id, nearby_id
)
violations.extend(pair_violations)
return violations
def _check_polygon_pair(self, poly1, poly2, min_spacing, id1, id2):
"""Check spacing between two polygons."""
violations = []
bbox1 = poly1.bounding_box()
bbox2 = poly2.bounding_box()
if bbox1.distance_to(bbox2) >= min_spacing:
return violations
for edge1 in poly1.edges:
for edge2 in poly2.edges:
dist = self._segment_distance(edge1, edge2)
if dist < min_spacing:
closest_pts = self._closest_points_on_segments(edge1, edge2)
violations.append({
'point1': closest_pts[0],
'point2': closest_pts[1],
'distance': dist,
'polygon1_id': id1,
'polygon2_id': id2
})
return violations
Quadtree spatial index for efficient range and intersection queries.
Complexity Analysis
Time Complexity Comparison
| Method | Preprocessing | Query | Overall | Space |
| Brute Force | None | O(n²m²) | O(n²m²) | O(1) |
| Spatial Index | O(n log n) | O(k log n) | O(n log n + km²) | O(n) |
| R-tree | O(n log n) | O(log n + k) | O(n log n + km²) | O(n) |
Where:
- n = number of polygons
- m = average edges per polygon
- k = average nearby polygons per query
Performance Scaling
import time
import numpy as np
def benchmark_spacing_detection():
polygon_counts = [10, 50, 100, 500, 1000]
results = {
'brute_force': [],
'spatial_index': [],
'rtree': []
}
for n_polygons in polygon_counts:
test_polygons = generate_test_layout(n_polygons)
start = time.perf_counter()
bf_detector = BruteForceDetector()
bf_results = bf_detector.detect_narrow_spacing(test_polygons, 0.1)
bf_time = time.perf_counter() - start
results['brute_force'].append(bf_time)
start = time.perf_counter()
si_detector = OptimizedSpacingDetector(world_bounds)
si_results = si_detector.detect_narrow_spacing(test_polygons, 0.1)
si_time = time.perf_counter() - start
results['spatial_index'].append(si_time)
print(f"N={n_polygons}: BF={bf_time:.3f}s, SI={si_time:.3f}s, "
f"Speedup={bf_time/si_time:.1f}x")
return results
benchmark_results = benchmark_spacing_detection()
Interactive Tutorial
Tutorial 1: Basic Spacing Check
import zlayout
import matplotlib.pyplot as plt
components = [
]
detector = zlayout.NarrowSpacingDetector()
violations = detector.detect_narrow_spacing(
components,
min_spacing=0.1
)
print(f"Found {len(violations)} spacing violations")
for i, violation in enumerate(violations):
print(f"Violation {i+1}: {violation['distance']:.3f} < 0.1")
print(f" Between polygons {violation['polygon1_id']} and {violation['polygon2_id']}")
Axis-aligned rectangle for bounding boxes and simple EDA components.
Tutorial 2: Process Node Validation
process_spacing_rules = {
"28nm": 0.028,
"14nm": 0.014,
"7nm": 0.007,
"3nm": 0.003,
}
def validate_process_node(layout, process_node):
min_spacing = process_spacing_rules[process_node]
violations = detector.detect_narrow_spacing(
layout.components,
min_spacing=min_spacing
)
critical_violations = [
v for v in violations
if v['distance'] < min_spacing * 0.8
]
return {
'total_violations': len(violations),
'critical_violations': len(critical_violations),
'pass': len(violations) == 0,
'min_distance_found': min([v['distance'] for v in violations]) if violations else float('inf')
}
test_layout = generate_cpu_layout()
for process in ["28nm", "14nm", "7nm", "3nm"]:
result = validate_process_node(test_layout, process)
status = "PASS" if result['pass'] else "FAIL"
print(f"{process} Process: {status}")
print(f" Violations: {result['total_violations']}")
print(f" Critical: {result['critical_violations']}")
print(f" Min distance: {result['min_distance_found']:.4f}")
Real-world Applications
1. Advanced Process DRC
class AdvancedDRCChecker:
def __init__(self, process_rules):
self.rules = process_rules
self.detectors = {}
def comprehensive_spacing_check(self, layout):
"""Multi-layer spacing validation."""
all_violations = {}
layer_rules = {
'metal1': self.rules['metal1_spacing'],
'metal2': self.rules['metal2_spacing'],
'via': self.rules['via_spacing'],
'poly': self.rules['poly_spacing']
}
for layer_name, min_spacing in layer_rules.items():
layer_components = layout.get_layer_components(layer_name)
violations = self.detect_narrow_spacing(
layer_components, min_spacing
)
if layer_name == 'via':
violations.extend(self._check_via_to_via_spacing(
layer_components, min_spacing * 1.2
))
all_violations[layer_name] = violations
return all_violations
2. Parasitic Extraction Guidance
def analyze_coupling_risk(spacing_violations, frequency_mhz=1000):
"""Analyze electrical coupling risk from spacing violations."""
coupling_analysis = []
for violation in spacing_violations:
distance = violation['distance']
coupling_capacitance = calculate_coupling_capacitance(
distance,
conductor_width=1.0,
dielectric_constant=3.9
)
coupling_noise_mv = estimate_coupling_noise(
coupling_capacitance, frequency_mhz
)
risk_level = "HIGH" if coupling_noise_mv > 50 else \
"MEDIUM" if coupling_noise_mv > 10 else "LOW"
coupling_analysis.append({
'violation': violation,
'coupling_capacitance_ff': coupling_capacitance * 1e15,
'coupling_noise_mv': coupling_noise_mv,
'risk_level': risk_level
})
return coupling_analysis
Advanced Optimizations
GPU Acceleration for Large Datasets
class GPUSpacingDetector:
def __init__(self, use_cuda=True):
self.use_cuda = use_cuda and cuda_available()
def detect_narrow_spacing_gpu(self, polygons, min_spacing):
"""GPU-accelerated spacing detection."""
if not self.use_cuda:
return self.fallback_cpu_detection(polygons, min_spacing)
gpu_polygons = self._prepare_gpu_data(polygons)
violations = self._cuda_spacing_kernel(gpu_polygons, min_spacing)
return self._format_violations(violations)
def _cuda_spacing_kernel(self, gpu_data, min_spacing):
"""CUDA kernel for parallel distance computation."""
"""
__global__ void spacing_kernel(
float* polygon_data,
int num_polygons,
float min_spacing,
int* violations_out
) {
int idx = blockIdx.x * blockDim.x + threadIdx.x;
// Parallel distance computation...
}
"""
pass
Memory-Efficient Streaming
class StreamingSpacingDetector:
def __init__(self, chunk_size=1000):
self.chunk_size = chunk_size
def detect_large_layout(self, layout_iterator, min_spacing):
"""Process layouts too large to fit in memory."""
violations = []
polygon_chunks = []
for chunk in self._chunk_iterator(layout_iterator, self.chunk_size):
chunk_violations = self._process_chunk(chunk, min_spacing)
violations.extend(chunk_violations)
polygon_chunks.append(chunk)
if len(polygon_chunks) > 3:
polygon_chunks.pop(0)
if len(polygon_chunks) > 1:
cross_violations = self._check_chunk_boundaries(
polygon_chunks[-2], polygon_chunks[-1], min_spacing
)
violations.extend(cross_violations)
return violations
Performance Summary
Narrow spacing detection performance characteristics:
Algorithm Complexity:
- Brute Force: O(n²m²) - prohibitive for large layouts
- Spatial Index: O(n log n + km²) - practical for production
- GPU Accelerated: O(n log n) with massive parallelism
Memory Usage:
- Basic: O(n) for polygon storage
- Spatial Index: O(n) additional for index structure
- Streaming: O(chunk_size) for arbitrarily large layouts
Practical Performance:
- 1K polygons: ~10ms (spatial index)
- 10K polygons: ~100ms (spatial index)
- 100K polygons: ~1s (spatial index)
- 1M+ polygons: GPU acceleration recommended
Optimization Guidelines:
- Use spatial indexing for >100 polygons
- Consider bounding box pre-filtering
- GPU acceleration for >100K polygons
- Streaming for memory-constrained environments
The algorithm is essential for modern EDA flows, enabling reliable manufacturing at advanced process nodes while maintaining reasonable computational performance.
1.14.0