加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 大数据 > 正文

algorithm – A DAG：自引用HASH：从任何级别的子级搜索第一级父

发布时间：2020-12-16 06:12:40 所属栏目：大数据 来源：网络整理
导读：我有电路原理图的网表(子电路的集合),一般是由一些SPICE模拟器创建的.它通常具有层次结构(顶层子电路调用或实例化不同的子电路,并通过引脚定义它们之间的一些连接性).示例网表如下所示： subckt AN2D0 A1 A2 VDD VSS Z M_u2 (net5 A2 VDD VDD) pch M_u1 (net
我有电路原理图的网表(子电路的集合),一般是由一些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

现在,在不同的层次结构中,可以实例化相同的子电路.每个被调用的子电路都在调用子电路之前定义.这种图称为有向无环GRAPH.我已经从网表中自我引用了HASH表以节省空间.如果子电路正在调用某个子电路实例,则指向该引脚.在最后一个层次结构中,我们将获得MOSFET D或S或G或B节点(因为已定义了AN2D0子电路).如果任何网络(实例的引脚之间的连接)从层次结构(除了调用子电路,例如net5)引出到父调用子电路,它被称为引脚(例如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引脚).

请建议哪种算法最适合此类,以及将它们存储在自引用哈希表中是否有效.

解决方法

根据我的经验,最好使用索引过程生成图中节点的唯一标识,然后创建一个平面哈希,其中键是此id.使用id创建链接.例如：

a => b,b => c,c => d,d =>一个

翻译成

??％graph =(????a => {content => …???????????linksto => [b]},????b => {content => …???????????linksto => [ C ] },????c => {content => …???????????linksto => [d]},????d => {content => …???????????linksto => [ 一个 ] }??);

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
    相关内容
      推荐文章
        站长推荐
        热点阅读

          【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

          建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

          Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同