Virginia Tech - Wake Forest University School of Biomedical Engineering & Sciences
Computer Science Technical Reports @Virginia TechNot a member yet
997 research outputs found
Sort by
Multi-Dimensional Characterization of Temporal Data Mining on Graphics Processors
Get PDFThrough the algorthmic design patterns of data parallelism and task parallelism, the graphics processing unit (GPU) offers the potential to vastly accelerate discovery and innovation across a multitude of disciplines. For example, the exponential growth in data volume now presents an obstacle for high-throughput data mining in ï¬elds such as neuroinformatics and bioinformatics. As such, we present a characterization of a MapReduce-based data-mining application on a general-purpose GPU (GPGPU). Using neuroscience as the application vehicle, the results of our multi-dimensional performance evaluation show that a “one-size-ï¬ts-all†approach maps poorly across different GPGPU cards. Rather, a high-performance implementation on the GPGPU should factor in the 1) problem size, 2) type of GPU, 3) type of algorithm, and 4) data-access method when determining the type and level of parallelism. To guide the GPGPU programmer towards optimal performance within such a broad design space, we provide eight general performance characterizations of our data-mining application
An Application-Oriented Approach for Accelerating Data-Parallel Computation with Graphics Processing Unit
Get PDFThis paper presents a novel parallelization and quantitative characterization of various optimization strategies for data-parallel computation on a graphics processing unit (GPU) using NVIDIA's new GPU programming framework, Compute Unified Device Architecture (CUDA). CUDA is an easy-to-use development framework that has drawn the attention of many different application areas looking for dramatic speed-ups in their code. However, the performance tradeoffs in CUDA are not yet fully understood, especially for data-parallel applications. Consequently, we study two fundamental mathematical operations that are common in many data-parallel applications: convolution and accumulation. Specifically, we profile and optimize the performance of these operations on a 128-core NVIDIA GPU. We then characterize the impact of these operations on a video-based motion-tracking algorithm called vector coherence mapping, which consists of a series of convolutions and dynamically weighted accumulations, and present a comparison of different implementations and their respective performance profiles
Computational Steering in the Problem Solving Environment WBCSim
Get PDFComputational steering allows scientists to interactively control a numerical experiment and adjust parameters of the computation on-the-fly and explore “what if †analysis. Computational steering effectively reduces computational time, makes research more efficient, and opens up new product design opportunities. There are several problem solving environments (PSEs) featuring computational steering. However, there is hardly any work explaining how to enable computational steering for PSEs embedded with legacy simulation codes. This paper describes a practical approach to implement computational steering for such PSEs by using WBCSim as an example. WBCSim is a Web based simulation system designed to increase the productivity of wood scientists conducting research on wood-based composites manufacturing processes. WBCSim serves as a prototypical example for the design, construction, and evaluation of small-scale PSEs. Various changes have been made to support computational steering across the three layers—client, server, developer—comprising the WBCSim system. A detailed description of the WBCSim system architecture is presented, along with a typical scenario of computational steering usage
On the Robust Mapping of Dynamic Programming onto a Graphics Processing Unit
Get PDFGraphics processing units (GPUs) have been widely used to accelerate algorithms that exhibit massive data parallelism or task parallelism. When such parallelism is not inherent in an algorithm, computational scientists resort to simply replicating the algorithm on every multiprocessor of a NVIDIA GPU, for example, to create such parallelism, resulting in embarrassingly parallel ensemble runs that deliver significant aggregate speed-up. However, the fundamental issue with such ensemble runs is that the problem size to achieve this speed-up is limited to the available shared memory and cache of a GPU multiprocessor. An example of the above is dynamic programming (DP), one of the Berkeley 13 dwarfs. All known DP implementations to date use the coarse-grained approach of embarrassingly parallel ensemble runs because a ï¬ner-grained parallelization on the GPU would require extensive communication between the multiprocessors of a GPU, which could easily cripple performance as communication between multiprocessors is not natively supported in a GPU. Consequently, we address the above by proposing a ï¬ne-grained parallelization of a single instance of the DP algorithm that is mapped to the GPU. Our parallelization incorporates a set of techniques aimed to substantially improve GPU performance: matrix re-alignment, coalesced memory access, tiling, and GPU (rather than CPU) synchronization. The specific DP algorithm that we parallelize is cal led Smith-Waterman (SWat), which is an optimal local-sequence alignment algorithm. We use this SWat algorithm as a baseline to compare our GPU implementation, i.e., CUDA-SWat, to our Cell implementation, i.e., Cell-SWat
An Empirical Study of a Repeatable Method for Reengineering Procedural Software Systems to Object- Oriented Systems
Get PDFThis paper describes a repeatable method for reengineering a procedural
system to an object-oriented system. The method uses coupling metrics to assist a domain
expert in identifying candidate objects. An application of the method to a simple program
is given, and the effectiveness of the various coupling metrics are discussed. We perform
a detailed comparison of our repeatable method with an ad hoc, manual reengineering
effort based on the same procedural program. The repeatable method was found to be
effective for identifying objects. It produced code that was much smaller, more efficient,
and passed more regression tests than the ad hoc method. Analysis of object-oriented
metrics indicated both simpler code and less variability among classes for the repeatable
method
Proceedings of the Fourth Annual Virginia Tech Center for Human-Computer Interaction Research Experience for Undergraduates (REU) Symposium
Get PDFVirginia Tech's Center for Human-Computer Interaction presents the project abstracts for the REU 2009 symposium. The REU (Research Experience for Undergraduates) program provides undergraduate students from various universities with the opportunity to spend eight weeks at Virginia Tech, working with our faculty and graduate students on research projects using the state-of-the-art technology and laboratories assembled here. The REU program is sponsored primarily by the National Science Foundation (IIS-0851774, IIS-0552732). Additional support was provided by the NSF (CNS-0540509), the VT CS Department CSRC, and IBM Research
Inter-Block GPU Communication via Fast Barrier Synchronization
Get PDFThe graphics processing unit (GPU) has evolved from a ï¬xed-function processor with programmable stages to a programmable processor with many ï¬xed-function components that deliver massive parallelism. Consequently, GPUs increasingly take advantage of the programmable processing power for general-purpose, non-graphics tasks, i.e., general-purpose computation on graphics processing units (GPGPU). However, while the GPU can massively accelerate data parallel (or task parallel) applications, the lack of explicit support for inter-block communication on the GPU hampers its broader adoption as a general-purpose computing device. Inter-block communication on the GPU occurs via global memory and then requires a barrier synchronization across the blocks, i.e., inter-block GPU communication via barrier synchronization. Currently, such synchronization is only available via the CPU, which in turn, incurs signiï¬cant overhead. Thus, we seek to propose more efï¬cient methods for inter-block communication. To systematically address this problem, we ï¬rst present a performance model for the execution of kernels on GPUs. This performance model partitions the kernel’s execution time into three phases: (1) kernel launch to the GPU, (2) computation on the GPU, and (3) inter-block GPU communication via barrier synchronization. Using three well-known algorithms — FFT, dynamic programming, and bitonic sort — we show that the latter phase, i.e., inter-block GPU communication, can consume more than 50% of the overall execution time. Therefore, we propose three new approaches to inter-block GPU communication via barrier synchronization, all of which run only on the GPU: GPU simple synchronization, GPU tree-based synchronization, and GPU lock-free synchronization. We then evaluate the efficacy of each of these approaches in isolation via a micro-benchmark as well as integrated with the three aforementioned algorithms. For the micro-benchmark, the experimental results show that our GPU lock-free synchronization performs 7.8 times faster than CPU explicit synchronization and 3.7 times faster than CPU implicit synchronization. When integrated with the FFT, dynamic programming, and bitonic sort algorithms, our GPU lock-free synchronization improves the performance by 8%, 24%, and 39%, respectively, when compared to the more efï¬cient CPU implicit synchronization
Priority-enabled Scheduling for Resizable Parallel Applications
Get PDFIn this paper, we illustrate the impact of dynamic resizability on parallel scheduling.
Our ReSHAPE framework includes an application scheduler that supports dynamic resizing of parallel applications. We propose and evaluate new scheduling policies made possible by our ReSHAPE framework. The framework also provides a platform to experiment with more interesting and sophisticated scheduling policies and scenarios for resizable parallel applications. The proposed policies support scheduling of parallel applications with and without user assigned priorities. Experimental results show that these scheduling policies significantly improve individual application turn around time as well as overall cluster utilization
Taming Multi-core Parallelism with Concurrent Mixin Layers
Get PDFThe recent shift in computer system design to multi-core technology requires that the developer leverage explicit parallel programming techniques in order to utilize available performance. Nevertheless, developing the requisite parallel applications remains a prohibitively-difficult undertaking, particularly for the general programmer. To mitigate many of the challenges in creating concurrent software, this paper introduces a new parallel programming methodology that leverages feature-oriented programming (FOP) to logically decompose a product line architecture (PLA) into concurrent execution units. In addition, our efficient implementation of this methodology, that we call concurrent mixin layers, uses a layered architecture to facilitate the development of parallel applications. To validate our methodology and accompanying implementation, we present a case study of a product line of multimedia applications deployed within a typical multi-core environment. Our performance results demonstrate that a product line can be effectively transformed into parallel applications capable of utilizing multiple cores, thus improving performance. Furthermore, concurrent mixin layers significantly reduces the complexity of parallel programming by eliminating the need for the programmer to introduce explicit low-level concurrency control. Our initial experience gives us reason to believe that concurrent mixin layers is a promising technique for taming parallelism in multi-core environments
BABES: Brushing+Linking, Attributes, and Blobs Extension to Storyboard
Get PDFAbstract. In this day and age, people not only deal with data but deal
with vast amounts of data which needs to be sorted and made sense of.
A subset of these people are intelligence analysts who sort through an
enormous amount of data that need to be organized to uncover plots and
subplots. We are proposing a tool called BABES (Brushing+Linking,
Attributes, and Blobs Extension to Storyboard) that will enable the
intelligence analyst to sort through data efficiently, uncover plots and
subplots using the brushing and linking and attributes features and work
with multiple subplots at the same time using the concept of ’blobs’