Handling routability in floorplan design with twin binary trees

As technology moves into the deep-submicron era, the complexities of VLSI circuits grow rapidly. Interconnect optimization has become an important concern. Most routability-driven floorplanners [H.M. Chen, H. Zhou, F.Y. Young, D.F. Wong, H.H. Yang, N. Sherwani, Integrated floorplanning and interconnect planning, in: Proceedings of IEEE International Conference on Computer-Aided Design, 1999, pp. 354–357; S. Krishnamoorthy, J. Lou, H.S. Sheng, Estimating routing congestion using probabilistic analysis, in: Proceedings of International Symposium on Physical Design, 2001, pp. 112–117; M. Wang, M. Sarrafzadeh, Modeling and minimization of routing congestion, in: IEEE Asia and South Pacific Design Automation Conference, 2000, pp. 185–190] use grid-based approach that divides a floorplan into grids as in global routing to estimate congestion by the expected number of nets passing through each grid. This approach is direct and accurate, but not efficient enough when dealing with complex circuits containing many nets. In this paper, an efficient and innovative interconnect-driven floorplanner using twin binary trees (TBT) representation [B. Yao, H. Chen, C.K. Cheng, R. Graham, Revisiting floorplan representations, in: Proceedings of International Symposium on Physical Design, 2001, pp. 138–143; E.F.Y. Young, C.C.N. Chu, Z.C. Shen, Twin binary sequences: a non-redundant representation for general non-slicing floorplan, in: Proceedings of International Symposium on Physical Design, 2002, pp. 196–201] is proposed. The estimations are based on the wire densities (number of wires passing through per unit length) on the half-perimeter boundaries of different regions in a floorplan. These regions are defined naturally by the TBT representation. Buffer planning is also considered by deciding if buffers can be inserted successfully for each net. In order to increase the efficiency of our floorplanner, a fast algorithm for the least common ancestor (LCA) problem in Bender and Farach-Colton [The LCA problem revisited, in: Latin American Theoretical INformatics, 2000, pp. 88–94] is used to compute wire density, and a table look-up approach is used to obtain the buffer insertion information. Experimental results show that our floorplanner can reduce the number of unroutable wires. The performance is comparable with other interconnect-driven floorplanners that perform global routing-like operations directly to estimate routability, but our estimation method is much faster and is scalable for large complex circuits.     

Packet concatenation at the IP level for performance enhancement in wireless local area networks

Wireless local area networks experience performance degradation in presence of small packets. The main reason for that is the large overhead added at the physical and link layers. This paper proposes a concatenation algorithm which groups IP layer packets prior to transmission, called PAC-IP. As a result, the overhead added at the physical and the link layers is shared among the grouped packets. Along with performance improvement, PAC-IP enables packet-based fairness in medium access as well as includes QoS support module handling delay-sensitive traffic demands. The performance of the proposed algorithm is evaluated through both simulations and an experimental WLAN testbed environment covering the single-hop and the widespread infrastructure network scenarios. Obtained results underline significant performance enhancement in different operating scenarios and channel conditions. Dzmitry Kliazovich received his Masters degree in Telecommunication science from Belarusian State University of Informatics and Radioelectronics in 2002. He is currently working towards the Ph.D. degree in University of Trento, Italy. From September 2005 to February 2006 he was a visiting researcher at the Computer Science Department of the University of California at Los Angeles. He is an author of more than 20 research papers published in international books, journals and conference proceedings. His main research interest lies in field of wireless networking with a focus on performance optimization and cross-layer design. Fabrizio Granelli was born in Genoa in 1972. He received the “Laurea” (M.Sc.) degree in Electronic Engineering from the University of Genoa, Italy, in 1997, with a thesis on video coding, awarded with the TELECOM Italy prize, and the Ph.D. in Telecommunications from the same university, in 2001. Since 2000 he is carrying on his teaching activity as Assistant Professor in Telecommunications at the Dept. of Information and Communication Technology—University of Trento (Italy). In August 2004, he was visiting professor at the State University of Campinas (Brasil). He is author or co-author of more than 60 papers published in international journals, books and conferences, and he is member of the Technical Committee of the International Conference on Communications (from 2003 to 2007) and Global Telecommunications Conference (GLOBECOM2003 and GLOBECOM2004). Dr. Granelli is guest-editor of ACM Journal on Mobile Networks and Applications, special issues on “WLAN Optimization at the MAC and Network Levels” and “Ultra-Wide Band for Sensor Networks”, and Co-Chair of 10th IEEE Workshop on Computer-Aided Modeling, Analysis, and Design of Communication Links and Networks (CAMAD’04). Dr. Granelli is General Vice-Chair of the First International Conference on Wireless Internet (WICON’05) and General Chair of the 11th IEEE Workshop on Computer-Aided Modeling, Analysis, and Design of Communication Links and Networks (CAMAD’06). His main research activities are in the field of networking and signal processing, with particular reference to network performance modeling, medium access control, wireless networks, cognitive radio systems, and video transmission over packet networks. He is Senior Member of IEEE and Associate Editor of IEEE Communications Letters.     

Development of a large word-width high-speed asynchronous multiply and accumulate unit

This paper details the design of the fastest known asynchronous Multiply and Accumulate unit (MAC) architecture published to date. The MAC architecture herein is based on the MAC developed in Smith et al. (J. Syst. Archit. 47/12 (2002) 977–998). However, the MAC developed in Smith et al. (2002) contains conditional rounding, scaling, and saturation (CRSS) logic, not present in other comparable MACs (Twenty-Sixth Hawaii International Conference on System Sciences, vol. 1, 1993, pp. 379–388; Asian South-Pacific Design Automation Conference, 2000, pp. 15–16; Sixth IEEE International Conference on Proceedings of ICECS, vol. 2, 1999, pp. 629–633); thus making the comparison between the MAC developed in Smith et al. (2002) and other delay-insensitive/self-timed MACs in the literature not completely fair, in favor of the other MACs. This paper first details the removal of the CRSS logic from the MAC developed in Smith et al. (2002), and describes its subsequent optimal re-pipelining, in order to provide a more fair comparison. This yields a speedup of 1.12. Secondly, this paper details the application of the NULL Cycle Reduction technique (The 10th International Workshop on Logic and Synthesis, 2001, pp. 185–189; Gate and throughput optimizations for NULL convention self-timed digital circuits, Ph.D. Dissertation, School of Electrical Engineering and Computer Science, University of Central Florida, 2001) to the MAC's feedback loop, and subsequent re-pipelining of the feed-forward partial product generation and summation circuitry to further increase throughput, resulting in an additional speedup of 1.31 (a speedup of 1.46 over the MAC from Smith et al. (2002). Lastly, the bit-wise completion strategy is utilized in lieu of full-word completion to decrease the area required by 6% and also increase the MAC's throughput an additional 1%.     

Introduction (September 1966)

The purpose of this Special Issue is to present selected papers based on oral presentations made at the 1966 International Solid-State Circuits Conference. Unlike the conference Proceedings, which publishes digests of these presentations, it was our aim to make complete papers available to members of the IEEE Group on Circuit Theory.     

Fast Substrate Noise Aware Floorplanning for Mixed Signal SOC Designs

In this paper, we introduce a novel substrate noise estimation technique during early floorplanning for mixed signal system-on-chip (SOC), based on block preference directed graph (BPDG). Given a set of analog and digital blocks, BPDG is constructed based on their inherent noise characteristics to capture the preferred relative locations for substrate noise minimization. For each instance of floorplan in sequence pair or ${B}^{ast}$-tree, we efficiently count the number of violations against BPDG which correlates remarkably well with accurate but computation-intensive substrate noise modeling. Thus, our BPDG-based model can guide fast substrate noise-aware floorplanning and layout optimization for mixed signal SOC. Our experimental results show that the proposed approach is significantly faster than conventional full-blown substrate model-based floorplanning.      

Bus-driven floorplanning with thermal consideration

As the increasing number of buses in multi-core SoC designs, bus planning problems become a dominant factor in determining the chip performance. To cope with these issues, it is desirable to consider them in the early floorplanning stage. Recently, many bus-driven floorplanners have been proposed in the literature. However, these proposed algorithms only consider the bus planning problem without the thermal effect. As a result, there are hotspots, which result in high chip temperature, on the chip. In this paper, a thermal-driven bus-driven floorplanning algorithm is proposed to separate hotspots during the perturbation stage and to keep buses away from hotspots during the routing stage. To avoid time-consuming thermal simulations, the superposition of thermal profiles, which are the thermal distribution of each module, is adopted to efficiently estimate the module temperature. Compared with the state-of-the-art bus-driven floorplanner, experimental results demonstrate that the proposed algorithm can effectively separate hotspots and reduce the chip temperature.     

面向软模块的稳定固定边框布图规划算法

该文提出一种稳定的面向软模块的固定边框布图规划算法。该算法基于正则波兰表达式(Normalized Polish Expression, NPE)表示,提出一种基于形状曲线相加和插值技术的计算NPE最优布图的方法,并运用模拟退火(Simulation Annealing, SA)算法搜索最优解。为了求得满足固定边框的布图解,提出一种基于删除后插入(Insertion After Delete, IAD)算子的后布图优化方法。对8个GSRC和MCNC电路的实验结果表明,所提出算法在1%空白面积率的边框约束下的布图成功率接近100%,在总线长上较已有文献有较大改进,且在求解速度上较同类基于SA的算法有较大优势。     

Fixed-outline floorplanning: enabling hierarchical design

Classical floorplanning minimizes a linear combination of area and wirelength. When simulated annealing is used, e.g., with the sequence pair representation, the typical choice of moves is fairly straightforward. In this paper, we study the fixed-outline floorplan formulation that is more relevant to hierarchical design style and is justified for very large ASICs and SoCs. We empirically show that instances of the fixed-outline floorplan problem are significantly harder than related instances of classical floorplan problems. We suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context. Wirelength improvements and optimization of aspect ratios of soft blocks are explicitly addressed by these techniques. Our proposed moves are based on the notion of floorplan slack. The proposed slack computation can be implemented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically indistinguishable from the fastest reported . A similar slack computation is possible with many other floorplan representations. In all cases the computation time approximately doubles. Our empirical evaluation is based on a new floorplanner implementation Parquet-1 that can operate in both outline-free and fixed-outline modes. We use Parquet-1 to floorplan a design, with approximately 32000 cells, in 37 min using a top-down, hierarchical paradigm.     

CNS: a new energy efficient transmission scheme for wireless sensor networks

We present in this paper a new energy-efficient communication scheme called CNS (Compression with Null Symbol) that combines the power of data compression and communication through silent symbol. The concept of communication through silent symbol is borrowed from the energy efficient schemes proposed in Sinha (Proceedings of 6th IEEE consumer communications and networking conference (CCNC), Las Vegas, pp. 1–5, 2009), Ghosh et al. (Proceedings of 27th IEEE international performance computing and communications conference (IPCCC), USA, pp. 85–92, 2008), and Sinha and Sinha (Proceedings of international conference on distributed computing and internet technologies (ICDCIT), LNCS, pp. 139–144, 2008). We show that the average theoretical energy saving at the transmitter by CNS is 62.5%, assuming an ideal channel and for equal likelihood of all possible binary strings of a given length. Next, we propose a transceiver design that uses a hybrid modulation scheme utilizing FSK and ASK so as to keep the cost/complexity of the radio devices low. Considering an additive white gaussian noise (AWGN) channel and a non-coherent detection based receiver, CNS shows a saving in transmitter energy by 30% when compared to binary FSK, for equal likelihood of all possible binary strings of a given length. Simultaneously, there is a saving of 50% at the receiver for all types of data modulation due to halving of the transmitted data duration, compared to binary encoding. In contrast, RBNSiZeComm proposed in Sinha (Proceedings of 6th IEEE consumer communications and networking conference (CCNC), Las Vegas, pp. 1–5, 2009), TSS proposed in Ghosh et al. (Proceedings of 27th IEEE international performance computing and communications conference (IPCCC), USA, pp. 85–92, 2008) and RZE proposed in Sinha and Sinha (Proceedings of international conference on distributed computing and internet technologies (ICDCIT), LNCS, pp. 139–144, 2008) generate average transmitter energy savings of about 41, 20, and 35.2%, respectively. Also, at the receiver side, while RBNSiZeComm does not generate any saving, TSS and RZE produce about 36.9 and 12.5% savings on an average, respectively. Considering certain data types that may occur in the context of some wireless sensor networks (WSN) based applications (e.g., remote healthcare, agricultural WSNs, etc.), our simulation results demonstrate that for AWGN noisy channels, the transmitter side savings vary from about 33–50% on an average, while for RBNSiZeComm, this saving is about 33–61% on the same data set (Sinha in Proceedings of 6th IEEE consumer communications and networking conference (CCNC), Las Vegas, pp. 1–5, 2009). Thus, taking into account the low cost/complexity of the proposed transceiver, these results clearly establish that CNS can be a suitable candidate for communication in low power wireless sensor networks, such as in remote healthcare applications, body area networks, home automation, WSNs for agriculture and many others.     

Chair's Introduction to 2009 IEEE Circuits and Systems International Conference on Testing and Diagnosis

Based on the recommendation of ICTD'09 TPC members, this Special Issue of the Journal of Electronic Science & Technology of China (JESTC) contained 22 high quality papers selected from the Proceedings of 2009 IEEE Circuits and Systems International Conference on Testing and Diagnosis (ICTD'09) which is fully sponsored by the IEEE Circuits and Systems Society (CASS), and is technically co-sponsored by the University of Electronic Science and Technology of China (UESTC), the Chinese Institute of Electronics (CIE), the China Instrument & Control Society (CIS), and organized by UESTC.     

An analysis of high-frequency noise in RF active CMOS mixers

An analysis of high-frequency noise in RF active CMOS mixers including single-balanced and double-balanced architectures is presented. The analysis investigates the contribution of non-white gate-induced noise to the output noise power as well as the spot noise figure (NF) of the RF CMOS mixer. It accounts for the non-zero correlation between the gate-induced noise and the channel’s thermal noise. The noise contribution of the RF transconductor and the switching pair to the output noise power is studied. Experimental results verify the accuracy of the analytical model. Payam Heydari (S’98–M’00) received the B.S. and M.S. degrees in electrical engineering from the Sharif University of Technology, in 1992, 1995, respectively. He received the Ph.D. degree in electrical engineering from the University of Southern California, in 2001. During the summer of 1997, he was with Bell-Labs, Lucent Technologies, where he worked on noise analysis in deep submicrometer very large-scale integrated (VLSI) circuits. During the summer of 1998, he was with IBM T. J. Watson Research Center, Yorktown Heights, NY, where he worked on gradient-based optimization and sensitivity analysis of custom-integrated circuits. Since August 2001, he has been an Assistant Professor of Electrical Engineering at the University of California, Irvine, where his research interest is the design of high-speed analog, RF, and mixed-signal integrated circuits. Dr. Heydari has received the 2005 National Science Foundation (NSF) CAREER Award, the 2005 IEEE Circuits and Systems Society Darlington Award, the 2005 Henry Samueli School of Engineering Teaching Excellence Award, the Best Paper Award at the 2000 IEEE International Conference on Computer Design (ICCD), the 2000 Honorable Mention Award from the Department of EE-Systems at the University of Southern California, and the 2001 Technical Excellence Award in the area of Electrical Engineering from the Association of Professors and Scholars of Iranian Heritage (APSIH). He was recognized as the 2004 Outstanding Faculty at the EECS Department of the University of California, Irvine. His name was included in the 2006 Who’s Who in America. Dr. Heydari Professor Heydari has been the Associate Editor of IEEE TRANS. ON CIRCUITS AND SYSTEMS, I, since 2006. He currently serves on the Technical Program Committees of International Symposium on Low-Power Electronics and Design (ISLPED), International Symposium on Quality Electronic Design (ISQED), and the Local Arrangement Chair of the ISLPED conference. He was the Student Design Contest Judge for the DAC/ISSCC Design Contest Award in 2003, the Technical Program Committee member of the IEEE Design and Test in Europe (DATE) from 2003 to 2004, and International Symposium on Physical Design (ISPD) in 2003.     

Scaling Analysis of On-Chip Power Grid Voltage Variations in Nanometer Scale ULSI

This paper presents a detailed scaling analysis of the power supply distribution network voltage drop in DSM technologies. The effects of chip temperature, electromigration and interconnect technology scaling (including resistivity increase of Cu interconnects due to electron surface scattering and finite barrier thickness) are taken into consideration during this analysis. It is shown that the voltage drop effect in the power/ground (P/G) distribution network increases rapidly with technology scaling, and that using well-known countermeasures such as wire-sizing and/or decoupling capacitor insertion which are typically used in the present design methodologies may be insufficient to limit the voltage fluctuations over the power grid for future technologies. It is also shown that such voltage drops on power supply lines of switching devices in a clock distribution network can introduce significant amount of skew which in turn degrades the signal integrity.This work was done when the author was with the Dept. of EESystems, University of Southern California.Amir H. Ajami received his B.S. degree in electrical engineering from the University of Tehran, Tehran, Iran in 1993. He received his M.S. and Ph.D. degrees in electrical engineering from the University of Southern California, Los Angeles, CA, in 1999 and 2002, respectively.He is currently a member of consulting staff in research and development division at MagmaDesign Automation, Inc., Santa Clara, CA. He has previously held positions at Cadence Design Systems, Inc., andMagma Design Automations, Inc., in 1999 and 2000, respectively. His research interests are in the area of technology scaling issues in high-performance VLSI designs with emphasis on full-chip thermal analysis, thermalaware timing and power optimization methodologies, and signal integrity. He has coauthored several papers on the modeling and analysis of the effects of substrate thermal gradients on performance degradation and development of thermal-aware physical-synthesis optimization algorithms.Dr. Ajami is a member of Association of Computing Machinery (ACM) and IEEE. HE serves on the technical program committee of the 2005 IEEE International Symposium on Quality Electronics Design.Kaustav Banerjee received the Ph.D. degree in electrical engineering and computer sciences from the University of California at Berkeley in 1999. He was with Stanford University, Stanford, CA, from 1999 to 2002 as a Research Associate at the Center for Integrated Systems. In July 2002, he joined the faculty of the Electrical and Computer Engineering Department at the University of California, Santa Barbara, as an Assistant Professor. From February 2002 to August 2002 he was a Visiting Professor at the Circuit Research Labs of Intel in Hillsboro, Oregon. In the past, he has also held summer/visiting positions at Texas Instruments Inc., Dallas, Texas, Fujitsu Labs and the Swiss Federal Institute of Technology (EPFL). His present research interests focus on a wide variety of nanometer scale issues in high-performance VLSI and mixed-signal designs, as well as on circuits and systems issues in emerging nanoelectronics. He is also interested in some exploratory interconnect and circuit architectures including 3-D ICs. At UCSB, Dr. Banerjee mentors several doctoral and masters students. He also co-advises graduate students at Stanford University, University of Illinois at Urbana-Champaign and EPFL-Switzerland. He has co-directed two doctoral dissertations at Stanford University and the University of Southern California. Dr. Banerjee served as Technical Program Chair of the 2002 IEEE International Symposium on Quality Electronic Design (ISQED 02), and is the General Chair of ISQED 05. He also serves or has served on the technical program committees of the IEEE International Electron Devices Meeting, the IEEE International Reliability Physics Symposium, the EOS/ESD Symposium and the ACM International Symposium on Physical Design. His research has been chronicled in over 100 journals and refereed international conference papers and a book chapter. He has also co-edited a book titled Emerging Nanoelectronics: Life with and after CMOS by Kluwer in 2004. Dr. Banerjee has been recognized through the ACM SIGDA Outstanding New Faculty Award (2004) as well as a Best Paper Award at the Design Automation Conference (2001). He is listed in Whos Who in America and Whos Who in Science and Engineering.Massoud Pedram received a B.S. degree in Electrical Engineering from the California Institute of Technology in 1986 and M.S. and Ph.D. degrees in Electrical Engineering and Computer Sciences from the University of California, Berkeley in 1989 and 1991, respectively. He then joined the department of Electrical Engineering, Systems at the University of Southern California where he is currently a professor. Dr. Pedram has served on the technical program committee of a number of conferences, including the Design automation Conference (DAC), Design and Test in Europe Conference (DATE), Asia-Pacific Design automation Conference (ASP-DAC), and International Conference on Computer Aided Design (ICCAD). He served as the Technical Co-chair and General Co-chair of the International Symposium on Low Power Electronics and Design (SLPED) in 1996 and 1997, respectively. He was the Technical Program Chair and the General Chair of the 2002 and 2003 International Symposium on Physical Design. Dr. Pedram has published four books, 60 journal papers, and more than 150 conference papers. His research has received a number of awards including two ICCD Best Paper Awards, a Distinguished Citation from ICCAD, a DAC Best Paper Award, and an IEEE Transactions on VLSI Systems Best Paper Award. He is a recipient of the NSFs Young Investigator Award (1994) and the Presidential Faculty Fellows Award (a.k.a. PECASE Award) (1996).Dr. Pedram is a Fellow of the IEEE, a member of the Board of Governors for the IEEE Circuits and systems Society, an associate editor of the IEEE Transactions on Computer Aided Design, the IEEE Transactions on Circuits and Systems, and the IEEE Circuits and Systems Society Distinguished Lecturer Program Chair. He is also an Advisory Board Member of the ACM Interest Group on Design Automation, and an associate editor of the ACM Transactions on Design Automation of Electronic Systems. His current work focuses on developing computer aided design methodologies and techniques for low power design, synthesis, and physical design. For more information, please go to URL address: .     

Fast CORDIC Algorithm Based on a New Recoding Scheme for Rotation Angles and Variable Scale Factors

This work proposes a new rotation mode CORDIC algorithm, which considerably reduces the iteration number. It is achieved by combining several design techniques. Particularly, a new table-lookup recoding scheme for rotation angles and variable scale factors is developed to reduce the iteration numbers for rotation and scale factor compensation. By addressing the MSB parts of the residual rotation angles to a lookup table, two micro rotation angles are retrieved that in combination best matches the MSB parts. We also combine the leading-one bit detection operations for residual rotation angles, to skip unnecessary rotations. The resulting problems of variable scale factors are then solved by our previous fast decomposition and compensation algorithm (C.C. Li and S.G. Chen, in Proceedings of 1996 IEEE International Symposium Circuits and Systems, May 1996, Atlanta, USA, pp. 264–267; C.C. Li and S.G. Chen, in Proceedings of 1997 IEEE International Conference on Acoustic, Speech and Signal Processing, Munich, 1997, Germany, pp. 639–642). To further reduce the iteration number of scale factor compensation, we again apply the mentioned residual recoding technique and the leading-one bit detection scheme to the fast variable scale factor algorithm. Those techniques collectively reduce the iteration number significantly. Simulations show that in average the new design needs only 9.78 iterations to generate results with 22-bit accuracy, including all the iterations for rotations and scale factor compensations. Statistically, the total iteration number is less than n/2 for results with n-bit accuracy. The introduced extra table size is of the same order of magnitude as that for the angle set {tan^–1 2^–i , i = 0,1,...,n}, required by general CORDIC algorithms. The new recoding scheme can be applied to other elementary function such as division and square-root functions.     

CSP-based object-oriented description and simulation of a reconfigurable adaptive beamforming architecture using the OODRA workbench

Application of the Object-Oriented Design of Reliable/Reconfigurable Architectures (OODRA) workbench to the performance simulation of a reconfigurable adaptive digital beamforming architecture is described in this paper. The performance effects due to chip/wafer partitioning and reconfiguration for fault tolerance and yield enhancement are presented. The experiments described illustrate use of the OODRA workbench in architectural-level performance evaluation of algorithm-specific reconfigurable architectures, particularly for signal processing applications.This research was supported in part by SDIO/IST and managed by the Office of Naval Research under contract N00014-89-K-0070 and in part by the Semiconductor Research Corporation under Contract 88-DP-109. Portions of this paper were presented at the IEEE International Conference on Wafer Scale Integration, January 1989, and the ACM/IEEE Design Automation Conference, June 1989.     

Topology/Floorplan/Pipeline Co-Design of Cascaded Crossbar Bus

On-chip bus design has a significant impact on the die area, power consumption, performance and design cycle of complex system-on-chips (SoCs). Especially, for high frequency systems having on-chip buses pipelined extensively to cope with long wire delay, a naive bus design may yield a significant area/power cost mostly due to bus pipeline cost. The topology, floorplan, and pipeline are the most important design factors that affect the cost and frequency of the on-chip bus. Since they are strongly correlated with each other, it is imperative to codesign all of the three. In this paper, we present an automated codesign method for cascaded crossbar bus design. We present CADBUS (CAscadeD crossbar BUS design tool), an automated tool for AXI-based cascaded crossbar bus architecture design. The primary objective of this study is to design a cascaded crossbar bus, including the topology/floorplan/bus pipelines, having minimum area/power cost while satisfying the given constraints of communication bandwidth/latency or frequency. Experimental results of the three industrial strength SoCs show that, compared to the existing approach, the proposed method gives as much as 11.6%–34.2% (9.9%–33.5%) savings in bus area (power consumption).      

固定边框的多电压布图规划算法

多电压设计是应对SoC功耗挑战的一种有效方法,但会带来线长、面积等的开销。为减少线长、芯片的空白面积及提高速度,提出了一种改进的固定边框多电压布图方法.对基于NPE（Normalized Polish Expression）表示的布图解,采用形状曲线相加算法来计算其最优的布图实现,并通过增量计算方法来减少计算NPE及多电压分配的时间.为使所得布图解满足给定的边框约束,提出了一个考虑固定边框约束的目标函数,并采用删除后插入（Insertion after Delete,IAD）算子对SA求得布图解进行后优化.实验结果表明,和已有方法相比,所提出方法在线长和空白面积率方面有较明显优势,且所有电路在不同高宽比、不同电压岛数下均实现了极低的空白面积率（< <1%）.     

An efficient large systems analysis method using system dynamic behavior

This paper presents our unified approach to the solution of large system analysis problems. The macromodular behavioral technique combines multiple-logic function macromodeling, functional latency and nested macromodel. We take advantage of the dynamic behavior and the repetitive modular structure of a system to improve the computational efficiency during system analysis. Several Bipolar and MOSFET electronic networks are used to demonstrate the merits of the macromodular behavioral method for large system analysis.Parts of the paper have been presented at the 16th Design Automation Conference (1979) and at the 1980 IEEE International Symposium on Circuits and Systems.     

Test Planning and Test Resource Optimization for Droplet-Based Microfluidic Systems

Recent years have seen the emergence of droplet-based microfluidic systems for safety-critical biomedical applications. In order to ensure reliability, microsystems incorporating microfluidic components must be tested adequately. In this paper, we investigate test planning and test resource optimization for droplet-based microfluidic arrays. We first formulate the test planning problem and prove that it is NP-hard. We then describe an optimization method based on integer linear programming (ILP) that yields optimal solutions. Due to the NP-hard nature of the problem, we develop heuristic approaches for optimization. Experimental results indicate that for large array sizes, the heuristic methods yield solutions that are close to provable lower bounds. These heuristics ensure scalability and low computation cost. This research was supported in part by the National Science Foundation under grant number IIS-0312352. A preliminary version of this paper appeared in Proc. European Test Symposium. pp. 72–77, 2004 Fei Su received the B.E. and the M.S. degrees in automation from Tsinghua University, Beijing, China, in 1999 and 2001, respectively, and the M.S. degree in electrical and computer engineering from Duke University, Durham, NC, in 2003. He is now a Ph.D. candidate in electrical and computer engineering at Duke University. His research interests include design and testing of mixed-technology microsystems, electronic design automation, mixed-signal VLSI design, MEMS modeling and simulation. Sule Ozev received her B.S. degree in Electrical Engineering at Bogazici University in 1995, and her M.S. and Ph.D. degrees in Computer Science and Engineering at University of California, San Diego in 1998 and 2002 respectively. Since 2002, she has been a faculty member at Duke University, Electrical and Computer Engineering Department. Her research interests include RF circuit analysis and testing, process variability analysis, and mixed-signal testing. Krishnendu Chakrabarty received the B. Tech. degree from the Indian Institute of Technology, Kharagpur, in 1990, and the M.S.E. and Ph.D. degrees from the University of Michigan, Ann Arbor, in 1992 and 1995, respectively, all in Computer Science and Engineering. He is now Associate Professor of Electrical and Computer Engineering at Duke University. Dr Chakrabarty is a recipient of the National Science Foundation Early Faculty (CAREER) award and the Office of Naval Research Young Investigator award. His current research projects include: design and testing of system-on-chip integrated circuits; design automation of microfluidics-based biochips; microfluidics-based chip cooling; distributed sensor networks. Dr Chakrabarty has authored three books Microelectrofluidic Systems: Modeling and Simulation (CRC Press, 2002), Test Resource Partitioning for System-on-a-Chip (Kluwer, 2002), and Scalable Infrastructure for Distributed Sensor Networks (Springer, 2005) 3/4 and edited the book volume SOC (System-on-a-Chip) Testing for Plug and Play Test Automation (Kluwer 2002). He has published over 200 papers in journals and refereed conference proceedings, and he holds a US patent in built-in self-test. He is a recipient of best paper awards at the 2005 IEEE International Conference on Computer Design and 2001 IEEE Design, Automation and Test in Europe (DATE) Conference. He is also a recipient of the Humboldt Research Fellowship, awarded by the Alexander von Humboldt Foundation, Germany. Dr Chakrabarty is an Associate Editor of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on VLSI Systems, IEEE Transactions on Circuits and System I, ACM Journal on Emerging Technologies in Computing Systems, and an Editor of Journal of Electronic Testing: Theory and Applications (JETTA). He a member of the editorial board for Sensor Letters and Journal of Embedded Computing and he serves as a subject area editor for the International Journal of Distributed Sensor Networks. He has also served as an Associate Editor of IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. He is a senior member of IEEE, a member of ACM and ACM SIGDA, and a member of Sigma Xi. He serves as Vice Chair of Technical Activities in IEEE’s Test Technology Technical Council, and is a member of the program committees of several IEEE/ACM conferences and workshops. He served as the Program Co-Chair for the 2005 IEEE Asian Test Symposium.     

Test of switched-capacitor ladder filters using OBT

In this paper, a way to test switched-capacitors ladder filters by means of Oscillation-Based Test (OBT) methodology is proposed. Third-order low-pass Butterworth and Elliptic filters are considered in order to prove the feasibility of the proposed approach. A topology with a non-linear element in an additional feedback loop is employed for converting the Circuit Under Test (CUT) into an oscillator. The idea is inspired in some author's previous works (G. Huertas, D. Vázquez, A. Rueda, J.L. Huertas, Oscillation-based Test Experiments in Filters: a DTMF example, in: Proceedings of the International Mixed-Signal Testing Workshop (IMSTW'99), British Columbia, Canada, 1999, pp. 249–254; G. Huertas, D. Vazquez, E. Peralías, A. Rueda, J.L. Huertas, Oscillation-based test in oversampling A/D converters, Microelectronic Journal 33(10) (2002) 799–806; G. Huertas, D. Vázquez, E. Peralías, A. Rueda. J.L. Huertas, Oscillation-based test in bandpass oversampled A/D converters, in: Proceedings of the International Mixed-Signal Test Workshop, June 2002, Montreaux (Switzerland), pp. 39–48; G. Huertas, D. Vázquez, A. Rueda, J.L. Huertas, Practical oscillation-based test of integrated filters, IEEE Design and Test of Computers 19(6) (2002) 64–72; G. Huertas, D. Vázquez, E. Peralías, A. Rueda, J.L. Huertas, Testing mixed-signal cores: practical oscillation-based test in an analog macrocell, IEEE Design and Test of Computers 19(6) (2002) 73–82). Two methods are used, the describing function approach for the treatment of the non linearity and the root-locus method for analysing the circuit and predicting the oscillation frequency and the oscillation amplitude. In order to establish the accuracy of these predictions, the oscillators have been implemented in SWITCAP (K. Suyama, S.C. Fang, Users' Manual for SWITCAP2 Version 1.1, Columbia University, New York, 1992). Results of a catastrophic fault injection in switches and capacitors of the filter structure are reported. A specification-driven fault list for capacitors is also defined based on the sensitivity analysis. The ability of OBT for detecting this kind of faults is presented.