Get best of the week

NPS, transportador, computação automática e de novo ... corotinas

1. Novamente sobre corotinas


No meu artigo anterior, prezado Habr, apenas toquei nos problemas de conhecimento da programação moderna. A discussão que se seguiu apenas confirmou os medos espontâneos que surgiram: os notórios “fundamentos teóricos” imediatamente se tornaram uma fonte de desacordo. O fato de eles (discordâncias) não existirem ou serem de natureza diferente não parece incomodar a maioria dos programadores "reais". Além disso, talvez não seja particularmente interessante, porque os programadores são estimulados principalmente por um interesse - código, código e apenas código. Bem, quase "como o médico receitou" [1] ...

Tocando no assunto de corutin em meu artigo e comentários, eu nem sonhei com o quanto eles estão na tendência "atual". Surpreendeu, no entanto, as "faixas de acompanhamento" dos meus comentários com ou sem. Para o que, dizem, programadores? No entanto, parece-me que tudo ficou claro depois de ler o artigo sobre o recém-aprovado C ++ 20 e as perspectivas de seu desenvolvimento [2]. Para minha surpresa, verificou-se que as corotinas estão na vanguarda das inovações presentes e futuras do meu amado C ++ (veja também a biblioteca CppCoro ).

Bem, diga-me, é possível levar a sério e / ou com calma uma sobrancelha que, ao que parece, se imagina alguém? Bata o que é chamado! :(

Os antecedentes de meu conhecimento com corotinas (eu os chamarei todos da mesma maneira da maneira antiga) são os seguintes. Havia uma necessidade de paralelizar, mas algo adequado não era. Eu tive que inventar, estudando a literatura disponível. Como resultado, as corotinas foram rejeitadas imediatamente e encadeadas posteriormente. A razão é que ambos são métodos estruturais de programas paralelos, e não modelos computacionais. Mas eu não queria isso.

A descrição do que eu finalmente cheguei é dada em meus artigos anteriores sobre Habré. Essa conversa está longe de terminar, mas por enquanto, como as corotinas foram lembradas, uma vez que já se tornaram objeto de uma discussão tão acalorada? A única coisa são os "pontos" dos processos de parada / comutação. Diferentemente dos encadeamentos, eles possibilitaram prever o comportamento de processos que simulam operações paralelas. Em teoria, isso também reduziu as perdas do sistema para a implementação do paralelismo. Mas, no entanto, em suma, tudo isso fundamentalmente alguma coisa não mudou. E como os "pontos" foram simplesmente imitados pelos estados do modelo de programação de autômatos (AP), meu conhecimento com corotinas foi concluído por sete.

Mas não pude supor que a encarnação das corotinas, agora denominadas corotinas, me superasse. Disto, e o meu, possivelmente "ataques" injustificados a eles, pelos quais peço sinceras desculpas aos apologistas de Corutin. Provavelmente apressado. No entanto, as circunstâncias recém-descobertas não afetaram minha atitude em relação às corotinas. Para o novo código, para raciocinar a seu favor, nunca vi nada fundamentalmente novo. No entanto, quero observar que as corotinas são, no entanto, mais próximas e mais claras para mim do que os fios, porque contêm, como eu disse acima, um análogo do conjunto de estados internos de autômatos finitos (CA).

No entanto, pare de se arrepender. Voltemos aos autômatos que cobrem completamente o “tema da corotina”. A seguir, apresentarei os recursos do AP associados à modelagem de modelos paralelos bastante conhecidos na teoria e na prática - modelos de algoritmos paralelos e de pipeline em camadas. A solução automática, na minha opinião, parece mais visual, natural e simples do que seria baseada nas mesmas corotinas.

2. Formas de algoritmos paralelos e de pipeline


Suponha que você precise calcular a expressão:

y = (((a + b) * (c + d)) + ((e * f) + (q + h))).

Além disso, seja definido o tempo de execução da operação, definido em unidades arbitrárias de tempo discreto - medidas em que a adição leva 1 medida e a multiplicação leva 5 medidas.
Com base na lógica de calcular a expressão, o tempo de execução das operações e o número de variáveis ​​intermediárias, em uma modalidade, a distribuição das operações por camadas e o número de camadas em si podem parecer, por exemplo, o seguinte:

t1 = a + b; t2 = c + d; t3 = e * f; t4 = q + h;
Nível0: t1; t2; t3; t4;
Nível1: t5 = t1 * t2; t6 = t3 + t4;
Nível2: t7 = t5 + t6;

Graficamente, isso é mostrado na fig. 1, que mostra duas opções para a distribuição de cálculos em camadas e o tempo de cálculo afixado em ticks. Sua comparação mostra que, no caso geral, uma diminuição no número de camadas não significa automaticamente uma redução no tempo de computação.

imagem
FIG. 1. Forma paralela de camada para calcular uma expressão,

mas mais uma opção pode ser considerada, que já é representada por uma infinidade de formas paralelas de camada que resolvem um único problema. Na fig. A Figura 2 mostra exatamente essa solução. O tempo de computação diminuiu. A paralelização do NPS também pode ser atraente, levando em consideração sua execução em sistemas multiprocessadores.

imagem
FIG. 2. NPS paralelo

Se você girar o gráfico JPF, poderá obter o esquema da computação em pipeline. Nele, os elementos do transportador serão camadas, cujo tempo de operação é reduzido para a camada mais lenta. Na fig. A Figura 3 mostra esse esquema de pipelining da expressão original.

imagem
FIG. 3. Modelo de tubulação

Como para este exemplo, o tempo discreto do transportador é de 5 ciclos de relógio, o tempo de cálculo será ainda pior que a pior versão do NPS. Vantagens do pipeline apenas na continuidade dos cálculos.

3. Um modelo de autômato para calcular expressões


Se você remover as restrições na sincronização das operações, o NPS poderá ser transformado em um circuito que gerará o resultado como um pipeline, mas sem restrições relacionadas à sequência e ao tempo das operações. Esse diagrama de rede lógico com uma demonstração da operação de adição (a implementação da multiplicação é semelhante) na forma de um modelo de rede de espaçonave é mostrado na Fig. 4.

imagem
Fig. 4. Cálculos de expressões baseadas em uma rede de máquinas de estados finitos

Você pode ver que a rede produz constantemente um resultado com um atraso de 7 ciclos de relógio, ou seja, bem como o modelo mais rápido do NPS (Fig. 7). Suas desvantagens incluem instabilidade de saída associada a corridas de dados. Por exemplo, uma alteração simultânea no valor das variáveis ​​nos pares de variáveis ​​g, he e, f levará a uma alteração em t4 no próximo ciclo de clock, após um ciclo de clock para uma alteração na variável t6 e outro ciclo de clock na variável de saída t7 (consulte a Fig. 1 e Fig. 4) . Ao mesmo tempo, após 5 ciclos de relógio, a variável t3 será alterada, o que levará a uma alteração e à saída dos valores finalmente estabelecidos das variáveis ​​t6, t7.

imagem
FIG. 5. Modelagem de NPS com uma rede de autômatos

Na fig. A Figura 5 mostra como a introdução de um bloco adicional torna possível simular a computação do NPS. Da mesma forma, você pode simular o modelo de computação em pipeline, bem como bloquear a alteração na saída associada às corridas de dados.

3. Conclusões


Seria estranho duvidar que as “figuras” acima não possam ser realizadas usando corotinas. Para ser sincero, eu não gostaria de fazer isso. Para mim, é muito mais fácil criar autômatos que implementam as operações necessárias e, alterando apenas o número e os relacionamentos entre eles, implementa o cálculo de qualquer expressão.

Não me canso de repetir que estou atraído pelo conceito de programação visual implementado no pacote Stateflow no MATLAB. Aqui você também pode criar as operações de autômato necessárias e, em seguida, usá-las, como blocos padrão, "desenha" um esquema de cálculo para qualquer expressão, que após a compilação se transforma em um programa de trabalho (por exemplo, no mesmo C ++). Ao mesmo tempo, durante o processo de design, estarão disponíveis ferramentas de visualização e depuração específicas da tecnologia de programação automatizada.

É verdade que a questão pode surgir - por que links permanentes para um determinado ambiente desconhecido do CPSU, se houver Stateflow? Mas falaremos sobre isso separadamente ainda ...

É uma coisa ingrata fazer previsões, mas, no entanto, com base na minha experiência, vou expressar um pensamento sedicioso: como linguagens de alto nível usadas para negar a programação em linguagem assembly, a programação visual, mais cedo ou mais tarde não menos aglomeração de programação em linguagens de alto nível.

Literatura

1. Programadores, vamos estudar as fontes dos programas clássicos. [Recurso eletrônico], Modo de acesso: habr.com/en/post/488808 grátis. Yaz. russo (data do tratamento 02.22.2020).
2. C ++ 20 aprovado! O que esperar e o que preparar para os desenvolvedores do C ++ 23. [Recurso eletrônico], Modo de acesso:habr.com/en/company/yandex/blog/488588 gratuitamente. Yaz. russo (data do tratamento 02.20.2020).

More articles:


All Articles