Current Search: Van Engelen, Robert (x)
Search results
 Title
 Acceleration Methods Forbayesian Network Sampling.
 Creator

Yu, Haohai, Van Engelen, Robert A., Van Hoeij, Mark, Mascagni, MichaelV., Liu, Xiuwen, Department of Computer Science, Florida State University
 Abstract/Description

Bayesian inference with Bayesian networks is a #Pcomplete problem in general. Exact Bayesian inference is feasible in practice only on smallscale Bayesian networks or networks that are dramatically simplified, such as with naive Bayes or other approximations. Stochastic sampling methods, in particular importance sampling, form one of the most prominent and efficient approximate inference techniques that gives answers in reasonable computing time. A critical problem for importance sampling...
Show moreBayesian inference with Bayesian networks is a #Pcomplete problem in general. Exact Bayesian inference is feasible in practice only on smallscale Bayesian networks or networks that are dramatically simplified, such as with naive Bayes or other approximations. Stochastic sampling methods, in particular importance sampling, form one of the most prominent and efficient approximate inference techniques that gives answers in reasonable computing time. A critical problem for importance sampling is to choose an importance function to efficiently and accurately sample the posterior probability distribution given a set of observed variables (also referred to as evidence). Choosing an importance function, or designing a new function, faces two major hurdles: how to approach the posterior probability distribution accurately and how to reduce the generation of undesirable inconsistent samples caused by deterministic relations in the network (also known as the rejection problem). In my dissertation I propose Refractor Importance Sampling, consisting of a family of importance sampling algorithms to effectively break the lower bound on the error of the importance function to ensure it can approach the posterior probability distribution of a Bayesian network given evidence. The aim is to increase the convergence rate of the approximation and to reduce sampling variance. I also propose Posterior Subgraph Clustering to improve the sampling process by breaking a network into several small independent subgraphs. To address the rejection problem, I propose Zero Probability Backfilling and Compressed Vertex Tree methods to detect and store deterministic constrains that are the root cause of inconsistent samples. The rejection problem is NPhard and I prove in my dissertation that even limiting the inconsistent samples to a certain degree with positive probability is too hard to be polynomial. I propose the ktest to measure the hardness of the rejection problem by scaling the clause density of a CNF constructed from a Bayesian network. In the final part of my dissertation, I design and implement importance sampling algorithms for GPU platforms to speed up sampling by exploiting finegrain parallelism. GPUs are costeffective computing devices. However, the randomness of memoryintensive operations by Bayesian network sampling causes difficulties to obtain computational speedups with these devices. In my dissertation I propose a new method, Parallel Irregular Wavefront Sampling, to improve memory access on GPU by leveraging the conditional independence relations between variables in a network. I improve this scheme further by using the posterior distribution as an oracle to reduce costly memory fetches in the GPU. The proposed methods are implemented and experimentally tested. The results show a significant contribution in efficiency and accuracy of Bayesian network sampling for Bayesian inference with realworld and synthetic benchmark Bayesian networks.
Show less  Date Issued
 2011
 Identifier
 FSU_migr_etd0912
 Format
 Thesis
 Title
 Closed Form Solutions of Linear Difference Equations.
 Creator

Cha, Yongjae, Van Hoeij, Mark, Van Engelen, Robert A., Agashe, Amod, Aldrovandi, Ettore, Aluﬃ, Paolo, Department of Mathematics, Florida State University
 Abstract/Description

In this thesis we present an algorithm that finds closed form solutions for homogeneous linear recurrence equations. The key idea is transforming an input operator Linp to an operator Lg with known solutions. The main problem of this idea is how to find a solved equation Lg to which Linp can be reduced. To solve this problem, we use local data of a difference operator, that is invariant under the transformation.
 Date Issued
 2011
 Identifier
 FSU_migr_etd3960
 Format
 Thesis
 Title
 Solutions of Second Order Recurrence Relations.
 Creator

Levy, Giles, Van Hoeij, Mark, Van Engelen, Robert A., Aldrovandi, Ettore, Aluﬃ, Paolo, Department of Mathematics, Florida State University
 Abstract/Description

This thesis presents three algorithms each of which returns a transformation from a base equation to the input using transformations that preserve order and homogeneity (referred to as gttransformations). The first and third algorithm are new and the second algorithm is an improvement over prior algorithms for the second order case. The first algorithm `Find 2F1' finds a gttransformation to a recurrence relation satisfied by a hypergeometric series u(n) = hypergeom([a+n, b],[c],z), if such...
Show moreThis thesis presents three algorithms each of which returns a transformation from a base equation to the input using transformations that preserve order and homogeneity (referred to as gttransformations). The first and third algorithm are new and the second algorithm is an improvement over prior algorithms for the second order case. The first algorithm `Find 2F1' finds a gttransformation to a recurrence relation satisfied by a hypergeometric series u(n) = hypergeom([a+n, b],[c],z), if such a transformation exists. The second algorithm `Find Liouvillian' finds a gttransformation to a recurrence relation of the form u(n+2) + b(n)u(n) = 0 for some b(n) in C(n), if such a transformation exists. The third algorithm `Database Solver' takes advantage of a large database of sequences, `The OnLine Encyclopedia of Integer Sequences' maintained by Neil A. J. Sloane at AT&T Labs Research. It employs this database by using the recurrence relations that they satisfy as base equations from which to return a gttransformation, if such a transformation exists.
Show less  Date Issued
 2010
 Identifier
 FSU_migr_etd3099
 Format
 Thesis
 Title
 Openmath Library for Computing on Riemann Surfaces.
 Creator

Lebedev, Yuri, Seppälä, Mika, Van Engelen, Robert, Van Hoeij, Mark, Aluﬃ, Paolo, Department of Mathematics, Florida State University
 Abstract/Description

This thesis carefully reviews computational methods that will act as a tool in the research of Riemann surfaces. We are interested in representing a Riemann surface from many equivalent points of view. The goal is to define a Riemann surface so it can be freely and unambiguously exchanged between mathematical servers by creating a set of suitable OpenMath CDs.
 Date Issued
 2008
 Identifier
 FSU_migr_etd3208
 Format
 Thesis
 Title
 ChernSchwartzMacpherson Classes of Graph Hypersurfaces and Schubert Varieties.
 Creator

Stryker, Judson P., Aluﬃ, Paolo, Van Engelen, Robert, Aldrovandi, Ettore, Hironaka, Eriko, Van Hoeij, Mark, Department of Mathematics, Florida State University
 Abstract/Description

This dissertation finds some partial results in support of two positivity conjectures regarding the ChernSchwartzMacPherson (CSM) classes of graph hypersurfaces (conjectured by Aluffi and Marcolli) and Schubert varieties (conjectured by Aluffi and Mihalcea). Direct calculations of some of these CSM classes are performed. Formulas for CSM classes of families of both graph hypersurfaces and coefficients of Schubert varieties are developed. Additionally, the positivity of the CSM class of...
Show moreThis dissertation finds some partial results in support of two positivity conjectures regarding the ChernSchwartzMacPherson (CSM) classes of graph hypersurfaces (conjectured by Aluffi and Marcolli) and Schubert varieties (conjectured by Aluffi and Mihalcea). Direct calculations of some of these CSM classes are performed. Formulas for CSM classes of families of both graph hypersurfaces and coefficients of Schubert varieties are developed. Additionally, the positivity of the CSM class of certain families of these varieties is proven. The first chapter starts with an overview and introduction to the material along with some of the background material needed to understand this dissertation. In the second chapter, a series of equivalences of graph hypersurfaces that are useful for reducing the number of cases that must be calculated are developed. A table of CSM classes of all but one graph with 6 or fewer edges are explicitly computed. This table also contains Fulton Chern classes and Milnor classes for the graph hypersurfaces. Using the equivalences and a series of formulas from a paper by Aluffi and Mihalcea, a new series of formulas for the CSM classes of certain families of graph hypersurfaces are deduced. I prove positivity for all graph hypersurfaces corresponding to graphs with first Betti number of 3 or less. Formulas for graphs equivalent to graphs with 6 or fewer edges are developed (as well as cones over graphs with 6 or fewer edges). In the third chapter, CSM classes of Schubert varieties are discussed. It is conjectured by Aluffi and Mihalcea that all Chern classes of Schubert varieties are represented by effective cycles. This is proven in special cases by B. Jones. I examine some positivity results by analyzing and applying combinatorial methods to a formula by Aluffi and Mihalcea. Positivity of what could be considered the ``typical' case for low codimensional coefficients is found. Some other general results for positivity of certain coefficients of Schubert varieties are found. This technique establishes positivity for some known cases very quickly, such as the codimension 1 case as described by Jones, as well as establishing positivity for codimension 2 and families of cases that were previously unknown. An unexpected connection between one family of cases and a second order PDE is also found. Positivity is shown for all cases of codimensions 14 and some higher codimensions are discussed. In both the graph hypersurfaces and Schubert varieties, all calculated ChernSchwartzMacPherson classes were found to be positive.
Show less  Date Issued
 2011
 Identifier
 FSU_migr_etd1531
 Format
 Thesis
 Title
 Parametric Uncertainty Analysis of Uranium Transport Surface Complexation Models.
 Creator

Miller, Geoffery L., Ye, Ming, Van Engelen, Robert, Plewa, Tomasz, Department of Scientific Computing, Florida State University
 Abstract/Description

Parametric uncertainty analysis of surface complexation modeling (SCM) has been studied using linear and nonlinear analysis. A computational SCM model was developed by Kohler et al. (1996) to simulate the breakthrough of Uranium(VI) in a column of quartz. Calibration of parameters which describe the reactions involved during reactivetransport simulation has been found to fit experimental data well. Further uncertainty analysis has been conducted which determines the predictive capability of...
Show moreParametric uncertainty analysis of surface complexation modeling (SCM) has been studied using linear and nonlinear analysis. A computational SCM model was developed by Kohler et al. (1996) to simulate the breakthrough of Uranium(VI) in a column of quartz. Calibration of parameters which describe the reactions involved during reactivetransport simulation has been found to fit experimental data well. Further uncertainty analysis has been conducted which determines the predictive capability of these models. It was concluded that nonlinear analysis results in a more accurate prediction interval coverage than linear analysis. An assumption made by both linear and nonlinear analysis is that the parameters follow a normal distribution. In a preliminary study, when using Monte Carlo sampling a uniform distribution among a known feasible parameter range, the model exhibits no predictive capability. Due to high parameter sensitivity, few realizations exhibit accuracy to the known data. This results in a high confidence of the calibrated parameters, but poor understanding of the parametric distributions. This study first calibrates these parameters using a global optimization technique, multistart quasinewton BFGS method. Second, a Morris method (MOAT) analysis is used to screen parametric sensitivity. It is seen from MOAT that all parameters exhibit nonlinear effects on the simulation. To achieve an approximation of the simulated behavior of SCM parameters without the assumption of a normal distribution, this study employs the use of a CovarianceAdaptive Monte Carlo Markov chain algorithm. It is seen from posterior distributions generated from accepted parameter sets that the parameters do not necessarily follow a normal distribution. Likelihood surfaces confirm the calibration of the models, but shows that responses to parameters are complex. This complex surface is due to a nonlinear model and high correlations between parameters. The posterior parameter distributions are then used to find prediction intervals about an experiment not used to calibrate the model. The predictive capability of Adaptive MCMC is found to be better than that of linear and nonlinear analysis, showing a better understanding of parametric uncertainty than previous study.
Show less  Date Issued
 2011
 Identifier
 FSU_migr_etd2410
 Format
 Thesis
 Title
 Adaptive Series Estimators for Copula Densities.
 Creator

Gui, Wenhao, Wegkamp, Marten, Van Engelen, Robert A., Niu, Xufeng, Huﬀer, Fred, Department of Statistics, Florida State University
 Abstract/Description

In this thesis, based on an orthonormal series expansion, we propose a new nonparametric method to estimate copula density functions. Since the basis coefficients turn out to be expectations, empirical averages are used to estimate these coefficients. We propose estimators of the variance of the estimated basis coefficients and establish their consistency. We derive the asymptotic distribution of the estimated coefficients under mild conditions. We derive a simple oracle inequality for the...
Show moreIn this thesis, based on an orthonormal series expansion, we propose a new nonparametric method to estimate copula density functions. Since the basis coefficients turn out to be expectations, empirical averages are used to estimate these coefficients. We propose estimators of the variance of the estimated basis coefficients and establish their consistency. We derive the asymptotic distribution of the estimated coefficients under mild conditions. We derive a simple oracle inequality for the copula density estimator based on a finite series using the estimated coefficients. We propose a stopping rule for selecting the number of coefficients used in the series and we prove that this rule minimizes the mean integrated squared error. In addition, we consider hard and soft thresholding techniques for sparse representations. We obtain oracle inequalities that hold with prescribed probability for various norms of the difference between the copula density and our threshold series density estimator. Uniform confidence bands are derived as well. The oracle inequalities clearly reveal that our estimator adapts to the unknown degree of sparsity of the series representation of the copula density. A simulation study indicates that our method is extremely easy to implement and works very well, and it compares favorably to the popular kernel based copula density estimator, especially around the boundary points, in terms of mean squared error. Finally, we have applied our method to an insurance dataset. After comparing our method with the previous data analyses, we reach the same conclusion as the parametric methods in the literature and as such we provide additional justification for the use of the developed parametric model.
Show less  Date Issued
 2009
 Identifier
 FSU_migr_etd3929
 Format
 Thesis
 Title
 Methods for Linear and Nonlinear Array Data Dependence Analysis with the Chains of Recurrences Algebra.
 Creator

Birch, Johnnie L., Van Engelen, Robert, Ruscher, Paul, Gallivan, Kyle, Whalley, David, Yuan, Xin, Department of Computer Science, Florida State University
 Abstract/Description

The presence of data dependences between statements in a loop iteration space imposes strict constraints on statement order and loop restructuring when preserving program semantics. A compiler determines the safe partial ordering of statements that enhance performance by explicitly disproving the presence of dependences. As a result, the false positive rate of a dependence analysis technique is a crucial factor in the effectiveness of a restructuring compiler's ability to optimize the...
Show moreThe presence of data dependences between statements in a loop iteration space imposes strict constraints on statement order and loop restructuring when preserving program semantics. A compiler determines the safe partial ordering of statements that enhance performance by explicitly disproving the presence of dependences. As a result, the false positive rate of a dependence analysis technique is a crucial factor in the effectiveness of a restructuring compiler's ability to optimize the execution of performancecritical code fragments. This dissertation investigates reducing the false positive rate by improving the accuracy of analysis methods for dependence problems and increasing the total number of problems analyzed. Fundamental to these improvements is the rephrasing of the dependence problem in terms of Chains of Recurrences (CR), a formalism that has been shown to be conducive to efficient loop induction variable analysis. An infrastructure utilizing CRanalysis methods and enhanced dependence testing techniques is developed and tested. Experimental results indicate capabilities of dependence analysis methods can be improved without a reduction in efficiency. This results in a reduction in the false positive rate and an increase in the number of optimized and parallelized code fragments.
Show less  Date Issued
 2007
 Identifier
 FSU_migr_etd3750
 Format
 Thesis
 Title
 Scrambled Quasirandom Sequences and Their Applications.
 Creator

Chi, Hongmei, Mascagni, Michael, Huckaba, Sam, Burmester, Mike, Van Engelen, Robert, Srinivasan, Ashok, Department of Computer Science, Florida State University
 Abstract/Description

QuasiMonte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasiMonte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasiMonte Carlo sample values by any practical way. A recently proposed method, called randomized quasiMonte Carlo methods, takes advantage of...
Show moreQuasiMonte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasiMonte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasiMonte Carlo sample values by any practical way. A recently proposed method, called randomized quasiMonte Carlo methods, takes advantage of Monte Carlo and quasiMonte Carlo methods. Randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques in randomized quasiMonte Carlo methods, which provide an elegant approach to obtain error estimates for quasiMonte Carlo based on treating each scrambled sequence as a different and independent random sample. The core of randomized quasiMonte Carlo is to find an effective and fast algorithm to scramble (randomize) quasirandom sequences. This dissertation surveys research on algorithms and implementations of scrambled quasirandom sequences and proposes some new algorithms to improve the quality of scrambled quasirandom sequences. Besides obtaining error estimates for quasiMonte Carlo, scrambling techniques provide a natural way to parallelize quasirandom sequences. This scheme is especially suitable for distributed or grid computing. By scrambling a quasirandom sequence we can produce a family of related quasirandom sequences. Finding one or a subset of optimal quasirandom sequences within this family is an interesting problem, as such optimal quasirandom sequences can be quite useful for quasiMonte Carlo. The process of finding such optimal quasirandom sequences is called the derandomization of a randomized (scrambled) family. We summarize aspects of this technique and propose some new algorithms for finding optimal sequences from the Halton, Faure and Sobol sequences. Finally we explore applications of derandomization.
Show less  Date Issued
 2004
 Identifier
 FSU_migr_etd3823
 Format
 Thesis
 Title
 Interaction Design Patterns for Musical Applications.
 Creator

Brandt, William Patrick, Douglas, Ian, Van Engelen, Robert, Stoecklin, Sarah, Department of Computer Science, Florida State University
 Abstract/Description

Interaction design patterns provide bestpractice solutions to software user interface design problems. Several interaction design pattern collections have been published, but none of them address the details of interaction for software that facilitates musical composition on a personal computer. This paper presents a new interaction design pattern collection for musical applications and explains the pattern creation process, organizational structure, and validation model for the collection....
Show moreInteraction design patterns provide bestpractice solutions to software user interface design problems. Several interaction design pattern collections have been published, but none of them address the details of interaction for software that facilitates musical composition on a personal computer. This paper presents a new interaction design pattern collection for musical applications and explains the pattern creation process, organizational structure, and validation model for the collection. Additionally, this paper surveys general design pattern concepts and usercentered software design practices and illustrates how these two subjects have been merged within the interaction design discipline.
Show less  Date Issued
 2004
 Identifier
 FSU_migr_etd3129
 Format
 Thesis
 Title
 Massively Parallel Algorithms for CFD Simulation and Optimization on Heterogeneous ManyCore Architectures.
 Creator

Duffy, Austen C., Sussman, Mark, Hussaini, M. Yousuﬀ, Van Engelen, Robert, Cogan, Nick, Gallivan, Kyle, Department of Mathematics, Florida State University
 Abstract/Description

In this dissertation we provide new numerical algorithms for use in conjunction with simulation based design codes. These algorithms are designed and best suited to run on emerging heterogenous computing architectures which contain a combination of traditional multicore processors and new programmable manycore graphics processing units (GPUs). We have developed the following numerical algorithms (i) a new Multidirectional Search (MDS) method for PDE constrained optimization that utilizes a...
Show moreIn this dissertation we provide new numerical algorithms for use in conjunction with simulation based design codes. These algorithms are designed and best suited to run on emerging heterogenous computing architectures which contain a combination of traditional multicore processors and new programmable manycore graphics processing units (GPUs). We have developed the following numerical algorithms (i) a new Multidirectional Search (MDS) method for PDE constrained optimization that utilizes a Multigrid (MG) strategy to accelerate convergence, this algorithm is well suited for use on GPU clusters due to its parallel nature and is more scalable than adjoint methods (ii) a new GPU accelerated point implicit solver for the NASA FUN3D code (unstructured NavierStokes) that is written in the Compute Unified Device Architecture (CUDA) language, and which employs a novel GPU sharing model, (iii) novel GPU accelerated smoothers (developed using PGI Fortran with accelerator compiler directives) used to accelerate the multigrid preconditioned conjugate gradient method (MGPCG) on a single rectangular grid, and (iv) an improved pressure projection solver for adaptive meshes that is based on the MGPCG method which requires fewer grid point calculations and has potential for better scalability on hetergeneous clusters. It is shown that a multigrid  multidirectional search (MGMDS) method can run up to 5.5X faster than the MDS method when used on a one dimensional data assimilation problem. It is also shown that the new GPU accelerated point implicit solver of FUN3D is up to 5.5X times faster than the CPU version and that the solver can perform up to 40% faster on a single GPU being shared by four CPU cores. It is found that GPU accelerated smoothers for the MGPCG method on uniform grids can run over 2X faster than the nonaccelerated versions for 2D problems, and that the new MGPCG pressure projection solver for adaptive grids is up to 4X faster than the previous MG algorithm.
Show less  Date Issued
 2011
 Identifier
 FSU_migr_etd0651
 Format
 Thesis
 Title
 A Modular Data Pipelining Architecture (MDPA) for Enabling Universal Accessibility in P2P Grids.
 Creator

Lee, Sangmi, Erlebacher, Gordon, Dennis, Larry, Fox, Geoffrey C., Riccardi, Gregory, Van Engelen, Robert A., Department of Computer Science, Florida State University
 Abstract/Description

The enormous growth in wireless communications and miniaturized handheld devices in the last few years, have given rise to a vast range of new services for heterogeneous user environments. The concept of a PeertoPeer (P2P) Grid has extended traditional distributed services to accommodate diverse user devices, resources sharing environments and higher level services. In traditional multitier distributed services, services have generally been designed for accessing backend resources and...
Show moreThe enormous growth in wireless communications and miniaturized handheld devices in the last few years, have given rise to a vast range of new services for heterogeneous user environments. The concept of a PeertoPeer (P2P) Grid has extended traditional distributed services to accommodate diverse user devices, resources sharing environments and higher level services. In traditional multitier distributed services, services have generally been designed for accessing backend resources and middle ware without taking into consideration the display and networking capabilities of clients. Current developments in the design of miniature devices, their growing compute, display and communication capabilities, combined with their increasing ubiquity in daytoday life mandate a paradigm shift in the way services are designed. In this dissertation, we suggest that the nature and capabilities of these devices be factored in, into the design of services. Doing so would enable the service to cope with the everchanging landscape of pervasive devices within the P2P Grid infrastructure. We address a number of interrelated issues. First, we propose a software architecture, called the Modular Data Pipelining Architecture (MDPA), which separates user presentation from data, and refines data processing within stages of the pipeline which can potentially be deployed for Webbased collaborative application in P2P Grid environments. Second, MDPA provides a modular approach to this problem which can be expanded incrementally to deal with future changes in the nature of these devices. Third, although this thesis has been organized in the context of device capabilities, some of the ideas could be extended to deal with changing protocol, transport and communication standards in other network centric communication environments. We also introduce how we deploy the software architecture for the P2P Grid represented with Web service semantics. We also present a Universally Accessible Web service architecture, CAROUSEL Web service, which is our collaborative Grid service linked with a Web Service infrastructure and event brokering service. Finally, we also describe our approaches to content adaptation for different devices and users.
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd3206
 Format
 Thesis
 Title
 A Block Incremental Algorithm for Computing Dominant Singular Subspaces.
 Creator

Baker, Christopher Grover, Gallivan, Kyle, Srivastava, Anuj, Engelen, Robert van, Department of Computer Science, Florida State University
 Abstract/Description

This thesis presents and evaluates a generic algorithm for incrementally computing the dominant singular subspaces of a matrix. The relationship between the generality of the results and the necessary computation is explored. The performance of this method, both numerical and computational, is discussed in terms of the algorithmic parameters, such as block size and acceptance threshhold. Bounds on the error are presented along with a posteriori approximations of these bounds. Finally, a group...
Show moreThis thesis presents and evaluates a generic algorithm for incrementally computing the dominant singular subspaces of a matrix. The relationship between the generality of the results and the necessary computation is explored. The performance of this method, both numerical and computational, is discussed in terms of the algorithmic parameters, such as block size and acceptance threshhold. Bounds on the error are presented along with a posteriori approximations of these bounds. Finally, a group of methods are proposed which iteratively improve the accuracy of computed results and the quality of the bounds.
Show less  Date Issued
 2004
 Identifier
 FSU_migr_etd0961
 Format
 Thesis
 Title
 Reducing the Cost of Comparisons within Conditional Transfers of Control.
 Creator

Kreahling, William C., Whalley, David, Bellenot, Steve, Van Engelen, Robert, Srinivasan, Ashok, Yuan, Xin, Department of Computer Science, Florida State University
 Abstract/Description

A significant percentage of execution cycles are devoted to performing conditional transfers of control, which occur frequently, cause pipeline flushes when mispredicted and can prevent other code improving transformations from being applied. The work required for each conditional transfer of control can be broken into three portions: the comparison, the calculation of the branch target address and the actual transfer of control. Most of the research investigating the reduction of costs...
Show moreA significant percentage of execution cycles are devoted to performing conditional transfers of control, which occur frequently, cause pipeline flushes when mispredicted and can prevent other code improving transformations from being applied. The work required for each conditional transfer of control can be broken into three portions: the comparison, the calculation of the branch target address and the actual transfer of control. Most of the research investigating the reduction of costs associated with these instructions have focused on the calculation of the branch target address or the actual transfer of control, overlooking the comparison portion. In this dissertation we propose several techniques to reduce the costs associated with the comparison portion of conditional transfers of control. The first technique attempts to merge multiple conditions, avoiding the execution of comparison and branch instructions. The other two methods decouple the definition of the values to be compared with the actual comparison itself. In the second technique the comparison becomes an effect that implicitly occurs whenever specified registers are assigned values, avoiding the execution of a separate comparison instruction. The third technique uses a similar concept, but instead of implicit comparisons, it uses a single comparison and branch instruction in conjunction with a comparison specification. This technique attempts to capture the advantages of common branching techniques used today, without the traditional disadvantages of using a single instruction to perform both the comparison and branch.
Show less  Date Issued
 2005
 Identifier
 FSU_migr_etd2873
 Format
 Thesis
 Title
 Parallel Random Number Generation.
 Creator

Qiu, Yue, Mascagni, Michael, Rikvold, Per Arne, Kumar, Piyush, Van Engelen, Robert, Department of Computer Science, Florida State University
 Abstract/Description

Random number generators have been studied and used for decades, and various kinds of generators have been proposed and improved to fit different types of problems. Better generators fit the problem tightly and utilize the architecture fully. Under current architecture, multiple processor cores enable simultaneous execution of independent computational threads. Highperformance computing uses programs with multiple threads. Random number generators are being studied as a source of independent...
Show moreRandom number generators have been studied and used for decades, and various kinds of generators have been proposed and improved to fit different types of problems. Better generators fit the problem tightly and utilize the architecture fully. Under current architecture, multiple processor cores enable simultaneous execution of independent computational threads. Highperformance computing uses programs with multiple threads. Random number generators are being studied as a source of independent, paralleled, and reliable streams. Parallelization of random number generators is not trivial; different schemes and approaches have been proposed and scrutinized. In my work, correlations of random number streams will be examined from the perspective of computational finance. I extended the support of SPRNG to shared memory, more specifically OpenMP. I implemented some of the generators in SPRNG in GPU, with completely redesigned GPUoriented data structure and optimizations. In supplemental files, generators of SGLCG, ALFG, and MLFG are put into three separate packages accordingly. These packages are not the final release version.
Show less  Date Issued
 2013
 Identifier
 FSU_migr_etd8716
 Format
 Thesis
 Title
 Formally Evaluating Wireless Security Protocols.
 Creator

Cubukcu, Ilkay, Yasinsac, Alec, Kohout, Ladislav, Van Engelen, Robert A., Department of Computer Science, Florida State University
 Abstract/Description

The Cryptographic Protocol Analysis Language Evaluation System (CPALES) is a tool used to analyze protocols with formal methods. In this thesis, we exercise CPALES against two security protocols, the Secure Protocol of Aziz & Diffie, and IEEE 802.1X Standard protocol. Analyzing cryptographic protocols with formal methods assist us not only finding the flaws but also in understanding them. CPALES is a nice tool to analyze protocols with formal methods. It has an ability to evaluate not only...
Show moreThe Cryptographic Protocol Analysis Language Evaluation System (CPALES) is a tool used to analyze protocols with formal methods. In this thesis, we exercise CPALES against two security protocols, the Secure Protocol of Aziz & Diffie, and IEEE 802.1X Standard protocol. Analyzing cryptographic protocols with formal methods assist us not only finding the flaws but also in understanding them. CPALES is a nice tool to analyze protocols with formal methods. It has an ability to evaluate not only protocols works in wired environment but also wireless protocols. Our analysis with CPALES makes it possible to explore protocol attacks, prove protocol correctness, and analyze protocols in great detail, as well as test the capabilities of CPALES on the wireless protocols. We discuss and analyze several protocols, including The Secure Protocol and IEEE 802.1X Standard protocol, and show how attacks and solutions are simulated on these protocols with Cryptographic Protocol Analysis Language (CPAL). We also discuss the analysis of the interactions between the subprotocols (EAP and RADIUS) in IEEE 802.1X Standard protocol. Our analysis of the attacks on the IEEE 802.1X Standard protocol proved that even though it is a useful protocol for wireless LANs, it is not secure. However, the Secure Protocol has strong confidentiality but is computationally expensive due to the public key infrastructure.
Show less  Date Issued
 2005
 Identifier
 FSU_migr_etd2960
 Format
 Thesis
 Title
 Aeroacoustic Characteristics of Supersonic Twin Jets.
 Creator

Yerapotina, Sandeep, Anjaneyulu, Krothapalli, Alvi, Farukh, Engelen, Robert van, Department of Mechanical Engineering, Florida State University
 Abstract/Description

An experimental study was conducted to examine the aeroacoustic characteristics of supersonic twin jets and compare them to a single jet of equivalent area. Axisymmetric converging diverging nozzles having a fully expanded Mach number of 1.76 were operated at overexpanded and ideally expanded conditions. Planar velocity field measurements were made using Particle Image Velocimetry (PIV) at cold operating conditions. The results obtained show a decrease in potential core length for the twin...
Show moreAn experimental study was conducted to examine the aeroacoustic characteristics of supersonic twin jets and compare them to a single jet of equivalent area. Axisymmetric converging diverging nozzles having a fully expanded Mach number of 1.76 were operated at overexpanded and ideally expanded conditions. Planar velocity field measurements were made using Particle Image Velocimetry (PIV) at cold operating conditions. The results obtained show a decrease in potential core length for the twin jets. The twin jets were found to merge earlier when they were canted. Lower turbulence levels were observed for the twin jets compared to a single jet. The turbulence in the inter nozzle region of the canted twin jets was significantly reduced due to increased jet interaction. Farfield noise measurements for the twin jets were made at two azimuthal angles and compared to a single jet of equivalent diameter. Noise measurements showed a reduction in OASPL for the twin jets at most of the polar angles measured, with a 2 dB reduction in peak radiation direction. The OASPL levels of the twin jets showed a strong dependence on the azimuthal angle. Broadband shock noise was observed to have shifted to higher frequencies. Acoustic shielding was observed at some sideline angles, which caused significant reduction in high frequency noise.
Show less  Date Issued
 2005
 Identifier
 FSU_migr_etd0650
 Format
 Thesis
 Title
 A Mechanism for Tracking the Effects of Requirement Changes in Enterprise Software Systems.
 Creator

Datta, Subhajit, Engelen, Robert van, Hawkes, Lois, Yasinsac, Alec, Department of Computer Science, Florida State University
 Abstract/Description

Managing the effects of changing requirements remains one of the greatest challenges of enterprise software development. The iterative and incremental model provides an expedient framework for addressing such concerns. This thesis proposes a set of metrics – Mutation Index, Component Set, Dependency Index – and a methodology to measure the effects of requirement changes from one iteration to another. To evaluate the effectiveness of the proposed metrics, sample calculations and results from a...
Show moreManaging the effects of changing requirements remains one of the greatest challenges of enterprise software development. The iterative and incremental model provides an expedient framework for addressing such concerns. This thesis proposes a set of metrics – Mutation Index, Component Set, Dependency Index – and a methodology to measure the effects of requirement changes from one iteration to another. To evaluate the effectiveness of the proposed metrics, sample calculations and results from a real life case study are included. Future directions of our work based on this mechanism are also discussed.
Show less  Date Issued
 2006
 Identifier
 FSU_migr_etd0828
 Format
 Thesis
 Title
 Content Markup Language Design Principles.
 Creator

Strotmann, Andreas, Kohout, Ladislav J., Seppala, Mika, Van Engelen, Robert A., Gallivan, Kyle, Levitz, Hilbert, Department of Computer Science, Florida State University
 Abstract/Description

The research goal of this dissertation is to point the way towards a better understanding for the hidden complexities of knowledge communication and content markup, with a view to cleaner, more principled designs. The following four specific contributions are shown to be particularly useful tools in the quest for understanding and improving the design of content markup languages: Linguistics parallel: Since human language is a highquality existing solution to a generalization of the problem...
Show moreThe research goal of this dissertation is to point the way towards a better understanding for the hidden complexities of knowledge communication and content markup, with a view to cleaner, more principled designs. The following four specific contributions are shown to be particularly useful tools in the quest for understanding and improving the design of content markup languages: Linguistics parallel: Since human language is a highquality existing solution to a generalization of the problem that knowledge communication languages aim to solve, the study of the "engineering solutions" of human language provide a guideline to engineering solutions for content markup language design. Language layers and components: We propose a general architecture for knowledge communication languages, noting that human language appears to be structured in a deeply related parallel fashion. Compositionality: The Compositionality Principle is a fundamental research paradigm in the study of the semantics of human language. We show how this principle, which we have introduced into our research field from linguistics, has already had a notable effect on improving content markup languages. Categorial semantics: A categorial semantics of a knowledge communication language is another fundamental tool, as linguists who study the semantics of human language have discovered. In particular, we introduce the concept of categorial types into the discussion, and propose a complete categorial type system for one particular language, namely OpenMath. This dissertation is thus concerned with the architecture of such languages. The linguistics parallel posits a parallel between human language and content markup architectures based on a realization that the problems they solve are deeply related, which leads us to propose a general architecture of layers and components for content markup and knowledge communication languages. The compositionality principle provides an architectural guideline for the design of the two core layers of such languages, and writing a categorial type system for a compositional content markup language turns out to be an immensely useful tool for designing such a language. Application of this approach to several existing language proposals provides evidence for its practical usefulness, by showing how failure to adhere to these design principles produces concrete bugs in their specifications.
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd1534
 Format
 Thesis
 Title
 A Unified Compiler Framework for Program Analysis, Optimization, and Automatic Vectorization with Chains of Recurrences.
 Creator

Shou, Yixin, Van Engelen, Robert A., Erlebacher, Gordon, Gallivan, Kyle, Whalley, David, Yuan, Xin, Department of Computer Science, Florida State University
 Abstract/Description

In this dissertation a unified compiler framework for program analysis, optimization, and automatic vectorization with techniques based on the Chains of Recurrences (CR) algebra is proposed. The root theoretical foundations of the CR algebra and the CR# additions for program analysis, that is specifically developed for this dissertation research, are given. Based on the theory, an extension of the Single Static Assignment (SSA) form, called the Inductive SSA form, is proposed. The form...
Show moreIn this dissertation a unified compiler framework for program analysis, optimization, and automatic vectorization with techniques based on the Chains of Recurrences (CR) algebra is proposed. The root theoretical foundations of the CR algebra and the CR# additions for program analysis, that is specifically developed for this dissertation research, are given. Based on the theory, an extension of the Single Static Assignment (SSA) form, called the Inductive SSA form, is proposed. The form associates inductive proofs with SSA variables to describe their inductive properties. The proofs are derived with algorithms based on the CR# theory. Inductive SSA provides an internal program representation that facilitates more effective loop analysis by a compiler. Based on the Inductive SSA form, a collection of compiler algorithms for program optimization at the SSA level is described and evaluated. More specifically, Inductive SSA merges static SSA information with semantic recurrence information to describe the value progressions of loopvariant variables. We will show how Inductive SSA enables and/or enhances loopvariant variable analysis, improves dependence testing for loops, and how it can be effectively used by many classic compiler optimizations to improve compilation results. Inductive SSA is based on our theoretical work on extending the CR formalism by the CR# (CRsharp) algebra and lattice to effectively represent the value sequences and value ranges of conditionally updated variables in loops. Using empirical results on SPEC benchmarks with GCC 4.1, we will show that the Inductive SSA form captures more recurrence relations compared to stateoftheart induction variable recognition techniques. Because the CR# term rewriting system is complete (confluent and terminating), it can be used for congruence detection in programs at all optimization levels. The Inductive SSA program analysis is far less sensitive to syntactical code changes, due to the real semantic information it captures. As a result of the independence of code structure, the phase ordering problem, in which multiple optimizing transformations can be ordered based on their effect on enabling or disabling other transformations, is greatly alleviated with Inductive SSA for many traditional lowlevel and looplevel optimizations. The experimental results show that the effectiveness of loopvariant variable analysis, congruence detection, and loop optimizations can be significantly increased with Inductive SSA. For this dissertation research a math function library generator is also developed. Many computational tasks require repeated evaluation of functions over structured grids, such as plotting in a coordinate system, rendering of parametric objects in 2D and 3D, numerical grid generation, and signal processing. The library generator speeds up closedform function evaluations over grids by vectorizing the CR forms of these functions. The approach is comparable to aggressive strength reduction and shortvector vectorization of the resulting CRs. Strength reduction of floating point operations is usually prevented in a compiler due to safety issues related to floating point roundoff. Autotuning of the library ensures safe floating point evaluation. Experiments show significantly improved execution of streaming SIMD extensions (SSE) and instructionlevel parallelism (ILP) of math function evaluations.
Show less  Date Issued
 2009
 Identifier
 FSU_migr_etd1744
 Format
 Thesis
 Title
 Optimizing MPI PointtoPoint Communication Performance on RDMAEnabled SMPCMP Clusters.
 Creator

Small, Matthew, Yuan, Xin, Shute, Valerie, Van Engelen, Robert, Srinivasan, Ashok, Department of Computer Science, Florida State University
 Abstract/Description

Clusters of Symmetric Multiprocessing (SMP) nodes with multicore Chip Multiprocessors (CMP), also known as SMPCMP clusters, are ubiquitous today. Message Passing Interface (MPI) is the de facto standard for developing message passing applications for such clusters. Most modern SMPCMP clusters support Remote Direct Memory Access (RDMA), which allows for flexible and efficient communication schemes but introduces a new model that can be challenging to exploit. This dissertation research...
Show moreClusters of Symmetric Multiprocessing (SMP) nodes with multicore Chip Multiprocessors (CMP), also known as SMPCMP clusters, are ubiquitous today. Message Passing Interface (MPI) is the de facto standard for developing message passing applications for such clusters. Most modern SMPCMP clusters support Remote Direct Memory Access (RDMA), which allows for flexible and efficient communication schemes but introduces a new model that can be challenging to exploit. This dissertation research explores leveraging the flexibility provided by RDMA to optimize MPI pointtopoint communications for both small and medium to large messages on SMPCMP clusters. For small messages, a scheme is devised that improves the buffer memory management in the existing RDMAbased small message channel design; and a novel shared small message channel design is developed that reduces both individual channel resource requirements as well as the number of channels needed by an MPI application, greatly improving small message channel resource utilization and scalability without adding significant overheads or sacrificing the performance benefits of RDMA. MPI medium and large messages are realized by various rendezvous protocols whose performance is very sensitive to the timing of the critical events in the communication (protocol invocation scenarios). As such, existing MPI implementations that use a fixed protocol across all communications suffer from various performance problems such as unnecessary synchronization and communication progress issues. In my research, I explore the idea of protocol customization that allows different protocols to be used for different situations. First, a repository of protocols that can collectively provide nearoptimal performance for all protocol invocation scenarios is developed. This repository provides the foundation for profiledriven and compilerassisted protocol customization for performance improvement. Furthermore, a communication system with dynamic protocol selection is developed that integrates four protocols into a single system and is able to choose an optimized protocol to suit the runtime characteristics of a particular communication while fully supporting MPI semantics. These techniques reduce unnecessary synchronizations, decrease the number of control messages that are in the critical path of communications, and improve the communication progress, which results in a significantly better communicationcomputation overlap capability.
Show less  Date Issued
 2012
 Identifier
 FSU_migr_etd5434
 Format
 Thesis
 Title
 Efficient XML Stream Processing and Searching.
 Creator

Zhang, Wei, Van Engelen, Robert A., Gordon, Erlebacher, Liu, Xiuwen, Yuan, Xin, Duan, Zhenhai, Department of Computer Science, Florida State University
 Abstract/Description

In this dissertation, I present a tabledriven streaming XML (Extensible Markup Language) parsing and searching technique, called TDX, and investigate related techniques. TDX expedites XML parsing, validation and searching by prerecording the states of an XML parser in tabular forms and by utilizing an efficient runtime streaming parsing engine based on a twostack pushdown automaton. The parsing tables are automatically produced from the XML schemas or from the WSDL (Web Services...
Show moreIn this dissertation, I present a tabledriven streaming XML (Extensible Markup Language) parsing and searching technique, called TDX, and investigate related techniques. TDX expedites XML parsing, validation and searching by prerecording the states of an XML parser in tabular forms and by utilizing an efficient runtime streaming parsing engine based on a twostack pushdown automaton. The parsing tables are automatically produced from the XML schemas or from the WSDL (Web Services Description Language) service descriptions. Because the schema constraints and XPath expressions are preencoded in a parsing table, the approach effectively implements a schemaspecific XML parser and/or query processor that combines parsing, validation and search into a single pass. Moreover, the runtime parsing engine is independent of XML schemas and XPath query expressions, parsing can be populated onthefly to the runtime engine, thus TDX efficiently eliminates the recompilation and redeployment requirements of schemaspecific parsers to address the schema changes. Similarly, different XPath queries can also be preprocessed at compile time and populated onthefly to the TDX searching engine without runtime overhead. To construct the parsing tables, we developed a set of mapping rules that translate XML schemas to augmented grammars. The augmented grammars support the full expressive power of the W3C XML Schema by introducing permutation phrase grammars and multioccurrence phrase grammars. The augmented grammars are suitable to construct a predicative parsing table. The predictive parsing table constructed from the augmented grammars can be integrated into the parser at any time to maximize the performance or be populated onthefly at runtime and address schema changes efficiently. Because parsing tables or searching tables are preprocessed at compile time, and looking up the tables at runtime is deterministic and takes constant time, TDX efficiently implements a single pass, predictive validating parser without backtracking or function calling overheads. Our experimental results show a significant performance improvement compared to widely used XML parsers, either validating and nonvalidating, and to XML query processors.
Show less  Date Issued
 2012
 Identifier
 FSU_migr_etd5297
 Format
 Thesis
 Title
 The Representation of Association Semantics with Annotations in a Biodiversity Informatics System.
 Creator

Gaitros, Daivd A., Riccardi, Greg, Ronquist, Fredrik, Engelen, Robert van, Srinivasan, Ashok, Department of Computer Science, Florida State University
 Abstract/Description

A specialized variation of associations for biodiversity data is defined and developed that makes the capture and discovery of information about biological images easier and more efficient. Biodiversity is the study of the diversity of plants and animals within a given region. Storing, understanding, and retrieving biodiversity data is a complex problem. Biodiversity experts disagree on the structure and the basic ontologies. Much of the knowledge on this subject is contained in private...
Show moreA specialized variation of associations for biodiversity data is defined and developed that makes the capture and discovery of information about biological images easier and more efficient. Biodiversity is the study of the diversity of plants and animals within a given region. Storing, understanding, and retrieving biodiversity data is a complex problem. Biodiversity experts disagree on the structure and the basic ontologies. Much of the knowledge on this subject is contained in private collections, paper notebooks, and the minds biologists. Collaboration among scientists is still problematic because of the logistics involved in sharing collections. This research adds value to image repositories by collecting and publishing semantically rich user specified associations among images and other objects. Current database and annotation techniques rely on structured data sets and ontologies to make storing, associating, and retrieving data efficient and reliable. A problem with biodiversity data is that the information is usually stored as adhoc text associated with nonstandardized schemas and ontologies. This research developed a method that allows the storage of adhoc semantic associations through a complex relationship of working sets, phylogenetic character states, and image annotations. MorphBank is a collaborative research project supported by an NSF BDI grant (0446224  $2,249,530.00) titled "Web Image Database Technology for Comparative Morphology and Biodiversity Research". MorphBank is an online museumquality collection of biological images that facilitates the collaboration of biologists from around the world. This research proves the viability of using association semantics through annotations of biodiversity informatics for storing and discovery of new information.
Show less  Date Issued
 2007
 Identifier
 FSU_migr_etd0437
 Format
 Thesis
 Title
 Reducing the WCET of Applications on Low End Embedded Systems.
 Creator

Zhao, Wankang, Whalley, David, Srivastava, Anuj, Baker, Theodore P., Engelen, Robert A. van, Gallivan, Kyle, Department of Computer Science, Florida State University
 Abstract/Description

Applications in embedded systems often need to meet specified timing constraints. It is advantageous to not only calculate the WorstCase Execution Time (WCET) of an application, but to also perform transformations that attempt to reduce the WCET, since an application with a lower WCET will be less likely to violate its timing constraints. A compiler has been integrated with a timing analyzer to obtain the WCET of a program on demand during compilation. This environment is used to investigate...
Show moreApplications in embedded systems often need to meet specified timing constraints. It is advantageous to not only calculate the WorstCase Execution Time (WCET) of an application, but to also perform transformations that attempt to reduce the WCET, since an application with a lower WCET will be less likely to violate its timing constraints. A compiler has been integrated with a timing analyzer to obtain the WCET of a program on demand during compilation. This environment is used to investigate three different types of compiler optimization techniques to reduce WCET. First, an interactive compilation system has been developed that allows a user to interact with a compiler and get feedback regarding the WCET. In addition, a genetic algorithm is used to automatically search for an effective optimization phase sequence to reduce the WCET. Second, a WCET code positioning optimization has been investigated that uses worstcase path information to reorder basic blocks so that the branch penalties can be reduced in the worstcase path. Third, WCET path optimizations, similar to frequent path optimizations, are used to reduce the WCET. There are several contributions to this work. To the best of our knowledge, this is the first compiler that interacts with a timing analyzer to use WCET predictions during the compilation of applications. The dissertation demonstrates that a genetic algorithm search can find an optimization sequence that simultaneously improves both WCET and code size. New compiler optimizations have been developed that use WC path information from a timing analyzer. The results show that the WCET code positioning algorithms typically find the optimal layout of the basic blocks with the minimal WCET. It is also shown that frequent path optimizations can be applied on WC paths using worstcase path information from a timing analyzer to reduce WCET. These new compiler optimizations described in this dissertation not only significantly reduce WCET, but also are completely automatic.
Show less  Date Issued
 2005
 Identifier
 FSU_migr_etd0528
 Format
 Thesis
 Title
 Application Configurable Processors.
 Creator

Zimmer, Christopher J., Whalley, David, Tyson, Gary, Engelen, Robert van, Department of Computer Science, Florida State University
 Abstract/Description

As the complexity requirements for embedded applications increase, the performance demands of embedded compilers also increase. Compiler optimizations, such as software pipelining and recurrence elimination, can significantly reduce execution time for applications, but these transformations require the use of additional registers to hold data values across one or more loop iterations. Compilers for embedded systems have difficulty exploiting these optimizations since they typically do not...
Show moreAs the complexity requirements for embedded applications increase, the performance demands of embedded compilers also increase. Compiler optimizations, such as software pipelining and recurrence elimination, can significantly reduce execution time for applications, but these transformations require the use of additional registers to hold data values across one or more loop iterations. Compilers for embedded systems have difficulty exploiting these optimizations since they typically do not have enough registers on an embedded processor to be able to apply the transformations. In this paper, we evaluate a new application configurable processor utilizing several different register structures which can enable these optimizations without increasing the architecturally addressable register storage requirements. Using this approach can lead to an improved execution time through enabled optimizations and reduced register pressure for embedded architectures.
Show less  Date Issued
 2006
 Identifier
 FSU_migr_etd0494
 Format
 Thesis
 Title
 The Design, Implementation, and Evaluation of a Reliable Multicast Protocol for Ethernet Switched Networks.
 Creator

Ding, Shiling, Yuan, Xin, Liu, Xiuwen, Engelen, Robert van, Department of Computer Science, Florida State University
 Abstract/Description

Recent advances in multicasting present new opportunities for improving communication performance for clusters of workstations. The standard IP multicast, however, only supports unreliable multicast, which is diffcult to use for building high level message passing routines. Thus, reliable multicast primitives must be implemented over the standard IP multicast to facilitate the use of multicast for high performance communication on clussters of workstations. In this paper, we present the...
Show moreRecent advances in multicasting present new opportunities for improving communication performance for clusters of workstations. The standard IP multicast, however, only supports unreliable multicast, which is diffcult to use for building high level message passing routines. Thus, reliable multicast primitives must be implemented over the standard IP multicast to facilitate the use of multicast for high performance communication on clussters of workstations. In this paper, we present the design, implementation, and evaluation of a reliable multicast protocol, called Mary Treebased Reliable Multicast Protocol(MTRMP), that we develop for efficient reliable multicast on Ethernet switched clusters. MTRMP eliminates the ACKimplosion problem and achieves scalability by organizing receivers in a logical tree structure. To achieve high throughput, MTRMP distributes the error recovery task to receivers and allows the sender to move ahead without ensuring that all receivers receive a packet. The results of our evaluation show that MTRMP performs better than other existing reliable multicast protocols on Ethernet switched networks.
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd0732
 Format
 Thesis
 Title
 Developing a Bioinformatics Utility Belt to Eliminate Search Redundancy from the EverGrowing Databases.
 Creator

Taylor, Misha, Engelen, Robert van, Swofford, David, Baker, Theodore, Thompson, Steven M., Department of Computer Science, Florida State University
 Abstract/Description

Biological databases are growing at an exponential rate. Designing algorithms to deal with the inherent redundancy in these databases which can cope with the overwhelming amount of data returned from similarity searches is an active area of research. This paper presents an overview of a realworld problem related to biological database searching, outlining how a human expert solves this problem. Then, several bioinformatics approaches are presented from the literature, forming a "utility belt...
Show moreBiological databases are growing at an exponential rate. Designing algorithms to deal with the inherent redundancy in these databases which can cope with the overwhelming amount of data returned from similarity searches is an active area of research. This paper presents an overview of a realworld problem related to biological database searching, outlining how a human expert solves this problem. Then, several bioinformatics approaches are presented from the literature, forming a "utility belt" which might be used to solve the problem computationally.
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd0345
 Format
 Thesis
 Title
 Internet Computing with Matlab.
 Creator

Gokarn, Arthi, Van Engelen, Robert A., Yuan, Xin, Hawkes, Lois Wright, Department of Computer Science, Florida State University
 Abstract/Description

The purpose of this project is to create MATLAB applications that use the capabilities of the World Wide Web to send data to a remote server for computation and to display the results in on a local MATLAB® application. The data is sent to and received from the remote application using gSOAP. Data can be sent to a remote server, which need not have a copy of MATLAB installed. This is accomplished by calling gSOAP functions from MEXfiles written in the C programming language. The MEX interface...
Show moreThe purpose of this project is to create MATLAB applications that use the capabilities of the World Wide Web to send data to a remote server for computation and to display the results in on a local MATLAB® application. The data is sent to and received from the remote application using gSOAP. Data can be sent to a remote server, which need not have a copy of MATLAB installed. This is accomplished by calling gSOAP functions from MEXfiles written in the C programming language. The MEX interface code and accompanying C code is automatically generated by gSOAP. The use of the gSOAP compiler (which is part of this project) simplifies this task, which otherwise requires users to program most of the data communications at a lower level. This project specializes on efficient data representations for communication with Web services, such as sparse numerical matrix representations. The diagram shows the visualization of weather forecast data through MATLAB.
Show less  Date Issued
 2004
 Identifier
 FSU_migr_etd4206
 Format
 Thesis
 Title
 Realtime Computing with the Parareal Algorithm.
 Creator

Christopherr.Harden, Peterson, Janet, Gunzburger, Max, Van Engelen, Robert, Department of Scientific Computing, Florida State University
 Abstract/Description

This thesis presents and evaluates a particular algorithm used for the real time computations of time dependent ordinary and partial differential equations which employs a parallelization strategy over the temporal domain. We also discuss the coupling of this method with another popular technique used for real time computations, model reduction, which will be shown to provide more gains than either method alone. In particular, we look at reduced order modeling based on proper orthogonal...
Show moreThis thesis presents and evaluates a particular algorithm used for the real time computations of time dependent ordinary and partial differential equations which employs a parallelization strategy over the temporal domain. We also discuss the coupling of this method with another popular technique used for real time computations, model reduction, which will be shown to provide more gains than either method alone. In particular, we look at reduced order modeling based on proper orthogonal decompositions. We present some applications in terms of solving time dependent nonlinear partial diï¬erential equations and solving these equations with a coupled approach of combining model reduction and the parareal algorithm . The performance of this method, both numerically and computationally, is discussed in terms of the gains in speedup and efficiency, and in terms of the scalability of the parallelization of the temporal domain on a larger and larger set of compute nodes or processors.
Show less  Date Issued
 2008
 Identifier
 FSU_migr_etd4272
 Format
 Thesis
 Title
 There & Never Back Again: A WalkonSubdomains Tale.
 Creator

Hamlin, Preston William, Mascagni, Michael, Haiduc, Sonia, van Engelen, Robert, Florida State University, College of Arts and Sciences, Department of Computer Science
 Abstract/Description

Simulation software is used in a multitude of industry and academic fields, in an assortment of scopes. One might be interested in gravitation of celestial bodies, or field structures of molecular interactions. The scale to which these simulations can grow demands an equally scalable computational mechanism. Traditional and even accelerated solvers suffer from a lack of general scalability, depending on multiple input aspects and recursive refinement. Monte Carlo solvers offer a highly...
Show moreSimulation software is used in a multitude of industry and academic fields, in an assortment of scopes. One might be interested in gravitation of celestial bodies, or field structures of molecular interactions. The scale to which these simulations can grow demands an equally scalable computational mechanism. Traditional and even accelerated solvers suffer from a lack of general scalability, depending on multiple input aspects and recursive refinement. Monte Carlo solvers offer a highly scalable computational mechanism, as it is not prone to the curse of dimensionality and the error can be driven down simply by taking more samples. In the course of refactoring such a Monte Carlo simulation software artefact, several anomalies were noted in its implementation structure. Through attempts at remediating the undesirable behaviour, a general problem of susceptibility was discovered for the WalkonSubdomains family of algorithms.
Show less  Date Issued
 2016
 Identifier
 FSU_FA2016_Hamlin_fsu_0071N_13643
 Format
 Thesis
 Title
 Improving Monte Carlo Linear Solvers Through Better Iterative Processes.
 Creator

Aggarwal, Vikram, Srinivasan, Ashok, Mascagni, Michael, Engelen, Robert van, Department of Computer Science, Florida State University
 Abstract/Description

Monte Carlo (MC) linear solvers are fundamentally based on the ability to estimate a matrixvector product, using a random sampling process. They use the fact that deterministic stationary iterative processes to solve linear systems can be written as sums of a series of matrixvector products. Replacing the deterministic matrixvector products with MC estimates yields a MC linear solver. While MC linear solvers have a long history, they did not gain widespread acceptance in the numerical...
Show moreMonte Carlo (MC) linear solvers are fundamentally based on the ability to estimate a matrixvector product, using a random sampling process. They use the fact that deterministic stationary iterative processes to solve linear systems can be written as sums of a series of matrixvector products. Replacing the deterministic matrixvector products with MC estimates yields a MC linear solver. While MC linear solvers have a long history, they did not gain widespread acceptance in the numerical linear algebra community, for the following reasons: (i) their slow convergence, and (ii) the limited class of problems for which they converged. Slow convergence is caused by both, the MC process for estimating the matrixvector product, and the stationary process underlying the MC technique, while the latter is caused primarily by the stationary iterative process. The MC linear algebra community made significant advances in reducing the errors from slow convergence through better techniques for estimating the matrixvector product, and also through a variety of variance reduction techniques. However, use of MC linear algebra is still limited, since the techniques use only stationary iterative processes resulting from a diagonal splitting (for example, Jacobi), which have poor convergence properties. The reason for using such splittings is because it is believed that efficient MC implementations of more sophisticated splittings is not feasible. Consequently, little effort has been placed by the MC community on addressing this important issue. In this thesis, we address the issue of improving the iterative process underlying the MC linear solvers. In particular, we demonstrate that the reasons for considering only diagonal splitting is not valid, and show a specific nondiagonal splitting for which an efficient MC implementation is feasible, even though it superficially suffers from the drawbacks for which nondiagonal splittings were not considered by the MC linear algebra community. We also show that conventional techniques to improve deterministic iterative processes, such as the Chebyshev method, show promise in improving MC techniques too. Despite such improvements, we do not expect MC techniques to be competitive with modern deterministic techniques to accurately solve linear systems. However, MC techniques have the advantage that they can obtain approximate solutions fast. For example, an estimate of the solution can be obtained in constant time, independent of the size of the matrix, if we permit a small amount of preprocessing. There are other advantages too, such as the ability to estimate specific components of a solution, and latency and fault tolerance in parallel and distributed environments. There are a variety of applications where fast, approximate, solutions are useful, such as preconditioning, graph partitioning, and information retrieval. Thus MC linear algebra techniques are of relevance to important classes of applications. We demonstrate this by showing its benefits in an application to dynamic load balancing of parallel computations.
Show less  Date Issued
 2004
 Identifier
 FSU_migr_etd0017
 Format
 Thesis
 Title
 Extensions and Optimizations to the Scalable, Parallel Random Number Generators Library.
 Creator

Parker, Jason, Mascagni, Michael, Srinivasan, Ashok, Yasinsac, Alec, Van Engelen, Robert, Department of Physics, Florida State University
 Abstract/Description

With growing interest in devices that utilize the spin degree of freedom of the charge carriers, there is an extensive research effort into materials with high spin polarization. Two types of materials that have attracted particular attention are the half metallic (HM) ferromagnets and dilute magnetic semiconductors (DMS). I report on a series of experiments which probe the level spin polarization in HM CrO2 and the DMS Ga1 −xMnxAs. In order to accurately determine the spin polarization, P,...
Show moreWith growing interest in devices that utilize the spin degree of freedom of the charge carriers, there is an extensive research effort into materials with high spin polarization. Two types of materials that have attracted particular attention are the half metallic (HM) ferromagnets and dilute magnetic semiconductors (DMS). I report on a series of experiments which probe the level spin polarization in HM CrO2 and the DMS Ga1 −xMnxAs. In order to accurately determine the spin polarization, P, of CrO2 in a realistic device structure I have developed a method to chemically modify the surface of CrO2 to obtain a consistent and reproducible barrier, which preserves the bulk spin polarization. Using this method I have been able to produce high quality CrO2 based planar junctions with either superconducting (SC) or ferromagnetic (FM) counter electrodes. Analysis of both zero field and Zeeman split conductance data from CrO2SC junctions consistently yield P values close to 100%, providing unambiguous evidence that the high P of CrO2 is maintained at and across an artificial barrier in a realistic device structure. Magnetic tunnel junctions (MTJ) fabricated with CrO2 and Co electrodes display a low field inverse magnetoresistance with a maximum magnetoresistance (MR) of 24% occurring at 5K. The origin of this inverse sign is discussed in terms of selective spin transport due to variations in the type of interfacial bonding between the electrodes and the barrier. A strong linear bias dependence of the MR, similar to what is seen in the CrO2SC junctions, is observed. This linear background is attributed to a continuum of inelastic states in the barrier region. Measurements of the MR as a function of temperature display a rapid decrease in MR as temperature increases. Additionally we have carried out the first direct measurement of the degree of spin polarization of the magnetic semiconductor Ga1 −xMnxAs using Andreev reflection spectroscopy. Analysis of the conductance spectra of high transparency Ga0.95Mn0.05As/Ga junctions consistently yields an intrinsic value for P greater than 85%. Our experiments also revealed an extreme sensitivity of the measured spin polarization to the nature and quality of the interface for this material.
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd2231
 Format
 Thesis
 Title
 Extensions and Optimizations to the Scalable, Parallel Random Number Generators Library.
 Creator

Parker, Jason, Mascagni, Michael, Srinivasan, Ashok, Yasinsac, Alec, Van Engelen, Robert, Department of Computer Science, Florida State University
 Abstract/Description

This work will examine enhancements to the library for scalable, parallel pseudorandom number generation (SPRNG). SPRNG uses parameterization to produce many streams of random numbers with emphasis on parallel Monte Carlo methods. We extend the previous work to enable random access to these streams. This new method for generating streams improves both functionality and intuition of interface. Also considered are a few memory optimizations to the SPRNG library.
 Date Issued
 2003
 Identifier
 FSU_migr_etd2236
 Format
 Thesis
 Title
 Algorithms for Solving Linear Differential Equations with Rational Function Coefficients.
 Creator

Imamoglu, Erdal, van Hoeij, Mark, van Engelen, Robert, Agashe, Amod S. (Amod Sadanand), Aldrovandi, Ettore, Aluffi, Paolo, Florida State University, College of Arts and Sciences...
Show moreImamoglu, Erdal, van Hoeij, Mark, van Engelen, Robert, Agashe, Amod S. (Amod Sadanand), Aldrovandi, Ettore, Aluffi, Paolo, Florida State University, College of Arts and Sciences, Department of Mathematics
Show less  Abstract/Description

This thesis introduces two new algorithms to find hypergeometric solutions of second order regular singular differential operators with rational function or polynomial coefficients. Algorithm 3.2.1 searches for solutions of type: exp(∫ r dx) ⋅ ₂F₁ (a₁,a₂;b₁;f) and Algorithm 5.2.1 searches for solutions of type exp(∫ r dx) (r₀ ⋅ ₂F₁(a₁,a₂;b₁;f) + r₁ ⋅ ₂F´₁ (a₁,a₂;b₁;f)) where f, r, r₀, r₁ ∈ ℚ̅(̅x̅)̅ and a₁,a₂,b₁ ∈ ℚ and denotes the Gauss hypergeometric function. The algorithms use modular...
Show moreThis thesis introduces two new algorithms to find hypergeometric solutions of second order regular singular differential operators with rational function or polynomial coefficients. Algorithm 3.2.1 searches for solutions of type: exp(∫ r dx) ⋅ ₂F₁ (a₁,a₂;b₁;f) and Algorithm 5.2.1 searches for solutions of type exp(∫ r dx) (r₀ ⋅ ₂F₁(a₁,a₂;b₁;f) + r₁ ⋅ ₂F´₁ (a₁,a₂;b₁;f)) where f, r, r₀, r₁ ∈ ℚ̅(̅x̅)̅ and a₁,a₂,b₁ ∈ ℚ and denotes the Gauss hypergeometric function. The algorithms use modular reduction, Hensel lifting, rational function reconstruction, and rational number reconstruction to do so. Numerous examples from different branches of science (mostly from combinatorics and physics) showed that the algorithms presented in this thesis are very effective. Presently, Algorithm 5.2.1 is the most general algorithm in the literature to find hypergeometric solutions of such operators. This thesis also introduces a fast algorithm (Algorithm 4.2.3) to find integral bases for arbitrary order regular singular differential operators with rational function or polynomial coefficients. A normalized (Algorithm 4.3.1) integral basis for a differential operator provides us transformations that convert the differential operator to its standard forms (Algorithm 5.1.1) which are easier to solve.
Show less  Date Issued
 2017
 Identifier
 FSU_SUMMER2017_Imamoglu_fsu_0071E_13942
 Format
 Thesis
 Title
 Hypergeometric Solutions of Linear Differential Equations with Rational Function Coefficients.
 Creator

Kunwar, Vijay Jung, Van Hoeij, Mark, Van Engelen, Robert A., Agashe, Amod, Aldrovandi, Ettore, Hironaka, Eriko, Petersen, Kathleen, Department of Mathematics, Florida State...
Show moreKunwar, Vijay Jung, Van Hoeij, Mark, Van Engelen, Robert A., Agashe, Amod, Aldrovandi, Ettore, Hironaka, Eriko, Petersen, Kathleen, Department of Mathematics, Florida State University
Show less  Abstract/Description

Let L be a second order linear differential equation with rational function coefficients. We want to find a solution (if that exists) of L in terms of 2F1hypergeometric function. This thesis presents two algorithms to find such solution in the following cases: 1. L has five regular singularities where at least one of them is logarithmic. 2. L has hypergeometric solution of degree three, i.e, L is solvable in terms of 2F1(a,b;c  f) where f is a rational function of degree three.
 Date Issued
 2014
 Identifier
 FSU_migr_etd9021
 Format
 Thesis
 Title
 Factoring Univariate Polynomials over the Rationals.
 Creator

Novocin, Andrew, Van Hoeij, Mark, Van Engelen, Robert, Agashe, Amod, Aldrovandi, Ettore, Aluﬃ, Paolo, Department of Mathematics, Florida State University
 Abstract/Description

This thesis presents an algorithm for factoring polynomials over the rationals which follows the approach of the van Hoeij algorithm. The key theoretical novelty in our approach is that it is et up in a way that will make it possible to prove a new complexity result for this algorithm which was actually observed on prior algorithms. One difference of this algorithm from prior algorithms is the practical improvement which we call early termination. Our algorithm should outperform prior...
Show moreThis thesis presents an algorithm for factoring polynomials over the rationals which follows the approach of the van Hoeij algorithm. The key theoretical novelty in our approach is that it is et up in a way that will make it possible to prove a new complexity result for this algorithm which was actually observed on prior algorithms. One difference of this algorithm from prior algorithms is the practical improvement which we call early termination. Our algorithm should outperform prior algorithms in many common classes of polynomials (including irreducibles).
Show less  Date Issued
 2008
 Identifier
 FSU_migr_etd2515
 Format
 Thesis
 Title
 Solving Linear Differential Equations in Terms of Hypergeometric Functions by ₂Descent.
 Creator

Fang, Tingting, Van Hoeij, Mark, Van Engelen, Robert A., Agashe, Amod, Aldrovandi, Ettore, Aluﬃ, Paolo, Department of Mathematics, Florida State University
 Abstract/Description

Let L be a linear ordinary differential equation with coefficients in C(x). This thesis presents algorithms to solve L in closed form. The key part of this thesis is 2descent method, which is used to reduce L to an equation that is easier to solve. The starting point is an irreducible L, and the goal of 2descent is to decide if L is projectively equivalent to another equation $\tilde{L}$ that is defined over a subfield C(f) of C(x). Although part of the mathematics for 2descent has already...
Show moreLet L be a linear ordinary differential equation with coefficients in C(x). This thesis presents algorithms to solve L in closed form. The key part of this thesis is 2descent method, which is used to reduce L to an equation that is easier to solve. The starting point is an irreducible L, and the goal of 2descent is to decide if L is projectively equivalent to another equation $\tilde{L}$ that is defined over a subfield C(f) of C(x). Although part of the mathematics for 2descent has already been treated before, a complete implementation could not be given because it involved a step for which we do not have a complete implementation. Our key novelty is to give an approach that is fully implementable. We describe and implement the algorithm for order 2, and show by examples that the same also work for higher order. By doing 2descent for L, the number of true singularities drops to at most n/2 + 2 (n is the number of true singularities of L). This provides us ways to solve L in closed form(e.g.in terms of hypergeometric funtions).
Show less  Date Issued
 2012
 Identifier
 FSU_migr_etd5350
 Format
 Thesis
 Title
 Finding All Bessel Type Solutions for Linear Differential Equations with Rational Function Coefficients.
 Creator

Yuan, Quan, Van Hoeij, Mark, Van Engelen, Robert A., Agashe, Amod, Aldrovandi, Ettore, Aluﬃ, Paolo, Department of Mathematics, Florida State University
 Abstract/Description

A linear differential equation with rational function coefficients has a Bessel type solution when it is solvable in terms of Bessel functions, change of variables, algebraic operations and exponential integrals. For second order equations with rational function coefficients, the function f of change of variables must be a rational function or the square root of a rational function. An algorithm was given by Debeerst, van Hoeij, and Koepf, that can compute Bessel type solutions if and only if...
Show moreA linear differential equation with rational function coefficients has a Bessel type solution when it is solvable in terms of Bessel functions, change of variables, algebraic operations and exponential integrals. For second order equations with rational function coefficients, the function f of change of variables must be a rational function or the square root of a rational function. An algorithm was given by Debeerst, van Hoeij, and Koepf, that can compute Bessel type solutions if and only if change of variables is a rational function. In this thesis we extend this work to the square root case, resulting in a complete algorithm to find all Bessel type solutions. This algorithm can be easily extended to a Whittaker/Kummer solver. Combine the two algorithms, we can get a complete algorithm for all 0F1 and 1F1 type solutions. We also use our algorithm to analyze the relation between Bessel functions and Heun functions.
Show less  Date Issued
 2012
 Identifier
 FSU_migr_etd5296
 Format
 Thesis
 Title
 Assimilation of Airs Radiance Observations into a Mesoscale Model: Adjoint Development, Quality Control, and Assimilation Results.
 Creator

Carrier, Matthew J. (Matthew James), Zou, Xiaolei, Van Engelen, Robert A., Hart, Robert, Bourassa, Mark A., Liu, Guosheng, Department of Earth, Ocean and Atmospheric Sciences,...
Show moreCarrier, Matthew J. (Matthew James), Zou, Xiaolei, Van Engelen, Robert A., Hart, Robert, Bourassa, Mark A., Liu, Guosheng, Department of Earth, Ocean and Atmospheric Sciences, Florida State University
Show less  Abstract/Description

Radiance data obtained from NASA's Advanced Infrared Sounder (AIRS) is used in an attempt to improve the mesoscale prediction of temperature and moisture using one and fourdimensional variational data assimilation (1D/4DVar). The joint National Center for Atmospheric Research and Pennsylvania State University fifthgeneration mesoscale model (MM5) along with the Standalone AIRS Radiative Transfer Algorithm (SARTA) is selected for this project. This work aims to utilize AIRS "clearchannel...
Show moreRadiance data obtained from NASA's Advanced Infrared Sounder (AIRS) is used in an attempt to improve the mesoscale prediction of temperature and moisture using one and fourdimensional variational data assimilation (1D/4DVar). The joint National Center for Atmospheric Research and Pennsylvania State University fifthgeneration mesoscale model (MM5) along with the Standalone AIRS Radiative Transfer Algorithm (SARTA) is selected for this project. This work aims to utilize AIRS "clearchannel" radiances to enhance the firstguess analysis regarding the temperature and moisture content as a precursor to improving shortterm precipitation forecasts. The adjoint operator for SARTA has been derived and linked to the MM5 adjoint modeling system; a "clearchannel" identification scheme, which is compatible with SARTA, has been developed and verified; and a set of onedimensional variational data assimilation (1DVar) experiments have been done in order to determine the impact of AIRS channels on the vertical profiles of temperature and moisture. Lastly, a preliminary 4DVar experiment is carried out to determine the impact of a limited number of clearchannel AIRS radiances on the prediction of temperature and moisture. An adjointsensitivity based forecast verification technique is used to compare the 4DVar forecast results to a control forecast.
Show less  Date Issued
 2008
 Identifier
 FSU_migr_etd4155
 Format
 Thesis
 Title
 FeistelInspired Scrambling Improves the Quality of Linear Congruential Generators.
 Creator

Aljahdali, Asia Othman, Mascagni, Michael, Duke, D. W. (Dennis W.), Srinivasan, Ashok (Professor of Computer Science), van Engelen, Robert, Florida State University, College of...
Show moreAljahdali, Asia Othman, Mascagni, Michael, Duke, D. W. (Dennis W.), Srinivasan, Ashok (Professor of Computer Science), van Engelen, Robert, Florida State University, College of Arts and Sciences, Department of Computer Science
Show less  Abstract/Description

Pseudorandom number generators (PRNGs) are an essential tool in many areas, including simulation studies of stochastic processes, modeling, randomized algorithms, and games. The performance of any PRNGs depends on the quality of the generated random sequences; they must be generated quickly and have good statistical properties. Several statistical test suites have been developed to evaluate a single stream of random numbers, such as TestU01, DIEHARD, the tests from the SPRNG package, and a...
Show morePseudorandom number generators (PRNGs) are an essential tool in many areas, including simulation studies of stochastic processes, modeling, randomized algorithms, and games. The performance of any PRNGs depends on the quality of the generated random sequences; they must be generated quickly and have good statistical properties. Several statistical test suites have been developed to evaluate a single stream of random numbers, such as TestU01, DIEHARD, the tests from the SPRNG package, and a set of tests designed to evaluate bit sequences developed at NIST. TestU01 provides batteries of test that are sets of the mentioned suites. The predefined batteries are SmallCrush (10 tests, 16 pvalues) that runs quickly, Crush (96 tests, 187 pvalues) and BigCrush (106 tests, 2254 pvalues) batteries that take longer to run. Most pseudorandom generators use recursion to produce sequences of numbers that appear to be random. The linear congruential generator is one of the wellknown pseudorandom generators, the next number in the random sequences is determined by the previous one. The recurrences start with a value called the seed. Each time a recurrence starts with the same seed the same sequence is produced. This thesis develops a new pseudorandom number generation scheme that produces random sequences with good statistical properties via scrambling linear congruential generators. The scrambling technique is based on a simplified version of Feistel network, which is a symmetric structure used in the construction of cryptographic block ciphers. The proposed research seeks to improve the quality of the linear congruential generators’ output streams and to break up the regularities existing in the generators.
Show less  Date Issued
 2017
 Identifier
 FSU_SUMMER2017_Aljahdali_fsu_0071E_13941
 Format
 Thesis
 Title
 Computational Transformation Between Different Symbolic Representations of BK Products of Fuzzy Relations.
 Creator

Hoang, Ha V. (Ha Viet), Kohout, Ladislav J., Seppala, Mika, Hawkes, Lois W., Levitz, Hilbert, Van Engelen, Robert, Department of Computer Science, Florida State University
 Abstract/Description

Fuzzy relational calculi based on BK products of relations have representational and computational means for handling both concrete numerical representations of relations and symbolic manipulation of relations. BK calculus of relations together with fast fuzzy relational algorithms allows concrete numerical representations of relations to be used extensively in applications. On the other hand, when enriched by relational inequalities like BK Bootstrap or combined with other theories such as...
Show moreFuzzy relational calculi based on BK products of relations have representational and computational means for handling both concrete numerical representations of relations and symbolic manipulation of relations. BK calculus of relations together with fast fuzzy relational algorithms allows concrete numerical representations of relations to be used extensively in applications. On the other hand, when enriched by relational inequalities like BK Bootstrap or combined with other theories such as generalized morphisms, high level symbolic forms of relations can be used for symbolic manipulation of relations that have been abstracted from numerical representations. Furthermore, symbolic formulas of relations can be handled equationally. Equations over BKproducts can characterize relational properties in a universal way. The research in this dissertation focuses on symbolic manipulations of BK products of fuzzy relations. We have developed as a proofofconcept an automated tool that works with various representational forms of relations and facilitates transformations among them. Major contribution that this system brings into the field is that, it provides a link between numerical and symbolic representations of relations, which can substantially extend the applicability of fuzzy relations. The pilot implementation of the tool consists of two systems. At a high level of general fuzzy logic systems, the first system transforms BKproduct formulas syntactically between three notational forms: matrix form, set form and predicate form. We have defined for each kind of BKproduct representations a treetype data structure, called a notational tree. All transformations are then carried out by set of transformational algorithms among the notational trees of BK representational forms. At a lower level of tnorm based residuated logic systems (BL logic), we have developed a second system which is a term rewriting theorem prover/checker that validates and generates proofs for theorems of BK relational calculi. For each given theorem, a derivation tree will first be generated. A matching of any node in that tree with the theorem's conclusion will validate it. We proposed a generateandmatch algorithm based on a breadthfirstsearch navigation process through theorems' derivation trees which guarantees a loopfree result for any derivable theorem (in a given theory). The original version of this algorithm has been improved further by applying a humanlike proof strategy, which we called distancefirstsearch and optimized distancefirstsearch algorithms. These optimized versions improve the performance of our system significantly, reducing both number of logical inferences and the CPU's time required. The experiments also showed that proofs in BK calculi are significantly shorter than in predicate calculus of BL logic. Interestingly enough, proofs generated by the tool are the same as those done by hand. This illustrates the successfulness of our humanlike strategy.
Show less  Date Issued
 2007
 Identifier
 FSU_migr_etd4020
 Format
 Thesis
 Title
 Improving Processor Efficiency Through Enhanced Instruction Fetch.
 Creator

Hines, Stephen R. (Stephen Roderick), Whalley, David, Tyson, Gary, Erlebacher, Gordon, Van Engelen, Robert, Kumar, Piyush, Wang, Andy, Department of Computer Science, Florida...
Show moreHines, Stephen R. (Stephen Roderick), Whalley, David, Tyson, Gary, Erlebacher, Gordon, Van Engelen, Robert, Kumar, Piyush, Wang, Andy, Department of Computer Science, Florida State University
Show less  Abstract/Description

Instruction fetch is an important pipeline stage for embedded processors, as it can consume a significant fraction of the total processor energy. This dissertation describes the design and implementation of two new fetch enhancements that seek to improve overall energy efficiency without any performance tradeoff. Instruction packing is a combination architectural/compiler technique that leverages code redundancy to reduce energy consumption, code size, and execution time. Frequently occurring...
Show moreInstruction fetch is an important pipeline stage for embedded processors, as it can consume a significant fraction of the total processor energy. This dissertation describes the design and implementation of two new fetch enhancements that seek to improve overall energy efficiency without any performance tradeoff. Instruction packing is a combination architectural/compiler technique that leverages code redundancy to reduce energy consumption, code size, and execution time. Frequently occurring instructions are placed into a small instruction register file (IRF), which requires less energy to access than an L1 instruction cache. Multiple instruction register references are placed in a single packed instruction, leading to reduced cache accesses and static code size. Hardware register windows and compiler optimizations tailored for instruction packing yield greater reductions in fetch energy consumption and static code size. The Lookahead Instruction Fetch Engine (LIFE) is a microarchitectural technique designed to exploit the regularity present in instruction fetch. The nucleus of LIFE is the Tagless Hit Instruction Cache (THIC), a small cache that assists the instruction fetch pipeline stage as it efficiently captures information about both sequential and nonsequential transitions between instructions. THIC provides a considerable savings in fetch energy without incurring the performance penalty normally associated with small filter instruction caches. Furthermore, THIC makes the common case (cache hit) more energy efficient by making the tag check unnecessary. LIFE extends THIC by making use of advanced control flow metadata to further improve utilization of fetchassociated structures such as the branch predictor, branch target buffer, and return address stack. LIFE enables significant reductions in total processor energy consumption with no impact on application execution times even for the most aggressive powersaving configuration. Both IRF and LIFE (including THIC) improve overall processor efficiency by actively recognizing and exploiting the common properties of instruction fetch.
Show less  Date Issued
 2008
 Identifier
 FSU_migr_etd4036
 Format
 Thesis
 Title
 A Grid Computing Infrastructure for Monte Carlo Applications.
 Creator

Li, Yaohang, Mascagni, Michael, Peters, Michael H., Nolder, Craig, Whalley, David, Van Engelen, Robert, Yuan, Xin, Department of Computer Science, Florida State University
 Abstract/Description

Monte Carlo applications are widely perceived as computationally intensive but naturally parallel. Therefore, they can be effectively executed on the grid using the dynamic bagofwork model. We improve the efficiency of the subtaskscheduling scheme by using an NoutofM strategy, and develop a Monte Carlospecific lightweight checkpoint technique, which leads to a performance improvement for Monte Carlo grid computing. Also, we enhance the trustworthiness of Monte Carlo gridcomputing...
Show moreMonte Carlo applications are widely perceived as computationally intensive but naturally parallel. Therefore, they can be effectively executed on the grid using the dynamic bagofwork model. We improve the efficiency of the subtaskscheduling scheme by using an NoutofM strategy, and develop a Monte Carlospecific lightweight checkpoint technique, which leads to a performance improvement for Monte Carlo grid computing. Also, we enhance the trustworthiness of Monte Carlo gridcomputing applications by utilizing the statistical nature of Monte Carlo and by cryptographically validating intermediate results utilizing the random number generator already in use in the Monte Carlo application. All these techniques lead to our implementation of a gridcomputing infrastructure – GCIMCA (GridComputing Infrastructure for Monte Carlo applications), which is based on Globus and the SPRNG (Scalable Parallel Random Number Generators) library. GCIMCA intends to provide trustworthy gridcomputing services for largescale and highperformance distributed Monte Carlo computations. We apply Monte Carlo applications to GCIMCA to show the capability of our techniques. These applications include the gridbased Monte Carlo integration and a "reallife" Monte Carlo application  the gridbased hybrid Molecular Dynamics (MD)/Brownian Dynamics (BD) application for simulating the longtime, non equilibrium dynamics of receptorligand interactions. Our preliminary results show that our techniques and infrastructure can achieve significant speedup, efficiency, accuracy, and trustworthiness for gridbased Monte Carlo application
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd3079
 Format
 Thesis
 Title
 Enhanced Security for Mobile Agent Systems.
 Creator

McDonald, Jeffrey T. (Jeffrey Todd), Yasinsac, Alec, Huckaba, Sam, Murmester, Michael, Hawkes, Lois, Van Engelen, Robert, Department of Computer Science, Florida State University
 Abstract/Description

Researchers agree that protecting a standalone autonomous mobile agent with softwareonly approaches remains difficult. In this thesis, we produce several results that enhance mobile agent security and provide generalized code protection. Generalized Black Box and White Box Program Protection. We provide a novel technique for hiding a candidate program's input/output relationships by using a data encryption padding technique. This method provides general program/circuit protection and relies...
Show moreResearchers agree that protecting a standalone autonomous mobile agent with softwareonly approaches remains difficult. In this thesis, we produce several results that enhance mobile agent security and provide generalized code protection. Generalized Black Box and White Box Program Protection. We provide a novel technique for hiding a candidate program's input/output relationships by using a data encryption padding technique. This method provides general program/circuit protection and relies on the semantic security strength found in common data encryption ciphers. For white box security, we semantically protect the whitebox source code/gate structure information for relevant program classes defined by bounded input size. By using simple Boolean canonical circuit forms, we create an obfuscation technique that effectively hides all information regarding the source code or circuit gate structure. Leveraging our whitebox results, we demonstrate how to embed an encryption key in programs that have small input size with measurable security. Analyzing Mobile Code Protection Schemes and Tamperproofing. We consider programmatic intent protection for mobile agents and pose a new model for obfuscated code security based on random programs. We also lay foundations for a new code protection methodology for mobile agents based on techniques used in the data encryption field. Specifically, we employ circuit encryption techniques that use combined subcircuit permutation and substitution. Trust Framework for Mobile Agents and Application Security Models. We develop a novel framework to capture principles and trust relationships specific to the mobile agent paradigm. Application designers can also provide initial trust conditions to characterize the mobile execution environment; we seed a mobile interaction trust database with these conditions. We apply these models in context to our trust framework and show their relevance in designing secure mobile agent applications. MultipleAgent Protection Schemes. Multiple agents provide greater capability for security in mobile contexts. We develop architecture for mobility utilizing hybrid secure multiparty computation models, trusted highspeed threshold servers, and multiple agents. We also develop a novel approach to deal with colluding malicious hosts in context to data state integrity attacks.
Show less  Date Issued
 2006
 Identifier
 FSU_migr_etd2581
 Format
 Thesis
 Title
 Metrics and Techniques to Guide Software Development.
 Creator

Datta, Subhajit, Engelen, Robert van, Douglas, Ian, Hawkes, Lois, Baker, Theodore, Schwartz, Daniel, Mascagni, Michael, Department of Computer Science, Florida State University
 Abstract/Description

The objective of my doctoral dissertation research is to formulate, implement, and validate metrics and techniques towards perceiving some of the influences on software development, predicting the impact of user initiated changes on a software system, and prescribing guidelines to aid decisions affecting software development. Some of the topics addressed in my dissertation are: Analyzing the extent to which changing requirements affect a system's design, how the delegation of responsibilities...
Show moreThe objective of my doctoral dissertation research is to formulate, implement, and validate metrics and techniques towards perceiving some of the influences on software development, predicting the impact of user initiated changes on a software system, and prescribing guidelines to aid decisions affecting software development. Some of the topics addressed in my dissertation are: Analyzing the extent to which changing requirements affect a system's design, how the delegation of responsibilities to software components can be guided, how Aspect Oriented Programming (AOP) may be combined with Object Oriented Programming (OOP) to best deliver a system's functionality, whether and how characteristics of a system's design are influenced by a outsourced and offshore development. The metrics and techniques developed in my dissertation serve as heuristics across the software development life cycle, helping practitioners evaluate options and take decisions. By way of validation, the metrics and techniques have been applied to more than 10 real life software systems. To facilitate the application of the metrics and techniques, I have led the development of automated tools which can process software development artifacts such as code and Unified Modeling Language (UML) diagrams. The design and implementation of such tools are also discussed in the dissertation.
Show less  Date Issued
 2009
 Identifier
 FSU_migr_etd0824
 Format
 Thesis
 Title
 Enhancing Pattern Classification with Relational Fuzzy Neural Networks and Square BKProducts.
 Creator

Davis, Warren L., Kohout, Ladislav J., MeyerBäse, Anke, Engelen, Robert van, Lacher, R. Christopher, McDuffie, Ernest L., Department of Computer Science, Florida State University
 Abstract/Description

This research presents several important developments in pattern classification using fuzzy neural networks and BKSquare products and presents extensions to maxmin fuzzy neural network research. In this research, the max and min operations used in the fuzzy operations are replaced by more general tnorms and conorms, respectively. In addition, instead of the £ukasiewicz equivalence connective used in network of ReyesGarcia and Bandler, this research introduces a variety of equivalence...
Show moreThis research presents several important developments in pattern classification using fuzzy neural networks and BKSquare products and presents extensions to maxmin fuzzy neural network research. In this research, the max and min operations used in the fuzzy operations are replaced by more general tnorms and conorms, respectively. In addition, instead of the £ukasiewicz equivalence connective used in network of ReyesGarcia and Bandler, this research introduces a variety of equivalence connectives. A new software tool was developed specifically for this research, allowing for greater experimental flexibility, as well as some interesting options that allow greater exploitation of the merits of the relational BKsquare network. The effectiveness of this classifier is explored in the domain of phoneme recognition, taxonomic classification, and diabetes diagnosis. This research finds that the variance of fuzzy operations in equivalence and implication formulae, in complete divergence from classical composition, produces drastically different performance within this classifier. Techniques are presented that select effective fuzzy operation combinations. In addition, this classifier is shown to be effective at feature selection by using a technique which usually would be impractical with standard neural networks, but is made practical through the unique nature of this classifier.
Show less  Date Issued
 2006
 Identifier
 FSU_migr_etd0057
 Format
 Thesis
 Title
 Platforms for Hpjava: Runtime Support for Scalable Programming in Java.
 Creator

Lim, Sang Boem, Erlebacher, Gordon, Fox, Geoﬀrey C., Dennis, Larry, Schwartz, DanielG., Van Engelen, Robert A., Department of Computer Science, Florida State University
 Abstract/Description

The dissertation research is concerned with enabling parallel, highperformance computationâ in particular development of scientific software in the networkaware programming language, Java. Traditionally, this kind of computing was done in Fortran. Arguably, Fortran is becoming a marginalized language, with limited economic incentive for vendors to produce modern development environments, optimizing compilers for new hardware, or other kinds of associated software expected of by today's...
Show moreThe dissertation research is concerned with enabling parallel, highperformance computationâ in particular development of scientific software in the networkaware programming language, Java. Traditionally, this kind of computing was done in Fortran. Arguably, Fortran is becoming a marginalized language, with limited economic incentive for vendors to produce modern development environments, optimizing compilers for new hardware, or other kinds of associated software expected of by today's programmers. Hence, Java looks like a very promising alternative for the future. The dissertation will discuss in detail a particular environment called HPJava. HPJava is the environment for parallel programmingâespecially dataparallel scientific programmingâ in Java. Our HPJava is based around a small set of language extensions designed to support parallel computation with distributed arrays, plus a set of communication libraries. In particular the dissertation work will concentrate on issues related to the development of efficient run time support software for parallel languages extending an underlying objectoriented language. Two characteristic runtime communication libraries of HPJava are developed as an application level library and device level library. A highlevel communication API, Adlib, is developed as an application level communication library suitable for our HPJava. This communication library supports collective operations on distributed arrays. We include Java Object as one of the Adlib communication data types. So we fully support communication of intrinsic Java types, including primitive types, and Java object types. The Adlib library is developed on top of lowlevel communication library called mpjdev, designed to interface efficiently to the Java execution environment (virtual machine). The mpjdev API is a device level underlying communication library for HPJava. This library is developed to perform actual communication between processes. The mpjdev API is developed with HPJava in mind, but it is a standalone library and could be used by other ix systems. This can be implementing portably on network platforms and efficiently on parallel hardware. The dissertation describes the novelis sues in the interface and implementation of these libraries on different platforms, and gives comprehensive benchmark results on a parallel platform. All software developed in this project is available for free download from www.hpjava.org.
Show less  Date Issued
 2003
 Identifier
 FSU_migr_etd1353
 Format
 Thesis