POEMS: end-to-end performance design of large parallel adaptive computational systems

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.     

Performance evaluation of algorithms for mildly nonlinear elliptic problems

A number of numerical methods for mildly nonlinear elliptic boundary value problems on general domains is presented. The discretization procedures considered are: a fourth-order FFT-type method, collocation using Hermite bicubic splines and Galerkin with linear triangular as well as quadratic quadrilateral isoparametric elements. The linearized collocation and Galerkin equations are solved by various direct methods available in the ELLPACK system. A comparative study of the above equation solvers is presented for different domain geometries and compilers. The evaluation of software for the general mildly nonlinear elliptic equations is performed over 36 instances from a population of 16 parametrized problems with ‘real world’ and ‘mathematical’ behaviour. The performance data suggests that collocation is an effective method for such general problems, while Galerkin with quadratic quadrilateral isoparametric elements is uniformly superior to the one with linear elements.     

Development,evaluation and selection of methods for elliptic partial differential equations

We present a framework within which to evaluate and compare computational methods to solve elliptic partial differential equations. We then report on the results of comparisons of some classical methods as well as a new one presented here. Our main motivation is the belief that the standard finite difference methods are almost always inferior for solving elliptic problems and our results are strong evidence that this is true. The superior methods are higher order (fourth or more instead of second) and we describe a new collocation finite element method which we believe is more efficient and flexible than the other well known methods, e.g., fourth order finite differences, fourth order finite element methods of Galerkin, Rayleigh-Ritz or least squares type.Our comparisons are in the context of the relatively complicated problems that arise in realistic applications. Our conclusion does not hold for simple model problems (e.g., Laplaces equation on a rectangle) where very specialized methods are superior to the generally applicable methods that we consider. The accurate and relatively simple treatment of boundary conditions involving curves and derivations is a feature of our collocation method.     

Quadratic-spline collocation methods for two-point boundary value problems

A new collocation method based on quadratic splines is presented for second order two-point boundary value problems. First, O(h⁴) approximations to the first and second derivative of a function are derived using a quadratic-spline interpolant of u. Then these approximations are used to define an O(h⁴) perturbation of the given boundary value problem. Second, the perturbed problem is used to define a collocation approximation at interval midpoints for which an optimal O(h^3-J) global estimate for the jth derivative of the error is derived. Further, O(h^4-J) error bounds for the jth derivative are obtained for certain superconvergence points. It should be observed that standard collocation at midpoints gives O(h^2-J) bounds. Results from numerical experiments are reported that verify the theoretical behaviour of the method.     

A sixth order fast direct helmholtz equation solver

An O(h⁶) accurate difference approximation to solutions of the Helmholtz equation is derived. The discrete equations are solved using a reduction procedure and Fourier analysis. Its computational performance is compared with a fourth order similar method over a set of linear and mildly nonlinear elliptic boundary value problems.     

Smart VideoText: a video data model based on conceptual graphs

An intelligent annotation-based video data model called Smart VideoText is introduced. It utilizes the conceptual graph knowledge representation formalism to capture the semantic associations among the concepts described in text annotations of video data. The aim is to achieve more effective query, retrieval, and browsing capabilities based on the semantic content of video data. Finally, a generic and modular video database architecture based on the Smart VideoText data model is described.     

EPPOD: A Problem Solving Environment for Parallel Electronic Prototyping of Physical Object Design

One of the grand challenges for computer applications is the creation of a system that will provide accurate computer simulations of physical objects coupled with powerful design optimization tools to allow optimum prototyping and the final design of a broad range of physical objects. We refer to such a software environment aselectronic prototyping for physical object design (EPPOD). The research challenges in building such systems are in softwareintegration, in utilizingmassive parallelismto satisfy their large computational requirements, in incorporatingknowledgeinto the entire electronic prototyping process, in creatingintelligentuser interfaces for such systems, and in advancing thealgorithmic infrastructureneeded to support the desired functionality. In this paper we address issues related to the parallel processing of the computationally intensive components of the EPPOD problem solving environment on message passing parallel machines and present its software architecture. The parallel methodology adopted to map the underlying computations to parallel machines is based on the optimal decomposition of continuous and discrete geometric data associated with the physical object. One of the main goals of this methodology is thereuseof existing software parts while implementing various components of the EPPOD system on parallel computational environments. Finally, some performance data of the parallel algorithmic infrastructured developed are listed and discussed.     

Automating the analysis of option pricing algorithms throughintelligent knowledge acquisition approaches

The traditional approach for estimating the performance of numerical methods is to combine an operation's count with an asymptotic error analysis. This analytic approach gives a general feel of the comparative efficiency of methods, but it rarely leads to very precise results. It is now recognized that accurate performance evaluation can be made only with actual measurements on working software. Given that such an approach requires an enormous amount of performance data related to actual measurements, the development of novel approaches and systems that intelligently and efficiently analyze these data is of great importance to scientists and engineers. The paper presents intelligent knowledge acquisition approaches and an integrated prototype system, which enables the automatic and systematic analysis of performance data. The system analyzes the performance data which is usually stored in a database with statistical, and inductive learning techniques and generates knowledge which can be incorporated in a knowledge base incrementally. We demonstrate the use of the system in the context of a case study, covering the analysis of numerical algorithms for the pricing of American vanilla options in a Black and Scholes modeling framework. We also present a qualitative and quantitative comparison of two techniques used for the automated knowledge acquisition phase