Symmetry in Software Synthesis

Andrés Goens, Sergio Siccha, Jeronimo Castrillon

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

With the surge of multi- and many-core systems, much research has focused on algorithms for mapping and scheduling on these complex platforms. Large classes of these algorithms face scalability problems. This is why diverse methods are commonly used for reducing the search space. While most such approaches leverage the inherent symmetry of architectures and applications, they do it in a problem-specific and intuitive way. However, intuitive approaches become impractical with growing hardware complexity, like Network-on-Chip interconnect or heterogeneous cores. In this article, we present a formal framework that can determine the inherent local and global symmetry of architectures and applications algorithmically and leverage these for problems in software synthesis. Our approach is based on the mathematical theory of groups and a generalization called inverse semigroups. We evaluate our approach in two state-of-the-art mapping frameworks. Even for the platforms with a handful of cores of today and moderate-sized benchmarks, our approach consistently yields reductions of the overall execution time of algorithms. We obtain a speedup of more than 10 for one use-case and saved 10% of time in another.
Original languageEnglish
Article number20
Number of pages26
JournalACM Transactions on Architecture and Code Optimization
Volume14
Issue number2
DOIs
Publication statusPublished - 12 Jul 2017

Keywords / Materials (for Non-textual outputs)

  • network-on-chip
  • inverse-semigroups
  • Scalability
  • heterogeneous
  • metaheuristics
  • mapping
  • design-space exploration
  • group theory
  • clusters
  • automation
  • symmetry

Fingerprint

Dive into the research topics of 'Symmetry in Software Synthesis'. Together they form a unique fingerprint.

Cite this