Van de Geijn, Robert A. "Representing Linear Algebra Algorithms in Code: The FLAME API". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-01 (technical report). January 8, 2003. 23 pages.
The Formal Linear Algebra Methods Environment (FLAME) encompasses a methodology for deriving provably correct algorithms for dense linear algebra operations as well as an approach to representing (coding) the resulting algorithms. Central to the philosophy underlying FLAME are the observations that it is at a high level of abstraction that one best reasons about the correctness of algorithms, that therefore algorithms should themselves be expressed at a high level of abstraction, and that codes that implement such algorithms should themselves use an Application Programming Interface (API) that captures this high level of abstraction. A key observation is that in reasoning about algorithms intricate indexing is typically avoided and it is with the introduction of intricate indexing that programming errors are often encountered and confidence in code is deminished. Thus a carefully designed API avoids explicit indexing whenever possible. In this paper, we demonstrate how to construct one such API for coding linear algebra libraries in the C programming language. The emphasis is on properties that such APIs should embrace rather than the details of the particular API. Indeed, it should be obvious how similar interfaces can be defined for other languages, including Fortran, C++, and MATLAB M-script.
Gorinsky, Sergey, Sugat Jain, and Harrick Vin. "Robust Congestion Control for Multicast: Challenges and Opportunities". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-02 (technical report). January 2003. 6 pages.
Trust is the foundation of most congestion control protocols developed and deployed in the Internet today. Unfortunately, with the growth of the Internet, the assumption of universal trust is no longer tenable. A communicating entity can misbehave to obtain a self-beneficial bandwidth allocation. Thus, design of congestion control protocols that are robust to such misbehavior has become an important research area. In this paper, we discuss the specific problem of designing robust congestion control for multicast in the presence of untrusted hosts. We examine IP and peer-to-peer instantiations of the multicast service. For both cases, we show that protection against host misbehavior is harder than in unicast and poses new research challenges. We outline possible solutions for designing robust multicast congestion control protocols. Further, we argue that intrinsically different design requirements imposed by untrusted environments point to the need for exploring an integrative alternative to the traditional layered network architecture.
Huang, Xianglong, J. Eliot B. Moss, Kathryn S. Mckinley, Steve Blackburn, and Doug Burger. "Dynamic SimpleScalar: Simulating Java Virtual Machines". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-03 (technical report). February 2003. 23 pages.
Current user-mode machine simulators typically do not support simulation of dynamic compilation, threads, or garbage collection, all of which Java Virtual Machines (JVMs) require. In this paper, we describe, evaluate, and validate Dynamic SimpleScalar (DSS). DSS is a tool that simulates Java programs running on a JVM, using just-in-time compilation, executing on a simulated multi-way issue, out-of-order execution superscalar processor with a sophisticated memory system. We describe the implementation of the minimal support necessary for simulating a JVM in SimpleScalar, including signals, thread scheduling, synchronization, and dynamic code generation, all required by a JVM. We validate our simulator using IBM Research's JikesRVM, a state-of-the-art JVM that runs on a PowerPC architecture, and show that DSS loyally reflects the performance trends of a real JVM system. We then present a set of results using DSS. On the SPECjvm98 benchmarks, we study the best heap size for three different copying garbage collectors, and measure total, mutator, and collector memory characteristics. We compare our results with previous work, pointing out new insights, differences, and similarities. For example, we show there is a trade off between the locality benefits of copying collectors and the time to collect.
Miranker, Daniel, Weijia Xu, and Rui Mao. "MoBIoS: A Metric-Space DBMS to Support Biological Discovery". The University of Texas at Austin, Departments of Computer Sciences and Astronomy. Report# TR-03-04 (regular report). February 8, 2003. 10 pages.
MoBIoS is a specialized database management system whose storage manager is based on metric-space indexing, and whose query language entails biological data types. When relational database management systems are used to support biological data, important data types are relegated to blob and unstructured text fields. Consequently, even simple, but critical queries are executed by sequentially dumping the data to utilities outside the database. Metric-space indexing exploits the intrinsic clustering of a dataset without regard to a mapping of the data to a coordinate system. It is clear from an abundance of bioinformatic discoveries that biological data is not random and exhibits interesting structure with respect to clustering. Just as Geographic Information Systems have been enabled by spatial databases, we argue that Biological Information Systems will be enabled by metric -space databases. We show that both biological sequence data and mass-spectrometry protein signatures can be effectively managed in metric -space. Further, concomitant object-relational extensions to SQL allow concise declarative expression of complex proteomic algorithms.
Desikan, Rajagopalan, Jaehyuk Huh, Doug Burger, and Stephen W. Keckler. "Sharing Speculation : A Mechanism for Low-Latency Access to Falsely Shared Data". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-05 (technical report). May 12, 2003. 5 pages.
False sharing of data is an important phenomenon affecting performance in shared memory multiprocessors. False sharing results in unnecessary coherency overhead by causing invalidation of the shared cache line, and increasing the latency of the load accessing the cache line. As microprocessors incorporate increasingly large caches with large cache lines, false sharing will become more common, and unless methods are proposed to alleviate, can reduce the performance of shared memory multiprocessors. In this report, we propose sharing speculation , a mechanism to speculatively load values from cache lines that are falsely shared to reduce the latency of these loads, and later validating the speculation when the coherence permissions are eventually granted. We give a specific example of our proposed mechanism in the context of the Grid Processor, and show how the inherent data speculation mechanisms in the Grid Processor lend themselves to the efficient implementation of sharing speculation.
Dhillon, Inderjit S. and Suvrit Sra. "Modeling Data using Directional Distributions". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-06 (technical report). January 25, 2003. 21 pages.
Traditionally multi-variate normal distributions have been the staple of data modeling in most domains. For some domains, the model they provide is either inadequate or incorrect because of the disregard for the directional components of the data. We present a generative model for data that is suitable for modeling directional data (as can arise in text and gene expression clustering). We use mixtures of von Mises-Fisher distributions to model our data since the von Mises-Fisher distribution is the natural distribution for directional data. We derive an Expectation Maximization (EM) algorithm to find the maximum likelihood estimates for the parameters of our mixture model, and provide various experimental results to evaluate the "correctness" of our formulation. In this paper
Banerjee, Arindam, Inderjit S. Dhillon, Joydeep Ghosh, and Suvrit Sra. "Expectation Maximization for Clustering on Hyperspheres". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-07 (technical report). February 28, 2003. 33 pages.
High dimensional directional data is becoming increasingly important in contemporary applications such as analysis of text and gene-expression data. A natural model for multi-variate directional data is provided by the von Mises-Fisher (vMF) distribution on the unit hypersphere that is analogous to multi-variate Gaussian distribution in R d . In this paper, we propose modeling complex directional data as a mixture of vMF distributions. We derive and analyze two variants of the Expectation Maximization (EM) framework for estimating the parameters of this mixture. We also propose two clustering algorithms corresponding to these variants. An interesting aspect of our methodology is that the spherical kmeans algorithm (kmeans with cosine similarity) can be shown to be a special case of both our algorithms. Thus, modeling text data by vMF distributions lends theoretical validity to the use of cosine similarity which has been widely used by the information retrieval community. We provide several results on modeling high-dimensional text and gene data as experimental validation. The results indicate that our approach yields superior clusterings especially for difficult clustering tasks in high-dimensional space.
Gorinsky, Sergey, Sugat Jain, Harrick Vin, and Yongguang Zhang. "Robustness to Inflated Subscription in Multicast Congestion Control". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-09 (technical report). April 2003. 12 pages.
Group subscription is a useful mechanism for multicast congestion control: RLM, RLC, FLID-DL, and WEBRC form a promising line of multi-group protocols where receivers provide no feedback to the sender but control congestion via group membership regulation. Unfortunately, the group subscription mechanism also offers receivers an opportunity to elicit self-beneficial bandwidth allocations. In particular, a misbehaving receiver can ignore guidelines for group subscription and choose an unfairly high subscription level in a multi-group multicast session. This poses a serious threat to fairness of bandwidth allocation. In this paper, we present the first solution for the problem of inflated subscription. Our design guards access to multicast groups with dynamic keys and consists of two independent components: DELTA (Distribution of ELigibility To Access) - a novel method for in-band distribution of group keys to receivers that are eligible to access the groups according to the congestion control protocol, and SIGMA (Secure Internet Group Management Architecture) - a generic architecture for key-based group access at edge routers.
Singh, Vincent Ajay, Stephen W. Keckler, and Doug Burger. "A Routing Network for the Grid Processor Architecture". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-10 (technical report). April 2003. 9 pages.
This is a technical report on the proposed in--grid network/router for the grid architecture. This router architecture demonstrates a lightweight and robust solution for on-chip operand networks, and incorporates backpressure and dynamic routing techniques. A representative design was implemented in Verilog to test the functionality, and implemented at the circuit level in order to examine worst case delay. The results show that, in the common case, operands will be available to the next processor without incurring anything but transmission delay. Worst case delay estimates for the control logic and the transmission delay are presented for 100nm and 35nm technologies.
Bientinesi, Paolo, Enrique S. Quintana-Ort, and Robert A. van de Geijn. "FLAME@lab: A Farewell to Indices". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-11 (technical report). April 9, 2003. 13 pages.
MATLAB-like environments have been essential tools for the development of linear algebra libraries for almost three decades. The benefits include ease of implementation and maintenance of code, functionality, and interactivity. In this paper, we make the seemingly outrageous claim that the script language used for such environments is unnecessarily complex and stands in the way of the rapid development of robust, readable, and maintainable code. To correct this problem, we propose the introduction of nine almost trivial functions, the FLAME@lab API, that hide complex index manipulation. In isolation, the FLAME@lab interface illustrates how raising the level of abstraction at which one codes allows one to avoid intricate indexing in the code, thereby reducing the opportunity for the introduction of errors and raising the confidence in the correctness of the code. In combination with our Formal Linear Algebra Methods Environment (FLAME) approach to deriving linear algebra algorithms, FLAME@lab becomes an API for implementing proven correct algorithms. Finally, in combination with a similar API for C and for distributed memory parallel architectures (our PLAPACK environment), FLAME@lab becomes a natural step in the development of high-performance and parallel linear algebra libraries.
Dhillon, Inderjit S., Subramanyam Mallela, and Dharmendra S. Modha. "Information-Theoretic Co-Clustering". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-12 (technical report). April 2003. 18 pages.
Two-dimensional contingency or co-occurrence tables arise frequently in important applications such as text, web-log and market-basket data analysis. A basic problem in contingency table analysis is "co-clustering": simultaneous clustering of the rows and columns. A novel theoretical formulation views the contingency table as an empirical joint probability distribution of two discrete random variables and poses the co-clustering problem as an optimization problem in information theory --- the optimal co-clustering maximizes the mutual information between the clustered random variables subject to constraints on the number of row and column clusters. We present a co-clustering algorithm that monotonically increases the preserved mutual information by intertwining both the row and column clusterings at all stages. Using the practical example of simultaneous word-document clustering, we demonstrate that our algorithm works well in practice, especially in the presence of sparsity.
Lam, Simon S. and Huaiyu Liu. "Silk: A Resilient Routing Fabric for Peer-to-Peer Networks". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-13 (technical report). May 16, 2003 (revised, October 12, 2003). 28 pages.
Several proposed peer-to-peer networks use hypercube routing for scalability. In a previous paper, we showed that consistency of neighbor tables in hypercube routing guarantees the existence of a path from any source node to any destination node. Consistency, however, can be broken by the failure of one node. To improve the robustness of hypercube routing, we generalize the concept of consistency to K-consistency, for K ≥ 1. We then show that a K -consistent hypercube routing network provides at least K disjoint paths from any source node to any destination node with a probability close to 1. The first objective of this report is the design and specification of a new join protocol together with a proof that it generates K -consistent neighbor tables for an arbitrary number of concurrent joins (under the assumption that there is no concurrent leave or failure). To do so, we construct a more general definition of C-set tree than our previous one as the conceptual foundation for protocol design and reasoning about K -consistency. Both the new protocol and proof require major extensions to the ones in our previous paper to generalize them from 1-consistency to K -consistency. The second objective of this report is the design and evaluation of a failure recovery protocol for K -consistent networks. From simulation experiments in which up to 50% of the nodes in a K -consistent network failed (when a node fails, it becomes silent), we found that, for K ≥ 2, K -consistency was recovered in every experiment. The third objective of this report is to extend our join and failure recovery protocols such that they construct and maintain K -consistent neighbor tables for networks whose nodes join and fail concurrently and frequently. In particular, our join protocol is extended with rules to handle failures of not only existing nodes but also other joining nodes. These extended protocols, being implemented in our prototype system named Silk, will be referred to as Silk protocols. From simulation experiments in which the number of concurrent joins and failures was up to 50% of the initial network size, we found that, for K ≥ 2, Silk generated and maintained K -consistent neighbor tables after the concurrent joins and failures in every experiment. We also present an analysis of the communication and storage overheads of Silk protocols and show that Silk is scalable to a large number of network nodes
Heimlich, Marcel. "On Optimizing collective Communication". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-14 (honors). May 2003. 17 pages.
It has long been thought that research into collective communication algorithms on distributed memory parallel computers has been exhausted. This paper demonstrates that the implementations available as part of widely-used libraries are still suboptimal. We demonstrate this through the implementation of the "reduce-scatter" collective communication and comparison with the MPICH implementation of MPI. Performance on a large cluster is reported.
Sridhar, Srinath. "A Heap-Based Optimal Inversions-Sensitive Sorting Algorithm". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-15 (honors). April 18, 2003. 24 pages.
We introduce a heap-based sorting algorithm that makes n lg (I/n) + O(n lg lg (I/n) + n) comparisons and runs in time O(n lg (I/n) + n), where I is the number of inversions in the input sequence and n the number of items to be sorted. The coefficient 1 in the leading term for the number of comparisons matches the information-theoretic lower bound. The algorithm is simple and uses elementary data structures. This is the report of the undergraduate honors thesis of the author.
Fiduk, Kenneth W. "No Just Yet - Giving Objects Time to Die for Garbage Collection". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-16 (honors). May 8, 2003. 24 pages.
NO ABSTRACT
Singh, Vincent Ajay, Karthikeyan Sankaralingam, Stephen W. Keckler, and Doug Burger. "Design and Analysis of Routed Inter-ALU Networks for ILP Scalability and Performance". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-17 (technical report). Spring 2003. 22 pages.
Modern processors rely heavily on broadcast networks to bypass instruction results to dependent instructions in the pipeline. However, as architectures get wider and pipelines get deeper, broadcasting becomes more complex, slower, and more difficult to implement. This complexity is compounded by shrinking feature size, as the communication speed decreases relative to transistor switching speeds. This paper examines the fundamentals needs of bypass networks and proposes a method for classifying these Inter-ALU Networks based on how operands are routed from producers to consumers. We then propose and evaluate at both the circuit and architectural level a fine grain point-to-point Routed Inter-ALU Network (RIAN) that delivers the same instruction throughput as a full bypass network but at higher speeds and using fewer wires.
Martajaya, Jeson. "Transparent Access to Remote Services". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-18 (honors). May 16, 2003. 31 pages.
The emerging trend of distributed computing gives birth to various mechanisms of providing access to remote services. These services may be in form of dynamic libraries or custom-tailored applications. This paper suggests a simple and transparent mechanism to access these services which requires no central point that allows it to be incorporated into peer-to-peer systems. This mechanism integrates discovery and invocation of the services into one solution. The solution is implemented as an application suite named Java Remote Dynamic Loader (JRDL). This
Banerjee, Arindam, Srujana Merugu, Inderjit Dhillon, and Joydeep Ghosh. "Clustering with Bregman divergences". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-19 (technical report). July 10, 2003. 27 pages.
A wide variety of distortion functions are used for clustering, e.g., squared Euclidean distance, Mahalanobis distance and relative entropy. In this paper we consider the general case where the distortion is a Bregman divergence. We pose the hard clustering problem in terms of minimizing the loss in Bregman information, a quantity motivated by rate-distortion theory, and present an algorithm to minimize this loss. The proposed algorithm unifies several well-known partitional methods, such as classical {\tt kmeans} and information-theoretic clustering, which arise by special choices of the Bregman divergence. Further, we show an explicit bijection between Bregman divergences and exponential families. The bijection enables the development of an efficient viewpoint of EM for learning models involving mixtures of exponential distributions. This leads to a simple soft clustering algorithm involving Bregman divergences.
Natarajan, Karthik, Heather Hanson, Stephen W. Keckler, Charles R. Moore, and Doug Burger. "Microprocessor Pipeline Energy Analysis: Speculation and Over-Provisioning". The University of Texas at Austin, Departments of Computer Sciences and Astronomy. Report# TR-03-20 (regular tech report). June 18, 2007. 10 pages.
The increase in high-performance microprocessor power consumption is due in part to the large power overhead of wide-issue, highly speculative cores. Microarchitectural speculation, such as branch prediction, increases instruction throughput but carries a power burden due to wasted power for misspeculated instructions. Pipeline over-provisioning supplies excess resources which often go unused. In this paper, we use our detailed performance and power model for an Alpha 21264 to measure both the useful energy and the wasted effort due to mis-speculation and over-provisioning. Our experiments show that flushed instructions account for approximately 6% of total energy, while over-provisioning imposes a tax of 17% on average. These results suggest opportunities for power savings and energy efficiency throughout microprocessor pipelines.
Jung, Eunjin, Xiang-Yang Alex Liu, and Mohamed G. Gouda. "Key Bundles and Parcels: Secure Communication in Many Groups". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-21 (technical report). June 30, 2003. 10 pages.
We consider a system where each user is in one or more elementary groups. In this system, arbitrary groups of users can be specified using the operations of union, intersection, and complement over the elementary groups in the system. Each elementary group in the system is provided with a security key that is known only to the users in the elementary group and to the system server. Thus, for any user u to securely multicast a data item d to every user in an arbitrary group G, u first forwards d to the system server which encrypts it using the keys of the elementary groups that comprise G before multicasting the encrypted d to every user in G. Every elementary group is also provided with a key tree to ensure that the cost of changing the key of the elementary group, when a user leaves the group, is small. We describe two methods for packing the key trees of elementary groups into key bundles and into key parcels. Packing into key bundles has the advantage of reducing the number of encryptions needed to multicast a data item to the complement of an elementary group. Packing into key parcels has the advantage of reducing the total number of keys in the system. We apply these two methods to a class of synthetic systems: each system has 10000 users and 500 elementary groups, and each user is in 2 elementary groups on average. Simulations of these systems show that our proposals to pack key trees into key bundles and key parcels live up to their promises.
John, Chand T. "Thoughts on Hybrid Systems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-22 (honors). May 14, 2003. 6 pages.
There is a growing recognition of the presence of dynamical systems in many fields. In areas ranging from economics to physics and computer science to biology, many open fundamental problems are known to relate to the central problems in dynamical systems theory. Physicists generally work more with continuous dynamical systems, rather than discrete dynamical systems which computer scientists may study. The difference is that a continuous dynamical system is almost always defined as a system with an evolution function that satisfies a certain set of differential equations, while a discrete dynamical system is described by a state space involving discrete states and events which trigger discrete transitions between them. However, as computer science has come into contact with problems such as traffic management, automotive control, and modeling biological cell networks, which involve both continuous and discrete dynamical systems, a new formalism has emerged. This new formalism, the concept of a hybrid system, combines both the continuous and discrete formalisms into one entity that has fueled much research in recent years. Here we will formally introduce the notion of a hybrid system as an extension (or special case) of the concept of a dynamical system that is appropriate for many problems of interest in a wide variety of fields. We will then present summaries of some papers written on hybrid systems in recent years and present ideas for future research in the field.
Dhillon, Inderjit S., Suvrit Sra, and Joel A. Tropp. "The Metric Nearness Problem with Applications". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-23 (technical report). July 8, 2003. 14 pages.
Many practical applications in machine learning require pairwise distances among a set of objects. It is often desirable that these distance measurements satisfy the properties of a metric, especially the triangle inequality. Applications that could benefit from the metric property include data clustering and metric-based indexing of databases. In this paper, we present the metric nearness problem : Given a dissimilarity matrix, find the "nearest" matrix of distances that satisfy the triangle inequalities. A weight matrix in the formulation captures the confidence in individual dissimilarity measures, including the case of altogether missing distances. For an important class of nearness measures, the problem can be attacked with convex optimization techniques. A pleasing aspect of this formulation is that we can compute globally optimal solutions. Experiments on some sample dissimilarity matrices are presented, including some from biology.
Low, Tze Meng. "Generic Directed Acyclic Graphs". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-24 (honors). May 16, 2003. 11 pages.
NO ABSTRACT
Singh, Neha. "Analysis of Search Algorithms and Tree Structures for Proximity Search in Metric Spaces". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-25 (honors). Fall 2002. 18 pages.
NO ABSTRACT
Bientinesi, Paolo, Inderjit Dhillon, and Robert A. van de Geijn. "A Parallel Eigensolver for Dense Symmetric Matrices using Multiple Relatively Robust Representations". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-26 (technical report). July 29, 2003. 38 pages.
We present a new parallel solution for the dense symmetric eigenvalue/eigenvector problem that is based upon the tridiagonal eigensolver, Algorithm mbox MR 3 , recently developed by Dhillon & Parlett. Algorithm MR 3 has a complexity of O(n 2 ) operations for computing all eigenvalues and eigenvectors of a symmetric tridiagonal problem. Moreover the algorithm only requires O(n) extra workspace, and can be adapted to compute any subset of k eigenpairs in O(nk) time. In contrast, all earlier stable parallel algorithms for the tridiagonal eigenproblem require O(n 3 ) operations in the worst case while some implementations, such as Divide & Conquer, have an extra O(n 2 ) memory requirement. The proposed parallel algorithm balances the workload equally among the processors by traversing a matrix dependent representation tree which captures the sequence of computations performed by Algorithm MR 3 . The resulting implementation allows problems of very large size to be solved efficiently --- the largest dense problem solved in-core on a 256 processor machine with 2 GBytes of memory per processor is a matrix of size 128,000 times 128,000, which required 8 hours and 24 minutes of CPU time. We present comparisons with other eigensolvers and results on matrices that arise in the applications of computational quantum chemistry and finite element modeling of automobile bodies.
Bhagchandka, Dhiraj. "Classification of Firewalls and Proxies". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-28 (honors). Spring 2003. 47 pages.
NO ABSTRACT
Emerson, E. Allen, Kristina D. Hager, and Jay H. Konieczka. "Molecular Model Checking". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-29 (technical report). November 2003. 9 pages.
This paper shows how to perform model checking, a technique for automatic program verification, by a DNA algorithm. Our method depends on two ideas. First, Kripke structures can be compactly represented in a DNA substrate, coding each state and each edge by a strand of DNA. Second, satisfaction of temporal eventualities can be achieved through a self-propagating molecular chain reaction.
Yu, Zeyun and Chandrajit Bajaj. "A Geometric Feature Detection Approach to Particle Picking in Electron Micrographs". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-30 (technical report). July 28, 2003. 28 pages.
Accurate and automatic particle detection from cryo-electron microscopy (cryo-EM) images is very important for high-resolution reconstruction of large macromolecular structures. In this paper, we present a feature detection algorithm for particle picking. Two fundamental concepts seen in computational geometry, namely, distance transform and Voronoi diagram, are used for detection of critical features as well as for best selection of the particles against the micrographs. Unlike the conventional template-matching methods, our approach detects the particles based on their boundary features instead of intensities. The geometric features derived from the boundaries provide an efficient way for selecting particles quickly and accurately, which avoids a brute-force searching for the best position/orientation. Our approach is fully automatic and has been successfully applied to detect the particles with roughly circular or rectangular shapes. Particle detection can be enhanced by multiple sets of parameters used in edge detection and/or by anisotropic filtering. We will also discuss the extension of this approach for other types of particles with certain geometric features.
Bajaj, Chandrajit, Zeyun Yu, and Manfred Auer. "Volumetric Filtering, Feature Extraction, and Visualization of Volumetric Tomographic Molecular Imaging". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-31 (technical report). July 28, 2003. 22 pages.
We present algorithms for fully automatic volume filtering, boundary segmentation and skeletonization, and demonstrate their applications in cell and molecular tomographic imaging. We also introduce an interactive volumetric exploration tool (Volume Rover), which encapsulates implementations of the above filtering, and curve/surface feature extraction algorithms, and additionally uses multi-resolution interactive geometry and volume rendering, for the visualization.
Aziz, Adnan, Amit Prakash, and Vijaya Ramachandran. "A Near-Optimal Scheduler for Switch-Memory-Switch Routers". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-32 (technical report). July 31, 2003. 20 pages.
We present a simple and near optimal randomized parallel scheduling algorithm for scheduling packets in routers based on the Switch-Memory-Switch (SMS) architecture, which emulates output queuing by using a collection of small memories within the switch to buffer packets, and which forms the basis of the fastest routers in use today. For a router with N inputs and N outputs, our algorithm computes the schedule in O(log* N) rounds, where a round is a communication of a few bits between input ports and memory together with simple local computation at the inputs and memory. Furthermore, by using an O(log* N) deep pipeline at each input, our algorithm computes the schedule in a constant number of rounds. Our pipelined algorithm is quite simple and achieves optimal (i.e., constant) throughput with a tiny O(log*N) delay. We show that the total amount of buffer memory required by our algorithm is close to the minimum required. We also show that the number of buffer memories is within an ΕN additive term of 2N-1, for any positive constant Ε >0 (and is within an additive term of o(N) for the basic scheduler), where 2N-1 is the minimum number of memories needed under adversarial placement of packets. Furthermore we show that the number of extra memories that we use over the minimum of N that is required in the offline version, is within a constant factor of the minimum required by any on-line scheduler, even if that scheduler is allowed to fail occasionally. Our scheduling algorithm is randomized and works with high probability in N. We also prove that it is self-stabilizing, i.e., it resumes its normal behavior if occasional lapses occur due to the probabilistic nature of the algorithm. A preliminary version of these results appeared in the Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, June 2003. The main new contribution in this Technical Report is an improved pipelined scheduler that requires at most one message from each memory bank to an input in each communication step. A companion manuscript presents simulation results that show that the constant factors in our algorithms are quite small, indicating that our algorithms are likely to be quite practical.
Gorinsky, Sergey. "Robust Congestion Control for IP Multicast". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-33 (dissertation). August 2003. 124 pages.
IP multicast is a network service for scalable distribution of data to multiple receivers. Traditional protocols for multicast congestion control rely on trust: each party is assumed to follow guidelines for fair bandwidth sharing. However, with the growth and commercialization of the Internet, the assumption of universal trust is no longer tenable. In this dissertation, we consider a relaxed model where receivers are untrustworthy and can misbehave to acquire an unfairly high bandwidth at the expense of competing traffic. Our experiments with existing multicast protocols show that each of the evaluated protocols is vulnerable to receiver misbehavior. To take the first step towards robust multicast designs for distrusted environments, we focus on the class of feedback-free protocols where receivers provide no feedback to the sender and control congestion by regulating their subscription levels in the multi-group session. Unfortunately, the mechanism of group subscription offers a misbehaving receiver an opportunity to inflate its subscription level. Such inflated subscription attacks pose a major threat to fairness of bandwidth allocation. This dissertation is the first to solve the problem of inflated subscription. The presented designs rely on an insight that the ability of a receiver to access a multicast group should be tied with the congestion status of the receiver. First, we address individual attacks where a receiver inflates its subscription with no assistance from other receivers. Our solution guards access to multicast groups with dynamic keys and consists of two independent components: DELTA (Distribution of ELigibility To Access) - a novel method for in-band distribution of group keys to receivers that are eligible to access the groups according to the congestion control protocol, and SIGMA (Secure Internet Group Management Architecture) - a generic architecture for key-based group access at edge routers. DELTA and SIGMA require only minimal generic changes in the edge routers, do not alter the core of the network, and introduce no auxiliary servers. Then, we extend the design to protect multicast congestion control against inflated subscription of colluding receivers. To illustrate that integration with DELTA and SIGMA makes multicast protocols robust to inflated subscription and preserves other congestion control properties, we derive and evaluate robust adaptations of RLM and FLID-DL protocols.
Lai, Yung-Chuan (Sam). "Automation of Equational Proof Verification Using Haskell". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-34 (honors). August 2003. 19 pages.
Mistakes in a proof are strictly intolerable, because proofs are meant to assure the correctness of a theorem. Many proofs are still derived by humans today; consequently, they are error-prone. In order to minimize human errors, many rigorous proof styles have been developed, and equational logic is one of them. However, when writing an equational proof, it is still possible to make errors. Thus, it would be helpful to have software that checks proofs. This paper presents a logical model and a Haskell implementation for checking equational proofs in propositional logic. After reading the paper, the reader should be able to recognize the main obstacles to be overcome in building a proof verification tool in Haskell.
Pettie, Seth. "On the Shortest Path and Minimum Spanning Tree Problems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-35 (dissertation). August 2003. 204 pages.
The shortest path and minimum spanning tree problems are two of the classic textbook problems in combinatorial optimization. They are simple to describe and admit simple polynomial-time algorithms. However, despite years of concerted research effort, the asymptotic complexity of these problems remains unresolved. The main contributions of this dissertation are a number of asymptotically faster algorithms for the minimum spanning tree and shortest path problems. Of equal interest, we provide some clues as to why these problems are so difficult. In particular, we show why certain modern approaches to the problems are doomed to have super-linear complexity. A sampling of our results are listed below. We emphasize that all of our algorithms work with general graphs, and make no restrictive assumptions on the numerical representation of edge-lengths. (1) A provably optimal deterministic minimum spanning tree algorithm. (We give a constructive proof that the algorithmic complexity of the minimum spanning tree problem is equivalent to its decision-tree complexity.) (2) An all-pairs shortest path algorithm for general graphs running in time O(mn + n 2 log log n) , where m and n are the number of edges and vertices. This provides the first improvement over approaches based on Dijkstra's algorithm. (3) An all-pairs shortest path algorithm for undirected graphs running in O(mn log &alpha) time, where &alpha = &alpha(m,n) is the inverse-Ackermann function. (4) A single-source shortest path algorithm running in O(m &alpha + min [ n log log r, n log n ] ) time, where r bounds the ratio of any two edge lengths. For r polynomial in n this is O(m + n log log n) , an improvement over Dijkstra's algorithm. (5) An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem. This is the first inverse-Ackermann type lower bound for a comparison-based problem. (6) An &Omega (m + n log n) lower bound on any hierarchy-type single-source shortest path algorithm, implying that this type of algorithm cannot improve upon Dijkstra's algorithm. (All of our shortest path algorithms are of the hierarchy type.) (7) The first parallel minimum spanning tree algorithm that is optimal w.r.t. to both time and work. Our algorithm is for the EREW PRAM model. (8) A parallel, expected linear-work minimum spanning tree algorithm using only a polylogarithmic number of random bits. (9) An O(mn log &alpha) bound on the comparison-addition complexity of all-pairs shortest paths. This is within a tiny log &alpha factor of optimal when m = O(n) .
Xu, Guoliang, Qing Pan, and Chandrajit L. Bajaj. "Discrete Surface Modeling Using Geometric Flows". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-36 (technical report). August 17, 2003. 17 pages.
We use various nonlinear geometric partial differential equations to efficiently solve several surface modeling problems, including surface blending, N-sided hole filling and free-form surface fitting. The nonlinear equations used include two second order flows (mean curvature flow and average mean curvature flow), one fourth order flow (surface diffusion flow) and a sixth order flow. These nonlinear equations are discretized based on discrete differential geometry operators. The proposed approach is simple, efficient and gives very desirable results, for a range of surface models, possibly having sharp creases and corners.
Bajaj, Chandrajit, S. Khandelwal, J Moore, and V. Siddavanahalli. "Interactive Symbolic Visualization of Semi-automatic Theorem Proving". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-37 (technical report). August 2003. 7 pages.
We explore a new symbolic visualization model for semi-automatic theorem provers. Mechanized formal methods are finding increased use in the design and development of complex hardware and software systems. Most proofs are presented in a textual format, with intermediate formulas possibly consisting of megabytes of data, which are difficult to analyze and understand. This paper introduces a preliminary visualization environment for semi-automatic theorem provers in an attempt to help users steer the theorem proving process. The environment provides synchronized multi-resolution textual and graphical views and direct navigation of large expressions or proof trees from either of the twin interfaces. We identify three levels of the proof process at which synchronized multi-resolution graphical and textual visualization enhance user understanding.
Gupta, Ankur and Jayadev Misra. "Synthesizing Programs over Recursive Data Structures". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-38 (technical report). August 22, 2003. 20 pages.
This paper describes a methodology and its theoretical basis for synthesizing a class of programs which operate on recursive data structures. The methodology has appeared in an earlier paper by the author. This paper suggests a theoretical basis for the methodology. The theory rests on some elementary results in fixed point theory over lattices. Most of the required mathematics is developed in the paper.
Dhillon, Inderjit S. and Yuqiang Guan. "Information Theoretic Clustering of Sparse Co-Occurrence Data". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-39 (technical report). September 3, 2003. 15 pages.
A novel approach to clustering co-occurrence data poses it as an optimization problem in information theory which minimizes the resulting loss in mutual information. A divisive clustering algorithm that monotonically reduces this loss function was recently proposed. In this paper we show that sparse high-dimensional data presents special challenges which can result in the algorithm getting stuck at poor local minima. We propose two solutions to this problem: (a) a "prior" to overcome infinite relative entropy values as in the supervised Naive Bayes algorithm, and (b) local search to escape local minima. Finally, we combine these solutions to get a robust algorithm that is computationally efficient. We present detailed experimental results to show that the proposed method is highly effective in clustering document collections and outperforms previous information-theoretic clustering approaches.
Gunter, Brian C. and Robert A. van de Geijn. "Parallel Out-of-Core Computation and Updating of the QR Factorization". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-40 (technical report). September 10, 2003. 16 pages.
NO ABSTRACT
Kane, Kevin and James C. Browne. "The Component Starting Component: an environment for distributed systems and peer to peer research". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-42 (technical report). April 23, 2003. 9 pages.
Experimental research in distributed and peer-to-peer networks requires automated support for testing and deployment of components. We examine the requirements of such a system, and propose the Component Starting Component (CSC) as a solution. The Component Starting Component is a system for Java components, where hosts available as execution sites each run an instance of the CSC. When these hosts are needed, a client broadcasts a solicitation for service, and all available hosts respond with an offer of service. Unlike other systems, the CSC is designed to be lightweight and easily deployable, while assuring only authorized clients are able to use the service. We present the CSC protocol, analyze its fulfillments of the requirements, and present example applications and performance evaluation.
Boyed, Saurabh. "A Semantic Database Management System: SIM". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-43 (honors). Spring 2003. 19 pages.
SIM is a database management system based on the semantic data model. The goal of this research project was the design and implementation of SIM. SIM, an abbreviation for Semantic Information Manager, uses a data model that thrives in capturing the meaning of the data more than other database models. Thus, this higher-level database model enables the database designer and the users to see a conceptual view of the database. This paper presents an overview of some of the benefits of the semantic data model and emphasizes how SIM incorporates the semantic data model. We describe how SIM overcomes some of the weaknesses of the other database modeling systems. Several SIM and SQL examples are also provided to illustrate this matter and serve as the basis for comparative analysis. We also discuss some implementation considerations and software tools used for design and implementation of SIM. Finally, we propose some hitherto unapplied uses and applications of SIM that have the potential to streamline current database systems.
Nayate, Amol, Mike Dahlin, and Arun Iyengar. "Integrating Prefetching and Invalidation for Transparent Replication of Dissemination Services". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-44 (technical report). Fall 2003. 14 pages.
NO ABSTRACT
Howell, Jo Ann Shaw. "On the Reduction of a Matrix to Frobenius Form Using Residue Arithmetic". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-45 (dissertation). August 1971. 129 pages.
This thesis is concerned with the reduction of an integral matrix to Frobenius form exactly using residue arithmetic. Thus, exact integral factors of the characteristic polynomial are obtained. The algorithm is based on a modification of the Danilewski method. This algorithm can be performed using either single-modulus or multiple-modulus residue arithmetic, and examples are given for both cases. Included in this thesis is a description of the Danilewski method. The theory of residue arithmetic for integers, matrices, and polynomials is surveyed in order to provide an adequate background for describing the modified Danilewski method. The selection of the moduli is discussed, and numerical results from a computer program are given.
Roshan, Usman, Bernard M.E. Moret, Tandy Warnow, and Tiffani L. Williams. "Greedy Strict-Consensus Merger: A New Method to Combine Multiple Phylogenetic Trees". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-46 (technical report). October 2003. 11 pages.
Large and comprehensive phylogenetic trees are desirable for studying macroevolutionary processes and for classification purposes. One approach for obtaining large phylogenies is to combine the topologies (or source trees) from previous phylogenetic studies. Tree reconstruction techniques that use the above methodology are known as supertree methods. In this paper, we develop a new supertree algorithm called Greedy Strict-Consensus Merger (GSCM) and compare it to Matrix Representation Parsimony (MRP), the most popular supertree method. We test the behavior of GSCM and MRP on biological datasets and examine their performance with respect to maximum parsimony scores and running time. Our results demonstrate that the GSCM method outperforms MRP with respect to both these criteria on all the datasets we examined.
Yalagandula, Praveen and Mike Dahlin. "A Scalable Distributed Information Management System". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-47 (technical report). November 2003. 16 pages.
We present a Scalable Distributed Information Management System (SDIMS) that aggregates information about large-scale networked systems and that can serve as a basic building block for a broad range of large-scale distributed applications providing detailed views of nearby information and summary views of global information. To serve as a basic building block, a SDIMS should have four properties: scalability to many nodes and attributes, flexibility to accommodate a broad range of applications, support administrative autonomy and isolation, and robustness to node failures and disconnections. We design, implement and evaluate a SDIMS that (1) uses techniques from Distributed Hash Table (DHT) literature to create scalable aggregation trees, (2) provides flexibility through a simple API that lets applications control propagation of reads and writes, (3) provides autonomy and isolation through simple augmentations of current DHT algorithms, and (4) is robust to node and network reconfigurations through lazy reaggregation, on-demand reaggregation, and tunable spatial replication. Through extensive simulations and micro-benchmark experiments, we observe that our system is an order of magnitude more scalable than existing approaches, achieves autonomy and isolation properties at the cost of modestly increased read latency in comparison to flat DHTs, and gracefully handles failures.
Jump, Maria and Ben Hardekopf. "Pretenuring Based on Escape Analysis". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-48 (technical report). December 2003. 8 pages.
Our hypothesis is that escape analysis can estimate lifetime information for dynamically allocated objects. We then use this information to pretenure those objects that have long lifetimes. This technique avoids the cost incurred by a generational copying collector for copying long-lived objects from the nursery into an older generation. This approach is completely new -- all past work on pretenuring has involved profiling; our approach instead employs static analysis.
Dhillon, I.S., R.W. Heath, M.A. Sustik, and J.A. Tropp. "Generalized finite algorithms for constructing Hermitian matrices with prescribed diagonal and spectrum". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-49 (technical report). November 2003. 16 pages.
In this note, we present new algorithms that can replace the diagonal entries of a Hermitian matrix by any set of diagonal entries that majorize the original set without altering the eigenvalues of the matrix. They perform this feat by applying a sequence of (N-1) or fewer plane rotations, where N is the dimension of the matrix. Both the Bendel-Mickey and the Chan-Li algorithms are special cases of the proposed procedures. Using the fact that a positive semi-definite matrix can always be factored as X*X, we also provide more efficient versions of the algorithms that can directly construct factors with specified singular values and column norms. We conclude with some open problems related to the construction of Hermitian matrices with joint diagonal and spectral properties.
Lam, Simon S. and Huaiyu Liu. "Failure Recovery for Structured P2P Networks: Protocol Design and Performance Evaluation". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-50 (technical report). November 2003. Revised, April 2004, Report# TR-04-55. 14 pages.
Measurement studies indicate a high rate of node dynamics in p2p systems. In this paper, we address the question of how high a rate of node dynamics can be supported by structured p2p networks. We confine our study to the hypercube routing scheme used by several structured p2p systems. To improve system robustness and facilitate failure recovery, we introduce the property of K-consistency, K>=1, which generalizes consistency defined previously. (Consistency guarantees connectivity from any node to any other node.) We design and evaluate a failure recovery protocol based upon local information for K-consistent networks. The failure recovery protocol is then integrated with a join protocol that has been proved to construct $K$-consistent neighbor tables for concurrent joins. The integrated protocols were evaluated by a set of simulation experiments in which nodes joined a 2000-node network and nodes (both old and new) were randomly selected to fail concurrently over 10,000 seconds of simulated time. In each such "churn" experiment, we took a "snapshot" of neighbor tables in the network once every 50 seconds and evaluated connectivity and consistency measures over time as a function of the churn rate, timeout value in failure recovery, and K. We found our protocols to be effective, efficient, and stable for an average node lifetime as low as 8.3 minutes (the median lifetime measured for Napster and Gnutella was 60 minutes). Experiment results also show that the average routing delay of our protocols increases only slightly even when the churn rate is greatly increased.
Kim, Min Sik, Taekhyun Kim, YongJune Shin, Simon S. Lam, and Edward J. Powers. "A Wavelet-based Approach to Detect Shared Congestion". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-51 (technical report). November 2003. Revised, March 2004. 15 pages.
Congestion control has been performed at a per-flow level to provide fairness and efficiency in sharing network resources. Better utilization of network resources is achievable if it is known that two different packet flows share a congested link. Such knowledge can be used to implement cooperative congestion control or improve the overlay topology of a P2P system. Previous techniques to detect shared congestion have limitations, namely: they assume a common source or destination node, drop-tail queueing, or a single point of congestion. We propose in this paper a novel technique, applicable to any pair of paths on the Internet, without such limitations. Our technique employs a signal processing method, wavelet denoising, to separate queueing delay caused by network congestion from various other delay variations. Our wavelet-based technique is evaluated through both simulations and Internet experiments. We show that for paths with a common synchronization point, our technique provides faster convergence and higher accuracy while using fewer packets than previous techniques. Furthermore, we show that our technique is robust and accurate without a synchronization point; more specifically, it can tolerate a synchronization offset of up to one second between two packet flows.
Gouda, Mohamed G. and Eunjin Jung. "Certificate Dispersal in Ad Hoc Networks". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-52 (technical report). December 2003. 10 pages.
We investigate how to disperse the certificates, issued in an ad hoc network, among the network nodes such that the following condition holds. If any node u approaches any other node v in the network, then u can use the certificates stored either in u or in v to obtain th e public key of v (so that u can securely send messages to v). We define the cost of certificate dispersal as the average number of certi ficates stored in one node in the network. We give upper and lower bounds on the dispersability cost of certificates, and show that both bounds are tight. We also present two certificate dispersal algorithms, and show that one of those algorithms is more efficient than the other in several important cases. Finally, we identify a rich class of "certificate graphs" for which the dispersability cost is within a constant factor from the lower bound.
Miller, Lydia. "Security of the Grid Routing Protocol". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-53 (honors). December 2003. 41 pages.
NO ABSTRACT
Lin, Mei. "Congestion Control and an Analysis of TCP-friendly Rate Control". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-54 (honors). Fall 2003. 25 pages.
This paper presents a history of congestion control research and an analysis of a specific rate-based congestion control protocol, TCP-friendly rate control (TFRC). Two taxonomies of congestion control mechanisms are presented, and later used to classify general end-to-end congestion control schemes including window-based and rate-based methods. The classic TCP congestion control mechanisms are introduced as an instance of window-based congestion control. To address the research in congestion control for UDP flows, we discuss datagram congestion control protocol (DCCP) and the congestion manager (CM). Implemented in DCCP, TFRC is examined in detail for its TCP-friendliness and ability to provide smooth transmission for the applications. The sender\x92s and receiver\x92s protocols are presented using AP notation, and the equations used in the protocols are analyzed for their conduciveness to TCP-friendliness and smooth transmission. Lastly, two empirical studies of TFRC performance are summarized to validate the effectiveness of this protocol.
Lin, Ellie. "Creation of a Fine Controlled Action for a Robot". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-55 (honors). Fall 2003. 13 pages.
A common problem facing roboticists is the creation of fine controlled actions for a robot that must be interspersed with a baseline motion. We define a fine controlled action to be one in which small errors can make the difference in the success or failure of the action. A baseline motion is one that is executed repeatedly over time, such as walking straight or remaining idle. We examine the considerations that can affect the success of a fine controlled action that transitions between baseline motions. We introduce a general technique for implementing a fine controlled action that transitions from and to a baseline motion using the example of pushing an elevator button. We implement this technique in the area of robotic soccer. Our results demonstrate that this technique can successfully create fine controlled actions for a robot.
Page, David Scott. "Effective Data Access in Software IO Frameworks". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-56 (dissertation). Fall 2003. 145 pages.
NO ABSTRACT
Basu, Sugato. "Semi-supervised Clustering: Learning with Limited User Feedback". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-57 (regular technical report). November 2003. 45 pages.
NO ABSTRACT
Kolta, Ramakrishna and Mike Dahlin. "High Throughput Byzantine Fault Tolerance". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-58 (technical report). December 2003. 17 pages.
We argue for a simple change to Byzantine Fault Tolerant state machine replication libraries in order to provide high throughput. Traditional state machine replication based Byzantine fault tolerant (BFT) techniques provide high availability and security but fail to provide high throughput. This limitation stems from the fundamental assumption of generalized state machine replication techniques that all replicas execute requests sequentially in the same total order to ensure consistency across replicas. We propose a high throughput Byzantine fault tolerant architecture that uses application-specific information to identify and concurrently execute independent requests. Our architecture thus provides a general way to exploit application parallelism in order to provide high throughput without compromising correctness. Although this approach is extremely simple, it yields dramatic practical benefits. When sufficient application concurrency and hardware resources exist, CBASE, our system prototype, provides orders of magnitude improvements in throughput over BASE, a traditional BFT architecture. CBASE-FS, a Byzantine fault tolerant file system that uses CBASE, achieves twice the throughput of BASE-FS for the IOZone micro-benchmarks even in a configuration with modest available hardware parallelism.
Iyer, Subramanian. "Research Proposal Efficient and Effective Symbolic Model Checking". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-60 (technical report). October 26, 2003. 27 pages.
The main bottleneck in practical BDD-based symbolic model checking is that it is restricted by the ability to efficiently represent and perform operations on sets of states. Symbolic representations like BDDs grow very large quickly due to their necessity to cover the state space in a breadth first fashion. Satisfiability based techniques result in a proliferation of clauses, since they have to replicate the transition relation numerous times. We propose techniques to increase the capacity of automatic state-based verification as applied to sequential designs, i.e., symbolic model checking. Firstly, we propose a decompositional approach to model checking, which splits the problem into multiple partitions handled independently of each other. Secondly, we propose the use of dynamically partitioned BDDs as a capable data structure. This leads to vast improvements in state space traversal in general and error detection in buggy designs, in particular. Further, we consider the key issue of selecting good window functions for the partitioning approach. We would like to take advantage of the non-determinism afforded by POBDDs, and accordingly propose a study of windows based on general boolean functions. This is likely to show its full benefit of potentially exponential savings in the context of operations expressible as a sequence of compositions. We would like to address the issue of time scalability in verification, whereby the availability of larger amounts of computation time enables greater exploration of the state space. Finally, from a practical standpoint, we observe that extant verification approaches are unable to proceed very deep into the state space. It is our conjecture that partitioning can help in this context and we would like to explore this issue further.
Sohn, Bong-Soo and Chandrajit Bajaj. "Time-Varying Contour Topology". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-61 (technical report). December 12, 2003. 10 pages.
The contour tree has been used to compute the topology of isocontours, generate a minimal seed set for accelerated isocontour extraction, and provide a user interface to segment individual contour components in a scalar field. In this paper, we extend all the benefits of the contour tree to time-varying data visualization. We define temporal correspondence of contour components, and describe an algorithm to compute the correspondence information in time dependent contour trees. A graph representing the topology changes of time-varying isocontours is constructed in real-time for any selected isovalue using the pre-computed correspondence information. Quantitative properties such as surface area and volume changes of contour components are computed and labelled on the graph. This topology change graph helps users to easily detect the significant topological and geometric changes in time-varying isocontours. The graph is also used as a user interface to quickly segment, track and visualize the evolution of any selected contour component over time.
For help please contact trcenter@cs.utexas.edu
