Computer Science Technical Reports
Permanent URI for this collectionhttps://hdl.handle.net/20.500.12588/2094
Browse
Browsing Computer Science Technical Reports by Issue Date
Now showing 1 - 20 of 107
- Results Per Page
- Sort Options
Item How to Write a UTSA CS Division Technical Report(UTSA Department of Computer Science, 1995-12-07) Jeffery, Clinton L.Technical reports in on-line and printed form are an essential component of the network by which technology and ideas are distributed. This report is for UTSA students who are asked by their research advisors to produce a technical report that describes their work.Item Reducing Field Table Size in the Icon Translator(UTSA Department of Computer Science, 1995-12-16) Hatch, Richard; Jeffery, Clinton L.The size of generated code includes many pieces of static information about a program in addition to its actual instructions. In the case of the Icon programming language, a table used in the implementation of the record data type may become quite large. This report describes an implementation of compression techniques that saves 3-12 kilobytes per binary for typical graphical applications, and much more space (over 400 kbytes in one case) for larger programs using many records.Item Programming in Idol Version 10(UTSA Department of Computer Science, 1996-01-18) Jeffery, Clinton L.Idol is an object-oriented extension of the Icon programming language. Its simple object model is suitable for introducing object-oriented concepts, yet powerful enough to use on large projects. This document describes Idol in two parts. The first part, "An Object Primer", presents Idol's object-oriented programming concepts as an integral tool with which a programmer maps a good program design into a good implementation. As such, it serves as the "user's guide" for Idol's extensions to Icon. Idol's object-oriented programming facilities are viewed within the broader framework of structured programming and modular design in general. Idol's precise syntax and semantics are detailed in the second part, "An Icon-Derived Object Language", which serves as a reference manual.Item A Federated Model for Scheduling in Wide-Area Systems(UTSA Department of Computer Science, 1996-02-06) Weissman, Jon B.; Grimshaw, Andrew S.In this paper a model for scheduling in wide-area systems is described. The model is federated and utilizes a collection of local site schedulers that control the use of their resources. The wide-area scheduler consults the local site schedulers to obtain candidate machine schedules. A set of issues and challenges inherent to wide-area scheduling are also described and the proposed model is shown to address many of these problems. A distributed algorithm for wide-area scheduling is presented and relies upon information made available about the resource needs of user jobs. The wide-area scheduler will be implemented in Legion, a wide-area computing system developed at the University of Virginia.Item Optimizing the Icon Compiler(UTSA Department of Computer Science, 1996-05-04) Jones, Anthony G.This paper details a set of optimizations that were made to the Icon compiler. Several optimizations are implemented to the type inferencing system and the intermediate code generation with the goals of improving execution time of the generated executable and lower memory requirements.Item Fault Tolerant Scheduling in Distributed Networks(UTSA Department of Computer Science, 1996-09-25) Weissman, Jon B.; Womack, DavidWe present a model for application-level fault tolerance for parallel applications. The objective is to achieve high reliability with minimal impact on the application. Our approach is based on a full replication of all parallel application components in a distributed wide-area environment in which each replica is independently scheduled in a different site. A system architecture for coordinating the replicas is described. The fault tolerance mechanism is being added to a wide-area scheduler prototype in the Legion parallel processing system. A performance evaluation of the fault tolerant scheduler and a comparison to the traditional means of fault tolerance, checkpoint-recovery, is planned.Item Cooperative Web Caching Using Server-Directed Proxy Sharing: Ph.D. Dissertation Proposal(UTSA Department of Computer Science, 1998-04-28) Dykes, Sandra G.The World Wide Web suffers from scaling and reliability problems due to overloaded servers and congested routers. Caching at local proxy servers helps, but cannot satisfy more than a third to half of the requests; most requests must still be sent to the original HTTP server or to a higher level cache. This dissertation develops a protocol for cooperative distributed caching between proxy servers, known as server-directed proxy sharing (SDP). The goals of SDP are to reduce network contention, end-user response time, and denial of service incidents by distributing requests to caches on routes with more available bandwidth. SDP is designed to match characteristics of the HTTP protocol and web traffic patterns. For example, SDP takes advantage of web page structure by having the server piggyback a list of cache sites onto the page's HTML text. This allows the requestor to retrieve embedded images simultaneously from several cache sites, which decreases response time and better distributes network traffic. Server contact is further reduced by having caches lazily share directory information when they return requested objects. Dissertation work will consist of three phases. The first task is to characterize HTTP server workloads by collecting local traces, analyzing them and comparing results to published studies. In the second phase, an analytical event-driven simulation will be used to evaluate the cache system. In the final phase a prototype version will be implemented. The contribution of this dissertation lies both in the protocol design and in the simulation work. Previous simulation studies of Web caching systems modeled single Web servers without including network traffic, and used Web server traces to drive the simulation. Such simulations cannot compute response time or network congestion, and typically rely upon server load metrics such as bytes/sec and requests/sec to evaluate cache designs. I intend to develop a more predictive network cache simulator by 1) using analytical rather than trace workloads, and 2) adapting a network simulator to model interactions of network traffic generated by multiple Web servers and multiple cache sites. The ultimate goal of this simulation will be to determine whether we can provide realistic predictions of response time and network congestion for various caching protocols and workloads. SDP is designed to fit into the existing Web infrastructure; it operates at the applications layer and can be built on top of existing HTTP servers and proxy servers. The advantage of this approach is that SDP works with current network layer protocols and Web software, making it easy to distribute and install a prototype across the Internet.Item Reliability-Aware Dynamic Energy Management in Dependable Embedded Real-Time Systems(UTSA Department of Computer Science, 2006-01) Zhu, DakaiRecent studies show that, voltage scaling, which is an efficient energy management technique, has a direct and negative effect on system reliability because of the increased rate of transient faults (e.g., those induced by cosmic particles). In this work, we propose energy management schemes that explicitly take system reliability into consideration. The proposed reliability-aware energy management schemes dynamically schedule recoveries for tasks to be scaled down to recuperate the reliability loss due to energy management. Based on the amount of available slack, the application size and the fault rate changes, we analyze when it is profitable to reclaim the slack for energy savings without sacrificing system reliability. Checkpoint technique is further explored to efficiently use the slack. Analytical and simulation results show that, the proposed schemes can achieve comparable energy savings as ordinary energy management schemes while preserving system reliability. The ordinary energy management schemes that ignore the effects of voltage scaling on fault rate changes could lead to drastically decreased system reliability.Item Privacy-Preserving Decision Tree Mining Using A Random Replacement Perturbation(UTSA Department of Computer Science, 2006-03) Dowd, Jim; Xu, Shouhuai; Zhang, WeiningPrivacy-preserving data mining has become an important topic, and many methods have been proposed for a diverse set of privacy-preserving data mining tasks. However, privacy-preserving decision tree mining pioneered by [1] still remains to be elusive. Indeed, the work of [1] was recently showed to be flawed [2], meaning that an adversary can actually recover the original data from the perturbed ones. This naturally triggers the following question: Is the data mining approach of [1] still useful despite that its specific perturbation method (called adding noise) is flawed? In this paper we resolve this issue by exploring a different perturbation method for privacy-preserving decision tree mining. In particular, we show that this perturbation method is immune to attacks including that of [2]. Besides, we thoroughly investigate the parameter selections that are useful in guiding privacy-preserving decision tree mining practice. Systematic experiments show that our method is effective.Item Energy Efficient Redundant Configurations for Reliable Parallel Servers(UTSA Department of Computer Science, 2006-05) Zhu, Dakai; Melhem, Rami; Mossé, DanielModular redundancy and temporal redundancy are traditional techniques to increase system reliability. In addition to being used as temporal redundancy, with technology advancements, slack time can also be used by energy management schemes to save energy. In this paper, we consider the combination of modular and temporal redundancy for reliable service provided by multiple servers. We first propose an efficient adaptive parallel recovery scheme that appropriately processes service requests in parallel to increase the number of faults that can be tolerated and thus system reliability. Then we explore schemes to determine the optimal redundant configurations of the parallel servers to minimize system energy consumption for a given reliability goal or to maximize system reliability for a given energy budget. Our analysis shows that parallel recovery, small requests and optimistic approaches favor lower levels of modular redundancy, while restricted serial recovery, large requests and pessimistic approaches favor higher levels of modular redundancy.Item SSA-based Mobile Code: Implementation and Empirical Evaluation(UTSA Department of Computer Science, 2006-08) Amme, Wolfram; Von Ronne, Jeffery; Franz, MichaelAlthough one might expect transportation formats based on static single assignment form (SSA) to yield faster just-in-time compilation times than those based on stack-based virtual machines, this claim has not previously been validated in practice. We attempt to quantify the effect of using an SSA-based mobile code representation by integrating support for a verifiable SSA-based IR into Jikes RVM. Performance results, measured with various optimizations and on both the IA32 and PowerPC, show improvements in both compilation time and code quality.Item SafeTSA: An Inherently Type-Safe SSA-based Code Format(UTSA Department of Computer Science, 2006-08) Von Ronne, Jeffery; Amme, Wolfram; Franz, MichaelConventional type safe virtual machines, such as the Java Virtual Machine, utilize a stack-oriented bytecode language and require verification prior to execution. We present SafeTSA, a compiler-friendly alternative to stack-oriented bytecode based on static single assignment form. SafeTSA’s special features (type separation, dominator-based scoping, and high-level control structures) facilitate producer-side, ahead-of-time optimization and an inherently-safe, space-efficient encoding.Item POET: Parameterized Optimizations for Empirical Tuning(UTSA Department of Computer Engineering, 2006-09) Yi, Qing; Seymour, Keith; You, Haihang; Vuduc, Richard; Quinlan, DanThe excessive complexity of both machine architectures and applications have made it difficult for compilers to statically model and predict application behavior. This observation motivates the recent interest in performance tuning using empirical techniques. We present a new embedded scripting language, POET (Parameterized Optimization for Empirical Tuning), for parameterizing complex code transformations so that they can be empirically tuned. The POET language aims to significantly improve the generality, flexibility, and efficiency of existing empirical tuning systems. We have used the language to parameterize and to empirically tune three loop optimizations—interchange, blocking, and unrolling—for two linear algebra kernels. We show experimentally that the time required to tune these optimizations using POET, which does not require any program analysis, is significantly shorter than that when using a full compiler-based source-code optimizer which performs sophisticated program analysis and optimizations.Item Toward Robust Distance Metric Analysis for Similarity Estimation(UTSA Department of Computer Science, 2006-10) Yu, Jie; Amores, Jaume; Sebe, Nicu; Tian, QiIn this paper, we present a general guideline to establish the relation between a distribution model and its corresponding similarity estimation. A rich set of distance metrics, such as harmonic distance and geometric distance, is derived according to Maximum Likelihood theory. These metrics can provide a more accurate feature model than the conventional Euclidean distance (SSD) and Manhattan distance (SAD). Because the feature elements are from heterogeneous sources and may have different influence on similarity estimation, the assumption of single isotropic distribution model is often inappropriate. We propose a novel boosted distance metric that not only finds the best distance metric that fits the distribution of the underlying elements but also selects the most important feature elements with respect to similarity. We experiment with different distance metrics for similarity estimation and compute the accuracy of different methods in two applications: stereo matching and motion tracking in video sequences. The boosted distance metric is tested on fifteen benchmark data sets from the UCI repository and two image retrieval applications. In all the experiments, robust results are obtained based on the proposed methods.Item Adaptive Discriminant Projection for Content-based Image Retrieval(UTSA Department of Computer Science, 2006-10) Yu, Jie; Tian, QiContent-based Image Retrieval (CBIR) is a computer vision application that aims at automatically retrieving images based on their visual content. Linear Discriminant Analysis and its variants have been widely used in CBIR applications because of their effectiveness in finding a projection that maps the original high-dimensional space to a low-dimensional one and preserves the most discriminant features. Those techniques assume images from certain class(es) are all visually similar and try to cluster them in the projected space. In this paper we show that the human high-level concept of semantic similarity between images may not arise only from the low-level visual similarity and consequently that assumption is inappropriate in many cases. We propose an Adaptive Discriminant Projection framework which could model different data distributions based on the clustering of different classes. To learn the best model fitting the real scenario, Boosted Adaptive Discriminant Projection is further proposed. Extensive experiments are designed to evaluate our methods and compare them to the state-of-the-art techniques on benchmark data set and real image retrieval applications. The results show the superior performance of our proposed methods.Item Constructing Descriptive and Discriminant Features for Face Classification(UTSA Department of Computer Science, 2006-10) Yu, Jie; Tian, QiLinear Discriminant Analysis (LDA) has been widely applied in the field of face classification because of its simplicity and efficiency in capturing the most discriminant features. However LDA often fails when facing the small sample set and change in illumination, pose or expression. To overcome those difficulties, Principal Component Analysis (PCA), which recovers the most descriptive/informative features in the dimension-reduced feature space, is often used in the preprocessing stage. Although there is a trend of preferring LDA to PCA in classification, it has been found that PCA may perform better than LDA in some cases, especially when the size of the training set is small. In this paper we propose a parametric framework that can unify PCA and LDA to find both discriminant and descriptive features. To avoid the exhaustive parameter searching, we incorporate a non-linear boosting process to enhance a pool of hybrid classifiers and adaptively combine them into a more accurate one. To evaluate the performance of our boosted hybrid method, we compare it to state-of-the-art LDA variants and the other PCA-LDA techniques on three widely used face image benchmark databases. The experiment results show the superior performance of our novel boosted hybrid discriminant analysis.Item Learning Image Manifolds by Semantic Subspace Projection(UTSA Department of Computer Science, 2006-10) Yu, Jie; Tian, QiIn many image retrieval applications, the mapping between high-level semantic concept and low-level features is obtained through a learning process. Traditional approaches often assume that images with same semantic label share strong visual similarities and should be clustered together to facilitate modeling and classification. Our research indicates this assumption is inappropriate in many cases. Instead we model the images as lying on non-linear image subspaces embedded in the high-dimensional space and find that multiple subspaces may correspond to one semantic concept. By intelligently utilizing the similarity and dissimilarity information in semantic and geometric (image) domains, we find an optimal Semantic Subspace Projection (SSP) that captures the most important properties of the subspaces with respect to classification. Theoretical analysis proves that the well-known Linear Discriminant Analysis (LDA) could be formulated as a special case of our proposed method. To capture the semantic concept dynamically, SSP can integrate relevance feedback efficiently through incremental learning. Extensive experiments have been designed and conducted to compare our proposed method to the state-of-the-art techniques such as LDA, Locality Preservation Projection (LPP), Local Linear Embedding (LLE), Local Discriminant Embedding (LDE) and their semi-supervised algorithms. The results show the superior performance of SSP.Item A Self-Supervised Learning Framework for Classifying Microarray Gene Expression Data(UTSA Department of Computer Science, 2006-10) Lu, Yijuan; Tian, Qi; Liu, Feng; Sanchez, Maribel; Wang, YufengIt is important to develop computational methods that can effectively resolve two intrinsic problems in microarray data: high dimensionality and small sample size. In this paper, we propose a self-supervised learning framework for classifying microarray gene expression data using Kernel Discriminant-EM (KDEM) algorithm. This framework applies self-supervised learning techniques in an optimal nonlinear discriminating subspace. It efficiently utilizes a large set of unlabeled data to compensate for the insufficiency of a small set of labeled data and it extends linear algorithm in DEM to kernel algorithm to handle nonlinearly separable data in a lower dimensional space. Extensive experiments on the Plasmodium falciparum expression profiles show the promising performance of the approach.Item Energy Efficient Redundant Configurations for Reliable Servers in Distributed Systems(UTSA Department of Computer Science, 2007-02) Zhu, Dakai; Melhem, Rami; Mossé, DanielModular redundancy and temporal redundancy are traditional techniques to increase system reliability. In addition to being used as temporal redundancy, with technology advancements, slack time can also be used by energy management schemes to save energy. In this paper, we consider the combination of modular and temporal redundancy to achieve energy efficient reliable service provided by multiple servers. We first propose an efficient adaptive parallel recovery scheme that appropriately processes service requests in parallel to increase the number of faults that can be tolerated and thus system reliability. Then we explore schemes to determine the optimal redundant configurations of the parallel servers to minimize system energy consumption for a given reliability goal or to maximize system reliability for a given energy budget. Our analysis shows that small requests, optimistic approaches, and parallel recovery favor lower levels of modular redundancy, while restricted large requests, pessimistic approaches and serial recovery favor higher levels of modular redundancy.Item Error Analysis of Various Forms of Floating Point Dot Products(UTSA Department of Computer Science, 2007-05) Castaldo, Anthony M.; Whaley, R. Clint; Chronopoulos, Anthony T.This paper discusses both the theoretical and statistical errors obtained by various dot product algorithms. A host of linear algebra methods derive their error behavior directly from dot product. In particular, most high performance dense systems derive their performance and error behavior overwhelmingly from matrix multiply, and matrix multiply’s error behavior is almost wholly attributable to the underlying dot product that it is built from (sparse problems usually have a similar relationship with matrix-vector multiply, which can also be built from the dot product). With the expansion of standard workstations to 64-bit memories and multicore processors, much larger calculations are possible on even simple desktop machines than ever before. Parallel machines built from these hugely expanded nodes can solve problems of almost unlimited size. Therefore, assumptions about limited problem size that used to bound the linear rise in worst-case error due to canonical dot products can no longer be assumed to be true today, and will certainly not be true in the near future. Therefore, this paper discusses several implementations of dot product, their theoretical and achieved error bounds, and their suitability for use as performance-critical building block linear algebra kernels.