it-swarm-id.com

Mengapa lebih cepat memproses array yang diurutkan daripada array yang tidak disortir?

Ini adalah bagian dari kode C++ yang tampaknya sangat aneh. Untuk beberapa alasan aneh, mengurutkan data secara ajaib membuat kode hampir enam kali lebih cepat.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::Rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Tanpa std::sort(data, data + arraySize);, kode berjalan dalam 11,54 detik.
  • Dengan data yang diurutkan, kode ini berjalan dalam 1,93 detik.

Awalnya, saya pikir ini mungkin hanya sebuah anomali bahasa atau kompiler. Jadi saya mencobanya di Jawa.

import Java.util.Arrays;
import Java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Dengan hasil yang agak mirip tetapi kurang ekstrim.


Pikiran pertama saya adalah penyortiran membawa data ke dalam cache, tetapi kemudian saya berpikir betapa konyolnya karena array baru saja dihasilkan.

  • Apa yang sedang terjadi?
  • Mengapa lebih cepat memproses array yang diurutkan daripada array yang tidak disortir?
  • Kode ini merangkum beberapa istilah independen, dan urutannya tidak masalah.
22968
GManNickG

Anda adalah korban dari prediksi cabang gagal.


Apa itu Prediksi Cabang?

Pertimbangkan persimpangan kereta api:

 Image showing a railroad junction Gambar oleh Mecanismo, via Wikimedia Commons. Digunakan di bawah lisensi CC-By-SA 3.0 .

Sekarang demi argumen, anggaplah ini kembali pada 1800-an - sebelum komunikasi jarak jauh atau radio.

Anda adalah operator persimpangan dan Anda mendengar kereta datang. Anda tidak tahu ke mana harus pergi. Anda menghentikan kereta untuk bertanya kepada pengemudi ke arah mana mereka inginkan. Dan kemudian Anda mengatur sakelar dengan tepat.

Kereta berat dan memiliki banyak inersia. Jadi mereka butuh waktu lama untuk memulai dan memperlambat.

Apakah ada cara yang lebih baik? Anda menebak ke arah mana kereta akan pergi!

  • Jika Anda menebak dengan benar, itu berlanjut.
  • Jika Anda salah menebak, kapten akan berhenti, mundur, dan berteriak kepada Anda untuk membalik sakelar. Kemudian dapat memulai kembali di jalur lain.

Jika Anda menebak dengan benar setiap kali , kereta tidak akan pernah berhenti.
Jika Anda salah menebak terlalu sering , kereta akan menghabiskan banyak waktu untuk berhenti, mencadangkan, dan memulai kembali.


Pertimbangkan pernyataan if: Pada level prosesor, ini adalah instruksi cabang:

Screenshot of compiled code containing an if statement

Anda adalah prosesor dan Anda melihat cabang. Anda tidak tahu ke mana akan pergi. Apa yang kamu kerjakan? Anda menghentikan eksekusi dan menunggu hingga instruksi sebelumnya selesai. Kemudian Anda melanjutkan jalan yang benar.

Prosesor modern rumit dan memiliki jaringan pipa yang panjang. Jadi mereka butuh waktu lama untuk "menghangatkan" dan "memperlambat".

Apakah ada cara yang lebih baik? Anda menebak ke arah mana cabang akan pergi!

  • Jika Anda menebak dengan benar, Anda terus mengeksekusi.
  • Jika Anda salah menebak, Anda perlu menyiram pipa dan kembali ke cabang. Kemudian Anda dapat memulai kembali jalan lain.

Jika Anda menebak dengan benar setiap kali , eksekusi tidak akan pernah berhenti.
Jika Anda salah menebak terlalu sering , Anda menghabiskan banyak waktu mengulur waktu, memutar kembali, dan memulai kembali.


Ini adalah prediksi cabang. Saya akui itu bukan analogi terbaik karena kereta hanya bisa memberi sinyal arah dengan bendera. Tetapi di komputer, prosesor tidak tahu ke arah mana cabang akan pergi sampai saat terakhir.

Jadi bagaimana menurut Anda secara strategis untuk meminimalkan berapa kali kereta harus mundur dan turun ke jalan lain? Anda melihat sejarah masa lalu! Jika kereta pergi ke kiri 99% dari waktu, maka Anda menebak ke kiri. Jika itu bergantian, maka Anda mengubah tebakan Anda. Jika berjalan satu arah setiap 3 kali, Anda menebak ...

Dengan kata lain, Anda mencoba mengidentifikasi suatu pola dan mengikutinya.Ini kurang lebih bagaimana cara kerja prediktor cabang.

Sebagian besar aplikasi memiliki cabang yang berperilaku baik. Jadi prediktor cabang modern biasanya akan mencapai> 90% hit rate. Tetapi ketika dihadapkan dengan cabang yang tidak dapat diprediksi tanpa pola yang dapat dikenali, prediktor cabang hampir tidak berguna.

Bacaan lebih lanjut: Artikel "Prediktor cabang" di Wikipedia .


Seperti yang diisyaratkan dari atas, pelakunya adalah pernyataan if ini:

if (data[c] >= 128)
    sum += data[c];

Perhatikan bahwa data terdistribusi secara merata antara 0 dan 255. Ketika data diurutkan, kira-kira setengah dari iterasi tidak akan memasukkan pernyataan if. Setelah itu, mereka semua akan memasukkan pernyataan if.

Ini sangat bersahabat dengan prediktor cabang karena cabang secara berurutan pergi ke arah yang sama berkali-kali. Bahkan penghitung jenuh sederhana akan dengan benar memprediksi cabang kecuali untuk beberapa iterasi setelah berganti arah.

Visualisasi cepat:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Namun, ketika data benar-benar acak, prediktor cabang dianggap tidak berguna karena tidak dapat memprediksi data acak. Dengan demikian kemungkinan akan ada sekitar 50% kesalahan prediksi. (tidak lebih baik dari tebakan acak)

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Jadi apa yang bisa dilakukan?

Jika kompiler tidak dapat mengoptimalkan cabang menjadi langkah bersyarat, Anda dapat mencoba beberapa peretasan jika Anda bersedia mengorbankan keterbacaan untuk kinerja.

Menggantikan:

if (data[c] >= 128)
    sum += data[c];

dengan:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Ini menghilangkan cabang dan menggantinya dengan beberapa operasi bitwise.

(Perhatikan bahwa peretasan ini tidak sepenuhnya setara dengan pernyataan if asli. Namun dalam kasus ini, peretasan ini berlaku untuk semua nilai input data[].)

Tingkatan yang dicapai: Core i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - Rilis x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Pengamatan:

  • Dengan Cabang: Ada perbedaan besar antara data yang diurutkan dan yang tidak disortir.
  • Dengan Peretasan: Tidak ada perbedaan antara data yang diurutkan dan yang tidak disortir.
  • Dalam kasus C++, retasan sebenarnya sedikit lebih lambat dibandingkan dengan cabang saat data diurutkan.

Aturan umum adalah untuk menghindari percabangan yang bergantung pada data dalam loop kritis. (seperti dalam contoh ini)


Pembaruan:

  • GCC 4.6.1 dengan -O3 atau -ftree-vectorize pada x64 dapat menghasilkan gerakan bersyarat. Jadi tidak ada perbedaan antara data yang diurutkan dan yang tidak disortir - keduanya cepat.

  • VC++ 2010 tidak dapat menghasilkan gerakan bersyarat untuk cabang ini bahkan di bawah /Ox.

  • Intel Compiler 11 melakukan sesuatu yang ajaib. Ini menukar kedua loop , dengan demikian mengangkat cabang yang tidak dapat diprediksi ke loop luar. Jadi tidak hanya itu kebal dari kesalahan prediksi, itu juga dua kali lebih cepat dari apa pun yang dapat dihasilkan oleh VC++ dan GCC! Dengan kata lain, ICC mengambil keuntungan dari tes-loop untuk mengalahkan benchmark ...

  • Jika Anda memberikan Intel Compiler kode branchless, itu hanya akan langsung membuat vektornya menjadi salah ... dan sama cepatnya dengan cabang (dengan pertukaran loop).

Ini menunjukkan bahwa kompiler modern yang matang sekalipun dapat sangat bervariasi dalam kemampuannya untuk mengoptimalkan kode ...

30104
Mysticial

Prediksi cabang.

Dengan array yang diurutkan, kondisi data[c] >= 128 adalah false pertama untuk deretan nilai, kemudian menjadi true untuk semua nilai selanjutnya. Itu mudah diprediksi. Dengan array yang tidak disortir, Anda membayar biaya percabangan.

3879
Daniel Fischer

Alasan mengapa kinerja meningkat secara drastis ketika data disortir adalah bahwa hukuman prediksi cabang dihapus, seperti yang dijelaskan dengan indah dalam Mysticial jawaban.

Sekarang, jika kita melihat kodenya

if (data[c] >= 128)
    sum += data[c];

kita dapat menemukan bahwa arti dari cabang if... else... khusus ini adalah menambahkan sesuatu ketika suatu kondisi terpenuhi. Jenis cabang ini dapat dengan mudah diubah menjadi perpindahan bersyarat pernyataan, yang akan dikompilasi menjadi instruksi pemindahan bersyarat: cmovl, dalam sistem x86. Cabang dan dengan demikian penalti prediksi cabang potensial dihapus.

Dalam C, demikian C++, pernyataan, yang akan dikompilasi secara langsung (tanpa optimasi apa pun) ke dalam instruksi pemindahan bersyarat di x86, adalah operator ternary ... ? ... : .... Jadi kami menulis ulang pernyataan di atas menjadi pernyataan yang setara:

sum += data[c] >=128 ? data[c] : 0;

Sambil mempertahankan keterbacaan, kita dapat memeriksa faktor percepatan.

Pada Intel Core i7 - 2600K @ 3.4 GHz dan Mode Rilis Visual Studio 2010, patokannya adalah (format disalin dari Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Hasilnya kuat dalam beberapa tes. Kami mendapatkan speedup yang hebat ketika hasil cabang tidak dapat diprediksi, tetapi kami sedikit menderita saat diprediksi. Bahkan, ketika menggunakan gerakan bersyarat, kinerjanya sama terlepas dari pola data.

Sekarang mari kita melihat lebih dekat dengan menyelidiki x86 Majelis yang mereka hasilkan. Untuk mempermudah, kami menggunakan dua fungsi max1 dan max2.

max1 menggunakan cabang kondisional if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 menggunakan operator ternary ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

Pada mesin x86-64, GCC -S menghasilkan Majelis di bawah ini.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 menggunakan kode yang jauh lebih sedikit karena penggunaan instruksi cmovge. Tetapi keuntungan sebenarnya adalah bahwa max2 tidak melibatkan lompatan cabang, jmp, yang akan memiliki penalti kinerja yang signifikan jika hasil yang diprediksi tidak benar.

Jadi mengapa langkah kondisional berkinerja lebih baik?

Dalam prosesor x86 biasa, eksekusi instruksi dibagi menjadi beberapa tahap. Secara kasar, kami memiliki perangkat keras yang berbeda untuk menangani tahapan yang berbeda. Jadi kita tidak perlu menunggu satu instruksi untuk menyelesaikan untuk memulai yang baru. Ini disebutpipelining.

Dalam kasus cabang, instruksi berikut ditentukan oleh yang sebelumnya, jadi kami tidak bisa melakukan pipelining. Kita harus menunggu atau memprediksi.

Dalam kasus pemindahan bersyarat, instruksi pemindahan bersyarat eksekusi dibagi menjadi beberapa tahap, tetapi tahapan sebelumnya seperti Fetch dan Decode tidak bergantung pada hasil dari instruksi sebelumnya; hanya tahap terakhir yang membutuhkan hasilnya. Jadi, kami menunggu sebagian kecil dari waktu eksekusi satu instruksi. Inilah sebabnya mengapa versi pemindahan bersyarat lebih lambat daripada cabang saat prediksi mudah.

Buku Sistem Komputer: Perspektif Programmer, edisi kedua menjelaskan hal ini secara terperinci. Anda dapat memeriksa Bagian 3.6.6 untuk Petunjuk Pergerakan Bersyarat, seluruh Bab 4 untuk Prosesor Arsitektur, dan Bagian 5.11.2 untuk perlakuan khusus untuk Denda Prediksi dan Misprediksi Hukuman.

Terkadang, beberapa kompiler modern dapat mengoptimalkan kode kami ke Assembly dengan kinerja yang lebih baik, kadang-kadang beberapa kompiler tidak dapat (kode tersebut menggunakan kompiler asli Visual Studio). Mengetahui perbedaan kinerja antara pemindahan cabang dan bersyarat saat tidak dapat diprediksi dapat membantu kami menulis kode dengan kinerja yang lebih baik ketika skenario menjadi sangat rumit sehingga kompiler tidak dapat mengoptimalkannya secara otomatis.

3125
WiSaGaN

Jika Anda ingin tahu tentang lebih banyak optimasi yang dapat dilakukan untuk kode ini, pertimbangkan ini:

Dimulai dengan loop asli:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Dengan loop interchange, kita dapat dengan aman mengubah loop ini ke:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Kemudian, Anda dapat melihat bahwa kondisional if konstan selama eksekusi dari i loop, sehingga Anda dapat mengangkat if out:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Kemudian, Anda melihat bahwa loop dalam dapat diciutkan menjadi satu ekspresi tunggal, dengan asumsi model floating point memungkinkannya (/ fp: fast dilemparkan, misalnya)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Yang itu 100.000x lebih cepat dari sebelumnya

2143
vulcan raven

Tidak diragukan lagi beberapa dari kita akan tertarik pada cara mengidentifikasi kode yang bermasalah untuk prediktor cabang CPU. Alat Valgrind cachegrind memiliki simulator prediktor cabang, diaktifkan dengan menggunakan flag --branch-sim=yes. Menjalankannya di atas contoh dalam pertanyaan ini, dengan jumlah loop luar dikurangi menjadi 10.000 dan dikompilasi dengan g++, memberikan hasil ini:

Diurutkan:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Tidak disortir:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Mengebor ke dalam output baris demi baris yang dihasilkan oleh cg_annotate kita lihat untuk loop yang dimaksud:

Diurutkan:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Tidak disortir:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Ini memungkinkan Anda dengan mudah mengidentifikasi baris yang bermasalah - dalam versi yang tidak disortir, baris if (data[c] >= 128) menyebabkan 164.050.007 cabang bersyarat salah (Bcm) di bawah model prediktor cabang cachegrind, sedangkan itu hanya menyebabkan 10.006 dalam versi yang diurutkan.


Atau, di Linux Anda dapat menggunakan subsistem penghitung kinerja untuk menyelesaikan tugas yang sama, tetapi dengan kinerja asli menggunakan penghitung CPU.

perf stat ./sumtest_sorted

Diurutkan:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Tidak disortir:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Itu juga dapat melakukan anotasi kode sumber dengan pembongkaran.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Lihat tutorial kinerja untuk lebih jelasnya.

1784
caf

Saya baru saja membaca pertanyaan ini dan jawabannya, dan saya merasa ada jawaban yang hilang.

Cara umum untuk menghilangkan prediksi cabang yang saya temukan bekerja sangat baik dalam bahasa yang dikelola adalah pencarian tabel alih-alih menggunakan cabang (meskipun saya belum mengujinya dalam kasus ini).

Pendekatan ini bekerja secara umum jika:

  1. itu meja kecil dan cenderung di-cache di prosesor, dan
  2. anda menjalankan hal-hal dalam loop yang cukup ketat dan/atau prosesor dapat memuat data.

Latar belakang dan mengapa

Dari perspektif prosesor, memori Anda lambat. Untuk mengimbangi perbedaan dalam kecepatan, beberapa cache dibangun ke prosesor Anda (L1/L2 cache). Jadi bayangkan Anda melakukan perhitungan Nice dan mencari tahu bahwa Anda perlu memori. Prosesor akan mendapatkan operasinya 'memuat' dan memuat potongan memori ke dalam cache - dan kemudian menggunakan cache untuk melakukan sisa perhitungan. Karena memori relatif lambat, 'memuat' ini akan memperlambat program Anda.

Seperti prediksi cabang, ini dioptimalkan dalam prosesor Pentium: prosesor memperkirakan bahwa ia perlu memuat sepotong data dan mencoba memuatnya ke dalam cache sebelum operasi benar-benar menyentuh cache. Seperti yang telah kita lihat, prediksi cabang terkadang salah besar - dalam skenario terburuk Anda harus kembali dan benar-benar menunggu beban memori, yang akan memakan waktu selamanya ( dengan kata lain: gagal prediksi cabang itu buruk, beban memori setelah gagal prediksi cabang hanya mengerikan! ).

Untungnya bagi kita, jika pola akses memori dapat diprediksi, prosesor akan memuatnya dalam cache cepat dan semuanya baik-baik saja.

Hal pertama yang perlu kita ketahui adalah kecil ? Meskipun lebih kecil umumnya lebih baik, aturan praktisnya adalah tetap berpegang pada tabel pencarian yang berukuran <= 4096 byte. Sebagai batas atas: jika tabel pencarian Anda lebih besar dari 64K mungkin perlu dipertimbangkan kembali.

Membangun meja

Jadi kita sudah tahu bahwa kita bisa membuat tabel kecil. Hal berikutnya yang harus dilakukan adalah mendapatkan fungsi pencarian di tempat. Fungsi pencarian biasanya adalah fungsi kecil yang menggunakan beberapa operasi integer dasar (dan, atau, xor, shift, tambah, hapus, dan mungkin gandakan). Anda ingin agar input Anda diterjemahkan oleh fungsi pencarian ke semacam 'kunci unik' di tabel Anda, yang kemudian hanya memberi Anda jawaban dari semua pekerjaan yang Anda inginkan.

Dalam hal ini:> = 128 berarti kita dapat menyimpan nilainya, <128 berarti kita membuangnya. Cara termudah untuk melakukannya adalah dengan menggunakan 'DAN': jika kita menyimpannya, kita DAN itu dengan 7FFFFFFF; jika kita ingin menyingkirkannya, kita DAN itu dengan 0. Perhatikan juga bahwa 128 adalah kekuatan 2 - jadi kita dapat melanjutkan dan membuat tabel 32768/128 bilangan bulat dan mengisinya dengan nol dan banyak 7FFFFFFFF's.

Bahasa yang dikelola

Anda mungkin bertanya-tanya mengapa ini bekerja dengan baik dalam bahasa yang dikelola. Lagipula, bahasa yang dikelola memeriksa batas-batas array dengan cabang untuk memastikan Anda tidak mengacaukan ...

Ya, tidak persis ... :-)

Ada beberapa upaya untuk menghilangkan cabang ini untuk bahasa yang dikelola. Sebagai contoh:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

Dalam kasus ini, jelas bagi kompiler bahwa kondisi batas tidak akan pernah mengenai. Setidaknya kompiler Microsoft JIT (tapi saya berharap Java melakukan hal serupa) akan melihat ini dan menghapus centangnya sama sekali. WOW, itu berarti tidak ada cabang. Demikian pula, ia akan menangani kasus-kasus nyata lainnya.

Jika Anda mengalami masalah dengan pencarian dalam bahasa yang dikelola - kuncinya adalah menambahkan & 0x[something]FFF ke fungsi pencarian Anda untuk membuat pemeriksaan batas dapat diprediksi - dan melihatnya berjalan lebih cepat.

Hasil dari kasus ini

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
1247
atlaste

Karena data didistribusikan antara 0 dan 255 ketika array diurutkan, sekitar paruh pertama iterasi tidak akan memasukkan pernyataan if- (pernyataan if dibagikan di bawah).

if (data[c] >= 128)
    sum += data[c];

Pertanyaannya adalah: Apa yang membuat pernyataan di atas tidak dieksekusi dalam kasus-kasus tertentu seperti dalam kasus data yang diurutkan? Di sinilah "prediktor cabang". Prediktor cabang adalah sirkuit digital yang mencoba menebak ke arah mana cabang (mis. Struktur if-then-else) akan berjalan sebelum ini diketahui dengan pasti. Tujuan dari prediktor cabang adalah untuk meningkatkan aliran dalam pipa instruksi. Prediktor cabang memainkan peran penting dalam mencapai kinerja efektif tinggi!

Mari kita lakukan beberapa tanda bangku untuk memahaminya dengan lebih baik

Kinerja pernyataan if- tergantung pada apakah kondisinya memiliki pola yang dapat diprediksi. Jika kondisi selalu benar atau selalu salah, logika prediksi cabang dalam prosesor akan mengambil pola. Di sisi lain, jika polanya tidak dapat diprediksi, pernyataan if- akan jauh lebih mahal.

Mari kita ukur kinerja loop ini dengan kondisi berbeda:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Berikut adalah timing dari loop dengan pola true-false yang berbeda:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

Pola " buruk " true-false dapat membuat pernyataan if- hingga enam kali lebih lambat daripada pola " baik "! Tentu saja, pola mana yang baik dan mana yang buruk tergantung pada instruksi yang tepat yang dihasilkan oleh kompiler dan pada prosesor tertentu.

Jadi tidak ada keraguan tentang dampak prediksi cabang terhadap kinerja!

1118
Saqlain

Salah satu cara untuk menghindari kesalahan prediksi cabang adalah membangun tabel pencarian, dan mengindeksnya menggunakan data. Stefan de Bruijn mendiskusikan hal itu dalam jawabannya.

Tetapi dalam kasus ini, kita tahu nilai berada dalam kisaran [0, 255] dan kita hanya peduli dengan nilai> = 128. Itu berarti kita dapat dengan mudah mengekstraksi bit tunggal yang akan memberi tahu kita apakah kita menginginkan nilai atau tidak: dengan menggeser data ke 7 bit yang tepat, kita dibiarkan dengan 0 bit atau 1 bit, dan kita hanya ingin menambahkan nilai ketika kita memiliki 1 bit. Sebut saja bit ini "bit keputusan".

Dengan menggunakan nilai 0/1 dari bit keputusan sebagai indeks ke dalam array, kita dapat membuat kode yang akan sama cepatnya apakah data diurutkan atau tidak diurutkan. Kode kami akan selalu menambah nilai, tetapi ketika bit keputusan adalah 0, kami akan menambahkan nilai di tempat yang tidak kami pedulikan. Ini kodenya:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Kode ini menghabiskan setengah dari tambahan tetapi tidak pernah mengalami kegagalan prediksi cabang. Ini jauh lebih cepat pada data acak daripada versi dengan pernyataan if aktual.

Tetapi dalam pengujian saya, tabel pencarian eksplisit sedikit lebih cepat dari ini, mungkin karena pengindeksan ke tabel pencarian sedikit lebih cepat daripada sedikit pergeseran. Ini menunjukkan bagaimana kode saya mengatur dan menggunakan tabel pencarian (tidak terbayangkan disebut lut untuk "Tabel Pencarian" dalam kode). Berikut kode C++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

Dalam hal ini, tabel pencarian hanya 256 byte, sehingga sangat cocok dalam cache dan semuanya cepat. Teknik ini tidak akan bekerja dengan baik jika datanya bernilai 24-bit dan kami hanya ingin setengah dari mereka ... tabel pencarian akan terlalu besar untuk praktis. Di sisi lain, kita bisa menggabungkan dua teknik yang ditunjukkan di atas: pertama-tama pindahkan bit, lalu indeks tabel pencarian. Untuk nilai 24-bit yang kami inginkan hanya nilai setengah atas, kami berpotensi menggeser data dengan 12 bit, dan dibiarkan dengan nilai 12-bit untuk indeks tabel. Indeks tabel 12-bit menyiratkan tabel nilai 4096, yang mungkin praktis.

Teknik pengindeksan ke dalam array, alih-alih menggunakan pernyataan if, dapat digunakan untuk memutuskan pointer mana yang akan digunakan. Saya melihat perpustakaan yang mengimplementasikan pohon biner, dan alih-alih memiliki dua pointer bernama (pLeft dan pRight atau apa pun) memiliki array panjang-2 pointer dan menggunakan teknik "decision bit" untuk memutuskan mana yang akan diikuti. Misalnya, alih-alih:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

perpustakaan ini akan melakukan sesuatu seperti:

i = (x < node->value);
node = node->link[i];

Berikut tautan ke kode ini: Red Black Trees , Eternally Confuzzled

1039
steveha

Dalam kasus yang diurutkan, Anda dapat melakukan lebih baik daripada mengandalkan prediksi cabang yang sukses atau trik perbandingan tanpa cabang: hapus cabang sepenuhnya.

Memang, array dipartisi dalam zona yang berdekatan dengan data < 128 dan lainnya dengan data >= 128. Jadi, Anda harus menemukan titik partisi dengan pencarian dikotomik (menggunakan perbandingan Lg(arraySize) = 15), kemudian lakukan akumulasi langsung dari titik itu.

Sesuatu seperti (tidak dicentang)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

atau, sedikit lebih dikaburkan

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Pendekatan yang lebih cepat, yang memberikan perkiraan solusi untuk diurutkan atau tidak disortir adalah: sum= 3137536; (dengan asumsi distribusi yang benar-benar seragam, 1.638 sampel dengan nilai yang diharapkan 191.5) :-)

942
Yves Daoust

Perilaku di atas terjadi karena prediksi Cabang.

Untuk memahami prediksi cabang, orang harus terlebih dahulu memahami Pipa Instruksi :

Setiap instruksi dipecah menjadi urutan langkah-langkah sehingga langkah-langkah yang berbeda dapat dijalankan bersamaan secara paralel. Teknik ini dikenal sebagai pipa instruksi dan ini digunakan untuk meningkatkan throughput pada prosesor modern. Untuk memahami ini dengan lebih baik, silakan lihat ini contoh di Wikipedia .

Secara umum, prosesor modern memiliki jaringan pipa yang cukup panjang, tetapi untuk kemudahan mari kita pertimbangkan 4 langkah ini saja.

  1. JIKA - Ambil instruksi dari memori
  2. ID - Decode instruksi
  3. EX - Jalankan instruksi
  4. WB - Tulis kembali ke register CPU

pipa 4-tahap secara umum untuk 2 instruksi. 4-stage pipeline in general

Kembali ke pertanyaan di atas, mari pertimbangkan petunjuk berikut:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Tanpa prediksi cabang, berikut ini akan terjadi:

Untuk menjalankan instruksi B atau instruksi C prosesor harus menunggu sampai instruksi A tidak mencapai sampai tahap EX dalam pipa, karena keputusan untuk pergi ke instruksi B atau instruksi C tergantung pada hasil instruksi A. Jadi pipa akan terlihat seperti ini.

ketika jika kondisi mengembalikan true: enter image description here

Ketika jika kondisi kembali salah: enter image description here

Sebagai hasil dari menunggu hasil instruksi A, total siklus CPU yang dihabiskan dalam kasus di atas (tanpa prediksi cabang; untuk benar dan salah) adalah 7.

Jadi, apa prediksi cabang?

Prediktor cabang akan mencoba menebak ke arah mana cabang (struktur if-then-else) akan berjalan sebelum ini diketahui dengan pasti. Itu tidak akan menunggu instruksi A untuk mencapai tahap EX dari pipeline, tetapi akan menebak keputusan dan pergi ke instruksi itu (B atau C dalam contoh kita).

Dalam hal dugaan yang benar, pipeline terlihat seperti ini: enter image description here

Jika kemudian terdeteksi bahwa tebakan itu salah maka instruksi yang dieksekusi sebagian dibuang dan pipa memulai kembali dengan cabang yang benar, menimbulkan penundaan. Waktu yang terbuang untuk misprediksi cabang sama dengan jumlah tahapan dalam pipa dari tahap pengambilan ke tahap eksekusi. Mikroprosesor modern cenderung memiliki jaringan pipa yang cukup panjang sehingga penundaan kesalahan prediksi adalah antara 10 dan 20 siklus clock. Semakin lama pipa semakin besar kebutuhan untuk cabang yang bagus .

Dalam kode OP, pertama kali ketika bersyarat, prediktor cabang tidak memiliki informasi untuk mendasarkan prediksi, sehingga pertama kali secara acak akan memilih instruksi berikutnya. Kemudian dalam for loop, ini dapat mendasarkan prediksi pada histori. Untuk array yang diurutkan dalam urutan menaik, ada tiga kemungkinan:

  1. Semua elemen kurang dari 128
  2. Semua elemen lebih besar dari 128
  3. Beberapa elemen baru mulai kurang dari 128 dan kemudian menjadi lebih besar dari 128

Mari kita asumsikan bahwa prediktor akan selalu menganggap cabang yang benar pada putaran pertama.

Jadi dalam kasus pertama, ia akan selalu mengambil cabang yang benar karena secara historis semua prediksinya benar. Dalam kasus ke-2, awalnya ini akan memprediksi yang salah, tetapi setelah beberapa iterasi, ia akan memprediksi dengan benar. Dalam kasus ke-3, awalnya akan diprediksi dengan benar sampai elemen kurang dari 128. Setelah itu akan gagal untuk beberapa waktu dan memperbaiki sendiri ketika melihat kegagalan prediksi cabang dalam sejarah.

Dalam semua kasus ini, kegagalannya akan terlalu sedikit jumlahnya dan sebagai hasilnya, hanya beberapa kali ia harus membuang instruksi yang dieksekusi sebagian dan memulai kembali dengan cabang yang benar, menghasilkan siklus CPU yang lebih sedikit.

Tetapi dalam kasus array acak yang tidak disortir, prediksi perlu membuang instruksi yang dieksekusi sebagian dan memulai kembali dengan cabang yang benar sebagian besar waktu dan menghasilkan siklus CPU lebih banyak dibandingkan dengan array yang diurutkan.

765
Harsh Sharma

Jawaban resmi akan dari

  1. Intel - Menghindari Biaya Misprediksi Cabang
  2. Intel - Reorganisasi Cabang dan Loop untuk Mencegah Mispredicts
  3. Makalah ilmiah - arsitektur komputer prediksi cabang
  4. Buku: J.L. Hennessy, D.A. Patterson: Arsitektur komputer: pendekatan kuantitatif
  5. Artikel dalam publikasi ilmiah: T.Y. Yeh, Y.N. Patt membuat banyak dari ini berdasarkan prediksi cabang.

Anda juga dapat melihat dari diagram diagram yang indah ini mengapa prediktor cabang bingung.

 2-bit state diagram

Setiap elemen dalam kode asli adalah nilai acak

data[c] = std::Rand() % 256;

sehingga prediktor akan berubah sisi saat std::Rand() berhembus.

Di sisi lain, setelah itu diurutkan, prediktor yang akan pertama pindah ke keadaan sangat tidak diambil dan ketika nilai-nilai berubah dengan nilai tinggi prediktor yang akan di tiga kali melalui perubahan sepanjang jalan dari sangat tidak dibawa ke kuat diambil.


669
Surt

Di baris yang sama (saya pikir ini tidak disorot oleh jawaban apa pun) ada baiknya menyebutkan bahwa kadang-kadang (khususnya dalam perangkat lunak di mana kinerja penting — seperti di kernel Linux) Anda dapat menemukan beberapa pernyataan if seperti berikut:

if (likely( everything_is_ok ))
{
    /* Do something */
}

atau serupa:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Baik likely() dan unlikely() sebenarnya adalah makro yang didefinisikan dengan menggunakan sesuatu seperti __builtin_expect GCC untuk membantu kompiler memasukkan kode prediksi untuk mendukung kondisi dengan mempertimbangkan informasi yang diberikan oleh pengguna. GCC mendukung builtin lain yang dapat mengubah perilaku program yang sedang berjalan atau memancarkan instruksi tingkat rendah seperti membersihkan cache, dll. Lihat dokumentasi ini yang melewati builtins GCC yang tersedia.

Biasanya optimasi semacam ini terutama ditemukan dalam aplikasi waktu nyata yang sulit atau sistem embedded di mana waktu eksekusi sangat penting dan sangat penting. Misalnya, jika Anda memeriksa beberapa kondisi kesalahan yang hanya terjadi 1/10000000 kali, lalu mengapa tidak memberi tahu kompilator tentang hal ini? Dengan cara ini, secara default, prediksi cabang akan menganggap bahwa kondisinya salah.

634
rkachach

Operasi Boolean yang sering digunakan dalam C++ menghasilkan banyak cabang dalam program yang dikompilasi. Jika cabang-cabang ini berada di dalam loop dan sulit untuk diprediksi, mereka dapat memperlambat eksekusi secara signifikan. Variabel Boolean disimpan sebagai bilangan bulat 8-bit dengan nilai 0 untuk false dan 1 untuk true.

Variabel Boolean terlalu ditentukan dalam arti bahwa semua operator yang memiliki variabel Boolean sebagai input memeriksa apakah input memiliki nilai lain selain 0 atau 1, tetapi operator yang memiliki Boolean sebagai output tidak dapat menghasilkan nilai selain 0 atau 1. Ini membuat operasi dengan variabel Boolean sebagai input kurang efisien daripada yang diperlukan. Pertimbangkan contoh:

bool a, b, c, d;
c = a && b;
d = a || b;

Ini biasanya diterapkan oleh kompiler dengan cara berikut:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Kode ini jauh dari optimal. Cabang mungkin membutuhkan waktu lama jika salah duga. Operasi Boolean dapat dibuat jauh lebih efisien jika diketahui dengan pasti bahwa operan tidak memiliki nilai selain 0 dan 1. Alasan mengapa kompiler tidak membuat asumsi seperti itu adalah bahwa variabel mungkin memiliki nilai lain jika tidak diinisialisasi atau berasal dari sumber yang tidak diketahui. Kode di atas dapat dioptimalkan jika a dan b telah diinisialisasi ke nilai yang valid atau jika berasal dari operator yang menghasilkan output Boolean. Kode yang dioptimalkan terlihat seperti ini:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char digunakan sebagai ganti bool untuk memungkinkannya menggunakan operator bitwise (& dan |) alih-alih operator Boolean (&& dan ||). Operator bitwise adalah instruksi tunggal yang hanya membutuhkan satu siklus clock. OR operator (|) berfungsi bahkan jika a dan b memiliki nilai lain selain 0 atau 1. Operator AND (&) dan operator EKSKLUSIF OR (^) dapat memberikan hasil yang tidak konsisten jika operan memiliki nilai selain 0 dan 1.

~ tidak dapat digunakan untuk TIDAK. Sebagai gantinya, Anda bisa membuat Boolean TIDAK pada variabel yang dikenal sebagai 0 atau 1 dengan XOR'ing dengan 1:

bool a, b;
b = !a;

dapat dioptimalkan untuk:

char a = 0, b;
b = a ^ 1;

a && b tidak dapat diganti dengan a & b jika b adalah ekspresi yang tidak boleh dievaluasi jika a adalah false (&& tidak akan mengevaluasi b, & akan). Demikian juga, a || b tidak dapat diganti dengan a | b jika b adalah ekspresi yang tidak boleh dievaluasi jika a adalah true.

Menggunakan operator bitwise lebih menguntungkan jika operan adalah variabel daripada jika operan adalah perbandingan:

bool a; double x, y, z;
a = x > y && z < 5.0;

optimal dalam banyak kasus (kecuali Anda mengharapkan ekspresi && untuk menghasilkan banyak kesalahan prediksi cabang).

603
Maciej

Itu sudah pasti!...

Prediksi cabang membuat logika berjalan lebih lambat, karena pergantian yang terjadi dalam kode Anda! Ini seperti Anda akan jalan lurus atau jalan dengan banyak belokan, pasti yang lurus akan dilakukan lebih cepat! ...

Jika array diurutkan, kondisi Anda salah pada langkah pertama: data[c] >= 128, kemudian menjadi nilai sebenarnya untuk keseluruhan jalan ke ujung jalan. Begitulah cara Anda mencapai akhir logika lebih cepat. Di sisi lain, menggunakan array yang tidak disortir, Anda perlu banyak proses dan pembalikan yang membuat kode Anda berjalan lebih lambat pasti ...

Lihatlah gambar yang saya buat untuk Anda di bawah ini. Jalan mana yang akan selesai lebih cepat?

 Branch Prediction

Jadi secara pemrograman, prediksi cabang menyebabkan proses menjadi lebih lambat ...

Pada akhirnya, ada baiknya mengetahui bahwa kami memiliki dua jenis prediksi cabang yang masing-masing akan memengaruhi kode Anda secara berbeda:

1. Statis

2. Dinamis

 Branch Prediction

Prediksi cabang statis digunakan oleh mikroprosesor saat pertama kali cabang bersyarat ditemukan, dan prediksi cabang dinamis digunakan untuk keberhasilan eksekusi kode cabang bersyarat.

Agar dapat menulis kode Anda secara efektif untuk memanfaatkan aturan-aturan ini, ketika menulis jika-lain atau beralih pernyataan, periksa kasus yang paling umum terlebih dahulu dan bekerja secara progresif ke yang paling umum. Loop tidak selalu memerlukan urutan kode khusus untuk prediksi cabang statis, karena hanya kondisi loop iterator yang biasanya digunakan.

280
Alireza

Pertanyaan ini telah dijawab berulang kali dengan sangat baik. Masih saya ingin menarik perhatian kelompok untuk analisis menarik lainnya.

Baru-baru ini contoh ini (dimodifikasi sangat sedikit) juga digunakan sebagai cara untuk menunjukkan bagaimana sepotong kode dapat diprofilkan dalam program itu sendiri pada Windows. Sepanjang jalan, penulis juga menunjukkan bagaimana menggunakan hasil untuk menentukan di mana kode menghabiskan sebagian besar waktunya baik dalam kasus diurutkan & tidak disortir. Akhirnya karya ini juga menunjukkan bagaimana menggunakan fitur HAL (Hardware Abstraction Layer) yang sedikit diketahui untuk menentukan berapa banyak kesalahan prediksi cabang yang terjadi dalam kasus yang tidak disortir.

Tautannya ada di sini: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

262
ForeverLearning

Seperti yang telah disebutkan oleh orang lain, apa yang ada di balik misterinya adalah Branch Predictor .

Saya tidak mencoba menambahkan sesuatu tetapi menjelaskan konsepnya dengan cara lain. Ada pengantar singkat tentang wiki yang berisi teks dan diagram. Saya suka penjelasan di bawah ini yang menggunakan diagram untuk menguraikan Prediktor Cabang secara intuitif.

Dalam arsitektur komputer, prediktor cabang adalah sirkuit digital yang mencoba menebak ke arah mana cabang (mis. Struktur if-then-else) akan berjalan sebelum ini diketahui dengan pasti. Tujuan dari prediktor cabang adalah untuk meningkatkan aliran dalam pipa instruksi. Prediktor cabang memainkan peran penting dalam mencapai kinerja efektif tinggi di banyak arsitektur mikroprosesor pipelined modern seperti x86.

Percabangan dua arah biasanya diterapkan dengan instruksi lompat bersyarat. Lompatan bersyarat dapat "tidak diambil" dan melanjutkan eksekusi dengan cabang kode pertama yang mengikuti segera setelah lompatan bersyarat, atau dapat "diambil" dan melompat ke tempat yang berbeda dalam memori program di mana cabang kode kedua adalah disimpan. Tidak diketahui secara pasti apakah lompatan bersyarat akan diambil atau tidak diambil sampai kondisinya telah dihitung dan lompatan bersyarat telah melewati tahap eksekusi dalam pipa instruksi (lihat gbr. 1).

 figure 1

Berdasarkan skenario yang dijelaskan, saya telah menulis demo animasi untuk menunjukkan bagaimana instruksi dieksekusi dalam pipa dalam situasi yang berbeda.

  1. Tanpa Prediktor Cabang.

Tanpa prediksi cabang, prosesor harus menunggu sampai instruksi melompat bersyarat telah melewati tahap eksekusi sebelum instruksi berikutnya dapat memasuki tahap pengambilan di dalam pipa.

Contoh berisi tiga instruksi dan yang pertama adalah instruksi melompat bersyarat. Dua instruksi terakhir dapat masuk ke dalam pipa sampai instruksi lompat bersyarat dijalankan.

 without branch predictor

Diperlukan 9 siklus clock agar 3 instruksi dapat diselesaikan.

  1. Gunakan Branch Predictor dan jangan melakukan lompatan bersyarat. Mari kita asumsikan bahwa prediksi adalah bukan mengambil lompatan bersyarat.

 enter image description here

Diperlukan 7 siklus clock agar 3 instruksi dapat diselesaikan.

  1. Gunakan Branch Predictor dan lakukan lompatan bersyarat. Mari kita asumsikan bahwa prediksi adalah bukan mengambil lompatan bersyarat.

 enter image description here

Diperlukan 9 siklus clock agar 3 instruksi dapat diselesaikan.

Waktu yang terbuang untuk misprediksi cabang sama dengan jumlah tahapan dalam pipa dari tahap pengambilan ke tahap eksekusi. Mikroprosesor modern cenderung memiliki jaringan pipa yang cukup panjang sehingga penundaan kesalahan prediksi adalah antara 10 dan 20 siklus clock. Akibatnya, membuat saluran pipa lebih lama meningkatkan kebutuhan untuk prediktor cabang yang lebih maju.

Seperti yang Anda lihat, sepertinya kami tidak punya alasan untuk tidak menggunakan Branch Predictor.

Ini adalah demo sederhana yang menjelaskan bagian paling mendasar dari Predictor Cabang. Jika gif-gif itu menyebalkan, silakan menghapusnya dari jawaban dan pengunjung juga bisa mendapatkan demo dari git

176
Gearon

Keuntungan prediksi cabang!

Penting untuk dipahami bahwa misprediksi cabang tidak memperlambat program. Biaya prediksi yang terlewatkan adalah seolah-olah prediksi cabang tidak ada dan Anda menunggu evaluasi ekspresi untuk memutuskan kode apa yang akan dijalankan (penjelasan lebih lanjut pada paragraf berikutnya).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Setiap kali ada pernyataan if-else\switch, ekspresi harus dievaluasi untuk menentukan blok mana yang harus dieksekusi. Dalam kode Majelis yang dihasilkan oleh kompiler, instruksi branch bersyarat dimasukkan.

Instruksi cabang dapat menyebabkan komputer mulai mengeksekusi urutan instruksi yang berbeda dan dengan demikian menyimpang dari perilaku default dari mengeksekusi instruksi secara berurutan (yaitu jika ekspresi salah, program melewatkan kode blok if) tergantung pada beberapa kondisi, yang adalah evaluasi ekspresi dalam kasus kami.

Yang sedang berkata, kompilator mencoba untuk memprediksi hasil sebelum benar-benar dievaluasi. Ini akan mengambil instruksi dari blok if, dan jika ekspresi ternyata benar, maka hebat! Kami memperoleh waktu yang dibutuhkan untuk mengevaluasinya dan membuat kemajuan dalam kode; jika tidak maka kita menjalankan kode yang salah, pipa disiram, dan blok yang benar dijalankan.

Visualisasi:

Katakanlah Anda harus memilih rute 1 atau rute 2. Menunggu pasangan Anda memeriksa peta, Anda telah berhenti di ## dan menunggu, atau Anda bisa memilih route1 dan jika Anda beruntung (rute 1 adalah rute yang benar), maka hebatnya Anda tidak perlu menunggu pasangan Anda memeriksa peta (Anda menghemat waktu yang diperlukan untuk memeriksa peta), jika tidak, Anda hanya akan kembali.

Sementara pipa pembilasan sangat cepat, saat ini pertaruhan ini tidak sia-sia. Memprediksi data yang diurutkan atau data yang berubah lambat selalu lebih mudah dan lebih baik daripada memprediksi perubahan cepat.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
168
Tony Tannous

Ini tentang prediksi cabang. Apa itu?

  • Prediktor cabang adalah salah satu teknik peningkatan kinerja kuno yang masih menemukan relevansi dengan arsitektur modern. Sementara teknik prediksi sederhana memberikan pencarian cepat dan efisiensi daya, mereka menderita tingkat kesalahan prediksi yang tinggi.

  • Di sisi lain, prediksi cabang yang kompleks - baik berdasarkan neural atau varian dari prediksi cabang dua tingkat - memberikan akurasi prediksi yang lebih baik, tetapi mereka mengkonsumsi lebih banyak kekuatan dan kompleksitas yang meningkat secara eksponensial.

  • Selain itu, dalam teknik prediksi yang kompleks waktu yang dibutuhkan untuk memprediksi cabang itu sendiri sangat tinggi - mulai dari 2 hingga 5 siklus - yang sebanding dengan waktu pelaksanaan cabang yang sebenarnya.

  • Prediksi cabang pada dasarnya adalah masalah optimasi (minimalisasi) di mana penekanannya adalah pada untuk mencapai tingkat kesalahan serendah mungkin, konsumsi daya yang rendah, dan kompleksitas yang rendah dengan sumber daya minimum.

Ada tiga jenis cabang:

Meneruskan cabang bersyarat - berdasarkan kondisi run-time, PC (penghitung program) diubah untuk menunjuk ke sebuah alamat yang diteruskan dalam aliran instruksi.

Cabang conditional mundur - PC diubah ke titik mundur dalam aliran instruksi. Cabang didasarkan pada beberapa kondisi, seperti bercabang mundur ke awal loop program ketika tes di akhir loop menyatakan loop harus dieksekusi lagi.

Cabang tanpa syarat - ini termasuk lompatan, panggilan prosedur dan pengembalian yang tidak memiliki kondisi khusus. Misalnya, instruksi lompatan tanpa syarat dapat dikodekan dalam bahasa Assembly hanya sebagai "jmp", dan aliran instruksi harus segera diarahkan ke lokasi target yang ditunjuk oleh instruksi lompat, sedangkan lompatan kondisional yang mungkin dikodekan sebagai "jmpne" akan mengarahkan aliran instruksi hanya jika hasil perbandingan dua nilai dalam instruksi "bandingkan" sebelumnya menunjukkan nilai-nilai tidak sama. (Skema pengalamatan tersegmentasi yang digunakan oleh arsitektur x86 menambah kompleksitas tambahan, karena lompatan dapat berupa "dekat" (dalam suatu segmen) atau "jauh" (di luar segmen). Setiap jenis memiliki efek yang berbeda pada algoritma prediksi cabang.)

Prediksi Cabang Statis/dinamis : Prediksi cabang statik digunakan oleh mikroprosesor saat cabang kondisional pertama kali ditemui, dan prediksi cabang dinamis digunakan untuk keberhasilan eksekusi kode cabang bersyarat.

Referensi:

113
Farhad

Selain fakta bahwa prediksi cabang dapat memperlambat Anda, array yang diurutkan memiliki keuntungan lain:

Anda dapat memiliki kondisi berhenti alih-alih hanya memeriksa nilainya, dengan cara ini Anda hanya mengulang data yang relevan, dan mengabaikan sisanya.
Prediksi cabang hanya akan meleset satu kali.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
107
Yochai Timmer

Pada ARM, tidak diperlukan cabang, karena setiap instruksi memiliki bidang kondisi 4-bit, yang diuji dengan biaya nol. Ini menghilangkan kebutuhan untuk cabang pendek, dan tidak akan ada prediksi cabang hit. Oleh karena itu, versi yang disortir akan berjalan lebih lambat daripada versi yang tidak disortir pada ARM, karena biaya tambahan penyortiran. Lingkaran dalam akan terlihat seperti berikut:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize
103
Luke Hutchison

Array yang diurutkan diproses lebih cepat daripada array yang tidak disortir, karena fenomena yang disebut prediksi cabang.

Prediktor cabang adalah sirkuit digital (dalam arsitektur komputer) yang mencoba memprediksi ke arah mana cabang akan bergerak, meningkatkan aliran dalam pipa instruksi. Sirkuit/komputer memprediksi langkah selanjutnya dan menjalankannya.

Membuat prediksi yang salah mengarah ke kembali ke langkah sebelumnya, dan mengeksekusi dengan prediksi lain. Dengan asumsi prediksi itu benar, kode akan melanjutkan ke langkah berikutnya. Prediksi yang salah menghasilkan pengulangan langkah yang sama, sampai prediksi yang benar terjadi.

Jawaban atas pertanyaan Anda sangat sederhana.

Dalam array yang tidak disortir, komputer membuat beberapa prediksi, yang mengarah ke peningkatan kemungkinan kesalahan. Padahal, diurutkan, komputer membuat lebih sedikit prediksi mengurangi kemungkinan kesalahan. Membuat prediksi lebih banyak membutuhkan lebih banyak waktu.

Array yang Diurutkan: Jalan Lurus

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Array yang Tidak Disortir: Jalan Melengkung

______   ________
|     |__|

Prediksi cabang: Menebak/memprediksi jalan mana yang lurus dan mengikutinya tanpa memeriksa

___________________________________________ Straight road
 |_________________________________________|Longer road

Meskipun kedua jalan mencapai tujuan yang sama, jalan lurus lebih pendek, dan yang lainnya lebih panjang. Jika kemudian Anda memilih yang lain karena kesalahan, tidak ada jalan untuk kembali, dan karenanya Anda akan membuang waktu ekstra jika Anda memilih jalan yang lebih panjang. Ini mirip dengan apa yang terjadi di komputer, dan saya harap ini membantu Anda memahami lebih baik.


Saya juga ingin mengutip @Simon_Weaver dari komentar:

Itu tidak membuat prediksi lebih sedikit - itu membuat lebih sedikit prediksi yang salah. Masih harus memprediksi untuk setiap kali melalui loop ..

92
Omkaar.K

Asumsi oleh jawaban lain bahwa seseorang perlu mengurutkan data tidak benar.

Kode berikut ini tidak mengurutkan seluruh array, tetapi hanya segmen 200 elemen, dan dengan demikian berjalan tercepat.

Mengurutkan hanya bagian k-elemen yang menyelesaikan pra-pemrosesan dalam waktu linier daripada n.log(n).

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::Rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Ini juga "membuktikan" bahwa itu tidak ada hubungannya dengan masalah algoritmik seperti urutan, dan memang prediksi cabang.

14
user2297550

Karena diurutkan!

Sangat mudah untuk mengambil dan memanipulasi data yang dipesan daripada yang tidak diurutkan.

Persis seperti bagaimana saya memilih pakaian dari toko (dipesan) dan dari lemari pakaian saya (berantakan).

0
Arun Joshla