bluuebunny/crossref_metadata_2025 huggingface dataset:
EgoCap
Authors: Rhodin Helge , Richardt Christian , Casas Dan , Insafutdinov Eldar , Shafiei Mohammad , Seidel Hans-Peter , Schiele Bernt , Theobalt Christian
Published: November 2016

Marker-based and marker-less optical skeletal motion-capture methods use an
outside-in
arrangement of cameras placed around a scene, with viewpoints converging on the center. They often create discomfort with marker suits, and their recording volume is severely restricted and often constrained to indoor scenes with controlled backgrounds. Alternative suit-based systems use several inertial measurement units or an exoskeleton to capture motion with an
inside-in
setup, i.e. without external sensors. This makes capture independent of a confined volume, but requires substantial, often constraining, and hard to set up body instrumentation. Therefore, we propose a new method for real-time, marker-less, and egocentric motion capture: estimating the full-body skeleton pose from a lightweight stereo pair of fisheye cameras attached to a helmet or virtual reality headset - an
optical inside-in
method, so to speak. This allows full-body motion capture in general indoor and outdoor scenes, including crowded scenes with many people nearby, which enables reconstruction in larger-scale activities. Our approach combines the strength of a new generative pose estimation framework for fisheye views with a ConvNet-based body-part detector trained on a large new dataset. It is particularly useful in virtual reality to freely roam and interact, while seeing the fully motion-captured virtual body.
Functionality preserving shape style transfer
Authors: Lun Zhaoliang , Kalogerakis Evangelos , Wang Rui , Sheffer Alla
Published: November 2016

When geometric models with a desired combination of style and functionality are not available, they currently need to be created manually. We facilitate algorithmic synthesis of 3D models of man-made shapes which combines user-specified style, described via anexemplarshape, and functionality, encoded by a functionally differenttargetshape. Our method automatically transfers the style of the exemplar to the target, creating the desired combination. The main challenge in performing cross-functional style transfer is to implicitly separate an object's style from its function: while stylistically the output shapes should be as close as possible to the exemplar, their original functionality and structure, as encoded by the target, should be strictly preserved. Recent literature point to the presence of similarly shaped, salientgeometric elementsas a main indicator of stylistic similarity between 3D shapes. We therefore transfer the exemplar style to the target via a sequence of element-level operations. We allow onlycompatibleoperations, ones that do not affect the target functionality. To this end, we introduce a cross-structural element compatibility metric that estimates the impact of each operation on the edited shape. Our metric is based on the global context and coarse geometry of evaluated elements, and is trained on databases of 3D objects. We use this metric to cast style transfer as a tabu search, which incrementally updates the target shape using compatible operations, progressively increasing its style similarity to the exemplar while strictly maintaining its functionality at each step. We evaluate our framework across a range of man-made objects including furniture, light fixtures, and tableware, and perform a number of user studies confirming that it produces convincing outputs combining the desired style and function.
A scalable active framework for region annotation in 3D shape collections
Authors: Yi Li , Kim Vladimir G. , Ceylan Duygu , Shen I-Chao , Yan Mengyan , Su Hao , Lu Cewu , Huang Qixing , Sheffer Alla , Guibas Leonidas
Published: November 2016

Large repositories of 3D shapes provide valuable input for data-driven analysis and modeling tools. They are especially powerful once annotated with semantic information such as salient regions and functional parts. We propose a novel active learning method capable of enriching
massive
geometric datasets with
accurate
semantic region annotations. Given a shape collection and a user-specified region label our goal is to correctly demarcate the corresponding regions with minimal manual work. Our active framework achieves this goal by cycling between manually annotating the regions, automatically propagating these annotations across the rest of the shapes, manually verifying both human and automatic annotations, and learning from the verification results to improve the automatic propagation algorithm. We use a unified utility function that explicitly models the time cost of human input across all steps of our method. This allows us to jointly optimize for the set of models to annotate and for the set of models to verify based on the predicted impact of these actions on the human efficiency. We demonstrate that incorporating verification of all produced labelings within this unified objective improves both accuracy and efficiency of the active learning procedure. We automatically propagate human labels across a dynamic shape network using a conditional random field (CRF) framework, taking advantage of global shape-to-shape similarities, local feature similarities, and point-to-point correspondences. By combining these diverse cues we achieve higher accuracy than existing alternatives. We validate our framework on existing benchmarks demonstrating it to be significantly more efficient at using human input compared to previous techniques. We further validate its efficiency and robustness by annotating a massive shape dataset, labeling over 93,000 shape parts, across multiple model classes, and providing a labeled part collection more than
one order of magnitude
larger than existing ones.
Minimal BRDF sampling for two-shot near-field reflectance acquisition
Authors: Xu Zexiang , Nielsen Jannik Boll , Yu Jiyang , Jensen Henrik Wann , Ramamoorthi Ravi
Published: November 2016

We develop a method to acquire the BRDF of a homogeneous flat sample from only two images, taken by a near-field perspective camera, and lit by a directional light source. Our method uses the MERL BRDF database to determine the optimal set of lightview pairs for data-driven reflectance acquisition. We develop a mathematical framework to estimate error from a given set of measurements, including the use of multiple measurements in an image simultaneously, as needed for acquisition from near-field setups. The novel error metric is essential in the near-field case, where we show that using the condition-number alone performs poorly. We demonstrate practical near-field acquisition of BRDFs from only one or two input images. Our framework generalizes to configurations like a fixed camera setup, where we also develop a simple extension to spatially-varying BRDFs by clustering the materials.
FlexMolds
Authors: Malomo Luigi , Pietroni Nico , Bickel Bernd , Cignoni Paolo
Published: November 2016

We present FlexMolds, a novel computational approach to automatically design flexible, reusable molds that, once 3D printed, allow us to physically fabricate, by means of liquid casting, multiple copies of complex shapes with rich surface details and complex topology. The approach to design such flexible molds is based on a greedy bottom-up search of possible cuts over an object, evaluating for each possible cut the feasibility of the resulting mold. We use a dynamic simulation approach to evaluate candidate molds, providing a heuristic to generate forces that are able to open, detach, and remove a complex mold from the object it surrounds. We have tested the approach with a number of objects with nontrivial shapes and topologies.
Deep joint demosaicking and denoising
Authors: Gharbi Michaël , Chaurasia Gaurav , Paris Sylvain , Durand Frédo
Published: November 2016

Demosaicking and denoising are the key first stages of the digital imaging pipeline but they are also a severely ill-posed problem that infers three color values per pixel from a single noisy measurement. Earlier methods rely on hand-crafted filters or priors and still exhibit disturbing visual artifacts in hard cases such as moiré or thin edges. We introduce a new data-driven approach for these challenges: we train a deep neural network on a large corpus of images instead of using hand-tuned filters. While deep learning has shown great success, its naive application using existing training datasets does not give satisfactory results for our problem because these datasets lack hard cases. To create a better training set, we present metrics to identify difficult patches and techniques for mining community photographs for such patches. Our experiments show that this network and training procedure outperform state-of-the-art both on noisy and noise-free data. Furthermore, our algorithm is an order of magnitude faster than the previous best performing techniques.
VizGen
Authors: Yang Yuting , Prestwood Sam , Barnes Connelly
Published: November 2016

This paper introduces a novel domain-specific compiler, which translates visual computing programs written in dynamic languages to highly efficient code. We define "dynamic" languages as those such as Python and MATLAB, which feature dynamic typing and flexible array operations. Such language features can be useful for rapid prototyping, however, the dynamic computation model introduces significant overheads in program execution time. We introduce a compiler framework for accelerating visual computing programs, such as graphics and vision programs, written in generalpurpose dynamic languages. Our compiler allows substantial performance gains (frequently orders of magnitude) over general compilers for dynamic languages by specializing the compiler for visual computation. Specifically, our compiler takes advantage of three key properties of visual computing programs, which permit optimizations: (1) many array data structures have small, constant, or bounded size, (2) many operations on visual data are supported in hardware or are embarrassingly parallel, and (3) humans are not sensitive to small numerical errors in visual outputs due to changing floating-point precisions. Our compiler integrates program transformations that have been described previously, and improves existing transformations to handle visual programs that perform complicated array computations. In particular, we show that dependent type analysis can be used to infer sizes and guide optimizations for many small-sized array operations that arise in visual programs. Programmers who are not experts on visual computation can use our compiler to produce more efficient Python programs than if they write manually parallelized C, with fewer lines of application logic.
Robust light transport simulation via metropolised bidirectional estimators
Authors: Šik Martin , Otsu Hisanari , Hachisuka Toshiya , Křivánek Jaroslav
Published: November 2016

Efficiently simulating light transport in various scenes with a single algorithm is a difficult and important problem in computer graphics. Two major issues have been shown to hinder the efficiency of the existing solutions: light transport due to multiple highly glossy or specular interactions, and scenes with complex visibility between the camera and light sources. While recent bidirectional path sampling methods such as vertex connection and merging/unified path sampling (VCM/UPS) efficiently deal with highly glossy or specular transport, they tend to perform poorly in scenes with complex visibility. On the other hand, Markov chain Monte Carlo (MCMC) methods have been able to show some excellent results in scenes with complex visibility, but they behave unpredictably in scenes with glossy or specular surfaces due to their fundamental issue of sample correlation. In this paper, we show how to fuse the underlying key ideas behind VCM/UPS and MCMC into a single, efficient light transport solution. Our algorithm is specifically designed to retain the advantages of both approaches, while alleviating their limitations. Our experiments show that the algorithm can efficiently render scenes with both highly glossy or specular materials
and
complex visibility, without compromising the performance in simpler cases.
gTangle
Authors: Santoni Christian , Pellacini Fabio
Published: November 2016

Tangles are a form of structured pen-and-ink 2D art characterized by repeating, recursive patterns. We present a method to procedurally generate tangle drawings, seen as recursively split sets of arbitrary 2D polygons with holes, with anisotropic and non-stationary features. We formally model tangles with group grammars, an extension of set grammars, that explicitly handles the grouping of shapes necessary to represent tangle repetitions. We introduce a small set of expressive geometric and grouping operators, showing that they can respectively express complex tangles patterns and sub-pattern distributions, with relatively simple grammars. We also show how users can control tangle generation in an interactive and intuitive way. Throughout the paper, we show how group grammars can, in few tens of seconds, produce a wide variety of patterns that would take artists hours of tedious and time-consuming work. We then validated both the quality of the generated tangles and the efficiency of the control provided to the users with a user study, run with both expert and non-expert users.
Corrective 3D reconstruction of lips from monocular video
Authors: Garrido Pablo , Zollhöfer Michael , Wu Chenglei , Bradley Derek , Pérez Patrick , Beeler Thabo , Theobalt Christian
Published: November 2016

In facial animation, the accurate shape and motion of the lips of virtual humans is of paramount importance, since subtle nuances in mouth expression strongly influence the interpretation of speech and the conveyed emotion. Unfortunately, passive photometric reconstruction of expressive lip motions, such as a kiss or rolling lips, is fundamentally hard even with multi-view methods in controlled studios. To alleviate this problem, we present a novel approach for fully automatic reconstruction of detailed and expressive lip shapes along with the dense geometry of the entire face, from just monocular RGB video. To this end, we learn the difference between inaccurate lip shapes found by a state-of-the-art monocular facial performance capture approach, and the true 3D lip shapes reconstructed using a high-quality multi-view system in combination with applied lip tattoos that are easy to track. A robust gradient domain regressor is trained to infer accurate lip shapes from coarse monocular reconstructions, with the additional help of automatically extracted inner and outer 2D lip contours. We quantitatively and qualitatively show that our monocular approach reconstructs higher quality lip shapes, even for complex shapes like a kiss or lip rolling, than previous monocular approaches. Furthermore, we compare the performance of person-specific and multi-person generic regression strategies and show that our approach generalizes to new individuals and general scenes, enabling high-fidelity reconstruction even from commodity video footage.
SMASH
Authors: Monszpart Aron , Thuerey Nils , Mitra Niloy J.
Published: November 2016

Collision sequences are commonly used in games and entertainment to add drama and excitement. Authoring even two body collisions in the real world can be difficult, as one has to get timing and the object trajectories to be correctly synchronized. After tedious trial-and-error iterations, when objects can actually be made to collide, then they are difficult to capture in 3D. In contrast, synthetically generating plausible collisions is difficult as it requires adjusting different collision parameters (
e.g.,
object mass ratio, coefficient of restitution,
etc.
) and appropriate initial parameters. We present SMASH to directly
read off
appropriate collision parameters directly from raw input video recordings. Technically we enable this by utilizing laws of rigid body collision to regularize the problem of lifting 2D trajectories to a physically valid 3D reconstruction of the collision. The reconstructed sequences can then be modified and combined to easily author novel and plausible collisions. We evaluate our system on a range of synthetic scenes and demonstrate the effectiveness of our method by accurately reconstructing several complex real world collision events.
Directing user attention via visual flow on web designs
Authors: Pang Xufang , Cao Ying , Lau Rynson W. H. , Chan Antoni B.
Published: November 2016

We present a novel approach that allows web designers to easily direct user attention via visual flow on web designs. By collecting and analyzing users' eye gaze data on real-world webpages under the task-driven condition, we build two user attention models that characterize user attention patterns between a pair of page components. These models enable a novel web design interaction for designers to easily create a visual flow to guide users' eyes (i.e., direct user attention along a given path) through a web design with minimal effort. In particular, given an existing web design as well as a designer-specified path over a subset of page components, our approach automatically optimizes the web design so that the resulting design can direct users' attention to move along the input path. We have tested our approach on various web designs of different categories. Results show that our approach can effectively guide user attention through the web design according to the designer's high-level specification.
Manifold differential evolution (MDE)
Authors: Liu Yong-Jin , Xu Chun-Xu , Yi Ran , Fan Dian , He Ying
Published: November 2016

Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently out-performs the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.
Computational multicopter design
Authors: Du Tao , Schulz Adriana , Zhu Bo , Bickel Bernd , Matusik Wojciech
Published: November 2016

We present an interactive system for computational design, optimization, and fabrication of multicopters. Our computational approach allows non-experts to design, explore, and evaluate a wide range of different multicopters. We provide users with an intuitive interface for assembling a multicopter from a collection of components (e.g., propellers, motors, and carbon fiber rods). Our algorithm interactively optimizes shape and controller parameters of the current design to ensure its proper operation. In addition, we allow incorporating a variety of other metrics (such as payload, battery usage, size, and cost) into the design process and exploring tradeoffs between them. We show the efficacy of our method and system by designing, optimizing, fabricating, and operating multicopters with complex geometries and propeller configurations. We also demonstrate the ability of our optimization algorithm to improve the multicopter performance under different metrics.
A scalable schur-complement fluids solver for heterogeneous compute platforms
Authors: Liu Haixiang , Mitchell Nathan , Aanjaneya Mridul , Sifakis Eftychios
Published: November 2016

We present a scalable parallel solver for the pressure Poisson equation in fluids simulation which can accommodate complex irregular domains in the order of a billion degrees of freedom, using a single server or workstation fitted with GPU or Many-Core accelerators. The design of our numerical technique is attuned to the subtleties of heterogeneous computing, and allows us to benefit from the high memory and compute bandwidth of GPU accelerators even for problems that are too large to fit entirely on GPU memory. This is achieved via algebraic formulations that adequately increase the density of the GPU-hosted computation as to hide the overhead of offloading from the CPU, in exchange for accelerated convergence. Our solver follows the principles of Domain Decomposition techniques, and is based on the Schur complement method for elliptic partial differential equations. A large uniform grid is partitioned in non-overlapping subdomains, and bandwidth-optimized (GPU or Many-Core) accelerator cards are used to efficiently and concurrently solve independent Poisson problems on each resulting subdomain. Our novel contributions are centered on the careful steps necessary to assemble an accurate global solver from these constituent blocks, while avoiding excessive communication or dense linear algebra. We ultimately produce a highly effective Conjugate Gradients preconditioner, and demonstrate scalable and accurate performance on high-resolution simulations of water and smoke flow.
Interactive sound propagation with bidirectional path tracing
Authors: Cao Chunxiao , Ren Zhong , Schissler Carl , Manocha Dinesh , Zhou Kun
Published: November 2016

We introduce
Bidirectional Sound Transport (BST)
, a new algorithm that simulates sound propagation by bidirectional path tracing using multiple importance sampling. Our approach can handle multiple sources in large virtual environments with complex occlusion, and can produce plausible acoustic effects at an interactive rate on a desktop PC. We introduce a new metric based on the signal-to-noise ratio (SNR) of the energy response and use this metric to evaluate the performance of ray-tracing-based acoustic simulation methods. Our formulation exploits temporal coherence in terms of using the resulting sample distribution of the previous frame to guide the sample distribution of the current one. We show that our sample redistribution algorithm converges and better balances between early and late reflections. We evaluate our approach on different benchmarks and demonstrate significant speedup over prior geometric acoustic algorithms.
Efficient GPU path rendering using scanline rasterization
Authors: Li Rui , Hou Qiming , Zhou Kun
Published: November 2016

We introduce a novel GPU path rendering method based on scan-line rasterization, which is highly work-efficient but traditionally considered as GPU hostile. Our method is parallelized over
boundary fragments
, i.e., pixels directly intersecting the path boundary. Non-boundary pixels are processed in bulk as horizontal spans like in CPU scanline rasterizers, which saves a significant amount of winding number computation workload. The distinction also allows the majority of our algorithmic steps to focus on boundary fragments only, which leads to highly balanced workload among the GPU threads. In addition, we develop a ray shooting pattern that minimizes the global data dependency when computing winding numbers at anti-aliasing samples. This allows us to shift the majority of winding-number-related workload to the same kernel that consumes its result, which saves a significant amount of GPU memory bandwidth. Experiments show that our method gives a consistent 2.5X speedup over state-of-the-art alternatives for high-quality rendering at Ultra HD resolution, which can increase to more than 30X in extreme cases. We can also get a consistent 10X speedup on animated input.
Stair blue noise sampling
Authors: Kailkhura Bhavya , Thiagarajan Jayaraman J. , Bremer Peer-Timo , Varshney Pramod K.
Published: November 2016

A common solution to reducing visible aliasing artifacts in image reconstruction is to employ sampling patterns with a blue noise power spectrum. These sampling patterns can prevent discernible artifacts by replacing them with incoherent noise. Here, we propose a new family of blue noise distributions,
Stair blue noise
, which is mathematically tractable and enables parameter optimization to obtain the optimal sampling distribution. Furthermore, for a given sample budget, the proposed blue noise distribution achieves a significantly larger alias-free low-frequency region compared to existing approaches, without introducing visible artifacts in the mid-frequencies. We also develop a new sample synthesis algorithm that benefits from the use of an unbiased spatial statistics estimator and efficient optimization strategies.
Vivace
Authors: Fratarcangeli Marco , Tibaldo Valentina , Pellacini Fabio
Published: November 2016

The solution of large sparse systems of linear constraints is at the base of most interactive solvers for physically-based animation of soft body dynamics. We focus on applications with hard and tight per-frame resource budgets, such as video games, where the solution of soft body dynamics needs to be computed in a few milliseconds. Linear iterative methods are preferred in these cases since they provide approximate solutions within a given error tolerance and in a short amount of time. We present a parallel randomized Gauss-Seidel method which can be effectively employed to enable the animation of 3D soft objects discretized as large and irregular triangular or tetrahedral meshes. At the beginning of each frame, we partition the set of equations governing the system using a randomized graph coloring algorithm. The unknowns in the equations belonging to the same partition are independent of each other. Then, all the equations belonging to the same partition are solved at the same time in parallel. Our algorithm runs completely on the GPU and can support changes in the constraints topology. We tested our method as a solver for soft body dynamics within the Projective Dynamics and Position Based Dynamics frameworks. We show how the algorithmic simplicity of this iterative strategy enables great numerical stability and fast convergence speed, which are essential features for physically based animations with fixed and small hard time budgets. Compared to the state of the art, we found our method to be faster and scale better while providing stabler solutions for very small time budgets.
Image-space control variates for rendering
Authors: Rousselle Fabrice , Jarosz Wojciech , Novák Jan
Published: November 2016

We explore the theory of integration with control variates in the context of rendering. Our goal is to optimally combine multiple estimators using their covariances. We focus on two applications, re-rendering and gradient-domain rendering, where we exploit coherence between temporally and spatially adjacent pixels. We propose an image-space (iterative) reconstruction scheme that employs control variates to reduce variance. We show that recent works on scene editing and gradient-domain rendering can be directly formulated as control-variate estimators, despite using seemingly different approaches. In particular, we demonstrate the conceptual equivalence of screened Poisson image reconstruction and our iterative reconstruction scheme. Our composite estimators offer practical and simple solutions that improve upon the current state of the art for the two investigated applications.
Parallel type-checking with haskell using saturating LVars and stream generators
Authors: Newton Ryan R. , Ağacan Ömer S. , Fogg Peter , Tobin-Hochstadt Sam
Published: November 2016

Given the sophistication of recent type systems, unification-based type-checking and inference can be a time-consuming phase of compilation---especially when union types are combined with subtyping. It is natural to consider improving performance through parallelism, but these algorithms are challenging to parallelize due to complicated control structure and difficulties representing data in a way that is both efficient and supports concurrency. We provide techniques that address these problems based on the LVish approach to deterministic-by-default parallel programming. We extend LVish with
Saturating LVars
, the first LVars implemented to release memory during the object's lifetime. Our design allows us to achieve a parallel speedup on worst-case (exponential) inputs of Hindley-Milner inference, and on the
Typed Racket type-checking algorithm
, which yields up an 8.46× parallel speedup on 14 cores for type-checking examples drawn from the Racket repository.
Drinking from both glasses
Authors: Cao Man , Zhang Minjia , Sengupta Aritra , Bond Michael D.
Published: November 2016

It is notoriously challenging to develop parallel software systems that are both scalable and correct. Runtime support for parallelism---such as multithreaded record & replay, data race detectors, transactional memory, and enforcement of stronger memory models---helps achieve these goals, but existing commodity solutions slow programs substantially in order to track (i.e., detect or control) an execution's cross-thread dependences accurately. Prior work tracks cross-thread dependences either "pessimistically," slowing every program access, or "optimistically," allowing for lightweight instrumentation of most accesses but dramatically slowing accesses involved in cross-thread dependences.

This paper seeks to
hybridize
pessimistic and optimistic tracking, which is challenging because there exists a fundamental mismatch between pessimistic and optimistic tracking. We address this challenge based on insights about how dependence tracking and program synchronization interact, and introduce a novel approach called
hybrid tracking
. Hybrid tracking is suitable for building efficient runtime support, which we demonstrate by building hybrid-tracking-based versions of a dependence recorder and a region serializability enforcer. An adaptive, profile-based policy makes runtime decisions about switching between pessimistic and optimistic tracking. Our evaluation shows that hybrid tracking enables runtime support to overcome the performance limitations of both pessimistic and optimistic tracking alone.
Gunrock
Authors: Wang Yangzihao , Davidson Andrew , Pan Yuechao , Wu Yuduo , Riffel Andy , Owens John D.
Published: November 2016

For large-scale graph analytics on the GPU, the irregularity of data access/control flow and the complexity of programming GPUs have been two significant challenges for developing a programmable high-performance graph library. "Gunrock," our high-level bulk-synchronous graph-processing system targeting the GPU, takes a new approach to abstracting GPU graph analytics: rather than designing an abstraction around
computation
, Gunrock instead implements a novel
data-centric
abstraction centered on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high-performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge. We evaluate Gunrock on five graph primitives (BFS, BC, SSSP, CC, and PageRank) and show that Gunrock has on average at least an order of magnitude speedup over Boost and PowerGraph, comparable performance to the fastest GPU hardwired primitives, and better performance than any other GPU high-level graph library.
Production-guided concurrency debugging
Authors: Machado Nuno , Lucia Brandon , Rodrigues Luís
Published: November 2016

Concurrency bugs that stem from schedule-dependent branches are hard to understand and debug, because their root causes imply not only different event orderings, but also changes in the control-flow between failing and non-failing executions. We present Cortex: a system that helps exposing and understanding concurrency bugs that result from schedule-dependent branches, without relying on information from failing executions. Cortex preemptively exposes failing executions by perturbing the order of events and control-flow behavior in non-failing schedules from production runs of a program. By leveraging this information from production runs, Cortex synthesizes executions to guide the search for failing schedules. Production-guided search helps cope with the large execution search space by targeting failing executions that are similar to observed non-failing executions. Evaluation on popular benchmarks shows that Cortex is able to expose failing schedules with only a few perturbations to non-failing executions, and takes a practical amount of time.
A high-performance parallel algorithm for nonnegative matrix factorization
Authors: Kannan Ramakrishnan , Ballard Grey , Park Haesun
Published: November 2016

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors
W
and
H
, for the given input matrix
A
, such that
A
≈
WH
. NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient distributed algorithms to solve the problem for big data sets.

We propose a high-performance distributed-memory parallel algorithm that computes the factorization by iteratively solving alternating non-negative least squares (NLS) subproblems for
W
and
H
. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). As opposed to previous implementations, our algorithm is also flexible: (1) it performs well for both dense and sparse matrices, and (2) it allows the user to choose any one of the multiple algorithms for solving the updates to low rank factors
W
and
H
within the alternating iterations. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements.
Distributed Halide
Authors: Denniston Tyler , Kamil Shoaib , Amarasinghe Saman
Published: November 2016

Many image processing tasks are naturally expressed as a pipeline of small computational kernels known as stencils. Halide is a popular domain-specific language and compiler designed to implement image processing algorithms. Halide uses simple language constructs to express what to compute and a separate scheduling co-language for expressing when and where to perform the computation. This approach has demonstrated performance comparable to or better than hand-optimized code. Until now, however, Halide has been restricted to parallel shared memory execution, limiting its performance for memory-bandwidth-bound pipelines or large-scale image processing tasks.

We present an extension to Halide to support distributed-memory parallel execution of complex stencil pipelines. These extensions compose with the existing scheduling constructs in Halide, allowing expression of complex computation and communication strategies. Existing Halide applications can be distributed with minimal changes, allowing programmers to explore the tradeoff between recomputation and communication with little effort. Approximately 10 new of lines code are needed even for a 200 line, 99 stage application. On nine image processing benchmarks, our extensions give up to a 1.4× speedup on a single node over regular multithreaded execution with the same number of cores, by mitigating the effects of non-uniform memory access. The distributed benchmarks achieve up to 18× speedup on a 16 node testing machine and up to 57× speedup on 64 nodes of the NERSC Cori supercomputer.
DomLock
Authors: Kalikar Saurabh , Nasre Rupesh
Published: November 2016

We present efficient locking mechanisms for hierarchical data structures. Several applications work on an abstract hierarchy of objects, and a parallel execution on this hierarchy necessitates synchronization across workers operating on different parts of the hierarchy. Existing synchronization mechanisms are either too coarse, too inefficient, or too
ad hoc
, resulting in reduced or unpredictable amount of concurrency. We propose a new locking approach based on the structural properties of the underlying hierarchy. We show that the developed techniques are efficient even when the hierarchy is an arbitrary graph, and are applicable even when the hierarchy involves mutation. Theoretically, we present our approach as a locking-cost-minimizing instance of a generic algebraic model of synchronization for hierarchical data structures. Using STMBench7, we illustrate considerable reduction in the locking cost, resulting in an average throughput improvement of 42%.
Contention-conscious, locality-preserving locks
Authors: Chabbi Milind , Mellor-Crummey John
Published: November 2016

Over the last decade, the growing use of cache-coherent NUMA architectures has spurred the development of numerous
locality-preserving
mutual exclusion algorithms. NUMA-aware locks such as HCLH, HMCS, and cohort locks exploit locality of reference among nearby threads to deliver high lock throughput under high contention. However, the hierarchical nature of these locality-aware locks increases latency, which reduces the throughput of uncontended or lightly-contended critical sections. To date, no lock design for NUMA systems has delivered both low latency under low contention and high throughput under high contention.

In this paper, we describe the design and evaluation of an adaptive mutual exclusion scheme (AHMCS lock), which employs several orthogonal strategies---a hierarchical MCS (HMCS) lock for high throughput under high contention, Lamport's fast path approach for low latency under low contention, an adaptation mechanism that employs hysteresis to balance latency and throughput under moderate contention, and hardware transactional memory for lowest latency in the absence of contention. The result is a top performing lock that has most properties of an ideal mutual exclusion algorithm. AHMCS exploits the strengths of multiple contention management techniques to deliver high performance over a broad range of contention levels. Our empirical evaluations demonstrate the effectiveness of AHMCS over prior art.
GPU multisplit
Authors: Ashkiani Saman , Davidson Andrew , Meyer Ulrich , Owens John D.
Published: November 2016

Multisplit is a broadly useful parallel primitive that permutes its input data into contiguous
buckets
or
bins
, where the function that categorizes an element into a bucket is provided by the programmer. Due to the lack of an efficient multisplit on GPUs, programmers often choose to implement multisplit with a sort. However, sort does more work than necessary to implement multisplit, and is thus inefficient. In this work, we provide a parallel model and multiple implementations for the multisplit problem. Our principal focus is multisplit for a small number of buckets. In our implementations, we exploit the computational hierarchy of the GPU to perform most of the work locally, with minimal usage of global operations. We also use warp-synchronous programming models to avoid branch divergence and reduce memory usage, as well as hierarchical reordering of input elements to achieve better coalescing of global memory accesses. On an NVIDIA K40c GPU, for key-only (key-value) multisplit, we demonstrate a 3.0-6.7x (4.4-8.0x) speedup over radix sort, and achieve a peak throughput of 10.0 G keys/s.
Data-centric combinatorial optimization of parallel code
Authors: Luo Hao , Chen Guoyang , Li Pengcheng , Ding Chen , Shen Xipeng
Published: November 2016

Memory performance is one essential factor for tapping into the full potential of the massive parallelism of GPU. It has motivated some recent efforts in GPU cache modeling. This paper presents a new data-centric way to model the performance of a system with heterogeneous memory resources. The new model is composable, meaning it can predict the performance difference due to placing data differently by profiling the execution just once.
NUMA-aware scheduling and memory allocation for data-flow task-parallel applications
Authors: Drebes Andi , Pop Antoniu , Heydemann Karine , Drach Nathalie , Cohen Albert
Published: November 2016

Dynamic task parallelism is a popular programming model on shared-memory systems. Compared to data parallel loop-based concurrency, it promises enhanced scalability, load balancing and locality. These promises, however, are undermined by non-uniform memory access (NUMA) systems. We show that it is possible to preserve the uniform hardware abstraction of contemporary task-parallel programming models, for both computing and memory resources, while achieving near-optimal data locality. Our run-time algorithms for NUMA-aware task and data placement are fully automatic, application-independent, performance-portable across NUMA machines, and adapt to dynamic changes. Placement decisions use information about inter-task data dependences and reuse. This information is readily available in the run-time systems of modern task-parallel programming frameworks, and from the operating system regarding the placement of previously allocated memory. Our algorithms take advantage of data-flow style task parallelism, where the privatization of task data enhances scalability through the elimination of false dependences and enables fine-grained dynamic control over the placement of application data. We demonstrate that the benefits of dynamically managing data placement outweigh the privatization cost, even when comparing with target-specific optimizations through static, NUMA-aware data interleaving. Our implementation and the experimental evaluation on a set of high-performance benchmarks executing on a 192-core system with 24 NUMA nodes show that the fraction of local memory accesses can be increased to more than 99%, resulting in a speedup of up to 5× compared to a NUMA-aware hierarchical work-stealing baseline.
Dynamical mechanisms of phase-2 early afterdepolarizations in human ventricular myocytes: insights from bifurcation analyses of two mathematical models
Authors: Kurata Yasutaka , Tsumoto Kunichika , Hayashi Kenshi , Hisatome Ichiro , Tanida Mamoru , Kuda Yuhichi , Shibamoto Toshishige
Published: November 2016

Early afterdepolarization (EAD) is known as a cause of ventricular arrhythmias in long QT syndromes. We theoretically investigated how the rapid ( IKr) and slow ( IKs) components of delayed-rectifier K+ channel currents, L-type Ca2+ channel current ( ICaL), Na+/Ca2+ exchanger current ( INCX), Na+-K+ pump current ( INaK), intracellular Ca2+ (Cai) handling via sarcoplasmic reticulum (SR), and intracellular Na+ concentration (Nai) contribute to initiation, termination, and modulation of phase-2 EADs, using two human ventricular myocyte models. Bifurcation structures of dynamical behaviors in model cells were explored by calculating equilibrium points, limit cycles (LCs), and bifurcation points as functions of parameters. EADs were reproduced by numerical simulations. The results are summarized as follows: 1) decreasing IKs and/or IKr or increasing ICaL led to EAD generation, to which mid-myocardial cell models were especially susceptible; the parameter regions of EADs overlapped the regions of stable LCs. 2) Two types of EADs (termination mechanisms), IKs activation–dependent and ICaL inactivation–dependent EADs, were detected; IKs was not necessarily required for EAD formation. 3) Inhibiting INCX suppressed EADs via facilitating Ca2+-dependent ICaL inactivation. 4) Cai dynamics (SR Ca2+ handling) and Nai strongly affected bifurcations and EAD generation in model cells via modulating ICaL, INCX, and INaK. Parameter regions of EADs, often overlapping those of stable LCs, shifted depending on Cai and Nai in stationary and dynamic states. 5) Bradycardia-related induction of EADs was mainly due to decreases in Nai at lower pacing rates. This study demonstrates that bifurcation analysis allows us to understand the dynamical mechanisms of EAD formation more profoundly.

NEW & NOTEWORTHY We investigated mechanisms of phase-2 early afterdepolarization (EAD) by bifurcation analyses of human ventricular myocyte (HVM) models. EAD formation in paced HVMs basically depended on bifurcation phenomena in non-paced HVMs, but was strongly affected by intracellular ion concentrations in stationary and dynamic states. EAD generation did not necessarily require IKs.
Lifelong quercetin enrichment and cardioprotection in Mdx/Utrn+/− mice
Authors: Ballmann Christopher , Denney Thomas S. , Beyers Ronald J. , Quindry Tiffany , Romero Matthew , Amin Rajesh , Selsby Joshua T. , Quindry John C.
Published: November 2016

Duchenne Muscular Dystrophy (DMD) is associated with progressive cardiac pathology; however, the SIRT1/PGC1-α activator quercetin may cardioprotect dystrophic hearts. We tested the extent to which long-term 0.2% dietary quercetin enrichment attenuates dystrophic cardiopathology in Mdx/Utrn+/− mice. At 2 mo, Mdx/Utrn+/− mice were fed quercetin-enriched (Mdx/Utrn+/−-Q) or control diet (Mdx/Utrn+/−) for 8 mo. Control C57BL/10 (C57) animals were fed a control diet for 10 mo. Cardiac function was quantified by MRI at 2 and 10 mo. Spontaneous physical activity was quantified during the last week of treatment. At 10 mo hearts were excised for histological and biochemical analysis. Quercetin feeding improved various physiological indexes of cardiac function in diseased animals. Mdx/Utrn+/−-Q also engaged in more high-intensity physical activity than controls. Histological analyses of heart tissues revealed higher expression and colocalization of utrophin and α-sarcoglycan. Lower abundance of fibronectin, cardiac damage (Hematoxylin Eosin-Y), and MMP9 were observed in quercetin-fed vs. control Mdx/Utrn+/− mice. Quercetin evoked higher protein abundance of PGC-1α, cytochrome c, ETC complexes I–V, citrate synthase, SOD2, and GPX compared with control-fed Mdx/Utrn+/−. Quercetin decreased abundance of inflammatory markers including NFκB, TGF-β1, and F4/80 compared with Mdx/Utrn+/−; however, P-NFκB, P-IKBα, IKBα, CD64, and COX2 were similar between groups. Dietary quercetin enrichment improves cardiac function in aged Mdx/Utrn+/− mice and increases mitochondrial protein content and dystrophin glycoprotein complex formation. Histological analyses indicate a marked attenuation in pathological cardiac remodeling and indicate that long-term quercetin consumption benefits the dystrophic heart.

NEW & NOTEWORTHY The current investigation provides first-time evidence that quercetin provides physiological cardioprotection against dystrophic pathology and is associated with improved spontaneous physical activity. Secondary findings suggest that quercetin-dependent outcomes are in part due to PGC-1α pathway activation.