bluuebunny/crossref_metadata_2025 huggingface dataset:
Crumpling sound synthesis
Authors: Cirio Gabriel , Li Dingzeyu , Grinspun Eitan , Otaduy Miguel A. , Zheng Changxi
Published: November 2016

Crumpling a thin sheet produces a characteristic sound, comprised of distinct clicking sounds corresponding to buckling events. We propose a physically based algorithm that automatically synthesizes crumpling sounds for a given thin shell animation. The resulting sound is a superposition of individually synthesized clicking sounds corresponding to visually significant and insignificant buckling events. We identify visually significant buckling events on the dynamically evolving thin surface mesh, and instantiate visually insignificant buckling events via a stochastic model that seeks to mimic the power-law distribution of buckling energies observed in many materials.

In either case, the synthesis of a buckling sound employs linear modal analysis of the deformed thin shell. Because different buckling events in general occur at different deformed configurations, the question arises whether the calculation of linear modes can be reused. We amortize the cost of the linear modal analysis by dynamically partitioning the mesh into nearly rigid pieces: the modal analysis of a rigidly moving piece is retained over time, and the modal analysis of the assembly is obtained via Component Mode Synthesis (CMS). We illustrate our approach through a series of examples and a perceptual user study, demonstrating the utility of the sound synthesis method in producing realistic sounds at practical computation times.
Interchangeable components for hands-on assembly based modelling
Authors: Duncan Noah , Yu Lap-Fai , Yeung Sai-Kit
Published: November 2016

Interchangeable components allow an object to be easily reconfigured, but usually reveal that the object is composed of parts. In this work, we present a computational approach for the design of components which are interchangeable, but also form objects with a coherent appearance which conceals their composition from parts. These components allow a physical realization of Assembly Based Modelling, a popular virtual modelling paradigm in which new models are constructed from the parts of existing ones. Given a collection of 3D models and a segmentation that specifies the component connectivity, our approach generates the components by jointly deforming and partitioning the models. We determine the component boundaries by evolving a set of closed contours on the input models to maximize the contours' geometric similarity. Next, we efficiently deform the input models to enforce both C0 and C1 continuity between components while minimizing deviation from their original appearance. The user can guide our deformation scheme to preserve desired features. We demonstrate our approach on several challenging examples, showing that our components can be physically reconfigured to assemble a large variety of coherent shapes.
360° video stabilization
Authors: Kopf Johannes
Published: November 2016

We present a hybrid 3D-2D algorithm for stabilizing 360° video using a deformable rotation motion model. Our algorithm uses 3D analysis to estimate the rotation between key frames that are appropriately spaced such that the right amount of motion has occurred to make that operation reliable. For the remaining frames, it uses 2D optimization to maximize the visual smoothness of feature point trajectories. A new low-dimensional flexible deformed rotation motion model enables handling small translational jitter, parallax, lens deformation, and rolling shutter wobble. Our 3D-2D architecture achieves better robustness, speed, and smoothing ability than either pure 2D or 3D methods can provide. Stabilizing a video with our method takes less time than playing it at normal speed. The results are sufficiently smooth to be played back at high speed-up factors; for this purpose we present a simple 360° hyperlapse algorithm that remaps the video frame time stamps to balance the apparent camera velocity.
Texture space caching and reconstruction for ray tracing
Authors: Munkberg Jacob , Hasselgren Jon , Clarberg Petrik , Andersson Magnus , Akenine-Möller Tomas
Published: November 2016

We present a
texture space
caching and reconstruction system for Monte Carlo ray tracing. Our system gathers and filters shading on-demand, including querying secondary rays, directly within a filter footprint around the current shading point. We shade on local grids in texture space with primary visibility decoupled from shading. Unique filters can be applied per material, where any terms of the shader can be chosen to be included in each kernel. This is a departure from recent screen space image reconstruction techniques, which typically use a single, complex kernel with a set of large auxiliary guide images as input. We show a number of high-performance use cases for our system, including interactive denoising of Monte Carlo ray tracing with motion/defocus blur, spatial and temporal shading reuse, cached product importance sampling, and filters based on linear regression in texture space.
Hyperbolic orbifold tutte embeddings
Authors: Aigerman Noam , Lipman Yaron
Published: November 2016

Tutte's embedding is one of the most popular approaches for computing parameterizations of surface meshes in computer graphics and geometry processing. Its popularity can be attributed to its simplicity, the guaranteed bijectivity of the embedding, and its relation to continuous harmonic mappings.

In this work we extend Tutte's embedding into hyperbolic cone-surfaces called orbifolds. Hyperbolic orbifolds are simple surfaces exhibiting different topologies and cone singularities and therefore provide a flexible and useful family of target domains. The hyperbolic Orbifold Tutte embedding is defined as a critical point of a Dirichlet energy with special boundary constraints and is proved to be bijective, while also satisfying a set of points-constraints. An efficient algorithm for computing these embeddings is developed.

We demonstrate a powerful application of the hyperbolic Tutte embedding for computing a consistent set of bijective, seamless maps between all pairs in a collection of shapes, interpolating a set of user-prescribed landmarks, in a fast and robust manner.
Interactively controlled quad remeshing of high resolution 3D models
Authors: Ebke Hans-Christian , Schmidt Patrick , Campen Marcel , Kobbelt Leif
Published: November 2016

Parametrization based methods have recently become very popular for the generation of high quality quad meshes. In contrast to previous approaches, they allow for intuitive user control in order to accommodate all kinds of application driven constraints and design intentions. A major obstacle in practice, however, are the relatively long computations that lead to response times of several minutes already for input models of moderate complexity. In this paper we introduce a novel strategy to handle highly complex input meshes with up to several millions of triangles such that quad meshes can still be created and edited within an interactive workflow. Our method is based on representing the input model on different levels of resolution with a mechanism to propagate parametrizations from coarser to finer levels. The major challenge is to guarantee consistent parametrizations even in the presence of charts, transition functions, and singularities. Moreover, the remaining degrees of freedom on coarser levels of resolution have to be chosen carefully in order to still achieve low distortion parametrizations. We demonstrate a prototypic system where the user can interactively edit quad meshes with powerful high-level operations such as guiding constraints, singularity repositioning, and singularity connections.
High-resolution interaction with corotational coarsening models
Authors: Torres Rosell , Rodríguez Alejandro , Espadero José M. , Otaduy Miguel A.
Published: November 2016

This paper presents a numerical coarsening method for corotational elasticity, which enables interactive large deformation of high-resolution heterogeneous objects. Our method derives a coarse elastic model from a high-resolution discretization of corotational elasticity with high-resolution boundary conditions. This is in contrast to previous coarsening methods, which derive a coarse elastic model from an unconstrained high-resolution discretization of regular linear elasticity, and then apply corotational computations directly on the coarse setting. We show that previous approaches fail to handle high-resolution boundary conditions correctly, suffering accuracy and robustness problems. Our method, on the other hand, supports efficiently accurate high-resolution boundary conditions, which are fundamental for rich interaction with high-resolution heterogeneous models. We demonstrate the potential of our method for interactive deformation of complex medical imaging data sets.
Dispersion kernels for water wave simulation
Authors: Canabal José A. , Miraut David , Thuerey Nils , Kim Theodore , Portilla Javier , Otaduy Miguel A.
Published: November 2016

We propose a method to simulate the rich, scale-dependent dynamics of water waves. Our method preserves the dispersion properties of real waves, yet it supports interactions with obstacles and is computationally efficient. Fundamentally, it computes wave accelerations by way of applying a dispersion kernel as a spatially variant filter, which we are able to compute efficiently using two core technical contributions. First, we design novel, accurate, and compact pyramid kernels which compensate for low-frequency truncation errors. Second, we design a
shadowed convolution
operation that efficiently accounts for obstacle interactions by modulating the application of the dispersion kernel. We demonstrate a wide range of behaviors, which include capillary waves, gravity waves, and interactions with static and dynamic obstacles, all from within a single simulation.
Dynamic furniture modeling through assembly instructions
Authors: Shao Tianjia , Li Dongping , Rong Yuliang , Zheng Changxi , Zhou Kun
Published: November 2016

We present a technique for parsing widely used furniture assembly instructions, and reconstructing the 3D models of furniture components and their dynamic assembly process. Our technique takes as input a multi-step assembly instruction in a vector graphic format and starts to group the vector graphic primitives into semantic elements representing individual furniture parts, mechanical connectors (e.g., screws, bolts and hinges), arrows, visual highlights, and numbers. To reconstruct the dynamic assembly process depicted over multiple steps, our system identifies previously built 3D furniture components when parsing a new step, and uses them to address the challenge of occlusions while generating new 3D components incrementally. With a wide range of examples covering a variety of furniture types, we demonstrate the use of our system to animate the 3D furniture assembly process and, beyond that, the semantic-aware furniture editing as well as the fabrication of personalized furnitures.
Scalable inside-out image-based rendering
Authors: Hedman Peter , Ritschel Tobias , Drettakis George , Brostow Gabriel
Published: November 2016

Our aim is to give users real-time free-viewpoint rendering of real indoor scenes, captured with off-the-shelf equipment such as a high-quality color camera and a commodity depth sensor. Image-based Rendering (IBR) can provide the realistic imagery required at real-time speed. For indoor scenes however, two challenges are especially prominent. First, the reconstructed 3D geometry must be compact, but faithful enough to respect occlusion relationships when viewed up close. Second, man-made materials call for view-dependent texturing, but using too many input photographs reduces performance. We customize a typical RGB-D 3D surface reconstruction pipeline to produce a coarse global 3D surface, and local, per-view geometry for each input image. Our tiled IBR preserves quality by economizing on the expected contributions that entire groups of input pixels make to a final image. The two components are designed to work together, giving real-time performance, while hardly sacrificing quality. Testing on a variety of challenging scenes shows that our inside-out IBR scales favorably with the number of input images.
Bilateral guided upsampling
Authors: Chen Jiawen , Adams Andrew , Wadhwa Neal , Hasinoff Samuel W.
Published: November 2016

We present an algorithm to accelerate a large class of image processing operators. Given a low-resolution reference input and output pair, we model the operator by fitting local curves that map the input to the output. We can then produce a full-resolution output by evaluating these low-resolution curves on the full-resolution input. We demonstrate that this faithfully models state-of-the-art operators for tone mapping, style transfer, and recoloring. The curves are computed by lifting the input into a bilateral grid and then solving for the 3D array of affine matrices that best maps input color to output color per
x, y
, intensity bin. We enforce a smoothness term on the matrices which prevents false edges and noise amplification. We can either globally optimize this energy, or quickly approximate a solution by locally fitting matrices and then enforcing smoothness by blurring in grid space. This latter option reduces to joint bilateral upsampling [Kopf et al. 2007] or the guided filter [He et al. 2013], depending on the choice of parameters. The cost of running the algorithm is reduced to the cost of running the original algorithm at greatly reduced resolution, as fitting the curves takes about 10 ms on mobile devices, and 1--2 ms on desktop CPUs, and evaluating the curves can be done with a simple GPU shader.
Bounded distortion parametrization in the space of metrics
Authors: Chien Edward , Levi Zohar , Weber Ofir
Published: November 2016

We present a framework for global parametrization that utilizes the edge lengths (squared) of the mesh as variables. Given a mesh with arbitrary topology and prescribed cone singularities, we flatten the original metric of the surface under strict bounds on the metric distortion (various types of conformal and isometric measures are supported). Our key observation is that the space of bounded distortion metrics (given any particular bounds) is convex, and a broad range of useful and well-known distortion energies are convex as well. With the addition of nonlinear Gaussian curvature constraints, the parametrization problem is formulated as a constrained optimization problem, and a solution gives a locally injective map. Our method is easy to implement. Sequential convex programming (SCP) is utilized to solve this problem effectively. We demonstrate the flexibility of the method and its uncompromised robustness and compare it to state-of-the-art methods.
Centroidal power diagrams with capacity constraints
Authors: Xin Shi-Qing , Lévy Bruno , Chen Zhonggui , Chu Lei , Yu Yaohui , Tu Changhe , Wang Wenping
Published: November 2016

This article presents a new method to optimally partition a geometric domain with capacity constraints on the partitioned regions. It is an important problem in many fields, ranging from engineering to economics. It is known that a capacity-constrained partition can be obtained as a
power diagram
with the squared L2 metric. We present a method with super-linear convergence for computing optimal partition with capacity constraints that outperforms the state-of-the-art in an order of magnitude. We demonstrate the efficiency of our method in the context of three different applications in computer graphics and geometric processing: displacement interpolation of function distribution, blue-noise point sampling, and optimal convex decomposition of 2D domains. Furthermore, the proposed method is extended to capacity-constrained optimal partition with respect to general cost functions beyond the squared Euclidean distance.
Efficient rendering of heterogeneous polydisperse granular media
Authors: Müller Thomas , Papas Marios , Gross Markus , Jarosz Wojciech , Novák Jan
Published: November 2016

We address the challenge of efficiently rendering massive assemblies of grains within a forward path-tracing framework. Previous approaches exist for accelerating high-order scattering for a limited, and static, set of granular materials, often requiring scene-dependent precomputation. We significantly expand the admissible regime of granular materials by considering
heterogeneous
and
dynamic
granular mixtures with spatially varying grain concentrations, pack rates, and sizes. Our method supports both procedurally generated grain assemblies and dynamic assemblies authored in off-the-shelf particle simulation tools. The key to our speedup lies in two complementary aggregate scattering approximations which we introduced to jointly accelerate construction of short and long light paths. For low-order scattering, we accelerate path construction using novel
grain scattering distribution functions
(GSDF) which aggregate intra-grain light transport while retaining important grain-level structure. For high-order scattering, we extend prior work on
shell transport functions
(STF) to support dynamic, heterogeneous mixtures of grains with varying sizes. We do this without a scene-dependent precomputation and show how this can also be used to accelerate light transport in arbitrary continuous heterogeneous media. Our multi-scale rendering automatically minimizes the usage of explicit path tracing to only the first grain along a light path, or can avoid it completely, when appropriate, by switching to our aggregate transport approximations. We demonstrate our technique on animated scenes containing heterogeneous mixtures of various types of grains that could not previously be rendered efficiently. We also compare to previous work on a simpler class of granular assemblies, reporting significant computation savings, often yielding higher accuracy results.
Reconstructing personalized anatomical models for physics-based body animation
Authors: Kadleček Petr , Ichim Alexandru-Eugen , Liu Tiantian , Křivánek Jaroslav , Kavan Ladislav
Published: November 2016

We present a method to create personalized anatomical models ready for physics-based animation, using only a set of 3D surface scans. We start by building a template anatomical model of an average male which supports deformations due to both 1) subject-specific variations: shapes and sizes of bones, muscles, and adipose tissues and 2) skeletal poses. Next, we capture a set of 3D scans of an actor in various poses. Our key contribution is formulating and solving a large-scale optimization problem where we compute both subject-specific and pose-dependent parameters such that our resulting anatomical model explains the captured 3D scans as closely as possible. Compared to data-driven body modeling techniques that focus only on the surface, our approach has the advantage of creating physics-based models, which provide realistic 3D geometry of the bones and muscles, and naturally supports effects such as inertia, gravity, and collisions according to Newtonian dynamics.
Authoring directed gaze for full-body motion capture
Authors: Pejsa Tomislav , Rakita Daniel , Mutlu Bilge , Gleicher Michael
Published: November 2016

We present an approach for adding directed gaze movements to characters animated using full-body motion capture. Our approach provides a comprehensive authoring solution that automatically infers plausible directed gaze from the captured body motion, provides convenient controls for manual editing, and adds synthetic gaze movements onto the original motion. The foundation of the approach is an abstract representation of gaze behavior as a sequence of gaze shifts and fixations toward targets in the scene. We present methods for automatic inference of this representation by analyzing the head and torso kinematics and scene features. We introduce tools for convenient editing of the gaze sequence and target layout that allow an animator to adjust the gaze behavior without worrying about the details of pose and timing. A synthesis component translates the gaze sequence into coordinated movements of the eyes, head, and torso, and blends these with the original body motion. We evaluate the effectiveness of our inference methods, the efficiency of the authoring process, and the quality of the resulting animation.
Keep calm and react with foresight
Authors: De Matteis Tiziano , Mencagli Gabriele
Published: November 2016

This paper addresses the problem of designing scaling strategies for
elastic
data stream processing. Elasticity allows applications to rapidly change their configuration on-the-fly (e.g., the amount of used resources) in response to dynamic workload fluctuations. In this work we face this problem by adopting the
Model Predictive Control
technique, a control-theoretic method aimed at finding the optimal application configuration along a limited prediction horizon in the future by solving an online optimization problem. Our control strategies are designed to address latency constraints, using Queueing Theory models, and energy consumption by changing the number of used cores and the CPU frequency through the
Dynamic Voltage and Frequency Scaling
(DVFS) support available in the modern multicore CPUs. The proactive capabilities, in addition to the latency- and energy-awareness, represent the novel features of our approach. To validate our methodology, we develop a thorough set of experiments on a high-frequency trading application. The results demonstrate the high-degree of flexibility and configurability of our approach, and show the effectiveness of our elastic scaling strategies compared with existing state-of-the-art techniques used in similar scenarios.
Work stealing for interactive services to meet target latency
Authors: Li Jing , Agrawal Kunal , Elnikety Sameh , He Yuxiong , Lee I-Ting Angelina , Lu Chenyang , McKinley Kathryn S.
Published: November 2016

Interactive web services increasingly drive critical business workloads such as search, advertising, games, shopping, and finance. Whereas optimizing parallel programs and distributed server systems have historically focused on average latency and throughput, the primary metric for interactive applications is instead consistent responsiveness, i.e., minimizing the number of requests that miss a target latency. This paper is the first to show how to generalize work-stealing, which is traditionally used to minimize the makespan of a single parallel job, to optimize for a target latency in interactive services with multiple parallel requests.

We design a new adaptive work stealing policy, called
tail-control
, that reduces the number of requests that miss a target latency. It uses instantaneous request progress, system load, and a target latency to choose when to parallelize requests with stealing, when to admit new requests, and when to limit parallelism of large requests. We implement this approach in the Intel Thread Building Block (TBB) library and evaluate it on real-world workloads and synthetic workloads. The tail-control policy substantially reduces the number of requests exceeding the desired target latency and delivers up to 58% relative improvement over various baseline policies. This generalization of work stealing for multiple requests effectively optimizes the number of requests that complete within a target latency, a key metric for interactive services.
Grain graphs
Authors: Muddukrishna Ananya , Jonsson Peter A. , Podobas Artur , Brorsson Mats
Published: November 2016

Average programmers struggle to solve performance problems in OpenMP programs with tasks and parallel for-loops. Existing performance analysis tools visualize OpenMP task performance from the runtime system's perspective where task execution is interleaved with other tasks in an unpredictable order. Problems with OpenMP parallel for-loops are similarly difficult to resolve since tools only visualize aggregate thread-level statistics such as load imbalance without zooming into a per-chunk granularity. The runtime system/threads oriented visualization provides poor support for understanding problems with task and chunk execution time, parallelism, and memory hierarchy utilization, forcing average programmers to rely on experts or use tedious trial-and-error tuning methods for performance. We present
grain graphs
, a new OpenMP performance analysis method that visualizes
grains
-- computation performed by a task or a parallel for-loop chunk instance -- and highlights problems such as low parallelism, work inflation and poor parallelization benefit at the grain level. We demonstrate that grain graphs can quickly reveal performance problems that are difficult to detect and characterize in fine detail using existing visualizations in standard OpenMP programs, simplifying OpenMP performance analysis. This enables average programmers to make portable optimizations for poor performing OpenMP programs, reducing pressure on experts and removing the need for tedious trial-and-error tuning.
Be my guest
Authors: Wang Tianzheng , Chabbi Milind , Kimura Hideaki
Published: November 2016

The MCS lock is one of the most prevalent queuing locks. It provides fair scheduling and high performance on massively parallel systems. However, the MCS lock mandates a
bring-your-own-context
policy: each lock user must provide an additional context (i.e., a queue node) to interact with the lock. This paper proposes MCSg, a variant of the MCS lock that relaxes this restriction.

Our key observation is that
not all lock users are created equal
. We analyzed how locks are used in massively-parallel modern systems, such as NUMA-aware operating systems and databases. We found that such systems often have a small number of "regular" code paths that enter the lock very frequently. Such code paths are the primary beneficiary of the high scalability of MCS locks.

However, there are also many "guest" code paths that infrequently enter the lock and do not need the same degree of fairness to access the lock (e.g., background tasks that only run periodically with lower priority). These guest users, which are typically spread out in various modules of the software, prefer context-free locks, such as ticket locks.

MCSg provides these guests a context-free interface while regular users still enjoy the benefits provided by MCS. It can also be used as a drop-in replacement of MCS for more advanced locks, such as cohort locking. We also propose MCSg++, an extended version of MCSg, which avoids guest starvation and non-FIFO behaviors that might happen with MCSg.

Our evaluation using microbenchmarks and the TPC-C database benchmark on a 16-socket, 240-core server shows that both MCSg and MCSg++ preserve the benefits of MCS for regular users while providing a context-free interface for guests.
Multi-core on-the-fly SCC decomposition
Authors: Bloemen Vincent , Laarman Alfons , van de Pol Jaco
Published: November 2016

The main advantages of Tarjan's strongly connected component (SCC) algorithm are its linear time complexity and ability to return SCCs on-the-fly, while traversing or even generating the graph. Until now, most
parallel
SCC algorithms sacrifice both: they run in quadratic worst-case time and/or require the full graph in advance.

The current paper presents a novel parallel, on-the-fly SCC algorithm. It preserves the linear-time property by letting workers explore the graph randomly while carefully communicating partially completed SCCs. We prove that this strategy is correct. For efficiently communicating partial SCCs, we develop a concurrent, iterable disjoint set structure (combining the union-find data structure with a cyclic list).

We demonstrate scalability on a 64-core machine using 75 real-world graphs (from model checking and explicit data graphs), synthetic graphs (combinations of trees, cycles and linear graphs), and random graphs. Previous work did not show speedups for graphs containing a large SCC. We observe that our parallel algorithm is typically 10-30× faster compared to Tarjan's algorithm for graphs containing a large SCC. Comparable performance (with respect to the current state-of-the-art) is obtained for graphs containing many small SCCs.
AUTOGEN
Authors: Chowdhury Rezaul , Ganapathi Pramod , Tithi Jesmin Jahan , Bachmeier Charles , Kuszmaul Bradley C. , Leiserson Charles E. , Solar-Lezama Armando , Tang Yuan
Published: November 2016

We present AUTOGEN---an algorithm that for a wide class of dynamic programming (DP) problems automatically discovers highly efficient cache-oblivious parallel recursive divide-and-conquer algorithms from inefficient iterative descriptions of DP recurrences. AUTOGEN analyzes the set of DP table locations accessed by the iterative algorithm when run on a DP table of small size, and automatically identifies a recursive access pattern and a corresponding provably correct recursive algorithm for solving the DP recurrence. We use AUTOGEN to autodiscover efficient algorithms for several well-known problems. Our experimental results show that several autodiscovered algorithms significantly outperform parallel looping and tiled loop-based algorithms. Also these algorithms are less sensitive to fluctuations of memory and bandwidth compared with their looping counterparts, and their running times and energy profiles remain relatively more stable. To the best of our knowledge, AUTOGEN is the first algorithm that can automatically discover new nontrivial divide-and-conquer algorithms.
Scalable adaptive NUMA-aware lock
Authors: Zhang Mingzhe , Lau Francis C. M. , Wang Cho-Li , Cheng Luwei , Chen Haibo
Published: November 2016

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as local locking and remote locking only perform well under a certain level of contention, and often require non-trivial tuning for a particular configuration. Besides, for large NUMA systems, because of unmanaged lock server's nomination, current distance-first NUMA policies cannot perform satisfactorily.

In this work, we propose SANL, a locking scheme that can deliver high performance under various contention levels by adaptively switching between the local and the remote lock scheme. Furthermore, we introduce a new NUMA policy for the remote lock that jointly considers node distances and server utilization when choosing lock servers. A comparison with seven representative locking schemes shows that SANL outperforms the others in most contention situations. In one group test, SANL is 3.7 times faster than RCL lock and 17 times faster than POSIX mutex.
SPIRIT
Authors: Hegde Nikhil , Liu Jianqiao , Kulkarni Milind
Published: November 2016

Repeated, depth-first traversal of trees is a common algorithmic pattern in an important set of applications from diverse domains such as cosmological simulations, data mining, and computer graphics. As these applications operate over massive data sets, it is often necessary to distribute the trees to process all of the data.

In this work, we introduce SPIRIT, a runtime system to ease the writing of distributed tree applications. SPIRIT automates the challenging tasks of tree distribution, optimizing communication and parallelizing independent computations. The common algorithmic pattern in tree traversals is exploited to effectively schedule parallel computations and improve locality. As a result, pipeline parallelism in distributed traversals is identified, which is complemented by load-balancing, and locality-enhancing, message aggregation optimizations. Evaluation of SPIRIT on tree traversal in Point Correlation (PC) shows a scalable system, achieving speedups upto 38x on a 16-node, 64 process system compared to a 1-node, baseline configuration. We also find that SPIRIT results in substantially less communication and achieves significant performance improvements over implementations in other distributed graph systems.
OPR
Authors: Qian Xuehai , Sen Koushik , Hargrove Paul , Iancu Costin
Published: November 2016

The ability to reproduce a parallel execution is desirable for debugging and program reliability purposes. In debugging (13), the programmer needs to manually step back in time, while for resilience (6) this is automatically performed by the the application upon failure. To be useful, replay has to faithfully reproduce the original execution. For parallel programs the main challenge is inferring and maintaining the order of conflicting operations (data races). Deterministic record and replay (R&R) techniques have been developed for multithreaded shared memory programs (5), as well as distributed memory programs (14). Our main interest is techniques for large scale scientific (3; 4) programming models.
Generic messages
Authors: Salucci Luca , Bonetta Daniele , Marr Stefan , Binder Walter
Published: November 2016

Systems based on event-loops have been popularized by Node.JS, and are becoming a key technology in the domain of cloud computing. Despite their popularity, such systems support only share-nothing parallelism via message passing between parallel entities usually called workers. In this paper, we introduce a novel parallel programming abstraction called Generic Messages (GEM
s
), which enables shared-memory parallelism for share-nothing event-based systems. A key characteristic of GEM
s
is that they enable workers to share state by specifying how the state can be accessed once it is shared. We call this aspect of the GEM
s
model capability-based parallelism.
Preemption-aware planning on big-data systems
Authors: Rabozzi Marco , Mazzucchelli Matteo , Cordone Roberto , Fumarola Giovanni Matteo , Santambrogio Marco D.
Published: November 2016

Recent developments in Big Data frameworks are moving towards reservation based approaches as a mean to manage the increasingly complex mix of computations, whereas preemption techniques are employed to meet strict jobs deadlines. Within this work we propose and evaluate a new planning algorithm in the context of reservation based scheduling. Our approach is able to achieve high cluster utilization while minimizing the need for preemption that causes system overheads and planning mispredictions.
Concurrent hash tables
Authors: Maier Tobias , Sanders Peter , Dementiev Roman
Published: November 2016

Concurrent hash tables are one of the most important concurrent data structures with numerous applications. Since hash table accesses can dominate the execution time of the overall application, we need implementations that achieve good speedup. Unfortunately, currently available concurrent hashing libraries turn out to be far away from this requirement in particular when contention on some elements occurs.

Our starting point for better performing data structures is a fast and simple lock-free concurrent hash table based on linear probing that is limited to word-sized key-value types and does not support dynamic size adaptation. We explain how to lift these limitations in a provably scalable way and demonstrate that dynamic growing has a performance overhead comparable to the same generalization in sequential hash tables.

We perform extensive experiments comparing the performance of our implementations with six of the most widely used concurrent hash tables. Ours are considerably faster than the best algorithms with similar restrictions and an order of magnitude faster than the best more general tables. In some extreme cases, the difference even approaches four orders of magnitude.
On designing NUMA-aware concurrency control for scalable transactional memory
Authors: Mohamedin Mohamed , Palmieri Roberto , Peluso Sebastiano , Ravindran Binoy
Published: November 2016

NUMA architectures posed the challenge of rethinking parallel applications due to the non-homogeneity introduced by their design, and their real benefits are limited to the characteristics of the particular workload. We name as
partitionable transactional workloads
such workloads that may be able to exploit the distributed nature of NUMA, such as transactional workloads where data and accesses can be easily partitioned among the so called NUMA zones. However, in case those workloads require the synchronization on shared data, we have to face the issue of exploiting the NUMA architecture also in the concurrency control for their transactions. Therefore in this paper we present a NUMA-aware concurrency control for transactional memory that we designed for promoting scalability in scenarios where both the transactional workload is prone to scale, and the characteristics of the underlying memory model are inherently non-uniform, such as NUMA architectures.
Merge-based sparse matrix-vector multiplication (SpMV) using the CSR storage format
Authors: Merrill Duane , Garland Michael
Published: November 2016

We present a perfectly balanced, "merge-based" parallel method for computing sparse matrix-vector products (SpMV). Our algorithm operates directly upon the Compressed Sparse Row (CSR) sparse matrix format, a predominant in-memory representation for general-purpose sparse linear algebra computations. Our CsrMV performs an equitable multi-partitioning of the input dataset, ensuring that no single thread can be overwhelmed by assignment to (a) arbitrarily-long rows or (b) an arbitrarily-large number of zero-length rows. This parallel decomposition requires neither offline preprocessing nor specialized/ancillary data formats. We evaluate our method on both CPU and GPU microarchitecture across an enormous corpus of diverse real world matrix datasets. We show that traditional CsrMV methods are inconsistent performers subject to order-of-magnitude slowdowns, whereas the performance response of our method is substantially impervious to row-length heterogeneity.
Affinity-aware work-stealing for integrated CPU-GPU processors
Authors: Farooqui Naila , Barik Rajkishore , Lewis Brian T. , Shpeisman Tatiana , Schwan Karsten
Published: November 2016

Recent integrated CPU-GPU processors like Intel's Broadwell and AMD's Kaveri support hardware CPU-GPU shared virtual memory, atomic operations, and memory coherency. This enables fine-grained CPU-GPU work-stealing, but architectural differences between the CPU and GPU hurt the performance of traditionally-implemented work-stealing on such processors. These architectural differences include different clock frequencies, atomic operation costs, and cache and shared memory latencies. This paper describes a preliminary implementation of our work-stealing scheduler, Libra, which includes techniques to deal with these architectural differences in integrated CPU-GPU processors. Libra's affinity-aware techniques achieve significant performance gains over classically-implemented work-stealing. We show preliminary results using a diverse set of nine regular and irregular workloads running on an Intel Broadwell Core-M processor. Libra currently achieves up to a 2× performance improvement over classical work-stealing, with a 20% average improvement.
Acute limb heating improves macro- and microvascular dilator function in the leg of aged humans
Authors: Romero Steven A. , Gagnon Daniel , Adams Amy N. , Cramer Matthew N. , Kouda Ken , Crandall Craig G.
Published: November 2016

Local heating of an extremity increases blood flow and vascular shear stress throughout the arterial tree. Local heating acutely improves macrovascular dilator function in the upper limbs of young healthy adults through a shear stress-dependent mechanism but has no such effect in the lower limbs of this age group. The effect of acute limb heating on dilator function within the atherosclerotic prone vasculature of the lower limbs of aged adults is unknown. Therefore, the purpose of this study was to test the hypothesis that acute lower limb heating improves macro- and microvascular dilator function within the leg vasculature of aged adults. Nine young and nine aged adults immersed their lower limbs at a depth of ~33 cm into a heated (~42°C) circulated water bath for 45 min. Before and 30 min after heating, macro (flow-mediated dilation)- and microvascular (reactive hyperemia) dilator functions were assessed in the lower limb, following 5 min of arterial occlusion, via Doppler ultrasound. Compared with preheat, macrovascular dilator function was unchanged following heating in young adults ( P = 0.6) but was improved in aged adults ( P = 0.04). Similarly, microvascular dilator function, as assessed by peak reactive hyperemia, was unchanged following heating in young adults ( P = 0.1) but was improved in aged adults ( P < 0.01). Taken together, these data suggest that acute lower limb heating improves both macro- and microvascular dilator function in an age dependent manner.

NEW & NOTEWORTHY We demonstrate that lower limb heating acutely improves macro- and microvascular dilator function within the atherosclerotic prone vasculature of the leg in aged adults. These findings provide evidence for a potential therapeutic use of chronic lower limb heating to improve vascular health in primary aging and various disease conditions.
Positive versus negative effects of VEGF165 on Ca2+ signaling and NO production in human endothelial cells
Authors: Boeldt Derek S. , Krupp Jennifer , Yi Fu-Xian , Khurshid Nauman , Shah Dinesh M. , Bird Ian M.
Published: November 2016

The role increased vascular endothelial growth factor (VEGF) plays in vascular function during normal vs. preeclamptic pregnancy has been a source of some controversy of late. In this study, we seek to understand how VEGF165 influences vasodilator production via Ca2+ signaling mechanisms in human endothelial cells. We utilize human umbilical vein endothelial cells (HUVEC) as well as intact ex vivo human umbilical vein (HUV Endo) to address direct stimulation of Ca2+ and NO by VEGF165 alone, as well as the effect of VEGF165 on subsequent ATP-stimulated Ca2+ signaling and NO production. We show that VEGF165 stimulates Ca2+ responses in both HUVEC and HUV Endo, which results in a corresponding increase in NO production in HUV Endo. Longer-term VEGF165 pretreatment then inhibits sustained Ca2+ burst responses to ATP in HUVEC and HUV Endo. This is paralleled by a corresponding drop in ATP-stimulated NO production in HUV Endo, likely through inhibition of Cx43 gap-junction function. Thus, although VEGF165 makes a small initial positive impact on vasodilator production via direct stimulation of Ca2+ responses, this is outweighed by the greater subsequent negative impact on Ca2+ bursts and vasodilator production promoted by more potent agonists such as ATP. Overall, elevated levels of VEGF165 associated with preeclampsia could contribute to the endothelial dysfunction by preventing Ca2+ bursts to other agonists including but not limited to ATP.

NEW & NOTEWORTHY In this manuscript, we show that VEGF levels associated with preeclampsia are a net negative contributor to potential vasodilator production in both a human ex vivo and in vitro endothelial cell model. Therefore, pharmacological targeting of VEGF-stimulated signaling pathways could be a novel treatment modality for preeclampsia-related hypertension.
Dung biomass smoke activates inflammatory signaling pathways in human small airway epithelial cells
Authors: McCarthy Claire E. , Duffney Parker F. , Gelein Robert , Thatcher Thomas H. , Elder Alison , Phipps Richard P. , Sime Patricia J.
Published: November 2016

Animal dung is a biomass fuel burned by vulnerable populations who cannot afford cleaner sources of energy, such as wood and gas, for cooking and heating their homes. Exposure to biomass smoke is the leading environmental risk for mortality, with over 4,000,000 deaths each year worldwide attributed to indoor air pollution from biomass smoke. Biomass smoke inhalation is epidemiologically associated with pulmonary diseases, including chronic obstructive pulmonary disease (COPD), lung cancer, and respiratory infections, especially in low and middle-income countries. Yet, few studies have examined the mechanisms of dung biomass smoke-induced inflammatory responses in human lung cells. Here, we tested the hypothesis that dung biomass smoke causes inflammatory responses in human lung cells through signaling pathways involved in acute and chronic lung inflammation. Primary human small airway epithelial cells (SAECs) were exposed to dung smoke at the air-liquid interface using a newly developed, automated, and reproducible dung biomass smoke generation system. The examination of inflammatory signaling showed that dung biomass smoke increased the production of several proinflammatory cytokines and enzymes in SAECs through activation of the activator protein (AP)-1 and arylhydrocarbon receptor (AhR) but not nuclear factor-κB (NF-κB) pathways. We propose that the inflammatory responses of lung cells exposed to dung biomass smoke contribute to the development of respiratory diseases.
Lethal H1N1 influenza A virus infection alters the murine alveolar type II cell surfactant lipidome
Authors: Woods Parker S. , Doolittle Lauren M. , Rosas Lucia E. , Joseph Lisa M. , Calomeni Edward P. , Davis Ian C.
Published: November 2016

Alveolar type II (ATII) epithelial cells are the primary site of influenza virus replication in the distal lung. Development of acute respiratory distress syndrome in influenza-infected mice correlates with significant alterations in ATII cell function. However, the impact of infection on ATII cell surfactant lipid metabolism has not been explored. C57BL/6 mice were inoculated intranasally with influenza A/WSN/33 (H1N1) virus (10,000 plaque-forming units/mouse) or mock-infected with virus diluent. ATII cells were isolated by a standard lung digestion protocol at 2 and 6 days postinfection. Levels of 77 surfactant lipid-related compounds of known identity in each ATII cell sample were measured by ultra-high-performance liquid chromatography-mass spectrometry. In other mice, bronchoalveolar lavage fluid was collected to measure lipid and protein content using commercial assay kits. Relative to mock-infected animals, ATII cells from influenza-infected mice contained reduced levels of major surfactant phospholipids (phosphatidylcholine, phosphatidylglycerol, and phosphatidylethanolamine) but increased levels of minor phospholipids (phosphatidylserine, phosphatidylinositol, and sphingomyelin), cholesterol, and diacylglycerol. These changes were accompanied by reductions in cytidine 5′-diphosphocholine and 5′-diphosphoethanolamine (liponucleotide precursors for ATII cell phosphatidylcholine and phosphatidylethanolamine synthesis, respectively). ATII cell lamellar bodies were ultrastructurally abnormal after infection. Changes in ATII cell phospholipids were reflected in the composition of bronchoalveolar lavage fluid, which contained reduced amounts of phosphatidylcholine and phosphatidylglycerol but increased amounts of sphingomyelin, cholesterol, and protein. Influenza infection significantly alters ATII cell surfactant lipid metabolism, which may contribute to surfactant dysfunction and development of acute respiratory distress syndrome in influenza-infected mice.