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

Coupling Experiments to Theory to Build a Better Battery

A Berkeley Lab-led team of researchers has reported that a new lithium-sulfur battery component allows a doubling in capacity compared to a conventional lithium-sulfur battery, even after more than 100 charge cycles.

DRIFTing to Fast, Precise Data

Non-destructive technique identifies key variations in Alaskan soils, quickly providing insights into carbon levels.

A Shortcut to Modeling Sickle Cell Disease

Using Oak Ridge National Laboratory's Titan supercomputer, a team led by Brown University's George Karniadakis devised a multiscale model of sickle cell disease that captures what happens inside a red blood cell affected by the disease.

Remotely Predicting Leaf Age in Tropical Forests

New approach offers data across species, sites, and canopies, providing insights into carbon uptake by forests.

Conservation Mind Game

A new study led by Kathryn Caldwell, an assistant professor of psychology at Ithaca College, demonstrates that homeowners can be encouraged to make changes to their energy use with a simple education plan and some helpful tricks from the world of social psychology.

X-Rays Reveal 'Handedness' in Swirling Electric Vortices

Scientists used spiraling X-rays at Berkeley Lab to observe, for the first time, a property that gives left- or right-handedness to swirling electric patterns - dubbed polar vortices - in a layered material called a superlattice.

Breaking Bad Metals with Neutrons

By combining the latest developments in neutron scattering and theory, researchers are close to predicting phenomena like superconductivity and magnetism in strongly correlated electron systems. It is likely that the next advances in superconductivity and magnetism will come from such systems, but they might also be used in completely new ways such as quantum computing.

ORNL Researchers Use Titan to Accelerate Design, Training of Deep Learning Networks

For deep learning to be effective, existing neural networks to be modified, or novel networks designed and then "trained" so that they know precisely what to look for and can produce valid results. This is a time-consuming and difficult task, but one that a team of ORNL researchers recently demonstrated can be dramatically expedited with a capable computing system.

Dark Energy Survey Publicly Releases First Three Years of Data

At a special session held during the American Astronomical Society meeting in Washington, D.C., scientists on the Dark Energy Survey (DES) announced today the public release of their first three years of data. This first major release of data from the Survey includes information on about 400 million astronomical objects, including distant galaxies billions of light-years away as well as stars in our own galaxy.

Ingredients for Life Revealed in Meteorites That Fell to Earth

A detailed study of blue salt crystals found in two meteorites that crashed to Earth - which included X-ray experiments at Berkeley Lab - found that they contain both liquid water and a mix of complex organic compounds including hydrocarbons and amino acids.


  • Filters

  • × Clear Filters

Superconducting X-Ray Laser Takes Shape in Silicon Valley

An area known for high-tech gadgets and innovation will soon be home to an advanced superconducting X-ray laser that stretches 3 miles in length, built by a collaboration of national laboratories. On January 19, the first section of the machine's new accelerator arrived by truck at SLAC National Accelerator Laboratory in Menlo Park after a cross-country journey that began in Batavia, Illinois, at Fermi National Accelerator Laboratory.

Kelsey Stoerzinger Earns Young Investigator Lectureship

Kelsey Stoerzinger, Pauling Fellow at Pacific Northwest National Laboratory, is one of the 2018 Caltech Young Investigator Lecturers in Engineering and Applied Physics.

North Dakota State University Joins Two National Distributed Computing Groups

The NDSU Center for Computationally Assisted Science and Technology (CCAST) joins OSG (Open Science Grid) and XSEDE (Extreme Science and Engineering Discovery Environment).

DOE Announces Funding for New HPC4Manufacturing Industry Projects

The Department of Energy's Advanced Manufacturing Office (AMO) today announced the funding of $1.87 million for seven new industry projects under an ongoing initiative designed to utilize DOE's high-performance computing (HPC) resources and expertise to advance U.S. manufacturing and clean energy technologies.

DOE Announces First Awardees for New HPC4Materials for Severe Environments Program

The Department of Energy's Office of Fossil Energy (FE) today announced the funding of $450,000 for the first two private-public partnerships under a brand-new initiative aimed at discovering, designing and scaling up production of novel materials for severe environments.

Two Argonne Scientists Recognized for a Decade of Breakthroughs

Two scientists with the U.S. Department of Energy's (DOE) Argonne National Laboratory have been named to the Web of Science's Highly Cited List of 2017, ranking in the top 1 percent of their peers by citations and subject area. Materials Scientist Khalil Amine and Energy and Environmental Policy Scientist David Streets say they are thrilled to see their work -- and the laboratory -- recognized in such a way.

Argonne Welcomes Department of Energy Secretary Perry

U.S. Department of Energy Secretary Rick Perry visited Argonne National Laboratory yesterday, getting a first-hand view of the multifaceted and interdisciplinary research program laboratory of the Department.

Argonne names John Quintana Deputy Laboratory Director for Operations and COO

John Quintana has been named Deputy Laboratory Director for Operations and Chief Operations Officer (COO) of the U.S. Department of Energy's (DOE) Argonne National Laboratory.

Developing Next-Generation Sensing Technologies

Recently, the Advanced Research Projects Agency-Energy (ARPA-E) announced $20 million in funding for 15 projects that will develop a new class of sensor systems to enable significant energy savings via reduced demand for heating and cooling in residential and commercial buildings.

Supporting the Development of Offshore Wind Power Plants

Offshore wind is becoming a reality in the United States, especially in the northeast states. To support this development, the Center for Future Energy System (CFES) at Rensselaer Polytechnic Institute will present a webinar titled "Turbine and Transmission System Technologies for Offshore Wind (OSW) Power Plants." The program will be held on Wednesday, Dec. 20, from 2 to 4 p.m. Advance registration is required.


  • Filters

  • × Clear Filters

Exploring Past, Present, and Future Water Availability Regionally, Globally

New open-source software simulates river and runoff resources.

Arctic Photosynthetic Capacity and Carbon Dioxide Assimilation Underestimated by Terrestrial Biosphere Models

New measurements offer data vital to projecting plant response to environmental changes.

DRIFTing to Fast, Precise Data

Non-destructive technique identifies key variations in Alaskan soils, quickly providing insights into carbon levels.

Superconducting Tokamaks Are Standing Tall

Plasma physicists significantly improve the vertical stability of a Korean fusion device.

Graphene Flexes Its Muscle

Crumpling reduces rigidity in an otherwise stiff material, making it less prone to catastrophic failure.

Remotely Predicting Leaf Age in Tropical Forests

New approach offers data across species, sites, and canopies, providing insights into carbon uptake by forests.

What's the Noise Eating Quantum Bits?

The magnetic noise caused by adsorbed oxygen molecules is "eating at" the phase stability of quantum bits, mitigating the noise is vital for future quantum computers.

Rewritable Wires Could Mean No More Obsolete Circuitry

An electric field switches the conductivity on and off in atomic-scale channels, which could allow for upgrades at will.

Filtering Water Better than Nature

Water passes through human-made straws faster than the "gold standard" protein, allowing us to filter seawater.

Machine Learning Provides a Bridge to the Texture of the Quantum World

Machine learning and neural networks are the foundation of artificial intelligence and image recognition, but now they offer a bridge to see and recognize exotic insulating phases in quantum materials.


Spotlight

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

Friday March 25, 2016, 12:05 PM

NMSU Undergrad Tackles 3D Particle Scattering Animations After Receiving JSA Research Assistantship

Thomas Jefferson National Accelerator Facility

Tuesday February 02, 2016, 10:05 AM

Shannon Greco: A Self-Described "STEM Education Zealot"

Princeton Plasma Physics Laboratory

Monday November 16, 2015, 04:05 PM

Rare Earths for Life: An 85th Birthday Visit with Mr. Rare Earth

Ames Laboratory

Tuesday October 20, 2015, 01:05 PM

Meet Robert Palomino: 'Give Everything a Shot!'

Brookhaven National Laboratory

Tuesday April 22, 2014, 11:30 AM

University of Utah Makes Solar Accessible

University of Utah

Wednesday March 06, 2013, 03:40 PM

Student Innovator at Rensselaer Polytechnic Institute Seeks Brighter, Smarter, and More Efficient LEDs

Rensselaer Polytechnic Institute (RPI)

Friday November 16, 2012, 10:00 AM

Texas Tech Energy Commerce Students, Community Light up Tent City

Texas Tech University

Wednesday November 23, 2011, 10:45 AM

Don't Get 'Frosted' Over Heating Your Home This Winter

Temple University

Wednesday July 06, 2011, 06:00 PM

New Research Center To Tackle Critical Challenges Related to Aircraft Design, Wind Energy, Smart Buildings

Rensselaer Polytechnic Institute (RPI)

Friday April 22, 2011, 09:00 AM

First Polymer Solar-Thermal Device Heats Home, Saves Money

Wake Forest University

Friday April 15, 2011, 12:25 PM

Like Superman, American University Will Get Its Energy from the Sun

American University

Thursday February 10, 2011, 05:00 PM

ARRA Grant to Help Fund Seminary Building Green Roof

University of Chicago

Tuesday December 07, 2010, 05:00 PM

UC San Diego Installing 2.8 Megawatt Fuel Cell to Anchor Energy Innovation Park

University of California San Diego

Monday November 01, 2010, 12:50 PM

Rensselaer Smart Lighting Engineering Research Center Announces First Deployment of New Technology on Campus

Rensselaer Polytechnic Institute (RPI)

Friday September 10, 2010, 12:40 PM

Ithaca College Will Host Regional Clean Energy Summit

Ithaca College

Tuesday July 27, 2010, 10:30 AM

Texas Governor Announces $8.4 Million Award to Create Renewable Energy Institute

Texas Tech University

Friday May 07, 2010, 04:20 PM

Creighton University to Offer New Alternative Energy Program

Creighton University

Wednesday May 05, 2010, 09:30 AM

National Engineering Program Seeks Subject Matter Experts in Energy

JETS Junior Engineering Technical Society

Wednesday April 21, 2010, 12:30 PM

Students Using Solar Power To Create Sustainable Solutions for Haiti, Peru

Rensselaer Polytechnic Institute (RPI)

Wednesday March 03, 2010, 07:00 PM

Helping Hydrogen: Student Inventor Tackles Challenge of Hydrogen Storage

Rensselaer Polytechnic Institute (RPI)

Thursday February 04, 2010, 02:00 PM

Turning Exercise into Electricity

Furman University

Thursday November 12, 2009, 12:45 PM

Campus Leaders Showing the Way to a Sustainable, Clean Energy Future

National Wildlife Federation (NWF)

Tuesday November 03, 2009, 04:20 PM

Furman University Receives $2.5 Million DOE Grant for Geothermal Project

Furman University

Thursday September 17, 2009, 02:45 PM

Could Sorghum Become a Significant Alternative Fuel Source?

Salisbury University

Wednesday September 16, 2009, 11:15 AM

Students Navigating the Hudson River With Hydrogen Fuel Cells

Rensselaer Polytechnic Institute (RPI)





Showing results

0-4 Of 2215