Organizando células padrão (notas de alguém de fora)

Tendo encontrado o artigo " Destruindo o monopólio ... ", o autor, como pessoa, embora muito longe da EDA , mas naturalmente inquisitivo, não teve preguiça de seguir os links e involuntariamente se pegou pensando que uma das principais soluções técnicas é o uso de linhas de células padrão ( célula padrão layout) - parece bastante controverso.

Sim, esse arranjo é intuitivo, porque escrevemos e lemos de maneira semelhante. Além disso, é tecnologicamente simples organizar células em linhas, é muito conveniente conectar barramentos VDD e GND. Por outro lado, surge um problema combinatório complexo, é necessário cortar o circuito em peças lineares e organizá-las de maneira a (aproximadamente) minimizar o comprimento total das juntas.

E, claro, surgiu a questão de saber se existem soluções alternativas ... é isso que se ...


Figura 1 linhas típicas de células padrão ( daqui )

E se

Do ponto de vista da redução do comprimento total da ligação, seria útil organizar células padrão ao longo de algumas das curvas ex abrangentes : Peano ou Hilbert.

Essas curvas consistem em uma massa de vários "cantos e recantos", com certeza há uma configuração na qual as células padrão conectadas estão, em média, próximas umas das outras.
Ou pode servir como uma iteração zero para otimização adicional.


Figura 2 Curva de Hilbert, campos 8X8 e 64X64

1. As curvas de varredura são auto-semelhantes, o que se encaixa bem no conceito geral.
2. Eles têm uma alta localidade, ou seja, pontos localizados em algum lugar próximo da curva provavelmente estão próximos e no espaço.
3. Conter uma rede hierarquicamente organizada de canais.
4. Para o circuito lógico, você pode escolher um quadrado ou retângulo 1x2,2x1 adequado no qual ele é colocado em excesso e "movê-lo" ao longo da curva de varredura (consulte a Figura 3) para selecionar a geometria ideal, pois esse é apenas um grau de liberdade com uma função de custo bastante barata .
   
5. A conveniência da conexão dos pneus (VDD / GND) permanecerá.
6. ...

Figura 3 Três peças de uma curva de Hilbert com turnos diferentes.

Então:

• vamos experimentar com a curva de Hilbert
• vamos experimentar em um quadrado 64X64 (Figura 3)
• no passo elementar da curva, pode haver várias células e espaços padrão - quantas e em que ordem é o parâmetro do experimento
• todas as etapas elementares são organizadas de forma idêntica
• etapas elementares seguem uma sobreposição, ou seja, se a etapa começar com uma célula padrão, deve haver um espaço no final dela e vice-versa
• todos os espaços e células padrão são do mesmo tamanho - 1X1
• todas as células são serializadas em alguma ordem, essa ordem também é um parâmetro
• outro parâmetro é o deslocamento do início da curva (pontos (0,0)), a partir do qual organizaremos as células padrão em uma determinada ordem
  
• os comprimentos de ligação entre as células padrão são calculados de acordo com L1 (distância de Manhattan)
• a soma dos comprimentos de todas as ligações é o valor desejado, tendo determinado a quantidade mínima, encontraremos a localização ideal

E como um coelho experimental, vamos usar um somador de 8 bits. É bastante simples, mas não trivial. Existem muitos elementos e conexões para sentir os possíveis prós e contras. Ao mesmo tempo, não há número suficiente deles para poder experimentar "no joelho".

Totalizador

4 é um diagrama esquemático de um somador de bit único completo


Figura 5 Então, veja este utilitário gráfico Neato do graphwiz


6 adicionador assinado de 8 bits, aqui

Mas trabalharemos apenas com números inteiros, sem o sinalizador de erro W.


Fig. 7 Portanto, o somador de 8 bits vê o utilitário de pontos do graphwiz.

Parece uma dança de pequenos cisnes.


A Fig. 8 é o mesmo gráfico após a otimização usando neato.

Experiência 1

• etapa elementar da curva de Hilbert - (passagem, célula, célula, passagem)
• vértices gráficos (células unitárias) classificados em ordem alfabética

Fig.9 em X - mude desde o início, em Y - o comprimento de todos os caminhos

A distância mínima (a primeira de) em um turno de 207 (O comprimento total de todas as ligações é 1968), vamos ver como é esse arranjo ideal.


A Figura 10 é o gráfico ideal para o turno 207, não parece muito agradável.

Experiência 2

• etapa elementar da curva de Hilbert - (passagem, célula, célula, passagem)
• vértices do gráfico (células unitárias) na ordem natural (como veio na descrição do gráfico, veja a descrição do gráfico acima) -

11 em X - o deslocamento desde o início, em Y - o comprimento de todos os caminhos


Fig. 12 gráfico ideal para o cisalhamento 11, comprimento 750

Experiência 3

• etapa elementar da curva de Hilbert - (passagem, célula, célula, passagem)
• a ordem dos vértices é determinada atravessando a largura do gráfico, vértices sem links no início da lista, o fim de semana no final

Fig.13 em X - mude desde o início, em Y - o comprimento de todos os caminhos


Fig. 14 Arranjo ideal - turno 3, comprimento total 1451
Coloque todos os vértices de entrada no início e a saída no final não foi muito boa
uma ideia

Experiência 4

• o passo elementar da curva de Hilbert - (passagem, célula, célula) Sic!
• a ordem dos vértices é natural, como no experimento 2

Fig.15 em X - mude desde o início, em Y - o comprimento de todos os caminhos


Fig. 16 Arranjo ideal - turno 10, comprimento total 503

Experiência 5

Precisamos fazer algo com IO, definimos-os no pós-processamento, ou seja, para cada turno
construa um arranjo sem vértices de IO, depois construa um quadro de extensão absorvente ao redor do gráfico, aplique vértices de IO ao ponto mais desocupado do quadro e calcule o comprimento final

• etapa elementar da curva de Hilbert - (pular, célula, célula)
• a ordem dos vértices é determinada pela visualização em largura, mas sem vértices de IO

Fig.17 em X é o deslocamento desde o início, em Y é o comprimento de todos os caminhos


Fig. 18 A localização ideal é o turno 607, o comprimento total de 484, a média de 3,333793

Parece bom, mas e se otimizarmos não o comprimento total dos caminhos, mas sua soma com a área do retângulo ocupado. Suas dimensões são diferentes, portanto, assumiremos que calculamos não o comprimento do caminho, mas a área sob os caminhos.

Experiência 6

Os parâmetros são os mesmos do experimento 5, otimizamos a área.


Fig.19 em X - mude desde o início, em Y - o comprimento de todos os caminhos


Fig. 20 Arranjo ideal - turno 966, comprimento total 639, média 3,30345

O retângulo ficou bastante alongado. Mas e se considerarmos não a área do retângulo, mas o quadrado da hipotenusa, levando-nos a formas mais quadradas?

Experiência 7

Os parâmetros são os mesmos do experimento 5, otimizamos o quadrado da hipotenusa.


Fig.21 em X é o deslocamento desde o início, em Y é o comprimento de todos os caminhos


Fig. 22 Arranjo ideal - turno 70, comprimento total 702, média 3,46207

Experiência 8

• passo elementar da curva de Hilbert - (célula, pular) Sic!
• a ordem dos vértices é determinada pela visualização em largura, mas sem vértices de IO

Assumimos que o custo de andar em Y é duas vezes maior que em X, isso é mais próximo da realidade.

Fig.23 em X é o deslocamento desde o início, em Y é o comprimento de todos os caminhos


Fig. 24 Arranjo ideal - turno 344, comprimento total 650, média 3,8

Conclusões

Preliminar “escolha editorial” - experimento 6.

Seria bom organizar os vértices de IO, mas isso requer uma dica lateral,
onde exatamente (direção) essa classe de vértices deve estar localizada.

Mas primeiro eu gostaria de ouvir a opinião de especialistas.

PS : obrigado a YuriPanchul e andy_p pela falta de uma reação negativa reflexa.

UPD (11/02/2019): adicionada "experiência 8", em que as células padrão estão localizadas nos nós da curva de Hilbert, ou seja, estritamente em uma treliça quadrada. Além disso, por um lado, eles são combinados em linhas tradicionais e, por outro lado, estão localizados ao longo da curva de Hilbert.