🍛 👊🏾 🦄 Apakah ada paralelisme dalam algoritme arbitrer dan cara menggunakannya dengan cara terbaik 😳 🤚🏻 👩🏿‍🤝‍👩🏽

Paralelisasi pemrosesan data saat ini digunakan terutama untuk mengurangi waktu komputasi dengan memproses data secara bersamaan di beberapa bagian pada banyak perangkat komputasi yang berbeda dan kemudian menggabungkan hasilnya. Eksekusi paralel memungkinkan untuk "melewati" hukum dasar yang dirumuskan oleh Lord Rayleigh pada tahun 1871, yang menurutnya (sebagaimana diterapkan pada pembuangan panas prosesor) daya disipasi panasnya sebanding dengan daya keempat frekuensi clock prosesor (menggandakan frekuensi meningkatkan pembuangan panas 16 kali) dan benar-benar menggantinya dengan yang linier dari jumlah komputer paralel - dengan tetap mempertahankan frekuensi clock). Tidak ada yang diberikan secara gratis - tugas mengungkapkan (biasanya disembunyikan untuk pengamat yang belum tahu, [1]) potensi paralelisme dalam algoritme tidak terletak di permukaan,dan efisiensi penggunaan (paralelisme) nya - terlebih lagi.

Di bawah ini adalah ilustrasi proses deteksi paralelisme untuk kasus paling sederhana dalam mengevaluasi ekspresi axb + a / c (a, b, c - input data).

a) - "operator cloud" (urutan eksekusi tidak ditentukan), b) - eksekusi berurutan lengkap, tidak ditentukan), b) - eksekusi berurutan lengkap, c) - eksekusi paralel

, . ( ) ( – ., ). .1 “ ”, ( ) .

(- ), . , . () . NP- [2], ( ) ( -). , “ ” (Data Science).

AlgoWiki [3].

, , c ILP (Instruction-Level Parallelism, , EPIC (Explicitly Parallel Instruction Computing, ). , .

() ( , ). (). “ - ”, ( ) , – () ). , (- ).

( ) - (), [4]. ( ).

( ) O(N2) , N – ( ), ( ) . ( ). .. , . , .

, , .

. ax2+bx+c=0.

Gambar tersebut menunjukkan bentuk tier-paralel dari algoritma untuk menyelesaikan persamaan kuadrat lengkap dalam bilangan real dalam bentuk kanonik (nomor tingkatan LPF terletak di sebelah kanan) — - - ( )

( “ ”, 6 4- ). ( ) – 1- 4, 2,3,4 - 5- 6 . , ( ) ( ) ! – ( ).

( ) , - D-F SPF@home. http://vbakanov.ru/dataflow/content/installdf.exe http://vbakanov.ru/spf@home/content/installspf.exe ( - http://vbakanov.ru/dataflow/dataflow.htm http://vbakanov.ru/spf@home/spf@home.htm).

Gambar tersebut menunjukkan diagram kompleks instrumen (* .set dan * .gv - file program dan file grafik informasi dari program yang dianalisis, masing-masing, * .mvr, * .med - file metrik dari simpul dan busur dari grafik algoritma, masing-masing, * .cls, * .ops - file parameter kalkulator dan operator program, masing-masing, * .lua - file teks dalam bahasa Lua yang berisi metode reorganisasi — - (*.set *.gv – , *.mvr, *.med – , *.cls, *.ops – , *.lua – Lua,

(set-) – gv- ( “ - ”, ( ) , – () ). , (- ).

() . “” .

Lua (Lua ANSI C, , - , ).

++, GUI Win’32- ( ) GIT-. ( ).

(Lua- “” API- SPF@home).

( D-F SPF@home ).

D-F (Data-Flow) , . 1 “Data-Flow” ( ), (), ; . - , , , “” . D-F , .

D-F , , . ( set- D-F, ):

, . D-F , - SPF@home. SPF@home gv- ( ), , Lua- ( API- , ):

CreateTiersByEdges("EdgesData.gv")  --     EdgesData.gv 
--    “”
-- CreateTiersByEdges_Bottom("EdgesData.gv")  --     EdgesData.gv 
--    “”
--
OpsOnTiers={} --   1D- OpsOnTiers 
for iTier=1,GetCountTiers() do --   
   OpsOnTiers[iTier]={} --  iTier-  2D- OpsOnTiers
   for nOp=1,GetCountOpsOnTier(iTier) do --       iTier  
      OpsOnTiers[iTier][nOp]=GetOpByNumbOnTier(nOp,iTier) --    nOp
end end --   for  iTier  for  nOp

gv- mvr med-, cls ops- . ( “-”, ) . , .

SPF@home “ ” , / ( ). med-.

, c ILP (Instruction-Level Parallelism, ), SPF@home .

.. Lua-, . ( ) :

I. “” ( ).

II. ( ).

III. .

( ) ; ( ).

, (, ) , , ( – ).

1) ( ) .

2) .

- . ( , , , ). “” API- “” ( , ).

“” ( ) ( ). “” “” ( ; “” ””).

( ) - “ ”, , “” . ( ). “” Windows- WinExec, ShellExecute CreateProcess, (, METIS -), Lua.

.6 ( ) “Bulldozer”, , “” “”.

Dalam gambar. menunjukkan diagram batang lebar dari tingkatan IPF nyata dari salinan layar saat sistem SPF @ home beroperasi (rata-rata aritmatika lebar ditunjukkan oleh garis putus-putus, a) dan diagram simbolik tindakan metode Bulldozer - b) — . SPF@home (- , a) “Bulldozer” - )

, ( 1,5-2 ) , (- ).

.. ( Lua) (., c , , .).

SPF@home ( ) . , . ( ) ( , , ). , .

, ( ) .

1. .., .. . — .: -, 2002. — 608 c.
2. ., . . : — , , 2012. — 420 c.
3. AlgoWiki. . URL: http://algowiki-project.org ( 31.07.2020).
4. .. . . — .: -, 2018. — 390 .
5. Roberto Ierusalimschy. Programming in Lua. Third Edition. PUC-Rio, Brasil, Rio de Janeiro, 2013. — 348 p.

Apakah ada paralelisme dalam algoritme arbitrer dan cara menggunakannya dengan cara terbaik

More articles: