Standardna binarna pretraga više nije najbrži način za pronalaženje vrednosti u sortiranim nizovima na modernim procesorima. Novi SIMD Quad algoritam demonstrira kako kombinacija paralelne obrade i kvaternarne pretrage može duplirati performanse u specifičnim uslovima rada. Ova metoda koristi prednosti SIMD instrukcija za istovremenu proveru više elemenata čime prevazilazi teoretska ograničenja klasičnih algoritama.
Inženjeri koji rade na Roaring Bitmap formatu često koriste nizove 16-bitnih celih brojeva gde je brzina pretrage kritična za performanse sistema. Tradicionalni pristup deli niz na polovine dok novi pristup deli niz na četvrtine i koristi hardversko ubrzanje za finalnu proveru. Ovakva arhitektura algoritma direktno koristi prednosti modernog paralelizma na nivou memorije.
Tehnika kvaternarne pretrage i SIMD ubrzanje
Srž SIMD Quad algoritma leži u hibridnom pristupu koji kombinuje kvaternarnu interpolacionu pretragu sa paralelnim instrukcijama procesora. Umesto provere jednog po jednog elementa sistem učitava blokove od 16 elemenata direktno u SIMD registre. Na ovaj način se koristi NEON arhitektura na ARM čipovima ili SSE2 na x64 platformama za trenutnu proveru celog bloka podataka.
Algoritam prvo koristi interpolaciju na nivou blokova kako bi brzo suzio opseg pretrage na jedan specifičan blok od 16 elemenata. Nakon toga se primenjuje paralelna operacija koja upoređuje ciljanu vrednost sa svim elementima u bloku u samo jednom ciklusu procesora. Ovim se drastično smanjuje broj grananja u kodu što je ključno za održavanje visoke brzine izvršavanja.
Rezultati testiranja na Apple M4 i Intel procesorima
Benchmark testovi sprovedeni na Apple M4 i Intel Emerald Rapids procesorima pokazuju konzistentnu prednost novog algoritma nad standardnom funkcijom std::binary_search. Na Intel platformi SIMD Quad je bio više nego duplo brži prilikom rada sa toplim kešom memorije. Sa druge strane na Apple platformi najveći dobici su zabeleženi u situacijama sa hladnim kešom gde je algoritam efikasnije upravljao memorijskim kašnjenjem.
Interesantno je da kvaternarni pristup (deljenje na četiri dela) bolje iskorišćava paralelizam memorijskog nivoa nego klasična binarna podela. Iako ovaj metod generiše nešto više instrukcija moderne procesorske jedinice ih obrađuju bez dodatnog opterećenja. Testovi su potvrdili da je SIMD Quad brži u svim testiranim scenarijima nezavisno od veličine niza ili stanja keš memorije.
0 komentara