KI sortiert Elemente um bis zu 69 Prozent schneller
Mit Hilfe von neuen Algorithmen und dem Einsatz von KI beschleunigt eine Schweizer Firma das Sortieren von Elementen deutlich.
(Bild: whiteMocca / shutterstock.com)
Der Schweizer IT-Firma mimicry ist es gelungen, das Sortieren von Elementen in der Programmierung mit KI-Hilfe weiter zu beschleunigen. Die auf Deep Reinforced Learning basierende Technik geht dabei deutlich über den zugrundeliegenden Ansatz AlphaDev von Google DeepMind hinaus. Nach eigenen Angaben hat mimicry einen Algorithmus für die Sortierung von vier Elementen gefunden, dessen Durchsatz um 43 bis 69 Prozent schneller ist, und zwar mit 12 statt 28 Befehlen. Ähnliches gilt für einen Algorithmus für die Sortierung von drei Elementen, der je nach Architektur zwischen 9 Prozent langsamer und 41 schneller war; mit 9 statt 17 Befehlen.
(Bild: mimicry)
Dieser Fortschritt basiert insbesondere auf einem neuen Lösungsweg mit sogenannten Shuffle-Vektoren, die quasi die Sortierreihenfolge anzeigen, statt Elemente direkt zu sortieren. Anders gesagt: Wird der Shuffle-Vektor auf den zu sortierenden Vektor angewendet, kommt das sortierte Element heraus. deep RL kommt bei der Suche nach idealen Shuffle-Vektoren zum Einsatz, unter optimaler Nutzung des Vektorprozessors (SIMD) der CPU, sofern vorhanden, und reduziertem Befehlssatz.
Der ursprüngliche Ansatz von AlphaDev (Juni 2023) führt Methoden des deep RL zur Suche nach idealen Sortieralgorithmen ein. deep RL basiert auf Reinforced Learning (RL) und unterstützt dieses mit neuronalen Netzen. Bei RL trainiert der KI-Agent ohne Datensammlung, sondern nähert sich durch Versuch und Irrtum einem idealen Ergebnis an. Dieses Konzept ist beispielsweise auch in der Robotik erfolgversprechend. Neben KI hebt mimicry aber die klassische Ingenieursleistung hervor: "Unsere Ergebnisse illustrieren die Vorteile davon, menschlichen Genius mit KI-basierten Tools zu kombinieren, um bessere Software zu kreieren und neuartige Routinen zu finden."
Der scalarSort3-Algorithmus ohne SIMD-Nutzung für vorzeichenlose Werte mit 14 Befehlen sieht wie folgt aus:
// Sort3mu - sort 3 uint32t values pointed to by buffer
uint8 t shuf3mu0[] = { 8, 4, 8, 0, 4, 0 };
uint8 t shuf3mul[] = { 4, 8, 0, 8, 0, 4 };
void Sort3mu(uint32 t* buffer) {
asm volatile(
"mov (%0), %%eax \n"
"mov 4(%0), %%edx \n"
"cmp %%eax, %%edx \n"
"sbb %%rbx, %%rbx \n"
"mov 8(%0), %%ecx \n"
"cmp %%eax, %%ecx \n"
"sbb %%r8, %%r8 \n"
"cmp %%ecx, %%edx \n"
"adc $0, %%r8 \n"
"movzb shuf3mu0+3(%%rbx,%%r8,2), %%r9 \n"
"mov %%ecx, 4(%0,%%r8,4) \n"
"movzb shuf3mul+3(%%rbx,%%r8,2), %%rcx \n"
"mov %%eax, (%0,%%r9) \n"
"mov %%edx, (%0,%%rcx) \n"
: "+r"(buffer)
:
: "eax","edx","rbx","rcx","r8","r9","memory");
} Die Firma mimicry ist darauf spezialisiert, veralte Software in Unternehmen durch automatisierte Prozesse auf den neuesten technischen Stand zu bringen, wobei dabei auch Methoden der KI zum Einsatz kommen. Eine Beschreibung des neuen Algorithmus findet sich im Blog der Firma, beziehungsweise die Quellen unter Apache-2-Lizenz bei GitHub.
(who)
