Break-out Topics and Talks

Tuesday, February 26, 2002

SESSION I 9:35 - 10:50	Artificial Intelligence Henry Kautz Sieg Hall 324	Computational Biology Martin Tompa Sieg Hall 322	Architecture Susan Eggers HUB 209A
SESSION II 11:00 - 12:15	Systems and Networking Hank Levy Sieg Hall 324	Programming Languages and Simulation Alan Borning Sieg Hall 322	Databases I Alon Halevy HUB 209A
SESSION III 3:00 - 4:15	Ubiquitous Computing Larry Arnstein Sieg Hall 324	Graphics and Vision Zoran Popovic Sieg Hall 322	Databases II Dan Suciu HUB 209A
SESSION IV 4:30 - 5:45	Compilers Craig Chambers Sieg Hall 324	Theory Richard Ladner Sieg Hall 322	Reconfigurable Hardware Carl Ebeling HUB 209A

Session I

Artificial Intelligence: Henry Kautz

• Improving Web Interactions with Machine Learning (Powerpoint Slides)
  Corin Anderson
  "The web experience today suffers from a one-size-fits-all philosophy -- web sites deliver the same content to each and every visitor, and interact with first-time users and veteran surfers in exactly the same way. However, one size frequently does not fit all. Instead the web experience should be personalized for each visitor, adapting to their needs and behaviors. In this talk I will present work done on improving interactions for wireless web visitors, and automatically adding shortcut links based on navigation history. This work employs machine learning to mine user models from web logs and applies these models to evaluate autonomous adaptations to the site.”
• Sample-Based Methods for Robot Soccer
  Cody Kwok
  "Robot soccer has recently become a popular test bed for AI and robotics. The environment is constantly changing and adversarial, robots therefore need to coordinate their control with motion and strategy planning in real time. I will talk about our robot soccer team participating in the Robocup Soccer, an annual event with over a hundred research institutions all over the world. The talk focuses on the important research problem of estimating the state of the soccer field, which provides the information needed for high-level decision making. Our sample-based method is able to efficiently keep track of the dynamic soccer environment, given very inaccurate vision-based environment detection, large motion errors and low on-board processing power of these robots.”
• High Precision Natural Language Interfaces to Databases: A Graph Theoretic Approach
  Ana-Maria Popescu, Oren Etzioni, and Henry Kautz
  "The need for Natural Language Interfaces (NLIs) to databases has become increasingly acute as more nontechnical people access information through their web browsers, PDAs, and cell phones. Yet NLIs are only usable if they map natural language questions to SQL queries correctly. We introduce the PRECISE NLI, which reduces the semantic interpretation challenge in NLIs to a graph matching problem. We show that, for a broad class of natural language questions, PRECISE is guaranteed to return a correct SQL query and compares favorably with other available NLIs.”

Computational Biology: Martin Tompa

• Towards pooling of large-scale yeast two-hybrid screens
  Zasha Weinberg
  "Pooling is a strategy that can improve the throughput of biological experiments. In this talk, I consider applying pooling to the yeast two-hybrid system. Although there is good reason to believe that pooling will significantly improve its throughput, the significant error rates found in the two-hybrid system complicate matters. My work shows how this complication can be addressed and analyzes other work necessary to implement pooling for the two-hybrid system.”
• Enhancing gene-finding techniques with molecular simulations (Powerpoint Slides)
  Don Patterson
  "Accurate splice site prediction is a critical component of any computational approach to gene prediction in higher organisms. Existing approaches generally use sequence-based models that capture local dependencies among nucleotides in a small window around the splice site. We present evidence that computationally predicted secondary structure in pre-messenger RNAs contains information that can be exploited to improve splice site prediction beyond that possible with conventional sequence-based approaches.”
• Discriminative Motifs
  Saurabh Sinha
  "This talk describes a new view of motif discovery, addressing a common problem in existing motif finders. A motif is treated as a feature of the input promoter regions that leads to a good classifier between these promoters and a set of background promoters. This perspective allows us to adapt existing methods of feature selection, a well studied topic in machine learning, to motif discovery. We develop a general algorithmic framework that can be specialized to work with a wide variety of motif models, including consensus models with degenerate symbols or mismatches, and composite motifs. A key feature of our algorithm is that it measures over-representation while maintaining information about the distribution of motif instances in individual promoters. The assessment of a motif's discriminative power is normalized against chance behaviour by a probabilistic analysis. We apply our framework to two popular motif models, and are able to detect several known binding sites in sets of co-regulated genes in yeast.”
• Extensions to REDUCE: Regulatory Element Detection Using Correlation with Expression (PDF Slides)
  Dan Grossman
  "We present extensions to a recently proposed computational method for discovery of transcription factor binding motifs by correlating genome sequence and genome-wide expression data. We have augmented the original approach by making feasible the examination of a far larger search space and by incorporating an empirical background distribution based on negative controls. Analyses of datasets used by the proponents of the original model and of other publicly available sets confirm our algorithm's aptitude for uncovering motifs known in the biological literature as well as novel putative regulatory sequences.”

Architecture: Susan Eggers

• A Modeling Framework for Network Processor Systems
  Patrick Crowley
  "This presentation introduces a modeling framework for network processing systems. The framework is composed of independent application, system and traffic models which describe router functionality, system resources/organization and packet traffic, respectively. The framework uses the Click Modular router to describe router functionality. Click modules are mapped onto an object-based description of the system hardware and are profiled to determine maximum packet flow through the system and aggregate resource utilization for a given traffic model. This paper presents several modeling examples of uniprocessor and multiprocessor systems executing IPv4 routing and IPSec VPN encryption/decryption. Model-based performance estimates are compared to the measured performance of the real systems being modeled; the estimates are found to be accurate within 10%. The framework emphasizes ease of use and utility, and permits users to begin full system analysis of existing or novel applications and systems very quickly.”
• A Prefetching Memory System for Mediaprocessors (PDF Slides)
  Stefan G. Berg "Mediaprocessors are programmable processors specifically designed to provide flexible, cost-effective, high-performance computing platforms for multimedia computing. Most mediaprocessors support data cache, DMA, or both on a single chip. First, we will discuss advantages and disadvantages of utilizing a data cache or DMA. Then, we introduce a prefetching cache-based memory system that requires minimal programmer input, but can transfer data between processor and main memory as efficiently as a DMA controller. The data transfer is efficient for three reasons. First, it utilizes a prefetcher to tolerate main memory latency. Second, it transfers both input and output data in blocks to minimize page misses in the off-chip DRAM and sustain a high memory throughput. Third, a no-write-allocate write-miss policy is used to efficiently utilize main memory bandwidth. The simulation results show that our cache-based memory system, on average, reduces execution time by 54% compared to a baseline cache-based architecture. In comparison, the average execution time reduction of a DMA controller over the baseline architecture was 56%.”
• The Computation Cache: A Scalable Execution Algorithm for Exploiting Multiple Functional Units (Powerpoint Slides)
  Steven Swanson and Mark Oskin
  "The next two decades will bring us computation resources that seem unimaginable today. Advancements in lithographic technology will make devices with billions of transistors possible. With these computational resources come three challenges. First, relative to computation, communication will be orders of magnitude more expensive. Second, the transistors and the manufacturing process will be unreliable. To maintain reasonable yields, we must be willing to tolerate some flaws in each chip. Finally, our ability to engineer complex computing devices in a reasonable time is coming into question, and leading to the ever-expanding productivity-gap between the complexity of modern architectures and the rate at which they can be effectively designed and verified. We propose the Computation Cache, a unique way to construct systems that forges together the concepts of an instruction cache and a microprocessor into a single unified concept. A computational cache is a tiled node architecture, where each tile can be thought of as a word in a conventional instruction cache that also has the ability to compute. By using many simple tiles and by configuring itself dynamically, the Computation Cache is both easy to design and robust to manufacturing defects. Data flows around the Computation Cache to the instructions that need it (similar to dataflow computing). Dataflow computation using a fully distributed execution algorithm allows the Computation Cache to extract much of the parallelism in a program and maximize performance.”
• Increasing Thread-Level Parallelism Through Minithreads on SMT
  Joshua Redstone
  "Recently, several manufacturers have announced small-scale SMTs (e.g., 2 to 4 thread contexts), both as single CPUs and as components of multiple CPUs on a chip. While these small-scale SMTs can significantly boost performance, they still leave modern wide-issue CPUs with underutilized resources, i.e., substantial performance potential is still unexploited. A primary obstacle to the construction of larger-scale SMTs is the register file. In this talk we propose and evaluate a new mechanism to boost thread-level parallelism (and therefore, thruput) on small-scale SMTs, without the significant cost of additional register files. This mechanism, called minithreads, adds additional (minithread) program counters to each of SMT's hardware contexts. These PCs provide an application with the ability to create more thread-level parallelism within a context by forking minithreads that will share the context's architectural registers. Our results show a significant improvement of a mini-thread enhanced SMT over a normal SMT of between 10% and 83% over a range of configurations.”

Session II

Systems and Networking: Hank Levy

• Measuring ISP network topologies
  Neil Spring
  "Realistic ISP topologies for network modeling and protocol simulation have been hard to come by. In this talk, we describe new techniques to measure router-level ISP network topologies using web-accessible traceroute servers. Our techniques a) choose traceroutes that traverse potentially unique paths through the ISP's network, b) discover which IP addresses represent the same router, and c) use DNS names to divide maps into POPs and backbone. We will summarize each technique, and show a sample of measured topologies.
• Using DNS to build Internet applications (Powerpoint Slides)
  Krishna Gummadi
  "Many newly proposed internet services and emerging peer-to-peer systems need the ability to estimate the latency between arbitrary hosts in the internet. However, the absence of inexpensive and reliable mechanisms for estimating network latencies force the systems today to use ad-hoc or propreitary solutions. Examples include distributed binning algorithm to build topologically sensitive overlays for peer-to-peer systems and Akamai's Edgesuite to direct clients to a close replica server. In this talk, we present our solution to estimate the latency between any two remote hosts in the internet -- King. King works by measuring the latency between the domain name servers of the hosts involved. Our preliminary evaluations indicate that estimates produced by King are fairly accurate (over 70% of the estimates are within an error of 20%). Furthermore, its accuracy is no worser than previously proposed more expensive solutions, like IDMAPs and GNP. We also discuss three different applications that could benefit from using king: (1) wide-area network latency measurements, (2) closest server selection (3) building topologically sensitive overlays.”
• A study of BGP misconfiguration (PDF Slides)
  Ratul Mahajan
  "It is well-known that simple, accidental BGP configuration errors can disrupt Internet connectivity. Yet little is known about the frequency of misconfiguration or its causes, except for the few spectacular incidents of widespread outages. In this talk, we present the first quantitative study of BGP misconfiguration. Over a three week period, we analyzed routing table advertisements from 23 vantage points across the Internet backbone to detect incidents of misconfiguration. For each incident we polled the ISP operators involved to verify whether it was a misconfiguration, and to learn the cause of the incident. We also actively probed the Internet to determine the impact of misconfiguration on connectivity. Surprisingly, we find that configuration errors are pervasive, with 200-1200 prefixes (0.2-1.0\% of the BGP table size) suffering from misconfiguration each day. Close to 3 in 4 of all new prefix advertisements were results of misconfiguration. Fortunately, the connectivity seen by end users is surprisingly robust to misconfigurations. While misconfigurations can substantially increase router processing overhead, only one in twenty five affects connectivity. While the causes of misconfiguration are diverse, we argue that most could be prevented through better router design.”
• How to run 10,000 untrusted applications on a single machine (and why) (Powerpoint Slides)
  Andrew Whitaker, Marianne Shaw, and Steve Gribble
  "A developing trend on the Internet is the migration of application functionality into third-party infrastructure; examples include web hosting centers and content distribution networks. Ideally, any user should be able to deploy an Internet service at a well-connected point in the network. However, this model has significant implications for security and scalability. Security is threatened because application code is untrusted, and may be written in arbitrary machine code. Scalability is an issue because most services fall in the "heavy tail" of the popularity curve, which defeats attempts to cache popular services in memory. The Denali project attacks these security and scalability problems head-on by using lightweight virtual machines. Denali is a virtual machine monitor (VMM), which exposes a virtualized hardware interface to a set of virtual machines. Each virtual machine contains a guest operating system, which provides conventional OS abstractions like sockets and threads. VMM's provide security because they are simpler than a conventional OS, and because each virtual machine is isolated to a private namespace. Denali achieves scalability be storing unpopular services on disk until they are referenced. In this talk, we discuss the motivation for Denali in greater depth, and present performance results from our current prototype.”

Programming Languages and Simulation: Alan Borning

• Centralia: A Domain-Specific Programming Language for Urban Simulation (Powerpoint Slides) 
  Michael Noth
  "UrbanSim is a system for constructing integrated models of urban land use, transportation, and environmental impacts. It simulates patterns of urban development under different possible scenarios over periods of twenty or more years, and is intended to support deliberation and debate on such issues as building new transit systems or freeways, or changing zoning or economic incentives, as well as on broader issues such as sustainable, livable cities, economic vitality, social equity, and environmental preservation. The Centralia language is a Java-based, domain-specific programming language designed to facilitate the creation of agent-based microsimulations in UrbanSim. It includes both generally useful extensions to Java, and also constructs specifically tailored to describing agents that interact and generate complex emergent behaviors, such as households, employers, and real estate developers.”
• ArchJava: Connecting Software Architecture to Implementation (Powerpoint Slides)
  Jonathan Aldrich, Craig Chambers, and David Notkin
  "Software architecture describes the structure of a system, enabling more effective design, program understanding, and formal analysis. However, existing approaches decouple implementation code from architecture, allowing inconsistencies, causing confusion, violating architectural properties, and inhibiting software evolution. ArchJava is an extension to Java that seamlessly unifies software architecture with implementation, ensuring that the implementation conforms to architectural constraints. A case study applying ArchJava to a circuit-design application suggests that ArchJava can express architectural structure effectively within an implementation, and that it can aid in program understanding and software evolution.”
• MultiJava: Modular Open Classes and Symmetric Multiple Dispatch for Java (Powerpoint Slides)
  Todd Millstein
  "We present MultiJava, a backward-compatible extension to Java supporting open classes and symmetric multiple dispatch. Open classes allow one to add to the set of methods that an existing class supports without editing that class or its clients, obviating the need for tedious workarounds like the "visitor" design pattern. Multimethods generalize traditional receiver-based dynamic dispatching by allowing all arguments to be uniformly dispatched upon, resolving an asymmetry that makes some common idioms difficult to program. MultiJava retains Java's class-based encapsulation properties as well as its modular typechecking and compilation schemes.”

Databases I: Alon Halevy

• Piazza: The First Peer Data Management System  
  Maya Rodrig
  "Existing peer-to-peer systems have focused on specific application domains or on providing file-system-like capabilities; these systems ignore the semantics of the information being transferred. There is a much greater potential for data and resource sharing, that can be achieved by exploiting semantic knowledge about the data. Piazza is the first Peer Data Management System (PDMS). A PDMS is a distributed, self-organizing, heterogeneous community of cooperating peers, sharing data and resources. Our goal is to enable users to share data across local or wide-area networks in an ad-hoc, highly dynamic distributed architecture. We have built the system infrastructure and are exploring efficient data distribution, lookup, indexing, and query processing techniques. The data placement algorithms attempt to distribute data across peers in such a way as to minimize the cost of satisfying the total query workload in the system, under existing storage resources and bandwidth constraints. We want to make data available when and where it is needed.”
• Propagating Updates in a Peer Data Management System (Powerpoint Slides)
  Peter Mork
  "In a peer data management system, it will often be necessary to materialize views for speed and availability. As the underlying base relations change, it is necessary to propagate these changes to the materialized views. We propose publishing both updategrams (a change to a base relation) and boosters (tuples that could join with a specific updategram) as first class objects. We present a formal algebra and use that to propose a System-R style algorithm for identifying the best synchronization plan. Our experimental results justify the utility of boosters.”
• Query Answering in Peer Databases (Powerpoint Slides) 
  Igor Tatarinov
  "In a Peer Database Management System, every machine can serve as both a client executing queries and a server providing data. PDMSs represent a natural step beyond data integration systems. The latter employ a single mediated schema and specify mappings between that schema and the data sources. In a PDBMs on the other hand, all peers are treated equally so a single mediated schema is undesirable and perhaps even impossible to build. We consider the problem of answering queries in a PDBMS where data resides in "stored" relations but queries are formulated over "peer" relations. The user may be interested in seeing _all_ results or _some_ results. In the latter, more interesting case, a query can be answered even if some peers are unavailable.”
• Indexing Data in a Peer-based Distributed System (Powerpoint Slides)
  Bart Niswonger
  "Describes the problem of indexing in a peer-based distributed system. Highlights the three main issues of a) agreeing on what is to be indexed, b) constructing an index of that (multi-dimensional) data and c) distributing that index. Finally discusses some solutions to these issues, from both existing projects and our own work.”

Session III

Ubiquitous Computing: Larry Arnstein

• The Location Stack: Designing for Location-Aware Mobile Computing (Powerpoint Slides)
  Jeffrey Hightower
  "Physical location is essential information for emerging mobile computing systems: We want to capture activities in a biological laboratory to record and reproduce experiments. We need directions. We want to interact naturally with I/O devices encountered in our environments. Yet despite the importance of location information, current systems typically treat location in their own idiosyncratic manner. Either the entire implementation (including sensing, representation, and application logic) is a monolithic hodgepodge of functionality or location data is simply simulated in order to remain focused on application research. Fortunately, the time has come to change all this -- to reduce cost and duplicated effort and enable reuse, evolution, and interoperability. In this talk I will present our seven-layer Location Stack, similar in spirit to the classic Open System Interconnect (OSI) layered model of computer networks. The location stack is a powerful engineering tool allowing location-aware computing designers to adopt a common vocabulary and standard infrastructure.”
• The PlantCare project
  Anthony LaMarca, Affiliate CSE Faculty, Intel Research Laboratories at Seattle
  "Here at the Seattle Intel Research lab we are actively exploring the next generation of autonomous smart environments. One initial experiment consists of integrating sensor networks, robots, and new software architectures to manage the health of houseplants. During this talk, I will describe our approach to the problem, the current status of the project and share our preliminary results.”
• one.world: Programming for Pervasive Computing Environments
  Eric Lemar
  "Pervasive computing provides an attractive vision for the future of computing. Computing power will be available everywhere. Mobile and stationary devices will dynamically connect and coordinate to seamlessly help people accomplish their tasks. However, for this vision to become a reality, programmers must build applications that constantly adapt to an environment in which people, devices, and services keep coming and going. This talk explores how to make the programmers' task feasible. I will discuss how to structure the necessary system level support and how programming for a highly dynamic computing environments impacts application development. I will introduce one.world, a system that we have built, and reflect on our own and other's experiences with it.”

Graphics and Vision: Zoran Popovic

• Recent SIGGRAPH Submissions
  Brett Allen, Steve Capell, Yung-Yu Chuang, Craig Kaplan, Karen Liu, Zoran Popovic, Steve Seitz, Chris Thompson, Li Zhang, and Doug Zongker
  

Databases II: Dan Suciu

• Semantic Mappings for Data Mediation (Powerpoint Slides)
  Jayant Madhavan
  "Many modern-day applications require the mediation of data from multiple disparate data sources. Each of these sources often represents similar data using different models or schemas. Identifying semantic mappings between related data entities in these different sources is an essential first step towards building such applications. This is often a tedious and costly manual process, requiring experts who understand the semantics of the domain and the data model. The Database and Machine Learning groups at UW have been investigating issues related to mapping between models in the context of data integration and data migration, and more recently in the context of peer data management and the Semantic Web. In this talk, I will focus on the challenges in this inherently difficult problem. I will provide an overview of our research efforts, which have focussed on using machine learning as a solution to build robust semi-automatic systems (LSD and Glue) for obtaining accurate semantic mappings. I will also describe our current research on providing a formal basis for representation and reasoning about mappings - a key to automated data mediation.”
• Data Integration in the Rapidly Evolving Domain of Genetics (Powerpoint Slides)
  Peter Mork
  "The GeneSeek data integration system provides a single interface to numerous online genetic databases. The contents of the underlying sources are evolving rapidly. We present two solutions for managing this complexity. First, we propose constructing a meta-wrapper, which allows us to separate syntactic and semantic translation into separate processes. Second, we propose a high-order query language (PQL), which allows users to express the ways in which relationships can be joined into paths. This facilitates the construction of queries resilient to changes in the schema.”
• Containment of XPath Expressions
  Gerome Miklau
  "XPath expressions are a simple but popular way of querying semi-structured data in XML form. The containment problem for XPath expressions has many applications. In this talk we define the containment problem, review its applications, and summarize results on the computational hardness of this problem.”
• A Scalable Algorithm for Query Minimization
  Isaac Kunen and Dan Suciu
  "Minimizing a query means finding an equivalent one with the least number of joins. Although the problem has been known for over 25 years, no scalable algorithm exists today for two reasons: queries used to be written directly by users and were already minimal, and even for conjunctive queries the problem is NP-hard. Today, many queries are automatically generated and are complex and redundant, making minimization necessary. Moreover, recent theoretical work on tree-decomposition has provided a new approach to query containment, a subproblem in query minimization. We describe a scalable query minimization algorithm that scales to conjunctive queries with hundreds of joins. The algorithm incorporates four techniques: a fast heuristic for tree-decomposition, randomization, table-pruning, and incremental recomputation. In our experimental evaluation we show that each contributes significantly to the algorithm's performance.”

Session IV

Compilers: Craig Chambers

• Composing Dataflow Analyses and Transformations  
  Sorin Lerner
  "Dataflow analyses can have mutually beneficial interactions. Previous efforts to exploit these interactions have either (1) iteratively performed each individual analysis until no further improvements are discovered or (2) developed ``super-analyses'' that manually combine conceptually separate analyses. We have devised a new approach that allows analyses to be defined independently while still enabling them to be combined automatically and profitably. Our approach avoids the loss of precision associated with iterating individual analyses and the implementation difficulties of manually writing a super-analysis. The key to our approach is a novel method of implicit communication between the individual components of a super-analysis based on graph transformations. In this presentation I define our approach, and show how it works on several examples; I briefly cover the theoretical guarantees that our framework provides; finally I present experimental results showing that in practice (1) our framework produces results at least as precise as iterating the individual analyses while compiling at least 5 times faster, and (2) our framework achieves the same precision as a manually written super-analysis while incurring a compile-time overhead of less than 20%.”
• ESP: Error Detection via Scalable Program Analysis  
  Manuvir Das, Sorin Lerner, Mark Seigle
  "The ESP project is a method for static detection of protocol errors in large C/C++ programs. ESP takes as input a set of source files and a specification of a high level protocol that the code in the source files is expected to satisfy. It uses static analysis to detect violations of the protocol in the source code. Our goal is an analysis that satisfies three properties: it identifies a superset of the possible errors in the program, it scales to very large programs, and it reports few false errors. This talk will present an overview of the architecture of ESP, the main technical contributions and experimental data for a 300,000 line program. This is joint work Manuvir Das at Microsoft Research.”
• Automatic Construction of Staged Compilers  
  Matthai Philipose
  "The ability to optimize programs while they execute has become increasingly important in recent years. The primary challenge in such optimization is to keep the run-time overhead of optimization down while maximizing its effectiveness. Naively using traditional compilation techniques at run-time results in unacceptably high run-time compilation overhead, although the quality of code produced can be very high. On the other hand, the widely used solution of Just-In-Time (JIT) compilation keeps run-time overhead low by sacrificing performance and at considerable cost to engineer the special JIT compiler. In this talk, I will present a technique called "staged compilation", which produces run-time compilers that often have much lower _run-time_ overhead than traditional compilers, yet do not sacrifice any of their functionality. These fast compilers can be produced at little additional engineering cost, given the slower traditional version of the compiler. The key to the technique is an automatic method to transfer optimization overhead to static compile time from run-time, for arbitrary optimizations. I will present the main components of the technique, and a brief evaluation of a preliminary prototype. Staged compilation can speed up pipelines of classical compiler optimizations by up to an order of magnitude, and more commonly by a factor of 4.5 to 5.”

Theory: Richard Ladner

• Practical Aspects of Competitive Auctions (PDF Slides)
  Jason Hartline
  "In this talk we discuss interesting results from profit optimizing auctions. We will pay special attention to practicality issues for the sale of digital goods (pay-per-view TV, mp3s, etc). We will review the competitive framework for worst case analysis of auctions and present several auctions that perform well in this metric. We will also present new results for auctioning content to be distributed via multicast.”
• Fast Computation of Low Rank Matrix Approximations
  Frank McSherry
  "There are many applications in which it is important to compute, for a given matrix A, a matrix of low rank that approximates it well. This problem is closely related to the problem of computing eigenvectors and eigenvalues of a matrix, and has numerous applications in engineering. We demonstrate an efficient technique based on sampling that allows us to compute low rank matrix approximations using substantially less time and space than current techniques. This improvement comes at the cost of accuracy; the approximations we derive are not optimal. However, we can bound the difference in quality between our approach and the optimal matrix, and conclude that as long as significant eigenstructure is present, our approximation is sufficient.”
• Bit Allocation and the Multiple Choice Knapsack Problem (PDF Slides)
  Alexander Mohr
  "We show that the problem of optimal bit allocation among a set of independent discrete quantizers given a budget constraint is equivalent to the multiple choice knapsack problem (MCKP). This result has three implications: first, it provides a trivial proof that the problem of optimal bit allocation is NP-hard and that its related decision problem is NP-complete; second, it unifies research into solving these problems that has to-date been done independently in the data compression community and the operations research community; third, many practical algorithms for approximating the optimal solution to MCKP can be used for bit allocation. Results for three different optimization algorithms will be given.”
• Improved Satisfiability Testing Using Ordered Clause Learning (Powerpoint Slides)
  Ashish Sabharwal
  "Satisfiability testing of propositional formulas (SAT) is one of the central NP-complete problems appearing naturally in Artificial Intelligence and other fields. Numerous variants of a simple recursive branching procedure are used to heuristically solve this problem. A major drawback of this approach lies in redoing computation that can potentially be reused. Clause learning overcomes this by recording helpful information on the way. We propose a further improvement to clause learning that utilizes the underlying structure of the input formula to produce a good branching order. This allows us to handle formulas with number of variables an order of magnitude more than the current practical limit. We also present the first theoretical relationship between clause learning and a well known proof system called resolution and show that the former is more powerful than a fairly broad subclass of the latter.”

Reconfigurable Hardware: Carl Ebeling

• Learning in silicon, from adaptive transistors to learning systems  
  David Hsu
  "What could we buid if our transistors could adapt? I will present an overview of work on learning in silicon at the University of Washington. First I will briefly describe floating-gate transistors, single transistor devices that can store and alter a non-volatile analog memory. I will then show how to build primitive learning circuits that encapsulate the behavior of prominent learning paradigms. Finally I will discuss larger silicon learning systems that we have fabricated or are in the process of designing. This is joint work with Seth Bridges, Crhis Diorio, Miguel Figueroa, and Aaron Schon.”
• Compiling for Coarse-Grained Adaptable Architectures (Powerpoint Slides)
  Carl Ebeling
  "Mobile embedded computing devices are key components in the emerging information technology infrastructure, displacing in many instances the PC as the interface to information. As the capability of these devices increases, the combined performance, power and cost demands are becoming difficult to satisfy.. To meet these demands, the platforms used to build these systems must provide much of the functionality using ASIC components instead of more flexible processors. Coarse-grained adaptable architectures, which combine the advantages of processors and ASICs, have the potential to radically change the way embedded systems platforms are built. This potential has not yet been realized, in part because programming these architectures is too much like designing hardware. This talk will present our proposed approach for compiling high-level language programs to coarse-grained adaptable architectures. This approach combines a traditional compiler frontend with a scheduler based on simultaneous place and route algorithms. We believe this formulation allows the many different constraints imposed by coarse-grained adaptable architecture to be solved effectively.”
• ACME Lab - The Totem and Precis Projects (Powerpoint Slides)
  Mark L. Chang
  "We will present two major current research projects in the ACME Lab,headed by Professor Scott Hauck: The Totem Project and the Precis Project. - Totem Project -
  We are investigating the impact of modifying the structure of an FPGA to support a class or a specific set of algorithms, while still providing flexibility within that set. By generating a custom array for a given computation domain, we explore the design space between an ASIC and an FPGA. However, the manual creation of these customized reprogrammable architectures would be a labor-intensive process, leading to high design costs. Therefore, The Totem Project's focus is to provide automatic generation of domain-specialized reconfigurable architectures. - Precis -
  We present a design-time tool, Précis, which assists the developer in analyzing the precision requirements of algorithms specified in MATLAB. Through the combined use of simulation, user input, and program analysis, we demonstrate a methodology for precision analysis that can aid the developer in focusing their manual precision optimization efforts.”