3-D ICs can continue to improve power, performance, area, and cost beyond traditional Moore’s law scaling limitations by leveraging the third dimension and short vertical interconnects. Several recent studies present methodologies to implement 3-D ICs, but most of these studies implement each tier separately after partitioning a design into multiple tiers, resulting in inaccurate buffer insertion, which becomes more severe in advanced technology nodes. In this article, we present a new methodology called “Cascade2D flow” which utilizes design and microarchitecture insight for tier partitioning and implements 3-D ICs using 2-D commercial tools. By modeling vertical interconnects with sets of anchor cells and dummy wires, Cascade2D flow places, and routes and optimizes multiple tiers simultaneously in the 2-D version of a 3-D IC called “cascade2D design,” which enables accurate buffer insertion. Two flavors of 3-D ICs—monolithic 3-D (M3D) and face-to-face-bonded (F2F-bonded) 3-D ICs—of a commercial in-order, 32-bit application processor at foundry 28 nm, 14/16 nm, and predictive 7-nm technology nodes are implemented using this new methodology. We investigate the power, performance and area improvements of 3-D ICs over the 2-D counterparts to examine the efficacy of the methodology. Our new methodology outperforms the state-of-the-art 3-D IC design flows in the both flavors of 3-D ICs with up to$4\times $better power savings. In the best case, 3-D ICs from Cascade2D flow show 25% better performance at iso-power and 20% lower power at iso-performance.

Monolithic 3-D IC (M3-D) is a promising solution to improve the performance and energy-efficiency of modern processors. But, designers are faced with challenges in design tools and methodologies, especially for power and thermal verifications. We developed a new physical design flow that optimally places and routes cache modules in one tier and logic gates in the other. Our tool also builds high-quality clock and power delivery networks targeting logic-on-memory M3-D designs. Finally, we developed a sign-off analysis tool flow to evaluate power, performance, area (PPA), thermal, and voltage-drop quality for given M3-D designs. Using our complete register transfer level (RTL)-to-Graphic Design System (GDS) tool flow, we designed commercial quality 2-D and M3-D implementation of Arm Cortex-A7 and Cortex-A53 processors in a commercial 28-nm technology. Experimental results show that our 3-D processors offer 20% (A7) and 21% (A53) performance gain, compared with their 2-D commercial counterparts. The voltage-drop degradation of our 3-D Cortex-A7 and Cortex-A53 processors is less than 3% of the supply voltage, while temperature increase is 10.71 °C and 13.04 °C, respectively.

Due to the short die-to-die distance and inferior heat dissipation capability, Face-to-Face (F2F) boned 3D ICs are often considered to be vulnerable to electrical and thermal coupling. This study is the first to quantify the impacts of the electro-thermal coupling on the full-chip timing, power, and performance. We first present an implementation flow for realistic F2F 3D ICs including pad layers and power grids. Then, we propose our signal integrity analysis, parasitic extraction, and thermal analysis flows. Next, we investigate the impacts of the coupling on the delay, power, and noise of F2F 3D ICs, and provide guidelines to mitigate these effects. Our experimental results show that the inter-die electrical coupling causes up to 5.81% timing degradation and 4.00% noise increase, while the thermal coupling leads to less than 0.41% timing degradation and nearly no noise increase. The impact of the combined electro-thermal coupling on delay and noise reaches 6.07% and 4.05%, respectively.

High-density 3D techniques (such as wafer bonding and monolithic-3D) show tremendous promise in reducing interconnect lengths and relieving 2D congestion. We propose an enhanced 3D implementation methodology and use it to design an Arm Cortex-A microprocessor in 3D. The methodology is fully integrated and tested using commercial EDA tools and incorporates all physical IP needed to implement modern microprocessors. The resulting 3D implementation consists of two parts, 1) a multi-tier co-placement approach for enhanced placement quality, 2) integration of 3D SRAMs for improved microprocessor PPA. Compared to the 2D baseline, our implementations show an overall area reduction of 8.5% and can either achieve an 18% peak frequency uplift at iso-power or a 41% power reduction at near iso-performance (-3% frequency).

As 2-D scaling reaches its limit, monolithic 3-D (M3D) IC is a leading contender for continuing equivalent scaling. Although M3D shows power and performance benefits over 2-D designs, designing a power delivery network (PDN) for M3D is challenging. In this paper, for the first time, we present a system-level PDN model of M3D designs focusing on both resistive (IR) and inductive (Ldi/dt) components of power supply integrity. In addition, we present frequency- and time-domain analyses of M3D PDNs. We show that the additional resistance in M3D PDNs, while being worse for resistive drops, improves resiliency against ac current noise showing 35.9% peak impedance reduction compared to 2-D PDNs during worst case resonant oscillations. Then, we present methodologies to improve power supply integrity of M3D designs based on the observations. Our optimization methodologies offer up to 32.6% and 17.0% static and dynamic voltage drop reduction compared to the baseline M3D designs, respectively, showing 9.0% lower dynamic voltage drop compared to the 2-D counterparts.

Faithful system-level modeling is vital to design and technology pathfinding, and requires accurate representation of interconnects. In this study, Rent's rule is modernized to cater to advanced technology and design, and applied to derive a priori wirelength distribution models. Furthermore, a priori interconnect branching models are proposed to capture design constraints and their handling by the Electronic-Design-Automation tools. These interconnect branching models are embedded into the wirelength distribution models and validated against a suite of state-of-the-art commercial designs across technology nodes. Novel design-specific critical-path models are presented which capture trends in technology and microarchitecture, providing a reliable framework for future technology and design benchmarking.

In this paper, we present full-chip designs and their power, performance, and area (PPA) metrics using the ASAP7 process design kit (PDK) and library. Reliable cell library is a key element in evaluating new technological options such as monolithic 3D (M3D) ICs. Given an RTL, we conduct synthesis and place/route to obtain commercial-quality 2D and M3D IC designs and compare PPA. The ASAP7 library is highly useful to build high-quality designs that accurately reflect 7nm technology node. In addition, the full front-end and back-end access provided in ASAP7 allows us to see the impact of various device and interconnect parameters at the full-chip level for both 2D and monolithic 3D ICs. This work demonstrates the critical role of an academic PDK and library in enabling high-quality research in disruptive technologies such as M3D integration.

Standard cell libraries are the foundation for the entire back-end design and optimization flow in modern application-specific integrated circuit designs. At 7nm technology node and beyond, standard cell library design and optimization is becoming increasingly difficult due to extremely complex design constraints, as described in the ASAP7 process design kit (PDK). Notable complexities include discrete transistor sizing due to FinFETs, complicated design rules from lithography and restrictive layout space from modern standard cell architectures. The design methodology presented in this paper enables efficient and high-quality standard cell library design and optimization with the ASAP7 PDK. The key techniques include exhaustive transistor sizing for cell timing optimization, transistor placement with generalized Euler paths and back-end design prototyping for library-level explorations.

As 2D scaling reaches its limit, monolithic 3D IC (M3D) is a leading contender to continue equivalent scaling. Although M3D shows power and performance benefits over 2D designs, designing a power delivery network (PDN) for M3D is challenging. In this paper, for the first time, we present a system-level PDN model of M3D designs focusing on both resistive (IR) and inductive (Ldi/dt) components of power-supply integrity. In addition, we present frequency- and time-domain analysis of the M3D PDN. We show that the additional resistance in the M3D PDN, while being worse for resistive drops, improves resiliency against current noise showing 35.9% peak impedance reduction during worst-case resonant oscillations.

Monolithic 3-D (M3D) IC is one of the potential technologies to break through the challenges of continued circuit power and performance scaling. In this paper, for the first time, we demonstrate the power benefits of M3D and present design guideline in a 7-nm FinFET technology node. The predictive 7-nm process design kit (PDK) and the standard cell library using both high-performance (HP) and low-standby-power (LSTP) device technologies are developed based on NanGate 45-nm PDK using accurate dimensional, material, and electrical parameters from publications and a commercial-grade tool flow. We implement full-chip M3D designs utilizing industry-standard physical design tools, and gauge the impact of M3D technology on performance, power, and area metrics. We also provide the design guidelines as well as a new partitioning methodology to improve M3D design quality. This paper shows that M3D designs outperform 2-D counterparts by 16% and 16.5% on average in terms of isoperformance total power reduction with 7-nm HP and LSTP cell library, respectively. This demonstrates the power benefits of M3D technology in both HP and low-power future generation devices.

Monolithic 3D IC (M3D) has the potential to provide a break-through in the power and performance scaling challenges. We, for the first time, present a comprehensive study of M3D on a commercial design across multiple technology nodes. The performance and power impact of M3D is investigated using a commercial, in-order, 32-bit application processor, implemented on foundry 28nm and 14/16nm process nodes, as well as a predictive 7nm node. We study the factors across the technology nodes that affect the efficiency of M3D, and propose a roadmap for optimum technology and design interaction that will enable the full entitlement of M3D.

In recent years, operating at near-threshold supply voltages has been proposed to improve energy efficiency in circuits, yet decreased efficacy of dynamic voltage scaling has been observed in recent planar technologies. However, foundries have introduced a shift from planar to FinFET fabrication processes. In this paper, we study 7nm FinFET's ability to voltage scale and compare it to planar technologies across three dynamic voltage scaling scenarios. The switch to FinFET allows for a return to strong voltage scalability. We find up to 8.6× higher energy efficiency at NT compared to nominal supply voltage (vs. 4.8× gain in 20nm planar).

Monolithic 3D IC (M3D) can continue to improve power, performance, area and cost beyond traditional Moore's law scaling limitations by leveraging the third-dimension and fine-grained monolithic inter-tier vias (MIVs). Several recent studies present methodologies to implement M3D designs, but most, if not all of these studies implement top and bottom tier separately after partitioning, which results in inaccurate buffer insertion. In this paper, we present a new methodology called ‘Cascade2D’ that utilizes design and micro-architecture insight to partition and implement an M3D design using 2D commercial tools. By modeling MIVs with sets of anchor cells and dummy wires, we implement and optimize both top and bottom tier simultaneously in a single 2D design. M3D designs of a commercial, in-order, 32-bit application processor at the foundry 28nm, 14/16nm and predictive 7nm technology nodes are implemented using this new methodology and we investigate the power, performance and area improvements over 2D designs. Our new methodology consistently outperforms the state-of-the-art M3D design flow with up to 4× better power savings. In the best case scenario, M3D designs from the Cascade2D flow show 25% better performance at iso-power and 20% lower power at isoperformance.

Monolithic 3D IC is an emerging technology to continuously satisfy demands for power reduction under challenges posed by traditional device scaling. In this paper, for the first time, we study power benefits of 4-tier monolithic 3D ICs compared with 2-tier monolithic 3D and 2D ICs. We present a tier partitioning methodology that significantly extends the capability of a state-of-the-art flow built for 2-tier monolithic 3D ICs. We develop two complete RTL-to-GDSII design flows to achieve this goal and offer quantitative comparisons. In addition, we study impacts of inter-tier via usage on 2-tier and 4-tier monolithic 3D ICs. Our experiments show that poorly controlled inter-tier via usage results in up to 6.05% degradation in total power savings. Thus, we develop an effective strategy to achieve inter-tier via configurations to optimize power metrics. Experiments show that 4-tier monolithic 3D ICs outperform 2-tier and 2D IC by 15% and 50% in terms of power and 25% and 75% in area under the same performance.

Test cases that drive an application under test via its graphical user interface (GUI) consist of sequences of steps that perform actions on, or verify the state of, the application user interface. Such tests can be hard to maintain, especially if they are not properly modularized - that is, common steps occur in many test cases, which can make test maintenance cumbersome and expensive. Performing modularization manually can take up considerable human effort. To address this, we present an automated approach for modularizing GUI test cases. Our approach consists of multiple phases. In the first phase, it analyzes individual test cases to partition test steps into candidate subroutines, based on how user-interface elements are accessed in the steps. This phase can analyze the test cases only or also leverage execution traces of the tests, which involves a cost-accuracy tradeoff. In the second phase, the technique compares candidate subroutines across test cases, and refines them to compute the final set of subroutines. In the last phase, it creates callable subroutines, with parameterized data and control flow, and refactors the original tests to call the subroutines with context-specific data and control parameters. Our empirical results, collected using open-source applications, illustrate the effectiveness of the approach.

Enterprise applications are difficult to test because their intended functionality is either not described precisely enough or described in cumbersome business rules. It takes a lot of effort on the part of a test architect to understand all the business rules and design tests that "cover" them, i.e., exercise all their constituent scenarios. Part of the problem is that it takes a complicated set up sequence to drive an application to a state in which a business rule can even fire. In this paper, we present a business rule modeling language that can be used to capture functional specification of an enterprise system. The language makes it possible to build tool support for rule authoring, so that obvious deficiencies in rules can be detected mechanically. Most importantly, we show how to mechanically generate test sequences--i.e., test steps and test data--needed to exercise these business rules. To this end, we translate the rules into logical formulae and use constraint solving to generate test sequences. One of our contributions is to overcome scalability issues in this process, and we do this by using a novel algorithm for organizing search through the space of candidate sequences to discover covering sequences. Our results on three case studies show the promise of our approach.

Monolithic 3D IC (M3D) is one potential technology to help with the challenges of continued circuit power and performance scaling. In this paper, for the first time, the power benefits of monolithic 3D IC (M3D) using a 7nm FinFET technology are investigated. The predictive 7nm Process Design Kit (PDK) and standard cell library for both high performance (HP) and low standby power (LSTP) device technologies are built based on NanGate 45nm PDK using accurate dimensional, material, and electrical parameters from publications and a commercial-grade tool flow. In addition, we implement full-chip M3D GDS layouts using both 7nm HP and LSTP cells and industry-standard physical design tools, and evaluate the resulting full-chip power, performance, and area metrics. Our study first shows that 7nm HP M3D designs outperform 7nm HP 2D designs by 16.8% in terms of iso-performance total power reduction. Moreover, 7nm LSTP M3D designs reduce the total power consumption by 14.3% compared to their 2D counterparts. This convincingly demonstrates the power benefits of M3D technologies in both high performance as well as low power future generation devices.

FinFETs have recently overtaken bulk CMOS transistors as the device of choice for systems-on-chip. This paper provides some background on FinFETs together with their associated manufacturing processes and shows how they influence physical design of standard cells as well as place & route and timing closure for larger blocks.

Despite the seemingly obvious advantage of test automation, significant skepticism exists in the industry regarding its cost-benefit tradeoffs. Test scripts for web applications are fragile: even small changes in the page layout can break a number of tests, requiring the expense of re-automating them. Moreover, a test script created for one browser cannot be relied upon to run on a different web browser: it requires duplicate effort to create and maintain versions of tests for a variety of browsers. Because of these hidden costs, organizations often fall back to manual testing.

Test automation, which involves the conversion of manual test cases to executable test scripts, is necessary to carry out efficient regression testing of GUI-based applications. However, test automation takes significant investment of time and skilled effort. Moreover, it is not a one-time investment: as the application or its environment evolves, test scripts demand continuous patching. Thus, it is challenging to perform test automation in a cost-effective manner. At IBM, we developed a tool, called ATA [1], [2], to meet this challenge. ATA has novel features that are designed to lower the cost of initial test automation significantly. Moreover, ATA has the ability to patch scripts automatically for certain types of application or environment changes. How well does ATA meet its objectives in the real world? In this paper, we present a detailed case study in the context of a challenging production environment: an enterprise web application that has over 6500 manual test cases, comes in two variants, evolves frequently, and needs to be tested on multiple browsers in time-constrained and resource-constrained regression cycles. We measured how well ATA improved the efficiency in initial automation. We also evaluated the effectiveness of ATA's change-resilience along multiple dimensions: application versions, browsers, and browser versions. Our study highlights several lessons for test-automation practitioners as well as open research problems in test automation.

We focus on functional testing of enterprise applications with the goal of exercising an application's interesting behaviors by driving it from its user interface. The difficulty in doing this is focusing on the interesting behaviors among an unbounded number of behaviors. We present a new technique for automatically generating tests that drive a web-based application along interesting behaviors, where the interesting behavior is specified in the form of “business rules.” Business rules are a general mechanism for describing business logic, access control, or even navigational properties of an application's GUI. Our technique is black box, in that it does not analyze the application's server-side implementation, but relies on directed crawling via the application's GUI. To handle the unbounded number of GUI states, the technique includes two phases. Phase 1 creates an abstract state-transition diagram using a relaxed notion of equivalence of GUI states without considering rules. Next, Phase 2 identifies rule-relevant abstract paths and refines those paths using a stricter notion of state equivalence. Our technique can be much more effective at covering business rules than an undirected technique, developed as an enhancement of an existing test-generation technique. Our experiments showed that the former was able to cover 92% of the rules, compared to 52% of the rules covered by the latter.

Predictive MOSFET models are critical for early stage design-technology co-optimization and circuit design research. In this work, Predictive Technology Model files for sub-20nm multi-gate transistors have been developed (PTM-MG). Based on MOSFET scaling theory, the 2011 ITRS roadmap and early stage silicon data from published results, PTM for FinFET devices are generated for 5 technology nodes corresponding to the years 2012-2020 on the ITRS roadmap.

Mention “test case”, and it conjures up the image of a script or a program that exercises a system under test. In industrial practice, however, test cases often start out as steps described in natural language. These are essentially directions a human tester needs to follow to interact with an application, exercising a given scenario. Since tests need to be executed repeatedly, such manual tests then have to go through test automation to create scripts or programs out of them. Test automation can be expensive in programmer time. We describe a technique to automate test automation. The input to our technique is a sequence of steps written in natural language, and the output is a sequence of procedure calls with accompanying parameters that can drive the application without human intervention. The technique is based on looking at the natural language test steps as consisting of segments that describe actions on targets, except that there can be ambiguity in identifying segments, in identifying the action in a segment, as well as in the specification of the target of the action. The technique resolves this ambiguity by backtracking, until it can synthesize a successful sequence of calls. We present an evaluation of our technique on professionally created manual test cases for two open-source web applications as well as a proprietary enterprise application. Our technique could automate over 82% of the steps contained in these test cases with no human intervention, indicating that the technique can reduce the cost of test automation quite effectively.

The coming ten years promise great changes in silicon technology, with the end of planar bulk CMOS and the rise of interconnect parasitics to true significance. With such shifts in the underlying technology, the simple extrapolation of performance metrics may lead to pronounced prediction errors in design pathfinding. In this work, we utilize newly developed Predictive Technology Models for FinFETs aligned to the 2011 ITRS. Together with predictive interconnect models, we project performance and power landscape for the technology nodes from 20nm to 7nm. We present an overview of models, assess the advantage of FinFET over bulk CMOS devices, benchmark the scaling of critical design metrics, and illustrate major design barriers toward the 7nm node.

In industrial practice, test cases often start out as steps described in natural language and are intended to be executed by a human. Since tests are executed repeatedly, they go through an automation process, in which they are converted to automated test scripts (or programs) that perform the test steps mechanically. Conventional test-automation techniques can be time-consuming, require specialized skills, and can produce fragile scripts. To address these limitations, we present a tool, called ata, for automating the test-automation task. Using a novel combination of natural-language processing, backtracking exploration, and learning, ata can significantly improve tester productivity in automating manual tests. ata also produces change-resilient scripts, which automatically adapt themselves in the presence of certain common types of user-interface changes.

In the era of globally distributed software engineering, the practice of outsourced, off shored software testing (OOST) has witnessed increasing adoption. Although there have been ethnographic studies of the development aspects of global software engineering and of the in-house practice of testing, there have been fewer studies of OOST, which to succeed, can require dealing with unique challenges. To address this limitation of the existing studies, we conducted-and, in this paper, report the findings of-an ethnographically-informed study of three vendor testing teams involved in OOST practice. Specifically, we studied how test engineers perform their tasks under deadline pressures, the challenges that they encounter, and their strategies for coping with the challenges. Our study provides insights into the differences and similarities between in-house testing and OOST, the influence of team structures on the degree of pressure experienced by test engineers in the OOST setup, and the factors that influence quality and productivity under OOST.

The success of an open-source project depends to a large degree on the proactive and constructive participation by the developer community. An important role that developers play in a project is that of a code committer. However, code-commit privilege is typically restricted to the core group of a project. In this paper, we study the phenomenon of the induction of external developers as code committers. The trustworthiness of an external developer is one of the key factors that determines the granting of commit privileges. Therefore, we formulate different hypotheses to explain how the trust is established in practice. To investigate our hypotheses, we developed an automated approach based on mining code repositories and bug-tracking systems. We implemented the approach and performed an empirical study, using the Eclipse projects, to test the hypotheses. Our results indicate that, most frequently, developers establish trust and credibility in a project by contributing to the project in a non-committer role. Moreover, the employing organization of a developer is another factor--although a less significant one--that influences trust.

Given the high costs of software testing and fixing bugs after release, early detection of bugs using static analysis can result in significant savings. However, despite their many benefits, recent availability of many such tools, and evidence of a positive return-on-investment, static-analysis tools are not used widely because of various usability and usefulness problems. The usability inhibitors include the lack of features, such as capabilities to merge reports from multiple tools and view warning deltas between two builds of a system. The usefulness problems are related primarily to the accuracy of the tools: identification of false positives (or, spurious bugs) and uninteresting bugs among the true positives. In this paper, we present the details of an online portal, developed at IBM Research, to address these problems and promote the adoption of static-analysis tools. We report our experience with the deployment of the portal within the IBM developer community. We also highlight the problems that we have learned are important to address, and present our approach toward solving some of those problems.

Although many static-analysis techniques have been developed for automatically detecting bugs, such as null dereferences, fewer automated approaches have been presented for analyzing whether and how such bugs are fixed. Attempted bug fixes may be incomplete in that a related manifestation of the bug remains unfixed. In this paper, we characterize the “completeness” of attempted bug fixes that involve the flow of invalid values from one program point to another, such as null dereferences, in Java programs. Our characterization is based on the definition of a bug neighborhood, which is a scope of flows of invalid values. We present an automated analysis that, given two versions P and P' of a program, identifies the bugs in P that have been fixed in P', and classifies each fix as complete or incomplete. We implemented our technique for null-dereference bugs and conducted empirical studies using open-source projects. Our results indicate that, for the projects we studied, many bug fixes are not complete, and thus, may cause failures in subsequent executions of the program.

A workload-aware low-power neuromorphic controller for dynamic voltage scaling in VLSI systems is presented. The neuromorphic controller predicts future workload values and preemptively regulates supply voltage based on past workload profile. Our specific contributions include: (1) implementation of a digital and analog version of the controller in 45nm CMOS technology, resulting in 3% performance hit with a power overhead in the range of 10-150 microwatts, (2) higher prediction accuracy compared to a software based OS-governed DVS scheme by 50%, reducing wasted power and improving error margins, (3) digital design has minimal power overhead and is more reconfigurable, while analog design is better suited for nonlinear and complex computational tasks.

Model transforms are a class of applications that convert a model to another model or text. The inputs to such transforms are often large and complex; therefore, faults in the models that cause a transformation to generate incorrect output can be difficult to identify and fix. In previous work, we presented an approach that uses dynamic tainting to help locate input-model faults. In this paper, we present techniques to assist with repairing input-model faults. Our approach collects runtime information for the failing transformation, and computes repair actions that are targeted toward fixing the immediate cause of the failure. In many cases, these repair actions result in the generation of the correct output. In other cases, the initial fix can be incomplete, with the input model requiring further repairs. To address this, we present a pattern-analysis technique that identifies correct output fragments that are similar to the incorrect fragment and, based on the taint information associated with such fragments, computes additional repair actions. We present the results of empirical studies, conducted using real model transforms, which illustrate the applicability and effectiveness of our approach for repairing different types of faults.

Resonant clock distribution with distributed LC oscillators is promising to reducing clock power and jitter noise. Yet the difficulty in the integration of on-chip inductors still limits its application in practice. This paper resolves such a key issue with sub-50 ¿m magnetic inductors, which are fully compatible with the CMOS process. These inductors leverage soft magnetic coils to achieve inductances up to 4nH, Q-factor of 3 at 1 GHz with a device diameter of only 30-50 ¿m, resulting in area savings of nearly 100X as compared to conventional design. The latency and noise performance of the resonant clock network is demonstrated to be comparable to those using conventional inductors without soft magnetic materials. In addition, inductors with integrated magnetic materials significantly reduce mutual coupling and eddy current loss in the power grid below the clock network. These design advantages enable high density of on-chip distributed oscillators, providing better phase averaging, lower power and superior noise characteristics as compared to traditional buffer-tree based clock network.

Null dereference is a commonly occurring defect in Java programs, and many static-analysis tools identify such defects. However, most of the existing tools perform a limited interprocedural analysis. In this paper, we present an interprocedural path-sensitive and context-sensitive analysis for identifying null dereferences. Starting at a dereference statement, our approach performs a backward demand-driven analysis to identify precisely paths along which null values may flow to the dereference. The demand-driven analysis avoids an exhaustive program exploration, which lets it scale to large programs. We present the results of empirical studies conducted using large open-source and commercial products. Our results show that: (1) our approach detects fewer false positives, and significantly more interprocedural true positives, than other commonly used tools; (2) the analysis scales to large subjects; and (3) the identified defects are often deleted in subsequent releases, which indicates that the reported defects are important.

Service-oriented applications can be expensive to test because services are hosted remotely, are potentially shared among many users, and may have costs associated with their invocation. In this paper, we present an approach for reducing the costs of testing such applications. The key observation underlying our approach is that certain aspects of an application can be tested using locally deployed semantic service stubs, instead of actual remote services.A semantic service stub incorporates some of the service functionality, such as verifying preconditions and generating output messages based on post conditions. We illustrate how semantic stubs can enable the client test suite to be partitioned into subsets, some of which need not be executed using remote services. We also present a case study that demonstrates the feasibility of the approach, and potential cost savings for testing. The main benefits of our approach are that it can (1) reduce the number of test cases that need to be run to invoke remote services, (2) ensure that certain aspects of application functionality are well-tested before service integration occurs.

This paper presents a new approach for locating and repairing faults that cause runtime exceptions in Java programs. The approach handles runtime exceptions that involve a flow of an incorrect value that finally leads to the exception. This important class of exceptions includes exceptions related to dereferences of null pointers, arithmetic faults (e.g., ArithmeticException), and type faults (e.g., ArrayStoreException). Given a statement at which such an exception occurred, the technique combines dynamic analysis (using stack-trace information) with static backward data-flow analysis (beginning at the point where the runtime exception occurred) to identify the source statement at which an incorrect assignment was made; this information is required to locate the fault. The approach also identifies the source statements that may cause this same exception on other executions, along with the reference statements that may raise an exception in other executions because of this incorrect assignment; this information is required to repair the fault. The paper also presents an application of our technique to null pointer exceptions. Finally, the paper describes an implementation of the null-pointer-exception analysis and a set of studies that demonstrate the advantages of our approach for locating and repairing faults in the program.

Model-driven development (MDD) is widely used to develop modern business applications. MDD involves creating models at different levels of abstractions. Starting with models of domain concepts, these abstractions are successively refined, using transforms, to design-level models and, eventually, code-level artifacts. Although many tools exist that support transform creation and verification, tools that help users in understanding and using transforms are rare. In this paper, we present an approach for assisting users in understanding model transformations and debugging their input models. We use automated program-analysis techniques to analyze the transform code and compute constraints under which a transformation may fail or be incomplete. These code-level constraints are mapped to the input model elements to generate model-level rules. The rules can be used to validate whether an input model violates transform constraints, and to support general user queries about a transformation. We have implemented the analysis in a tool called XYLEM. We present empirical results, which indicate that (1) our approach can be effective in inferring useful rules, and (2) the rules let users efficiently diagnose a failing transformation without examining the transform source code.

Carbon nanotube transistor (CNT) is promising to be the technology of choice for nanoscale integration. In this work, we develop the first compact model of CNT, with the objective to explore the optimal process and design space for robust low-power applications. Based on the concept of the surface potential, the new model accurately predicts the characteristics of a CNT device under various process and design conditions, such as diameter, chirality, gate dielectrics, and bias voltages. With the physical modeling of the contact, this model covers both the Schottky-barrier CNT (SB-CNT) and MOS-type CNT. The proposed model does not require any iteration and thus, significantly enhances the simulation efficiency to support large-scale design research. Using this model, we benchmark the performance of a FO4 inverter with CNT and 22nm CMOS technology. The following key insights are extracted: (1) even with the SB-CNT and realistic layout parasitics, the circuit speed can be more than 10X that of 22nm CMOS; (2) The diameter range of 1-1.5nm exhibits the maximum tolerance to contact materials and process variations; (3) a CNT circuit allows better scaling of the supply voltage (Vdd) for power reduction. For a fixed energy consumption and Vdd, the CNT speed is 4X that of 22nm CMOS. Overall, the new model enables efficient design research with CNT, revealing tremendous opportunities for both high-speed and low-power applications.

Program-dependence information is useful for a variety of applications, such as software testing and maintenance tasks, and code optimization. Properly defined, control and data dependences can be used to identify semantic dependences. To function effectively on whole programs, tools that utilize dependence information require information about interprocedural dependences: dependences that are identified by analyzing the interactions among procedures. Many techniques for computing interprocedural data dependences exist; however, virtually no attention has been paid to interprocedural control dependence. Analysis techniques that fail to account for interprocedural control dependences can suffer unnecessary imprecision and loss of safety. This article presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence. The article presents two approaches for computing interprocedural control dependences, and empirical results pertaining to teh use of those approaches.

Analysis techniques, such as control flow, data flow, and control dependence, are used for a variety of software engineering tasks, including structural and regression testing, dynamic execution profiling, static and dynamic slicing, and program understanding. To be applicable to programs in languages such as Java and C++, these analysis techniques must account for the effects of exception occurrences and exception handling constructs; failure to do so can cause the analysis techniques to compute incorrect results and, thus, limit the usefulness of the applications that use them. This paper discusses the effects of exception handling constructs on several analysis techniques. The paper presents techniques to construct representations for programs with explicit exception occurrences-exceptions that are raised explicitly through throw statements-and exception handling constructs. The paper presents algorithms that use these representations to perform the desired analyses. The paper also discusses several software engineering applications that use these analyses. Finally, the paper describes empirical results pertaining to the occurrence of exception handling constructs in Java programs and their effect on some analysis tasks.

Many algorithms for automating software engineering tasks require program slices. To be applicable to large software systems, these slices must be computed interprocedurally. Slicing techniques based on the system dependence graph (SDG) provide one approach for computing interprocedural slices, but these techniques are defined only for programs in which called procedures necessarily return to call sites. When applied to programs that contain arbitrary interprocedural control flow, existing SDG-based slicing techniques can compute incorrect slices; this limits their applicability. This paper presents an approach to constructing SDGs, and computing slices on SDGs, that accommodates programs with arbitrary interprocedural control flow. The main benefit of our approach is that it allows the use of the SDG-based slicing technique on a wide class of practical programs to which it did not previously apply.

Exception-handling constructs provide a mechanism for mixing exceptions and a facility for designating protected code by attaching exception handlers to blocks of code. Despite the frequency of their occurrences, the behavior of exception-handling constructs is often the least understood and poorly tested part of a program. The presence of such constructs introduces new structural elements, such as control-flow paths, in a program. To adequately test such programs, these new structural elements must be considered for coverage during structural testing. In this paper, we describe a class of adequacy criteria that can be used to test the behavior of exception-handling constructs. We present a subsumption hierarchy of the criteria, and illustrate the relationship of the criteria to those found in traditional subsumption hierarchies. We describe techniques for generating the testing requirements for the criteria using our control-flow representations. We also describe a methodology for applying the criteria to unit and integration testing of programs that contain exception-handling constructs.

Analysis techniques, such as control flow, data flow, and control dependence, are used for a variety of maintenance tasks, including regression testing, dynamic execution profiling, and static and dynamic slicing. To be applicable to programs in languages, such as Java and C++ however, these analysis techniques should, to the extent possible, account for the effects of exception occurrences and exception handling constructs. The paper presents techniques to construct intraprocedural and interprocedural representations on which existing techniques can be performed and demonstrates their applicability to several maintenance tasks.

Program dependence information is useful for a variety of software testing and maintenance tasks. Properly defined, control and data dependencies can be used to identify semantic dependencies. To function effectively on whole programs, tools that utilize dependence information require information about interprocedural dependencies: dependencies that exist because of interactions among procedures. Many techniques for computing data and control dependencies exist; however, in our search of the literature we find only one attempt to define and compute interprocedural control dependencies. Unfortunately, that approach can omit important control dependencies, and incorrectly identifies control dependencies for a large class of programs. This paper presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence, an efficient algorithm for calculating interprocedural control dependencies, and empirical results obtained by our implementation of the algorithm.