Baris utama versus Kolom tata letak utama matriks

16

Dalam pemrograman perhitungan matriks padat, apakah ada alasan untuk memilih tata letak baris-utama dari lebih dari tata letak kolom-utama?

Saya tahu bahwa tergantung pada tata letak matriks yang dipilih, kita perlu menulis kode yang sesuai untuk menggunakan memori cache secara efektif untuk keperluan kecepatan.

Tata letak baris-utama tampaknya lebih alami dan lebih sederhana (setidaknya bagi saya). Tetapi perpustakaan utama seperti LAPACK yang ditulis dalam Fortran menggunakan tata letak kolom utama, jadi pasti ada alasan untuk membuat pilihan ini.

smilingbuddha
sumber
Jika kita mempertimbangkan komputasi b = A * x dengan vektor kolom x, untuk baris-mayor A kita dapat menggunakan produk dalam vektor, A (i,:) ^ T x untuk mendapatkan b (i); untuk kolom-mayor kita hanya perlu vektor pengali skalar, sum_i A (:, i) x (i). Menurut saya kolom utama jauh lebih baik! Bagaimana menurut anda?
Hui Zhang
Latih diri Anda untuk menyukai kolom-utama. Sangat mudah ketika Anda memvisualisasikan vektor sebagai kolom, atau transposisi mereka sebagai baris. Itu membuat visualisasi perkalian matriks sangat sederhana, dan membuatnya mudah untuk mengikuti banyak matematika yang diterbitkan.
Mike Dunlavey

Jawaban:

18

Layout utama kolom adalah skema yang digunakan oleh Fortran dan itulah mengapa itu digunakan di LAPACK dan perpustakaan lain.

Secara umum itu jauh lebih efisien dalam hal penggunaan bandwidth memori dan kinerja cache untuk mengakses elemen-elemen dari array dalam urutan di mana mereka diletakkan dalam memori. Bergantung pada bagaimana matriks Anda disimpan, ada baiknya Anda memilih algoritma yang memanfaatkan ini.

penyimpanan internal Penyimpanan internal format utama kolom

Brian Borchers
sumber
11

Dalam ruang hampa tanpa mempertimbangkan perangkat lunak yang ada, tidak ada alasan untuk memilih kolom utama daripada baris utama dari sudut pandang kode. Namun, sebagian besar literatur matematika ditulis dengan cara yang mengelompokkan vektor ke dalam matriks dengan menyimpannya sebagai kolom, bukan baris. Misalnya ketika Anda menulis persamaan nilai eigen lengkap , XSEBUAHX=XΛXmatrix berisi semua vektor eigen yang dituliskan dalam kolom. Anda tidak pernah benar-benar melihatnya ditulis dengan cara lain (walaupun saya mendengar bahwa orang-orang statistik menyukai vektor baris). Oleh karena itu, wajar jika perangkat lunak paling awal mengasumsikan format utama kolom sehingga jika Anda memiliki matriks yang merupakan kumpulan vektor, penyimpanan setiap vektor tunggal berdekatan. Jadi, saya membayangkan bahwa tradisi baru saja diteruskan ke masa kini, dan jika Anda ingin berinteraksi dengan Fortran ye olde, Anda ingin menggunakan kolom utama. Jadi hampir semua aljabar linear numerik yang sangat efisien dilakukan dalam kolom utama.

Alasan C adalah baris utama agak merupakan konsekuensi dari sintaks arraynya; Anda mendeklarasikan array 3 baris dengan 2 kolom sebagai double a[3][2], dan indeks kemudian bervariasi lebih cepat dari indeks sebelumnya, yang untuk array 2D menjadikannya baris utama. Menggabungkan ini dengan urutan pembacaan Barat alami dari kiri ke kanan, itu membuat baris utama tampak lebih alami.

Victor Liu
sumber
2
Saya pikir ini adalah argumen yang buruk. Fakta bahwa indeks terakhir dalam '' double a [3] [2] '' 'bervariasi paling cepat bukanlah suatu kebetulan - itu adalah keputusan desain yang sadar hanya dengan cara yang sama seperti itu adalah keputusan desain sadar di Fortran untuk lakukan sebaliknya jika Anda memiliki larik 'nyata' (3,2) '' '.
Wolfgang Bangerth
1
Selain itu, tidak benar lagi bahwa hampir semua aljabar linear numerik yang sangat efisien adalah kolom utama. Ini mungkin masih berlaku untuk BLAS dan LAPACK, tetapi itu tidak benar sama sekali untuk setiap perpustakaan aljabar linier utama yang telah muncul dalam 15 tahun terakhir: misalnya, baik PETSc dan Trilinos menggunakan baris format penyimpanan matriks jarang utama.
Wolfgang Bangerth
Saya sadar bahwa konvensi C adalah keputusan yang disengaja, mungkin didasarkan pada urutan bacaan alami. Maksud saya mungkin itu tidak dirancang dengan aljabar linear numerik dalam pikiran, menjadikannya kebetulan bahwa itu baris utama. Kedua, saya tidak bermaksud argumen untuk mempertahankan matriks jarang, hanya padat. Untuk jarang, itu sedikit campuran di luar sana, dengan format baris dan kolom terkompresi.
Victor Liu
5
Bukan untuk memperjelas titik, tetapi C pada awalnya adalah bahasa sistem, berdasarkan dari bahasa sebelumnya B dan BCPL, berjalan pada sistem seperti PDP-11 yang awalnya tidak memiliki angka floating point. Untuk mengatakan bahwa mereka mendesainnya dengan angka dalam pikiran adalah hal yang cukup.
Victor Liu
7
Pernah ke sana, dll. Alasan matriks dalam C memindahkan indeks terakhir tercepat adalah karena C tidak memiliki matriks. Ini memiliki vektor vektor, yang dapat diimplementasikan secara transparan sebagai blok memori yang solid, atau sebagai array pointer ke array. Membuat urutan indeks kompatibel dengan Fortran (saya kira) bahkan tidak ada dalam radar Dennis Ritchie.
Mike Dunlavey
2

Tatanan kolom-utama sepertinya lebih alami. Misalnya, jika Anda ingin menyimpan film ke file gambar dengan gambar maka Anda menggunakan urutan kolom, dan itu sangat intuitif dan tidak ada yang akan menyimpannya dalam urutan baris-utama.

Jika Anda seorang programmer di C / C ++ Anda harus menggunakan beberapa pustaka tingkat yang lebih tinggi untuk matriks (Eigen, Armadillo, ...) dengan urutan kolom-utama default. Hanya maniak yang akan menggunakan pointer C mentah dengan urutan baris-utama, meskipun C / C ++ menawarkan sesuatu yang mengingatkan pengindeksan matriks.

Untuk kesederhanaan segala sesuatu dengan tatanan baris-utama harus dianggap sebagai paling tidak terbentuk aneh. Slice by slice adalah tatanan alami dan itu berarti tatanan kolom-utama (seperti Fortran). Ayah / ibu kami memiliki alasan yang sangat bagus mengapa mereka memilihnya.

Sayangnya sebelum menjadi jelas beberapa perpustakaan menarik dibuat dalam urutan baris-utama, mungkin karena kurangnya pengalaman.

Untuk memperjelas mengingat definisi urutan baris-utama di mana indeks kanan bervariasi lebih cepat dalam satu langkah melalui memori misalnya A (x, y, z) itu adalah indeks-z, itu berarti bahwa dalam piksel memori dari irisan yang berbeda berbatasan, apa yang kita inginkan mau. Untuk film A (x, y, t) indeks terakhir adalah waktu t. Tidak sulit membayangkan bahwa tidak mungkin untuk menyimpan film dalam mode baris-utama.

Paul
sumber
2

Pilihan pengindeksan baris-utama / kolom-besar dapat memiliki dampak signifikan pada kinerja karena cara kerja memori dan cache, dan cara beberapa indeks dikonversi menjadi indeks linier. Secara internal, memori adalah larik 1 dimensi tunggal, dan elemen am×n matriks akan disusun secara linear:

  • elemen msaya,j akan disimpan di indeks saya×m+j jika urutan baris-utama digunakan
  • elemen msaya,j akan disimpan di indeks j×n+saya jika pesanan kolom-utama digunakan

Sekarang bayangkan algoritma berikut:

for i from 1 to m
   for j from 1 to n
      do something with m(i,j)

Jika urutan baris-utama digunakan, maka ini akan melintasi semua indeks linier saya×m+jsecara berurutan, menghasilkan lokalitas memori yang baik, sedangkan jika urutan kolom-utama digunakan, maka akses memori berturut-turut akan tersebar di memori. Konsekuensi dapat dramatis terutama ketika memori virtual / swapping memasuki adegan.

Kesimpulan:

  1. ya, itu penting, tetapi pilihannya tergantung pada cara data diakses. Untuk contoh sebelumnya, jika urutan kolom digunakan, yang dapat Anda lakukan hanyalah menukar kedua loop.

  2. aturan praktis: indeks cepat berubah harus dipetakan ke lokasi berturut-turut dalam memori.

  3. lebih penting lagi, mengukur / membandingkan dampak dari pilihan adalah hal yang mendasar, karena itu tergantung pada banyak parameter (ukuran data, ukuran cache, cara bahasa yang digunakan memetakan banyak indeks ke indeks linier, cara operasi sistem mengelola memori virtual, cara loop bersarang di perpustakaan aljabar linier yang Anda gunakan ...)

BrunoLevy
sumber