Doe Science news source
The DOE Science News Source is a Newswise initiative to promote research news from the Office of Science of the DOE to the public and news media.
  • 2017-11-20 14:05:06
  • Article ID: 685518

GraphBLAS: Building Blocks For High Performance Graph Analytics

Berkeley Lab Researchers Contribute to GraphBLAS and Will Leverage it for Exascale Applications

  • Left to Right: Aydín Buluç (Berkeley Lab), Tim Mattson (Intel) and Jeremy Kepner (MIT).

Many of us thought linear algebra and graph structures were concepts we’d never again have to deal with after high school. However, these concepts underpin a variety of transactions, from Internet searches to cryptography, artificial intelligence and even operation of the power grid. They are also vital to many computational science and parallel computing applications. 

Now after nearly five years of collaboration between researchers in academia, industry and national research laboratories—including Aydın Buluç, a scientist in Lawrence Berkeley National Laboratory’s (Berkeley Lab’s) Computational Research Division (CRD)—GraphBLAS, a collection of standardized building blocks for graph algorithms in the language of linear algebra, is publicly available.

“When people talk about artificial intelligence, big data and data analytics, significant pieces of those come down to graph structures, which is a way of representing relationships between items,” says Tim Mattson, an Intel Senior Principal Engineer and a member of the GraphBLAS collaboration.

In the era of big data, Mattson notes that there is an increasing interest in finding patterns and connections in this information by building graphs and exploring their properties.

“This is a newish application area for scalable supercomputing. Graph problems are fairly straightforward to write down mathematically; however, getting them to work on petabytes of data, on a highly distributed system and in a reasonable amount of time, is actually very difficult,” he adds. “But if we can view graphs as linear algebra problems—which have been central to science and engineering applications in high performance computing for decades—then we can immediately apply everything that we’ve learned from parallel supercomputing over the last 35 years to graphs.” 

This is where Buluç’s experience proved to be extremely useful. Buluç began applying linear algebra to high performance graph analysis nearly a decade ago when he was a graduate student at the University of California Santa Barbra (UCSB). For his Ph.D. thesis, he created Combinational BLAS, an extensible distributed-memory parallel graph library offering a small but powerful set of linear algebra primitives specifically targeting graph analytics. This library later partly inspired the bigger GraphBLAS effort.  Another CRD Scientist, Ariful Azad, is a major contributor to the Combinatorial BLAS library and graph applications that use Combinatorial BLAS for scalability.

After earning his doctorate, Buluç continued this work at Berkeley Lab as a Luis Alvarez fellow and then as a research scientist. Along the way he also began collaborating with Jeremy Kepner, a Lincoln Laboratory Fellow at the Massachusetts Institute of Technology (MIT). Mattson notes that Buluç and Kepner were driving forces in the modern resurgence to get the community to think about graphs as linear algebra. He connected with both researchers via Buluç’s thesis advisor, UCSB Professor John Gilbert. 

“Aydin Buluç was a leader in demonstrating highly scalable implementations of matrix based graph algorithms, his work inspired others to try similar approaches,” says Kepner. “Tim Mattson then championed the idea that a GraphBLAS standard would allow hardware people and software people to work together and magnify our collective efforts.”

According to Mattson, the impetus to create a standard BLAS (Basic Linear Algebra Subprograms) for graph analytics came in 2012 when Intel launched a Science and Technology Center for Big Data at MIT to produce new data management systems and compute architectures for Big Data. As one of the center’s principal investigators, Mattson began building a team of researchers from academic and research institutions across the country with experience in high performance graph analysis, including Buluç, Gilbert and Kepner.

Over the next several years, the collaboration worked to define the mathematical concepts that would go into GraphBLAS. Because this software library was going to be publicly available, it couldn’t be overwhelming for users. So the team aimed to identify the smallest number of linear algebra functions to get the job done. Once the team agreed on the mathematical concepts, a subset of the researchers spent a couple of more years to bind GraphBLAS to the C programming language.

“GraphBLAS is an elegantly small number of functions that are feasible to implement in hardware, as we have demonstrated in the Lincoln Laboratory Graph Processor,” says Kepner. “It allows us to explore graphs with powerful mathematical properties such as associativity, commutativity and distributivity.  More recently, GraphBLAS has begun to be of interest to people beyond the graph community, including machine learning, databases, and simulations.”

Thanks to the efforts of Texas A&M Professor Timothy Davis, the GraphBLAS will soon be in many major Linux distributions and in many of the most popular mathematical programming environments in the world. Additionally, hardware manufacturers are starting to build computers specifically designed to accelerate these operations. Kepner notes that the confluence of these efforts will allow millions to enjoy the benefits of GraphBLAS. 

As a member of the ExaGraph: Combinatorial Methods for Enabling Exascale Application Co-Design Center, which is a Department of Energy Exascale Computing Project (ECP), Buluç and Azad plan to use GraphBLAS to develop graph and combinatorial algorithms for exascale systems. 

“As science problems get bigger, more computing power will be necessary to address these challenges,” says Buluç. “These large-scale applications have many computational components that we call motifs; that’s the whole idea of co-design. Exascale applications are a patchwork of different motifs, and if we optimize all other motifs for exascale and ignore the graph and combinatorics motifs, we’ll hit a performance bottleneck. That’s why this work is so important.”

Basics of BLAS

Many people are familiar with programming languages—like Python, C, C++, Java, and thousands of others—that are used to create a variety of software and applications. These high-level languages make coding relatively easy for humans but make little sense to computer hardware, which only comprehends low-level binary language of ones and zeros. Low-level programs essentially allow the programmer to have more control over how the computer hardware will perform, which means the developer will be able to ensure optimal software performance on a particular machine. 

It turns out that only a small number of low-level routines are required to perform most common linear algebra computing operations. So in 1979, researchers at NASA’s Jet Propulsion Laboratory, Sandia National Laboratories and the University of Texas at Austin publicly released Basic Linear Algebra Subprograms (BLAS), a library of these low-level routines for performing linear algebra operations such as vector addition, scalar multiplication, dot products, linear combinations and matrix multiplication. 

“When BLAS entered the scene in the late 1970s and early 1980s, it was transformative,” says Mattson. “Instead of handcrafting linear algebra algorithms from scratch, I could build them off of these common building blocks. And if a vendor would optimize those common building blocks just for their hardware, I could gain the benefits of that optimization pretty much for free.”

In subsequent years, various research collaborations created a variety of BLAS libraries for different tasks. Realizing the benefits to users, vendors also worked with researchers to optimize these building blocks to run on their hardware. GraphBLAS is essentially a continuation of this BLAS heritage.

“My hope is that GraphBLAS will be just as remarkable for those doing high performance graph analytics,” adds Mattson.

In addition to Buluç, Gilbert, Kepner and Mattson, other members of the GraphBLAS steering committee include David Bader of Georgia Tech and Henning Meyerhenke Karlsruhe Institute of Technology.

The Department of Energy’s Office of Science partially funded the development of GraphBLAS through the Office of Advanced Scientific Computing Research’s Applied Math Early Career program. Buluç was also awarded a DOE Office of Science Early Career Research Program award in 2013.

Download GraphBLAS specification and reference implementations here: http://graphblas.org/ 

X
X
X
  • Filters

  • × Clear Filters

Chemists Demonstrate Sustainable Approach to Carbon Dioxide Capture From Air

Chemists at Oak Ridge National Laboratory have demonstrated a practical, energy-efficient method of capturing carbon dioxide directly from air. If deployed at large scale and coupled to geologic storage, the technique may bolster the portfolio of responses to global climate change.

Nucleation a boon to sustainable nanomanufacturing

Young-Shin Jun, professor of energy, environmental & chemical engineering in the School of Engineering & Applied Science, and Quingun Li, a former doctoral student in her lab, are the first to measure the activation energy and kinetic factors of calcium carbonate's nucleation, both key to predicting and controlling the process.

Breaking the Symmetry Between Fundamental Forces

Scientists improve our understanding of the relationship between fundamental forces by re-creating the earliest moments of the universe.

Greater Than the Sum of Its Parts

Argonne scientists and their collaborators have developed a new model that merges basic electrochemical theory with theories used in different contexts, such as the study of photoelectrochemistry and semiconductor physics, to describe phenomena that occur in any electrode.

A prize-winning measurement device could aid a wide range of industries

Companies dealing with liquids ranging from wastewater to molten metals could benefit from a prize-winning device developed by researchers at the U.S. Department of Energy's (DOE) Princeton Plasma Physics Laboratory (PPPL) and Princeton University.

After 150 years, a Breakthrough in Understanding the Conversion of CO2 to Electrofuels

Using surface-enhanced Raman spectroscopy, Columbia Engineers are first to observe how CO2 is activated at the electrode-electrolyte interface; their finding shifts the catalyst design from trial-and-error paradigm to a rational approach and could lead to alternative, cheaper, and safer renewable energy storage.

Water Plays Unexpected Role in Forming Minerals

Water molecules line up tiny particles to attach and form minerals; understanding how this happens impacts energy extraction and storage along with waste disposal.

X-Rays Uncover a Hidden Property That Leads to Failure in a Lithium-Ion Battery Material

X-ray experiments at the Department of Energy's SLAC National Accelerator Laboratory and Lawrence Berkeley National Laboratory have revealed that the pathways lithium ions take through a common battery material are more complex than previously thought.

Graphene helps protect photocathodes for physics experiments

Argonne researchers have used thin sheets of graphene to prevent photocathode materials from interacting with air, which increases their lifetimes. Photocathodes are used to convert light to electricity in accelerators and other physics experiments.

Heavy Particles Get Caught Up in the Flow

First direct measurement show how heavy particles containing a charm quark get caught up in the flow of early universe particle soup.


  • Filters

  • × Clear Filters

JCESR renewed for another five years

The U.S. Department of Energy (DOE) today announced its decision to renew the Joint Center for Energy Storage Research (JCESR), a DOE Energy Innovation Hub led by Argonne National Laboratory and focused on advancing battery science and technology.

Binghamton designated as NextFlex New York Node for flexible hybrid electronics initiative

NextFlex has designated Binghamton University to be the New York "Node" for its flexible hybrid electronics (FHE) initiative. As the NextFlex New York Node, Binghamton will design, develop and manufacture tools; process materials and products for flexible hybrid electronics; and attract, train and employ an advanced manufacturing workforce, building on the region's existing electronics manufacturing base.

First Particle Tracks Seen in Prototype for International Neutrino Experiment

The largest liquid-argon neutrino detector in the world has just recorded its first particle tracks, signaling the start of a new chapter in the story of the international Deep Underground Neutrino Experiment (DUNE). DUNE's scientific mission is dedicated to unlocking the mysteries of neutrinos, the most abundant (and most mysterious) matter particles in the universe.

Tais Gorkhover Wins LCLS Young Investigator Award for Pioneering Novel X-ray Imaging Methods

Tais Gorkhover, a principal investigator with the Stanford PULSE Institute, will receive the 2018 LCLS Young Investigator Award, granted to early-career scientists in recognition of exceptional research using the Linac Coherent Light Source (LCLS) X-ray free-electron laser at the Department of Energy's SLAC National Accelerator Laboratory.

ORNL, United Kingdom Lab Partner on Nuclear Energy Research

The United Kingdom's National Nuclear Laboratory and the U.S. Department of Energy's Oak Ridge National Laboratory have agreed to cooperate on a wide range of nuclear energy research and development efforts that leverage both organizations' unique expertise and capabilities.

Nat Fisch receives Fusion Power Associates' Distinguished Career Award

Feature describes lifetime career award for PPPL physicist and professor Nat Fisch.

Wells Fargo Innovation Incubator Expands Focus to Include the Food-Water-Energy Interconnection

The Wells Fargo Innovation Incubator (IN2), a technology incubator and platform funded by the Wells Fargo Foundation and administered by the National Renewable Energy Laboratory (NREL), is expanding its program to advance technologies that address the interconnection of food, water and energy.

Graham George receives Lytle Award for contributions to X-ray absorption spectroscopy

Graham Neil George, professor and Canada Research Chair in X-ray Absorption Spectroscopy (XAS) at the University of Saskatchewan, has been chosen to receive the 2018 Farrel W. Lytle Award for his outstanding contributions to synchrotron science at the Department of Energy's SLAC National Accelerator Laboratory.

UIC company develops hybrid air-conditioning system with help from DOE

NETenergy, a clean tech startup company based on technology developed at the University of Illinois at Chicago and licensed from UIC, will commercialize its unique hybrid, super-efficient air-conditioning system with funding from the U.S. Department of Energy.The $500,000 grant was awarded to NETenergy's partner, National Renewable Energy Laboratory, as part of the DOE's Technology Commercialization Fund.

STAR Team Receives Secretary's Achievement Award

The Brookhaven Lab scientists, engineers, and support staff who run the Solenoidal Tracker (STAR) experiment at the Lab's Relativistic Heavy Ion Collider (RHIC) received one of 17 Achievement Awards presented by Secretary of Energy Rick Perry at the Secretary's Honor Awards ceremony held in Washington, D.C. August 29.


  • Filters

  • × Clear Filters

Breaking the Symmetry Between Fundamental Forces

Scientists improve our understanding of the relationship between fundamental forces by re-creating the earliest moments of the universe.

Water Plays Unexpected Role in Forming Minerals

Water molecules line up tiny particles to attach and form minerals; understanding how this happens impacts energy extraction and storage along with waste disposal.

Heavy Particles Get Caught Up in the Flow

First direct measurement show how heavy particles containing a charm quark get caught up in the flow of early universe particle soup.

Seeing Between the Atoms

New detector enables electron microscope imaging at record-breaking resolution.

Scaling Up Single-Crystal Graphene

New method can make films of atomically thin carbon that are over a foot long.

Discovered: Optimal Magnetic Fields Suppress Instabilities in Tokamak Plasmas

U.S. and Korean scientists show how to find and use beneficial 3-D field perturbations to stabilize dangerous edge-localized modes in plasma.

New Electron Glasses Sharpen Our View of Atomic-Scale Features

A new approach to atom probe tomography promises more precise and accurate measurements vital to semiconductors used in computers, lasers, detectors, and more.

Getting an Up-Close, 3-D View of Gold Nanostars

Scientists can now measure 3-D structures of tiny particles with properties that hold promise for advanced sensors and diagnostics.

Small, Short-Lived Drops of Early Universe Matter

Particle flow patterns suggest even small-scale collisions create drops of early universe quark-gluon plasma.

Tuning Terahertz Beams with Nanoparticles

Scientists uncover a way to control terahertz radiation using tiny engineered particles in a magnetic field, potentially opening the doors for better medical and environmental sensors.


Spotlight

Thursday September 06, 2018, 01:05 PM

Writing Code for a More Skilled and Diverse STEM Workforce

Brookhaven National Laboratory

Tuesday September 04, 2018, 11:30 AM

New graduate student summer school launches at Princeton Plasma Physics Laboratory

Princeton Plasma Physics Laboratory

Friday August 31, 2018, 06:05 PM

The Gridlock State

California State University (CSU) Chancellor's Office

Friday August 31, 2018, 02:05 PM

Meet Jasmine Hatcher and Trishelle Copeland-Johnson

Brookhaven National Laboratory

Friday August 24, 2018, 11:05 AM

Argonne hosts Modeling, Experimentation and Validation Summer School

Argonne National Laboratory

Wednesday August 22, 2018, 01:05 PM

Students affected by Hurricane Maria bring their research to SLAC

SLAC National Accelerator Laboratory

Wednesday August 22, 2018, 10:05 AM

Brookhaven Lab Pays Tribute to 2018 Summer Interns

Brookhaven National Laboratory

Monday August 20, 2018, 12:05 PM

Changing How Buildings Are Made

Washington University in St. Louis

Thursday August 16, 2018, 12:05 PM

CSUMB Selected to Host Architecture at Zero Competition in 2019

California State University, Monterey Bay

Friday July 20, 2018, 03:00 PM

Department of Energy Invests $64 Million in Advanced Nuclear Technology

Rensselaer Polytechnic Institute (RPI)

Thursday July 19, 2018, 05:00 PM

Professor Miao Yu Named the Priti and Mukesh Chatter '82 Career Development Professor

Rensselaer Polytechnic Institute (RPI)

Tuesday July 03, 2018, 11:05 AM

2018 RHIC & AGS Annual Users' Meeting: 'Illuminating the QCD Landscape'

Brookhaven National Laboratory

Friday June 29, 2018, 06:05 PM

Argonne welcomes The Martian author Andy Weir

Argonne National Laboratory

Monday June 18, 2018, 09:55 AM

Creating STEM Knowledge and Innovations to Solve Global Issues Like Water, Food, and Energy

Illinois Mathematics and Science Academy (IMSA)

Friday June 15, 2018, 10:00 AM

Professor Emily Liu Receives $1.8 Million DoE Award for Solar Power Systems Research

Rensselaer Polytechnic Institute (RPI)

Thursday June 07, 2018, 03:05 PM

Celebrating 40 years of empowerment in science

Argonne National Laboratory

Monday May 07, 2018, 10:30 AM

Introducing Graduate Students Across the Globe to Photon Science

Brookhaven National Laboratory

Wednesday May 02, 2018, 04:05 PM

Students from Massachusetts and Washington Win DOE's 28th National Science Bowl(r)

Department of Energy, Office of Science

Thursday April 12, 2018, 07:05 PM

The Race for Young Scientific Minds

Argonne National Laboratory

Wednesday March 14, 2018, 02:05 PM

Q&A: Al Ashley Reflects on His Efforts to Diversify SLAC and Beyond

SLAC National Accelerator Laboratory

Thursday February 15, 2018, 12:05 PM

Insights on Innovation in Energy, Humanitarian Aid Highlight UVA Darden's Net Impact Week

University of Virginia Darden School of Business

Friday February 09, 2018, 11:05 AM

Ivy League Graduate, Writer and Activist with Dyslexia Visits CSUCI to Reframe the Concept of Learning Disabilities

California State University, Channel Islands

Wednesday January 17, 2018, 12:05 PM

Photographer Adam Nadel Selected as Fermilab's New Artist-in-Residence for 2018

Fermi National Accelerator Laboratory (Fermilab)

Wednesday January 17, 2018, 12:05 PM

Fermilab Computing Partners with Argonne, Local Schools for Hour of Code

Fermi National Accelerator Laboratory (Fermilab)

Wednesday December 20, 2017, 01:05 PM

Q&A: Sam Webb Teaches X-Ray Science from a Remote Classroom

SLAC National Accelerator Laboratory

Monday December 18, 2017, 01:05 PM

The Future of Today's Electric Power Systems

Rensselaer Polytechnic Institute (RPI)

Monday December 18, 2017, 12:05 PM

Supporting the Development of Offshore Wind Power Plants

Rensselaer Polytechnic Institute (RPI)

Tuesday October 03, 2017, 01:05 PM

Stairway to Science

Argonne National Laboratory

Thursday September 28, 2017, 12:05 PM

After-School Energy Rush

Argonne National Laboratory

Thursday September 28, 2017, 10:05 AM

Bringing Diversity Into Computational Science Through Student Outreach

Brookhaven National Laboratory

Thursday September 21, 2017, 03:05 PM

From Science to Finance: SLAC Summer Interns Forge New Paths in STEM

SLAC National Accelerator Laboratory

Thursday September 07, 2017, 02:05 PM

Students Discuss 'Cosmic Opportunities' at 45th Annual SLAC Summer Institute

SLAC National Accelerator Laboratory

Thursday August 31, 2017, 05:05 PM

Binghamton University Opens $70 Million Smart Energy Building

Binghamton University, State University of New York

Wednesday August 23, 2017, 05:05 PM

Widening Horizons for High Schoolers with Code

Argonne National Laboratory

Saturday May 20, 2017, 12:05 PM

Rensselaer Polytechnic Institute Graduates Urged to Embrace Change at 211th Commencement

Rensselaer Polytechnic Institute (RPI)

Monday May 15, 2017, 01:05 PM

ORNL, University of Tennessee Launch New Doctoral Program in Data Science

Oak Ridge National Laboratory

Friday April 07, 2017, 11:05 AM

Champions in Science: Profile of Jonathan Kirzner

Department of Energy, Office of Science

Wednesday April 05, 2017, 12:05 PM

High-Schooler Solves College-Level Security Puzzle From Argonne, Sparks Interest in Career

Argonne National Laboratory

Tuesday March 28, 2017, 12:05 PM

Champions in Science: Profile of Jenica Jacobi

Department of Energy, Office of Science

Friday March 24, 2017, 10:40 AM

Great Neck South High School Wins Regional Science Bowl at Brookhaven Lab

Brookhaven National Laboratory

Wednesday February 15, 2017, 04:05 PM

Middle Schoolers Test Their Knowledge at Science Bowl Competition

Argonne National Laboratory

Friday January 27, 2017, 04:00 PM

Haslam Visits ORNL to Highlight State's Role in Discovering Tennessine

Oak Ridge National Laboratory

Tuesday November 08, 2016, 12:05 PM

Internship Program Helps Foster Development of Future Nuclear Scientists

Oak Ridge National Laboratory

Friday May 13, 2016, 04:05 PM

More Than 12,000 Explore Jefferson Lab During April 30 Open House

Thomas Jefferson National Accelerator Facility

Monday April 25, 2016, 05:05 PM

Giving Back to National Science Bowl

Ames Laboratory





Showing results

0-4 Of 2215