Computer Science Division
University of California, Berkeley
Technical Progress Report (08/01/98 - 07/31/99)
The key enabling technology for the project was the emergence of scalable,
low-latency, high-bandwidth VLSI switches, pioneered in massively parallel
processors and transferred into system area network (SAN) configurations.
With SAN technology, it became
feasible to construct powerful, integrated systems by literally plugging together many state-of-the-art commercial workstations or PCs to form a
high-performance cluster. However, to realize the potential of SAN-based cluster design, critical limitations of existing systems had to be overcome.
Particularly, the costly communication stack forming the software interface between the user application and the network had to be essentially
eliminated, while preserving the ability to share communication resources effectively. In addition, the operating system functionality associated with an
individual node had to be made available cluster-wide. Overcoming these challenges enabled many novel design concepts, such as file and virtual
memory systems that utilize remote memories in preference over disks, schedulers that coordinate actions implicitly, massively scalable I/O, and
scalable active services.
The project demonstrated the design approach, the solution to core challenges,
and novel design opportunities by building and utilizing a cluster of over
one hundred Ultrasparc workstations interconnected by a multigigabyte Myricom
network. This prototype cluster enabled
many further investigations; it was basis for Inktomi (now the world's largest search engine), set the world records for throughput and response time on
the disk-to-disk database sort benchmark and held them for two years, broke the RSA key challenge, put clusters on the Linpack Top-500 list, hosted
the transcodng proxy service (BARWAN Transcend) and the media gateway service (MASH), provided the simulation engine for
processor-in-memory (IRAM) and configurable architectures (BRASS), enabled real-time video effects processing and allowed massive image
processing in digital libraries. Technology from the project has transferred to industry in many forms, including the recent Intel/Microsoft/Compaq
Virtual Interface Architecture (VIA).
The first major application breakthrough on Titan/NOW was Inktomi, which
debuted on a segment of the NOW cluster in summer 1995 as the first search
engine to offer fast response time and a large search set. It utilized the capacity and parallel transfer of cluster I/O to support a very large database,
while using the fast communication layer to fully parallelize each query for fast response. The approach and the underlying communication technology
transferred to the company, which powers many of the world's leading search sites, including HotBot, NBC's Snap!, Yahoo! and the Disney Internet
Guide (DIG) for children and families. Additional advances came through the development of active infrastructure services, in collaboration with the
MASH and BARWAN projects, which place services into the infrastructure that adapt content and access to the needs of a large number of potentially
limited clients. For example, the Transcend proxy provides not only caching, but actively renders pages and reprocesses images into a form where they
can be transferred quickly over a low-speed link and presented on a small Palm Pilot. The Media Gateway participates in an mbone session while
transcoding the video stream to match the limited connection of its client. Each of these reside permanently in a portion of NOW, but grow out to utilize
cluster resources as demand increases. In addition, NOW has been made available to the national computation science and computer science
community as an experimental resource with the National Partnership for Advanced Computing Infrastructure (NPACI).
A rich set of demanding applications are now heavily using the infrastructure and stressing the system as forecasted in the proposal. For example, the vision group has recently produced techniques for photorealistic rendering. They routinely run on as many as a hundred nodes, because they need fast turn-around around in the rendering process to determine how to adjust scene, lighting, etc. to reveal the impact of their techniques. They also routinely consume thousands of node hours to produce movies once these decisions are made. There is a great deal of machinery involved in the state management for this sort of application. This problem, and that of integrating the two modes of use with interactive parallel scientific use, and the systems experiments, presents a family of challenges of the kind that we hoped would arise from the proposed cycle of innovation. Several important technological components have been developed within the project, such as self-scheduled parallel IO system, called River, and the ability to run IP traffic within a virtual network over Myrinet active messages.
The multimedia component of the project has been strongly influenced by advances in multicast communication, which is still in transition and needs to be explored further to fully complete the proposed work. One of the exciting driving applications is real-time software video effects. Often multicast is used for delivering multimedia content, and with the arrival of Steven McCanne on the faculty mid way through the Titan project, this became an important aspect of the multimedia work. An unexpected result was that extensions of the multicast session management techniques would be instrumental in managing parallel, real time video effects processing within the TITAN/NOW infrastructure. However, multicast is still in transition as the commercial world shifts from DVMRP to PIM and as new protocols and transports are developed internally. We are continuing to work closely with NorTel networks in upgrading the IP network in Titan to better support multicast for the multimedia component driving the core Titan infrastructure.
We have replaced the ATM cloud and 10 Mb/s external network of NOW with a switch gigabit core and 100 Mb/s links to the NOW nodes.
[MaCu99] Design Challenges of Virtual Networks: Fast, General-Purpose
SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP) , Atlanta, Georgia, May 4-6, 1999.
Alan M. Mainwaring and David E. Culler.
We have conducted an extensive performance evaluation study of the sensitivity
to commmunication performance of a range of workloads on NOW by building
an in situ measurement facility for conventional distributed applications
and by integrating the measurement capability into our communication layers.
Extending the tools we developed to isolate the performance factors, including
instruction breakdowns, scaling of computational work, MPI send, receive,
and wait time, and cache traces for parallel applications, we conducted
extensive studies of the sensitivity of traditional distributed system
workloads to network latency, overhead and bandwidth. While the sensitivity
is quite different from parallel programs, overhead remains the dominant
factor [MaCu99, Mar99].
[MaCu99] NFS Sensitivity to High Performance Networks,
SIGMETRICS'99, Atlanta, May 1999
Richard Martin and David Culler
[Mar99] Application Sensitivity to Network Performance
PhD Thesis, U.C. Berkeley, 1999
Richard P. Martin
We have studied in detail how to minimize the latency of a message through a network that consists of a number of store-and-forward stages, especially for the page size chunks transported within cluster files systems. This research is especially important for today's low overhead communication subsystems that employ dedicated processing elements for protocol processing. We have developed an abstract pipeline model that reveals a crucial performance tradeoff. We exploit this tradeoff in fragmentation algorithms designed to minimize message latency. By applying a rather formal methodology to the Myrinet-GAM system, we have improved its latency by up to 51% [Wan*98]
[Wan98] Modeling and Optimizing Pipeline Latency.
1998 SIGMETRICS Conference on the Measurement and Modeling of Computer Systems , Madison, Wisconsin , 6/24/98 - 6/26/98 .
Randolph Y. Wang, Arvind Krishnamurthy, Richard P. Martin, Thomas E. Anderson, David E. Culler.
We demonstrated a global layer operating system, Glunix, that scales beyond 100 workstations connected by low latency custom network interfaces
via a high bandwidth switch. It provides a parallel network process abstraction and it able to run both parallel programs and unmodified sequential
programs. This was a cornerstone in all research conducted on NOW and has executed many million jobs. A heartbeat monitor and automatic restart
facility, GluGuard, was developed to maintain the collection of Glunix components across failures and incremental reconfigurations. The development
of Glunix revealed several fundamental limitations in the classic Unix interface that compromise perfect virtualization. We developed a sophisticated
interpositioning stategy to overcome these difficulties. Detail is provided in the [Gho98, Gho*98]
[Gho98] User Level Operating System Services,
PhD Thesis, U.C. Berkeley, 1998
Douglas P. Ghormley
[Gho*98] GLUnix: A Global Layer Unix for a Network
Software-Practice and Experience, Vol. 28, No. 9, July 25. 1998 .
Douglas P. Ghormley, David Petrou, Steven H. Rodrigues, Amin M. Vahdat, Thomas E. Anderson.
One of the critical issues revealed in our technology evaluation phase
was coordinated scheduling of parallel programs. Most programs are
the assumption that the consituent processes actually run at the same time. Local operating system schedulers do not obey this discipline, and the lack
of coscheduling can result in slowdowns of one or even two orders of magnitude relative to dedicated user. Although Glunix provided an explicit gang
scheduling capability, that solution was unsatifactory for several reasons. We wanted to be able to mix sequential and parallel jobs and allow
interactive use. Gang scheduling is inefficient in presence of load imbalance or when consituent processes are operating independently. Its
implementation is complex and introduces another set of potential failures and performance bottlenecks. The deep question was whether it was
possible to design mechanisms where parallel programs could get themselves coscheduled over local schedulers when they require it - using only the
communication inherent to the program. We developed an elegant and simple adpative technique, where the communication runtime observes how
long it waits for responses and reacts by either continuing to wait or by blocking. A complete development and evaluation of the effectiveness of this
approach over a wide range of applications and scenarios is provided by [Arp*98, Arp98]
[Arp*98] Scheduling with Implicit Information in Distributed Systems.
1998 SIGMETRICS Conference on the Measurement and Modeling of Computer Systems , pages 233-243 , Madison , Wisconsin , June
24-26, 1998 .
Andrea C. Arpaci-Dusseau, David E. Culler, Alan Mainwaring.
[Arp98] Implicit Coscheduling: Coordinated Scheduling with Implicit Information in Distributed Systems
Ph.D. Dissertation, University of California, Berkeley, December 1998.
Andrea C. Arpaci-Dusseau
An fundamental strength of cluster architectures proved to be the ability
to drive massive I/O bandwidth across a large number of independently
attached disks. To explore this capability, we built a very high-performance parallel I/O facility and used it to set (and hold for two years) the world
record disk-to-disk sorting benchmark (both the response oriented Datamation benchmark and the bandwidth oriented Minute Sort). Detail is in the
[Arp*98b] Searching for the Sorting Record: Experiences in Tuning NOW-Sort.
The 1998 Symposium on Parallel and Distributed Tools (SPDT '98) , Welches, Oregon , August 3-4, 1998 .
Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson.
This investigation revealed that disks are a fundamental source of performance
variation, due to mechanical characteristics, variations is transfer rates,
and numerous other factors, which has largely been overlooked. Thus, we investigated the fundamental question of designing parallel I/O systems with
robust performance and developed a novel, adaptive scheme where applications are constructed as a composition of flows and computation is
scheduled based on availability of data. This dataflow scheme generalizes techniques employed within DBMS systems. Replication provides a means
of obtaining 'performance availability', not just functional availability. Detail is provided in the following.
[Arp*99] Cluster I/O with River: Making the Fast Case Common.
Remzi H. Arpaci-Dusseau, Eric Anderson, Noah Treuhaft,
David E. Culler, Joseph M. Hellerstein, David A. Patterson, Katherine Yelick.
[Kee*98] A Case for Intelligent Disks (IDISKs). Kimberly K. Keeton, David A. Patterson and Joe Hellerstein. SIGMOD Record, Vol. 27, No. 3, August 1998.
One major dimension of this study was the basic node granularity and
the design issues of multiple processors per node. We constructed
an cluster of
four 8-processor Enterprise 5000 SMPS, each with multiple network interfaces. Upon this system, we extended our Active Message system to utilize
multiple network interfaces simultaneously and developed a multiprotocol version of Active Messages that transparently utilized shared memory within a
node and the fast network between nodes. The hardware configuration was carefully chosen to permit a very controlled comparison of cluster and
[Lum98] Design and Evaluation of Multi-Protocol Communication
on a Cluster of SMP's,
PhD thesis, University of California at Berkeley, November 1998.
Steven S. Lumetta.
A very large number of demanding applications were developed and evaluating on NOW, spanning a rich spectrum of areas from architectural
simulation, machine learning, protocol verification, dynamic solids modeling, numerical linear algebra, adaptive mesh refinement, finite element modeling,
maximum liklihood genetics, parallel rendering, improcessing, compression, real-time video effects, content distillation, latent semantic indexing, and
several others. However, the massive impact was realized in the form of scalable internet services, which exploiting the availability, I/O capacity and
bandwidth, and fast communication of the cluster. The most dramatic of these was the Inktomi search engine, originally prototyped on NOW and
rapidly transitioned into industry. Today the Inktomi clusters serve roughly 50% of the searches on the web, servicing 20 million distinct users through
numerous popular search interfaces and portals. It is still running a version of Active Messages derived directly from the Technology Exporation phase
of the NOW project. Detail of the design is given in the following.
Delivering High Availability for Inktomi Search
Eric A. Brewer
SIGMOD Record ACM Special Interest Group on Management of Data, vol 27. no 2, 1998
We investigated the larger research question of extending core aspects
of cluster technology out to the wide area. One of the key discoveries
use of moving funtionality traditionally associated with 'front-end' machines, such as load-balancing and fail-over, automatically into the client. A
second was the extension of the cache consistent network file system and OS interpositioning for service replication to remote clusters. Detail is in the
[Vah*98] "WebOS: Operating System Services For Wide Area Applications", Amin Vahdat, Tom Anderson, Mike Dahlin, Eshwar
Belani, David Culler, Paul Eastham, and Chad Yoshikawa. Seventh Symposium on High Performance Distributed
Computing July 1998.
[Vah98] "Operating System Services for Wide-Area
Applications,'' Amin Vahdat. PhD Dissertation, Department of Computer
Science, University of California, Berkeley, December 1998
A second fundamental area of development was the use of scalable transcoding
services in the cluster to support constrained, poorly connected, or
mobile devices. This investigation was done jointly with two other DARPA projects. The first prototype was the Transcend proxy, developed as part
of the BARWAN project, to provide on-the-fly content distillation to deliver content to small clients over bandwidth constrained links.
[Fox98] Experience with TopGun Wingman: A Proxy-Based
Web Browser for the 3Com PalmPilot
A. Fox, I. Goldberg, S. Gribble, D. C. Lee, A. Polito, and E. A. Brewer
Proceedings of Middleware '98, Lake District, England, September 1998.
The second was the Media Gateway proxy developed as part of the MASH
project. In this case, the proxy participates as a well-connected
part of a
multicast-based video session, but it down samples the multimedia stream to match the limited bandwidth and functionality of a client, which may not
even be able to participate in multicast.
[Ami98] An Active Service Framework and its
Application to Real-time Multimedia Transcoding.
Elan Amir, Steven McCanne, and Randy Katz.
Proceedings of ACM SIGCOMM '98, Vancouver, British Columbia, September 1998.
For both of these services, a portion of the NOW cluster was set aside
for baseline capability and has the load increased the proxy service would
negotiate with the Glunix layer to obtain additional transient resources.
The general facilities include a multimedia authoring laboratory, studio
classrooms, and infrastructure to support the use of digital video in distributed
collaboration and distance learning which is part of the Berkeley Internet
Broadcasting System. These facilities are briefly described and specific
projects completed in the past year are highlighted.
Multimedia Authoring Laboratory (514 Soda Hall)
The multimedia authoring laboratory includes equipment for capturing and editing images, audio, and video media. The laboratory also has media compression facilities (e.g., JPEG, MPEG, etc.) and a variety of peripherals (e.g., CD-ROM burners, color printers, removable media devices, etc.). The laboratory is used to produce videotape demonstrations of various research projects (e.g., "The Campanile Movie," "Landay CSCW Video Clips," etc.) and on-line multimedia titles (e.g., "The ACM SIGCHI Video Gallery," "Conversations with History," "California Sheet Music Project," "BMRC Retreats," etc.).
A studio classroom has audio/video equipment that supports distance
learning and distributed collaboration. This classroom is used to
produce the weekly Berkeley Multimedia, Interfaces, and Graphics (MIG)
Seminar that is broadcast world-wide on the Internet Mbone. Beginning in
the fall 1998 semester, selected other classes have been broadcast live
to the Berkeley campus and recorded for on-demand replay as part of the
Berkeley Internet Broadcasting System described below.
A significant upgrade to the classroom was completed during the past year. Some of the changes made were:
1. Sound proofing the room for improved audio.
2. Installation of permanently mounted microphones in the ceiling for audience questions.
3. Installations of a VCR and ELMO Camera Stand at the speaker position and a scan converter for the presentation computer to simplify speaker operation and improve capture of presentation material for remote participants.
4. Installation of computer-controlled cameras for the speaker and the audience.
5. Installation of an audio mixer.
6. Installations of two capture machines so remote participants can view two video streams from the room (e.g., speaker and presentation material or audience and speaker).
7. Installation of improved lighting of the speaker to improve the visual images.
8. Installation of a point-to-point audio/video link to the broadcast center in 530 Soda Hall. This link allows us to produce a third audio/video stream from the classroom or to simulcast the program using a different technology (e.g., Real Networks).
These infrastructure improvements have improved: 1) the quality of the captured audio and video, 2) the quality of the programs produced from the room, and 3) reduced the labor and effort required to produce a program. We continue to improve the classroom as we discover new problems and opportunities. Currently we are working on the quality of captured audio, support for remote operation of all equipment, and improved interactivity for remote participants.
The weekly Berkeley MIG Seminar broadcast has been produced for more
than four years. This seminar has been extremely successful both as a production
and as a vehicle for research. We use both Internet Mbone and Real
Networks technology to broadcast the seminars. A typical broadcast is composed
of three simulcast sessions.
1. A low bit-rate Mbone broadcast (200 Kbs aggregate bandwidth) that is transmitted on the public Mbone.
2. A medium bit-rate Mbone broadcast (1 Mbs aggregate bandwidth) that is transmitted on the vBNS and Calren2 experimental networks.
3. A Real Networks broadcast composed of a 50 Kbs and a 250 Kbs stream that is transmitted over the Internet.
Several research projects are described below that relate to the software needed to produce and manage these broadcasts. We have continued to improve the campus infrastructure for producing on-demand and live streaming video programs. During the past year we have installed machines, called video gateways, at different locations on campus. We installed one video gateway in the Office of Media Services (OMS), which is the campus audio/video support organization, which allows us to produce programs from approximately 20 other rooms on campus. We also installed a video gateway connected to a satellite dish so we can capture live material as a source for video processing and compression algorithm development.
During the next year we plan to install more video gateways in OMS and classrooms so we can increase the number of concurrent broadcasts and satisfy the demand by other researchers for distributed collaboration experiments. In addition, we will continue to enhance the equipment in 405 Soda Hall.
Many research accomplishments relate to development of the Berkeley Internet Broadcasting System (BIBS). The goal of this system is to support live and on-demand interactive television using streaming audio/video on the Internet. Distance learning is the primary application. To make this system practical, we must reduce the cost and effort required to produce a broadcast and to improve the quality of the broadcasts (i.e., audio/video media and interactivity). The remainder of this section describes research in four areas: broadcast production, parallel video processing, layered multicast, and end-user digital video editing.
The key to reducing cost is to incorporate software automation. For example, the Berkeley MIG Seminar requires ten processes to be started on seven different machines. These processes are configured to work together by setting parameters to the different programs. For example, the rtpgw process that transcodes the medium bit-rate video stream produced by the machine in the classroom to a low bit-rate video stream that will be broadcast to the Public Mbone must be configured with the appropriate session addresses and coding parameters. Starting the broadcast required 30-45 minutes and was error prone because the broadcast engineer made mistakes starting the processes and entering the parameters. The broadcast engineer was typically a graduate student with at least one month of training.
We developed a tool, called the Broadcast Manager (bmgr), which stores broadcast configurations in a file and provides a GUI interface for starting and monitoring programs and entering and editing broadcast configurations [Wu99]. After deploying bmgr, we are able to start the broadcast in less than five minutes with essentially no errors. We now use undergraduates with approximately thirty minutes of training as broadcast engineers. This automation tool was so successful we were able to broadcast six additional classes in the fall 1998 semester with essentially no error due to configuration errors.
Another tool we started to develop is a Director's Console (dc) which
allows the broadcast engineer to control all audio/video equipment in the
studio classroom. For example, the broadcast engineer can switch
audio/video streams to the different capture machines, adjust the bit-rates
allocated to the different streams, and move the cameras (e.g., pan and
tilt). A typical broadcast is composed of two streams: the speaker and
the presentation material. During a lecture the speaker might use a presentation
PC to show slides or demonstrate programs, an ELMO camera stand to show
transparencies, or a VCR to play a videotape. Using dc, the appropriate
stream can be switched into the broadcast and the bit-rate allocated to
the stream adjusted. For example, we typically allocate 100 Kbs to the
speaker video, 64 Kbs to the speaker audio, and 35 Kbs to the presentation
material for the Public Mbone broadcast which must be less than 200 Kbs
for the session. But, when the speaker switches to the VCR or plays an
animation or video on the PC, we reduce the bit-rate allocated to the speaker
and raise the bit-rate allocated to the presentation material because that
stream is more important. Another example of using dc is to change the
broadcast when a person asks a questions, that is, switch the presentation
stream to the audience camera and move the camera to the left or right
side of the room depending on where the person is seated.
The current dc tool is a manual interface. In other words, it mechanizes existing control interfaces. We are working on improvements that will automate the decisions made by a human operator. For example, the bit-rate allocation mentioned above can be automated by recognizing when the speaker switches the projected presentation material from one source to another and by dynamically adjusting the allocations using the SCUBA protocol [Amir97]. Other examples of automation are recognizing an audience question from the speaker microphones, switching the video streams and pointing the camera using sound location on the three audience microphones.
Another example is accepting a question from a remote participant. The changes required for this even include: 1) turn-off room microphones to reduce feedback, 2) switch the remote audio to the speakers in the room and adjust the sound levels, and 3) switch the remote speaker video stream, if available, to the projection screen. We also plan to use the video effects processor discussed in the next section to add a title to the person asking the remote question.
Lastly, we anticipate that this automation system should include local preference setting by remote participants.
Parallel Video Processing
Another technique to improve visual quality is to incorporate special
effects (e.g., composition, titling, chromakey, etc.). Given the dramatic
improvement of off-the-shelf processors, we decided to develop a software-only
video effects system using network-of-workstations (NOW) technology. The
system is now in its second year of development and continues to be a research
vehicle for multimedia issues. During the past year we published papers
describing a user-interface and model for software-only video effects [Wong
98], the use of temporal parallelism [Meyer-Patel98], and the use of spatial
parallelism [Mayer-Patel99a]. Mechanisms to support functional, temporal,
and spatial parallelism have been implemented and demonstrated on several
video effects (e.g., titling and fades).
We have also designed and developed control mechanisms for the system that use IP-Multicast and submitted a paper describing these mechanisms [Meyer-Patel99b]. The system was demonstrated as part of the Berkeley MIG Seminar in February 1999 when video effects were generated in real-time and incorporated into the seminar broadcast. All experiments and measurements have been conducted using the Sparc NOW acquired with Titan funds. In addition, we use Intel-donated PC's as part of our development environment.
We are continuing to develop video effects for the system and mechanisms to incorporate the system into dc so it can be used on a regular basis. We are also exploring the development of an effect scripting language which will reduce the coding required to specify video effects and the possibility of distributed effects processing to other nodes on the Internet with customization by end-users.
Directory Services for Layered Multicast Sessions
The long-term vision for Internet streaming video includes the use of
source-channel and layered coding to delivery the best quality possibility
to every end station given the bandwidth and latency constraints of the
network connection. For example, a participant connected to a high-speed
wireline network should get a better image than someone connected by a
wireless network. Rather than simulcasting several different streams, as
we now do, we want to incorporate layered multicasting in which different
layers are transmitted on different multicast addresses [McCanne96]. One
problem with this technology is selecting session addresses and distributing
them to participants. An example will illustrate the problem. Suppose several
people at Berkeley are communicating with several people at another university.
Suppose further that the connection between the two universities is a slow
link. The system ought to allocate a base layer that will be shared by
all participants and enhancement layers that are available only to participants
on each campus. But, given that multicast addresses are allocated by administrative
scopes, the addresses allocated for the enhancement layers at Berkeley
will be different than the addresses allocated at the other university.
The current IETF protocols and software tools for Mbone session announcements
(i.e., SAP and sdr) do not support layered multicast addressing. A solution
to this problem, including caching of announcements, was designed and implemented
during the past year, and a paper describing the system was published [Swan
98]. The paper won the Best Student Paper Award at ACM Multimedia '98.
This work used computer systems and networking facilities acquired with Titan funds.
End-User Direct Manipulation Non-Linear Editor
Digital audio and video are not ubiquitous. Easy-to-use tools that will
run on any desktop are not available. One aspect of the problem is that
conventional non-linear editing systems use a complicated, but very functional,
user interface. During this past year we developed an end-user direct manipulation
interface for a non-linear audio/video editor. The idea was to simplify
the user interface by constraining the functions available. A prototype
system was implemented, and a paper has been submitted for publication
that describes the system [Steele98].
This work used computer systems acquired with Titan funds.
[Amir97] E. Amir, S. McCanne, and R. Katz. "Receiver-driven Bandwidth
Adaptation for Light-weight Sessions," Proceedings of ACM Multimedia '97,
Seattle, WA, Nov 1997
[Mayer-Patel97] K. Mayer-Patel and L.A. Rowe, "Design and Performance of the Berkeley Continuous Media Toolkit," in Multimedia Computing and Networking 1997, Proc. IS&T/SPIE Symposium on Electronic Imaging: Science & Technology, pp 194-206 San Jose CA, Jan 1997.
[Mayer-Patel98] K. Mayer-Patel and L.A. Rowe, "Exploiting Temporal Parallelism for Software-only Video Effects Processing," Proc. ACM Multimedia 98, Bristol UK, Sep 1998.
[Mayer-Patel99] K. Mayer-Patel and L.A. Rowe, "Exploiting Spatial Parallelism for Software-only Video Effects Processing," Multimedia Computing and Networking 1999, Proc. IS&T/SPIE Symposium on Electronic Imaging: Science & Technology, pp.252-263, San Jose CA, Jan 1999.
[McCanne96] S. McCanne, V. Jacobson, and M. Vetterli, "Receiver-driven Layered Multicast," Proc. ACM SIGCOMM 96, Stanford CA, Aug 1996, pp. 117-130.
[Steele99] M. Steele, M. Hearst, and L.A. Rowe,, "The Video Workbench: A Direct Manipulation Interface for Digital Media Editing by Amateur Videographers," Submitted for publication, January 1999.
[Swan98] A. Swan, S. McCanne and L.A. Rowe, "Layered Transmission and Caching for the Multicast Session Directory Service," Proc. ACM Multimedia 98, pp. 119-128, Bristol UK, Sep 1998.
[Wong 98] Tina H. Wong, Ketan Mayer-Patel, David Simpson and L.A. Rowe, "A Software-Only Video Production Switcher for the Internet MBone Multimedia Computing and Networking 1998, Proc. IS&T/SPIE Symposium on Electronic Imaging: Science & Technology, San Jose CA, Jan 1998.
[Wu99] D. Wu, A. Swan, and L.A. Rowe, "An Internet Mbone Broadcast Management System," Multimedia Computing and Networking 1999, Proc. IS&T/SPIE Symposium on Electronic Imaging: Science & Technology, San Jose, CA, Jan 1999.
CONTROL: Continuous Output and Navigation Technology with Refinement On-Line
The CONTROL project has been developing technologies to give users control over long-running, data-intensive operations. Prior to this work, long-running operations resulted in batch processing, in which users had to wait while the system completed all the steps of a particular task. CONTROL remedies this problem with three basic techniques. First, it delivers data in a non-blocking fashion, so that users receive continuous feedback during processing. Second, it provides estimation and abstraction techniques so that users get meaningful information out of the data that has been processed at any given time; these techniques provide progressive refinement to an eventually correct and complete result. Third, it allows users to control the system’s processing on-line, changing the data delivery as they observe the output. CONTROL-based applications shield users from frustrating wait times, encouraging interactive experimentation with large data sets. CONTROL technology also has the power to allow low-cost equipment to be useful for large tasks, by providing useful estimations with a minimal investment of computing resources. We have applied this technology to a variety of applications, including relational query processing, data mining, data visualization, and spreadsheets.
"Interactive Data Analysis with CONTROL" Joseph Hellerstein, Ron Avnur,
Andy Chou, Chris Olston, Vijayshankar Raman, Tali Roth, Christian Hidber,
Peter J. Haas. To appear, IEEE Computer.
GiST: Generalized Search Trees
This work is based on a data structure called the Generalized Search Tree, or GiST. The GiST is a template index structure that can be used to support arbitrary queries over arbitrary data types. GiSTs are a key component of efficient extensible and object-relational database systems, since they allow users to easily develop custom indexing support for their applications. We have developed concurrency control and recovery protocols for GiSTs; this work allows GiSTs to be used in industrial-strength, high-performance transactional databases, and in fact a commercial database vendor is aggressively working on integrating GiSTs into their products. In joint work with computer vision researchers, GiSTs are being used by to the image database queries in Berkeley’s BlobWorld project (http://elib.cs.berkeley.edu/photos/blobworld/). We are also pursuing the application of GiST to genome matching problems in bioinformatics.
GiSTs allow indexes to be built for any queries over any data, but such indexes can not always be efficient due to inherent mathematical limitations. Within the GiST project we have worked to characterize this problem by developing a theory of indexability, akin to theories of tractability, to measure the hardness of an indexing task. We have also developed a practical analysis toolkit called amdb (the “access method debugger”) to help evaluate, tune and debug custom indexes for specific applications.
Blobworld: A System for Region-Based Image Indexing and Retrieval (with
Chad Carson, Serge J. Belongie, Megan C. Thomas and Jitendra
Malik). To appear, Visual '99.