{"622759":{"#nid":"622759","#data":{"type":"news","title":"New Methods of Reordering Sparse Tensors Show Measurable Increases in Speed","body":[{"value":"\u003Cp\u003EA team of researchers, which includes several\u0026nbsp;\u003Ca href=\u0022https:\/\/www.cse.gatech.edu\/\u0022\u003ESchool of Computational Science and Engineering\u0026nbsp;\u003C\/a\u003E(CSE) faculty, has created two tensor reordering methods, BFS-MCS and Lexi-Order, that are proven to be more effective for storing and operating efficiently with sparse tensors than current state-of-the-art approaches.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOn modern multicore central processing units, the reordering algorithm Lexi-Order obtains up to 4.14 times speedup on sequential HiCOO-MTTKRP \u0026ndash; a sparse tensor format with one of the most computationally expensive kernels in sparse tensor computations \u0026ndash; and 11.88 times speedup on its parallel counterpart.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe full findings from the\u0026nbsp;\u003Ca href=\u0022http:\/\/fruitfly1026.github.io\/static\/files\/ics19-li.pdf\u0022\u003Epaper\u003C\/a\u003E\u0026nbsp;introducing these methods will be presented this Thursday, June 27, at the\u0026nbsp;\u003Ca href=\u0022https:\/\/ics19.eecis.udel.edu\/\u0022\u003EInternational Conference on Supercomputing\u003C\/a\u003E\u0026nbsp;(ICS).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFor those new to tensors, a tensor is an algebraic object related to space that provides a natural and concise mathematical framework for formulating and solving problems in computational science. These objects are represented in the form of cubes, with the X and Y axis depths ranging according to the size of data entries they can hold.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETensors are fed information in the form of numeric data from a variety of applications but, oftentimes, these entries mainly consist of zeroes. In these instances, the tensors are considered sparse and do not need to be stored or explicitly computed on.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe primary investigator of this research,\u0026nbsp;\u003Cstrong\u003EJiajia Li\u003C\/strong\u003E, is a staff scientist at the\u0026nbsp;\u003Ca href=\u0022http:\/\/hpc.pnl.gov\/\u0022\u003EHigh Performance Computing (HPC) group\u003C\/a\u003E\u0026nbsp;of Pacific Northwest National Laboratory (PNNL) and recent doctoral graduate of CSE. Li has led research on sparse tensors in the past, including\u0026nbsp;\u003Ca href=\u0022https:\/\/sc18.supercomputing.org\/breaking-news-sc18-papers-program-and-awards-finalists-posted\/\u0022\u003ESupercomputing 2018 Best Student Paper Award\u003C\/a\u003E\u0026nbsp;winning work,\u0026nbsp;\u003Ca href=\u0022http:\/\/fruitfly1026.github.io\/static\/files\/sc18-li.pdf\u0022\u003EHiCOO\u003C\/a\u003E, which this new work builds upon.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u003Ca href=\u0022https:\/\/www.cse.gatech.edu\/news\/615074\/hicoo-takes-home-best-student-paper-title-supercomputing-2018-creating-new-storage\u0022\u003E[See Related: HiCOO Takes Home Best Student Paper Title of Supercomputing 2018 by Creating a New Storage Format]\u003C\/a\u003E\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;A sparse tensor is often a natural way to represent a multifactor or multi-relational dataset, and has found numerous applications in data analysis and mining for healthcare, natural language processing, machine learning, and social network analytics, among many others,\u0026rdquo; she said.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;This paper formalizes the problem of reordering a sparse tensor to improve the spatial and temporal locality of operations within it, and proposes two reordering algorithms for this problem.\u0026rdquo;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAccording to Li, there are a variety of data structures and techniques for storing and operating efficiently with sparse tensors. One technique is to reorder the tensor, which means relabeling the indices \u0026ndash; and, therefore, reorganizing the nonzero structure of the tensor.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOne form of reordering explored in prior work is to sort the input tensor which can improve locality, but simultaneously aggravates load balance.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EShe said, \u0026ldquo;We observe that reordering increases imbalance by as much as 6.7 times in practice. In this paper, we propose improvements to the data structure and corresponding algorithms that address this problem. A new partition-based superblock scheduling is also proposed for the HiCOO format to improve load balance.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe team of investigators for this paper include Li, PNNL Team Lead Scientist\u0026nbsp;\u003Cstrong\u003EKevin Barker,\u0026nbsp;\u003C\/strong\u003E\u003Ca href=\u0022http:\/\/www.cnrs.fr\/en\/cnrs\u0022\u003EFrench National Center for Scientific Research\u003C\/a\u003E\u0026nbsp;Scientist\u0026nbsp;\u003Cstrong\u003EBora Ucar,\u0026nbsp;\u003C\/strong\u003Eand CSE Professors\u0026nbsp;\u003Cstrong\u003EUmit Catalyurek\u003C\/strong\u003E,\u0026nbsp;\u003Cstrong\u003EJimeng Sun\u003C\/strong\u003E, and\u0026nbsp;\u003Cstrong\u003ERich Vuduc\u003C\/strong\u003E.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe code is released as part of Parallel Tensor Infrastructure (ParTI!) and can be found\u0026nbsp;\u003Ca href=\u0022https:\/\/github.com\/hpcgarage\/ParTI\u0022\u003Ehere\u003C\/a\u003E.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"CSE faculty and alumni creating new methods for increasing speed of operations within sparse tensors."}],"uid":"34540","created_gmt":"2019-06-25 17:31:36","changed_gmt":"2019-08-23 20:29:47","author":"Kristen Perez","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2019-06-25T00:00:00-04:00","iso_date":"2019-06-25T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"622758":{"id":"622758","type":"image","title":"Sparse Tensor Reordering - ICS 2019","body":null,"created":"1561483552","gmt_created":"2019-06-25 17:25:52","changed":"1561483552","gmt_changed":"2019-06-25 17:25:52","alt":"Comparison of HiCOO representations before and after Lexi-Order.","file":{"fid":"237173","name":"Screen Shot 2019-06-25 at 1.25.03 PM.png","image_path":"\/sites\/default\/files\/images\/Screen%20Shot%202019-06-25%20at%201.25.03%20PM.png","image_full_path":"http:\/\/tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/Screen%20Shot%202019-06-25%20at%201.25.03%20PM.png","mime":"image\/png","size":84005,"path_740":"http:\/\/tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/Screen%20Shot%202019-06-25%20at%201.25.03%20PM.png?itok=K91h1tcN"}}},"media_ids":["622758"],"groups":[{"id":"50877","name":"School of Computational Science and Engineering"},{"id":"47223","name":"College of Computing"},{"id":"431631","name":"OMS"},{"id":"624060","name":"Center for High Performance Computing (CHiPC)"}],"categories":[],"keywords":[{"id":"167322","name":"supercomputing"},{"id":"3427","name":"High performance computing"},{"id":"181217","name":"cse-hpc"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EKristen Perez\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECommunications Officer\u003C\/p\u003E\r\n","format":"limited_html"}],"email":["kristen.perez@cc.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}