“Entropia, uma fonte ergódica, um espaço de mensagem multidimensional, bits, polissemia, o processo de Markov - todas essas palavras soam muito impressionantes, em qualquer ordem em que forem colocadas. Se você organizá-los na ordem correta, eles adquirem um determinado conteúdo teórico. E um especialista de verdade às vezes pode encontrar uma solução para os problemas práticos do dia a dia com a ajuda deles. ”
John PIRS "Não vejo o mal"
Este post está cheio de discussões sobre a otimização sutil de operações matemáticas no MK com recursos limitados, bem como avaliações subjetivas de vários aspectos do desenvolvimento de software incorporado.
Aqueles a quem esse aviso não assustou, pergunto em gato.
Antes de continuarmos a descrever o procedimento para extrair uma raiz quadrada de um número inteiro, a operação é inversa ao quadrado e, consequentemente, multiplicada, vamos falar sobre o último.
Suponha que tenhamos a oportunidade de multiplicar um número de 8 bits por um número de 8 bits, obtendo um resultado de 16 bits (8 * 8 = 16), como podemos obter a implementação da operação 16 * 16 = 32 com base nessa operação. A maneira óbvia é representar 16 como a soma de dois 8, então obtemos
(16)*(16)=(1(8)*256+2(8))*1(8)*256+2(8)) =1*1*256*256+1*2*256+2*1*256+2*2Se na expressão resultante substituirmos a multiplicação por 256 por um deslocamento à esquerda por 8 dígitos, obteremos um algoritmo completamente funcional. Vamos estimar o tempo gasto na implementação - precisamos de 4 multiplicações de 8 * 8 = 16 e 4 adições de números de 4 bytes 32 + 32 = 32. Para o AVR do tipo MK, obtemos 4 * 2 + 4 * 4 = 24 ciclos, mas isso é para uma solução "frontal". Vamos tentar melhorar o resultado. O fato de não precisarmos de 4, mas de 3 adições e uma atribuição simplifica um pouco a situação, já que o zeramento inicial do resultado não é necessário, mas ainda não o levamos em consideração, embora fosse necessário e o tempo total deveria ser de 24 + 4 = 28 ciclos. Mas, se levarmos em conta a presença de uma mudança nos três primeiros termos (respectivamente, temos que o mínimo (dois bytes baixos) é zero e não faz sentido adicioná-lo ao resultado), teremos que adicionar não 4 bytes, mas três e dois, o que reduzirá tempo de execução para 1 * 2 + 2 = 4 medidas e obtenha 20 medidas. Além disso, podemos prestar atenção ao fato de que o primeiro e o último termo não se cruzam, o que nos permite substituir o zeramento da metade mais alta do resultado pela atribuição do primeiro termo e reduzir o tempo de execução por outros 2 ciclos de relógio para 18. Além disso, usando os recursos arquitetônicos, ou seja, a presença do comando de transferência de registro pares, salve mais duas medidas e o resultado final - 16 medidas em vez dos 28 originais - um pouco, mas é legal.
Métodos de otimização semelhantes funcionam para a operação 32 * 32 = 32, para a qual você pode reduzir o tempo de execução do esperado 4 * 4 * (2 + 4) + 4 = 100 ciclos de clock para (3 + 5 + 4 + 3) + (5 + 3 +3) + (4 + 3) + 3 = 36 compassos, o que não é nada mau. Bem, ao final da consideração de várias opções de multiplicação, observamos que 16 * 16 = 16 podem ser obtidos em 3 + 3 + 3 = 9 ciclos. Observe que todas essas considerações são válidas apenas sob a suposição de que existe uma operação 8 * 8 = 16 para 2 medidas e, se não estiver no MK de destino, o tempo de execução de todas as outras versões da operação definitivamente não se tornará mais rápido.
Vamos resumir o tempo necessário para realizar a multiplicação (8 * 8 = 8 2, 8 * 8 = 16 9, 16 * 16 = 16 16, 16 * 16 = 32 36) e agora considerar o problema original.
Precisamos extrair a raiz inteira quadrada do número de 32 bits H, ou seja, encontrar o maior número de 16 bits n de modo que n * n <= H. Todos nós do curso secundário conhecemos o método de aproximação sucessiva à raiz quadrada (n = (N / n '+ n) / 2), mas ao usá-lo, teremos que dividir os números inteiros, e essa é uma operação que consome muito tempo.
Portanto, outros esquemas de cálculo foram desenvolvidos, um dos quais é o método de aproximação bit a bit, que no pseudo-código tem a seguinte aparência:
- valores iniciais -> n = 0; b = 0x8000;
- execute 16 vezes -> se ((n + b) * (n + b)> = H) n = n + b; b = b >> 1;
Você pode estimar imediatamente o tempo gasto nessa opção 16 (o número de bits do resultado) * (2 (organização do ciclo) +2 (adição) + X (multiplicação) +5 (comparação e solução) +2 (modificação do resultado) / 2 (média intervalo) +2 (deslocamento de bits)) = 16 * (12 + X). Você pergunta por que na fórmula X, em vez do número 16, e acontece que uma emboscada nos aguardava, já que estamos escrevendo em C, e não em montador. O fato é que na biblioteca padrão não há operação de multiplicação com uma alteração na profundidade de bits e não podemos aplicar 16 * 16 = 32, mas somos forçados a usar 32 * 32 = 32, o que leva a X = 36 em vez de X = 16 e o valor final é 16 * 48 = 768 ciclos de relógio para extrair o valor inteiro da raiz quadrada de um número de 32 bits.
Claro, isso é muito melhor que o método Newton, mas um pouco demais, vamos ver o que pode ser feito.
Portanto, é óbvio que a maior parte do tempo é gasta no cálculo do próximo resultado da multiplicação. Obviamente, você pode reescrevê-lo no assembler e usar a versão mais barata da multiplicação, obtendo 16 * (12 + 16) = 448 ticks, mas deixaremos esse caminho como último recurso. Considere o processo com mais cuidado e veja que não calculamos a multiplicação de um número aleatório por si só, mas sim a multiplicação do valor anterior com algum aumento, e o quadrado do valor anterior é conhecido. Portanto, podemos recorrer a um esquema de diferenças com base na fórmula (n + b) * (n + b) = n * n + 2 * n * b + b * b. À primeira vista, parece uma zombaria - em vez de uma multiplicação, precisamos fazer quatro partes e até duas adições de números longos (32 bits). Mas vamos começar a entender: já temos n * n, b * b, considerando que é fácil obter b = b '/ 2, como b' * b '/ 4, e da mesma forma 2 * n * b = 2 * n * b '/ 2.
Surge o seguinte esquema de cálculo:
- valores iniciais -> nn = 0; n = 0; b = 0x8000; bb = b * b;
- repita 16 vezes -> se (nn + n + bb> = H) {n = n + b; nn = nn + bb + n}; bb >> 2; b> 1;
Estimamos os custos de implementação 16 * (2 (organização do ciclo) +12 (atribuição e duas adições) +5 (comparação e solução) + (2 (adição) +8 (duas adições)) / 2 (intervalo médio) +8 (desloque-se para a direita em 2) +2 (desloque-se para a direita) = 16 * 34 = 544 ciclos de relógio.Melhor que com a multiplicação incorreta de 32 * 32, mas ainda temos reservas.
O que são - vamos prestar atenção à operação mais cara - adicionando e comparando um total de 17 ciclos de clock e refazendo o loop principal do algoritmo:
2. repetir 16 vezes -> T = H-bb-n; se (T> = 0) {H = T; n = n + b);}; bb >> 2; b> 1;
Então, o tempo de execução do ciclo será 16 * (2 (organização do ciclo) +12 (cálculo da nova diferença) +1 (comparação e solução) + ((4 (atribuição) +2 (adição)) / 2 (meio tempo médio) +8 +2) = 16 * 28 = 448 ciclos, se você levar em conta as peculiaridades da arquitetura, poderá salvar outros 2 + 2 = 4 * 16 = 64 ciclos e manter-se em menos de 400 ciclos.
Temos um resultado ainda melhor, como quando usamos a multiplicação correta 16 * 16 = 32, mas sem o assembler, "em C puro". No entanto, há um número negativo significativo - se tudo é intuitivo na versão com multiplicação, a variante com um esquema de diferenças sem comentários dá a impressão de uma sessão de magia negra, você deve escolher. Observe também que trocamos o número de medidas por memória adicional para variáveis intermediárias, o que geralmente acontece.
Nota necessária - não obtivemos um ganho significativo (às vezes) em comparação com multiplicações, pois temos uma implementação rápida de 8 * 8 = 16. Se ele estiver ausente no MK (e isso acontecer) ou não for tão rápido (e isso também acontecer), o esquema de diferenças se tornará várias vezes mais rápido, pois utiliza apenas operações padrão de adição e turno, que são garantidas em qualquer MK.
Parecia que não funcionaria melhor, mas, ao que parece, ainda existem reservas para aumentar o desempenho do algoritmo. Vamos tentar usar outro método clássico de aceleração - dividir e conquistar. E se você primeiro extrair a raiz quadrada da metade mais antiga do argumento e refiná-la? Primeiro de tudo, mostramos que isso é fundamentalmente possível. De fato, apresentamos o argumento na forma H = H '<< 16 + H' 'e o resultado na forma n = n' << 8 + n ''. Como n '' <256, seu quadrado obviamente será menor que o quadrado do número n = n '<< 8 + 256 = (n' + 1) << 8. Daqui resulta que a parte mais alta do resultado não excede a raiz quadrada da parte mais alta do argumento.
A implementação dessa abordagem é deixada para o leitor curioso.
O que essa abordagem nos fornecerá, porque o número total de iterações permanecerá inalterado - podemos realizar a primeira metade das iterações com números de menor duração, e isso leva a uma redução nos custos de tempo. Essa abordagem pode ser aplicada à variante com multiplicação e à variante da diferença; o ganho total será de até um quarto do tempo total de execução.
Nota necessária - a aplicabilidade dessa abordagem não é de todo óbvia. Ao implementar para MKs como o AVR, a aceleração da execução ocorre, mas para algumas arquiteturas, por exemplo, para x86, a desaceleração da operação apareceu inesperadamente. Aparentemente, trabalhar com dados não nativos (16 bits) nessa arquitetura é significativamente mais caro no tempo do que com nativos (32 bits). Não conduzi um estudo aprofundado, mas o fato ocorreu e devo relatá-lo para evitar mal-entendidos.
Mas isso não é tudo. Como já embarcamos no caminho da separação e do domínio, por que não ir além - extraia a raiz dos bits passo a passo, começando pelos mais antigos (começando pelos mais jovens é contraproducente no nosso caso). O esquema do algoritmo é o mesmo - adicionamos a próxima porção de bits no resultado atual e tentamos adicionar o próximo bit ao resultado, verificando se ultrapassamos o valor raiz. A peculiaridade é que só podemos verificar os bits mais altos do argumento, até chegarmos aos bits mais baixos.
Ao implementar, usamos mais um truque - em vez de mover nossos números subtraídos para a direita, moveremos nosso argumento decrementado para a esquerda, o significado não muda e a velocidade aumenta. Aumenta devido a dois fatores - 1) basta subtrair apenas números de 16 bits (há uma peculiaridade e isso deve ser levado em consideração, mas estamos considerando um estudo de caso, vout) e 2) não precisamos mudar o quadrado do próximo bit, pois sempre será igual a um. Mas você tem que pagar por tudo neste mundo e teremos um deslocamento da diferença estendida (6 bytes) para a esquerda e 2 bits por relógio. Veja pseudo código
- valores iniciais -> n = 0; H1 = 0;
- repita 16 vezes -> (H1, H) << 2; T = H1-n-1; se (T> 0) {H1 = T; n = n + 2}; n << 1;
e avalie o tempo de execução, obtendo 16 * (12 (turno estendido) +4 (calculando a diferença) +1 (solução) +2 (atribuição) +1 (aumento) +2 (turno)) = 16 * 22 = 352 medidas, talvez , o resultado está quase perfeito. Ao implementar esta opção, existem pequenas armadilhas, deixo isso de novo para o leitor curioso (bem, ele consegue o emprego).
Bem, na conclusão da seção que me levou a escrever este post. Existe uma biblioteca McuCpp absolutamente maravilhosa, de autoria de Anton Chizhov, na qual, com base na classe de autoria loki, Andriescu é extraordinariamente elegante (bem, na medida em que a elegância possa ser aplicada aos modelos C ++), trabalhe com pinos <a «
github.com/KonstantinChizhov/ Mcucpp »Tenho grande respeito pelo autor mencionado (ambos) e, recentemente, em conexão com as circunstâncias, que discutirei mais adiante, olhei as fontes desta biblioteca e mais uma vez admirado.
No entanto, entre outros arquivos, vi template_utils.h, no qual algumas rotinas auxiliares foram implementadas e, entre elas, uma raiz inteira de um número de 32 bits. O fato de usar o algoritmo de aproximação seqüencial mais simples com multiplicação não é assustador, pois esse algoritmo não perde muito em velocidade, mas na capacidade de compreensão, ele oferece muitos pontos à frente e ainda vence. Mas não gostei muito do fato de ter sido implementado de maneira imprecisa (em termos de desempenho), porque "as crianças podem vê-lo". A imprecisão consiste em representar o número selecionado com 32 bits, porque sabemos firmemente que a raiz do número de 32 bits não ultrapassará 16 bits, então por que precisamos mudar zero bytes. E este é exatamente o caso em que o próprio compilador nunca tentará realizar a otimização e deve ajudá-lo.
Conversão de função óbvia
static inline uint32_t sqrt(uint32_t value) { uint16_t result = 0; uint16_t add = 0x8000; for (uint8_t i = 16; i !=0; ++i) { uint32_t rootGuess = result | add; uint32_t guess = rootGuess * rootGuess; if (value >= guess) { result = rootGuess; } add >>= 1; } return result; }
nos permite salvar 2 ciclos em um deslocamento de bit e 2 ciclos na criação do próximo fator em cada ciclo, e organizar o ciclo na forma indicada são outros 4 ciclos (eu sei que o compilador pode fazer essa otimização para nós, mas por que não ajudá-lo explicitamente ), o que é bastante bom para alterações de código puramente cosméticas que não afetam sua compreensibilidade.
Nota posterior - um comentário me fez pensar que seria mais correto
for (uint_fast8_t i= ...)
Obrigado Oleg pela ajuda.
A cereja no bolo é a função de extrair toda a raiz quadrada do número do sinal localizado logo abaixo, que afirma ser √-1 = 65635 = -1 Por outro lado, por que não, o que é pior do que qualquer outro resultado, isso não é exceção para nós? causa no MK, e a raiz quadrada inteira de um número negativo não existe.
Bem, a conclusão sobre o motivo pelo qual me voltei para a biblioteca de Anton Chizhov. Fui solicitado por um post recente sobre o RTOS doméstico para MK sob o nome MAX (MultiAgent Coherent System) - veja a epígrafe do post anunciado por seus criadores e portado para o MK fabricado por Milander. Nota - este post não é de forma alguma material promocional e logo ficará claro para os leitores. Dos autores do mcucpp mencionados acima, o SO usou a implementação de um buffer de anel (sem diminuir as vantagens da biblioteca Anton, devo dizer que essa parte não é uma referência e ainda é uma formulação suave, sobre a qual escrevi em outro post que não publicarei). Como trabalho em estreita colaboração com as instalações de produção de Milander, o material me interessou e eu seguimos o link para o site dos desenvolvedores.
Aqui começa o próximo grito de Yaroslavna.
No ano passado, quando a criação do RTOS doméstico foi anunciada pela primeira vez, baixei uma descrição do produto de software deste site, mas de alguma forma minhas mãos não chegaram ao estudo. Pela natureza da minha atividade, eu tenho que lidar com componentes domésticos (eu entendo o suficiente ...), então seria bom ter o software apropriado. Lembrando que, no lançamento do ano passado, o diretor da empresa falou sobre os milhões de rublos gastos no desenvolvimento e a grande equipe que trabalhava na criação desse produto de software, decidi ver a versão de teste disponível para download gratuito e aqui estou compartilhando os resultados.
Para começar, a descrição por meio ano quase caiu pela metade (de 115 para 55 páginas) e, se o desaparecimento de aplicativos com capturas de tela descrevendo o processo de lançamento de produtos da "Descrição do programa" é bem-vindo, não a aparência desses materiais (para a criação dos quais Gastei, embora não seja muito significativo, mas ainda tempo e dinheiro) em um documento como o "Guia do Operador". Pessoalmente, estou perplexo. Além disso, na primeira frase do documento, vemos um desvio franco da verdade, uma vez que o próprio RTOS não se destina a "criar programas" de forma alguma, por algum motivo os autores não se permitiram tais declarações na versão anterior do documento, a influência do serviço de marketing é sentida. Ele também fornece que, se a descrição costumava estar na pasta / docs do diretório raiz, e isso era lógico, agora está oculto em / toolchain / macs / docs, bem, como disseram na minha juventude: "todo mundo está louco à sua maneira", seguimos em frente.
Começo a olhar para a descrição, olhando para o código fonte (ele está gentilmente incluído na versão de teste) e, perplexo, encontro a ausência de drivers de dispositivos periféricos adaptados para trabalhar com este sistema operacional. Primeiro, sugeri que esse é um recurso do teste; depois, no fórum, nas informações dos desenvolvedores, acho que realmente não há drivers, mas eles estão trabalhando nisso. Mais de seis meses (seis meses, Carl, na verdade, quase um ano) a partir do momento em que o sistema operacional foi lançado para o MK, e eles trabalham com drivers. Naturalmente, ou como se costuma dizer, não é preciso dizer que não se pode falar de terceiros (sistema de arquivos, pilha de rede, pilha USB). Uma ideia engraçada dos autores sobre os requisitos para o desenvolvimento de software para o MK, tudo bem, dirigiu novamente.
Ou seja, o SO declarado, cujo recurso destacado é a organização da interação dentro de um sistema com vários controladores, não possui meios nativos de organizar essa interação. O que temos na linha de fundo - e temos gerenciamento de tarefas, na verdade, um sheduler, serviço de tempo mínimo e meios de sincronizar tarefas, e isso é tudo - engraçado, para dizer o mínimo. Tudo bem, analisaremos ainda mais, mesmo em um conjunto de componentes que são interessantes soluções possíveis, especialmente considerando que em um site (não na empresa do fabricante) vi um "exame" do código fonte deste sistema operacional por referência. Este documento disse que o produto de software não usa componentes de terceiros (importação) e é original, seria necessário ter certeza.
A primeira observação é que, se você usar arquivos ARM originais incluídos no pacote de código-fonte para portar para uma arquitetura específica do Cortex-M0 (BE1T 1986), isso será muito semelhante ao uso de fragmentos de texto de terceiros (importados) - pessoalmente acho que esse é o uso, mas Provavelmente não sei tudo. Bem, e em segundo lugar, o código-fonte do sheduler e dos componentes relacionados ao gerenciamento de tarefas é realmente original e não tem análogos (pelo menos não conheço nenhum), mas esse é o tipo de originalidade quando recordo a frase do velho xamã do filme "O espírito maligno de Yambuya" sobre o grande caçador: "Corte as orelhas, cozinhe e coma - você teria adivinhado?"
Vou tentar explicar - no design do sistema operacional em geral e no RTOS em particular, uma das questões complexas é a questão de garantir o acesso de todos os processos no sistema a um recurso compartilhado - tempo de execução do processador.
O fato é que um sistema projetado incorretamente (e uma tarefa mal escrita) pode bloquear a execução de todas as tarefas com uma prioridade mais baixa, o que certamente irá confundir o programador. Não se trata de executar operações proibidas, como controle de interrupção (este é um tópico para uma discussão separada e simplesmente não possui uma solução na estrutura de MKs simples, embora os autores do SO em questão afirmem ter resolvido esse problema usando o MPU), mas de execução contínua sem esperar.Esse problema é amplamente conhecido, pode ser resolvido de diferentes maneiras, há extensa literatura disponível sobre esse assunto, como regra, um conjunto de filas de tarefas com prioridades diferentes e um sheduler modificado são usados. Isso requer certos custos para organizar filas com tempo de acesso O (1) e, por exemplo, no FREE-RTOS, ao tentar definir mais de 20 possíveis níveis de prioridade, o programador recebe uma pergunta confusa do compilador e se ele realmente precisa tanto (e mesmo se essa pergunta existe uma resposta afirmativa, sem modificar o código fonte, você não pode obter tantas prioridades).Portanto, fiquei um pouco surpreso ao descobrir que o sistema operacional em questão permite que você tenha até 60 prioridades (e até mais). A surpresa se espalhou quando olhei através da fonte. Em vez de filas de tarefas separadas com prioridades iguais, os autores usam uma fila (também existe uma segunda fila de tarefas bloqueadas) pronta para a execução de tarefas, o que ajuda a economizar memória (provavelmente esse era o objetivo de uma solução) devido ao fato de que- a operação de adicionar uma tarefa à fila se torna O (n) e
- isso torna impossível o uso de um sheduler modificado - na minha opinião, um pouco caro por 20 * (3 * 4) = 240 bytes de RAM. A solução é incomumente original, mas, do meu ponto de vista, essa é sua única vantagem.
Em geral, eu ainda não entendia o motivo pelo qual os autores receberiam dinheiro (mas ainda não decidiram fazer isso, a julgar pelo fórum) e quais soluções e recursos específicos tornam possível dar ao software um nome tão retumbante. Especialmente considerando a quantidade de software fornecida gratuitamente por vários fornecedores de MK (é claro, importados). Enquanto navegava no fórum da empresa na tentativa de encontrar uma resposta, vi referências ao produto de software mcucpp mencionado anteriormente (os autores da MAKS foram supostamente inspirados pelas idéias de Chizhov - três vezes ha), nas quais descobri uma falha menor descrita acima.A conclusão desta seção é que, se outras decisões sobre substituição de importações no campo de software forem implementadas de maneira semelhante com resultados de qualidade semelhante, as perspectivas de construção de sistemas embarcados domésticos me parecerão muito mal definidas.Concluindo, eu gostaria de voltar ao manual (não, não um desenvolvedor de SO, nem quero mencioná-lo ao lado de bons desenvolvedores) do desenvolvedor da empresa e fabricante do MK - Milander mencionado. Você faz bons microcontroladores (não vou mentir, eles são inferiores em parâmetros aos análogos estrangeiros, mas não fatalmente), por exemplo, ao mesmo tempo (em 2013), o BE1T era quase o melhor entre os colegas de classe, mas no quintal de 2019 e durante esse período muitos os alcançaram. e superado.Mas, se o bom MK produzido pela empresa não tiver:- ( , ) ( , , , , ),
- ( ),
- () 2,
- HAL, CMSIS (- ),
- ,
- ,
- (3rd part), ,
- ,
- ,
- , (, , ..) « »,
- , , ( , , MIT , « »), , (?).
Obviamente, tudo isso não aparece por si só e custa dinheiro, mas parece-me que uma empresa do seu nível poderia arcar com o trabalho de 5 pessoas por seis meses para criar tudo isso acima (com exceção da cláusula, talvez cláusula 10, embora agora todas sejam significativas e muitos pequenos fabricantes de MK têm seu próprio IDE). Se isso for realizado, o solo desaparecerá para a aparência de artesanato, como o SO descrito neste post.Embora possa ser que eu não saiba algo e, na verdade, não seja tão simples, é uma pena que seja realmente assim.Peço desculpas antecipadamente se minhas anotações parecerem muito duras, foi você (Milander) que eu não quis ofender.