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 (ACS) 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 Division (MIPS) 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 1993. This report lists only those projects funded using Fiscal Year 1993 dollars and hence does not list multi-year awards initiated prior to Fiscal Year 1993.

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

Program Pie Charts	xii

Summary	xiii

Design, Tools and Test	1

The Program	1

Initiatives and Opportunities	2

Awards	3

Theory	3

Design Automation - Generic	4

Design Automation - Applications	9

Testing - Generic	12

Testing - Applications	14

Simulation	15

Microelectronic Systems Architecture	19

The Program	19

Initiatives and Opportunities	20

Awards	21

Technology Driven Architecture	21

Application Driven Architecture	28

Workshops and Conferences	32

Circuits and Signal Processing	33

The Program	33

Initiatives and Opportunities	34

Awards	35

Circuits	35

One-Dimensional Digital Signal Processing	36

Multidimensional Digital Signal Processing	39

Digital Representation	44

Implementation	47

Miscellaneous	48

Experimental Systems	51

The Program	51

Initiatives and Opportunities	52

Awards	53

Graphics and Solid Modelling	53

General Purpose Computing	54

Application Specific Computing	57

Other	59

Systems Prototyping and Fabrication	61

The Program	61

Initiatives and Opportunities	62

Awards	63

Systems Prototyping and Fabrication	63

Education	70

Index of Presidential Young Investigators	71

Index of Research Initiation Investigators	73

Index of Principal Investigators	75

Index of Institutions	79

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

The objective of the Design, Tools and Test Program is to obtain 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;

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

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

The HPCC initiative in MIPS builds on the support of the Application Specific Computing Systems work and represents a major extension of the research to encompass the broader class of general high performance computing systems.

Research on high performance computing systems is responsive to such major drivers as: technology, applications and new ideas. To make advances in this area that can be effectively exploited, requires that experimental systems be built quickly and cheaply and new kinds of design tools be developed and supplied to the research community to enable this to occur. 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.

Each of the programs in MIPS plays an important role in this initiative.

The Microelectronic Systems Architecture Program seeks to provide new architectural ideas and technological innovations by exploring novel architectures capable of high performance.

The Experimental Systems Program concentrates on the prototyping, experimentation with, and evaluation of promising new computer architectures and hardware/software computing systems.

The Systems Prototyping and Fabrication Program supports the development of new technologies and tools for rapid systems prototyping of experimental systems, and provides access to these technologies for the research community. This program also supports the development of educational materials and access to these new technologies for educational use in order to provide a new generation of highly qualified computing systems designers and implementors (MOSIS).

The Design, Tools and Test Program focuses on high performance computing system design tools and methodologies.

The Circuits and Signal Processing Program focuses on a wide range of signal processing problems needing high performance computing, and serves as an application driver for high performance computing research.

MIPS Directions (continued)

With less and less industrial support available for long range exploratory research on novel high performance computing systems, MIPS will play an increasingly important role in supporting such research, with emphasis on research having a wide range of potential applications. The implications for industrial competitiveness are very strong in this area.

We see the need to:

1 .	Work more closely with the applications as we move toward higher performance computing to understand the computing needs of these applications.

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

3 .	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.

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

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

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

MIPS and the Advanced Manufacturing Technology Initiative

MIPS' role focuses on Manufacturing Design, Modeling and Simulation, and on Information Technologies for Manufacturing.

Key R&D areas include:

Mathematical, Physical and Computer Models of Artifacts and Manufacturing Processes and Systems.

Integrated computer representation of the manufacturing system at all levels -material, tool, machine, cell, assembly operation, and the entire enterprise.

Advanced CAD Tools, frameworks and integrated systems for manufacturing Design.

Simulation Tools and Systems needed for representing future virtual manufacturing systems.

High Performance Application Specific Computing Systems for manufacturing .

Development of CAD tools, new fabrication technologies and techniques needed for rapid prototyping of products and manufacturing processes.

The emphasis is on research needed for developing Virtual Prototyping and extending VLSI design methodology to electromechanical parts and systems.

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	Murali R. Varanasi	mvaranas@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

4201 Wilson Blvd.

Arlington, Virginia 22230

(703) 306-1936

MICROELECTRONIC INFORMATION PROCESSING SYSTEMS

DIVISION

Experimental Systems

Design, Tools and Test

Systems Prototyping

and Fabrication

Microelectronic Systems

Architecture

Circuits and

Signal Processing

Summary

Number	Dollars

Design, Tools and Test	58	$4,116,233

Theory	7	$540,800

Design Automation - Generic	19	$1,491,051

Design Automation - Applications	10	$532,426

Testing - Generic	8	$529,458

Testing - Applications	7	$556,528

Simulation	7	$465,970

Microelectronic Systems Architecture	49	$3,788,560

Technology Driven Architecture	32	$2,873,490

Application Driven Architecture	16	$903,470

Workshops and Conferences	1	$11,600

Circuits and Signal Processing	54	$4,032,372

Circuits	3	$253,223

One-Dimensional Digital Signal Processing	14	$1,083,818

Multidimensional Digital Signal Processing	19	$1,397,639

Digital Representation	8	$732,810

Implementation	6	$273,238

Miscellaneous	4	$291,644

Experimental Systems	27	$7,072,859

Graphics and Solid Modelling	5	$785,814

General Purpose Computing	13	$3,468,737

Application Specific Computing	7	$2,713,808

Other	2	$104,500

Systems Prototyping and Fabrication	28	$2,230,633

Systems Prototyping and Fabrication	26	2,125,157

Education	2	105,506

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 used 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 on design of integrated circuit (IC) chips and systems. Emphasis is on automating the design process in new, existing and mixed technologies. Research topics include: Theoretical Foundations of IC Chip and System Design; Models, Algorithms and Methodologies; Tools and Frameworks for Designing IC Chips and Systems; Design Synthesis; Simulation of Designs; Design testing and Validation.

Theory and Foundations - computational models and algorithms for design tools in advanced technologies.

Synthesis - layout, logic, and high level synthesis, synthesis for performance and testability, synthesis with formal verification, hardware-software co-design; design of mixed signal and asynchronous systems.

Simulation - numerical and symbolic simulation as techniques for evaluating designs before manufacture.

Testing - identification and evaluation of manufacturing test methods; integrating IC testing with diagnosis, reliability and system test; testing large designs; and models for detection of realistic failure modes.

DRIVING FORCES

The technology of VLSI/ULSI circuits has changed significantly in the last five years. Examples are: 100K to 3M transistors per chip and speed increase from 20MHz to 200MHz. In addition demands for deployment of substantially more computing systems of greater complexity and higher performance are increasing. These must be high integrity, fault tolerant, and trusted. As a result, there is a substantial need for Electronic Design Automation (EDA) infrastructure because interfaces, applications, and advanced computing systems will devour VLSI designs.

These advances in technology make it possible to design a system on one or a few chips, which makes the design process far more complex. The higher operating and switching speeds make electrical effects more pronounced, thus causing a new dimension in EDA design.

Manufacturing costs go up at an exponential rate. Designers now need tools that factor in manufacturing parameters, such as yield, into the design equation. Again automation is a must since designers cannot be expected to know details of manufacturing.

Competitiveness requires that the product design cycle be reduced to allow rapid prototyping of hardware designs, and that factors such as cost and operating environment be accounted for.

TOPICS

Theory creates intellectual foundations for the design of ICs and systems. It explores the capabilities and limits of computing in the VLSI/ULSI medium. The goal is to find fundamentals for design of future ICs and systems.

Synthesis research is focused on tools and algorithms for automating the IC and system design processes. This includes design synthesis at all levels, hardware-software co-design, design frameworks, synthesizing testable designs, design of asynchronous and mixed signal circuits, and tools for formal methods for proving properties of designs.

Testing starts with design verification and continues during the lifetime of the system. Research includes: design validation, manufacturing test, integrating IC test with system test and diagnosis; and models for detection of realistic failure modes.

Research in functional and electrical simulation are supported. Speed and efficiency in solving the circuit equations are important, especially in light of larger designs and the need to account for more electrical effects.

Initiatives and Opportunities

There are many opportunities and Special Programs that are available through the DTT Program. The Special Programs include:

Advanced Manufacturing Technology (AMT)

High Performance Computing and Communications (HPCC)

Software Capitalization Grants

Small Grants for Exploratory Research (SGER)

Research Experiences for Undergraduates (REU) Supplements

Topics which are pertinent to the HPCC and AMT initiatives include:

*	Application of EDA theory, tools and methods to the AMT area.

*	Models of computation which reflect the specific needs of high performance computing, or of AMT. (e.g. high density, high speed)

*	Algorithms and tools for solving HPCC or AMT system design problems.

*	High performance system synthesis, including interconnect problems for systems of chips, on-chip data management, design validation, and test.

*	Tools for creating designs with novel features that may occur in HPCC and AMT systems.

*	Parallelism as a model of computation for electrical and optical mediums.

*	Validation techniques, such as proving correctness of critical parts of a design, timing analysis, electrical and functional simulation, system test techniques and testing high-speed high-density chips.

*	Accurate simulation of material/device electrical properties under high frequency excitation.

Software Capitalization activities include distributing EDA tools developed in an academic research environment; and upgrading laboratory or prototype software.

Awards

Theory

University of Florida; Sartaj Sahni; High Performance Solutions to VLSI CAD Problems; (MIP-9103379 A01); $92,329; 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Northwestern University; Majid Sarrafzadeh; Algorithm Design for VLSI Layout; (MIP-9207267 & A01); $115,000; 24 months.

The research is in four areas of geometric algorithms for design tools. The research topics are:

1.	floor planning by graph dualization;

2.	placement of modules by exploiting circuit regularities;

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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of Minnesota; Clark Thomborson; Algorithms for VLSI Design; (MIP-9023238 A02 & A03); $71,502; 12 months.

The theory underlying optimal adder design and global wire routing is well understood, so the focus is on implementation issues. Experimental software is being developed to determine optimal adders. Attention is being paid to tradeoffs between the smallest area, fastest, and least power adders. The feasibility of using large linear programs to solve the problem of routing wires on chips and modules is being investigated. Theoretical work is on the problem of finding minimum length tree shaped interconnections (Steiner trees) among a set of terminals on a VLSI chip. Rendering grey-scale images on a monochrome display terminal or laser printer is being explored. Algorithms, amenable to speedup on parallel or pipelined computers, are sought.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

New York University; Robert Paige and Jaizhen Cai; A Transformational Programming Environment for Hardware Specifications; (MIP-9300210); $50,000; 12 months.

This research is on testing the feasibility of a transformational methodology, previously used only for software productivity improvement, within the context of hardware specification and synthesis. The research involves the designing and implementing a transformational environment for a hardware specification and synthesis language. This environment supports VHDL-like specifications, symbolic analysis of these specifications, and correctness preserving source-to-source transformations. Two applications are being carried out. The first emphasizes automatic hardware design in which the system is used to transform algorithmic level hardware specifications into register transfer level implementations. The second application deals with hardware verification by automatic linear time model checking using a subset of temporal logic.

This grant is made under the Small Grants for Exploratory Research (SGER) program.

State University of New York - Stony Brook; Armen Zemanian; VLSI/ULSI Parameter Computations; (MIP-9200748); $50,000; 24 months.

This research is on three dimensional modeling methods for predicting performance and characteristics of VLSI-ULSI circuits and devices. The research topics are:

1.	three dimensional corner corrections for capacitance calculations;

2.	inductance computations and transmission line parameters; and

3.	dominant paths in interconnect networks including path ranking. These computations are needed for assessment of delay times in off-chip interconnection lines and for modeling pulse propagation through MOSFET circuits. The approach is to use infinite electrical network theory to simplify the computation of coupling between interconnection lines and adjacent devices. This theory leads to efficient numerical methods, including domain contraction techniques, which yield more powerful computation algorithms.

University of Virginia; James P. Cohoon and Jeffrey S. Salowe; Next Generation Research in Physical Design; (MIP-9107717 A02); $99,469; 12 months.

This research takes an integrated look across the physical design activities of partitioning, floorplanning and routing. The work has two components, routing and partitioning. In routing, algorithms for generalized multi-layer and multi-net routing are being explored. 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 Washington; Steven M. Burns; NYI: A Design Language for Asynchronous Circuit Synthesis; (MIP-9257987 A01); $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. The research consists of 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 - Generic

Stanford University; David Dill; PYI: Automatic Verification of Finite-State Concurrent Systems; (MIP-8858807 A05); $62,500; 12 months.

Research is on the verification of finite-state concurrent systems, both abstract systems and their implementations in hardware. The approach is to represent the set of states as a boolean function in the form of a binary decision diagram, then find and inspect the set of states reachable from a set of initial states. A protocol description language and a verification system are being developed and tested on real-world designs. Additionally, effort is being made to characterize conditions under which verification is particularly attractive, for example using it in the initial design phase when the system is abstract. Several benchmark examples for other users are being developed.

University of California - Berkeley; Ernest Kuh; Design Methodologies for High-Density, High-Performance, Wire-Dominated Chips and Multichip Modules; (MIP-9117328 A01); $200,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). Integrated circuit (IC) design is now dominated by wires which can no longer be considered as perfect conductors.

The long term goal of this research is to find a new CAD methodology for designing high-performance large and dense circuits which have a large portion of the physical layout occupied by the wires. New algorithms with major emphasis on ability to handle efficiently very large problem instances are being developed. These include algorithms for the problem of extended floor-planning; such as, performance-driven partitioning, timing simulation including transmission lines, clock skew optimization, routing and compaction. Also being developed are algorithms to solve problems which span the boundaries of several of these classical problems and explore dependencies which were previously not studied. Much of this research is common to high performance design of both high-density chips and multichip modules.

University of California - Davis; Venkatesh Akella; RIA: High-Level Synthesis of Self-Timed Circuits ; (MIP-9308668); $100,000; 36 months.

This research is focused on developing a systematic approach for high-level synthesis of self-timed circuits. The framework for the research is a set of design tools (SHILPA) that produces macro cell based realizations of circuits from behavioral descriptions. Research problems include the following:

1.	techniques for resource sharing based on flow analysis;

2.	efficient partitioning of a sequential specification into a set of communicating sequential processes;

3.	development of a tool for gate-level realizations of asynchronous circuits in SHILPA; and

4.	investigating graphical and VHDL interfaces to SHILPA.

University of California - Irvine; Nikil Dutt; RIA: Design Conceptualization for High Level Synthesis of Hardware; (MIP-9009239 A02); $5,000.

This research is on a framework for IC circuit and system design, which uses a mixed media approach to aid engineers in modeling designs for high level synthesis. Design tools are being built on top of a graphical input language and a tabular intermediate representation. The representation uses a general design model that includes synchronous and asynchronous behavior, timing constraints and protocols between communicating designs. Specific research tasks are:

1.	An environment for high level synthesis whi ch provides multiple input media for design conceptualization and capture;

2.	Inclusion of partially designed structures and user bindings into the environment;

3.	Modeling guidelines for design description in VHDL which support high level synthesis and simulation.

This supplement provides support for a minority graduate student.

University of California - Irvine; Daniel Gajski; System Synthesis From Specification Charts; (MIP-8922851 A03); $19,806.

Research is on system synthesis where specifications are expressed in terms of a graphical language called "specification charts". It has sufficient expressive power to describe IC systems in terms of activities initiated and terminated by events. Topics are:

1.	definition of the specification charts languag e;

2.	determining how to translate the language into VHDL;

3.	algorithms for partitioning the specifications into system components (e.g. chips) and for quality estimations using system quality measures;

4.	incorporation of interface synthesis into system synthesis; and

5. evaluation of the tools being developed.

This grant includes support for NSF-ESPRIT cooperation.

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

Synthesis and Mapping are necessary steps in designing Field Programmable Gate Arrays (FPGAs), and this research is a systematic study of these problems in look-up table based FPGA designs. Questions being investigated include: effects of node duplication, effects of depth relaxation, and effects of logic resynthesis during mapping and system-level partitioning mapping in multiple chip FPGA designs. Algorithms being developed are:

1.	for computing optimal or near optimal synthesis or mapping solutions under a give n objective function; and

2.	for synthesizing a set of mapping solutions of smooth trade off between various design objectives, such as area, delay and routability.

Computational methods for integrating the synthesis and mapping steps in FPGA designs based on combinatorial and Boolean optimization techniques are being investigated.

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

The unifying theme of this research is that the underlying geometries, embedding dimensions and topological representations of CAD designs, together afford a perspective for effective algorithm design. The research is in three areas.

1.	Performance-driven synthesis at various leve ls of design, including clustering for proble m decomposition and 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 geomet ry in the associated cost surfaces. This includes time-bounded stochastic optimizations, and a non-monotone class of annealing methods.

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

University of Colorado; Gary Hachtel, Michael Lightner and Fabio Somenzi; Synthesis and Verification of Combinational, Sequential and Behavioral Logic; (MIP-9115432 A02 & A03); $293,064; 12 months (Joint support with the Advanced Research Projects Agency - Total Grant $654,865).

This a joint project with Colorado, (G. Hachtel, M. Lightner and F. Somenzi), UC, Berkeley (R.K. Brayton, A.R. Newton and A. Sangiovanni-Vincentelli), and Stanford (G. 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 are:

1.	Performance oriented synthesis through realistic modeling and delay/area tradeoff optimization;

2.	Maximization of testability; and

3.	Exploiting partitioning to solve both chip and multi-chip module design problems.

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 to support a variety of applications;

2.	design, synthesis, and formal approaches based on the theory and algorithms;

3.	design of embedded controllers, including hardware-software co-design; and

4.	application of logic techniques to "non-standard" 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of Illinois; C. L. Liu; Research in Computer-Aided Design of VLSI Circuits; (MIP-9222408 & A01); $91,000; 24 months.

The research is on algorithms for high level synthesis and layout of VLSI CAD designs. Algorithms for complex, large industrial type design problems are being developed. Research topics include:

1.	high level synthesis with testability as an important goodness measure,

2.	timing driven placement algorithms for EPGAs, and

3.	channel and switchbox routing in which the effect of cross talk is to be taken into consideration.

For the first problem, the effect of register allocation and functional unit binding on the testability of the circuit is being examined. Then the scheduling step is being examined. Research on the second problem is based on the notion of a "neighborhood graph" which is used in guiding an iterative improvement algorithm that produces placements which satisfy given timing constraints. An integer programming approach is being used for the third problem, because this avoids parallel long wires that are close together in the routing solution.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Indiana University; Steven Johnson; Decomposing Digital-System Specifications Into Interacting Sequential Processes; (MIP-9208745 & A01); $142,196; 24 months.

This research is on developing formal techniques to decompose higher-level system specifications into interacting sequential processes. A functional algebra is used for defining formal representations and building a set of transformations for manipulating them. The notion of "interaction schemes" is the central subject. The project is composed of four activities:

1.	theoretical studies of the decomposition of digital systems; especially formal derivation of control-synchronization and data-communication protocols;

2.	automation of formal transformations which correctly do sequential decompositions;

3.	integration of the mechanized formal system with available CAD tools, and other reasoning systems; and

4.	application of the design system to meaningful examples of digital-system designs.

Massachusetts Institute of Technology; Srinivas Devadas; NYI: Formal Methods for Hardware and Software Verification; (MIP-9258376 A01); $62,500; 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 useful Boolean representations of circuits and efficient 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 efficiently 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.

University of Massachusetts - Amherst; Premachandran Menon; Optimization of Multilevel Logic; (MIP-9311185); $51,771; 24 months (Joint support with the Circuits and Signal Processing, Microelectronic Systems Architecture and Systems Prototyping and Fabrication Programs - Total Grant $92,444).

This research is on the development and implementation of optimization techniques for multilevel combinational logic circuits specified at the gate level. Logical implementation techniques which have been proven effective in test pattern generation are being used for this purpose. These techniques are being applied to three problems in logic optimization: area reduction, delay reduction, and testability enhancement. Relationships between signal values are being used to identify common subfunctions without generating expressions for them and putting them in any standard form. This approach is efficient and could substitute for Boolean factorization in logic optimization. Techniques for delay reduction involve replacing segments of long paths with shorter ones so that false paths are not created and undetectable faults are identified during delay reduction. The effectiveness of these techniques as supplements to an existing synthesis system are being investigated.

Princeton University; Sharad Malik; RIA: Accurate and Efficient Timing Verification of Synchronous Digital Circuits; (MIP-9209805 A01); $5,000.

This research is on verifying the temporal correctness of synchronous digital systems. The emphasis is on obtaining accurate, efficient algorithms within the paradigm of certified timing analysis. This combines the efficiency and coverage of timing analysis with the accuracy of timing simulation. Vectors that sensitize the long paths in the combinational parts of the circuit are generated by timing analysis. These are then used in timing simulation. The research addresses the problem that in order to provide these vectors, timing analysis must consider the functionality of the circuit components.

This grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.

Princeton University; Wayne Wolf; Control Minimization and Performance Optimization for High-Level Synthesis; (MIP-9121901 A02); $64,740; 12 months.

Research is on the relationship between high-level control specifications and the finite state machine (FSM) implementation of that control. 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 complex control systems.

The approach is to use the behavior FSM, 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 developed for compaction on a cylinder are being used to move both simple outputs and branches to minimize the number of states around cycles in a behavior state transition graph.

This grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.

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

This research concerns the development of algorithms and software 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.

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

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. This research is on an alternative approach based on temporal logic model checking. In this approach 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. The technique has been used in the past to find subtle errors in a number of non-trivial designs.

Pennsylvania State University; Barry M. Pangrle; Control and Layout Issues in Performance-Driven, High-Level Synthesis; (MIP-9118440 A01); $60,012; 12 months.

This research is focused on two problems of high level synthesis, 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 of the datapath components, the control logic, and the routing.

University of Pittsburgh; Steven Levitan; Temporal Specification Verification; (MIP-9102721 A01); $68,885; 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 primarily 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 modules. The verification process is based on a 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.

University of Utah; Erik Brunvand and Ganesh Gopalakrishnan; The Design of Asynchronous Circuits and Systems with Emphasis on Correctness and Proven Optimizations; (MIP-9215878); $77,577; 24 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $155,154).

This research merges two efforts in asynchronous circuit compilation. These are the work of Gopalakrishnan on the language hopCP and its use in verification; and the work of Brunvand on asynchronous circuit compilation. The research is:

1.	enhancing the expressive power as well as the semantic clarity of concurrent hardware description languages for asynchronous circuits and systems;

2.	extending the formal basis for compiling from HDL's to circuit designs;

3.	formally characterizing and improving the optimizations used in asynchronous circuit compilation; and

4.	studying the performance of implemented circuits with regard to a variety of parameters.

Design Automation - Applications

Tanner Research; John Tanner; Analog VLSI Neural Network Employing A Novel Linear Synapse; (ISI-9307452); $249,936; 24 months.

This is SBIR Phase II research on designing a synapse for a neural network (NN). During Phase I the company devised a novel synapse circuit, which is linear over a range that is 10 times that of previous state-of-the-art circuits, and half the size of previous circuits. Also a NN for the chip was designed. During Phase II, the company is designing and testing the remaining network elements and improving the synapse. A full scale prototype chip that implements on-chip learning, and contains up to 650,000 synapses is being developed. The chip design enables interconnection of several chips in order to form a multi-layer network. In addition a prototype back propagation network which will integrate all network elements on a single chip and allows interconnection of at least two chips is being designed.

University of California - Berkeley; Jan Rabaey; High Level Synthesis Techniques for VLSI; (MIP-9222254); $4,981; 12 months (Joint support with the Circuits and Signal Processing and the Systems Prototyping and Fabrication Programs - Total Grant $14,944).

A number of powerful high level synthesis environments have been proposed in the area of real time signal processing, both in Europe and the United States. Most existing tools span only restricted application domains or very specific architectural styles. The goal of this research is to boost the field of high-level synthesis for digital signal processing by bringing together researchers from the IMEC Research Center at Leuven, Belgium and the University of California at Berkeley. This promotes exchanging synthesis techniques and tools, and addressing the global architectural domain. This cooperation will result in the training of researchers with a wider vision and scope of expertise in the field of high level synthesis.

This grant includes support for NSF-ESPRIT cooperation.

University of California - Santa Cruz; Wayne W. Dai; PYI: Computer Aided Design for VLSI Circuits; (MIP-9058100 A03); 12 months (Joint support with the Systems Prototyping and Fabrication 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 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 planer 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of California - San Diego; Alex Orailoglu; RIA: Synthesis of Self Recovering and Fault Secure Micro-architectures; (MIP-9308535); $100,000; 36 months.

This research is on automatic synthesis of fault-tolerant micro-architectures. Two areas are being investigated. One is an exploration of methodologies and CAD tools for synthesis of self-recovering micro-architectures. The model for self-recovering designs is a flow-graph representation in which partial results from two copies of the graph are periodically compared at a checkpoint. Research is on scheduling, allocation, binding, and checkpoint insertion. The second is an investigation of techniques automatic synthesis of fault-secure micro-architectures. Salient features of the research are: algorithms for region delineation so as to ameliorate hardware bottlenecks, and region scheduling so as to relax and weaken precedence constraints between regions.

Georgia Institute of Technology; Abhijit Chatterjee; RIA: Design Tools for Reliable Computations in Digital Signal Processing and Control VLSI; (MIP-9309740); $96,954; 36 months.

This research concerns the development of algorithms and software tools for synthesizing signal processing and control circuits that can perform highly reliable computations under adverse conditions. This is achieved by the use of both off-line (passive) and on-line (active) method. The approach is to extract mathematical models of circuit behavior from high-level descriptions of circuits, and then operate on them with numerical algorithms. These in turn generate a group of architectural specifications that are functionally equivalent. Design optimization is achieved by transformation of the multiplier constants and restructuring of the circuit flow graphs. The optimizations are carried out so as to maintain high levels of testability and fault-tolerance without regard to cost criteria such as node activity.

University of Illinois - Urbana; Farid Najm; RIA: Synthesis of Reliable and Low-Power VLSI Circuits; (MIP-9308426); $100,000; 36 months.

This research is on synthesis algorithms for design of reliable, low power CMOS and BiCMOS VLSI designs. The basis for the research is to use boolean transition density to measure deviant activity and thus to help solve power consumption and reliability issues. Research activities include:

1. exploring use of circuit activity as a parameter to be minimized; and

2. investigating the effects of minimizing local power dissipation on circuit design.

Algorithms incorporating these new optimization ideas are being developed and integrated into a synthesis environment. The environment integrates the objectives of optimizing area, performance, testability, reliability, and power into a unified set of design algorithms.

University of Michigan; Karem Sakallah, Trevor Mudge and Edward Davidson; Timing Verification and Optimal Clocking of Latch-Controlled Synchronous Digital Circuits; (MIP-9014058 A02); $37,000; 12 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $127,660).

This research is on the temporal modeling of latch-controlled synchronous digital systems. The use of level-sensitive latches, as opposed to edge-triggered flip-flops, has become quite common in recent years because latches are easily implemented in MOS VLSI, the leading technology for building digital systems. A consistent theoretical framework for describing the timing constraints which must be satisfied by such systems for proper operation is being developed. This framework is being used to develop efficient algorithms for timing verification and optimal clocking.

Both of these problems require the solution of large linear programs (LPs). The special structures of these LPs will be utilized to reduce the solution time so that the algorithms can be used in an interactive design environment. The practical significance of this framework and associated algorithms is being assessed experimentally on actual industrial VLSI designs.

University of Minnesota; Eugene Shragowitz; Fuzzy Logic Approach to Physical Design of VLSI and PCB; (MIP-9123945 A01); $48,448; 12 months.

In this research fuzzy logic is being applied to reasoning about problems of VLSI physical design and printed circuit boards (PCB). This includes identification of important factors for each problem, selection of linguistic variables, formulation of the membership functions for linguistic values in fuzzy sets and formulation of the decision rules. A fuzzy logic model of timing-driven placement, where area, timing, and routability may become conflicting goals is being developed. This model incorporates timing analysis and prediction, especially pre-layout prediction of path and net criticality, and weight functions for nets in computation of timing bounds. A second fuzzy logic model for placement of cells on a VLSI chip in the presence of conflicting goals is being developed. The model is being adapted to PCB placement, taking into account parameters such as connectivity, timing, transmission line effects, routability, and thermal impact. Experiments with the algorithms on benchmark circuits are being performed.

Carnegie Mellon University; Donald Thomas and Daniel Siewiorek; Digital System Level Synthesis Tools; (MIP-9112930 A03 & A04); $135,042; 12 months (Joint support with the Systems Prototyping and Fabrication Program - Total Grant $260,084).

This research is on algorithms and techniques for system-level synthesis of digital electronic systems. Inputs to the system are intended to be high level specifications in terms of system behavior. Research builds on two existing design systems; the system architects workbench, and a microcomputer board design system, called MICON. Research issues being investigated are: partitioning specifications for appropriate style selection, synthesis - including learning and problem solving approaches, internal representation of design information, system level design representation and human interface, and controlled iteration with different types of synthesis tools (design process control). The algorithms are being integrated into a prototype system-level synthesis framework.

This grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.

Carnegie Mellon University; Roy M. Maxion; Discovering Information in Large, High-Dimensional Databases; (IRI-9224544); $10,000; 12 months (Joint support with the Database and Expert Systems Program, the Knowledge Models and Cognitive Systems Program, the Experimental Systems Program and the Statistics Program - Total Grant $140,000).

This research is on discovering functional relationships among high-dimensional data associated with manufacturing, such as VLSI production. In this case, hundreds of variables must be precisely controlled to achieve high-quality yield. This research is investigating a number of new ideas for high-dimensional, nonparametric regression which are largely untested with respect to their comparative performance in realistic situations. A large-scale simulation experiment is being performed to evaluate the effects of sample size, dimensionality, signal-to-noise ratio, and various underlying functions on the integrated mean squared error of the fitted model. The results of the study are being used to determine when each of the proposed models is most valuable. This research is being applied 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.

Testing - Generic

Colorado State University; Carol Q. Tong; Detection of Multiple Faults Using SSFTS in CMOS Logic Circuits; (MIP-9307538); $17,985; 18 months.

A research program on the use of single stuck-at-fault test sets (SSFTS) to detect multiple faults and their combinations in CMOS VLSI circuits is being planned. Preliminary results are being simulated and extended to more complex fault conditions. Also, circuits under consideration are being expanded from combinational to sequential circuits, both synchronous and asynchronous. A fault model that permits use of both voltage and current in detecting faults is being formulated.

This is a Research Planning Grant for Women Scientists and Engineers.

Yale University; Debashis Bhattacharya; Efficient Parallel Techniques for Hierarchical Fault Simulation and Test Generation; (MIP-9101966 A01 & A02); $72,802; 12 months.

This research is on:

1.	hierarchical fault simulation in coarse-grain MIMD parallel computers or distributed systems; and

2.	parallel test generation on MIMD parallel machines with and without shared memory.

An investigation of 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 is 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 explored 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 Iowa; Irith Pomeranz and Sudhakar M. Reddy; High-Quality Tests for Combinational Circuits; (MIP-9220549); $164,586; 24 months.

This research is on finding procedures to derive compact or small test sets that cover a comprehensive set of modeled faults, required to achieve high reliability of manufactured VLSI chips. A fault model that allows uniform representation of various fault models is being explored as the basis for generating small, yet comprehensive test sets. A set of tools to deal with different aspects of testing quality for combinational and fully scanned sequential circuits is being built. These are:

1.	generation of small test sets for a comprehensive set of faults, including efficient treatment of path delay faults;

2.	design for testability to allow faults undetectable in the original to be detected in a modified circuit; and

3.	built in test pattern generation based on the test sets produced when stored pattern tests cannot be used.

University of Iowa; Irith Pomeranz; PYI: A New Search Strategy for Design Automation; (MIP-9357581); $25,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 that require two pattern tests.

University of Michigan; John Hayes; Testing Complex Systems with Reusable Tests; (MIP-9200526 A01); $91,539; 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.

Theorems and algorithms are being developed.

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

The research is in various facets of 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 for ATPG; parallel algorithms for ATPG; 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.

University of Texas; Jacob Abraham; Fault Modeling and Test Generation for Mixed-Signal Integrated Circuits; (MIP-9222481 A01); $8,046.

This research is on fault modeling and test generation for mixed signal integrated circuits. In the area of fault models, 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.

This grant includes support for NSF-ESPRIT cooperation.

Virginia Polytechnic Institute; James Armstrong and Walling Cyre; Rapid Development and Testing of Behavioral Models; (MIP-9120620 A01); $87,000; 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" as a base 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. Behavioral models are being expressed in the high-level language, VHDL.

Testing - Applications

Auburn University; Adit Singh; Exploiting Defect Clustering Information in VLSI Testing; (MIP-9208928 A01); $55,902.

This project is investigating the use of information about defect clustering on wafers to make yield predictions for individual dies based on test results for neighboring dies. The hypothesis is that defects on a wafer are clustered, thus most good dies are close to other good ones and most defective dies are close to others. Clustering information can then be used for targeting particular tests to individual dies on the wafer. Simulations using wafer defect distribution data from the published literature is being employed to assess the viability of the approach. Accurate models to predict defect levels attainable are being developed and strategies for testing dies on the wafer are being determined.

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

The focus here 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 A03); $86,960; 12 months.

This research is based on an automatic test pattern generation (ATPG) 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.

University of Massachusetts - Amherst; Israel Koren; Topological and Physical Layout Design Techniques for Yield Enhancement; (MIP-9305912); $204,000; 36 months.

This research is on design tools which can compensate for manufacturing yield losses due to the complexity of the logic. Preliminary results have shown that yield can be enhanced by the technique of reducing the sensitivity of the chip to point defects. Yield optimization algorithms and techniques which are applicable to the last two stages of design - topological/symbolic, and physical layout are being explored. Physical layout strategies for yield enhancement in the channel routing and compaction phases for standard cell designs are being investigated. Yield enhancements in topological designs are being illustrated through PLA-based designs.

University of Rhode Island; Jien-Chung Lo; RIA: Entering an New Era of Low Cost Concurrent Error Detecting Digital System Designs in CMOS VLSI ; (MIP-9308085); $45,000; 36 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $90,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, those that are detectable by the current sensor and those that are not, are being developed. New design rules for hardware redundancy are being explored.

Virginia Polytechnic Institute; Dong S. Ha; Software Capitalization: CAD Tools for VLSI Circuit Testing; (MIP-9310115); $38,566; 12 months.

Four fault simulators and automatic test pattern generators (ATPGs), produced in research projects at the Virginia Polytechnic Institute, are being developed and enhanced so as to bring them into a state for distribution to general users. These tools are:

1.	FSIM, combinational circuit fault simulator;

2.	HOPE, a synchronous sequential fault simulator;

3.	ATALANTA, an ATPG for stuck-at faults in combinational circuits; and

4.	SOPRANO, an ATPG for stuck-open faults in combinational circuits.

This grant is made under the Software Capitalization Program.

University of Wisconsin; Kewal Saluja; Test Algorithms for Physical Neighborhood Pattern Sensitive Faults in Reconfigurable Rams; (MIP-9111886 A02); $63,600; 12 months.

This research addresses testing large, reconfigurable random access memories for faults due to certain patterns originating in the physical neighborhood of a memory cell. These are pattern sensitive faults (PSF). Current methods do not deal with 5 and 9 cell neighborhoods, and are complex.

In this research, necessary and sufficient conditions to test check bits for neighborhood pattern sensitive faults are being developed. Based on these results, algorithms to test for 5 and 9 cell physical neighborhood PSFs in random access memories (RAMs) are being designed. These algorithms deal with the cases where logical and physical address spaces are not identical, memories are reconfigured, and where built in error detection and correction techniques are employed. The use of these algorithms for built in self test implementation is being explored.

Simulation

University of Arizona; Olgierd Palusinski; Techniques for Accelerated Simulation of Electronic Circuits and Systems; (MIP-9017037 A02, A03 & A04); $59,970; 12 months.

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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

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

This research is on simulation techniques and modeling approaches for analog circuits. Accuracy of the analysis is the key goal. 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 include sigma-delta modulators, phase-locked loops, and switched capacitor circuits among others.

Massachusetts Institute of Technology; Jacob K. White; PYI: Simulation of Switching Filter and Phase-Lock Loop Circuits; (MIP-8858764 A05); $25,000.

This research is on three topics in modeling, analysis, and simulation of high-frequency circuits and devices:

1.	Multipole accelerated 3-D interconnect analysis;

2.	Simulation of clocked analog circuits; and

3.	Simulation for micro-electro-mechanical (MEM) devices.

For the interconnect analysis, multipole-accelerated approach to circuit analysis is being applied to problems of determining effective and accurate methods to simulate cross-talk effects, and perform inductance extraction. In simulation of clocked analog circuits, algorithms for detailed simulation of switched-capacitor filters and switching power converters are being developed. Initial work in MEM device simulation explores simulating interactions between mechanical, electrostatic and fluidic forces, while simultaneously accounting for the behavior induced by the external circuitry. Algorithms for analyzing both static and transient behavior are being investigated.

Washington University; Roger D. Chamberlain; RIA: Partitioning of VLSI Systems for Distributed Simulation; (MIP-9309658); $90,000; 36 months.

This research is on approaches to partitioning VLSI systems for distributed simulation on multiprocessor architectures. The approach is to use knowledge of a VLSI system and the distributed simulation algorithms to perform a partitioning and assignment of system components to processors in a manner that minimizes the execution time of the distributed simulation. Central to the approach is an initial partitioning that is refined as information is gathered about the simulation workload. In this way assignment of components to processors can take advantage of measured data that is unknown (and therefore unavailable) prior to the simulation run. The approach has three phases:

1.	Algorithms for initial partitioning of the circuit components are being developed;

2.	Means of assigning partitions to processors are being developed; and

3.	Rules for migrating components from one processor to another are being devised.

Carnegie Mellon University; Ronald Rohrer; ADAPTS: A Comprehensive Circuit/Timing Simulation Strategy for Integrated Circuits; (MIP-9014402 A02); $66,000; 12 months.

A piecewise linear circuit timing simulator that is robust and efficient in the approximate transient analysis of lumped circuits is being developed. To better simulate the highly nonlinear bipolar and biMOS circuits, a simulation strategy to work with piecewise linear rather than piecewise constant table approximations of nonlinear device characteristics is being explored. Inductance is being included on an equal basis with capacitance.

The steady state solution computation is being made more efficient by solving for its conditions explicitly, prior to seeking the transient response that may attain it. Thus, circuit simulation is to be invoked only to obtain successive steady state conditions, but not for intermediate transient time points. To maintain transient simulation computational efficiency, explicit integration strategies that allow the exploitation of both temporal and spatial latency are being used. To insure the stability of explicit integration approximations, the computed steady state conditions are being employed to limit step size. This is intended to overcome the stiff systems problem.

The above strategies are being embodied in the SPECS (Simulation Program for Electronic Circuits and Systems) software.

University of Texas - Austin; Lawrence T. Pillage; PYI: CAD Tools for New Circuit Technologies; (MIP-9157363 A03); $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. To this end, tools which are applicable at the integrated circuit, packaging, module, and board levels without loss of generality are being developed. Specific areas being investigated are: fast extraction techniques which trade off some accuracy for efficiency; and simulation models and techniques to enable topdown 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; Andrew T. Yang; NYI: Modeling and Simulation of Advanced Microelectronics and Optoelectronic Circuits and Systems; (MIP-9257279 A01); $100,000; 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 complex nonlinear and electromagnetic effects;

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

4. Development of a technique for fast power waveform simulation based on analytic digital macromodeling, which makes the method well suited to simulating circuit netlists derived from layout extraction;

5. Fast 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.

Microelectronic Systems Architecture

Dr. J. Robert Jump, Program Director

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

The Program

The Microelectronic Systems Architecture (MSA) program supports 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.

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 software and hardware 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. Primary emphasis is placed on obtaining new architectural and design knowledge. 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 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, artifical intelligence and neural networks);

Initiatives and Opportunities

The Microelectronic Systems Architecture program is actively soliciting proposals particulary in the areas which relate to the HPCC program, and recent initiatives such as Biotechnology, Advanced Manufacturing Technology (AMT) and Advanced Materials Processing (AMP).

Possible research includes:

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

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

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

*	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); $144,439; 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 som e of the resulting networks.

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

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. Iinitial 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 mMeasurement of the memory systems of a number of machines to determine the effe ct that those memory systems have on overall system performance.

University of California - Davis; Matthew Farrens; NYI: High Performance Single Chip VLSI Processors; (MIP-9257259 A01); $62,500; 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); $12,500; 12 months (Joint support with the Circuits and Signal Processing Program - Total Grant $25,000).

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 of 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 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 - Santa Cruz; Anujan Varma; NYI: Research in High-Speed Interconnection and Switching Technologies; (MIP-9257103 A01); $75,409; 12 months.

This research aims to develop architectures and protocols for highspeed 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.

Georgia Institute of Technology; Umakishore Ramachandran and H. Venkateswaran; The Impact of Architectural Features on the Performance of Parallel Algorithms; (MIP-9200005 A01); $84,820; 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.

Georgia Institute of Technology; Umakishore Ramachandran; PYI: Architectural Issues in Parallel and Distributed Computing; (MIP-9058430 A03); $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.

University of Illinois - Urbana; Andrew Chien; High-Performance, Adaptive Routing in Multiprocessor Networks; (MIP-9223732); $95,000; 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 - Urbana; Wen-Mei Hwu; Speculative and Predicated Execution Support for Instruction-Level Parallel Processing; (MIP-9308013); $163,670; 24 months.

Speculative execution and predicated execution are two important sources of parallelism for VLIW and superscalar processors. Speculative execution tentatively executes instructions before knowing that their execution is required. Predicated execution merges multiple possible execution paths into a single path so that the hardware can simultaneously process multiple paths. Both methods allow the compiler to extract program parallelism in the presence of conditional branches. With superscalar and VLIW designs becoming increasingly popular in the microprocessor industry, these methods have become increasingly important for future high performance microprocessors to achieve their performance goals.

This project addresses three critical issues involved in incorporating speculative execution and predicated execution into future superscalar and VLIW microprocessor systems. First, the design complexity of increasing levels of architecture support for speculative execution and predicated execution are being studied. Secondly, compiler optimizers and schedulers that exploit each level of the architecture support are being developed. Thirdly, an integrated approach is being defined to coordinate speculative execution and predicated execution to best improve program execution performance. The objective is to provide architecture expertise and compiler prototypes required for the microprocessor industry to understand the cost and effectiveness of each level of hardware support.

University of Illinois - Urbana; Josep Torrellas; RIA: Characterizing and Optimizing the Performance of Memory Hierarchies in Scalable Shared-Memory Multiprocessors; (MIP-9308098); $100,000; 36 months.

This research aims at improving the performance of memory hierarchies in scalable shared-memory multiprocessors. The research uses advanced performance monitoring hardware to characterize the performance of a real scalable machine, namely the 32-processor Cedar machine developed at the University of Illinois. Data from the characterization is being generalized to other machines, and optimizations such as new algorithms or hardware support are being evaluated.

The research focuses on four research issues in memory hierarchies:

1.	the performance of cache memories and prefetch buffers under frequent vector and block traffic;

2.	the performance of Omega interconnection networks connecting the fastest layers of the memory hierarchy to global memory;

3.	dynamic page migration and replication in the memory hierarchy to increase data locality; and

4.	the cache memory performance of the operating system.

University of Illinois - Urbana; Benjamin W. Wah; Architecture Specific Resource Management via Intelligent Compilation and Strategy Learning; (MIP-9218715 & A01); $102,769; 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of Illinois - Urbana; Pen-Chung Yew, Wen-Mei Hwu and John Bruner; Improving the Performance of Scalable Shared-Memory Multiprocessors; (MIP-9307910); $106,090; 12 months (Joint support with the Experimental Systems Program - Total Grant $197,429).

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; Ahmed El-Amawy; Theory and Design of Branch-and-Combine Clock Networks; (MIP-9117206 A01); $52,162; 12 months.

A new clock distribution scheme for arbitrarily large parallel and distributed systems, called the branch-and-combine scheme, is proposed. This scheme can guarantee a constant skew upper-bound irrespective of the system size. A theoretical foundation for such schemes is developed to address other critical design issues. The model will be instrumental in establishing formal relationships among topological properties of the clock distribution networks, the timing constraints, and the upper skew bound. Other relevant issues in clock design are also being studied.

Massachusetts Institute of Technology; William Dally; PYI: Concurrent VLSI Architecture; (MIP-8657531 A07); $37,500.

This research focuses on the evaluation of the prototype MDP components, the assembly of a single-board (64-processor) J-Machine system, the revision of the MDP component design as required, and the assembly of a 16-board (1024-processor) J-Machine system. The Concurrent Smalltalk and the Concurrent Aggregates programming systems are being installed on the J-Machine and some small applications are being demonstrated.

University of Massachusetts; Maciej Ciesielski and Wayne Burleson; High-Performance VLSI Synthesis with Wave Pipelining; (MIP-9208267 A01); $65,546; 12 months (Joint support with the Systems Prototyping & Fabrication Program - Total Grant $90,546).

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 being designed, fabricated and tested to verify the feasibility of our methods and CAD tools.

Michigan State University; Lionel M. Ni, Abdol-Hossein Esfahanian and Philip K. McKinley; Multicast Communication in Multicomputers; (MIP-9204066 A01 & A02); $122,990; 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of Michigan; Karem Sakallah, Trevor Mudge and Edward Davidson; Timing Verification and Optimal Clocking of Latch-Controlled Synchronous Digital Circuits; (MIP-9014058 A02); $90,660; 12 months (Joint support with the Design, Tools and Test Program - Total Grant $127,660).

This research is on the temporal modeling of latch-controlled synchronous digital systems. The use of level-sensitive latches, as opposed to edge-triggered flip-flops, has become quite common in recent years because latches are easily implemented in MOS VLSI, the leading technology for building digital systems. A consistent theoretical framework for describing the timing constraints which must be satisfied by such systems for proper operation is being developed. This framework is being used to develop efficient algorithms for timing verification and optimal clocking.

Both of these problems require the solution of large linear programs (LPs). The special structures of these LPs will be utilized to reduce the solution time so that the algorithms can be used in an interactive design environment. The practical significance of this framework and associated algorithms is being assessed experimentally on actual industrial VLSI designs.

Wayne State University; Vipin Chaudhary; RIA: Adaptive Load Balancing for Heterogenous Distributed Systems; (MIP-9309489); $89,999; 36 months.

This project explores a new scheme for achieving load balancing in a heterogeneous distributed computing system. With the advent of optical links it is now feasible to migrate tasks from one computer to a remote computer. This scheme is being implemented and tested using real-world problems in a real heterogeneous distributed computing environment. A salient feature of the scheme is its semi-distributed, adaptive nature, i.e., the parameters taken into consideration and the algorithm for load balancing itself change during run time. The algorithm is stable, i.e., no processes are allowed to migrate without making any progress. No assumptions are made about the dependency relations of the various tasks. Various job classes with precedence constraints are allowed. Other important real-world constraints such as the inability of a process to execute on particular computers, a process needing more than one computer simultaneously for its execution, a set of processes needing to be executed on a particular subset of computers, etc., are also incorporated into the scheme. The scheme starts with an initial static load balance and then evolves into an adaptive algorithm.

University of Minnesota; David J. Lilja; New Mechanisms for Parallel Loop Scheduling; (MIP-9221900); $160,942; 36 months.

Automated assignment of separate loop iterations to different processors is a powerful technique for scheduling programs to run on parallel computers. This project is investigating four research approaches to loop scheduling: investigation of processor allocation strategies, minimization of time in loop-control critical sections, techniques for scheduling loops with large but regular execution time variations, and adaptive techniques for minimizing memory reference effects. Research methods include simulation and measurement of prototype implementations on several parallel computers.

Rutgers University; Miles Murdocca; Development of a Methodology for Implementing Hardware Dataflow Graphs Using Reconfigurable Optical Interconnects; (MIP-9224707); $245,128; 36 months.

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 - Geneseo; Rong Lin; A New Switching Mechanism for Reconfigurable Bus System Architectures and Algorithms; (MIP-9307664); $51,188; 24 months.

This project is investigating a novel parallel processing technique, shift switching, in reconfigurable bus systems. The research has four parts. The first part classifies and evaluates shift switches and their inclusion in efficient VLSI architectures. The second part develops and analyzes some efficient reconfigurable bus architectures with shift switches for such parallel computations as prefix operations, sorting, list ranking, tree search, and transitive closure. The third part investigates application-specific architectures using shift switches for computer arithmetic, image processing, and computer vision. The fourth part investigates the relation between PRAM models and reconfigurable busses with shift switching.

North Carolina State University; Wentai Liu; CMOS IC Performance Enhancement Via Wave Pipelining; (MIP-9212346 A01); $85,520; 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.

North Dakota State University; Yahui Zhu; RIA: On the Theoretical and Practical Aspects of Allocation and Scheduling for Mesh Systems; (MIP-9307594); $89,983; 36 months.

This project is a study of processor allocation and task scheduling for mesh-connected multicomputers. Parallel applications submitted to a mesh system need to be gang-scheduled on dedicated processors, which may be required to form a special structure, such as a submesh. This project is investigating both theoretical and practical aspects of mesh allocation and scheduling, using a three-phase approach. The three phases are:

1.	to develop strategies for generalized process or allocation to satisfy various application specifications;

2.	to devise and evaluate scheduling algorithms by adopting two- and three-dimensional packing heuristics; and

3.	to apply the algorithms to practical systems.

Ohio State University; Dhabaleswar K. Panda; RIA: Communication and Synchronization in k-ary n-cube cluster-c Scalable Systems; (MIP-9309627); $99,549; 36 months.

This project studies wormhole routing in clustered multiprocessor systems. A clustered system raises new communication and synchronization issues in parallel systems by deviating from the traditional assumption of one processor per node. This project addresses these issues by:

1.	developing communication algorithms for frequently used communication patterns on clustered systems;

2.	developing synchronization mechanisms and algorithms to provide concurrent intercluster and intracluster synchronization; and

3.	developing guidelines and architectural supports for interfacing processor clusters to k-ary n-cube wormhole-routed networks.

Theoretical and probabilistic analysis together with simulation experiments are being used to develop and validate the results. This research promises significant impact on the development of future clustered scalable systems supporting various programming paradigms such as distributed-memory, cache-coherent shared memory, and distributed-shared memory.

Pennsylvania State University; Tse-Yun Feng and Chitaranjan Das; Evaluation Techniques for Hypercube and MIN-Based Architectures; (MIP-9104485 A02); $89,098; 12 months.

Hypercube and multistage interconnection network (MIN)-based architectures are two promising classes of parallel computers that have received considerable attention in recent years. The objective of this research is to develop analytical evaluation techniques for predicting performance, dependability, and performance-related dependability behavior of these two classes of multiprocessors.

The performance model is based on a three-level approach - network level, task (job) level, and system level. The network level analysis gives the average communication delay which can be used in finding job completion time at the task level. Using the job completion time, system level parameters such as throughput and response time could be computed from an appropriate queing model. Dependability analysis would consider the degradation of the computing elements and communication network for finding task-based reliability or availability. The dependability model is aimed at finding a proper subcube for the execution of a task. The analysis covers both unique-path and multi-path MINs. Performance-related dependability models are being developed by associating suitable performance measures with the structure states of a multiprocessor. This project will make available a complete set of tools for analyzing these two classes of multiprocessors that have a great promise for different applications.

University of Rhode Island; Jien-Chung Lo; RIA: Entering a New Era of Low Cost Concurrent Error Detecting Digital System Designs in CMOS VLSI ; (MIP-9308085); $45,000; 36 months (Joint support with the Design, Tools and Test Program - Total Grant $90,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 design 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, those that are detectable by the current sensor and those that are not, are being developed. New design rules for hardware redundancy are being explored.

University of Rhode Island; Qing Yang; Introducing a Novel Cache Design to Vector Computers; (MIP-9208041 A01); $11,018.

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); $92,601; 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 Utah; Erik Brunvand and Ganesh Gopalakrishnan; The Design of Asynchronous Circuits and Systems with Emphasis on Correctness and Proven Optimizations; (MIP-9215878); $77,577; 24 months (Joint support with the Design, Tools and Test Program - Total Grant $155,154).

This research merges two efforts in asynchronous circuit compilation. These are the work of Gopalakrishnan on the language hopCP and its use in verification; and the work of Brunvand on asynchronous circuit compilation. The research is:

1.	enhancing the expressive power as well as the semantic clarity of concurrent hardware description languages for asynchronous circuits and systems;

2.	extending the formal basis for compiling from HDL's to circuit designs;

3.	formally characterizing and improving the optimizations used in asynchronous circuit compilation; and

4.	studying the performance of implemented circuits with regard to a variety of parameters.

University of Washington; Susan J. Eggers; PYI: Code Generation for Uniprocessors; (MIP-9058439 A03); $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 spa ce architecture.

University of Washington; Arun K. Somani; Error Detection and Recovery in High-Performance Fault-Tolerant Processor Systems Employing Caches; (MIP-9224462); $159,332; 24 months.

This is a project to mitigate the effects of transient faults in redundant computer systems that use cache memories. Redundant computer systems typically employ a voting circuit as part of the processor-memory interface to check for consistency in all bus transactions. If cache memories are used, many operations do not use the processor-memory interface, and so escape the scrutiny of the voter. In this project new cache protocols are being designed that provide for fault tolerance in redundant systems. The new protocols require the cache controllers to broadcast the contents of cache lines on occasion, and require cache controllers to respond to requests from the memory system to replace erroneous data. The project covers the development, analysis, and application of fault-tolerant cache protocols.

University of Wisconsin - Madison; Mark D. Hill; PYI: Cache Memory Design; (MIP-8957278 A04); $62,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

Arizona State University; Chaitali Chakrabarti; RIA: VLSI Architectures and Algorithms for Motion Estimation Using Hough Transform; (MIP-9309504); $99,000; 36 months.

In the past, real-time image processing has been restricted to low-level tasks such as filtering; the more complex medium and high-level tasks have been left to general-purpose computers which are unable to handle the large computation rates of these tasks. Real-time computation of these tasks thus necessitates development of task-specific algorithms and architectures. This project is developing efficient algorithms and architectures for an important and representative medium-level task: motion estimation of 2-dimensional and 3-dimensional objects. The approach reduces the number of computations in motion estimation by implementing it in the Hough space. Specifically, the objects are represented by peaks in the Hough space, and motion parameters are extracted from shifts of these peaks. To facilitate real-time computation of Hough transforms, efficient algorithms that reduce the size of the Hough transform parameter space are being developed. To keep the design costs low, these algorithms are targeted to customized versions of a "base" architecture: a highly pipelined linear array of processors, which has access to an array of memory banks. Apart from developing an efficient scheme for real-time motion estimation, this research will also provide design guidelines for algorithm and architecture development of other medium- and high-level image processing tasks.

San Diego State University; Jay Harris; VLSI Implementation of the Z-J Algorithm for Bit Error Correction; (MIP-9114270 A01); $55,508; 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.

University of California - Berkeley; John Wawrzynek; PYI: Application-Specific VLSI Architectures; (MIP-8958568 A06); $26,800; 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 Southern California; V. K. Prasana; Parallel Techniques for Problems in Vision and Robotics; (IRI-9217528 A01); $30,759; 12 months (Joint support with the Robotics & Machine Intelligence Program - Total Grant $61,519).

This research continues earlier efforts to study parallelism for image understanding and robotics as well as to understand 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 robotic 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 Maine; Seth Wolpert; Examination of a Neuronal Algorithm Using VLSI-Based Models; (MIP-9210945 A01); $10,000.

The objective of this research is to recreate the function of a network of biological neurons using a VLSI-based neuronal analog, of neuromime. By reconstructing a well-documented network of biological neurons and comparing the signal patterns resident in the artificial network with those of the biological network, the hardware and sorfware of the network may be related to one another.

This is being carried out in five iterations of modify, design, and test. In each iteration, a nominal neuromime is augmented with discrete components to match the characteristics of each of nine biological counterparts. These changes are then incorporated into the nominal chip, submitted for fabrication, and subsequently tested.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Johns Hopkins University; Andreas Andreou and Fernando Pineda; Analog Computation and VLSO Architectures for Contraction Mappings; (ECS-9313934); (Joint support with the Communications and Computational Systems Program - Total Grant $73,550).

This research 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 its associated inverse problems. The purpose is to restrict the investigation to networks that can be physically implemented in subthreshold analog VLSI. With this 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Johns Hopkins University; Andreas Andreou; RIA: Fault Tolerance in Analog VLSI Focal Plane Processors; (MIP-9010364 A01); $6,250.

Analog VLSI is a promising approach to the design of systems for machine vision since it leads to distributed, data driven architectures, that map the light stimuli directly to the crux of computing hardware, the silicon substrate. This emerging class of signal processing systems is based on relatively simple computational primitives such as logarithmic photodetectors, aggregating resistive networks and coupled non-linear resistive networks. Furthermore, there are power and area efficient features that make them attractive for wafer scale integration. However, manufacturing of such systems at the wafer scale will strongly depend on establishing design methodologies that make them robust to defects in the fabrication process. Equally important, these must be augmented with yield estimation models as well as testing and failure analysis procedures. The above issues are addressed in this research in a comprehensive program that involves both analytical calculations and experimental studies.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Boston University; Mark Karpovsky; On-Line and Off-Line Error Detection Mechanisms in the Coding Theory Framework; (MIP-9208487 A01); $59,144; 24 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).

This award supports a postdoctoral researcher, who is an internationally known scholar in the areas of design, testing, and diagnosis of computer hardware.

Northeastern University; Elias S. Manolakos; RIA: Parallel Processing Algorithms and Architectures for the Estimation of Higher Order Statistics; (MIP-9309319); $89,991; 36 months.

The main goal of this project is the design and evaluation of VLSI architectures for the efficient estimation of Higher Order Statistics (HOS) from time-series data. In addition parallel algorithms to speed-up off-line HOS-based data analysis and modeling in parallel processing systems are being developed. Simulations are being performed on a Transputer-based multiprocessor for validation purposes and proof-of-concept prototypes will be designed using hardware description languages for performance/area estimation. As a by-product of this research, public domain parallel processing software will be provided on various platforms (CM, Transputers, Monsoon dynamic data-flow) to allow scientists who are not experts in signal processing to experiment with the powerful HOS-based techniques in the analysis and modeling of large amounts of statistical data.

Dartmouth College; Barry Fagin; Application-Specific Architectures for Multimedia; (MIP-9312350); $48,709; 12 months.

The objectives of this research are:

1.	a quantitative analysis of the computational requirements of multimedia, and

2.	the development of new system architectures based on this analysis.

The methods to be employed are:

1.	Performance analysis of multimedia applications on a 100 Mb/s fiber optic network of workstations,

2.	Performance comparisons of solid-state and conventional disk storage in client-server networked video applications,

3.	Computational profiling of existing standard multimedia algorithms,

4.	The evaluation of prototype designs using FPGA (field-programmable gate array) emulation, and

5.	The construction and evaluation of complete board-level systems at the Thayer Rapid Prototyping Facility.

Princeton University; Kenneth Steiglitz; Scaling Large Special Purpose Computers; (MIP-9201484 A01); $4,000.

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; Virginia M. Lo, Bella Bose and Sanjay Rajopadhye; Algorithms & Abstractions for Mapping Parallel Algorithms to Parallel Architectures; (MIP-9108528 A02 & A03); $130,865; 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Pennsylvania State University; Mary Irwin and Robert Owens; High Performance, Fine Grained, Application Specific, VLSI Architectures; (MIP-9102500 A02); $89,055; 12 months.

The primary thrust of the research is the investigation of a more general purpose signal processing architecture which achieves the same level of performance as special-purpose signal processing architectures without an accompanying increase in granularity. Most attempts at trying to expand an architecture to accommodate a more general class of applications usually result in an increase in granularity. With the increase in granularity either the overall size of the processor increases or, to keep the overall physical size constant, fewer processing cells are utilized. In either case, the end result is a decrease in performance. This project attempts the development of more general purpose signal processing architectures which avoid this difficulty while maintaining the granularity, performance, and physical size of fine grain processors with the flexibility of more coarse grain processors.

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

This research focuses on both the development of new signal processing algorithms which will advance the state-of-the-art in speech recognition, and the demonstration of the utility of parallel architectures, especially reconfigurable multiprocessor systems, in implementing speech recognition algorithms.

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 A01); $21,106.

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).

This grant includes support for NSF-ESPRIT cooperation.

University of Wisconsin; Parameswaran Ramanathan; Time-Constrained Communication in Real-Time Systems With Point-to-Point Interconnection Topology; (MIP-9213716); $180,000; 36 months.

A major limitation of real-time distributed computing systems is that communication latency between tasks on different nodes can be large. This research is directed towards alleviating this limitation using three methods. First, algorithms for assigning deadlines to information transfers between tasks are being developed. Second, partitions of information transfers into messages are being investigated. Third, routing and delivery strategies are being developed. The result is a set of solutions which can be used to design real-time communications systems.

Workshops and Conferences

University of Illinois - Urbana; Benjamin Wah; International Conference on Application-Specific Array Processors; Venice, Italy; October 25-27, 1993; (MIP-9311908); $11,600; 12 months.

This conference, sponsored by the EUROMICRO Association, the IEEE Computer Society, IFIP, AEI, and AICA, focuses on parallel computing, system design methodologies, technology and implementation within the context of application specific computing. Application specific computing is directly related to high performance computing and is a major component in this program. This conference will take place in conjunction with the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems.

This grant supports travel by selected graduate students to permit them to attend the conference.

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 technology. CSP is a highly active research area that covers a wide spectrum ranging from theory to VLSI implementations and applications. Often driven by advances in technology, it also serves as a catalyst for new technological innovations. A classification of CSP research based on signal characteristics, applications, and technology is as follows:

1.	One-Dimensional Digital Signal Processing (1-D DSP) research is concerned with the representation of 1-D signals (example, audio, and EKG signals) in digital form, and the processing of such signals using digital technology.

2.	Multi-Dimensional Digital Signal Processing (M-D DSP) research is directed towards signals which are inherently functions of two or more independent variables, including images and video signals.

3.	VLSI Signal Processing research deals with algorithms/architectures that can be mapped (with ease?) onto VLSI circuits.

4.	Circuits research is concerned with the better understanding of non-linear and high-frequency circuits.

Areas of research include:

1-D DSP: signal compression for reduced data rate with applications to personal communications, signal enhancement and recovery from partial information, signal representation and models, optimization and approximation, algorithm development, and alternate architectures for implementation.

M-D DSP: algorithms for M-D signal processing and applications to specific signal categories (image, for example) and multimedia communications.

Digital Representation: efficient and effective A/D conversion, compression, decomposition, and modeling of data.

VLSI SP: analog, digital, mixed analog/digital VLSI for signal processing, and CAD for signal processing architectures.

Circuits: emphasis is placed on analysis and design of circuits including neural networks for signal processing applications.

In 1-D DSP new approaches to non-linear signal processing, new orthogonal decompositions and representations, and new filter structures and designs are encouraged.

M-D DSP is a growing area driven by problems arising in important application such as HDTV. In VLSI signal processing, analog, mixed analog/digital VLSI, and CAD for analog design are areas of importance, and are all presently supported in part by the CSP program.

Initiatives and Opportunities

There are many opportunities and special programs that are available through the CSP Program. Several which are most frequently inquired about are:

HIGH PERFORMANCE COMPUTING and COMMUNICATIONS (HPCC)

The Circuits and Signal Processing Program will focus on a wide range of signal processing problems needing high performance computing, and will continue to serve as an application driver for high-performance computing research.

A component of the HPCC program - Grand Challenge Applications Groups - will provide funding for multidisciplinary groups of scientists, engineers, and mathematicians to apply emerging high performance computing and communications systems to advance the solution of diverse science and engineering problems. The emphasis will be on support for groups requiring HPCC capabilities, where such focused, cross-disciplinary support is generally unavailable or difficult to obtain. Projects will include design of models, algorithms and software to fully realize the potential of parallel, distributed and heterogeneous computing systems on Grand Challenge Application problems.

BIOTECHNOLOGY

In addition to the biotech-related research areas currently supported by CISE, new opportunities for the CSP Program will include:

Bio-based or bio-motivated sensing, sensor development, sensor integration; new methods for computer imaging, 3-D recognition, interactive visualization for medical diagnoses; new models and architectures for building "intelligence" (perception, learning, language, speech) into human-computer interfaces.

Representative contemporary and novel applications to various areas of 1-D and M-D DSP include:

Array Processing: echo imaging problems that arise in diagnostic medicine; remote sensing; nondestructive testing; (adaptive) noise suppression or cancellation with applications to fetal heartbeat monitors and hearing aid applications.

(Adaptive) Filters: modeling biological phenomena, e.g., whitening filters which model neural noise; ARMA modeling of nonstationary (REAL!) processes, e.g., speech processing.

Image Processing: medical image compression (VQ, subband coding, for archival purposes - X-ray to MRI; restoration of blurred or noise-corrupted images; tomographic imaging of time-varying data, e.g., aperiodic time variations in data resulting from diseased human hearts; 3-D image reconstruction with limited tomographic data.

Spectral Analysis: detection of malignant tumors by multivariate analysis of proton magnetic resonance spectra of (blood) serum.

MANUFACTURING and MATERIALS

Potential applications areas include:

Imaging: remote sensing - radar, acoustic, IR, UV

Microstructure: x-ray crystallography, electron and confocal microscopy; electronic photography

Image Understanding: robotics - inspection and quality control; security; VHS; agriculture - environmental monitoring

Array Processing: source localization; active noise control

Other: manufacturing processes (digital process control); automotive electronics (IVHS)

Awards

Circuits

University of California - Berkeley; Leon O. Chua; Research on Problems in Nonlinear Networks and Systems; (MIP-9114168 A02); $132,823; 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); $12,500; 12 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $25,000).

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 A01); $107,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.

One-Dimensional Digital Signal Processing

California State University - Northridge; John W. Adams; New Concepts in Digital Signal Processing; (MIP-9200581 A01); $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 California - Davis; William A. Gardner; Theory and Application of Higher-Order Cyclostationarity; (MIP-9112800 A01); $93,082; 12 months.

The cyclostationarity property of communications and telemetry signals enables the generation of spectral lines with appropriate nonlinear transformations, and renders fluctuations in distinct spectral bands statistically dependent. The frequencies at which spectral lines can be generated are directly related to the separations between dependent spectral bands, which in turn are directly related to carrier frequencies, keying rates, pulse rates, and so on, in the signal. These inherent properties of cyclostationary signals can be exploited to great advantage for numerous tasks in signal processing.	The objectives of this research are:

1.	to investigate new cyclostationarity-exploiting methods for identifying the kernels in the Volterra series representation of time-invariant and multiply-periodic time-variant nonlinear systems; and

2.	to further develop the recently introduced cyclic temporal and spectral moment and cumulant theory of higher-order cyclostationarity, with application to designi ng higher-order spectral-line generators for signal detection and identification, and for signal parameter estimation and synchronization.

University of California - Santa Barbara; John Shynk; RIA: Adaptive Equalization and Detection of Cochannel Signals for Time-Varying Channels; (MIP-9308919); $90,000; 36 months.

This research is developing nonlinear adaptive algorithms for the detection of cochannel signals transmitted over time-varying channels. These algorithms directly estimate both channels, and the results are used to perform joint sequence estimation or joint symbol detection. At least two performance criteria are being considered, including maximum likelihood sequence estimation and maximum a posteriori symbol detection. The focus will be on applications where the channels are rapidly time-varying and the data are transmitted in short bursts. Dual-mode adaptive algorithms that combine fast training with blind equalization/tracking for cochannel signal detection are also being developed. These algorithms will be designed to have a superior symbol error rate performance compared to conventional interference cancellation techniques.

University of Southern California; Jerry M. Mendel; Applications of Fuzzy Systems to Signal Processing; (MIP-9122018 A01); $67,611; 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; and, 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 A01); $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 Etter; Adaptive IIR Filtering Using a Stochastic Filter; (MIP-9106126 A02); $8,000 (Joint support with the Office of Crossdisciplinary Activities - 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.

Yale University; Arye Nehorai; New Methods and Results in Signal Processing and System Identification; (MIP-9122753 A01); $51,922; 12 months.

This research focuses on new theoretical and algorithmic solutions to three problems in the general area of signal modeling and system identification:

1.	a computationally-efficient high-order Yule-Walker estimator and its adaptive counterpart;

2.	fitting rational transfer function models to frequency response data; and

3.	hypothesis testing and detection with the optimal instrumental variable method.

Northeastern University; Hanoch Lev-Ari; Spectrum Analysis and Estimation for Nonstationary Signals; (MIP-9220182); $144,675; 36 months.

This research aims to develop efficient model-based techniques for non-stationary signal analysis and spectral estimation, with a particular emphasis on Burg's maximum-entropy approach and the order-recursive realization of linear predictors. The ultimate objectives are:

1.	to construct numerically-robust adaptive algorithms for estimating the parameters of such models;

2.	to establish the statistical properties (e.g., rate of convergence, tracking capability and steady-state error) of such algorithms when applied to both persistent and transient non-stationary signals; and

3.	to obtain simple procedures for recovering spectral characterizations, such as the Wigner-Ville distribution or the cyclic spectrum fro m the estimated model parameters.

Adaptive algorithms that efficiently estimate periodically-varying model parameters associated with cyclostationary signals have been constructed. The ultimate goal is to extend these results to a broader family of signals, including stationary, cyclostationary, harmonizable, and asymptotically-mean-stationary signals. In particular, multiresolution wavelet basis functions are used to characterize the dynamics of time-varying model parameters, leading to the construction of adaptive estimation algorithms that are recursive in time, order and resolution.

Northeastern University; John G. Proakis; Adaptive Signal Processing Algorithms Based on Nonlinear Performance Criteria; (MIP-9115526 A01); $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 A02); $25,000; 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 project; 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 will be 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 will be 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 A01); $89,601; 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.

Cornell University; Thomas W. Parks; Optimal Design of Filters for Multirate Systems; (MIP-9224424); $221,550; 36 months.

The objective of this research is to develop procedures for the design of optimum multirate digital filters. The criterion used for optimality is derived from the norm of a linear operator that represents the filter. When applied to the design of linear, time-invariant filters this measure of optimality reduces to the usual Chebyshev frequency domain error criterion. For multirate-systems, this approach leads to a new criterion for filter optimality. This provides a quantitative, analytic design procedure that yields better filters than intuitive design methods that are in common use.

The methods for the development of appropriate error functions use techniques from singular value decomposition and analysis of periodically time-varying linear systems. The development of efficient design algorithms is based on semi-infinite programming and Remez-like multiple exchange methods.

This research is expected to establish limits for performance of multirate filters as well as to provide improved filters. Present designs can be compared with the best attainable to determine possible improvements.

Carnegie Mellon University; Virginia L. Stonick; PYI: Globally optimal and stable adaptive filtering algorithm.; (MIP-9157221 A04 & A05); $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 will be 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 Wisconsin - Madison; Barry D. Van Veen; PYI: Detection and Estimation in Low Dimensional Subspaces; (MIP-8958559 A04); $41,000; 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

California Institute of Technology; P. P. Vaidyanathan; New Directions in One and Multidimensional Multirate Systems, Filter Banks, and Applications; (MIP-9215785); $162,393; 36 months.

This research addresses coding gain optimization in one dimensional paraunitary filter banks. Paraunitary filter banks include both subband and transform coders as extreme special cases, and have the advantage of perfect signal recovery in the absence of quantization. This approach opens up a large class of problems, some fundamental, in signal processing and in systems theory, all of which are being addressed. A number of properties of the filter bank transformer that parallel traditional Fourier transform properties (e.g., the convolution theorem) are also being addressed. Again, the coding gain optimization for paraunitary and orthonormal convolvers is being addressed. The above research is also being generalized to nonuniform filter banks (i.e., systems with unequal decimation ratios, as in the most common discrete time wavelet transformers). Finally, several extensions of these ideas to multidimensional multirate systems are being considered.

University of California - San Diego; Bhaskar D. Rao; Novel Constrained Least Squares Algorithms With Application to MEG; (MIP-9220550); $168,297; 36 months.

This research is studying novel algorithms for computing solutions to least squares problems with constraints, especially those problems that are underdetermined. The primary application is expected to be in Magnetoencephalography (MEG), a potentially new modality for the imaging of the brain. Both algorithm development and analysis are being considered, with MEG providing the forum for the testing and evaluation of these algorithms. It is expected that this research will greatly enhance our understanding of nonlinear iterative techniques.

University of Florida; Jian Li; RIA: Utilizing Sensor and Wave Properties for Antenna Array Processing ; (MIP-9308302); $100,00; 36 months.

To achieve the best possible estimation performance with an antenna array, signal processing algorithms must consider both sensor and wave properties, and exploit the advantages of these properties. The main objectives of this research are:

1.	to exploit the advantages of different polarization sensitive arrays;

2.	to develop the direction and polarization estimation techniques for both completely and partially polarized waves; and

3.	to take into account the mutual coupling effects between antenna sensors for directio n and polarization estimation and for modeling nearby scatters with antenna theory.

The algorithms are being applied to both simulated and experimental data from industrial and government sources. The performance of the algorithms are being evaluated for both types of data.

Georgia Institute of Technology; Vijay K. Madisetti; RIA: The Fast Discrete Radon Transform; (MIP-9211725 A01); $9,856.

This research is investigating a new method for the computation of the Radon transform and its inverse that avoids a number of problems associated with conventional methods. These include sensitivity to noise, necessity for interpolation, and significant amounts of computation. The discrete Fast Radon Transform (FRT/IFRT), as this method is called, provides an increased flexibility in sampling, in addition to a dramatic reduction in the computational complexity. The basic approach taken is to apply advanced signal processing techniques in the frequency domain to the reconstruction problem. Use of optimization methods and the properties of discrete periodic signals, result in a rich theory for the FRT/IFRT. Experimental results have validated theoretical analyses of its performance.

Illinois Institute of Technology; Nikolas F. Galatsanos; RIA: Wavelet Based Multi-Channel Subband Image Restoration; (MIP-9309910); $88,740; 36 months.

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.

University of Illinois - Urbana; Yoram Bresler; PYI: Statistical Techniques in Inverse Problems; (MIP-9157377 A01); $50,028; 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 - Urbana; Michael T. Orchard; NYI: Optimal Motion Compensation for Video Compression; (MIP-9357823); $25,000; 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 unifyied framework for these two approaches to motion estimation, and to develop hybrid algorithms taking advantage of the best features of both approaches.

Harvard University; David Mumford; Mathematical, Computational and Biological Aspects of Vision; (MPS-9121266 A01); $37,000; 12 months (Joint support with the Computational Mathematics Program, the Database, Software Development and Computational Biology Program, and the Robotics and Machine Intelligence Program - Total Grant $151,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. A new technique involving variational problems for discontinuous maps is being used to attack some of these problems. This mathematical approach is being compared with the neural techniques by which animals solve the problem. To do this, "neural net" implementations are being studied and experiments are being 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.

Massachusetts Institute of Technology; Alan Willsky; Statistical Signal Processing and Estimation for Spatial and Multidimensional Data: Multiresolution Methods, Efficient Algorithms and Geometric Reconstruction; (MIP-9015281 A02); $45,000; 12 months (Joint support with the Engineering Systems Program - Total Grant $65,000).

There are three major components of this research program which has as its overall objective the development of new classes of algorithms for statistical signal processing and estimation of spatial and multidimensional data. The first is the development of statistical models and methods for multiscale signal analysis and processing in one and several dimensions. Problems that are being addressed include the development of a statistical counterpart to the emerging theory of multiresolution signal decompositions and wavelet transforms, the investigation of iterative, multigrid signal processing algorithms, and applications of these methods to topics ranging from inverse reconstruction problems to problems of signal or image segmentation.

The second is the development of efficient algorithms for processing spatial data. This topic focuses on the exploitation of the structure of noncausal models, such as those described by partial difference equations or Markov random fields, in order to develop extremely efficient and highly parallel algorithms. Specific problems being investigated include the employment of radially inward and outward recursions for multidimensional signal processing, parallel processing structures based on spatial partitioning of multidimensional signal processing, and the development of efficient algorithms for tracking motion and other temporal changes in space-time random fields.

The third is the development of statistical methods for estimating or reconstructing geometric features in multidimensional data given uncertain measurements of various quantities, such as the support of a convex object in 2-D or 3-D, or the 2-D silhouette of 3-D objects.

University of Michigan - Ann Arbor; Andrew E. Yagle; PYI: Fast Algorithms for Estimation and Inverse Scattering; (MIP-8858082 A04); $25,000; 12 months.

Research efforts focus on the development of a variety of fast algorithms for signal processing applications. These include a geometric approach to phase retrieval, reconstructing a signal of finite support from its Fourier magnitude, fast algorithms for close-to-Toeplitz-plus-Hankel systems of equations with applications to two-sided spectral estimation, and time-frequency methods - wavelets and short-time Fourier transforms - to perform spatially-varying windowing in order to improve the composition of derivatives of non-stationary signals in non-stationary noise.

University of Missouri - Rolla; John A. Stuller and Nancy Hubing; Time-Delay and Image Motion Estimation; (MIP-9223020 & A01); $254,836; 36 months.

This research has three major objectives:

1.	to derive the mathematical operations that should be performed on two or more stochastic signals to obtain theoretically optimum estimates of the delay or displacement between them;

2.	to develop practical systems that attain or closely approximate the theoretically optimu m estimates; and

3.	to compare the accuracy of the theoretically optimum estimates with the estimates obtained by the practical systems.

The research method is primarily theoretical, but includes computational studies and simulation experiments. The approach has the potential to synthesize the traditional divisions between:

1.	motion estimation based on optical flow and motion estimation based on feature tracking; and

2.	segmentation and motion estimation.

This unification should lead to an increased understanding of image motion estimation and improved motion estimation techniques.

Washington University; Donald L. Snyder; Stochastic Inverse Problems for Computational Imaging; (MIP-9101991 A03 & A04); $77,301; 12 months (Joint support with the Computational Mathematics Program - Total Grant $107,301).

The goals of this research are the development of:

1.	improved image restoration algorithms for dealing with stochastic inverse problems;

2.	methods for assessing the quality of the images which are produced; and

3.	strategies for parallel implementation of the resulting algorithms.

The primary focus is on quantum-limited data which arises in such diverse applications as imaging faint objects in outer space and imaging radioactivity concentrations within human tissue.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Rutgers University; James Flanagan and Richard Mammone; Sound Capture from Spatial Volumes - Parallel Processing of Three-Dimensional Arrays of Sensors; (MIP-9121541 A01); $91,451; 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.

City University of New York - City College; Patrick L. Combettes; RIA: Parallel Projection Methods for Set Theoretic Signal Restoration & Reconstruction; (MIP-9308609); $90,000; 36 months.

The goal of this research is to lay a theoretical and computational foundation for the use of parallel projection methods in set theoretic signal/image restoration and reconstruction. Its main motivation is to overcome the shortcomings of the Method of Successive Projections (MOSP, POCS in the Convex case) that currently prevail in the field: MOSP is not well suited for implementation on parallel processors due to its serial structure; it provides poor solutions if the sets do not intersect (inconsistent formulations); and it converges slowly and there is no general rule for adapting the relaxation coefficients to speed up the iterations.

A general Method Of Parallel Projections (MOPP) is being developed in which the current iterate is projected simultaneously onto selected sets and the update is a relaxed convex combination of the projections. Research objectives include, a formal study of the convergence properties of MOPP for convex and nonconvex, as well as for the consistent and inconsistent formulations; development of iteration-dependent, extrapolated overrelaxations to achieve very fast convergence; and investigation of the practical and computational issues pertaining to signal/image recovery applications.

Polytechnic University; Seung P. Kim; RIA: Block Transform Domain Digital Filter: Theory and Implementation; (MIP-9211495 A01); $5,848.

This research focuses on digital filtering in a Block Transform Domain (BTD). Such an approach can offer performance improvements close to the data compression ratio without significantly increasing the system cost. This is because when the number of bits used in the signal representation is reduced, the errors due to finite precision computations can be reduced through proper bit allocations within the transform coefficient representations and filtering computations and by eliminating intermediate steps such as an inverse block transform.

Mathematical descriptions and properties of the BTD filters are being examined. Minimum roundoff filter design are also being investigated for state-space and lattice as well as FIR structures in the block transform domain. In order to implement the resulting nonuniform precision computations, a Block Parallel, Bit-Serial (BPBS) approach is proposed. The resulting structure is regular and permits faster computation by taking advantage of the compressed signal representation.

University of Rochester; A. Murat Tekalp and Warren E. Smith; Modeling and Suppression of Motion Artifacts in Magnetic Resonance Imaging; (MIP-9119443 A02); $22,844; 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.

Lehigh University; Rick S. Blum; RIA: Distributed Signal Dectection in Uncertain Environments; (MIP-9211298 A01); $4,980.

Distributing multiple sensors over some region for the purpose of detecting a signal in noise is becoming increasingly attractive. The majority of the research work concerning the design of such schemes has focused on signal detection problems where a complete observation model which categorizes the environment under consideration is known. This research deals with distributed detection schemes for cases where a complete observation model is not available due to incomplete knowledge of the operating environment. This is an extremely practical case which has applications in air traffic control, radar weather monitoring, and other radar and sonar systems. Robustness results for important cases with alternative hypothesis which are not simple, finite observation sample sizes, dependent observations, and non-additive observations are being sought. The plan to construct these schemes focuses on applying the theory of minimax robust statistics. Cases with nonstationary, possibly non-Gaussian background environments and possibly dependent observations are also being investigated.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

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

This 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 will be explored, in which a sequence of image-based objervations 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 proposed. 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 a object. The proposed shape models suggest certain recognition algorithms, and these will be explored in a variety of application areas.

Washington State University; Thomas R. Fischer and Roberto H. Bamberger; Analysis and Design of Multidimensional Filter Banks with Application to Image Coding; (MIP-9116683 A02 & A03); $119,063; 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Digital Representation

Stanford University; Robert M. Gray and Richard A. Olshen; Tree-structured Image Compression and Classification; (MIP-9311190); $103,971; 12 months.

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; Paul R. Gray, Avideh Zakhor and Bernhard E. Boser; Continuation of Research in High-Speed, High-Resolution Analog-Digital Conversion; (MIP-9214951); $278,190; 36 months.

The rapid evolution of LSI and VLSI digital technologies has resulted in much wider utilization of digital techniques for signal processing and control applications than in the past. As the level of integration of such systems continues to increase, it has become more and more desirable to implement the Analog/Digital (A/D) conversion function on the VLSI control or signal processing device itself. Great progress has been made in the past ten years in the implementation of analog functions of various types of MOS LSI technology, using NMOS initially, then CMOS as that technology matured, and most recently BiCMOS technology.

This research is directed towards new architectures and new approaches to monolithic A/D conversion which more closely approach the fundamental limits imposed by the technology used to implement them. Topics of emphasis include self-calibration techniques for high-speed, high resolution pipeline A/D converters, properties of parallel pipeline, or "systolic" A/D converters, micropower high speed A/D converters using charge transfer signal processing, optimum decoding algorithms and stability and scaling in oversampled A/D converters, approaches to very high speed oversampled A/D converters, and performance limits for the electromechanical sigma-delta A/D converter used for readout purposes in sensor applications.

University of California - Berkeley; Avideh Zakhor; PYI: Signal Interpretation and Representation Using Neural Architectures; (MIP-9057466 A03); $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 California - Irvine; Ian Galton; RIA: Frequency to Digital Conversion; (MIP-9309656); $99,994; 36 months.

This research is evaluating the viability of and will further develop a novel technique for simultaneously performing the previously separate operations of phase-tracking and A/D conversion. The technique gives rise to a family of systems referred to as Sigma-Delta Frequency-to-Digital Converters (SDFDCs), and offers the potential of significant reductions in analog circuit requirements for a variety of applications. Each system uses coarse analog phase measurements, quantization noise shaping, and decimation filtering to perform instantaneous frequency-to-digital conversion. Because they operate on instantaneous frequency in the manner that SD modulators operate on amplitude, they share many of the benefits enjoyed by SD modulator-based A/D converters such as reduced analog circuit requirements and amenability to VLSI implementation. The research is developing rigorous theoretical results supported by simulations with the goal of characterizing SDFDC performance. A VLSI prototype targeted to a specific application will also be developed.

Georgia Institute of Technology; Mark J. T. Smith; Dynamic Multirate Systems for Image and Video Compression; (MIP-9116113 A01); $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 filte r 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.

University of Maryland; Nariman Farvardin; A Novel Structured Vector Quantization Scheme: Design, Analysis and Applications; (MIP-9109109 A01); $89,929; 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 A01); $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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

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

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 A01); $49,508; 12 months (Joint support with the Computer Systems Program - Total Grant $79,508).

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 A04 & A05); $62,500; 12 months.

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 California - Berkeley; Jan Rabaey; High Level Synthesis Techniques for VLSI; (MIP-9222254); $4,982; 12 months (Joint support with the Design, Tools and Test and Systems Prototyping and Fabrication Programs - Total Grant $14,944).

High Level Synthesis has undergone remarkable progress in recent years. A number of powerful synthesis environments have been proposed in the area of real time signal processing, both in Europe and the United States. Unfortunately, most of the existing tools span only restricted application domains or very specific architectural styles. To be successful at an industrial level, a unification of the synthesis approaches is clearly essential.

The goal of this research is to boost the field of high-level synthesis for digital signal processing by bringing together researchers from the IMEC Research Center at Leuven, Belgium and the University of California at Berkeley. The objectives are to exchange synthesis techniques and tools in an attempt to come to a unified framework, addressing the global architectural domain. At the same time, this cooperation will result in the training of researchers with a wider vision and scope of expertise in the field of high level synthesis.

This grant includes support for NSF-ESPRIT cooperation.

University of Maryland - College Park; K.J. Ray Liu; RIA: Novel Approaches for Numerical Signal Processing: Algorithms and Architectures; (MIP-9309506); $89,985; 36 months.

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 will be 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 Minnesota; Keshab K. Parhi; NYI: Dedicated VLSI Digital Signal and Image Processors; (MIP-9258670 A01); $10,000.

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 A01 & A02); $56,263; 12 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $103,546).

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 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Miscellaneous

University of Alabama - Huntsville; Partha P. Banerjee; PYI: Studies in Nonlinear Wave Propagation & Optical Signal Processing; (MIP-9296000 A02); $5,000.

This research focuses on the problems of wave propagation in nonlinear and dispersive media and their numerical simulation on computers. A secondary focus is on acousto-optics and optical information processing including the optical interconnection problem.

University of California - Davis; G. Robert Redinbo; Fault Tolerance in Cell-Site Processing for Mobile Cellular Communication Systems; (MIP-9215957); $161,449; 36 months.

Mobile cellular communication systems, a rapidly growing communications medium, rely upon significant digital processing elements, particularly in the central cell sites where numerous users in a geographic area interface with the full network. Reliability is a serious design requirement where processing elements are shared among many users and failures can significantly degrade the network performance for all users. This research is applying new evolving fault tolerance design methodologies to modern system designs which employ configurations of high-speed functional processing units, Application-Specific Integrated Circuits (ASICs).

In the new fault-tolerance design philosophy, algorithm-based fault tolerance, data sample integrity is paramount, and special number codes are being used to generate parity values in parallel with the normal processing operations. Comparisons between these values and other associated parity generation are very similar to functional elements employed in the main processing operations, and therefore can be substituted for failed functional elements when failures are detected.

The important interrelationships between detecting failed functional units and protecting the underlying control units are being examined. Simple reliability calculations employing straightforward failure rate models are being used to guide fault tolerance levels and the system location for detection facilities.

This award includes support for undergraduate students under the Research Experiences for Undergraduates Program.

William Marsh Rice Univiversity; Don Johnson; Databases for Signal Processing Research; (MIP-9301646 & A01); $41,461; 12 months.

Rice University is establishing a two-part database composed of sampled signals and signal processing software with the Signal Processing Society serving as the gatekeeper. This database will be accessible through the InterNet at no charge to users. Data and programs are being solicited from university, industrial, and military sources. The data will provide a needed testbed for evaluation of signal processing algorithms; the software will provide the signal processing community with state-of-the-art algorithms and simulation systems.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of Wyoming; Robert F. Kubichek; RIA: Output-based Objective Estimation of Speech Quality and Intelligibility ; (MIP-9309315); $83,734; 24 months.

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 superconductivity. Architectural innovations might include new parallel l/O structures, highbandwidth interconnects, or reconfigurable fault-tolerant subsystems or exploration of advanced memory hierarchies on system performance. New evaluation techniques might include instrumentation for performance evaluation or debugging. These innovations might be applied to produce CAD engines, large sensor arrays, or signal processing architectures, for example.

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.

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

Initiatives and Opportunities

Due to several special initiatives (such as High Performance Computing and Communications, and Advanced Manufacturing Technology) there are an increasing number of opportunities for the construction and evaluation of experimental systems.

Issues which need to be addressed include: use of optoelectronics, both as subsystems and for interconnects; use of micromachinery as components; active power management for low power portable devices; and increasing use of analog and mixed analog/digital subsystems.

The ability to rapidly construct application specific systems for use on a specific problem will require greater design reuse, greater sharing of design/parts/knowledge between groups, utilization of fast turnaround fabrication services, use of a large shared knowledge base of parts and manufacturing information.

It is anticipated that greater use will be made of high performance hardware simulators to enable users to quickly "implement" entire systems using a combination of FPGAs and existing parts. For many system studies this may be used as the only realization of the system allowing for rapid construction, sharing of resources, and encouraging reuse of designs and subsystems.

Awards

Graphics and Solid Modelling

Cornell University; Herbert B. Voelcker; Mechanical Tolerancing and Dimensional Metrology; (DDM-9115435 A02); $60,000; 12 months (Joint support with the Computer Integrated Engineering Program - Total Grant $130,429).

Recent national studies have identified serious deficiencies in mechanical tolerancing and metrology standards and practices, and in the teaching of these in universities, training institutes, and industry. The central problem underlying all of these deficiencies is the lack of proper scientific foundations for mechanical tolerancing. In essence, tolerancing and metrology evolved from shop-floor practice, and are taught and applied as collections of special-case techniques.

This project attempts to lay scientific foundation for these fields and to introduce them in education.

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

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 (SG) 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 algorith ms 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 (i.e. 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 is aimed at re-establishing CSG as an industrially viable representation for solids, and enabling fully symmetric dual-representation modeling systems to be built which should be considerably more powerful than today's B-rep-only systems.

Duke University; Gershon Kedem; Parallel Raycasting Engines and CAD/CAE/CAM Applications; (MIP-9007711 A05); $10,178.

This is a joint project with Herbert B. Voelcker (Cornell University) to continue the successful research on custom hardware for solid modelling. Duke is extending and improving the hardware itself, while Cornell is building software for constructive solid geometry (CSG), integrating the resulting system with applications, and conducting field tests. The initial 8-processor system is being upgraded to 256 processors, to allow parallel processing of more complex objects. At the same time, the numerical precision of the hardware is being increased, and a tag system is included to allow the processors to keep track of software-specified properties of parts of objects.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program. The students are using the Ray-casting Engine to discretize large molecules such as proteins. Using the discrete representation of the proteins they compute physical and chemical properties, such as molecular docking and fitting of ligands into proteins' active sites.

University of North Carolina - Chapel Hill; Henry Fuchs, John W. Poulton and Vernon L. Chi; Supercomputing Power for Interactive Visualization; (MIP-9000894 A07); (Joint support with the Advanced Research Projects Agency - Total Grant $356,965).

This grant supports two additions to the Pixel-planes project. The first is for construction of a high-resolution head mounted display. This display extends the use of Pixel-planes to three-dimensional visualization in large volumes of space, with the user able to walk around and interact with the image. The capability for such visualization allows the meaningful presentation of complex data.

The second allows completion of the work originally planned.

University of North Carolina - Chapel Hill; John W. Poulton and Henry Fuchs; Scalable Graphics: From Personal to Supercomputer Visualization Engines ; (MIP-9306208); $685,636; 12 months (Joint support with the Advanced Research Projects Agency - Total Grant $1,323,445).

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.

General Purpose Computing

University of Southern California; Michel Dubois, Peter B. Danzig, Massoud Pedram and Rafael H. Saavedra; The U.S.C. Multiprocessor Testbed: A Testbed for Scalable Shared-Memory Systems; (MIP-9223812); $415,456; 15 months.

A testbed for experimenting with memory hierarchies in multiprocessors is being supported. A processor node in the testbed contains cache and memory system controllers made from field-programmable gate arrays. To experiment with a memory control mechanism or coherency technique, the investigators program the gate arrays to implement the mechanism. For software support of experimental techniques, the GNU-C compiler is being modified to generate appropriate code, such as non-blocking prefetches, and the Mach microkernel is being ported to provide thread scheduling.

University of Illinois - Urbana; Pen-Chung Yew, Wen-mei Hwu and John Bruner; Improving the Performance of Scalable Shared-Memory Multiprocessors; (MIP-9307910); $91,339; 12 months (Joint support with the Microelectronic Systems Architecture Program - Total Grant $197,429).

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.

Massachusetts Institute of Technology; Anant Agarwal; Automatic Management of Locality in a Scalable Cache-Coherent Multiprocessor: The MIT Alewife Machine; (MIP-9012773 A03); $561,958; 12 months (Joint support with the Computer Systems Architecture Program - Total Grant $611,958).

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 A02); $25,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 architectur e.

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 - Ann Arbor; Trevor N. Mudge, Edward S. Davidson, John P. Hayes, Santosh G. Abraham and Richard B. Brown; Rapid Prototyping and Evaluation of High-Performance Computers; (MIP-9208342); $240,950; 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; Ultra III: Implementing a Scalable Shared-Memory Multiprocessor; (MIP-8915488 A04); $16,165; 6 months.

This project is building and evaluating ULTRA, a MIMD multiprocessor, using combining switches in the processor-memory interface. The supplement allows completion of an enhancement begun in FY 1992. In the enhanced ULTRA, first generation combining switches are being replaced by more modern switches built by NCR.

New York University; Allan Gottlieb; Evaluating the NYU Ultracomputer; (MIP-9303014); $42,661; 6 months (Joint support with the Systems Prototyping and Fabrication Program - Total Grant $51,891)

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.

Carnegie Mellon University; Roy M. Maxion; Discovering Information in Large, High-Dimensional Databases; (IRI-9224544); $10,000; 12 months (Joint support with the Database and Expert Systems Program, the Knowledge Models and Cognitive Systems Program, the Design, Tools and Test Program and the Statistics Program - Total Grant $140,000).

Discovering functional relationships among high-dimensional data is astronishingly 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 models 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.

University of Virginia; William A. Wulf, James H. Aylor and Jack W. Davidson; Implementation of High Bandwidth Memory Systems ; (MIP-9307626); $996,441; 24 months.

This project is building and measuring experimental memory systems that match the high data rates of processors with the low random access data rates of memory parts. The goal is to detect streams of memory references at compile time and use a smart memory controller to prefetch the streams at run time. The memory controller can use features of the memory system such as page mode, nibble mode, or Rambus to maximize the data rates of the memory parts. It then buffers the streams until the processor asks for the data. The project includes compiler research as well as research into the architecture of the memory controllers. This is similar to the vectorization efforts on such machines as the Cray supercomputers, but more general since a smart memory controller can be designed for any combination of processor speeds, memory features, and program characteristics.

Virginia Polytechnic Institute; Peter M. Athanas; RIA: An Architecture and Compiler for Adaptive Computing; (MIP-9308390); $99,235; 36 months.

A new processing platform and high-level compiler are being developed that will significantly improve program execution times. Typical computationally intensive programs tend to spend nearly all of their execution time within a small fraction of the compiled executable code. Efforts to improve the performance of these tasks are best rewarded when focused on these frequently accessed portions. The new hardware and software will allow the configuration and fundamental operations of a core processing platform to adapt to the computationally intensive portions of a targeted application. The high-level language compiler is responsible for identifying the computationally dominant portions of an application, and for synthesizing hardware structures that can be dynamically loaded into the processing platform for subsequent execution. A general-purpose platform embracing these principles can reap the performance benefits of application-specific processors, and also retain a general purpose nature by accommodating a wide variety of tasks. Furthermore, computer architectures that adopt these techniques may become a cost-effective alternative to conventional high-performance computing platforms.

University of Washington; Theodore H. Kehl; Self-Timed Logic in Multiprocessors; (MIP-9101464 A02); $181,579; 12 months.

This project involves building and measuring two self-timed components inserted into an existing shared-memory multiprocessor computer system. The two components are a multilayered backplane with self-timed arbitration logic and a self-timed memory module. The goals are to demonstrate the ability to increase the number of processors while also doubling memory performance for this system. This project is testing the viability of self-tuning systems (the system is self-tuning in that the operating margins are adjusted based on the actual components used in the system).

University of Washington; Lawrence Snyder and Carl Ebeling; Chaotic Routing: Study and Implementation; (MIP-9213469); $365,237; 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 - Madison; Mark D. Hill, David A. Wood and James R. Larus; Cooperative Shared Memory and the Wisconsin Wind Tunnel; (MIP-9225097); $422,716; 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

International Computer Science Institute; Nelson Morgan; A System for Connectionist Speech Recognition Research; (MIP-9311980); $680,002; 12 months.

This project is constructing a computer optimized toward speech recognition algorithms, and is evaluating speech algorithms on the machine. A fundamental goal of the project is to explore the architectural changes needed for speech processing in future production systems. The new computer is a low-degree multiprocessor, each node of which contains a high-speed general-purpose processor, a multiple-accumulate processor, memory, and a communications interface for the multiprocessor interconnect. The computer will also be capable of being extended to include analog processing or smart sensors. This new machine will provide the performance of supercomputers at a small fraction of their cost on the speech recognition problem, and will contribute to the development of speech recognition systems for everyday use in commodity computers.

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

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 - Ann Arbor; Kang G. Shin; Architecture and OS Support for Real-Time Fault-Tolerant Communication; (MIP-9203895 A01); $388,242; 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 68020 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 North Carolina - Chapel Hill; Raj K. Singh and Vernon L. Chi; BioSCAN: A VLSI-Based System for Biosequence Analysis; (MIP-9024585 A02); $31,905; 12 months (Joint support with the Instrumentation and Instrument Development Program - Total Grant $61,905).

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.

Carnegie Mellon University; L. Richard Carley and Takeo Kanade; A Three Dimensional Imaging System Integrating Parallel Analog Signal Processing and IC Sensors; (MIP-8915969 A08); (Joint support with the Advanced Research Projects Agency - Total Grant $84,000).

The topic of this research is the design and use of a smart sensor system for light-stripe range finding. A plane of light is swept over a three-dimensional object that is imaged on a two-dimensional array of pixels. (The array of pixels and the plane of light are parallel planes.) At the time that a point on the object is illuminated, the corresponding pixel will receive its maximum light intensity. By recording the times at which pixels receive their maximum light intensities, the three-dimensional structure of the object can be determined. The sensor uses photodiodes integrated on a chip with analog circuitry at each pixel that can determine the time of maximum illumination. This circuitry is augmented with inter-pixel signal processing circuitry to increase the accuracy of the sensor, and with A/D converters and multiplexors to allow communication with a computer. A 28 x 32 sensor array has been fabricated and demonstrated.

Carnegie Mellon University; Takeo Kanade, L. Richard Carley, Dean Pomerleau and Andrew Gruss; ALVINN-On-A-Chip: A Computational Sensor for Road Following; (MIP-9305494); $621,385; 24 months.

This project is building and deploying an intelligent imaging sensor for road following. The sensor generates the heading information required to steer a robotic vehicle by watching the road. On-chip processing is performed by a neural network trained to drive autonomously on public highways. The circuitry which performs the neural computations is integrated with a photosensor array in order to directly sense road-image information. The photosensor array includes analog signal processing in each cell and binary optics for better photon statistics, decreased transducer size, and less interference.

University of Utah; Lee A. Hollaar; Implementation and Evaluation of a Parallel Text Searcher for Very Large Databases; (MIP-9323174 A03 & A04); $492,274; 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.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

Other

National Academy of Sciences; Gary E. Dwoskin; Information Technology and Manufacturing; (MIP-9312296); $100,000; 16 months (Joint support with the Directorate for Engineering - Total Grant $200,000).

The Computer Science and Telecommunications Board and the Manufacturing Studies Board are developing a set of research directions for the National Science Foundation in support of better development and application of information technology for manufacturing. They have established a study committee to develop a well-defined set of recommendations for research. The committee includes representatives from private manufacturing industries, representatives from computer software companies, and academics from computer science and other relevant disciplines. The committee will produce two reports on its findings.

Virginia Polytechnic Institute; Peter Athanas and A. Lynn Abbott; IEEE Workshop on FPGAs for Custom Computing Machines: Processors, Programming and Applications, April 5-7, 1993, Napa, California; (MIP-9306310); $4,500; 06 months (Joint support with the Systems Prototyping and Fabrication Program - Total Grant $9,000).

Field programmable gate array (FPGA) devices represent a relatively new technology that provides a means of implementing hardware functionality which can be modified under software control. When integrated into a computing platform these devices can provide direct hardware execution for operations that have been conventionally evaluated using software. The purpose of this workshop is to assess the current state of FPGA computing and establish goals for further development of reconfigurable processing platforms.

Systems Prototyping and Fabrication

Dr. Murali R. Varanasi, Program Director

(703) 306-1936 mvaranas@nsf.gov

The Program

The Systems Prototyping and Fabrication Program (SPF) has three principal interrelated thrusts. The first (prototyping) supports research in rapid system prototyping of experimental information processing systems. The second (fabrication) supports research related to state of the art problems in and the infrastructures and services needed for the fabrication of parts for these systems. The third (overlapping) area is assistance to undergraduate microelectronics education. This includes the support and administrative oversight of MOSIS.

SYSTEMS PROTOTYPING

Systems Prototyping deals with the issues involved in the engineering of rapid prototypes of experimental information processing systems. The goal is to develop methodologies and technologies that reduce the time needed to prototype interesting experimental systems. To make this possible, the program element seeks to provide the necessary infrastructure, environments and services for rapid prototyping. The knowledge, methodologies and services developed in this program will be useful both to industrial and university research groups interested in building experimental systems for experimentation and evaluation of new ideas and concepts. Research is supported on: systems-level design tools for specification and synthesis of systems (jointly with the Design, Tools and Test program), design frames (at the chip and board level), the interface problem, specifications, formats at the system level, standards and new intermediate packaging technologies.

MICROELECTRONIC FABRICATION

The Microelectronic Fabrication element supports basic research needed to understand, model and control the microfabrication process. This involves work on new technology, pattern definition and transfer, modeling and simulation, and process automation (computer integrated manufacture of integrated systems). The emphasis is on work at the system level as opposed to addressing materials and device physics issues. This program element encourages research proposals from university groups knowledgeable of industrial problems in the systems-fabrication area. Solutions to existing problems might require the development of: architectures for manufacturing, simulation and real-time control; new disciplines for modelling semiconductor manufacturing equipment and processes; new test structures, sensors and instrumentation for process monitoring; modelling and simulation at the process, device and circuit level; and integration of CAD, CAM and CAT.

EDUCATION

This element consists of two components. The first is MOSIS (MOS Implementation Service) which serves as a broker to the semiconductor foundry industry and plays the major role in fabricating student chips. Secondly this includes funding proposals dealing with new technology issues at the undergraduate level such as: sponsorship of educationally oriented conferences and workshops, funding of innovative technology development that significantly impacts the educational infrastructure as regards system prototyping, distribution of preliminary versions of innovative educational materials (both hardware and software), encouragement of the upgrading of subject matter, curriculum, laboratories, and faculty.

Initiatives and Opportunities

The Systems Prototyping and Fabrication Program offers opportunities in the development of new technologies necessary for the prototyping of experimental systems, and provides access to these technologies for the research community. This program also supports the development of educational materials and access to these new technologies for educational use in order to provide a new generation of highly qualified system designers and implementors.

The pace of technological innovation is accelerating and this acceleration offers both industry and academia new technologies and methodologies to exploit. For example, while MOSIS has and will continue to provide a valuable service to the university education and research community, other methods of implementation must be made available. Prototyping, package design, design for testing and manufacture must be integrated with and closely coupled to systems and circuit design. The needs for higher performance and reliability with smaller size, lower cost and lower power also dictate the same. This means the universities must adopt more of a systems outlook to educate those designers, and provide them with a more comprehensive design experience.

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

This program currently supports and is actively soliciting proposals in areas related to High Performance Computing and Communications (HPCC), and recent federal interagency initiatives such as Manufacturing and to a lesser extent Advanced Materials Processing. Listed below are some of the key issues related to these initiatives.

*	Overcoming the performance limitations due to packaging by integrating new packaging concepts into the design process.

*	Reducing the cost and time for fabrication and prototyping with new tools, equipment, and services.

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

*	Simplifying and automating the fabrication processes.

*	Establishing package and multi-chip module packaging standards.

*	Functional and physical partitioning across and within package levels.

*	Establishing a better relationship between tool designers and those doing fabrication, packaging and prototyping, in areas such as requirements, integration, and evaluation of performance.

*	Developing and integrating techniques for the transition of a virtual to a physical prototype.

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

*	Exposing students to the above considerations in a system-level design experience, with practice in the optimized selection among alternatives and exposure to design verification.

*	Innovative use of curricular materials, compression of topics, and curriculum updating to introduce these advances into an overcrowded undergraduate curriculum.

Awards

Systems Prototyping and Fabrication

Stanford University; Teresa H.-Y. Meng; PYI: Digital Signal Processing Techniques for Image Analysis; (MIP-8957058 A04); $55,000; 12 months.

This research focuses on architectures and applications for digital signal processing (DSP). A specific goal is a machine vision system for optical lithography alignment using DSP techniques. To accomplish this goal, new adaptive filtering techniques for edge and line detection and overlay measurements are being developed. To help with the design of the algorithm, a high-level simulator for evaluating algorithms is being developed to run on a distrubutive system.

Research is concentrating on automated gate-level synthesis of efficient hazard-free asynchronous circuits (using standard cell libraries), developing a unified approach to synchronous and asynchronous circuit synthesis, and integration of synthesis and verification of both synchronous and asynchronous designs into the same toolset.

University of California - Berkeley; David A. Hodges, Lawrence A. Rowe and Costas J. Spanos; Computer Integrated Manufacturing: Database Support and Control Applications; (MIP-9014940 A02); $197,327; 12 months.

This research is on systems for instruction in and control of IC (integrated circuit) manufacturing (CIM). There are two parts:

1.	The user interface. The primary thrust is developing graphical user interfaces and multimedia applications to improve manufacturing productivity and training. These include a standard desktop interface for control, scheduling, analysis and management programs. Also being developed is an engineer's notebook, and a hypermedia introduction to semiconductor manufacturing.

2.	Process control and development. Research is focused on designing and prototyping object-oriented systems to support routine manufacturing applications at the equipment level.

Activities include: real-time monitoring, statistical process control, fault diagnosis, the efficient development of new recipes, and the economical creation of equipment models. Experiments with real-time monitoring of applications on equipment (processing and analytical) and equipment maintenance are being done. Results are being used to create a photolithography workcell prototype.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of California - Berkeley; Jan Rabaey; High Level Synthesis Techniques for VLSI; (MIP-9222254); $4,981; 12 months (Joint support with the Circuits and Signal Processing and the Design, Tools and Test Programs - Total Grant $14,944).

High Level Synthesis has undergone remarkable progress in recent years. A number of powerful synthesis environments have been proposed in the area of real time signal processing, both in Europe and the United States. Unfortunately, most of the existing tools span only restricted application domains or very specific architectural styles. To be successful at an industrial level, a unification of the synthesis approaches is clearly essential.

The goal of this proposal is to boost the field of high-level synthesis for digital signal processing by bringing together researchers from the IMEC Research Center at Leuven, Belgium and the University of California at Berkeley. The objectives are to exchange synthesis techniques and tools in an attempt to come to a unified framework, addressing the global architectural domain. At the same time, this cooperation will result in the training of researchers with a wider vision and scope of expertise in the field of high level synthesis.

This grant includes support for NSF-ESPRIT cooperation.

University of California - Santa Cruz; Wayne W. Dai; PYI: Computer Aided Design for VLSI Circuits; (MIP-9058100 A03); $72,500; 12 months (Joint support with the Design, Tools and Test Program - Total Grant $72,500).

This research models the interconnection topology and metrics needed for optimally laying out high-speed interconnections in multi-chip modules. Three topics are being pursued:

1.	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. The lines are on the substrates of silicon-on-silicon thin film MCMs. Algorithms to implement a simple and robust method for designing these transmission lines are being developed.

2.	Routing of clock signals for optimum system performance. In this work a novel algorith m is being developed to construct a planer clock tree which can be embedded on a sing le layer of metal.

3.	A multiple bus network for parallel processing which matches the MCM requirements of higher I/O pin count and inter-chip routing density is being investigated. An algorithm with good fault tolerant properties that leads to uniform bus load and processor fanout is being developed.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of California - Santa Cruz; Martine Schlag and Pak K. Chan; Routability-Driven Logic Partitioning for Multiple-FPGA Systems; (MIP-9223740 & A01); $288,256; 36 months.

This research addresses the problem of multi-way partitioning of large designs onto multiple FPGA systems. The task is challenging because the partitioning methods must accurately assess and enhance routing so that the partitions can be successfully implemented on individual FPGAs. Existing methods result in poor device utilization because they rely on very conservative rules-of-thumb to ensure the successful place-and-route of individual FPGAs. This work has the following specific goals:

1.	to develop new methods for assessing the intrinsic routing requirements of system designs with respect to the architectural resources of FPGAs;

2.	to develop effective methods for exercising the tradeoff between logic and routing resources in heterogeneous FPGA architectures; and

3.	to incorporate these advances within an integrated routability-driven multi-way partitioning and technology mapping strategy that will allow effective utilization of the reconfigurable hardware resource.

In addition to new techniques for routability analysis, partitioning and technology mapping, the research develops new insights into the synergy between system-level interconnect architecture, FPGA device architecture, routability, and partitioning.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

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

This research addresses some key requirements for 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 Hartford; Abiodun Ilumoka; RIA: Cost Effective CAD for Robust Design of Integrated Circuits using Artificial Neural Networks; (MIP-9309914); $89,874; 36 months.

A high proportion of future integrated systems will contain mixed analog/digital subsystems required to meet demanding quality specifications. CAD (computer-aided design) tools currently available for integrated circuit (IC) quality enhancement (or robust design) although effective are plagued by the problem of high simulation cost, the greatest part of which is due to circuit simulation and extraction of performance. This problem arises due to the fact that accurate prediction of circuit performance requires that ICs be modeled at a number of different levels of abstraction including process, layout, device and circuit levels. Furthermore, since current methodologies simulate several instances of the IC in order to investigate quality, the cost problem is compounded.

To date, research efforts to reduce simulation costs have produced a number of approximation techniques which sacrifice accuracy for reduction in computational cost. Thus, although the cost problem is ameliorated, simulator output has significant error. Artificial neural networks (ANNs) provide a non-parametric method for mapping one set of data to another based on information established during an adjustment procedure called "training". Research is focused on the study of improved robust design techniques for MOSFET ICs which exploit the versatile mapping capability of ANNs.

University of Delaware; Phillip Christie; A Renormalization Group Approach to Interconnection Optimization; (MIP-9224154); $50,000; 12 months.

Recent advances in statistical physics based on the concept of the renormalization group are applied to the problem of computer interconnection optimization. This enables a thermodynamic model of system connectivity to be developed which is consistent with the hierarchical boundary conditions imposed by the rack-board-chip method of computer construction. From this theoretical description a new optimization algorithm, called geometrical annealing, is proposed. In contrast to other thermodynamically based algorithms, geometrical annealing acknowledges the spatial relationships that exist between optimal wire length arrangements by employing minimization routines based on geometrical principles. It is anticipated that this property may hold the key to matching the performance of experienced human designers who naturally employ their spatial awareness in producing efficient wiring layouts. Other benefits of this research will include a deeper understanding of the relationship between statistical mechanics and combinatorial optimization, the thermodynamic justification of the power-law relationship between connectivity and system size, known as Rent's rule, and the development of new thermodynamic relationships between the parameters which characterize hierarchically structured systems.

University of Florida; Mark E. Law; PFF: A Multidisciplinary Approach to IC Process Modeling Using the SUPREM-IV Modeling; (MIP-9253735 A01); $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.

Massachusetts Institute of Technology; Hae-Seung Lee; PYI: Analog Device and Circuit Design in Integrated Circuits and Sensors; (MIP-8858020 A06); $37,500.

The focus of this research is on a next generation fabrication technology for analog/digital converters and the demonstration of the integrability of the new technology through the implementation of a high-performance analog-digital converter. Research concentrates in two areas:

l.	BiCMOS Phase-locked Loop Designs. Testing of the first silicon containing transmit and receive phase-locked loops includes test s at 250 Mhz and a characterization of the master slave phase-lock technique, verification of the accuracy of the SPICE simulation and a check of injection locking. Based on the tests and evaluations, the complete system is then designed and implemented in a second chip design.

2.	Integrated Capacitive Sensors and Circuits. Integrated capacitive pressure sensors are being fabricated and tested. Sigma-delta oversampling techniques in the readout are being investigated as a possible replacement for the successive approximation readout technique currently in use.

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

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 Technological University; Ashok K. Goel and Esther T. Ososanya; Experimental Validation of Interconnection and Transistor Delay Models for the GaAs-Based Integrated Circuits; (MIP-9223989); $71,563; 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 the 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 A05); $71,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 a input high-level functional specifications 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.

This grant includes a supplement for undergraduate students under the Research Experiences for Undergraduates Program.

Dartmouth College; Barry S. Fagin; Quantitative Construction of New FPGA Architectures for Large System Prototyping; (MIP-9222643); $57,947; 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.

New York University; Allan Gottlieb; Evaluating the NYU Ultracomputer; (MIP-9303014); $9,230; 6 months (Joint support with the Experimental Systems Program - Total Grant $51,891).

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.

State University of New York - Binghamton; Jiayuan Fang; NYI: Analysis and Modeling of High-Speed Interconnects in Electronics Packaging; (MIP-9357561); $25,000; 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.

University of Rochester; Alexander Albicki; Synthesizing Energy Efficient Circuits and Systems; (MIP-9300936); $137,473; 24 months.

This research aims to expand the current applications of logic synthesis to include the domain of synthesis for reduced power dissipation. It is based on the assumption that switching activity, the number of internal nodes that are charged or discharged when a new set of inputs is applied to the system, is a strong indicator of power dissipation in static CMOS structures. The research builds on some novel results obtained in the synthesis of two level logic circuits, such that they exhibit, optimal switching activities. These results are being utilized to explore procedures for the energy efficient synthesis of arbitrary combinational logic functions.

The goal of this research is the development of a new synthesis tool which will enable users to easily implement digital functions with reduced energy dissipation, while maintaining full testability. When an integrated circuit is operating in the testing mode, the energy consumption may be far greater than during normal operation as many internal nodes which do not usually switch are being tested. The proposed research will ensure that under testing conditions the energy consumption of the system is minimal thus avoiding damage to the circuit.

North Carolina State University - Raleigh; Paul D. Franzon; NYI: Advanced Interconnect and Display Approaches; (MIP-9357574); $25,000; 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.

Carnegie Mellon University; Ronald A. Rohrer; Analysis and Design of Electronic System Packaging and Interconnect; (MIP-9216942); $269,978; 36 months.

This research is directed toward the problem of extracting three-dimensional circuit models from microcircuit and packaging layout descriptions by using the newly developed Asymptotic Waveform Evaluation (AWE) technique to develop interconnect models in an efficient manner. Several features of AWE make this approach attractive: a large speed-up over traditional interconnect extraction and simulation methods; the ability to perform efficient time-domain sensitivity analysis; the capability to handle distributed elements without making a lumped model; an efficient strategy for building macromodels of linear interconnect; and the ease with which three-dimensional electromagnetic problems (involving distributed resistance, capacitance, inductance, as well as retardation effects) can be handled. AWE sensitivity analysis helps to identify "critical" nets which must be extracted with detailed models; this should improve efficiency by allowing the remaining nets to be treated more simply.

The first task in this work is the efficient simulation of nonlinear circuits which contain high-speed interconnect by development of a simulation strategy which combines the benefits of AWE for the linear portion of the circuit (interconnect) with the generality of existing simulation algorithms for the nonlinear circuit elements (such as transistors). The second task is the efficient extraction of accurate circuit models from three-dimensional interconnect geometry. This is done in such a way that the subsequent circuit simulation remains efficient. Greater simulation efficiency is achieved by eliminating the detailed interconnect models and replacing them by macromodels.

Carnegie Mellon University; Donald Thomas and Daniel Siewiorek; Digital System Level Synthesis Tools; (MIP-9112930 A03 & A04); $125,042; 12 months (Joint support with the Design, Tools and Test Program - Total Grant $260,084).

This research is on algorithms and techniques for system-level synthesis of digital electronic systems. Inputs to the system are intended to be high level specifications in terms of system behavior. Research builds on two existing design systems; the system architects workbench, and a microcomputer board design system, called MICON. Research issues being investigated are: partitioning specifications for appropriate style selection, synthesis - including learning and problem solving approaches, internal representation of design information, system level design representation and human interface, and controlled iteration with different types of synthesis tools (design process control). The algorithms are being integrated into a prototype system-level synthesis framework.

This grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.

University of North Texas; Weiping Shi; RIA: Reconfiguration of Re-Programmable Field Programmable Gate Arrays; (MIP-9309120); $90,000; 36 months.

Effective techniques to perform in-circuit reconfiguration for FPGAs may lead to a new generation of fault-tolerant computer systems for high reliability and high performance applications. Future programmable computer architectures could allow software running on the hardware platform to dynamically adjust the architecture according to the current task.

This research is concerned with the diagnosis and reconfiguration of re-programmable Field-Programmable Gate Arrays (FPGAs). In particular, the effort focuses on the design of FPGA interconnect diagnosis algorithms, development of in-circuit reconfiguration strategies for fault tolerance and change of functionality, and the establishment of a theoretical framework for self-adjustable FPGA systems.

Since an FPGA contains many connection wires and switches and requires a great amount of diagnosis time, especially if the diagnosis has to be done often, fast-diagnosis algorithm time implies a great saving in time and resources, and greater reliability. Fast diagnosis algorithms will also benefit other areas where interconnect diagnosis is important, such as VLSI, MCM and PCB production.

MITRE Corporation; John F. Beetem; Incremental Placement and Routing for Field-Programmable Gate Arrays; (MIP-9396073); $130,700; 24 months.

Field-programmable gate arrays (FPGAs) have the potential to revolutionize rapid hardware prototyping both in industry and in university research and instruction. To realize this potential, FPGA placement and routing tools must be orders of magnitude faster than those currently available. This project is investigating the use of incremental placement and routing to speed up FPGA design. Design is an iterative process characterized by small changes. By processing design changes as minimally as possible, incremental placement and routing has the potential to be dramatically faster than conventional tools which must reprocess an entire design from scratch. For placement, a generalized incremental form of the force-directed algorithm with time-varying cost functions is being investigated. Routing is being investigated using incremental penalty-driven iterative improvement and a generalized graph representation of routing resources. The algorithms produced will be implemented to demonstrate their efficacy and at the same time provide high-quality FPGA design tools. As a side benefit, the algorithms will also be applicable to conventional IC and PC board placement and routing tasks.

Virginia Polytechnic Institute; Peter Athanas and A. Lynn Abbott; IEEE Workshop on FPGAs for Custom Computing Machines: Processors, Programming and Applications, April 5-7, 1993, Napa, California; (MIP-9306310); $4,500; 6 months (Joint support with the Experimental Systems Program - Total Grant $9,000).

Field programmable gate array (FPGA) devices represent a relatively new technology that provides a means of implementing hardware functionality which can be modified under software control. When integrated into a computing platform these devices can provide direct hardware execution for operations that have been conventionally evaluated using software. The purpose of this workshop is to assess the current state of FPGA computing and establish goals for further development of reconfigurable processing platforms.

University of Washington; Gaetano Borriello; PYI: CAD for System Integration of Custom Components; (MIP-8858782 A07); $47,490.

This research deals with some of the issues involved in the automatic synthesis and interconnection of digital circuits. One focus is on the specification and synthesis of glue logic in addition to the components themselves. A second focus is on the partitioning of hardware and software components in a system using embedded microcontrollers. The main aspects of the work include:

1.	An internal representation for circuit behavior that allows the specification of complex timing constraints as well as mixing structural and behavioral specifications;

2.	Synthesis methods for mixed synchronous control logic;

3.	Timing optimization of sequential logic; and

4.	New high-level synthesis approaches that take timing constraints into account.

The goal is to develop a synthesis tool that takes as input a concurrent program specification of a circuit and partitions it into appropriate elements (to be implemented in hardware and/or software) and then generates the glue logic to tie the components together as well as interconnect to the environment.

Research is concentrating on six areas: timing analysis of concurrent processes; interface specification, synthesis, and verification; hardware/software co-synthesis; mobile robots; behavioral simulation; and programmable logic devices.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

West Virginia University; Lawrence A. Hornak; NYI: Cointegrated Polymer Waveguide Optical Interconnections for Wafer-Level MCM Systems; (MIP-9257101 A01); $100,000; 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 the first 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.

Research is concentrating on characterization of polymer samples, prism coupler measurement and modification, and development of compatible lithography, wet/dry etch, and polymer processing for waveguide fabrication. Instructional efforts will focus on integrating the lithography and processing modeling tools into the curriculum and offering of an advanced course in applied photonics and optoelectronics.

University of Wisconsin - Madison; Rajiv Jain; RIA: Partitioning, Rapid Prototyping and High Level Synthesis; (MIP-9307830); $99,996; 36 months.

Partitioning of large designs into smaller and more manageable parts is a very important design task. In high-level synthesis of register-transfer level designs, partitioning the specification is done prior to synthesizing the designs. If the input specification is control-dominated, the specification is partitioned into a set of states, or if the specification is data-dominated then it is partitioned into a set of graphs. In either case, the sets of the partition are synthesized independently and the complete design assembled together. This research re-examines the partitioning problem, outlines some concerns with existing techniques and presents a fresh approach to formulating and solving the partitioning problem.

Specifically, the effort focuses on a data-path model which can be used for rapid-prototyping at the register-transfer level design and for partitioning of the input specification. The solution to these problems is achieved by scheduling the input specificiation onto the data-path model. The scheduling result can then be interpreted from a rapid-prototyping perspective or from a partitioning perspective as desired by the designer.

Education

University of Hawaii; Michael J. S. Smith; PYI: Computer-Aided Analog Integrated Circuit (IC) Design; (MIP-8957407 A03 & A04); $72,500; 12 months.

This research effort has focused on two topics: microsystems design using FPGA's and microsystems education and training. An FPGA board (for the Macintosh) was developed, and a second generation design has been started. In the area of education and training, a CD-ROM containing pertinent educational material has been developed and work is now underway writing a textbook on microsystems education. Work is also continuing on mixed analog-digital design.

During this grant period, the research is focused on the concept of a reprogrammable add-in card for personal computers and the completion of the draft of a textbook on ASIC design.

This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.

University of Tennessee; Donald W. Bouldin; 1993 Workshop on Rapid Prototyping of Integrated Circuits for Universities, October 18-19, 1993, Washington, DC; (MIP-9319902); $33,006; 12 months.

This award provides 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.

Index of Presidential Young Investigators

Agarwal, Anant	54

Banerjee, Partha P.	48

Birmingham, William P.	66

Borriello, Gaetano	69

Bresler, Yoram	40

Buckley, Kevin M.	38

Burns, Steven M.	4

Bushnell, Michael L.	13

Cong, Jason	6

Dai, Wayne W.	10, 63

Dally, William	24

Devadas, Srinivas	7

Dill, David	4

Eggers, Susan J.	27

Fang, Jiayuan	67

Farrens, Matthew	21

Ferguson, Frankie J.	14

Franzon, Paul D.	67

Hill, Mark D.	28

Hornak, Lawrence A.	69

Kahng, Andrew	6

Larrabee, Tracy	14

Lee, Hae-Seung	65

Lee, Yung-Cheng	64

Meng, Teresa H.-Y.	63

Orchard, Michael T.	41

Parhi, Keshab K.	47

Pillage, Lawrence T.	16

Pomeranz,Irith	13

Rabaey, Jan	47

Ramachandran, Umakishore	22

Riskin, Eve A.	46

Saleh, Resve A.	15

Siu, Kai-Yeung	21, 35

Smith, Michael J.S.	70

Stonick, Virginia L.	39

Van Veen, Barry D.	39

Varma, Anujan	22

Wawrzynek, John	29

White, Jacob K.	16

Yagle, Andrew E.	41

Yang, Andrew T.	17

Zakhor, Avideh	45

Index of Research Initiation Investigators

Akella, Venkatesh	5

Andreou, Andreas	30

Athanas, Peter M.	56

Blum, Rick S.	43

Chakrabarti, Chaitali	28

Chamberlain, Roger D.	16

Chatterjee, Abhijit	10

Chaudhary, Vipin	25

Combettes, Patrick L.	42

Dutt, Nikil	5

Galatsanos, Nikolas F.	40

Galton, Ian	45

Ilumoka, Abiodun	64

Jain, Rajiv	70

Kim, Seung P.	43

Kubichek, Robert F.	49

Li, Jian	40

Liu, K. J. Ray	47

Lo, Jien-Chung	14, 26

Madisetti, Vijay K.	40

Malik, Sharad	8

Manolakos, Elias S.	30

Najm, Farid	10

Nowick, Steven M.	8

Orailoglu, Alex	10

Panda, Dhabaleswar K.	26

Schreier, Richard	46

Shi, Weiping	68

Shynk, John	36

Torrellas, Josep	23

Zhu, Yahui	26

Index of Principal Investigators

A

Abbott, A. Lynn	59, 69

Abraham, Jacob	13

Abraham, Santosh G.	55

Adams, John W.	36

Agarwal, Anant	54

Akella, Venkatesh	5

Albicki, Alexander	67

Andreou, Andreas	29, 30

Armstrong, James	13

Athanas, Peter M.	56, 59, 69

Aylor, James H.	56

B

Bamberger, Roberto H.	44

Banerjee, Partha P.	48

Beetem, John F.	68

Bhattacharya, Debashis	12

Bhuyan, Laxmi N.	27

Birmingham, William P.	66

Blum, Rick S.	43

Borriello, Gaetano	69

Bose, Bella	31

Boser, Bernhard E.	45

Bouldin, Donald W.	70

Bresler, Yoram	40

Brown, Richard B.	55

Bruner, John	23, 54

Brunvand, Erik	9, 27

Buckley, Kevin M.	38

Burleson, Wayne	24, 65

Burns, Steven M.	4

Bushnell, Michael L.	13

C

Cai, Jaizhen	3

Carley, L. Richard	58

Chakrabarti, Chaitali	28

Chamberlain, Roger D.	16

Chan, Pak K.	64

Chatterjee, Abhijit	10

Chaudhary, Vipin	25

Chi, Vernon L.	53, 58

Chien, Andrew	22

Christie, Phillip	65

Chua, Leon O.	35

Ciesielski, Maciej	24, 65

Clarke, Edmund M.	8

Cohoon, James P.	4

Combettes, Patrick L.	42

Cong, Jason	6

Cyre, Walling	13

D

Dai, Wayne W.	10, 63

Dally, William	24

Danzig, Peter B.	54

Das, Chitaranjan	26

Davidson, Edward S.	11, 24, 55

Davidson, Jack W.	56

Devadas, Srinivas	7

Dill, David	4

Dubois, Michel	54

Dutt, Nikil	5

Dwoskin, Gary E.	59

E

Ebeling, Carl	56

Eggers, Susan J.	27

El-Amawy, Ahmed	24

Esfahanian, Abdol-Hossein	24

Etter, Delores	37

F

Fagin, Barry S.	30, 66

Fang, Jiayuan	67

Farrens, Matthew	21

Farvardin, Nariman	46

Feng, Tse-Yun	26

Ferguson, Frankie J.	14

Fischer, Thomas R.	44

Flanagan, James	42

Franzon, Paul D.	67

Fuchs, Henry	53, 54

G

Gajski, Daniel	5

Galatsanos, Nikolas F.	40

Galton, Ian	45

Gardner, William A.	36

Geman, Stuart A.	43

Gidas, Basilis	43

Goel, Ashok K.	66

Gopalakrishnan, Ganesh	9, 27

Gottlieb, Allan	55, 67

Gray, Paul R.	45

Gray, Robert M.	44

Grenander, Ulf	43

Gruss, Andrew	58

H

Ha, Dong S.	15

Hachtel, Gary	6

Harris, Jay	28

Hayes, John P.	13, 55

Hill, Mark D.	28, 56

Hodges, David A.	63

Hollaar, Lee A.	58

Hornak, Lawrence A.	69

Hubing, Nancy	42

Hwu, Wen-Mei	22, 23, 54

I

Ilumoka, Abiodun	64

Irwin, Mary Jane	31

J

Jain, Rajiv	70

Johnson, Don	49

Johnson, Steven	7

K

Kahng, Andrew	6

Kanade, Takeo	58

Karpovsky, Mark	30

Kaveh, Mostafa	38

Kedem, Gershon	53

Kehl, Theodore H.	56

Kim, Seung P.	43

Koren, Israel	14

Kubichek, Robert F.	49

Kuh, Ernest	5

L

Larrabee, Tracy	14

Larus, James R.	56

Law, Mark E.	65

Lee, Edward A.	47

Lee, Hae-Seung	65

Lee, Yung-Cheng	64

Lev-Ari, Hanoch	37

Levitan, Steven	9

Li, Jian	40

Lightner, Michael	6

Lilja, David J.	25

Lin, Rong	25

Liu, C. L.	6

Liu, K. J. Ray	47

Liu, Wentai	25

Lo, Jien-Chung	14, 26

Lo, Virginia	31

Louri, Ahmed	21

M

Madisetti, Vijay K.	40

Malik, Sharad	8

Mammone, Richard	42

Manolakos, Elias S.	30

Maxion, Roy M.	11, 55

McClure, Donald E.	43

McKinley, Philip K.	24

Mendel, Jerry M.	36

Meng, Teresa H.-Y.	63

Menon, Premachandran	7

Morgan, Nelson	57

Mudge, Trevor N.	11, 24, 55

Mumford, David	41

Murdocca, Miles	25

N

Najm, Farid	10

Nehorai, Arye	37

Ni, Lionel M.	24

Nikias, Chrysostomos L.	37

Nowick, Steven M.	8

O

Olshen, Richard A.	44

Orailoglu, Alex	10

Orchard, Michael T.	41

Ososanya, Esther T.	66

Owens, Robert	31

P

Paige, Robert	3

Palusinski, Olgierd	15

Panda, Dhabaleswar K.	26

Pangrle, Barry M.	8

Parhi, Keshab K.	47

Parks, Thomas W.	38

Pedram, Massoud	54

Pillage, Lawrence T.	16

Pineda, Fernando	29

Pomeranz, Irith	12, 13

Pomerleau, Dean	58

Poulton, John W.	53, 54

Pradhan, Dhiraj K.	31

Prasana, V. K.	29

Proakis, John G.	38

R

Rabaey, Jan	10, 47, 47, 63

Rajopadhye, Sanjay	31

Ramachandran, Umakishore	22

Ramanathan, Parameswaran	32

Rao, Bhaskar D.	39

Reddy, Sudhakar M.	12

Redinbo, G. Robert	48

Riskin, Eve A.	46

Rohrer, Ronald A.	16, 68

Rowe, Lawrence A.	63

S

Saavedra, Rafael H.	54

Sahni, Sartaj	3

Sakallah, Karem	11, 24

Saleh, Resve A.	15

Salowe, Jeffrey S.	4

Saluja, Kewal	15

Sarrafzadeh, Majid	3

Schlag, Martine	64

Schreier, Richard	46

Shi, Weiping	68

Shin, Kang G.	57

Shragowitz, Eugene	11

Shynk, John	36

Siewiorek, Daniel	11, 68

Silverman, Harvey F.	31, 48

Singh, Adit	14

Singh, Raj K.	58

Siu, Kai-Yeung	21, 35

Smith, Alan J.	21

Smith, Mark J. T.	45

Smith, Michael J.S.	70

Smith, Warren E.	43

Snyder, Donald L.	42

Snyder, Lawrence	56

Somani, Arun K.	28

Somenzi, Fabio	6

Spanos, Costas J.	63

Steiglitz, Kenneth	31

Stonick, Virginia L.	39

Stuller, John A.	42

T

Tanner, John	9

Tekalp, A. Murat	43

Thomas, Donald	11, 68

Thomborson, Clark	3

Tong, Carol	12

Torrellas, Josep	23

V

Vaidyanathan, P. P.	39

Van Veen, Barry D.	39

Varma, Anujan	22

Venkateswaran, H.	22

Voelcker, Herbert B.	53

W

Wah, Benjamin W.	23, 32

Wawrzynek, John	29

White, Jacob K.	16

Willsky, Alan	41

Willson, A. N.	35

Wolf, Wayne	8

Wolpert, Seth	29

Wood, David A.	56

Wulf, William A.	56

Wyatt, John L.	57

Y

Yagle, Andrew E.	41

Yang, Andrew T.	17

Yang, Qing	27

Yew, Pen-Chung	23, 54

Z

Zakhor, Avideh	45

Zemanian, Armen	4

Zhu, Yahui	26

Index of Institutions

Arizona State University	28

Auburn University	14

Boston University	30

Brown University	31, 43, 48

California Institute of Technology	39

California State University - Northridge	36

Carnegie Mellon University	8, 11, 16, 39, 55

58, 68

City University of New York - City College	42

Colorado State University	12

Columbia University	8

Cornell University	38, 53

Dartmouth College	30, 66

Duke University	53

Georgia Institute of Technology	10, 22, 40, 45

Harvard University	41

Illinois Institute of Technology	40

Indiana University	7

International Computer Science Institute	57

Johns Hopkins University	29, 30

Lehigh University	43

Louisiana State University	24

Massachusetts Institute of Technology	7, 16, 24

41, 54, 57, 65

Michigan State University	24

Michigan Technological University	66

MITRE Corporation	68

National Academy of Sciences	59

New York University	3, 21, 55, 67

North Carolina State University	25, 67

North Dakota State University	26

Northeastern University	30, 37, 38

Northwestern University	3

Ohio State University	26

Oregon Advanced Computing Institute	31

Oregon State University	46

Pennsylvania State University	26, 31, 37

Polytechnic University	43

Princeton University	3, 8, 31

Rutgers University	13, 25, 42

San Diego State University	28

Stanford University	4, 23, 63

State University of New York - Stony Brook	4

State University of New York - Geneseo	25

State University of New York - Binghamton	67

Tanner Research	9

Texas A&M University	27, 54

University of Alabama - Huntsville	48

University of Arizona	15, 21

University of California - Berkeley	5, 10, 21, 29

35, 45, 47, 63

University of California - Davis	5, 21, 36, 48

University of California - Irvine	5, 21, 35, 45

University of California - Los Angeles	6, 35

University of California - San Diego	10, 39

University of California - Santa Barbara	36

University of California - Santa Cruz	10, 14, 22

63, 64

University of Colorado	6, 37, 64

University of Delaware	65

University of Florida	3, 40, 65

University of Hartford	64

University of Hawaii	70

University of Illinois - Urbana	6, 10, 15, 22, 23

32, 40, 41, 54

University of Iowa	12, 13

University of Maine	29

University of Maryland	46, 47

University of Massachusetts	7, 14, 24, 65

University of Michigan	11, 13, 24, 41, 55, 57, 66

University of Minnesota	3, 11, 25, 38, 47

University of Missouri - Rolla	42

University of North Carolina - Chapel Hill	53

54, 58

University of North Texas	68

University of Pittsburgh	9

University of Rhode Island	14, 26, 27

University of Rochester	43, 67

University of Southern California	29, 36, 37, 54

University of Tennessee	70

University of Texas - Austin	13, 16

University of Utah	9, 27, 58

University of Virginia	4, 56

University of Washington	4, 17, 27, 28, 46, 56, 69

University of Wisconsin - Madison	15, 28, 32, 39, 56, 70

University of Wyoming	49

Virginia Polytechnic Institute	13, 15, 56, 59, 69

Washington State University	44

Washington University	16, 42

Wayne State University	25

West Virginia University	69

William Marsh Rice Univiversity	49

Yale University	12, 37