home button research button publications button teaching button contact button
MARTIN BURTSCHER

Recent Research Projects

The following is an overview of some projects I have worked on with my students and collaborators.

I am looking for motivated students who are interested in working on similar research with me.
Please check out our BS program, MS program, and PhD program.


N-body Simulation (BH)

We created the first and probably still the fastest entirely GPU-based implementation of the Barnes-Hut algorithm for simulating n-body systems, i.e., computing the motion of many objects under the influence of mutual forces. Such simulations can, for example, help us understand how galaxies evolve over time.

To the right is a slowed-down simulation of a 1000-star cluster. It shows how the stars orbit each other under mutual gravitational forces. The CUDA source code is available here and a detailed description of this work is available here.

On a Titan V GPU, our code can simulate a time step per second with 6.5 million stars and supports inputs of up to 74 million stars.


n-body simulation

Traveling Salesperson Problem (TSP)

We wrote two of the fastest GPU codes that implement the 2-opt heuristic (with random restarts) to compute a good solution for the TSP problem, i.e., for finding a short route that visits each location of a given set of locations exactly once and returns to the starting point. Such solutions are used, for example, in the planning of delivery-truck routes or robot-arm movements.

To the right is a slowed-down visualization of a 575-location run. It shows how an initially random tour is gradually shortened until the heuristic no longer applies. The CUDA code is available here and detailed descriptions of this work are available here and here.

On a Titan V GPU, our code can evaluate over 300 billion tour modifications per second and supports inputs of up to 32000 locations.


TSP animation

Maximal Independent Set (MIS)

We devised a GPU implementation for computing maximal independent sets that is not only much faster than other single-device codes but also consistently produces larger sets. An independent set of a graph is a subset of its vertices such that there is no edge connecting any two vertices in the set. Such sets are used, for example, to assign to an ambulance as many non-emergency medical transports as possible.

To the right is a visualization of the steps of our algorithm on a very small graph. The CUDA code is available here and a detailed description of this work is available here.

On a Titan V GPU, our code finds a MIS with 49.0% of the vertices of the U.S. road map in just 4.5 milliseconds. This input has 23.9 million intersections and 57.7 million road segments.


MIS animation

Parallelized Linear Recurrences (PLR)

We invented a new technique to compute linear recurrences in parallel and implemented it on a GPU. Recurrences are computations where later result values depend on earlier result values, making them difficult to parallelize. Our PLR approach is more general and/or outperforms other techniques on most recurrences. Linear recurrences are used, for example, to simplify parallel programming and to improve the quality of digital sound.

To the right is a visualization of a low-pass filter that smoothens the noisy green audio signal and produces the clearer purple signal. The CUDA code is available here and a detailed description of this work is available here.

On a Titan V GPU, our code can apply a single-stage low-pass filter on 170 hours of CD-quality music in one second.


PLR animation

Connected Components (CC)

We developed an approach for computing the connected components of an undirected graph that is much faster than the fastest prior GPU, multi-core CPU, and serial codes. A connected component of a graph is a subset of its vertices such that any vertex can reach all other vertices in the subset by following the edges of the graph but cannot reach vertices from other components. Connected components are used for cancer and tumor detection, drug discovery, etc.

To the right is a visualization of a connected-components algorithm. The CUDA code of our implementation is available here and a detailed description of this work is available here.

On a Titan V GPU, our code finds the connected components of a 2002 crawl of the .uk domain in under 15 milliseconds. This symmetrised input contains 18.5 million vertices (web pages) and 523.6 million edges.


ECL-CC animation

Automatic Synthesis of Lossless Compression Algorithms (CRUSHER)

We pioneered a method to automatically generate lossless compression and decompression algorithms. Our first-of-its-kind CRUSHER framework creates millions of algorithm candidates from which it selects the most effective for a given set of training inputs and constraints. In this way, it has already produced customized algorithms that not only outperform the state of the art in compression ratio but also require little memory, are GPU-friendly, or provide a high throughput.

We have successfully used CRUSHER to generate massively-parallel compressors, space-probe-friendly compressors, per-file customized compressors, and an algorithm that works well for both single- and double-precision floating-point data. Below is a visualization of how our approach can be used to improve the cost-effectiveness of space probes.

space compression animation


Research Awards

Excellence in Research Award
College of Science and Engineering, Texas State University, 2017

Best Paper Candidate
IEEE International Conference on Computer Communications and Networks, 2015

Excellence in Research Award
College of Science and Engineering, Texas State University, 2014

Academic Partnership Award
NVIDIA Corporation, 2011

Best Paper Award
IEEE International Symposium on Performance Analysis of Systems and Software, 2011

Best Paper Candidate
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2010

Presentations

Martin's presentation at GTC'18
Jayadharini's presentation at GTC'17
Martin's presentation at GTC'17
Sepideh's presentation at GTC'16
Jared's presentation at GTC'15
Martin's presentation at GTC'15
Martin's second presentation at GTC'14
Martin's first presentation at GTC'14
Martin and Rupesh's presentation at GTC'13
Martin's presentation at GTC'12
Martin's interview on Portuguese TV in 2011
Martin's research overview 2011
Martin's keynote at EuroPVM/MPI'09


Sponsors

This work has kindly been supported by research and teaching grants, subcontracts, and equipment gifts from:
National Science Foundation
Department of Energy
Defense Advanced Research Projects Agency
NVIDIA Corporation
Intel Corporation
Microsoft Corporation


News

2019-08-23: Martin receives Excellence in Teaching Award from College of Science and Engineering
2019-07-18: The CLUSTER'19 paper is accepted
2019-06-24: Martin presents a fast and high-quality MIS implementation for GPUs at ETH Zurich
2019-06-21: The ICCAD'19 paper is accepted
2019-05-07: Martin gives another guest lecture on GPU programming at UT Austin
2019-05-06: Martin is invited to review proposals for NASA's AIST program
2019-05-02: Martin gives guest lecture on GPU programming at UT Austin
2019-04-30: An interview about ECL is published in ACM XRDS
2019-04-30: Martin is invited to be a member of the program committee of DRBSD'19
2019-04-12: Martin talks about high-performance design and implementation of complex algorithms for GPUs at AMD
2019-01-16: NVIDIA donates Titan V GPU to ECL
2019-01-16: The OpenMP ECL-MIS code for computing large maximal independent sets is released
2018-12-10: Martin is invited to be a member of the program committee of GPGPU'19
2018-12-01: Martin receives DARPA IDEA subaward
2018-11-11: Martin presents the zooming into a fractal parallel-programming project at EduHPC'18
2018-10-05: The ESPT'18 paper is accepted
2018-09-24: Martin's EduHPC'18 peachy assignment is accepted
2018-09-18: The WOSET'18 paper is accepted
2018-07-06: Martin talks about automatic parallelization of linear recurrences at ETH Zurich
2018-06-22: Martin presents a fast connected-components algorithm for GPUs at UT Austin
2018-06-13: Martin presents a fast connected-components algorithm for GPUs at HPDC'18
2018-04-23: Martin talks about automatic parallelization of linear recurrences at Texas A&M University
2018-04-12: Martin talks about automatic parallelization of linear recurrences at Oakland University
2018-04-06: Prof. Ganesh Gopalakrishnan from the University of Utah gives a colloquium on "Can Formal Methods (alone) Rescue HPC Debugging?"
2018-03-30: Sindhu, Sahar, Jayadharini, and Evan's TOPC'18 paper is accepted
2018-03-30: Martin talks about the synthesis of data-compression algorithms at DCC'18
2018-03-28: Martin talks about automatic parallelization of linear recurrences at GTC'18
2018-03-26: Sepideh talks about automatic parallelization of linear recurrences at ASPLOS'18
2018-03-25: Jayadharini's HPDC'18 paper is accepted
2018-03-01: Martin is invited to be a mentor in the Oakland University PI Academy
2018-02-06: Sepideh's PLR code for parallelizing linear recurrences is released
2018-01-02: Martin is invited to be a member of the program committee of DRBSD'18
2017-12-29: NVIDIA donates Titan Xp GPU to ECL
2017-12-24: Steven and Sahar's DCC'18 paper is accepted
2017-11-14: Sepideh's ASPLOS'18 paper is accepted
2017-10-28: Martin is invited to be a member of the program committee of GPGPU'18
2017-08-25: Martin receives Excellence in Research Award from College of Science and Engineering
2017-06-08: Martin is invited to be a member of the external review committee of PPoPP'18
2017-05-18: Martin presents a fast and high-quality MIS implementation for GPUs at UT Austin
2017-05-10: Jayadharini presents a fast connected-components algorithm for GPUs at GTC'17
2017-05-10: Martin presents a fast and high-quality MIS implementation for GPUs at GTC'17
2017-04-21: Arthi receives CS Graduate Research Excellence Award
2017-04-21: Jayadharini receives CS Graduate Research Excellence Award
2017-04-21: Jared receives CS Graduate Research Excellence Award
2017-04-21: Sahar receives CS Graduate Research Excellence Award
2017-04-21: Kristi receives CS Undergraduate Research Excellence Award
2017-04-21: Dean receives CS Undergraduate Research Excellence Award
2017-03-17: Kristi receives NSF Graduate Research Fellowship
2017-03-17: Jared receives NSF Graduate Research Fellowship
2017-02-03: Sepideh receives the Conference of Southern Graduate School's Outstanding Master's Thesis Award in Math, Physical Sciences and Engineering
2017-01-14: Martin is invited to be a member of the program committee of DRBSD'17
2016-11-28: Martin is invited to be a member of the program committee of EuroPar'17
2016-11-15: Martin talks about synthesizing compression algorithms in real-time at SC'16
2016-11-14: Martin gives CS colloquium at the University of Utah
2016-11-11: Martin receives Alpha Chi Favorite Professors for 2016 Award
2016-11-09: Sepideh receives the Graduate College's Outstanding Master's Thesis Award
2016-10-27: FPcrush is now available on Maverick at TACC
2016-10-26: ACCN book chapter is accepted
2016-10-20: Martin is invited to be a member of the program committee of GPGPU'17
2016-10-10: Martin presents his Barnes Hut GPU implementation at UT Austin
2016-09-19: Jared's AGRP'16a book chapter is published
2016-09-19: Annie et al.'s AGRP'16b book chapter is published
2016-09-14: Jared presents a data-compression approach for space probes at SPACE'16
2016-08-01: Martin receives REU supplement grant from NSF
2016-07-29: Martin is invited to be a member of the external review committee of PPoPP'17
2016-06-16: Sepideh presents a generalized prefix-scan algorithm at PLDI'16
2016-06-16: Farbod, Hari, and Annie's SC'16 paper is accepted
2016-05-27: Jared presents an energy characterization of GPU benchmark suites at HPPAC'16
2016-05-05: Jared and Annie's SPACE'16 paper is accepted
2016-04-11: Sepideh presents a generalized prefix-scan algorithm for GPUs at UT Austin
2016-04-10: PLDI'16 AEC found the SAM code to meet or exceed expectations
2016-04-08: Jayadharini receives CS Graduate Research Excellence Award
2016-04-08: Sahar receives CS Graduate Research Excellence Award
2016-04-08: Sindhu receives CS Graduate Research Excellence Award
2016-04-08: Sepideh receives CS Graduate Research Excellence Award
2016-04-08: Kristi receives CS Undergraduate Research Excellence Award
2016-04-08: Jared receives CS Undergraduate Research Excellence Award
2016-04-08: Sepideh receives Outstanding Master's Student Award from College of Sci. and Eng.
2016-04-07: NVIDIA donates Titan X GPU to ECL
2016-04-06: Sepideh presents a new prefix-scan algorithm for GPUs at GTC'16
2016-03-13: Sepideh and Annie's SAM code for higher-order and tuple-based prefix scans is released
2016-03-08: The GPU Education Center at Texas State University has been renewed
2016-02-23: Jared's HPPAC'16 paper is accepted
2016-02-12: HCW'16 paper is accepted
2016-02-05: A collection of single-precision floating-point data sets is made available
2016-02-04: The SPDP compressor for floating-point data is released
2016-01-20: Sepideh and Annie's PLDI'16 paper is accepted
2015-12-16: Jared receives the CRA 2016 Outstanding Undergraduate Researcher Award
2015-12-05: Jared's AGRP book chapter is accepted
2015-12-05: Annie et al.'s AGRP book chapter is accepted
2015-12-02: Steven's SPDP compression filter for HDF5 is released
2015-11-13: Martin receives Alpha Chi Favorite Professors for 2015 Award
2015-10-26: Martin is named senior advisor of Hyperion Core
2015-10-10: Martin is invited to be a member of the program committee of GPGPU'16
2015-09-11: Annie talks about synthesizing effective compression algorithms for GPUs at Cluster'15
2015-09-01: Martin is promoted to Professor
2015-08-05: ICCCN'15 paper is ranked among top 5 of 88 and nominated for best paper award
2015-06-29: NVIDIA donates Tesla K40 GPU to ECL
2015-06-06: HPCC'15 paper is accepted
2015-06-02: Martin receives REU supplement grant from NSF
2015-06-02: Martin starts consulting for Hyperion Core
2015-05-13: JIS'15 paper is accepted
2015-05-11: Annie, Hari, and Farbod's Cluster'15 paper is accepted
2015-05-04: Saeed's PDPTA'15 paper is accepted
2015-04-29: Martin gives math colloquium at Southern Methodist University
2015-04-24: Jared receives Outstanding Undergraduate Student Award from College of Sci. and Eng.
2015-04-24: Sindhu receives CS Graduate Research Excellence Award
2015-04-24: Farbod receives CS Graduate Research Excellence Award
2015-04-24: Sepideh receives CS Graduate Research Excellence Award
2015-04-24: Molly receives CS Graduate Research Excellence Award
2015-04-24: Jared receives CS Undergraduate Research Excellence Award
2015-04-24: Annie receives CS Undergraduate Research Excellence Award
2015-04-13: ICCCN'15 paper is accepted
2015-03-20: Jared talks about GPU code optimizations to reduce energy at GTC'15
2015-03-20: Martin talks about synthesizing effective compression algorithms for GPUs at GTC'15
2015-02-07: Molly talks about improved GPU parallelization for hill climbing at GPGPU'15
2015-02-07: Jared talks about GPU code optimizations to reduce energy at GPGPU'15
2015-01-06: Jared's GPGPU'15a paper is accepted
2015-01-06: Molly's GPGPU'15b paper is accepted
2015-01-01: Martin joins the advisory board of Accelogic
2014-12-04: Martin receives REP grant from Texas State University
2014-11-05: Martin is named Distinguished Scientist by the ACM
2014-11-03: Jared presents power characteristics of irregular GPGPU programs at GPCDP'14
2014-10-28: Molly presents a performance characterization of irregular GPU kernels at IISWC'14
2014-10-23: CVIU'14 paper is accepted
2014-10-13: SIGCSE'15 paper is accepted
2014-09-24: Jared's GPCDP'14 paper is accepted
2014-09-04: NVIDIA donates Jetson TK1 Development Kits
2014-08-22: Martin receives Excellence in Research Award from College of Science and Engineering
2014-08-19: Martin and Ilya's patent on future execution is licensed
2014-08-16: Martin is invited to be a member of the program committee of Cluster'15
2014-08-15: Martin et al. teach TUES workshop at Texas State University
2014-07-16: Martin is invited to be a member of the external review committee of PPoPP'15
2014-06-23: Martin et al. receive NSF CSR grant
2014-06-18: Martin et al. receive NSF XPS grant
2014-06-17: Molly's IISWC'14 paper is accepted
2014-05-24: Martin is invited to be a member of the external review committee of PLDI'15
2014-05-19: NAS'14 paper is accepted
2014-05-13: Hassan's DMIN'14 paper is accepted
2014-05-01: Martin is invited to be a participant in the DOE's Workshop on Exascale Productivity
2014-04-25: Jared receives CS Undergraduate Research Excellence Award
2014-03-27: Martin talks about accurately measuring power on K20/K40 GPUs at GTC'14
2014-03-26: Martin presents a high-speed CUDA 2-opt TSP solver for large problems at GTC'14
2014-03-26: Martin co-hosts a "GTC Speakers Hangout" at GTC'14
2014-03-24: Martin receives Alpha Chi Favorite Professors for Spring 2014 Award
2014-03-05: 3DOR'14 paper is accepted
2014-03-01: Martin gives talk on measuring GPU power with the K20 built-in sensor at GPGPU'14
2014-02-05: Martin receives REU supplement grant from NSF
2014-01-31: Dr. Ben Zorn from Microsoft Research gives colloquium on Synthesis and Security in a World of Devices and Services
2014-01-26: GPGPU'14 paper is accepted
2014-01-09: Invited HPCwire article is published
2013-11-20: SAC'14 paper is accepted
2013-10-22: EduPDHPC'13 paper is accepted
2013-10-15: IPCCC'13 paper is accepted
2013-09-09: SC'13 poster is accepted
2013-08-16: Martin starts consulting for Accelogic
2013-07-06: PASA'13 paper is accepted
2013-06-05: MASCOTS'13 paper is accepted
2013-05-23: Martin presents IPDPS'13a paper in Boston, MA
2013-05-07: PDPTA'13 paper is accepted
2013-05-06: Martin is invited to be a member of the program committee of PLDI'14
2013-04-19: Martin gives ECE colloquium at The University of Alabama in Huntsville
2013-04-16: Prof. Keshav Pingali from UT Austin gives guest lecture on parallel programming
2013-04-08: Martin is invited to be a member of the program committee of PPoPP'14
2013-03-21: Martin and Rupesh present their work on irregular GPU codes at GTC'13
2013-01-23: GPGPU'13 paper is accepted
2013-01-16: The LonestarGPU suite of irregular CUDA programs is released
2013-01-15: NVIDIA donates Tesla K20 GPUs to ECL
2012-12-23: IPDPS'13a paper is accepted
2012-12-23: IPDPS'13b paper is accepted
2012-12-08: ISPASS'13 poster is accepted
2012-12-06: Ziliang and Martin receive REP grant from Texas State University
2012-11-30: NVIDIA donates 16 additional high-end GPUs for teaching lab
2012-11-12: PPoPP'13 paper is accepted
2012-10-18: TC'14 paper is accepted
2012-09-29: Martin is invited to be a member of the program committee of GPGPU'13
2012-09-23: Martin teaches half-day CUDA optimization tutorial at PACT'12
2012-09-21: Martin gives CS colloquium at Marquette University
2012-09-04: NVIDIA donates Kepler-based GPU to ECL
2012-08-17: IISWC'12 paper is accepted
2012-08-16: Martin et al. receive NSF TUES grant (press release)
2012-08-03: Martin et al. teach PerfExpert tutorial at the TACC Summer Supercomputing Institute
2012-08-01: Martin receives Early Adopter grant from NSF/TCPP Curriculum Initiative on PDC
2012-07-11: Martin et al. receive NSF CNS grant
2012-06-11: Martin is invited to be a member of the program committee of PPoPP'13
2012-06-11: NVIDIA donates 8 high-end GPUs for energy-efficient computing research
2012-05-17: Martin presents his Barnes Hut GPU implementation at GTC'12
2012-04-27: Prof. Igor Szczyrba from UNC gives colloquium on Modeling of Traumatic Brain Injuries
2012-04-23: BIOCOMP'12 paper is accepted
2012-04-20: Molly receives Outstanding Graduate Student Award from the College of Science
2012-03-15: ICS'12 paper is accepted
2012-03-05: Martin receives Excellence in Teaching Award from College of Science and Engineering
2012-02-25: Martin teaches half-day CUDA optimization tutorial at PPoPP'12
2012-02-25: Martin et al. teach half-day PerfExpert tutorial at PPoPP'12
2012-02-07: Texas State University is selected as a CUDA Teaching Center by NVIDIA
2011-12-08: NVIDIA donates 16 high-end GPUs for teaching lab
2011-11-19: PPoPP'12 paper is accepted
2011-11-14: Martin receives NVIDIA Academic Partnership Award
2011-11-14: Martin et al.'s PerfExpert project is showcased by TACC at SC'11
2011-10-11: Martin is invited to be a member of the program committee of GPGPU'12
2011-10-10: Martin teaches half-day CUDA optimization tutorial at PACT'11
2011-10-07: Dr. Lars Koesterke from TACC gives colloquium on Intel's MIC accelerator
2011-09-30: Martin et al. teach half-day PerfExpert tutorial at Cluster'11
2011-08-18: Texas State University donates high-end server to ECL
2011-08-05: Martin et al. teach half-day PerfExpert tutorial at the TACC Summer Institute
2011-07-21: Martin presents PDPTAb'11 paper in Las Vegas, NV
2011-07-21: Martin is invited to be a member of the external review committee of PPoPP'12
2011-07-20: Martin presents PDPTAa'11 paper in Las Vegas, NV
2011-07-08: Martin teaches half-day CUDA optimization tutorial at GPU'11 in Coimbra, Portugal
2011-07-07: Martin is interviewed by Portuguese TV on GPU programming
2011-04-25: Martin et al. teach full-day PerfExpert tutorial at TACC
2011-04-21: Olalekan's PDPTA'11 paper is accepted
2011-04-19: Molly gives guest lecture on multicore architectures at Texas State University
2011-04-19: Martin gives guest lecture on GPU programming at UT Austin
2011-04-17: Molly's PDPTA'11 paper is accepted
2011-04-12: ISPASS'11 paper receives best paper award
2011-04-08: Molly receives CS Graduate Research Excellence Award
2011-04-05: Molly receives NSF Graduate Research Fellowship
2011-04-04: Martin gives guest lecture on GPU programming at UT Austin
2011-04-04: BIOCOMP'11 paper is accepted
2011-03-05: Molly presents GPGPU'11 paper in Newport Beach, CA
2011-03-02: Martin et al.'s PerfExpert research is featured on TACC web page
2011-02-10: Intel donates high-end server to ECL
2011-02-07: Martin et al.'s PerfExpert research is covered in magazine article
2011-02-02: PLDI'11 paper is accepted
2011-01-22: Molly's GPGPU'11 paper is accepted
2011-01-19: TC'12 paper is accepted
2011-01-11: Martin gives guest lectures at WACS in Braga, Portugal
2011-01-11: Martin et al.'s brain injury research is covered in newspaper article
2010-12-10: Martin is interviewed by Genome Technology on PerfExpert
2010-12-06: ISPASS'11 paper is accepted
2010-12-03: Martin receives REP grant from Texas State University
2010-11-18: Martin presents SC'10 paper in New Orleans, LA
2010-11-16: Martin et al.'s Traumatic Brain Injury Simulator is demonstrated by Intel at SC'10
2010-10-23: PPoPP'11 paper is accepted
2010-10-01: NVIDIA donates 2 high-end GPUs to ECL
2010-09-01: Inauguration of ECL

Official Texas State University Disclaimer