各位 EDA lab 的同学: 打搅了, 希望你们能来捧场 (听说你们老师也有动员, 是吧?). Thanks, - Ric 作者: ric2k1 (Ric) 看板: NTUGIEE_EDA 标题: [提醒] 明天 (二) 2pm 的演讲 时间: Mon Dec 18 18:05:11 2006 ※ [本文转录自 NTUGIEE_ric 看板] 作者: ric2k1 (Ric) 看板: NTUGIEE_ric 标题: [提醒] 明天 (二) 2pm 的演讲 时间: Mon Dec 18 18:04:10 2006 没课的同学请务必来听演讲, 免得变成我跟 speaker 的 one-to-one meeting... -------------------------------------------------------------------- Time: 12/19 (Tue), 2:00pm Place: BL 114 Speaker: Prof. David Wu Topic: Somce pondering on Relative Flexibility: Can this century-old Go Game teaching lead to some new thoughts for combinatorial optimization strategies? Abstract Ancient Chinese Go Game players and professional masons shared two things in common. They were both facing NP-hard problems, and they all happened to follow a same old teaching firstly found in the centuries old Chinese Go Game book (棋经): “Golden are the corners; Silvery are the sides; and strawy are the interiors (金角银边草肚皮)”. Bizarre it might sound at the first glance, but it is a principle survives for long years. This working teaching seems concealing some hidden combinatorial optimization philosophy accumulated along thousands of years’ practice: a notion of Relative Flexibility. Inspired by this notion, we invented a so-called Less Flexibility First (微机优先) optimization principle and designed corresponding heuristics for the 2D rectangle packing and Stock Cutting problems. The results are nearly surprising. E.g., among the 21 benchmarks of Stock Cutting, under low run time, optimum solutions of 12 cases are obtained (a thing never heard of from all other methods), and 18 cases reach packing density over 99%. This heuristic, though deterministic, even outperforms all well known conventional stochastic 2D packing and VLSI floor planning heuristics upon both public benchmarks and randomly generated very tough examples on both running time and packing densities. And particularly, for the "very hard" floorplanning examples (with all rectangles with aspect ratio of 6~11), the LFF demonstrated its robust "immunity", compared to the vulnerability of the Annealing method. In this talk, we would post this wondering: what and why makes this idea working so well in the test problems and if it can be adapted to help solving other hard problems. Short Bio: Dr. Yu-Liang (David) Wu received the Ph.D. degree in Electrical and Computer Engineering from University of California at Santa Barbara in 1994. On 1985, he worked in Internet Systems Corporation as a system programmer on network communication protocols (DARPA TCP/IP, Telnet). From 1986 to 1988, he worked at AT&T Bell Labs on the development of several telephone operation systems. >From 1988 to 1989, he worked for Amdahl Corporation on tester software designs for super computers. Before he joined the Chinese University of Hong Kong in January 1996, he had worked at Cadence Design Systems Incorporation as a senior MTS since December 1994, where he worked in the R&D of the silicon synthesis product (PBS) targeting at binding the gap between logic and physical level optimizations for deep-submicron chip designs. His current research interests majorly relate to optimization of logic and physical design automation of VLSI circuits and FPGA related CAD tool designs and architectural analysis/optimization. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.121.134.49 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.21.240 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.21.240 ※ 编辑: ric2k1 来自: 140.112.21.240 (12/18 18:07)