WPC܉ 2B%RVe3|VDutch Roman 10pt (ASCII) (Port) (FW) P6P"^(88T(@@T(8(,TTTTTTTTTT,,Pptth pAY  }V [ PA 2 $@  catnameSet font for sub-category headings$<$ g~> pA  }V [ PA dttfootFooters - DTT Program - SOA Section of SOAQjpy(#Xdddy   Design, Tools and Test Program`+(#f_y(#Xdddy   `(#JDesign, Tools and Test ProgrammsafootFooters for MSA - SOA klpy(#Xdddy   Microelectronic Systems Architecture Program`9(#f_y(#Xdddy   `(#<Microelectronic Systems Architecture ProgramcspfootCSA Program Footers - SOAOipy(#Xdddy   Circuits and Signal Processing Program`3(#fG_`(#BCircuits and Signal Processing ProgramG2   ? ; -esfooters -SOAExperimental Systems Program Footers - SOAO4py(#Xdddy   Experimental Systems Program`)(#f_y(#Xdddy   `(#LExperimental Systems ProgramspffootSPF Footers - SOA 5opy(#Xdddy   Systems Prototyping and Fabrication Program`8(#f_y(#Xdddy   `(#<Systems aprototyping and Fabrication ProgramindxfootIndex Footers - SOA |py(#Xdddy   Index:_y(#Xdddy   `(#cIndexsummary footrSummary Section Footer N(Summary`(#f((o`(#aSummary(2 h; i prog1colDefine margins to simulate columns - 1 only f\ Xd BorderBorder for Preface, etc cL+ XX  Figure 1 xxxx Figure 1 y!(#,XXxxxxXdd(#,yPrefacePreface footer](Preface`(#f((o`(#aPreface(summary-footrSummary Section FooterjP(wSummary`(#y((W`(#tSummary(2 $ :+dtt-footFooters - DTT Program - SOA Section of SOABwy(#XXdddy   Design, Tools and Test Program`.(#yy(#XXdddy   `(#]Design, Tools and Test Programes-footrs -SOAExperimental Systems Program Footers - SOAOI\bwy(#XXdddy   Experimental Systems Program`,(#yy(#XXdddy   `(#_Experimental Systems Programindex-footIndex Footers - SOANy(#Xdddy   Index`(#~y(#Xdddy   `(#yIndexIntro-footFooter for the Introduction sectiona-Introduction`(#y--o`(#oIntroduction-2'@C >"4$&msa-footFooters for MSA - SOAU6wy(#XXdddy   Microelectronic Systems Architecture Program`<(#yy(#XXdddy   `(#OMicroelectronic Systems Architecture Programspf-footSPF Footers - SOAy(#Xdddy   Systems Prototyping and Fabrication Program`;(#|y(#Xdddy   `(#SSystems Prototyping and Fabrication Programcsp-footCSA Program Footers - SOA y(#Xdddy   Circuits and Signal Processing Program`6(#|y(#Xdddy   `(#XCircuits and Signal Processing Programdirectns-footfooter for MIPS Directions pageb. 0MIPS Directions`(#f00o`(#YMIPS Directions02+k(R~)*Xp+advisoryAdvisory Committee Footers2 oDivison of Microelectronic Information Processing Systems Advisory Committee`^(#vopo`(#)Division of Microelectronic Information Processing Systems Advisory CommitteepStaffStaff FootercLcDivision of Microelectronic Information Processing Systems Staff`Q(#ncco`(#.Division of Microelectronic Information Processing Systems Staffc8pt-10pt, ed 10ptbegin 8 pt, end 10 pt$$ 1E [ PA  }V [ PA Normal2.t+|,,<-Dutch Roman 10pt (ASCII) (Port) (FW)Dutch Bold Italic 10pt (ASCII) (Port) (FW)Dutch Bold 14pt (ASCII) (Port) (FW)xddPlphdttt"^ pAh  }V [ PA HPCC-MIPSFooter for HPCC-MIPS d$XHigh Performance Computing and Communications Initiative`I(#~XXo`(#HHigh Performance Computing and Communications InitiativeX27 /X/ XR0!R0TOC-FooterTable of Contents Footer{1Table of Contents`"(#~11o`(#oTable of Contents12fh1 MACNormal!}}     X` hp x (#%'0*,.8135@8:<     :}D4P T I. A. 1. a.(1)(a) i) a)T0*ÍÍ*Í ., US     X` hp x (#%'0*,.8135@8:<     :}D4P T I. A. 1. a.(1)(a) i) a)T0*ÍÍ*Í ., US2@;.8",89^:"^(88T(@@T(8(,TTTTTTTTTT,,Pllt|ld|@T|h|hx`hxlthlH,HT(TXHXL4P`04X0`TXTHH8`LlPLHTTTprogtabProgram Tabs - SOA"ȪoX` hp x (#%'0*,.8135@8: xiAT(AxN<,P!x~> pAx/U8(,tG}U~> pACqd,SƔ [ PAPO8gC0,3g~> pAX\KYD,Ac~> pA \y.S8(,}S `> xiAX  XX X4` H(#T$2 A % 9E % }t  UUUUUUUUUUUUU WZ WZe W WD  |0Z |0Z' 8U/@ ?  #h24PkP#Microelectronic P h  MicroelectronicM'8 V ( #h24PkP#Systems P Q & SystemsR,= l & ? #h24PkP#Architecture P  = ArchitectureK%6j = V #h24PkP#(30%) P  S (30%)R,= #h24PkP#Experimental P  ExperimentalM'8X#h24PkP#Systems P SystemsK%6+#h24PkP#(54%) P (54%)N(98 i7 <#h24PkP#Computer P  9ComputerM'8j  R#h24PkP#Systems P  PSystemsK%6  i#h24PkP#(16%) P  g(16%)H!3'B#:}D4P XP# P  H!3)#:}D4P XP# P  X  `UUUUUUUUUUUUU _~~3Z _~~3Zp p< _~~3 _~~3p<o_ _~~[ _~~[o_opo  _~~Z[ _~~Z[opo p P*; #]24PkP#Graphics & P   Graphics &a;L$ #]24PkP# Solid Modelling P ! Solid ModellingM'8#]24PkP#General P 'GeneralM'8#]24PkP#Purpose P PurposeO):x7U#]24PkP#Computing P  ComputingQ+<nm#]24PkP#Application P  ApplicationN(9 #]24PkP#Specific P SpecificO):+\#]24PkP#Computing P  ComputingK%6;.  #]24PkP#Other P  Other  H"3o R  #:}D4P XP# P   H"3S#:}D4P XP# P   ^  `UUUUUUUUUUUUU uu+Z uu+Z'' 'W  uu+ uu+'W '76 uu uu'76s uu uus uu uu(  uuZ uuZ( '' L&7/] #]24PkP#Theory P z. TheoryL&7#]24PkP#Design P SDesignP*;r #]24PkP#Automation P  AutomationO):". #]24PkP#- Generic P  - GenericW1BJ#]D4P P#Design Automation P Design AutomationR,=a#]D4P P#Applications P  ApplicationsM'8#]D4P P#Testing P .TestingO):CL#]D4P P# Generic P  $ GenericM'8X#]D4P P#Testing P TestingR,=F#]D4P P#Applications P  ApplicationsP*;^b *$ #]24PkP#Simulation P  2 Simulation* H"3  u #:}D4P XP# P * } H"3S#:}D4P XP# P  ''  UUUUUUUUUUUUU Z Z_q  M< M<M Mw  < < _{ O OGGY AZ AZAcQ L&7 j #]24PkP#Design P  DesignK%6 8 #]24PkP#Tools P  ToolsG!2> , #]24PkP#& P  &J$5T   #]24PkP#Test P % $ TestU/@  #]24PkP#Microelectronic P  MicroelectronicM'8  #]24PkP#Systems P  SystemsR,=( )z #]24PkP#Architecture P  s ArchitectureN(9J#]24PkP#Circuits P !YCircuitsG!2r#]24PkP#& P &L&7#]24PkP#Signal P SSignalP*;P` #]24PkP#Processing P  ProcessingV0AGP#]24PkP# Systems P ! SystemsQ+<Gxg:#]24PkP#Prototyping P  HPrototypingS->GLa#]24PkP# & P  o &Q+<GF#]24PkP#Fabrication P  FabricationR,=x #]24PkP#Experimental P  ? ExperimentalM'8 #]24PkP#Systems P SystemsH"3Sp#:}D4P XP# P  H"3=d#:}D4P XP# P   2   UUUUUUUUUUUUU F~ulZ F~ulZN  N  F~uZl F~uZl N N Y3D|#]24PkP#Systems Prototyping P .Systems PrototypingU/@6#]24PkP#and Fabrication P and FabricationO):  #]24PkP#Education P  . Education H"3 S #:}D4P XP# P Q  H"3 I #:}D4P XP# P  "   `UUUUUUUUUUUUU R~DZ R~DZc c. }  R~ID R~IDc. } Rd  R~I R~IRd |Rb R~ R~|Rb|c@ R~s R~s|c@|cl  R~Zs R~Zs|cl c N(9 #]24PkP#Circuits P  CircuitsJ$56 T #]24PkP#One- P  %One-Q+<<|} >#]24PkP#Dimensional P  LDimensionalL&7  e#]24PkP#Signal P O sSignalP*;]m #]24PkP#Processing P  ProcessingW1Bl6 .#]24PkP#Multi-Dimensional P =Multi-DimensionalW1BuG V#]24PkP#Signal Processing P dSignal ProcessingM'89#]24PkP#Digital P \ DigitalT.?`"#]24PkP#Representation P 01RepresentationT.?} #]24PkP#Implementation P ImplementationS-> z #]24PkP#Miscellaneous P   Miscellaneousf H"3 SW #:}D4P XP# P #  H"39 #:}D4P XP# P   ^  `UUUUUUUUUUUUU uu+Z uu+Z   uu+ uu+ 6 uu uu6s uu uus# uu uu#  uuZ uuZ  L&7]| #]24PkP#Theory P . TheoryL&7rU#]24PkP#Design P DesignP*;#]24PkP#Automation P  'AutomationO):"#]24PkP#- Generic P  i- GenericW1B<#]D4P P#Design Automation P Design AutomationR,=&#]D4P P#Applications P  qApplicationsM'8M#]D4P P#Testing P TestingO): C#]D4P P# Generic P  U$ GenericM'8#]D4P P#Testing P  TestingR,= #]D4P P#Applications P  UApplicationsP*;b $ #]24PkP#Simulation P  2 Simulation H"3 S #:}D4P XP# P }  H"3 I #:}D4P XP# P   Figure 1 XX Figure 1 ! jx)XX'ddx The Foundation provides awards for research in the sciences and engineering. The awardee is wholly responsible for the conduct of such research and preparation of the results for publication. The Foundation, therefore, does not assume responsibility for such findings or their interpretation. The Foundation welcomes proposals on behalf of all qualified scientists and engineers, and strongly encourages women, minorities, and persons with disabilities to compete fully in any of the research and researchrelated Programs described in this document.  xQ  }Q4-> xiA Facilitation Awards for Scientists and Engineers with Disabilities }V [ PA  provide funding for special assistance or equipment to enable persons with disabilities (investigators and other staff, including student research assistants) to work on an NSF project. See the program announcement, or contact the program coordinator in the Directorate for Education and Human Resources. In accordance with Federal statutes and regulations and NSF policies, no person on grounds of race, color, age, sex, national origin, or disability shall be excluded from participation in, denied the benefits of, or be subject to discrimination under, any program or activity receiving financial assistance from the National Science Foundation.  xQ #}Q4-> xiA#Privacy Act and Public Burden#}V [ PAP#. Information requested on NSF application materials is solicited under the authority of the National Science Foundation Act of 1950, as amended. It will be used in connection with the selection of qualified proposals and may be used and disclosed to qualified reviewers and staff assistant as part of the review process and to other government agencies. See Systems of Records, NSF50, "Principal Investigator/Proposal File and Associated Records," and NSF51, "Reviewer/Proposals File and Associated Records," 56 Federal Register 54907 (Oct. 23, 1991). Submission of the information is voluntary. Failure to provide full and complete information, however, may reduce the possibility of your receiving an award. The public reporting burden for this collection of information is estimated to average 120 hours per response, including the time for reviewing instructions. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to: Herman G. Fleming, Reports Clearance Officer, Division of CPO, NSF, Arlington, VA 22230; and to the Office of Management and Budget, Paperwork Reduction Project (31450058), Wash., DC 20503. The National Science Foundation has TDD (Telephonic Device for the Deaf) capability, which enables individuals with hearing impairment to communicate with the Division of Human Resource Management about NSF programs, employment, or general information. The number is (703) 3060096 effective 11/15/93.  xQ  }Q4-> xiA Ordering by Electronic Mail }V [ PA  If you are a user of electronic mail and have access to either BITNET or INTERNET, you may order publications electronically. BITNET users should address requests to pubs@nsf. INTERNET users should send requests to pubs@nsf.gov. In your request, include the NSF publication number and title, number of copies, your name, and a complete mailing address. Publications will be mailed within 2 days of receipt of request. Catalog of Federal Domestic Assistance Number 47070; Computer and Information Science and Engineering.$(#(#(#(#!'#$00*0*0*'#.*!0    margins XX  XX  cLBorder XXXX XX Figure 1 !xxxx Figure 1 yA(#,XXxxxxXdd(#,yPreface(ǎPreface`l$%m((A`p#%hPreface( XX   b  5Prognam x~> pA! v8PrefacePrognam }V [ PA ۃ 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, CrossDisciplinary 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.  xQj The  Microelectronic Information Processing Systems Division (MIPS)  supports research on novel computing and information processing systems including signal processing. Emphasis is on experimental research, technologyrelated research and particularly the critical link between conceptualization and realization for integrated systems. Technologies include VLSI, ULSI, OPTICAL, OPTOELECTRONIC, INTERCONNECTION 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; technologydriven and applicationdriven systems architectures; and fabrication and testing of systems. For signalprocessing systems, research on algorithms and architectures relating to these new technologies that have promise for realtime 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 multiyear 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. 5Bernard Chern t3Division Director .Microelectronic Information .Processing Systems Division $.P-P-XX = 1 ""xx< 1 B!"  xx<LddqI<  b #x~> pA!ż#e The 1993 MIPS Summary of Awards is dedicated to:   # [ PASưP# Leona M. Berghaus#x~> pA!ż# ă on the occasion of her retirement from  The National Science Foundation  b after years of dedicated Federal service#}V [ PAP#у B0=...XX  K !0  cLBorder XXXX xxxx Figure 1 Axxxx Figure 1 ya(#,XXxxxxXdd(#,yTOC-Footer2O qITable of Contents`"(#f22P I` (#WTable of Contents2  b 5Prognam x~> pA! `3Table of Contents#Prognam }V [ PA ۃ    X Preface p"(#eiii X Table of Contents pl"(#e v X The MIPS Division p|"(#evii X MIPS Directions px"(#e ix X MIPS Staff px"(#e xi X Program Pie Charts pH"(#d xii X Summary pP"(#dxiii X Design, Tools and Test pd"(#e 1 XX` ` The Program ` pd"(#e 1 XX` ` Initiatives and Opportunities ` pd"(#e 2 XX` ` Awards ` pd"(#e 3 XX` ` X "` ` Theory pd"(#e 3 XX` ` X "` ` Design Automation Generic pd"(#e 4 XX` ` X "` ` Design Automation Applications p"(#f 9 XX` ` X "` ` Testing Generic pH"(#e 12 XX` ` X "` ` Testing Applications pH"(#e 14 XX` ` X "` ` Simulation pH"(#e 15 X Microelectronic Systems Architecture pH"(#e 19 XX` ` The Program ` pH"(#e 19 XX` ` Initiatives and Opportunities ` pH"(#e 20 XX` ` Awards ` pH"(#e 21 XX` ` X "` ` Technology Driven Architecture pH"(#e 21 XX` ` X "` ` Application Driven Architecture pH"(#e 28 XX` ` X "` ` Workshops and Conferences pH"(#e 32 X Circuits and Signal Processing pH"(#e 33 XX` ` The Program ` pH"(#e 33 XX` ` Initiatives and Opportunities ` pH"(#e 34 XX` ` Awards ` pH"(#e 35 XX` ` X "` ` Circuits pH"(#e 35 XX` ` X "` ` OneDimensional Digital Signal Processing pH"(#e 36 XX` ` X "` ` Multidimensional Digital Signal Processing pH"(#e 39 XX` ` X "` ` Digital Representation pH"(#e 44 XX` ` X "` ` Implementation pH"(#e 47 XX` ` X "` ` Miscellaneous pH"(#e 48 &.P-P-XX  cLBorder XXXX xxxx Figure 1 axxxx Figure 1 y(#,XXxxxxXdd(#,y X Experimental Systems pH"(#e 51 XX` ` The Program ` pH"(#e 51 XX` ` Initiatives and Opportunities ` pH"(#e 52 XX` ` Awards ` pH"(#e 53 XX` ` X "` ` Graphics and Solid Modelling pH"(#e 53 XX` ` X "` ` General Purpose Computing pH"(#e 54 XX` ` X "` ` Application Specific Computing pH"(#e 57 XX` ` X "` ` Other pH"(#e 59 X Systems Prototyping and Fabrication p"(#f61 XX` ` The Program ` p"(#f61 XX` ` Initiatives and Opportunities ` p"(#f62 XX` ` Awards ` p"(#f63 XX` ` X "` ` Systems Prototyping and Fabrication p"(#f63 XX` ` X "` ` Education p"(#f70 X Index of Presidential Young Investigators p"(#f71 X Index of Research Initiation Investigators p"(#f73 X Index of Principal Investigators p"(#f75 X Index of Institutions p"(#f79 8.P-P-XX  margins XXXX  XX  cLBorder XXXX xxxx Figure 1 xxxx Figure 1 y(#,XXxxxxXdd(#,yaIntro-footO P -Introduction`l$%m--X`!%cIntroduction- XX   b  x~> pA! I $Microelectronic Information Processing Systems }V [ PA у  Y  pA3 The MIPS Division6catname }V [ PA  XThe 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.(# XThe 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.(#  Y#  pA3 The Programs{=catname }V [ PA   Y l, g~> pA3 Design, Tools and Test Program }V [ PA у XThe 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.(#  Y  & g~> pA3 Systems Prototyping and Fabrication Program }V [ PA у XSupports 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).(#  Y$  % g~> pA3 Microelectronic Systems Architecture Program }V [ PA у XSupports 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 proofofconcept prototyping.(#+.P-P-XX  cLBorder XXXX xxxx Figure 1 xxxx Figure 1 y(#,XXxxxxXdd(#,y  Y  ( g~> pA3 Circuits and Signal Processing Program }V [ PA у XSupports 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, specialpurpose hardware, and realtime computing. Circuit theory research encompasses such activities as nonlinear, discretetime, analog and hybrid circuits, and analog/ digital conversion.(#  Y - g~> pA3 Experimental Systems Program }V [ PA у XSupports research experiments that involve building and evaluating information processing and computing systems. These are goaloriented 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.(#  : yp4dddy 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. xxxx Figure 1  Figure 1 y}t }t ddARCH-A_p<y R.P-P-XX  margins XXXX  XX X` hp x (#%'0*,.8135@8: pA! 4MIPS DirectionsSPrognam }V [ PA ۃ MIPS' planning takes into account advances in technology and new knowledge, and the need for closer ties  xQ of computer science and engineering to real world applications. Greater emphasis is now placed on complete  xQ 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:  Yl  g~> pA3 /hBasic research (hardware & system software) on new high performance computer architectures and computing systems;(# /hDevelopment of tools & CAD frameworks for their design, analysis and realization;(# /hAlgorithm development and computational techniques for grand challenge problems in the areas of research supported by MIPS.(#  }V [ PA  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.  xQ hThe Microelectronic Systems Architecture Program seeks to provide new architectural ideas and technological innovations by exploring novel architectures capable of high performance. (#  xQ hThe Experimental Systems Program concentrates on the prototyping, experimentation with, and evaluation of promising new computer architectures and hardware/software computing systems. (#  xQ5! hThe 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).(#  xQ% hThe Design, Tools and Test Program focuses on high performance computing system design tools and methodologies.(#  xQ?( hThe 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.(# *.P-P-XX  cLBorder XXXX xxxx Figure 1 xxxx Figure 1 y!(#,XXxxxxXdd (#,y  b 5Prognam x~> pA! (.MIPS Directions (continued)QcPrognam }V [ PA ۃ 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.XWork more closely with the applications as we move toward higher performance computing to understand the computing needs of these applications.(# @2.XIntegrate advanced packaging technology into computing system design and explore the system level tradeoffs arising in the design of high performance computing systems.(# @3.XDevelop 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.XDevelop 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.XSupport geographically distributed collaborative novel computing system design requiring expertise from many areas (e.g., architecture, software, storage technology, I/O, applications, etc.). (# @6.XDevelop a new generation of systems level design tools which have increased functionality, are highly automated, and accept high level specifications as inputs.(#  xQz $ 10b/10 }U~> pAG MIPS and the Advanced Manufacturing Technology Initiativejm10b/10 }V [ PA ۃ MIPS' role focuses on Manufacturing Design, Modeling and Simulation, and on Information Technologies for Manufacturing. Key R&D areas include:  Y  g~> pA3 /X#}V [ PAP#Mathematical, Physical and Computer Models of Artifacts and Manufacturing Processes and Systems.(#  Y  g~> pA3 /X#}V [ PAP#Integrated computer representation of the manufacturing system at all levels material, tool, machine, cell, assembly operation, and the entire enterprise.(#  Y"  g~> pA3 /X#}V [ PAP#Advanced CAD Tools, frameworks and integrated systems for manufacturing Design.(#  Y#  g~> pA3 /X#}V [ PAP#Simulation Tools and Systems needed for representing future virtual manufacturing systems.(#  Y%  g~> pA3 /X#}V [ PAP#High Performance Application Specific Computing Systems for manufacturing .(#  Y0'  g~> pA3 /X#}V [ PAP#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.q* .P-P-XX  cLBorder XXXX xxxx Figure 1 !xxxx Figure 1 yA(#,XXxxxxXdd (#,y cStaff m%n%c;;TDivision of Microelectronic Information Processing Systems Staff`"(#fcc;M`<(#&Division of Microelectronic Information Processing Systems Staffc  b   x~> pA! 6Division of  $Microelectronics Information Processing Systems  b> 6MIPS Staff }V [ PA у 5Bernard Chern t3Division Director 4bchern@nsf.gov ^4John R. Lehmann R/Deputy Division Director T3jlehmann@nsf.gov X` hp x (#%'0*,.8135@8:@nsf ` ` The address and telephone number for all of the above:x` .National Science Foundation X34201 Wilson Blvd. J/Arlington, Virginia 22230 ; 4(703) 3061936 P' .P-P-XX  l  cLBorder XXXX xxxx Figure 1 Axxxx Figure 1 ya(#,XXxxxxXdd (#,y summary foot;;( ?+Summary`"(#f(( ?c` (#aSummary(xxxx Figure 1 axxxx Figure 1  U 1  1 yH ` xxxx` X ddES-_A <yy N p` xxxxp` ^ ddDTT-A ` yy  xxxx '' ddMIPS-A yy " xxxxxx 2 ddSPF-A yy (#xxxx(#"  ddCSP-A <yy! N xxxxxx ^ ddMSA-A y c~> pAA    MICROELECTRONIC INFORMATION PROCESSING SYSTEMS 7DIVISION  }V [ PA   Pp   Experimental Systems  p   Design, Tools and Test  p  ( Systems Prototyping  (  and Fabrication      Microelectronic Systems     Architecture  !    Circuits and   Signal Processing  .P-P-XX  cLBorder XXXX xxxx Figure 1 !xxxx Figure 1 yA(#,XXxxxxXdd (#,y  bX  x~> pA! 8Summary }V [ PA у  xP ` x  }U~> pAG NNumber aDollars  X(#" }V [ PA  Design, Tools and Test@`Q58@8 (#^$4,116,233 Theory@R7@ (#`$540,800 Design Automation Generic@`Q19@8 (#^$1,491,051 Design Automation Applications@`Q10@ (#`$532,426 Testing Generic@R8@ (#`$529,458 Testing Applications@R7@ (#`$556,528 Simulation@R7@ (#`$465,970 Microelectronic Systems Architecture@`Q49@8 (#^$3,788,560 Technology Driven Architecture@`Q32@8 (#^$2,873,490 Application Driven Architecture@`Q16@ (#`$903,470 Workshops and Conferences@R1@!(#a$11,600 Circuits and Signal Processing@`Q54@8 (#^$4,032,372 Circuits@R3@ (#`$253,223 OneDimensional Digital Signal Processing@`Q14@8 (#^$1,083,818 Multidimensional Digital Signal Processing@`Q19@8 (#^$1,397,639 Digital Representation@R8@ (#`$732,810 Implementation@R6@ (#`$273,238 Miscellaneous@R4@ (#`$291,644 Experimental Systems@`Q27@8 (#^$7,072,859 Graphics and Solid Modelling@R5@ (#`$785,814 General Purpose Computing@`Q13@8 (#^$3,468,737 Application Specific Computing@R7@8 (#^$2,713,808 Other@R2@ (#`$104,500 Systems Prototyping and Fabrication@`Q28@8 (#^$2,230,633 Systems Prototyping and Fabrication@`Q26@ (#_2,125,157 Education@R2@!(#a105,506  yO!  }S `> XiA This summary data includes funds designated for special Foundation initiatives, and equipment matching funds from the Office of CrossDisciplinary 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.  }V [ PA  $ .P-P-XX = =...XX  b   MASTER.DTT  margins XXXX  XX ϡprogdefXtd%"ȪprogtabX(#""Ȫprogtab  Bdtt-foot ? ?E  y(#XXdddy Design, Tools and Test Program`l$%mE)  y(#XXdddy `T%QDesign, Tools and Test Program5Prognam x~> pA! ]0Design, Tools and TestݓPrognam }V [ PA ۃ 'Dr. Robert B. Grafton, Program Director , (703) 3061936 rgrafton@note.nsf.gov  Y  pA3 6The Program3catname }V [ PA ۃ  XX X4` H(#T$ 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, hardwaresoftware codesign; 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.!  xQ  4 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.  xQt' 8 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. ]+.x,x,XXԌ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.  Y( - pA3 Initiatives and Opportunities catname }V [ PA ۃ 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: *XApplication of EDA theory, tools and methods to the AMT area.  *XModels of computation which reflect the specific needs of high performance computing, or of AMT. (e.g. high density, high speed)  *XAlgorithms and tools for solving HPCC or AMT system design problems.  *XHigh performance system synthesis, including interconnect problems for systems of chips, on-chip data management, design validation, and test.  *XTools for creating designs with novel features that may occur in HPCC and AMT systems.  *XParallelism as a model of computation for electrical and optical mediums.  *XValidation 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.  *XAccurate 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.i&.x,x,XX  Y  margins XXXX  XX "ȪprogtabX4` H(#T$8 pA3 Awardscatname }V [ PA ۃ  Yy  pA3 8Theory߮catname }V [ PA ۃ  xP ԇ }U~> pAG  University of Florida ; Sartaj SahniSahni, Sartaj;  }Q4-> xiA High Performance Solutions  xP to VLSI CAD Problems }U~> pAG ; (MIP9103379 A01); $92,329; 12 months.  }V [ PA  ,  Three areas of computationaly efficient algorithms for design of IC's are under investigation.H ,  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.H ,  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.H ,  3.Module orientation and rotation problems for a variety of design styles are being examined to determine which are NPhard and polynomially solvable. Approximation algorithms, heuristics, and polynomial algorithms are being developed for the NPhard problems.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H  xP  }U~> pAG  Northwestern University ; Majid SarrafzadehSarrafzadeh, Majid;  }Q4-> xiA Algorithm Design  xP for VLSI Layout }U~> pAG ; (MIP9207267 & A01); $115,000; 24 months.  }V [ PA  ,  The research is in four areas of geometric algorithms for design tools. The research topics are:H ,  1.floor planning by graph dualization;H ,  2.placement of modules by exploiting circuit regularities;H ,  3.rectilinear Steiner tree problems; andH ,  4.point dominance problems.H ,  In floorplanning, 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:+.x,x,XX single layer routing using Steiner trees are being investigated. Point dominance, from computational geometry, is being applied to circuit layout problems.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of Minnesota ; Clark ThomborsonThomborson, Clark;  }Q4-> xiA Algorithms for  xP VLSI Design }U~> pAG ; (MIP9023238 A02 & A03); $71,502; 12 months.  }V [ PA  ,@CThe 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 greyscale images on a monochrome display terminal or laser printer is being explored. Algorithms, amenable to speedup on parallel or pipelined computers, are sought.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP!  }U~> pAG  New York University ; Robert PaigePaige, Robert and Jaizhen CaiCai, Jaizhen;  }Q4-> xiA A Transformational Programming Environment for Hardware  xP" Specifications }U~> pAG ; (MIP9300210); $50,000; 12 months.  }V [ PA  ,@CThis 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 VHDLlike specifications, symbolic analysis of these specifications, and correctness preserving sourcetosource8:+.x,x,XX,11x,x,XX8 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.H ,  This grant is made under the Small Grants for Exploratory Research (SGER) program.H  xP`  }U~> pAG  State University of New York Stony Brook ; Armen  xP( ZemanianZemanian, Armen;  }Q4-> xiA VLSI/ULSI Parameter Computations }U~> pAG ; (MIP9200748); $50,000; 24 months.  }V [ PA  ,  This research is on three dimensional modeling methods for predicting performance and characteristics of VLSIULSI circuits and devices. The research topics are:H ,  1.three dimensional corner corrections for capacitance calculations;H ,  2.inductance computations and transmission line parameters; andH ,  3.dominant paths in interconnect networks including path ranking. These computations are needed for assessment of delay times in offchip 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.H .x,x,XX  xP  }U~> pAG  University of Virginia ; James P. CohoonCohoon, James P. and Jeffrey S.  xP SaloweSalowe, Jeffrey S.;  }Q4-> xiA Next Generation Research in Physical Design }U~> pAG ; (MIP9107717 A02); $99,469; 12 months.  }V [ PA  ,@CThis 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 multilayer and multinet 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 floorplanning, Steiner routing, and identification of critical nets. Algorithms are being integrated into a tool for overall design, and a visualization tool is being developed.T$  xP  }U~> pAG  University of Washington ; Steven M. BurnsBurns, Steven M. NYI;  }Q4-> xiA NYI: A Design  xP Language for Asynchronous Circuit Synthesis }U~> pAG ; (MIP9257987 A01); $62,500; 12 months.  }V [ PA  ,@CThis 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.T$8 .x,x,XXW]3x,x,XX8ԯ  Y#  pA3 .Design Automation Genericcatname }V [ PA ۃ  xPi& ԇ }U~> pAG  Stanford University ; David DillDill, David PYI;  }Q4-> xiA PYI: Automatic Verification of  xP1' FiniteState Concurrent Systems }U~> pAG ; (MIP8858807 A05); $62,500; 12 months.  }V [ PA  ,  Research is on the verification of finitestate concurrent systems, both abstract systems and their implementations in hardware. The approach is to+.x,x,XX 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 realworld designs. Additionally, effort is being made to characterize conditions under which verification is8+.x,x,XX+i&x,x,XX8 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.H  xPx  }U~> pAG  University of California Berkeley ; Ernest KuhKuh, Ernest;  }Q4-> xiA Design Methodologies for High-Density, High-Performance,  xP Wire-Dominated Chips and Multichip Modules }U~> pAG ; (MIP9117328 A01); $200,000; 12 months.  }V [ PA  ,  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.H ,  The long term goal of this research is to find a new CAD methodology for designing highperformance 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 floorplanning; such as, performancedriven 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.H  xP@  }U~> pAG  University of California Davis ; Venkatesh AkellaAkella, Venkatesh RIA;  }Q4-> xiA RIA:  xP High-Level Synthesis of Self-Timed Circuits  }U~> pAG ; (MIP9308668); $100,000; 36 months.  }V [ PA  ,  This research is focused on developing a systematic approach for highlevel synthesis of selftimed 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:H ,  1.techniques for resource sharing based on flow analysis;H ,  2.efficient partitioning of a sequential specification into a set of communicating sequential processes;H*.x,x,XXԌ,@C3.Fdevelopment of a tool for gatelevel realizations of asynchronous circuits in SHILPA; andT$ ,@C4.Finvestigating graphical and VHDL interfaces to SHILPA.T$  xPx  }U~> pAG  University of California Irvine ; Nikil DuttDutt, Nikil RIA;  }Q4-> xiA RIA: Design  xP@ Conceptualization for High Level Synthesis of Hardware }U~> pAG ; (MIP9009239 A02); $5,000.  }V [ PA  ,@CThis 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:T$ ,@C1.FAn environment for high level synthesis which provides multiple input media for design conceptualization and capture;T$ ,@C2.FInclusion of partially designed structures and user bindings into the environment;T$ ,@C3.FModeling guidelines for design description in VHDL which support high level synthesis and simulation.T$ ,@CThis supplement provides support for a minority graduate student.T$  xP  }U~> pAG  University of California Irvine ; Daniel GajskiGajski, Daniel;  }Q4-> xiA System  xP Synthesis From Specification Charts }U~> pAG ; (MIP8922851 A03); $19,806.  }V [ PA  ,@CResearch 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:T$ ,@C1.Fdefinition of the specification charts language;T$ ,@C2.Fdetermining how to translate the language into VHDL;T$ ,@C3.Falgorithms for partitioning the specifications into system components (e.g. chips) and for quality estimations using system quality measures;T$ ,@C4.Fincorporation of interface synthesis into system synthesis; andT$ ,@C5. evaluation of the tools being developed.T$ ,@CThis grant includes support for NSFESPRIT cooperation.T$8*.x,x,XX+??x,x,XX8  xP  }U~> pAG  University of California Los Angeles ; Jason CongCong, Jason NYI;  }Q4-> xiA NYI:  xP Synthesis and Mapping in LookupTable Based FPGA Designs }U~> pAG ; (MIP9357582); $25,000; 12 months.  }V [ PA  ,  Synthesis and Mapping are necessary steps in designing Field Programmable Gate Arrays (FPGAs), and this research is a systematic study of these problems in lookup table based FPGA designs. Questions being investigated include: effects of node duplication, effects of depth relaxation, and effects of logic resynthesis during mapping and systemlevel partitioning mapping in multiple chip FPGA designs. Algorithms being developed are:H ,  1.for computing optimal or near optimal synthesis or mapping solutions under a given objective function; andH ,  2.for synthesizing a set of mapping solutions of smooth trade off between various design objectives, such as area, delay and routability.H ,  Computational methods for integrating the synthesis and mapping steps in FPGA designs based on combinatorial and Boolean optimization techniques are being investigated.H  xPP  }U~> pAG  University of California Los Angeles ; Andrew KahngKahng, Andrew NYI;  }Q4-> xiA NYI:  xP Synthesis of HighSpeed, HighComplexity VLSI Systems }U~> pAG ; (MIP9257982 A01); $25,000; 12 months.  }V [ PA  ,  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.H ,  1.Performance-driven synthesis at various levels of design, including clustering for problem decomposition and fast hierarchical placement, and estimation of intrinsic resource requirements via topological criteria.H ,  2.Assessment of design problem complexity based on the interaction between topology of neighborhood structures and scaling geometry in the associated cost surfaces. This includes time-bounded stochastic optimizations, and a non-monotone class of annealing methods.H ,  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.Hh).x,x,XX  xP  }U~> pAG  University of Colorado ; Gary HachtelHachtel, Gary, Michael LightnerLightner, Michael and  xP Fabio SomenziSomenzi, Fabio;  }Q4-> xiA Synthesis and Verification of Combinational,  xP Sequential and Behavioral Logic }U~> pAG ; (MIP9115432 A02 & A03); $293,064; 12 months (Joint support with the Advanced Research Projects Agency Total Grant $654,865).  }V [ PA  ,@CThis a joint project with Colorado, (G. Hachtel, M. Lightner and F. Somenzi), UC, Berkeley (R.K. Brayton, A.R. Newton and A. SangiovanniVincentelli), 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:T$ ,@C1.FPerformance oriented synthesis through realistic modeling and delay/area tradeoff optimization;T$ ,@C2.FMaximization of testability; andT$ ,@C3.FExploiting partitioning to solve both chip and multichip module design problems.T$ ,@CThe model is of sequential circuits based on a network of interacting, possibly nondeterministic, 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. T$ ,@CResearch topics are:T$ ,@C1.Falgorithms and theory for logic manipulation to support a variety of applications;T$ ,@C2.Fdesign, synthesis, and formal approaches based on the theory and algorithms;T$ ,@C3.Fdesign of embedded controllers, including hardwaresoftware codesign; andT$ ,@C4.Fapplication of logic techniques to "nonstandard" areas such as machine learning, theorem proving and combinatorics.T$ ,@CA set of coordinated synthesis tools is being  xQ produced. The tools operate at both high level or  xQ low level depending on whether they operate above or below the FSM model.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xPJ&  }U~> pAG  University of Illinois ; C. L. LiuLiu, C. L.;  }Q4-> xiA Research in Computer-Aided  xP' Design of VLSI Circuits }U~> pAG ; (MIP9222408 & A01); $91,000; 24 months.  }V [ PA  ,@CThe research is on algorithms for high level synthesis and layout of VLSI CAD designs. Algorithms for complex, large industrial type design8*.x,x,XX0*vxAx,x,XX8 problems are being developed. Research topics include:H ,  1.high level synthesis with testability as an important goodness measure,H ,  2.timing driven placement algorithms for EPGAs, andH ,  3.channel and switchbox routing in which the effect of cross talk is to be taken into consideration.H ,  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.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H  xP  }U~> pAG  Indiana University ; Steven JohnsonJohnson, Steven;  }Q4-> xiA Decomposing  xPP Digital-System Specifications Into Interacting Sequential Processes }U~> pAG ; (MIP9208745 & A01); $142,196; 24 months.  }V [ PA  ,  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:H ,  1.theoretical studies of the decomposition of digital systems; especially formal derivation of control-synchronization and datacommunication protocols;H ,  2.automation of formal transformations which correctly do sequential decompositions;H ,  3.integration of the mechanized formal system with available CAD tools, and other reasoning systems; andH ,  4.application of the design system to meaningful examples of digital-system designs.H  xP'  }U~> pAG  Massachusetts Institute of Technology ; Srinivas DevadasDevadas, Srinivas NYI;  xP'  }Q4-> xiA NYI: Formal Methods for Hardware and Software Verification }U~> pAG ; (MIP9258376 A01); $62,500; 12 months.  }V [ PA  ,  Research is on logic and behavioral verification of VLSI circuit designs, and application of hardware*.x,x,XX verification techniques to software verification. Topics include:T$ ,@C1.FUse 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.T$ ,@C2.FAutomatic 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 microprocessors against instruction set specifications.T$ ,@C3.FFBDD 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.T$  xP   }U~> pAG University of Massachusetts Amherst ; Premachandran  xP MenonMenon, Premachandran;  }Q4-> xiA Optimization of Multilevel Logic }U~> pAG ; (MIP9311185); $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).  }V [ PA  ,@CThis 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. T$ 8*.x,x,XX+zx,x,XX8Ԍ xP ԙ }U~> pAG  Princeton University ; Malik, Sharad RIA Sharad Malik;  }Q4-> xiA RIA: Accurate and  xP Efficient Timing Verification of Synchronous Digital Circuits }U~> pAG ; (MIP9209805 A01); $5,000.  }V [ PA  ,  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.H ,  This grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.H  xP0  }U~> pAG  Princeton University ; Wayne WolfWolf, Wayne;  }Q4-> xiA Control Minimization and  xP Performance Optimization for HighLevel Synthesis }U~> pAG ; (MIP9121901 A02); $64,740; 12 months.  }V [ PA  ,  Research is on the relationship between highlevel control specifications and the finite state machine (FSM) implementation of that control. Models for two problems in highlevel control synthesis are being explored: Analysis of delays in mixed datacontrol systems before scheduling; and scheduling in complex control systems.H ,  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.H ,  This grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.H  xP%  }U~> pAG  Columbia University ; Steven M. NowickNowick, Steven M. RIA;  }Q4-> xiA RIA: The Design of  xPH& High-Performance Asynchronous Controllers }U~> pAG ; (MIP9308810); $100,000; 36 months.  }V [ PA  ,  This research concerns the development of algorithms and software tools for the design of asynchronous circuits. Previous work in the area has produced a "locallyclocked" asynchronous design*.x,x,XX style, which produces high performance implementations that are hazardfree 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 hazardfree logic minimization. The extensions include: a heuristic twolevel minimization algorithm; an exact productofsums solution; timeoptimized multilevel logic synthesis; testing oriented twolevel minimization; and hazarddecreasing, multilevel transforms. Third is an exploration of systematic ways to test asynchronous designs.T$  xP  }U~> pAG  Carnegie Mellon University ; Edmund M. ClarkeClarke, Edmund M.;  }Q4-> xiA Automatic Verification of FiniteState Concurrent Systems in Hardware and  xPh Software }U~> pAG ; (CCR9217549); $37,000; 12 months (Joint support with the Knowledge and Database Systems Program Total Grant $148,300).  }V [ PA  ,@CLogical 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 nontrivial designs. T$  xP!  }U~> pAG  Pennsylvania State University ; Barry M. PangrlePangrle, Barry M.;  }Q4-> xiA Control and  xP`" Layout Issues in PerformanceDriven, HighLevel Synthesis }U~> pAG ; (MIP9118440 A01); $60,012; 12 months.  }V [ PA  ,@CThis 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 highlevel 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 scheme8*.x,x,XX+x,x,XX8 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.H  xP  }U~> pAG  University of Pittsburgh ; Steven LevitanLevitan, Steven;  }Q4-> xiA Temporal  xP Specification Verification }U~> pAG ; (MIP9102721 A01); $68,885; 12 months.  }V [ PA  ,  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.HX.x,x,XX  xP  }U~> pAG  University of Utah ; Erik BrunvandBrunvand, Erik and Ganesh  xP GopalakrishnanGopalakrishnan, Ganesh;  }Q4-> xiA The Design of Asynchronous Circuits and  xP Systems with Emphasis on Correctness and Proven Optimizations }U~> pAG ; (MIP9215878); $77,577; 24 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $155,154).  }V [ PA  ,@CThis 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:T$ ,@C1.Fenhancing the expressive power as well as the semantic clarity of concurrent hardware description languages for asynchronous circuits and systems;T$ ,@C2.Fextending the formal basis for compiling from HDL's to circuit designs;T$ ,@C3.Fformally characterizing and improving the optimizations used in asynchronous circuit compilation; andT$ ,@C4.Fstudying the performance of implemented circuits with regard to a variety of parameters.T$80.x,x,XX x,x,XX8ԯ  Y@  pA3 &+Design Automation ApplicationsBcatname }V [ PA ۃ  xP" ԇ }U~> pAG  Tanner Research ; John TannerTanner, John;  }Q4-> xiA Analog VLSI Neural Network  xPI# Employing A Novel Linear Synapse }U~> pAG ; (ISI9307452); $249,936; 24 months.  }V [ PA  ,  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 stateoftheart 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+.x,x,XX synapse. A full scale prototype chip that implements onchip learning, and contains up to 650,000 synapses is being developed. The chip design enables interconnection of several chips in order to form a multilayer 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.T$8'.x,x,XX+ "x,x,XX8  xP  }U~> pAG  University of California Berkeley ; Jan RabaeyRabaey, Jan;  }Q4-> xiA High Level  xP Synthesis Techniques for VLSI }U~> pAG ; (MIP9222254); $4,981; 12 months (Joint support with the Circuits and Signal Processing and the Systems Prototyping and Fabrication Programs Total Grant $14,944).  }V [ PA  ,  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.H ,  This grant includes support for NSFESPRIT cooperation.H  xP  }U~> pAG  University of California Santa Cruz ; Wayne W. DaiDai, Wayne W. PYI;  }Q4-> xiA PYI:  xPP Computer Aided Design for VLSI Circuits }U~> pAG ; (MIP9058100 A03); 12 months (Joint support with the Systems Prototyping and Fabrication Program Total Grant $72,500).  }V [ PA  ,  Interconnection topology and metrics needed for laying out highspeed interconnections in multichip modules are being pursued. The first topic is optimal design of transmission lines for multichip modules (MCM). These are selfdamped lossy transmission lines in a tree network, which propagates highspeed signals. Algorithms to implement a robust method for designing these transmission lines are being developed. Attention is paid to distortionfree signal propagation, crosstalk, 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 interchip routing density. An algorithm with good fault tolerant properties that leads to uniform bus load and processor fanout is being developed.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H *.x,x,XXԌ xP ԙ }U~> pAG  University of California San Diego ; Alex OrailogluOrailoglu, Alex RIA;  }Q4-> xiA RIA:  xP Synthesis of Self Recovering and Fault Secure Microarchitectures }U~> pAG ; (MIP9308535); $100,000; 36 months.  }V [ PA  ,@CThis research is on automatic synthesis of faulttolerant microarchitectures. Two areas are being investigated. One is an exploration of methodologies and CAD tools for synthesis of selfrecovering microarchitectures. The model for selfrecovering designs is a flowgraph 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 faultsecure microarchitectures. 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.T$  xP0  }U~> pAG  Georgia Institute of Technology ; Abhijit ChatterjeeChatterjee, Abhijit RIA;  }Q4-> xiA RIA: Design Tools for Reliable Computations in Digital Signal  xP Processing and Control VLSI }U~> pAG ; (MIP9309740); $96,954; 36 months.  }V [ PA  ,@CThis 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 offline (passive) and online (active) method. The approach is to extract mathematical models of circuit behavior from highlevel 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 faulttolerance without regard to cost criteria such as node activity.T$  xP#  }U~> pAG  University of Illinois Urbana ; Farid NajmNajm, Farid RIA;  }Q4-> xiA RIA: Synthesis of  xP$ Reliable and Low-Power VLSI Circuits }U~> pAG ; (MIP9308426); $100,000; 36 months.  }V [ PA  ,@CThis 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:T$8*.x,x,XX+DD x,x,XX8Ԍ,  1. exploring use of circuit activity as a parameter to be minimized; andH ,  2. investigating the effects of minimizing local power dissipation on circuit design.H ,  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.H  xP`  }U~> pAG  University of Michigan ; Karem SakallahSakallah, Karem, Trevor MudgeMudge, Trevor and  xP( Edward DavidsonDavidson, Edward;  }Q4-> xiA Timing Verification and Optimal Clocking of  xP Latch-Controlled Synchronous Digital Circuits }U~> pAG ; (MIP9014058 A02); $37,000; 12 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $127,660).  }V [ PA  ,  This research is on the temporal modeling of latchcontrolled synchronous digital systems. The use of levelsensitive latches, as opposed to edgetriggered flipflops, 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.H ,  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.H  xP  }U~> pAG  University of Minnesota ; Eugene ShragowitzShragowitz, Eugene;  }Q4-> xiA Fuzzy Logic  xP Approach to Physical Design of VLSI and PCB }U~> pAG ; (MIP9123945 A01); $48,448; 12 months.  }V [ PA  ,  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 prelayout*.x,x,XX 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.T$  xP`  }U~> pAG  Carnegie Mellon University ; Donald ThomasThomas, Donald and Daniel  xP( SiewiorekSiewiorek, Daniel;  }Q4-> xiA Digital System Level Synthesis Tools }U~> pAG ; (MIP9112930 A03 & A04); $135,042; 12 months (Joint support with the Systems Prototyping and Fabrication Program Total Grant $260,084).  }V [ PA  ,@CThis research is on algorithms and techniques for systemlevel 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 systemlevel synthesis framework.T$ ,@CThis grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.T$  xPx  }U~> pAG  Carnegie Mellon University ; Roy M. MaxionMaxion, Roy M.;  }Q4-> xiA Discovering  xP@ Information in Large, HighDimensional Databases }U~> pAG ; (IRI9224544); $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).  }V [ PA  ,@CThis research is on discovering functional relationships among highdimensional data associated with manufacturing, such as VLSI production. In this case, hundreds of variables must be precisely controlled to achieve highquality yield. This research is investigating a number of new ideas for highdimensional, nonparametric regression which are largely untested with respect to their comparative performance in realistic situations. A largescale8*.x,x,XX+}}Fx,x,XX8 simulation experiment is being performed to evaluate the effects of sample size, dimensionality, signaltonoise 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 micromodeled 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.H.x,x,XX 8.x,x,XXx,x,XX8ԯ  Y(  pA3 3Testing Generic {catname }V [ PA ۃ  xP ԇ }U~> pAG  Colorado State University ; Carol Q. TongTong, Carol;  }Q4-> xiA Detection of  xPi Multiple Faults Using SSFTS in CMOS Logic Circuits }U~> pAG ; (MIP9307538); $17,985; 18 months.  }V [ PA  ,  A research program on the use of single stuckatfault 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.H ,  This is a Research Planning Grant for Women Scientists and Engineers.H  xPy   }U~> pAG Yale University ; Debashis BhattacharyaBhattacharya, Debashis;  }Q4-> xiA Efficient Parallel Techniques for Hierarchical Fault Simulation and Test  xP  Generation }U~> pAG ; (MIP9101966 A01 & A02); $72,802; 12 months.  }V [ PA  ,  This research is on:H ,  1.hierarchical fault simulation in coarse-grain MIMD parallel computers or distributed systems; andH ,  2.parallel test generation on MIMD parallel machines with and without shared memory. H ,  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. H +.x,x,XX ,@CA 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.T$  xP   }U~> pAG University of Iowa ; Irith PomeranzPomeranz, Irith and Sudhakar M. ReddyReddy, Sudhakar M.;  xP  }Q4-> xiA High-Quality Tests for Combinational Circuits }U~> pAG ; (MIP9220549); $164,586; 24 months.  }V [ PA  ,@CThis 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:T$ ,@C1.Fgeneration of small test sets for a comprehensive set of faults, including efficient treatment of path delay faults;T$ ,@C2.Fdesign for testability to allow faults undetectable in the original to be detected in a modified circuit; andT$ ,@C3.Fbuilt in test pattern generation based on the test sets produced when stored pattern tests cannot be used.T$81'.x,x,XX+' "x,x,XX8  xP  }U~> pAG  University of Iowa ; Irith PomeranzPomeranz,Irith PYI;  }Q4-> xiA PYI: A New Search  xP Strategy for Design Automation }U~> pAG ; (MIP9357581); $25,000; 12 months.  }V [ PA  ,  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 fullsized solutions are expected to have very high quality. Research problems being explored are:H ,  1.test generation for various fault models on designs given at the gate and higher levels;H ,  2.builtinselftest methods; andH ,  3.testing of synchronous sequential circuits that require two pattern tests.H  xP  }U~> pAG  University of Michigan ; John HayesHayes, John;  }Q4-> xiA Testing Complex Systems  xP with Reusable Tests }U~> pAG ; (MIP9200526 A01); $91,539; 12 months.  }V [ PA  ,  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:H ,  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;H ,  2.development of testpreserving 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; andH ,  3.finding methods for designing builtinselftesting circuits to provide localized input stimuli generation and response analysis for modules.H ,  Theorems and algorithms are being developed.H  xP$  }U~> pAG  Rutgers University ; Michael L. BushnellBushnell, Michael L. PYI;  }Q4-> xiA PYI: ComputerAided  xP% Design of ULSI Circuits }U~> pAG ; (MIP9058536 A03); $62,500; 12 months.  }V [ PA  ,  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*.x,x,XXԫbased, switchlevel algorithms for ATPG; parallel algorithms for ATPG; robust delay fault builtin 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.T$  xP  }U~> pAG  University of Texas ; Jacob AbrahamAbraham, Jacob;  }Q4-> xiA Fault Modeling and Test  xP Generation for MixedSignal Integrated Circuits }U~> pAG ; (MIP9222481 A01); $8,046.  }V [ PA  ,@CThis 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.T$ ,@CThis grant includes support for NSFESPRIT cooperation.ƀ%  xP  }U~> pAG  Virginia Polytechnic Institute ; James ArmstrongArmstrong, James and Walling  xPp CyreCyre, Walling;  }Q4-> xiA Rapid Development and Testing of Behavioral Models }U~> pAG ; (MIP9120620 A01); $87,000; 12 months.  }V [ PA  ,@CThis 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 highlevel language, VHDL.T$8$.x,x,XX+`X)x,x,XX8  YX  pA3 10Testing Applicationscatname }V [ PA ۃ  xP  ԇ }U~> pAG  Auburn University ; Adit SinghSingh, Adit;  }Q4-> xiA Exploiting Defect Clustering  xP Information in VLSI Testing }U~> pAG ; (MIP9208928 A01); $55,902.  }V [ PA  ,  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.H  xP  }U~> pAG  University of California Santa Cruz ; Frankie J. FergusonFerguson, Frankie J. PYI;  xP  }Q4-> xiA PYI: Hierarchal Test Pattern Generation for Manufacturing  xPq Defects }U~> pAG ; (MIP9158491 A02); $62,500; 12 months.  }V [ PA  ,  The focus here is on developing costeffective testing methodologies that detect more defective ICs than current methods. There are two approaches to manufacturing test. The use of highlevel fault models reduces test generation costs, but furnish lower quality tests. The use of lowlevel 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 multilevel metal CMOS technologies.H  xPi&  }U~> pAG  University of California Santa Cruz ; Tracy LarrabeeLarrabee, Tracy PYI;  }Q4-> xiA PYI: Sequential and Combinational Test Pattern Generation for  xP' Realistic Faults Using Boolean Satisfiability }U~> pAG ; (MIP9158490 A03); $86,960; 12 months.  }V [ PA  ,  This research is based on an automatic test pattern generation (ATPG) system (called Nemesis)+.x,x,XX 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.T$  xP  }U~> pAG  University of Massachusetts Amherst ; Israel KorenKoren, Israel;  xPi  }Q4-> xiA Topological and Physical Layout Design Techniques for Yield  xP1 Enhancement }U~> pAG ; (MIP9305912); $204,000; 36 months.  }V [ PA  ,@CThis 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 PLAbased designs.T$  xPA  }U~> pAG  University of Rhode Island ; Jien-Chung LoLo, Jien-Chung RIA;  }Q4-> xiA RIA: Entering an New Era of Low Cost Concurrent Error Detecting Digital System  xP Designs in CMOS VLSI  }U~> pAG ; (MIP9308085); $45,000; 36 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $90,000).  }V [ PA  ,@CThis research is on a class of concurrent error detecting (CED) methods for design in CMOS VLSI. The basis for the research is a novel builtin 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, onchip 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.T$ 8+.x,x,XX+2 2x,x,XX8Ԍ xP ԙ }U~> pAG  Virginia Polytechnic Institute ; Dong S. HaHa, Dong S.;  }Q4-> xiA Software  xP Capitalization: CAD Tools for VLSI Circuit Testing }U~> pAG ; (MIP9310115); $38,566; 12 months.  }V [ PA  ,  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:H ,  1.FSIM, combinational circuit fault simulator;H ,  2.HOPE, a synchronous sequential fault simulator;H ,  3.ATALANTA, an ATPG for stuckat faults in combinational circuits; andH ,  4.SOPRANO, an ATPG for stuckopen faults in combinational circuits.H ,  This grant is made under the Software Capitalization Program.H.x,x,XX  xP  }U~> pAG  University of Wisconsin ; Kewal SalujaSaluja, Kewal;  }Q4-> xiA Test Algorithms for Physical Neighborhood Pattern Sensitive Faults in Reconfigurable  xP Rams }U~> pAG ; (MIP9111886 A02); $63,600; 12 months.  }V [ PA  ,@CThis 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. T$ ,@CIn 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.T$8h.x,x,XXFI4x,x,XX8ԯ  Y  6 pA3 Simulationcatname }V [ PA ۃ  xP ԇ  }U~> pAG University of Arizona ; Olgierd PalusinskiPalusinski, Olgierd;  }Q4-> xiA Techniques for  xP Accelerated Simulation of Electronic Circuits and Systems }U~> pAG ; (MIP9017037 A02, A03 & A04); $59,970; 12 months.  }V [ PA  ,  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:H ,  1. Modeling of MOS circuits based on modified nodal analysis;H ,  2. Application of spectral algorithms to bipolar circuits with various model switching strategies;H ,  3. Construction of an efficient spectral algorithm for computation of transients in lossy transmission lines with frequency dependent parameters and nonlinear termination networks;H ,  4. Using spectral techniques in a relaxation framework.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H).x,x,XX  xP  }U~> pAG  University of Illinois Urbana ; Resve A. SalehSaleh, Resve A. PYI;  }Q4-> xiA PYI: A Simulation Environment for the Analysis of Transient Faults in  xP VLSI Circuits }U~> pAG ; (MIP9057887 A04); $62,500; 12 months.  }V [ PA  ,@CThis research is on simulation techniques and modeling approaches for analog circuits. Accuracy of the analysis is the key goal. Highlevel 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 macromodel 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 macromodel. The new models and algorithms are being integrated into a multilevel analog simulation tool that includes the ability to perform circuit level, functional level and behavior level simulation within one simulation run. Circuits considered include sigmadelta modulators, phaselocked loops, and switched capacitor circuits among others.T$8i&.x,x,XXQ*x,x,XX8  xP  }U~> pAG  Massachusetts Institute of Technology ; Jacob K. WhiteWhite, Jacob K. PYI;  }Q4-> xiA PYI:  xP Simulation of Switching Filter and PhaseLock Loop Circuits }U~> pAG ; (MIP8858764 A05); $25,000.  }V [ PA  ,  This research is on three topics in modeling, analysis, and simulation of highfrequency circuits and devices:H ,  1.Multipole accelerated 3D interconnect analysis;H ,  2.Simulation of clocked analog circuits; andH ,  3.Simulation for microelectromechanical (MEM) devices.H ,  For the interconnect analysis, multipoleaccelerated approach to circuit analysis is being applied to problems of determining effective and accurate methods to simulate crosstalk effects, and perform inductance extraction. In simulation of clocked analog circuits, algorithms for detailed simulation of switchedcapacitor 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.H  xP  }U~> pAG  Washington University ; Roger D. ChamberlainChamberlain, Roger D. RIA;  }Q4-> xiA RIA:  xPp Partitioning of VLSI Systems for Distributed Simulation }U~> pAG ; (MIP9309658); $90,000; 36 months.  }V [ PA  ,  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:H ,  1.Algorithms for initial partitioning of the circuit components are being developed;H ,  2.Means of assigning partitions to processors are being developed; andH ,  3.Rules for migrating components from one processor to another are being devised.H(.x,x,XX  xP  }U~> pAG  Carnegie Mellon University ; Ronald RohrerRohrer, Ronald;  }Q4-> xiA ADAPTS: A Comprehensive Circuit/Timing Simulation Strategy for Integrated  xP Circuits }U~> pAG ; (MIP9014402 A02); $66,000; 12 months.  }V [ PA  ,@CA 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.T$ ,@CThe 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.T$ ,@CThe above strategies are being embodied in the  xQ SPECS ( S imulation  P rogram for  E lectronic C ircuits  xQ and S ystems) software.T$  xP  }U~> pAG  University of Texas Austin ; Lawrence T. PillagPillage, Lawrence T. PYIe;  }Q4-> xiA PYI: CAD  xP Tools for New Circuit Technologies }U~> pAG ; (MIP9157363 A03); $62,500; 12 months.  }V [ PA  ,@CThe 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 multichip modules requires development of tools for the extraction, characterization and simulation of transmission lines at the system simulation level. Toward this end interconnect macromodels, similar to those for onchip RC interconnect circuits, which are compatible with systemlevel design automation tools, are being explored.T$8(.x,x,XXh)OOx,x,XX8  xP  }U~> pAG  University of Washington ; Andrew T. YangYang, Andrew T. NYI;  }Q4-> xiA NYI: Modeling and Simulation of Advanced Microelectronics and Optoelectronic  xP Circuits and Systems }U~> pAG ; (MIP9257279 A01); $100,000; 12 months.  }V [ PA  ,  This research is on modeling and simulation of mixed analog/digital circuit designs. Topics include:H ,  1. Hierarchical modeling and simulation of tightly coupled, mixed digital circuits;H ,  2. Simulation of highperformance circuits with complex nonlinear and electromagnetic effects;H ,  3. Modeling and simulation of optoelectronic integrated circuits, with the focus on automatic model generation;H ,  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;H ,  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.H.x,x,XX 8.x,x,XXiQQx,x,XX8ԯ.x,x,XX = MASTER.DTT =...XX  b  MASTER.MSA  margins XXXX  XXXX ϡprogdefXtd%Xtd%"ȪprogtabU6msa-footEEI  y(#XXdddy Microelectronic Systems Architecture Program`l$%mI)  y(#XXdddy `D%CMicroelectronic Systems Architecture Program5Prognam x~> pA! ~ )Microelectronic Systems Architecture2Prognam }V [ PA ۃ x)Dr. J. Robert Jump, Program Director ^ $(703) 3061936 jjump@note.nsf.gov  Y* 6 pA3 The Programcatname }V [ PA ۃ  XX X4` H(#T$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.  ,TECHNOLOGYDRIVEN 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: *XMethodologies 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.(# *XDesign 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.(# *XStudies of system programmability, architectural support for programming languages and system software, compiler techniques to exploit and to enhance system architectural features.(# *XStudies of both software and hardware strategies to enhance the reliability, availability, and fault tolerance of microelectronic systems. (# ( +APPLICATIONDRIVEN 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: *XRequirement specification, analysis, decomposition of problems and mapping of problem subcomponents onto functional building blocks, and analysis of the cost-performance trade-offs;(# *XThe 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);(# ) .x,x,XX  Y - pA3 Initiatives and Opportunitiescatname }V [ PA ۃ 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: *XInnovative application-specific machine architectures that can tackle grand challenge problems, e.g. biotechnology and environmental studies, etc., and recent initiatives noted above.(# *XDesign of innovative microelectronic systems using new device and packaging technologies such as optoelectronics, optical interconnects, VLSI, GaAs, MCM packaging, and analog-digital devices.(# *XDesign of high performance memory systems, including I/O, for superscalar and parallel machines.(# *XPerformance evaluation of microelectronic systems using a combination of analytical modeling, simulation, benchmarking and measurements on such systems.(# *XExperimental research that deals with building of small-scale, proof-of-concept prototypes, simulation or emulation of new system designs using software or FPGA emulators.(# Q!.x,x,XX  Y  margins XXXX  XX "ȪprogtabX4` H(#T$8 pA3 Awardscatname }V [ PA ۃ  Yy  pA3 ,Technology Driven Architecturej catname }V [ PA ۃ  xP ԇ }U~> pAG  University of Arizona ; Ahmed LouriLouri, Ahmed;  }Q4-> xiA Design of 3-D Optical Interconnects for High-Density Chip-to-Chip and Board-to-Board  xP Interconnections }U~> pAG ; (MIP9310082); $144,439; 12 months.  }V [ PA  ,  As device speeds rise, communication rather than device speed becomes the limiting factor in performance and cost of highperformance computing systems. Optical interconnects offer the potential for highspeed, scalable communications that can keep up with progress in devices. This research explores the application of freespace optics to highdensity 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:H ,  1.developing suitable optical network topologies;H ,  2.identifying optical implementation techniques and required devices;H ,  3.identifying interface components;H ,  4.developing modeling and simulation techniques for evaluating the performance of the chosen topologies and implementations; andH ,  5.physically implementing and measuring some of the resulting networks.H  xP  }U~> pAG  University of California Berkeley ; Alan J. SmithSmith, Alan J.;  }Q4-> xiA Cache  xPb Memories and CPU Performance Architecture }U~> pAG ; (MIP9116578 A01); $76,000; 12 months (Joint support with the Computer Systems Architecture Program Total Grant $126,000).  }V [ PA  ,  In the area of cache memories and CPU performance architecture the research efforts are directed at three items:H ,  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.H ,  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:+".x,x,XX source code on sharing behavior.8" ,@C3.FThe mMeasurement of the memory systems of a number of machines to determine the effect that those memory systems have on overall system performance.T$  xP2  }U~> pAG  University of California Davis ; Matthew FarrensFarrens, Matthew NYI;  }Q4-> xiA NYI: High  xP Performance Single Chip VLSI Processors }U~> pAG ; (MIP9257259 A01); $62,500; 12 months.  }V [ PA  ,@CThe 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 conflictfree message passing system into the lowest level of the processor design to facilitate low latency intraMISC communication. This approach allows for increased machine parallelism with minimal code expansion, and provides an alternative approach to single instruction stream multiissue machines such as superscalars and VLIWs.T$ ,@CThe 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.T$  xPj#  }U~> pAG  University of California Irvine ; Kai-Yeung Siu, Kai-Yeung NYISiu;  }Q4-> xiA NYI: Analysis  xP2$ and Design of Artificial Neural Networks }U~> pAG ; (MIP9357553); $12,500; 12 months (Joint support with the Circuits and Signal Processing Program Total Grant $25,000).  }V [ PA  ,@CArtificial 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 of8:+".x,x,XX,"1"1x,x,XX8 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.H  xP`  }U~> pAG  University of California Santa Cruz ; Anujan VarmaVarma, Anujan NYI;  }Q4-> xiA NYI: Research in HighSpeed Interconnection and Switching  xP Technologies }U~> pAG ; (MIP9257103 A01); $75,409; 12 months.  }V [ PA  ,  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 highspeed crossbar switches as the interconnection means. The structure of these switches as well as mechanisms for connection setup, routing, and flowcontrol across multiple cascaded switches are being studied. Photonic switch architectures obtained by combining dimensions of switching, such as wavelength and space, are under investigation.H  xP  }U~> pAG  Georgia Institute of Technology ; Umakishore RamachandranRamachandran, Umakishore  xP and H. VenkateswaranVenkateswaran, H.;  }Q4-> xiA The Impact of Architectural Features on  xP the Performance of Parallel Algorithms }U~> pAG ; (MIP9200005 A01); $84,820; 12 months.  }V [ PA  ,  The main thrust of the research is to study the interrelationship 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 largescale 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.H0*#.x,x,XX  xP  }U~> pAG  Georgia Institute of Technology ; Umakishore Ramachandran!Ramachandran, Umakishore PYI!;  xP  }Q4-> xiA PYI: Architectural Issues in Parallel and Distributed Computing }U~> pAG ; (MIP9058430 A03); $62,500; 12 months.  }V [ PA  ,@CBeehive 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 cachebased multiprocessor environment. The novel aspects of the architecture are readerinitiated cache coherence, latency tolerance through buffered writes, elimination of falsesharing, and efficient support for synchronization via the caches. The architectural features are designed to be compatible with an interconnection network.T$ ,@CResearch issues include: Compiletime 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.T$  xP  }U~> pAG  University of Illinois Urbana ; Andrew ChienChien, Andrew;  xP  }Q4-> xiA High-Performance, Adaptive Routing in Multiprocessor Networks }U~> pAG ; (MIP9223732); $95,000; 12 months.  }V [ PA  ,@CThe 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:T$ ,@C1.Fselection of deadlockfree algorithms with varying degrees of adaptiveness;T$ ,@C2.Fa set of analytic models of router speeds based on switch and buffer delay measurements;T$ ,@C3.Fan empirical study of network traffic patterns to determine the need for adaptiveness in routing; andT$ ,@C4.Fa set of techniques for extending routers to meet requirements such as fault tolerance and inorder message delivery.T$  xP#  }U~> pAG  University of Illinois Urbana ; Wen-Mei HwuHwu, Wen-Mei;  }Q4-> xiA Speculative and Predicated Execution Support for Instruction-Level Parallel  xP% Processing }U~> pAG ; (MIP9308013); $163,670; 24 months.  }V [ PA  ,@CSpeculative 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 single8*#.x,x,XX*#i#j3x,x,XX8 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.H ,  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.H  xP  }U~> pAG  University of Illinois Urbana ; Josep TorrellasTorrellas, Josep RIA;  }Q4-> xiA RIA: Characterizing and Optimizing the Performance of Memory  xP Hierarchies in Scalable Shared-Memory Multiprocessors }U~> pAG ; (MIP9308098); $100,000; 36 months.  }V [ PA  ,  This research aims at improving the performance of memory hierarchies in scalable sharedmemory multiprocessors. The research uses advanced performance monitoring hardware to characterize the performance of a real scalable machine, namely the 32processor 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.H ,  The research focuses on four research issues in memory hierarchies:H ,  1.the performance of cache memories and prefetch buffers under frequent vector and block traffic;H ,  2.the performance of Omega interconnection networks connecting the fastest layers of the memory hierarchy to global memory;H ,  3.dynamic page migration and replication in the memory hierarchy to increase data locality; andH ,  4.the cache memory performance of the operating system.H0*$.x,x,XX  xP  }U~> pAG  University of Illinois Urbana ; Benjamin W. WahWah, Benjamin W.;  xP  }Q4-> xiA Architecture Specific Resource Management via Intelligent  xP Compilation and Strategy Learning }U~> pAG ; (MIP9218715 & A01); $102,769; 12 months.  }V [ PA  ,@CThis 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.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of Illinois Urbana ; Pen-Chung YewYew, Pen-Chung, Wen-Mei  xP HwuHwu, Wen-Mei and John BrunerBruner, John;  }Q4-> xiA Improving the Performance of Scalable  xP Shared-Memory Multiprocessors }U~> pAG ; (MIP9307910); $106,090; 12 months (Joint support with the Experimental Systems Program Total Grant $197,429).  }V [ PA  ,@CSophisticated 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 looplevel parallelism, and hierarchical network design. The study of these issues involves the hardwareassisted collection of empirical data on Cedar and the use of simulation. The information thus obtained could lead to the design of nextgeneration systems that, compared to presentday systems, provide higher sustained performance across a broader range of applications.T$8%$.x,x,XX*$$lx,x,XX8  xP  }U~> pAG  Louisiana State University ; Ahmed El-AmawyEl-Amawy, Ahmed;  }Q4-> xiA Theory and  xP Design of Branch-and-Combine Clock Networks }U~> pAG ; (MIP9117206 A01); $52,162; 12 months.  }V [ PA  ,  A new clock distribution scheme for arbitrarily large parallel and distributed systems, called the branchandcombine scheme, is proposed. This scheme can guarantee a constant skew upperbound 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.H  xP  }U~> pAG  Massachusetts Institute of Technology ; William DallyDally, William PYI;  }Q4-> xiA PYI:  xP Concurrent VLSI Architecture }U~> pAG ; (MIP8657531 A07); $37,500.  }V [ PA  ,  This research focuses on the evaluation of the prototype MDP components, the assembly of a singleboard (64processor) JMachine system, the revision of the MDP component design as required, and the assembly of a 16board (1024processor) JMachine system. The Concurrent Smalltalk and the Concurrent Aggregates programming systems are being installed on the JMachine and some small applications are being demonstrated.H  xP  }U~> pAG  University of Massachusetts ; Maciej CiesielskiCiesielski, Maciej and Wayne  xPX BurlesonBurleson, Wayne;  }Q4-> xiA High-Performance VLSI Synthesis with Wave  xP  Pipelining }U~> pAG ; (MIP9208267 A01); $65,546; 12 months (Joint support with the Systems Prototyping & Fabrication Program Total Grant $90,546).  }V [ PA  ,  Wavepipelining is a method of highperformance 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 wavepipelining in static logic to include dynamic CMOS logic which is known for its smaller area and higherperformance. Previous work in wavepipelining 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*%.x,x,XX 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.T$  xP  }U~> pAG  Michigan State University ; Lionel M. NNi, Lionel M.i, AbdolHossein  xP EsfahanianEsfahanian, Abdol-Hossein and Philip K. McKinleyMcKinley, Philip K.;  }Q4-> xiA Multicast Communication  xP` in Multicomputers }U~> pAG ; (MIP9204066 A01 & A02); $122,990; 12 months.  }V [ PA  ,@CThis 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.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of Michigan ; Karem SakallahSakallah, Karem, Trevor MudgeMudge, Trevor and  xP Edward DavidsonDavidson, Edward;  }Q4-> xiA Timing Verification and Optimal Clocking of  xPp Latch-Controlled Synchronous Digital Circuits }U~> pAG ; (MIP9014058 A02); $90,660; 12 months (Joint support with the Design, Tools and Test Program Total Grant $127,660).  }V [ PA  ,@CThis research is on the temporal modeling of latchcontrolled synchronous digital systems. The use of levelsensitive latches, as opposed to edgetriggered flipflops, 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.T$ ,@CBoth 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.T$8h)%.x,x,XX+%%x,x,XX8  xP  }U~> pAG  Wayne State University ; Vipin ChaudharyChaudhary, Vipin RIA;  }Q4-> xiA RIA: Adaptive Load  xP Balancing for Heterogenous Distributed Systems }U~> pAG ; (MIP9309489); $89,999; 36 months.  }V [ PA  ,  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 realworld problems in a real heterogeneous distributed computing environment. A salient feature of the scheme is its semidistributed, 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 realworld 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.H  xPp  }U~> pAG  University of Minnesota ; David J. LiljaLilja, David J.;  }Q4-> xiA New Mechanisms for  xP8 Parallel Loop Scheduling }U~> pAG ; (MIP9221900); $160,942; 36 months.  }V [ PA  ,  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 loopcontrol 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.H  xP$  }U~> pAG  Rutgers University ; Miles MurdoccaMurdocca, Miles;  }Q4-> xiA Development of a Methodology for Implementing Hardware Dataflow Graphs Using  xPH& Reconfigurable Optical Interconnects }U~> pAG ; (MIP9224707); $245,128; 36 months.  }V [ PA  ,  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*&.x,x,XX 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 freespace optics. An advantage of this kind of gate array is quick reconfiguration of the optical interconnections which allows dataflow graphs to be changed quickly.T$ ,@CThis 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 wellsuited to the factory floor. Reconfigurable optical computers of the type under development in this project may allow highspeed computation to be inserted into manufacturing processes in new ways.T$  xPh  }U~> pAG  State University of New York Geneseo ; Rong LinLin, Rong;  }Q4-> xiA A New Switching Mechanism for Reconfigurable Bus System Architectures  xP and Algorithms }U~> pAG ; (MIP9307664); $51,188; 24 months.  }V [ PA  ,@CThis 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 applicationspecific 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.T$  xP  }U~> pAG  North Carolina State University ; Wentai LiuLiu, Wentai;  }Q4-> xiA CMOS IC  xP! Performance Enhancement Via Wave Pipelining }U~> pAG ; (MIP9212346 A01); $85,520; 12 months.  }V [ PA  ,@CWave 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 pipelined8*&.x,x,XX+&&x,x,XX8 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.H  xP  }U~> pAG  North Dakota State University ; Yahui ZhuZhu, Yahui RIA;  }Q4-> xiA RIA: On the Theoretical and Practical Aspects of Allocation and Scheduling for  xP( Mesh Systems }U~> pAG ; (MIP9307594); $89,983; 36 months.  }V [ PA  ,  This project is a study of processor allocation and task scheduling for meshconnected multicomputers. Parallel applications submitted to a mesh system need to be gangscheduled 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 threephase approach. The three phases are:H ,  1.to develop strategies for generalized processor allocation to satisfy various application specifications;H ,  2.to devise and evaluate scheduling algorithms by adopting two and threedimensional packing heuristics; andH ,  3.to apply the algorithms to practical systems.H  xP  }U~> pAG  Ohio State University ; Dhabaleswar K. PandaPanda, Dhabaleswar K. RIA;  }Q4-> xiA RIA: Communication and Synchronization in k-ary n-cube cluster-c  xPX Scalable Systems }U~> pAG ; (MIP9309627); $99,549; 36 months.  }V [ PA  ,  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:H ,  1.developing communication algorithms for frequently used communication patterns on clustered systems;H ,  2.developing synchronization mechanisms and algorithms to provide concurrent intercluster and intracluster synchronization; andH ,  3.developing guidelines and architectural supports for interfacing processor clusters to kary ncube wormholerouted networks.H ,  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*'.x,x,XX future clustered scalable systems supporting various programming paradigms such as distributedmemory, cachecoherent shared memory, and distributedshared memory.T$  xP  }U~> pAG  Pennsylvania State University ; Tse-Yun FengFeng, Tse-Yun and  xPx Chitaranjan DasDas, Chitaranjan;  }Q4-> xiA Evaluation Techniques for Hypercube and  xP@ MIN-Based Architectures }U~> pAG ; (MIP9104485 A02); $89,098; 12 months.  }V [ PA  ,@CHypercube 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 performancerelated dependability behavior of these two classes of multiprocessors.T$ ,@CThe performance model is based on a threelevel 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 taskbased reliability or availability. The dependability model is aimed at finding a proper subcube for the execution of a task. The analysis covers both uniquepath and multipath MINs. Performancerelated 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.T$  xP  }U~> pAG  University of Rhode Island ; Jien-Chung LoLo, Jien-Chung RIA;  }Q4-> xiA RIA: Entering a New Era of Low Cost Concurrent Error Detecting Digital System  xP`" Designs in CMOS VLSI  }U~> pAG ; (MIP9308085); $45,000; 36 months (Joint support with the Design, Tools and Test Program Total Grant $90,000).  }V [ PA  ,@CThis research is on a class of concurrent error detecting (CED) methods for design in CMOS VLSI. The basis for the research is a novel builtin 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, onchip cache memories, and fast fourier transform processors. 8*'.x,x,XX+'M'Mx,x,XX8 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.H  xP  }U~> pAG  University of Rhode Island ; Qing YangYang, Qing;  }Q4-> xiA Introducing a Novel  xP Cache Design to Vector Computers }U~> pAG ; (MIP9208041 A01); $11,018.  }V [ PA  ,  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.H  xP  }U~> pAG  Texas A&M University ; Laxmi N. BhuyanBhuyan, Laxmi N.;  }Q4-> xiA Cache Architectures  xPp for Large Shared Memory Multiprocessors }U~> pAG ; (MIP9301959); $92,601; 12 months.  }V [ PA  ,  This project addresses the problem of designing coherent caches for scalable multiprocessors with shared address spaces. Maintaining cache coherence in largescale 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.HH&(.x,x,XX  xP  }U~> pAG  University of Utah ; Erik BrunvandBrunvand, Erik and Ganesh  xP GopalakrishnanGopalakrishnan, Ganesh;  }Q4-> xiA The Design of Asynchronous Circuits and  xP Systems with Emphasis on Correctness and Proven Optimizations }U~> pAG ; (MIP9215878); $77,577; 24 months (Joint support with the Design, Tools and Test Program Total Grant $155,154).  }V [ PA  ,@CThis 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:T$ ,@C1.Fenhancing the expressive power as well as the semantic clarity of concurrent hardware description languages for asynchronous circuits and systems;T$ ,@C2.Fextending the formal basis for compiling from HDL's to circuit designs;T$ ,@C3.Fformally characterizing and improving the optimizations used in asynchronous circuit compilation; andT$ ,@C4.Fstudying the performance of implemented circuits with regard to a variety of parameters.T$  xPP  }U~> pAG  University of Washington ; Susan J. EggersEggers, Susan J. PYI;  }Q4-> xiA PYI: Code  xP Generation for Uniprocessors }U~> pAG ; (MIP9058439 A03); $62,500; 12 months.  }V [ PA  ,@CThe 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 sharingrelated 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.T$ ,@CThe current focus of the research is in the following areas:T$ ,@C1.FCompiler reorganization of shared data;T$ ,@C2.FRuntime code generation; andT$ ,@C3.FA protection model for a single address space architecture.T$8$(.x,x,XX'((~Ox,x,XX8  xP  }U~> pAG  University of Washington ; Arun K. SomaniSomani, Arun K.;  }Q4-> xiA Error Detection and Recovery in High-Performance Fault-Tolerant Processor  xP Systems Employing Caches }U~> pAG ; (MIP9224462); $159,332; 24 months.  }V [ PA  ,  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 processormemory interface to check for consistency in all bus transactions. If cache memories are used, many operations do not use the processormemory 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 faulttolerant cache protocols.H).x,x,XX  xP  }U~> pAG  University of Wisconsin Madison ; Mark D. HillHill, Mark D. PYI;  }Q4-> xiA PYI: Cache  xP Memory Design }U~> pAG ; (MIP8957278 A04); $62,500; 12 months.  }V [ PA  ,@CThe 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.T$ ,@CThe 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.T$8h).x,x,XXh))x,x,XX8ԯ  Y  pA3 {,Application Driven Architecturecatname }V [ PA ۃ  xP ԇ }U~> pAG  Arizona State University ; Chaitali ChakrabartiChakrabarti, Chaitali RIA;  }Q4-> xiA RIA: VLSI Architectures and Algorithms for Motion Estimation Using Hough  xP Transform }U~> pAG ; (MIP9309504); $99,000; 36 months.  }V [ PA  ,  In the past, realtime image processing has been restricted to lowlevel tasks such as filtering; the more complex medium and highlevel tasks have been left to generalpurpose computers which are unable to handle the large computation rates of these tasks. Realtime computation of these tasks thus necessitates development of taskspecific algorithms and architectures. This project is developing efficient algorithms and architectures for an important and representative mediumlevel task: motion estimation of 2dimensional and 3dimensional 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 realtime 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+).x,x,XX realtime motion estimation, this research will also provide design guidelines for algorithm and architecture development of other medium and highlevel image processing tasks.T$  xP  }U~> pAG  San Diego State University ; Jay HarrisHarris, Jay;  }Q4-> xiA VLSI Implementation  xPy of the Z-J Algorithm for Bit Error Correction }U~> pAG ; (MIP9114270 A01); $55,508; 12 months.  }V [ PA  ,@CThe focus of this research is on the design of very large scale integrated circuit structures that can implement the ZiganirovJelenek 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.T$ ,@CThis 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.T$8Q*).x,x,XX+))x,x,XX8  xP  }U~> pAG  University of California Berkeley ; John WawrzynekWawrzynek, John PYI;  }Q4-> xiA PYI:  xP ApplicationSpecific VLSI Architectures }U~> pAG ; (MIP8958568 A06); $26,800; 12 months.  }V [ PA  ,  The focus of this research is on designing applicationspecific 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 applicationspecific VLSI computing architectures is crucial to the success of this project due to the requirements on massive computations and on realtime human interaction.H ,  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 highspeed CMOS techniques under development and may include provisions for analog I/O.H  xP  }U~> pAG  University of Southern California ; V. K. PrasanaPrasana, V. K.;  }Q4-> xiA Parallel  xPP Techniques for Problems in Vision and Robotics; }U~> pAG  (IRI9217528 A01); $30,759; 12 months (Joint support with the Robotics & Machine Intelligence Program Total Grant $61,519).  }V [ PA  ,  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:H ,  1.design and analysis of efficient parallel algorithms for problems in vision and robotics on wellestablished parallel models of computation;H ,  2.implementation of the parallel solutions on stateoftheart parallel machines, andH ,  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.H ,  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 taskplanning arising in terrain navigation and**.x,x,XX industrial automation will be investigated. The parallel models to be employed include the meshconnected processor array, reconfigurable mesh array, and the hypercube. The algorithms will be implemented on Connection Machine CM5, Maspar MP1 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.T$  xPH  }U~> pAG  University of Maine ; Seth WolpertWolpert, Seth;  }Q4-> xiA Examination of a Neuronal  xP Algorithm Using VLSIBased Models }U~> pAG ; (MIP9210945 A01); $10,000.  }V [ PA  ,@CThe objective of this research is to recreate the function of a network of biological neurons using a VLSIbased neuronal analog, of neuromime. By reconstructing a welldocumented 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.T$ ,@CThis 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.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  Johns Hopkins University ; Andreas AndreouAndreou, Andreas and Fernando  xP PinedaWolpert, SethPineda, Fernando;  }Q4-> xiA Analog Computation and VLSO Architectures for  xP! Contraction Mappings }U~> pAG ; (ECS9313934); (Joint support with the Communications and Computational Systems Program Total Grant $73,550).  }V [ PA  ,@CThis 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. 8**.x,x,XX+*T*Tx,x,XX8 Indeed, significant departures from ideal linear behavior can be tolerated, provided that these departures are reproducible across chips.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H  xP  }U~> pAG  Johns Hopkins University ; Andreas AndreouAndreou, Andreas RIA;  }Q4-> xiA RIA: Fault  xP Tolerance in Analog VLSI Focal Plane Processors }U~> pAG ; (MIP9010364 A01); $6,250.  }V [ PA  ,  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 nonlinear 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.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H  xP  }U~> pAG  Boston University ; Mark KarpovskyKarpovsky, Mark;  }Q4-> xiA On-Line and Off-Line  xPx Error Detection Mechanisms in the Coding Theory Framework }U~> pAG ; (MIP9208487 A01); $59,144; 24 months.  }V [ PA  ,  This research focuses on the development of a unified framework for combining online and offline error detection mechanisms at both the chip and board levels. This framework includes: concurrent checking of the device for online detection, space and time compression of test responses, analysis of distortions in the resulting signatures for error detection and diagnosis for builtin selftesting (BIST), and concurrent checking of hardware required for (BIST).H ,  This award supports a postdoctoral researcher, who is an internationally known scholar in the areas of design, testing, and diagnosis of computer hardware.H*+.x,x,XX  xP  }U~> pAG  Northeastern University ; Elias S. ManolakosManolakos, Elias S. RIA;  }Q4-> xiA RIA: Parallel Processing Algorithms and Architectures for the Estimation of  xP Higher Order Statistics }U~> pAG ; (MIP9309319); $89,991; 36 months.  }V [ PA  ,@CThe main goal of this project is the design and evaluation of VLSI architectures for the efficient estimation of Higher Order Statistics (HOS) from timeseries data. In addition parallel algorithms to speedup offline HOSbased data analysis and modeling in parallel processing systems are being developed. Simulations are being performed on a Transputerbased multiprocessor for validation purposes and proofofconcept prototypes will be designed using hardware description languages for performance/area estimation. As a byproduct of this research, public domain parallel processing software will be provided on various platforms (CM, Transputers, Monsoon dynamic dataflow) to allow scientists who are not experts in signal processing to experiment with the powerful HOSbased techniques in the analysis and modeling of large amounts of statistical data.T$  xPP  }U~> pAG  Dartmouth College ; Barry FaginFagin, Barry;  }Q4-> xiA ApplicationSpecific  xP Architectures for Multimedia }U~> pAG ; (MIP9312350); $48,709; 12 months.  }V [ PA  ,@CThe objectives of this research are:T$ ,@C1.Fa quantitative analysis of the computational requirements of multimedia, andT$ ,@C2.Fthe development of new system architectures based on this analysis.T$ ,@CThe methods to be employed are:T$ ,@C1.FPerformance analysis of multimedia applications on a 100 Mb/s fiber optic network of workstations,T$ ,@C2.FPerformance comparisons of solidstate and conventional disk storage in clientserver networked video applications,T$ ,@C3.FComputational profiling of existing standard multimedia algorithms,T$ ,@C4.FThe evaluation of prototype designs using FPGA (fieldprogrammable gate array) emulation, andT$ ,@C5.FThe construction and evaluation of complete boardlevel systems at the Thayer Rapid Prototyping Facility.T$8H&+.x,x,XX+++Vx,x,XX8  xP  }U~> pAG  Princeton University ; Kenneth SteiglitzSteiglitz, Kenneth;  }Q4-> xiA Scaling Large Special  xP Purpose Computers }U~> pAG ; (MIP9201484 A01); $4,000.  }V [ PA  ,  The research is on the limits of scalable specialpurpose architectures for highly parallel computation, especially computation on regular arrays. Important applications of arraybased computation can be found in digital signal processing, and in many areas of scientific computation, including manybody problems with gravitational or coulombic interactions, fluid dynamics, and wave propagation. These applications require highly parallel computation either because of the need for realtime operation, or because the total number of operations required is very large. H ,  The basic problems being addressed are:H ,  1.The design and reliability analysis of large faulttolerant arrays, and online reconfiguration and errordetection algorithms for these specialpurpose architectures;H ,  2.The design and analysis of reliable clocking schemes for very large arrays of processors, especially the comparison of synchronous, selftimed, and hybrid clocking;H ,  3.A study of the general issue of costeffective scaling of large, specialpurpose computer architectures for regular computations; and,H ,  4.Extension of the work to Hierarchical Data Computations, such as those in the fast monopole and multipole methods for manybody problems, where particles are distributed in space, and are clustered by decomposing space into hierarchical domains.H  xPX   }U~> pAG Oregon Advanced Computing Institute ; Virginia M. LoLo, Virginia, Bella  xP  BoseBose, Bella and Sanjay RajopadhyeRajopadhye, Sanjay;  }Q4-> xiA Algorithms & Abstractions for  xP Mapping Parallel Algorithms to Parallel Architectures }U~> pAG ; (MIP9108528 A02 & A03); $130,865; 12 months.  }V [ PA  ,  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*,.x,x,XX 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.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  Pennsylvania State University ; Mary IrwinIrwin, Mary and Robert  xP OwensOwens, Robert;  }Q4-> xiA High Performance, Fine Grained, Application Specific,  xP VLSI Architectures }U~> pAG ; (MIP9102500 A02); $89,055; 12 months.  wQ(  }V [ PA ,@CThe primary thrust of the research is the investigation of a more general purpose signal processing architecture which achieves the same level of performance as specialpurpose 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.T$  xP  }U~> pAG  Brown University ; Harvey F. SilvermanSilverman, Harvey F.;  }Q4-> xiA Parallel Architectures for Speech Recognition: Testing Expensive Algorithms in a  xPX Reconfigurable Environment }U~> pAG ; (MIP9120843 A02); $52,283; 12 months (Joint support with the Circuits and Signal Processing Program Total Grant $99,466).  }V [ PA  ,@CThis 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.T$  xP$  }U~> pAG  Texas A&M University ; Dhiraj K. PradhanPradhan, Dhiraj K.;  }Q4-> xiA Development of Integrated OnLine and OffLine Error Detection Mechanisms in  xPH& the Coding Theory Framework }U~> pAG ; (MIP9218238 A01); $21,106.  }V [ PA  ,@CThis research focuses on the development of a unified framework for combining online and offline error detection mechanisms at both the chip and board levels. This framework includes: concurrent checking of the device for online detection, space8*,.x,x,XX+,,x,x,XX8 and time compression of test responses, analysis of distortions in the resulting signatures for error detection and diagnosis for builtin self testing (BIST), and concurrent checking of hardware required for (BIST).H ,  This grant includes support for NSFESPRIT cooperation.t-.x,x,XX  xP  }U~> pAG  University of Wisconsin ; Parameswaran RamanathanRamanathan, Parameswaran;  xP  }Q4-> xiA Time-Constrained Communication in Real-Time Systems With  xP Point-to-Point Interconnection Topology }U~> pAG ; (MIP9213716); $180,000; 36 months.  }V [ PA  ,@CA major limitation of realtime 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 realtime communications systems.T$8 -.x,x,XXx--x,x,XX8ԯ  Y  pA3 /Workshops and Conferences8 catname }V [ PA ۃ  xP ԇ }U~> pAG  University of Illinois Urbana ; Benjamin WahWah, Benjamin;  }Q4-> xiA International Conference on Application-Specific Array Processors; Venice, Italy;  xP October 2527, 1993 }U~> pAG ; (MIP9311908); $11,600; 12 months.  }V [ PA  ,  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.H ,  This grant supports travel by selected graduate students to permit them to attend the conference.H-.x,x,XX 8-.x,x,XXa--x,x,XX8ԯ MASTER.MSA a-.x,x,XX  b  MASTER.CSP  margins XXXX  XXXX ϡprogdefXtd%Xtd%"Ȫprogtab csp-footII%  y(#XXdddy Circuits and Signal Processing Program`l$%m%)  y(#XXdddy `X%ICircuits and Signal Processing Program5Prognam x~> pA!  ,Circuits and Signal ProcessingPrognam }V [ PA ۃ F)Dr. John H. Cozzens, Program Director &(703) 3061936 jcozzens@nsf.gov  Y* 6 pA3 The ProgramGcatname }V [ PA ۃ  XX X4` H(#T$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.XOneDimensional Digital Signal Processing (1D DSP) research is concerned with the representation of 1D signals (example, audio, and EKG signals) in digital form, and the processing of such signals using digital technology.(# 2.XMultiDimensional Digital Signal Processing (MD DSP) research is directed towards signals which are inherently functions of two or more independent variables, including images and video signals.(# 3.XVLSI Signal Processing research deals with algorithms/architectures that can be mapped (with ease?) onto VLSI circuits.(# 4.XCircuits research is concerned with the better understanding of nonlinear and highfrequency circuits.(# Areas of research include: X1D 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.(# XMD DSP: algorithms for MD signal processing and applications to specific signal categories (image, for example) and multimedia communications.(# XDigital Representation: efficient and effective A/D conversion, compression, decomposition, and modeling of data.(# XVLSI SP: analog, digital, mixed analog/digital VLSI for signal processing, and CAD for signal processing architectures.(# XCircuits: emphasis is placed on analysis and design of circuits including neural networks for signal processing applications.(# In 1D DSP new approaches to nonlinear signal processing, new orthogonal decompositions and representations, and new filter structures and designs are encouraged. MD 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. ;(..x,x,XX  Y - pA3 Initiatives and Opportunities%catname }V [ PA ۃ 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 highperformance 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, crossdisciplinary 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. 5BIOTECHNOLOGY In addition to the biotechrelated research areas currently supported by CISE, new opportunities for the CSP Program will include: ,Biobased or biomotivated sensing, sensor development, sensor integration; new methods for computer imaging, 3D recognition, interactive visualization for medical diagnoses; new models and architectures for building "intelligence" (perception, learning, language, speech) into humancomputer interfaces.(# Representative contemporary and novel applications to various areas of 1D and MD DSP include: XArray 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.(# X(Adaptive) Filters: modeling biological phenomena, e.g., whitening filters which model neural noise; ARMA modeling of nonstationary (REAL!) processes, e.g., speech processing.(# XImage Processing: medical image compression (VQ, subband coding, for archival purposes Xray to MRI; restoration of blurred or noisecorrupted images; tomographic imaging of timevarying data, e.g., aperiodic time variations in data resulting from diseased human hearts; 3D image reconstruction with limited tomographic data.(# XSpectral Analysis: detection of malignant tumors by multivariate analysis of proton magnetic resonance spectra of (blood) serum. (# -MANUFACTURING and MATERIALS Potential applications areas include: XImaging: remote sensing radar, acoustic, IR, UV(# XMicrostructure: xray crystallography, electron and confocal microscopy; electronic photography(# XImage Understanding: robotics inspection and quality control; security; VHS; agriculture environmental monitoring(# XArray Processing: source localization; active noise control(# XOther: manufacturing processes (digital process control); automotive electronics (IVHS)(#+/.x,x,XX  Y  margins XXXX  XX "ȪprogtabX4` H(#T$8 pA3 Awards4catname }V [ PA ۃ  Y  pA3 7CircuitsL5catname }V [ PA ۃ  xPb ԇ }U~> pAG  University of California Berkeley ; Leon O. ChuaChua, Leon O.;  }Q4-> xiA Research  xP* on Problems in Nonlinear Networks and Systems }U~> pAG ; (MIP9114168 A02); $132,823; 12 months.  }V [ PA  ,  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 sigmadelta 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 recentlydeveloped techniques from nonlinear dynamics.H  xPB  }U~> pAG  University of California Irvine ; Kai-Yeung SiuSiu, Kai-Yeung NYI;  }Q4-> xiA NYI: Analysis  xP  and Design of Artificial Neural Networks }U~> pAG ; (MIP9357553); $12,500; 12 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $25,000).  }V [ PA  ,  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 networkbased 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.H$0.x,x,XX ,@CThe 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.T$  xP  }U~> pAG  University of California Los Angeles ; A. N. WillsonWillson, A. N.;  xPj  }Q4-> xiA Theoretical Studies of Continuous and Discrete-Time Electrical  xP2 Circuits }U~> pAG ; (MIP9201104 A01); $107,900; 12 months.  }V [ PA  ,@CThis 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 twodimensional 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.T$8z0.x,x,XX%0+b0x,x,XX8ԯ%0.x,x,XX  Y  pA3  'OneDimensional Digital Signal ProcessingEcatname }V [ PA ۃ  xPy ԇ }U~> pAG  California State University Northridge ; John W. AdamsAdams, John W.;  xPA  }Q4-> xiA New Concepts in Digital Signal Processing }U~> pAG ; (MIP9200581 A01); $79,466; 12 months.  }V [ PA  ,  Recent research has revealed that the minimax and leastsquares optimality criteria are inappropriate for many digital signal processing applications. Minimax and leastsquares optimization problems are subsets of a more general (and much more important) class of problems which are referred to as peakconstrained leastsquares (PCLS) optimization problems. PCLS solutions are needed for many digital signal processing applications, but PCLS research is still in its infancy.H ,  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:H ,  1.new multiple exchange algorithms;H ,  2.extensions of conventional quadratic programming algorithms; andH ,  3.extensions of Lawson's algorithm.H  xP  }U~> pAG  University of California Davis ; William A. GardnerGardner, William A.;  }Q4-> xiA Theory  xP and Application of Higher-Order Cyclostationarity }U~> pAG ; (MIP9112800 A01); $93,082; 12 months.  }V [ PA  ,  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; andH ,  2.to further develop the recently introduced cyclic temporal and spectral moment and cumulant theory of higher-order cyclostationarity, with application to designing higher-order spectral-line generators for+1.x,x,XX signal detection and identification, and for signal parameter estimation and synchronization.8"  xPa  }U~> pAG  University of California Santa Barbara ; John ShynkShynk, John RIA;  }Q4-> xiA RIA: Adaptive Equalization and Detection of Cochannel Signals for  xP Time-Varying Channels }U~> pAG ; (MIP9308919); $90,000; 36 months.  }V [ PA  ,@CThis research is developing nonlinear adaptive algorithms for the detection of cochannel signals transmitted over timevarying 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 timevarying and the data are transmitted in short bursts. Dualmode 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.T$  xPY  }U~> pAG  University of Southern California ; Jerry M. MendelMendel, Jerry M.;  xP!  }Q4-> xiA Applications of Fuzzy Systems to Signal Processing }U~> pAG ; (MIP9122018 A01); $67,611; 12 months.  }V [ PA  ,@CIn many practical signal processing problems, information is often represented in two forms: one is a set of inputoutput 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 IFTHEN 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 IFTHEN rules into signal processing system design within the framework of fuzzy system theory. The objectives are to:T$ ,@C1.Ftheoretically justify the practical successes of fuzzy systems; T$ ,@C2.Fdevelop synthesis methods for fuzzy systems which use both numerical and linguistic information; andT$ ,@C3.Fapply these synthesis methods to signal processing problems, such as timeseries prediction, and subject these methods to8+1.x,x,XX+14y14x,x,XX8 theoretical performance analyses. , ,  An optimal design method for fuzzy systems which will match given inputoutput pairs to arbitrary accuracy is also being developed.H  xP  }U~> pAG  University of Southern California ; Chrysostomos L. NikiasNikias, Chrysostomos L.;  xPx  }Q4-> xiA Adaptive Signal Processing Algorithms Based on Nonlinear  xP@ Performance Criteria }U~> pAG ; (MIP9206829 A01); $51,415; 12 months.  }V [ PA  ,  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:H ,  1.blind deconvolution algorithms based on criteria with memory nonlinearity;H ,  2.decision feedback equalizers using higherorder statistics;H ,  3.joint estimation and detection algorithms of the MLtype and MAPtype when the signals are Gaussian distributed;H ,  4.adaptive multichannel signal recovery algorithms when the signals have gone through severe magnitude and phase distortion; andH ,  5.blind deconvolution algorithms based on neural networks and Volterra filters.H ,  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.H  xP  }U~> pAG  University of Colorado ; Delores EtterEtter, Delores;  }Q4-> xiA Adaptive IIR Filtering  xP Using a Stochastic Filter }U~> pAG ; (MIP9106126 A02); $8,000 (Joint support with the Office of Crossdisciplinary Activities Total Grant $16,000).  }V [ PA  ,  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.H ,  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*2.x,x,XX in order to represent an adaptive IIR filter and to meet both accuracy and convergence speed constraints.T$  xP  }U~> pAG  Yale University ; Arye NehoraiNehorai, Arye;  }Q4-> xiA New Methods and Results in  xP Signal Processing and System Identification }U~> pAG ; (MIP9122753 A01); $51,922; 12 months.  }V [ PA  ,@CThis research focuses on new theoretical and algorithmic solutions to three problems in the general area of signal modeling and system identification:T$ ,@C1.Fa computationally-efficient high-order Yule-Walker estimator and its adaptive counterpart;T$ ,@C2.Ffitting rational transfer function models to frequency response data; andT$ ,@C3.Fhypothesis testing and detection with the optimal instrumental variable method.T$  xP0  }U~> pAG  Northeastern University ; Hanoch Lev-AriLev-Ari, Hanoch;  }Q4-> xiA Spectrum Analysis  xP and Estimation for Nonstationary Signals }U~> pAG ; (MIP9220182); $144,675; 36 months.  }V [ PA  ,@CThis research aims to develop efficient modelbased techniques for nonstationary signal analysis and spectral estimation, with a particular emphasis on Burg's maximumentropy approach and the orderrecursive realization of linear predictors. The ultimate objectives are:T$ ,@C1.Fto construct numericallyrobust adaptive algorithms for estimating the parameters of such models;T$ ,@C2.Fto establish the statistical properties (e.g., rate of convergence, tracking capability and steadystate error) of such algorithms when applied to both persistent and transient nonstationary signals; andT$ ,@C3.Fto obtain simple procedures for recovering spectral characterizations, such as the WignerVille distribution or the cyclic spectrum from the estimated model parameters.T$ ,@CAdaptive algorithms that efficiently estimate periodicallyvarying 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 asymptoticallymeanstationary signals. In particular, multiresolution wavelet basis functions are used to characterize the dynamics of timevarying model parameters, leading to the construction of adaptive estimation algorithms that are recursive in time, order and resolution.T$ 8*2.x,x,XX+2m2m6x,x,XX8Ԍ xP ԙ }U~> pAG  Northeastern University ; John G. ProakisProakis, John G.;  }Q4-> xiA Adaptive Signal  xP Processing Algorithms Based on Nonlinear Performance Criteria }U~> pAG ; (MIP9115526 A01); $57,996; 12 months.  }V [ PA  ,  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:H ,  1.blind deconvolution algorithms based on criteria with memory nonlinearity;H ,  2.decision feedback equalizers using higherorder statistics;H ,  3.joint estimation and detection algorithms of the MLtype and MAPtype when the signals are Gaussian distributed;H ,  4.adaptive multichannel signal recovery algorithms when the signals have gone through severe magnitude and phase distortion; andH ,  5.blind deconvolution algorithms based on neural networks and Volterra filters.H ,  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.H  xP   }U~> pAG  University of Minnesota ; Kevin M. BuckleyBuckley, Kevin M. PYI;  }Q4-> xiA PYI: Digital Signal  xP Processing for Hearing Aids and Source Localization }U~> pAG ; (MIP9057071 A02); $25,000; 12 months.  }V [ PA  ,  In the general area of Source Localization Estimation (SLE), this research will:H ,  1.continue SLE algorithm performance evaluation(s);H ,  2.investigate algorithm improvements based on considerations of analytical performance expressions derived during the course of this project; andH ,  3.address the combined issue of robust estimation and high resolution in the presence modeling errors.H ,  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 realtime testing both in*3.x,x,XX the laboratory and in the field. Adaptive methods will be examined for use in active noise cancellation of undesired nonstationary noise.T$  xP  }U~> pAG  University of Minnesota ; Mostafa KavehKaveh, Mostafa;  }Q4-> xiA Array Signal  xP Processing: Estimator Design and Experiments }U~> pAG ; (MIP9202081 A01); $89,601; 12 months.  }V [ PA  ,@CThis 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.T$  xPX  }U~> pAG  Cornell University ; Thomas W. ParksParks, Thomas W.;  }Q4-> xiA Optimal Design of  xP  Filters for Multirate Systems }U~> pAG ; (MIP9224424); $221,550; 36 months.  }V [ PA  ,@CThe 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.T$ ,@CThe 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-infinite8*3.x,x,XX+33ox,x,XX8 programming and Remez-like multiple exchange methods.H ,  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.H  xP  }U~> pAG  Carnegie Mellon University ; Virginia L. StonickStonick, Virginia L. PYI;  }Q4-> xiA PYI:  xP Globally optimal and stable adaptive filtering algorithm. }U~> pAG ; (MIP9157221 A04 & A05); $62,500; 12 months.  }V [ PA  ,  This research addresses the use of numerical optimization methods to develop realtime adaptive filters for estimating, identifying, or predicting timevarying and potentially nonlinear processes. The first phase of this work will be devoted to the development, analysis, and simulation of an optimal adaptive infiniteimpulse 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 timevarying environments, and will ultimately lead to their more widespread use.H4.x,x,XX  xP  }U~> pAG  University of Wisconsin Madison ; Barry D. Van VeenVan Veen, Barry D. PYI;  }Q4-> xiA PYI:  xP Detection and Estimation in Low Dimensional Subspaces }U~> pAG ; (MIP8958559 A04); $41,000; 12 months.  }V [ PA  ,@CThis 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.T$ ,@CProcessing 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.T$8p4.x,x,XXP44x,x,XX8ԯ  Y  pA3  &Multidimensional Digital Signal Processing˜catname }V [ PA ۃ  xP  ԇ }U~> pAG  California Institute of Technology ; P. P. VaidyanathanVaidyanathan, P. P.;  }Q4-> xiA New Directions in One and Multidimensional Multirate Systems, Filter  xP Banks, and Applications }U~> pAG ; (MIP9215785); $162,393; 36 months.  }V [ PA  ,  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+4.x,x,XX (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.T$  xP"  }U~> pAG  University of California San Diego ; Bhaskar D. RaoRao, Bhaskar D.;  }Q4-> xiA Novel  xPI# Constrained Least Squares Algorithms With Application to MEG }U~> pAG ; (MIP9220550); $168,297; 36 months.  }V [ PA  ,@CThis 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 the8+4.x,x,XX+4 4x,x,XX8 testing and evaluation of these algorithms. It is expected that this research will greatly enhance our understanding of nonlinear iterative techniques.H  xP  }U~> pAG  University of Florida ; Jian LiLi, Jian RIA;  }Q4-> xiA RIA: Utilizing Sensor and Wave  xPx Properties for Antenna Array Processing  }U~> pAG ; (MIP9308302); $100,00; 36 months.  }V [ PA  ,  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:H ,  1.to exploit the advantages of different polarization sensitive arrays;H ,  2.to develop the direction and polarization estimation techniques for both completely and partially polarized waves; andH ,  3.to take into account the mutual coupling effects between antenna sensors for direction and polarization estimation and for modeling nearby scatters with antenna theory.H ,  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.H  xP8  }U~> pAG  Georgia Institute of Technology ; Vijay K. MadisettiMadisetti, Vijay K. RIA;  }Q4-> xiA RIA: The  xP Fast Discrete Radon Transform }U~> pAG ; (MIP9211725 A01); $9,856.  }V [ PA  ,  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.HH&5.x,x,XX  xP  }U~> pAG  Illinois Institute of Technology ; Nikolas F. GalatsanosGalatsanos, Nikolas F. RIA;  }Q4-> xiA RIA:  xP Wavelet Based Multi-Channel Subband Image Restoration }U~> pAG ; (MIP9309910); $88,740; 36 months.  }V [ PA  ,@CThe 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.T$ ,@CIn order to fully exploit the potential advantages of this approach, three classes of multi-channel restoration algorithms are being considered:T$ ,@C1.Fstochastic restoration algorithms where the multi-channel statistics of the wavelet-based subbands are used to model the space-varying nature of the original image;T$ ,@C2.Fdeterministic algorithms where multi-channel regularization operators and parameters are used; andT$ ,@C3.Fhierarchical image restoration where the image is progressively restored starting from its coarse features and continuing to the finer ones.T$  xP  }U~> pAG  University of Illinois Urbana ; Yoram BreslerBresler, Yoram PYI;  }Q4-> xiA PYI: Statistical  xPp Techniques in Inverse Problems }U~> pAG ; (MIP9157377 A01); $50,028; 12 months.  }V [ PA  ,@CThis 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 spatiallyrelated data, such as is acquired in multispectral, or multi-modality remote sensing and diagnostic imaging.T$8*5.x,x,XX'5E5Kx,x,XX8  xP  }U~> pAG  University of Illinois Urbana ; Michael T. OrchardOrchard, Michael T. NYI;  }Q4-> xiA NYI:  xP Optimal Motion Compensation for Video Compression }U~> pAG ; (MIP9357823); $25,000; 12 months.  }V [ PA  ,  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 motioninduced 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.H  xP  }U~> pAG  Harvard University ; David MumfordMumford, David;  }Q4-> xiA Mathematical,  xPP Computational and Biological Aspects of Vision }U~> pAG ; (MPS9121266 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).  }V [ PA  ,  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.H(6.x,x,XX  xP  }U~> pAG  Massachusetts Institute of Technology ; Alan WillskyWillsky, Alan;  xP  }Q4-> xiA Statistical Signal Processing and Estimation for Spatial and Multidimensional Data: Multiresolution Methods, Efficient  xPX Algorithms and Geometric Reconstruction }U~> pAG ; (MIP9015281 A02); $45,000; 12 months (Joint support with the Engineering Systems Program Total Grant $65,000).  }V [ PA  ,@CThere 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.T$ ,@CThe 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 spacetime random fields.T$ ,@CThe 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 2D or 3D, or the 2D silhouette of 3D objects.T$  xP`"  }U~> pAG  University of Michigan Ann Arbor ; Andrew E. YagleYagle, Andrew E. PYI;  }Q4-> xiA PYI:  xP(# Fast Algorithms for Estimation and Inverse Scattering }U~> pAG ; (MIP8858082 A04); $25,000; 12 months.  }V [ PA  ,@CResearch 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 closetoToeplitzplusHankel systems of equations with applications to twosided spectral estimation, and timefrequency methods wavelets8*6.x,x,XXh)66Mx,x,XX8 and shorttime Fourier transforms to perform spatiallyvarying windowing in order to improve the composition of derivatives of nonstationary signals in nonstationary noise.H  xP  }U~> pAG  University of Missouri Rolla ; John A. StullerStuller, John A. and Nancy  xPx HubingHubing, Nancy;  }Q4-> xiA Time-Delay and Image Motion Estimation }U~> pAG ; (MIP9223020 & A01); $254,836; 36 months.  }V [ PA  ,  This research has three major objectives:H ,  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;H ,  2.to develop practical systems that attain or closely approximate the theoretically optimum estimates; andH ,  3.to compare the accuracy of the theoretically optimum estimates with the estimates obtained by the practical systems.H ,  The research method is primarily theoretical, but includes computational studies and simulation experiments. The approach has the potential to synthesize the traditional divisions between:H ,  1.motion estimation based on optical flow and motion estimation based on feature tracking; andH ,  2.segmentation and motion estimation.H ,  This unification should lead to an increased understanding of image motion estimation and improved motion estimation techniques.H  xPX  }U~> pAG  Washington University ; Donald L. SnyderSnyder, Donald L.;  }Q4-> xiA Stochastic Inverse  xP  Problems for Computational Imaging }U~> pAG ; (MIP9101991 A03 & A04); $77,301; 12 months (Joint support with the Computational Mathematics Program Total Grant $107,301).  }V [ PA  ,  The goals of this research are the development of:H ,  1.improved image restoration algorithms for dealing with stochastic inverse problems;H ,  2.methods for assessing the quality of the images which are produced; andH ,  3.strategies for parallel implementation of the resulting algorithms.H ,  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.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H*7.x,x,XX  xP  }U~> pAG  Rutgers University ; James FlanaganFlanagan, James and Richard MammoneMammone, Richard;  xP  }Q4-> xiA Sound Capture from Spatial Volumes - Parallel Processing of  xP Three-Dimensional Arrays of Sensors }U~> pAG ; (MIP9121541 A01); $91,451; 12 months.  }V [ PA  ,@CHigh-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.T$  xP  }U~> pAG  City University of New York City College ; Patrick L.  xPh CombettesCombettes, Patrick L. RIA;  }Q4-> xiA RIA: Parallel Projection Methods for Set Theoretic  xP0 Signal Restoration & Reconstruction }U~> pAG ; (MIP9308609); $90,000; 36 months.  }V [ PA  ,@CThe 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.T$ ,@CA 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 iterationdependent, extrapolated overrelaxations to achieve very fast convergence; and investigation of the practical and computational issues pertaining to signal/image recovery applications.T$8'7.x,x,XX+77x,x,XX8  xP  }U~> pAG  Polytechnic University ; Seung P. KimKim, Seung P. RIA;  }Q4-> xiA RIA: Block Transform  xP Domain Digital Filter: Theory and Implementation }U~> pAG ; (MIP9211495 A01); $5,848.  }V [ PA  ,  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.H ,  Mathematical descriptions and properties of the BTD filters are being examined. Minimum roundoff filter design are also being investigated for statespace and lattice as well as FIR structures in the block transform domain. In order to implement the resulting nonuniform precision computations, a Block Parallel, BitSerial (BPBS) approach is proposed. The resulting structure is regular and permits faster computation by taking advantage of the compressed signal representation.H  xP  }U~> pAG  }U~> pAG  University of Rochester ; A. Murat TekalpTekalp, A. Murat and Warren E.  xP SmithSmith, Warren E.;  }Q4-> xiA Modeling and Suppression of Motion Artifacts in Magnetic  xPp Resonance Imaging }U~> pAG ; (MIP9119443 A02); $22,844; 12 months.  }V [ PA  ,  Artifacts due to involuntary patient motion have been a major source of image degradation in 2D and 3D 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.H ,  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 motioncorrupted 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.H *8.x,x,XXԌ xP  }U~> pAG  Lehigh University ; Rick S. BlumBlum, Rick S. RIA;  }Q4-> xiA RIA: Distributed Signal  xP Dectection in Uncertain Environments }U~> pAG ; (MIP9211298 A01); $4,980.  }V [ PA  ,@CDistributing 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 nonadditive observations are being sought. The plan to construct these schemes focuses on applying the theory of minimax robust statistics. Cases with nonstationary, possibly nonGaussian background environments and possibly dependent observations are also being investigated.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP8  }U~> pAG  Brown University ; Stuart A. GemanGeman, Stuart A., Ulf GrenanderGrenander, Ulf, Basilis  xP GidasGidas, Basilis and Donald E. McClureMcClure, Donald E.;  }Q4-> xiA Mathematical Sciences:  xP Mathematical and Computational Problems in Object Recognition }U~> pAG ; (DMS9217655); $20,002; 12 months (Joint support with the Computational Mathematics Program, the Statistics Program, and the Probability Program Total Grant $170,001).  }V [ PA  ,@CThis 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 imagebased 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, multiarmed bandit problems, the game of "twenty questions," and, of course, previous work in machine vision.T$ ,@CThe second class of problems is the recognition of nonrigid, or deformable, objects. Examples8*8.x,x,XX+88x,x,XX8 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.H  xP  }U~> pAG  Washington State University ; Thomas R. FischerFischer, Thomas R. and Roberto  xP H. BambergerBamberger, Roberto H.;  }Q4-> xiA Analysis and Design of Multidimensional Filter  xP Banks with Application to Image Coding }U~> pAG ; (MIP9116683 A02 & A03); $119,063; 12 months.  }V [ PA  ,  The basic goal of this research is to develop general analysis and design methods for multidimensional filter bank signal decompositions, featuring nonrectangular 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:H 9.x,x,XX ,@C1.Fdesign exact/nearexact reconstruction multidimensional multirate filter banks for a variety of nonrectangular spectral partitions;T$ ,@C2.Fdevelop a theory for the subband coding gain and coder performance of multidimensional multirate filter bank source coders, emphasizing the filter banks developed in 1;T$ ,@C3.Fdevelop a theory for the influence of perceptual weighting functions in subband coding systems; andT$ ,@C4.Fdetermine 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.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$89.x,x,XX99 x,x,XX8ԯ  Y  pA3 0Digital Representation= catname }V [ PA ۃ  xPA ԇ }U~> pAG  Stanford University ; Robert M. GrayGray, Robert M. and Richard A. OlshenOlshen, Richard A.;  xP   }Q4-> xiA Tree-structured Image Compression and Classification }U~> pAG ; (MIP9311190); $103,971; 12 months.  }V [ PA  ,  Treestructured vector quantization is an approach to image compression that applies ideas from statistical clustering algorithms and treestructured 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 treestructured 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+9.x,x,XX further signal processing. Such systems can provide direct low level classification or provide an efficient front end to more sophisticated fullframe recognition algorithms.T$ ,@CVector 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.T$8'9.x,x,XX+9A9x,x,XX8  xP  }U~> pAG  University of California Berkeley ; Paul R. GrayGray, Paul R., Avideh  xP ZakhorZakhor, Avideh and Bernhard E. BoserBoser, Bernhard E.;  }Q4-> xiA Continuation of Research in  xP High-Speed, High-Resolution Analog-Digital Conversion }U~> pAG ; (MIP9214951); $278,190; 36 months.  }V [ PA  ,  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.H ,  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 selfcalibration techniques for highspeed, 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 sigmadelta A/D converter used for readout purposes in sensor applications.H  xP  }U~> pAG  University of California Berkeley ; Avideh ZakhorZakhor, Avideh PYI;  }Q4-> xiA PYI: Signal Interpretation and Representation Using Neural  xPx Architectures }U~> pAG ; (MIP9057466 A03); $62,500; 12 months.  }V [ PA  ,  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 fractaltype 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.H':.x,x,XX  xP  }U~> pAG  University of California Irvine ; Ian GaltonGalton, Ian RIA;  }Q4-> xiA RIA: Frequency  xP to Digital Conversion }U~> pAG ; (MIP9309656); $99,994; 36 months.  }V [ PA  ,@CThis 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 SigmaDelta 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.T$  xP  }U~> pAG  Georgia Institute of Technology ; Mark J. T. SmithSmith, Mark J. T.;  }Q4-> xiA Dynamic  xP Multirate Systems for Image and Video Compression }U~> pAG ; (MIP9116113 A01); $55,726; 12 months.  }V [ PA  ,@CThis 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:T$ ,@C1.Fdynamically change with the input signal to enable higher quality representations; and T$ ,@C2.Fsimultaneously preserve all of the aliasing cancellation and high quality reconstruction properties achievable with conventional filter banks.T$ ,@CNew 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.T$8(:.x,x,XX(:H:Ix,x,XX8  xP  }U~> pAG  University of Maryland ; Nariman FarvardinFarvardin, Nariman;  }Q4-> xiA A Novel Structured Vector Quantization Scheme: Design, Analysis and  xP Applications }U~> pAG ; (MIP9109109 A01); $89,929; 12 months.  }V [ PA  ,  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 welldefined subset of the Cartesian product of the codebook of a specific entropycoded 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.H ,  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 realworld problems will be studied.H  xP  }U~> pAG  Oregon State University ; Richard SchreierSchreier, Richard RIA;  }Q4-> xiA RIA: Fundamentals  xP of Delta-Sigma Modulation }U~> pAG ; (MIP9210935 A01); $5,000.  }V [ PA  ,  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.H #;.x,x,XX ,@CThe 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. T$ ,@CThe results of these investigations are being incorporated into a computer program for the automated design of delta-sigma modulators.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of Washington ; Eve A. RiskinRiskin, Eve A. NYI;  }Q4-> xiA NYI: Vector  xP Quantization Codebook Processing and Organization }U~> pAG ; (MIP9257587 A01); $37,500.  }V [ PA  ,@CNew 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. T$ ,@CIn 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. T$ ,@CIn 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.T$8%;.x,x,XX$;y;{Kx,x,XX8ԯH&;.x,x,XX  Y  pA3 64Implementationx>catname }V [ PA ۃ  xPy ԇ }U~> pAG  University of California Berkeley ; Edward A. LeeLee, Edward A.;  }Q4-> xiA Design  xPA Methodology for Signal Processing }U~> pAG ; (MIP9201605 A01); $49,508; 12 months (Joint support with the Computer Systems Program Total Grant $79,508).  }V [ PA  ,  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 realtime constraints, and are amenable to synchronous dataflow representations and static (compiletime) scheduling. Other algorithms involve some decision making or runtime control flow, and can be accommodated efficiently by a broader dataflow model that includes runtime flow control. When such algorithms are combined into complete systems, more dynamics must be supported, and discreteevent principles, or realtime operating systems must be included. This research is looking at ways to combine diverse semantics, and is pursuing cosimulation 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.H  xPY  }U~> pAG  University of California Berkeley ; Jan RabaeyRabaey, Jan PYI;  }Q4-> xiA PYI:  xP! Architectures and Synthesis for Digital Signal Processing }U~> pAG ; (MIP8958578 A04 & A05); $62,500; 12 months.  }V [ PA  ,  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.H  xP$  }U~> pAG  University of California Berkeley ; Jan RabaeyRabaey, Jan;  }Q4-> xiA High Level  xP% Synthesis Techniques for VLSI }U~> pAG ; (MIP9222254); $4,982; 12 months (Joint support with the Design, Tools and Test and Systems Prototyping and Fabrication Programs Total Grant $14,944).  }V [ PA  ,  High Level Synthesis has undergone remarkable progress in recent years. A number of powerful synthesis environments have been proposed in the+<.x,x,XX 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. T$ ,@CThe 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.T$ ,@CThis grant includes support for NSFESPRIT cooperation.T$  xP  }U~> pAG  University of Maryland College Park ; K.J. Ray LiuLiu, K. J. Ray RIA;  }Q4-> xiA RIA: Novel Approaches for Numerical Signal Processing: Algorithms  xPq and Architectures }U~> pAG ; (MIP9309506); $89,985; 36 months.  }V [ PA  ,@CThe 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.T$  xP1'  }U~> pAG  University of Minnesota ; Keshab K. ParhiParhi, Keshab K. NYI;  }Q4-> xiA NYI: Dedicated  xP' VLSI Digital Signal and Image Processors }U~> pAG ; (MIP9258670 A01); $10,000.  }V [ PA  ,@CResearch efforts are directed towards the design of dedicated, highperformance digital signal and8+<.x,x,XX+<4y<4x,x,XX8 image processors. The emphasis is on realtime processing, where samples are processed as they are received from the source, as opposed to being stored in buffers and then processed in batch.H ,  Design of algorithm topologies for recursive signal processing algorithms were once considered a major challenge. Using the relaxed lookahead 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, decisionfeedback equalizers, and adaptive differential vector quantizers are being pursued.H ,  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.H0=.x,x,XX  xP  }U~> pAG  Brown University ; Harvey F. SilvermanSilverman, Harvey F.;  }Q4-> xiA Parallel Architectures for Speech Recognition: Testing Expensive Algorithms in a  xP Reconfigurable Environment }U~> pAG ; (MIP9120843 A01 & A02); $56,263; 12 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $103,546).  }V [ PA  ,@CA 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, generalpurpose, computing structure, and speech recognition/training algorithms, to advance the stateoftheart in both areas through their interaction.T$ ,@COne 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.T$ ,@CA second feature is the incorporation of improvements to the current computational and recognition performance of a talkerindependent, connected alphadigit recognizer, database, training, and tools, all developed at Brown. These include microphonearray data acquisition, new signalprocessing algorithms, nonparametric modeling, better durational modeling, and new VQ/featurespace methods.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$8=.x,x,XX=L=V6x,x,XX8ԯ  Y  pA3 5Miscellaneoustbcatname }V [ PA ۃ  xP) ԇ }U~> pAG  University of Alabama Huntsville ; Partha P. BanerjeeBanerjee, Partha P. PYI;  }Q4-> xiA PYI: Studies in Nonlinear Wave Propagation & Optical Signal  xP! Processing }U~> pAG ; (MIP9296000 A02); $5,000.  }V [ PA  ,  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 acoustooptics and optical information processing including the optical interconnection problem.H1'=.x,x,XX  xP)  }U~> pAG  University of California Davis ; G. Robert RedinboRedinbo, G. Robert;  }Q4-> xiA Fault Tolerance in Cell-Site Processing for Mobile Cellular  xP! Communication Systems }U~> pAG ; (MIP9215957); $161,449; 36 months.  }V [ PA  ,@CMobile 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 configurations8+=.x,x,XX'= ) =x,x,XX8 of highspeed functional processing units, ApplicationSpecific Integrated Circuits (ASICs).H ,  In the new faulttolerance design philosophy, algorithmbased 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.H ,  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.H ,  This award includes support for undergraduate students under the Research Experiences for Undergraduates Program.H  xP  }U~> pAG  William Marsh Rice Univiversity ; Don JohnsonJohnson, Don;  }Q4-> xiA Databases for  xP Signal Processing Research }U~> pAG ; (MIP9301646 & A01); $41,461; 12 months.  }V [ PA  ,  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.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H >.x,x,XX  xP  }U~> pAG  University of Wyoming ; Robert F. KubichekKubichek, Robert F. RIA;  }Q4-> xiA RIA: Output-based Objective Estimation of Speech Quality and  xP Intelligibility  }U~> pAG ; (MIP9309315); $83,734; 24 months.  }V [ PA  ,@CDeveloping 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 inputtooutput distortion measures. A related, yet almost unexplored problem, is estimation of transmission quality using only received speech without access to the transmitted speech record (OutputBased Quality or OBQ). A second problem is objectively measuring intelligibility using only received speech (OutputBased 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 speakerindependent speech recognition.T$ ,@COBQ 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.T$88>.x,x,XX >9>/x,x,XX8ԯ >.x,x,XX = MASTER.CSP ?=...XX  b  MASTER.ES  margins XXXX  XXXX ϡprogdefXtd%Xtd%"ȪprogtabOIes-foot%%!8  y(#XXdddy Experimental Systems Program`l$%m"8)  y(#XXdddy `%SExperimental Systems Program5Prognam x~> pA! 1Experimental Systems ~Prognam }V [ PA ۃ 4(Dr. Michael J. Foster, Program Director &(703) 3061936 mfoster@nsf.gov  Y* 6 pA3 The Programkcatname }V [ PA ۃ  XX X4` H(#T$ The Experimental Systems program supports research projects that involve building, evaluating, and experimenting with a computer or informationprocessing system. These are goaloriented 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 proofofconcept 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 faulttolerant 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, offtheshelf 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.)@.x,x,XX  Y - pA3 Initiatives and Opportunitiescatname }V [ PA ۃ 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. A.x,x,XX  Y "ȪprogtabX4` H(#T$8 pA3 Awardscatname }V [ PA ۃ  Yy  pA3 -Graphics and Solid Modellingncatname }V [ PA ۃ  xP ԇ }U~> pAG  Cornell University ; Herbert B. VoelckerVoelcker, Herbert B.;  }Q4-> xiA Mechanical  xP Tolerancing and Dimensional Metrology }U~> pAG ; (DDM9115435 A02); $60,000; 12 months (Joint support with the Computer Integrated Engineering Program Total Grant $130,429).  }V [ PA  ,  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 shopfloor practice, and are taught and applied as collections of specialcase techniques.H ,  This project attempts to lay scientific foundation for these fields and to introduce them in education.H  xP  }U~> pAG  Cornell University ; Herbert B. VoelckerVoelcker, Herbert B.;  }Q4-> xiA Solid Modeling:  xP BoundarytoCSG Conversion }U~> pAG ; (DDM9215463); $30,000; 12 months (Joint support with the Computer Integrated Engineering Program Total Grant $89,949).  }V [ PA  ,  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 (Breps). 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 198991. Their cellbased 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:H ,  1.development of significantly better algorithms for cellbased BCSG conversion;H ,  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) Brep modeling systems; andH ,  3.development of theory and techniques, using new algebraicpatch and constructiveshell representations, to enable BCSG conversion to accommodate freeform solids.H ,  This research is aimed at reestablishing CSG as an industrially viable representation for solids, and:+B.x,x,XX enabling fully symmetric dualrepresentation modeling systems to be built which should be considerably more powerful than today's Breponly systems.T$  xP  }U~> pAG  Duke University ; Gershon KedemKedem, Gershon;  }Q4-> xiA Parallel Raycasting Engines  xPj and CAD/CAE/CAM Applications }U~> pAG ; (MIP9007711 A05); $10,178.  }V [ PA  ,@CThis 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 8processor 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 softwarespecified properties of parts of objects.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program. The students are using the Raycasting 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.T$  xP   }U~> pAG University of North Carolina Chapel Hill ; Henry FuchsFuchs, Henry,  xP John W. PoultonPoulton, John W. and Vernon L. ChiChi, Vernon L.;  }Q4-> xiA Supercomputing Power for  xPJ Interactive Visualization }U~> pAG ; (MIP9000894 A07); (Joint support with the Advanced Research Projects Agency Total Grant $356,965).  }V [ PA  ,@CThis grant supports two additions to the Pixelplanes project. The first is for construction of a highresolution head mounted display. This display extends the use of Pixelplanes to threedimensional 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.T$ ,@CThe second allows completion of the work originally planned.T$ 8:+B.x,x,XX,B1B1x,x,XX8Ԍ xP ԙ }U~> pAG  University of North Carolina Chapel Hill ; John W. PoultonPoulton, John W.  xP and Henry FuchsFuchs, Henry;  }Q4-> xiA Scalable Graphics: From Personal to  xP Supercomputer Visualization Engines  }U~> pAG ; (MIP9306208); $685,636; 12 months (Joint support with the Advanced Research Projects Agency Total Grant $1,323,445).  }V [ PA  ,  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 numberH( C.x,x,XX ,@of identical processors. Each renderer generates a fullscreen image, but for only a fraction of the primitives in the scene. The system then merges these images over a highspeed 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.T$8C.x,x,XX C@C<3x,x,XX8ԯ  YH  pA3 /General Purpose Computing?catname }V [ PA ۃ  xP ԇ }U~> pAG  University of Southern California ; Michel DuboisDubois, Michel, Peter B.  xP DanzigDanzig, Peter B., Massoud PedramPedram, Massoud and Rafael H. SaavedraSaavedra, Rafael H.;  }Q4-> xiA The U.S.C. Multiprocessor Testbed: A Testbed for Scalable Shared-Memory  xP Systems }U~> pAG ; (MIP9223812); $415,456; 15 months.  }V [ PA  ,  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 fieldprogrammable 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 GNUC compiler is being modified to generate appropriate code, such as nonblocking prefetches, and the Mach microkernel is being ported to provide thread scheduling.H  xP  }U~> pAG  University of Illinois Urbana ; Pen-Chung YewYew, Pen-Chung, Wen-mei  xPa HwuHwu, Wen-mei and John BrunerBruner, John;  }Q4-> xiA Improving the Performance of Scalable  xP) Shared-Memory Multiprocessors }U~> pAG ; (MIP9307910); $91,339; 12 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $197,429).  }V [ PA  ,  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 looplevel parallelism, and hierarchical network design. The study of these issues involves the hardwareassisted collection of empirical data on +C.x,x,XX Cedar and the use of simulation. The information thus obtained could lead to the design of nextgeneration systems that, compared to presentday systems, provide higher sustained performance across a broader range of applications.T$  xP9  }U~> pAG  Massachusetts Institute of Technology ; Anant AgarwalAgarwal, Anant;  xP  }Q4-> xiA Automatic Management of Locality in a Scalable CacheCoherent  xP Multiprocessor: The MIT Alewife Machine }U~> pAG ; (MIP9012773 A03); $561,958; 12 months (Joint support with the Computer Systems Architecture Program Total Grant $611,958).  }V [ PA  ,@CThe 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 meshconnected 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.T$  xP$  }U~> pAG  Massachusetts Institute of Technology ; Anant AgarwalAgarwal, Anant PYI;  }Q4-> xiA PYI:  xP$ Automatic Locality Management in Scaleable Multiprocessors }U~> pAG ; (MIP9157393 A02); $25,000; 12 months.  }V [ PA  ,@CParallel 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 the8+C.x,x,XX+C#C#x,x,XX8 vehicle for this research, an experimental parallel machine called the Alewife is being implemented. Alewife employs techniques for:H ,  1.communication latency minimization, using scalable coherent caches and software partitioning and placement of programs, andH ,  2.communication latency tolerance, using a new rapidcontextswitching processor architecture.H ,  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 fullmap directory with the memory overhead of a limited directory. A rapidcontextswitching 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.H ,  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.H  xP  }U~> pAG  University of Michigan Ann Arbor ; Trevor N. MudgeMudge, Trevor N., Edward S. DavidsonDavidson, Edward S., John P. HayesHayes, John P., Santosh G. AbrahamAbraham, Santosh G.  xPP and Richard B. BrownBrown, Richard B.;  }Q4-> xiA Rapid Prototyping and Evaluation of  xP High-Performance Computers }U~> pAG ; (MIP9208342); $240,950; 12 months.  }V [ PA  ,  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 builtin logic analyzer and stimulus generator permit detailed performance measurement and functional testing.H  xPH&  }U~> pAG  New York University ; Allan GottliebGottlieb, Allan;  }Q4-> xiA Ultra III: Implementing  xP' a Scalable SharedMemory Multiprocessor }U~> pAG ; (MIP8915488 A04); $16,165; 6 months.  }V [ PA  ,  This project is building and evaluating ULTRA, a MIMD multiprocessor, using combining switches in the processormemory interface. The supplement*D.x,x,XX 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.T$  xP  }U~> pAG  New York University ; Allan GottliebGottlieb, Allan;  }Q4-> xiA Evaluating the NYU  xPx Ultracomputer }U~> pAG ; (MIP9303014); $42,661; 6 months (Joint support with the Systems Prototyping and Fabrication Program Total Grant $51,891)  }V [ PA  ,@CThis 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 highbandwidth 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.T$  xP  }U~> pAG  Carnegie Mellon University ; Roy M. MaxionMaxion, Roy M.;  }Q4-> xiA Discovering  xPp Information in Large, HighDimensional Databases }U~> pAG ; (IRI9224544); $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).  }V [ PA  ,@CDiscovering functional relationships among highdimensional 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 highquality yield. This research addresses both theoretical and practical concerns. On the theoretical end, statisticians have recently proposed a number of compelling new ideas for highdimensional, 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 largescale simulation experiment is performed that employs statistical design to evaluate the effects of sample size, dimensionality, signaltonoise ratio, and various kinds of underlying functions on the integrated mean8*D.x,x,XX+D\D\%x,x,XX8 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 micromodeled 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.H  xP(  }U~> pAG  University of Virginia ; William A. WulfWulf, William A., James H. AylorAylor, James H. and  xP Jack W. DavidsonDavidson, Jack W.;  }Q4-> xiA Implementation of High Bandwidth Memory  xP Systems  }U~> pAG ; (MIP9307626); $996,441; 24 months.  }V [ PA  ,  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.H  xP  }U~> pAG  Virginia Polytechnic Institute ; Peter M. AthanasAthanas, Peter M. RIA;  }Q4-> xiA RIA: An  xP Architecture and Compiler for Adaptive Computing }U~> pAG ; (MIP9308390); $99,235; 36 months.  }V [ PA  ,  A new processing platform and highlevel 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 highlevel language compiler is responsible for identifying the computationally dominant portions of an application, and for*E.x,x,XX synthesizing hardware structures that can be dynamically loaded into the processing platform for subsequent execution. A generalpurpose platform embracing these principles can reap the performance benefits of applicationspecific 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 costeffective alternative to conventional highperformance computing platforms.T$  xP`  }U~> pAG  University of Washington ; Theodore H. KehlKehl, Theodore H.;  }Q4-> xiA Self-Timed Logic  xP( in Multiprocessors }U~> pAG ; (MIP9101464 A02); $181,579; 12 months.  }V [ PA  ,@CThis project involves building and measuring two selftimed components inserted into an existing sharedmemory multiprocessor computer system. The two components are a multilayered backplane with selftimed arbitration logic and a selftimed 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 selftuning systems (the system is selftuning in that the operating margins are adjusted based on the actual components used in the system).T$  xP  }U~> pAG  University of Washington ; Lawrence SnyderSnyder, Lawrence and Carl EbelingEbeling, Carl;  xPp  }Q4-> xiA Chaotic Routing: Study and Implementation }U~> pAG ; (MIP9213469); $365,237; 12 months.  }V [ PA  ,@CThe 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.T$  xP!  }U~> pAG  University of Wisconsin Madison ; Mark D. HillHill, Mark D., David A.  xP`" WoodWood, David A. and James R. LarusLarus, James R.;  }Q4-> xiA Cooperative Shared Memory and the  xP(# Wisconsin Wind Tunnel }U~> pAG ; (MIP9225097); $422,716; 12 months.  }V [ PA  ,@CThe goal of this project is to design hardware and software for scalable sharedaddressspace computers. Cooperative shared memory, the approach taken in the project, provides a simple design for sharedmemory 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 in8*E.x,x,XX+EE^x,x,XX8 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 checkedoutmemory 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.H  F.x,x,XX ,@CA new virtual prototyping approach is being used for evaluating the new architecture. The Wisconsin Wind Tunnel runs parallel sharedmemory programs on a parallel messagepassing 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.T$8@F.x,x,XX FFx,x,XX8ԯ  Y  pA3 ,Application Specific Computingcatname }V [ PA ۃ  xP ԇ }U~> pAG  International Computer Science Institute ; Nelson MorganShin, Kang G.Morgan, Nelson;  }Q4-> xiA A System for Connectionist Speech Recognition Research; (MIP9311980); $680,002; 12 months.  }V [ PA  ,  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 lowdegree multiprocessor, each node of which contains a highspeed generalpurpose processor, a multipleaccumulate 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.H  xP$  }U~> pAG  Massachusetts Institute of Technology ; John L. WyattWyatt, John L.;  }Q4-> xiA Smart Vision Sensors: Analog VLSI Systems for Integrated Image  xPi& Acquisition and Early Vision Processing }U~> pAG ; (MIP9117724 A02 and A03); $500,000; 12 months (Joint support with the Advanced Research Projects Agency Total Grant $1,408,700).  }V [ PA  ,  The primary goal of this research is to design and test analog VLSI systems for applications of realtime machine vision. In realtime machine vision the+F.x,x,XX 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 VLSIhigh speed, low power and small areacan be exploited and its disadvantageslimited accuracy, inflexibility and lack of storage capacitycan 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, widerange 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 imageprocessing tasks at hundredstothousands of frames per second using only tenstohundreds of milliwatts.T$  xP$  }U~> pAG  University of Michigan Ann Arbor ; Kang G. ShinShin, Kang G.;  xP$  }Q4-> xiA Architecture and OS Support for Real-Time Fault-Tolerant  xP% Communication }U~> pAG ; (MIP9203895 A01); $388,242; 12 months.  }V [ PA  ,@CThis is a project to build and experiment with a multiprocessor for realtime 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,8+F.x,x,XX+F F x,x,XX8 and a custom chip for communications routing. An initial multiprocessor containing only a few nodes is being developed to allow experimentation that will guide fullscale 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.H  xP  }U~> pAG  University of North Carolina Chapel Hill ; Raj K. SinghSingh, Raj K. and  xP Vernon L. ChiChi, Vernon L.;  }Q4-> xiA BioSCAN: A VLSIBased System for Biosequence  xP Analysis }U~> pAG ; (MIP9024585 A02); $31,905; 12 months (Joint support with the Instrumentation and Instrument Development Program Total Grant $61,905).  }V [ PA  ,  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.H  xP  }U~> pAG  Carnegie Mellon University ; L. Richard CarleyCarley, L. Richard and Takeo  xPx KanadeKanade, Takeo;  }Q4-> xiA A Three Dimensional Imaging System Integrating  xP@ Parallel Analog Signal Processing and IC Sensors }U~> pAG ; (MIP8915969 A08); (Joint support with the Advanced Research Projects Agency Total Grant $84,000).  }V [ PA  ,  The topic of this research is the design and use of a smart sensor system for lightstripe range finding. A plane of light is swept over a threedimensional object that is imaged on a twodimensional 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 threedimensional structure of the object can be determined. The sensor uses photodiodes integrated*G.x,x,XX on a chip with analog circuitry at each pixel that can determine the time of maximum illumination. This circuitry is augmented with interpixel 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.T$  xP  }U~> pAG  Carnegie Mellon University ; Takeo KanadeKanade, Takeo, L. Richard CarleyCarley, L. Richard, Dean PomerleauPomerleau, Dean and Andrew GrussGruss, Andrew;  xP`  }Q4-> xiA ALVINN-On-A-Chip: A Computational Sensor for Road  xP( Following }U~> pAG ; (MIP9305494); $621,385; 24 months.  }V [ PA  ,@CThis 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. Onchip 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 roadimage information. The photosensor array includes analog signal processing in each cell and binary optics for better photon statistics, decreased transducer size, and less interference.T$  xP8  }U~> pAG  University of Utah ; Lee A. HollaarHollaar, Lee A.;  }Q4-> xiA Implementation and  xP Evaluation of a Parallel Text Searcher for Very Large Databases }U~> pAG ; (MIP9323174 A03 & A04); $492,274; 12 months.  }V [ PA  ,@CThis project concerns the application of the Utah Retrieval System Architecture to very large databases of fulltext documents. This effort involves the development of a mediumscale (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 highspeed 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 mediumspeed 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.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$8(G.x,x,XX+GYGV"x,x,XX8  Y Ԉ pA3 9OtherE#catname }V [ PA ۃ  xP ԇ }U~> pAG  National Academy of Sciences ; Gary E. DwoskinDwoskin, Gary E.;  }Q4-> xiA Information  xPy Technology and Manufacturing }U~> pAG ; (MIP9312296); $100,000; 16 months (Joint support with the Directorate for Engineering Total Grant $200,000).  }V [ PA  ,  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 welldefined 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.HH.x,x,XX  xP  }U~> pAG  Virginia Polytechnic Institute ; Peter AthanasAthanas, Peter and A. Lynn  xPy AbbottAbbott, A. Lynn;  }Q4-> xiA IEEE Workshop on FPGAs for Custom Computing Machines: Processors, Programming and Applications, April 5-7,  xP  1993, Napa, California }U~> pAG ; (MIP9306310); $4,500; 06 months (Joint support with the Systems Prototyping and Fabrication Program Total Grant $9,000).  }V [ PA  ,@CField 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.T$8H.x,x,XXHHx,x,XX8ԯH.x,x,XX =  MASTER.ES I=...XX  b   MASTER.SPF  margins XXXX  XX ϡprogdefXtd%Xtd%"Ȫprogtabspf-foot!8"8  y(#XXdddy Systems Prototyping and Fabrication Program`l$%m)  y(#XXdddy `|%DSystems Prototyping and Fabrication Program5Prognam x~> pA!  *Systems Prototyping and Fabrication1Prognam }V [ PA ۃ 'Dr. Murali R. Varanasi, Program Director '(703) 3061936 mvaranas@nsf.gov  Y* 6 pA3 The Program2catname }V [ PA ۃ  XX X4` H(#T$ 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. 2SYSTEMS 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: systemslevel 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 systemsfabrication area. Solutions to existing problems might require the development of: architectures for manufacturing, simulation and realtime 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. 7EDUCATION 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. %J.x,x,XX  Y - pA3 Initiatives and OpportunitiestAcatname }V [ PA ۃ 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 (minifab production lines, FieldProgrammable Gate Arrays (FPGA), MultiChip Modules (MCM), optical interconnect, microsensors, etc), new methodologies (fast prototyping, topdown 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. *XOvercoming the performance limitations due to packaging by integrating new packaging concepts into the design process.  *XReducing the cost and time for fabrication and prototyping with new tools, equipment, and services.  *XExploiting new technologies (field programmable gate arrays, multichip modules, etc.) and new methodologies in research and education.  *XSimplifying and automating the fabrication processes.  *XEstablishing package and multichip module packaging standards.  *XFunctional and physical partitioning across and within package levels.  *XEstablishing a better relationship between tool designers and those doing fabrication, packaging and prototyping, in areas such as requirements, integration, and evaluation of performance.  *XDeveloping and integrating techniques for the transition of a virtual to a physical prototype.  *XDeveloping design frames that allow "hardware simulation" of applicationspecific systems.(# *XExposing students to the above considerations in a systemlevel design experience, with practice in the optimized selection among alternatives and exposure to design verification.  *XInnovative use of curricular materials, compression of topics, and curriculum updating to introduce these advances into an overcrowded undergraduate curriculum.  Q*K.x,x,XX  margins XXXX  XX "ȪprogtabX4` H(#T$  Y 8 pA3 Awards-Qcatname }V [ PA ۃ  YA  pA3  *Systems Prototyping and FabricationQcatname }V [ PA ۃ  xP ԇ }U~> pAG  Stanford University ; Teresa H.Y. MengMeng, Teresa H.-Y. PYI;  }Q4-> xiA PYI: Digital Signal  xP Processing Techniques for Image Analysis }U~> pAG ; (MIP8957058 A04); $55,000; 12 months.  }V [ PA  ,  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 highlevel simulator for evaluating algorithms is being developed to run on a distrubutive system.H ,  Research is concentrating on automated gatelevel synthesis of efficient hazardfree 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.H  xPz  }U~> pAG  University of California Berkeley ; David A. HodgesHodges, David A.Hodges, David A.,  xPB Lawrence A. RoweRowe, Lawrence A.Rowe, Lawrence A. and Costas J. SpanosSpanos, Costas J.Spanos, Costas J.;  }Q4-> xiA Computer Integrated  xP  Manufacturing: Database Support and Control Applications }U~> pAG ; (MIP9014940 A02); $197,327; 12 months.  }V [ PA  ,  This research is on systems for instruction in and control of IC (integrated circuit) manufacturing (CIM). There are two parts:H ,  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.H ,  2.Process control and development. Research is focused on designing and prototyping objectoriented systems to support routine manufacturing applications at the equipment level.H ,  Activities include: realtime monitoring, statistical process control, fault diagnosis, the efficient development of new recipes, and the economical:+L.x,x,XX creation of equipment models. Experiments with realtime monitoring of applications on equipment (processing and analytical) and equipment maintenance are being done. Results are being used to create a photolithography workcell prototype.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of California Berkeley ; Jan RabaeyRabaey, Jan;  }Q4-> xiA High Level  xPR Synthesis Techniques for VLSI }U~> pAG ; (MIP9222254); $4,981; 12 months (Joint support with the Circuits and Signal Processing and the Design, Tools and Test Programs Total Grant $14,944).  }V [ PA  ,@CHigh 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. T$ ,@CThe 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.T$ ,@CThis grant includes support for NSFESPRIT cooperation.T$  xP$  }U~> pAG  University of California Santa Cruz ; Wayne W. DaiDai, Wayne W. PYI;  }Q4-> xiA PYI:  xP% Computer Aided Design for VLSI Circuits }U~> pAG ; (MIP9058100 A03); $72,500; 12 months (Joint support with the Design, Tools and Test Program Total Grant $72,500).  }V [ PA  ,@CThis research models the interconnection topology and metrics needed for optimally laying out highspeed interconnections in multichip modules. Three topics are being pursued:T$8:+L.x,x,XX,L0L0x,x,XX8Ԍ,  1.Optimal design of transmission lines for multichip modules (MCM). These are selfdamped lossy transmission lines in a tree network, which propagates highspeed signals. The lines are on the substrates of silicononsilicon thin film MCMs. Algorithms to implement a simple and robust method for designing these transmission lines are being developed.H ,  2.Routing of clock signals for optimum system performance. In this work a novel algorithm is being developed to construct a planer clock tree which can be embedded on a single layer of metal.H ,  3.A multiple bus network for parallel processing which matches the MCM requirements of higher I/O pin count and interchip routing density is being investigated. An algorithm with good fault tolerant properties that leads to uniform bus load and processor fanout is being developed.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H  xPP  }U~> pAG  University of California Santa Cruz ; Martine SchlagSchlag, Martine and  xP Pak K. ChanChan, Pak K.;  }Q4-> xiA Routability-Driven Logic Partitioning for  xP Multiple-FPGA Systems }U~> pAG ; (MIP9223740 & A01); $288,256; 36 months.  }V [ PA  ,  This research addresses the problem of multiway 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 rulesofthumb to ensure the successful placeandroute of individual FPGAs. This work has the following specific goals:H ,  1.to develop new methods for assessing the intrinsic routing requirements of system designs with respect to the architectural resources of FPGAs;H ,  2.to develop effective methods for exercising the tradeoff between logic and routing resources in heterogeneous FPGA architectures; andH ,  3.to incorporate these advances within an integrated routabilitydriven multiway partitioning and technology mapping strategy that will allow effective utilization of the reconfigurable hardware resource.H ,  In addition to new techniques for routability analysis, partitioning and technology mapping, the*M.x,x,XX research develops new insights into the synergy between systemlevel interconnect architecture, FPGA device architecture, routability, and partitioning.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of Colorado Boulder ; YungCheng LeeLee, Yung-Cheng PYI;  }Q4-> xiA PYI:  xP Multichip Module Design for Manufacturing }U~> pAG ; (MIP9058409 A05); $62,500; 12 months.  }V [ PA  ,@CThis 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, flipchip soldering and robot controlled pickandplace techniques are being used. Simulation studies validate the design before prototyping.T$ ,@CResearch is concentrating on the selfaligning 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.T$  xP  }U~> pAG  University of Hartford ; Abiodun IlumokaIlumoka, Abiodun RIA;  }Q4-> xiA RIA: Cost Effective CAD for Robust Design of Integrated Circuits using Artificial  xP8 Neural Networks }U~> pAG ; (MIP9309914); $89,874; 36 months.  }V [ PA  ,@CA high proportion of future integrated systems will contain mixed analog/digital subsystems required to meet demanding quality specifications. CAD (computeraided 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.T$ ,@CTo 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 nonparametric method for mapping one set of data to8*M.x,x,XX+MiMi2x,x,XX8 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.H  xPx  }U~> pAG  University of Delaware ; Phillip ChristieChristie, Phillip;  }Q4-> xiA A Renormalization  xP@ Group Approach to Interconnection Optimization }U~> pAG ; (MIP9224154); $50,000; 12 months.  }V [ PA  ,  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 rackboardchip 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 powerlaw 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.H  xP@  }U~> pAG  University of Florida ; Mark E. LawLaw, Mark E.;  }Q4-> xiA PFF: A Multidisciplinary Approach to IC Process Modeling Using the SUPREMIV  xP Modeling }U~> pAG ; (MIP9253735 A01); $100,000; 12 months.  }V [ PA  ,  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 SUPREMIV, a standard integrated circuit process modeling tool that utilizes advanced finite element techniques.H ,  This is a Presidential Faculty Fellow (PFF) Award initially awarded in Fiscal Year 1992.H0*N.x,x,XX  xP  }U~> pAG  Massachusetts Institute of Technology ; Hae-Seung LeeLee, Hae-Seung PYI;  }Q4-> xiA PYI: Analog Device and Circuit Design in Integrated Circuits and  xP Sensors }U~> pAG ; (MIP8858020 A06); $37,500.  }V [ PA  ,@CThe 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 highperformance analogdigital converter. Research concentrates in two areas:T$ ,@Cl.FBiCMOS Phaselocked Loop Designs. Testing of the first silicon containing transmit and receive phaselocked loops includes tests at 250 Mhz and a characterization of the master slave phaselock 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.T$ ,@C2.FIntegrated Capacitive Sensors and Circuits. Integrated capacitive pressure sensors are being fabricated and tested. Sigmadelta oversampling techniques in the readout are being investigated as a possible replacement for the successive approximation readout technique currently in use.T$  xP8  }U~> pAG  University of Massachusetts ; Maciej CiesielskiCiesielski, Maciej and Wayne  xP BurlesonBurleson, Wayne;  }Q4-> xiA High-Performance VLSI Synthesis with Wave  xP Pipelining }U~> pAG ; (MIP9208267 A01); $25,000; 12 months (Joint support with the Microelectronic Systems Architecture Program Total Grant $90,546).  }V [ PA  ,@CWavepipelining is a method of highperformance 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 wavepipelining in static logic to include dynamic CMOS logic which is known for its smaller area and higherperformance. Previous work in wavepipelining 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 to8*N.x,x,XX*NNkx,x,XX8 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.H  xPx  }U~> pAG  Michigan Technological University ; Ashok K. GoelGoel, Ashok K. and Esther  xP@ T. OsosanyaOsosanya, Esther T.;  }Q4-> xiA Experimental Validation of Interconnection and  xP Transistor Delay Models for the GaAs-Based Integrated Circuits }U~> pAG ; (MIP9223989); $71,563; 12 months.  }V [ PA  ,  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:H ,  1.design and fabrication of several GaAsbased logic circuits to retain the ability to alter the various design parameters;H ,  2.application of the interconnection and the GaAs MESFET delay models recently developed for the determination of propagation delays in these GaAsbased logic circuits;H ,  3.experimental measurements of propagation delays in these circuits and comparison with developed delay models;H ,  4.modification of the interconnection and transistor delay models, as required; andH ,  5.experimental validation of the final models.H  xP%  }U~> pAG  University of Michigan ; William P. BirminghamBirmingham, William P. PYI;  }Q4-> xiA PYI:  xPH& ComputerAided Design Synthesis }U~> pAG ; (MIP9057981 A05); $71,500; 12 months.  }V [ PA  ,  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*O.x,x,XX of manufacturing issues. The knowledgebased synthesis system MICON serves as a software workbench. MICON takes a input highlevel functional specifications for a microprocessorbased system and generates a complete design. More specifically, this research focuses on three major topics:T$ ,@C1.FA designfortestability extension (DFT);T$ ,@C2.FA domainindependent version of MICON (DIM); and,T$ ,@C3.FAn interface to highlevel (behavioral) synthesis tools.T$ ,@CResearch is concentrating on three areas: heuristic search methods for largescale optimization, knowledge acquisition tools, and timing verification.T$ ,@CThis grant includes a supplement for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP0  }U~> pAG  Dartmouth College ; Barry S. FaginFagin, Barry S.;  }Q4-> xiA Quantitative Construction  xP of New FPGA Architectures for Large System Prototyping }U~> pAG ; (MIP9222643); $57,947; 12 months.  }V [ PA  ,@CToday'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 FPGAimplemented interconnect and control, complex systems can be constructed that emulate different microprocessor architectures. This research attempts to identify target applications for which specialpurpose 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:T$ ,@C1.Fthe implementation of custom microprocessors and general emulation systems on FPGAs;T$ ,@C2.Fquantitative analysis of these designs;T$ ,@C3.Fmeasurement of performance, power consumption, and other relevant parameters of these designs; andT$ ,@C4.Fuse of results to develop new FPGA architectures better suited to the prototyping of complex digital systems.T$8(O.x,x,XX+OOx,x,XX8  xP  }U~> pAG  New York University ; Allan GottliebGottlieb, Allan;  }Q4-> xiA Evaluating the NYU  xP Ultracomputer }U~> pAG ; (MIP9303014); $9,230; 6 months (Joint support with the Experimental Systems Program Total Grant $51,891).  }V [ PA  ,  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 highbandwidth 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.H  xP  }U~> pAG  State University of New York Binghamton ; Jiayuan FangFang, Jiayuan NYI;  xP  }Q4-> xiA NYI: Analysis and Modeling of HighSpeed Interconnects in  xPP Electronics Packaging }U~> pAG ; (MIP9357561); $25,000; 12 months.  }V [ PA  ,  This research is concerned with the analysis and modeling of electrical performance of highspeed interconnects in electronics packaging. The finitedifference timedomain (FDTD) method, which is a fullwave solution of Maxwell's equations in three dimensions, is used to simulate signal propagation through interconnects. Topics pursued are:H ,  1.Development of a computational scheme for conformed finitedifference grid to model complexshape 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 finitedifference grid.H ,  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 highclock rate signals; and development of design guidelines for typical interconnection discontinuities in high performance electronics packaging.H*P.x,x,XX  xP  }U~> pAG  University of Rochester ; Alexander AlbickiAlbicki, Alexander;  }Q4-> xiA Synthesizing Energy  xP Efficient Circuits and Systems }U~> pAG ; (MIP9300936); $137,473; 24 months.  }V [ PA  ,@CThis 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.T$ ,@CThe 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.T$  xP  }U~> pAG  North Carolina State University Raleigh ; Paul D. FranzonFranzon, Paul D. NYI;  xP  }Q4-> xiA NYI: Advanced Interconnect and Display Approaches }U~> pAG ; (MIP9357574); $25,000; 12 months.  }V [ PA  ,@CThe 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 guidedwave optical and holographic freespace 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 systemwide 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.T$8(P.x,x,XX+PPx,x,XX8  xP  }U~> pAG  Carnegie Mellon University ; Ronald A. RohrerRohrer, Ronald A.;  }Q4-> xiA Analysis and  xP Design of Electronic System Packaging and Interconnect }U~> pAG ; (MIP9216942); $269,978; 36 months.  }V [ PA  ,  This research is directed toward the problem of extracting threedimensional 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 speedup over traditional interconnect extraction and simulation methods; the ability to perform efficient timedomain 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 threedimensional 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.H ,  The first task in this work is the efficient simulation of nonlinear circuits which contain highspeed 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 threedimensional 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.H  xP@  }U~> pAG  Carnegie Mellon University ; Donald ThomasThomas, Donald and Daniel  xP SiewiorekSiewiorek, Daniel;  }Q4-> xiA Digital System Level Synthesis Tools }U~> pAG ; (MIP9112930 A03 & A04); $125,042; 12 months (Joint support with the Design, Tools and Test Program Total Grant $260,084).  }V [ PA  ,  This research is on algorithms and techniques for systemlevel 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*Q.x,x,XX 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 systemlevel synthesis framework.T$ ,@CThis grant includes support for an undergraduate student under the Research Experiences for Undergraduates Program.T$  xP  }U~> pAG  University of North Texas ; Weiping ShiShi, Weiping RIA;  }Q4-> xiA RIA: Reconfiguration  xP of Re-Programmable Field Programmable Gate Arrays }U~> pAG ; (MIP9309120); $90,000; 36 months.  }V [ PA  ,@CEffective techniques to perform incircuit reconfiguration for FPGAs may lead to a new generation of faulttolerant 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.T$ ,@CThis research is concerned with the diagnosis and reconfiguration of reprogrammable FieldProgrammable Gate Arrays (FPGAs). In particular, the effort focuses on the design of FPGA interconnect diagnosis algorithms, development of incircuit reconfiguration strategies for fault tolerance and change of functionality, and the establishment of a theoretical framework for selfadjustable FPGA systems.T$ ,@CSince 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, fastdiagnosis 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.T$  xP  }U~> pAG  MITRE Corporation ; John F. BeetemBeetem, John F.;  }Q4-> xiA Incremental Placement  xP and Routing for FieldProgrammable Gate Arrays }U~> pAG ; (MIP9396073); $130,700; 24 months.  }V [ PA  ,@CFieldprogrammable 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 has8*Q.x,x,XX+QMQMx,x,XX8 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 forcedirected algorithm with timevarying cost functions is being investigated. Routing is being investigated using incremental penaltydriven 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 highquality FPGA design tools. As a side benefit, the algorithms will also be applicable to conventional IC and PC board placement and routing tasks.H  xPH  }U~> pAG  Virginia Polytechnic Institute ; Peter AthanasAthanas, Peter and A. Lynn  xP AbbottAbbott, A. Lynn;  }Q4-> xiA IEEE Workshop on FPGAs for Custom Computing Machines: Processors, Programming and Applications, April 5-7,  xP 1993, Napa, California }U~> pAG ; (MIP9306310); $4,500; 6 months (Joint support with the Experimental Systems Program Total Grant $9,000).  }V [ PA  ,  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.H  xP  }U~> pAG  University of Washington ; Gaetano BorrielloBorriello, Gaetano PYI;  }Q4-> xiA PYI: CAD for  xPx System Integration of Custom Components }U~> pAG ; (MIP8858782 A07); $47,490.  }V [ PA  ,  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:H ,  1.An internal representation for circuit behavior that allows the specification of complex timing constraints as well as mixing structural and behavioral specifications;H ,  2.Synthesis methods for mixed synchronous*R.x,x,XX control logic;8" ,@C3.FTiming optimization of sequential logic; andT$ ,@C4.FNew highlevel synthesis approaches that take timing constraints into account.T$ ,@CThe 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.T$ ,@CResearch is concentrating on six areas: timing analysis of concurrent processes; interface specification, synthesis, and verification; hardware/software cosynthesis; mobile robots; behavioral simulation; and programmable logic devices.T$ ,@CThis grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.T$  xP0  }U~> pAG  West Virginia University ; Lawrence A. HornakHornak, Lawrence A. NYI;  }Q4-> xiA NYI: Cointegrated Polymer Waveguide Optical Interconnections for  xP WaferLevel MCM Systems }U~> pAG ; (MIP9257101 A01); $100,000; 12 months.  }V [ PA  ,@CMotivated 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 multichip 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.T$ ,@CResearch 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.T$80*R.x,x,XX+RROx,x,XX8  xP  }U~> pAG  University of Wisconsin Madison ; Rajiv JainJain, Rajiv RIA;  }Q4-> xiA RIA:  xP Partitioning, Rapid Prototyping and High Level Synthesis }U~> pAG ; (MIP9307830); $99,996; 36 months.  }V [ PA  ,  Partitioning of large designs into smaller and more manageable parts is a very important design task. In highlevel synthesis of registertransfer level designs, partitioning the specification is done prior to synthesizing the designs. If the input specification is controldominated, the specification is partitioned into a set of states, or if the specification is datadominated 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 reexamines the partitioning problem, outlines some concerns with existing techniques and presents a fresh approach to formulating and solving the partitioning problem.H S.x,x,XX ,@CSpecifically, the effort focuses on a datapath model which can be used for rapidprototyping at the registertransfer level design and for partitioning of the input specification. The solution to these problems is achieved by scheduling the input specificiation onto the datapath model. The scheduling result can then be interpreted from a rapidprototyping perspective or from a partitioning perspective as desired by the designer.T$8@S.x,x,XXSSx,x,XX8ԯ  Y  pA3 47Educationcatname }V [ PA spf-foot6\t  y(#XXdddy Systems Prototyping and Fabrication Program`l$%m7\t  y(#XXdddy `|%DSystems Prototyping and Fabrication Programۃ  xPq ԇ }U~> pAG  University of Hawaii ; Michael J. S. SmithSmith, Michael J.S. PYI;  }Q4-> xiA PYI: Computer xP9 Aided Analog Integrated Circuit (IC) Design }U~> pAG ; (MIP8957407 A03 & A04); $72,500; 12 months.  }V [ PA  ,  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 CDROM containing pertinent educational material has been developed and work is now underway writing a textbook on microsystems education. Work is also continuing on mixed analogdigital design.H ,  During this grant period, the research is focused on the concept of a reprogrammable addin card for personal computers and the completion of the draft of a textbook on ASIC design.H ,  This grant includes support for undergraduate students under the Research Experiences for Undergraduates Program.H$S.x,x,XX  xPq  }U~> pAG  University of Tennessee ; Donald W. BouldinBouldin, Donald W.;  }Q4-> xiA 1993 Workshop on Rapid Prototyping of Integrated Circuits for Universities,  xP October 1819, 1993, Washington, DC }U~> pAG ; (MIP9319902); $33,006; 12 months.  }V [ PA  ,@CThis 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 stateoftheart 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.T$8'S.x,x,XX$SqSx,x,XX8ԯ MASTER.SPF (S.x,x,XX  b index-foot6\7\d  y(#XXdddy Index`l$%md)  y(#XXdddy `#%jIndex5Prognam x~> pA!  'Index of Presidential Young Investigators'Prognam }V [ PA ۃ Agarwal, Anant pt754 Banerjee, Partha P. pt748 Birmingham, William P. pt766 Borriello, Gaetano pt769 Bresler, Yoram pt740 Buckley, Kevin M. pt738 Burns, Steven M. p t84 Bushnell, Michael L. pt713 Cong, Jason p t86 Dai, Wayne W. pt310, 63 Dally, William pt724 Devadas, Srinivas p t87 Dill, David p t84 Eggers, Susan J. pt727 Fang, Jiayuan pt767 Farrens, Matthew pt721 Ferguson, Frankie J. pt714 Franzon, Paul D. pt767 Hill, Mark D. pt728 Hornak, Lawrence A. pt769 Kahng, Andrew p t86 Larrabee, Tracy pt714 T.x,x,XX Lee, Hae-Seung p$%m65 Lee, Yung-Cheng p$%m64 Meng, Teresa H.-Y. p$%m63 Orchard, Michael T. p$%m41 Parhi, Keshab K. p$%m47 Pillage, Lawrence T. p$%m16 Pomeranz,Irith p$%m13 Rabaey, Jan p$%m47 Ramachandran, Umakishore p$%m22 Riskin, Eve A. p$%m46 Saleh, Resve A. p$%m15 Siu, Kai-Yeung p#%i21, 35 Smith, Michael J.S. p$%m70 Stonick, Virginia L. p$%m39 Van Veen, Barry D. p$%m39 Varma, Anujan p$%m22 Wawrzynek, John p$%m29 White, Jacob K. p$%m16 Yagle, Andrew E. p$%m41 Yang, Andrew T. p$%m17 Zakhor, Avideh p$%m458:T.x,x,XXTTx,x,XX8ԯ ZT.x,x,XX =U=...XX  b 5Prognam x~> pA!  &Index of Research Initiation Investigators Prognam }V [ PA ۃ Akella, Venkatesh p t85 Andreou, Andreas pt730 Athanas, Peter M. pt756 Blum, Rick S. pt743 Chakrabarti, Chaitali pt728 Chamberlain, Roger D. pt716 Chatterjee, Abhijit pt710 Chaudhary, Vipin pt725 Combettes, Patrick L. pt742 Dutt, Nikil p t85 Galatsanos, Nikolas F. pt740 Galton, Ian pt745 Ilumoka, Abiodun pt764 Jain, Rajiv pt770 Kim, Seung P. pt743 Kubichek, Robert F. pt749 V.x,x,XX Li, Jian p$%m40 Liu, K. J. Ray p$%m47 Lo, Jien-Chung p#%i14, 26 Madisetti, Vijay K. p$%m40 Malik, Sharad p,%%n8 Manolakos, Elias S. p$%m30 Najm, Farid p$%m10 Nowick, Steven M. p,%%n8 Orailoglu, Alex p$%m10 Panda, Dhabaleswar K. p$%m26 Schreier, Richard p$%m46 Shi, Weiping p$%m68 Shynk, John p$%m36 Torrellas, Josep p$%m23 Zhu, Yahui p$%m268 V.x,x,XXVVx,x,XX8ԯV.x,x,XX =W=...XX  b 5Prognam x~> pA!  +Index of Principal InvestigatorsPrognam }V [ PA ۃ A Abbott, A. Lynnpt359, 69 Abraham, Jacobpt713 Abraham, Santosh G.pt755 Adams, John W.pt736 Agarwal, Anant pt754 Akella, Venkatesh p t85 Albicki, Alexanderpt767 Andreou, Andreaspt329, 30 Armstrong, Jamespt713 Athanas, Peter M.pt/56, 59, 69 Aylor, James H.pt756 B Bamberger, Roberto H.pt744 Banerjee, Partha P. pt748 Beetem, John F.pt768 Bhattacharya, Debashispt712 Bhuyan, Laxmi N.pt727 Birmingham, William P. pt766 Blum, Rick S. pt743 Borriello, Gaetano pt769 Bose, Bellapt731 Boser, Bernhard E.pt745 Bouldin, Donald W.pt770 Bresler, Yoram pt740 Brown, Richard B.pt755 Bruner, Johnpt323, 54 Brunvand, Erikpt49, 27 Buckley, Kevin M. pt738 Burleson, Waynept324, 65 Burns, Steven M. p t84 Bushnell, Michael L. pt713 C Cai, Jaizhenp t83 Carley, L. Richardpt758 Chakrabarti, Chaitali pt728 Chamberlain, Roger D. pt716 Chan, Pak K.pt764 Chatterjee, Abhijit pt710 Chaudhary, Vipin pt725 Chi, Vernon L.pt353, 58 Chien, Andrewpt722 Christie, Phillippt765 Chua, Leon O.pt735 Ciesielski, Maciejpt324, 65 Clarke, Edmund M.p t88 Cohoon, James P.p t84 Combettes, Patrick L. pt742 Cong, Jason p t86 Cyre, Wallingpt713 :+X.x,x,XXԌVD Dai, Wayne W. p#%i10, 63 Dally, William p$%m24 Danzig, Peter B.p$%m54 Das, Chitaranjanp$%m26 Davidson, Edward S.p"%e11, 24, 55 Davidson, Jack W.p$%m56 Devadas, Srinivas p,%%n7 Dill, David p,%%n4 Dubois, Michelp$%m54 Dutt, Nikil p,%%n5 Dwoskin, Gary E.p$%m59 VE Ebeling, Carlp$%m56 Eggers, Susan J. p$%m27 El-Amawy, Ahmedp$%m24 Esfahanian, Abdol-Hosseinp$%m24 Etter, Deloresp$%m37 VF Fagin, Barry S.p#%i30, 66 Fang, Jiayuan p$%m67 Farrens, Matthew p$%m21 Farvardin, Narimanp$%m46 Feng, Tse-Yunp$%m26 Ferguson, Frankie J. p$%m14 Fischer, Thomas R.p$%m44 Flanagan, Jamesp$%m42 Franzon, Paul D. p$%m67 Fuchs, Henryp#%i53, 54 VG Gajski, Danielp,%%n5 Galatsanos, Nikolas F. p$%m40 Galton, Ian p$%m45 Gardner, William A.p$%m36 Geman, Stuart A.p$%m43 Gidas, Basilisp$%m43 Goel, Ashok K.p$%m66 Gopalakrishnan, Ganeshp$$%j9, 27 Gottlieb, Allanp#%i55, 67 Gray, Paul R.p$%m45 Gray, Robert M.p$%m44 Grenander, Ulfp$%m43 Gruss, Andrewp$%m58 VH Ha, Dong S.p$%m15 Hachtel, Garyp,%%n6 Harris, Jayp$%m28 Hayes, John P.p#%i13, 55 Hill, Mark D. p#%i28, 568:+X.x,x,XX,X4X4x,x,XX8ԌHodges, David A.pt763 Hollaar, Lee A.pt758 Hornak, Lawrence A. pt769 Hubing, Nancypt742 Hwu, Wen-Meipt/22, 23, 54 I Ilumoka, Abiodun pt764 Irwin, Mary Janept731 J Jain, Rajiv pt770 Johnson, Donpt749 Johnson, Stevenp t87 K Kahng, Andrew p t86 Kanade, Takeopt758 Karpovsky, Markpt730 Kaveh, Mostafapt738 Kedem, Gershonpt753 Kehl, Theodore H.pt756 Kim, Seung P. pt743 Koren, Israelpt714 Kubichek, Robert F. pt749 Kuh, Ernestp t85 L Larrabee, Tracy pt714 Larus, James R.pt756 Law, Mark E.pt765 Lee, Edward A.pt747 Lee, Hae-Seung pt765 Lee, Yung-Cheng pt764 Lev-Ari, Hanochpt737 Levitan, Stevenp t89 Li, Jian pt740 Lightner, Michaelp t86 Lilja, David J.pt725 Lin, Rongpt725 Liu, C. L.p t86 Liu, K. J. Ray pt747 Liu, Wentaipt725 Lo, Jien-Chung pt314, 26 Lo, Virginiapt731 Louri, Ahmedpt721 M Madisetti, Vijay K. pt740 Malik, Sharadp t88 Mammone, Richardpt742 Manolakos, Elias S. pt730 Maxion, Roy M.pt311, 55 McClure, Donald E.pt743 McKinley, Philip K.pt724 Mendel, Jerry M.pt736*Y.x,x,XXԌMeng, Teresa H.-Y. p$%m63 Menon, Premachandranp,%%n7 Morgan, Nelsonp$%m57 Mudge, Trevor N.p"%e11, 24, 55 Mumford, Davidp$%m41 Murdocca, Milesp$%m25 VN Najm, Farid p$%m10 Nehorai, Aryep$%m37 Ni, Lionel M.p$%m24 Nikias, Chrysostomos L.p$%m37 Nowick, Steven M. p,%%n8 VO Olshen, Richard A.p$%m44 Orailoglu, Alex p$%m10 Orchard, Michael T. p$%m41 Ososanya, Esther T.p$%m66 Owens, Robertp$%m31 VP Paige, Robertp,%%n3 Palusinski, Olgierdp$%m15 Panda, Dhabaleswar K. p$%m26 Pangrle, Barry M.p,%%n8 Parhi, Keshab K. p$%m47 Parks, Thomas W.p$%m38 Pedram, Massoudp$%m54 Pillage, Lawrence T. p$%m16 Pineda, Fernandop$%m29 Pomeranz, Irithp#%i12, 13 Pomerleau, Deanp$%m58 Poulton, John W.p#%i53, 54 Pradhan, Dhiraj K.p$%m31 Prasana, V. K.p$%m29 Proakis, John G.p$%m38 VR Rabaey, Janp!%a10, 47, 47, 63 Rajopadhye, Sanjayp$%m31 Ramachandran, Umakishorep$%m22 Ramanathan, Parameswaranp$%m32 Rao, Bhaskar D.p$%m39 Reddy, Sudhakar M.p$%m12 Redinbo, G. Robertp$%m48 Riskin, Eve A. p$%m46 Rohrer, Ronald A.p#%i16, 68 Rowe, Lawrence A.p$%m63 VS Saavedra, Rafael H.p$%m54 Sahni, Sartajp,%%n3 Sakallah, Karemp#%i11, 24 Saleh, Resve A. p$%m15 Salowe, Jeffrey S.p,%%n48*Y.x,x,XX+YmYm6x,x,XX8ԌSaluja, Kewalpt715 Sarrafzadeh, Majidp t83 Schlag, Martinept764 Schreier, Richard pt746 Shi, Weiping pt768 Shin, Kang G.pt757 Shragowitz, Eugenept711 Shynk, John pt736 Siewiorek, Danielpt311, 68 Silverman, Harvey F.pt331, 48 Singh, Aditpt714 Singh, Raj K.pt758 Siu, Kai-Yeung pt321, 35 Smith, Alan J.pt721 Smith, Mark J. T.pt745 Smith, Michael J.S. pt770 Smith, Warren E.pt743 Snyder, Donald L.pt742 Snyder, Lawrencept756 Somani, Arun K.pt728 Somenzi, Fabiop t86 Spanos, Costas J.pt763 Steiglitz, Kennethpt731 Stonick, Virginia L. pt739 Stuller, John A.pt742 T Tanner, Johnp t89 Tekalp, A. Muratpt743 Thomas, Donaldpt311, 68 Thomborson, Clarkp t83 Tong, Carolpt712 Torrellas, Josep pt723 Z.x,x,XX VV Vaidyanathan, P. P.p$%m39 Van Veen, Barry D. p$%m39 Varma, Anujan p$%m22 Venkateswaran, H.p$%m22 Voelcker, Herbert B.p$%m53 VW Wah, Benjamin W.p#%i23, 32 Wawrzynek, John p$%m29 White, Jacob K. p$%m16 Willsky, Alanp$%m41 Willson, A. N.p$%m35 Wolf, Waynep,%%n8 Wolpert, Sethp$%m29 Wood, David A.p$%m56 Wulf, William A.p$%m56 Wyatt, John L.p$%m57 VY Yagle, Andrew E. p$%m41 Yang, Andrew T. p$%m17 Yang, Qingp$%m27 Yew, Pen-Chungp#%i23, 54 VZ Zakhor, Avidehp$%m45 Zemanian, Armenp,%%n4 Zhu, Yahui p$%m268Z.x,x,XXZZox,x,XX8ԯZ.x,x,XX =[=...XX  b 5Prognam x~> pA! 1Index of Institutionsc1Prognam }V [ PA ۃ Arizona State Universitypt6 28 Auburn Universitypt6 14 Boston Universitypt6 30 Brown Universitypt. 31, 43, 48 California Institute of Technologypt6 39 California State University Northridgept6 36 Carnegie Mellon Universitypt' 8, 11, 16, 39, 55 pt2 58, 68 City University of New York City Collegept6 42 Colorado State Universitypt6 12 Columbia Universitypt6 8 Cornell Universitypt2 38, 53 Dartmouth Collegept2 30, 66 Duke Universitypt6 53 Georgia Institute of Technologyp|t* 10, 22, 40, 45 Harvard Universitypt6 41 Illinois Institute of Technologypt6 40 Indiana Universitypt6 7 International Computer Science Institutept6 57 Johns Hopkins Universitypt2 29, 30 Lehigh Universitypt6 43 Louisiana State Universitypt6 24 Massachusetts Institute of Technologypt/ 7, 16, 24 p|t* 41, 54, 57, 65 Michigan State Universitypt6 24 Michigan Technological Universitypt6 66 MITRE Corporationpt6 68 National Academy of Sciencespt6 59 New York Universitypt* 3, 21, 55, 67 North Carolina State Universitypt2 25, 67 North Dakota State Universitypt6 26 Northeastern Universitypt. 30, 37, 38 Northwestern Universitypt6 3:+\.x,x,XX Ohio State Universityp$%l 26 Oregon Advanced Computing Institutep$%l 31 Oregon State Universityp$%l 46 Pennsylvania State Universityp"%d 26, 31, 37 Polytechnic Universityp$%l 43 Princeton Universityp8#%f 3, 8, 31 Rutgers Universityp"%d 13, 25, 42 San Diego State Universityp$%l 28 Stanford Universityp"%e 4, 23, 63 State University of New York Stony Brookp$%l 4 State University of New York Geneseop$%l 25 State University of New York Binghamtonp$%l 67 Tanner Researchp$%l 9 Texas A&M Universityp#%h 27, 54 University of Alabama Huntsvillep$%l 48 University of Arizonap#%h 15, 21 University of California Berkeleyp!%a 5, 10, 21, 29 p!%` 35, 45, 47, 63 University of California Davisp!%a 5, 21, 36, 48 University of California Irvinep!%` 5, 21, 35, 45 University of California Los Angelesp#%i 6, 35 University of California San Diegop#%h 10, 39 University of California Santa Barbarap$%l 36 University of California Santa Cruzp"%d 10, 14, 22 p#%h 63, 64 University of Coloradop"%e 6, 37, 64 University of Delawarep$%l 65 University of Floridap"%d 3, 40, 65 University of Hartfordp$%l 64 University of Hawaiip$%l 70 University of Illinois Urbanap %] 6, 10, 15, 22, 23 p!%` 32, 40, 41, 54 University of Iowap#%h 12, 13 University of Mainep$%l 29 University of Marylandp#%h 46, 47 University of Massachusettsp!%a 7, 14, 24, 65 University of Michiganpp%T 11, 13, 24, 41, 55, 57, 668:+\.x,x,XX,\4\4x,x,XX8ԌUniversity of Minnesotapt' 3, 11, 25, 38, 47 University of Missouri Rollapt6 42 University of North Carolina Chapel Hillpt6 53 pt2 54, 58 University of North Texaspt6 68 University of Pittsburghpt6 9 University of Rhode Islandpt. 14, 26, 27 University of Rochesterpt2 43, 67 University of Southern Californiap|t* 29, 36, 37, 54 University of Tennesseept6 70 University of Texas Austinpt2 13, 16 University of Utahpt/ 9, 27, 58 ].x,x,XX University of Virginiap#%h 4, 56 University of Washingtonp%U 4, 17, 27, 28, 46, 56, 69 University of Wisconsin Madisonpx%X 15, 28, 32, 39, 56, 70 University of Wyomingp$%l 49 Virginia Polytechnic Institutep %\ 13, 15, 56, 59, 69 Washington State Universityp$%l 44 Washington Universityp#%h 16, 42 Wayne State Universityp$%l 25 West Virginia Universityp$%l 69 William Marsh Rice Univiversityp$%l 49 Yale Universityp#%h 12, 378H ].x,x,XX]H]G6x,x,XX8ԯ