Pertanyaan Kapan, jika pernah, apakah loop unrolling masih berguna?


Saya telah mencoba untuk mengoptimalkan beberapa kode sangat penting-kinerja (semacam algoritma cepat yang disebut jutaan dan jutaan kali dalam simulasi monte carlo) oleh loop unrolling. Inilah lingkaran dalam yang saya coba untuk mempercepat:

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

Saya mencoba membuka gulungan ke sesuatu seperti:

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

Ini benar-benar tidak ada perbedaan jadi saya mengubahnya kembali ke bentuk yang lebih mudah dibaca. Saya pernah mengalami pengalaman serupa saat-saat lain. Saya sudah mencoba loop unrolling. Mengingat kualitas prediksi cabang pada perangkat keras modern, kapan, jika pernah, apakah loop membuka gulungan masih merupakan pengoptimalan yang bermanfaat?


75
2018-02-27 22:41


asal


Jawaban:


Loop unrolling masuk akal jika Anda dapat mematahkan rantai ketergantungan. Ini memberikan CPU yang tidak teratur atau super-skalar, kemungkinan untuk menjadwalkan berbagai hal dengan lebih baik dan dengan demikian berjalan lebih cepat.

Contoh sederhana:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

Di sini rantai ketergantungan argumen sangat pendek. Jika Anda mendapatkan kios karena Anda memiliki cache-miss pada data-array, cpu tidak dapat melakukan apa-apa selain menunggu.

Di sisi lain kode ini:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

bisa berjalan lebih cepat. Jika Anda mendapatkan cache miss atau kios lain dalam satu perhitungan, masih ada tiga rantai ketergantungan lain yang tidak bergantung pada kios. CPU yang rusak dapat mengeksekusi ini.


99
2018-02-27 22:54



Mereka tidak akan membuat perbedaan karena Anda melakukan perbandingan jumlah yang sama. Ini contoh yang lebih baik. Dari pada:

for (int i=0; i<200; i++) {
  doStuff();
}

menulis:

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

Bahkan kemudian hampir pasti tidak masalah tetapi Anda sekarang melakukan 50 perbandingan daripada 200 (bayangkan perbandingannya lebih rumit).

Manual loop unrolling secara umum sebagian besar merupakan artefak sejarah. Ini adalah daftar hal-hal yang sedang berkembang yang akan dilakukan oleh kompiler yang bagus untuk Anda ketika itu penting. Misalnya, kebanyakan orang tidak mau repot-repot menulis x <<= 1 atau x += x dari pada x *= 2. Anda baru saja menulis x *= 2 dan kompilator akan mengoptimalkannya bagi Anda untuk apa pun yang terbaik.

Pada dasarnya ada semakin sedikit kebutuhan untuk menebak-nebak kompilator Anda.


19
2018-02-27 22:44



Terlepas dari prediksi cabang pada perangkat keras modern, sebagian besar kompiler melakukan loop unrolling untuk Anda.

Akan bermanfaat untuk mengetahui seberapa banyak pengoptimalan yang dilakukan kompilator untuk Anda.

saya menemukan Presentasi Felix von Leitner sangat mencerahkan tentang masalah ini. Saya sarankan Anda membacanya. Ringkasan: Penyusun modern sangat SANGAT pintar, jadi optimisasi tangan hampir tidak pernah efektif.


13
2018-02-27 22:48



Sejauh yang saya pahami, kompiler modern sudah membuka gulungan di mana sesuai - contohnya adalah gcc, jika melewati bendera optimasi, manual mengatakan akan:

Buka gulungan yang jumlahnya sebesar   iterasi dapat ditentukan pada   mengkompilasi waktu atau saat masuk ke   lingkaran.

Jadi, dalam prakteknya kemungkinan bahwa kompiler Anda akan melakukan hal-hal sepele untuk Anda. Terserah Anda untuk memastikan bahwa sebanyak mungkin loop Anda mudah bagi compiler untuk menentukan berapa banyak iterasi yang diperlukan.


2
2018-02-27 22:50



Loop membuka gulungan, apakah itu tangan membuka gulungan atau kompilator membuka gulungan, sering dapat kontra-produktif, terutama dengan CPU x86 yang lebih baru (Core 2, Core i7). Intinya: patokan kode Anda dengan dan tanpa loop yang membuka gulungan pada CPU apa pun yang Anda rencanakan untuk menerapkan kode ini.


2
2018-02-27 23:40



Berusaha tanpa mengetahui bukanlah cara untuk melakukannya.
Apakah jenis ini mengambil persentase waktu keseluruhan yang tinggi?

Semua loop unrolling dilakukan adalah mengurangi loop overr / incrementing / decrementing, membandingkan kondisi stop, dan jumping. Jika apa yang Anda lakukan dalam loop membutuhkan lebih banyak siklus instruksi daripada loop di atas itu sendiri, Anda tidak akan melihat banyak peningkatan persentase-bijaksana.

Berikut ini contoh cara mendapatkan performa maksimal.


1
2018-02-28 16:41



Loop membuka gulungan dapat membantu dalam kasus-kasus tertentu. Satu-satunya keuntungan tidak melewati beberapa tes!

Hal ini misalnya dapat memungkinkan penggantian skalar, penyisipan perangkat lunak yang efisien mengambil ... Anda akan terkejut sebenarnya bagaimana berguna dapat (Anda dapat dengan mudah mendapatkan 10% percepatan pada kebanyakan loop bahkan dengan -O3) dengan secara agresif membuka gulungan.

Seperti yang dikatakan sebelumnya, itu sangat tergantung pada loop dan kompilator dan eksperimen diperlukan. Sulit untuk membuat aturan (atau heuristik kompilator untuk membuka gulungan akan menjadi sempurna)


1
2018-03-01 20:38



Loop unrolling sepenuhnya tergantung pada ukuran masalah Anda. Itu sepenuhnya tergantung pada algoritma Anda yang mampu mengurangi ukuran menjadi kelompok kerja yang lebih kecil. Apa yang Anda lakukan di atas tidak terlihat seperti itu. Saya tidak yakin apakah simulasi monte carlo bahkan bisa dibuka.

Saya skenario bagus untuk loop unrolling akan memutar gambar. Karena Anda bisa merotasi kelompok kerja yang terpisah. Agar ini berfungsi, Anda harus mengurangi jumlah iterasi.


0
2018-02-27 22:45



Loop unrolling masih berguna jika ada banyak variabel lokal baik dalam maupun dengan loop. Untuk menggunakan kembali register tersebut lebih banyak daripada menyimpan satu untuk indeks loop.

Dalam contoh Anda, Anda menggunakan sejumlah kecil variabel lokal, tidak terlalu sering menggunakan register.

Perbandingan (ke loop end) juga merupakan kelemahan utama jika perbandingannya berat (yaitu non-test instruksi), terutama jika itu tergantung pada fungsi eksternal.

Loop membuka gulungan membantu meningkatkan kesadaran CPU untuk prediksi cabang juga, tetapi itu tetap terjadi.


0
2018-02-27 22:49