↘️ ⛓️ 😲 Existe paralelismo em um algoritmo arbitrário e como usá-lo da melhor maneira 👨🏿‍🎤 🤶🏼 👩🏻‍🎨

A paralelização do processamento de dados é usada atualmente principalmente para reduzir o tempo computacional, processando simultaneamente os dados em partes em muitos dispositivos de computação diferentes e, em seguida, combinando os resultados. A execução paralela torna possível "contornar" a lei fundamental formulada por Lord Rayleigh em 1871, segundo a qual (conforme aplicada à dissipação de calor dos processadores) sua potência de dissipação de calor é proporcional à quarta potência da frequência do relógio do processador (dobrar a frequência aumenta a dissipação de calor 16 vezes) e realmente substituí-la por uma potência linear de o número de computadores paralelos - enquanto mantém a frequência do relógio). Nada é dado de graça - a tarefa de revelar (geralmente oculta para o observador não iniciado, [1]) o potencial de paralelismo em algoritmos não está na superfície,e a eficiência de seu uso (paralelismo) - ainda mais.

Abaixo está uma ilustração do processo de detecção de paralelismo para o caso mais simples de avaliação da expressão axb + a / c (a, b, c - dados de entrada).

a) - "nuvem de operadores" (sequência de execução não está definida), b) - execução totalmente sequencial, não definida), b) - execução totalmente sequencial, c) - execução paralela

, . ( ) ( – ., ). .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.

A figura mostra a forma paralela de camadas do algoritmo para resolver a equação quadrática completa em números reais na forma canônica (os números das camadas do LPF estão localizados à direita) — - - ( )

( “ ”, 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).

A figura mostra um diagrama do complexo instrumental (* .set e * .gv - o arquivo do programa e o arquivo do gráfico de informações do programa analisado, respectivamente, * .mvr, * .med - arquivos das métricas dos vértices e arcos do gráfico do algoritmo, respectivamente, * .cls, * .ops - arquivos de parâmetros de calculadoras e operadores de programa, respectivamente, * .lua - um arquivo de texto em linguagem Lua contendo métodos de reorganização — - (*.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”, , “” “”.

Na fig. mostra diagramas de barra das larguras das camadas de IPFs reais a partir de cópias de tela quando o sistema SPF @ home está operando (a média aritmética das larguras é mostrada por uma linha pontilhada, a) e um diagrama simbólico da ação do método 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.

Existe paralelismo em um algoritmo arbitrário e como usá-lo da melhor maneira

More articles: