More Like this

1. OpenACC Based GPU Parallelization of Plane Sweep Algorithm for Geometric Intersection.

   https://doi.org/10.1007/978-3-030-12274-4  

   Paudel, Anmol ; Puri, Satish ( January 2019 , Chandrasekaran S., Juckeland G., Wienke S. (eds) Accelerator Programming Using Directives. WACCPD 2018. Lecture Notes in Computer Science, Springer, Cham)

   Line segment intersection is one of the elementary operations in computational geometry. Complex problems in Geographic Information Systems (GIS) like finding map overlays or spatial joins using polygonal data require solving segment intersections. Plane sweep paradigm is used for finding geometric intersection in an efficient manner. However, it is difficult to parallelize due to its in-order processing of spatial events. We present a new fine-grained parallel algorithm for geometric intersection and its CPU and GPU implementation using OpenMP and OpenACC. To the best of our knowledge, this is the first work demonstrating an effective parallelization of plane sweep on GPUs. We chose compiler directive based approach for implementation because of its simplicity to parallelize sequential code. Using Nvidia Tesla P100 GPU, our implementation achieves around 40X speedup for line segment intersection problem on 40K and 80K data sets compared to sequential CGAL library. 

   more » « less
2. Issues in the Reproducibility of Deep Learning Results

   https://doi.org/10.1109/SPMB47826.2019.9037840  

   Jean-Paul, S. ; Elseify, T. ; Obeid, I. ; Picone, J. ( December 2019 , IEEE Signal Processing in Medicine and Biology Symposium (SPMB))

   Obeid, I. ; Selesnik, I. ; Picone, J. (Ed.)

   The Neuronix high-performance computing cluster allows us to conduct extensive machine learning experiments on big data [1]. This heterogeneous cluster uses innovative scheduling technology, Slurm [2], that manages a network of CPUs and graphics processing units (GPUs). The GPU farm consists of a variety of processors ranging from low-end consumer grade devices such as the Nvidia GTX 970 to higher-end devices such as the GeForce RTX 2080. These GPUs are essential to our research since they allow extremely compute-intensive deep learning tasks to be executed on massive data resources such as the TUH EEG Corpus [2]. We use TensorFlow [3] as the core machine learning library for our deep learning systems, and routinely employ multiple GPUs to accelerate the training process. Reproducible results are essential to machine learning research. Reproducibility in this context means the ability to replicate an existing experiment – performance metrics such as error rates should be identical and floating-point calculations should match closely. Three examples of ways we typically expect an experiment to be replicable are: (1) The same job run on the same processor should produce the same results each time it is run. (2) A job run on a CPU and GPU should produce identical results. (3) A job should produce comparable results if the data is presented in a different order. System optimization requires an ability to directly compare error rates for algorithms evaluated under comparable operating conditions. However, it is a difficult task to exactly reproduce the results for large, complex deep learning systems that often require more than a trillion calculations per experiment [5]. This is a fairly well-known issue and one we will explore in this poster. Researchers must be able to replicate results on a specific data set to establish the integrity of an implementation. They can then use that implementation as a baseline for comparison purposes. A lack of reproducibility makes it very difficult to debug algorithms and validate changes to the system. Equally important, since many results in deep learning research are dependent on the order in which the system is exposed to the data, the specific processors used, and even the order in which those processors are accessed, it becomes a challenging problem to compare two algorithms since each system must be individually optimized for a specific data set or processor. This is extremely time-consuming for algorithm research in which a single run often taxes a computing environment to its limits. Well-known techniques such as cross-validation [5,6] can be used to mitigate these effects, but this is also computationally expensive. These issues are further compounded by the fact that most deep learning algorithms are susceptible to the way computational noise propagates through the system. GPUs are particularly notorious for this because, in a clustered environment, it becomes more difficult to control which processors are used at various points in time. Another equally frustrating issue is that upgrades to the deep learning package, such as the transition from TensorFlow v1.9 to v1.13, can also result in large fluctuations in error rates when re-running the same experiment. Since TensorFlow is constantly updating functions to support GPU use, maintaining an historical archive of experimental results that can be used to calibrate algorithm research is quite a challenge. This makes it very difficult to optimize the system or select the best configurations. The overall impact of all of these issues described above is significant as error rates can fluctuate by as much as 25% due to these types of computational issues. Cross-validation is one technique used to mitigate this, but that is expensive since you need to do multiple runs over the data, which further taxes a computing infrastructure already running at max capacity. GPUs are preferred when training a large network since these systems train at least two orders of magnitude faster than CPUs [7]. Large-scale experiments are simply not feasible without using GPUs. However, there is a tradeoff to gain this performance. Since all our GPUs use the NVIDIA CUDA® Deep Neural Network library (cuDNN) [8], a GPU-accelerated library of primitives for deep neural networks, it adds an element of randomness into the experiment. When a GPU is used to train a network in TensorFlow, it automatically searches for a cuDNN implementation. NVIDIA’s cuDNN implementation provides algorithms that increase the performance and help the model train quicker, but they are non-deterministic algorithms [9,10]. Since our networks have many complex layers, there is no easy way to avoid this randomness. Instead of comparing each epoch, we compare the average performance of the experiment because it gives us a hint of how our model is performing per experiment, and if the changes we make are efficient. In this poster, we will discuss a variety of issues related to reproducibility and introduce ways we mitigate these effects. For example, TensorFlow uses a random number generator (RNG) which is not seeded by default. TensorFlow determines the initialization point and how certain functions execute using the RNG. The solution for this is seeding all the necessary components before training the model. This forces TensorFlow to use the same initialization point and sets how certain layers work (e.g., dropout layers). However, seeding all the RNGs will not guarantee a controlled experiment. Other variables can affect the outcome of the experiment such as training using GPUs, allowing multi-threading on CPUs, using certain layers, etc. To mitigate our problems with reproducibility, we first make sure that the data is processed in the same order during training. Therefore, we save the data from the last experiment and to make sure the newer experiment follows the same order. If we allow the data to be shuffled, it can affect the performance due to how the model was exposed to the data. We also specify the float data type to be 32-bit since Python defaults to 64-bit. We try to avoid using 64-bit precision because the numbers produced by a GPU can vary significantly depending on the GPU architecture [11-13]. Controlling precision somewhat reduces differences due to computational noise even though technically it increases the amount of computational noise. We are currently developing more advanced techniques for preserving the efficiency of our training process while also maintaining the ability to reproduce models. In our poster presentation we will demonstrate these issues using some novel visualization tools, present several examples of the extent to which these issues influence research results on electroencephalography (EEG) and digital pathology experiments and introduce new ways to manage such computational issues. 

   more » « less
3. GPU-I-TASSER: a GPU accelerated I-TASSER protein structure prediction tool

   https://doi.org/10.1093/bioinformatics/btab871  

   MacCarthy, Elijah A. ; Zhang, Chengxin ; Zhang, Yang ; KC, Dukka B. ; Cowen, ed., Lenore ( January 2022 , Bioinformatics)

   Accurate and efficient predictions of protein structures play an important role in understanding their functions. Iterative Threading Assembly Refinement (I-TASSER) is one of the most successful and widely used protein structure prediction methods in the recent community-wide CASP experiments. Yet, the computational efficiency of I-TASSER is one of the limiting factors that prevent its application for large-scale structure modeling.

   We present I-TASSER for Graphics Processing Units (GPU-I-TASSER), a GPU accelerated I-TASSER protein structure prediction tool for fast and accurate protein structure prediction. Our implementation is based on OpenACC parallelization of the replica-exchange Monte Carlo simulations to enhance the speed of I-TASSER by extending its capabilities to the GPU architecture. On a benchmark dataset of 71 protein structures, GPU-I-TASSER achieves on average a 10× speedup with comparable structure prediction accuracy compared to the CPU version of the I-TASSER.

   The complete source code for GPU-I-TASSER can be downloaded and used without restriction from https://zhanggroup.org/GPU-I-TASSER/.

   Supplementary data are available at Bioinformatics online.

    

   more » « less
4. Rumor Has It: Optimizing the Belief Propagation Algorithm for Parallel Processing

   https://doi.org/10.1145/3409390.3409401  

   Trotter, Michael ; Wood, Timothy ; Huang, H. Howie ( August 2020 , 49th International Conference on Parallel Processing - ICPP : Workshops)

   null (Ed.)

   By modelling how the probability distributions of individuals’ states evolve as new information flows through a network, belief propagation has broad applicability ranging from image correction to virus propagation to even social networks. Yet, its scant implementations confine themselves largely to the realm of small Bayesian networks. Applications of the algorithm to graphs of large scale are thus unfortunately out of reach. To promote its broad acceptance, we enable belief propagation for both small and large scale graphs utilizing GPU processing. We therefore explore a host of optimizations including a new simple yet extensible input format enabling belief propagation to operate at massive scale, along with significant workload processing updates and meticulous memory management to enable our implementation to outperform prior works in terms of raw execution time and input size on a single machine. Utilizing a suite of parallelization technologies and techniques against a diverse set of graphs, we demonstrate that our implementations can efficiently process even massive networks, achieving up to nearly 121x speedups versus our control yet optimized single threaded implementations while supporting graphs of over ten million nodes in size in contrast to previous works’ support for thousands of nodes using CPU-based multi-core and host solutions. To assist in choosing the optimal implementation for a given graph, we provide a promising method utilizing a random forest classifier and graph metadata with a nearly 95% F1-score from our initial benchmarking and is portable to different GPU architectures to achieve over an F1-score of over 72% accuracy and a speedup of nearly 183x versus our control running in this new environment. 

   more » « less
5. Real‐time parallel 3D multiple particle tracking with single molecule centrifugal force microscopy

   https://doi.org/10.1111/jmi.12773  

   KOU, L. ; JIN, L. ; LEI, H. ; HU, C. ; LI, H. ; HU, X. ; HU, X. ( November 2018 , Journal of Microscopy)

   Real‐time tracking of multiple particles is key for quantitative analysis of dynamic biophysical processes and materials science via time‐lapse microscopy image data, especially for single molecule biophysical techniques, such as magnetic tweezers and centrifugal force microscopy. However, real‐time multiple particle tracking with high resolution is limited by the current imaging processes or tracking algorithms. Here, we demonstrate 1 nm resolution in three dimensions in real‐time with a graphics‐processing unit (GPU) based on a compute unified device architecture (CUDA) parallel computing framework instead of only a central processing unit (CPU). We also explore the trade‐offs between processing speed and size of the utilized regions of interest and a maximum speedup of 137 is achieved with the GPU compared with the CPU. Moreover, we utilize this method with our recently self‐built centrifugal force microscope (CFM) in experiments that track multiple DNA‐tethered particles. Our approach paves the way for high‐throughput single molecule techniques with high resolution and efficiency.

   Particles are widely used as probes in life sciences through their motions. In single molecule techniques such as optical tweezers and magnetic tweezers, microbeads are used to study intermolecular or intramolecular interactions via beads tracking. Also tracking multiple beads’ motions could study cell–cell or cell–ECM interactions in traction force microscopy. Therefore, particle tracking is of key important during these researches. However, parallel 3D multiple particle tracking in real‐time with high resolution is a challenge either due to the algorithm or the program. Here, we combine the performance of CPU and CUDA‐based GPU to make a hybrid implementation for particle tracking. In this way, a speedup of 137 is obtained compared the program before only with CPU without loss of accuracy. Moreover, we improve and build a new centrifugal force microscope for multiple single molecule force spectroscopy research in parallel. Then we employed our program into centrifugal force microscope for DNA stretching study. Our results not only demonstrate the application of this program in single molecule techniques, also indicate the capability of multiple single molecule study with centrifugal force microscopy.

    

   more » « less