1994 Graduate Student Research Conference Program (GSRC94)
Session 1:Volume Visualization
The VolVis Volume Visualization System
Rick Avila and Arie Kaufman
The VolVis volume visualization system has been developed which contains
a powerful set of tools for displaying and analyzing three dimensional
data. The VolVis system is supported by a generalized abstract model
which provides for both geometric and volumetric constructs. VolVis
also contains several rendering algorithms including ray tracing of
isosurfaces and transparent volumes. In addition, a fast volume rendering
algorithm has been developed, which is capable of exploiting existing
graphics hardware without placing any viewing restrictions or compromising
accuracy. VolVis also includes a volumetric navigation facility, an
animation generator, quantitative analysis tools, and a generalized
protocol for communicating with 3D input devices.
Wavelet-Based Volume Morphing
Taosong He and Arie Kaufman
This paper presents a technique for performing volume morphing
between two volumetric datasets in the wavelet domain.
The idea is to decompose the volumetric datasets into
a set of frequency bands, apply smooth interpolation to each band,
and reconstruct to form the morphed model. In addition, a technique for
establishing a suitable correspondence among object voxels is presented.
The combination of these two techniques results in a
smooth transition between the two datasets and produces morphed volume with
fewer high frequency distortions than those obtained from spatial domain volume
morphing.
The Cube-3 Real-Time Volume Rendering Architecture
Hanspeter Pfister and Arie Kaufman
We describe a high-performance special-purpose system,
Cube-3, for displaying and manipulating high-resolution
volumetric datasets in real-time. A primary goal of Cube-3
is to render 512x 512 x 512, 16-bit per voxel, datasets at about
30 frames per second. Cube-3 implements a ray-casting algorithm
in a highly-parallel and pipelined architecture, using a 3D skewed
volume memory, a modular fast bus, 2D skewed buffers, 3D interpolation
and shading units, and a ray projection cone.
Cube-3 will allow users to interactively visualize and
investigate in real-time static (3D) and dynamic (4D) high-resolution
volumetric datasets.
Volumetric Ray Tracing
Lisa Sobierajski and Arie Kaufman
In this talk I will present an efficient ray tracing method for scenes
containing volumetric as well as geometric data. A global illumination
equation is developed for this method, which is able to capture both
realistic effects and practical volume rendering.
In this method, ray-object intersection calculations result in standard
intersection points, as well as intersection segments. For accuracy and
efficiency, all objects along a ray are sorted according to distance and
intersection classification before any intersection calculations
are performed. The intersection results are then passed to a shader,
which evaluates the intensity equation defined by the illumination model
to determine the final pixel value.
Parallel Performance Measures for Volume Ray Casting
Claudio Silva and Arie Kaufman
We describe a technique for achieving fast volume ray casting on
highly parallel machines, using a load balancing scheme and an
efficient pipelined approach to compositing. We propose a new model
for measuring the amount of work one needs to perform in order to
render a given volume, and use this model to obtain a better load
balancing scheme for distributed memory machines. We also discuss in
detail the design tradeoffs of our technique. In order to validate
our model we have implemented it on the Intel iPSC/860 and the Intel
Paragon, and conducted a detailed performance analysis.
Splatting
Rajesh M. Munshi
Volume rendering is the generation of images from
discrete samples of volume data. Splatting is a
"feed-forward" algorithm that directly renders
rectilinear volume meshes, by mapping each volume
element onto the image plane. This method achieves
interactive speed through parallel execution,
successive refinement, table-driven shading, and
table-driven filtering. The method achieves high
image quality and can render volumes as either
clouds or surfaces by changing the shading functions.
It can also smoothly trade rendering time for image
quality at several stages of the rendering pipeline.
Concurrency Control and Database Systems
"Concurrency Factory": A Tool for Design of Distributed Systems
Oleg Sokolsky and Scott Smolka
Communication is the critical part of distributed systems, where
several independent devices or processes perform concurrently.
"Concurrency Factory" is a software tool that allows to design
the communication structure of a distributed system as a
hierarchical network of communicating finite-state automata.
It also provides facilities for simulation of the resulting
system and its verification against a logical or behavioural
specification.
Semantics and Concurrency Control
Wai-Hong Leung and Arthur Bernstein
This talk presents a novel method of
breaking transaction into steps where the semantics of these
steps are specified by a pre- and post-condition. With the
information of the pre- and post-condition, we try to schedule the
execution of the steps based on interference. A step is said to interefere
with a pre- or post-condition if the condition maybe invalidated by the
execution of the step. The steps are kept atomic by using conventional
concurrency control methods.
Novel Method for Memoization in Deductive Databases
Prasad Rao and I.V. Ramakrishnan
XSB provides a facility for tabulating results of queries.
Efficient methods of tabulating calls and returns, that
enable a large degree of term sharing using a technique
known as substitution factoring have yielded good results
with respect to performance enhancements.
Other optimization techniques like using subsumption to
avoid some calls, making the memoed data executable, etc.
are being looked at currently.
XSB as an Efficient Deductive Database Engine
Konstantinos Sagonas, Terrance Swift and David S. Warren
The XSB Programming System is a shareware logic programming system
that includes the full functionality of Prolog. A goal of XSB is to
tie together the logical power of Prolog with the declarativeness and
persistence of deductive database systems. To this end, XSB extends
Prolog by adding tabling and HiLog, two features used by the newest
generation of deductive database systems. However XSB's engine
executes at the speed of compiled Prolog and evaluates most programs
significantly faster than other deductive databases that are currently
available. In this talk, we will present the key features of XSB,
and report on the status of underway work aiming extend XSB in various
directions. Version 1.4.0 of XSB is available by anonymous ftp from
cs.sunysb.edu.
Table-Parallelism and XSB
Juliana Freire and David Warren
Multiprocessor machines hold promise for delivering very high computing power
at a reasonable cost. However, such machines will not gain wide acceptance
unles they can be viewed essentially as ``black boxes'' that simply run
software faster. The challenge, therefore, is to exploit parallelism in
application programs in a way that is invisible to the programmer, and that
does not incur major overheads.
Prolog stands out for having inherent forms of parallelism, {\em
and-parallelism} and {\em or-parallelism}, that can be exploited
transparently. A Parallel Prolog system would enable sequential Prolog
programs to run in a parallel machine with little or no modifications.
XSB is a Logic Programming system that supports SLG, a novel evaluation
technique. SLG adds {\em tabling} capabilities to XSB, making it complete
for datalog programs and thus suitable to be used as a deductive database
system. SLG's use of tabling gives rise to a new and
elegant model of shared-memory parallelism: {\em table-parallelism}.
In this talk we will cover the basics of parallel logic programming
and discuss some of the issues involved in the
parallelization of SLG, how it is related, and how it would compare,
with other parallel implementations of Prolog.
Completion Detection for Distributed SLG
Rui Hu, Philip Lewis and David Warren
SLG resolution is a tabling strategy which applies to non-floundering general
logic programs. It is implemented in the publicly available XSB system whose
engine, the SLG-WAM, currently implements a restriction of SLG.
It has been shown
that the SLG-WAM can compute in-memory recursive queries an order of magnitude
faster than current deductive databases. At the same time, the SLG-WAM fully
integrates Prolog code with tabled SLG code, and can execute Polog code with
minimal overhead compared to the WAM.
The SLG-WAM thus ties together the paradigms of logic
programming and deductive databases. This paper addresses some concepts
of shared memory and distributed SLG, especially the completion detection
algorithm. We use transaction approach to insure correct execution of
concurrent subgoals. And the idea of distributed termination detection is
used to detect the completion of distributed running subgoals in
distributed SLG.
Networks and Multimedia
Network Management
Mattthias Bannach and Arthur Bernstein
As the size of networks increases due to internetworking, the need to
perform management throughout the entire network faces new problems.
Devices in the network nowadays report problems they notice to a so
called management station. As the number of these messages increases
with the size of the network, it is often hard
to figure out the actual source of such problem.
In collaboration with Stony Brook Services we are working on a network
management software to resolve this problem.
The talk will give an introdution to this subject.
Real-Time Groupware
Mauricio Cortes and Prateek Mishra
Computer Supported Cooperative Work (CSCW) is an emerging area in Computer
Science that studies workgroup interaction for productive tasks. Applications
developed for workgroups, also called groupware, introduce new challenges in
various areas such as: operating system, networks, distributed computing,
multimedia, artificial intelligence, user interface, and programming lan-
guages. However, there are new issues, particular to CSCW, such as group
interaction modelling, multi-user interface design, and collaborative
programming tools. The talk will cover a brief presentation of basic CSCW
concepts and a case study developed at Stony Brook.
Last year, we built an initial collaborative prototype. This first prototype
allows two or more radiologists to collaborate in the diagnostic by sharing
in real-time images, annotations, and imaging operations. Currently, we are
developing a second version of this project relaxing some of network cons-
traints, improving the user interface, and implementing interaction protocols.
A Layered Model for Multimedia
Michael Wynblatt and Gary Schloss
Multimedia application development offers many challenges that make
ad hoc programming difficult. Current development systems have limited
scope and functionality, and are generally incompatible with each other.
We propse an abstract model for multimedia which is oriented toward
application development. It provides both a general framework and a
detailed model of the various components of a multimedia application,
which should be of use to application developers and toolkit developers
alike. We are currently designing an authoring system based on our
model.
A Campus Wide Information System
Sanford Barr and Peter Henderson
This talk will go over the design and implementation of a prototype distributed
information system currently under development. In the talk we'll address
the issues of liberating data from legacy systems, Security (network level
and data level), and Information Publishing/Verification/Updating.
A hybrid of different technologies are discussed, including Client/Server
Databases, World Wide Web, SGML, and others. We'll also go over a few
of the projects under development using these technologies.
The talk will also focus on some of the more people oriented issues of
overcoming the departmental and individual fear of "loss of control" over
information, and possible pitfalls to avoid.
Distributed Systems and Program Debugging
HCSA -- A Hybrid Client/Server Architecture
Michael Vernick and Gary Schloss
HCSA (Hybrid Client-Server Architecture), a flexible system layout
based on the popular Client-Server Architecture (CSA), is introduced.
The HCSA combines the advantages of the traditional CSA with those of
the Shared Disk Architecture (SDA) by enhancing the networked server's
direct, high-speed access to hared storage with modifications that
allow all the clients network access to both the server and the
servers' set of disks. HCSA can run applications in either CSA mode,
SDA mode, or a combination of the two and is more fault-tolerant than
the CSA since there are two paths between any client and the shared
data. Moreover, a simulation study which compares different file
system protocols demonstrates that the HCSA is able to support more
clients than the CSA under varying system workloads.
High-Performance Computing on a Network of Workstations
Manish Verma and Tzi-cker Chiueh
Workstations connected by commodity high speed networks
provide a cost effective alternative parallel computing
platform for scientific and engineering applications.
However, their usability is limited due to the lack of
efficient and easy to use programming environments and the
high latency to communication in this setup. We are developing
a distributed shared memory system that will support parallel
programming on a network of PC's. It will use a fast
communication mechanism to reduce latency. Furthermore,
it will use compiler extracted information to overlap
computation and communication to further attenuate its
affects on performance. The talk will focus on the design
and implementation aspects of this system.
Execution of Security Policies in Distributed Systems
Christina Serban and Bruce McMillin
In recent years several theoretical models have been proposed for
security policies in computer systems. A few of those are widely known and
accepted for different types of environments. In order to check that a
system's design complies with a given security policy,
formal methods and proofs are used. Sometimes, however, unnecessarily
restrictive policies must be specified since all run-time
interleavings cannot be anticipated.
In this work, we propose to formally specify a system's security
policy and then *evaluate this security policy at run time* to ensure
that the security policy is enforced. It is hoped that this will allow for
more interactions and more concurrency than statically specificed policies.
Using an in-house developed technique called CCSP we evaluate at run
time the truth of assertions that need to hold for the security
policy to be in force. CCSP has been used successfully to evaluate
safety and liveness properties through dissemination of auxiliary
variables and traces throughout the distributed system. We expect
that controlling the information dissemination to evaluate
the security policy will be our major challenge in this work.
High-Level Debugging
Karen Bernstein and Eugene Stark
Even though last twenty years have produced significant advances in
program language design, the available debugging tools have remained
virtually unchanged. In this talk, I will describe how we are applying
techniques from program language theory in order to develop a practical
high-level debugger that matches closely the level of abstraction
provided by the programming language.
Debuggers for Parallel Machines
Sanjay Padubidri and Larry Wittie
Issues concerning debugging parallel programs become important as
parallelism becomes more mainstream as a way of gaining high
performance.
In this talk we will discuss some of these issues, survey state of the
art in debuggers for parallel machines and talk about future research
plans.
Image Analysis
Terrain Modeling
Lori Scarlatos
In a virtual world, quality of the terrain model is fundamental to the
character, quality, and complexity of the simulation in that everything
(literally and figuratively) rests on the terrain. In a dynamic virtual
world, ongoing events require that this terrain model change as the
actual surface changes. Adaptive Hierarchical Triangulation (AHT) are
currently being applied and extended to address this problem for the
ARPA/TEC program, "Environmental Technology Development for Advanced
Distributed Simulations (ADS)". The AHT solution provides the following
benefits over other methods:
1) Consistent terrain views between all fidelities benefit interoperability
by ensuring, for example, that a hill displayed at a fine resolution will
not shift or disappear at a coarser resolution;
2) Faithful generalizations of the surface topology at all fidelity levels
facilitate pruning of the search space to improve performance of
spatial operations;
3) Tree structure of the hierarchy supports dynamic terrain updates by
allowing localized changes to the terrain, minimizing the amount of
rebuilding required; and
4) Enhanced fidelity models may be generated on an as-needed basis for
efficient realism at low computational cost.
Data Compression to Reduce PDF417 Symbol Size
Hongwei Shi, Theo Pavlidis and Steve Skiena
PDF417 is a high density two-dimensional bar-code symbology. The
high reliability of its retrieval suggests the possibility for it to serve
as an alternative to OCR. The idea is that when a page of text is printed,
the corresponding bar-code symbols are also printed on the same page. The
purpose of data compression here is to reduce the size of the bar-code
symbols so that they become less intrusive on the pages.
I will talk about why adaptive compressors such as the LZ
family cannot do the job, and introduce the static schemes we have
developed.
Use of Constraints as a Second Stage Character Classification Technique
George Sazaklis and Theo Pavlidis
When graph matching is used as part of a character recognition
system,it faces conflicting requirements: the need for flexibility
to account for distortions and the need for precision to
discriminate between characters that have the same overall shape
(e.g. O and Q). One possible solution is to use a flexible first
stage classifier and then a strict second stage classifier.
This talk is going to describe the second stage in a character
classification system and the concept of constraints, which are
character-specific rules used to disambiguate similar character shapes.
Two ways of implementing the constraints are discussed.
Analysing Program Behavior
Aggie Y. Sun and Bruce McMillin
Understanding the behavior of a computer program is a challenging
yet fascinating area or computer science with many advantages.
If the behavior of a program is well understood, faults can be
detected, specifications can be checked and among other advantages,
assurance can be gained. However, program behavior is very
complex and varies from one program to another. Therefore, this
presentation concentrates on extracting two properties which
are inherent in most while programs : progress and feasibility.
Progress determines if a goal state of a program will eventually
be reached and feasibility defines the constraints on the
execution governed by the dataflow. These properties are
extracted in an automated fashion using symbolic execution
coupled with linear algebraic techniques.
The LINK Project
David Wagner and Steve Skiena
The LINK project is a collection of combinatorial objects, and algorithms
that operate on these objects. These routines are implemented in C++
in order to support the object oriented paradigm. The basic combinatorial
objects are implemented as template classes so that they may be integrated
into existing code, and the routines may be used with any type of object.
Return to the GRC home page
If you have problems with this page, please send E-mail to:
evans@cs.sunysb.edu