Status Report for Advanced User Interfaces

Objective

The goal of the Interact project is to provide tools and technology to facilitate rich information visualization, high-bandwidth human-computer interaction, and effective collaboration. User interfaces represent a bottleneck in current design systems: designers are faced with larger collections of data than ever before, more levels of abstraction, and significant collaboration challenges, yet little research has been done to deal with these problems. Drawing from the fields of information visualization, data mining, distributed systems, and virtual reality, we hope to set new paradigms for design management, navigation, and manipulation, and ultimately enhance the productivity of design engineers.

Our goals for the previous quarter were to write applications that demonstrate, unify, and promote the display and interaction techniques we've been working on. We have made progress on several such applications, including an advanced hierarchy browser, Java code visualization tool, and a custom visualization of a partitioning algorithm. We have also started writing small applets in order to interactively demonstrate our ideas over the WWW. Lastly, we have fortified and added features to some of our core libraries.

Over the next quarter we plan to focus on the visualization of aspects of Java code. We see this as a way to leverage our software expertise and to collaborate with the JavaTime project for high-level design specification. We will also continue to work on the visualization of search for graph partitioning, layout, and clustering.

Detailed Description, Progress and Status

In last quarter's report we described a browser for high-bandwidth hierarchy browsing which demonstrates and unifies a number of the technologies we have been investigating, including fisheye-lens, gesture input, and level-of-detail. Through experiments we have discovered some drawbacks of these algorithms, for although they help the user rapidly comb through vast hierarchies, they pose performance difficulties to the rendering process. Typically, hardware-accelerated rendering is made fast through advanced caching schemes. However, the dynamic nature of these algorithms makes it difficult to cache much information. Certain graphics processors such as SGI's Onyx provide hardware convolution that may alleviate this problem, but such hardware is prohibitively expensive and won't be commonplace for years to come. Other possible solutions include different algorithms for caching such as oct-tree, or different camera/rendering strategies from the default OpenInventor renderer.

Despite the efficiency problems, we have had promising initial results for our browser. We have provided the program with file system information for the browseable hierarchy, and have level of detail and fisheye in two separate applications which we hope to merge over the next quarter. Optimization may be a challenge for the reasons stated above, but otherwise we see great potential for success. At this year's Design Automation Conference (DAC) we plan to demonstrate this effectiveness of this browser on circuit design databases, code hierarchies, and possibly some tree-related algorithm such as a BDD.

Cone tree overview of hierarchy

As part of the hierarchy browser, we have implemented a simple and elegant fisheye display algorithm described by M. Sarkar and M. Brown[1] in Java to demonstrate interactively the possibilities of "focus and context" display techniques to designers over the web. The applet version is available at http://www-cad.eecs.berkeley.edu/research/interact/fish and contains a short tutorial on fisheye algorithms. Short-term improvements to this basic demo are to include text-annotated graphs and high-level schematics, flowcharts, and block diagrams. We have also experimented in expanding the algorithm to 3D and expect to have promising results over the next quarter.

Fisheye snapshot. The circle's radius represents the distortion constant.	Partition visualization snapshot for a small graph. Nodes are colored by gain.

Graph embedding, clustering, and manipulation are also fundamental technologies for information visualization. We have begun to investigate these areas as part of the Interact infrastructure, and envision a system which automatically partitions, clusters, and hierarchically displays a complex set of relationships so that people can achieve high-level understanding of a system without having a priori knowledge of how that system is composed. Furthermore, we see an interactively guided application in which the user can specify added semantic information to the algorithm as its running to improve the performance as an interesting research prospective. Our current implementation utilizes a force-directed algorithm which works quite well for sparse graphs such as might be found in a computer network topology, but which are less common in complex systems full of interrelationships such as circuit or software design.

On the application side, progress has been made in collaboration with Dr. Wray Buntine towards a custom visualization of graph partitioning algorithms to assist another project within our group. The user sees a raw view of the circuit, divided into two levels as the algorithm progresses. Nodes (cells) which are colored based on factors such as gain, probability, and recentness of movement, animate across the divide. We don't believe that this is necessarily the most effective visualization of the process, but it is a good start to linking the two development efforts, and is also a feature we would like to see in the final version of the visualization application.

The other application area that we are focused on is graphical representation of Java code. We hope that this may eventually lead to a visual programming environment, but for now we simply want to better instrument existing development and execution environments with more sophisticated analysis and displays of simple code properties. This ranges from simple properties such as code age, nested loops, and version information to more complicated runtime properties such as thread execution and synchronization. We hope that we can leverage the development efforts of the JavaTime project, and can in turn be of use to them. Currently we have adopted an existing Java bytecode parser and modified it so that we can start developing analysis tools and visualizations which operate on the parsed code.

We have postponed many of our input device developments in favor of data analysis and visualization tools—we need sophisticated data representations to interact with before we can really make strides in input device design and evaluation for EDA. Our one remaining project in this area is a hardware gesture recognition module which will perform recognition on the input signals from the dataglove and emulate keyboard output to the host computer. This will provide a portable, high-performance, and platform-independent gesture package that we plan to use for data manipulation experiments in the near future. More information on this project can be found at http://embedded.eecs.berkeley.edu/~hwawen/classes/cs150.

We have also extended our gesture language to a modified subset of American Sign Language (ASL) and used this successfully with our X Windows keyboard emulation application to write email. We have not tested this as extensively as we had hoped and leave this as a project for a future quarter.

Future Plans and Projected Milestones

Over the next quarter we plan to proceed with multiple sub-projects, with one emphasis on visualization of Java code for design and another on search algorithms:

• Finalize the development of certain fundamental visualization library data structures and algorithms including fisheye viewing, graph display, and graph layout so that these can be commonly shared by, and fully leveraged by multiple applications.
• Expanded search algorithm development environment libraries with support for displaying more rich information such as "state space" abstractions and perhaps Matlab bindings for displaying histograms and other conventional plots.
• Begin work on prototype future environment for developing Java code. An emphasis will be placed on inter-tool communication and user interface. We hope to have an environment with the feel of an Integrated Development Environment (IDE) but with the flexibility of traditional UNIX development tools. The emphasis from our perspective will be code visualization; hopefully we can come up with clean ways of integrating other editors, compilers, profilers into the picture.