Existing tiled manycore architectures propose to convert abundant silicon resources into general-purpose parallel processors with unmatched computational density and programmability. However, as we approach 100 K cores in one chip, conventional manycore architectures struggle to navigate three key axes: scalability, programmability, and density. Many manycores sacrifice programmability for density; or scalability for programmability. In this paper, we explore HammerBlade, which simultaneously achieves scalability, programmability and density. HammerBlade is a fully open-source RISC-V manycore architecture, which has been silicon-validated with a 2048-core ASIC implementation using a 14/16nm process. We evaluate the system using a suite of parallel benchmarks that captures a broad spectrum of computation and communication patterns.

Hypergraphs offer flexible and robust data representations for many applications, but methods that work directly on hypergraphs are not readily available and tend to be prohibitively expensive. Much of the current analysis of hypergraphs relies on first performing a graph expansion – either based on the nodes (clique expansion), or on the hyperedges (line graph) − and then running standard graph analytics on the resulting representative graph. However, this approach suffers from massive space complexity and high computational cost with increasing hypergraph size. Here, we present efficient, parallel algorithms to accelerate and reduce the memory footprint of higher-order graph expansions of hypergraphs. Our results focus on the hyperedge-based s-line graph expansion, but the methods we develop work for higher-order clique expansions as well. To the best of our knowledge, ours is the first framework to enable hypergraph spectral analysis of a large dataset on a single shared-memory machine. Our methods enable the analysis of datasets from many domains that previous graph-expansion-based models are unable to provide. The proposed s-line graph computation algorithms are orders of magnitude faster than state-of-the-art sparse general matrix-matrix multiplication methods, and obtain approximately 2–31× speedup over a prior state-of-the-art heuristic-based algorithm for$s$-line graph computation.

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hyper-graphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected if there is at least one common “neighbor”. However, minimal commonality sometimes discards the “strength” of connections and interactions among groups. To this end, considering the “width” of a connection, referred to as the s-overlap of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, s-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the s-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute s-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the s-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than 10x) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large$s$value).

One of the tasks for the SC19 Student Cluster Competition is to reproduce the results in the reproducibility challenge article “Computing Planetary Interior Normal Modes with a Highly Parallel Polynomial Filtering Eigensolver”, by J. Shi et al., which describes a highly parallel algorithm for computing planetary normal modes. In running experiments from the article, we study the weak and strong scalability of the algorithm, as well as the relationship between model size, degree of polynomial filter, and execution time. We investigate these findings on a two-node, 64-core Intel Skylake-based Xeon cluster. Unfortunately, we are able to confirm some, but not all, of the original findings, with discrepancies possibly due to a low number of experimental runs due to competition time limits as well as nonuniform scaling of compute resources.

Label Propagation, while more commonly known as a machine learning algorithm for classification, is also an effective method for detecting communities in networks. We propose a new Direction Optimizing Label Propagation Algorithm (DOLPA) that relies on the use of frontiers and alternates between label push and label pull operations to enhance the performance of the standard Label Propagation Algorithm (LPA). Specifically, DOLPA has parameters for tuning the processing order of vertices in a graph, which in turn reduces the number of edges visited and improves the quality of solution obtained. We apply DOLPA to the community detection problem, present the design and implementation of the algorithm, and discuss its shared-memory parallelization using OpenMP. Empirically, we evaluate our algorithm using synthetic graphs as well as real-world networks. Compared with the state-of-the-art Parallel Label Propagation algorithm, we achieve at least two times the F-Score while reducing the runtime by 50% for synthetic graphs with overlapping communities. We also compare DOLPA against state of the art parallel implementation of the Louvain method using the same graphs and show that DOLPA achieves about three times the F-Score at 10% the runtime.

A light field contains information in four dimensions, two spatial and two angular. Representing a light field by sampling it with a fixed number of pixels implies an inherent trade-off between angular resolution and spatial resolution- one apparently fixed at the time of capture. To enable flexible trade-offs in spatial and angular resolution after the fact, in this paper we apply techniques from super resolution in an integrated fashion. Our approach explores the similarity between light field super resolution (LFSR) and single image super resolution (SISR) and proposes a neural network framework that can carry out flexible super resolution tasks. We present concrete instances of the framework for center-view spatial LFSR, full-view spatial LFSR, and combined spatial and angular LFSR. Experiments with synthetic and real-world data sets show the center-view and full-views approaches outperform state-of-the-art spatial LFSR by over 1dB in PSNR and that the combined approach achieves comparable performance to state-of-the-art spatial LFSR algorithms. Visual results for images rendered from the combined approach show improved resolution of detail, without rendering artifacts.

As with many imaging tasks, disparity estimation for light fields seems to be well-matched to machine learning approaches. Neural network-based methods can achieve an overall bad pixel rate as low as four percent on the 4D light field benchmark dataset, continued effort to improve accuracy is resulting in diminishing returns. On the other hand, due to the growing importance of mobile and embedded devices, improving the efficiency is emerging as an important problem. In this paper, we improve the efficiency of existing neural net approaches for light field disparity estimation by introducing efficient network blocks, pruning redundant sections of the network and downsampling the resolution of feature vector. To improve performance, we also propose densely sampled epipolar image plane volumes as input. Experiment results show that our approach can achieve similar results compared with state-of-the-art methods while using only one-tenth runtime.

Learning based depth estimation from light field has made significant progresses in recent years. However, most existing approaches are under the supervised framework, which requires vast quantities of ground-truth depth data for training. Furthermore, accurate depth maps of light field are hardly available except for a few synthetic datasets. In this paper, we exploit the multi-orientation epipolar geometry of light field and propose an unsupervised monocular depth estimation network. It predicts depth from the central view of light field without any ground-truth information. Inspired by the inherent depth cues and geometry constraints of light field, we then introduce three novel unsupervised loss functions: photometric loss, defocus loss and symmetry loss. We have evaluated our method on a public 4D light field synthetic dataset. As the first unsupervised method published in the 4D Light Field Benchmark website, our method can achieve satisfactory performance in most error metrics. Comparison experiments with two state-of-the-art unsupervised methods demonstrate the superiority of our method. We also prove the effectiveness and generality of our method on real-world light-field images.

In this paper, we propose a distributed, unordered, label-correcting distance-1 Grundy (vertex) coloring algorithm, namely, Distributed Control (DC) coloring algorithm. Our algorithm eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. DC proceeds optimistically, correcting the colors asynchronously as the algorithm progresses and depends on local ordering of tasks to minimize the execution of sub-optimal work. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm and compare their performance with 4 different types of standard RMAT graphs and real-world graphs. We show that the elimination of waiting time of global and vertex-centric barriers and investing this time for local ordering leads to improved scaling for graphs with prominent power-law characteristics and densely interconnected local subgraphs.

Economic competitiveness and national security depend increasingly on the insightful analysis of large data sets. The diversity of real-world data sources and analytic workflows impose challenging hardware and software requirements for parallel graph platforms. The irregular nature of graph methods is not supported well by the deep memory hierarchies of conventional distributed systems, requiring new processor and runtime system designs to tolerate memory and synchronization latencies. Moreover, the efficiency of relational table operations and matrix computations are not attainable when data is stored in common graph data structures. In this paper, we present HAGGLE, a high-performance, scalable data analytics platform. The platform's hybrid data model supports a variety of distributed, thread-safe data structures, parallel programming constructs, and persistent and streaming data. An abstract runtime layer enables us to map the stack to conventional, distributed computer systems with accelerators. The runtime uses multithreading, active messages, and data aggregation to hide memory and synchronization latencies on large-scale systems.

Deep neural networks have shown their excellent abilities in light field depth estimation. Most of learning based approaches focus on the depth feature extraction from the epipolar plane images (EPIs) or sub-apertures of light field, while pay less attention to the focal stack which is also one of the most distinctive characteristics of light field. In this paper, we propose a FocalStackNet which learns depth semantic features and local structure information from the focal stack for light field depth estimation. Specifically, we formulate the disparity estimation as a pixel-wise classification task, and discretize the continuous disparity range into 115 bins. Then we generate a discrete focal stack and extract a set of focal stack patches as training data. Finally, we train a two-pathway convolutional neural networks (CNN) to predict the disparity label of each pixel. Evaluation experiments are carried on the public 4D light field synthetic dataset. Our method achieves state-of-the-art performance. It ranks first among the published methods on the aspects of average and median error scores of Bad Pixel Ratio 0.03.

To take full advantage of modern high performance architectures, many large-scale data-driven applications require loosely-coupled, fine-grained asynchronous communication. Accordingly, efficient lightweight middleware based on state-of-the-art networking technology such as RDMA is becoming a necessity. The performance critical task of handling RDMA synchronization, for existing message passing runtimes are mostly coarse granular in nature and thus may be associated with various hidden costs. While low-level RDMA libraries expose fine-grained RDMA communication that can be efficiently controlled, the critical tasks of RDMA buffer management, synchronization and flow control are left to the userspace applications requiring tedious programming effort that may lead to sub-optimal performance. In this paper we present a user-space RDMA transport layer that allows RDMA-enabled memory to be managed internally while still exposing zero-copy completion event-based RDMA transfers for message passing. The integration of an RDMA transport layer enables the opportunity for parallel applications to utilize RDMA-managed buffers for accelerating communication while co-existing with high-level MPI, GASNet or similar middleware. We show a performance speedup of up to 8X in latency/bandwidth benchmarks and 5%-90% improvement in response time or messaging rate in three reference applications with regard to their MPI implementations.

Today's cutting-edge network hardware features extremely low latency and high bandwidth transactions for higher-level communication substrates. The Cray XC/XE family of network fabrics, also known as Cray Aries/Gemini respectively, supports such high-performance remote memory access operations (RMA) and a plethora of transaction modes to optimize communication via lower-level interfaces such as uGNI and DMAPP. However, enabling efficient one-sided communication for higher-level substrates is difficult due to barriers presented by the programming model itself, as well as miscellaneous synchronization bottlenecks at the runtime layers. We present an efficient programming model based on a distributed memory allocator for RMA and a communication substrate based on readers and writers for inter-node message passing and RMA operations. We try to maximize performance by introducing a scalable RMA event notification scheme and synchronization protocols that fully leverage Aries/Gemini fabric. Micro-benchmark results demonstrate that our library outperforms Cray MPI-3.0-based RMA one-sided operations by 1.5X and up to 6X in certain cases and is comparable or improves upon performance on others.

Because they were developed for optimal sequential complexity, classical graph algorithms as found in textbooks have strictly-defined orders of operations. Enforcing a prescribed order of operations, or even an approximate order, in a distributed memory setting requires significant amounts of synchronization, which in turn can severely limit scalability. As a result, new algorithms are typically required to achieve scalable performance, even for solving well-known graph problems. Yet, even in these cases, parallel graph algorithms are written according to parallel programming models that evolved for, e.g., scientific computing, and that still have inherent, and scalability-limiting, amounts of synchronization. In this paper we present a new approach to parallel graph algorithms: synchronization-avoiding algorithms. To eliminate synchronization and its associated overhead, synchronization-avoiding algorithms perform work in an unordered and fully asynchronous fashion in such a way that the result is constantly refined toward its final state. "Wasted" work is minimized by locally prioritizing tasks using problem-dependent task utility metrics. We classify algorithms for graph applications into two broad categories: algorithms with monotonic updates (which evince global synchronization) and algorithms with non-monotonic updates (which evince vertex-centric synchronization). We apply our approach to both classes and develop novel, synchronization-avoiding algorithms for solving exemplar problems: SSSP and connected components for the former, graph coloring for the latter. We demonstrate that eliminating synchronization in conjunction with effective scheduling policies and optimizations in the runtime results in improved scalability for both classes of algorithms.

The following topics are dealt with: parallel processing; learning (artificial intelligence); graphics processing units; graph theory; parallel algorithms; scheduling; application program interfaces; parallel architectures; storage management; parallel machines.

Epipolar Plane Image (EPI) implies some important depth cues for light field depth estimation. Intuitively, the EPI patches with different spatial scales and orientations may exhibit different features and result in different estimation precision. In this paper, we discuss this issue and present a scale and orientation aware EPI-Patch learning model for depth estimation. We take the multi-orientation EPI patches of each pixel as input, and design two types of network structures for adaptive scale selection and orientation fusion. One type is a scale-aware structure, which feeds one orientation patch into a multi-layer feed-forward network with long and short skip connections. The other type is a shared-weight network for fusing the multi-orientation features. We demonstrate the effectiveness of our model by experiments on 4D Light Field Benchmark.

In this paper we explore scheduling and runtime system support for unordered distributed graph computations that rely on optimistic (speculative) execution. Performance of such algorithms is impacted by two competing trends: the higher degree of parallelism enabled by optimistic execution in turn requires substantial runtime support. To address the potentially high overhead and scheduling complexity introduced by the runtime, we investigate customizable scheduling policies that augment the scheduler of the underlying runtime to adapt it to a specific graph application. We present several implementations of Distributed Control (DC), a data-driven unordered approach with work prioritization and demonstrate that customizable scheduling policies result in the most efficient implementation, outperforming the well-known ?-stepping Single-Source Shortest Paths (SSSP) and Jones-Plassmann vertex-coloring algorithms. We apply two scheduling techniques, flow control and adaptive frequency of network progress, which allow application-level control over the balance of domain work and the runtime work. Experimental results show the benefit of such application-aware scheduling for irregular distributed graph algorithms.

We propose a distributed, unordered, label-correcting distance-1 vertex coloring algorithm, called Distributed Control (DC) coloring algorithm. DC eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm in the AM++ AMT runtime and compare their performance. We show that, with runtime support, the elimination of waiting time of vertex-centric barriers and investing this time for local ordering results in better execution time for power-law graphs with dense local subgraphs.

The maximal independent set (MIS) graph problem arises in many applications such as computer vision, information theory, molecular biology, and process scheduling. The growing scale of graph data suggests the use of distributed memory hardware as a cost-effective approach to providing necessary compute and memory resources. Existing distributed memory parallel MIS algorithms rely on synchronous communication and use techniques such as subgraph computations. In this paper, we present an asynchronous distributed-memory parallel graph algorithm that relies on a virtual directed acyclic graph (DAG) that is created during the algorithm execution. We introduce two additional algorithms that save computations by ordering generated work. The first algorithm applies ordering globally to reduce computations, and the second algorithm applies ordering locally at the level of threads to minimize the synchronization overhead. We use two different implementations of Luby's algorithm variants as baseline to compare the performance of the presented algorithms: (1) vertex-centric Luby A and Luby B implementations, and (2) the CombBLAS linear-algebra Luby A implementation. Results show that proposed algorithms outperform both implementations of Luby algorithms, especially in distributed execution. Furthermore, we show that for low- diameter graphs the algorithm that applies global ordering scales better than other algorithms and for high diameter graphs the original asynchronous algorithm and thread-level ordering algorithm show better performance.

Light-field cameras capture not only 2D images, but also the angles of the incoming light. These additional light angles bring the benefit of getting a sub-aperture image array from a single light-field image. Inspired by the traditional optical flow with occlusion detection, this paper focuses on the correlation analysis and the occlusion modeling for the sub-aperture array, and unifies them into a light-field flow framework. The main challenges faced are subpixel displacements and occlusion handling among the sub-aperture images. We build a light-field flow for joint depth estimation and occlusion detection, and develop a geometric occlusion model. More specifically, we firstly estimate subpixel-accuracy optical flows from each two sub-aperture images by the phase shift theorem, then a forward-backward consistency checking is adopted to detect the occluded regions. According to the geometric complementary character of occlusion in a light-field image, an occlusion filling strategy is proposed to refine depth estimation in the occluded regions. Experimental results on the synthetic scenes and Lytro Illum camera data both demonstrate the effectiveness and robustness of our method which has excellent performance in handling occlusions.

In distributed computing, parallel overheads such as \emph{synchronization overhead} may hinder performance. We introduce the idea of \emph{Distributed Control} (DC) where global synchronization is reduced to \emph{termination detection} and each worker proceeds ahead optimistically, based on the local knowledge of the global computation. To avoid "wasted'' work, \DC relies on local work prioritization. However, the work order obtained by local prioritization is susceptible to interference from the runtime. We show that employing effective scheduling policies and optimizations in the runtime, in conjunction with eliminating global barriers, improves performance in two graph applications: single-source shortest paths and connected components.

Maintaining a scalable high-performance virtual global address space using distributed memory hardware has proven to be challenging. In this paper we evaluate a new approach for such an active global address space that leverages the capabilities of the network fabric to manage addressing, rather than software at the endpoint hosts. We describe our overall approach, design alternatives, and present initial experimental results that demonstrate the effectiveness and limitations of existing network hardware.

Depth recovery from a light-field camera is an essential and interesting problem. One of its most challenges is to get accurate estimation for the depth discontinuities and occluded regions. We propose a simple and efficient solution with a cascade occlusion culling filter. It is a cascade processing corresponding to the different manifestations of occlusions at ray-level, pixel-level and image-level. (i) At ray-level, any potential occluded ray will be filtered out in depth-cue responses computation, and then reliable multiple-cue cost volumes are constructed. (ii) At pixel-level, occlusions generally result in weak depth discontinuity ramp edges. These discontinuities will be preserved and enhanced by a multiple-cue cost-volume filter with edge preserving property. (iii) At image-level, occlusion is embodied in the uncertain regions. In order to obtain optimal depth estimation of uncertain regions, an iterative depth optimization framework is applied to integrate the aforementioned filtered multiple-cue cost volumes with their confidences. We show that our method has good depth-discontinuity preserving property, and is insensitive to the surface color / texture discontinuities at the same time. Experimental results on Lytro Illum camera data demonstrate the effectiveness and robustness of our method which has excellent performance in handling discontinuities and occlusions.

Measurements for distributed algorithms, such as performance results, are usually reported using averages, similarly to prevailing practice in other areas of computer science. We argue that including standard deviations offers additional information and that the minimal burden of providing standard deviations is outweighed by the benefits. We propose a new way of reporting run time speedup that incorporates standard deviation and demonstrate its usefulness in terms of two distributed graph algorithms.

A vast majority of legacy runtime systems and middleware prevalent in cluster and supercomputing environments are static in nature. Due to the rising scale and complexity of high-performance computing systems, the static nature of systems software would prospectively impede its scalability and resilience. Traditionally, the mobility of servers is further limited since services are statically bound to specific communication endpoints. To address these challenges imminent for exascale-class systems, distributed middleware needs to support dynamic reconfiguration, redundant and replicated state, and adaptation where the number of servers can vary according to the load in the system. We identify the key features necessary from the underlying network infrastructure to support dynamic adaptation and elasticity in distributed system software, and describe the implementation of a high-performance middleware library that implements the proposed interface. We discuss several novel approaches for dynamic resolution using range computations performed by hosts (in software) and by switches (in hardware), and compare the performance on contemporary Ethernet networks. Finally, we validate the benefits offered by our library with two different applications -- a scalable DHCP server and an elastic key-value store.

With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.

Visualization schemas need to be enhanced to support next-generation high-performance computing (HPC) environments. New HPC runtimes perform more actions in a unit of time, but they also perform a wider variety of actions. Existing schemas are too simple to illustrate the variety of information that HPC developers need. However, existing schemas can be extended in simple ways to become more effective for next-generation HPC environments. This paper presents extensions to the common Vampir style plot that use high-definition alpha composition and color weaving. These two techniques incorporate new detail into the traditional plot style, providing useful information for HPC developers.

We introduce a novel plenoptic function that can be directly captured or generated after the fact in plenoptic cameras. Whereas previous approaches represent the plenoptic function over a 4D ray space (as radiance or light field), we introduce the representation of the plenoptic function over a 3D plane space. Our approach uses the Radon plenoptic function instead of the traditional 4D plenoptic function to achieve 3D representation - which promises reduced size, making it suitable for use in mobile devices. Moreover, we show that the original 3D luminous density of the scene can be recovered via the inverse Radon transform. Finally, we demonstrate how various 3D views and differently-focused pictures can be rendered directly from this new representation.

Graphics processing units (GPUs) can effectively accelerate many applications, but their applicability has been largely limited to problems whose solutions can be expressed neatly in terms of linear algebra. Indeed, most GPU programming languages limit the user to simple data structures - typically only multidimensional rectangular arrays of scalar values. Many algorithms are more naturally expressed using higher level language features, such as algebraic data types (ADTs) and first class procedures, yet building these structures in a manner suitable for a GPU remains a challenge. We present a region-based memory management approach that enables rich data structures in Harlan, a language for data parallel computing. Regions enable rich data structures by providing a uniform representation for pointers on both the CPU and GPU and by providing a means of transferring entire data structures between CPU and GPU memory. We demonstrate Harlan's increased expressiveness on several example programs and show that Harlan performs well on more traditional data-parallel problems.

To achieve more complete and more uniformly highlighted salient object regions, this study presents a computational saliency enhancement model that incorporates the properties of multi‐scale and logarithmic response into the local and global contrasts. A distinct feature of the authors model is a novel saliency enhancement operator. This operator can effectively enhance the saliency of object interior regions while simultaneously reducing blur on object boundaries caused by multiple scales. Their model is a general one that can make flexible tradeoffs between precision and recall. Detailed comparisons with 12 state‐of‐the‐art methods show that their method can obtain satisfactory salient object regions that are closer to the human‐labelled results. In addition, their method provides superior results in precision–recall, F ‐measure and mean absolute error.

It is impossible to directly visualize all of the items of a large dataset at once. Often, the number of items exceeds the number of pixels. Since direct representation is not a reliable option, a variety of methods have been developed for dealing with indirect representation. Such methods include clustering and intelligent filtering to reduce the number of items being considered in the first place. However, these techniques impose a high computational and interpretation costs. The alternative is to employ techniques to directly deal with the over-plotting that occurs. that occurs when there are too many items to display without overlapping. Over-plotting techniques include alpha composition, color weaving and selective plotting. Each of these has variants that yield different cognitive or computational optimizations. Unfortunately, most advanced over-plotting techniques are wrapped up in specific libraries. Experimenting with different techniques is cumbersome because they have not been provided with uniform interfaces or in a single runtime. This paper presents Abstract Rendering, a recasting of the rendering process that enables concise expression of many over-plotting techniques. Furthermore, the Abstract Rendering formulation yields efficient execution strategies. Combined, it is practical to explore different over-plotting techniques for large data without requiring significant alteration to existing pipelines.

Light fields are image-based representations that use densely sampled rays as a scene description. In this paper, we explore geometric structures of 3D lines in ray space for improving light field triangulation and stereo matching. The triangulation problem aims to fill in the ray space with continuous and non-overlapping simplices anchored at sampled points (rays). Such a triangulation provides a piecewise-linear interpolant useful for light field super-resolution. We show that the light field space is largely bilinear due to 3D line segments in the scene, and direct triangulation of these bilinear subspaces leads to large errors. We instead present a simple but effective algorithm to first map bilinear subspaces to line constraints and then apply Constrained Delaunay Triangulation (CDT). Based on our analysis, we further develop a novel line-assisted graph-cut (LAGC) algorithm that effectively encodes 3D line constraints into light field stereo matching. Experiments on synthetic and real data show that both our triangulation and LAGC algorithms outperform state-of-the-art solutions in accuracy and visual quality.

Recently, graph computation has emerged as an important class of high-performance computing application whose characteristics differ markedly from those of traditional, compute-bound kernels. Libraries such as BLAS, LAPACK, and others have been successful in codifying best practices in numerical computing. The data-driven nature of graph applications necessitates a more complex application stack incorporating runtime optimization. In this paper, we present a method of phrasing graph algorithms as collections of asynchronous, concurrently executing, concise code fragments which may be invoked both locally and in remote address spaces. A runtime layer performs a number of dynamic optimizations, including message coalescing, message combining, and software routing. We identify a number of common patterns in these algorithms, and explore how this programming model can express those patterns. Algorithmic transformations are discussed which expose asyn- chrony that can be leveraged by the runtime to improve performance and reduce resource utilization. Practical implementations and performance results are provided for a number of representative algorithms.

Recently, graph computation has emerged as an important class of high-performance computing application whose characteristics differ markedly from those of traditional, compute-bound, kernels. Libraries such as BLAS, LAPACK, and others have been successful in codifying best practices in numerical computing. The data-driven nature of graph applications necessitates a more complex application stack incorporating runtime optimization. In this paper, we present a method of phrasing graph algorithms as collections of asynchronous, concurrently executing, concise code fragments which may be invoked both locally and in remote address spaces. A runtime layer performs a number of dynamic optimizations, including message coalescing, message combining, and software routing. Practical implementations and performance results are provided for a number of representative algorithms.

The number of cores in multi- and many-core high-performance processors is steadily increasing. MPI, the de-facto standard for programming high-performance computing systems offers a distributed memory programming model. MPI's semantics force a copy from one process' send buffer to another process' receive buffer. This makes it difficult to achieve the same performance on modern hardware than shared memory programs which are arguably harder to maintain and debug. We propose generalizing MPI's communication model to include ownership passing, which make it possible to fully leverage the shared memory hardware of multi- and many-core CPUs to stream communicated data concurrently with the receiver's computations on it. The benefits and simplicity of message passing are retained by extending MPI with calls to send (pass) ownership of memory regions, instead of their contents, between processes. Ownership passing is achieved with a hybrid MPI implementation that runs MPI processes as threads and is mostly transparent to the user. We propose an API and a static analysis technique to transform legacy MPI codes automatically and transparently to the programmer, demonstrating that this scheme is easy to use in practice. Using the ownership passing technique, we see up to 51% communication speedups over a standard message passing implementation on state-of-the art multicore systems. Our analysis and interface will lay the groundwork for future development of MPI-aware optimizing compilers and multi-core specific optimizations, which will be key for success in current and next-generation computing platforms.

Multi-core shared memory architectures are ubiquitous in both High-Performance Computing (HPC) and commodity systems because they provide an excellent trade-off between performance and programmability. MPI's abstraction of explicit communication across distributed memory is very popular for programming scientific applications. Unfortunately, OS-level process separations force MPI to perform unnecessary copying of messages within shared memory nodes. This paper presents a novel approach that transparently shares memory across MPI processes executing on the same node, allowing them to communicate like threaded applications. While prior work explored thread-based MPI libraries, we demonstrate that this approach is impractical and performs poorly in practice. We instead propose a novel process-based approach that enables shared memory communication and integrates with existing MPI libraries and applications without modifications. Our protocols for shared memory message passing exhibit better performance and reduced cache footprint. Communication speedups of more than 26% are demonstrated for two applications.

A plenoptic camera captures the 4D radiance about a scene. Recent practical solutions mount a microlens array on top of a commodity SLR to directly acquire these rays. However, they suffer from low resolution as hundreds of thousands of views need to be captured in a single shot. In this paper, we develop a simple but effective technique for improving the image resolution of the plenoptic camera by maneuvering the demosaicing process. We first show that the traditional solution by demosaicing each individual microlens image and then blending them for view synthesis is suboptimal. In particular, this demosaicing process often suffers from aliasing artifacts, and it damages high frequency information recorded by each microlens image hence degrades the image quality. We instead propose to de-mosaic the synthesized view at the rendering stage. Specifically, we first transform the radiance to the desired focal plane and then apply frequency domain plenoptic resampling. A full resolution color filtered image is then created by performing a 2D integral projection from the reparam-eterized radiance. Finally, we conduct demosacing to obtain the color result. We show that our solution can achieve visible resolution enhancement on dynamic refocusing and depth-assisted deep focus rendering.

Long-running HPC applications guard against node failures by writing checkpoints to parallel file systems. Writing these checkpoints with petascale class machines has proven difficult and the increased concurrency demands of exascale computing will exacerbate this problem. To meet checkpointing demands and sustain application-perceived throughput at exascale, multi-tiered hierarchical storage architectures involving solid-state burst buffers are being considered. In this paper, we describe the design and implementation of cento, a multi-level, content-addressable checkpoint file system for large-scale HPC systems. cento achieves in-flight checkpoint data reduction across all compute nodes through compression and elimination of duplicate blocks over a series of checkpoints. Through a detailed analysis of checkpoint dumps, we assess the benefits of data reduction for scientific applications that are representative of production workloads. We observe upto 40% data reduction within a limited sample of representative workloads. Finally, experiments on existing systems show a decrease in checkpoint commit latencies by 5 to 20 % reducing the load on the parallel file system.

In this paper, we describe the challenges involved in designing a family of highly-efficient Breadth-First Search (BFS) algorithms and in optimizing these algorithms on the latest two generations of Blue Gene machines, Blue Gene/P and Blue Gene/Q. With our recent winning Graph 500 submissions in November 2010, June 2011, and November 2011, we have achieved unprecedented scalability results in both space and size. On Blue Gene/P, we have been able to parallelize a scale 38 problem with 238 vertices and 242 edges on 131,072 processing cores. Using only four racks of an experimental configuration of Blue Gene/Q, we have achieved a processing rate of 254 billion edges per second on 65,536 processing cores. This paper describes the algorithmic design and the main classes of optimizations that we have used to achieve these results.

We have developed a high-level language, called Kanor, for declaratively specifying communication in parallel programs. Designed as an extension of C++, it serves to coordinate partitioned address space programs written in the bulk synchronous parallel (BSP) style. Kanor's declarative semantics enable the programmers to write correct and maintainable parallel applications. The communication abstraction has been carefully designed to be amenable to compiler optimizations. While partitioned address space programming has several advantages, it needs special compiler optimizations to effectively leverage the shared memory hardware when running on multicore machines. In this paper, we introduce such shared-memory optimizations in the context of Kanor. One major way we achieve these optimizations is by selectively moving some of the variables into a globally shared address space - a process that we term partial globalization. We identify scenarios in which such a transformation is beneficial, and present an algorithm to identify and correctly transform Kanor communication steps into zero-copy communication using hardware shared memory, by introducing minimal synchronization. We then present a runtime strategy that complements the compiler algorithm to eliminate most of the runtime synchronization overheads by using a copy-on-conflict technique. Finally, we show that our solution often performs much better than shared-memory optimized MPI, and ne ver performs significantly worse than MPI even in the presence of dependencies introduced due to buffer sharing. The techniques in this paper demonstrate that it is possible to program in a partitioned address space style, without sacrificing the performance advantages of hardware shared memory. To the best of our knowledge no other automatic compiler techniques have been developed so far that achieve zero-copy communication from a partitioned address space program. We expect out results to be applicable beyond Kanor, to other partitioned address space programming environments, such as MPI.

The scope of scientific computing continues to grow and now includes diverse application areas such as network analysis, combinatorialcomputing, and knowledge discovery, to name just a few. Large problems in these application areas require HPC resources, but they exhibit computation and communication patterns that are irregular, fine-grained, and non-local, making it difficult to apply traditional HPC approaches to achieve scalable solutions. In this paper we present Active Pebbles, a programming and execution model developed explicitly to enable the development of scalable software for these emerging application areas. Our approach relies on five main techniques--scalable addressing, active routing, message coalescing, message reduction, and termination detection--to separate algorithm expression from communication optimization. Using this approach, algorithms can be expressed in their natural forms, with their natural levels of granularity, while optimizations necessary for scalability can be applied automatically to match the characteristics of particular machines. We implement several example kernels using both Active Pebbles and existing programming models, evaluating both programmability and performance. Our experimental results demonstrate that the Active Pebbles model can succinctly and directly express irregular application kernels, while still achieving performance comparable to MPI-based implementations that are significantly more complex.

A variety of programming models exist to support large-scale, distributed memory, parallel computation. These programming models have historically targeted coarse-grained applications with natural locality such as those found in a variety of scientific simulations of the physical world. Fine-grained, irregular, and unstructured applications such as those found in biology, social network analysis, and graph theory are less well supported. We propose Active Pebbles, a programming model which allows these applications to be expressed naturally; an accompanying execution model ensures performance and scalability.

Active messages have proven to be an effective approach for certain communication problems in high performance computing. Many MPI implementations, as well as runtimes for Partitioned Global Address Space languages, use active messages in their low-level transport layers. However, most active message frameworks have low-level programming interfaces that require significant programming effort to use directly in applications and that also prevent optimization opportunities. In this paper we present AM++, a new user-level library for active messages based on generic programming techniques. Our library allows message handlers to be run in an explicit loop that can be optimized and vectorized by the compiler and that can also be executed in parallel on multicore architectures. Runtime optimizations, such as message combining and filtering, are also provided by the library, removing the need to implement that functionality at the application level. Evaluation of AM++ with distributed-memory graph algorithms shows the usability benefits provided by these library features, as well as their performance advantages.

Betweenness centrality is a measure based on shortest paths that attempts to quantify the relative importance of nodes in a network. As computation of betweenness centrality becomes increasingly important in areas such as social network analysis, networks of interest are becoming too large to fit in the memory of a single processing unit, making parallel execution a necessity. Parallelization over the vertex set of the standard algorithm, with a final reduction of the centrality for each vertex, is straightforward but requires Ω(|V|2) storage. In this paper we present a new parallelizable algorithm with low spatial complexity that is based on the best known sequential algorithm. Our algorithm requires O(|V| + |E|) storage and enables efficient parallel execution. Our algorithm is especially well suited to distributed memory processing because it can be implemented using coarse-grained parallelism. The presented time bounds for parallel execution of our algorithm on CRCW PRAM and on distributed memory systems both show good asymptotic performance. Experimental results with a distributed memory computer show the practical applicability of our algorithm.

We introduce LogGOPSim---a fast simulation framework for parallel algorithms at large-scale. LogGOPSim utilizes a slightly extended version of the well-known LogGPS model in combination with full MPI message matching semantics and detailed simulation of collective operations. In addition, it enables simulation in the traditional LogP, LogGP, and LogGPS models. Its simple and fast single-queue design computes more than 1 million events per second on a single processor and enables large-scale simulations of more than 8 million processes. LogGOPSim also supports the simulation of full MPI applications by reading and simulating MPI profiling traces. We analyze the accuracy and the performance of the simulation and propose a simple extrapolation scheme for parallel applications. Our scheme extrapolates collective operations with high accuracy by rebuilding the communication pattern. Point-to-point operation patterns can be copied in the extrapolation and thus retain the main characteristics of scalable parallel applications.

The data-state and data-flow models of information visualization are known to be expressively equivalent. Each model is most effective for different combinations of analysis processes and data characteristics. Visualization frameworks tend to either (1) work within a single model or (2) permit either model in separate sub-frameworks. In either case, converting between the two models falls entirely to the programmer. The theoretical basis for automatic translation between the two models was established by Chi. However, that process is insufficiently specified to be directly implemented. This paper characterizes the practical advantages of the data-state model. This is used to identify when such a transformation is beneficial. It then expands on Chi's theoretical framework to provide the tools for translating visualization program fragments from the data-flow to the data-state model. A partial implementation of the expanded theory is described for the Stencil visualization environment.

Many large-scale parallel programs follow a bulk synchronous parallel (BSP) structure with distinct computation and communication phases. Although the communication phase in such programs may involve all (or large numbers) of the participating processes, the actual communication operations are usually sparse in nature. As a result, communication phases are typically expressed explicitly using point-to-point communication operations or collective operations. We define the dynamic sparse data-exchange (DSDE) problem and derive bounds in the well known LogGP model. While current approaches work well with static applications, they run into limitations as modern applications grow in scale, and as the problems that are being solved become increasingly irregular and dynamic.

This paper presents an in-depth analysis of the impact of system noise on large-scale parallel application performance in realistic settings. Our analytical model shows that not only collective operations but also point-to-point communications influence the application's sensitivity to noise. We present a simulation toolchain that injects noise delays from traces gathered on common large-scale architectures into a LogGPS simulation and allows new insights into the scaling of applications in noisy environments. We investigate collective operations with up to 1 million processes and three applications (Sweep3D, AMG, and POP) with up to 32,000 processes.We show that the scale at which noise becomes a bottleneck is system-specific and depends on the structure of the noise. Simulations with different network speeds show that a 10x faster network does not improve application scalability. We quantify noise and conclude that our tools can be utilized to tune the noise signatures of a specific system.

Computational photography is based on capturing and processing discrete representations of all the light rays in the 3D space of a scene. Compared to conventional photography, which captures 2D images, computational photography captures the entire 4D 'lightfield', (the full 4D radiance). To multiplex the 4D radiance onto conventional 2D sensors, light-field photography demands sophisticated optics and imaging technology. Two-dimensional image rendering is based on creating 2D projections of the 4D radiance.

Abstract The focused plenoptic camera differs from the traditional plenoptic camera in that its microlenses are focused on the photographed object rather than at infinity. The spatio‐angular tradeoffs available with this approach enable rendering of final images that have significantly higher resolution than those from traditional plenoptic cameras. Unfortunately, this approach can result in visible artifacts when basic rendering is used. In this paper, we present two new methods that work together to minimize these artifacts. The first method is based on careful design of the optical system. The second method is computational and based on a new lightfield rendering algorithm that extracts the depth information of a scene directly from the lightfield and then uses that depth information in the final rendering. Experimental results demonstrate the effectiveness of these approaches.

C++ template metaprogramming has been used with great success to build software applications and libraries. In practice, however, template metaprogramming suffers usability, reliability, and capability shortcomings, and it is not well understood in theory. Template metaprogramming has these problems because it relies on emergent properties of disparate language features that were tailored to other purposes. As a step toward solid and sound language support for metaprogramming, this paper establishes firm semantic foundations for select capabilities of template metaprogramming.

The optimizations in modern compilers are constructed for a predetermined set of primitive types. As a result, programmers are unable to exploit optimizations for user-defined types where these optimizations would be correct and beneficial. Moreover, because the set of optimizations is also fixed, programmers are unable to incorporate new optimizations into the compiler. To address these limitations, we apply the reuse methodologies from generic programming to compiler analyses and optimizations. To enable compilers to apply optimizations to classes of types rather than particular types, we define optimizations in terms of generic interface descriptions (similar to C++ concepts or Haskell type classes). By extending these interface descriptions to include associated program analysis and transformation fragments, we enable compilers to incorporate user-defined transformations and analyses. Since these transformations are explicitly associated with interface descriptions, they can be applied in generic fashion by the compiler. We demonstrate that classical compiler optimizations, when generalized using this framework, can apply to a broad range of types, both built-in and user-defined. Finally, we present an initial implementation, the principles of which are generalizable to other compilers.

The dataflow model allows natural expression of parallelism in an application. Applications expressed in the dataflow model can be executed either using the data-driven or the demand-driven schemes. Although both these schemes have their utility in different scenarios, the realization of the demand-driven scheme is not adequately supported in the existing solutions for task parallelism. In this paper, we examine some of the requirements placed by the demand-driven execution scheme on task parallelism. We present PFunc, a new library-based solution for task parallelism that fully supports the demand-driven execution scheme. We compare the runtimes and peak memory consumption of an unsymmetric sparse LU factorization emulation parallelized using both the data- and demand-driven execution schemes. This comparison shows that the demand-driven model provides benefits that necessitate its full support in task parallelism.

Long running High Performance Computing (HPC) applications at scale must be able to tolerate inevitable faults if they are to harness current and future HPC systems. Message Passing Interface (MPI) level transparent checkpoint/restart fault tolerance is an appealing option to HPC application developers that do not wish to restructure their code. Historically, MPI implementations that provided this option have struggled to provide a full range of interconnect support, especially shared memory support. This paper presents a new approach for implementing checkpoint/restart coordination algorithms that allows the MPI implementation of checkpoint/restart to be interconnect agnostic. This approach allows an application to be checkpointed on one set of interconnects (e.g., InfiniBand and shared memory) and be restarted with a different set of interconnects (e.g., Myrinet and shared memory or Ethernet). By separating the network interconnect details from the checkpoint/restart coordination algorithm we allow the HPC application to respond to changes in the cluster environment such as interconnect unavailability due to switch failure, re-load balance on an existing machine, or migrate to a different machine with a different set of interconnects. We present results characterizing the performance impact of this approach on HPC applications.

Considerable work has been done on providing fault tolerance capabilities for different software components on large-scale high-end computing systems. Thus far, however, these fault-tolerant components have worked insularly and independently and information about faults is rarely shared. Such lack of system-wide fault tolerance is emerging as one of the biggest problems on leadership-class systems. In this paper, we propose a coordinated infrastructure, named CIFTS, that enables system software components to share fault information with each other and adapt to faults in a holistic manner. Central to the CIFTS infrastructure is a Fault Tolerance Backplane (FTB) that enables fault notification and awareness throughout the software stack, including fault-aware libraries, middleware, and applications. We present details of the CIFTS infrastructure and the interface specification that has allowed various software programs, including MPICH2, MVAPICH, Open MPI, and PVFS, to plug into the CIFTS infrastructure. Further, through a detailed evaluation we demonstrate the nonintrusive low-overhead capability of CIFTS that lets applications run with minimal performance degradation.

The implementation and optimization of collective communication operations is an important field of active research. Such operations directly influence application performance and need to map the communication requirements in an optimal way to steadily changing network architectures. In this work, we define an abstract domain-specific language to express arbitrary group communication operations. We show the universality of this language and how all existing collective operations can be implemented with it. By design, it readily lends itself to blocking and nonblocking execution, as well as to off-loaded execution of complex group communication operations. We also define several offline and online optimizations (compiler transformations and scheduling decisions, respectively) to improve the overall performance of the operation. Performance results show that the overhead to express current collective operations is negligible in comparison to the potential gains in a highly optimized implementation.

Microbenchmarks have long been used to assess the performance characteristics of high-performance networks. It is generally assumed that microbenchmark results indicate the parallel performance of real applications. This paper reports the results of performance studies using real applications in a strictly controlled environment with different networks. In particular, we compare the performance of Myrinet and InfiniBand, and analyze them with respect to microbenchmark performance, real application performance and power consumption.

The impact of operating system noise on the performance of large-scale applications is a growing concern and ameliorating the effects of OS noise is a subject of active research. A related problem is that of network noise, which arises from shared use of an interconnection network by parallel processes. To characterize the impact of network noise on parallel applications we conducted a series of simulations and experiments using a newly-developed benchmark. Experiment results show a decrease in the communication performance of a parallel reduction operation by a factor of two on 246 nodes. In addition, simulations show that influence of network noise grows with the system size. Although network noise is not as well-studied as OS noise, our results clearly show that it is an important factor that must be considered when running large-scale applications.

Suitable reference marks are an important part of creating an understandable visualization. The reference marks create the frame in which the data is understood, thereby preserving the context of the data and allowing the transition from data to information to be made. However, reference marks (including legends, axial and point labels) are given insufficient attention in many visualization frameworks. When explicitly present, they often require completely separate specification from the visualization for which they are a reference. This paper presents a framework independent method for deriving reference marks from the data analysis pathway. We also describe how this approach has been implemented in the Stencil library, and how it may be implemented in other libraries.

The call-by-need lambda calculus provides an equational framework for reasoning syntactically about lazy evaluation. This paper examines its operational characteristics.

HPC today faces new challenges due to paradigm shifts in both hardware and software. The ubiquity of multi-cores, many-cores, and GPGPUs is forcing traditional serial as well as distributed-memory parallel applications to be parallelized for these architectures. Emerging applications in areas such as informatics are placing unique requirements on parallel programming tools that have not yet been addressed. Although, of all the available parallel programming models, task parallelism appears to be the most promising in meeting these new challenges, current solutions for task parallelism are inadequate. In this paper, we introduce PFunc, a new library for task parallelism that extends the feature set of current solutions for task parallelism with custom task scheduling, task priorities, task affinities, multiple completion notifications and task groups. These features enable PFunc to naturally and efficiently parallelize a wide variety of modern HPC applications and to support the SPMD model of parallel programming. We present three case studies: demand-driven DAG execution, frequent pattern mining and iterative sparse solvers to demonstrate the utility of PFunc's new features.

Collective operations and non-blocking point-to-point operations are two important parts of PM I that each provide important performance and programmability benefits. Although non-blocking collective operations are an obvious extension to MPI, there have been no comprehensive studies of this functionality. This dissertation will study non- blocking collective operations, integrating theory, practice, and application. We use a well-understood network model to found our theoretical analyses and we realize our communication operations as a portable library layered on MPI. A real-world quantum-mechanical application is used as a deployment and evaluation vehicle for our approach.

Message progression schemes that enable communication and computation to be overlapped have the potential to improve the performance of parallel applications. With currently available high-performance networks there are several options for making progress: manual progression, use of a progress thread, and communication offload. In this paper we analyze threaded progression approaches, comparing the effects of using shared or dedicated CPU cores for progression. To perform these comparisons, we propose time-based and work-based benchmark schemes. As expected, threaded progression performs well when a spare core is available to be dedicated to communication progression, but a number of operating system effects prevent the same benefits from being obtained when communication progress must share a core with computation. We show that some limited performance improvement can be obtained in the shared-core case by real-time scheduling of the progress thread.

Multistage interconnection networks based on central switches are ubiquitous in high-performance computing. Applications and communication libraries typically make use of such networks without consideration of the actual internal characteristics of the switch. However, application performance of these networks, particularly with respect to bisection bandwidth, does depend on communication paths through the switch. In this paper we discuss the limitations of the hardware definition of bisection bandwidth (capacity-based) and introduce a new metric: effective bisection bandwidth. We assess the effective bisection bandwidth of several large-scale production clusters by simulating artificial communication patterns on them. Networks with full bisection bandwidth typically provided effective bisection bandwidth in the range of 55-60%. Simulations with application-based patterns showed that the difference between effective and rated bisection bandwidth could impact overall application performance by up to 12%.

Concepts are a recently proposed extension to C++ for the direct linguistic support of generic programming. As the interface description mechanism for large-scale generic libraries, concepts do not exist in isolation, but rather in semantic frameworks (or concept lattices). Concepts provide powerful type-checking capabilities for generic programming and the semantics associated with them present new and interesting capabilities for library-compiler interactions. This paper presents some of these emergent capabilities in the context of a library of algebraic concepts. Based on this library, which possesses rich, well-structured and mathematically-based semantics, we demonstrate how the concepts therein can enable a sophisticated oncept-aware design for a broad range of scientific generic libraries. In particular, we show that concepts can enable the description and application of property-based, library-defined, optimizations. Whereas compilers without concepts are limited to optimization of built-in types, library-defined optimizations based on concepts not only allow for optimizations of user-defined types unknown to the compiler, they are even applicable to types unknown to the library developer.

Non-blocking collective operations have recently been shown to be a promising complementary approach for overlapping communication and computation in parallel applications. However, in order to maximize the performance and usability of these operations it is important that they progress concurrently with the application without introducing CPU overhead and without requiring explicit user intervention. While studying non- blocking collective operations in the context of our portable library (libNBC), we found that most MPI implementations do not sufficiently support overlap over the InfiniBand network. To address this issue, we developed a low-level communication layer for libNBC based on the Open Fabrics InfiniBand verbs API. With this layer we are able to achieve high degrees of overlap without the need to explicitly progress the communication operations. We show that the communication overhead of parallel application kernels can be reduced up to 92% while not requiring user intervention to make progress.

Accurate, reproducible and comparable measurement of collective operations is a complicated task. Although different measurement schemes are implemented in well- known benchmarks, many of these schemes introduce different systematic errors in their measurements. We characterize these errors and select a window-based approach as the most accurate method. However, this approach complicates measurements significantly and introduces a clock synchronization as a new source of systematic errors. We analyze approaches to avoid or correct those errors and develop a scalable synchronization scheme to conduct benchmarks on massively parallel systems. Our results are compared to the window-based scheme implemented in the SKaMPI benchmarks and show a reduction of the synchronization overhead by a factor of 16 on 128 processes.

Existing Information Visualization models provide insufficient support to visualization programmers in creating applications. They either broad and taxonomy based, or narrowly focused on isolated aspects of the visualization problem. Taxonomy based tools are good for categorizing what has been or needs to be done, but provide little help in accomplishing those goals. Narrowly focused models allow particular aspects of the visualization problem to be efficiently solved, but leave heavy burdens for integrating many such narrow tools together to solve the over arching visualization problem. This insufficiency of visualization models is most evident where interaction is concerned: It is often left as an afterthought. In this paper, we describe the Stencil visualization model, an intermediate model that covers many visualization specific issues. We argue that the Stencil model can guide visualization program construction through several stages of common application pipelines; thereby improving the resulting visualization products and reducing significant barriers to visualization adoption.

As high-performance computing enters the mainstream, parallel programming mechanisms (including the Message Passing Interface, or MPI) must be supported in new environments such as C# and the Common Language Infrastructure (CLI). Making effective use of MPI with the CLI requires an interface that reflects the high-level object-oriented nature of C# and that also supports its programming idioms. However, for performance reasons, this high-level functionality must ultimately be mapped to low-level native MPI libraries. In addition to abstraction penalty concerns, avoiding unwanted overhead in this mapping process is significantly complicated by the safety and portability features of the CLI virtual machine, such as garbage collection and just-in-time compilation. In this paper, we describe our approach to using features of C# and the CLI---such as reflection, unsafe code regions, and run-time code generation---to realize an elegant, yet highly efficient, C# interface to MPI. Experimental results demonstrate that there is no appreciable overhead introduced by our approach when compared to the native MS-MPI library.

Although overlapping communication with computation is an important mechanism for achieving high performance in parallel programs, developing applications that actually achieve good overlap can be difficult. Existing approaches are typically based on manual or compiler-based transformations. This paper presents a pattern and library-based approach to optimizing collective communication in parallel high-performance applications, based on using non-blocking collective operations to enable overlapping of communication and computation. Common communication and computation patterns in iterative SPMD computations are used to motivate the transformations we present. Our approach provides the programmer with the capability to separately optimize communication and computation in an application, while automating the interaction between computation and communication to achieve maximum overlap. Performance results with a model application show more than a 90% decrease in communication overhead, resulting in 21% overall performance improvements.

To be able to fully exploit ever larger computing platforms, modern HPC applications and system software must be able to tolerate inevitable faults. Historically, MPI implementations that incorporated fault tolerance capabilities have been limited by lack of modularity, scalability and usability. This paper presents the design and implementation of an infrastructure to support checkpoint/restart fault tolerance in the Open MPI project. We identify the general capabilities required for distributed checkpoint/restart and realize these capabilities as extensible frameworks within Open MPI's modular component architecture. Our design features an abstract interface for providing and accessing fault tolerance services without sacrificing performance, robustness, or flexibility. Although our implementation includes support for some initial checkpoint/restart mechanisms, the framework is meant to be extensible and to encourage experimentation of alternative techniques within a production quality MPI implementation.

Collective operations and non-blocking point-to-point operations have always been part of MPI. Although non-blocking collective operations are an obvious extension to MPI, there have been no comprehensive studies of this functionality. In this paper we present LibNBC, a portable high-performance library for implementing non-blocking collective MPI communication operations. LibNBC provides non-blocking versions of all MPI collective operations, is layered on top of MPI-1, and is portable to nearly all parallel architectures. To measure the performance characteristics of our implementation, we also present a microbenchmark for measuring both latency and overlap of computation and communication. Experimental results demonstrate that the blocking performance of the collective operations in our library is comparable to that of collective operations in other highperformance MPI implementations. Our library introduces a very low overhead between the application and the underlying MPI and thus, in conjunction with the potential to overlap communication with computation, offers the potential for optimizing real-world applications.

Abstract Many modern programming languages support basic generics, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support, and in doing so have enabled a broader, more powerful form of generic programming. This paper reports on a comprehensive comparison of facilities for generic programming in eight programming languages: C++, Standard ML, Objective Caml, Haskell, Eiffel, Java, C# (with its proposed generics extension), and Cecil. By implementing a substantial example in each of these languages, we illustrate how the basic roles of generic programming can be represented in each language. We also identify eight language properties that support this broader view of generic programming: support for multi-type concepts, multiple constraints on type parameters, convenient associated type access, constraints on associated types, retroactive modeling, type aliases, separate compilation of algorithms and data structures, and implicit argument type deduction for generic algorithms. We find that these features are necessary to avoid awkward designs, poor maintainability, and painfully verbose code. As languages increasingly support generics, it is important that language designers understand the features necessary to enable the effective use of generics and that their absence can cause difficulties for programmers.

The growth in the number of generally available, distributed, heterogeneous computing systems places increasing importance on the development of user-friendly tools that enable application developers to efficiently use these resources. Open MPI provides support for several aspects of heterogeneity within a single, open-source MPI implementation. Through careful abstractions, heterogeneous support maintains efficient use of uniform computational platforms. We describe Open MPI's architecture for heterogeneous network and processor support. A key design features of this implementation is the transparency to the application developer while maintaining very high levels of performance. This is demonstrated with the results of several numerical experiments

Sparse matrix computations are important for many scientific computations, with matrix-vector multiplication being a fundamental operation for modern iterative algorithms. For large sparse matrices, the primary performance limitation on matrix-vector product is memory bandwidth, rather than algorithm performance. In fact, the wide disparity between memory bandwidth and CPU performance suggests that one could trade cycles for bandwidth and still improve the time to compute a matrix-vector product. Accordingly, this paper presents an approach to improving the performance of matrix-vector product based on lossless compression of the index information commonly stored in sparse matrix representations. Two compressed formats, and their multiplication algorithms, are given, along with experimental results demonstrating their effectiveness. For an assortment of large sparse matrices, compression ratios and corresponding speedups of up to 30% are achieved. The efficiency of the compression algorithm allows its cost to be easily amortized across repeated matrix-vector products.

Many interesting problems in graph theory can be reduced to solving an eigenproblem of the adjacency matrix or Laplacian of a graph. Given the availability of high-quality linear algebra and graph libraries, one might expect that one could merely use a graph data structure within a eigensolver. However, conventional libraries are rigidly constructed, requiring conversion to library-specific data structures or using heavyweight abstraction methods that prevent efficient composition. The generic programming methodology addresses the problems of reusability and composability by careful factorization of a domain into efficient library abstractions. We describe the composition process that makes the data structures from a library supporting one domain usable with the algorithms of another library for a disjoint domain without conversion or heavyweight abstractions. To illustrate the process, we compose two separately-developed libraries, one for solving eigenproblems sequentially and the other for solving graph problems in parallel, effecting an efficient, scalable parallel graph eigensolver.

Generic programming has emerged as an important technique for the development of highly reusable and efficient software libraries. In C++, generic programming is enabled by the flexibility of templates, the C++ type parametrization mechanism. However, the power of templates comes with a price: generic (template) libraries can be more difficult to use and develop than non-template libraries and their misuse results in notoriously confusing error messages. As currently defined in C++98, templates are unconstrained, and type-checking of templates is performed late in the compilation process, i.e., after the use of a template has been combined with its definition. To improve the support for generic programming in C++, we introduce concepts to express the syntactic and semantic behavior of types and to constrain the type parameters in a C++ template. Using concepts, type-checking of template definitions is separated from their uses, thereby making templates easier to use and easier to compile. These improvements are achieved without limiting the flexibility of templates or decreasing their performance - in fact their expressive power is increased. This paper describes the language extensions supporting concepts, their use in the expression of the C++ Standard Template Library, and their implementation in the ConceptGCC compiler. Concepts are candidates for inclusion in the upcoming revision of the ISO C++ standard, C++0x.

Generic programming has recently emerged as a paradigm for developing highly reusable software libraries, most notably in C++. We have designed and implemented a constrained generics extension for C++ to support modular type checking of generic algorithms and to address other issues associated with unconstrained generics. To be as broadly applicable as possible, generic algorithms are defined with minimal requirements on their inputs. At the same time, to achieve a high degree of efficiency, generic algorithms may have multiple implementations that exploit features of specific classes of inputs. This process of algorithm specialization relies on non-local type information and conflicts directly with the local nature of modular type checking. In this paper, we review the design and implementation of our extensions for generic programming in C++, describe the issues of algorithm specialization and modular type checking in detail, and discuss the important design tradeoffs in trying to accomplish both.We present the particular design that we chose for our implementation, with the goal of hitting the sweet spot in this interesting design space.

Many applications in comparative genomics lend themselves to implementations that take advantage of common high-performance features in modern microprocessors. However, the common suggestion that a data-parallel, multithreaded, or high-throughput implementation is possible often ignores the complexity of actually creating such software. In this paper, we present two parallel algorithms for a classic comparative genomics algorithm, the dot plot. First, we describe a data-parallel algorithm that achieves speedups of up to 14.4x over the sequential version for large genomic comparisons. Then, we use the new algorithm as the base for a coarse-grained parallel version, suitable for multiprocessor and cluster environments, that scales linearly with the number of processors. These speedups introduce the opportunity to perform full pairwise comparisons on entire genomes on a much larger scale than previously possible. We also present the experimental, model-driven approach used to develop the algorithm that allowed us to carefully study and evaluate implementation options and to fully understand the parameters affecting its performance

This paper describes the process used to extend the Boost Graph Library (BGL) for parallel operation with distributed memory. The BGL consists of a rich set of generic graph algorithms and supporting data structures, but it was not originally designed with parallelism in mind. In this paper, we revisit the abstractions comprising the BGL in the context of distributed-memory parallelism, lifting away the implicit requirements of sequential execution and a single shared address space. We illustrate our approach by describing the process as applied to one of the core algorithms in the BGL, breadth-first search. The result is a generic algorithm that is unchanged from the sequential algorithm, requiring only the introduction of external (distributed) data structures for parallel execution. More importantly, the generic implementation retains its interface and semantics, such that other distributed algorithms can be built upon it, just as algorithms are layered in the sequential case. By characterizing these extensions as well as the extension process, we develop general principles and patterns for using (and reusing) generic, object-oriented parallel software libraries. We demonstrate that the resulting algorithm implementations are both efficient and scalable with performance results for several algorithms.

Support for object-oriented programming has become an integral part of mainstream languages, and more recently generic programming has gained widespread acceptance as well. A natural question is how these two paradigms, and their underlying language mechanisms, should interact. One particular design option, that of using subtyping to constrain the type parameters of generic functions, has been chosen in the generics of Java and those planned for a future revision of C#.Certain shortcomings have previously been identified in using subtyping for constraining parametric polymorphism in the context of generic programming.To address these, we propose extending object-oriented interfaces and subtyping to include associated types and constraint propagation.Associated types are type members of interfaces and classes. Constraint propagation allows certain constraints on type parameters to be inferred from other constraints on those parameters and their use in base class type expressions.The paper demonstrates these extensions in the context of C# (with generics), describes a translation of the extended features to C#, and presents a formalism proving their safety. The formalism is applicable to other mainstream object-oriented languages supporting F-bounded polymorphism, such as Java.

Concepts are an essential language feature for generic programming in the large. Concepts allow for succinct expression of constraints on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. In this paper we present the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common with the type classes of Haskell, though our primary influence is from best practices in the C++ community, where concepts are used to document type requirements for templates in generic libraries. Concepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are similar to nested types and type sharing in ML.

Abstract We present case studies that apply generic programming to the development of high‐performance parallel code for solving two archetypal partial differential equations (PDEs). We examine the overall structure of the example scientific codes and consider their generic implementation. With a generic approach it is a straightforward matter to reuse software components from different sources; implementations with components from the Iterative Template Library (ITL), the Matrix Template Library (MTL), Blitz++, A++/P++, and Fortran BLAS are presented. Our newly developed Generic Message Passing library is used for communication. We compare the generic implementations with equivalent implementations developed with alternative libraries and languages and discuss performance as well as software engineering issues. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract We describe two different libraries for using the Message Passing Interface (MPI) with the C# programming language and the Common Language Infrastructure (CLI). The first library provides C# bindings that closely match the original MPI library specification. The second library presents a fully object‐oriented interface to MPI and exploits modern language features of C#. The interfaces described here use the P/Invoke feature of the CLI to dispatch to a native implementation of MPI, such as LAM/MPI or MPICH. Performance results using the Shared Source CLI demonstrate only a small performance overhead. Copyright © 2005 John Wiley & Sons, Ltd.

In C++, multi-dimensional arrays are often used but the language provides limited native support for them. The language, in its Standard Library, supplies sophisticated interfaces for manipulating sequential data, but relies on its bare-bones C heritage for arrays. The MultiArray library, a part of the Boost library collection, enhances a C++ programmer's tool set with versatile multi-dimensional array abstractions. It includes a general array class template and native array adaptors that support idiomatic array operations and interoperate with C++ Standard Library containers and algorithms. The arrays share a common interface, expressed as a generic programming concept, in terms of which generic array algorithms can be implemented. We present the library design, introduce a generic interface for array programming, demonstrate how the arrays integrate with the C++ Standard Library, and discuss the essential aspects of their implementation. Copyright © 2004 John Wiley & Sons, Ltd.

Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and their extensions have proven valuable in practice. This paper reports on a comprehensive comparison of generics in six programming languages: C++, Standard ML, Haskell, Eiffel, Java (with its proposed generics extension), and Generic C. By implementing a substantial example in each of these languages, we identify eight language features that support this broader view of generic programming. We find these features are necessary to avoid awkward designs, poor maintainability, unnecessary run-time checks, and painfully verbose code. As languages increasingly support generics, it is important that language designers understand the features necessary to provide powerful generics and that their absence causes serious difficulties for programmers.

Abstract The Lambda Library (LL) adds a form of lambda functions to C++, which are common in functional programming languages. The LL is implemented as a template library using standard C++; thus no language extensions or preprocessing is required. The LL consists of a rich set of tools for defining unnamed functions. In particular these unnamed functions work seamlessly with the generic algorithms in the C++ Standard Library. The LL offers significant improvements, in terms of generality and ease of use, compared to the current tools in the C++ Standard Library. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract The major contribution of this paper is the application of modern analysis techniques to the important Message Passing Interface standard, work done in order to obtain information useful in designing both application programmer interfaces for object‐oriented languages, and message passing systems. Recognition of ‘Design Patterns’ within MPI is an important discernment of this work. A further contribution is a comparative discussion of the design and evolution of three actual object‐oriented designs for the Message Passing Interface ( MPI‐1SF ) application programmer interface (API), two of which have influenced the standardization of C++ explicit parallel programming with MPI‐2, and which strongly indicate the value of a priori object‐oriented design and analysis of such APIs. Knowledge of design patterns is assumed herein. Discussion provided here includes systems developed at Mississippi State University (MPI++), the University of Notre Dame (OOMPI), and the merger of these systems that results in a standard binding within the MPI‐2 standard. Commentary concerning additional opportunities for further object‐oriented analysis and design of message passing systems and APIs, such as MPI‐2 and MPI/RT, are mentioned in conclusion. Connection of modern software design and engineering principles to high performance computing programming approaches is a new and important further contribution of this work. Copyright © 2001 John Wiley & Sons, Ltd.

In this paper we present the Generic Graph Component Library (GGCL), a generic programming framework for graph data structures and graph algorithms. Following the theme of the Standard Template Library (STL), the graph algorithms in GGCL do not depend on the particular data structures upon which they operate, meaning a single algorithm can operate on arbitrary concrete representations of graphs. To attain this type of flexibility for graph data structures, which are more complicated than the containers in STL, we introduce several concepts to form the generic interface between the algorithms and the data structures: Vertex, Edge, Visitor, andDecorator. We describe the principal abstractions comprising the GGCL, the algorithms and data structures that it provides, and provide examples that demonstrate the use of GGCL to implement some common graph algorithms. Performance results are presented which demonstrate that the use of novel lightweight implementation techniques and static polymorphism in GGCL results in code which is significantly more efficient than similar libraries written using the objectoriented paradigm. Submitted as a Research Paper to OOPSLA99. Subject Areas: frameworks, design patterns

Simulating transients in semiconductor devices involves numerically solving the time-dependent drift-diffusion equations, usually in two or three space dimensions. Because of the computation cost of these simulations, methods that perform careful domain decomposition so as to exploit parallel processing have received much recent attention. In this paper, we describe using accelerated waveform relaxation (WR) to perform parallel device transient simulation using both clusters of workstations and the IBM SP-2. The accelerated WR algorithms are compared to pointwise direct and iterative methods, and it is shown that the accelerated WR method is competitive on a single processor. In addition, it is shown that with a domain decomposition chosen for rapid iterative method convergence rather than parallel efficiency, the pointwise methods parallelize poorly but the WR method achieves near linear speedup (with respect to the number of processors) on the IBM SP-2.

For signals containing discontinuities, the usual assumptions of Gauss-Markov distributed signal sources do not hold. To preserve edges, non-Gaussian prior models have been developed for use in Bayesian restoration. These models are generally dependent upon two parameters, one controlling the size of reconstructed discontinuities, and the other controlling data smoothing. The authors propose a maximum likelihood technique for automatically estimating these parameters, resulting in the optimization of an expression dependent upon the prior model partition function. An exact expression is derived for the 1D signal model partition function, while an approximation is proposed for the 2D image model partition function. Parameters estimated from degraded signals result in high quality restorations.>

In this paper we compare accelerated waveform relaxation algorithms to pointwise methods for the transient simulation of semiconductor devices on parallel machines. Experimental results are presented for simulations on small clusters of workstations and on an Intel iPSC/860. The results show that accelerated waveform methods are competitive with standard pointwise methods on serial machines, but are significantly faster on loosely-coupled MIMD machines.

This paper presents the algorithms for CMVSIM, a program for performing the transient simulation of grid based analog signal processors on a massively parallel computer. A grid-based equation formulation approach and a block-diagonal preconditioned CGS algorithm are described, and it is shown how they are used to efficiently perform transient simulation using the massively parallel Connection Machine. Experimental results using CMVSIM to simulate realistic image processing circuits are given to demonstrate that the algorithms presented are effective for a general class of grid-based signal processors. In particular, the results presented demonstrate that CMVSIM: running on a full-size Connection Machine can be as much as 650 times faster than what is, to the authors' knowledge, the fastest serial transient simulation algorithm running on a SUN-4/490 workstation.>

A conjugate-direction based acceleration to the waveform relaxation (WR) algorithm is derived. Experimental results demonstrated the effectiveness of the acceleration when solving the large, sparsely connected algebraic and differential system generated by standard spatial discretization of the 2D time-dependent semiconductor device equations. The waveform conjugate-direction methods were up to 15 times faster than ordinary WR.>

Specialized algorithms for circuit-level simulation of grid-based analog signal processing arrays on a massively parallel processor are described and implementation results presented. The trapezoidal rule is used to discretize the differential equations that describe the analog array behavior, Newton's method is used to solve the nonlinear equations generated at each time-step, and a block conjugate-gradient squared algorithm is used to solve the linear equations generated by Newton's method. Excellent parallel performance of the algorithm is achieved through the use of a novel, but very natural, mapping of the circuit data onto the massively parallel architecture. The mapping takes advantage of the underlying computer architecture and the structure of the analog array problem. Experimental results demonstrate that a full-size Connection Machine can provide a 1400 times speedup over a SUN-4/280 workstation.>

A variable-band relaxation algorithm for solving large linear systems is developed as an alternative to Gauss-Jacobi relaxation. This algorithm seeks to improve the reliability of Gauss-Jacobi relaxation by extracting a variable-sized band from the matrix and solving that band directly. This leads to a relaxation algorithm with provably better convergence properties. The algorithm can be used effectively on a massively parallel computer because band matrices can be solved in log(n) time on n/2 processors. Test results are presented which compare the convergence properties of variable-band and Gauss-Jacobi relaxation.>