Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization

Abstract

In this paper we present a family of multi-objective hypergraph partitioning algorithms based on the multilevel paradigm, which are capable of producing solutions in which both the cut and the maximum subdomain degree are simultaneously minimized. This type of partitionings are critical for existing and emerging applications in VLSI CAD as they allow to both minimize and evenly distribute the interconnects across the physical devices. Our experimental evaluation on the ISPD98 benchmark show that our algorithms produce solutions that when compared against those produced by hMETIS have a maximum subdomain degree that is reduced by up to 36% while achieving comparable quality in terms of cut.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 29, 2004
Accession Number
ADA439471

Entities

People

  • George Karypis
  • Navaratnasothie Selvakkumaran

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Climbing
  • Collapse
  • Computer Science
  • Construction
  • Governments
  • Information Operations
  • Iterations
  • Mathematics
  • Military Research
  • Minnesota
  • Multiplexing
  • Standards
  • Universities

Fields of Study

  • Computer science

Readers

  • Integrated Circuit Design and Technology.
  • Operations Research
  • Systems Analysis and Design