Although the demise of Moore's law has been predicted many times in the recent past, the emergence of silicon photonics has the potential to extend the lifetime of Moore's law significantly. Using conventional CMOS processing for the generation, routing, and processing of light waves, silicon photonics has finally brought the full power of photonics to very large scale integration (VLSI). However, along with these benefits, significant challenges in computer aided design of silicon photonics have also arisen. This paper presents a novel symbolic method based on Gröbner basis of tangent space polynomials of parametric curves to address these challenges. We analyze the design, optimization and verification of silicon photonic wave guides using parametric polynomials, and demonstrate the powerful method of Gröbner basis functions to solve complex problems such as envelope generation, rectification, manufacturability, singularity detection, reticle and etch processing model generation, tapering loss minimization, and bend loss minimization. We present the use of computer algebra systems such as MAXIMA and REDUCE, to analyze waveguide arrays. In addition, the methods presented in this paper can also be used for the analysis of curves arising from micro-electronic mechanical systems and micro-fluidics VLSI layouts.

Modern very large-scale integration (VLSI) layout databases routinely consist of 10e15 edges, and thus problems of information retrieval, intellectual property (IP) inventory control, tampering detection, IP infringement detection, data tagging, and database version control, are extremely computationally intensive. All these tasks can be reduced to the problem of copy detection, and in this paper, we propose a canonical hash function for VLSI layout datasets which can be used for efficient copy detection and signature generation. The proposed signature is independent of the ordering of the layout elements, their tessellation, resolution, and even vertex count. These parameters, which do not contribute to the final wafer image, increase the entropy of the data and thus standard hash functions such as message digest (MD5) or secure hash algorithm (SHA), are not suitable for this problem of VLSI layout hashing. In this paper, a novel, entropy reduced hash function is developed which can be used to alleviate the above mentioned problems of physical IP management. The proposed method has O(n logn + k) time complexity, and O(√n) memory complexity, where n is the number of edges in the input layout, and k is the number of intersections between edges. The proposed system has been implemented, and computational results validating our approach are also provided.

Testing of embedded core based system-on-chip (SoC) ICs is a well known problem, and the upcoming IEEE P1500 Standard on Embedded Core Test (SECT) standard proposes DFT solutions to alleviate it. One of the proposals is to provide every core in the SoC with test access wrappers. Previous approaches to the problem of wrapper design have proposed static core wrappers, which are designed for a fixed test access mechanism (TAM) width. We present the first report of a design of reconfigurable core wrappers which allow for a dynamic change in the width of the TAM executing the core test. Analysis of the corresponding scheduling problem indicates that good approximate schedules can be achieved without significant computational effort. Specifically, we derive a O(N/sub C//sup 2/B) time algorithm which can compute near optimal SoC test schedules, where N/sub C/ is the number of cores and B is the number of top level TAMs. Experimental results on benchmark SoCs are presented which improve upon integer programming based methods, not only in the quality of the schedule, but also significantly reduce the computation time.

Summary form only given. Reusability of tests is crucial for reducing total design time. This raises the problem of test knowledge transfer, physical test application and test scheduling. We present a formulation of the embedded core-based system-on-chip (SOC) test scheduling problem (ECTSP) as a network transportation problem. The problem is NP-hard and we present a O(mn(m+2n)) 2-approximation algorithm using the result of the single source unsplittable flow problem (U/sub FP/). We have implemented a Test Planner Tool TFLOW with the Common Lisp language using the U/sub FP/ algorithm given by Dinitz et al. (1999).

Test scheduling and TAM (test access mechanism) optimization for core-based SoCs is a challenging problem. Test schedules must be crafted with the objectives of minimizing testing time to reduce test cost, under the constraints of total available TAM width. Moreover precedence relations and power constraints must be met to ensure safe, effective, and high-quality testing. Prior research in test scheduling has mainly used constructive approaches such as rectangle packing to solve this problem, but these approaches fail to address the problem of creating a simple, standard representation for SoC test schedules that can be used by a wide range of optimization algorithms. In this paper we present a novel and efficient method to represent SoC test schedules and TAM width assignment based on the use of k-tuples. The proposed approach provides a compact, standardized representation of test schedules. This facilitates fast and efficient evaluation of SoC test automation solutions to reduce test costs. We propose heuristic algorithms based on the use of k-tuples to solve scheduling problems for SoCs in an efficient manner; extensions to our method to incorporate precedence relations among tests and power constraints in the schedule are also presented. Finally, experimental results using the new ITC'02 SoC benchmarks validate the quality of our solutions.

A formulation of core-based system-on-chip (SoC) test scheduling as a network transportation problem is presented. Given a set of tests, with demands for transportation of test bits (either for test stimuli or test response) and unrelated parallel test resources (e.g., test access mechanisms or built-in self-test engines), the authors determine the start times and resource mappings of all the tests such that the finish time for the complete SoC test is minimized. The problem is NP-hard and they present an approximation algorithm using a result from the solution of the single source unsplittable flow problem. The proposed method uses the number of test bits that need to be transported for a test as the invariant and is hence relatively independent of the test application and execution model. Experimental results on benchmark SoCs demonstrate that their method outperforms the state-of-the-art integer linear programming formulations, not only in terms of schedule quality, but also significantly reduces the computation time.

We address the problem of automatic analysis of geometrically proximate nets in VLSI layout by presenting a framework (named FASCL) which supports pairwise analysis of nets based on a geometric kernel. The exact form of the analysis function can be specified to the kernel, which assumes a coupling function based on pairwise interaction between geometrically proximate nets. The user can also attach these functions to conditions and FASCL will automatically apply the function to all pairs of nets which satisfy a condition. Our method runs with sub-quadratic time complexity, O(N/sup 1+k/), where N is the number of nets and we have proved that k<1. We have successfully used the program to analyze circuits for bridging faults, coupling capacitance extraction, crosstalk analysis, signal integrity analysis and delay fault testing.