Chip ARM Pecahkan Rekor Kecepatan untuk Algoritma Kompresi Data

Dalam dunia kompresi data, delta coding telah lama menjadi teknik andalan untuk membuat data lebih kecil dan efisien disimpan. Proses ini mengubah rangkaian angka menjadi perbedaan antara nilai-nilai yang berurutan, menciptakan pola yang dapat dikompresi dengan sangat baik. Namun, membalikkan proses ini—merekonstruksi data asli melalui operasi yang disebut prefix sum—secara tradisional menjadi hambatan komputasi karena ketergantungan serial yang melekat. Penelitian baru mengungkapkan bagaimana teknik optimasi inovatif pada arsitektur Neoverse V2 terbaru dari ARM memecahkan penghalang kinerja sebelumnya untuk operasi fundamental ini.

Hambatan Tersembunyi dalam Dekompresi Data

Sementara delta coding sendiri berjalan efisien pada 41 GB/s di perangkat keras modern, operasi kebalikannya tetap jauh lebih lambat. Masalahnya terletak pada sifat matematis dari prefix sum: setiap nilai keluaran bergantung pada semua perhitungan sebelumnya. Hal ini menciptakan apa yang disebut arsitek komputer sebagai rantai ketergantungan, di mana prosesor harus menunggu setiap operasi selesai sebelum memulai yang berikutnya. Pendekatan tradisional seperti algoritma FastPFoR yang sudah mapan justru berkinerja lebih buruk daripada implementasi skalar sederhana pada prosesor Graviton 4 ARM, hanya mencapai 7,7 GB/s dibandingkan dengan 10,8 GB/s untuk pendekatan naif.

Saya pikir bagian pertama adalah salah ketik, tapi ternyata benar; pendekatan naif lebih cepat daripada metode 'yang lebih baik'. Demonstrasi lain tentang betapa pentingnya melakukan benchmark pada platform target!

Hasil yang mengejutkan ini menyoroti bagaimana kinerja algoritma dapat sangat bervariasi di berbagai arsitektur prosesor, menekankan pentingnya optimasi spesifik-platform daripada mengandalkan metode mapan yang mungkin dirancang untuk perangkat keras yang berbeda.

Memutus Rantai Ketergantungan

Terobosan datang dari restrukturisasi komputasi untuk meminimalkan ketergantungan serial ini. Alih-alih langsung menerapkan total berjalan ke setiap nilai baru, pendekatan baru memproses data dalam blok dan menunda langkah akumulasi. Hal ini memungkinkan perangkat keras eksekusi out-of-order prosesor untuk mengerjakan beberapa operasi secara bersamaan daripada menunggu setiap hasil. Teknik ini menukar peningkatan kecil dalam total instruksi dengan peningkatan paralelisme yang dramatis, mencapai 19,8 GB/s—hampir dua kali lipat kinerja implementasi naif dan 2,6 kali lebih cepat daripada FastPFoR.

Metode ini melampaui prefix sum sederhana ke transformasi yang lebih kompleks seperti delta-of-delta coding (efektif untuk urutan timestamp) dan pengkodean XOR-with-previous (digunakan dalam skema kompresi floating-point seperti Gorilla). Untuk pembalikan delta-of-delta, teknik pipelining memberikan peningkatan kecepatan 2,2x, sementara operasi XOR diuntungkan dari pendekatan alternatif berbasis transpose yang meningkatkan kinerja sebesar 2,0x.

Konsep Teknis Utama yang Dijelaskan

• Delta Coding: Menyimpan perbedaan antara nilai-nilai berurutan alih-alih angka mentah, menciptakan pola yang lebih mudah dikompresi
• Prefix Sum: Operasi kebalikan yang merekonstruksi nilai asli dengan mengakumulasi perbedaan
• Dependency Chain: Ketika setiap kalkulasi bergantung pada hasil sebelumnya, memaksa eksekusi berurutan
• SIMD Intrinsics: Fungsi khusus prosesor yang beroperasi pada beberapa elemen data secara bersamaan
• Neoverse V2: Arsitektur CPU kelas server terbaru dari ARM yang digunakan dalam prosesor AWS Graviton4

Debat CPU vs GPU dalam Beban Kerja Dunia Nyata

Diskusi secara alami meluas ke apakah GPU dapat mempercepat operasi ini lebih lanjut. Meskipun GPU unggul dalam komputasi paralel, overhead transfer memori antara RAM sistem dan memori GPU sering kali meniadakan keuntungan teoretis untuk beban kerja kompresi data dunia nyata. Seperti yang dikatakan seorang komentator, Jika data sudah berada di memori GPU, ya. Kalau tidak, Anda akan dibatasi oleh hambatan memori DRAM←→VRAM.

Analisis biaya-kinerja mengungkapkan pertukaran yang menarik. Membandingkan harga instance cloud, instance m8g.8xlarge berbasis ARM dengan 32 inti menawarkan bandwidth memori 175 GB/s seharga 1,44 dolar AS per jam, sementara instance GPU dengan bandwidth teoretis serupa harganya lebih mahal. Untuk basis data deret waktu dan beban kerja analitis tipikal di mana data mengalami beberapa transformasi sementara di-cache dalam memori CPU, pendekatan ARM menunjukkan efisiensi yang menarik.

Perbandingan Performa pada AWS Graviton4 (Neoverse V2)

Kondisi pengujian: working set 4 KiB, 20.000 iterasi, single-threaded, L1 cache hot

Melampaui Kinerja Teoretis

Diskusi komunitas mengungkapkan pertimbangan praktis yang melampaui angka throughput mentah. Beberapa komentator menunjuk bahwa menyisipkan nilai absolut pada interval teratur dalam aliran yang dikode-delta dapat memungkinkan paralelisasi sempurna, meskipun ini akan mengorbankan efisiensi kompresi. Yang lain berbagi pengalaman dari menerapkan algoritma serupa dalam sistem produksi, mencatat bahwa pendekatan optimal sangat bergantung pada pola akses data dan frekuensi pembaruan.

Teknik yang dijelaskan tidak terbatas pada integer 32-bit—teknik ini secara alami meluas ke tipe data 8, 16, dan 64-bit, membuatnya berlaku untuk berbagai skenario kompresi data dari sistem basis data hingga komputasi ilmiah. Implementasi referensi menggunakan intrinsik SIMD, yang pada dasarnya adalah instruksi assembly yang dibungkus dalam fungsi C, memungkinkan kontrol halus atas kemampuan prosesor.

Seiring volume data terus tumbuh secara eksponensial, optimasi seperti ini menunjukkan bahwa masih ada kinerja signifikan yang dapat dibuka dalam algoritma fundamental melalui pemrograman yang sadar arsitektur. Hasilnya menunjukkan bahwa terkadang optimasi paling efektif datang bukan dari menambah lebih banyak perangkat keras pada suatu masalah, tetapi dari bekerja lebih cerdas dengan perangkat keras yang sudah kita miliki.

Referensi: NEON Delta Coding