Ein Branch&Bound-Ansatz zur Verdrahtung von Field Programmable Gate-Arrays

Authors: 
Möhrke, Ulrich
Herrmann, Paul
Steffen, M.
Spruth, Wilhelm G.
Year: 
1998
Language: 
German
Abstract: 
Zur Verdrahtung der meisten FPGA-Architekturen können die aus dem ASIC-Entwurf stammenden Werkzeuge wie z.B. Kanalverdrahter nicht eingesetzt werden. Eine vollautomatische Verdrahtung mit optimalen Signallaufzeiten kann nur dann erreicht werden, wenn bei gegebener Plazierung die Leitungführung den technologischen Gegebenheiten angepaßt wird. Diese unterscheiden sich deutlich von denen in ASICs. Im Rahmen des von der Deutschen Forschungsgemeinschaft (DFG) geförderten Gemeinschafts-Projekts 'FPGA Entwurfssystem', an dem die Universität Leipzig, die Universität Tübingen und die Technische Universität München beteiligt sind, wurden am Lehrstuhl für Computersysteme (Prof. W.G. Spruth) des Instituts für Informatik der Universität Leipzig Verfahren zur effizienten und qualitativ hochwertigen Verdrahtung von FPGA-Bausteinen entwickelt. Es wird eine Beschreibung des Verdrahtungsproblems für FPGAs gegeben und ein Lösungsansatz mit Hilfe des Branch&Bound- Verfahrens vorgestellt. Die Ergebnisse in Form von Programmlaufzeiten, Länge des kritischen Pfades und Anzahl der betrachteten Suchknoten in Abhängigkeit von einer Vielzahl von Schaltungsvarianten sind tabellarisch dargestellt und dokumentieren eine deutliche Verkürzung der längsten Pfade gegenüber dem Plazier- und Verdrahtungswerkzeug von Xilinx. Abschließend werden Probleme und weiterführende Arbeiten diskutiert.
Appeared / Erschienen in: 
Report Nr. 5/1998 des Institutes für Informatik der Universität Leipzig
Pubdate / Erscheinungsdatum: 
1998
Pages / Seitenanzahl: 
12
AttachmentSize
1998-67.pdf102.62 KB