Preface

The Computer and Information Science and Engineering (CISE) Directorate, under the direction of an Assistant Director, consists of the following six divisions and offices: Advanced Scientific Computing (ASC) Division, Computer and Computation Research (CCR) Division, Cross-Disciplinary Activities (CDA) Office, Information, Robotics and Intelligent Systems (IRIS) Division, Microelectronic Information Processing Systems (MIPS) Division, and the Networking and Communications Research and Infrastructure (NCRI) Division.

The Microelectronic Information Processing Systems (MIPS) Division supports research on novel computing and information processing systems including signal processing. Emphasis is on experimental research, technology-related research and particularly the critical link between conceptualization and realization for integrated systems. Technologies include VLSI, ULSI, OPTICAL, OPTO-ELECTRONIC, INTER-CONNECTION and other emerging technologies. The focus is on research pertaining to hardware systems and their supporting software, including: experimental research involving these new systems; infrastructures, environments, tools, methodologies and services for rapid systems prototyping; design methodologies and tools; technology-driven and application-driven systems architectures; and fabrication and testing of systems. For signal-processing systems, research on algorithms and architectures relating to these new technologies that have promise for real-time computing is emphasized.

The purpose of this Summary of Awards for the MIPS Division is to provide the scientific and engineering communities with a summary of those grants awarded in Fiscal Year 1994. This report does not list multi-year awards initiated prior to Fiscal Year 1994 which received no funds in Fiscal Year 1994.

Similar areas of research are grouped together for reader convenience. The reader is cautioned, however, not to assume that these categories represent the totality of interests of each program, or the total scope of each grant. Projects may bridge several programs or deal with topics not explicitly mentioned herein. Thus, these categories have been assigned administratively and for the purpose of this report only.

In this document, grantee institutions and principal investigators are identified first. Award identification numbers, award amounts, and award durations are enumerated after the individual project titles. Within each category, the awards are listed alphabetically by state and institution.

Readers wishing further information on any particular project described in this report are advised to contact the principal investigators directly.

Bernard Chern

Division Director

Microelectronic Information

Processing Systems Division

Table of Contents

Preface	iii

Table of Contents	v

The MIPS Division	vii

MIPS Directions	ix

MIPS Staff	xi

Summary	xiii

Design, Tools and Test	1

The Program	1

Opportunities	2

Awards	3

Design Automation - Generic	3

Design Automation - Applications	8

Testing - Generic	10

Testing - Applications	12

Simulation	13

Other	15

Microelectronic Systems Architecture	17

Program Description	17

Initiatives and Opportunities	18

Awards	19

Technology Driven Architecture	19

Application Driven Architecture	25

Workshops and Conferences	30

Circuits and Signal Processing	31

The Program	31

Awards	33

Circuits	33

Analog (Mixed Analog/Digital) Signal Processing	34

One-Dimensional Digital Signal Processing	35

Multidimensional Digital Signal Processing	39

Digital Representation	45

Implementation	46

Miscellaneous	48

Experimental Systems	53

The Program	53

Initiatives and Opportunities	54

Awards	55

Graphics and Solid Modelling	55

General Purpose Computing	56

Application Specific Computing	59

Other	62

Systems Prototyping and Fabrication	63

The Program	63

Initiatives and Opportunities	64

Awards	65

Systems Prototyping and Fabrication	65

Education	71

Infrastructure	71

Index of Presidential Young Investigators	73

Index of Research Initiation Investigators	75

Index of Principal Investigators	77

Index of Institutions	81

Microelectronic Information Processing Systems

The MIPS Division

The area of computing systems, which involves the structure of computers, is central to MIPS today and will be even more so in the future. This is a core area of computer science and engineering and in the 1990's encompasses much more than just hardware. Computing systems deals with computer architecture, hardware implementation, system software (operating systems and compilers), networking, and data storage systems. The advent of gigabit networks, high performance microprocessors and parallel systems is dramatically impacting research on systems level architecture of high performance computing systems.

The emphasis in MIPS is on real systems i.e. physically realizable. Special weight is placed on design, prototyping, evaluation, and novel use of computing systems and on the tools needed to design and build them. This involves technology driven and application related research, experimental research and theoretical studies. The MIPS programs support research on: high level design (design automation and CAD tools); systems level architecture studies; experimental systems research projects which build and evaluate HARDWARE/SOFTWARE SYSTEMS; signal processing algorithms and systems; knowledge of applications; methodologies, tools and packaging technologies for rapid prototyping at the system level; and infrastructure needed to support MIPS' educational and research activities, e.g. MOSIS.

The Programs

Design, Tools and Test Program

Supports the development of fundamental knowledge about the complete design cycle for integrated circuits and systems from conception through manufacturing and operational test. Emphasis is on integrating all aspects of the cycle, and automating the design and testing processes. There are four topical research areas within the Program. These are: Theoretical Foundations, Design Automation and Tools, Manufacturing Test, and Design Simulation.

Systems Prototyping and Fabrication Program

Supports research on technologies, tools, and methodologies needed for the prototyping of experimental information processing systems and for Microelectronics Education. Issues that arise in rapid system prototyping are explored, including use of new packaging techniques such as multichip modules, and such systems issues as interfacing and standards. Support is also provided for new prototyping services. Basic research necessary to model, simulate, measure, automate and improve the microfabrication process is supported. Microelectronics Education support includes workshops, conferences, development of curriculum and courseware materials, and educational support services such as those for FPGA's and fabrication (MOSIS).

Microelectronic Systems Architecture Program

Supports basic research on computing systems and methods for their design. Computing Systems deals with computer architecture, hardware implementation, systems software, networking, and data storage. Research is encouraged on the fundamental aspects of computing systems architectures and scientific design methods that better utilize existing or emerging technologies, support systems software or address important applications whose computational requirements cannot be met by conventional architectures. The program emphasizes physically realizable systems and, when necessary, limited proof-of-concept prototyping.

Circuits and Signal Processing Program

Supports research on circuit theory and analog and digital signal processing. The emphasis is on modern signal processing, stressing the impact of VLSI, including areas such as: signal representation, filtering, novel algorithms, special-purpose hardware, and real-time computing. Circuit theory research encompasses such activities as nonlinear, discrete-time, analog and hybrid circuits, and analog/ digital conversion.

Experimental Systems Program

Supports research experiments that involve building and evaluating information processing and computing systems. These are goal-oriented projects usually undertaken by teams of designers, builders, and users. The building of a system must itself represent a major intellectual effort, and offer advances in our understanding of information systems architecture by addressing significant and timely research questions. The system prototypes being built should be suitable for exploring applications and performance issues.

Basic research in Computer Architecture and Computing Systems is supported by the National Science Foundation primarily through three programs in the CISE Directorate: the Microelectronic Systems Architecture Program and the Experimental Systems Program in the MIPS Division; and the Computer Systems Program in the CCR Division. The following pie chart shows the relative support through these three programs.

MIPS Directions

MIPS' planning takes into account advances in technology and new knowledge, and the need for closer ties of computer science and engineering to real world applications. Greater emphasis is now placed on complete systems with a broad and coherent research program in new systems architectures, automated design, and design tools to aid in research and development of high performance architectures.

The MIPS role in the High Performance Computing and Communications (HPCC) Program focuses on the support of:

Basic research (hardware & system software) on new high performance computer architectures and computing systems and on "Computer Science Challenges";

Development of tools & CAD frameworks for their design, analysis and realization;

Algorithm development and computational techniques for "grand and national challenge" problems in the areas of research supported by MIPS.

Research on high performance computing systems is responsive to such major drivers as: technology, applications and new ideas. In order to make advances in this area and to effectively exploit them, experimental systems must be built quickly and cheaply and new kinds of design tools must be developed and supplied to the research community. These prototype systems can be used to evaluate new computing architectures by subjecting them to real applications which provide believable tests of novel ideas and performance. Only by constructing prototypes, performing measurements and evaluating performance, can we realistically gauge the interaction between a new computing system, its applications, and its users. Emphasis is on long range exploratory research.

We see the need to:

Work more closely with the applications as we move toward higher performance computing to understand the computing needs of these applications. The 1992 initiative on High Performance and Application-Specific Computing Systems (ASCS) was a step in this direction.

Integrate advanced packaging technology into computing system design and explore the system level tradeoffs arising in the design of high performance computing systems.

Develop the necessary infrastructure and human resources in the computing systems area, especially the education of students able to design and build hardware/software systems.

Develop new services, tools, and methodologies for universities to utilize new fabrication and device technologies in order to do rapid system prototyping for electrical and mechanical systems essential for experimental research on these increasingly complex systems.

Support geographically distributed collaborative novel computing system design requiring expertise from many areas (e.g., architecture, software, storage technology, I/O, applications, etc.).

Develop a new generation of systems level design tools which have increased functionality, are highly automated, and accept high level specifications as inputs.

MIPS Directions (continued)

Rapid Prototyping & Design

There is a need to be able to design and build "prototype" systems quickly, and easily in both universities and industry in order to test the validity of a concept and to shorten the design-build-evaluate cycle.

Rapid prototyping allows designs created with CAD systems and expressed in an all-digital format to be "prototyped" either by simulating their performance and/or by constructing limited numbers of actual parts to ascertain performance.

We feel this is an important research area, and so MIPS was one of the major participants in a Program Announcement on Rapid Prototyping: Virtual and Physical isssued by the Foundation in April 1994.

In May 1994, the MIPS Division sponsored a Workshop to examine design and prototyping as done in VLSI and in the mechanical world. The sucess of the VLSI revolution, leads one naturally to ask the question what can we learn from that sucess, and how might it be applicable to the design of electomechanical systems? This was the central issue the workshop examined. A number of Findings and Recommendations were put forward by the workshop1. In particular, it recommended the active investigation of Solid Freeform Fabrication (SFF) and Micro electromechanical Systems (MEMS) mechanical implementation technologies where the VLSI experience will be most relevant and provides a good starting point to apply VLSI-like Systems Design Methodologies.

The MIPS Division is offering researchers an opportunity to examine more closely today's SFF design methodology and to consider extending that methodology to incorporate increased use of digital interface descriptions between design and fabrication, design rules, levels of abstraction, CAD tools, and improved languages for the description of 3-D objects in order to advance the design and prototyping of artifacts built using SFF technologies.

1 New Paradigms for Manufacturing (NSF 94-123)

Division of

Microelectronics Information Processing Systems

MIPS Staff

Bernard Chern

Division Director

bchern@nsf.gov

John R. Lehmann

Deputy Division Director

jlehmann@nsf.gov

Program	Program Director	Net Address

Design, Tools and Test	Robert B. Grafton	rgrafton@nsf.gov

Microelectronic Systems Architecture	J. Robert Jump	jjump@nsf.gov

Circuits and Signal Processing	John H. Cozzens	jcozzens@nsf.gov

Experimental Systems	Michael J. Foster	mfoster@nsf.gov

Systems Prototyping and Fabrication	John Staudhammer	jstaudha@nsf.gov

The above E-mail addresses are for the ARPANET, the CSNET and the NSFNET; for BITNET use the form:

<name>@nsf

The address and telephone number for all of the above:

National Science Foundation

Room 1155

4201 Wilson Blvd.

Arlington, Virginia 22230

(703) 306-1936

MICROELECTRONIC INFORMATION PROCESSING SYSTEMS

DIVISION

Summary

Number	Dollars

Design, Tools and Test	63	$4,475,252

Design Automation - Generic	26	$1,974,381

Design Automation - Applications	7	$464,874

Testing - Generic	10	$885,202

Testing - Applications	7	$490,030

Simulation	9	$407,155

Other	4	$253,610

Microelectronic Systems Architecture	48	$3,986,410

Technology Driven Architecture	31	$2,622,644

Application Driven Architecture	16	$1,357,766

Workshops and Conferences	1	$6,000

Circuits and Signal Processing	68	$4,472,125

Circuits	5	$315,686

Analog (Mixed Analog/Digital) Signal Processing	5	$313,774

One-Dimensional Digital Signal Processing	15	$1,196,304

Multidimensional Digital Signal Processing	20	$1,529,204

Digital Representation	5	$301,967

Implementation	8	$406,872

Miscellaneous	10	$408,318

Experimental Systems	30	$7,753,309

Graphics and Solid Modelling	5	$913,775

General Purpose Computing	12	$3,265,545

Application Specific Computing	12	$3,568,989

Other	1	$5,000

Systems Prototyping and Fabrication	30	$2,838,218

Systems Prototyping and Fabrication	27	$2,457,083

Education	1	$1,918

Infrastructure	2	$379,217

This summary data includes funds designated for special Foundation initiatives, and equipment matching funds from the Office of Cross-Disciplinary Activities. It does not include program funds use to support Intergovernmental Personnel Act employees, their travel costs, or costs of travel of review panelists and site visitors.

Design, Tools and Test

Dr. Robert B. Grafton, Program Director

(703) 306-1936 rgrafton@note.nsf.gov

The Program

The Design, Tools and Test Program supports basic research in Electronic Design Automation (EDA). Findings of the research contribute to fundamental knowledge about the complete EDA design cycle for integrated circuits (ICs) and systems, from conception through manufacturing test.

Emphasis is on finding methodologies needed to design, verify, simulate, and test the more complex and heterogeneous systems of the future. Discovering these new methodologies, with their appropriate abstractions to simplify and expedite the process, will provide the basis for the development of the next generation of EDA tools. Additional focus is on system level design issues and the myriad tradeoffs that must be made in developing a balanced, manufacturable, and profitable system design.

Research in EDA tools needs to address derivation of appropriate models for the design domains, technologies, and physical effects of interest and concern today. This research, while fundamental in nature, must have roots in the real world of industry. Thus, researchers often have ties to industry so as to keep abreast of changing industry concerns.

Topics in EDA tools research can be positioned in a three-dimensional space where the three axes represent the traditional EDA area, the application domain, and the enabling implementation technology. This framework provides a way to assess the potential impact and difficulty of the problems addressed.

DRIVING FORCES

The technology of VLSI/ULSI circuits changes rapidly. It is now possible to put up to 3 million transistors on a chip and operate at speeds up to 200MHz. The demand for computing systems of greater complexity and higher performance is high. Interfaces, applications, and advanced computing systems require ever more sophisticated, high quality, and trusted VLSI electronics. Thus, there is substantial need for a new generation of EDA tools for IC and system design and test.

Manufacturing costs go up at an exponential rate. Designers now need tools that factor in manufacturing parameters, such as yield and defect types, into the design equation. Because circuit operation is now sensitive to electro-magnetic effects, manufacturing tolerances must be accounted for in design.

Competitiveness requires that the product design cycle must be reduced, and new mechanisms for rapid verification and prototyping of designs must be developed. This, in turn, requires sophisticated EDA tools which enable design engineers to find viable solutions to design problems in a highly complex design space. Additionally, designers must account for factors, such as cost and operating environment.

The changing technology, manufacturing cost and competitiveness dictate the major research problems of finding methodologies to: Rapidly design a complex IC system; Verify the resulting design; and Test the manufactured product.

GENERAL TOPICS

High operating and switching speeds make electrical effects on the chip an important factor, thus causing a new dimension in EDA tool research. It is necessary to use an integration of analytical and experimental methodologies to achieve suitable designs. Research is supported on mixed signal and digital technologies within the broad areas of theory, design automation, tools, manufacturing test, and simulation.

Theoretical research explores computational models and algorithms for design and testing methods in advanced technologies and in mixed signal and asynchronous systems.

Design automation investigates algorithms, tools and analysis methods for design at several levels, including physical and high level synthesis. Goals are performance, testability, synthesis, and verifiability of designs. Integration of software with hardware aspects are part of system synthesis.

Manufacturing test research includes work on evaluation of new manufacturing test methods; algorithms for test pattern generation for test of large IC designs; models for detection of realistic failure modes; and integrating testing with other design activities.

Numerical and symbolic simulation are necessary parts of the design evaluation and analysis. Of special interest is the application of computer science, numerical analysis and electrical engineering knowledge to computation of electrical effects now present in designs with small feature size, high speed, and mixed signal designs.

Opportunities

Some special opportunities available through the DTT Program include:

RESEARCH EXPERIENCES FOR UNDERGRADUATES (REU)

This is an opportunity to add one or two undergraduates to a grant to take part in the research activity. Since the goal is to interest promising undergraduates in a scientific research career, their participation should be meaningful to the student as well as helping the research progress.

Grant supplements are generally for one or two students, with preference given to members of groups underrepresented in engineering.

SMALL GRANTS FOR EXPLORATORY RESEARCH (SGER)

This provides for a one year grant to explore a research topic that, for some reason, may be inappropriate for a normal grant submission.

SOFTWARE CAPITALIZATION GRANTS

Software capitalization grants or supplements are to facilitate development of well-documented, useable prototypes of EDA research-developed tools, and their distribution to designers and other researchers.

Awards

Design Automation - Generic

Stanford University; Giovanni De Micheli; PYI: Computer-Aided Design (CAD) Algorithms; (MIP-8858806 A006); $8,000; 12 months.

This research is on a hardware synthesis system that can transform automatically a procedural description of a hardware design into a geometric description of a VLSI chip suitable for fabrication. Results on logic synthesis are being extended to structural synthesis. The issue being addressed here is architectural partitioning. Being developed are synthesis techniques and circuit optimization methods at electrical and geometric levels of representation. Algorithms to synthesize circuits with minimal delay, area and power are being developed.

University of California - Berkeley; Ernest S Kuh; Design Methodologies for High-Density, High-Performance, Wire-Dominated Chips and Multichip Modules; (MIP-9117328 A002, A003, A004); $220,000; 12 months.

This a joint project with the UC at Berkeley (S. Kuh), UC at Santa Barbara (M. Marek-Sadowska) and UC at San Diego (C.-K. Cheng and T. C. Hu). The goal of this research is to create methodology for designing high-performance, large, dense circuits which have a large portion of the physical layout occupied by the wires. Algorithms which can handle very large problem instances are being developed. These include algorithms for extended floor-planning; such as, performance-driven partitioning, timing simulation, transmission lines, clock skew optimization, routing and compaction. Also being developed are algorithms to solve problems which span the boundaries of classical VLSI design problems

University of California - Los Angeles; Jason Cong; NYI: Synthesis and Mapping in Lookup-Table Based FPGA Designs; (MIP-9357582 A001); $100,000; 12 months.

Synthesis and Mapping are necessary steps in designing Field Programmable Gate Arrays (FPGAs). This research is a systematic study of these problems in look-up table based FPGA designs. Questions being investigated include: node duplication, depth relaxation, logic resynthesis during mapping, and system-level partitioning in multiple chip FPGA designs. Algorithms being developed include: near optimal synthesis, and tradeoffs between design objectives, such as area, delay and routability. Combinatorial and Boolean optimization techniques are being investigated.

University of California - Los Angeles; Andrew B Kahng; NYI: Synthesis of High-Speed, High-Complexity VLSI Systems; (MIP-9257982 A002); $100,000; 12 months.

The unifying theme of this research is that underlying geometries, embedding dimensions and topological representations of CAD designs, together afford a perspective for effective algorithm design. This notion is applied to:

1.	Performance-driven synthesis: including clustering for problem decomposition, fast hierarchical placement, and estimation of intrinsic resource requirements via topological criteria.

2.	Assessment of design problem complexity based on the interaction between topology of neighborhood structures and scaling geometry in the associated cost surfaces. Time-bounded stochastic optimizations, and a non-monotone class of annealing methods are also being investigated.

3.	Capturing the underlying physics of high-speed devices and interconnects while maintaining algorithmically tractable formulations. Examples are a unified routing tree optimization and separation of the interconnect topology from subsequent geometric embedding.

University of California - San Diego; Chung-Kuan Cheng; Research on Circuit Partitioning; (MIP-9315794, A001); $23,685; 12 months; (Joint support with the Microelectronic Systems Architecture Program - Total Grant $47,371).

This is an investigation into hierarchical partitioning methods. The principal investigator is extending partitioning research by adopting different circuit models including petri nets, data flows, and state machines, by improving the efficiency and effectiveness of the methods, and by deriving theoretical results on variations of partitioning formulations. He plans to apply partitioning methods to netlist mappings for various hardware emulation machines and to find potential applications of these methods to VLSI design problems

University of Southern California; Massoud Pedram; NYI: Low Power VLSI Design; (MIP-9457392); $12,500; 12 months; (Joint support with the Microelectronic Systems Architecture Program - Total Grant $25,000).

This research investigates modeling and estimation of power consumption as well as techniques for minimizing power at levels of design abstraction (layout, logic, register- transfer and behavioral levels). Principles and methods to guide the design of power efficient electronic systems are being explored; and the impact of availability of low-power design techniques on chip, module, and system level designs is being assessed. Topics being investigated include: spatio-temporal power estimation; state assignment for low power; power dissipation in boolean networks; common subexpression extraction; and FPGA synthesis for low power.

University of Colorado; Gary Hachtel, Fabio Somenzi, Michael Lightner; Synthesis and Verification of Combinational, Sequential and Behavioral Logic; (MIP-9115432 A004, A005, A006); $311,149; (Joint support with the Advanced Research Projects Agency - Total Grant $683,065).

This a joint project with Colorado, (Hachtel, Lightner and Somenzi), Berkeley (Brayton, Newton, Sangiovanni), and Stanford (De Micheli). The research is a systematic approach to synthesis and verification of logic at all levels, combinational, sequential and behavioral, from HDL specifications. Objectives include: performance oriented synthesis, maximization of testability, and

partitioning. Both chip and multi-chip module design problems are being explored.

The model is of sequential circuits based on a network of interacting, possibly non-deterministic, finite state machines (FSMs), in which interconnections can have unbounded delay attributes. In this model, the component machines may have symbolic or encoded I/O and can degenerate to just combinational logic or just latches. This enables uniform treatment of disparate objects such as RAMs, controllers, ALUs, pipeline registers, etc. Research topics are:

1.	algorithms and theory for logic manipulation

2.	design, synthesis, and formal approaches

3.	design of embedded controllers

4.	hardware-software co-design, and

5.	applications to areas such as machine learning, theorem proving and combinatorics.

A set of coordinated synthesis tools is being produced. The tools operate at both high level or low level depending on whether they operate above or below the FSM model.

Yale University; Debashis Bhattacharya; Efficient Parallel Techniques for Hierarchical Fault Simulation and Test Generation; (MIP-9101966 A003); $51,690; 12 months.

Issues in two-dimensional circuit partitioning leading to two-dimensional, loosely-coupled, pipeline-like information flow in a distributed memory parallel computer, and partitioning of circuits employing partial scan design methodologies are being explored. Formal methods to analyze the computational complexity of the resultant parallel algorithms are being formulated. Implementations are being tested using industrial size benchmark circuits. A BDD-based approach is being taken for test generation. This has advantages in generating tests for large combinational circuits and sequential circuits. Algorithms are being developed for machines with shared memory, and for distributed-memory MIMD machines. Also being investigated are the generalization of BDD's to multi-valued decision diagrams, and the use of BDD-based test generation in a hierarchical design framework.

University of Florida; Sartaj K Sahni; High Performance Solutions to VLSI CAD Problems; (MIP-9103379 A002, A003); $100,000; 12 months.

Three areas of computationaly efficient algorithms for design of IC's are under investigation.

1.	Algorithms for display of VLSI artwork: Sequential and parallel algorithms to quickly display collections of polygons and lines on popular display devices are being investigated.

2.	When a VLSI design can be modeled by graphs, it is often required to split or delete a set of vertices so that the resulting graph will satisfy design criteria. Classes of graphs for which the problems are polynomially solvable and methods for minimizing the number of components in the resulting digraph are being determined.

3.	Module orientation and rotation problems for a variety of design styles are being examined to determine which are NP-hard and polynomially solvable. Approximation algorithms, heuristics, and polynomial algorithms are being developed for the NP-hard problems.

Northwestern University; Majid Sarrafzadeh; Algorithm Design for VLSI Layout; (MIP-9207267 A002); $30,694; 12 months.

Research is in four areas of geometric algorithms for design tools. Topics are:

1.	floor planning by graph dualization

2.	placement of modules

3.	rectilinear Steiner tree problems, and

4.	point dominance problems.

In floor-planning, topological aspects of the problem are considered and geometric issues such as sizing are explored. A clustering technique for module placement, that exploits regularities in circuit structures, is being investigated. In this way natural clusters that reflect the hierarchical perspective of circuit connections can be built automatically. Problems in approximate designs for global and single layer routing using Steiner trees are being investigated. Point dominance, from computational geometry, is being applied to circuit layout problems.

University of Illinois; Prithviraj Banerjee; Parallel Algorithms for Synthesis and Test; (MIP-9320854); $42,000; 12 months.

This research is on developing portable circuit design and test algorithms that run on parallel computers. These include algorithms for synthesis of combinational circuits; and test generation and fault simulation of combinational and sequential circuits. Algorithms are being written using an environment that makes it possible to port CAD applications across a wide range of MIMD machines. In addition they are designed to allow a maximum overlap of computation and communication.

Iowa State University; Liang-Fang Chao; RIA: Optimizing Synthesis for Periodic Real-Time Applications; (MIP-9410080); $100,000; 36 months.

This research is on finding pipeline scheduling for the behavioral description of an iterative or recursive algorithm or loops. This extends the scheduling algorithm to more realistic resource models and to graphs with conditionals. The goal is to expose the parallelism in an iterative or recursive algorithm to provide information for optimization. Focus is on the innermost loops or iterations, which are the most time-critical for applications. The approach is to study the structure of cyclic data-flow graphs with edge delays in order to optimize behavioral transformation, scheduling and partitioning.

Massachusetts Institute of Technology; Srinivas Devadas; NYI: Formal Methods for Hardware and Software Verification; (MIP-9258376 A002, A003); $100,000; 12 months.

Research is on logic and behavioral verification of VLSI circuit designs, and application of hardware verification techniques to software verification. Topics include:

1.	Use of Free Binary Decision Diagrams (FBDDs) to find Boolean representations of circuits and manipulation methods for them. Algorithms for combinational and sequential, synthesis, test and verification applications are being developed.

2.	Automatic methods to verify pipelined implementations against unpipelined specifications are being explored. The methods ensure that each data transfer that takes place upon the execution of any instruction in the unpipelined circuit also occurs in the pipelined circuit. A symbolic simulation method is being developed that will verify pipelined micro-processors against instruction set specifications.

3.	FBDD representations are being used to find symbolic traversal methods which allow for automatic software verification. These are also being used to debug software programs by verifying that the program satisfies correctness properties.

Princeton University; Sharad Malik; NYI: Design Automation for Embedded Systems; (MIP-9457396); $25,000; 12 months.

This research is on designing the programmable components of integrated circuits. Gates, as basic units of computation on silicon, are well understood. This research is focused on understanding embedded instructions as basic units of computation on silicon. Initial work is on finding methodologies for synthesizing embedded software. Problems being examined are: worst case timing analysis; power modeling and analysis; and high- quality retargetable code synthesis. Approaches include: developing timing models capable of handling features such as caches and pipelines, and determining worst-case paths; analyzing system power consumption; and formal architectural specification of specialized architectures, as well as code-generation algorithms that can take advantage of special architectures.

Princeton University; Wayne H Wolf; Control Minimization and Performance Optimization for High-Level Synthesis; (MIP-9121901 A003, A004); $66,531; 12 months.

Models for two problems in high-level control synthesis are being explored: Analysis of delays in mixed data- control systems before scheduling; and scheduling in control systems. The approach is to use a finite state machine whose inputs and outputs are partially ordered in time. The approach to solving the state minimization problem is to search over possible schedules of input and output events to choose an implementation of a minimum number of states. Algorithms to minimize the number of states around cycles in a behavior state transition graph are being developed.

Carnegie-Mellon University; Edmund M Clarke; Automatic Verification of Finite-State Concurrent Systems in Hardware and Software; (CCR-9217549 A001); $37,000; 12 months; (Joint support with the Software Engineering Program - Total Grant $148,300).

This research is on temporal logic model checking. Logical errors in sequential circuit designs and communication protocols have always been an important problem. The most widely used method for verifying such systems is based on extensive simulation and can easily miss significant errors when the number of possible states is very large. Specifications are expressed in a propositional temporal logic, and sequential circuits and communication protocols are modeled as state transition systems. An efficient search procedure is used to determine automatically if the specifications are satisfied by the transition system.

Carnegie-Mellon University; Rob A Rutenbar, Jonathan Cagan; Extending VLSI Layout Strategies to Geometric Synthesis of 3-Dimensional Mechanical Systems; (MIP-9410899); $25,000; 12 months; (Joint support with the Engineering Design Program - Total Grant $50,000).

This research is on exploring algorithms for 3-D mechanical component arrangement that derive from successful strategies used for 2-D VLSI problems. The approach is to develop the critical connections and extensions between the core geometric synthesis algorithms in 2-D VLSI layout and 3-D solid modeling that will yield efficient mechanical shape synthesis tools, which support rapid exploration of novel 3-D component arrangements. Basic stochastic optimization techniques, shape representations, and optimization-control techniques are being used to:

1.	Arrange 3-D mechanical components (extending VLSI placement strategies);

2.	Route tubes, cables and wires in three dimensions (extending VLSI routing strategies);

3.	Find algorithms to meet criteria such as; vibration, thermal, space constraints, component balance, manufacturing, maintenance, accessibility, and human factors (extending linear analysis methods from circuit design);

4.	Support rapid redesign of families of products.

Pennsylvania State University; Barry Pangrle; Control and Layout Issues in Performance-Driven, High- Level Synthesis; (MIP-9118440 A002); $61,813; 12 months.

This research is focused on control and datapath synthesis, and how the tradeoffs between the two affect layout and performance of VLSI designs. First is finding control/datapath tradeoffs based on high-level transformations performed on the control/data flow graph. Second is incorporation of layout considerations into the generation of the datapath connectivity. A new data path generation scheme that aims at producing datapaths with better performance and layout characteristics is being developed. This research is being performed within the basic framework of the Keystone System which automatically synthesizes and simulates all datapath components, control logic, and routing.

University of Pittsburgh; Steven P Levitan; Temporal Specification Verification; (MIP-9102721 A002); $70,809; 12 months.

This research is on verifying timing specifications for interconnection of modules in both synchronous and asynchronous digital systems. The notion of temporal behavior is being abstracted from the notion of functional behavior by focusing on the control protocols of the modules and ignoring the data values computed by the modules. In this model, the interface protocols of each module are given along with the connectivity between modules. A static graph is built that describes the temporal relationships among all the external signals of all the comparison between the possible behaviors of the system, represented by the graph, and the legal behaviors as represented by a set of constraints. The key constraint is that the temporal behavior of one module cannot violate the temporal constraints of another module within the system. The algorithms support multiple system states, state transitions, and checking of conditionals and loops within the protocols. This searching is tractable because functional behavior and data values generated by modules are not considered.

Southwest Texas State University; Tod T Amon; RIA: Verifying the Temporal Behavior of Concurrent Systems; (MIP-9410279); $89,957; 36 months.

This research examines the question of how synchronization affects the temporal behavior of concurrent systems. The problem addressed is that of determining tight bounds on separation times between system events. The concurrent system model used is a directed graph whose vertices represent events (synchronizations) and whose edges are annotated with delay information (bounds on computation times). The approach is to use algebraic techniques for manipulating an infinitely unfolded graph to implicitly examine the entire set of temporal behaviors. The research is extending the types of temporal analyses that can be preformed, as well as extending the classes of concurrent systems whose timing behavior can be efficiently verified. Applications in the area of asynchronous circuits are also being investigated.

Southern Methodist University; Sukumaran Nair; RIA: Spectral-Based Numerical Methods for Combinational Logic Synthesis; (MIP-9410822); $90,000; 36 months.

This research is on numerical methods for digital logic synthesis based on spectral information of the logic description. The approach is to use the BDD description of the circuits to develop efficient methods for computing the spectral coefficients. Because of the numerical nature of the algorithms, design optimizations can be included in the synthesis process, rather than later. Theoretical results are being derived and used to implement a new class of synthesis algorithms that are suitable for incorporation into existing design environments. The algorithms are being tested on industry benchmarks.

Texas A & M University; Dhiraj K Pradhan, Duncan M H Walker, Wolfgang Kunz; Novel Methods in Computer-Aided Circuit Design and Testing Using Recursive Learning; (MIP-9406946); $69,000; 12 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $106,030).

This research investigates modeling and estimation of power consumption, as well as techniques for minimizing power at the levels of design abstraction (layout, logic, register-transfer and behavioral). Principles and methods to guide the design of power efficient electronic systems are being explored; and the impact of availability of low-power design techniques on chip, module, and system level designs is being assessed. Topics being investigated include: spatio-temporal power estimation; state assignment for low power; power dissipation in boolean networks; common subexpression extraction; and FPGA synthesis for low power.

University of Utah; Ganesh Gopalakrishnan; A Multi-Paradigm Verification System Tailored for the Design Refinement Cycle; (MIP-9321836); $50,651; 24 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $104,861).

The design of a VLSI system involves multiple design representations; and the design must go through several iterations aimed at meeting many performance and cost constraints. Verification that the design meets constraints is necessary. This research is developing rigorous verification methods that span multiple design representations, accommodate design revisions, and provide incisive partial verification methods (e. g. verification focussed on the "corners" of the behavioral space) that fit within designers' time budgets. These ideas are being validated by verifying real asynchronous designs.

University of Virginia; James P Cohoon, Jeffrey S Salowe; Next Generation Research in Physical Design; (MIP-9107717 A003); $101,402; 12 months.

This research takes an integrated look across the physical design activities of partitioning, floorplanning and routing. These algorithms are designed to route on any number of layers, work on a rectilinear, gridless surface with obstacles, account for technology constraints, and permit horizontal, vertical and 45 degree wiring on a layer. In partitioning, a powerful geometric partitioning technique called SHARP is being used to develop algorithms (including parallel ones) which bridge between various physical design activities, such as floor-planning, Steiner routing, and identification of critical nets. Algorithms are being integrated into a tool for overall design, and a visualization tool is being developed.

University of Virginia; Gabriel Robins; NYI: New Directions in High-Performance VLSI Layout; (MIP-9457412); $25,000; 12 months.

Realistic formulations of performance-driven layout are the focus of this research. Accurate models of circuit delay are sought. These models include parameters, such as capacitance, resistance, inductance, etc. Delay-optimal trees to define an envelope of achievable routing performance are being studied. Methods for constructing near-optimal layouts are being investigated. Additionally, the routing problem is being recast as one of constructing low-delay routing graphs where cycles are allowed. This can have the advantage of designs being tolerant to certain types of open faults due to manufacturing defects or electro-migration.

University of Washington; Steven M Burns; NYI: A Design Language for Asynchronous Circuit Synthesis; (MIP-9257987 A002); $62,500; 12 months.

This research is on developing a unifying design language and framework in which asynchronous circuit designs can be completely specified, and in which decisions made during synthesis of the implementation can be recorded. The language is an extension of Hoare's CSP with a means to specify structural hierarchy with a refinement hierarchy superimposed upon it. There are three interconnected tasks: language definition; developing tools such as a parser, flattener, view generator, handshaking expansions, and production rule sets; and application of the tools to a large design or a real time system. An algorithm for determining the maximum time separation of event occurrences in a concurrent system is being developed.

Design Automation - Applications

University of California - Santa Barbara; Forrest Brewer; Production Language Based High-Level Synthesis; (MIP-9320752); $62,321; 12 months.

The goal of this research is to create a new class of synthesis tools for design of controller-data path machines under constraints of pre-defined interfaces. The results will be integrated with commercial EDA design tools. A design output format, which can be simulated and allows automated re-design of selected portions of the design, is being developed. In a second task, approximate sequential reachability analysis is being used to design and implement algorithms for optimizing and partitioning controller designs. The third task is to explore scheduling algorithms for both the control and data-path portions of the design. Finally, an optimizing compiler is being built. It contains algorithms which solve encoding issues for high performance designs, and performs re-scheduling of the data-path operations to minimize required resources while maintaining design behavior.

University of California - Santa Cruz; Wayne W Dai; PYI: Computer-Aided Design of VLSI Circuits--Constrained Net Embedding for Multichip Modules; (MIP-9058100 A004, A005); $41,250; 12 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $72,500).

Interconnection topology and metrics needed for laying out high-speed interconnections in multi-chip modules are being pursued. The first topic is optimal design of transmission lines for multi-chip modules (MCM). These are self-damped lossy transmission lines in a tree network, which propagates high-speed signals. Algorithms for designing these transmission lines are being developed. Attention is paid to distortion-free signal propagation, cross-talk, switching noise, and thermal resistance. The second topic is routing of clock signals for optimum system performance. An algorithm is being developed to construct a clock tree which can be embedded on a single layer of metal. Path length from the clock source to each clock terminal is exactly the same. The third topic is a multiple bus network for parallel processing which matches the MCM requirements of higher I/O pin count and inter- chip routing density. An algorithm with good fault tolerant properties that leads to uniform bus load and processor fanout is being developed.

Michigan State University; Chin-Long Wey; Efficient Testing Paradigms and Diagnosable Design Methodologies for Analog Integrated Circuits and Systems; (MIP-9321255); $47,947; 24 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $93,114).

This research is on test paradigms for high-frequency, linear and nonlinear mixed signal circuits and systems. Issues in BIST (Built-In Self-Test) and design for testability are being addressed. Fault models for hard faults (open or short circuits) and for soft faults (deviations from nominal component values) are being developed. For BIST design, a high speed, low power, current mode copier is employed as the sample/hold circuit to achieve 10 ns/sample at 0.1% accuracy under 3.3V power supply. Both CMOS and BiCMOS technology are being used. Design for testability is on properly selecting component values and topological structure to increase testability and diagnosability. The problem of determining component values is formulated as an optimization problem which includes testability strategy as a parameter. The new methods are being tested on realistic circuits.

University of Michigan; Karem A. Sakallah, Trevor N. Mudge, Edward S. Davidson; Timing Issues in the Design of Digital Systems; (MIP-9404632); $233,356; 24 months; (Joint support with the Microelectronic Systems Architecture Program - Total Grant $350,034).

This research is on a timing verification and optimization framework for designing an entire digital system. The research builds on a widely used model for synchronous timing analysis and an efficient method for estimating gate and wire delays. The model is being extended to include relevant functional information in order to enhance accuracy. Components of the framework are: design decomposition to isolate critical elements; a path delay calculator; algorithms for finding synchronizer components; clock analysis algorithms; a symbolic sequential timing verification component; a hybrid timing-logic simulator; and design optimizers.

Columbia University; Steven M. Nowick; RIA: The Design of High-Performance Asynchronous Controllers; (MIP-9308810 A001); $5,000.

This research is on algorithms and tools for the design of asynchronous circuits. Previous work in the area has produced a "locally-clocked" asynchronous design style, which produces high performance implementations that are hazard-free at the gate level. Three extensions to this design style are being investigated. The first is to explore an alternative unclocked asynchronous controller design method, which only requires a single feedback cycle to implement a state change. This work includes implementation of generalized burst mode specifications to the unclocked state machines. Second is the development of extensions to hazard-free logic minimization. The extensions include: a heuristic two-level minimization algorithm; an exact product-of-sums solution; time-optimized multi-level logic synthesis; testing oriented two-level minimization; and hazard-decreasing, multi-level transforms. Third is an exploration of systematic ways to test asynchronous designs.

University of North Carolina - Charlotte; Dian Zhou; NYI: Performance-Driven VLSI Designs; (MIP-9457402); $12,500; 12 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $25,000).

Three research issues in high-performance VLSI system design are being addressed:

1.	how to relate the system performance function, characterized by electrical parameters, to the geometrical parameters of the VLSI physical design;

2.	how to model performance driven VLSI physical designs based on given technology and computational capability; and

3.	how to characterize the fundamental computational aspects of modeled problems and develop effective algorithms for solving them.

A distributed RLC circuit model for interconnects is being designed. It considers: non-monotone circuit response, coupling effect among the signal lines, and low energy consumption. Efficient computation methods that solve time-varying Maxwell equations using the adaptive wavelet collocation method (AWCM) are being devised. The algorithms and methods are being included in a CAD system.

Testing - Generic

Stanford University; Edward J McCluskey; Research on Reliable Computers; (MIP-9107760 A001); $149,991; 12 months.

This research is on techniques for reducing the occurrence of run-time errors in circuits and systems. Emphasis is on preventing the introduction of faults into the system through verification and synthesis techniques, and on improving the detection and diagnosis of faults causing run-time errors so that the faults can be removed from the system. Topics being pursued are:

1.	Developing synthesis methods that automatically synthesize a synchronous, register-transfer level (RTL) hardware specification from a behavioral VHDL language specification;

2.	Determining what coverage of multiple stuck-at faults or bridging faults can be expected by a test for delay faults in an arbitrary circuits;

3.	Investigating methods for utilizing output waveform characteristics in delay testing; and

4.	Finding fault models for intermittent failures, and methods to detect their presence.

University of California - Santa Barbara; Kwang-Ting Cheng; RIA: Strategies and Methods for High Quality Delay Testing; (MIP-9409174); $100,000; 36 months.

This research is on strategies and methods to generate high quality tests for all faults that might affect the performance of a circuit. Three topics are being investigated. First, new testability conditions are being formulated for faults that are not testable under all existing conditions, and test generation methods for such faults are being explored. Second, methods for automatic generation of validatable, non-robust tests of the highest quality are being developed. Third, methods for generating non-robust tests with high robustness are being found.

University of Iowa; Irith Pomeranz; NYI: A New Search Strategy for Design Automation; (MIP-9357581 A001); $100,000; 12 months.

A method for solving CAD design and test problems, which is especially suitable for solving large problems because it does not deteriorate as circuit size is increased, is being explored. The approach is to scale down the problem while retaining all of its details; find high quality solutions for a sequence of small circuits; develop rules for solving these problems; and then scale up these miniature solutions into a solution for the large problem. Since the miniature solutions are optimal, the full-sized solutions are expected to have very high quality. Research problems being explored are:

1.	test generation for various fault models on designs given at the gate and higher levels;

2.	built-in-self-test methods; and

3.	testing of synchronous sequential circuits.

University of Massachusetts; Premachandran Menon; Delay-Verifiable Combinational and Non-Scan Sequential Circuits; (MIP-9320886); $59,998; 24 months.

This research explores a new delay test set, called a delay-verification test set, which detects the presence of any path delay faults that can affect the timing of the circuit. The approach is to find necessary and sufficient conditions for delay verifiability; i.e. the existence of a complete delay-verification test set. Algorithms for the synthesis of area-efficient, delay-verifiable circuits and the generation of delay verification test sets are being developed. A second topic is a design and test methodology for sequential circuits without scan latches in functional paths. A method, based on clock suppression, is being used to generate transitions on state variables for delay testing. State assignment techniques to improve delay-fault testability without scan and clock suppression are being investigated.

University of Michigan; John P Hayes; Testing Complex Systems with Reusable Tests; (MIP-9200526 A002, A003); $102,569; 12 months.

This research deals with obtaining a fundamental understanding of how to use hierarchy effectively in testing (as it is used in design). The three integrated components of the research are:

1.	How to design and control propagation of precomputed test stimuli to each module of the circuit from the circuit inputs and propagation of responses from the module to the circuit outputs;

2.	Development of test-preserving transformations of circuits which allow a circuit design to be changed during synthesis while preserving the fault coverage powers of a known or transformed test set; and

3.	Finding methods for designing built-in-self-testing circuits to provide localized input stimuli generation and response analysis for modules.

Rutgers University; Michael L Bushnell; PYI: Computed-Aided Design of ULSI Circuits; (MIP-9058536 A004); $62,500; 12 months.

The research is on automatic test pattern generation (ATPG). Problems being considered include: false timing path detection algorithms; reduction in memory requirements for ATPG for very large state machines; neural net-based, switch-level algorithms; parallel algorithms; robust delay fault built-in self- testing circuits; statistical delay fault simulation. Software for algorithms is being developed. Additionally, a distributed data base retrieval algorithm that operates on a network of work stations is being explored.

North Carolina State University; Clay Gloster; MRIA: Complete Testability with Partial Scan; (MIP-9410793); $42,964; 36 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $85,928).

This research is on partial scan for system test. The main problem addressed is: given a sequential circuit, find the minimal set of flip-flops that are to be included in the scan chain while maintaining complete or 100% fault coverage. The approach is to define a metric, "profit", for a particular scan chain configuration. This metric is equal to the probability that the required states for testing the target faults will be obtained using deterministic test generation techniques. Various optimization techniques are being used to find the scan chain configuration that has large "profit." Algorithms for using this technique are being developed into a test tool.

University of Texas; Jacob A Abraham; Fault Modeling and Test Generation for Mixed-Signal Integrated Circuits; (MIP-9222481 A002); $94,000; 12 months.

This research is on fault modeling and test generation for mixed signal integrated circuits. Defect and yield statistics are being used to derive comprehensive fault models for analog circuits. These include functional fault models useable in design for test and test generation. New test generation algorithms are being derived for analog circuits, and techniques are being developed to interface the analog tests with the digital circuitry in a mixed signal circuit. The fundamental theories are being validated experimentally with designs and data from industry. (Joint research with Mani Soma, University of Washington.)

Virginia Polytechnic Institute and State University; James R. Armstrong, Walling R. Cyre; Rapid Development and Testing of Behavioral Models; (MIP-9120620 A002, A003); $108,180; 12 months.

This research is on methods to create behavior models that accurately represent the functionality and timing of complex devices. The work is on developing a "Modeler's Assistant", expressed in VHDL, for structured development of behavioral models. Specific problems being solved are: developing a process primitive set for the Modeler's Assistant, developing and evaluating performance measures for structured behavioral model development, developing a natural language interface for the Modeler's Assistant, and building into the Modeler's Assistant the capability to automatically generate tests for any behavioral model which has been constructed by the system.

University of Wisconsin; Charles R Kime; Built-In Self-Test for Random Pattern Resistant Faults; (MIP-9319742); $65,000; 12 months.

This research is on techniques for testing circuits having random pattern resistant faults. The focus is on methods for synthesizing random pattern testable circuits. The synthesis algorithms being developed include algorithms for design of random pattern testable two level and multi-level combinational logic; extensions to some classes of sequential logic are also being investigated. Two methods being pursued are weighted cellular automaton, and fixed bit biased pseudo-random pattern generator.

Testing - Applications

University of California - Santa Cruz; Frankie J Ferguson; PYI: Hierarchal Test Pattern Generation for Manufacturing Defects; (MIP-9158491 A003, A004); $66,100; 12 months.

The focus is on developing cost-effective testing methodologies that detect more defective ICs than current methods. There are two approaches to manufacturing test. The use of high-level fault models reduces test generation costs, but furnish lower quality tests. The use of low-level fault models increases the quality of circuits that have passed the tests, but causes testing costs to mushroom. This research integrates these two techniques so that tests can be generated that detect virtually all plausible manufacturing defects without excessive automatic test pattern generation costs. The approach is to develop a software tool, "Carafe" (circuit and realistic fault detector), which determines the most likely faults to occur in a CMOS circuit. It exploits the hierarchical nature of VLSI circuit designs, making fault extraction faster and more memory efficient. Also it supports multi-level metal CMOS technologies.

University of California - Santa Cruz; Tracy Larrabee; PYI: Sequential and Combinational Test Pattern Generation; for Realistic Faults Using Boolean Satisfiability; (MIP-9158490 A004, A005); $80,959; 12 months.

This research is based on an automatic test pattern generation system (called Nemesis) that generates a test pattern for a given fault by first constructing a formula representing all possible tests for the fault, and then applying a Boolean satisfiability algorithm to the resulting formula. This method separates the formula extraction from the formula satisfaction thus providing flexibility and generality. A testing system, based on Nemesis, that will generate tests detecting all realistic manufacturing defects in both combinational and sequential ICs is being developed.

Southern Illinois University; Spyros Tragoudas; RIA: Built-In Test Pattern Generation Methods; (MIP-9409905); $89,971; 36 months.

This research is on test pattern generators for combinational circuits. Various schemes for LSFR/SR pseudo-random test pattern generators are being examined. The focus is on finding high quality ATPG algorithms that require minimal hardware overhead. Several families of not-necessarily primitive, characteristic polynomials are being investigated with the objective of guaranteeing that test patterns will be applied randomly to all outputs. In addition, various partial scan schemes that follow the structural approach are being studied.

Princeton University; Niraj K Jha; High-Level Synthesis for Hierarchical Testability; (MIP-9319269); $77,000; 12 months.

This research is concerned with finding efficient hierarchical testability techniques for controller-data path systems. The approach is to start with module level test sets, derived for any suitable fault model, and use high level synthesis to ensure that these test sets can be combined into a system level test set which can provide complete test coverage of all the embedded modules. The aim is to invent algorithms that reduce test generation and application times, yet obtain complete, or nearly complete, system level test coverage with little or no area and delay overhead. The testability techniques are being embedded into algorithms for scheduling and allocation. Also being explored are methods for performing synthesis with both low power and testability as design criteria.

University of North Carolina - Charlotte; Rafic Z Makki; New Approaches to the Testing of Digital Integrated Circuits; (MIP-9406931); $75,000; 24 months.

This research explores test methods for manufacturing test of CMOS integrated circuit chips based on monitoring of the dynamic portion of the power supply current (iDDT). Since an iDDT pulse is created any time a CMOS circuit switches states, the monitoring of iDDT provides observability into the switching behavior of the circuit. This, combined with standard test methods, can provide improved testability of manufactured IC chips. New accurate fault models based on actual physical tests as opposed to simulation alone, and new design methods for enhancing iDDT-testability are being investigated. The methods are being incorporated into a design-for-testability tool, and are being evaluated on real designs.

University of Rhode Island; Jien-Chung Lo; RIA: Efficient Designs of Concurrent Error Detection in CMOS VLSI; (MIP-9308085 A001); $5,000.

This research is on a class of concurrent error detecting (CED) methods for design in CMOS VLSI. The basis for the research is a novel built-in current sensor which is critical to new design methods for CED circuits in static CMOS. This technique is being applied to designs of floating point arithmetic units, processor control units, on-chip cache memories, and fast fourier transform processors. Algorithms for partitioning realistic faults into subsets are being developed. New design rules for hardware redundancy are being explored.

University of Washington; Mani Soma; Fault Modeling and Test Generation for Mixed-Signal Integrated Circuits; (MIP-9212504 A001); $96,000; 12 months.

This research is on fault modeling and test generation for mixed signal integrated circuits. Defect and yield statistics are being used to derive comprehensive fault models for analog circuits. These include functional fault models useable in design for test and test generation. New test generation algorithms are being derived for analog circuits, and techniques are being developed to interface the analog tests with the digital circuitry in a mixed signal circuit. The fundamental theories are being validated experimentally with designs and data from industry. (Joint research with Jacob Abraham, University of Texas.)

Simulation

University of Arizona; Olgierd A Palusinski; Techniques for Accelerated Simulation of Electronic Circuits and Systems; (MIP-9017037 A005); $10,000.

This research applies spectral techniques to the time domain simulation of integrated circuits. The methods have been used to compute transient effects in multiple transmission lines. They are based on the expansion of unknown variables in the Chebyshev series. This assures very compact representation of waveforms, thus reducing computational penalties imposed by data interchange in relaxation methods. Tasks include:

1.	Modeling of MOS circuits based on modified nodal analysis.

2.	Application of spectral algorithms to bipolar circuits with various model switching strategies.

3.	Construction of an efficient spectral algorithm for computation of transients in lossy transmission lines with frequency dependent parameters and nonlinear termination networks.

4.	Using spectral techniques in a relaxation framework.

University of South Florida; Peter M Maurer; Improving the Performance of Digital Logic Simulation; (MIP-9403414); $98,626; 24 months.

This research is on compiled simulation of synchronous and asynchronous circuits. A digital logic simulation algorithm, called the Inversion Algorithm, is being investigated. This is an efficient algorithm, yet capable of simulating any digital circuit. Basic extensions are being made to the algorithm. These involve including unit and multi-delay timing models, a logic model with unknown value, new gates, new types of functions, as well as bit-parallel simulation. Further, it is being redesigned so as to reduce both the complexity of the simulation and the number of events processed during simulation. Additional activities include extending the existing model to a multiple processor implementation, and to handle asynchronous sequential circuits. Application of the Inversion Algorithm to hierarchical simulation and incremental compilation is being explored.

University of Illinois; Resve A Saleh; PYI: A Simulation Environment for the Analysis of Transient Faults in VLSI Circuits; (MIP-9057887 A005); $62,500; 12 months.

This research is on accurate simulation techniques and modeling approaches for analog circuits. High-level modeling approaches are being developed for functional blocks in the circuits that improve the overall efficiency of simulation. Software is being developed that checks for the integrity and robustness of new macro-model primitives before they are used in a simulation. A consistency checking and optimization tool is being used to verify and correct the performance of a given parameterized macro-model. The new models and algorithms are being integrated into a multi-level analog simulation tool that includes the ability to perform circuit level, functional level and behavior level simulation within one simulation run. Circuits considered are sigma-delta modulators, phase-locked loops, and switched capacitor circuits.

Michigan Technological University; Jeffrey O Coleman; RIA: Convex-Programming Design of Signals and Systems; (MIP-9409686); $46,775; 36 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $97,114).

The PI is creating a special-purpose programming language in which optimization problems can be specified in a natural and direct way. The focus is on developing associated translation software to convert such a specification into a particular canonical form for numerical optimization using recently developed, ultra-efficient, interior-point algorithms. The canonical form is a linear-matrix- inequality (LMI) program, where each constraint takes the form of a requirement that a linear (plus a constant) matrix function of the optimization variables be positive definite.

Control theorists have recently demonstrated that a tremendous variety of constraints can be put into this generic form. Often, however, the required LMI constraints are not related to the underlying problem in an intuitive way. Software to translate specifications in a "comfortable language" to sets of LMIs is being developed in order to make these powerful optimization techniques easy to apply. The language is being applied to real problems in communication and signal-processing circuit designs.

State University of New York - Stony Brook; Michael M. Green, Robert C. Melville; Development of Continuation Methods for Circuit Simulation at Bell Laboratories; (MIP-9412779); $5,754; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $11,508).

The Simulation and Modeling Group at AT&T Bell Laboratories has recently created a circuit simulator for dc simulation of their in- house integrated circuits. This simulator, called SFRAME has advantages over simulation programs such as SPICE. These include global convergence, the ability to find more than one or sometimes even all of a circuit's operating points, and the ability to incorporate the sophisticated bipolar junction transistor models used at Bell Laboratories. This work is to make enhancements to SFRAME, including initialization capability, ability to simulate circuits containing MOS transistors, and identification of the stability of operating points found. This is an industry-university collaboration.

State University of New York - Stony Brook; Michael M Green; NYI: Improved Circuit Simulation Using Results from Circuit Theory; (MIP-9457387); $12,500; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $25,000).

This research is applying the principal investigator's previous work in the area of nonlinear circuit theory to the way designers simulate analog circuits. In particular, improvements to the continuation methods of solving dc operating points of circuits are being made guaranteeing that all of a circuit's operating points will be found during a single analysis. Continuation methods are being applied to sensitivity analysis of circuits; for example, by making observations of a continuation curve, a designer could determine whether a circuit is prone to a latch up condition. Another enhancement to circuit simulation includes checking the accuracy of transistor models by verifying that all models satisfy passivity and the no- gain condition.

University of Texas; Lawrence T Pillage; PYI: CAD Tools for New Circuit Technologies; (MIP-9157363 A004); $62,500; 12 months.

The research is on developing simulation capabilities at the system level, which are as powerful as those at the chip level. Tools which are applicable at the integrated circuit, packaging, module, and board levels without loss of generality are being developed. Topics being investigated are: fast extraction techniques which trade off some accuracy for efficiency; and simulation models and techniques to enable top-down design. Timing analysis of boards or multi-chip modules requires development of tools for the extraction, characterization and simulation of transmission lines at the system simulation level. Toward this end interconnect macro- models, similar to those for on-chip RC interconnect circuits, which are compatible with system-level design automation tools, are being explored.

University of Washington; Carl Sechen; Symbolic Analysis of Large Analog Circuits; (MIP-9406470); $46,000; 12 months.

This research explores algorithms and techniques for symbolic analysis of large linear or linearized integrated circuits in the complex frequency domain. The approach is to extract transfer functions of circuits in symbolic form. In the case of large circuits, approximate symbolic network functions, in expanded or nested format, are generated. Both perturbation-based, and tree enumeration approaches are being used. The symbolic algorithms and simulators are being integrated into an analog design automation system.

University of Washington; Andrew T Yang; NYI: Modeling and Simulation of Advanced Microelectronics and Optoelectronic Circuits and Systems; (MIP-9257279 A002); $62,500; 12 months.12 months.

This research is on modeling and simulation of mixed analog/digital circuit designs. Topics include:

1.	Hierarchical modeling and simulation of tightly coupled, mixed digital circuits;

2.	Simulation of high-performance circuits with nonlinear and electromagnetic effects;

3.	Modeling and simulation of optoelectronic integrated circuits, with automatic model generation;

4.	Development of a technique for fast power waveform simulation based on analytic digital macromodeling;

5.	Simulation of interconnect problems using asymptotic waveform evaluation so as to obtain efficiency and accuracy in approximating nonlinear portions of the circuit.

Algorithms for solving these problems, including methods for simulating designs with over 100,000 transistors, are being developed.

Other

University of California - San Diego; Michael J Bailey, Ramesh C Jain; Making Rapid Prototyping Viable for Remote Use on the National Information Infrastructure; (MIP-9420099); $51,381; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, Experimental Systems Program, Circuits and Signal Processing Program and Microelectronic Systems Architecture Program - Total Grant $706,290).

This project is working to make rapid prototyping and reverse engineering facilities available over wide-area computer networks. It includes several research thrusts along with an integration effort to ensure that the facilities will be usable remotely with little on-site intervention. The project has four major thrusts:

1.	development of algorithms for checking consistency of geometric descriptions;

2.	development of new languages based on constructive solid geometry for communicating geometric descriptions;

3.	connection of rapid prototyping equipment to a wide rear network, with device drivers and server software to allow remote access; and

4.	connection of a 3D scanner to the network for remote access.

Carnegie-Mellon University; Roy A. Maxion, Andrzej J. Strojwas, David L. Banks; Discovering Information in Large, High-Dimensional Databases; (IRI-9224544 A001); $10,000; 12 months; (Joint support with the Knowledge Models and Cognitive Systems, Database & Expert Systems, Experimental Systems, and Statistics Programs - Total Grant $150,000).

This research addresses both theoretical and practical concerns. On the theoretical end, statisticians have recently proposed a number of compelling new ideas for high-dimensional, nonparametric regression. Little is known about their comparative performance in realistic situations. To remedy this, a large-scale simulation experiment is performed that employs statistical design to evaluate the effects of sample size, dimensionality, signal-to-noise ratio, and various kinds of underlying functions on the integrated mean squared error of the fitted model. The results of the study are examined in an analysis of variance, leading to clear conclusions as to the circumstances under which each of the proposed methods is most valuable. On the practical side, this research applies the methodology studied to VLSI production data.

University of Pennsylvania; Ruzena K Bajcsy, Dimitri Metaxas, Vijay Kumar, Daniel K. Bogen; Rapid Prototyping of Rehabilitation Aids for the Physically Disabled; (MIP-9420397); $179,999; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, Experimental Systems Program, Microelectronic Systems Architecture Program, CISE Institutional Infrastructure - Total Grant $1,044,713).

The methods of rapid prototyping are ideally suited to rehabilitation devices. Because each person requires unique performance and function in a rehabilitation device, devices specific to each person must be rapidly designed and produced. This project is investigating a completely integrated approach to the design and prototyping of passive mechanical rehabilitation devices. The approach involves: the quantitative assessment of the form and performance of human limbs; the design of the assistive device; evaluation of the device using virtual prototyping; feedback from the consumer and therapist; actual prototyping of the device; evaluation of the function and performance of the device; and redesign based on performance. The contributions of the product include: the development of new computer-based tools for the assessment of human performance; a manufacturing technique for a new class of hyperelastic materials; the integration of tools into a rapid prototyping system for rehabilitation devices; and development of mechanisms for systematic evaluation of the final product.

University of Utah; Erik L Brunvand; International Symposium on Advanced Research in Asynchronous Circuits and Systems, Salt Lake City, Utah, November 3-5, 1994; (MIP-9406532); $12,230; 12 months.

Research in asynchronous systems has had a resurgence in the past five years. Asynchronous operation is a viable option for modern system design. CAD systems have been developed for asynchronous circuit design, asynchronous processors have been built and evaluated, and controllers and systems have been designed. Problems in hazard-free operation, formal specification and verification of designs are being pursued. This symposium provides a forum where researchers may assess the current state of research in the field, and exchange ideas about present work.

Microelectronic Systems Architecture

Dr. J. Robert Jump, Program Director

(703) 306-1936 jjump@note.nsf.gov

Program Description

The Microelectronic Systems Architecture (MSA) program supports basic research on innovative design of computer systems at the physical and the system level to achieve high system performance. It encourages studies on the impact of new hardware and software technologies, as well as the impact of new applications and algorithms on computer system architectures. The style of architectural research employed includes theoretical and analytical studies, simulations and limited proof-of-concept prototyping. The program emphasis is on physically realizable systems.

TECHNOLOGY-DRIVEN ARCHITECTURES

The program supports architectural research which explores the capabilities and limitations of current and future hardware and software technologies. The objective in these studies is to better understand and to extend the performance, programmability, applications span, and reliability of microelectronic systems. Typical issues which are addressed include:

*	Methodologies for system design that map high-level abstractions and system specifications to low-level physical implementations while considering the design tradeoffs of chip area, power consumption, clock rate, packaging, cost and programmability.

*	Design of general-purpose and special-purpose computers, such as superscalar processors, parallel processors, distributed and real-time systems. The design issues may include cache and high performance memory systems, multi-threading, interconnection strategies, pipelines, networking and I/O systems, co-processor architectures, etc.

*	Studies of system programmability, architectural support for programming languages and system software, compiler techniques to exploit and to enhance system architectural features.

*	Studies of both hardware and software strategies to enhance the reliability, availability, and fault tolerance of microelectronic systems.

APPLICATION-DRIVEN ARCHITECTURES

The program supports the design of special-purpose computers for applications that can better utilize emerging microelectronic technologies in a cost-effective manner. Projects focusing on the design and development of application-driven computing systems must involve innovative architectural research and a cost/performance analysis and evaluation of the resulting design. Primary emphasis is placed on obtaining new architectural and design knowledge and evaluating their effectiveness. A secondary emphasis is placed on studies that can provide a better understanding of the problem solving methods using microelectronic technologies. Typical issues which are addressed include:

*Requirement specification, analysis, decomposition of problems and mapping of problem subcomponents onto functional building blocks, and analysis of the cost-performance trade-offs;

*	The design and evaluation of special-purpose computers and their required software for applications whose requirements, such as performance, memory size and physical size, cannot be met by available general purpose computers (for example, speech processing, graphics, simulation, image processing, signal processing, artificial intelligence and neural networks).

Initiatives and Opportunities

Special areas of research of interest to the Microelectronic Systems Architecture program include:

*	Design and evaluation of high performance memory systems, including I/O, for superscalar and parallel machines.

See the Dear Colleague Letter NSF 94-75 and the NSF Workshop on High Performance Memory Systems Final Report (Report No. TR-93-35, Computer Science Dept., University of Virginia, June 1993).

*	Innovative application-specific machine architectures that can tackle grand challenge problems, e.g. biotechnology and environmental studies, etc.

*	Design and evaluation of innovative microelectronic systems using new device and packaging technologies such as optoelectronics, optical interconnects, VLSI, GaAs, MCM packaging, and analog-digital devices.

*	Performance evaluation of microelectronic systems using a combination of analytical modeling, simulation, benchmarking and measurements on such systems.

*	Experimental research that deals with building of small-scale, proof-of-concept prototypes, simulation or emulation of new system designs using software or FPGA emulators.

Awards

Technology Driven Architecture

University of Arizona; Ahmed Louri; Design of 3-D Optical Interconnects for High-Density Chip-to-Chip and Board-to-Board Interconnections; (MIP-9310082 A001); $98,822; 12 months.

As device speeds rise, communication rather than device speed becomes the limiting factor in performance and cost of high-performance computing systems. Optical interconnects offer the potential for high-speed, scalable communications that can keep up with progress in devices. This research explores the application of free-space optics to high-density interconnects that are capable of bandwidth, interconnect density, and error rates far beyond the capabilities of current electrical interconnects and backplanes. The approach consists of:

1.	developing suitable optical network topologies;

2.	identifying optical implementation techniques and required devices;

3.	identifying interface components;

4.	developing modeling and simulation techniques for evaluating the performance of the chosen topologies and implementations; and

5.	physically implementing and measuring some of the resulting networks.

University of California - Berkeley; Alan J Smith; Cache Memories and CPU Performance Architecture; (MIP-9116578 A002); $82,300; 12 months; (Joint support with the Computer Systems Architecture Program - Total Grant $132,300).

In the area of cache memories and CPU performance architecture the research efforts are directed at three items:

1.	A study of the behavior of vector workloads and the extent to which vector machines can be expected to benefit from the use of cache memories. Initial results suggest that cache memories would work well.

2.	A study of cache consistency in multiprocessors. Current research is directed at analyzing some multiprocessor traces in order to understand sharing behavior, and to evaluate the relative performance of a number of multiprocessor cache consistency algorithms. The project is generating further traces and study the effect of changes in the source code on sharing behavior.

3.	The measurement of the memory systems of a number of machines to determine the effect that those memory systems have on overall system performance.

University of California - Davis; Matthew Farrens; NYI: High Performance Single Chip VLSI Processors; (MIP-9257259 A002, A003); $89,315; 12 months.

The research is to investigate various configurations of decoupled architectures and to extend the concept into the field of parallel processing. It is anticipated that, with several decoupled processors communicating via architectural queues called Multiple Instruction Stream Computer (MISC), it will function as a type of dynamic superscalar processor, providing significant performance gains. The MISC architecture uses multiple asynchronous processing elements to separate a program into streams that can be executed in parallel, and integrates a conflict-free message passing system into the lowest level of the processor design to facilitate low latency intra-MISC communication. This approach allows for increased machine parallelism with minimal code expansion, and provides an alternative approach to single instruction stream multi-issue machines such as superscalars and VLIWs.

The relationship between optimal processor configuration and transistor count is also being investigated. The goal is to define the design points at which a change to multiple processors becomes advantageous.

University of California - Irvine; Kai-Yeung Siu; NYI: Analysis and Design of Artificial Neural Networks; (MIP-9357553 A001); $31,250; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $62,500).

Artificial neural networks present a new model for massively parallel computation and a promising paradigm for solving large scale optimization problems. This research is exploring the advantages of neural network-based models over conventional models for computation, and a novel design of neuromorphic computing architectures for applications in signal and image processing. A theoretical framework is being established to derive tight tradeoffs between the number of elements and the number of layers in neural networks. The results should answer some of the key open questions in the analysis of neural networks using classical mathematical tools such as rational approximation techniques and harmonic analysis.

University of California - Los Angeles; Milos D Ercegovac; Arithmetic Algorithms and Structures for Low-Power Systems; (MIP-9314172); $100,608; 12 months.

The objective of the proposed research is the development of numerical computing systems which operate with a small amount of electrical power. It concentrates on arithmetic structures and algorithms and models power consumption by the number of signal transitions. These low-power structures are essential for the development of future computing systems. An important goal of the proposed research is to further the understanding of the effect of number representation, algorithm, and implementation on the power dissipation of numerical computation structures. Moreover, methods and technique for the design of low-power structures are being developed, as well as low-power designs for specific operations, such as adders, comparators, multipliers, and dividers.

University of California - San Diego; Chung-Kuan Cheng; Research on Circuit Partitioning; (MIP-9315794, A001); $38,686; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $62,371).

This is an investigation into hierarchical partitioning methods motivated by the need to:

1.	cope with high circuit complexity,

2.	improve a system's performance under I/O pin count constraints, and

3.	control intermodule delay in order to optimize system performance.

The principal investigator is extending partitioning research by adopting different circuit models including petri nets, data flows, and state machines, by improving the efficiency and effectiveness of the methods, and by deriving theoretical results on variations of partitioning formulations. He is also applying partitioning methods to netlist mappings for various hardware emulation machines and to find potential applications of these methods to VLSI design problems.

University of California - Santa Cruz; Anujan Varma; NYI: High-Speed Interconnection and Switching Technologies; (MIP-9257103 A002, A003); $92,091; 12 months.

This research aims to develop architectures and protocols for high-speed interconnection within computer systems. Typical applications to be considered include interconnection of processor subsystems among themselves for multiprocessor configurations, and the interconnection of processors to I/O subsystems. The focus is on high-speed crossbar switches as the interconnection means. The structure of these switches as well as mechanisms for connection setup, routing, and flow-control across multiple cascaded switches are being studied. Photonic switch architectures obtained by combining dimensions of switching, such as wavelength and space, are under investigation.

University of Southern California; Massoud Pedram; NYI: Low Power VLSI Design; (MIP-9457392); $12,500; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $25,000).

This research investigates modeling and estimation of power consumption as well as techniques for minimizing power at the various levels of design abstraction (layout, logic, register- transfer and behavioral levels). Principles and methods to guide the design of power efficient electronic systems are being explored; and the impact of availability of low-power design techniques on chip, module, and system level designs is being assessed. Topics being investigated include: spatio-temporal power estimation; state assignment for low power; power dissipation in boolean networks; common subexpression extraction; and FPGA synthesis for low power.

University of Colorado; Harry F Jordan; Propagation Delay Uncertainty and Its Effect on Latchless Circuits; (MIP-9322241); $48,778; 12 months.

This project is investigating the use of time-of-flight design techniques in the design of optical computers. This is a new design approach that takes advantage of the absence of capacitive and inductive effects, giving optical interconnects an advantage over electrical one in high-speed digital systems. As a result, propagation delays can be precisely controlled in optical interconnects and logic, thus mitigating problems such as clock skew. This feature of optics motivates a new method of digital design, where latches used to synchronize signals are removed. To synchronize signals at logic gates, the designer instead relies on adjustments of signal propagation delays. Clock gating is used to eliminate residual timing uncertainty which would cause phase drift in feedback loops. This new scheme eliminates latch overhead and allows deep pipelining at the gate level.

Georgia Institute of Technology; Umakishore Ramachandran; PYI: Architectural Issues in Parallel and Distributed Computing; (MIP-9058430 A004); $62,500; 12 months.

Beehive is a project that investigates the software and hardware issues in the design of scalable shared memory multiprocessors. The architecture is designed to support a form of weakly consistent memory model in a cache-based multiprocessor environment. The novel aspects of the architecture are reader- initiated cache coherence, latency tolerance through buffered writes, elimination of false-sharing, and efficient support for synchronization via the caches. The architectural features are designed to be compatible with an interconnection network.

Research issues include: Compile-time and runtime issues in the exploration of the weak memory model and the architectural features, novel simulation techniques for the evaluation of such complex parallel systems, and exploration of optical interconnects for such scalable architectures.

Georgia Institute of Technology; Umakishore Ramachandran, H. Venkateswaran; The Impact of Architectural Features on the Performance of Parallel Algorithms; (MIP-9200005 A002); $89,943; 12 months.

The main thrust of the research is to study the inter- relationship between parallel algorithms and architectures. The objective is to understand the impediments to the efficient implementation of parallel algorithms on realistic parallel architectures. This research involves studying the impact of architectural issues such as latency, network contention, granularity, synchronization, and communication on the performance of parallel algorithms. The approach to be taken is to identify frequently occurring parallel kernels in large-scale scientific/engineering applications; experiment with these kernels on target architectures of both SIMD and MIMD varieties; and augment the experimental work with simulation studies to extrapolate the results for future parallel architectures. The effects of input/output features on the performance of such parallel kernels are also being studied.

University of Illinois; Andrew A Chien; High-Performance, Adaptive Routing in Multiprocessor Networks; (MIP-9223732 A001); $86,997; 12 months.

The selection of good routing algorithms in multicomputer networks is necessary to prevent deadlock, avoid hot spots, and maximize performance. This project establishes a framework for selecting routing algorithms, which consists of four parts:

1.	selection of deadlock-free algorithms with varying degrees of adaptiveness;

2.	a set of analytic models of router speeds based on switch and buffer delay measurements;

3.	an empirical study of network traffic patterns to determine the need for adaptiveness in routing; and

4.	a set of techniques for extending routers to meet requirements such as fault tolerance and in-order message delivery.

University of Illinois; Benjamin W Wah; Architecture Specific Resource Management Via Intelligent Compilation and Strategy Learning; (MIP-9218715 A002, A003); $107,739; 12 months.

This research targets efficient distributed computing through intelligent scheduling of application programs. The approach has three components: compiler development, measurement of system loads, and automated learning of optimal scheduling policies. Compilers are modified to extract control and data dependencies from applications programs, emit performance monitoring code, and allow partitioning into processes with predictable resource requirements. A neural network model is being developed to characterize system loads based on ready list lengths, I/O traffic, and network congestion. Finally, an automated learning system will tune scheduling policies to balance system loads using the predicted and measured application program requirements.

University of Illinois; Pen-Chung Yew, John Bruner, Wen-mei Hwu; Improving the Performance of Scalable Shared-Memory Multiprocessors; (MIP-9307910 A001); $169,669; 12 months.

Sophisticated performance measurement and simulation tools developed on the Cedar multiprocessor system during the last four years are being used to study several key architectural and compiler issues that can enhance the performance of scalable shared memory multiprocessors. These issues include memory latency reduction and hiding strategies, data synchronization requirements for loop-level parallelism, and hierarchical network design. The study of these issues involves the hardware-assisted collection of empirical data on Cedar and the use of simulation. The information thus obtained could lead to the design of next- generation systems that, compared to present-day systems, provide higher sustained performance across a broader range of applications.

Louisiana State University; David M Koppelman; RIA: Employing Instruction History in the Management of Shared Memory Coherent Caches; (MIP-9410435); $91,848; 36 months.

This project is investigating a coherent cache parallel computer in which decisions on a particular cache block are based upon the run time history of the particular instruction accessing the block. The cache management scheme will detect and exploit a variety of instruction behaviors. The system could have certain instructions invalidate after reading, force a cache block to be copied to another processor, or, on a miss, bring in a cache block with a predetermined invalidation time. These will result in fewer messages and lower latency. Each of these techniques is being developed in detail and evaluated using execution driven simulations. The results will establish the efficacy of the technique which can be used to improve the performance of a wide range of parallel computers from office fileservers to supercomputers.

University of Massachusetts; Maciej Ciesielski and Wayne Burleson; High-Performance VLSI Synthesis with Wave Pipelining; (MIP-9208267 A02); $66,914; 12 months (Joint support with the Systems Prototyping and Fabrication Program - Total Grant $91,914).

Wave-pipelining is a method of high-performance circuit design which implements pipelining in logic without the use of intermediate latches. As a result, several computation waves (signals) related to different clock cycles can propagate through the logic simultaneously. This research extends previous implementations of wave-pipelining in static logic to include dynamic CMOS logic which is known for its smaller area and higher-performance. Previous work in wave-pipelining uses the insertion of delay elements on signal and clock lines to equalize path delays. These delays are often imprecise and can require a significant amount of VLSI area. To avoid these problems, we equalize the paths by restructuring the computation within the logic block. The restructuring at the logic level using tools of modern logic synthesis, is targeted towards highly structured computations and regular arrays. The new methods are implemented in a suite of CAD tools to make wave pipelining accessible in automatic VLSI synthesis systems. Several VLSI test chips are designed, fabricated and tested to verify the feasibility of our methods and CAD tools.

Michigan State University; Lionel M Ni, Philip K McKinley, Abdol Esfahanian; Multicast Communication in Multicomputers; (MIP-9204066 A003, A004); $131,823; 12 months.

This research project studies multicast communication, in which the same data packet is delivered from a source node to an arbitrary number of destination nodes. The project explores architectural support for multicast as well as software support for use in systems that do not provide architectural support.

University of Michigan; Peter M Chen; RIA: Designing Hierarchical Storage Systems for Large Capacity and Low Latency; (MIP-9409229); $99,999; 36 months.

This project is investigating the integration of new storage technologies, such as flash RAM and helical scan tapes, into the storage hierarchy to take advantage of each technology's strengths while masking its weaknesses. Ground-breaking work in disk arrays has already been accomplished; in this project, the emphasis is on other areas of the hierarchy, such as solid-state memories and magnetic tapes. For example, this research is investigating how to increase the effective capacity of solid-state memories to mitigate their higher cost. This research consists of three stages:

1.	measure new storage devices and trace current I/O workloads;

2.	design and simulate new hierarchical architectures and algorithms; and

3.	implement a prototype hierarchical storage system and measure its operation under real use.

University of Michigan; Pinaki Mazumder; Theory, Design, Implementation and Automatic Compilation of Adaptive Circuits for Built-in Self-Repairable USLI/MCM Chips; (MIP-9312604); $182,888; 36 months.

The goal of this research is to develop an innovative and unified methodology for designing self-repairable ultra-large integrated (ULSI) circuits and multi-chip module (MCM) chips. This research is exploiting the combinatorial optimization capabilities offered by adaptive circuits consisting of simple threshold devices interconnected programmable resistive networks for the purpose of adding a self-repair capability to hardware devices.	The proposed research consists of three phases. In the first phase, theoretical models for both regular array logic and unstructured random logic repair problems are being developed, and extensive simulations are being performed to measure the performance of the adaptive self-repair circuits. In the second phase, adaptive circuits are being designed using CMOS technology, and experimental chips are being fabricated and tested as "proofs of concept." In the third phase, software are being developed to allow the proposed adaptive built-in-self-repair circuits to be automatically synthesized by VLSI/CAD software and incorporated within macro blocks. This project initiates a new area of research that is a natural sequel to the on-going works in the fields of Built-In-Self-Testing (BIST) and Design for Testability (DFT).

University of Michigan; Karem A Sakallah, Trevor N Mudge, Edward S Davidson; Timing Issues in the Design of Digital Systems; (MIP-9404632); $116,678; 24 months; (Joint support with the Design, Tools and Test Program - Total Grant $350,034).

This research is on a timing verification and optimization framework for designing an entire digital system (e.g., a microprocessor). The research builds on a widely used model for synchronous timing analysis and an efficient method for estimating gate and wire delays. The model is being extended to include relevant functional information in order to enhance accuracy. Components of the framework are: design decomposition to isolate critical elements; a path delay calculator; algorithms for finding synchronizer components; clock analysis algorithms; a symbolic sequential timing verification component; a hybrid timing-logic simulator; and design optimizers.

Rutgers University; Miles Murdocca; Development of a Methodology for Implementing Hardware Dataflow Graphs Using Reconfigurable Optical Interconnects; (MIP-9224707 A001); $10,000.

In this project a system is being built to translate a dataflow language into hardware and implement the hardware on an optical gate array. The system is comprised of three components: a compiler to translate a dataflow language such as ID into a dataflow graph; a method for converting dataflow graphs into hardware described by a hardware description language, along with a simulator; and a synthesis program for mapping HDL descriptions onto an optical gate array. The optical gate array consists of planes of electronic gates, with the planes interconnected by free-space optics. An advantage of this kind of gate array is quick reconfiguration of the optical interconnections which allows dataflow graphs to be changed quickly.

This project is applicable to the development of advanced integrated engineering cells for manufacturing. Because of noise immunity and lack of electromagnetic interference, optical computation is well-suited to the factory floor. Reconfigurable optical computers of the type under development in this project may allow high-speed computation to be inserted into manufacturing processes in new ways.

State University of New York - Buffalo; Chunming Qiao; RIA: Reducing Communication Latency with Path Multiplexing in Optically Interconnected Multiprocessor Systems; (MIP-9409864); $96,300; 36 months.

This project develops an innovative approach to all-optical TDM communications in multiprocessor systems. The proposed approach is an extension of a previously developed connection paradigm for reducing control latency in reconfigurable optical interconnection networks. Using the proposed approach, a connection is established during a set of time slots along the path which are dependent on each other, so that no time-slot interchanging is required and simple switching devices can be used. As a result, the overall communication latency as well as the complexity of the network can be reduced. Thus, a near term impact of this research is on the design of high-performance, low-complexity optical interconnection networks suitable for multiprocessor systems. The research also has long-term impact on the advancement of technologies such as Asynchronous Transfer Mode (ATM) and Wavelength-Division Multiplexing (WDM) as the emerging technologies for computer communications.

State University of New York - Buffalo; Ramalingam Sridhar; RIA: High-Performance VLSI Systems Using CMOS Wave- Pipelined Transmission Gate Logic; (MIP-9409762); $97,370; 36 months.

Wave pipelining eliminates the intermediate register stages in a pipelined system by using the internal capacitance of the combinational logic for temporary storage. To obtain a high operating speed, equal path delays must be ensured between all the input and the output nodes of a given functional block. This requires symmetric rise and fall times, and delay independence on the input patterns for each component within the functional unit. This project proposes a method that uses a modified complementary Pass-transistor Logic (CPL) circuits as the basic cells to implement a high performance CMOS wave-pipelined system. Preliminary research and design results show that the family of basic cells, called Wave-pipelined Transmission-Gate Logic (WTGI), using standard CMOS technology, can be designed to have equal rise/fall times and reduced gate delay variations as compared to other approaches. The project addresses the design of a WTGL cell library for computational and signal processing applications. Further, logic synthesis and the delay tuning algorithms are being developed with an emphasis towards an application in signal processing. CAD tools that can effectively use the WRGL technique are being developed.

North Carolina State University; Wentai Liu; CMOS IC Performance Enhancement Via Wave Pipelining; (MIP-9212346 A002); $87,063; 12 months.

Wave pipelining techniques have a good potential to improve the performance of a digital system design. The success of achieving CMOS wave pipelining requires a design methodology which tightly couples the knowledge of technology, process, circuit, logic, and system architecture design as well as CAD tools for design and testing. While preliminary results have clearly demonstrated the feasibility of wave pipelining in CMOS, more work is needed toward the efficient design of wave pipelined systems. This project is to develop and demonstrate design techniques and VLSI structures for wave pipelining based on CMOS technology, primarily because of its wide availability and relatively low cost. Useful application areas for wave pipelining in high speed systems include high speed sampling circuitry, digital phase locked loops, MUX and DEMUX, error correction circuits, data and clock recovery for fiber optics.

University of North Carolina - Charlotte; Junsheng Long; RIA: Recoverable Distributed Shared Memory Using Evolutionary Concurrent Checkpointing; (MIP-9410028); $100,000; 36 months.

The shared memory computation model provides an attractive alternative to the message passing model. In a distributed environment, node failures occur more often than in a tightly-coupled multiprocessor system due to man-made downtime. The fault recovery issue must be dealt with in order to make the shared memory computation model feasible for distributed environments.

The objectives of this project are:

1.	to develop a low overhead concurrent checkpointing scheme with a controllable checkpoint interval and no global synchronization;

2.	to design a recoverable distributed shared memory system based on the new checkpointing scheme;

3.	to build an experimental system to examine the engineering issues related to building such systems;

4.	to evaluate different checkpointing schemes, with benchmark applications; and

5.	to explore potential distributed applications, based on shared memory computations.

Carnegie-Mellon University; L. Richard Carley, David J Allstot, Rob A Rutenbar, Donald E Thomas; Design of Ultra-Low Power IC's; (MIP-9408457); $104,890; 24 months; (Joint support with the Experimental Systems Program - Total Grant $554,000).

This project combines analog circuit design and CAD to produce digital circuits that can operate at substantially reduced voltages, which will result in lower power consumption. The project has introduced the QuadRail logic family, which allows voltage control of transistor thresholds to maintain constant logic thresholds. Use of this family permits lower supply voltages because of the tighter control of device thresholds. However, use of this family requires optimization of individual digital cells, new device layout methods, and new strategies for floorplanning, placement, and routing. The research in this project is exploring all of these optimization areas, and is producing a battery powered demonstration system for speech signal processing.

Pennsylvania State University; Chitaranjan Das; Low Cost Adaptive Routing Algorithms for n-Dimensional Meshes; (MIP-9406984); $116,969; 24 months.

This main thrust of this research is the performance modeling of routing algorithms. Almost all prior research work on oblivious and adaptive routing using virtual channel flow control relies on simulation for performance prediction. Although simulation can mimic a physical system quite accurately, it is very expensive in terms of computation time. The analytical models being developed will be quite effective in evaluating various routing algorithms and architectural features, and are much more efficient than simulation. The project is also investigating the fault-tolerant properties of adaptive routing algorithms.

University of Rhode Island; Qing Yang; Introducing a Novel Cache Design to Vector Computers; (MIP-9208041 A002); $10,232.

This is a supplement to provide a Research Opportunity Award (ROA) for a faculty member at an urban undergraduate minority institution. The visiting faculty member is studying the caching behavior of an interval Newton method for solving large systems of nonlinear equations. Both analytical and experimental techniques are being used to determine the caching behavior of several algorithms for solving systems of equations. Caching behavior is being studied on both existing vector computers and on the new cache organization that has been designed by the principal investigator.

Texas A & M University; Laxmi N Bhuyan; Cache Architectures for Large Shared Memory Multiprocessors; (MIP-9301959 A001); $98,472; 12 months.

This project addresses the problem of designing coherent caches for scalable multiprocessors with shared address spaces. Maintaining cache coherence in large-scale systems is time consuming due to the lack of sufficient broadcasting capacity in the interconnection networks. A dynamic cache coherence protocol is being designed and evaluated to reduce the cache coherence overheads in large systems. This protocol limits invalidation or update traffic to a subtree of the interconnection network. The first phase of the project consists of embedding rooted trees into various networks, and studying the hardware and timing complexities of directories using the embeddings. In a second phase, issues such as fault tolerance adaptive routing, and task mapping are being addressed. The research makes use of analytic techniques and execution driven simulation.

University of Washington; Susan J Eggers; PYI: Code Generation for Uniprocessors; (MIP-9058439 A004); $62,500; 12 months.

The long range focus of this research is on improving the performance of parallel programs. One thrust uses compiler technology to obtain better multiprocessor cache performance, i. e. reduce the amount of sharing-related bus traffic. The initial phase of that work is the detection of false sharing and measuring its impact on cache miss ratios and bus utilization. Another area of investigation is measuring the amount and type of program level parallelism in nonscientific parallel programs and determining the levels of hardware parallelism that best execute them.

The current focus of the research is in the following areas:

1.	Compiler reorganization of shared data;

2.	Runtime code generation; and

3.	A protection model for a single address space architecture.

University of Wisconsin; Mark D Hill; PYI: Cache Memory Design; (MIP-8957278 A005); $37,500; 12 months.

The long range focus of this research is on the performance evaluation and implementation of multiprocessors that are easy to program, provide orders of magnitude more computing power, and can be implemented cost effectively. The principal thrust of this work is on the design of cache memories, with specific tasks on the development of multiprocessor compilers, the implementation and semantics of address translation, the implementation of coherent shared memory in systems with multiple caches, the interaction between cache design and implementation factors, and the future effectiveness of cache hierarchies.

The focus of the research during this period is on the completion of the study of cooperative shared memory, the continuation of the work on the Wisconsin Wind Tunnel, and the study of operating system modifications to take advantage of variable page sizes.

Application Driven Architecture

San Diego State University; Jay H Harris; RUI: VLSI Implementation of the Z-J Algorithm for Bit Error Correction; (MIP-9114270 A002); $59,353; 12 months.

The focus of this research is on the design of very large scale integrated circuit structures that can implement the Ziganirov-Jelenek stack algorithm for sequential decoding of long constraint length codes. Chips are being fabricated using mask making and foundry facilities available through the USC/ISI Mosis Program.

This research is also focused on the impact of stack design and algorithm performance of factors like the word length of the decoding metric, the length of the stack, and the constraint length. These results can improve our understanding of the design of high speed sequential decoders. It will result in devices that can test decoding concepts, and can extend the range of application of an important technique for achieving reliable communication and high density data storage.

San Jose State University; Belle Wei; RUI: A VLSI Arithmetic Data Path for a Complex Number Digital Signal Processor; (MIP-9321143); $34,285; 12 months.

This project deals with the design and implementation of VLSI algorithms and circuits for arithmetic operations on complex numbers. The research is motivated by the need for these circuits in high-speed digital signal processing applications. The goals of the research are to:

1.	Develop VLSI design algorithms for the arithmetic data path of complex number digital signal processors.

2.	Design and implement VLSI circuits and components for the developed algorithms, with emphasis on both architecture and circuit design.

3.	Study the trade-off between chip area and VLSI circuit latency/throughput and to develop a design curve exhibiting their trade-offs for benchmark complex number applications.

4.	Specify other data path components for the complex number digital signal processor to support high-throughput input/output operations and ease of programming.

University of California - Berkeley; John Wawrzynek; PYI: Application-Specific VLSI Architectures; (MIP-8958568 A007, A008); $73,200; 12 months.

The focus of this research is on designing application- specific VLSI architectures, specifically for the generation of realistic musical sounds using parallel processing and VLSI technologies. The approach is to develop mathematical models for the motions of physical musical instruments, and to numerically solve these models to produce sounds using "synthesis by simulation. " The design of efficient and fast application-specific VLSI computing architectures is crucial to the success of this project due to the requirements on massive computations and on real-time human interaction. The focus of this research is on the integration of the vector coprocessor, designed to accelerate neural net computations, into a supercomputer designed for connectionist computations. This supercomputer will use the high-speed CMOS techniques under development and may include provisions for analog I/O.

University of California - San Diego; Michael J Bailey, Ramesh C Jain; Making Rapid Prototyping Viable for Remote Use on the National Information Infrastructure; (MIP-9420099); $4,440; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, Experimental Systems Program, Circuits and Signal Processing Program, Design, Tools and Test Program and Communications Research Program - Total Grant $706,293).

This project is working to make rapid prototyping and reverse engineering facilities available over wide-area computer networks. It includes several research thrusts along with an integration effort to ensure that the facilities will be usable remotely with little on-site intervention. The project has four major thrusts:

1.	development of algorithms for checking consistency of geometric descriptions;

2.	development of new languages based on constructive solid geometry for communicating geometric descriptions;

3.	connection of rapid prototyping equipment to a wide rear network, with device drivers and server software to allow remote access; and

4.	connection of a 3D scanner to the network for remote access.

University of Southern California; V. K Prasanna; Parallel Techniques for Problems in Vision & Robotics; (IRI-9217528 A001); $30,881; 12 months; (Joint support with the Robotics and Machine Intelligence Program - Total Grant $61,763).

This research continues earlier efforts of the PI in studying parallelism for image understanding and robotics as well as in understanding the power of reconfiguration. There are three spheres of emphasis in this work:

1.	design and analysis of efficient parallel algorithms for problems in vision and robotics on well-established parallel models of computation;

2.	implementation of the parallel solutions on state of the art parallel machines; and

3.	a study of the power of reconfigurable meshes in solving fundamental problems of interest to the parallel processing community as well as problems arising in image processing, vision and robotics.

These problems are among the generic high and intermediate level problems in image understanding and robotics. Specifically, in image understanding, design and analysis of algorithms for motion analysis (object tracking), image and stereo matching, model based object recognition as well as algorithms for several symbolic computation based approaches used in understanding images will be investigated. In robotics applications, parallel solutions to a variety of practical problems in real time robot motion- and task-planning arising in terrain navigation and industrial automation will be investigated. The parallel models to be employed include the mesh-connected processor array, reconfigurable mesh array, and the hypercube. The algorithms will be implemented on Connection Machine CM-5, Maspar MP-1 and the Image Understanding Architecture (IUA). In the work on the reconfigurable mesh model, design and analysis of fast and processor efficient parallel solutions to several fundamental problems on the reconfigurable mesh will be investigated. Problems to be considered include arithmetic problems, image problems and geometric problems on planar points. Known techniques on other parallel models will be studied for possible mapping onto the reconfigurable mesh.

University of South Florida; N. Ranganathan; VLSI Architectures for Pattern Matching and Recognition; (MIP-9407034); $109,970; 36 months.

The goal of this research is the investigation, design and implementation of high performance VLSI architectures for two dimensional pattern matching and recognition. Although several hardware algorithms have been proposed in the literature for the one-dimensional pattern (string) matching problem and its variations, very little work has been done in the area of hardware algorithms for matching and recognition of two-dimensional patterns. Most of the research has been aimed at efficient software algorithms based on different features and matching strategies. Many pattern matching applications need real-time response, perform number of repetitive computations on different data sets, make use of regular and local operations, are modular, and have a fair amount of inherent parallelism. The design of special purpose hardware for pattern matching could speed up the task considerably, making it amenable for real-time applications.

Specifically, the main objectives of this research are:

1.	Develop new and efficient hardware algorithms and VLSI chips for a class of pattern matching problems such as scene matching, approximate string matching, polygon matching and tree matching.

2.	Design and develop an application specific system architecture for pattern matching and recognition through integration of the above mentioned VLSI components at board level.

Georgia Institute of Technology; Richard M Fujimoto; Adaptive Mechanisms for Parallel Simulation; (MIP-9408550); $193,383; 36 months.

This project is examining adaptive synchronization protocols that monitor the execution of the parallel simulator, and automatically adapt the simulator's execution to optimize performance. Adaptive mechanisms allow the underlying simulation system to achieve maximum performance, particularly for dynamically changing workloads that often arise in practice. These mechanisms can also simplify the development of parallel simulation software to the extent that some degree of performance "tuning" is automatically performed by the simulation system, rather than by the application programmer, who may not be an expert in parallel simulator performance.

A protocol that uses memory allocation to control execution is proposed. A second problem that is being addressed concerns analyzing and defining suitable incremental state saving methods that are designed to execute efficiently with rollback-based parallel and distributed simulators. Both problems are being attacked using experimentation on implementations running on multiprocessor hardware, and analytic modeling techniques.

Johns Hopkins University; Andreas G Andreou, Fernando Pineda; Analog Computation and VLSI Architectures for Contraction Mappings; (ECS-9313934 A001); $71,248; 12 months (Joint support with the Communications and Computational Systems Program - Total Grant $71,248).

This project is developing a new class of recurrent networks. The architecture of the networks is inspired by recent work on image encoding based on iterated transformation theory and it's associated inverse problems. The purpose is to restrict our investigation to networks that can be physically implemented in subthreshold analog VLSI. With their approach, analog components that implement high quality arithmetic operations are unnecessary. Indeed, significant departures from ideal linear behavior can be tolerated, provided that these departures are reproducible across chips.

Boston University; Mark G Karpovsky; On-Line and Off-Line Error Detection Mechanisms in the Coding Theory Framework; (MIP-9208487 A002); $62,874; 12 months.

This research focuses on the development of a unified framework for combining on-line and off-line error detection mechanisms at both the chip and board levels. This framework includes: concurrent checking of the device for on-line detection, space and time compression of test responses, analysis of distortions in the resulting signatures for error detection and diagnosis for built-in self-testing (BIST), and concurrent checking of hardware required for (BIST).

Princeton University; Kenneth Steiglitz; Scaling Large Special Purpose Computers; (MIP-9201484 A002); $84,689; 12 months.

The research is on the limits of scalable special-purpose architectures for highly parallel computation, especially computation on regular arrays. Important applications of array-based computation can be found in digital signal processing, and in many areas of scientific computation, including many-body problems with gravitational or coulombic interactions, fluid dynamics, and wave propagation. These applications require highly parallel computation either because of the need for real-time operation, or because the total number of operations required is very large.

The basic problems being addressed are:

1.	The design and reliability analysis of large fault-tolerant arrays, and on-line reconfiguration and error-detection algorithms for these special-purpose architectures;

2.	The design and analysis of reliable clocking schemes for very large arrays of processors, especially the comparison of synchronous, self-timed, and hybrid clocking;

3.	A study of the general issue of cost-effective scaling of large, special-purpose computer architectures for regular computations; and,

4.	Extension of the work to Hierarchical Data Computations, such as those in the fast monopole and multipole methods for many-body problems, where particles are distributed in space, and are clustered by decomposing space into hierarchical domains.

Oregon Advanced Computing Institute; Bella Bose, Sanjay Rajopadhye, Virginia M Lo; Algorithms and Abstractions for Mapping Parallel Algorithms to Parallel Architectures; (MIP-9108528 A004); $82,914; 12 months.

The problem of mapping parallel algorithms to parallel architectures involves the assignment of tasks in the parallel computation to processors and the routing of messages through the interconnection network. This research utilizes information about the regularity present in both the computation and the interconnection network for efficient mapping. It focuses on the design, implementation, and testing of mapping algorithms for three target architectures: the mesh, hypercube, and deBruijn network. In addition, it develops a graph description language and an underlying graph theoretic model to support mapping. The model captures information about the static and temporal structure of the computation, while the language enables the user to express this information in a natural and compact notation. This research represents a step in the evolution toward automatic mapping. It paves the way for the compiler to play an increasing important role as a source of information for the mapper.

Oregon State University; Bella Bose; Balanced Codes for VLSI Systems; (MIP-9404924); $187,805; 36 months.

This project deals with the properties and applications of balanced codes. In a balanced code, each code word contains equal number of 1's and O's. These codes find many applications in computer and communication systems such as noise reduction in VLSI systems, fault masking in bus lines of VLSI systems, delay insensitive communications in asynchronous systems, data transmission in fiber optics, data storage in optical discs and magnetic tapes, and fault tolerant synchronous circuits. The objective of this research is to develop design methods for balanced codes suitable to these applications. Our aim is to design codes which require low redundancy but at the same time have fast and simple encoding/decoding algorithms. Other topics such as error correcting balanced codes, asymmetric error correcting and detecting codes applicable to the above mentioned applications are also being investigated.

University of Pennsylvania; Ruzena K Bajcsy, Dimitri Metaxas, Vijay Kumar, Daniel K Bogen; Rapid Prototyping of Rehabilitation Aids for the Physically Disabled; (MIP-9420397); $160,000; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, Experimental Systems Program, Design, Tools and Test Program and CISE Institutional Infrastructure - Total Grant $1,042,713).

The methods of rapid prototyping are ideally suited to rehabilitation devices. Because each person requires unique performance and function in a rehabilitation device, devices specific to each person must be rapidly designed and produced. This project is investigating a completely integrated approach to the design and prototyping of passive mechanical rehabilitation devices. The approach involves: the quantitative assessment of the form and performance of human limbs; the design of the assistive device; evaluation of the device using virtual prototyping; feedback from the consumer and therapist; actual prototyping of the device; evaluation of the function and performance of the device; and redesign based on performance. The contributions of the product include: the development of new computer-based tools for the assessment of human performance; a manufacturing technique for a new class of hyperelastic materials; the integration of tools into a rapid prototyping system for rehabilitation devices; and development of mechanisms for systematic evaluation of the final product.

Brown University; Harvey F Silverman; Parallel Architectures for Speech Recognition: Testing Expensive Algorithms in a Reconfigurable Environment; (MIP-9120843 A004); $51,333; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $102,666).

A strong research program in the areas of computing architectures for advanced speech recognition, algorithms, and experimentation is currently in place in the Laboratory for Engineering Man/machine Systems (LEMS) at Brown. This research focuses on a reconfigurable, general-purpose, computing structure, and speech recognition/training algorithms, to advance the state-of-the-art in both areas through their interaction.

One feature of these efforts is the evaluation of the effects of changes to the early stages of a speech recognizer. This computationally intensive task will utilize the projected Armstrong III reconfigurable hardware system to accelerate the current training algorithm.

A second feature is the incorporation of improvements to the current computational and recognition performance of a talker-independent, connected alpha-digit recognizer, database, training, and tools, all developed at Brown. These include microphone-array data acquisition, new signal-processing algorithms, non-parametric modeling, better durational modeling, and new VQ/feature-space methods.

University of South Carolina; Thomas M Conte; RIA: Fast Simulation of Computer Architectures Using Field-Programmable Gate Arrays as Hardware Accelerators; (MIP-9410377); $84,955; 36 months.

This research is on architectural-level simulation using field-programmable gate arrays as hardware accelerators. The goals of this research include the development of a paradigm for architectural specification that is both general-purpose and can be used to produce fast and efficient simulators, development of a graphical user interface-based entry tool, development of tools for automatic translation of an architectural description to FPGA programming information, and implementation of a trace-driven execution environment to run the simulations. The key idea behind this work is to use FPGA's to simulate a system above the gate level, at the level of events, dependencies, resources and delays. FPGA's place a limit on the size of the hardware-implemented data structures, which will be extended via a software monitor to allow virtual, unlimited-length structures. The simulation will be automatically translated from a high-level description by use of methods adapted from high-level synthesis and the compilation of C programs. To aid in entering the architectural description, a graphical user interface tool is being developed. The paradigm for system description is based on a discrete-event architectural model of system behavior. This paradigm is hierarchical and provides a library that takes advantage of existing fast simulation techniques for cache and processor simulation.

Texas A & M University; Dhiraj K Pradhan; Development of Integrated On-Line and Off-Line Error Detection Mechanisms in the Coding Theory Framework; (MIP-9218238 A002); $66,436; 12 months.

This research focuses on the development of a unified framework for combining on-line and off-line error detection mechanisms at both the chip and board levels. This framework includes: concurrent checking of the device for on-line detection, space and time compression of test responses, analysis of distortions in the resulting signatures for error detection and diagnosis for built-in self testing (BIST), and concurrent checking of hardware required for (BIST).

Workshops and Conferences

University of Illinois; Wen-mei Hwu; 21st Annual International Symposium on Computer Architecture, Chicago, Illinois; (MIP-9414528); $6,000; 6 months.

This is an attendance and travel grant for the 21st Annual International Symposium on Computer Architecture on April 18-21 in Chicago, Illinois. It is co-sponsored by the Association for Computing Machinery and the IEEE. The Symposium, through a combination of invited talks, panel sessions, tutorials, workshops and refereed paper presentations, continues to serve the various needs of the computer architecture research community. It is an important conference in the computer architecture area. This grant provided support to help twenty graduate students attend the symposium.

Circuits and Signal Processing

Dr. John H. Cozzens, Program Director

(703) 306-1936 jcozzens@nsf.gov

The Program

The Circuits and Signal Processing (CSP) program supports basic research in the areas of digital signal processing, analog signal processing, and supporting hardware and software systems. This research is typically driven by important applications and emerging technologies. Signal processing is a highly active research area, with topics ranging from theory to Very Large Scale Integrated (VLSI) circuit implementations and applications. Although signal processing is typically driven by advances in technology, discoveries in this field also serve as a catalyst for new technological innovations. A taxonomy of research areas, based on signal characteristics, applications, and/or technology, include:

One-Dimensional Digital Signal Processing (1-D DSP) - the representation of time-varying signals (e.g., audio, EKG, etc.) in digital form, and the processing of such signals;

*	(adaptive) filtering and equalization

*	filter design, theory, and analysis, both linear and nonlinear multirate processing and wavelets

*	time-frequency representations

Statistical Signal and Array Processing (SSAP) - the use of statistical techniques for the processing of signals that may arise from multiple sources;

*	cyclostationary signal processing

*	higher order statistics

*	(statistical) array processing

*	nonstationary and time-frequency

Image and Multi-Dimensional Digital Signal Processing (IMDSP) - the acquisition, manipulation, and display of multidimensional data using digital technology;

*	image analysis, filtering, restoration, and enhancement

*	image and video coding

*	vector quantization

Analog Signal Processing (ASP) - the processing of data without conversion to sampled-digital form;

*	analog-to-digital conversion

*	analog curcuits and filters

Special attention is currently given to research in:

*	antenna array processing with application to wireless communications systems, especially cellular telephony, Personal Communications Systems (PCS), and wireless local area networks

*	computed tomography and SAR

*	data quality validation1

*	manufacturing applications, e.g., nondestructive test and evaluation

*	scalable/progressive/multiresolution approaches in signal decomposition, compression, and other signal processing1

*	signal compression for reduced data rate with applications to wireless communications systems

*	signal processing techniques to support content analysis1

Low priority areas include high-level image processing and high-level speech processing, as these areas are supported elsewhere in the Foundation; and mature areas such as classical circuit theory and (classical) spectral estimation.

Participation in signal processing research by undergraduate students and underrepresented faculty sectors is encouraged.

1 This is research topic was suggested by the panelists of a recent workshop on signal processing for the National Information Infrastructure (NII) sponsored by the Circuits and Signal Processing Program. This workshop was held at the National Science Foundation in Ballston, VA, on 18-19 August 1994, "to assess the current state of signal processing in the NII, to identify important issues and trends of research and development of signal processsing theory and applications for the NII, and to make recommendations for research and development." The entire document - NSF 95-10 (new) - is also avaible at web location http://www ee gatech.edu/users/215/nii/niireport.html

Awards

Circuits

University of California - Berkeley; Leon O Chua; Research on Problems in Nonlinear Networks and Systems; (MIP-9114168 A003, A004); $151,282; 12 months.

Nonlinearity is an essential component in almost all natural (from ocean waves to heart rhythms) and man made (from clocks to lasers) systems, but it is often shunned by engineers in view of its intractability. The goal of this research is to exploit the use of nonlinearity in engineering, and to develop mathematical techniques and numerical tools for analyzing complicated nonlinear phenomena, including bifurcation and failure boundaries, chaos, and the dynamics of sigma-delta modulation. Among several application areas involving nonlinearity, the focus is on the design of cellular neural networks for image processing such as handwritten character recognition (e.g., ZIP codes), motion detection, and early vision capabilities (e.g., robotic vision). To enhance the future engineer's ability to derive and validate nonlinear device models, and to analyze and design practical nonlinear circuits and systems, user friendly software and hardware tool kits are being developed which implement the most advanced mathematical theories and recently-developed techniques from nonlinear dynamics.

University of California - Irvine; Kai-Yeung Siu; NYI: Analysis and Design of Artificial Neural Networks; (MIP-9357553 A001); $31,250; 12 months; (Joint support with the Microelectronic Systems Architecture Program - Total Grant $62,500).

Artificial neural networks present a new model for massively parallel computation and a promising paradigm for solving large scale optimization problems. This research is exploring the advantages of neural network-based models over conventional models for computation, and a novel design of neuromorphic computing architectures for applications in signal and image processing. A theoretical framework is being established to derive tight tradeoffs between the number of elements and the number of layers in neural networks. The results should answer some of the key open questions in the analysis of neural networks using classical mathematical tools such as rational approximation techniques and harmonic analysis.

University of California - Los Angeles; A. N. Willson; Theoretical Studies of Continuous and Discrete-Time Electrical Circuits; (MIP-9201104 A002, A003); $114,900; 12 months.

This research is examining several important theoretical issues in nonlinear transistor networks including stability criteria for and global properties of dc operating points, transient circuit simulation, and stability issues related to analog resistive networks for implementing two-dimensional signal processing algorithms. Additional research is being pursued in the design of FIR filter banks, neural networks, and other topics. While these areas of research are somewhat diverse, they share the unifying characteristic that all projects have as their primary goal the development of a better and more rigorous understanding of the fundamental nature of the circuits and their properties, and the development of new and useful techniques for their analysis and design.

State University of New York - Stony Brook; Michael M. Green, Robert C Melville; Development of Continuation Methods for Circuit Simulation at Bell Laboratories; (MIP-9412779); $5,754; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $11,508).

The Simulation and Modeling Group at AT&T Bell Laboratories has recently created a circuit simulator for dc simulation of their in-house integrated circuits. This simulator, called SFRAME, has a number of advantages over Newton-Raphsonbased simulation programs such as SPICE. These advantages include global convergence, the ability to find more than one or sometimes even all of a circuit's operating points, and the ability to incorporate the sophisticated bipolar junction transistor models used at Bell Laboratories; running SPICE on circuits incorporating these models has led to severe convergence problems.

This research is affecting major enhancements to SFRAME, including initialization capability, ability to simulate circuits containing MOS transistors, and identification of the stability of operating points found.

State University of New York - Stony Brook; Michael M Green; NYI: Improved Circuit Simulation Using Results from Circuit Theory; (MIP-9457387); $12,500; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $25,000).

This research is applying the principal investigator's previous work in the area of nonlinear circuit theory to make major enhancements to the way designers simulate analog circuits. In particular, improvements to the continuation methods of solving dc operating points of circuits are being made guaranteeing that all of a circuit's operating points will be found during a single analysis. Moreover, continuation methods are being applied to sensitivity analysis of circuits; for example, by making observations of a continuation curve, a designer could determine whether a circuit is prone to a latch up condition.

Erroneous models are thought to be a major source of convergence problems and erroneous results in circuit simulation. Therefore, another enhancement to circuit simulation includes checking the accuracy of transistor models by verifying that all models satisfy passivity and the no-gain condition.

Analog (Mixed Analog/Digital) Signal Processing

University of California - Berkeley; Paul R Gray, Robert G Meyer; Continuation of Research in High-Frequency Analog Electronic Circuits for Communication Systems; (MIP-9101525 A002); $110,000; 12 months.

This research is in the area of monolithic high- frequency communication circuits, and is directed at exploring new ways to use silicon integrated-circuit technology to improve the performance and reduce the cost of communication systems of various kinds with primary emphasis on data communications. Particular emphasis is placed on circuit techniques applicable to clock recovery in high-speed communications systems, optimization of the sensitivity in fiber-optic communication receivers, and the application of BICMOS technology for the particular needs of high-speed communications applications.

University of California - Davis; Stephen H Lewis; RIA: High-Speed, High-Resolution, Analog-to-Digital Conversion in CMOS Technologies; (MIP-9210071 A001); $6,438.

While traditional video-rate applications have required no more than 10-bit resolution, new applications such as wide dynamic-range imaging systems require at least 12-bit resolution. The requirements for such applications exceed the capabilities of present, state-of-the-art analog-to-digital converters using CMOS technologies. The objectives of this research are:

1.	to create techniques that can overcome the practical linearity limitations of analog-todigital conversion interfaces without an associated loss in conversion rate and without the use of trimming or calibration; and,

2.	to demonstrate these techniques by fabricating prototypes.

The focus of 1. is on pipelined, analog-to-digital conversion interfaces in CMOS technologies for high-resolution, video-rate applications. Circuit techniques that can overcome the practical linearity limitations are being studied. Since these techniques may reduce the maximum conversion rate, combinations of parallelism and digital signal processing techniques that have the potential to overcome such a reduction are being explored.

University of Illinois; Bang-Sup Song; Generalized Background Digital Calibration of ADC's; (MIP-9312671); $105,664; 24 months.

This research is part of a continued effort to extend a background calibration principle to common multi-step/pipelined Analog-to-Digital Converters (ADC's). The basic idea is to replace a component trimming procedure usually done in the factory by a hidden electronic real-time calibration circuit running in background. Unlike other calibration techniques running in the foreground, this technique is based on dithering and nonlinear interpolation. The goal is to improve the performance of inherently fast ADC's by maintaining simple system architectures that perform a sophisticated trimming operation in background. The generic research on lower-power design using a recycled residue amplifier and capacitive reference divider will help develop a family of high-performance analog digital interface circuits with low power and premium speeds not readily available in monolithic forms.

Oregon State University; Gabor Temes; Digitally Corrected Oversampling Data Convealers; (MIP-9196199 A003); $29,172; 12 months.

This research involves the development of faster and more accurate analog-to-digital and digital-to-analog data converters. The converters studied are of the interpolating type, which effectively trade conversion speed for accuracy. That is, in interpolating type converters, the use of a multibit (rather than a single-bit) front end in an interpolating converter can lead to a higher resolution for a given speed or a higher conversion speed for a fixed resolution. However, a multibit front end requires an analog component accuracy which cannot be achieved without complicated and expensive trimming and or randomizing techniques.	A novel digital self-calibration and correction technique which achieves the requisite accuracy of the multibit system without any trimming or randomizing, using only a simple additional digital

stage is being developed in this research. The work involves an architectural study of the novel system development of the circuit blocks needed, and design, fabrication and testing of several fully integrated converters based on the novel principle. This new approach should lead to faster and or more accurate converters than any of the currently available ones. Such converters will lead to further developments in important applications such as digital radio and television, digital audio, ISDN, radar, etc.

Washington State University; Terri S Fiez; NYI: High Performance Analog Signal Processing for Mixed-Mode Integrated Circuits; (MIP-9257112 A001); $62,500; 12 months.

The focus of this research is the development of high performance analog architectures and circuits for mixed analog-digital IC's. Emphasis is being placed on improving the immunity of the analog circuits to digital switching noise and on obtaining high speed and accuracy analog circuit performance with the newly emerging 3.3 Volt power supply standard. Current-mode circuits are being examined as a way of overcoming these limitations, and are being used to implement area efficient, high-order sigma-delta A/D converters. This research will yield a general understanding of the advantages and limitations of current-mode circuits as compared to voltage-mode circuits.

One-Dimensional Digital Signal Processing

Auburn University; Jitendra K Tugnait; Higher Order Statistical Signal and Image Processing and Analysis; (MIP-9312559); $88,042; 24 months.

This research is concerned with the development, analysis and evaluation of algorithms for signal/image processing and analysis that exploit higher order statistics of signals/images in addition to, or in lieu of, the usual second order statistics. Both time series (only system output is observed) and system identification (both input and output are observed) formulations are being considered; and both one-dimensional and multidimensional signals and systems are being investigated. Whereas the second order statistics of signals are a function of only the underlying system transfer function magnitude, Higher Order Statistics (HOS) of the data carry useful information about the phase characteristics of the underlying signal/system which is crucial in deconvolution problems such as those arising in digital communication channel equalization, seismic wavelet processing, and image restoration, analysis and synthesis.

Time domain as well as frequency domain methods using higher order cumulant functions and higher order cumulant spectra (or higher order integrated cumulant spectra), respectively, are being pursued. Among the applications being investigated are:

1.	image texture synthesis and classification;

2.	differential time-delay and doppler estimation in unknown spatially correlated Gaussian noise;

3.	blind deconvolution with unknown, possibly nonminimum, phase channels including image restoration; and,

4.	system identification with noise inputs.

California State University - Northridge; John W Adams; New Concepts in Digital Signal Processing; (MIP-9200581 A002); $79,466; 12 months.

Recent research has revealed that the minimax and least-squares optimality criteria are inappropriate for many digital signal processing applications. Minimax and least-squares optimization problems are subsets of a more general (and much more important) class of problems which are referred to as Peak-Constrained Least-Squares (PCLS) optimization problems. PCLS solutions are needed for many digital signal processing applications, but PCLS research is still in its infancy.

The objective of this research is to develop new concepts in digital signal processing that are based on PCLS optimization. Techniques from the theory of mathematical programming are being used as the basis for this research. Three categories of design algorithms are being developed:

1.	new multiple exchange algorithms;

2.	extensions of conventional quadratic programming algorithms; and

3.	extensions of Lawson's algorithm.

University of Southern California; Jerry M Mendel; Applications of Fuzzy Systems to Signal Processing; (MIP-9122018 A002); $70,094; 12 months.

In many practical signal processing problems information is often represented in two forms: one is a set of input-output data pairs, obtained by measuring the outputs of the system for some typical input signals; the other is a set of linguistic descriptions about the system, often in the form of IF-THEN fuzzy rules, from human experts who are very familiar with the behavior of the system. This research is developing a general method to combine both numerical input/output pairs and linguistic IF-THEN rules into signal processing system design within the framework of fuzzy system theory. The objectives are to:

1.	theoretically justify the practical successes of fuzzy systems;

2.	develop synthesis methods for fuzzy systems which use both numerical and linguistic information; and,

3.	apply these synthesis methods to signal processing problems, such as time-series prediction, and subject these methods to theoretical performance analyses.

An optimal design method for fuzzy systems which will match given input-output pairs to arbitrary accuracy is also being developed.

University of Southern California; Chrysostomos L Nikias; Adaptive Signal Processing Algorithms Based on Nonlinear Performance Criteria; (MIP-9206829 A002); $51,415; 12 months.

This is a collaborative research project with John G. Proakis (Northeastern University). The research focuses on the development, testing and mathematical analysis of adaptive signal processing algorithms based on nonlinear performance criteria. Areas of research include:

1.	blind deconvolution algorithms based on criteria with memory nonlinearity;

2.	decision feedback equalizers using higher-order statistics;

3.	joint estimation and detection algorithms of the ML-type and MAP-type when the signals are Gaussian distributed;

4.	adaptive multichannel signal recovery algorithms when the signals have gone through severe magnitude and phase distortion; and,

5.	blind deconvolution algorithms based on neural networks and Volterra filters.

Special emphasis is placed on the investigation of the numerical properties and performance of the algorithms. Performance metrics being considered include probability of error in the restored sequence as a function of SNR, sensitivity to signal statistics and data conditioning, rate of convergence, choice of sliding windows, and finite length effects. Applications of the new algorithms are being considered in digital communications, speech, image processing and geophysics.

University of Colorado; Delores M Etter; Adaptive IIR Filtering Using a Stochastic Filter; (MIP-9106126 A003); $8,000; 12 months; (Joint support with the CDA Special Projects Program - Total Grant $16,000).

A stochastic filter consists of a bank of fixed filters with a set of corresponding probabilities. The fixed filters from a basis set of filters for the stochastic filter, and the probabilities determine the specific realization represented by the stochastic filter. This research is investigating the use of a stochastic filter to adaptively model an Infinite Impulse Response (IIR) system. Guidelines for selecting the basic set of filters are being developed in order to represent an adaptive IIR filter and to meet both accuracy and convergence speed constraints.

Georgia Institute of Technology; Petros Maragos; Nonlinear Systems for Speech Signal Processing; (MIP-9396301 A002); $58,632; 12 months.

This research focuses on the development of nonlinear signal processing systems and algorithms that can model or extract information about two types of nonlinear and time-varying phenomena in speech production: modulations and turbulence. A new model is being examined for short-time speech resonances that combines both amplitude and frequency modulation. Preliminary experimental findings are consistent with this model. Fractal models for describing the geometric fragmentation of the speech signals are being used to quantify the degree of speech turbulence. A nonlinear filtering algorithm to measure the short-time fractal dimension of speech signals is also being examined.

Purdue University; Michael D Zoltowski; Closed-Form Angle Estimation with Circular Arrays/Apertures for Mobile/Cellular Communications and Surveillance Radar; (MIP-9320890); $113,020; 36 months.

The digital communications industry is currently investing a plethora of resources towards the development and experimental verification of prototype antenna arrays to be deployed on mobile communication vehicles, including the commercial automobile of the future, as a means of discriminating amongst signals co-located in frequency based on their respective spatial locations. Given the small aperture on a mobile communications unit, the uniform circular array (UCA) geometry is ideal due to its rotational invariance with respect to azimuth. This research is based on a recent breakthrough by the principal investigator: the development of a simple, closed form algorithm for use in conjunction with a UCA that provides automatically paired source azimuth and elevation angle estimates. In contrast, the algorithms for 2D arrival-angle estimation to date have required expensive spectral searches, iterative solutions to multidimensional optimization problems, or ad-hoc schemes for pairing direction cosine estimates with respect to each of a number of different array axes.

The new algorithm, UCA-ESPRIT, is fundamentally different from ESPRIT in that it is not based on a displacement invariance array structure but rather is based on phase mode excitation and hinges on a recursive relationship between Bessel functions. A theoretical performance analysis of UCA-ESPRIT is being conducted. This will prove extremely useful for predicting its performance in a mobile communications environment. Novel strategies for incorporating mutual coupling effects are being developed as well. The real world performance of UCA-ESPRIT will be assessed with experimental data from a prototype circular antenna array currently being built at the Polytechnic University of Madrid for mobile sea communications with the INMARSAT satellite system. Adaptations of UCA-ESPRIT for filled circular arrays are also being developed.

Northeastern University; John G Proakis; Adaptive Signal Processing Algorithms Based on Nonlinear Performance Criteria; (MIP-9115526 A002); $57,996; 12 months.

This is a collaborative research project with Chrysostomos L. Nikias (University of Southern California). The research focuses on the development, testing and mathematical analysis of adaptive signal processing algorithms based on nonlinear performance criteria. Areas of research include:

1.	blind deconvolution algorithms based on criteria with memory nonlinearity;

2.	decision feedback equalizers using higher-order statistics;

3.	joint estimation and detection algorithms of the ML-type and MAP-type when the signals are Gaussian distributed;

4.	adaptive multichannel signal recovery algorithms when the signals have gone through severe magnitude and phase distortion; and,

5.	blind deconvolution algorithms based on neural networks and Volterra filters.

Special emphasis is placed on the investigation of the numerical properties and performance of the algorithms. Performance metrics being considered include probability of error in the restored sequence as a function of SNR, sensitivity to signal statistics and data conditioning, rate of convergence, choice of sliding windows, and finite length effects. Applications of the new algorithms are being considered in digital communications, speech, image processing and geophysics.

University of Minnesota; Kevin M Buckley; PYI: Digital Signal Processing for Hearing Aids and Source Localization; (MIP-9057071 A003); $62,500; 12 months.

In the general area of Source Localization Estimation (SLE), this research will:

1.	continue SLE algorithm performance evaluation(s);

2.	investigate algorithm improvements based on considerations of analytical performance expressions derived during the course of this research; and,

3.	address the combined issue of robust estimation and high resolution in the presence modeling errors.

In the area of acoustical/biomedical digital signal processing, specifically hearing aids, effort is being directed towards the specification of algorithm constraints and appropriate cost functions, incorporating robustness and real-time testing both in the laboratory and in the field. Adaptive methods are being examined for use in active noise cancellation of undesired nonstationary noise.

University of Minnesota; Mostafa Kaveh; Array Signal Processing: Estimator Design and Experiments; (MIP-9202081 A002, A003); $98,126; 12 months.

This research builds on experience that has been gained during the construction and calibration of a laboratory ultrasound-in-air array, in order to establish a systematic approach for experimentation and theoretical analysis. Optimizing functionals are being developed for a general class of estimators with similar computational burden as the well-known method of MUSIC. These estimators are expected to significantly reduce the threshold signal to noise ratio, for a general calibrated array, over a method such as MUSIC. Analysis techniques are being established within a probabilistic framework for comparing the resolution thresholds of estimators in this class. Detection methods are also being developed in conjunction with experimental measurements that make optimum use of the array calibration data. The new algorithms are being generalized to cases involving wideband signals and signals possessing special characteristics such as cyclostationarity. The ongoing experimental work, which includes the implementation of subspace estimation algorithms on DSP processors, is intended to establish the level of practicality of many proposed methods.

Ohio State University; Peter Clarkson; Robust Parameter Estimation in the Detection of Cardiac Arrhythmias; (MIP-9220769); $71,758; 12 months.

This research is concerned with improving the efficiency and robustness of parameter estimation schemes employed by implantable and portable devices for cardioversion and defibrillation. The goal is to replace the ad-hoc estimation schemes used in present generation devices by robust estimators that produce optimal minimum variance estimates for a wide range of unknown error distributions and which maintain close-to-optimal performance in the presence of parameter fluctuations. These objectives are pursued through estimation schemes that are based on the application of order statistic operations to the data.

Carnegie-Mellon University; Virginia L Stonick; PYI: Practical Approaches to Optimal Adaptive Filtering of Real Time Non-Linear Systems; (MIP-9157221 A006); $62,500; 12 months.

This research addresses the use of numerical optimization methods to develop real-time adaptive filters for estimating, identifying, or predicting time-varying and potentially nonlinear processes. The first phase of this work is devoted to the development, analysis, and simulation of an optimal adaptive Infinite-Impulse Response (IIA) filtering algorithm for telecommunications using homotopy continuation methods to perform the necessary nonlinear optimization. This research will increase our understanding of IIA filter structures in time- varying environments, and will ultimately lead to their more widespread use.

University of Pennsylvania; Saleem A Kassam; Arrays for High Resolution Imaging and Efficient Digital Filtering; (MIP-9321856); $86,147; 12 months.

Many imaging systems use arrays of individual elements to sense the propagating field produced by an object. Through signal processing techniques such as beamforming, an image of the object may then be formed. In addition to such passive arrays, imaging systems may use active arrays to both illuminate an object with a radiated field and to record the reflected field. Examples of imaging array systems occur in radio astronomy, sonar, microwave imaging and ultrasound imaging.

This research is aimed at developing fundamental new results for array design and associated signal processing, based on recent developments on the characterization of array performance in linear imaging. Active imaging systems (e.g., ultrasound imaging arrays) are a particular focus of this investigation, although some of the proposed work also addresses passive arrays. Using the idea of the "coarray," this work is studying how to deploy array elements (and associated hardware) in the most efficient way to obtain large array apertures and high resolutions. The results will allow minimum redundancy active arrays and minimum complexity active arrays to be specified. This research on arrays includes a study of their characteristics under real operating conditions, and will extend to some experimental work with an acoustic array system.

William Marsh Rice University; C. Sidney Burrus; Iterative Reweighted Least Squares Design of Digital Filters; (MIP-9316588); $251,108; 36 months.

This research is developing a new and significantly better method for the design of a wide variety of digital filters. The new method is based on a successive approximation algorithm called Iteratively Reweighted Least Squares (IRLS). Initial results with the new method using a second order IRLS with a form of path-following or homotopy modification have produced a robust, quadratically converging, efficient, versatile filter design technique. This method is being applied to three filter design problems:

1.	the constrained least-squares and, more generally, the constrained L p approximation problem;

2.	complex approximation problems in (equalization) adaptive filter design; and,

3.	multidimensional filter design and image processing problems.

Robust convergence is crucial for the practical success of any iterative algorithm. This research is doing a theoretical analysis of the convergence for the more general optimization criteria, developing a practical adaptive filter design program, and presenting it in a form accessible to the practicing engineer.

University of Wisconsin; Barry D Van Veen; PYI: Detection and Estimation in Low Dimensional Subspaces; (MIP-8958559 A005); $37,500; 12 months.

This research involves the development and evaluation of efficient, high performance signal processing algorithms for signal estimation and detection. Algorithms for processing data collected at arrays of sensors and for analysis of time series are of particular interest. One technique for reducing the complexity and improving the performance of signal processing algorithms is based on mapping data into subspaces prior to processing. Mapping of data into subspaces is appropriate for almost all signal processing problems, and is especially applicable, if not mandatory, to problems in which large quantities of data must be processed. A key issue under study is the design of linear transformations which maximize performance while minimizing subspace dimension. Processing of data mapped into subspaces is being explored in adaptive beamforming, adaptive filtering, spectrum estimation, and source location estimation problems, as well as in more general nonlinear signal processing algorithms. Determination of appropriate performance criteria for transformation design and tradeoffs between performance and complexity are under investigation. Statistical analysis and simulation are being utilized to analyze the performance of the resulting algorithms.

Multidimensional Digital Signal Processing

University of California - Berkeley; Martin Vetterli; Adaptive Signal Decompositions with Applications in Compression; (MIP-9321302); $126,131; 24 months.

This research explores adaptive methods for high performance, lossy signal compression, and in particular, focuses on a variety of methods that rely on signal expansions. Among these are:

1.	signal adaptive expansions that include quantization and entropy coding. These are generalizations of transform or subband/wavelet and wavelet packet schemes. In particular, adaptive wavelet packets are being studied, both from the point of a view of constructing bases and that of finding good and efficient algorithms to find the best bases.

2.	Overcomplete expansions or frames. The focus is on quantization performance and computational complexity.

3.	The class of compression algorithms that use successive approximation. A rate-distortion version of matching pursuit is being developed; generalizations of hierarchical methods based on wavelets and wavelet packets are being investigated.

4.	Adaptive schemes for compression, including adaptive transforms and quantization.

Goals include a lossy equivalent of arithmetic coding, and a lossy dictionary based predictive compression scheme that resembles a lossy Lempel-Ziv algorithm.

University of Florida; Jian Li; NYI: SAR Image Formation and Processing Techniques for Environmental Monitoring; (MIP-9457388); $12,500; 12 months; (Joint support with the CDA Special Projects Program - Total Grant $25,000).

The research exploits the advantages of using Synthetic Aperture Radar (SAR) to detect, analyze, and quantify environmental changes. The first research thrust focuses on improving SAR image formation with a phased array airborne or spaceborne radar. Efficient SAR image formation techniques are being developed by appropriately designing the transmitted waveforms of the phased array radar. The trade-offs between nonparametric and parametric techniques are being studied and understood. The second research thrust focuses on the SAR image understanding and ground truth evaluation. Statistical clustering algorithms and various feature extraction schemes that adequately incorporate electromagnetic phenomenology are being developed and evaluated. The third research thrust focuses on the detection, analysis, and quantification of environmental changes through repeated SAR imaging of critical regions including the environmentally fragile Florida wetlands. Change detection techniques are being developed to quantify and document subtle environmental changes from these images.

Georgia Institute of Technology; Ronald W Schafer, S. J. McGrath, Mark A. Clements, James H. McClellan, Thomas P. Barnwell; Infrastructure and Research Program for Signal Processing in Multimedia Systems; (MIP-9205853 A003); $166,497; 12 months; (Joint support with the CISE Institutional Infrastructure - Total Grant $365,193).

The objective of this research is to establish an infrastructure for signal processing in multimedia systems. Equipment is being acquired, installed, and integrated into an existing research environment consisting of networked UNIX workstations and minicomputers. This equipment will provide the capabilities to acquire multimedia signals, including image, video, speech, audio, text, and fax; store and access these signals on high-speed, high-capacity disk storage subsystems; process them using custom high- speed, real-time, DSP microcomputer-based processors, hosted by UNIX workstations; communicate a variety of these signals between workstations over a high-speed fiber network; and output the processed signals at their intended destinations. Special-purpose systems - an HDTV workstation, and a custom DSP multiprocessor - will be integrated into the infrastructure to allow for real-time processing of high-resolution video sequences and images. The goal of this infrastructure is to build an environment in which the DSP algorithms, which will play a major role in the growth of multimedia technology, may be developed in such a fashion as to lead directly to real-time implementations of those algorithms. The companion part to this infrastructure is a program of research based on this environment, being conducted in areas with immediate and urgent application to the problems facing multimedia information systems. This includes real-time video encoding, concentrating on the problems of inter and intra-frame redundancy elimination. Advances in this area will lead to affordable applications in a host of areas such as video mail, video messaging, real-time video communications, and interactive learning and presentations.

Georgia Institute of Technology; Mark J Smith; Dynamic Multirate Systems for Image and Video Compression; (MIP-9116113 A002); $55,726; 12 months.

This research addresses the general problem of coding images and video signals at low bit rates using a multirate analysis/synthesis filter bank (or subband coding) framework. Thus far, analysis/synthesis filter banks for subband image/video coding have been static with respect to the input. This research explores new classes of multirate filter banks that:

1.	dynamically change with the input signal to enable higher quality representations; and,

2.	simultaneously preserve all of the aliasing cancellation and high quality reconstruction properties achievable with conventional filter banks.

New methods for quantization and coding based on image modeling and vector quantization are also being studied. These are intended to operate in synchrony with the adaptive multirate filter banks. While this work focuses primarily on achieving high quality compression at low bit rates, extensions of these concepts to higher rates are also being considered.

Illinois Institute of Technology; Nikolas P Galatsanos; RIA: Wavelet Based Multi-Channel Subband Image Restoration; (MIP-9309910 A001); $6,610.

The research is exploring a novel, multi-channel approach to the image restoration problem that utilizes a wavelet-based subband decomposition. Such a decomposition facilitates the incorporation of localized space-variant statistics and prior knowledge into the restoration process as well as adaptive noise suppression at various resolution levels. Furthermore, it can be implemented in a practical and computationally efficient manner. In order to fully exploit the potential advantages of this approach, three classes of multi-channel restoration algorithms are being considered:

1.	stochastic restoration algorithms where the multi-channel statistics of the wavelet-based subbands are used to model the space-varying nature of the original image;

2.	deterministic algorithms where multi-channel regularization operators and parameters are used; and,

3.	hierarchical image restoration where the image is progressively restored starting from its coarse features and continuing to the finer ones.

Northwestern University; Aggelos K Katsaggelos; Database for Image Processing Research; (MIP-9322726); $25,180; 24 months.

This grant provides partial support for an IEEE-sponsored database comprised of sampled images and image sequences that has been established at the National Center for Supercomputing Applications (NCSA) in Urbana, Illinois, with the Signal Processing Society serving as a gatekeeper. This database is accessible via the InterNet at no charge to the users. Data is being solicited from university, industrial and military sources. The data will provide a needed testbed for evaluation of image processing algorithms.

University of Illinois; Yoram Bresler; PYI: Statistical Techniques in Inverse Problems; (MIP-9157377 A002); $62,500; 12 months.

This research falls into four broad areas: image reconstruction, reconstruction of time-varying distributions, sensor array processing, and visualization of multiparameter data. In the area of image processing, the principal objective is to develop the theory and associated computational algorithms for superresolution image reconstruction from partial and noisy data, using statistical models. For the second area, the goal is to develop optimum signal acquisition schemes subject to physical or economic constraints, and the associated efficient reconstruction algorithms for imaging spatial data that is time varying during the acquisition process. In the area of sensor area processing, several issues are being addressed including the design of computationally efficient algorithms for the (sub)optimal solutions of model fitting problems, wideband source location, and imaging with sensor arrays. Finally, in the last area, the goal is to address the effective fusion, display, and visualization of multi-parameter spatially-related data, such as is acquired in multispectral, or multi-modality remote sensing and diagnostic imaging.

University of Illinois; Zhi-Pei Liang; RIA: Efficient Dynamic Magnetic Resonance Imaging with A Priori Constraints; (MIP-9410463); $100,000; 36 months.

As functional MRI provides a new way to study human brain functions, it becomes increasingly important to improve the temporal resolution of the experiments so that rapid transient neuronal events can be captured. In conventional Fourier transform-based imaging methods, each of the dynamic images is acquired independently so that the temporal resolution possible is limited by the number of data points collected in Fourier space to achieve a certain level of spatial resolution. This research seeks to overcome this problem by incorporating a priori information into the imaging process. Specifically, new optimal methods for data acquisition and image reconstruction are being developed that exploit both the underlying model for the signal as well as the available a priori information about both the object being imaged and the dynamic changes. These methods promise to give more than an order of magnitude of improvement in imaging efficiency over the traditional Fourier imaging methods, and should find application in a variety of dynamic imaging problems, particularly in real-time imaging of functional brain activities.

University of Illinois; Michael T Orchard; NYI: Optimal Motion Compensation for Video Compression; (MIP-9357823 A001); $62,500; 12 months.

Efficient compression of video sequences should exploit the high interframe redundancy due to the smoothness of motion fields in typical scenes. Current video coding algorithms use very simplistic motion models, limiting the degree to which motion- induced redundancy can be exploited in video coding. This research is investigating improved methods for estimating motion in video sequences, and compensating for that motion to achieve increased coding efficiency. Methods are being considered which estimate motion at the encoder, requiring transmission of motion overhead, and as well as those which estimate motion directly at the decoder. The goal is to provide a unified framework for these two approaches to motion estimation, and to develop hybrid algorithms taking advantage of the best features of both approaches.

University of Illinois; Kannan Ramchandran; RIA: Hierarchical Decompositions for Adaptive Image and Video Compression; (MIP-9409587); $100,000; 36 months.

This research is investigating a new and innovative class of adaptive and hierarchical methods in image and video compression. It has two primary objectives:

1.	to develop a powerful and flexible infrastructure for addressing new and challenging image communication applications, targeted at overcoming the drawbacks of current state-of-the-art methods; and,

2.	based on this, to formulate novel, optimal, fast algorithms using joint optimization methods.

A novel compression framework based on wavelets and efficient, flexible signal descriptions using adaptive wavelet packets and adaptive quantization is being explored. This research is also studying motion compensation in a new hierarchical estimation-theoretic framework, and is formalizing the fundamental subject of optimal resource allocation in a dependent coding environment. Joint optimization of the source-coder functional components is being considered throughout, and is being extended to include the channel for transmission applications.

University of Notre Dame; Ken D Sauer; Model Based Tomography: A Comprehensive Approach to Iterative Image Reconstruction; (MIP-9300560); $97,094; 12 months.

Low dosage transmission medical imaging, emission medical imaging, and nondestructive testing of materials are all examples of tomographic reconstruction problems which can benefit greatly from improved reconstruction techniques. This research introduces a strategy for the development of computationally efficient reconstruction algorithms which directly search for the statistically optimal fit to measured data. This approach exploits the wide availability of digital computation and storage to substantially improve reconstruction in demanding applications. The research has three essential components:

1.	a general measurement system model which characterizes the physical measurement apparatus for both the transmission and emission problems, which can be extended to include nonlinear effects such as scattering;

2.	a new class of computationally tractable image cross section models which preserves image detail while suppressing noise artifacts; and,

3)	a fast numerical algorithm, known as Gauss-Seidel, which is being used as a basis for efficient and accurate multiscale reconstruction methods.

Algorithmic techniques are being evaluated using data collected from the Nondestructive Evaluation Section at the Lawrence Livermore National Laboratories.

Johns Hopkins University; Jerry L Prince; PFF: Three-Dimensional Image Processing; (MIP-9350336); $100,000; 12 months.

This program has two major components: research and teaching in image processing, both having a focus on three-dimensional data. The research component is divided into two major thrusts:

1.	the development of new methods for estimating motion in three dimensions from three-dimensional data sets. The first aim involves optimizing data acquisition methods given a prior stochastic description of the motion and assuming the use of a certain optical flow method. The second aim explores the theory of three-dimensional vector tomography and its implementation using a magnetic resonance scanner.

2.	The estimation of shape from three- dimensional data sets. This topic focuses on active surface methods: the definition of new active surfaces, the algorithms and their convergence properties, and the use of active surface methods for 3-D image registration.

The teaching component of this grant has two main objectives:

1.	to develop a state-of-the-art signal and image processing laboratory, and,

2.	to develop new courses and textbooks on image reconstruction.

The overall goal is to provide a comprehensive educational program at the cutting edge of signal and image processing.

Harvard University; David Mumford; Mathematical, Computational and Biological Aspects of Vision; (DMS-9121266 A002); $36,500; 12 months; (Joint support with the Robotics and Machine Intelligence Program, the Computational Mathematics Program, and the Databases, Software Development and Computational Biology Program - Total Grant $146,500).

A visual signal, as recorded on the retina of an animal or by a TV camera, differs from many signals analyzed by engineers in that it is produced by a world with many overlapping objects and shadows, and, to "decode" the signal, these must be teased apart so as to reconstruct the world geometry. Most classical techniques smooth over the discontinuities in the signal produced by this multiplicity of effects, making it harder to separate them and reconstruct the world geometry. This research is using new techniques involving variational problems for discontinuous maps to attack some of these problems. It seeks to compare this mathematical approach with the neural techniques by which animals solve the problem. To do this, "neural net" implementations are being studied and experiments formulated to study how close these nets are to the true neural activities in animals. The goal is to understand mathematically one of the most remarkable cognitive abilities of living organisms.

William Marsh Rice University; Richard G Baraniuk; NYI: Signal Analysis and Processing in Matched Coordinate Systems; (MIP-9457438); $25,000; 12 months.

This research aims to extend current methods of time-frequency and time-scale analysis by developing a general theory for signal analysis and processing in alternative coordinate systems. Specific tools under investigation include optimal, signal-dependent time-scale representations, information measures for time-frequency and time-scale analysis, and operator-based, generalized coordinate systems. Test signals are being drawn from problems in machine health monitoring, magnetic resonance imaging, and dispersive signal processing.

Rutgers University; James L Flanagan, Richard Mammone; Sound Capture from Spatial Volumes - Parallel Processing of Three-Dimensional Arrays of Sensors; (MIP-9121541 A002); $94,302; 12 months.

High-quality sound pick up in enclosures, such as meeting rooms and auditoria, is central to effective teleconferencing by large groups separated by distance. The basic goal of this research is the exploration of the potential of using sensors in 3D configurations to achieve spatial volume selectivity, and hence, high quality sound pick up comparable to that enjoyed when the speakers are face-to-face in the same room. Both beamforming and matched field processing are being examined, with detailed computer studies preceding measurements and experiments in real rooms.

Stevens Institute of Technology; Sankar Basu; Multidimensional Nonseparable Subband Coding; (MIP-9322592); $80,588; 24 months.

This research is providing a parameterization of the entire family of multidimensional perfect reconstruction subband coding filter banks. The motivation for doing this lies in practical application of efficient coding and compression of image (video) type signals. The parametric description of the family of multidimensional filter banks so obtained is being used to design perfect reconstruction filter banks having desirable frequency separation properties. The entire family of nonseparable multidimensional smooth wavelets resulting from iterations of these filter banks is also being completely parameterized in this way.

The techniques being adopted essentially consist of those from multidimensional system theory. The biorthogonal problems are being approached by formulating them as matrix extension or matrix completion problems in the ring of multidimensional polynomials or stable proper rational functions; and the paraunitary problems as problems of describing, or equivalently, synthesizing multidimensional lossless systems. Similar strategies are being used in the acausal formulation as well as in dealing with special classes of solutions such as the linear phase solutions.

Stevens Institute of Technology; Alan L Stewart, Roger S Pinkham; Self-Adjoint Operators and Models of Space-Variant Visual Acuity; (MIP-9405081); $82,514; 12 months.

Current theories of visual processing are theories of local responses. Even models of space-variant acuity concentrate on properties of the local receptive fields, with the rationalization that the visual system is approximately homogeneous within any small neighborhood. The response of the entire visual field is pieced together from models of local responses.

The theory of integral operators allows the experimental study of human acuity to be united with computational model is visual processing. This mathematical tool is being applied in this context to provide simpler and more intuitive proofs of key theorems which relate threshold assessment to eigenvalue problems. At the same time, everyday experimental concepts, such as threshold sensitivity, take on new elegance when placed within the theory of integral operators.

University of Rochester; A. Murat Tekalp, Warren E Smith; Modeling and Suppression of Motion Artifacts in Magnetic Resonance Imaging; (MIP-9119443 A003, A004); $154,281; 12 months.

Artifacts due to involuntary patient motion have been a major source of image degradation in 2-D and 3-D Fourier Magnetic Resonance Imaging (MRI) for many years. These artifacts, often called "ghosts," manifest themselves as a series of repeated and blurred versions of some features in the patient. Most of the contemporary methods which account for motion effects require additional hardware or instrumentation to monitor the patient motion. This research is examining novel signal/image processing methods for the detection and correction of motion artifacts in MRI by means of postprocessing of the motion-corrupted raw MR data. The research entails modeling (mathematically) the data acquisition process in the presence of arbitrary patient motion, the development of signal/image enhancement algorithms based on the resulting model, and their verification with controlled MRI experiments as well as clinical MRI data. A major advantage of the proposed methods is that they can be implemented in software and do not require any additional hardware installation to existing systems.

Brown University; Stuart A Geman, Donald E McClure, Basilis Gidas, Ulf Grenander; Mathematical Sciences: Mathematical and Computational Problems in Object Recognition; (DMS-9217655 A001); $20,000; 12 months; (Joint support with the Robotics and Machine Intelligence Program, the Computational Mathematics Program, the Statistics Program, and the Probability Program- Total Grant $170,000).

The research program focuses on mathematical aspects of object recognition. There are two classes of problems. The first is the recognition of rigid objects positioned in a scene at arbitrary rotations, locations, and scales. A large repertoire of shapes is assumed known in advance, and the problem is to then devise computationally efficient algorithms for recognizing which, if any, of these objects are present in a given scene. Sequential and adaptive strategies are being explored, in which a sequence of image-based observations is made, with the choice of an observation depending upon the results of previous observations. There are close connections to coding theory, sequential design of experiments, multi-armed bandit problems, the game of "twenty questions," and, of course, previous work in machine vision.

The second class of problems is the recognition of nonrigid, or deformable, objects. Examples include handwritten numerals and various biological shapes, such as leaves, hands, organelles, etc. Here the issue of shape modeling appears to be central. An approach through deformable templates is being studied. Templates are prototypes which capture global characteristics, whereas deformations are random transformations, satisfying certain regularity constraints, that act upon templates to produce the possible presentations of an object. The new shape models suggest certain recognition algorithms, and these will be explored in a variety of application areas.

Washington State University; Thomas R Fischer, Roberto H Bamberger; Analysis and Design of Multidimensional Filter Banks with Application to Image Coding; (MIP-9116683 A004, A005); $121,281; 12 months.

The basic goal of this research is to develop general analysis and design methods for multidimensional filter bank signal decompositions, featuring non-rectangular spectral partitions, and to integrate such methods with novel source coding techniques to produce a family of effective and efficient image and video coders. The work focuses on the following four tasks:

1.	design exact/near-exact reconstruction multidimensional multirate filter banks for a variety of non-rectangular spectral partitions;	2.	develop a theory for the subband coding gain and coder performance of multidimensional multirate filter bank source coders, emphasizing the filter banks developed in 1;

3.	develop a theory for the influence of perceptual weighting functions in subband coding systems; and,

4.	determine a theory for the performance of linear prediction in a multirate filter bank signal decomposition, with emphasis on the source coding application. Fixed, forward adaptive, and backward adaptive prediction are being considered.

Digital Representation

Stanford University; Robert M Gray, Richard A Olshen; Tree-structured Image Compression and Classification; (MIP-9311190 A001, A002); $119,606; 12 months; (Joint support with the Communications Research - Total Grant $123,914).

Tree-structured vector quantization is an approach to image compression that applies ideas from statistical clustering algorithms and tree-structured classification and regression algorithms to produce compression codes that trade off bit rate and average distortion in a near optimal fashion. This research is examining the explicit combination of these two forms of signal processing, compression and classification, into single tree-structured algorithms that permit a trade off between traditional distortion measures, such as squared error, with measures of classification accuracy such as Bayes risk. The intent is to produce codes with implicit classification information, that is, for which the stored or communicated compressed image incorporates classification information without further signal processing. Such systems can provide direct low level classification or provide an efficient front end to more sophisticated full-frame recognition algorithms.

Vector quanitization algorithms for relatively large block sizes are also being developed with an emphasis on multiresolution compression algorithms. In order to improve the promising performance found in preliminary studies or combined compression and classification, it will be necessary to use larger block sizes or, equivalently, more context. Multiresolution or hierarchial quantizers provide a simple and effective means of accomplishing this. Other related issues are being explored, including improved prediction methods for predictive vector quantization and image sequence coding.

University of California - Berkeley; Avideh Zakhor; PYI: Signal Interpretation and Representation Using Neural Architectures; (MIP-9057466 A004); $62,500; 12 months.

This research incorporates signal and image representation, synthesis and restoration, and issues related to the applicability of multiresolution decompositions to various classes of signals and signal processing algorithms. These include fractal-type signals to which traditional wavelet analysis applies, and those which are best represented by different filters at different resolutions. For the latter class of signals, an adaptive subband coding algorithm is being developed that affects the multiresolution decompositions.

University of Maryland; Nariman Farvardin; A Novel Structured Vector Quantization Scheme: Design, Analysis and Applications; (MIP-9109109 A002); $52,361; 12 months.

The basic idea of this research is to develop a class of suboptimal vector quantizers in which the codebook is derived, in a simple manner from another highly structured codebook, therefore, eliminating the need to store the codebook and hence allowing the design of very large codebooks. For memoryless sources, the codebook of the Structured Vector Quantization (SVQ) is selected as a well-defined subset of the Cartesian product of the codebook of a specific entropy-coded scalar quantizer. Since the SVQ codebook is a part of a highly structured codebook, the memory requirements, the complexity, and the needed training data are reduced significantly, hence, allowing the possibility of designing SVQs with large codebooks. The research plan entails the design, analysis and simulation of SVQs, along with a meaningful comparison of their merits with respect to other known quantization schemes. Based on the results of this research, the application and performance of SVQs in more practical situations representative of real-world problems will be studied.

Oregon State University; Richard Schreier; RIA: Fundamentals of Delta-Sigma Modulation; (MIP-9210935 A002); $5,000.

Delta-sigma modulation forms the foundation for the highly linear and manufacturable analog-to-digital and digital-to-analog converters known as "oversampled noise-shaping" converters. These circuits find application in narrow band systems such as digital audio equipment and medical and geophysical instrumentation. At present, there are no adequate tests for stability of these nonlinear systems - designers can only use extensive computer simulations and hope that the simulations exercise the circuit adequately. This research is developing a quick and completely rigorous method which combines analytical techniques with numerical algorithms to prove the robust stability of a delta-sigma modulator. The idle-channel noise of delta-sigma modulators is a second research topic. How to guarantee aperiodic behavior in delta-sigma modulators is being shown, but this alone is not sufficient to guarantee an absence of tones. Listening experiments using data derived from simulations need to be performed in order to judge the effectiveness of the technique. The results of these investigations are being incorporated into a computer program for the automated design of delta-sigma modulators.

University of Washington; Eve A Riskin; NYI: Vector Quantization Codebook Processing and Organization; (MIP-9257587 A002); $62,500; 12 months.

New ways to use Vector Quantization (VQ) other than strictly for data compression are being investigated, and are being applied to applications such as image processing, halftoning, progressive transmission, and immunity against communication channel noise. In many applications, both VQ and

many image processing operations are applied to small subblocks of an image. The image processing step can be applied ahead of time to each vector in a VQ codebook, with the processed vectors stored along with the codebook. If the computational complexity of the VQ encoder is lower than that of the image processing step, this reduces the computational complexity. This approach is being applied to halftoning, edge detection, and histogram equalization.

In a progressive transmission system, the received image is reconstructed as an increasingly better reproduction of the transmitted image as bits arrive. Ways to organize and order a VQ codebook so that it can be used for direct progressive transmission of full search VQ are being studied. In an ordered VQ, the VQ codeword index is correlated with the codeword location in the input space. This ordinal mapping feature of clustering codewords with similar indexes to obtain additional reproduction vectors for the decoder is being exploited. Extentions to progressive transmission of ordered VQ indexes over noisy communication channels are being included.

Implementation

University of California - Berkeley; Edward A Lee; Design Methodology for Signal Processing; (MIP-9201605 A002); $51,379; 12 months; (Joint support with the Computer Systems Architecture - Total Grant $81,379).

This research deals with design methodology for heterogeneous implementations of signal processing systems. Some signal processing algorithms consist of highly repetitive, predictable computations on streams of samples with hard real-time constraints, and are amenable to synchronous dataflow representations and static (compile-time) scheduling. Other algorithms involve some decision making or run-time control flow, and can be accommodated efficiently by a broader dataflow model that includes run-time flow control. When such algorithms are combined into complete systems, more dynamics must be supported, and discrete-event principles, or real-time operating systems must be included. This research is looking at ways to combine diverse semantics, and is pursuing co-simulation techniques and understanding of the interaction between what formal methods are available within each model of computation. A design framework (called Ptolemy) that supports all these models, individually or in combination, is being developed as a testbed.

University of California - Berkeley; Jan Rabaey; PYI: Architectures and Synthesis for Digital Signal Processing; (MIP-8958578 A006); $37,500.

Research efforts are focused on the development of the HYPER high level synthesis environment. In order to obtain a complete and more functional environment, extensions and improvements are being developed that provide more accurate cost and performance predictions, transform (recursive) structures into alternate forms which achieve maximally fast performance (amongst others), and incorporate an optimization environment for background memory and input/output interfaces.

University of Maryland; K. J. Ray Liu; RIA: Novel Approaches for Numerical Signal Processing: Algorithms and Architectures; (MIP-9309506 A001); $10,000.

The objective of this research is to develop efficient signal processing algorithms and architectures based on a new numerical matrix decomposition called the URV decomposition. The major advantage of the URV decomposition is that it provides as much information as the singular value decomposition but with much less computational complexity. Using this new numerical tool, signal processing algorithms that currently employ either the singular value or QR decompositions can be reformulated, leading to more efficient and robust implementations. Analysis and development of efficient URV-based signal processing algorithms are being conducted with applications to adaptive array processing, reduced rank signal processing, signal compression, multi-dimensional filter design, and image processing. VLSI architectures and parallel processor implementations will also be considered for high-performance signal processing using the URV decomposition.

University of Maryland; K. J. Ray Liu; NYI: High Performance Computing for Signal Processing; (MIP-9457397); $12,500; 12 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $25,000).

There are three major architectural models used in high-performance signal/image processing:

1.	VLSI-signal processing - high-throughput VLSI architectures for low-cost application-specific implementations used in applications such as communication systems, speech, video/HDTV, and radar;

2.	parallel signal processing on massively parallel computers - parallel algorithms for complex signal/imaging systems used in computer vision, medical imaging, and the processing of vast amounts of data in deep space exploration; and

3.	distributed signal processing on high-speed networks - used in applications such as document image processing, multimedia, automatic signal processing in manufacturing, and medical signal/image processing.

This research will focus on the development of efficient algorithms and architectures for each architectural model, and in comparative studies of the advantages and disadvantages of these different computing schemes. The goal is to investigate which signal/image processing problems can be carried out optimally under different computing and communication schemes.

Harvard University; Woodward Yang; NYI: VLSI Design for High Performance Signal Processing and Computation; (MIP-9257964 A001); $62,500; 12 months.

The focus of this research is on the development of innovative VLSI design methodologies that will facilitate the next generation of high performance signal processing and computing systems. A variety of analog, digital, and mixed signal circuitry will be implemented for use in high performance computing applications including object recognition, smart sensors, adaptive neural networks, and programmable analog filters.

University of Minnesota; Keshab K Parhi; NYI: Dedicated VLSI Digital Signal and Image Processors; (MIP-9258670 A002); $52,500; 12 months.

Research efforts are directed towards the design of dedicated, high-performance digital signal and image processors. The emphasis is on real-time processing, where samples are processed as they are received from the source, as opposed to being stored in buffers and then processed in batch. Design of algorithm topologies for recursive signal processing algorithms were once considered a major challenge. Using the relaxed look-ahead technique, new concurrent algorithms and topologies for adaptive LMS and lattice filters, cascade and lattice recursive digital filters, and predictive speech and image coders have been developed. Design of concurrent topologies for wave digital filters, decision-feedback equalizers, and adaptive differential vector quantizers are being pursued. The decoding speed in Huffman and arithmetic coders (used for lossless compression) is limited due to the feedback. For the Huffman decoder, the codeword length multiplicity constraint is being exploited to design codes where multiple bits can be simultaneously decoded in parallel. The performance of these decoders is further improved by the use of conditional coding. Novel approaches for design of parallel arithmetic coders are also being pursued.

Brown University; Harvey F Silverman; Parallel Architectures for Speech Recognition: Testing Expensive Algorithms in a Reconfigurable Environment; (MIP-9120843 A004); $51,333; 12 months; (Joint support with the Microelectronic Systems Architecture Program - Total Grant $102,666).

A research program in the areas of computing architectures for advanced speech recognition, algorithms, and experimentation is currently in place in the Laboratory for Engineering Man/machine Systems (LEMS) at Brown. This research focuses on a reconfigurable, general-purpose, computing structure, and speech recognition/training algorithms, to advance the state-of-the-art in both areas through their interaction. One feature of these efforts is the evaluation of the effects of changes to the early stages of a speech recognizer. This computationally intensive task will utilize the projected Armstrong III reconfigurable hardware system to accelerate the current training algorithm. A second feature is the incorporation of improvements to the current computational and recognition performance of a talker-independent, connected alphadigit recognizer, database, training, and tools, all developed at Brown. These include microphone-array data acquisition, new signal-processing algorithms, non-parametric modeling, better durational modeling, and new VQ/feature-space methods.

Brown University; Harvey F Silverman; A Large-Scale, Intelligent Three-Dimensional Microphone-Array Sound-Capture System; (MIP-9314625 A001); $15,000; 12 months; (Joint support with the Experimental Systems Program - Total Grant $339,324).

This is a joint project between Brown and Rutgers to build a large microphone array with associated processors for beam forming. Applications are direction finding, echo cancellation, and speaker differentiation in telconference systems, multimedia educational systems, and large conference centers. Groups of microphones share microphone modules that perform analog-to-digital conversion and low-level processing. The microphone modules are linked over a high speed serial network (possibly optical) to a multiprocessors signal processing system for the higher level processing. The resulting system is being evaluated in an experimental teleconferencing facility.

Miscellaneous

University of California - San Diego; Michael J Bailey, Ramesh C Jain; Making Rapid Prototyping Viable for Remote Use on the National Information Infrastructure; (MIP-9420099); $166,510; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, the Experimental Systems Program, the Microelectronic Systems Architecture Program, the Design, Tools and Test Program, and the Communications Research Program - Total Grant $706,290).

This project is working to make rapid prototyping and reverse engineering facilities available over wide-area computer networks. It includes several research thrusts along with an integration effort to ensure that the facilities will be usable remotely with little on-site intervention. The project has four major thrusts:

1.	development of algorithms for checking consistency of geometric descriptions;

2.	development of new languages based on constructive solid geometry for communicating geometric descriptions;

3.	connection of rapid prototyping equipment to a wide rear network, with device drivers and server software to allow remote access;

4.	connection of a 3D scanner to the network for remote access.

University of California - Santa Barbara; Ali H Sayed; RIA: Coupled State-Space Filtering with Applications; (MIP-9409319); $100,000; 36 months.

The purpose of this research is to develop modular and parallelizable algorithms for problems in adaptive filtering, robust estimation, control, and structured matrix computations. A major motivation for this work is the need to properly identify, model, and exploit convenient structures that might exist in a particular problem in order to develop a computationally effective solution. An intrinsic and relevant part of the proposed work is to first identify common ingredients, as well as to explicitly clarify, the interrelations and interplays that exist among several problems in the disciplines of control, signal processing, and mathematics.

In this regard, the proposed research develops a unifying point of view that simultaneously addresses a variety of seemingly unrelated problems in estimation, control, adaptive filtering, and matrix computations. It shows that the solutions to many applications in these areas turn out to share a key and surprisingly simple ingredient, namely, that of computing the triangular factors of matrices that exhibit structure. The significance of this particular fact and, more generally, of the proposed research as a whole, is that it enables several well-understood concepts from matrix theory and linear algebra to be applied in order to simplify the derivation of a variety of algorithms, to propose new computationally efficient variants, and to exploit new forms of structure. The proposed research consists of theoretical investigations and algorithm implementations. The techniques developed in this work have applications in several areas including, among others, new windowing schemes for adaptive RLS filtering, analysis of gradient- based algorithms, and modular and square-root algorithms for instrumental variable methods, robust estimation, and control. Equally important is the development of a systematic and unifying methodology.

Massachusetts Institute of Technology; Alan S Willsky; US- France Cooperative Research: Statistical Signal and Image Processing, Failure Detection, System Theory, and System Modeling; (INT-9313898); $10,000; 36 months; (Joint support with the Western Europe Program and the Systems Theory Program - Total Grant $30,250).

This three-year award supports ongoing US-France cooperative research in image and signal processing among investigators from the Massachusetts Institute of Technology, the University of California at Davis, and INRIA/Rocquencourt and Rennes (French National Institute for Research in Computer Science and Applied Mathematics). The U.S. and French teams are led by Alan Willsky, MIT, and Albert Benveniste, INRIA, respectively. The objective of this research is to investigate various problems in geometric modeling, nonlinear systems, and image processing. These include:

1.	multiresolution statistical signal and image processing;

2.	failure and event detection;

3.	new approaches to nonlinear parameter systems; and,

4.	discrete event systems.

The project takes advantage, in particular, of French advances in nonlinear systems modeling and different, but complementary, approaches to problems in discrete event systems. The collaboration will advance understanding on analysis and design of circuits for signal processing applications.

Michigan Technological University; Jeffrey O Coleman; RIA: Convex-Programming Design of Signals and Systems; (MIP-9409686); $50,339; 36 months; (Joint support with the Design, Tools and Test Program - Total Grant $97,114).

This research is creating a special-purpose programming language in which optimization problems can be specified in a natural and direct way. The focus is on developing associated translation software to convert such a specification into a particular canonical form for numerical optimization using recently developed, ultra-efficient, interior-point algorithms. The canonical form is a Linear-Matrix- Inequality (LMI) program, where each constraint takes the form of a requirement that a linear (plus a constant) matrix function of the optimization variables be positive definite.

Control theorists have recently demonstrated that a tremendous variety of common (and uncommon) constraints can be put into this generic form. Often, however, the required LMI constraints are not related to the underlying problem in an intuitive way. Software to translate specifications in a "comfortable language" to sets of LMIs is being developed in order to make these powerful optimization techniques easy to apply. The language is being applied to real problems in communication and signal-processing circuit designs.

University of Minnesota; William K Durfee; Virtual Environments for Rapid Prototyping of Product Interfaces; (MIP-9420394); $30,000; 36 months; (Joint support with the Experimental Systems Program - Total Grant $400,010).

The goal of this research is to apply virtual environment technology to develop product prototyping tools, with a particular emphasis on emulating user interfaces. The approach is to emulate an interface using computer-based visual, aural, and haptic displays. The haptic display will use either playback of prerecorded sound clips or a physically based model of the control. The visual display will use the display monitor of a graphics workstation to show the emulated control in the context of the entire product.

The specific objectives of this project are to: design and construct one or more haptic displays; through modeling and experimentation develop new knowledge for the control of high-performance haptic displays; design and implement high-fidelity aural and visual displays for the virtual environment; and conduct a series of human subject experiments to determine how the three displays interact to determine the level of realism perceived by the user.

Rensselaer Polytechnic Institute; Badrinath Roysam; Real-Time Algorithms for Automatic Vasculature Map Generation and Feature-Based Location Determination From Intra-Ocular Image Sequences; (MIP-9412500); $15,639; 12 months; (Joint support with the Robotics and Machine Intelligence Program, the Bioengineering Program, and the Computational Mathematics Program - Total Grant $49,047).

Laser eye surgery is the most effective known procedure for treating Choroidal NeoVascularization (CNV) found in a variety of conditions including age-related macular degeneration, histoplasmic choroiditis, etc. However, the current rate of success of this procedure is less than 50% for eradication of the CNV following one treatment session, with a recurrence and/or persistence rate of about 50%. This research will make possible an instrument that will drastically reduce this failure rate.

The instrument consists of a computerized multi-spectral 3-D fundus camera with an associated head-up display and a real-time laser tracking system. The tracking system uses a set of automatic image analysis routines that allow accurate mapping of the pathologies, and computerized laser treatment planning.

The core image-processing problems that are being addressed are:

1.	constructing a wide-area map of the retinal vasculature from an image sequence; and,

2.	determining the location of the current frame relative to the wide-area map constructed in step (i) to an accuracy of 2 pixels, or better, at a frame rate of at least 30 per second.

The above problems are being solved by the development of a fast algorithm for matching point sets with unknown correspondences, in the presence of a small number of noise points. This algorithm operates by limiting the search to a minimally- sufficient subset of the most reliable image feature points. In addition, the proposed algorithm is being implemented on a linear array of processors, further enabling real-time operation.

Pennsylvania State University; Stephan V Schell; 1994 Workshop on Cyclostationary Signals; Monterey, CA; August 1-2, 1994; (MIP-9415277); $1,000; 6 months; (Joint support with the Communications Research Program - Total Grant $2,000).

This grant provides partial support for a workshop being conducted solely for the benefit of researchers and practitioners in the signal processing, telecommunication, and mathematical statistics communities. Participation from individuals in academia, industry, and government is being strongly encouraged. This will be the second such workshop on cyclostationary signals, and is being organized by the PI (Stephan V. Schell) and Dr. Chad M. Spooner of Mission Research Corporation. It is organized partially in response to the consensus among attendees of the 1992 workshop that another workshop should be held, and partially in response to continued interest in the theory and applications of cyclostationary signals among researchers and practitioners in academia, industry, and government.

NSF support of this workshop is being used exclusively to encourage recent Ph.D.'s and graduate students working in the field to attend the workshop. This encouragement is being accomplished by providing an offset to the travel expenses incurred by these participants.

Tufts University; Krishnamurthy Soumyanath; A Retraining Program for Defense Industry Engineers in Mixed Signal VLSI Design and Manufacturing; (MIP-9412900); 24 months; (Joint support with the Advanced Research Projects Agency - Total Grant $557,000).

This TRP funded proram is a University/Industry collaborative effort to retrain defense industry engineers in Mixed Signal VLSI (Very Large Scale Integrated Circuits) design and Manufacturing. These integrated circuits are "systems on a chip" that incorporate both the sensitive analog circuitry for pre-processing external, i.e., "real-world" signals and the digital control/processing circuitry on the same semiconductor substrate. This is an important, and rapidly growing (25% annually-projected to reach $11 billion by 1995) dual-use area where the US holds the lead in the world markets. This lead is currently at risk due to the low numbers of highly talented mixed signal designers entering the industry. The availability of highly skilled and experienced Defense technologists, due to defense cutbacks, provides a valuable opportunity to redress this gap.

Partners from the VLSI industry and Defense industry have joined with Tufts in developing this program to retrain the available engineering and scientific talent, which will produce designers with new perspectives for the industry. This will serve to strengthen our country's leadership position in mixed signal VLSI, thus improving economic growth, defense readiness and the availability of relevant educational support. The current list of partners is: Analog Devices, Analogic Corp., Lockheed Sanders, Loral Infrared and Imaging Systems, Ratheon Corporation, Sipex Corporation, and Textron Defense Systems.

University of Texas; Guanghan Xu, Dim-Lee Kwong; Development of Advanced Signal Processing Algorithms for On-Line Temperature Profile Measurement in Semiconductor Manufacturing; (MIP-9400732); $29,230; 12 months; (Joint support with the Systems Prototyping and Fabrications Program - Total Grant $79,230).

This research is directed towards the development, implementation, and demonstration of advanced model-based signal processing algorithms for real-time measurement of wafer temperature profile in Rapid Thermal Processing (RTP). RTP cluster tools are strategically important for submicron semiconductor manufacturing because of trends towards reduced thermal budget and tightened process control requirements on large diameter silicon wafers. Despite its significant advantages, commercial versions of RTP modules for various chemical vapor deposition applications are not available.

Advanced model-based signal processing algorithms are being developed, which when coupled with the acoustic thermometry and acoustic/pyrometer approaches, accurately measure the wafer temperature profile at fast acquisition rates and with a minimum number of sensors. This entails algorithm development, implementation, and validation using real data from commercial RTP tools at UT-Austin and SEMATECH.

University of Wyoming; Robert F Kubichek; RIA: Output-Based Objective Estimation of Speech Quality and Intelligibility; (MIP-9309315 A001); $5,600.

Developing effective automatic, or objective techniques for assessing speech quality to replace human listener scores (i.e., subjective quality) has been the object of much research. Current algorithms base quality estimates on input-to-output

distortion measures. A related, yet almost unexplored problem, is estimation of transmission quality using only received speech without access to the transmitted speech record (Output-Based Quality or OBQ). A second problem is objectively measuring intelligibility using only received speech (Output-Based Intelligibility or OBI). This research addresses both of these difficult problems, and is based on recently developed technologies that utilize models of hearing perception to provide speaker-independent speech recognition. OBQ and OBI estimates are being determined from carefully designed distance measures between Perceptual Linear Prediction (PLP) coefficients of output speech and cluster centroids derived from training data. A PLP analysis system is being implemented. Methods for estimating OBQ and OBI estimates are being developed. Finally, the algorithms are being tested on a variety of speech databases. Statistical analyses will characterize their performance in terms of their correlation with subjective results and robustness to speaker and distortion variation.

Experimental Systems

Dr. Michael J. Foster, Program Director

(703) 306-1936 mfoster@nsf.gov

The Program

The Experimental Systems program supports research projects that involve building, evaluating, and experimenting with a computer or information-processing system. These are goal-oriented projects generally undertaken by teams of designers, builders, and users. The building of the system must itself represent a major intellectual effort, and offer advances in our understanding of information systems architecture. A system supported by the Experimental Systems program will usually include both hardware and software components.

Research on information processing systems involves interaction among diverse elements such as hardware architectures, computational models, compilers, operating systems, applications, performance evaluation tools, and user interfaces. Building and evaluating real experimental systems is the only way to understand these interactions in large systems; other techniques, such as simulation and analysis, have only limited uses in understanding the system issues in such a complex environment. Software simulators, for instance, do not provide the computing speed needed for large experiments, nor the needed performance incentives for porting large application systems for experimentation. Without real experimental systems, important areas of information systems architectures cannot advance.

A successful proposal to the Experimental Systems program should demonstrate the feasibility and utility of the project. Feasibility can be shown by describing prior proof-of-concept prototypes or simulation studies that indicate that the proposed system can be built and will meet its design goals. Utility can be shown by demonstrating that building the system will provide substantial advances in computer system architecture, or that the system is inherently useful. Details of the measurement and evaluation procedures that will demonstrate the benefits of the system in an application should be given in the proposal.

The system to be built must be novel in some way, and the impact of the novel aspects of the system upon its architecture must be evaluated during the course of the research. To justify construction the new system must be potentially superior to existing systems in the chosen application area. Ideally, building the system would provide new knowledge of systems architecture, open up new application areas, and/or contribute to our knowledge about system building techniques. An appropriate project might be a system built using a new architecture or technology, which addresses an application in a new way. An inappropriate project would be one in which the research uses, simply as a platform, a special purpose machine whose design, fabrication, and evaluation are straightforward. The novel aspects of an experimental system may fall into several different areas; the system might feature application of a new technology, new architecture, or new techniques for performance measurement and evaluation to a computationally stressing problem. Examples of technological innovation are massively parallel analog systems, or applications of opto-electronics. Architectural innovations might include new parallel l/O structures, hardware-software codesign, or limited modifications to commodity processors. New evaluation techniques might include instrumentation for performance evaluation or debugging. These innovations might be applied to produce high-performance computers, intelligent sensors, or signal processing architectures, for example. A list of projects currently supported under the Experimental Systems program can be found in the Microelectronic Information Processing Systems Division Summary of Awards.

To justify support under this program, a proposal should show that system building is necessary for answering significant and timely research questions. The research issues should be such that the best way to address them is to build the proposed system and measure its performance. Building for its own sake is discouraged; analysis and simulation should be performed in sufficient detail before a proposal is sent to the Experimental Systems program. Furthermore, off-the-shelf hardware should be employed in the building stage whenever the research goals do not require custom construction.

By encouraging the design, construction, test, and evaluation of novel information processing systems, NSF hopes to achieve several goals:

* Settle major research issues and add to fundamental knowledge in information processing;

* Guide university research in computer science and engineering toward meaningful problems of industrial interest;

* Strengthen the system-building expertise in our research institutions;

* Educate a new generation of researchers in experimental ssytems research.

Potential applicants are encouraged to discuss their research ideas with the program director prior to formal submission.

Initiatives and Opportunities

During the 1994 Fiscal Year, the Experimental Systems program participated in several initiatives. These initiatives were intended to encourage research directions that had been identified as important by the research commumnity and that crossed program lines.

HIGH PERFORMANCE STORAGE SYSTEMS AND WIDE-BAND I/O

This initiative resulted from recommendations developed by the NSF Workshop on High Performance Memory Systems, and by the Information Infrastructure Technology and Applications Task Force. Proposals that addressed problems of accessing large data sets at a high rate over networks were especially encouraged. Topics of interest included the following:

*	The development of new memory systems that take advantage of emerging storage technologies;

*	New techniques for organizing cache memory and other buffering schemes to alleviate memory and network latency;

*	Partitioning of systems to reduce data movement;

*	Reliability and fault-tolerance of new memory systems.

RAPID PROTOTYPING: VIRTUAL AND PHYSICAL

Emerging national needs and recent technological advances point to rapid prototyping as an essential area of research in the strategic area of advanced manufacturing. The goal of research in rapid prototyping is to develop and integrate the tools and technologies needed for rapid and efficient design and manufacturing of products, processes, and systems. The result will be reduced product delivery times to meet dynamic market requirements.

RESEARCH IN NEW GENERATION OPERATING SYSTEMS ARCHITECTURES

To meet the diverse needs of applications on diverse computing platforms, today's operating systems have been growing in size and complexity, incurring more overhead in providing required services. There is a need for a systematic evaluation of the abstractions needed for the design and implementation of operating systems for the current and emerging generations of system architectures and applications.

Several research issues related to this initiative are of interest to the Experimental Systems program. These generally involve architectural support for operating systems on networks of workstations or on collections of supercomputers connected by gigabit networks.

Awards

Graphics and Solid Modelling

University of California - San Diego; Michael J Bailey, Ramesh C Jain; Making Rapid Prototyping Viable for Remote Use on the National Information Infrastructure; (MIP-9420099); $12,312; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, the Circuits and Signal Processing Program, the Microelectronic Systems Architecture Program, the Design, Tools and Test Program, and the Communications Research Program- Total Grant $706,290).

This project is working to make rapid prototyping and reverse engineering facilities available over wide-area computer networks. It includes several research thrusts along with an integration effort to ensure that the facilities will be usable remotely with little on-site intervention. The project has four major thrusts:

1.	development of algorithms for checking consistency of geometric descriptions;

2.	development of new languages based on constructive solid geometry for communicating geometric descriptions;

3.	connection of rapid prototyping equipment to a wide area network, with device drivers and server software to allow remote access;

4.	connection of a 3D scanner to the network for remote access.

Cornell University; Herbert B Voelcker; Research in Solid Modeling: Boundary-to-CSG Conversion; (DMI-9215463 A002); $30,000; 12 months; (Joint support with the Computer Integrated Engineering Program - Total Grant $90,000).

The development of solid modeling as an industrially viable technology was paced by the development, in the 1970's, of theory and algorithms for boolean operations on solids, i.e., for converting constructive (CSG) representations into boundary representations (B-reps). Theory and algorithms for the inverse conversion, from boundary to CSG (called BCSG), were largely unknown prior to the work of Shapiro and Vossler in 1989-91. Their cell-based methods are mathematically sound and have been implemented experimentally, but several important practical issues remain open. This research addresses those issues through the following goals:

1.	development of significantly better algorithms for cell-based BCSG conversion;

2.	development of a publicly available implementation of BCSG, initially for a domain of natural quadric surfaces, that is usable with one or more open architecture (ie. public) B-rep modeling systems; and

3.	development of theory and techniques, using new algebraic-patch and constructive-shell representations, to enable BCSG conversion to accommodate freeform solids.

This research will re-establish CSG as an industrially viable representation for solids, and will enable fully symmetric dual-representation modeling systems to be built which should be considerably more powerful than today's B-rep-only systems.

Cornell University; Herbert B Voelcker; Massively Parallel Computation for Mechanical Manufacturing and Design; (MIP-9317620); $124,784; 12 months; (Joint support with the CISE Instrumentation Program - Total Grant $384,784).

Solid modeling is a critical enabling technology for mechanical CAD/CAM because it provides geometrically complete representations of parts and products, and enables important manufacturing processes to be modeled. Today's industrial systems operate far below the technology's potential because solid modeling requires enormous computing resources, and because current algorithms and representations cannot handle several important applications.

This project is designing new implementations of ray-casting representations for the solid models used in mechanical CAD, and extending the models to new applications. New implementations for ray-casting engines are being developed, using both custom hardware and software running on massively parallel machines. Using the new hardware, new applications of ray representations are being explored, including the solution of boundary-value problems, computation of medial axis transforms, methods for representing mechanical tolerances, and representation of solid objects.

University of North Carolina; John W Poulton, Henry Fuchs; Scalable Graphics: From Personal to Supercomputer Visualization Engines; (MIP-9306208 A001, A002, A003); $736,679; 12 months; (Joint support with the Advanced Projects Research Agency - Total Grant $855,141).

The object of this project is to build and experiment with a new graphics engine that will eliminate the current limits to scalability in commercial graphics systems. The work centers on a new graphics engine architecture called image composition, which is radically different from the organization of today's commercial systems. In image composition, rendering is distributed over a number of identical processors. Each renderer generates a full-screen image, but for only a fraction of the primitives in the scene. The system then merges these images over a high-speed network to form a single image of all primitives. Since each subimage is independent, and since the images can be merged on a distributed network whose throughput scales linearly with the number of subimages, performance of the entire system can be scaled up arbitrarily by adding more processors.

University of Pennsylvania; Ruzena K Bajcsy, Dimitri Metaxas, Vijay Kumar, Daniel K Bogen; Rapid Prototyping of Rehabilitation Aids for the Physically Disabled; (MIP-9420397); $10,000; 24 months; (Joint support with the Systems Prototyping and Fabrications Program, the Microelectronic Systems Architecture Program, the Design, Tools and Test Program, and the CISE Institutional Infrastructure Program - Total Grant $1,042,713).

The methods of rapid prototyping are ideally suited to rehabilitation devices. Because each person requires unique performance and function in a rehabilitation device, devices specific to each person must be rapidly designed and produced. This project is investigating a completely integrated approach to the design and prototyping of passive mechanical rehabilitation devices. The approach involves: the quantitative assessment of the form and performance of human limbs; the design of the assistive device; evaluation of the device using virtual prototyping; feedback from the consumer and therapist; actual prototyping of the device; evaluation of the function and performance of the device; and redesign based on performance. The contributions of the product include: the development of new computer-based tools for the assessment of human performance; a manufacturing technique for a new class of hyperelastic materials; the integration of tools into a rapid prototyping system for rehabilitation devices; and development of mechanisms for systematic evaluation of the final product.

General Purpose Computing

Stanford University; Michael J Flynn, Bruce A Wooley, S. Simon Wong, Giovanni De Micheli, R F W Pease; Sub-Nanosecond Arithmetic II; (MIP-9313701); $315,000; 12 months.

This project is attempting to speed up computer arithemtic by several orders of magnitude using a combination of algorithmic, circuit, and packaging techniques. CAD tools to automate the application of these techniques are also being developed under the project. Specific research problems include the development of a package capable of passing large numbers of signals with 100 picosecond rise times, and the integration of wave pipelined data paths into an overall system.

University of California - Berkeley; Domenico Ferrari; A Next-Generation Infrastructure for Integrating Computing and Communications; (CDA-9401156); $200,000; 12 months; (Joint support with the CISE Institutional Infrastructure Program - Total Grant $569,305).

This award provides support for the development of Titan, a computing system consisting of an integrated ensemble of computing and communication elements, organized to provide the user with a number of services. These services will include multimedia capabilities in delivery vehicles; storage and communication; large computing power; large storage space; innovative parallel languages, debuggers, and libraries; and high accessibility from both mobile and fixed locations. The experimental facilities requested include workstations and servers constituting the backbone of the distributed system providing cycles to the user, ATM switches for linking workstations and servers, a video editing system, a massive storage unit, and equipment for linking the network to the currently available CM-5 parallel computer.

The proposed research projects fall into three areas: network and communications; distributed supercomputer projects which are mainly concerned with providing parallel computing to every user through a combined architecture, operating systems, and programming language effort; and multimedia services which requires integrating systems support, software support, and artificial intelligence tools to create, store, play, edit, search, input, and output multimedia objects. The networking, multimedia, and computing aspects of Titan form will form the infrastructure for a number of computationally intensive applications.

University of California - Irvine; Isaac D Scherson; Massively Parallel Scientific Computing: Architectures, Networks and Applications; (MIP-9205737 A001); $154,573; 12 months.

Massively parallel computers show promise in several computational areas. In this project a commercial massively parallel computer is being used for several large-scale computational problems, including the architectural simulation of the P3, a proposed experimental massively parallel computer. Other applications of the commercial machine come from physics, chemistry, and discrete mathematics.

University of Illinois; Josep Torrellas; NYI: Increasing the Performance of Scalable Shared-Memory Multiprocessors; (MIP-9457436); $25,000; 12 months.

Scalable shared-memory machines are a promising way of attaining large-scale multiprocessing without surrendering much programmability. Achieving high performance from these machines, however, is challenging because many complex architecture and architecture-software implementation issues that have been only partially studied considerably impact the performance of the machines. The objective of this research is to contribute in three areas to help make shared-memory multiprocessors the preferred source of computing power. The three thrusts of this project are to: study the optimal division of responsibilities among the hardware, compiler, and operating system to maintain cache coherence in scalable share-memory multiprocessors; design algorithms and hardware to effectively support multiprogramming of parallel programs in scalable shared-memory multiprocessors; and optimize the management of memory hierarchies and the interaction of the operating system with the architecture.

Massachusetts Institute of Technology; Anant Agarwal; Automatic Management of Locality in a Scalable Cache- Coherent Multiprocessor: The MIT Alewife Machine; (MIP-9012773 A004); $608,404; 12 months.

The goal of the Alewife experiment is to demonstrate that a parallel computer system can be made both scalable and easily programmable. To achieve this end, a scalable parallel computer system called Alewife is being designed, built and evaluated as the experimental vehicle for this project. The system is a mesh- connected set of processor nodes, each consisting of a slightly modified SPARC processor, called SPARCLE, some main memory and cache, a Caltech route chip, and a custom memory management circuit, all on a custom PC board.

Massachusetts Institute of Technology; Anant Agarwal; PYI: Automatic Locality Management in Scaleable; Multiprocessors; (MIP-9157393 A003); $100,000, 12 months.

Parallel computers can be made both scalable and easily programmable through architectures that exploit and automatically manage communication locality. The goal of this research is to discover and to evaluate techniques for automatic locality management in scalable multiprocessors. As the vehicle for this research, an experimental parallel machine called the Alewife is being implemented. Alewife employs techniques for:

1.	communication latency minimization, using scalable coherent caches and software partitioning and placement of programs, and

2.	communication latency tolerance, using a new rapid-context-switching processor architecture.

Alewife implements a new protocol called "limitless directories" for scalable cache coherence. This scheme uses a combination of hardware and software techniques to realize the performance of a full-map directory with the memory overhead of a limited directory. A rapid-context-switching processor called Sparcle is also being designed. Sparcle can switch in about 10 cycles to another thread when it suffers a cache miss that requires service over the interconnection network.

The major goal for this grant period is to get a small prototype Alewife system operational, including the hardware as well as the entire software system.

University of Michigan; Trevor N Mudge, Richard B Brown, Santosh Abraham, John P Hayes, Edward S Davidson; Rapid Prototyping and Evaluation of High-Performance Computers; (MIP-9208342 A001); $205,443; 12 months.

This project supports a rapid prototyping facility that allows researchers in computer architecture to prototype their designs and obtain accurate performance measurements. The equipment in the facility are available nationally over the Internet, and staff are employed by the facility to assist remote users in prototyping their designs and in connecting custom hardware to the facility's equipment. The major component of the facility is a Quickturn Enterprise System that can prototype logic netlists of a target system in a network of FPGA's. It can emulate the target with a slowdown of only a few hundredfold, which is fast enough to exercise the design with significant benchmarks, test functionality, and take performance measurements. A built-in logic analyzer and stimulus generator permit detailed performance measurement and functional testing.

New York University; Allan Gottlieb; Evaluating the NYU Ultracomputer; (MIP-9303014 A001); $400,468; 12 months.

This is a project to characterize and model the performance of a scalable shared memory computer. Ultracomputer uses a multistage interconnection network with hardware combining to provide high-bandwidth scalable connections between processors and memory. Ultra III, on which the work is being performed, uses Xilinx parts to implement most of the glue logic in the PEs (processing elements). These can act as programmable performance monitors at each processor. These tools are being used to evaluate the impact of combining on overall system performance, measure the performance of scientific applications, measure and compare alternative operating system designs, and construct mathematical models of parallel system behavior.

North Carolina State University; Dharma P Agrawal; On a Class of Scalable Networks: Design, Performance and VLSI Layout; (MIP-9403191); $40,436; 24 months.

This project is a study of a two level interconnection networks, called dBcubes, in which hypercube subgraphs are interconnected by a de Bruijn graph. The purported advantage of this scheme is scalability. The hypercubes provide high local connectivity, while the de Bruijn graph allows a combination of fixed degree and low diameter. The goal of this project is to determine whether the study of interconnection networks of this type is relevant to practical computer architectures. Topics to be investigated include replacement of either the hypercubes or the de Bruijn graph with simpler graphs, a study of wormhole routing, algorithm embedding, and several implementation issues.

Pennsylvania State University; Robert M Owens, Mary J Irwin; Architecture, Algorithms and Software in the Design of a Massively Parallel, Fine Grain Processor; (MIP-9408921); $450,029; 24 months.

This project is investigating the design, implementation, and use of a family of family of massively parallel computers that use one processor per digit. A first generation design, completed in an earlier project, contains 16,384 fine grain processors on a single board. The processors contain a small number of parallel logic circuits and a configuration memory that controls the logic and interconnect. The entire machine is programmed for a problem by setting all configuration registers to transform the machine into a special-purpose computer for the problem. By improving the density of processors on chips and the speeds of interconnect and interface, this project is increasing the operation rate of the machine by a factor of 4 to 10. In addition to the design and implementation of architectures, this project is developing both high and low level programming tools for the machines. Finally, algorithms for solving compute intensive problems on these machines are being developed and tested.

University of Washington; Lawrence Snyder, Carl Ebeling; Chaotic Routing: Study and Implementation; (MIP-9213469 A001); $374,068; 12 months.

The chaotic router for multiprocessor systems avoids congestion in message routing by derouting packets chosen at random at congested nodes of a network. The routers can thus adapt to varying message traffic. In this project, the router is being implemented and its performance is being measured within a testbed that approximates a real multiprocessor.

University of Wisconsin; Mark D Hill, James R Larus, David A Wood; Cooperative Shared Memory and the Wisconsin Wind Tunnel; (MIP-9225097 A001); $392,124; 12 months.

The goal of this project is to design hardware and software for scalable shared-address-space computers. Cooperative shared memory, the approach taken in the project, provides a simple design for shared-memory hardware and a programming model that can be used by programmers and compilers to understand an application's communication behavior. Cooperative shared memory uses simple directory hardware together with a set of pragmas for use in applications software. The pragmas allow the applications software to indicate which processors will be using a block of memory: a processor can check out a block when it expects frequent use, check it back in when it is done, and can indicate that it expects to check out a block in the near future. Simple directory hardware can be used to place checked-out-memory locations in the caches of the appropriate processors. Common state transitions in the directory protocol are implemented in hardware, while the less common ones use software traps. Note that the pragmas and the resulting hardware actions

affect only the execution speed of a program, not its correctness. A new virtual prototyping approach is being used for evaluating the new architecture. The Wisconsin Wind Tunnel runs parallel shared-memory programs on a parallel message-passing computer and concurrently evaluates the programs execution times on proposed hardware using a distributed simulation. The simulation runs quickly because instructions that make only local memory references are executed directly.

Application Specific Computing

Massachusetts Institute of Technology; Robert C. Berwick; High Performance Computing for Learning; (IRI-9217041 A002); $24,000; 12 months; (Joint support with the Special Programs, the Knowledge Models and Cognitive Systems, the Robotics and Machine Intelligence, the Advanced Research Projects Agency, the Advanced Scientific Computing Centers Program, the CISE Instrumentation Program, and the Linguistics Program - Total Grant $725,000).

This project has been designed to push the High Performance Computing algorithmic and architectural envelope via a CM-5 and VLSI testbed. It will advance new algorithms and software for a broad class of optimization and learning problems, tested on and directly driving operating system and architectural changes on the CM-5 (working with one of the CM-5's key architects). The learning problems addressed are essentially an entire class of modeling/optimization problems that intersect with nearly all HPCC Grand Challenge Problems.

Massachusetts Institute of Technology; John L. Wyatt; Smart Vision Sensors: Analog VLSI Systems for Integrated Image Acquisition and Early Vision Processing; (MIP-9117724 A004, A005); $500,000; 12 months; (Joint support with the Advanced Research Projects Agency - Total Grant $1,414,567).

The primary goal of this research is to design and test analog VLSI systems for applications of real-time machine vision. In real-time machine vision the sheer volume of image data to be acquired, managed and processed leads to communications bottlenecks between imagers, memory and processors, and to very high computational demands. The goal is to determine how the advantages of analog VLSI--high speed, low power and small area--can be exploited and its disadvantages--limited accuracy, inflexibility and lack of storage capacity--can be minimized. The work is concentrated on early vision tasks, i.e., tasks that occur early in the signal flow path of animal or machine. Proposed designs include chips for camera velocity estimation, depth from stereo, image segmentation and smoothing, surface reconstruction, wide-range brightness adaptive imaging, and automatic fiducial mark alignment for wafer fabrication. MIT's earlier designs have shown that the typical subsystem is physically very small and will perform one or more computationally intensive image-processing tasks at hundreds-to- thousands of frames per second using only tens-to-hundreds of milliwatts.

University of Michigan; Kang G. Shin; Architecture and OS Support for Real-Time Fault- Tolerant Communication; (MIP-9203895 A002); $404,742; 12 months.

This is a project to build and experiment with a multiprocessor for real-time applications. The multiprocessor will ultimately consist of 19 nodes arranged in a hexagonal mesh, with each node containing three processors for computation, a commercial controller for communications control, and a custom chip for communications routing. An initial multiprocessor containing only a few nodes is being developed to allow experimentation that will guide full-scale construction. Experiments on the system consist largely of synthetic benchmark programs produced by a workload generator. The workload generator produces benchmarks that have computation, communication, and deadline characteristics of several classes of applications, but are easier to vary an instrument than real applications would be.

University of Minnesota; William K. Durfee; Virtual Environments for Rapid Prototyping of Product Interfaces; (MIP-9420394); $370,010; 36 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $400,010).

The goal of this research is to apply virtual environment technology to develop product prototyping tools, with a particular emphasis on emulating user interfaces. The approach is to emulate an interface using computer-based visual, aural, and haptic displays. The haptic display will use either playback of prerecorded sound clips or a physically based model of the control. The visual display will use the display monitor of a graphics workstation to show the emulated control in the context of the entire product.

The specific objectives of this project are to: design and construct one or more haptic displays; through modeling and experimentation develop new knowledge for the control of high-performance haptic displays; design and implement high-fidelity aural and visual displays for the virtual environment; and conduct a series of human subject experiments to determine how the three displays interact to determine the level of realism perceived by the user.

University of North Carolina; Raj K Singh; BioSCAN: A VLSI-Based System for Biosequence Analysis; (MIP-9024585 A003, A004); $230,697; 12 months; (Joint support with the the Databases, Software Development and Computational Biology Program - Total Grant $330,697).

The goal of this project is to construct an attached processor using application specific integrated circuits. This processor will perform high speed partial pattern matching of biological sequence data (such as DNA or protein sequences) against entries in a database. This processor will serve as a filter to provide information on partial matches (of segments) at a very high speed. This partial match information is used by the host processor to determine which sequences merit further detailed comparison (i.e. this prefiltering greatly limits the number of sequences which must be subsequently compared when considering insertions and deletions of subsequences). The subsequent full match will be carried out in the host processor.

University of Oregon; Zary Segall, Stephen F Fickas; Collaborative Research: Architecture, Design and Implementation of Mobile Computers; (MIP-9403573); $300,000; 24 months.

This is a joint effort between two universities for rapid prototyping of mobile computers. The projects involve teams of students who over the course of a semester design the hardware, software, and packaging of mobile computer systems, and fabricate prototypes by combining standard electronic parts with custom fabricated cases and interconnect harnesses. This project focusses primarily on mobile computing for the diagnosis of telecommunications networks. Mobile computer systems that include stationary and mobile computers, interface devices, and software, are being designed and fabricated for these applications. The project goal is to systematize the prototyping process in several ways: by providing an integrated design tool that can simultaneously represent electronic, thermal, and mechanical constraints; by providing modular template architectures for mobile computers; and by reporting on experience in the co-design of software, mobile hardware, and stationary hardware in a mobile computing system.

Carnegie-Mellon University; L. Richard Carley, David J Allstot, Rob A Rutenbar, Donald E Thomas; Design of Ultra-Low Power IC's; (MIP-9408457); $449,110; 24 months; (Joint support with the Microelectronic Systems Architecture Program - Total Grant $554,000).

This project combines analog circuit design and CAD to produce digital circuits that can operate at substantially reduced voltages, which will result in lower power consumption. The project has introduced the QuadRail logic family, which allows voltage control of transistor thresholds to maintain constant logic thresholds. Use of this family permits lower supply voltages because of the tighter control of device thresholds. However, use of this family requires optimization of individual digital cells, new device layout methods, and new strategies for floorplanning, placement, and routing. The research in this project is exploring all of these optimization areas, and is producing a battery powered demonstration system for speech signal processing.

Carnegie-Mellon University; Roy A Maxion, Andrzej J Strojwas, David L Banks; Discovering Information in Large, High-Dimensional Databases; (IRI-9224544 A001); $10,000; 12 months; (Joint support with the Knowledge Models and Cognitive Systems Program, Database & Expert Systems, the Design, Tools and Test Program, and the Statistics Program - Total Grant $150,000).

Discovering functional relationships among high-dimensional data is astonishingly hard. Overcoming the "curse of dimensionality" is a vital problem for any complex manufacturing industry, such as VLSI production, in which hundreds of variables must be precisely controlled in order to achieve high-quality yield. This research addresses both theoretical and practical concerns. On the theoretical end, statisticians have recently proposed a number of compelling new ideas for high-dimensional, nonparametric regression (e.g., ACE, AVAS, LOESS, PPR, MARS, RPR and several other algorithms). These ideas are largely untested, and little is known about their comparative performance in realistic situations. To remedy this, a large-scale simulation experiment is performed that employs statistical design to evaluate the effects of sample size, dimensionality, signal-to-noise ratio, and various kinds of underlying functions on the integrated mean squared error of the fitted model. The results of the study are examined in an analysis of variance, leading to clear conclusions as to the circumstances under which each of the proposed methods is most valuable. On the practical side, this research applies the methodology studied in the simulation experiment to VLSI production data as micro-modeled by the PREDITOR software, which is widely used in industry to calculate from physical principles the actual result of each step in the production of a VLSI circuit wafer.

Carnegie-Mellon University; Daniel P Siewiorek; Collaborative Research: Architecture, Design and Implementation of Mobile Computers; (MIP-9403473); $330,000; 24 months.

This is a joint effort between two universities for rapid prototyping of mobile computers. The projects involve teams of students who over the course of a semester design the hardware, software, and packaging of mobile computer systems, and fabricate prototypes by combining standard electronic parts with custom fabricated cases and interconnect harnesses. This project focusses primarily on mobile computing for the diagnosis of telecommunications networks. Mobile computer systems that include stationary and mobile computers, interface devices, and software, are being designed and fabricated for these applications. The project goal is to systematize the prototyping process in several ways: by providing an integrated design tool that can simultaneously represent electronic, thermal, and mechanical constraints; by providing modular template architectures for mobile computers; and by reporting on experience in the co-design of software, mobile hardware, and stationary hardware in a mobile computing system.

Carnegie-Mellon University; D. Lansing Taylor, Scott E Fahlman; High Performance Imaging in Biological Research; (BIR-9217091 A002, A003, A004); $115,000; 24 months; (Joint support with the CDA Special Projects Program, the Knowledge Models and Cognitive Systems Program, the Robotics and Machine Intelligence Program, and the Ecology, Cell Biology Program - Total Grant $915,000).

This is a project to research and develop an Automated Interactive Microscope (AIM). The AIM will combine the latest technologies in light microscopy and reagent chemistry with advanced techniques for computerized image processing, image analysis, and display, implemented on high-performance parallel computers. This combination will produce an automated, high-speed, interactive tool that will make possible new kinds of basic biological research on living cells and tissues. While one milestone of the research will be to show the proof-of-concept of AIM, the on-going thrust will be continued development as new technologies arise and the involvement of the biological community.

Brown University; Harvey F Silverman; A Large-Scale, Intelligent Three-Dimensional Microphone-Array Sound-Capture System; (MIP-9314625, A001); $324,324; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $339,324).

This is a joint project between Brown and Rutgers to build a large microphone array with associated processors for beam forming. Applications are direction finding, echo cancellation, and speaker differentiation in teleconference systems, multimedia educational systems, and large conference centers. Groups of microphones share microphone modules that perform A/D conversion and low-level processing. The microphone modules are linked over a high speed serial network (possibly optical) to a multiprocessor signal processing system for the higher level processing. The resulting system is being evaluated in an experimental teleconferencing facility.

University of Utah; Lee A Hollaar; Implementation and Evaluation of a Parallel Text Searcher for Very Large Databases; (MIP-9023174 A005, A006); $511,106; 12 months.

This project concerns the application of the Utah Retrieval System Architecture to very large databases of full-text documents. This effort involves the development of a medium scale (4 to 10 GBytes) parallel backend search server using augmented RISC processors as the searching engines. Data is being gathered and analyzed to determine if the existence of a high-speed search server changes the complexity and arrival rate of queries by real users (law students). In addition, a suitable partitioning of functionality such that remote users can be supported by such a searching engine over medium-speed networks (such as ISDN) is being studied. The researchers are also examining how the system can be reconfigured to deal with disk and searcher failures.

Other

Salk Institute for Biological Studies; Terrence J Sejnowski; Workshop on Neuromorphic Engineering, Telluride, CO, July 3-16, 1994; (IBN-9408680); $5,000; 12 months; (Joint support with the Neuroengineering Program, the Computational Neuroscience Program, and the Databases, Software Development and Computational Biology Program - Total Grant $51,000).

Recently a new field of engineering has emerged, referred to as neuromorphic engineering, that is based on the design and fabrication of artificial neural systems, such as vision chips, head-eye systems, and roving robots, whose architecture and design principles are based on those of biological nervous systems. A two-week workshop on neuromorphic engineering was held to bring together young investigators and more established researchers from academia with their counterparts in industry and national laboratories, working on both neurobiological as well as engineering aspects of

sensory systems and sensory-motor integration. Formal lectures were given, but the primary focus was hands-on experience with research tools for all participants. The workshop served as a bridge between the engineering world of artificial neural systems and the neuroscience community. The workshop will provide an environment for intensive interactions between members of these two communities - merging engineering principles with experimental results from neuroscience. The workshop will also serve as a prototype for the development of a similar yearly summer workshop. The interaction of these two disciplines should have significant impact both on the development of new technologies (new artificial neural systems) and on our understanding of how the nervous system is designed.

Systems Prototyping and Fabrication

Dr. John Staudhammer, Program Director

(703) 306-1936 jstaudha@nsf.gov

The Program

The Systems Prototyping and Fabrication Program addresses rapid prototyping technologies. The goal is to develop and integrate the tools and technologies needed for rapid and efficient design and fabrication of products, processes and systems. The SPF Program consists of three principal elements. The first (systems prototyping) supports fundamental research on rapid system prototyping methodologies, tools, environments, etc. with particular interest in the informational infrastructure needed for prototyping systems (virtual prototyping). The second (microfabrication) supports research related to advancing the state of the art in the modeling and control aspects of the fabrication (physical prototyping1). The third element (education) provides assistance to microelectronics education through support of MOSIS and administrative oversight for its involvement in microfabrication for educational institutions.

SYSTEMS PROTOTYPING

Systems Prototyping deals with the information technology for tying together design and fabrication in order to implement quick turnaround design of prototypes. The goal is to create methodologies and define technologies that reduce the time needed to build components and systems. SPF seeks to provide the design methodology and tools as well as infrastructure and services for rapid prototyping. Research is supported on: systems level design tools and environments for virtual prototyping of systems, design frames, design methodology interface problems, specification languages and formats and modeling techniques for packaging technologies.

New initiatives in this program element include research in rapid prototyping in advanced manufacturing. New tools and technologies for virtual prototyping coupled with innovative services and an updated infrastructure that allows distributed rapid prototyping over high speed networks are of particular interest. Projects include new languages for machine and process design, and CAD/CAM integration, as well as projects encompassing modeling, simulation, model validation, and design tools and techniques. Research dealing with the application of useful VLSI design paradigms to SFF (Solid Free-form Fabrication) and MEMS (Micro-ElectroMechanical Systems) are also addressed.

MICROFABRICATION

This program element supports basic research needed to understand, model and control microfabrication processes, including nanotechnology and biochips, pattern definition and transfer, and modeling, simulation and automation (for computer integrated manufacture of VLSI components and systems). The emphasis is on research focused on modeling and control aspects of physical prototyping. Topics of interest include architectures for manufacturing, simulation and real time control; disciplines for using semiconductor manufacturing equipment and processes; test structures, sensors and instrumentation for process monitoring; modeling and simulation at the process, device, circuit and system levels; integration of CAD, CAM and CAT methodologies and the application of these methodologies to SFF, MEMS and other mechanical and electromechanical prototyping technologies.

EDUCATION

This program element consists of two components. The first is MOSIS (MOS Implementation Service) which serves as a broker providing access to the semiconductor foundry industry. This program also deals with new technology issues at the undergraduate level through sponsorship of educationally oriented conferences and workshops, funding of innovative technology developments that significantly impact educational approaches to system prototyping (such as FPGA design frames), distribution of preliminary versions of innovative research and educational materials, and encouragement for the upgrading of microelectronics-related subject matter, curriculum, laboratories, and faculty.

Initiatives and Opportunities

The Systems Prototyping and Fabrication Program encourages research leading to the development of new technologies for rapid prototyping and provides the research and educational communities with access to these new technologies.

While MOSIS has provided and will continue to provide a valuable service to the university education and research community, other methods of virtual and physical implementation are needed. Methodologies for prototyping, packaging, testing and manufacturing must be integrated with and closely coupled to systems and circuit design technologies. Requirements for higher performance and improved reliability with smaller size, lower cost and lower power also dictate such integration. Young designers must work with more of a systems outlook, and have a more comprehensive design experience at a higher level of system implementation.

New technologies (mini-fab production lines, Field Programmable Gate Arrays (FPGA), Multi-Chip Modules (MCM), optical interconnect, micro-sensors, biochips, etc.), and new methodologies (fast prototyping, top-down design, powerful CAD tools, design libraries, etc.) when coupled with innovative services and an updated infrastructure have the potential to meet this need.

Listed below are some of the key issues related to the SPF activities;

*	Overcoming performance limitations increasingly due to packaging shortcomings.

*	Reducing the time and cost for prototype fabrication with new methodologies (virtual prototyping, for example), tools, equipment, and services.

*	Exploiting new technologies (field programmable gate arrays, multichip modules, etc.) and new methodologies for rapid physical prototyping in research and education.

*	Applying relevant VLSI design paradigms to solid free-form fabrication (SFF), micro-electromechanical systems (MEMS) and other mechanical technologies.

*	Simplifying, automating and speeding up access to microfabrication processes.

*	Making new package and multi-chip module approaches available to the academic community.

*	Defining new methods for functional and physical partitioning across and within package levels.

*	Encouraging a closer relationship between CAD tool designers and those doing fabrication, packaging and prototyping, in areas such as requirements, integration, and evaluation of system performance.

*	Developing, integrating and improving distributed access to virtual and physical prototyping techniques.

*	Developing design frames that allow rapid hardware simulation of application-specific systems.

*	Exposing students to a system-level design experience, with practice in optimizing the selection among design alternatives and with exposure to requirements for design verification.

*	Innovative use of curricular materials, compression of topics, curriculum updating, and use of higher levels of abstraction.

Awards

Systems Prototyping and Fabrication

San Jose State University; Albert K Hu; RIA: Run-to-Run Process Control System for Semiconductor Manufacturing; (MIP-9410219); $99,803; 36 months.

The project is aimed at developing a run-to-run process control system for quality enhancement of semiconductor manufacturing process. Based on post-process and in-situ measurements on product wafers, low order polynomial process models are suggested as a way of adjusting recipes that can increase the process qualities with minimal disruption to the production process. The proposer has demonstrated some of his methodology in industrial applications.

University of California - San Diego; Michael J Bailey, Ramesh C Jain; Making Rapid Prototyping Viable for Remote Use on the National Information Infrastructure; (MIP-9420099); $221,647; 24 months; (Joint support with the Experimental Systems Program, the Circuits and Signal Processing Program, the Microelectronic Systems Architecture Program, the Design, Tools and Test Program, and the Communications Research Program - Total Grant $706,290).

This project is working to make rapid prototyping and reverse engineering facilities available over wide-area computer networks. It includes several research thrusts along with an integration effort to ensure that the facilities will be usable remotely with little on-site intervention.

The project has four major thrusts:

1.	development of algorithms for checking consistency of geometric descriptions;

2.	development of new languages based on constructive solid geometry for communicating geometric descriptions;

3.	connection of rapid prototyping equipment to a wide rear network, with device drivers and server software to allow remote access; and

4.	connection of a 3D scanner to the network for remote access.

University of California - Santa Cruz; Wayne W Dai; PYI: Computer-Aided Design of VLSI Circuits--Constrained Net Embedding for Multichip Modules; (MIP-9058100 A004, A005,); $31,250; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $72,500).

Interconnection topology and metrics needed for laying out high-speed interconnections in multi-chip modules are pursued. The first topic is optimal design of transmission lines for multi-chip modules (MCM). These are self-damped lossy transmission lines in a tree network, which propagates high-speed signals. Algorithms to implement a robust method for designing these transmission lines are being developed. Attention is paid to distortion-free signal propagation, cross-talk, switching noise, and thermal resistance. The second topic is routing of clock signals for optimum system performance. An algorithm is being developed to construct a planar clock tree which can be embedded on a single layer of metal. Path length from the clock source to each clock terminal is exactly the same. The third topic is a multiple bus network for parallel processing which matches the MCM requirements of higher I/O pin count and inter- chip routing density. An algorithm with good fault tolerant properties that leads to uniform bus load and processor fanout is being developed.

University of Colorado; Elizabeth Bradley; Automatic Construction of Accurate Models of Physical Systems; (MIP-9403223); $64,799; 12 months.

This award provides funding for developing automatic construction of accurate models for physical systems. Specific information about the target system will be provided through measurements made directly on a physical device, or a user's observations described to the program in varying degrees of precision, and hypotheses suggested by a user. In addition to construction of such models, a secondary objective is to understand what matters in a model, what qualitative and quantitative are affected by the requirements of the situation and knowledge of the user. Such understanding is of practical importance in validating existing models and designs.

University of Colorado; Yung-Cheng Lee; PYI: Multichip Module Design for Manufacturing; (MIP-9058409 A006, A007,); $72,500; 12 months.

This research addresses some key requirements of the design for manufacture of very small supercomputers used in intelligent machines such as portable robots. This multidisciplinary effort is centered on developing a compact rapid prototyping and manufacturing center. Microscale laser lithography, flip-chip soldering and robot controlled pick-and-place techniques are being used. Simulation studies validate the design before prototyping. Research is concentrating on the self-aligning mechanism with an emphasis on the reliability of solder joints, fuzzy logic modeling with focus on the process modeling and optimization, and further improvement of thermosonic bonding technology.

University of Colorado; Yung-Cheng Lee, Thomas Siewert, Teh-Hua Ju, Leonard J Bond; Thermosonic Bonding for Flip-Chip and Ball-Grid-Array Connections; (MIP-9400655); $240,000; 36 months; (Joint support with the Microelectromechanical Research Program - Total Grant $329,853).

This award provides funding for developing Thermosonic Bonding technology, for connections in electronic packaging applications. Such a technology and the knowledge base resulting from the studies will have a profound impact on solderless packaging technologies in manufacturing. The resulting technologies can also be useful to support prototyping facilities and education in manufacturing engineering. The technology can simplify the prototyping procedures for multichip (MCM) modules. Such technologies are critical to low-cost and environmentally sound prototyping and manufacturing methods.

University of Colorado; Ganesh Subbarayan; RIA: A Methodology for Prototyping and Optimally Designing Land-Grid-Array Connectors for Multi-Chip Modules; (MIP-9409748); $100,000; 36 months.

The aim of the project is to develop a methodology for prototyping and designing land-grid-array connectors for multichip modules in high performance computers. An optimal design procedure to study the effects of several parameters on the connectors is a part of the investigation. A design verification procedure using scaled-up prototypes of LGA connector contacts through experimental models is also being explored.

University of Florida; Mark E Law; PFF: A Multidisciplinary Approach to IC Process Modeling Using the SUPREM-IV Modeling Tool; (MIP-9253735 A002); $100,000; 12 months.

This multidisciplinary research focuses on the development of silicon models for point defect behavior, which are vital to understanding dopant diffusion. Models are being developed and parameterized for the effect of silicidation and stress on point defect kinetics. These models are then implemented in SUPREM-IV, a standard integrated circuit process modeling tool that utilizes advanced finite element techniques. This is a Presidential Faculty Fellow (PFF) Award initially awarded in Fiscal Year 1992.

University of Kentucky; Charles E Stroud; RIA: Self-Testing, Diagnostic and Repair Configurations for Field Programmable Gate Arrays; (MIP-9409682); $90,000; 36 months.

The research is directed at system level testing by developing algorithms and circuit configurations which can be loaded into FPGA's to provide self-testing, fault diagnostic and repair capabilities. Once faults in an FPGA have been detected and identified, reconfiguration algorithms would then be used to remap the system function into the FPGA while avoiding the existing faults. It is conjectured that by using this approach, development of application-specific system diagnostic software for testing the FPGA system function can be avoided.

University of Maryland; K. J. Ray Liu; NYI: High Performance Computing for Signal Processing; (MIP-9457397); $12,500; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $25,000).

There are three major architectural models used in high-performance signal/image processing:

1.	signal processing - high- throughput VLSI architectures for low-cost application-specific implementations used in applications such as communication systems, speech, video/HDTV, and radar;

2.	parallel signal processing on massively parallel computers - parallel algorithms for complex signal/imaging systems used in computer vision, medical imaging, and the processing of vast amounts of data in deep space exploration;

3.	distributed signal processing on high-speed networks - used in applications such as document image processing, multimedia, automatic signal processing in manufacturing, and medical signal/image processing.

This research focuses on the development of efficient algorithms and architectures for each architectural model, and in comparative studies of the advantages and disadvantages of these different computing schemes. The goal is to investigate which signal/image processing problems can be carried out optimally under different computing and communication schemes.

University of Massachusetts; Maciej Ciesielski and Wayne Burleson; High-Performance VLSI Synthesis with Wave Pipelining; (MIP-9208267 A02); $25,000; 12 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $91,914).

Wave-pipelining is a method of high-performance circuit design which implements pipelining in unlocked gates without the use of intermediate latches. As a result, several computation waves (signals) related to different clock cycles can propagate through the logic simultaneously. This research extends previous implementations of wave-pipelining in static logic to include dynamic CMOS logic which has a smaller area and higher-performance. Previous work in wave-pipelining used the insertion of delay elements on signal and clock lines to equalize path delays. These delays are often imprecise and can require a significant amount of VLSI area. To avoid these problems, we equalize the paths by restructuring the computation within the logic block. The restructuring at the logic level using tools of modern logic synthesis, is targeted towards highly structured computations and regular arrays. The new methods are implemented in a suite of CAD tools to make wave pipelining accessible in automatic VLSI synthesis systems. Several VLSI test chips are designed, fabricated and tested to verify the feasibility of our methods and CAD tools.

University of Massachusetts - Dartmouth; Robert H Caverly; RUI: High Frequency Analog Telecommunications Circuits; (MIP-9414308); $174,499; 36 months.

This RUI award supports development of standard cell library of high frequency analog CMOS telecommunication circuits in 2.0, 1.2 and 0.8 micron technologies. Design and evaluation data on the library cells will be included with the library. The entire library and evaluation data will be made available to interested investigators over Internet. It is expected that the project will provide support to the wireless research community, as well as students in the area or analog circuitry.

Michigan State University; Chin-Long Wey; Efficient Testing Paradigms and Diagnosable Design Methodologies for Analog Integrated Circuits and Systems; (MIP-9321255); $45,167; 24 months; (Joint support with the Design, Tools and Test Program - Total Grant $93,114).

This research is on test paradigms for high-frequency, linear and nonlinear mixed signal circuits and systems. Issues in BIST (Built-In Self-Test) and design for testability are being addressed. Fault models for hard faults (open or short circuits) and for soft faults (deviations from nominal component values) are being developed. For BIST design, a high speed, low power, current mode copier is employed as the sample/hold circuit to achieve 10 ns/sample at 0.1% accuracy under 3. 3V power supply. Both CMOS and BiCMOS technology are being used. Design for testability work focuses on properly selecting component values and topological structure to increase testability and diagnosability. The problem of determining component values is formulated as an optimization problem which includes testability strategy as a parameter. The new methods are being tested on realistic circuits.

Michigan Technological University; Ashok K Goel, Esther T Ososanya; Experimental Validation of Interconnection and Transistor Delay Models for the GaAs-Based Integrated Circuits; (MIP-9223989 A001, A002); $42,382; 12 months.

During the last few years, GaAs technology has emerged rapidly from basic research to device and circuit development. It is crucial to know the expected propagation delays in an integrated circuit before it is fabricated. To meet this objective, numerical models have been developed that address crosstalk and propagation delays in parallel and crossing VLSI multilevel interconnections as well as for the transverse delays in the GaAs MESFETs and GaAs/AIGaAs MODFETs. In addition to determining the crosstalk and propagation delays, the models can be utilized to achieve the optimization of the device and interconnection dimensions and other parameters for minimum crosstalk and delays. Validation of these numerical models by comparison of the modeling results with actual experimental observations is critical if they are to be incorporated into GaAs CAD tools. This research effort focuses on the following set of objectives:

1.	design and fabrication of several GaAs-based logic circuits to retain the ability to alter the various design parameters;

2.	application of the interconnection and the GaAs MESFET delay models recently developed for the determination of propagation delays in these GaAs-based logic circuits;

3.	experimental measurements of propagation delays in these circuits and comparison with developed delay models;

4.	modification of the interconnection and transistor delay models, as required; and,

5.	experimental validation of the final models.

University of Michigan; William P Birmingham; PYI: Computer-Aided Design Synthesis; (MIP-9057981 A006, A007); $69,500; 12 months.

This research focuses on the development of a set of tools to rapidly prototype digital systems taking into account a need to minimize lifetime costs by building testable systems and including consideration of manufacturing issues. The knowledge- based synthesis system MICON serves as a software workbench. MICON takes an input high-level functional specification for a microprocessor-based system and generates a complete design. More specifically, this research focuses on three major topics:

1.	A design-for-testability extension (DFT);

2.	A domain-independent version of MICON (DIM); and,

3.	An interface to high-level (behavioral) synthesis tools.

Research is concentrating on three areas: heuristic search methods for large-scale optimization, knowledge acquisition tools, and timing verification.

University of Michigan; William P Birmingham; Board Level Timing Verification; (MIP-9318956); $93,958; 24 months.

The proposed research deals with analytically verifying the satisfaction of timing constraints of component interfaces in board level circuits. A methodology, VITCh (VLSI Interface Timing Checker), that will allow the analytic timing verification of realistic board-level circuits through new models of behavior and verification is investigated. Also there is developed a hierarchial model of interface behavior that allows the task to be decomposed to minimize overall complexity. This model allows efficient timing analysis of board-level circuits and thereby enables the analytical verification of large and complex circuits that prior approaches were unable to verify. A CAD system implementing VITCh provides a testbed for experimentally validating the model and methodology. The timing analysis problem is solved by decomposing the task into several subtasks that can be executed concurrently. Each subtask is performed such that timing constraints are verified during the process of circuit behavior emulation and eliminates the need to build and analyze composite representations of circuit behavior. The research plan includes testing VITCh on circuits ranging from tens to hundreds of components to establish the range of applicability of the algorithm as a function of circuit size.

Dartmouth College; Barry S Fagin; Quantitative Construction of New FPGA Architectures for Large System Prototyping; (MIP-9222643 A001); $55,976; 12 months.

Today's microprocessors are much more remarkable in their similarities than in their differences; this is not likely to change for the foreseeable future. By combining a fixed set of datapath components with FPGA-implemented interconnect and control, complex systems can be constructed that emulate different microprocessor architectures. This research attempts to identify target applications for which special-purpose processors can offer performance gains. Current areas of investigation include gene sequence analysis and multimedia systems. The objectives of this research are the completion of a quantitative study of the utility of FPGAs in the prototyping of large heterogeneous digital systems, and the development of new FPGA architectures based on this study. The methods employed consist of:

1.	the implementation of custom microprocessors and general emulation systems on FPGAs;

2.	quantitative analysis of these designs;

3.	measurement of performance, power consumption, and other relevant parameters of these designs; and,

4.	use of results to develop new FPGA architectures better suited to the prototyping of complex digital systems.

State University of New York - Binghamton; Jiayuan Fang; NYI: Analysis and Modeling of High-Speed Interconnects in Electronics Packaging; (MIP-9357561 A001); $62,500; 12 months.

This research is concerned with the analysis and modeling of electrical performance of high-speed interconnects in electronics packaging. The finite-difference time-domain (FDTD) method, which is a full-wave solution of Maxwell's equations in three dimensions, is used to simulate signal propagation through interconnects. Topics pursued are:

1.	Development of a computational scheme for conformed finite-difference grid to model complex-shape interconnects. The objective of this scheme is to enhance the resolution and accuracy of numerical solutions while maintaining the computation efficiency associated with the regular rectangular finite-difference grid.

2.	Analysis and modeling of electrical properties of interconnection discontinuities in electronics packaging. Issues involved in this topic include: modeling of electrical characteristics of interconnection discontinuities over the frequency range from dc to tens of gigahertz; evaluation of impacts of parasitics associated with interconnection discontinuities on the propagation of high-clock rate signals; and development of design guidelines for typical interconnection discontinuities in high performance electronics packaging.

North Carolina State University; Paul D Franzon; NYI: Advanced Interconnect and Display Approaches; (MIP-9357574 A001); $62,500; 12 months.

The primary focus of this work is to resolve issues dealing with the design and implementation of high bandwidth reconfigurable interconnect systems based on Micro ElectroMechanical Systems (MEMS) which are commonly referred to as Micromachines. Different guided-wave optical and holographic free-space optical switch elements are being implemented and compared in terms of bandwidth, switch reconfiguration rate, and range of programmability. Application to data switching, and programmable interconnect devices for rapid prototyping are being addressed with attention to both technological and system-wide performance/cost design issues. Comparisons are made with conventional technologies. Also being investigated is the application of some of the optical MEMS elements to advanced image projection.

North Carolina State University; Clay Gloster; MRIA: Complete Testability with Partial Scan; (MIP-9410793); $42,964; 36 months; (Joint support with the Design, Tools and Test Program - Total Grant $85,928).

This research is on the use of partial scan for system test. The goal is to find solutions that do not sacrifice fault coverage. The main problem addressed is: given a sequential circuit, find the minimal set of flip-flops that are to be included in the scan chain while maintaining complete fault coverage. The approach is to define a metric, "profit", for a particular scan chain configuration. This metric is equal to the probability that the required states for testing the target faults will be obtained using deterministic test generation techniques. Various optimization techniques are being used to find the scan chain configuration that has large profit. Algorithms for using this technique are being developed into a test tool.

University of North Carolina - Charlotte; Dian Zhou; NYI: Performance-Driven VLSI Designs; (MIP-9457402); $12,500; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $25,000).

Three research issues in high-performance VLSI system design are being addressed:

1.	how to relate the system performance function, characterized by electrical parameters, to the geometrical parameters of the VLSI physical design;

2.	how to model performance driven VLSI physical designs based on given technology and computational capability; and,

3.	how to characterize the fundamental computational aspects of modeled problems and develop effective algorithms for solving them.

A distributed RLC circuit model for interconnects is being designed. It considers: non-monotone circuit response, coupling effect among the signal lines, and low energy consumption. Efficient computation methods that solve time-varying Maxwell equations using the adaptive wavelet collocation method (AWCM) are being devised. The algorithms and methods are being included in a CAD system.

University of Pennsylvania; Ruzena K Bajcsy, Dimitri Metaxas, Vijay Kumar, Daniel K Bogen; Rapid Prototyping of Rehabilitation Aids for the Physically Disabled; (MIP-9420397); $442,714; 24 months; (Joint support with the Experimental Systems Program, the Microelectronic Systems Architecture Program, the Design, Tools and Test Program, and the CISE Institutional Infrastructure - Total Grant $1,042,713).

The methods of rapid prototyping are ideally suited to rehabilitation devices. Because each person requires unique performance and function in a rehabilitation device, devices specific to each person must be rapidly designed and produced. This project is investigating a completely integrated approach to the design and prototyping of passive mechanical rehabilitation devices. The approach involves: the quantitative assessment of the form and performance of human limbs; the design of the assistive device; evaluation of the device using virtual prototyping; feedback from the consumer and therapist; actual prototyping of the device; evaluation of the function and performance of the device; and redesign based on performance. The contributions of the product include: the development of new computer-based tools for the assessment of human performance; a manufacturing technique for a new class of hyperelastic materials; the integration of tools into a rapid prototyping system for rehabilitation devices; and development of mechanisms for systematic evaluation of the final product.

Texas A & M University; S. H. K. Embabi; RIA: Investigation on the Implementation of Field Programmable Analog Array Chips; (MIP-9410413); $91,184; 36 months.

The research focusses on development of Field-programmable Analog Arrays (FPAA). The main objective is to search for generic analog arrays which can be used for realization of analog circuits and systems. Several configurable analog block styles with different granularities are considered to arrive at optimal configurable analog blocks. The research also includes considerations of architectural and interconnection issues.

Texas A & M University; Dhiraj K Pradhan, Duncan M H Walker, Wolfgang Kunz; Novel Methods in Computer-Aided Circuit Design and Testing Using Recursive Learning; (MIP-9406946); $37,030; 12 months; (Joint support with the Design, Tools and Test Program - Total Grant $106,030).

This research investigates modeling and estimation of power consumption as well as techniques for minimizing power at the various levels of design abstraction (layout, logic, register- transfer and behavioral levels). Principles and methods to guide the design of power efficient electronic systems are being explored; and the impact of availability of low-power design techniques on chip, module, and system level designs is being assessed. Topics being investigated include: spatio-temporal power estimation; state assignment for low power; power dissipation in boolean networks; common subexpression extraction; and FPGA synthesis for low power.

University of Texas; Guanghan Xu, Dim-Lee Kwong; Development of Advanced Signal Processing Algorithms for On-Line Temperature Profile Measurement in Semiconductor Manufacturing; (MIP-9400732); $50,000; 12 months; (Joint support with the Circuits and Signal Processing Program - Total Grant $79,230).

This research is directed towards the development, implementation, and demonstration of advanced model-based signal processing algorithms for real-time measurement of wafer temperature profile in Rapid Thermal Processing (RTP). RTP cluster tools are strategically important for submicron semiconductor manufacturing because of trends towards reduced thermal budget and tightened process control requirements on large diameter silicon wafers. Despite its significant advantages, commercial versions of RTP modules for various chemical vapor deposition applications are not available.

In this project, the investigators are developing advanced model-based signal processing algorithms, which when coupled with the acoustic thermometry and acoustic/pyrometer approaches, accurately measure the wafer temperature profile at fast acquisition rates and with a minimum number of sensors. This entails algorithm development, implementation, and validation using real data from commercial RTP tools at UT-Austin and SEMATECH.

University of Utah; Ganesh Gopalakrishnan; A Multi-Paradigm Verification System Tailored for the Design Refinement Cycle; (MIP-9321836); $54,210; 24 months; (Joint support with the Design, Tools and Test Program - Total Grant $104,861).

The design of a VLSI system involves multiple design representations; and the design must go through several iterations aimed at meeting many performance and cost constraints. Verification that the design meets constraints is necessary. This research is developing rigorous verification methods that span multiple design representations, accommodate design revisions, and provide incisive partial verification methods (e.g., verification focussed on the "corners" of the behavioral space) that fit within designers' time budgets. These ideas are being validated by verifying the real asynchronous designs.

West Virginia University; Lawrence A Hornak; NYI: Cointegrated Polymer Waveguide Optical Interconnections for Wafer-Level MCM Systems; (MIP-9257101 A002); $62,500; 12 months.

Motivated by the need for robust polymers optically superior to polyamides yet suitable for cointegration of optical interconnection waveguides directly with the active CMOS interconnection substrate of advanced multi-chip modules (MCMs), the research seeks to fabricate optical waveguides with polyphenylsilsesquioxane (PPSQ), a spin

castable, low temperature processed silicon ladder polymer used as a thin and thick film dielectric for microelectronics. This material potentially offers the low loss obtainable with less stable optical polymers while offering thermal stability and process latitude (patterning, wet, dry etching) exceeding that of polyamide. This research assesses the suitability of PPSQ together with planarizing and superstrate polymer layers for providing a multilayer system supporting fabrication of high density waveguide arrays directly over the Si devices of emerging active MCM substrate.

Education

University of Tennessee; Donald W Bouldin; 1993 Workshop on Rapid Prototyping of Integrated Circuits for Universities, October 18-19,1993, Washington, DC; (MIP-9319902 A001); $1,918.

This award provides additional funding for a workshop to convene experts and scientists to assess the unique needs educators have for the rapid prototyping of integrated circuits and to suggest potential solutions for continuously improving the state-of-the-art in U. S. universities. User data indicates that in some cases resources are not being

used in the most effective manner. This workshop focuses on the prototyping facilities offered by MOSIS and how these facilities can be most effectively utilized by the education community. The workshop discusses and makes recommendations in the areas of: new technologies; design methodologies; testing; and policies, procedures, and information dissemination. Invited participants from universities, government agencies, and industry seek to determine how universities can improve their capabilities in the rapid prototyping of integrated circuits. A report will be produced and distributed to microelectronics educators as well as selected government and industry leaders.

Infrastructure

Western Michigan University; Naveed A Sherwani; VLSI Gopher; (MIP-9406651); $29,217; 12 months.

The research is directed at the design and implementation of a VLSI Gopher. The VLSI Gopher aims at providing an infrastructure to researchers in VLSI Design Automation. It is expected to provide the latest pertinent information on benchmarks, design layouts, research papers, university publications, proceedings of conferences, journals in a well organized format for use by the research community.

Advanced Research Projects Agency; Randy H. Katz; NSF/ARPA Agreement for Use of ARPA VLSI Implementations; (MIP-9419682); $350,000; 12 months; (Joint support with the Microelectromechanical Research Program, the Manufacturing Machines and Equipment Program, and the USEME Course and Curriculum Program - Total Grant $800,000).

A 1994 Memorandum of Understanding (MOU) between the National Science Foundation (NSF) and the Advanced Research Projects Agency (ARPA) extended a three-year joint program supporting VLSI (Very Large Scale Integration Fabrication) by MOSIS (Metal Oxide Semiconductor Implementation Service) for qualifying universities. The continuation of the MOU expands the original program to accelerate critical capabilities for Microsystems Design and Prototyping in U.S. universities. This includes expanding the original services and technologies available to universities authorized to use MOSIS as they become generally available and cost-effective (e.g., semi-custom and gallium arsenide chip fabrication), stressing VLSI education, especially undergraduate education needed for designing future electronic system; exploring new fabrication services designed specifically for the research and education community's desire for cost effective experimentation of state-of-the-art technologies (e.g., design of advanced sensor and micro-mechanical devices); and rapid prototyping methodologies, tools, and services needed for complete systems.

Index of Presidential/NSF Young Investigators

Agarwal, Anant	57

Baraniuk, Richard G.	43

Birmingham, William P.	68

Bresler, Yoram	41

Buckley, Kevin M.	37

Burns, Steven M.	8

Bushnell, Michael L.	11

Cong, Jason	3

Dai, Wayne W.	8, 65

De Micheli, Giovanni	3

Devadas, Srinivas	5

Eggers, Susan J.	25

Fang, Jiayuan	68

Farrens, Matthew	19

Ferguson, Frankie J.	12

Fiez, Terri S.	35

Franzon, Paul D.	69

Green, Michael M.	14, 33

Hill, Mark D.	25

Hornak, Lawrence A.	71

Kahng, Andrew B	3

Larrabee, Tracy	12

Lee, Yung-Cheng	66

Li, Jian	40

Liu, K. J. Ray	46, 66

Malik, Sharad	5

Orchard, Michael T.	41

Parhi, Keshab K.	47

Pedram, Massoud	4, 20

Pillage, Lawrence T.	14

Pomeranz, Irith	10

Rabaey, Jan	46

Ramachandran, Umakishore	21

Riskin, Eve A.	46

Robins, Gabriel	8

Saleh, Resve A.	13

Siu, Kai-Yeung	19, 33

Stonick, Virginia L.	38

Torrellas, Josep	57

Van Veen, Barry D.	39

Varma, Anujan	20

Wawrzynek, John	26

Yang, Andrew T.	15

Yang, Woodward	47

Zakhor, Avideh	45

Zhou, Dian	9, 69

Index of Research Initiation Investigators

Amon, Tod T.	7

Chao, Liang-Fang	5

Chen, Peter M.	22

Cheng, Kwang-Ting	10

Coleman, Jeffrey O.	14, 49

Conte, Thomas M.	29

Embabi, S. H. K.	70

Hu, Albert K.	65

Koppelman, David M.	22

Kubichek, Robert F.	51

Lewis, Stephen H.	34

Liang, Zhi-Pei	41

Liu, K. J. Ray	46

Lo, Jien-Chung	13

Long, Junsheng	24

Nair, Sukumaran	7

Nowick, Steven M.	9

Qiao, Chunming	23

Ramchandran, Kannan	42

Sayed, Ali H.	48

Sridhar, Ramalingam	23

Stroud, Charles E.	66

Subbarayan, Ganesh	66

Tragoudas, Spyros	12

Index of Principal Investigators

A

Abraham, Jacob A.	11

Abraham, Santosh	57

Adams, John W.	36

Agarwal, Anant	57

Agrawal, Dharma P.	58

Allstot, David J.	24, 60

Amon, Tod T.	7

Andreou, Andreas G.	27

Armstrong, James R.	11

B

Bailey, Michael J.	15, 26, 48, 55, 65

Bajcsy, Ruzena K.	16, 29, 56, 69

Bamberger, Roberto H.	44

Banerjee, Prithviraj	5

Banks, David L.	15, 60

Baraniuk, Richard G.	43

Barnwell, Thomas P.	40

Basu, Sankar	43

Berwick, Robert C.	59

Bhattacharya, Debashis	4

Bhuyan, Laxmi N.	25

Birmingham, William P.	68

Bogen, Daniel K.	16, 29, 56, 69

Bond, Leonard J.	66

Bose, Bella	28

Bouldin, Donald W.	71

Bradley, Elizabeth	65

Bresler, Yoram	41

Brewer, Forrest	8

Brown, Richard B.	57

Bruner, John	21

Brunvand, Erik L.	16

Buckley, Kevin M.	37

Burleson, Wayne	22, 67

Burns, Steven M.	8

Burrus, C. Sidney	39

Bushnell, Michael L.	11

C

Cagan, Jonathan	6

Carley, L. Richard	24, 60

Caverly, Robert H.	67

Chao, Liang-Fang	5

Chen, Peter M.	22

Cheng, Chung-Kuan	3, 20

Cheng, Kwang-Ting	10

Chien, Andrew A.	21

Chua, Leon O.	33

Ciesielski, Maciej	22, 67

Clarke, Edmund M.	6

Clarkson, Peter	38

Clements, Mark A.	40

Cohoon, James P.	7

Coleman, Jeffrey O.	14, 49

Cong, Jason	3

Conte, Thomas M.	29

Cyre, Walling R.	11

D

Dai, Wayne W.	8, 65

Das, Chitaranjan	24

Davidson, Edward S.	9, 23, 57

De Micheli, Giovanni	3, 56

Devadas, Srinivas	5

Durfee, William K.	49, 59

E

Ebeling, Carl	58

Eggers, Susan J.	25

Embabi, S. H. K.	70

Ercegovac, Milos D.	20

Esfahanian, Abdol	22

Etter, Delores M.	36

F

Fagin, Barry S.	68

Fahlman, Scott E.	61

Fang, Jiayuan	68

Farrens, Matthew	19

Farvardin, Nariman	45

Ferguson, Frankie J.	12

Ferrari, Domenico	56

Fickas, Stephen F.	60

Fiez, Terri S.	35

Fischer, Thomas R.	44

Flanagan, James L.	43

Flynn, Michael J.	56

Franzon, Paul D.	69

Fuchs, Henry	55

Fujimoto, Richard M.	27

G

Galatsanos, Nikolas P.	40

Geman, Stuart A.	44

Gidas, Basilis	44

Gloster, Clay	11, 69

Goel, Ashok K.	67

Gopalakrishnan, Ganesh	7, 70

Gottlieb, Allan	58

Gray, Paul R.	34

Gray, Robert M.	45

Green, Michael M.	14, 33, 34

Grenander, Ulf	44

H

Hachtel, Gary	4

Harris, Jay H.	25

Hayes, John P.	10, 57

Hill, Mark D.	25, 58

Hollaar, Lee A.	61

Hornak, Lawrence A.	71

Hu, Albert K.	65

Hwu, Wen-mei	21, 30

I

Irwin, Mary J.	58

J

Jain, Ramesh C.	15, 26, 48, 55, 65

Jha, Niraj K.	12

Jordan, Harry F.	20

Ju, Teh-Hua	66

K

Kahng, Andrew B	3

Karpovsky, Mark G.	28

Kassam, Saleem A.	38

Katsaggelos, Aggelos K.	41

Katz, Randy H.	71

Kaveh, Mostafa	38

Kime, Charles R.	11

Koppelman, David M.	22

Kubichek, Robert F.	51

Kuh, Ernest S.	3

Kumar, Vijay	16, 29, 56, 69

Kunz, Wolfgang	7, 70

Kwong, Dim-Lee	50, 70

L

Larrabee, Tracy	12

Larus, James R.	58

Law, Mark E.	66

Lee, Edward A.	46

Lee, Yung-Cheng	66

Levitan, Steven P.	6

Lewis, Stephen H.	34

Li, Jian	40

Liang, Zhi-Pei	41

Lightner, Michael	4

Liu, K. J. Ray	46, 47, 66

Liu, Wentai	24

Lo, Jien-Chung	13

Lo, Virginia M.	28

Long, Junsheng	24

Louri, Ahmed	19

M

Makki, Rafic Z.	12

Malik, Sharad	5

Mammone, Richard	43

Maragos, Petros	37

Maurer, Peter M.	13

Maxion, Roy A.	15, 60

Mazumder, Pinaki	22

McClellan, James H.	40

McClure, Donald E.	44

McCluskey, Edward J.	10

McGrath, S. J.	40

McKinley, Philip K.	22

Melville, Robert C.	14, 33

Mendel, Jerry M.	36

Menon, Premachandran	10

Metaxas, Dimitri	16, 29, 56, 69

Meyer, Robert G.	34

Mudge, Trevor N.	9, 23, 57

Mumford, David	42

Murdocca, Miles	23

N

Nair, Sukumaran	7

Ni, Lionel M.	22

Nikias, Chrysostomos L.	36

Nowick, Steven M.	9

O

Olshen, Richard A.	45

Orchard, Michael T.	41

Ososanya, Esther T.	67

Owens, Robert M.	58

P

Palusinski, Olgierd A.	13

Pangrle, Barry	6

Parhi, Keshab K.	47

Pease, R. F. W.	56

Pedram, Massoud	4, 20

Pillage, Lawrence T.	14

Pineda, Fernando	27

Pinkham, Roger S.	43

Pomeranz, Irith	10

Poulton, John W.	55

Pradhan, Dhiraj K.	7, 29, 70

Prasanna, V. K.	26

Prince, Jerry L.	42

Proakis, John G.	37

Q

Qiao, Chunming	23

R

Rabaey, Jan	46

Rajopadhye, Sanjay	28

Ramachandran, Umakishore	21

Ramchandran, Kannan	42

Ranganathan, N.	27

Riskin, Eve A.	46

Robins, Gabriel	8

Roysam, Badrinath	49

Rutenbar, Rob A.	6, 24, 60

S

Sahni, Sartaj K.	4

Sakallah, Karem A.	9, 23

Saleh, Resve A.	13

Salowe, Jeffrey S.	7

Sarrafzadeh, Majid	5

Sauer, Ken D.	42

Sayed, Ali H.	48

Schafer, Ronald W.	40

Schell, Stephan V.	50

Scherson, Isaac D.	57

Schreier, Richard	45

Sechen, Carl	14

Segall, Zary	60

Sejnowski, Terrence J.	62

Sherwani, Naveed A.	71

Shin, Kang G.	59

Siewert, Thomas	66

Siewiorek, Daniel P.	61

Silverman, Harvey F.	29, 47, 48, 61

Singh, Raj K.	60

Siu, Kai-Yeung	19, 33

Smith, Alan J.	19

Smith, Mark J.	40

Smith, Warren E.	44

Snyder, Lawrence	58

Soma, Mani	13

Somenzi, Fabio	4

Song, Bang-Sup	34

Soumyanath, Krishnamurthy	50

Sridhar, Ramalingam	23

Steiglitz, Kenneth	28

Stewart, Alan L.	43

Stonick, Virginia L.	38

Strojwas, Andrzej J.	15, 60

Stroud, Charles E.	66

Subbarayan, Ganesh	66

T

Taylor, D. Lansing	61

Tekalp, A. Murat	44

Temes, Gabor	35

Thomas, Donald E.	24, 60

Torrellas, Josep	57

Tragoudas, Spyros	12

Tugnait, Jitendra K.	35

V

Van Veen, Barry D.	39

Varma, Anujan	20

Venkateswaran, H.	21

Vetterli, Martin	39

Voelcker, Herbert B.	55

W

Wah, Benjamin W.	21

Walker, Duncan M. H.	7, 70

Wawrzynek, John	26

Wei, Belle	26

Wey, Chin-Long	9, 67

Willsky, Alan S.	49

Willson, A. N.	33

Wolf, Wayne H.	6

Wong, S. Simon	56

Wood, David A.	58

Wooley, Bruce A.	56

Wyatt, John L.	59

X

Xu, Guanghan	50, 70

Y

Yang, Andrew T.	15

Yang, Qing	25

Yang, Woodward	47

Yew, Pen-Chung	21

Z

Zakhor, Avideh	45

Zhou, Dian	9, 69

Zoltowski, Michael D.	37

Index of Institutions

Advanced Research Projects Agency	71

Auburn University	35

Boston University	28

Brown University	29, 44, 47, 48, 61

California State University - Northridge	36

Carnegie-Mellon University	6, 15, 24, 38, 60, 61

Columbia University	9

Cornell University	55

Dartmouth College	68

Georgia Institute of Technology	21, 27, 37, 40

Harvard University	42, 47

Illinois Institute of Technology	40

Iowa State University	5

Johns Hopkins University	27, 42

Louisiana State University	22

Massachusetts Institute of Technology	5, 49, 57, 59

Michigan State University	9, 22, 67

Michigan Technological University	14, 49, 67

New York University	58

North Carolina State University	11, 24, 58, 69

Northeastern University	37

Northwestern University	5, 41

Ohio State University	38

Oregon Advanced Computing Institute	28

Oregon State University	28, 35, 45

Pennsylvania State University	6, 24, 50, 58

Princeton University	5, 6, 12, 28

Purdue University	37

Rensselaer Polytechnic Institute	49

Rutgers University	11, 23, 43

Salk Institute for Biological Studies	62

San Diego State University	25

San Jose State University	26, 65

Southern Illinois University	12

Southern Methodist University	7

Southwest Texas State University	7

Stanford University	3, 10, 45, 56

State University of New York - Binghamton	68

State University of New York - Buffalo	23

State University of New York - Stony Brook	14, 33, 34

Stevens Institute of Technology	43

Texas A & M University	7, 25, 29, 70

Tufts University	50

University of Arizona	13, 19

University of California - Berkeley	3, 19, 26, 33

34, 39, 45, 46, 56

University of California - Davis	19, 34

University of California - Irvine	19, 33, 57

University of California - Los Angeles	3, 20, 33

University of California - San Diego	3, 15, 20, 26

48, 55, 65

University of California - Santa Barbara	8, 10, 48

University of California - Santa Cruz	8, 12, 20, 65

University of Colorado	4, 20, 36, 65, 66

University of Florida	4, 40, 66

University of Illinois	5, 13, 21, 30, 34, 41, 42, 57

University of Iowa	10

University of Kentucky	66

University of Maryland	45, 46, 47, 66

University of Massachusetts	10, 22, 67

University of Massachusetts - Dartmouth	67

University of Michigan	9, 10, 22, 23, 57, 59, 68

University of Minnesota	37, 38, 47, 49, 59

University of North Carolina	55, 60

University of North Carolina - Charlotte	9, 12

24, 69

University of Notre Dame	42

University of Oregon	60

University of Pennsylvania	16, 29, 38, 56, 69

University of Pittsburgh	6

University of Rhode Island	13, 25

University of Rochester	44

University of South Carolina	29

University of South Florida	13, 27

University of Southern California	4, 20, 26, 36

University of Tennessee	71

University of Texas	11, 14, 50, 70

University of Utah	7, 16, 61, 70

University of Virginia	7, 8

University of Washington	8, 13, 14, 15, 25, 46, 58

University of Wisconsin	11, 25, 39, 58

University of Wyoming	51

Virginia Polytechnic Institute

and State University	11

Washington State University	35, 44

West Virginia University	71

Western Michigan University	71

William Marsh Rice University	39, 43

Yale University	4