seveibar/am3352-dev-board

scripts/refine-decoupling-assignment.py

"""Minimize worst pad-to-ball distance by exchanging identical caps on each rail.
Physical occupied sites and copper clearances remain unchanged.
"""
import json,math,collections,statistics
from pathlib import Path
p=Path('design/decoupling-report.json');report=json.loads(p.read_text());rows=report['capacitors'];groups=collections.defaultdict(list)
for i,r in enumerate(rows):groups[(r['chip'],r['net'])].append(i)
def matching(cost,limit):
 match={}
 def visit(i,seen):
  for j in sorted(range(len(cost)),key=lambda j:cost[i][j]):
   if cost[i][j]>limit+1e-8 or j in seen:continue
   seen.add(j)
   if j not in match or visit(match[j],seen):match[j]=i;return True
  return False
 return {i:j for j,i in match.items()} if all(visit(i,set()) for i in sorted(range(len(cost)),key=lambda i:sum(v<=limit+1e-8 for v in cost[i]))) else None
def hungarian(a):
 n=len(a);u=[0.]*(n+1);v=[0.]*(n+1);p=[0]*(n+1);way=[0]*(n+1)
 for i in range(1,n+1):
  p[0]=i;j0=0;mins=[float('inf')]*(n+1);used=[False]*(n+1)
  while True:
   used[j0]=True;i0=p[j0];delta=float('inf');j1=0
   for j in range(1,n+1):
    if used[j]:continue
    cur=a[i0-1][j-1]-u[i0]-v[j]
    if cur<mins[j]:mins[j]=cur;way[j]=j0
    if mins[j]<delta:delta=mins[j];j1=j
   for j in range(n+1):
    if used[j]:u[p[j]]+=delta;v[j]-=delta
    else:mins[j]-=delta
   j0=j1
   if p[j0]==0:break
  while j0:j1=way[j0];p[j0]=p[j1];j0=j1
 return {p[j]-1:j-1 for j in range(1,n+1)}
for key,ids in groups.items():
 sites=[dict(rows[i]) for i in ids];points=[(r['x']+.51*round(math.cos(math.radians(r['rotation']))),r['y']+.51*round(math.sin(math.radians(r['rotation'])))) for r in sites]
 costs=[[math.hypot(rows[i]['targetX']-x,rows[i]['targetY']-y) for x,y in points] for i in ids];limits=sorted(set(v for row in costs for v in row));lo=0;hi=len(limits)-1
 while lo<hi:
  mid=(lo+hi)//2
  if matching(costs,limits[mid]) is not None:hi=mid
  else:lo=mid+1
 limit=limits[lo]+.05;assignment=hungarian([[d+.15*d*d if d<=limit else 1e6 for d in row] for row in costs])
 for i,j in assignment.items():
  r=rows[ids[i]];site=sites[j]
  for k in ['x','y','rotation','nearestPowerViaMm','nearestGroundViaMm']:r[k]=site[k]
  r['padToBallMm']=round(costs[i][j],4)
 print(key,'max',round(max(r['padToBallMm'] for r in sites),3),'->',round(max(rows[i]['padToBallMm'] for i in ids),3))
report['assignmentRefinement']='Minimum worst-case matching within each chip/supply rail, followed by minimum weighted distance among the accepted assignments. Identical 100 nF capacitor sites are exchanged without changing the occupied geometry.'
p.write_text(json.dumps(report,indent=2)+'\n');Path('design/decoupling-placement.json').write_text(json.dumps({r['name']:{k:r[k] for k in ['x','y','rotation']} for r in rows},indent=2)+'\n')
print('Mean',round(statistics.mean(r['padToBallMm'] for r in rows),3),'max',max(r['padToBallMm'] for r in rows))