Catálogo de publicaciones - libros

The PMLS parallelizing compiler for Standard ML is based upon the automatic instantiation of algorithmic skeletons at sites of higher order function use. PMLS seeks to optimise run-time parallel be- haviour by combining skeleton cost models with Structural Operational Semantics rule counts for HOF argument functions. In this paper, the formulation of a general rule count cost model as a set of over-determined linear equations is discussed, and their solution by singular value decom- position, and by a genetic algorithm, are presented.

Resource management is a critical concern in high-performance computing software. While management of processing resources to increase performance is the most critical, efficient management of memory resources plays an important role in solving large problems. This paper presents a dynamic memory management scheme for a declarative high-performance data-parallel programming system — the framework. In such systems, some sort of automatic resource management is a requirement. We present an automatic memory management scheme that provides good compromise between memory utilization and speed. In addition to basic memory management, we also develop methods that take advantages of the cache memory subsystem and explore balances between memory utilization and parallel communication costs.

This paper discusses an implementation of an adaptive resolution system for modeling regional air pollution based on the chemical transport model STEM. The grid adaptivity is implemented using the generic tool Paramesh. The computational algorithm uses a decomposition of the domain, with the solution in different sub-domains computed at different spatial resolutions. We analyze the parallel computational performance versus the accuracy of long time simulations.

Texas Air Quality Study 2000 revealed that ozone productivity in the Houston Ship Channel area was abnormally higher than other comparable cities in USA due to the large emissions of highly reactive unsaturated hydrocarbons from petrochemical industries. Simulations with popular Eulerian air quality models were shown to be inadequate to represent the transient high ozone events in the Houston Ship Channel area. In this study, we apply a multiscale Eulerian modeling approach, called CMAQ/SAFE, to reproduce the measured ozone productivity in the Houston Ship Channel and surrounding urban and rural areas. The modeling tool provides a paradigm for the multiple-level regional and local air quality forecasting operations that can utilize modern computational infrastructure such as grid computing technologies allowing to harness computing resources across sites by providing programmatic and high-bandwidth data linkage and establishing operational redundancy in the case of hardware or software failures at one operational site.

This paper discusses several aspects related to the consistency and stability of the discrete adjoints of upwind numerical schemes. First and third order upwind discretizations of the one-dimensional advection equation are considered in both the finite difference and finite volume formulations. We show that the discrete adjoints may lose consistency and stability near the points where upwinding is changed, and near inflow boundaries where the numerical scheme is changed. The impact of adjoint inconsistency and instability on data assimilation is analyzed.

Given a sequence of numbers and two positive integers ℓ and , we study the problem to find disjoint segments of , each has length at least ℓ, such that their sum of densities is maximized. We give the first known polynomial-time algorithm for the problem: For general , our algorithm runs in ( ℓ) time. For the special case with = 2 (respectively, = 3), we also show how to solve the problem in () (respectively, ( + ℓ)) time.

We study a new family of trees for computation of the Wiener indices. We introduce general tree transformations and derive formulas for computing the Wiener indices when a tree is modified. We present several algorithms to explore the Wiener indices of our family of trees. The experiments support new conjectures about the Wiener indices.

Given two arc-annotated sequences (,) and (,) representing RNA structures, the (APS) problem asks whether (,) can be obtained from (, ) by deleting some of its bases (together with their incident arcs, if any). In previous studies [3, 6], this problem has been naturally divided into subproblems reflecting intrinsic complexity of arc structures. We show that APS() is -Complete, thereby answering an open problem [6]. Furthermore, to get more insight into where actual border of APS hardness is, we refine APS classical subproblems in much the same way as in [11] and give a complete categorization among various restrictions of APS problem complexity.

RNA secondary structure prediction based on free energy rules for stacking and loop conformation remains a major computational method. The basic dynamic programming algorithm needs O(n) time to calculate the minimum free energy for RNA secondary structure. To date, there are two variants for handling this problem: either the internal loops are bounded by a maximal size k giving a time complexity of O(n*k), or one uses the trick of Rune Lyngso, which makes use of the regularities of loop energies, to reduce time complexity to O(n) without restriction. We propose a new dynamic programming algorithm for RNA secondary structure prediction by analyzing energy rules. Through only additional O(n) space, this algorithm eliminates redundant calculation in the energy calculation of internal loop with unrestricted/restricted size and reduces the time complexity of this part from O(n) to O(n), then the overall time complexity to O(n).

This paper aims to evaluate the clustering quality of various protein clustering tools that are publicly available as standalone applications. We first review the current protein sequence clustering methods, and introduce a new incrementally clustering tool denoted as PINC. We then propose an intuitive performance metric for evaluating them. The evaluation results of the tools on the public database Pfam are reported.