| Title | A Two-Layer Global Router for Ball Grid Array Packages |
| Author | Yung-Chia Lin, *Kuang-Yao Lee, Ting-Chi Wang (National Tsing Hua University, Taiwan) |
| Page | pp. 301 - 306 |
| Keyword | package routing, ball grid array |
| Abstract | As the manufacturing technology keeps shrinking, the number of I/O pins in a modern VLSI chip has easily grown to hundreds, or even thousands. With the pressing need of connecting the huge number of I/O pins to a PCB (Printed Circuit Board), a BGA (Ball Grid Array) package is used mostly nowadays. In this paper, we present a two-layer BGA global routing algorithm which routes nets one at a time while considering the minimization of the total wirelength and overflow. The experimental results show that our algorithm averagely decreases 96.8% total overflow and 83.33% maximum overflow as compared to a recent work; besides, our algorithm produces smaller total wirelength and runs 4.39 times faster. |
| Title | A Routing Method based on Nearest Via Assignment for 2-Layer Ball Grid Array Packages |
| Author | *Yoshiaki Kurata, Yoichi Tomioka, Yukihide Kohira, Atsushi Takahashi (Tokyo Institute of Technology, Japan) |
| Page | pp. 307 - 312 |
| Keyword | package routing, BGA packages, mixed integer programming |
| Abstract | In this paper, we propose a routing method for 2-layer ball grid array packages that generates a routing pattern satisfying the constraint of wire congestions. In the proposed method, the via of a net is restricted to be placed near to the ball of the net, and a routing pattern that satisfies the constraints is formulated as a mixed integer programming. In experiments with several data, we obtain a routing pattern that satisfies the constraints of wire congestion within a practical time by using a mixed integer programming solver. |
| Title | Throughput-Driven Hierarchical Partitioning-Based Placement for Regular Distributed Register Architecture |
| Author | *Ya-Shih Huang, Juinn-Dar Huang (National Chiao Tung University, Taiwan) |
| Page | pp. 313 - 317 |
| Keyword | throughput-driven, partitioning-based, placement, RDR architecture, multicycle communication |
| Abstract | As proceeding into deep submicron technology era, interconnect delay is no longer negligible and becoming the dominant factor of system performance. Allowing multicycle communication in distributed register architecture is one promising solution to cope with this problem. However, multicycle communication can worsen system throughput due to additionally incurred interconnect latency. Meanwhile, different placements incur different interconnect latency then result in different system throughputs. Therefore, in this paper, we propose a hierarchical partitioning-based placement algorithm targeting the regular distributed register architecture that tries to maximize the overall system throughput. The experimental results show that our placer achieves on average 4.77 times throughput improvement compared with the SA-based timing-driven placer VPR. We also believe our idea can be further applied to task mapping in network-on-chips as well as global placement of a gate-level placer. |
| Title | Overlap-aware Analytical Placement Based on Stable-LSE |
| Author | *Naoto Funatsu, Yasuhiro Takashima (University of Kitakyushu, Japan) |
| Page | pp. 318 - 323 |
| Keyword | LSE, Stable-LSE, Overlap area, Analytical Placement |
| Abstract | We propose a differentiable approximation with Stable-LSE in which the overlap area between two cells can be expressed. In the Stable-LSE, the drawback of LSE with a numerical unstable problem is improved without loss of its efficiency. As a result, two objective functions of total wire length minimization and overlap area minimization are optimized simultaneously. We also implement the proposed method with Stable-LSE. Our prototype solves a problem with 300 cells in a few seconds with little overlap. Thus, we confirm its efficiency empirically. |
| Title | Yield Improvement in Gridless Detailed Routing with Redundant Via Insertion |
| Author | *Chih-Ta Lin, Yih-Lang Li (National Chiao Tung University, Taiwan) |
| Page | pp. 324 - 329 |
| Keyword | redundant via, detailed routing |
| Abstract | In this paper, a redundant via-aware routing system is proposed. A via-aware global router is used to reduce the number of vias. A redundant via-aware detailed router combined with redundant via protection, dead-via avoided tile propagation, redundant via-aware path construction and incremental dead-via constraint relaxation is applied to reduce the number of dead-vias. Finally a greedy post-layout redundant via insertion method is used to insert the redundant via of all alive vias. Experimental results show that the proposed redundant via-aware routing system runs faster than previous works and is the first work to achieve a 100% redundant via insertion rate for all vias in MCNC benchmark circuits. |
| Title | Interconnect Utilization of the VPEX Via-Programmable Structured ASIC |
| Author | *Kazuma Kitamura, Syouta Yamada, Masahide Kawarasaki, Yuuichi Kokusyou (Ritsumeikan University, Japan), Usman Ahmed, Guy Lemieux (University of British Columbia, Canada), Masaya Yoshikawa (Meijo University, Japan), Takeshi Fujino (Ritsumeikan University, Japan) |
| Page | pp. 330 - 334 |
| Keyword | Via programabble device, CAD system |
| Abstract | In the past, we proposed via-programmable logic architecture VPEX to reduce the manufacturing cost of SoCs by eliminating the cost associated with photomasks. In this paper, we describe the CAD framework for VPEX. We focus mainly on the routing algorithm. The proposed CAD flow is used to generate the final GDS-II layout for some sample circuits. The preliminary results show that VPEX has enough routing resources a circuit occupying 89% of the logic fabric can be successfully routed utilizing only 58% of the available routing resources. |
| Title | Slack-Driven Obstacle-Avoiding Rectilinear Steiner Tree Routing |
| Author | *Yen-Hung Lin, Shu-Hsin Chang, Yih-Lang Li (National Chiao Tung University, Taiwan) |
| Page | pp. 335 - 340 |
| Keyword | Obstacle-avoiding rectilinear Steiner tree, slack-driven routing, Elmore delay model, timing constraint, worst negative slack |
| Abstract | Obstacle-avoiding rectilinear Steiner tree (OARST) con-struction is a fundamental problem associated with the trend toward IP-block-based System-on-Chip designs. The objective of previous studies on obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) has been to minimize the total wire-length of the constructed Steiner tree. Studies of performance-driven Steiner trees have demonstrated that the minimization of wirelength may worsen the performance of the Steiner tree. This work is the first to construct OARST based on the Elmore delay model and consider timing constraints. A critical-trunk-based tree growth mechanism is proposed. The critical trunks are constructed by extended single-source single-target maze routing called multi-source single-target maze routing. The unconnected pins are connected to critical trunks under the delay constraints of every sink. The proposed critical trunk is applied to solve slack-driven OARST problem. Experimental results demonstrate that the proposed algorithm successfully solves 66.67% worst negative slack (WNS) violations in slack-driven OARST problem while running faster than previous OARSMT algorithms. |
| Title | FLEC: A Framework for System-level Debugging Support, Formal Verification and Static Analysis |
| Author | *Yoshihisa Kojima, Tasuku Nishihara, Takeshi Matsumoto, Masahiro Fujita (University of Tokyo, Japan) |
| Page | pp. 341 - 346 |
| Keyword | system-level design, formal verification, system dependence graph, framework |
| Abstract | System-level design methodology has become more widely accepted for more productivity, however, there are still few verification tools available for system-level designs. In this paper, we propose a system-level verification framework called FLEC, which has the Extended System Dependence Graphs (ExSDGs) as the intermediate representation, and the engines for analysis, simulation and verification, wrapped with the shell scripting interface. Its modular structure allows to easily realize various applications for debugging support, formal verification and static analysis. |
| Title | Language-Controlled Integrated Debugging Technique |
| Author | *Noriaki Suzuki, Junji Sakai (NEC Corporation, Japan) |
| Page | pp. 347 - 351 |
| Keyword | debugging, system LSI |
| Abstract | A control technique is described that simplifies the setting of the mode used for debugging software of multi-core system LSIs. This technique is controlled by special debugging program written in DCL(gdebugging mechanisms control languageh) with co-operating special debugging hardware mechanisms which include a system-event trapper, a bus tracer, debug processor. DCL language is designed subset of C-language and adding several functions to control these hardware mechanisms effectively and easily. This technique was adopted in an application system LSI design for a cellular phone. We applied it for an actual program debugging including external events. In the result, efficient debugging was achieved using integration of break debugging and tracing. |
| Title | Soft-error Resiliency Evaluation on Delayed Multiple-modular Flip-Flops |
| Author | *Jun Furuta, Yusuke Moritani, Kazutoshi Kobayashi, Hidetoshi Onodera (Kyoto University, Japan) |
| Page | pp. 352 - 357 |
| Keyword | TMR, Built-in Soft Error, SEU, SET |
| Abstract | According to the process scaling, semiconductor devices are becoming more sensitive to soft errors since amount of critical charges are decreasing. In this paper, we estimate soft error rates(SERs) on latches and combinational circuits on a 90nm CMOS process from circuit-level simulations. We also estimate SERs of delayed TMR and DMR in which SET pulses areremoved by delay elements. As a result, it reveals that the delayed DMRare very weak to soft errors compared with the delayed TMR. |
| Title | Evaluation of Statistical Method of Estimating Coverage Metrics for Functional Verification |
| Author | Kohei Hosokawa, *Yuichi Nakamura (NEC, Japan) |
| Page | pp. 358 - 363 |
| Keyword | Statistics, Coverage Metrics, Functional Verification, FPGA-based emulators |
| Abstract | We propose a statistical method to estimate the coverage metrics for functional verification, which are statement, branch, condition, expression, and toggle coverage of LSIs. The new method of estimation evaluates the coverage metrics for functional verification from only a few hundred or thousand randomly sampled signals. The statistical estimation method allows the coverage metrics for functional verification to be measured by a system, such as with FPGA-based emulators, which cannot observe the status of all signals in LSIs. We applied the new approach to a circuit to bridge a PCI bus and a local communication bus. We confirmed that the estimation error in all the coverage metrics for function verification visually followed a normal probability distribution in theory, and passed the most of normal distribution tests with a 1% significance level. |
| Title | A Fast Approximation Method of Maximum Operation in Statistical Static Timing Analysis for Achieving Specified Yield |
| Author | *Shun Gokita, Yukihide Kohira, Atsushi Takahashi (Tokyo Institute of Technology, Japan) |
| Page | pp. 364 - 369 |
| Keyword | SSTA, normal distribution, maximum operation, specified yield |
| Abstract | In this paper, we propose a fast maximum-operation of two normal distributions that reduces the error of the estimated worst delay of a circuit obtained by repeating the proposed operation. The proposed maximum-operation outputs a normal distribution by which the worst delay defined is equal to the worst delay defined by the actual distribution and whose shape near the worst delay is close to the actual distribution. In experiments by using benchmark circuits, it is shown that the estimated worst delay obtained by using the proposed method is more accurate than that by existing methods. |
| Title | Dynamic Model of a Parallel Plate Actuator with Pull-in Consideration for CMOS-MEMS Simultaneous Behavior Anticipation |
| Author | *Yuheon Yi, Hiroyuki Fujita, Hiroshi Toshiyoshi (IIS, University of Tokyo, Japan) |
| Page | pp. 370 - 373 |
| Keyword | dynamic model, pullin, CMOS-MEMS behavior, resonant oscillation |
| Abstract | This study presents a newly developed analytical model that can handle post pull-in behavior of MEMS electrostatic actuator. In addition to the conventional Matlab model of the quadratic oscillation system, a displacement limiter has been inserted to represent the mechanical stopper. Thanks to the modification, the model has become applicable to both pre- and post pull-in region of electrostatic actuators. The new model has been integrated in the simulation model of self-oscillating CMOS-MEMS, and the versatility in the behavior-level simulation has been verified. |
| Title | Support System for ASIC Design based on Sysem Block Diagram |
| Author | *Koichi Mori (Tokyo Metropolitan University, Japan), Yuichi Nakamura (NEC, Japan), Takao Nishitani (Tokyo Metropolitan University, Japan) |
| Page | pp. 374 - 379 |
| Keyword | co-simulation, FPGA, Simulink, SOC |
| Abstract | A support system for designing a complex SOC is proposed. The employed approach is based on a system block diagram which runs on software. A specific block in the diagram is replaced by a FPGA chip, connected to a PC. Therefore, a system level support system with the co-simulation environment between software and hardware is realized. The simulation time is reduced 1/200 compared with the conventional approaches and the system bottle neck will be easily estimated by our proposed system. |
| Title | Equivalence Checking of Loops Before and After Pipelining by Applying Symbolic Simulation and Induction |
| Author | *Shanghua Gao, Takeshi Matsumoto, Hiroaki Yoshida, Masahiro Fujita (University of Tokyo, Japan) |
| Page | pp. 380 - 385 |
| Keyword | Equivalence checking, Pipelining, Loop, Symbolic simulation, Induction |
| Abstract | When applications contain large loops, high level synthesis often takes advantage of software pipelining technique in order to improve the performance. High level synthesis with pipelining utilization needs complicated algorithms. So it is desired to check its correctness. In this paper, we propose a novel approach for equivalence checking of loops before and after pipelining. The proposed approach applies a combination of symbolic simulation and induction. The experimental results show that our method can verify the equivalence of loops before and after pipelining. |