這類問(wèn)題是反復(fù)出現(xiàn)的,應(yīng)該比“Matlab使用高度優(yōu)化的庫(kù)”或“Matlab使用MKL”一次更清楚地回答堆棧溢出。
歷史:
矩陣乘法(與矩陣向量、向量乘法和許多矩陣分解一起)是線性代數(shù)中最重要的問(wèn)題。工程師們從早期就開(kāi)始用計(jì)算機(jī)解決這些問(wèn)題。
我不是歷史專家,但很顯然,當(dāng)時(shí)每個(gè)人都用簡(jiǎn)單的循環(huán)重寫了他的Fortran版本。隨后出現(xiàn)了一些標(biāo)準(zhǔn)化,識(shí)別了大多數(shù)線性代數(shù)問(wèn)題需要解決的“核”(基本例程)。然后,這些基本操作在一個(gè)名為:基本線性代數(shù)子程序(BLAS)的規(guī)范中標(biāo)準(zhǔn)化。然后,工程師可以在他們的代碼中調(diào)用這些標(biāo)準(zhǔn)的、經(jīng)過(guò)良好測(cè)試的blas例程,從而使他們的工作更加容易。
BLAS:
BLAS從第一級(jí)(定義標(biāo)量向量和向量操作的第一個(gè)版本)發(fā)展到第二級(jí)(向量矩陣運(yùn)算)到第三級(jí)(矩陣運(yùn)算),并提供了越來(lái)越多的“核”,使越來(lái)越多的基本線性代數(shù)運(yùn)算標(biāo)準(zhǔn)化。最初的Fortran 77實(shí)現(xiàn)仍然可以在Netlib網(wǎng)站.
爭(zhēng)取更好的業(yè)績(jī):
因此,多年來(lái)(特別是在BLAS第1級(jí)和第2級(jí)發(fā)布之間:80年代初),隨著向量操作和緩存層次結(jié)構(gòu)的出現(xiàn),硬件發(fā)生了變化。這些進(jìn)化使BLAS子例程的性能大大提高成為可能。然后,不同的供應(yīng)商來(lái)實(shí)現(xiàn)越來(lái)越有效率的BLAS例程。
我不知道所有的歷史實(shí)現(xiàn)(我不是天生的,也不是那個(gè)時(shí)候的孩子),但最著名的兩個(gè)實(shí)現(xiàn)出現(xiàn)在21世紀(jì)初:Intel MKL和GotoBLAS。您的Matlab使用Intel MKL,這是一個(gè)非常好的,優(yōu)化的BLAS,這解釋了您看到的偉大性能。
矩陣乘法的技術(shù)細(xì)節(jié):
那么,為什么Matlab(MKL)在dgemm
(雙精度一般矩陣-矩陣乘法)?簡(jiǎn)單地說(shuō):因?yàn)樗褂昧耸噶炕土己玫臄?shù)據(jù)緩存。更復(fù)雜的術(shù)語(yǔ):參見(jiàn)文章由喬納森·摩爾提供。
基本上,當(dāng)您在所提供的C+代碼中執(zhí)行乘法時(shí),您對(duì)緩存一點(diǎn)也不友好。由于我懷疑您創(chuàng)建了一個(gè)指向行數(shù)組的指針數(shù)組,所以您在內(nèi)部循環(huán)中訪問(wèn)“matice 2”的第k列:matice2[m][k]
都很慢。實(shí)際上,當(dāng)你訪問(wèn)matice2[0][k]
,您必須得到矩陣數(shù)組0的k元素。然后在下一次迭代中,您必須訪問(wèn)matice2[1][k]
,它是另一個(gè)數(shù)組(數(shù)組1)的第k個(gè)元素.然后在下一次迭代中訪問(wèn)另一個(gè)數(shù)組,依此類推.因?yàn)檎麄€(gè)矩陣matice2
不能放在最高的緩存中(它是8*1024*1024
),程序必須從主內(nèi)存中獲取所需的元素,從而損失大量時(shí)間。
如果您只是轉(zhuǎn)換了矩陣,以便訪問(wèn)將位于連續(xù)的內(nèi)存地址中,那么您的代碼將運(yùn)行得更快,因?yàn)楝F(xiàn)在編譯器可以同時(shí)在緩存中加載整個(gè)行。只需嘗試這個(gè)修改后的版本:
timer.start();float temp = 0;//transpose matice2for (int p = 0; p < rozmer; p++){
for (int q = 0; q < rozmer; q++)
{
tempmat[p][q] = matice2[q][p];
}}for(int j = 0; j < rozmer; j++){
for (int k = 0; k < rozmer; k++)
{
temp = 0;
for (int m = 0; m < rozmer; m++)
{
temp = temp + matice1[j][m] * tempmat[k][m];
}
matice3[j][k] = temp;
}}timer.stop();
因此,您可以看到緩存局部性如何極大地提高了代碼的性能?,F(xiàn)在是真實(shí)的dgemm
實(shí)現(xiàn)將其利用到了一個(gè)非常廣泛的層次:它們?cè)谟蒚LB(TransferingLookAbout緩沖器,長(zhǎng)話短說(shuō):可以有效緩存的內(nèi)容)定義的矩陣塊上執(zhí)行乘法,從而將處理的數(shù)據(jù)量準(zhǔn)確地流到處理器。另一方面是矢量化,它們使用處理器的向量化指令來(lái)優(yōu)化指令吞吐量,這在跨平臺(tái)C+代碼中是無(wú)法做到的。
最后,人們聲稱這是因?yàn)镾trassen‘s或CoppersSmith-Winograd算法是錯(cuò)誤的,這兩種算法在實(shí)踐中都是不可實(shí)現(xiàn)的,因?yàn)樯厦嫣岬降挠布紤]因素。