Advanced Computing, Mathematics and Data
Research Highlights

June 2015

A Collection of Quality HPC Research at IEEE Cluster 2015

Scientists from PNNL’s Advanced Computing, Mathematics, and Data Division, along with their collaborators, will put their expertise involving cluster computing on display as they showcase new tools and solutions for managing, monitoring, and scaling high-performance computing clusters during this year’s Institute of Electrical and Electronics Engineers Cluster 2015 conference in Chicago. Their collective works, including three accepted full papers and one short paper, will be showcased during the conference’s technical program.

New Additions to the Toolkit

In their work, PNNL’s High Performance Computing and Data Sciences groups with collaborators from Washington State University examined extreme-scale machine learning and data mining algorithms and how they can scale to large supercomputers. The results of their work will be featured in two papers at IEEE Cluster 2015: “Large Scale Frequent Pattern Mining using MPI One-Sided Model” and “Fast and Accurate Support Vector Machines on Large Scale Systems.” PNNL HPC scientist Abhinav Vishnu is the lead author of both papers.

Khushbu Agarwal and Abhinav Vishnu will share their work involving algorithms that manage communication complexities in large-scale computing.

In “Large Scale Frequent Pattern Mining using MPI One-Sided Model,” Vishnu and PNNL co-authors Khushbu Agarwal, Darren Kerbyson, and Adolfy Hoisie tackle communication complexity and load balancing using frequent pattern data mining, which involves finding frequently and jointly occurring attributes in data sets. Their resulting Library for Work Stealing, or LibWS, provides locality efficient and highly scalable work stealing approaches for load balancing on a variety of data distributions. Experimental evaluation using 4,096 processes on an InfiniBand cluster demonstrated excellent efficiency for several work distributions.

Meanwhile, in “Fast and Accurate Support Vector Machines on Large Scale Systems,” Vishnu, Kerbyson, and Hoisie with Jeyanthi Narasimhan and Lawrence Holder from WSU describe their design for a scalable support vector machine (SVM) algorithm that adaptively eliminates non-contributing data samples on distributed memory systems. SVMs are commonly employed for modeling, classification, and clustering because of their excellent theoretical foundation and accuracy.

“In the paper, we describe how we implemented the SVM algorithm, evaluating it using 10 different data sets on up to 4,096 cores,” Vishnu explained. “Our SVM algorithm managed to train two large data sets with significant speedups. The Offending URL data set with 2.3 million samples took eight minutes to complete the training, while using the typical standard, libsvm, it took 39 hours. For the UCI HIGGS Boson data set using 2.6 million samples, our SVM algorithm completed the training in two hours. With another algorithm, it took more than three.”

A ‘Taskmaster’ for Exascale Computing

The other full paper, “On the Application Task Granularity and the Interplay with the Scheduling Overhead in Many-core Shared Memory Systems,” co-authored by Dana Akhmetova, a Ph.D. intern, along with scientists Gokcen Kestor and Roberto Gioiosa all from PNNL’s HPC group, and Stefano Markidis from Sweden’s KTH Royal Institute of Technology, tackles issues related to task-based programming models, considered one of the most promising programming model approaches for exascale supercomputers.

Dana Akhmetova, Gokcen Kestor, and Roberto Gioiosa will present a systematic methodology to study the interplay between task granularity and scheduler overhead at IEEE Cluster 2015. Enlarge Image.

Their work examined how the goal in employing task-based programming models to program exascale applications is to condense the application into many smaller tasks and use overprovisioning, or reducing storage space, to improve the system’s reliability and performance.

“An overriding challenge faced by computing systems, especially as they advance toward extreme scales, involves maximizing their efficiency,” Kestor explained. “The granularity, or scale, of tasks directly affects system utilization as smaller tasks incur large scheduling overheads, while larger ones may induce system imbalance and underutilization on larger computing systems. We propose a systematic method to examine the interplay between task granularity and scheduler overhead, which can determine the optimal task granularity of an application for a given scheduler to offer the most reliable performance.”

Scaling RDF Database Performance

Accepted as a short paper, “High-performance, Distributed Dictionary Encoding of RDF Datasets” builds on ongoing work with the PNNL-developed Graph Engine for Multithreaded Systems, or GEMS, a multilayer software framework for querying high-volume graph databases. This time, PNNL scientists, including Alessandro Morari, David Haglin, Antonino Tumeo, and Vito Giovanni Castellana, implemented a novel, distributed Resource Description Framework (RDF) dictionary-encoding technique to improve overall database performance. RDF is a format for publishing/integrating data that has seen significant uptake in many communities, including open government, biomedical research, environmental sciences, humanities, social networks, geography, tourism, healthcare, and major search engines for the World Wide Web. Depending on the size of data sets, merely loading RDF data into the appropriate data structures for querying can take hours—if not days.

This HPC team with Alessandro Morari, David Haglin, Vito Giovanni Castellana, and Antonino Tumeo (clockwise from top left) are redefining how RDF terms are applied in databases for better performance.

The loading procedure includes a phase, named “dictionary encoding,” that assigns unique integer identifiers to long byte sequences, such as character strings, to decrease space consumption and improve overall querying performance. The new dictionary encoder presented in the paper scales significantly better and achieves higher performance than all other current state-of-the-art techniques. Providing an efficient and fast RDF loading phase is critical for obtaining a faster RDF database, especially for data sets that are periodically and dynamically updated.

“We compared our dictionary-encoding approach with two others notable implementations for high-performance systems, Message Passing Interface and MapReduce,” Morari, the paper’s primary author, explained. “Our approach proved to be between nine and 397 times faster than MapReduce and up to 36 times faster than MPI.”

A Good Team

PNNL’s HPC group continues to build on a positive track record for acceptance at major computing conferences, punctuated by PNNL’s commitment to foster opportunities for post-doctoral researchers to grow in their fields by working with more senior scientists. The group also has provided significant leadership for IEEE Cluster 2015 with Tumeo, a senior scientist, serving as the conference’s Technical Program Proceedings Chair, while Kerbyson, HPC’s associate division director, is a member of the Architectures Technical Program Committee.

“It is great to see such a strong presence this year,” Kerbyson added. “Out of 157 submissions to the conference, approximately 38 were accepted as full papers and a further 28 as short papers. Thus, PNNL’s HPC group has four of the 68 total acceptances, over six percent of the total.”

This year, IEEE Cluster 2015 will focus on cluster system design, management, hardware and software, and applications as they relate to exascale computing. The conference is being held September 8-11, 2015 in Chicago.

References:

• Akhmetova D, G Kestor, R Gioiosa, and S Markidis. 2015. “On the application task granularity and the interplay with the scheduling overhead in many-core shared memory systems.”
• Morari A, J Weaver, O Villa, D Haglin, A Tumeo, VG Castellana, and J Feo. 2015. “High-performance, Distributed Dictionary Encoding of RDF Datasets.”
• Vishnu A, K Agarwal, D Kerbyson, and A Hoisie. 2015. “Large Scale Frequent Pattern Mining using MPI One-Sided Model.”
• Vishnu A, J Narasimhan, L Holder, D Kerbyson, and A Hoisie. 2015. “Fast and Accurate Support Vector Machines on Large Scale Systems.”
  
  All in IEEE Cluster 2015. September 8-11, 2015, Chicago, Illinois. Institute of Electrical and Electronics Engineers, Piscataway, New Jersey.