计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2014年
3期
287-293
,共7页
现场可编程门阵列%多线程%布线%高扇出线网%低扇出线网%边界框图%确定性
現場可編程門陣列%多線程%佈線%高扇齣線網%低扇齣線網%邊界框圖%確定性
현장가편정문진렬%다선정%포선%고선출선망%저선출선망%변계광도%학정성
Field Programmable Gate Array(FPGA)%multi-thread%wiring%high fanout nets%low fanout nets%boundary diagram%deterministic
针对在现场可编程门阵列(FPGA)软件系统中大规模电路设计布线时间较长的问题，提出一种基于线网引脚位置划分且具有平台独立性的多线程 FPGA 布线算法。对高扇出线网采用将单根线网拆分成子线网并同时布线的方法，对低扇出线网采用选择若干位置不相交叠的线网进行同时布线的方法，给出线网边界框图的数据结构来缩短选择若干低扇出线网的时间，采取负载平衡机制和同步措施，分别提高布线效率和保证布线结果的确定性。实验结果证明，在Intel 4核处理器平台上，与单线程VPR算法相比，该并行算法的平均布线效率提高了90%，平均布线质量下降不超过2.3%，并能够得到确定的布线结果，在EDA方面具有重要的理论与实用价值。
針對在現場可編程門陣列(FPGA)軟件繫統中大規模電路設計佈線時間較長的問題，提齣一種基于線網引腳位置劃分且具有平檯獨立性的多線程 FPGA 佈線算法。對高扇齣線網採用將單根線網拆分成子線網併同時佈線的方法，對低扇齣線網採用選擇若榦位置不相交疊的線網進行同時佈線的方法，給齣線網邊界框圖的數據結構來縮短選擇若榦低扇齣線網的時間，採取負載平衡機製和同步措施，分彆提高佈線效率和保證佈線結果的確定性。實驗結果證明，在Intel 4覈處理器平檯上，與單線程VPR算法相比，該併行算法的平均佈線效率提高瞭90%，平均佈線質量下降不超過2.3%，併能夠得到確定的佈線結果，在EDA方麵具有重要的理論與實用價值。
침대재현장가편정문진렬(FPGA)연건계통중대규모전로설계포선시간교장적문제，제출일충기우선망인각위치화분차구유평태독립성적다선정 FPGA 포선산법。대고선출선망채용장단근선망탁분성자선망병동시포선적방법，대저선출선망채용선택약간위치불상교첩적선망진행동시포선적방법，급출선망변계광도적수거결구래축단선택약간저선출선망적시간，채취부재평형궤제화동보조시，분별제고포선효솔화보증포선결과적학정성。실험결과증명，재Intel 4핵처리기평태상，여단선정VPR산법상비，해병행산법적평균포선효솔제고료90%，평균포선질량하강불초과2.3%，병능구득도학정적포선결과，재EDA방면구유중요적이론여실용개치。
A platform-independent multi-thread routing method for FPGA is proposed to reduce long compiling times of large design in Field Programmable Gate Array(FPGA) software system. Specifically, the proposed method includes two aspects for maximal paralleli-zation. For high fanout nets, each is partitioned into several subnets to be routed in parallel. Low fanout nets with non-overlapping boundary diagrams are identified and routed in parallel. A new graph, named boundary diagram, is constructed to facilitate the process of selecting low fanout nets to be routed concurrently. In addition, load balancing strategies and synchronization mechanisms are introduced to promote routing efficiency and ensure deterministic results. Experimental results on Intel quad-core processor platforms show that, this technique improves the average routing efficiency by 90%with routing quality degrading by no more than 2.3%and provides deterministic results, which has great theoretical and practical value in EDA field.
