Riemannian optimization is the task of finding an optimum of a real-valued function defined on a Riemannian manifold. Riemannian optimization has been a topic of much interest over the past few years due to many applications including computer vision, signal processing, and numerical linear algebra. The substantial background required to successfully design and apply Riemannian optimization algorithms is a significant impediment for many potential users. Therefore, multiple packages, such as Manopt (in Matlab) and Pymanopt (in Python), have been developed. This article describes ROPTLIB, a C++ library for Riemannian optimization. Unlike prior packages, ROPTLIB simultaneously achieves the following goals: (i) it has user-friendly interfaces in Matlab, Julia, and C++; (ii) users do not need to implement manifold- and algorithm-related objects; (iii) it provides efficient computational time due to its C++ core; (iv) it implements state-of-the-art generic Riemannian optimization algorithms, including quasi-Newton algorithms; and (v) it is based on object-oriented programming, allowing users to rapidly add new algorithms and manifolds.

BACKGROUND: Genomic-scale sequence alignments are increasingly used to infer phylogenies in order to better understand the processes and patterns of evolution. Different partitions within these new alignments (e.g., genes, codon positions, and structural features) often favor hundreds if not thousands of competing phylogenies. Summarizing and comparing phylogenies obtained from multi-source data sets using current consensus tree methods discards valuable information and can disguise potential methodological problems. Discovery of efficient and accurate dimensionality reduction methods used to display at once in 2- or 3- dimensions the relationship among these competing phylogenies will help practitioners diagnose the limits of current evolutionary models and potential problems with phylogenetic reconstruction methods when analyzing large multi-source data sets. We introduce several dimensionality reduction methods to visualize in 2- and 3-dimensions the relationship among competing phylogenies obtained from gene partitions found in three mid- to large-size mitochondrial genome alignments. We test the performance of these dimensionality reduction methods by applying several goodness-of-fit measures. The intrinsic dimensionality of each data set is also estimated to determine whether projections in 2- and 3-dimensions can be expected to reveal meaningful relationships among trees from different data partitions. Several new approaches to aid in the comparison of different phylogenetic landscapes are presented. RESULTS: Curvilinear Components Analysis (CCA) and a stochastic gradient decent (SGD) optimization method give the best representation of the original tree-to-tree distance matrix for each of the three- mitochondrial genome alignments and greatly outperformed the method currently used to visualize tree landscapes. The CCA + SGD method converged at least as fast as previously applied methods for visualizing tree landscapes. We demonstrate for all three mtDNA alignments that 3D projections significantly increase the fit between the tree-to-tree distances and can facilitate the interpretation of the relationship among phylogenetic trees. CONCLUSIONS: We demonstrate that the choice of dimensionality reduction method can significantly influence the spatial relationship among a large set of competing phylogenetic trees. We highlight the importance of selecting a dimensionality reduction method to visualize large multi-locus phylogenetic landscapes and demonstrate that 3D projections of mitochondrial tree landscapes better capture the relationship among the trees being compared.

A Riemannian manifold optimization strategy is proposed to facilitate the relaxation of the orthonormality constraint in a more natural way in the course of performing independent component analysis (ICA) that employs a mutual information-based source-adaptive contrast function. Despite the extensive development of manifold techniques catering to the orthonormality constraint, only a limited number of works have been dedicated to oblique manifold (OB) algorithms to intrinsically handle the normality constraint, which has been empirically shown to be superior to other Riemannian and Euclidean approaches. Imposing the normality constraint implicitly, in line with the ICA definition, essentially guarantees a substantial improvement in the solution accuracy, by way of increased degrees of freedom while searching for an optimal unmixing ICA matrix, in contrast with the orthonormality constraint. Designs of the steepest descent, conjugate gradient with Hager-Zhang or a hybrid update parameter, quasi-Newton, and cost-effective quasi-Newton methods intended for OB are presented in this paper. Their performance is validated using natural images and systematically compared with the popular state-of-the-art approaches in order to assess the performance effects of the choice of algorithm and the use of a Riemannian rather than Euclidean framework. We surmount the computational challenge associated with the direct estimation of the source densities using the improved fast Gauss transform in the evaluation of the contrast function and its gradient. The proposed OB schemes may find applications in the offline image/signal analysis, wherein, on one hand, the computational overhead can be tolerated, and, on the other, the solution quality holds paramount interest.

Subspace tracking methods are widespread in signal and image processing. To reduce the influence of perturbations or outliers on the measurements, some authors have used a stochastic piecewise constant velocity model on the Grassmann manifold. This paper presents an efficient way to simulate such a model using a particular representation of the Grassmann manifold. By doing so, we can reduce the spatial and time complexity of filtering techniques based on this model. We also propose an approximation of this system which can be computed in a finite number of operations and show similar results if the subspace variation is slow.

Code restructuring compilers rely heavily on program analysis techniques to automatically detect data dependences between program statements. Dependences between statement instances in the iteration space of a loop nest impose ordering constraints that must be preserved in order to produce valid optimized, vectorized, and parallelized loop nests. This paper evaluates a new approach for fast and accurate nonlinear array dependence testing using Chains of Recurrences (CRs). A flow-sensitive loop analysis algorithm is presented for constructing the CR forms of array index expressions. Unlike other approaches, the CR forms are directly integrated into a standard dependence test to solve nonlinear CR-based dependence equations. To study the coverage and performance of the proposed CR-based enhancements of a standard test, we chose the inexact Banerjee test. We implemented a new CR-based Banerjee test in the Polaris compiler and compared the results to the Omega test and Range test on a set of SPEC and LAPACK Benchmark programs. The experimental results suggest that a CR enhancement can dramatically increase the effectiveness of a dependence test without a significant cost increase. More surprisingly, the findings indicate that the enhanced test exceeds the capabilities of the Omega and Range tests for many nonlinear dependence relations detected in the PERFECT Club and LAPACK Benchmark programs.

Several blind source separation algorithms obtain a separating matrix by computing the congruence transformation that "best" diagonalizes a collection of covariance matrices. Recent methods avoid a pre-whitening phase and directly attempt to compute a non-orthogonal diagonalizing congruence. However, since the magnitude of the sources is unknown, there is a fundamental indeterminacy on the norm of the rows of the separating matrix. We show how this indeterminacy can be taken into account by restricting the separating matrix to the oblique manifold. The geometry of this manifold is developed and a trust-region-based algorithm for non-orthogonal joint diagonalization is proposed

A modern DSP laboratory course should teach students how to quickly develop efficient applications using a mixture of C and assembly instructions. Since typical irregular DSP microprocessor architectures present some challenges to traditional optimizing compilers, we introduced a novel new interactive optimizing compiler, VISTA, in a DSP laboratory course to teach students about optimizing compilers and the trade-offs between code development in C and assembly. Students generally found VISTA educational and gained improved insight into effective DSP software development.

Linear representations are widely used to reduce dimension in applications involving high dimensional data. While specialized procedures exist for certain optimality criteria, such as principle component analysis (PCA) and Fisher discriminant analysis (FDA), they can not be generalized for more general criteria. To overcome this fundamental limitation, optimal component analysis (OCA) uses a stochastic gradient optimization procedure intrinsic to the manifold giving by the constraints of applications and therefore gives a procedure for finding optimal representations for general criteria. However, due to its generality nature, OCA often requires extensive computation for gradient estimation and updating. To significantly reduce the required computation, in this paper, we propose a two-stage method by first reducing the dimension of input to a smaller one (but larger than the final resulting dimension) using a computationally efficient method and then performing OCA in the reduced space. This reduces the computation time from days to minutes on widely used databases, making OCA learning feasible for many applications. Additionally, since the reduced space is much smaller, the stochastic gradient optimization tends to be more efficient. We illustrate the effectiveness of the proposed method on face classification.

Abstract This paper presents a novel method for parametric worst‐case execution time (WCET) estimation of loops. The method determines a parametric bound on the iteration space size of loops with both affine and non‐affine loop bounds in an efficient manner using a formulation based on Newton–Gregory interpolating polynomials. Parametric WCET formulae are used to support dynamic scheduling decisions at runtime, where the WCET of a scheduled task might not be known statically. To determine worst‐case execution time estimates of scientific and multimedia codes, which spent most of the execution time on executing loop iterations, efficient and accurate symbolic loop WCET estimation methods must be capable of analyzing loops with symbolic bounds, non‐rectangular loops, zero‐trip loops, loops with multiple critical paths, and loops with non‐unit strides. Copyright © 2006 John Wiley & Sons, Ltd.

Software designers face many challenges when developing applications for embedded systems. One major challenge is meeting the conflicting constraints of speed, code size, and power consumption. Embedded application developers often resort to hand-coded assembly language to meet these constraints since traditional optimizing compiler technology is usually of little help in addressing this challenge. The results are software systems that are not portable, less robust, and more costly to develop and maintain. Another limitation is that compilers traditionally apply the optimizations to a program in a fixed order. However, it has long been known that a single ordering of optimization phases will not produce the best code for every application. In fact, the smallest unit of compilation in most compilers is typically a function and the programmer has no control over the code improvement process other than setting flags to enable or disable certain optimization phases. This paper describes a new code improvement paradigm implemented in a system called VISTA that can help achieve the cost/performance trade-offs that embedded applications demand. The VISTA system opens the code improvement process and gives the application programmer, when necessary, the ability to finely control it. VISTA also provides support for finding effective sequences of optimization phases. This support includes the ability to interactively get static and dynamic performance information, which can be used by the developer to steer the code improvement process. This performance information is also internally used by VISTA for automatically selecting the best optimization sequence from several attempted. One such feature is the use of a genetic algorithm to search for the most efficient sequence based on specified fitness criteria. We include a number of experimental results that evaluate the effectiveness of using a genetic algorithm in VISTA to find effective optimization phase sequences.

This paper presents a unified approach for generalized induction variable recognition and substitution, pointer analysis, analysis of conditionally updated variables, value range analysis, array region analysis, and nonlinear dependence testing. The analysis techniques share a well-defined uniform approach based on the chains of recurrences algebra. The uniform algebraic approach provides a powerful unified framework for developing analysis algorithms for restructuring compilers. The paper introduces a new set of analysis algorithms that accurately handle conditional control flow, pointer arithmetic, and nonlinear symbolic expressions in loops, which are known to be problematic for conventional restructuring compilers.

Abstract Iterative compilation, where we search for the best program transformation based on profile feedback information, has been highly successful in determining good program optimizations, typically outperforming all static approaches. However, this benefit has come at a price, namely, a large number of executions of the target program which in many cases is unacceptable. This paper is concerned with reducing the number of program executions needed by iterative compilation by incorporating static models. We examine how static models may be incorporated into a purely iterative approach by developing several characterized heuristics. We empirically explore the tradeoff between reducing the number of executions required and the ultimate performance achieved for differing parameters or slack factors. We focus on tiling and unrolling as transformations and cache models as a test case for the feasibility of this approach. We show that a highly accurate model, used as a filter to profiling and appropriately parameterized, can reduce the number of executions by 50%. We also show that using a simple model to rank transformations and profiling, only those with the highest ranking can reduce the number of executions even further up to 70%, in cases where there is only a limited number of profiles available. We conclude that a production compiler might perform best using the last approach, gaining the benefit of iterative compilation at a much reduced cost. Copyright © 2004 John Wiley & Sons, Ltd.

Although linear representations are frequently used in image analysis, their performances are seldom optimal in specific applications. This paper proposes a stochastic gradient algorithm for finding optimal linear representations of images for use in appearance-based object recognition. Using the nearest neighbor classifier, a recognition performance function is specified and linear representations that maximize this performance are sought. For solving this optimization problem on a Grassmann manifold, a stochastic gradient algorithm utilizing intrinsic flows is introduced. Several experimental results are presented to demonstrate this algorithm.

Simplicity of linear representations (of images) makes them a popular tool in imaging analysis applications such as object recognition and image classification. Although several linear representations, namely PCA (principal component analysis), ICA, and FDA (Fisher discriminant analysis), have frequently been used, these representations are generally far from optimal in terms of actual application performance. We argue that representations should be chosen with respect to the application and the databases involved. Fixing an application, say object recognition, and assuming that recognition performance is computable for any linear basis (given a classifier and a database), we propose a Monte Carlo simulated annealing method that leads to optimal linear representations by maximizing the recognition performance over all fixed-rank subspaces. We illustrate this method on two popular databases.

It has long been known that a single ordering of optimization phases will not produce the best code for every application. This phase ordering problem can be more severe when generating code for embedded systems due to the need to meet conflicting constraints on time, code size, and power consumption. Given that many embedded application developers are willing to spend time tuning an application, we believe a viable approach is to allow the developer to steer the process of optimizing a function. In this paper, we describe support in VISTA, an interactive compilation system, for finding effective sequences of optimization phases. VISTA provides the user with dynamic and static performance information that can be used during an interactive compilation session to gauge the progress of improving the code. In addition, VISTA provides support for automatically using performance information to select the best optimization sequence among several attempted. One such feature is the use of a genetic algorithm to search for the most efficient sequence based on specified fitness criteria. We have included a number of experimental results that evaluate the effectiveness of using a genetic algorithm in VISTA to find effective optimization phase sequences.

This paper presents the gSOAP stub and skeleton compiler. The compiler provides a unique SOAP-to-C/C++ language binding for deploying C/C++ applications in SOAP Web Services, clients, and peer-to-peer computing networks. gSOAP enables the integratation of (legacy) C/C++/Fortran codes, embedded systems, and real-time software in Web Services, clients, and peers that share computational resources and information with other SOAP-enabled applications, possibly across different platforms, language environments, and disparate organizations located behind firewalls. Results on interoperability, legacy code integration, scalability, and performance are given.

Reliable performance is very important for high speed channel equalizers and echo cancellers used in high speed communications channels. A common type of hardware fault occurs when the coefficients get "stuck" at an uncontrollable value. Such faults lead to larger overall mean square errors, and generally poor performance. Redundancy can provide the ability to compensate for these types of faults if the proper design is introduced into the adaptive filter structure. Unfortunately this form of redundancy can lead to poor convergence performance for the adaptive filter after the fault occurrence. This paper examines the use of affine projection and row projection techniques to improve the convergence performance of the fault tolerant adaptive filtering structure. Algorithms are developed for two cases: fault knowledge and no fault knowledge incorporated in the adaptive filtering update. These algorithms are introduced in this paper and simulations are presented to illustrate the effectiveness of these approaches.

Waveform relaxation (WR) has been shown to be an effective algorithm to simulate large digital circuits. In this paper, we explore parallel WR methods to further improve the performance. The parallel processing issues under investigation include partitioning, task granularity, scheduling and allocation. The difficulty of addressing these issues is that circuit simulation problems tend to have highly irregular computational structures. The use of high-level waveforms generated from logic or timing simulators is introduced as a way of improving speed. The speed improvements for circuit partitioning, window selection and task allocation using high-level information are presented.

This paper discusses the comprehensive performance profiling, improvement and benchmarking of a Computational Fluid Dynamics code, one of the Grand Challenge applications, on three popular multiprocessors. In the process of analyzing performance we considered language, compiler, architecture, and algorithmic changes and quantified each of them and their incremental contribution to bottom-line performance. We demonstrate that parallelization alone cannot result in significant gains if the granularity of parallel threads and the effect of parallelization on data locality are not taken into account. Unlike benchmarking studies that often focus on the performance or effectiveness of parallelizing compilers on specific loop kernels, we used the entire CFD code to measure the global effectiveness of compilers and parallel architectures. We probed the performance bottlenecks in each case and derived solutions which eliminate or neutralize the performance inhibiting factors. The major conclusion of our work is that overall performance is extremely sensitive to the synergetic effects of compiler optimizations, algorithmic and code tuning, and architectural idiosyncrasies.

This paper presents a block Schur algorithm to obtain a factorization of a symmetric block Toeplitz matrix. We develop a version based on block hyperbolic Householder reflectors by adapting the representation schemes for block Householder reflectors to the hyperbolic case. If a singular principal submatrix is encountered during the factorization, the matrix is perturbed and an approximate factorization is obtained. This is then combined with iterative refinement to obtain the final solution.

In this paper, a nonsymmetric sparse linear system solver based on the exploitation of multilevel parallelism is proposed. One of the main issues addressed is the application of tearing techniques to enhance large grain parallelism in a manner that maintains reasonable stability. This is accomplished by a combination of a novel reordering technique (H*) and pivoting strategy. The large grain parallelism exposed by the reordering is combined with medium (various parallel row updates strategies) and fine grain (vectorization) parallelism to allow adaptation to a wide range of multiprocessor architectures. Experimental results are presented which show the effectiveness of the reordering, as well as the stability and efficiency of the solver. 1 Introduction Several techniques have been proposed to solve large sparse systems of linear equations on parallel processors. A key task which determines the effectiveness of these techniques is the identification and exploitation of the computatio...

In this paper, we give an overview of the Cedar multiprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks. We also present a methodology for judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.

Describes methods of increasing parallelism, thereby improving the performance, of waveform relaxation-based parallel circuit simulators. The key contribution is the use of parallel nonlinear relaxation and parallel model evaluation to solve large subcircuits that may lead to load balancing problems. These large subcircuits are further partitioned and solved on clusters of tightly-coupled multiprocessors. This paper describes a general hybrid/hierarchical approach for waveform relaxation, and then focuses on the implementation issues regarding parallel nonlinear relaxation and parallel model evaluation. A number of benchmark circuits are used to demonstrate the improved performance of this approach and its range of applicability in parallel circuit simulation.>

We present the design of the GFDL ocean circulation model as adapted for simulations of the Mediterranean basin for the Cedar multicluster architecture. The model simulates the basic aspects of large-scale, baroclinic ocean circulation, including treatment of irregular bottom topography. The data and computational mapping strategies and their effect on the design are discussed. The code was parameterized to offer several choices for data partitionings of the computational domain, for placement strategies for the data in the memory hierarchy, and for the number of clusters and processors used in the computational hierarchy of Cedar. The experiments and performance trends are discussed. Using four clusters and 32 processors the code demonstrates significant speedup compared to a single cluster and compared to a single processor. 1 Introduction The numerical modeling of ocean circulation is a task of great importance, both in its own right, as well as a component of climate studies. Num...

The implementation of asynchronous waveform relaxation on parallel processors is discussed. Three different approaches, all based on event-driven scheduling techniques, are compared to the standard data-flow scheme. Issues involving the use of priority queues and preemptive scheduling are described. Circuit examples are used to demonstrate that good speedup can be achieved by using the event-driven method. The results indicate that the combination of data-flow and event-driven scheduling, together with a suitable preemptive scheme, provides a speed improvement of 1.5 to 2.5 over standard data-flow scheduling on eight processors.>

This paper describes a class of parallel algorithms for circuit simulation based on hierarchical relaxation that has been implemented on the Cedar multiprocessor. The Cedar machine is a reconfigurable, general-purpose supercomputer that was designed and implemented at the University of Illinois. A hierarchical circuit simulation scheme was developed to exploit the hierarchical organization of Cedar. The new algorithm and a number of key issues, such as multilevel circuit partitioning, data partitioning, cluster algorithm selection, and cluster algorithm implementation are described in this paper. Performance results on a variety of different configurations of Cedar are also presented that illustrate the benefits of the hierarchical approach over the non-hierarchical approach.

The problem of finding an approximation of @@@@ = A†b (where A† is the pseudo-inverse of A ∈ @@@@m@@@@n with m ≥ n and rank(A) = n) is discussed. It is assumed that A is sparse but has neither a special pattern (as bandedness) nor a special property (as symmetry or positive definiteness). In this paper it is shown that preconditioners obtained by neglecting small elements during the decomposition of A into easily invertible matrices can be used efficiently with conjugate gradient-type methods if an adaptive strategy for deciding when an element is small is implemented. The resulting preconditioned methods are often better than the corresponding direct and pure iterative methods or those based on preconditionings in which elements are neglected when they appear in a predefined set of positions in the matrix, i.e. positional rather than numerical dropping. Numerical results are given to illustrate the performance of the CG-type methods preconditioned via numerical dropping.

It is demonstrated how the behavior of a cache-based multi-vector-processor memory system can be systematically characterized and its performance experimentally correlated with key features of the address stream. The approach is based on the definition of a family of parameterized kernels used to explore specific aspects of the memory system's performance. The empirical results from this kernel suite provide the data from which architectural or algorithmic characteristics can be studied. The results of applying the approach to an Alliant FX/8 are presented and evaluated.>

In this paper we discuss the performance prediction of Fortran constructs commonly found in numerical scientific computing. Although the approach is applicable to multi-processors in general, within the scope of the paper we will concentrate on the Alliant FX/8 multiprocessor. The techniques proposed involve a combination of empirical observations, architectural models and analytical techniques, and exploits earlier work on data locality analysis and empirical characterization of the behavior of memory systems. The Lawrence Livermore Loops are used as a test-case to verify the approach.

The speed and efficiency of the memory system is a key limiting factor in the performance of supercomputers. Consequently, one of the major concerns when developing a high-performance code, either manually or automatically, is determining and characterizing the influence of the memory system on performance in terms of algorithmic parameters. Unfortunately, the performance data available to an algorithm designer such as various benchmarks and, occasionally, manufacturer-supplied information, e.g. instruction timings and architecture component characteristics, are rarely sufficient for this task. In this paper, we discuss a systematic methodology for probing the performance characteristics of a memory system via a hierarchy of data-movement kernels. We present and analyze the results obtained by such a methodology on a cache-based multi-vector processor (Alliant FX/8). Finally, we indicate how these experimental results can be used for predicting the performance of simple Fortran codes by a combination of empirical observations, architectural models and analytical techniques.

Parallel supercomputers architectures with complex memory hierarchies or distributed memory systems have become very common. Unfortunately, the problems associated with restructuring software to take advantage of these memory systems are not eas-ily solved. This paper presents an overview of some of the mathematical issues behind several of these problems and attempts to give a brief look at some of the potential solutions. 1