AbstractGlobal routing in VLSI (ver

Abstract
Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on an integer programming formulation. The algorithm features a theoretical approximation bound while ensuring all the routing demands are concurrently satisfied. We provide both a serial and a parallel implementation as well as develop several heuristics to improve the quality of the solution and reduce running time. Our computational results on a well-known benchmark set show that, combined with certain heuristics, our new algorithms perform extremely well compared with other integer programming approaches. 1

ผลลัพธ์ (ไทย) 1:

นามธรรม
เส้นทางทั่วโลกใน VLSI (ขนาดใหญ่มากบูรณาการ) การออกแบบเป็นหนึ่งในความท้าทายที่สุดปัญหาการเพิ่มประสิทธิภาพต่อเนื่องในทฤษฎีการคำนวณและการปฏิบัติ ในบทความนี้เรานำเสนอขั้นตอนวิธีการเวลาพหุนามสำหรับปัญหาการกำหนดเส้นทางทั่วโลกขึ้นอยู่กับการกำหนดโปรแกรมจำนวนเต็มอัลกอริทึมมีการประมาณทฤษฎีผูกพันในขณะที่การสร้างความมั่นใจทุกความต้องการของเส้นทางมีความพึงพอใจที่เห็นพ้องกัน เราให้ทั้งแบบอนุกรมและแบบขนานการดำเนินการเช่นเดียวกับการพัฒนาหลายวิเคราะห์พฤติกรรมในการปรับปรุงคุณภาพของการแก้ปัญหาและลดเวลาในการทำงาน ผลการคำนวณของเราในการที่รู้จักกันดีการแสดงชุดมาตรฐานที่รวมกับการวิเคราะห์พฤติกรรมบางอย่างอัลกอริทึมใหม่ของเราดำเนินการเป็นอย่างดีเมื่อเทียบกับวิธีการเขียนโปรแกรมจำนวนเต็มอื่น ๆ 1

ผลลัพธ์ (ไทย) 2:

นามธรรม
สายสากลในการออกแบบ VLSI (รวมการขนาดใหญ่มาก) เป็นหนึ่งในปัญหาเพิ่มประสิทธิภาพเดี่ยว ๆ สุดท้าทายในทฤษฎีการคำนวณ ในเอกสารนี้ เรานำอัลกอริทึมเวลาโพลิโนเมียปัญหาสายส่วนกลางตามกำหนดการเขียนจำนวนเต็ม ลักษณะการทำงานอัลกอริทึมที่ผูกประมาณทฤษฎีขณะที่ความต้องการสายงานการผลิตทั้งหมดมั่นใจพร้อมความพึงพอใจ เรามีทั้งประจำการและดำเนินการควบคู่กัน ตลอดจนพัฒนาลองผิดลองถูกหลายเพื่อปรับปรุงคุณภาพของการแก้ปัญหา และลดเวลาทำงาน ผลคำนวณของเราบนมาตรฐานรู้จักตั้งแสดงนั้น พร้อมกับลองผิดลองถูกบาง อัลกอริทึมของเราใหม่ทำดีมากเมื่อเทียบกับจำนวนเต็มอื่น ๆ วิธีการเขียนโปรแกรม 1

ผลลัพธ์ (ไทย) 3:

เป็นนามธรรม
ระดับโลกในการเราติ้ง vlsi (การประกอบเป็นอย่างมากขนาดใหญ่)การออกแบบเป็นหนึ่งในปัญหาการปรับแต่งแบบแยกต่างหากที่ท้าทายที่สุดในการปฏิบัติและทฤษฎีนวัตกรรม ในเอกสารนี้เรามีอัลกอริธึมเวลา polynomial สำหรับปัญหาการเราติ้งระดับโลกที่ขึ้นอยู่บนพื้นฐานหลักการตั้งโปรแกรมจำนวนเต็มที่อัลกอริธึมที่โดดเด่นไปด้วยประมาณในเชิงทฤษฎีที่ผูกพันในขณะที่มีความมั่นใจได้ความต้องการการเราติ้งทั้งหมดได้รับความพอใจได้พร้อมกัน เราจัดให้บริการแบบอนุกรมและการนำไปใช้งานแบบขนานและพัฒนา Heuristics หลายอย่างเพื่อปรับปรุง คุณภาพ ของโซลูชันและลดเวลาการทำงาน ผลการค้นหานวัตกรรมของเราที่ตั้งค่าการวัด ประสิทธิภาพ ที่รู้จักกันดีว่าเมื่อรวมกับ Heuristics บางอย่างอัลกอริธึมแห่งใหม่ของเราทำเป็นอย่างมากเมื่อเทียบกับวิธีการตั้งโปรแกรมอื่นๆจำนวนเต็ม 1