Computer Science Technical Reports
Permanent URI for this collectionhttps://hdl.handle.net/20.500.12588/2094
Browse
Browsing Computer Science Technical Reports by Title
Now showing 1 - 20 of 107
- Results Per Page
- Sort Options
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 A Framework for Composing Noninterferent Languages(UTSA Department of Computer Science, 2013-09) Gampe, Andreas; von Ronne, JefferySoftware is frequently implemented using multiple specialized languages for different tasks. Security type systems, one technique to secure software, have previously only been studied for programs written entirely in a single language. We present a framework that facilitates reasoning over composite languages. In it, guarantees of sufficiently related component languages can be lifted to the composed language. This can significantly lower the burden necessary to certify that such composite programs are safe. Our simple but powerful approach relies, at its core, on computability and security-level separability. Besides non-interference, we also show how the framework can accommodate notions of declassification. To demonstrate the applicability of this framework, we show that a standard secure while language from the literature satisfies all necessary requirements of a composition host, and sketch how to securely embed an expressive fragment of SQL.Item A Logical Framework for Sequence Diagram with Combined Fragments(UTSA Department of Computer Science, 2011-11) Shen, Hui; Robinson, Mark; Niu, JianweiGraphical representations of scenarios, such as UML Sequence Diagrams and Message Sequence Charts, serve as a well-accepted means for modeling the interactions among software systems and their environment through the exchange of messages. The Combined Fragments of UML Sequence Diagram permit various types of control flow among messages (e.g., interleaving and branching) to express an aggregation of multiple traces encompassing complex and concurrent behaviors. However, Combined Fragments increase the difficulty of Sequence Diagram comprehension and analysis. This paper introduces an approach to formalizing the semantics of Sequence Diagrams with Combined Fragments in terms of Linear Temporal Logic (LTL) templates. In all the templates, different semantic aspects are expressed as separate, yet simple LTL formulas that can be composed to define the semantics of basic Sequence Diagram, all the Combined Fragments, and nested Combined Fragments. Moreover, the formalization enables us to leverage the analytical powers of automated decision procedures for LTL formulas to determine if a collection of Sequence Diagrams is consistent, safe, and deadlock-free.Item A random walk based approach for improving protein-protein interaction network and protein complex prediction(UTSA Department of Computer Science, 2011-12) Lei, Chengwei; Ruan, JianhuaMotivation: Recent advances in high-throughput technology have dramatically increased the availability of protein-protein interaction (PPI) data and stimulated the development of many methods for predicting protein complexes, which are important in understanding the functional organization of PPI networks. However, automated protein complex prediction from PPI data alone is significantly hindered by the high level of noise, sparseness, and highly skewed degree distribution of PPI networks. Here we present a novel network topology-based algorithm to remove spurious interactions and recover missing ones by computational predictions, and to increase the accuracy of protein complex prediction by reducing the impact of hub nodes. The key idea of our algorithm is that two proteins sharing some high-order topological similarities, which are measured by a novel random walk-based procedure, are likely interacting with each other and may belong to the same protein complex. Results: Applying our algorithm to a yeast PPI network, we found that the interactions in the reconstructed network have higher biological relevance than in the original network, assessed by multiple types of information, including gene ontology, gene expression, essentiality, conservation between species, and known protein complexes. Comparison with existing methods shows that the network reconstructed by our method has the highest quality. Using two independent graph clustering algorithms, we found that the reconstructed network has resulted in significantly improved prediction accuracy of protein complexes. Furthermore, our method is applicable to PPI networks obtained with different experimental systems such as affinity purification, Y2H, and PCA, and evidence shows that the predicted edges are likely bona fide physical interactions.Item A randomized steiner tree approach for biomarker discovery and classification of breast cancer metastasis(UTSA Department of Computer Science, 2011-12) Jahid, Md. Jamiul; Ruan, JianhuaMotivation: DNA microarray has become an important tool to help identify biomarker genes for improving the prognosis of metastatic breast cancer - a leading cause of cancer-related deaths in women worldwide. Recently, pathway-level relationships between genes have been increasingly used to build more robust classification models which also can provide useful biological insights. Due to the unavailability of complete pathways, protein-protein interaction (PPI) network is becoming more popular to researcher and opens a way to investigate the developmental process of breast cancer. Here, a network-based method is proposed to combine microarray gene expression profiles and PPI network for biomarker discovery for breast cancer metastasis. The key idea is to identify a small number of genes to connect differentially expressed genes into a single component in a PPI network; these intermediate genes contain important information about the pathways involved in metastasis and have a high probability of being biomarkers. Results: We applied this approach on three breast cancer microarray datasets, and identified significant numbers of well-known biomarker genes for breast cancer metastasis. Those selected genes are enriched with biological processes and pathways related to carcinogenic process, and, importantly, have higher stability across different datasets than in previous studies. Furthermore, those genes significantly increased cross-data classification accuracy in breast cancer metastasis. The randomized Steiner tree based approach described here is a new way to discover biomarker genes for breast cancer, and improves the prediction accuracy of metastasis. The analysis is limited here only to breast cancer, but can be easily applied to other diseases.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 A Verifiable, Control Flow Aware Constraint Analyzer for Bounds Check Elimination(UTSA Department of Computer Science, 2008-06) Niedzielski, David; Gampe, Andreas; von Ronne, Jeffery; Psarris, KleanthisThe Java programming language requires that out-of-bounds array accesses produce runtime exceptions. In general, this requires a dynamic bounds check each time an array element is accessed. However, if it can be proven that the array index does not exceed the bounds of the array, then the bounds check can be eliminated. We present a new algorithm based on extended Static Single Assignment (eSSA) form that builds a directed, weighted inequality graph representing control flow qualified, linear constraints among program variables derived from program statements. Our system then employs a customized depth-first search exploration algorithm to reason about relationships among variables, and provides a verifiable proof of its conclusions. This proof can be passed to and verified by a runtime system to minimize the run time performance impact of this analysis. Our system is novel in several respects. It takes into consideration both control flow and data flow when analyzing the constraint system; it handles general linear inequalities instead of simple difference constraints; and it provides verifiable proofs for its claims. We present experimental results which demonstrate that this method eliminates more bounds checks, and when combined with runtime verification, results in a lower runtime cost than prior work. Overall, this method improves performance by up to about 10% on the reported benchmarks.Item Achieving accurate and context-sensitive timing for code optimization(UTSA Department of Computer Science, 2008-01-18) Whaley, R. Clint; Castaldo, Anthony M.Key computational kernels must run near their peak efficiency for most high performance computing (HPC) applications. Getting this level of efficiency has always required extensive tuning of the kernel on a particular platform of interest. The success or failure of an optimization is usually measured by invoking a timer. Understanding how to build reliable and context-sensitive timers is one of the most neglected areas in HPC, and this results in a host of HPC software that looks good when reported in papers, but which delivers only a fraction of the reported performance when used by actual HPC applications. In this paper we motivate the importance of timer design, and then discuss the techniques and methodologies we have developed in order to accurately time HPC kernel routines for our well-known empirical tuning framework, ATLAS.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 An Abstracting Transformation for Amino Acid Polymorphism(UTSA Department of Computer Science, 2012-02-21) Castaldo, Anthony M.At least within exons coding for proteins, we believe what is important is the sequence of amino acids produced, and because amino acids average about three possible codings, very different looking DNA sequences, S1 and S2, can code for precisely the same sequence of amino acids. This paper describes an abstracting transformation which replaces each letter in the DNA sequence with a single letter mask that can be matched instead, such that if S1 and S2 both code for the same sequence of amino acids their mask sequence will be identical. [...]Item An Elastic Mixed-Criticality Task Model and Early-Release EDF Scheduling Algorithms(UTSA Department of Computer Science, 2016-02) Su, Hang; Zhu, Dakai; Brandt, ScottMany algorithms have recently been studied for scheduling mixed-criticality (MC) tasks. However, most existing MC scheduling algorithms guarantee the timely executions of high-criticality (HC) tasks at the expense of discarding low-criticality (LC) tasks, which can cause serious service interruption for such tasks. In this work, aiming at providing guaranteed services for LC tasks, we study an Elastic Mixed-Criticality (E-MC) task model for dual-criticality systems. Specifically, the model allows each LC task to specify its maximum period (i.e., minimum service level) and a set of early-release points. We propose an Early-Release (ER) mechanism that enables LC tasks be released more frequently and thus improve their service levels at runtime, with both conservative and aggressive approaches to exploiting system slack being considered, which is applied to both EDF and preference-oriented earliest-deadline (POED) schedulers. We formally prove the correctness of the proposed ER-EDF scheduler on guaranteeing the timeliness of all tasks through judicious management of the early releases of LC tasks. The proposed model and schedulers are evaluated through extensive simulations. The results show that, by moderately relaxing the service requirements of LC tasks in MC task sets (i.e., by having LC tasks’ maximum periods in the E-MC model be 2 to 3 times of their desired MC periods), most transformed E-MC task sets can be successfully scheduled without sacrificing the timeliness of HC tasks. Moreover, with the proposed ER mechanism, the runtime performance of tasks (e.g., execution frequencies of LC tasks, response times and jitters of HC tasks) can be significantly improved under the ER schedulers when compared to that of the state-of-the-art EDF-VD scheduler.Item An Empirical Study of Continuous Integration Failures in TravisTorrent(UTSA Department of Computer Science, 2018-07-03) Hassan, Foyzul; Wang, XiaoyinContinuous Integration (CI) is a widely used development practice where developers integrate their work after submitting code changes at central repository. CI servers usually monitor central repository for code change submission and automatically build software with changed code, perform unit testing, integration testing and provide test summary report. If build or test fails developers fix those issues and submit the code changes. Continuous submission of code modification by developers and build latency time creates stalls at CI server build pipeline and hence developers have to wait long time to get build outcome. In this paper, we categorize CI failures from TravisTorrent data set and studied the frequency of different failures. Our study on 1,187 CI failures from TravisTorrent data set shows that 829 of the CI failures are test failures, compared with 252 build script errors, 49 JavaDoc errors, and 67 stylechecking errors. It also reveals that 10.8% of CI-failure repair commits contains only build script revisions, and 25.6% CI-failure repair commits involve at least one build script revision.Furthermore, we proposed build prediction model that uses TravisTorrent data set with build error log clustering and AST level code change modification data to predict whether a build will be successful or not without attempting actual build so that developer can get early build outcome result. With the proposed model we can predict build outcome with an average F-Measure over 87% on all three build systems (Ant, Maven, Gradle) under the cross-project prediction scenario.Item An Optimal Boundary-Fair Scheduling Algorithm for Multiprocessor Real-Time Systems(UTSA Department of Computer Science, 2009-06) Zhu, Dakai; Qi, Xuan; Mossé, Daniel; Melhem, RamiAlthough the scheduling problem for multiprocessor real-time systems has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which follows the same line of research as the well-known Pfair scheduling algorithms and can also achieve full system utilization. However, different from the Pfair algorithms that make scheduling decisions at every time unit to enforce proportional progress (i.e., fairness) for each task, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries. The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved. The performance of Bfair is evaluated through extensive simulations. The results show that, compared to that of the Pfair algorithms, Bfair can significantly reduces the number of scheduling points (by upto 94%) and the time overhead of Bfair is comparable to that of the most efficient Pfair algorithm (i.e., P D^2). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule needs dramatically reduced number of context switches and task migrations, as low as 18% and 15%, respectively, when compared to those of Pfair schedules.Item ATLAS Installation Guide(UTSA Department of Computer Science, 2008-01-25) Whaley, R. ClintThis note provides a brief overview of ATLAS, and describes how to install it. It includes extensive discussion of common configure options, and describes why they might be employed on various platforms. In addition to discussing how to configure and build the ATLAS package, this note also describes how an installer can confirm that the resulting libraries are producing correct answers and running efficiently. Extensive examples are provided, including a full-length example showing the installation of both ATLAS and LAPACK on an example architecture.Item Augmented Stabilized Formulations with Fictitious Boundary Methods(UTSA Department of Computer Science, 2016-12-12) Ranjan, R.; Feng, Y.; Chronopoulos, A.Augmentation of the SUPS formulation was introduced earlier and successfully applied to solving incompressible Navier- Stokes equations for both two dimensional and three dimensional problems. Fictitious boundary methods (FBM) is a new methodology that aid the study of flow descriptions around solid obstacles on fixed Cartesian product grids that do not require body confirming meshes. FBM has been applied to lower order finite element and spectral/hp least squares techniques. We test the augmented stabilized finite element formulation introduced earlier, (ASUPS) to the fictitious boundary context and use it to solve incompressible flow problems. Utilizing the advantages of fictitious boundary methods we present solutions to flow around an array of two dimensional and three dimensional problems. In two dimensional flow computations we solve flow past a circular and elliptical shaped cylinders. For the ellipse shaped obstacles in a Newtonian flow field we examine the effects of varying boundary conditions and aspect ratios on the flow metrics. Finally we extend the procedures to solving two ellipse and two circular shaped obstacles facing the free stream. In three dimensional computations we examine incompressible flow around a three dimensional ellipse shaped obstacle at Reynolds number Re-200.Item Automated Programmable Code Transformation For Portable Performance Tuning(UTSA Department of Computer Science, 2010-04) Yi, QingWe present a framework which uses POET, an interpreted code transformation language, to effectively combine programmable control from developers, advanced optimizations by compilers, and flexible empirical tuning of optimizations to achieve portable high performance for scientific computing. We have extended ROSE, a C/C++/Fortran source-to-source compiler, to automatically analyze scientific computing benchmarks for memory performance optimizations. Instead of directly generating optimized code, our ROSE optimizer produces parameterized POET scripts as output. The auto-generated POET optimization script is then ported to different machines for portable performance tuning. Our results show that this approach is highly effective, and the code optimized by the auto-generated POET scripts can significantly outperform those optimized using the ROSE compiler alone.Item Automated Timer Generation for Empirical Tuning(UTSA Department of Computer Science, 2009-07) Magee, Josh; Yi, Qing; Whaley, R. ClintThe performance of real world applications often critically depends on a few computationally intensive routines that are either invoked numerous times by the application and/or include a significant number of loop iterations. It is desirable to separately study the performance of these critical routines, particularly in the context of automatic performance tuning, where a routine of interest is repetitively transformed using varying optimization strategies, and the performance of different implementations is gathered to guide further optimizations. This paper presents a framework for automatically generating timing drivers that independently measure the performance of critical routines separately from their original applications. We show that the timing drivers can accurately replicate the performance of routines when invoked directly within whole applications, thereby allowing critical routines to be correctly optimized in the context of empirical performance tuning.Item Automated Transformation for Performance-Critical Kernels(UTSA Department of Computer Science, 2007-06) Yi, Qing; Whaley, R. ClintThe performance of many scientific applications depends on a small number of key computational kernels which require a level of efficiency rarely satisfied by existing native compilers. We present a new approach to high performance kernel optimization, where a general-purpose transformation engine automates the production of highly efficient library routines. Our framework requires only an annotated kernel specification and can automatically produce optimized implementations based on tuning parameters controlled by a search driver. The transformation engine includes an extensive suite of optimizations which can be easily expanded using a custom transformation description language. We have applied our transformation engine to generate highly tuned code for key linear algebra kernels used in the ATLAS tuning framework. The time required to produce specifications for these kernels is orders of magnitude less than that required to hand-craft kernel implementations, and yet our framework has achieved similar performance to ATLAS’s highly tuned kernels.Item Automatic Generation of Implementations For Object-Oriented Abstractions(UTSA Department of Computer Science, 2009-05) Yi, Qing; Niu, Jianwei; Ancha, Anitha; Lakshmipathy, JeyashreeWe present a general-purpose code transformation system, the POET system, for the purpose of automatic code generation from high-level behavior specifications of object-oriented abstractions to low-level efficient implementations in C++ and Java. In particular, we have developed an extended finite-state-machine-based language, iFSM, which models the behavior logic together with implementation details of arbitrary OO abstractions. We then use the POET system to automatically translate the behavior specifications to type-safe OO implementations in Java or C++. Finally, we use the POET system to automatically translate the behavior specifications to the input language of a model-checker (NuSMV) and apply model checking to validate the correctness of the specification. If the iFSM specification is correct, our approach can always generate a correct and type-safe implementation.Item Batch Forwarding in Wireless Sensor Networks(UTSA Department of Computer Science, 2009-08) Korkmaz, TurgayBatch processing is a well-known concept in computer science and widely used to improve performance in many applications. Similarly, to improve the delivery ratio and end2end delay in wireless sensor networks (WSNs), we propose to use batch forwarding instead of streaming. Our main goal in this paper is to evaluate and compare the performance of batch forwarding and that of streaming. Accordingly, we first develop analytical models under simplified assumptions. We then conduct extensive actual experiments using TinyOS and IRIS motes from Crossbow. Both analytical and actual experimental results show that batch forwarding significantly improves the efficiency and delivery radio, particularly in heavily loaded network environments. Despite some delay due to batch formation, batch forwarding also improves the overall end2end delay performance due to its efficient use of resources. As a result, batch forwarding is a viable data gathering solution and must be used in WSN applications that generate significant amount of sensing data and require high delivery ratio and less delay.