AAPack Failed to Route Sequential Feedbacks

[kmurray]

Originally reported on Google Code with ID 61

AAPACK reports: 

Complex block 0: cb.G14, type: MATRIX
        ..............
WARNING(2): Empty heap occurred in get_heap_head.
WARNING(3): Some blocks are impossible to connect in this architecture.
Failed routing net n39
Routing failed. Disconnected rr_graph.
Failed route at end, repack cluster trying detailed routing at each stage.
WARNING(4): Empty heap occurred in get_heap_head.
WARNING(5): Some blocks are impossible to connect in this architecture.
Failed routing net n39
Routing failed. Disconnected rr_graph.
WARNING(6): Empty heap occurred in get_heap_head.
WARNING(7): Some blocks are impossible to connect in this architecture.
Failed routing net n39
Routing failed. Disconnected rr_graph.
WARNING(8): Empty heap occurred in get_heap_head.
WARNING(9): Some blocks are impossible to connect in this architecture.
Failed routing net n39
Routing failed. Disconnected rr_graph.
WARNING(10): Empty heap occurred in get_heap_head.
WARNING(11): Some blocks are impossible to connect in this architecture.
Failed routing net n39
Routing failed. Disconnected rr_graph.
ERROR(1): Can not find any logic block that can implement molecule.
ERROR(2):       Atom G14

However, in blif file s298, 
  .latch n39 G14 re clk 0 #latch index:4
  .subckt cell0 I[0]=n63 I[1]=G14 I[2]=G0 O[0]=n39 #BLE index: 2 lgknd index: 10

Obviously, this is a very common feedback loop in state machines. 

In the given architecture, ble2x2_new_vpr.xml,
  I group all D flip-flops into a block called "follower" and all outputs of follower
are connected to the feedback crossbars. 
  For example: 
    <mux name="cell0_I0_mux" input="follower.O[0] follower.O[1] follower.O[2] follower.O[3]
MATRIX.I[0] MATRIX.I[1] MATRIX.I[2] MATRIX.I[3] MATRIX.I[4] MATRIX.I[5] MATRIX.I[6]
MATRIX.I[7] " output="cell0.I[0]">

So, I try to bypass AAPack through feeding VPR with *.net file directly. However, netlist
parser of VPR pass. But errors occurs:
  vpr: SRC/timing/path_delay.c:832: void alloc_and_load_tnodes(t_timing_inf): Assertion
`count > 0' failed.
Abort

  With help of gdb, what I have learned is VPR cannot find a connection from MATRIX.I.
No blif or netist information can be learned.

  Blif file, net file and architecture.xml are all attached.

  Thank you very much in advance.

Reported by tangxifan on 2013-06-13 15:21:01

---

• _Attachment: s298_K3_N4_mpack.blif_
• _Attachment: s298_K3_N4_mpack.net_
• _Attachment: ble2x2_new_vpr.xml_

[kmurray]

This architecture looks poorly constructed.  For example, I can't see how this architecture
can implement a shift register because there is no path for a flip-flop output to connect
to another flip-flop input.  You probably want to fix that.

Reported by JasonKaiLuu on 2013-06-14 16:59:10

• Status changed: WontFix

[kmurray]

When a shift register is implemented in FPGA, a LUT(programmed as buffer) is inserted
between two flip-flops. There is no need to have a path from one flip-flop output to
another. 
In the architecture file (I am sorry it is generated by a C program, which looks poor),
cell[i] corresponds to a LUT-like combinational logic. Cell[i] output is connected
to follower input via "comb_out[i]_mux" and then follower output is connected to cell[i]
input. This is how a feedback loop is implemented. It is the same with classical one.

Here is an example, 
  <mux name="cell0_I0_mux" input="follower.O[0] follower.O[1] follower.O[2] follower.O[3]
MATRIX.I[0] MATRIX.I[1] MATRIX.I[2] MATRIX.I[3] MATRIX.I[4] MATRIX.I[5] MATRIX.I[6]
MATRIX.I[7] " output="cell0.I[0]">
      <delay_constant max="4.5e-11" in_port="follower.O[0] follower.O[1] follower.O[2]
follower.O[3] MATRIX.I[0] MATRIX.I[1] MATRIX.I[2] MATRIX.I[3] MATRIX.I[4] MATRIX.I[5]
MATRIX.I[6] MATRIX.I[7] " out_port="cell0.I[0]"/>
   </mux>
  <complete name="comb_out0_mux" input="cell0.O " output="follower.I[0]">
   </complete>

   And in blif file, 
   .latch n39 G14 re clk 0 #latch index:4
   .subckt cell0 I[0]=n63 I[1]=G14 I[2]=G0 O[0]=n39 #BLE index: 2 lgknd index: 10

   n39 is mapped to cell0 in architecture file and latch is mapped to ff[0] inside
follower. Cell0 output (Net n39) connects follower input (follower.I[0]) via comb0_out_mux.
Follower outputs (Net G14) connects cell0 input through "cell0_I0_mux". 

   In this case, I don't know why AApack cannot pack it. Or it does not support "comb0_out_mux",
which is a intermedia connection between two pb_types?

Reported by tangxifan on 2013-06-14 17:46:27

[kmurray]

For your architecture to work, you are going to need to use a new AAPack feature called
pre-packing.  This feature enables you to inform the the packer that if a cell in your
architecture is followed by a flip-flop, then that cell and flip-flop form a pair that
should be kept together during packing.  Without this feature, AAPack might mistakenly
pack the cell in a different logic block than its corresponding flip-flop which results
in a failed pack.  To use pre-packing, take a look at the "pack_pattern" attribute
in the latest VPR manual.  

We will be describing this pre-packing feature in more detail in an upcoming paper.

Reported by JasonKaiLuu on 2013-06-14 18:03:38