Template-based circuit understanding

When verifying or reverse-engineering digital circuits, one often wants to identify and understand small components in a larger system. A possible approach is to show that the sub-circuit under investigation is functionally equivalent to a reference implementation. In many cases, this task is difficult as one may not have full information about the mapping between input and output of the two circuits, or because the equivalence depends on settings of control inputs. We propose a template-based approach that automates this process. It extracts a functional description for a low-level combinational circuit by showing it to be equivalent to a reference implementation, while synthesizing an appropriate mapping of input and output signals and setting of control signals. The method relies on solving an exists/forall problem using an SMT solver, and on a pruning technique based on signature computation.

Additive tissue manufacturing for breast reconstruction: Combining CAD/CAM with adipose tissue engineering

The primary aim of this multidisciplinary project was to develop a new generation of breast implants. Disrupting the currently prevailing paradigm of silicone implants which permanently introduce a foreign body into mastectomy patients, highly porous implants developed as part of this PhD project are biodegradable by the body and augment the growth of natural tissue. Our technology platform leverages computer-assisted-design which allows us to manufacture fully patient-specific implants based on a personalised medicine approach. Multiple animal studies conducted in this project have shown that the polymeric implant slowly degrades within the body harmlessly while the body's own tissue forms concurrently.

Contributing to computing services to benchmarking asset management knowledge management

Asset management has broadened from a focus on maintenance management to whole of life cycle asset management requiring a suite of new competencies from asset procurement to management and disposal. Well developed skills and competencies as well as practical experience are a prerequisite to maintain capability, to manage demand as well to plan and set priorities and ensure on-going asset sustainability. This paper has as its focus to establish critical understandings of data, information and knowledge for asset management along with the way in which benchmarking these attributes through computer-aided design may aid a strategic approach to asset management. The paper provides suggestions to improve sharing, integration and creation of asset-related knowledge through the application of codification and personalization approaches.

A study of placement algorithms through trial interchange of logic modules

Based on trial interchanges, this paper develops three algorithms for the solution of the placement problem of logic modules in a circuit. A significant decrease in the computation time of such placement algorithms can be achieved by restricting the trial interchanges to only a subset of all the modules in a circuit. The three algorithms are simulated on a DEC 1090 system in Pascal and the performance of these algorithms in terms of total wirelength and computation time is compared with the results obtained by Steinberg, for the 34-module backboard wiring problem. Performance analysis of the first two algorithms reveals that algorithms based on pairwise trial interchanges (2 interchanges) achieve a desired placement faster than the algorithms based on trial N interchanges. The first two algorithms do not perform better than Steinberg's algorithm1, whereas the third algorithm based on trial pairwise interchange among unconnected pairs of modules (UPM) and connected pairs of modules (CPM) performs better than Steinberg's algorithm, both in terms of total wirelength (TWL) and computation time.

Data definition and manipulation languages for a CAD database

In this paper the main features of ARDBID (A Relational Database for Interactive Design) have been described. An overview of the organization of the database has been presented and a detailed description of the data definition and manipulation languages has been given. These have been implemented on a DEC 1090 system.

Algorithm for incremental compaction of geometrical layouts

In this paper, a new incremental algorithm for layout compaction is proposed. In addition to its linear time performance in terms of the number of rectangles in the layout, we also describe how incremental compaction can form a good feature in the design of a layout editor. The design of such an editor is also described. In the design of the editor, we describe how arrays can be used to implement quadtrees that represent VLSI layouts. Such a representation provides speed of data access and low storage requirements.

Set theoretic operations on polygons using the scan-grid approach

This paper describes an algorithm to compute the union, intersection and difference of two polygons using a scan-grid approach. Basically, in this method, the screen is divided into cells and the algorithm is applied to each cell in turn. The output from all the cells is integrated to yield a representation of the output polygon. In most cells, no computation is required and thus the algorithm is a fast one. The algorithm has been implemented for polygons but can be extended to polyhedra as well. The algorithm is shown to take O(N) time in the average case where N is the total number of edges of the two input polygons.

Käsityöläisyyden kuva kultasepän ammatissa : Käsityöläisyys Suomen Kultaseppien Liiton lehdessä 1990-luvun lopussa

The aim of this study is to survey the meaning of craftmanship in goldsmith occupation. The image of craftmanship is built theoretically as well as researcher's own practical experience. The study describes a dialogue between self-employed goldsmith s everyday work and trade union's opinion. Suomen Kultaseppien Liitto (The Goldsmith Assosiation of Finland) was chosen forthe trade union, because it is the biggest, the oldest and the most influential on the occupational area. The research data are volumes 1995 - 1998 of occupational membership journal of Suomen Kultaseppien Liitto. The data analyzed with Adapted Content Analysis and Grounded Theory. The professional occupation of goldsmiths, the role of craftmanship and the future of the occupation are discussed. Additionally, the relationship between the Suomen Kultaseppien Liitto and occupational culture and profession of goldsmiths was studied. Craft and craftmanship is most often discussed in articles related to tradition and education.Craftmanship is understood very idealistically, with little meaning in practical life. St. Eligius and the skill and art of goldsmiths in St Petersburg are raised to symbols of craftmanship. The occupational image is broken and a clear conflict between education and occupation is visible. Education produces artist-craftsmen, while handicraft workers are required in industry, and retailers or specially trained store assistant in business. Computer-aided design and manufacture render handicraft workmanship unnecessary. In a pessimistic view, the future possibilities of the goldsmith occupational profession are dim, because the artist-craftsmen are bound to lose to fast-paced machines. On the other hand, people involved in goldsmith education see the future light, designer-goldsmiths developing the occupational to new dimensions. Suomen Kultaseppien Liitto represents goldsmiths in public. The union, however is governed by non-artisan goldsmiths. The union stresses business attitudes and enterpreneurship, and has succeeded in protecting the privileges of retailers and industry. Goldsmiths profession is seen in the research data as a combination of precious-metal industry, jewellery and watch stores, anda goldsmith shop is considered a specialized giftstore. The goldsmiths occupation is not a profession, and the Suomen Kultaseppien Liitto is not a trade union for artist and craftmen. Accordingly, part of the representative authority of the union could be transferred from the Association to Taidekäsityöläiset Taiko ry, a member of organization of Ornamo. Results of this study show the importance of defining the images of the goldsmith occupational profession and the trade union. The results could be applied to goldsmith education to examine what would be the optimal education and training for present employment opportunities. The important background theories has been the theories of Habermas and Lévi-Strauss.

2 Algorithms For 3-Layer Channel Routing

A channel router is an important design aid in the design automation of VLSI circuit layout. Many algorithms have been developed based on various wiring models with routing done on two layers. With the recent advances in VLSI process technology, it is possible to have three independent layers for interconnection. In this paper two algorithms are presented for three-layer channel routing. The first assumes a very simple wiring model. This enables the routing problem to be solved optimally in a time of O(n log n). The second algorithm is for a different wiring model and has an upper bound of O(n2) for its execution time. It uses fewer horizontal tracks than the first algorithm. For the second model the channel width is not bounded by the channel density.

FSK bursts for efficient clutter rejection

The clutter-rejection properties of compact f.s.k. bursts with amplitude modulation are investigated. A procedure for computer-aided design of such signals is given. The loss of clutter performance on constraining the individual pulse amplitudes to be equal is evaluated.

Automated inspection of aircraft parts using a modified ICP algorithm

The application of computer-aided inspection integrated with the coordinate measuring machine and laser scanners to inspect manufactured aircraft parts using robust registration of two-point datasets is a subject of active research in computational metrology. This paper presents a novel approach to automated inspection by matching shapes based on the modified iterative closest point (ICP) method to define a criterion for the acceptance or rejection of a part. This procedure improves upon existing methods by doing away with the following, viz., the need for constructing either a tessellated or smooth representation of the inspected part and requirements for an a priori knowledge of approximate registration and correspondence between the points representing the computer-aided design datasets and the part to be inspected. In addition, this procedure establishes a better measure for error between the two matched datasets. The use of localized region-based triangulation is proposed for tracking the error. The approach described improves the convergence of the ICP technique with a dramatic decrease in computational effort. Experimental results obtained by implementing this proposed approach using both synthetic and practical data show that the present method is efficient and robust. This method thereby validates the algorithm, and the examples demonstrate its potential to be used in engineering applications.

CAD Standardization in Construction – a Process View

There has been a demand for uniform CAD standards in the construction industry ever since the large-scale introduction of computer aided design systems in the late 1980s. While some standards have been widely adopted without much formal effort, other standards have failed to gain support even though considerable resources have been allocated for the purpose. Establishing a standard concerning building information modeling has been one particularly active area of industry development and scientific interest within recent years. In this paper, four different standards are discussed as cases: the IGES and DXF/DWG standards for representing the graphics in 2D drawings, the ISO 13567 standard for the structuring of building information on layers, and the IFC standard for building product models. Based on a literature study combined with two qualitative interview studies with domain experts, a process model is proposed to describe and interpret the contrasting histories of past CAD standardisation processes.

Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Voltage and Temperature Aware Statistical Leakage Analysis Framework Using Artificial Neural Networks

Artificial neural networks (ANNs) have shown great promise in modeling circuit parameters for computer aided design applications. Leakage currents, which depend on process parameters, supply voltage and temperature can be modeled accurately with ANNs. However, the complex nature of the ANN model, with the standard sigmoidal activation functions, does not allow analytical expressions for its mean and variance. We propose the use of a new activation function that allows us to derive an analytical expression for the mean and a semi-analytical expression for the variance of the ANN-based leakage model. To the best of our knowledge this is the first result in this direction. Our neural network model also includes the voltage and temperature as input parameters, thereby enabling voltage and temperature aware statistical leakage analysis (SLA). All existing SLA frameworks are closely tied to the exponential polynomial leakage model and hence fail to work with sophisticated ANN models. In this paper, we also set up an SLA framework that can efficiently work with these ANN models. Results show that the cumulative distribution function of leakage current of ISCAS'85 circuits can be predicted accurately with the error in mean and standard deviation, compared to Monte Carlo-based simulations, being less than 1% and 2% respectively across a range of voltage and temperature values.

Impact of energy quantisation in single electron transistor island on hybrid complementary metal oxide semiconductor-single electron transistor integrated circuits

For the first time, the impact of energy quantisation in single electron transistor (SET) island on the performance of hybrid complementary metal oxide semiconductor (CMOS)-SET transistor circuits has been studied. It has been shown through simple analytical models that energy quantisation primarily increases the Coulomb Blockade area and Coulomb Blockade oscillation periodicity of the SET device and thus influences the performance of hybrid CMOS-SET circuits. A novel computer aided design (CAD) framework has been developed for hybrid CMOS-SET co-simulation, which uses Monte Carlo (MC) simulator for SET devices along with conventional SPICE for metal oxide semiconductor devices. Using this co-simulation framework, the effects of energy quantisation have been studied for some hybrid circuits, namely, SETMOS, multiband voltage filter and multiple valued logic circuits. Although energy quantisation immensely deteriorates the performance of the hybrid circuits, it has been shown that the performance degradation because of energy quantisation can be compensated by properly tuning the bias current of the current-biased SET devices within the hybrid CMOS-SET circuits. Although this study is primarily done by exhaustive MC simulation, effort has also been put to develop first-order compact model for SET that includes energy quantisation effects. Finally, it has been demonstrated that one can predict the SET behaviour under energy quantisation with reasonable accuracy by slightly modifying the existing SET compact models that are valid for metallic devices having continuous energy states.