George Karypis and collaborator receive SC21 test of time award for 1998 graph partitioning paper

{"value":"\n\nGeorge Karypis (top), an Amazon senior principal scientist, and Vipin Kumar, a University of Minnesota professor, have been awarded the SC21 Test of Time Award for a 1998 paper they coauthored which presented algorithms that have subsequently been applied in diverse application domains, from electronic design automation tools for field programmable gate arrays, to determining state-level electoral districts in the United States.\n\nGeorge Karypis, an Amazon senior principal scientist within the Amazon Web Services organization, has been awarded ++[the SC21 Test of Time Award](https://sc21.supercomputing.org/program/awards/sc-test-of-time-award/)++ for a 1998 paper he coauthored which presented algorithms that have subsequently been applied in diverse application domains, from multi-physics scientific simulations and VLSI computer-aided design systems, to database and geographic information systems.\n\nThe paper, “++[Multilevel Algorithms for Multi-constraint Graph Partitioning](http://glaros.dtc.umn.edu/gkhome/node/90)++”, introduced multi-constraint graph partitioning algorithms that address the need to load balance multi-phase scientific simulations across high-performance computing system nodes to enable efficient parallel execution of computations when each mesh element requires different computation resources (e.g., CPU cycles, memory and network bandwidth). Karypis coauthored the paper with fellow University of Minnesota professor ++[Vipin Kumar](https://www-users.cse.umn.edu/~kumar001/)++.\n\n“The paper generalized the standard min-cut balanced graph partitioning problem to one that seeks a min-cut partitioning that satisfies multiple balancing constraints, analyzes the feasibility of the partitions, and presents efficient and effective multilevel algorithms for computing them,” Karypis explained.\n\nCongratulations to George Karypis and Vipin Kumar, as their SC98 paper “Multilevel Algorithms for Multi-Constraint Graph Partitioning\" has won the ++[#SC21](https://twitter.com/hashtag/SC21?src=hash&ref_src=twsrc%5Etfw)++ Test of Time Award! ++[https://t.co/9tL6HfIUkC](https://t.co/9tL6HfIUkC)++ ++[pic.twitter.com/MagkiUSwSM](https://t.co/MagkiUSwSM)++\n\n— SC21 (@Supercomputing) ++[October 15, 2021](https://twitter.com/Supercomputing/status/1449019796100636674?ref_src=twsrc%5Etfw)++\n\nThe need to compute graph partitions that simultaneously satisfy multiple constraints arise in many domains, and the algorithms introduced in the paper have subsequently been used for developing electronic design automation (EDA) tools for ++[field programmable gate arrays](https://en.wikipedia.org/wiki/Field-programmable_gate_array)++ (FPGA), determining electoral districts that address US states’ different requirements, partitioning the computational graphs of large deep-learning models, and computations performed during graph neural network training, among other applications. The algorithms also have been incorporated into the ++[Metis](http://glaros.dtc.umn.edu/gkhome/metis/metis/overview)++, ++[ParMetis](http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview)++ and ++[hMetis](http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview)++ graph and hypergraph partitioning software applications.\n\n#### **How graph partitioning algorithms work**\n\nIn parallel and distributed processing, sparse graphs are often used to model the computational tasks (via vertices) and their interactions (via edges). In these graphs, each vertex has a weight that corresponds to the amount of computation associated with it, and each edge has a weight that corresponds to the amount of data that needs to be exchanged.\n\nGraph partitioning algorithms are used to divide the graph into k parts (where k is usually the number of processors/systems) and assign the tasks corresponding to the vertices of each partition to a single processor or system for execution. For the computations to be performed efficiently, the sum of the weights of the tasks of each partition must be nearly identical across the different partitions, leading to a work assignment that is load balanced.\n\nAt the same time, to reduce communication costs, the partitioning needs to minimize the number of edges that cross partition boundaries. The class of graph partitioning algorithms that meet these requirements are typically called bounded-capacity min-cut graph partitioning algorithms, where the term “bounded capacity” refers to the balance constraint and the term “min-cut” relates to the objective of minimizing the sum of the weights of the edges that cross partition boundaries.\n\n#### **Ideally, we want to compute a partitioning that simultaneously balances the computational and memory requirements across the different partitions**\n\nGeorge Karypis\n\nIn many applications, the bounded capacity min-cut formulation is not sufficient to meet requirements. For example, a computation’s tasks may require different amounts of computation and memory. If a standard bounded-capacity algorithm is used to balance the computations, it could lead to a task assignment that is severely unbalanced in terms of memory requirements. If the bounded-capacity algorithm is used to compute a partitioning that balances the memory requirements, it could lead to a computations load imbalance.\n\nIn either case, Karypis explains, the overall performance of the system will be negatively impacted. “Ideally, we want to compute a partitioning that simultaneously balances the computational and memory requirements across the different partitions,” he said.\n\nTo address these challenges, the paper’s coauthors introduced a model that allows an application to express its multiple balancing requirements, and developed multilevel graph partitioning algorithms that produce partitions that address the constraints, or come close.\n\n“Since our formulation and algorithms can simultaneously satisfy multiple balancing criteria, I refer to them as multi-constraint partitioning algorithms,” Karypis explained.\n\n#### **Other honors**\n\nThe SC21 Test of Time Award is one of several Karypis has earned within the past year.\n\nIn May, he received the ++[Distinguished Contributions Award](https://cse.umn.edu/cs/news/karypis-wins-pakdd-distinguished-contributions-award)++ during the 2021 Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD). Karypis, who also is a professor within the University of Minnesota’s computer science and engineering department, was honored for his outstanding contributions to the field of knowledge discovery and data mining, as well as for his long-standing participation in PAKDD.\n\nIn November 2020, Karypis was awarded the ++[10-Year-Highest Impact Award](https://www.amazon.science/latest-news/amazon-scholar-george-karypis-receives-icdm-10-year-highest-impact-award)++ at the 2020 IEEE Conference on Data Mining (ICDM).\n\nMore recently, Karypis presented a talk, “++[Deep Graph Library: Deep Graph learning at scale](https://www.amazon.science/latest-news/on-demand-the-2021-aws-machine-learning-summit)++”, at the AWS Machine Learning Summit held earlier this year. Prior to his presentation, Amazon Science interviewed Karypis about ++[his forthcoming talk](https://www.amazon.science/latest-news/3-questions-with-george-karypis-making-learning-from-data-embedded-in-graphs-easy-and-scalable)++ on deep graph neural networks.\n\nABOUT THE AUTHOR\n\n#### **Staff writer**\n\n\n\n\n\n\n\n\n\n\n\n","render":"<p><img src=\"https://dev-media.amazoncloud.cn/1721d23c16294911b3c022c4e095c25c_image.png\" alt=\"image.png\" /></p>\n<p>George Karypis (top), an Amazon senior principal scientist, and Vipin Kumar, a University of Minnesota professor, have been awarded the SC21 Test of Time Award for a 1998 paper they coauthored which presented algorithms that have subsequently been applied in diverse application domains, from electronic design automation tools for field programmable gate arrays, to determining state-level electoral districts in the United States.</p>\n<p>George Karypis, an Amazon senior principal scientist within the Amazon Web Services organization, has been awarded <ins><a href=\"https://sc21.supercomputing.org/program/awards/sc-test-of-time-award/\" target=\"_blank\">the SC21 Test of Time Award</a></ins> for a 1998 paper he coauthored which presented algorithms that have subsequently been applied in diverse application domains, from multi-physics scientific simulations and VLSI computer-aided design systems, to database and geographic information systems.</p>\n<p>The paper, “<ins><a href=\"http://glaros.dtc.umn.edu/gkhome/node/90\" target=\"_blank\">Multilevel Algorithms for Multi-constraint Graph Partitioning</a></ins>”, introduced multi-constraint graph partitioning algorithms that address the need to load balance multi-phase scientific simulations across high-performance computing system nodes to enable efficient parallel execution of computations when each mesh element requires different computation resources (e.g., CPU cycles, memory and network bandwidth). Karypis coauthored the paper with fellow University of Minnesota professor <ins><a href=\"https://www-users.cse.umn.edu/~kumar001/\" target=\"_blank\">Vipin Kumar</a></ins>.</p>\n<p>“The paper generalized the standard min-cut balanced graph partitioning problem to one that seeks a min-cut partitioning that satisfies multiple balancing constraints, analyzes the feasibility of the partitions, and presents efficient and effective multilevel algorithms for computing them,” Karypis explained.</p>\n<p>Congratulations to George Karypis and Vipin Kumar, as their SC98 paper “Multilevel Algorithms for Multi-Constraint Graph Partitioning&quot; has won the <ins><a href=\"https://twitter.com/hashtag/SC21?src=hash&amp;ref_src=twsrc%5Etfw\" target=\"_blank\">#SC21</a></ins> Test of Time Award! <ins><a href=\"https://t.co/9tL6HfIUkC\" target=\"_blank\">https://t.co/9tL6HfIUkC</a></ins> <ins><a href=\"https://t.co/MagkiUSwSM\" target=\"_blank\">pic.twitter.com/MagkiUSwSM</a></ins></p>\n<p>— SC21 (@Supercomputing) <ins><a href=\"https://twitter.com/Supercomputing/status/1449019796100636674?ref_src=twsrc%5Etfw\" target=\"_blank\">October 15, 2021</a></ins></p>\n<p>The need to compute graph partitions that simultaneously satisfy multiple constraints arise in many domains, and the algorithms introduced in the paper have subsequently been used for developing electronic design automation (EDA) tools for <ins><a href=\"https://en.wikipedia.org/wiki/Field-programmable_gate_array\" target=\"_blank\">field programmable gate arrays</a></ins> (FPGA), determining electoral districts that address US states’ different requirements, partitioning the computational graphs of large deep-learning models, and computations performed during graph neural network training, among other applications. The algorithms also have been incorporated into the <ins><a href=\"http://glaros.dtc.umn.edu/gkhome/metis/metis/overview\" target=\"_blank\">Metis</a></ins>, <ins><a href=\"http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview\" target=\"_blank\">ParMetis</a></ins> and <ins><a href=\"http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview\" target=\"_blank\">hMetis</a></ins> graph and hypergraph partitioning software applications.</p>\n<h4><a id=\"How_graph_partitioning_algorithms_work_16\"></a><strong>How graph partitioning algorithms work</strong></h4>\n<p>In parallel and distributed processing, sparse graphs are often used to model the computational tasks (via vertices) and their interactions (via edges). In these graphs, each vertex has a weight that corresponds to the amount of computation associated with it, and each edge has a weight that corresponds to the amount of data that needs to be exchanged.</p>\n<p>Graph partitioning algorithms are used to divide the graph into k parts (where k is usually the number of processors/systems) and assign the tasks corresponding to the vertices of each partition to a single processor or system for execution. For the computations to be performed efficiently, the sum of the weights of the tasks of each partition must be nearly identical across the different partitions, leading to a work assignment that is load balanced.</p>\n<p>At the same time, to reduce communication costs, the partitioning needs to minimize the number of edges that cross partition boundaries. The class of graph partitioning algorithms that meet these requirements are typically called bounded-capacity min-cut graph partitioning algorithms, where the term “bounded capacity” refers to the balance constraint and the term “min-cut” relates to the objective of minimizing the sum of the weights of the edges that cross partition boundaries.</p>\n<h4><a id=\"Ideally_we_want_to_compute_a_partitioning_that_simultaneously_balances_the_computational_and_memory_requirements_across_the_different_partitions_24\"></a><strong>Ideally, we want to compute a partitioning that simultaneously balances the computational and memory requirements across the different partitions</strong></h4>\n<p>George Karypis</p>\n<p>In many applications, the bounded capacity min-cut formulation is not sufficient to meet requirements. For example, a computation’s tasks may require different amounts of computation and memory. If a standard bounded-capacity algorithm is used to balance the computations, it could lead to a task assignment that is severely unbalanced in terms of memory requirements. If the bounded-capacity algorithm is used to compute a partitioning that balances the memory requirements, it could lead to a computations load imbalance.</p>\n<p>In either case, Karypis explains, the overall performance of the system will be negatively impacted. “Ideally, we want to compute a partitioning that simultaneously balances the computational and memory requirements across the different partitions,” he said.</p>\n<p>To address these challenges, the paper’s coauthors introduced a model that allows an application to express its multiple balancing requirements, and developed multilevel graph partitioning algorithms that produce partitions that address the constraints, or come close.</p>\n<p>“Since our formulation and algorithms can simultaneously satisfy multiple balancing criteria, I refer to them as multi-constraint partitioning algorithms,” Karypis explained.</p>\n<h4><a id=\"Other_honors_36\"></a><strong>Other honors</strong></h4>\n<p>The SC21 Test of Time Award is one of several Karypis has earned within the past year.</p>\n<p>In May, he received the <ins><a href=\"https://cse.umn.edu/cs/news/karypis-wins-pakdd-distinguished-contributions-award\" target=\"_blank\">Distinguished Contributions Award</a></ins> during the 2021 Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD). Karypis, who also is a professor within the University of Minnesota’s computer science and engineering department, was honored for his outstanding contributions to the field of knowledge discovery and data mining, as well as for his long-standing participation in PAKDD.</p>\n<p>In November 2020, Karypis was awarded the <ins><a href=\"https://www.amazon.science/latest-news/amazon-scholar-george-karypis-receives-icdm-10-year-highest-impact-award\" target=\"_blank\">10-Year-Highest Impact Award</a></ins> at the 2020 IEEE Conference on Data Mining (ICDM).</p>\n<p>More recently, Karypis presented a talk, “<ins><a href=\"https://www.amazon.science/latest-news/on-demand-the-2021-aws-machine-learning-summit\" target=\"_blank\">Deep Graph Library: Deep Graph learning at scale</a></ins>”, at the AWS Machine Learning Summit held earlier this year. Prior to his presentation, Amazon Science interviewed Karypis about <ins><a href=\"https://www.amazon.science/latest-news/3-questions-with-george-karypis-making-learning-from-data-embedded-in-graphs-easy-and-scalable\" target=\"_blank\">his forthcoming talk</a></ins> on deep graph neural networks.</p>\n<p>ABOUT THE AUTHOR</p>\n<h4><a id=\"Staff_writer_48\"></a><strong>Staff writer</strong></h4>\n"}