Gaetano Borriello - US grants

Research consists of two major parts. The first seeks to develop more tools that handle chip-interface design, based on the timing diagram methodology, covering all steps through testing and documentation. The second part seeks to develop tools that give system designers a spreadsheet-like way of evaluating architectural and system-timing decisions at the level of data- path diagrams.

A chaotic router is a non-minimal, adaptive message router that uses randomization in routing and derouting decisions. The use of randomization simplifies the router sufficiently that it's conjectured chaotic routing can be competitive with oblivious routing, achieving equivalent or better average-case performance, greatly improved worst-case performance and fault tolerance. Though the principles of chaotic routing apply to some degree to any topology with multiple paths between nodes, chaotic routers for binary n-cubes are presently under investigation. The goal of the research is to establish a compelling case for constructing an experimental version of a hypercube chaotic router. Towards that end a series of studies are presently underway. 1. The idealized router of the proposal is being converted to practical engineering designs; the details of the chaotic routing logic are being specified. Alternatives include sequential and parallel channel match algorithms, a virtual cut-through alternative to the store-and- forward of the proposal, various alternates for asynchronous channels, various queue sizes, etc. 2. A detailed simulator (with a granularity of approximately a half-dozen gate delays) has been created. Experiments are being run on a 256 node hypercube to compare the different chaotic router designs with various alternative routers, such as oblivious and priority routers. 3. Simulations are being run to analyze the effect of multiqueue size on the latency and throughput of the network. The role of message length on latency and throughput is also being analyzed. 4. Probabilistic analysis, completed last summer, shows that an idealized hypercube chaotic router is deterministically deadlock free and probabilistically livelock and starvation free. The new engineering designs are being abstracted and analyzed to assure that they are consistent with the idealized model of this theory. 5. The first version of a custom CMOS channel design is back from fabrication and is being tested. 6. Alternate implementation strategies, besides custom CMOS, are being investigated. 7. The generality of the chaotic routing principles are being analyzed in the context of different topologies. In particular, various forms of the mesh topology are being studied as alternates. 8. The role of clocked and self-timed logic in chaotic routing is being analyzed in light of the fact theoretical foundations are independent of the timing policy.

Three CAD design tools, produced in research projects at the University of Washington, are being developed and enhanced so as to bring them into a state for distribution to general users. These tools are: (1) MacTester, an interactive testing and debugging environment built around the Mackintosh computer; (2) WireC, a mixed graphical and procedural language for describing hardware systems; and (3) Gemini, a VLSI layout verification program that compares the circuit specification with the circuit layout. This grant is made under the Software Capitalization Program.

This is a conference that draws together researchers from both universities and industry across a wide range of disciplines. The emphasis of the conference is the design of systems taking into account chip design, packaging, and interconnection issues. By holding one session track instead of parallel sessions, the organizers emphasize the importance of a firm grasp of all of these issues for the modern system designer.

This project (named Chinook) seeks to develop appropriate abstractions for embedded system development, design, implementation, and validation that will enhance retargetability and shorten the design cycle. The abstractions will be provide leverage in automatically synthesizing the most labor intensive and error-prone elements of embedded software that lead to the great majority of errors and hamper design space exploration. The project is vertically integrated, that is, a range of tools and methods to support high-level specification, simulation, communication synthesis, operating system customization and optimization, and debugging and verification. Specific activities include: (1) development of a composition methodology for control-dominated systems, (2) communication and synchronization code synthesis including buffering and protocol specialization, and (3) debugging, verification, and visualization tools for embedded system design.

This CRCD project supports the development at the University of Washington of an exportable package for the capstone design course emphasizing computing appliences, creates two new undergraduate courses on embedded systems programming, creates a new graduate course on the elements of computing appliances, and brings the results of research in embedded system design and design automation as well as internetworking protocols to the undergraduate curriculum. The exportable package for the capstone course consists of course modules and web-based materials that can be augmented and updated by the community and used to rapidly set up new project courses, labs, and individual senior projects. The two courses on embedded systems programming include material on device drivers, real-time programming and operating systems, component-based programming models and also material in the area of wireless networking. Overall, the project is planned to modernize the computer engineering curriculum by focusing on a class of devices, services, and applications that are expected soon to be center-pieces of the consumer electronics and computing industries.

This workshop is to explore and assess the state-of-the art in electronic system design, and identify the research needed by this field in light of exponentially growing complexity and functionality. Topics covered include CAD tools; hardware-software co-design; architecture simulation (functional and behavioral); verification of functionality, timing, and communication protocols; optimizing compilers; and operating systems. Additionally, the idea of fostering design methodologies that encourage reuse of components
not only at the physical or logic design levels but also at the functional levels will be explored. The workshop report includes: (1) a statement of the most pressing problems to solve within the next decade, (2)
recommendations regarding the style and kind of research to be conducted and suggestions to the community as to how to implement these recommendations.

The objective of Labscape is to enable individual lab workers to contribute to a fine-grained formal representation of ongoing lab activities i.e., to build the database by doing the work, without having to stop and write things down in a notebook or to enter information into a computer. By eliminating the redundancy of doing the work and then recording it, accuracy and completeness will be improved. And, by capturing information at a finer detail than possible for manual entry systems, varied and novel applications can be supported. This research supports the development of both an effective scientific working environment and an effective scientific learning environment but supporting better artifacts arising from the work or learning.. There are two primary research thrusts of this proposal. The first is the highly domain specific question of how and what data should be captured in the physical context of performing an experiment -- this is both a data representation and a human-computer interaction problem. The required domain expertise is derived from close cooperation with the University of Washington's Cell Systems Initiative (CSI) and its corporate and academic affiliates. The second question is how to obtain good system properties in distributed laboratory environments characterized by high degrees of device and personal mobility. For this application, security, reliability, and functional extensibility are some of the most important properties. These issues will be investigated in concert with UW's Portolano program whose objective is to develop general device, networking, middleware, and programming technologies for ubiquitous computing applications.

ABSTRACT

Proposal: CNS 0454394
PI: Kaplan, David L.
CoPIs: Gaetano Borriello, Christopher J. Diorio, Edward D. Lazowska
Institution: University of Washington
Title: CRI: RFID Ecosystem
Program: NSF 04-588 CISE Computing Research Infrastructure


This project will explore applications for RFID tags in homes and workplaces rather than previously studied applications for product supply-chains. Applications relevant to the workplace and home will be explored that will integrate RFID capabilities with other ubiquitous computing technologies. Systems issues to be explored include: innovative RFID tags with additional sensing, middleware and operating-system support for sensing/actuation events, database organization based on distributed data on servers and tags, mining of sensing/actuation events to infer users activities, and ubiquitous computing applications for the workplace. These technologies have deep privacy, legal, social, and policy implications. The project will incorporate researchers in both technology and social aspects of technology. Broader impacts of this project include potential applications, and use in education and design projects at the University of Washington.

There is a need for middleware that blends personal and ambient sensor systems. The objective is for applications, running on a user's personal/wearable devices, to take advantage of the enhanced sensing capabilities of sensor networks installed in the environments that people typically move through. This cooperative sensing has the ability to greatly enhance personal systems while allowing users to retain control of privacy-sensitive information. Moreover, cooperation can enhance the computational capabilities and lessen the power requirements of applications by asking the ambient systems to do more of the work of elaborating the sensor data. This work is guided by practical applications and the concepts will be validated using personal health sensing and measurement as the initial application area. For example, the motivating application is a personal activity measurement system that not only measures a person's activities and level of exertion from measuring forces on their body but can also interface to equipment in a fitness center and gain further data from setting and sensors (e.g., heart rate monitors) on exercise equipment. The software artifacts will be middleware to make building these kinds of new applications more efficient and the applications themselves more robust to the availability of sensing and computational resources. The scientific results will be techniques to correlate sensing systems as well as methods for coordinating computations in a highly dynamic environment where users come and go. The middleware will be exercised in product-design courses at the University of Washington where students will build and evaluate hybrid wearable and ambient sensors systems.

Programmers usually modify a program intending to fix a bug or to add a new feature. While they often have a strong understanding of the actual changes they are making to a program, the dynamic effects of these changes on the run-time behavior of the program can be harder to comprehend. The approach helps developers identify when their changes to the source code and the changes in the consequent executable behavior are inconsistent: that is, the change in the source is not apparent in the behavior, or vice versa.

The approach identifies specific program elements and dependencies that likely account for the inconsistent nature of the change. Using a static and a dynamic dependence graph from each of two program versions, the dependences are partitioned according to their presence or absence in each of the four graphs. Particular partitions contain dependencies that are likely to represent inconsistent parts of a change; these partitions provide insight into the change that would be otherwise difficult to obtain.
The partitions allow distinctions to be made that cannot be made using the static dependence graphs alone, the dynamic dependence graphs alone, nor using a static and dynamic graph pair from a given version; much of the power of the approach arises because the cross-version variations in the dependence graphs are small, reducing information provided to the programmer. The intellectual merit includes empirical assessment over a broad set of programs and changes, ?value propositions? for using this information, applications of the approach, and use of the partitioning to augment conventional approaches to assessing software complexity.

The project addresses two categories of broader impacts: the people directly involved in the research, and the potential for the research to positively affect society through increased programmer productivity.

Innovation in public health is often bottom up: new processes and technologies are often identified by grassroots and non-governmental organizations and deployed locally before achieving broader use. Mobile technologies have a vast potential to strengthen health systems for under-served populations, but innovation is hindered by the difficulty and expertise required to create robust and deployable solutions. This work seeks to change this state of affairs by providing a set of tools based on commonly available mobile devices that will permit these organizations to easily deploy new health services, supervise their delivery, improve logistics, evaluate their programs' effectiveness, and disseminate their learning and tools to others around the world. The approach is based on cost-realism, namely, the appropriate mix of technology elements to tackle a problem based on a realistic assessment of the solution's sustainability in the community where it will be deployed. Thus, the focus is on using a mix of communication devices that are already likely to be in the possession of a large percentage of the target population such as mobile phones. There will also be experimentation with adding new sensor devices to mobile phones for physiological measurements. This collaborative work includes PATH, an organization uniquely suited to realizing scalable technology solutions in the public health space.

The goal of the research is to understand how mobile and cloud software can be constructed to make it easier to deploy modular applications that take advantage of components designed by a large community rather than a monolithic solution that is difficult to extend. In this way, a flourishing ecosystem will be created, much like application markets today, with the added capability of composing modules into larger systems. Evaluation will include both the use of the tools in a public health context as well as the ease with which new information services and systems are built and deployed. Given the wide range of potential applications students will be recruited from a wide variety of disciplines including the University of Washington Medical School, School of Public Health, and Information School and inter-disciplinary projects will be introduced into undergraduate capstone courses.

As the work is multi-disciplinary, research results will be as well. The focus is on human-computer interaction, mobile systems, communication, and software engineering. The primary technical challenges are in management of mobile data collection, expanding the sensing/perception capabilities of mobile phones for health, and architecting distributed information services. Improved methods for organizing data collection campaigns and their sustainable management in terms of both the deployment of instruments on mobile devices and tools to supervise the data collectors themselves will be foremost. Connecting mobile phones and their sensors in a structured arrangement that will allow use of everything from paper and cheap voice/SMS phones on one end of the spectrum to smartphones and tablets on the other will be a significant contribution to data collection methods. Exploiting standard interfaces and internet protocols between cloud-based modules will formalize the development of data architectures (above basic databases) that embody work processes and sustain management feedback loops.