Adapting application execution in CMPs using helper threads

In parallel to the changes in both the architecture domain–the move toward chip multiprocessors (CMPs)–and the application domain–the move toward increasingly data-intensive workloads–issues such as performance, energy efficiency and CPU availability are becoming increasingly critical. The CPU availability can change dynamically due to several reasons such as thermal overload, increase in transient errors, or operating system scheduling. An important question in this context is how to adapt, in a CMP, the execution of a given application to CPU availability change at runtime. Our paper studies this problem, targeting the energy-delay product (EDP) as the main metric to optimize. We first discuss that, in adapting the application execution to the varying CPU availability, one needs to consider the number of CPUs to use, the number of application threads to accommodate and the voltage/frequency levels to employ (if the CMP has this capability). We then propose to use helper threads to adapt the application execution to CPU availability change in general with the goal of minimizing the EDP. The helper thread runs parallel to the application execution threads and tries to determine the ideal number of CPUs, threads and voltage/frequency levels to employ at any given point in execution. We illustrate this idea using four applications (Fast Fourier Transform, MultiGrid, LU decomposition and Conjugate Gradient) under different execution scenarios. The results collected through our experiments are very promising and indicate that significant EDP reductions are possible using helper threads. For example, we achieved up to 66.3%, 83.3%, 91.2%, and 94.2% savings in EDP when adjusting all the parameters properly in applications FFT, MG, LU, and CG, respectively. We also discuss how our approach can be extended to address multi-programmed workloads.     

Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

Data reduction is a key technique in the study of fixed parameter algorithms. In the AI literature, pruning techniques based on simple and efficient-to-implement reduction rules also play a crucial role in the success of many industrial-strength solvers. Understanding the effectiveness and the applicability of data reduction as a technique for designing heuristics for intractable problems has been one of the main motivations in studying the phase transition of randomly-generated instances of NP-complete problems.In this paper, we take the initiative to study the power of data reductions in the context of random instances of a generic intractable parameterized problem, the weighted d-CNF satisfiability problem. We propose a non-trivial random model for the problem and study the probabilistic behavior of the random instances from the model. We design an algorithm based on data reduction and other algorithmic techniques and prove that the algorithm solves the random instances with high probability and in fixed-parameter polynomial time O(dknm) where n is the number of variables, m is the number of clauses, and k is the fixed parameter. We establish the exact threshold of the phase transition of the solution probability and show that in some region of the problem space, unsatisfiable random instances of the problem have parametric resolution proof of fixed-parameter polynomial size. Also discussed is a more general random model and the generalization of the results to the model.     

Landmark MDS ensemble

Landmark multidimensional scaling (LMDS) uses a subset of data (landmark points) to solve classical multidimensional scaling (MDS), where the scalability is increased but the approximation is noise-sensitive. In this paper we present an LMDS ensemble where we use a portion of the input in a piecewise manner to solve classical MDS, combining individual LMDS solutions which operate on different partitions of the input. Ground control points (GCPs) that are shared by partitions considered in the ensemble, allow us to align individual LMDS solutions in a common coordinate system through affine transformations. We incorporate priors into combining multiple LMDS solutions such that the weighted averaging by priors improves the noise-robustness of our method. Our LMDS ensemble is much less noise-sensitive while maintaining the scalability and the speed of LMDS. Experiments on synthetic data (noisy grid) and real-world data (similar image retrieval) confirm the high performance of the proposed LMDS ensemble.     

Stable local dimensionality reduction approaches

Dimensionality reduction is a big challenge in many areas. A large number of local approaches, stemming from statistics or geometry, have been developed. However, in practice these local approaches are often in lack of robustness, since in contrast to maximum variance unfolding (MVU), which explicitly unfolds the manifold, they merely characterize local geometry structure. Moreover, the eigenproblems that they encounter, are hard to solve. We propose a unified framework that explicitly unfolds the manifold and reformulate local approaches as the semi-definite programs instead of the above-mentioned eigenproblems. Three well-known algorithms, locally linear embedding (LLE), laplacian eigenmaps (LE) and local tangent space alignment (LTSA) are reinterpreted and improved within this framework. Several experiments are presented to demonstrate the potential of our framework and the improvements of these local algorithms.     

A coupling algorithm for partitioned solvers applied to bubble and droplet dynamics

Bubbles and droplets both consist of a liquid in contact with a gas. In this paper, we consider the interface between the incompressible liquid and the gas as a zero thickness structure. The position of the interface is determined by the equilibrium between surface tension effects and the fluid pressure difference across the interface. So, the structure interacts with the fluids on either side. The behaviour of a limited number of bubbles and droplets can therefore be simulated as a Fluid-Structure Interaction (FSI) problem.Most existing techniques frequently used for studying bubble and droplet dynamics, such as Level Set or Volume Of Fluid, use monolithic schemes. The flow on both sides of the interface and the position of the interface are calculated in a single code. In this contribution, a partitioned approach is presented. The position of the interface is calculated with a structural solver. Given a displacement of the interface, a separate flow solver calculates the flow on the liquid side of the interface with the Arbitrary Lagrangian-Eulerian (ALE) technique. The structural solver uses a reduced order model of the flow solver to obtain implicit coupling between both solvers. This reduced order model is built up during the coupling iterations of a time step. Grid and time converged solutions of two axisymmetric problems are calculated: an oscillating water droplet in air and the growth and detachment of an air bubble from the outlet of a vertical needle, submerged in quiescent water.     

一种大规模数据的快速潜在语义索引

潜在语义索引（LSI）已应用到现代信息检索的多个领域,但矩阵奇异值分解的高复杂度阻碍了该技术在大规模数据上的应用。提出一种大规模数据的快速LSI方法。给出一个降维问题的统一框架,LSI作为一种特征提取算法,可以在这个框架下转化为一个特征选择问题。利用该技术在最大程度保持LSI降维效果的同时,简化LSI的计算,使其能够应用于大规模数据。