Branchless Programming auf Arm, Java, Julia

23.08.2020

Nachdem ich neulich ein Video zum Thema Branchless Programming gefunden hatte habe ich gedacht - dort wurde nur C auf x86-Prozessoren beleuchtet. Mich hat das Thema so sehr interessiert, dass ich eigene Experimente veranstaltet habe:

@youtube.com

Branchless Programming - noch einmal kurz zusammengefasst - ist der Versuch, die Anzahl der bedingten Sprünge im Maschinencode zu minimieren. In Prozessorarchitekturen, die eine Pipeline aufweisen sorgen Sprünge dafür, dass die bereits in der Pipeline befindlichen und teilweise verarbeiteten Befehle verworfen werden müssen. Abhängig vom Wert der Bedinung kann die Ausführung an zwei verschiedenen Stellen im Code fortgesetzt werden und der Prozessor muss auf eine von beiden tippen, die dann in der Pipeline bereits vorverarbeitet wird. Kommt bei Auswertung der Bedingung die Variante heraus, auf die der Prozessor nicht gewettet hat, muss er seine Arbeit verwerfen und nochmal neu ansetzen. Das führt zu Leerstand in der Pipeline und - abhängig von der Länge - zu teils erheblichen Performanceeinbußen.

Bei heutigen Prozessoren entfällt ein großer Teil der Chipfläche daher auf die sogenannte Branch Prediction Logic. Die versucht, durch Analyse des Maschinencodes die Anzahl der erfolgreichen Tips zu beeinflussen, so dass das Leeren und neu Ansetzen der Pipeline (deutlich) seltener stattfinden muss. Besser wäre es jedoch, wenn man deterministisch dafür sorgen könnte, dass das nie passiert - dazu setzt man branchless Programming ein.

Dazu werden die logischen Bedingungen so transformiert, dass sie arithmetische Ausdrücke ergeben, von denen jeweils nur exakt einer wahr ist. Diese Transformation ist gegebenenfalls aber länger als die Variante mit bedingten Sprüngen - daher sollte man immer genau prüfen, ob das Ergebnis den zusätzlichen Aufwand tatsächlich rechtfertigt.

Jetzt aber genug der Theorie - kommen wir zu Experimenten und deren Ergebnissen...

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Virtuelles Netzwerklabor

    11.01.2017

    Nachdem ich hin und wieder vor der Herausforderung stehe, Anwendungen unter realen Netzwerkbedingungen zu testen, habe ich bereits vor längerer Zeit begonnen, ein virtuelles Netzwerklabor aufzubauen...

    Weiterlesen...

Neueste Artikel

  • Stratum-1-NTP-Server Links

    Ich habe meinen eigenen Stratum-1-NTP-Server mittels eines GPS-Empfängers, einer Adapterschaltung und einem Raspi gebaut. Hier fasse ich einige nützliche Links zu diesem Themengebiet zusammen

    Weiterlesen...
  • EBCMS threaded und mit mehr Markdown-Unterstützung

    Mein eigener Static Site Generator hat in den letzten Wochen einige größere Umbauten erfahren

    Weiterlesen...
  • Fork der BeanShell wegen Trojan Source

    Es gibt inzwischen einen von mir erstellten Fork des originalen Repository, in dem ich die Komponente zur Darstellung der Konsole gegen die ausgetauscht habe, die in der sQLshell in den Plugins MDIJavaEditor und MDISqlEditor zum Einsatz kommt - dadurch wird wenigstens durch das Syntax-Highlighting auf problematische Stellen im Code hingewiesen.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier.