KIP publications

 
year 2018
author(s) Jörg Steidel
title Solving Map Coloring Problems on Analog Neuromorphic Hardware
KIP-Nummer HD-KIP 18-89
KIP-Gruppe(n) F9
document type Bachelorarbeit
Keywords brainscales, neuromorphic hardware, csp, map coloring, snn, annealing
Abstract (de)

Die vorliegende Arbeit implementiert einen neuromorphen Löser für Kartenfärbungsprobleme auf dem BrainScaleS System, einem analogen beschleunigten gepulsten neuronalen Netzwerkemulator. Die Karten der australischen Territorien und der deutschen Bundesländer werden benutzt, um dessen Lösungsfähigkeit für Kartenfärbungsprobleme zu demonstrieren, d.h. Lösungen zu generieren, bei denen Nachbarländer nie die gleiche Farbe haben, und dessen Leistung zu analysieren.

Es werden zwei verschiedene Betriebsmodi untersucht. Experimente mit konstanten Stimulusraten werden darauf optimiert, möglichst schnell die erste korrekte Lösung zu finden. Es wird gezeigt, dass Konfigurationen existieren, bei denen sich der Einfluss von Hardwareschwankungen in Grenzen hält, was zu vorhersehbarem und robustem Netzwerkverhalten führt, selbst wenn die Hardware neu konfiguriert wird.

Eine andere Art von Experimenten sind Annealing-Experimente. Sie zeigen, dass Absenkung der Stimulusrate über Zeit genutzt werden kann, um Netzwerkkonvergenz zu erreichen. Biologische Konvergenzzeiten sind dabei vergleichbar mit denen, die in Simulationen auf dem SpiNNaker System erreicht wurden, was bedeutet, dass der Beschleunigungsfaktor des BrainScaleS Systems voll ausgenutzt werden kann. Durch Optimierung der Auslesezeiten werden Konfigurationen gefunden, in denen keine inkorrekten Lösungen auftreten, wodurch dort die Überprüfung auf verletzte Bedingungen nicht nötig ist. Daher werden neben dem gepulsten neuronalen Netzwerk nur geringe Rechenressourcen benötigt, um das Kartenfärbungsproblem zu lösen.

Abstract (en)

This thesis implements a neuromorphic solver for map coloring problems on the BrainScaleS system, an analog accelerated spiking neural network emulator. The maps of the territories of Australia and the German federal states are used to show that it is capable of solving map coloring problems i.e. generating solutions in which no bordering countries have the same color and analyze its performance.

Two different modes of operation are investigated. Experiments with constant stimulus rate are optimized to produce the first correct solution as fast as possible. It is shown that there are configurations for which the influence of hardware variations is limited, leading to predictable and robust network behavior even after hardware reconfiguration.

A second kind of experiments are annealing experiments. They show that decreasing the stimulus rate over time can be used to achieve network convergence. Biological convergence times are comparable to those achieved with similar networks simulated on the SpiNNaker system, which means one can take full advantage of the BrainScaleS' acceleration factor. Through the optimization of read out times configurations are found in which no incorrect solutions are produced, thus eliminating the need to check for violated constraints. Therefore, only very little computational resources other than the spiking neural network itself are needed to solve a map coloring problem.

bibtex
@mastersthesis{steidel2018mapcoloring,
  author   = {J\"org Steidel},
  title    = {Solving Map Coloring Problems on Analog Neuromorphic Hardware},
  school   = {Universit\"at Heidelberg},
  year     = {2018},
  type     = {Bachelorarbeit}
}
Datei pdf
up
KIP - Bibliothek
Im Neuenheimer Feld 227
Raum 3.402
69120 Heidelberg