LAPACK dalam pelayar web anda

Siaran ini pada asalnya diterbitkan di blog Quansight Labs dan telah diubah suai serta diterbitkan semula di sini dengan kebenaran Quansight.

Aplikasi web muncul dengan pantas sebagai sempadan baharu untuk pengiraan saintifik berprestasi tinggi dan pengalaman pengguna akhir yang didayakan AI. Menyokong revolusi ML/AI ialah algebra linear, cabang matematik berkenaan persamaan linear dan perwakilannya dalam ruang vektor dan melalui matriks. LAPACK ("Linear Algebra Package") ialah perpustakaan perisian asas untuk algebra linear berangka, menyediakan pelaksanaan yang teguh dan diuji pertempuran bagi operasi matriks biasa . Walaupun LAPACK merupakan komponen asas bagi kebanyakan bahasa pengaturcaraan pengkomputeran berangka dan pustaka, pelaksanaan LAPACK yang komprehensif dan berkualiti tinggi yang disesuaikan dengan kekangan unik web masih belum menjadi kenyataan. Itulah...sehingga kini.

Awal tahun ini, saya bertuah kerana menjadi pelatih musim panas di Quansight Labs, bahagian manfaat awam Quansight dan peneraju dalam ekosistem Python saintifik. Semasa latihan saya, saya berusaha untuk menambah sokongan LAPACK awal kepada stdlib, perpustakaan asas untuk pengiraan saintifik yang ditulis dalam C dan JavaScript dan dioptimumkan untuk digunakan dalam pelayar web dan persekitaran asli web lain, seperti Node.js dan Deno. Dalam catatan blog ini, saya akan membincangkan perjalanan saya, beberapa cabaran yang dijangka dan tidak dijangka (!), dan jalan di hadapan. Harapan saya ialah kerja ini, dengan sedikit nasib, menyediakan blok binaan yang kritikal dalam menjadikan penyemak imbas web persekitaran kelas pertama untuk pengiraan berangka dan pembelajaran mesin serta menggambarkan masa depan aplikasi web yang didayakan AI yang lebih berkuasa.

Bunyi menarik? Jom!

Apakah stdlib?

Pembaca blog ini yang biasa dengan LAPACK mungkin tidak begitu akrab dengan dunia teknologi web yang liar. Bagi mereka yang datang dari dunia pengiraan berangka dan saintifik dan mempunyai kebiasaan dengan ekosistem Python saintifik, cara paling mudah untuk memikirkan stdlib adalah sebagai perpustakaan pengkomputeran saintifik sumber terbuka dalam acuan NumPy dan SciPy. Ia menyediakan struktur data tatasusunan berbilang dimensi dan rutin yang berkaitan untuk matematik, statistik dan algebra linear, tetapi menggunakan JavaScript, bukannya Python, sebagai bahasa skrip utamanya. Oleh itu, stdlib berfokuskan laser pada ekosistem web dan paradigma pembangunan aplikasinya. Tumpuan ini memerlukan beberapa keputusan reka bentuk dan seni bina projek yang menarik, yang menjadikan stdlib agak unik jika dibandingkan dengan lebih banyak perpustakaan tradisional yang direka untuk pengiraan berangka.

Untuk mengambil NumPy sebagai contoh, NumPy ialah perpustakaan monolitik tunggal, di mana semua komponennya, di luar kebergantungan pihak ketiga pilihan seperti OpenBLAS, membentuk satu unit yang tidak boleh dibahagikan. Seseorang tidak boleh hanya memasang rutin NumPy untuk manipulasi tatasusunan tanpa memasang semua NumPy. Jika anda menggunakan aplikasi yang hanya memerlukan objek ndarray NumPy dan beberapa rutin manipulasinya, memasang dan menggabungkan semua cara NumPy termasuk sejumlah besar "kod mati". Dalam bahasa pembangunan web, kami akan mengatakan bahawa NumPy bukan "pokok boleh goyang". Untuk pemasangan NumPy biasa, ini membayangkan sekurang-kurangnya 30MB ruang cakera dan sekurang-kurangnya 15MB ruang cakera untuk binaan tersuai yang mengecualikan semua pernyataan nyahpepijat. Untuk SciPy, nombor tersebut boleh meningkat kepada 130MB dan 50MB, masing-masing. Tidak perlu dikatakan, penghantaran pustaka 15MB dalam aplikasi web untuk hanya beberapa fungsi adalah bukan permulaan, terutamanya bagi pembangun yang perlu menggunakan aplikasi web ke peranti yang mempunyai ketersambungan rangkaian yang lemah atau kekangan memori.

Memandangkan kekangan unik pembangunan aplikasi web, stdlib mengambil pendekatan bawah ke atas untuk reka bentuknya, di mana setiap unit fungsi boleh dipasang dan digunakan secara bebas daripada bahagian asas kod yang tidak berkaitan dan tidak digunakan. Dengan menerima seni bina perisian boleh reput dan modulariti radikal, stdlib menawarkan pengguna keupayaan untuk memasang dan menggunakan dengan tepat apa yang mereka perlukan, dengan kod yang sedikit atau tiada lebihan melebihi set API yang dikehendaki dan kebergantungan eksplisitnya, sekali gus memastikan jejak memori yang lebih kecil, bundle saiz dan penggunaan yang lebih pantas.

Sebagai contoh, katakan anda bekerja dengan dua tindanan matriks (iaitu, kepingan dua dimensi bagi kiub tiga dimensi), dan anda mahu memilih setiap kepingan lain dan melakukan operasi BLAS biasa y = a * x, dengan x dan y ialah ndarray dan a ialah pemalar skalar. Untuk melakukan ini dengan NumPy, anda perlu memasang semua NumPy
dahulu

pip install numpy

dan kemudian lakukan pelbagai operasi

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Dengan stdlib, selain mempunyai keupayaan untuk memasang projek sebagai perpustakaan monolitik, anda boleh memasang pelbagai unit fungsi sebagai pakej berasingan

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy

dan kemudian lakukan pelbagai operasi

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);

Yang penting, anda bukan sahaja boleh memasang mana-mana satu daripada lebih 4,000 pakej stdlib secara bebas, tetapi anda juga boleh membetulkan, menambah baik dan mengadun semula mana-mana satu daripada pakej tersebut dengan memotong repositori GitHub yang berkaitan (cth., lihat @stdlib/ndarray-fancy ). Dengan mentakrifkan lapisan eksplisit abstraksi dan pokok pergantungan, stdlib menawarkan anda kebebasan untuk memilih lapisan abstraksi yang betul untuk aplikasi anda. Dalam beberapa cara, ia adalah mudah—dan, jika anda terbiasa dengan reka bentuk perpustakaan perisian saintifik konvensional, mungkin idea yang tidak lazim—tetapi, apabila disepadukan rapat dengan platform web, ia mempunyai akibat yang kuat dan mencipta kemungkinan baharu yang menarik!

Bagaimana pula dengan WebAssembly?

Baiklah, jadi mungkin minat anda telah memuncak; stdlib nampaknya menarik. Tetapi apakah kaitan ini dengan LAPACK dalam pelayar web? Nah, salah satu matlamat kami pada musim panas yang lalu adalah untuk menggunakan etos stdlib—pakej yang kecil dan berskop sempit yang melakukan satu perkara dan melakukan satu perkara dengan baik—dalam membawa LAPACK ke web.

Tetapi tunggu, anda berkata! Itu adalah satu usaha yang melampau. LAPACK adalah luas, dengan kira-kira 1,700 rutin, dan melaksanakan walaupun 10% daripadanya dalam jangka masa yang munasabah merupakan satu cabaran yang besar. Bukankah lebih baik untuk menyusun sahaja LAPACK ke WebAssembly, sasaran kompilasi mudah alih untuk bahasa pengaturcaraan seperti C, Go dan Rust, yang membolehkan penggunaan di web dan memanggilnya sehari?

Malangnya, terdapat beberapa isu dengan pendekatan ini.

1. Menyusun Fortran ke WebAssembly masih merupakan bidang pembangunan aktif (lihat 1, 2, 3, 4, dan 5). Pada masa siaran ini, pendekatan biasa ialah menggunakan f2c untuk menyusun Fortran kepada C dan kemudian melakukan langkah kompilasi berasingan untuk menukar C kepada WebAssembly. Walau bagaimanapun, pendekatan ini bermasalah kerana f2c hanya menyokong sepenuhnya Fortran 77, dan kod yang dihasilkan memerlukan tampalan yang meluas. Kerja sedang dijalankan untuk membangunkan pengkompil Fortran berasaskan LLVM, tetapi jurang dan rantai alat yang kompleks kekal.
2. Seperti yang disebut di atas dalam perbincangan mengenai perpustakaan monolitik dalam aplikasi web, keluasan LAPACK adalah sebahagian daripada masalah. Walaupun masalah penyusunan diselesaikan, termasuk satu binari WebAssembly yang mengandungi semua LAPACK dalam aplikasi web yang perlu menggunakan hanya satu atau dua rutin LAPACK bermakna kod mati yang agak besar, menyebabkan masa pemuatan yang lebih perlahan dan penggunaan memori yang meningkat.
3. Walaupun seseorang boleh cuba menyusun rutin LAPACK individu kepada perduaan WebAssembly kendiri, berbuat demikian boleh mengakibatkan kembung binari, kerana berbilang perduaan kendiri mungkin mengandungi kod pendua daripada kebergantungan biasa. Untuk mengurangkan kembung binari, seseorang boleh cuba melakukan pemisahan modul. Dalam senario ini, satu faktor pertama daripada kebergantungan biasa ke dalam binari kendiri yang mengandungi kod kongsi dan kemudian menjana binari berasingan untuk API individu. Walaupun sesuai dalam beberapa kes, ini boleh menjadi sukar digunakan dengan cepat, kerana pendekatan ini memerlukan memautkan modul WebAssembly individu pada masa muat dengan menggabungkan eksport satu atau lebih modul dengan import satu atau lebih modul lain. Ini bukan sahaja boleh membosankan, tetapi pendekatan ini juga memerlukan penalti prestasi kerana fakta bahawa, apabila rutin WebAssembly memanggil eksport yang diimport, mereka kini mesti menyeberang ke dalam JavaScript, dan bukannya kekal dalam WebAssembly. Kompleks bunyi? Ia adalah!
4. Selain daripada modul WebAssembly yang beroperasi secara eksklusif pada argumen input skalar (cth., mengira sinus nombor tunggal), setiap contoh modul WebAssembly mesti dikaitkan dengan memori WebAssembly, yang diperuntukkan dalam kenaikan tetap 64KiB (iaitu, halaman " "). Dan yang penting, pada catatan blog ini, ingatan WebAssembly hanya boleh berkembang dan tidak pernah mengecut. Oleh kerana pada masa ini tiada mekanisme untuk melepaskan memori kepada hos, jejak memori aplikasi WebAssembly hanya boleh meningkat. Kedua-dua aspek ini digabungkan meningkatkan kemungkinan memperuntukkan memori yang tidak pernah digunakan dan kelaziman kebocoran memori.
5. Akhir sekali, walaupun berkuasa, WebAssembly memerlukan keluk pembelajaran yang lebih curam dan set rantai alat yang sering berkembang pesat dan lebih kompleks. Dalam aplikasi pengguna akhir, antara muka antara JavaScript—bahasa pengaturcaraan yang disusun secara dinamik asli web—dan WebAssembly seterusnya membawa kerumitan yang lebih tinggi, terutamanya apabila perlu melaksanakan pengurusan memori manual.

Untuk membantu menggambarkan perkara terakhir, mari kita kembali kepada rutin BLAS daxpy, yang menjalankan operasi y = a*x y dan dengan x dan y ialah vektor berjajak dan pemalar skalar. Jika dilaksanakan dalam C, pelaksanaan asas mungkin kelihatan seperti coretan kod berikut.

pip install numpy

Selepas penyusunan ke WebAssembly dan memuatkan binari WebAssembly ke dalam aplikasi web kami, kami perlu melakukan satu siri langkah sebelum kami boleh memanggil rutin c_daxpy daripada JavaScript. Pertama, kita perlu membuat instantiate modul WebAssembly baharu.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Seterusnya, kita perlu mentakrifkan memori modul dan mencipta contoh modul WebAssembly baharu.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy

Selepas mencipta contoh modul, kami kini boleh menggunakan rutin BLAS yang dieksport. Walau bagaimanapun, jika data ditakrifkan di luar memori modul, kita perlu menyalin data tersebut terlebih dahulu ke contoh memori dan sentiasa melakukannya dalam susunan bait kecil-endian.

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);

Sekarang data ditulis ke memori modul, kita boleh memanggil rutin c_daxpy.

void c_daxpy(const int N, const double alpha, const double *X, const int strideX, double *Y, const int strideY) {
    int ix;
    int iy;
    int i;
    if (N <= 0) {
        return;
    }
    if (alpha == 0.0) {
        return;
    }
    if (strideX < 0) {
        ix = (1-N) * strideX;
    } else {
        ix = 0;
    }
    if (strideY < 0) {
        iy = (1-N) * strideY;
    } else {
        iy = 0;
    }
    for (i = 0; i < N; i++) {
        Y[iy] += alpha * X[ix];
        ix += strideX;
        iy += strideY;
    }
    return;
}

Dan, akhirnya, jika kita perlu menghantar keputusan ke perpustakaan hiliran tanpa sokongan untuk "penunjuk" memori WebAssembly (iaitu, offset bait), seperti D3, untuk visualisasi atau analisis lanjut, kita perlu menyalin data daripada modul ingatan kembali kepada tatasusunan output asal.

const binary = new UintArray([...]);

const mod = new WebAssembly.Module(binary);

Itu banyak kerja hanya untuk mengira y = a*x y. Sebaliknya, bandingkan dengan pelaksanaan JavaScript biasa, yang mungkin kelihatan seperti coretan kod berikut.

// Initialize 10 pages of memory and allow growth to 100 pages:
const mem = new WebAssembly.Memory({
    'initial': 10,  // 640KiB, where each page is 64KiB
    'maximum': 100  // 6.4MiB
});

// Create a new module instance:
const instance = new WebAssembly.Instance(mod, {
    'env': {
        'memory': mem
    }
});

Dengan pelaksanaan JavaScript, kami kemudiannya boleh memanggil terus daxpy dengan data yang ditakrifkan secara luaran kami tanpa pergerakan data yang diperlukan dalam contoh WebAssembly di atas.

// External data:
const xdata = new Float64Array([...]);
const ydata = new Float64Array([...]);

// Specify a vector length:
const N = 5;

// Specify vector strides (in units of elements):
const strideX = 2;
const strideY = 4;

// Define pointers (i.e., byte offsets) for storing two vectors:
const xptr = 0;
const yptr = N * 8; // 8 bytes per double

// Create a DataView over module memory:
const view = new DataView(mem.buffer);

// Resolve the first indexed elements in both `xdata` and `ydata`:
let offsetX = 0;
if (strideX < 0) {
    offsetX = (1-N) * strideX;
}
let offsetY = 0;
if (strideY < 0) {
    offsetY = (1-N) * strideY;
}

// Write data to the memory instance:
for (let i = 0; i < N; i++) {
    view.setFloat64(xptr+(i*8), xdata[offsetX+(i*strideX)], true);
    view.setFloat64(yptr+(i*8), ydata[offsetY+(i*strideY)], true);
}

Sekurang-kurangnya dalam kes ini, bukan sahaja pendekatan WebAssembly kurang ergonomik, tetapi, seperti yang dijangkakan memandangkan pergerakan data yang diperlukan, terdapat kesan prestasi negatif, juga, seperti yang ditunjukkan dalam rajah berikut.

Rajah 1: Perbandingan prestasi pelaksanaan C, JavaScript dan WebAssembly (Wasm) stdlib untuk rutin BLAS daxpy untuk meningkatkan panjang tatasusunan (paksi-x). Dalam Wasm (salinan) penanda aras, data input dan output disalin ke dan dari memori Wasm, yang membawa kepada prestasi yang lebih lemah.

Dalam rajah di atas, saya memaparkan perbandingan prestasi pelaksanaan C, JavaScript dan WebAssembly (Wasm) stdlib untuk daxpy rutin BLAS untuk meningkatkan panjang tatasusunan, seperti yang disenaraikan di sepanjang paksi-x. Paksi-y menunjukkan kadar ternormal berbanding pelaksanaan garis dasar C. Dalam penanda aras Wasm, data input dan output diperuntukkan dan dimanipulasi secara langsung dalam memori modul WebAssembly, dan, dalam penanda aras Wasm (salinan), data input dan output disalin ke dan dari memori modul WebAssembly, seperti yang dibincangkan di atas. Daripada carta, kita mungkin melihat perkara berikut:

1. Secara amnya, terima kasih kepada penyusun just-in-time (JIT) yang sangat dioptimumkan, kod JavaScript, apabila ditulis dengan teliti, boleh melaksanakan hanya 2 hingga 3 kali lebih perlahan daripada kod asli. Keputusan ini mengagumkan untuk bahasa pengaturcaraan yang ditaip longgar dan disusun secara dinamik dan, sekurang-kurangnya untuk daxpy, kekal konsisten merentas pelbagai panjang tatasusunan.
2. Apabila saiz data dan dengan itu jumlah masa yang dibelanjakan dalam modul WebAssembly meningkat, WebAssembly boleh menghampiri kelajuan hampir asli (~1.5x). Keputusan ini lebih sejajar dengan prestasi WebAssembly yang dijangkakan.
3. Walaupun WebAssembly boleh mencapai kelajuan hampir asli, keperluan pergerakan data mungkin menjejaskan prestasi, seperti yang diperhatikan untuk daxpy. Dalam kes sedemikian, pelaksanaan JavaScript yang direka dengan baik yang mengelakkan keperluan sedemikian boleh mencapai prestasi yang sama, jika tidak lebih baik, seperti yang berlaku untuk daxpy.

Secara keseluruhan, WebAssembly boleh menawarkan peningkatan prestasi; walaubagaimanapun, teknologi itu bukanlah satu peluru perak dan perlu digunakan dengan berhati-hati untuk mencapai keuntungan yang diingini. Dan walaupun ketika menawarkan prestasi unggul, keuntungan tersebut mesti diseimbangkan dengan kos peningkatan kerumitan, saiz berkas yang berpotensi lebih besar dan rantai alat yang lebih kompleks. Untuk kebanyakan aplikasi, pelaksanaan JavaScript biasa akan berfungsi dengan baik.

Modulariti radikal

Sekarang saya telah mendakwa kes terhadap hanya menyusun keseluruhan LAPACK ke WebAssembly dan memanggilnya sehari, di manakah kita meninggalkannya? Nah, jika kita akan menerima etos stdlib, ia menyebabkan kita memerlukan modulariti radikal.

Untuk menerima modulariti radikal ialah mengiktiraf bahawa apa yang terbaik adalah sangat kontekstual, dan, bergantung pada keperluan dan kekangan aplikasi pengguna, pembangun memerlukan fleksibiliti untuk memilih abstraksi yang betul. Jika pembangun sedang menulis aplikasi Node.js, ini mungkin bermakna mengikat kepada perpustakaan yang dioptimumkan perkakasan, seperti OpenBLAS, Intel MKL atau Apple Accelerate untuk mencapai prestasi unggul. Jika pembangun menggunakan aplikasi web yang memerlukan set kecil rutin berangka, JavaScript berkemungkinan alat yang sesuai untuk tugas itu. Dan jika pembangun sedang mengusahakan aplikasi WebAssembly yang besar dan intensif sumber (mis., untuk penyuntingan imej atau enjin permainan), maka dapat menyusun rutin individu dengan mudah sebagai sebahagian daripada aplikasi yang lebih besar adalah yang paling penting. Pendek kata, kami mahukan LAPACK modular yang radikal.

Misi saya adalah untuk meletakkan asas bagi usaha sedemikian, untuk menyelesaikan masalah dan mencari jurang, dan semoga membawa kita beberapa langkah lebih dekat kepada algebra linear berprestasi tinggi di web. Tetapi bagaimana rupa modulariti radikal? Semuanya bermula dengan unit asas fungsi, pakej.

Setiap pakej dalam stdlib ialah perkara tersendiri, mengandungi ujian setempat bersama, penanda aras, contoh, dokumentasi, fail binaan dan data meta yang berkaitan (termasuk penghitungan sebarang kebergantungan) dan mentakrifkan permukaan API yang jelas dengan dunia luar . Untuk menambah sokongan LAPACK pada stdlib, ini bermakna mencipta pakej kendiri yang berasingan untuk setiap rutin LAPACK dengan struktur berikut:

pip install numpy

Ringkasnya,

• penanda aras: folder yang mengandungi penanda aras mikro untuk menilai prestasi berbanding pelaksanaan rujukan (iaitu, rujukan LAPACK).
• dokumen: folder yang mengandungi dokumentasi tambahan termasuk teks bantuan REPL dan pengisytiharan TypeScript yang mentakrifkan tandatangan API yang ditaip.
• contoh: folder yang mengandungi kod tunjuk cara boleh laku, yang, selain berfungsi sebagai dokumentasi, membantu kewarasan pembangun menyemak gelagat pelaksanaan.
• sertakan: folder yang mengandungi fail pengepala C.
• lib: folder yang mengandungi pelaksanaan sumber JavaScript, dengan index.js berfungsi sebagai titik masuk pakej dan fail *.js lain yang mentakrifkan modul pelaksanaan dalaman.
• src: folder yang mengandungi pelaksanaan sumber C dan Fortran. Setiap pakej LAPACK modular harus mengandungi pelaksanaan rujukan Fortran yang diubah suai sedikit (F77 kepada Fortran bentuk bebas). Fail C termasuk pelaksanaan C biasa yang mengikuti pelaksanaan rujukan Fortran, pembungkus untuk memanggil pelaksanaan rujukan Fortran, pembungkus untuk memanggil perpustakaan yang dioptimumkan perkakasan (cth., OpenBLAS) dalam aplikasi sisi pelayan dan pengikatan asli untuk memanggil ke dalam kompilasi. C daripada JavaScript dalam Node.js atau masa jalan JavaScript sebelah pelayan yang serasi.
• ujian: folder yang mengandungi ujian unit untuk menguji gelagat yang dijangkakan dalam kedua-dua JavaScript dan pelaksanaan asli. Ujian untuk pelaksanaan asli ditulis dalam JavaScript dan memanfaatkan pengikatan asli untuk interoperasi antara JavaScript dan C/Fortran.
• binding.gyp/include.gypi: bina fail untuk menyusun alat tambah asli Node.js, yang menyediakan jambatan antara JavaScript dan kod asli.
• manifest.json: fail konfigurasi untuk pengurusan pakej sumber terkumpul C dan Fortran dalaman stdlib.
• package.json: fail yang mengandungi data meta pakej, termasuk penghitungan kebergantungan pakej luaran dan laluan ke pelaksanaan JavaScript biasa untuk digunakan dalam aplikasi web berasaskan penyemak imbas.
• README.md: fail yang mengandungi dokumentasi utama pakej, yang termasuk tandatangan API dan contoh untuk antara muka JavaScript dan C.

Memandangkan keperluan dokumentasi dan ujian stdlib yang menuntut, menambah sokongan untuk setiap rutin adalah jumlah kerja yang baik, tetapi hasil akhirnya adalah teguh, berkualiti tinggi dan, yang paling penting, kod modular yang sesuai untuk dijadikan asas untuk pengiraan saintifik di web moden. Tetapi cukup dengan pendahuluan! Jom mula berniaga!

Pendekatan pelbagai fasa

Berdasarkan usaha terdahulu yang menambahkan sokongan BLAS kepada stdlib, kami memutuskan untuk mengikuti pendekatan berbilang fasa yang serupa apabila menambahkan sokongan LAPACK di mana kami mula-mula mengutamakan pelaksanaan JavaScript dan ujian serta dokumentasi yang berkaitan dan kemudian, setelah ujian dan dokumentasi hadir , pengisian balik C dan pelaksanaan Fortran dan sebarang pengikatan asli yang berkaitan dengan perpustakaan yang dioptimumkan perkakasan. Pendekatan ini membolehkan kami meletakkan beberapa perkara awal pada papan, boleh dikatakan, mendapatkan API dengan cepat di hadapan pengguna, mewujudkan prosedur ujian dan penanda aras yang teguh, dan menyiasat kemungkinan peluang untuk perkakas dan automasi sebelum menyelam ke dalam rumpai rantai alat dan prestasi binaan pengoptimuman. Tetapi di mana untuk bermula?

Untuk menentukan rutin LAPACK yang hendak disasarkan dahulu, saya menghuraikan kod sumber Fortran LAPACK untuk menjana graf panggilan. Ini membolehkan saya membuat kesimpulan pepohon kebergantungan untuk setiap rutin LAPACK. Dengan graf di tangan, saya kemudian melakukan jenis topologi, sekali gus membantu saya mengenal pasti rutin tanpa kebergantungan dan yang pasti akan menjadi blok pembinaan untuk rutin lain. Walaupun pendekatan mendalam di mana saya memilih rutin peringkat tinggi tertentu dan bekerja ke belakang akan membolehkan saya mendapatkan ciri tertentu, pendekatan sedemikian mungkin menyebabkan saya buntu cuba melaksanakan rutin kerumitan yang semakin meningkat. Dengan memfokuskan pada "daun" graf, saya boleh mengutamakan rutin yang biasa digunakan (iaitu, rutin dengan indegres tinggi) dan dengan itu memaksimumkan impak saya dengan membuka kunci keupayaan untuk menyampaikan berbilang rutin peringkat tinggi sama ada kemudian usaha saya atau oleh penyumbang lain.

Dengan rancangan saya di tangan, saya teruja untuk pergi bekerja. Untuk rutin pertama saya, saya memilih dlaswp, yang melakukan satu siri pertukaran baris pada matriks segi empat tepat umum mengikut senarai indeks pangsi yang disediakan dan yang merupakan blok binaan utama untuk rutin penguraian LU LAPACK. Dan ketika itulah cabaran saya bermula...

Cabaran

Legasi Fortran

Sebelum latihan Quansight Labs saya, saya adalah (dan masih!) penyumbang tetap kepada LFortran, pengkompil Fortran interaktif moden yang dibina di atas LLVM, dan saya berasa agak yakin dengan kemahiran Fortran saya. Walau bagaimanapun, salah satu cabaran pertama saya ialah memahami apa yang kini dianggap kod Fortran "warisan". Saya menyerlahkan tiga halangan awal di bawah.

Memformat

LAPACK pada asalnya ditulis dalam FORTRAN 77 (F77). Walaupun perpustakaan telah dipindahkan ke Fortran 90 dalam versi 3.2 (2008), konvensyen warisan masih berterusan dalam pelaksanaan rujukan. Salah satu konvensyen yang paling ketara ialah pemformatan.

Pembangun menulis program F77 melakukannya menggunakan reka letak bentuk tetap yang diwarisi daripada kad tebuk. Reka letak ini mempunyai keperluan yang ketat mengenai penggunaan lajur aksara:

• Komen yang menduduki keseluruhan baris mesti bermula dengan aksara khas (cth., *, !, atau C) dalam lajur pertama.
• Untuk baris bukan ulasan, 1) lima lajur pertama mesti kosong atau mengandungi label berangka, 2) lajur enam dikhaskan untuk aksara sambungan, 3) penyataan boleh laku mesti bermula pada lajur tujuh dan 4) sebarang kod di luar lajur 72 diabaikan.

Fortran 90 memperkenalkan susun atur borang percuma yang mengalih keluar sekatan panjang lajur dan baris dan diselesaikan pada ! sebagai watak komen. Coretan kod berikut menunjukkan pelaksanaan rujukan untuk dlacpy rutin LAPACK:

pip install numpy

Coretan kod seterusnya menunjukkan rutin yang sama, tetapi dilaksanakan menggunakan reka letak borang percuma yang diperkenalkan dalam Fortran 90.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Seperti yang mungkin diperhatikan, dengan mengalih keluar sekatan lajur dan menjauhkan diri daripada konvensyen F77 dalam penentuan penulisan dalam ALL CAPS, kod Fortran moden lebih jelas konsisten dan dengan itu lebih mudah dibaca.

Struktur kawalan berlabel

Satu lagi amalan biasa dalam rutin LAPACK ialah penggunaan struktur kawalan berlabel. Sebagai contoh, pertimbangkan coretan kod berikut di mana label 10 mesti sepadan dengan CONTINUE yang sepadan.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy

Fortran 90 menghilangkan keperluan untuk amalan ini dan meningkatkan kebolehbacaan kod dengan membenarkan seseorang menggunakan end do untuk menamatkan gelung do. Perubahan ini ditunjukkan dalam versi bentuk percuma dlacpy yang disediakan di atas.

Tatasusunan saiz andaian

Untuk membolehkan fleksibiliti dalam mengendalikan tatasusunan dengan saiz yang berbeza-beza, rutin LAPACK biasanya beroperasi pada tatasusunan yang mempunyai saiz yang diandaikan. Dalam rutin dlacpy di atas, matriks input A diisytiharkan sebagai tatasusunan dua dimensi yang mempunyai saiz andaian mengikut ungkapan A(LDA, *). Ungkapan ini mengisytiharkan bahawa A mempunyai bilangan baris LDA dan menggunakan * sebagai pemegang tempat untuk menunjukkan bahawa saiz dimensi kedua ditentukan oleh program panggilan.

Satu akibat daripada menggunakan tatasusunan saiz andaian ialah pengkompil tidak dapat melakukan semakan had pada dimensi yang tidak ditentukan. Oleh itu, amalan terbaik semasa ialah menggunakan antara muka eksplisit dan tatasusunan bentuk yang diandaikan (cth., A(LDA,:)) untuk mengelakkan capaian memori di luar sempadan. Ini menyatakan, penggunaan tatasusunan bentuk yang diandaikan boleh menimbulkan masalah apabila perlu menghantar sub-matriks kepada fungsi lain, kerana berbuat demikian memerlukan penghirisan yang selalunya mengakibatkan penyusun mencipta salinan dalaman data tatasusunan.

Berhijrah ke Fortran 95

Tidak perlu dikatakan, saya mengambil sedikit masa untuk menyesuaikan diri dengan konvensyen LAPACK dan mengamalkan pemikiran LAPACK. Walau bagaimanapun, sebagai seorang yang tulen, jika saya akan mengalihkan rutin, saya sekurang-kurangnya mahu membawa rutin yang saya berjaya alihkan ke zaman yang lebih moden dengan harapan dapat meningkatkan kebolehbacaan kod dan penyelenggaraan masa hadapan. Oleh itu, selepas membincangkan perkara dengan penyelenggara stdlib, saya memutuskan untuk memindahkan rutin ke Fortran 95, yang, walaupun bukan versi Fortran yang terbaharu dan terhebat, nampaknya mencapai keseimbangan yang tepat antara mengekalkan rupa dan rasa pelaksanaan asal, memastikan ( cukup baik) keserasian ke belakang dan memanfaatkan ciri sintaksis yang lebih baharu.

Liputan Ujian

Salah satu masalah dengan mengikuti pendekatan bawah ke atas untuk menambah sokongan LAPACK ialah ujian unit eksplisit untuk rutin utiliti peringkat rendah selalunya tidak wujud dalam LAPACK. Suite ujian LAPACK sebahagian besarnya menggunakan falsafah ujian hierarki yang menguji rutin peringkat lebih tinggi diandaikan untuk memastikan rutin peringkat rendah bergantung mereka berfungsi dengan betul sebagai sebahagian daripada aliran kerja keseluruhan. Walaupun seseorang boleh berhujah bahawa memfokuskan pada ujian integrasi berbanding ujian unit untuk rutin peringkat rendah adalah munasabah, kerana penambahan ujian untuk setiap rutin berpotensi meningkatkan beban penyelenggaraan dan kerumitan rangka kerja ujian LAPACK, ini bermakna kami tidak boleh bergantung pada sebelumnya. seni untuk ujian unit dan perlu menghasilkan ujian unit kendiri yang komprehensif untuk setiap rutin peringkat rendah sendiri.

Dokumentasi

Sepanjang jalan yang sama untuk menguji liputan, di luar LAPACK itu sendiri, mencari contoh didokumentasikan dunia sebenar yang mempamerkan penggunaan rutin peringkat rendah adalah mencabar. Walaupun rutin LAPACK secara konsisten didahului oleh ulasan dokumentasi yang memberikan penerangan tentang argumen input dan nilai pulangan yang mungkin, tanpa contoh kod, visualisasi dan grokking nilai input dan output yang dijangkakan boleh mencabar, terutamanya apabila berurusan dengan matriks khusus. Dan walaupun ketiadaan ujian unit atau contoh yang didokumenkan bukanlah penghujung dunia, ini bermakna menambah sokongan LAPACK ke stdlib akan menjadi lebih sukar daripada yang saya jangkakan. Menulis tanda aras, ujian, contoh dan dokumentasi hanya akan memerlukan lebih banyak masa dan usaha, yang berpotensi mengehadkan bilangan rutin yang boleh saya laksanakan semasa latihan.

Susun atur memori

Apabila menyimpan elemen matriks dalam ingatan linear, seseorang mempunyai dua pilihan: sama ada menyimpan lajur bersebelahan atau baris bersebelahan (lihat Rajah 2). Susun atur memori dahulu dirujuk sebagai susunan lajur-utama dan yang terakhir sebagai susunan baris-utama.

Rajah 2: Skema yang menunjukkan penyimpanan elemen matriks dalam ingatan linear sama ada dalam susunan (a) lajur-utama (gaya Fortran) atau (b) baris-utama (gaya-C). Pilihan reka letak yang hendak digunakan sebahagian besarnya adalah soal konvensyen.

Pilihan susun atur yang hendak digunakan sebahagian besarnya adalah soal konvensyen. Contohnya, Fortran menyimpan elemen dalam susunan lajur-utama, dan C menyimpan elemen dalam susunan baris-utama. Pustaka peringkat lebih tinggi, seperti NumPy dan stdlib, menyokong kedua-dua pesanan lajur dan baris utama, membolehkan anda mengkonfigurasi reka letak tatasusunan berbilang dimensi semasa penciptaan tatasusunan.

pip install numpy

Walaupun kedua-dua susun atur memori sememangnya lebih baik daripada yang lain, mengatur data untuk memastikan akses berjujukan mengikut konvensyen model storan asas adalah penting dalam memastikan prestasi optimum. CPU moden dapat memproses data berjujukan dengan lebih cekap berbanding data bukan berjujukan, yang disebabkan terutamanya oleh cache CPU yang, seterusnya, mengeksploitasi lokaliti spatial rujukan.

Untuk menunjukkan kesan prestasi akses unsur berjujukan vs bukan berjujukan, pertimbangkan fungsi berikut yang menyalin semua elemen daripada matriks MxN A ke matriks MxN B yang lain dan yang berbuat demikian dengan mengandaikan bahawa elemen matriks disimpan dalam lajur utama. pesanan.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Misalkan A dan B ialah matriks 3x2 berikut:

A=⎣⎡​ 135​ 246​ ⎦ ⎤​, B=⎣ ⎡​000​ 000​⎦⎤ ​

Apabila kedua-dua A dan B disimpan dalam susunan utama lajur, kita boleh memanggil rutin penyalinan seperti berikut:

pip install numpy

Walau bagaimanapun, jika A dan B kedua-duanya disimpan dalam susunan baris-utama, tandatangan panggilan bertukar kepada

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Perhatikan bahawa, dalam senario terakhir, kita gagal mengakses elemen dalam susunan berurutan dalam gelung paling dalam, kerana da0 ialah 2 dan da1 ialah -5 dan begitu juga untuk db0 dan db1. Sebaliknya, "penunjuk" indeks tatasusunan berulang kali melangkau ke hadapan sebelum kembali ke elemen terdahulu dalam ingatan linear, dengan ia = {0, 2, 4, 1, 3, 5} dan ib yang sama. Dalam Rajah 3, kami menunjukkan kesan prestasi akses tidak berurutan.

Rajah 3: Perbandingan prestasi apabila menyediakan matriks lajur-utama berbanding baris-utama untuk menyalin apabila salin mengandaikan akses elemen berjujukan mengikut susunan lajur-utama. Paksi-x menghitung saiz matriks yang semakin meningkat (iaitu, bilangan elemen). Semua kadar dinormalisasi berbanding hasil lajur utama untuk saiz matriks yang sepadan.

Daripada rajah, kita mungkin melihat bahawa prestasi utama lajur dan baris adalah kira-kira setara sehingga kita beroperasi pada matriks persegi yang mempunyai lebih daripada 1e5 elemen (M = N = ~316). Untuk 1e6 elemen (M = N = ~1000), menyediakan matriks baris-utama untuk menyalin menghasilkan penurunan prestasi yang lebih besar daripada 25%. Untuk 1e7 elemen (M = N = ~3160), kami melihat penurunan prestasi lebih daripada 85%. Kesan prestasi yang ketara mungkin disebabkan oleh penurunan lokaliti rujukan apabila beroperasi pada matriks baris-utama yang mempunyai saiz baris yang besar.

Memandangkan ia ditulis dalam Fortran, LAPACK menganggap susunan akses utama lajur dan melaksanakan algoritmanya dengan sewajarnya. Ini membentangkan isu untuk perpustakaan, seperti stdlib, yang bukan sahaja menyokong susunan baris-utama, tetapi menjadikannya reka letak memori lalai mereka. Sekiranya kami hanya mengalihkan pelaksanaan Fortran LAPACK ke JavaScript, pengguna yang menyediakan matriks baris-utama akan mengalami kesan prestasi buruk yang berpunca daripada akses tidak berurutan.

Untuk mengurangkan kesan prestasi buruk, kami meminjam idea daripada BLIS, perpustakaan seperti BLAS yang menyokong susun atur memori utama baris dan lajur dalam rutin BLAS, dan memutuskan untuk mencipta pelaksanaan LAPACK yang diubah suai apabila mengalihkan rutin daripada Fortran ke JavaScript dan C yang secara eksplisit menampung reka letak memori lajur dan baris utama melalui parameter langkah berasingan untuk setiap dimensi. Untuk sesetengah pelaksanaan, seperti dlacpy, yang serupa dengan fungsi salin yang ditakrifkan di atas, menggabungkan langkah yang berasingan dan bebas adalah mudah, selalunya melibatkan helah langkah dan pertukaran gelung, tetapi, bagi yang lain, pengubahsuaian ternyata kurang mudah disebabkan oleh pengendalian matriks khusus, corak akses yang berbeza-beza dan parameterisasi gabungan.

ndarrays

Rutin LAPACK terutamanya beroperasi pada matriks yang disimpan dalam memori linear dan unsur-unsurnya diakses mengikut dimensi yang ditentukan dan langkah dimensi terkemuka (iaitu, pertama). Dimensi menentukan bilangan elemen dalam setiap baris dan lajur, masing-masing. Langkah menentukan bilangan elemen dalam ingatan linear mesti dilangkau untuk mengakses elemen baris seterusnya. LAPACK menganggap bahawa unsur-unsur kepunyaan lajur yang sama sentiasa bersebelahan (iaitu, bersebelahan dalam ingatan linear). Rajah 4 memberikan gambaran visual konvensyen LAPACK (khususnya, skema (a) dan (b)).

Rajah 4: Skema yang menggambarkan generalisasi konvensyen tatasusunan berjajak LAPACK kepada tatasusunan berjajak tidak bersebelahan. a) Matriks bersebelahan 5-kali-5 disimpan dalam susunan lajur-utama. b) Sub-matriks bukan bersebelahan 3-demi-3 disimpan dalam susunan lajur-utama. Sub-matriks boleh dikendalikan dalam LAPACK dengan memberikan penunjuk kepada elemen diindeks pertama dan menentukan langkah dimensi terkemuka (iaitu, pertama). Dalam kes ini, langkah dimensi utama ialah lima, walaupun terdapat hanya tiga elemen setiap lajur, disebabkan oleh unsur-unsur sub-matriks yang tidak bersebelahan dalam ingatan linear apabila disimpan sebagai sebahagian daripada matriks yang lebih besar. Dalam LAPACK, langkah dimensi mengekori (iaitu, kedua) sentiasa diandaikan sebagai perpaduan. c) Sub-matriks bukan bersempadan 3-demi-3 yang disimpan dalam susunan lajur-utama yang mempunyai langkah bukan unit dan menyamaratakan konvensyen langkah LAPACK kepada kedua-dua dimensi pendahuluan dan mengekori. Generalisasi ini menyokong tatasusunan berbilang dimensi stdlib (juga dirujuk sebagai "ndarrays").

Perpustakaan, seperti NumPy dan stdlib, menyamaratakan konvensyen tatasusunan langkah LAPACK untuk menyokong

1. langkah bukan unit dalam dimensi terakhir (lihat Rajah 4 (c)). LAPACK menganggap bahawa dimensi terakhir matriks sentiasa mempunyai langkah unit (iaitu, elemen dalam lajur disimpan bersebelahan dalam ingatan linear).
2. langkah negatif untuk mana-mana dimensi. LAPACK memerlukan langkah dimensi matriks terkemuka adalah positif.
3. tatasusunan berbilang dimensi yang mempunyai lebih daripada dua dimensi. LAPACK hanya secara jelas menyokong vektor berjalur dan (sub)matriks.

Sokongan untuk langkah bukan unit dalam dimensi terakhir memastikan sokongan untuk penciptaan O(1) pandangan bukan bersebelahan memori linear tanpa memerlukan pergerakan data eksplisit. Pandangan ini sering dipanggil "hirisan". Sebagai contoh, pertimbangkan coretan kod berikut yang mencipta paparan sedemikian menggunakan API yang disediakan oleh stdlib.

pip install numpy

Tanpa sokongan untuk langkah bukan unit dalam dimensi terakhir, mengembalikan pandangan daripada ungkapan x['::2,::2'] tidak akan dapat dilakukan, kerana seseorang perlu menyalin elemen terpilih ke linear baharu penimbal memori untuk memastikan ketersambungan.

Rajah 5: Skema yang menggambarkan penggunaan manipulasi langkah untuk mencipta pandangan terbalik dan diputar bagi elemen matriks yang disimpan dalam ingatan linear. Untuk semua sub-skema, langkah disenaraikan sebagai [trailing_dimension, leading_dimension]. Tersirat untuk setiap skema ialah "offset", yang menunjukkan indeks unsur diindeks pertama supaya, untuk matriks A, elemen A_ij ialah diselesaikan mengikut i⋅strides[1] j⋅strides[0] offset. a) Memandangkan matriks 3-oleh-3 yang disimpan dalam susunan lajur-utama, seseorang boleh memanipulasi langkah dimensi pendahulu dan mengekor untuk mencipta pandangan di mana elemen matriks sepanjang satu atau lebih paksi diakses dalam susunan terbalik. b) Menggunakan manipulasi langkah yang sama, seseorang boleh mencipta pandangan berpusing bagi elemen matriks berbanding susunannya dalam ingatan linear.

Sokongan untuk langkah negatif membolehkan O(1) pembalikan dan putaran elemen sepanjang satu atau lebih dimensi (lihat Rajah 5). Contohnya, untuk membalikkan matriks dari atas ke bawah dan kiri ke kanan, seseorang hanya perlu menafikan langkah. Berdasarkan coretan kod sebelumnya, coretan kod berikut menunjukkan elemen terbalik tentang satu atau lebih paksi.

pip install numpy

Tersirat dalam perbincangan tentang langkah negatif ialah keperluan untuk parameter "offset" yang menunjukkan indeks unsur diindeks pertama dalam ingatan linear. Untuk tatasusunan berbilang dimensi berjajak A dan senarai langkah s, indeks yang sepadan dengan elemen A_ij⋅⋅⋅n boleh diselesaikan mengikut persamaan

$$\text{idx}=\text{mengimbangi}i\cdot s_{0}j\cdot s_1\dots n\cdot s_{N-1}$$idx=mengimbangi i⋅s0​ j⋅s1​ … n⋅sN−1 ​

di mana N ialah bilangan dimensi tatasusunan dan s_k sepadan dengan langkah ke-1.

Dalam rutin BLAS dan LAPACK yang menyokong langkah negatif—sesuatu yang hanya disokong apabila beroperasi pada vektor berjalur (cth., lihat daxpy di atas)—mengimbangi indeks dikira menggunakan logik yang serupa dengan coretan kod berikut:

pip install numpy

di mana M ialah bilangan elemen vektor. Ini secara tersirat mengandaikan bahawa penunjuk data yang disediakan menunjuk ke permulaan ingatan linear untuk vektor. Dalam bahasa yang menyokong penuding, seperti C, untuk beroperasi pada kawasan memori linear yang berbeza, seseorang biasanya melaraskan penuding menggunakan aritmetik penuding sebelum seruan fungsi, yang agak murah dan mudah, sekurang-kurangnya untuk kes satu dimensi.

Sebagai contoh, kembali ke c_daxpy seperti yang ditakrifkan di atas, kita boleh menggunakan aritmetik penuding untuk mengehadkan akses elemen kepada lima elemen dalam memori linear bermula pada elemen kesebelas dan keenam belas (nota: pengindeksan berasaskan sifar) tatasusunan input dan output, masing-masing, seperti yang ditunjukkan dalam coretan kod berikut.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Walau bagaimanapun, dalam JavaScript, yang tidak menyokong aritmetik penuding eksplisit untuk penimbal binari, seseorang mesti secara eksplisit membuat seketika objek tatasusunan ditaip baharu yang mempunyai offset bait yang dikehendaki. Dalam coretan kod berikut, untuk mencapai hasil yang sama seperti contoh C di atas, kita mesti menyelesaikan pembina tatasusunan ditaip, mengira offset bait baharu, mengira panjang tatasusunan ditaip baharu dan mencipta contoh tatasusunan ditaip baharu.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy

Untuk saiz tatasusunan yang besar, kos instantiasi tatasusunan ditaip boleh diabaikan berbanding dengan masa yang dihabiskan untuk mengakses dan beroperasi pada elemen tatasusunan individu; walau bagaimanapun, untuk saiz tatasusunan yang lebih kecil, instantiasi objek boleh memberi kesan ketara kepada prestasi.

Oleh itu, untuk mengelakkan kesan prestasi instantiasi objek yang buruk, stdlib menyahgandingkan penimbal data ndarray daripada lokasi elemen penimbal yang sepadan dengan permulaan paparan ndarray. Ini membenarkan ungkapan hirisan x[2:,3:] dan x[3:,1:] mengembalikan paparan ndarray baharu tanpa perlu membuat instantiat tika penimbal baharu, seperti yang ditunjukkan dalam coretan kod berikut.

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);

Akibat daripada menyahganding penimbal data dari permulaan paparan ndarray, kami juga berusaha untuk mengelak daripada membuat contoh tatasusunan ditaip baharu apabila memanggil rutin LAPACK dengan data ndarray. Ini bermakna mencipta tandatangan API LAPACK diubah suai yang menyokong parameter offset eksplisit untuk semua vektor dan matriks berjalur.

Untuk memudahkan, mari kembali kepada pelaksanaan JavaScript daxpy, yang telah ditakrifkan di atas sebelum ini.

pip install numpy

Seperti yang ditunjukkan dalam coretan kod berikut, kami boleh mengubah suai tandatangan dan pelaksanaan di atas supaya tanggungjawab untuk menyelesaikan elemen diindeks pertama dialihkan kepada pengguna API.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Untuk ndarray, peleraian berlaku semasa instantiasi ndarray, menjadikan penggunaan daxpy_ndarray dengan data ndarray sebagai penghantaran terus data meta ndarray yang berkaitan. Ini ditunjukkan dalam coretan kod berikut.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy

Sama seperti BLIS, kami melihat nilai dalam kedua-dua tandatangan API LAPACK konvensional (cth., untuk keserasian ke belakang) dan tandatangan API yang diubah suai (cth., untuk meminimumkan kesan prestasi buruk), dan oleh itu, kami memutuskan rancangan untuk menyediakan kedua-dua konvensional dan API yang diubah suai untuk setiap rutin LAPACK. Untuk meminimumkan pertindihan kod, kami menyasarkan untuk melaksanakan pelaksanaan "asas" peringkat rendah biasa yang kemudiannya boleh dibalut oleh API peringkat lebih tinggi. Walaupun perubahan untuk daxpy rutin BLAS yang ditunjukkan di atas mungkin kelihatan agak mudah, transformasi rutin LAPACK konvensional dan gelagat yang dijangkakannya kepada pelaksanaan umum selalunya kurang begitu.

dlaswp

Cukup dengan cabaran! Apakah rupa produk akhir?!

Mari datang bulatan penuh dan bawa ini kembali ke dlaswp, rutin LAPACK untuk melakukan satu siri pertukaran baris pada matriks input mengikut senarai indeks pangsi. Coretan kod berikut menunjukkan rujukan pelaksanaan LAPACK Fortran.

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);

Untuk memudahkan antara muka dengan pelaksanaan Fortran daripada C, LAPACK menyediakan antara muka C dua peringkat yang dipanggil LAPACKE, yang membungkus pelaksanaan Fortran dan membuat penginapan untuk kedua-dua baris dan lajur utama input dan matriks output. Antara muka peringkat pertengahan untuk dlaswp ditunjukkan dalam coretan kod berikut.

void c_daxpy(const int N, const double alpha, const double *X, const int strideX, double *Y, const int strideY) {
    int ix;
    int iy;
    int i;
    if (N <= 0) {
        return;
    }
    if (alpha == 0.0) {
        return;
    }
    if (strideX < 0) {
        ix = (1-N) * strideX;
    } else {
        ix = 0;
    }
    if (strideY < 0) {
        iy = (1-N) * strideY;
    } else {
        iy = 0;
    }
    for (i = 0; i < N; i++) {
        Y[iy] += alpha * X[ix];
        ix += strideX;
        iy += strideY;
    }
    return;
}

Apabila dipanggil dengan matriks lajur utama a, pembalut LAPACKE_dlaswp_work hanya menyampaikan hujah yang disediakan kepada pelaksanaan Fortran. Walau bagaimanapun, apabila dipanggil dengan matriks baris-major a, pembalut mesti memperuntukkan memori, menukar dan menyalin secara eksplisit a ke matriks sementara a_t, mengira semula langkah dimensi utama, memanggil dlaswp dengan a_t, menukar dan menyalin keputusan yang disimpan dalam a_t kepada a, dan akhirnya membebaskan memori yang diperuntukkan. Itu adalah jumlah kerja yang adil dan adalah perkara biasa di kebanyakan rutin LAPACK.

Coretan kod berikut menunjukkan pelaksanaan LAPACK rujukan yang dialihkan ke JavaScript, dengan sokongan untuk langkah dimensi mendahului dan mengekori, mengimbangi indeks dan vektor berjalur yang mengandungi indeks pangsi.

const binary = new UintArray([...]);

const mod = new WebAssembly.Module(binary);

Untuk menyediakan API yang mempunyai gelagat yang konsisten dengan LAPACK konvensional, saya kemudian membungkus pelaksanaan di atas dan menyesuaikan argumen input kepada pelaksanaan "asas", seperti yang ditunjukkan dalam coretan kod berikut.

pip install numpy

Saya kemudiannya menulis pembungkus yang berasingan tetapi serupa yang menyediakan pemetaan API lebih terus kepada tatasusunan berbilang dimensi stdlib dan yang melakukan beberapa pengendalian khas apabila arah untuk menggunakan pangsi adalah negatif, seperti yang ditunjukkan dalam coretan kod berikut.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]

Beberapa perkara yang perlu diberi perhatian:

1. Berbeza dengan API LAPACKE konvensional, parameter matrix_layout (order) tidak diperlukan dalam dlaswp_ndarray dan API asas, kerana susunan boleh disimpulkan daripada langkah yang disediakan.
2. Berbeza dengan API LAPACKE konvensional, apabila matriks input adalah baris-utama, kami tidak perlu menyalin data ke tatasusunan ruang kerja sementara, sekali gus mengurangkan peruntukan memori yang tidak perlu.
3. Berbeza dengan perpustakaan, seperti NumPy dan SciPy, yang antara muka dengan BLAS dan LAPACK secara langsung, apabila memanggil rutin LAPACK dalam stdlib, kita tidak perlu menyalin data berbilang dimensi bukan bersebelahan ke dan dari tatasusunan ruang kerja sementara sebelum dan selepas seruan, masing-masing. Kecuali apabila berantaramuka dengan BLAS dan LAPACK yang dioptimumkan perkakasan, pendekatan yang dijalankan membantu meminimumkan pergerakan data dan memastikan prestasi dalam aplikasi penyemak imbas yang dikekang sumber.

Untuk aplikasi sisi pelayan yang berharap dapat memanfaatkan perpustakaan yang dioptimumkan perkakasan, seperti OpenBLAS, kami menyediakan pembalut berasingan yang menyesuaikan hujah tandatangan umum kepada persamaan API yang dioptimumkan. Dalam konteks ini, sekurang-kurangnya untuk tatasusunan yang cukup besar, membuat salinan sementara boleh berbaloi.

Status semasa dan langkah seterusnya

Walaupun menghadapi cabaran, kemunduran yang tidak dijangka dan pelbagai lelaran reka bentuk, saya gembira untuk melaporkan bahawa, sebagai tambahan kepada dlaswp di atas, saya dapat membuka 35 PR dengan menambah sokongan untuk pelbagai rutin LAPACK dan utiliti yang berkaitan. Jelas sekali bukan 1,700 rutin, tetapi permulaan yang baik! :)

Walau bagaimanapun, masa depan cerah, dan kami agak teruja dengan kerja ini. Masih terdapat banyak ruang untuk penambahbaikan dan penyelidikan dan pembangunan tambahan. Khususnya, kami berminat untuk

1. terokai alatan dan automasi.
2. alamatkan isu binaan apabila menyelesaikan fail sumber kebergantungan Fortran yang tersebar merentas berbilang pakej stdlib.
3. melancarkan pelaksanaan C dan Fortran serta pengikatan asli untuk pakej LAPACK sedia ada stdlib.
4. teruskan mengembangkan perpustakaan rutin LAPACK modular stdlib.
5. mengenal pasti kawasan tambahan untuk pengoptimuman prestasi.

Sementara latihan Quansight Labs saya telah tamat, rancangan saya adalah untuk terus menambah pakej dan meneruskan usaha ini. Memandangkan potensi yang besar dan kepentingan asas LAPACK, kami ingin melihat inisiatif membawa LAPACK ke web ini terus berkembang, jadi, jika anda berminat untuk membantu memacu perkara ini ke hadapan, sila jangan teragak-agak untuk menghubungi! Dan jika anda berminat untuk menaja pembangunan, orang di Quansight akan lebih gembira untuk bersembang.

Dan dengan itu, saya ingin mengucapkan terima kasih kepada Quansight kerana menyediakan peluang latihan ini. Saya berasa amat bertuah kerana telah belajar begitu banyak. Menjadi pelatih di Quansight adalah impian saya sejak sekian lama, dan saya amat bersyukur kerana dapat memenuhinya. Saya ingin mengucapkan terima kasih khas kepada Athan Reines dan kepada Melissa Mendonça, yang merupakan mentor yang hebat dan orang yang hebat di sekelilingnya! Dan terima kasih kepada semua pembangun teras stdlib dan semua orang di Quansight kerana membantu saya dalam cara yang besar dan kecil sepanjang perjalanan.

Sola!

---

stdlib ialah projek perisian sumber terbuka yang didedikasikan untuk menyediakan suite komprehensif perpustakaan yang teguh dan berprestasi tinggi untuk mempercepatkan pembangunan projek anda dan memberi anda ketenangan fikiran kerana anda bergantung pada perisian berkualiti tinggi yang direka dengan mahir.

Jika anda menyukai siaran ini, berikan kami bintang ? di GitHub dan pertimbangkan untuk menyokong projek itu dari segi kewangan. Sumbangan anda dan sokongan berterusan membantu memastikan kejayaan jangka panjang projek dan amat dihargai!

Atas ialah kandungan terperinci LAPACK dalam pelayar web anda. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!