DAG: собственная ссылка HASH: поиск родителя первого уровня от любого потомка уровня, а затем поиск листьев этого родителя - PullRequest
Новая
       3

DAG: собственная ссылка HASH: поиск родителя первого уровня от любого потомка уровня, а затем поиск листьев этого родителя

4 голосов
/ 13 июня 2011

У меня есть netlist (набор подсхем) принципиальной схемы, как правило, создается неким SPICE-симулятором.Обычно он имеет иерархию (подсхема верхнего уровня вызывает или создает экземпляры различных подсхем и определяет некоторые соединения между ними через контакты).Пример списка соединений выглядит следующим образом: 

subckt AN2D0 A1 A2 VDD VSS Z

    M_u2 (net5 A2 VDD VDD) pch 
    M_u1 (net5 A1 VDD VDD) pch 
    M_u3 (Z net5 VDD VDD) pch 
    M_u4 (net17 A2 VSS VSS) nch 
    M_u2 (Z net5 VSS VSS) nch 

ends AN2D0

subckt LS_RX_CONTROLLER VDD VSS burst_start_or_sys burst_start_out pd pd_pwm_det pd_pwm_det_TII std_by std_by_or_sys sys_en sys_out

    I2 (burst_start_or_sys std_by VDD VSS burst_start_out) AN2D2
    I1 (net22 std_by_bar VDD VSS sys_out) AN2D2
    I5 (net022 pd VDD VSS pd_pwm_det) OR2D2
    I10 (net026 pd VDD VSS std_by_or_sys) NR2D2
    I9 (sys_en std_by VDD VSS net026) NR2D0
    I6 (std_by VDD VSS std_by_bar) INVD0
    I3 (pd_pwm_det_TII net037 VDD VSS net022) OR2D0
    I11 (sys_en std_by VDD VSS net037) OR2D0
    I0 (burst_start_or_sys sys_en VDD VSS net22) AN2D0

ends LS_RX_CONTROLLER

Теперь в разных иерархиях может быть реализована одна и та же подсхема.Каждая вызываемая подсхема определяется перед вызывающей подсхемой.Этот вид графика называется Направленный ациклический ГРАФ.Я сделал самозадерживающуюся таблицу HASH из списка соединений, чтобы сэкономить место.Если подсхема вызывает какой-либо экземпляр подсхемы, она затем указывает на вывод.В самой последней иерархии мы получим узел MOSFET D или S или G или B (так как была определена подсхема AN2D0).Если какая-либо сеть (соединение между выводом экземпляров) выводится из иерархии (ничего кроме вызова подсхемы, например, net5) к родительской вызывающей подсхеме, она называется pin (например, Z) и всегда будет указана в следующей строке определения подсхемыпо его названию ( subckt AN2D0 A1 A2 VDD VSS Z ).Я создал хэш хэшей хэшей. 

GRAPH --> subckt1--->p1
                     p2
                     net1
                     net2
          subckt2--->p1
                     p2
                     net1
                     net2
          subckt3--->p1 ---->I1.subckt1.p1--->pointing to value of p1 key of subckt1.
                             I2.subckt1.p2
                     p2
                     net1
                     net2

В данном случае GRAPH выглядит следующим образом: 

the name of subcircuit-->AN2D0

     name of pin or net-->Z
         name of instant connected to it-->M_u2.nch.D
         name of instant connected to it-->M_u3.pch.D
     name of pin or net-->VDD
         name of instant connected to it-->M_u1.pch.S
         name of instant connected to it-->M_u1.pch.B
         name of instant connected to it-->M_u2.pch.S
         name of instant connected to it-->M_u3.pch.S
         name of instant connected to it-->M_u2.pch.B
         name of instant connected to it-->M_u3.pch.B
     name of pin or net-->A1
         name of instant connected to it-->M_u3.nch.G
         name of instant connected to it-->M_u1.pch.G
     name of pin or net-->VSS
         name of instant connected to it-->M_u2.nch.S
         name of instant connected to it-->M_u4.nch.B
         name of instant connected to it-->M_u2.nch.B
         name of instant connected to it-->M_u3.nch.B
         name of instant connected to it-->M_u4.nch.S
     name of pin or net-->net5
         name of instant connected to it-->M_u3.nch.D
         name of instant connected to it-->M_u3.pch.G
         name of instant connected to it-->M_u1.pch.D
         name of instant connected to it-->M_u2.pch.D
         name of instant connected to it-->M_u2.nch.G
     name of pin or net-->A2
         name of instant connected to it-->M_u4.nch.G
         name of instant connected to it-->M_u2.pch.G
     name of pin or net-->net17
         name of instant connected to it-->M_u3.nch.S
         name of instant connected to it-->M_u4.nch.D

the name of subcircuit-->LS_RX_CONTROLLER

     name of pin or net-->burst_start_or_sys
         name of instant connected to it-->I2.AN2D2.A1
            M_u3.nch.G
            M_u1.pch.G
         name of instant connected to it-->I0.AN2D0.A1
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->burst_start_out
         name of instant connected to it-->I2.AN2D2.Z
            M_u2.nch.D
            M_u3.pch.D
     name of pin or net-->net037
         name of instant connected to it-->I11.OR2D0.Z
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I3.OR2D0.A2
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->net026
         name of instant connected to it-->I10.NR2D2.A1
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I9.NR2D0.ZN
            M_u3.nch.D
            M_u2.pch.D
            M_u4.nch.D
     name of pin or net-->std_by
         name of instant connected to it-->I9.NR2D0.A2
            M_u3.nch.G
            M_u1.pch.G
         name of instant connected to it-->I6.INVD0.I
            M_u3.pch.G
            M_u2.nch.G
         name of instant connected to it-->I2.AN2D2.A2
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I11.OR2D0.A2
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->sys_en
         name of instant connected to it-->I11.OR2D0.A1
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I0.AN2D0.A2
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I9.NR2D0.A1
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->VDD
         name of instant connected to it-->I2.AN2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.S
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I10.NR2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.B
         name of instant connected to it-->I0.AN2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.S
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I6.INVD0.VDD
            M_u3.pch.S
            M_u3.pch.B
         name of instant connected to it-->I9.NR2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.B
         name of instant connected to it-->I1.AN2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.S
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I11.OR2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I3.OR2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I5.OR2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
     name of pin or net-->sys_out
         name of instant connected to it-->I1.AN2D2.Z
            M_u2.nch.D
            M_u3.pch.D
     name of pin or net-->net022
         name of instant connected to it-->I3.OR2D0.Z
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I5.OR2D2.A1
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->pd_pwm_det_TII
         name of instant connected to it-->I3.OR2D0.A1
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->std_by_or_sys
         name of instant connected to it-->I10.NR2D2.ZN
            M_u3.nch.D
            M_u2.pch.D
            M_u4.nch.D
     name of pin or net-->net22
         name of instant connected to it-->I0.AN2D0.Z
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I1.AN2D2.A1
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->pd
         name of instant connected to it-->I10.NR2D2.A2
            M_u3.nch.G
            M_u1.pch.G
         name of instant connected to it-->I5.OR2D2.A2
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->std_by_bar
         name of instant connected to it-->I6.INVD0.ZN
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I1.AN2D2.A2
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->VSS
         name of instant connected to it-->I11.OR2D0.VSS
            M_u3.nch.S
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I5.OR2D2.VSS
            M_u3.nch.S
            M_u4.nch.B
            M_u2.nch.S
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I3.OR2D0.VSS
            M_u3.nch.S
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I6.INVD0.VSS
            M_u2.nch.S
            M_u2.nch.B
         name of instant connected to it-->I0.AN2D0.VSS
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I2.AN2D2.VSS
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I1.AN2D2.VSS
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I9.NR2D0.VSS
            M_u3.nch.S
            M_u4.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I10.NR2D2.VSS
            M_u3.nch.S
            M_u4.nch.B
            M_u3.nch.B
            M_u4.nch.S
     name of pin or net-->pd_pwm_det
         name of instant connected to it-->I5.OR2D2.Z
            M_u2.nch.D
            M_u3.pch.D

После этого имя подсхемы и ее вывод будутданные, которые могут быть созданы из любой иерархии уровней, и мы должны найти родителя, то есть отследить родителя до тех пор, пока сеть не будет выведена в качестве булавки.И затем отпряните все листья (MOSFETS D или G или S или B).

Пожалуйста, предложите, какой тип алгоритма лучше всего подойдет для этого, и эффективно ли сохранение их в хэш-таблице с самообращениемили нет.

1 Ответ

1 голос
/ 27 января 2012

По моему опыту, лучше использовать процесс индексации, чтобы сгенерировать уникальную идентификацию узлов в вашем графике, а затем создать плоский хеш, где ключом является этот идентификатор.Сделайте ссылки, используя идентификатор.Например:

a => b, b => c, c => d, d => a

означает

%graph = ( a => { content => ..., linksto => [ b ] }, b => { content => ..., linksto => [ c ] }, c => { content => ..., linksto => [ d ] }, d => { content => ..., linksto => [ a ] } );

...