集成电路通道布线数学建模
- 格式：docx
- 大小：18.98 KB
- 文档页数：15
集成电路通道布线数学建模：集成电路通道布线中脚标拥堵问题集成电路是利用半导体技术把电子元件集成在一起的具有特定功能的电路，已广泛应用于生产生活的方方面面。
随着技术的发展，集成电路内部的元器件数目已达到十亿级别，需要借助专用计算机软件才能完成电路设计与实现，该类软件统称为电子设计自动化（Electronic Design Automation,EDA）工具。
集成电路设计由多个阶段组成，其中一个重要阶段称为“物理设计”，先将器件摆放在合适的位置，然后用金属线连接器件实现连接关系。
其中，后者称为“布线”，它是EDA工具需要解决的重要问题。
简单而言，假设可用区域由m*n个方格组成，金属线允许沿着直线或直角（方格）放置，连接指定的方格（引脚）而不引起断路或短路，该过程称为“布线”。
由于金属线引入的寄生电阻会影响电路性能，所以需要最小化布线长度。
本题重点考虑“布线”问题中的一个特例：“通道布线”。
“通道”是指一个横向的布线区域，此区域的顶部和底部分布着需要连接的方格，需用金属线将相应的引脚连通起来。
（1）假设采用一层金属布线，那么已经布线的方格被锁定，不允许其它线路穿过，否则会形成短路。
图1所示为采用一层金属的通道布线例子，布线空间为，空间上下沿的数字分别对应方格的引脚编号，编号相同的引脚需要连接起来。
由于空间限制，角标拥堵导致无解，是布线无解的原因之一。
请针对一层金属的“通道布线”问题完成建模和求解，给出角标拥堵导致无解的条件和两三个例子。
（2）引脚标号不变的条件下，将替换（等于5或6或者更大）看是否有解。
在这里插入图片描述（3）可以观察得到，有些测例无法采用一层金属完成布线。
实际中，集成电路会采用多个金属层，不同的金属层处在不同的高度，相邻层之间需要用通孔连通，这样不同金属层可共用一个方格而不引起短路。
图2所示为芯片的剖面图，其中网状填充为金属层，点状填充为通孔。
图3所示为一个用两层金属的布线示例，其中蓝色为下层金属，黄色为上层金属，红色为通孔。
但是一个通孔的电阻等于5个方格的导线，请使用2层金属对“通道布线”对的脚标拥堵无法求解的问题，采用多层布局重新建模和求解，最小电阻和问题2最小电阻进行对比。
在这里插入图片描述注符号意义N布线区域的宽度K总的引脚对数i第i对引脚A_i第i对引脚的上引脚坐标B_i第i对引脚的下引脚坐标假设上引脚坐标从左至右按顺序编号假设两层金属版无差异*问题1和问题2启发思路我们使用A*算法1详细Python代码和解释请看这个大佬的帖子https:///Python_Matlab/article/details/1064 69362看了上面的帖子代码，你可能会理解是否有无解跟脚标顺序存在关联，不存在长宽的关系，所以检验有无解也就是检验上下脚标顺序是否按顺序排列。
如果你不明白为什么布线拥堵是和脚标有关系建议作图去理解~*0-1规划思路我们对有解情况进行求最小布线距离。
对布线的区域赋值为1未布线的区域赋值为0那d=sum（y)=｛x=1｝y∈（m,n）｛x=0｝方法二是否有解采取同样的解决方法而对于有解的距离计算采用曼哈顿距离公式进行推演在这里插入图片描述方法二的Matlab代码1. clc;clear2. Ai=[1 4 7 8 10 12 14];%输入上脚标坐标3. Bi=[1 2 8 5 13 11 15];%输入下脚标坐标4. a=sort(Bi);%对矩阵进行升序排序5. n=input('请输入n的数值');%输入宽度6. l=input('请输入l的数值');%输入长度7. K=sum(sum(Bi~=0));%K为Bi中非零元素数8. kuandu=['宽度',num2str(n)];9. disp(kuandu)10. changdu=['长度',num2str(l)];11. disp(changdu)12. duishu=['脚标对数',num2str(K)];13. disp(duishu)14. shangjiaobiao=['上引脚坐标',num2str(Ai)];15. disp(shangjiaobiao)16. xiajiaobiao=['下引脚坐标',num2str(Bi)];17. disp(xiajiaobiao)18. if a==Bi%如果排序矩阵跟原矩阵相同19. i=sym('i');%定义i20. ANS=abs(Ai-Bi);21. ANS1=sum(ANS);22. ANS2=n*K;23. d=ANS2+ANS1;24. Rmin=['最短布线长度',num2str(d)];25. disp(Rmin)26. else27. msgbox("无解")%输出无解28. end1234567891011121314151617181920212223242526272829问题3对于问题3的双层解决问题决定使第一层布线数在不拥堵的情况下达到最大，并且将剩余的布线放置到第二层，也就是将双层布线问题转化成两个一层布线问题，对于第二层脚标拥堵沿用第一问的解决方法，若第二层布线拥堵，则说明该情况在双层布线中无解。
如何使得第一层布线在不拥堵的情况下还能达到最大呢？让第一层的引脚对数达到顺序排列最大，将剩余脚标对放置到第二层。
对于如何筛选脚标对数则分别使用了贪婪算法和二分排序法进行筛选。
贪婪算法Python代码如下1. arrayLen=int(input())#数组长度2.3.4. list=[]#数组15. list2=[]#数组26.7. Temporaryarray1=[]#暂存8. Temporaryarray2=[]9.10. end_list=-111.12. list=input().split()13. list2=input().split()14.15.16. for i in range(arrayLen):17. list[i]=int(list[i])18. list2[i]=int(list2[i])#将字符变为数字19.20.21. for i in range(arrayLen-1):22. if(list[end_list-1]>list[end_list]):23. Temporaryarray1.append(list.pop(end_list-1))24. Temporaryarray2.append(list2.pop(end_list-1))25. else:26. end_list=end_list-127. print(list)28. print(list2)29.30. print()31. print(Temporaryarray1[::-1])32. print(Temporaryarray2[::-1])123456791011121314151617181920212223242526272829313233控制台输入的是数组长度上角标下角标例如数组长度是5上角标2 1 3 5 4下角标6 7 9 8 10那么输入52 13 5 46 7 9 8 10二分排序法Matlab代码如下1. function[s1,s2]=erfenpaixu(data)2. %data=[100 2 6 9 5 7 8 13 11 12];3. chang=length(data);4. for i=1:chang5. route(i)=0;6. end7. len=[];8.9. max_len=0;10. len(1)=1;11. for i=2:length(data)12. len(i)=1;13. route(route>=0)=0;14. for j=1:i-115. if(data(j)<data(i)&&(len(j)+1)>len(i))16. len(i)=len(j)+1;17. end18. end19. if(len(i)>max_len)20. %s1_temp=[s1_temp data(j)];21. max_len=len(i);22. end23.24. end25. max_len;26.27. max_select=max(len);28. s1=[];29. s2=[];30. for i=1:max_select31.32. ind=find(len==i);33. temp=min(data(ind));34. s1=[s1,temp];35.36. end37.38. for i=1:length(data)39. if~ismember(data(i),s1)40. s2=[s2,data(i)];41. end42. end43.44. s1;%第一层下脚标45. s2;%第二层下脚标46. %利用二分排序法进行筛选数据1234567810111213141516171819202122232425262728293032333435363738394041424344454647data=[具体数值]控制台输入如果需要调用筛选后的数据控制台输入[s1,s2]=erfenpaixu(data)%调用指令***缺陷问题对于以上问题的解决存在某种不具有实际意义的脚标排序情况如在4*7的布线空间中上脚标2 3 4 5 6下脚标6 7 8 9 10虽然其也是按照顺序排列但是其依然无解A这里插入图片描述其中Ai为上引脚坐标n为宽度Bi为下引脚坐标也就是说如果符合该公式其布线依然拥堵，题目依然无解。
当然这个公式只是一种数学猜想，希望读者们自己进行数据检验并提出改进空间。
