Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (5 results)

  • Article
  • Peer Reviewed
UC Davis Previously Published Works (2014)

Finding the shortest paths from a single source to all other vertices is a fundamental method used in a variety of higher-level graph algorithms. We present three parallel friendly and work-efficient methods to solve this Single-Source Shortest Paths (SSSP) problem: Workfront Sweep, Near-Far and Bucketing. These methods choose different approaches to balance the tradeoff between saving work and organizational overhead. 

In practice, all of these methods do much less work than traditional Bellman-Ford methods, while adding only a modest amount of extra work over serial methods. These methods are designed to have a sufficient parallel workload to fill modern massively-parallel machines, and select reorganizational schemes that map well to these architectures. We show that in general our Near-Far method has the highest performance on modern GPUs, outperforming other parallel methods.

We also explore a variety of parallel load-balanced graph traversal strategies and apply them towards our SSSP solver. Our work-saving methods always outperform a traditional GPU Bellman-Ford implementation, achieving rates up to 14x higher on low-degree graphs and 340x higher on scalefree graphs. We also see significant speedups (20–60x) when compared against a serial implementation on graphs with adequately high degree.

    Cover page: Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths
    • Article
    • Peer Reviewed
    IDAV Publications (2012)
    We design a high-performance parallel merge sort for highly parallel systems. Our merge sort is designed to use more register communication (not shared memory), and does not suffer from over-segmentation as opposed to previous comparison based sorts. Using these techniques we are able to achieve a sorting rate of 250 MKeys/sec, which is about 2.5 times faster than Thrust merge sort performance, and 70% faster than non-stable state-of-the-art GPU merge sorts. Building on this sorting algorithm, we develop a scheme for sorting variable-length key/value pairs, with a special emphasis on string keys. Sorting non-uniform, unaligned data such as strings is a fundamental step in a variety of algorithms, yet it has received comparatively little attention. To our knowledge, our system is the first published description of an efficient string sort for GPUs. We are able to sort strings at a rate of 70 MStrings/s on one dataset and up to 1.25 GB/s on another dataset using a GTX 580.
      Cover page: Efficient Parallel Merge Sort for Fixed and Variable Length Keys
      • Article
      • Peer Reviewed
      IDAV Publications (2011)
        Cover page: Efficient Parallel Scan Algorithms for Many-core GPUs
        • Article
        • Peer Reviewed
        UC Davis Previously Published Works (2020)
        The mechanisms underlying mammalian neural tube closure remain poorly understood. We report a unique cellular process involving multicellular rosette formation, convergent cellular protrusions, and F-actin cable network of the non-neural surface ectodermal cells encircling the closure site of the posterior neuropore, which are demonstrated by scanning electron microscopy and genetic fate mapping analyses during mouse spinal neurulation. These unique cellular structures are severely disrupted in the surface ectodermal transcription factor Grhl3 mutants that exhibit fully penetrant spina bifida. We propose a novel model of mammalian neural tube closure driven by surface ectodermal dynamics, which is computationally visualized.
          Cover page: Non-neural surface ectodermal rosette formation and F-actin dynamics drive mammalian neural tube closure
          • Article
          • Peer Reviewed
          UC Davis Previously Published Works (2020)
          During craniofacial development, defective growth and fusion of the upper lip and/or palate can cause orofacial clefts (OFCs), which are among the most common structural birth defects in humans. The developmental basis of OFCs includes morphogenesis of the upper lip, primary palate, secondary palate, and other orofacial structures, each consisting of diverse cell types originating from all three germ layers: the ectoderm, mesoderm, and endoderm. Cranial neural crest cells and orofacial epithelial cells are two major cell types that interact with various cell lineages and play key roles in orofacial development. The cellular basis of OFCs involves defective execution in any one or several of the following processes: neural crest induction, epithelial-mesenchymal transition, migration, proliferation, differentiation, apoptosis, primary cilia formation and its signaling transduction, epithelial seam formation and disappearance, periderm formation and peeling, convergence and extrusion of palatal epithelial seam cells, cell adhesion, cytoskeleton dynamics, and extracellular matrix function. The latest cellular and developmental findings may provide a basis for better understanding of the underlying genetic, epigenetic, environmental, and molecular mechanisms of OFCs.
            Cover page: Cellular and developmental basis of orofacial clefts
            Top