Department of Electrical and Computer Engineering

VLSI CAD Project

Supergate Implementation with Minimum Number of Transistors

Optimizing the performance of a circuit with respect to implementation cost, operational speed, and power requirements is the fundamental problem in digital electronic design. In the custom design approach, a transistorlevel implementation for the required functions is selected and an appropriate physical layout is made. For most commercial applications the required effort for transistor-level implementations may be prohibitive, in which case standard cell libraries are used. In the standard-cell-library approach, the main effort is the technology mapping between alternative implementations of the design and the preexisting elements of the library. Such an approach may be beneficial for reducing the design effort, but may not be able to achieve a desired level of performance. If high performance is required, the custom design approach has to be followed at least for the critical parts of the circuit. In such performance-critical cases, selecting the appropriate transistorlevel implementation for complex gates (supergates) is not trivial and the use of suitable CAD methods is needed. The proposed synthesis methodology accepts a Sum-of-Products expression that may have been simplified by any of the traditional approaches. It obtains from that an efficient (in terms of transistor-count) network, which in general is not series-parallel. The specific transistor network can then be used to implement various structures such as the following: (1) a supergate with function F in classic Domino logic, assuming that the given Sum-of-Products represents F; (2) the n-MOS network of a supergate with function F in Full CMOS (FCMOS) logic, assuming that the given Sum-of-Products represents F_not; (3) the p-MOS network (where all literals in the derived network have been inverted) of a supergate with function F in FCMOS logic, assuming that the given Sum-of-Products represents F. Note tat for the FCMOS implementation, the proposed methodology needs actually to be given (in separate steps) (i) the set of product terms of F from which it obtains the transistor network for the p-MOS part, and (ii) the set of product terms of F_not from which it obtains the transistor network for the n- MOS part. The n-MOS and p-MOS networks obtained by the proposed synthesis methodology are not necessarily related by simple series-parallel conversion rules, since each obtained transistor network is in general non-series-parallel. The basic methodology, described in D. Kagaris, T. Haniotakis, "A Methodology for Transistor-Efficient Supergate Design," IEEE Transactions on VLSI Systems, v. 15, n. 4, pp. 488-492, Apr. 2007, has been shown to substantially reduce the number of transistors for supergate implementation. It also results in faster implementations. This methodology forms the basis also for efficient low-power design of supergates as well as multi-output supergates.

VLSI Test Project

Built-in Test Mechanisms and Embedded Cores

In this project (funded by the National Science Foundation (NSF)), the problem of designing testable cores is viewed as that of selecting appropriate components in the core, called Core Components (CCs), for which no implementation details are released. Netlist information for the remaining portion of the core, the external core component (ECC), is generated but the selection of the CCs guarantees protection of the pre-designed intellectual core property and simplifies the testing process.It is proposed to test for functional faults by testing all CCs using primarily Built-In Self-Testable (BIST) schemes or scan techniques, and then bypassing them when the ECC is tested with scan techniques.BIST CCs will be used whenever the hardware overhead is low. Delay faults in the designed core are tested by combining gate-level ATPGs for the ECC with functional-level testing for the selected CCs. Delay faults associated with paths in the CCs may be tested using BIST schemes or scan designs. The segment path delay fault model may also be used for delayfault testing.The CCs are either BIST CCs or scan CCs according to the built-in test methodology used. Scan CCs are enclosed in boundary scan isolation rings that ensure controllability and observability of the CC.They are tested in a different session than the ECC and their rings participate in the scan chain used for testing the ECC. BIST CCs can be tested while testing the ECC. Scan CCs require less hardware overhead than that of BIST CCs and enhance the controllability/observability of the ECC.However, they prolong the overall test application time, and cause larger delays on critical paths.Also BIST CCs are better suited to at-speed testing, field testing, and are not affected by intra-chip delays when considering testing at the system and board level.Our research direction indicates a very important application of BIST.The current concern of BIST in ASICs is primarily its hardware overhead. In our context,however, there is enough freedom for generating CCs with low BIST hardware.Important research decisions include the number, location, sizes and types of the selected CCs but also the ratio of the BIST over scan CCs in the core.The selection of the CCs must guarantee that the intellectual property of the core is protected, the overall hardware overhead for testingthe CCs and the ECC is small, and the core is testable.The practicality of the overall scheme depends to a great extend on the proposed mechanisms for on-CC TPGs as well as Design-for-Testability (DFT) techniques for improving on-CC TPG or efficient scan designs that are used either to test the ECC or some of the CCs.(The investigators believe that existing response verification schemes can be used effectively for on-CC verification.)Research on the latter topics is of interest by its own since any ASIC can be considered a single CC.The proposed on-chip TPGs concern the generation of both deterministic and pseudorandom test sets, for either individual test patterns (needed for stuck-at faults in combinational circuits), test pattern pairs (needed for path delay faults or CMOS stuck-open faults),or test pattern sequences (needed for sequential circuits). They center around LFSRs, weighted random LFSRs, Cellular Automata,binary counters, ALUs, and combinations thereof. The DFT techniques apply test point insertion and advanced logic optimization methods such as retiming and resynthesis.They reduce the hardware overhead when applied to BIST CCs whereas for scan CCs and the ECC they also target the test application time.

Large Integrated MAC and Routing Protocols for Scalable MANETs

This project concerns the design of efficient protocols for the organization and management of mobile ad hoc networks (MANETs).The investigated protocols focus on the Medium Access Control (MAC) layer and the Network (routing) layer. The distinctive guiding principles in our approach is the integration of the protocols on the two levels and the scalability of the overall architecture.The first objective, integration, allows tighter coupling of the protocols in the two levels, so that appropriate information can be fed back from one to the other with the aim of improving the overall performance of the MANET. Traditional approaches rely on information that is provided only in one direction (i.e., weight assignments on links and/or nodes for routing purposes are obtained from the measurements on the lower level).In addition, traditional approaches built network layer protocols on top of previously developed MAC layer protocols that were not explicitly designed with mobility in mind.In contrast, the proposed architecture allows information, such as frequency and bandwidth, that is gathered during the discovery of a route in a mobile environment, to be passed down to the MAC layer for more efficient operation of its protocols. The second objective, scalability, allows the application of the proposed architecture to very large MANETs. Scalability is a crucial problem that has not been adequately solved by any existing approach so far. Scalability is identified as the major issue in the design of the network layer protocol and can only be obtained by some means of a hierarchical architecture that must be proactively updated in a distributed manner. The proposed architecture is dynamically reconfigurable and is supported by fast distributed algorithms. The routing protocol uses fast, scalable algorithms and takes also quality--of--service (QoS) requirements into account. The management protocol focuses on the mobile context issues of hierarchical cluster reconfiguration and of time scheduling for power conservation. This scheduling decision needs global information that is naturally available at the network layer,and more importantly, does not invalidate scheduling decisions for power conservation taken at the MAC layer. Finally, the supporting MAC layer protocol uses a multiple access reservation scheme that is designed with the routing and power conservation goals in mind.