11.2 Timing and Power Driven Physical Design

Time	Label	Presentation Title Authors
14:00	11.2.1	(Best Paper Award Candidate) A FAITHFUL BINARY CIRCUIT MODEL WITH ADVERSARIAL NOISE Speaker: Jürgen Maier, TU Wien, AT Authors: Matthias Fuegger¹, Jürgen Maier², Robert Najvirt², Thomas Nowak³ and Ulrich Schmid² ¹LSV, CNRS & ENS Paris-Saclay, FR; ²TU Wien, AT; ³Universite Paris Sud, FR Abstract Accurate delay models are important for static and dynamic timing analysis of digital circuits, and mandatory for formal verification. However, Függer et al. [IEEE TC 2016] proved that pure and inertial delays, which are employed for dynamic timing analysis in state-of-the-art tools like ModelSim, NC-Sim and VCS, do not yield faithful digital circuit models. Involution delays, which are based on delay functions that are mathematical involutions depending on the previous-output-to-input time offset, were introduced by Függer et al. [DATE'15] as a faithful alternative (that can easily be used with existing tools). Although involution delays were shown to predict real signal traces reasonably accurately, any model with a deterministic delay function is naturally limited in its modeling power. In this paper, we thus extend the involution model, by adding non-deterministic delay variations (random or even adversarial), and prove analytically that faithfulness is not impaired by this generalization. Albeit the amount of non-determinism must be considerably restricted to ensure this property, the result is surprising: the involution model differs from non-faithful models mainly in handling fast glitch trains, where small delay shifts have large effects. This originally suggested that adding even small variations should break the faithfulness of the model, which turned out not to be the case. Moreover, the results of our simulations also confirm that this generalized involution model has larger modeling power and, hence, applicability. Download Paper (PDF; Only available from the DATE venue WiFi)
14:30	11.2.2	EVT-BASED WORST CASE DELAY ESTIMATION UNDER PROCESS VARIATION Speaker: Charalampos Antoniadis, University of Thessaly, GR Authors: Charalampos Antoniadis, Dimitrios Garyfallou, Nestor Evmorfopoulos and Georgios Stamoulis, University of Thessaly, GR Abstract Manufacturing process variation in sub-20nm processes has introduced ever increasing overhead in Static Timing Analysis (STA) in order to guarantee the reliable operation of the circuit. Chip designers apply corner-based analysis and add guard-bands to design parameters in order to take into account the impact of process variation on timing. However, the aforementioned techniques are either too slow as the number of design parameters proliferates with the integration of more components into a chip or inaccurate due to the assumption that the worst case delay resides at the corners of design parameters. In this paper, we present a novel statistical methodology, which relies on Extreme Value Theory (EVT), to estimate the worst case delay of VLSI circuits under variations in gate/interconnect parameters. Despite the previous statistical approaches toward maximum delay estimation, our methodology can be applied regardless of the underlying gate/interconnect delay model or any assumption about the distribution of the Arrival Time (AT) at every circuit node, making it very appealing for integration to any level of timing analysis abstraction (from spice-to-gate level) and provide fast yet accurate results. Experimental results on ISCAS85/ISCAS89 circuits show that the estimated maximum AT at the Primary Outputs (POs) can be within 5% of the true maximum AT, at the cost of a few thousand Monte Carlo simulations. Download Paper (PDF; Only available from the DATE venue WiFi)
15:00	11.2.3	CO-SYNTHESIS OF FLOORPLANNING AND POWERPLANNING IN 3D ICS FOR MULTIPLE SUPPLY VOLTAGE DESIGNS Speaker: Jhih-Ying Yang, Department of Electrical Engineering, National Cheng Kung University, TW Authors: Jai-Ming Lin, Chien-Yu Huang and Jhih-Ying Yang, Department of Electrical Engineering, National Cheng Kung University, TW Abstract This paper addresses a 3D floorplanning methodology, which considers floorplanning and powerplanning at the same time for Multiple Supply Voltage (MSV) circuits. Physical design becomes more complex for MSV designs since modules with the same power domain have to be placed at close locations in 3D space to facilitate powerplanning and reduce IR-drop, which would deteriorate wirelength. By properly partitioning modules of the same power domain into several voltage islands and increasing overlap area of the voltage islands in contiguous dies, we can reduce routing resource usage without increasing wirelength significantly. Further, unlike previous works, our approach not only can handle a netlist with soft modules and hard modules but also can meet the fixed-outline constraint. The experimental results show that our methodology gets better results than other approach in designs with single voltage domain and is also promising for MSV designs. Download Paper (PDF; Only available from the DATE venue WiFi)
15:15	11.2.4	ACCELERATE ANALYTICAL PLACEMENT WITH GPU: A GENERIC APPROACH Speaker: Martin D. F. Wong, University of Illinois Urbana-Champaign, US Authors: Chun-Xun Lin and Martin Wong, University of Illinois at Urbana-Champaign, US Abstract This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation. Download Paper (PDF; Only available from the DATE venue WiFi)
15:30	IP4-17, 425	GENERAL FLOORPLANNING METHODOLOGY FOR 3D ICS WITH AN ARBITRARY BONDING STYLE Speaker: Chien-Yu Huang, Department of Electrical Engineering, National Cheng Kung University, TW Authors: Jai-Ming Lin and Chien-Yu Huang, Department of Electrical Engineering, National Cheng Kung University, TW Abstract This paper proposes a general floorplanning methodology which can be applied to 3D ICs with an arbitrary bonding style. Some researches have shown that a 3D IC with the hybrid bonding style, which includes face-to-back and face-to-face, may obtain better results than that simply using the face-to-back bonding style. We respectively present an approach to assign modules to tiers for each kind of bonding style. Further, a new utilization function, called cosine-shaped function, is proposed to estimate utilizations of bins required by the analytical-based approach. Our experimental results show the cosine shaped function can obtain a little better result than the bell-shaped function on IBM benchmarks for 2D floorplanning. We also show that the proposed 3D floorplanning methodology consumes less TSVs and induces shorter wirelength compared to previous work in the hybrid bonding style. Download Paper (PDF; Only available from the DATE venue WiFi)
15:31	IP5-1, 932	A PLACEMENT ALGORITHM FOR SUPERCONDUCTING LOGIC CIRCUITS BASED ON CELL GROUPING AND SUPER-CELL PLACEMENT Speaker: Massoud Pedram, University of Southern California, US Authors: Soheil Nazar Shahsavani, Alireza Shafaei Bejestan and Massoud Pedram, University of Southern California, US Abstract This paper presents a novel clustering based placement algorithm for single flux quantum (SFQ) family of superconductive electronic circuits. In these circuits nearly all cells receive a clock signal and a placement algorithm that ignores the clock routing cost will not produce high quality solutions. To address this issue, proposed approach simultaneously minimizes the total wirelength of the signal nets and area overhead of the clock routing. Furthermore, construction of a perfect H-tree in SFQ logic circuits is not viable solution due to the resulting very high routing overhead and the in-feasibility of building exact zero-skew clock routing trees. Instead a hybrid clock tree must be used whereby higher levels of the clock tree (i.e., those closer to the clock source) are based on H-tree construction whereas lower levels of the clock tree follow a linear (i.e., chain-like) structure. The proposed approach is able to reduce the overall half-perimeter wirelength by 15% and area by 8% compared with state-of-the-art techniques. Download Paper (PDF; Only available from the DATE venue WiFi)
15:32	IP5-2, 851	ABAX: 2D/3D LEGALISER SUPPORTING LOOK-AHEAD LEGALISATION AND BLOCKAGE STRATEGIES Speaker: Nikolaos Sketopoulos, University of Thessaly, GR Authors: Nikolaos Sketopoulos, Christos Sotiriou and Stavros Simoglou, Department of Electrical and Computer Engineering, University of Thessaly, GR Abstract Abax is a modern version of the classical Abacus, minimum displacement, greedy legaliser. Abax supports single-tier 2D or 3D legalisation for multiple, logic-on-logic 3D-IC tiers, efficient look-ahead legalisation of intermediate Global Placement (GP) iterations, Hard Macros, Blockages, row density constraints and multiple local cell displacement functions and cell orderings. For 3D-IC, Abax can produce multi-tier 3D-IC placements by performing Legalisation-based Partitioning. For efficient Look-ahead Legalisation, Abax supports two new local displacement cost functions, multi-cell mean and multi-cell total. We show that the classical single-cell displacement and multi-cell total can result in artifacts when legalising early intermediate GPs, and that multi-cell mean is the best candidate for Look-ahead Legalisation. Obstructions, i.e. Hard Macros and Blockages are handled by using two strategies. We present legalisation results for the ISPD2014 and ISPD2015 benchmarks, by using GP generated from Eh?Placer, and HPWL measurement by using RippleDP. For 3D, two-tier legalisation we illustrate a ~30% reduction in HPWL for a set of ISPD2014 benchmarks. For 2D legalisation on the ISPD2015 benchmarks, our average HPWL increase over GP is 3.03%, compared to 7.21% of the Eh?Placer legaliser, and 43.16% of the RippleDP legaliser. Download Paper (PDF; Only available from the DATE venue WiFi)
15:33	IP5-3, 864	LESAR: A DYNAMIC LINE-END SPACING AWARE DETAILED ROUTER Speaker: Yih-Lang Li, Computer Science Department, NCTU, TH Authors: Ying-Chi Wei, Radhamanjari Samanta and Yih-Lang Li, National Chiao-Tung University, TW Abstract As the VLSI technology scales down, 193nm optical lithography reaches the limit and one-dimensional (1D) unidirectional style lithography technique emerges as one of the most promising solutions for coming advanced technology nodes. The 1D process first generates unidirectional dense metal lines and then use line-end cutting to form the target patterns with cut masks. If cuts are too close, they will lead to conflicts. Line-end spacing rules become dynamic rather than static because of cut mask and also now need to be followed strictly. Line-end spacing check between two line-end pairs in the same mask has also been regarded as compulsory line-end spacing constraints that have not discussed in previous works yet. Complying with these rules during APR has become a new bottleneck. In this work, we propose to make the router aware of the dynamic line-end spacing rules, including end-end spacing and parity spacing constraints. Experimental results of our proposed router demonstrates that it can effectively expel all end-end spacing violations as well as 75% of parity spacing violations in a reasonable runtime increase of 14%. Download Paper (PDF; Only available from the DATE venue WiFi)
15:30		End of session Coffee Break in Exhibition Area Coffee Breaks in the Exhibition Area On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area (Terrace Level of the ICCD). Lunch Breaks (Großer Saal + Saal 1) On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the rooms "Großer Saal" and "Saal 1" (Saal Level of the ICCD) to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area. Tuesday, March 20, 2018 Coffee Break 10:30 - 11:30 Lunch Break 13:00 - 14:30 Awards Presentation and Keynote Lecture in "Saal 2" 13:50 - 14:20 Coffee Break 16:00 - 17:00 Wednesday, March 21, 2018 Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:30 Awards Presentation and Keynote Lecture in "Saal 2" 13:30 - 14:20 Coffee Break 16:00 - 17:00 Thursday, March 22, 2018 Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:00 Keynote Lecture in "Saal 2" 13:20 - 13:50 Coffee Break 15:30 - 16:00

Time

Label

Presentation Title
Authors

14:00

11.2.1

(Best Paper Award Candidate)
A FAITHFUL BINARY CIRCUIT MODEL WITH ADVERSARIAL NOISE
Speaker:
Jürgen Maier, TU Wien, AT
Authors:
Matthias Fuegger¹, Jürgen Maier², Robert Najvirt², Thomas Nowak³ and Ulrich Schmid²
¹LSV, CNRS & ENS Paris-Saclay, FR; ²TU Wien, AT; ³Universite Paris Sud, FR
Abstract
Accurate delay models are important for static and dynamic timing analysis of digital circuits, and mandatory for formal verification. However, Függer et al. [IEEE TC 2016] proved that pure and inertial delays, which are employed for dynamic timing analysis in state-of-the-art tools like ModelSim, NC-Sim and VCS, do not yield faithful digital circuit models. Involution delays, which are based on delay functions that are mathematical involutions depending on the previous-output-to-input time offset, were introduced by Függer et al. [DATE'15] as a faithful alternative (that can easily be used with existing tools). Although involution delays were shown to predict real signal traces reasonably accurately, any model with a deterministic delay function is naturally limited in its modeling power. In this paper, we thus extend the involution model, by adding non-deterministic delay variations (random or even adversarial), and prove analytically that faithfulness is not impaired by this generalization. Albeit the amount of non-determinism must be considerably restricted to ensure this property, the result is surprising: the involution model differs from non-faithful models mainly in handling fast glitch trains, where small delay shifts have large effects. This originally suggested that adding even small variations should break the faithfulness of the model, which turned out not to be the case. Moreover, the results of our simulations also confirm that this generalized involution model has larger modeling power and, hence, applicability.
Download Paper (PDF; Only available from the DATE venue WiFi)

14:30

11.2.2

EVT-BASED WORST CASE DELAY ESTIMATION UNDER PROCESS VARIATION
Speaker:
Charalampos Antoniadis, University of Thessaly, GR
Authors:
Charalampos Antoniadis, Dimitrios Garyfallou, Nestor Evmorfopoulos and Georgios Stamoulis, University of Thessaly, GR
Abstract
Manufacturing process variation in sub-20nm processes has introduced ever increasing overhead in Static Timing Analysis (STA) in order to guarantee the reliable operation of the circuit. Chip designers apply corner-based analysis and add guard-bands to design parameters in order to take into account the impact of process variation on timing. However, the aforementioned techniques are either too slow as the number of design parameters proliferates with the integration of more components into a chip or inaccurate due to the assumption that the worst case delay resides at the corners of design parameters. In this paper, we present a novel statistical methodology, which relies on Extreme Value Theory (EVT), to estimate the worst case delay of VLSI circuits under variations in gate/interconnect parameters. Despite the previous statistical approaches toward maximum delay estimation, our methodology can be applied regardless of the underlying gate/interconnect delay model or any assumption about the distribution of the Arrival Time (AT) at every circuit node, making it very appealing for integration to any level of timing analysis abstraction (from spice-to-gate level) and provide fast yet accurate results. Experimental results on ISCAS85/ISCAS89 circuits show that the estimated maximum AT at the Primary Outputs (POs) can be within 5% of the true maximum AT, at the cost of a few thousand Monte Carlo simulations.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:00

11.2.3

CO-SYNTHESIS OF FLOORPLANNING AND POWERPLANNING IN 3D ICS FOR MULTIPLE SUPPLY VOLTAGE DESIGNS
Speaker:
Jhih-Ying Yang, Department of Electrical Engineering, National Cheng Kung University, TW
Authors:
Jai-Ming Lin, Chien-Yu Huang and Jhih-Ying Yang, Department of Electrical Engineering, National Cheng Kung University, TW
Abstract
This paper addresses a 3D floorplanning methodology, which considers floorplanning and powerplanning at the same time for Multiple Supply Voltage (MSV) circuits. Physical design becomes more complex for MSV designs since modules with the same power domain have to be placed at close locations in 3D space to facilitate powerplanning and reduce IR-drop, which would deteriorate wirelength. By properly partitioning modules of the same power domain into several voltage islands and increasing overlap area of the voltage islands in contiguous dies, we can reduce routing resource usage without increasing wirelength significantly. Further, unlike previous works, our approach not only can handle a netlist with soft modules and hard modules but also can meet the fixed-outline constraint. The experimental results show that our methodology gets better results than other approach in designs with single voltage domain and is also promising for MSV designs.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:15

11.2.4

ACCELERATE ANALYTICAL PLACEMENT WITH GPU: A GENERIC APPROACH
Speaker:
Martin D. F. Wong, University of Illinois Urbana-Champaign, US
Authors:
Chun-Xun Lin and Martin Wong, University of Illinois at Urbana-Champaign, US
Abstract
This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:30

IP4-17, 425

GENERAL FLOORPLANNING METHODOLOGY FOR 3D ICS WITH AN ARBITRARY BONDING STYLE
Speaker:
Chien-Yu Huang, Department of Electrical Engineering, National Cheng Kung University, TW
Authors:
Jai-Ming Lin and Chien-Yu Huang, Department of Electrical Engineering, National Cheng Kung University, TW
Abstract
This paper proposes a general floorplanning methodology which can be applied to 3D ICs with an arbitrary bonding style. Some researches have shown that a 3D IC with the hybrid bonding style, which includes face-to-back and face-to-face, may obtain better results than that simply using the face-to-back bonding style. We respectively present an approach to assign modules to tiers for each kind of bonding style. Further, a new utilization function, called cosine-shaped function, is proposed to estimate utilizations of bins required by the analytical-based approach. Our experimental results show the cosine shaped function can obtain a little better result than the bell-shaped function on IBM benchmarks for 2D floorplanning. We also show that the proposed 3D floorplanning methodology consumes less TSVs and induces shorter wirelength compared to previous work in the hybrid bonding style.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:31

IP5-1, 932

A PLACEMENT ALGORITHM FOR SUPERCONDUCTING LOGIC CIRCUITS BASED ON CELL GROUPING AND SUPER-CELL PLACEMENT
Speaker:
Massoud Pedram, University of Southern California, US
Authors:
Soheil Nazar Shahsavani, Alireza Shafaei Bejestan and Massoud Pedram, University of Southern California, US
Abstract
This paper presents a novel clustering based placement algorithm for single flux quantum (SFQ) family of superconductive electronic circuits. In these circuits nearly all cells receive a clock signal and a placement algorithm that ignores the clock routing cost will not produce high quality solutions. To address this issue, proposed approach simultaneously minimizes the total wirelength of the signal nets and area overhead of the clock routing. Furthermore, construction of a perfect H-tree in SFQ logic circuits is not viable solution due to the resulting very high routing overhead and the in-feasibility of building exact zero-skew clock routing trees. Instead a hybrid clock tree must be used whereby higher levels of the clock tree (i.e., those closer to the clock source) are based on H-tree construction whereas lower levels of the clock tree follow a linear (i.e., chain-like) structure. The proposed approach is able to reduce the overall half-perimeter wirelength by 15% and area by 8% compared with state-of-the-art techniques.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:32

IP5-2, 851

ABAX: 2D/3D LEGALISER SUPPORTING LOOK-AHEAD LEGALISATION AND BLOCKAGE STRATEGIES
Speaker:
Nikolaos Sketopoulos, University of Thessaly, GR
Authors:
Nikolaos Sketopoulos, Christos Sotiriou and Stavros Simoglou, Department of Electrical and Computer Engineering, University of Thessaly, GR
Abstract
Abax is a modern version of the classical Abacus, minimum displacement, greedy legaliser. Abax supports single-tier 2D or 3D legalisation for multiple, logic-on-logic 3D-IC tiers, efficient look-ahead legalisation of intermediate Global Placement (GP) iterations, Hard Macros, Blockages, row density constraints and multiple local cell displacement functions and cell orderings. For 3D-IC, Abax can produce multi-tier 3D-IC placements by performing Legalisation-based Partitioning. For efficient Look-ahead Legalisation, Abax supports two new local displacement cost functions, multi-cell mean and multi-cell total. We show that the classical single-cell displacement and multi-cell total can result in artifacts when legalising early intermediate GPs, and that multi-cell mean is the best candidate for Look-ahead Legalisation. Obstructions, i.e. Hard Macros and Blockages are handled by using two strategies. We present legalisation results for the ISPD2014 and ISPD2015 benchmarks, by using GP generated from Eh?Placer, and HPWL measurement by using RippleDP. For 3D, two-tier legalisation we illustrate a ~30% reduction in HPWL for a set of ISPD2014 benchmarks. For 2D legalisation on the ISPD2015 benchmarks, our average HPWL increase over GP is 3.03%, compared to 7.21% of the Eh?Placer legaliser, and 43.16% of the RippleDP legaliser.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:33

IP5-3, 864

LESAR: A DYNAMIC LINE-END SPACING AWARE DETAILED ROUTER
Speaker:
Yih-Lang Li, Computer Science Department, NCTU, TH
Authors:
Ying-Chi Wei, Radhamanjari Samanta and Yih-Lang Li, National Chiao-Tung University, TW
Abstract
As the VLSI technology scales down, 193nm optical lithography reaches the limit and one-dimensional (1D) unidirectional style lithography technique emerges as one of the most promising solutions for coming advanced technology nodes. The 1D process first generates unidirectional dense metal lines and then use line-end cutting to form the target patterns with cut masks. If cuts are too close, they will lead to conflicts. Line-end spacing rules become dynamic rather than static because of cut mask and also now need to be followed strictly. Line-end spacing check between two line-end pairs in the same mask has also been regarded as compulsory line-end spacing constraints that have not discussed in previous works yet. Complying with these rules during APR has become a new bottleneck. In this work, we propose to make the router aware of the dynamic line-end spacing rules, including end-end spacing and parity spacing constraints. Experimental results of our proposed router demonstrates that it can effectively expel all end-end spacing violations as well as 75% of parity spacing violations in a reasonable runtime increase of 14%.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:30

End of session
Coffee Break in Exhibition Area

Coffee Breaks in the Exhibition Area

On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area (Terrace Level of the ICCD).

Lunch Breaks (Großer Saal + Saal 1)

On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the rooms "Großer Saal" and "Saal 1" (Saal Level of the ICCD) to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area.

Tuesday, March 20, 2018