Browsing School of Computational Science and Engineering Technical Reports by Issue Date
Now showing items 1-20 of 37
-
An Open Benchmark Suite for Evaluating Computer Architecture on Bioinformatics and Life Science Applications
(Georgia Institute of Technology, 2006)In this paper, we propose BIOPERF, a definitive benchmark suite of representative applications from the biology and life sciences community, where the codes are carefully selected to span a breadth of algorithms and ... -
Extracting Unrecognized Gene Relationships From the Biomedical Literature via Matrix Factorizations Using a Priori Knowledge of Gene Relationships
(Georgia Institute of Technology, 2006)The construction of literature-based networks of gene-gene interactions is one of the most important applications of text mining in bioinformatics. Extracting potential gene relationships from the biomedical literature ... -
Sparse Non-negative Matrix Factorizations via Alternating Non-negativity-constrained Least Squares
(Georgia Institute of Technology, 2006)Many practical pattern recognition problems require non-negativity constraints. For example, pixels in digital images and chemical concentrations in bioinformatics are non-negative. Non-negative matrix factorization (NMF) ... -
Feature Reduction via Generalized Uncorrelated Linear Discriminant Analysis
(Georgia Institute of Technology, 2006)High-dimensional data appear in many applications of data mining, machine learning, and bioinformatics. Feature reduction is commonly applied as a preprocessing step to overcome the curse of dimensionality. Uncorrelated ... -
Relationships Between Support Vector Classifiers and Generalized Linear Discriminant Analysis on Support Vectors
(Georgia Institute of Technology, 2006)The linear discriminant analysis based on the generalized singular value decomposition (LDA/GSVD) has been introduced to circumvent the nonsingularity restriction inherent in the classical LDA. The LDA/GSVD provides a ... -
BioPerf: A Benchmark Suite to Evaluate High-Performance Computer Architecture on Bioinformatics Applications
(Georgia Institute of Technology, 2006)The exponential growth in the amount of genomic data has spurred growing interest in large scale analysis of genetic information. Bioinformatics applications, which explore computational methods to allow researchers to ... -
Multiclass Classifiers Based on Dimension Reduction with Generalized LDA
(Georgia Institute of Technology, 2006-01-27)Linear discriminant analysis (LDA) has been widely used for dimension reduction of data sets with multiple classes. The LDA has been recently extended to various generalized LDA methods which are applicable regardless ... -
A Comparison of Generalized Linear Discriminant Analysis Algorithms
(Georgia Institute of Technology, 2006-01-28)Linear Discriminant Analysis (LDA) is a dimension reduction method which finds an optimal linear transformation that maximizes the class separability. However, in undersampled problems where the number of data samples ... -
Designing Irregular Parallel Algorithms With Mutual Exclusion and Lock-free Protocols
(Georgia Institute of Technology, 2006-02-25)Irregular parallel algorithms pose a significant challenge for achieving high performance because of the difficulty predicting memory access patterns or execution paths. Within an irregular application, fine-grained ... -
An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)
(Georgia Institute of Technology, 2006-02-25)We present an experimental study of parallel biconnected components algorithms employing several fundamental parallel primitives, e.g., prefix sum, list ranking, sorting, connectivity, spanning tree, and tree computations. ... -
Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors
(Georgia Institute of Technology, 2006-02-25)Graph theoretic problems are representative of fundamental computations in traditional and emerging scientific disciplines like scientific computing and computational biology, as well as applications in national security. ... -
On the Architectural Requirements for Efficient Execution of Graph Algorithms
(Georgia Institute of Technology, 2006-02-25)Combinatorial problems such as those from graph theory pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. The hierarchical ... -
An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs
(Georgia Institute of Technology, 2006-02-25)We compare parallel algorithms for random permutation generation on symmetric multiprocessors (SMPs). Algorithms considered are the sorting-based algorithm, Anderson's shuffling algorithm, the dart-throwing algorithm, ... -
A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs)
(Georgia Institute of Technology, 2006-02-25)The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. Many PRAM algorithms can be adapted to SMPs with ... -
A Cache-Aware Parallel Implementation of the Push-Relabel Network Flow Algorithm and Experimental Evaluation of the Gap Relabeling Heuristic
(Georgia Institute of Technology, 2006-02-25)The maximum flow problem is a combinatorial problem of significant importance in a wide variety of research and commercial applications. It has been extensively studied and implemented over the past 40 years. The ... -
Performance Analysis of Parallel Programs via Message-Passing Graph Traversal
(Georgia Institute of Technology, 2006-02-25)The ability to understand the factors contributing to parallel program performance are vital for understanding the impact of machine parameters on the performance of specific applications. We propose a methodology for ... -
ExactMP: An Efficient Parallel Exact Solver for Phylogenetic Tree Reconstruction Using Maximum Parsimony
(Georgia Institute of Technology, 2006-02-26)Constructing phylogenetic trees in the study of the evolutionary history of a group organisms is an extremely challenging problem in computational biology. The problem becomes intractable with growing number of organisms. ... -
Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2
(Georgia Institute of Technology, 2006-02-26)Graph abstractions are extensively used to understand and solve challenging computational problems in various scientific and engineering domains. They have particularly gained prominence in recent years for applications ... -
Parallel Algorithms for Evaluating Centrality Indices in Real-World Networks
(Georgia Institute of Technology, 2006-04-14)This paper discusses fast parallel algorithms for evaluating several centrality indices frequently used in complex network analysis. These algorithms have been optimized to exploit properties typically observed in ... -
Parallel Shortest Path Algorithms for Solving Large-Scale Instances
(Georgia Institute of Technology, 2006-08-30)We present an experimental study of parallel algorithms for solving the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs. We implement Meyer and Sander's Δ-stepping algorithm ...