Cannot export large RRGs with Capnp

[AlexPoupakis]

Trying to write a large RRG as a binary file fails with the message tried to allocate list with too many elements. The RRG in question has ~250M nodes and ~750M edges. It seems that Capnp has a size limit of 2^29-1 (~536M) elements on individual Lists.

Expected Behaviour

The serializer should be able to write the RRG as a binary file regardless of the number of nodes/edges. Moreover, the serializer is especially useful for large RRGs, since their xml version can be >50 GB, making reading/writing in xml format unnecessarily time-consuming.

Current Behaviour

Executing VPR with the flag --write_rr_graph rr_graph.bin for large RRGs yields the error capnp/layout.c++:1227: failed: tried to allocate list with too many elements

Possible Solution

The bug exists because in the /libs/libvtrcapnproto/gen/rr_graph_uxsdcxx.capnp, the RrNodes and RrEdges structs define the nodes and edges respectively as Lists.

A potential fix, with backward compatibility in mind, is implementing a chunked schema and adding extra fields to struct RrGraph. Depending on the number of elements, the edges can be either stored as struct RrEdges or as struct RrEdgesChunks by modifying the reader & writer.

The existing /libs/libvtrcapnproto/gen/rr_graph_uxsdcxx.capnp looks like:

struct RrNodes {
	nodes @0 :List(Node);
}

struct RrEdges {
	edges @0 :List(Edge);
}

struct RrGraph {
	toolComment @0 :Text;
	toolName @1 :Text;
	toolVersion @2 :Text;
	channels @3 :Channels;
	switches @4 :Switches;
	segments @5 :Segments;
	blockTypes @6 :BlockTypes;
	grid @7 :GridLocs;
	rrNodes @8 :RrNodes;
	rrEdges @9 :RrEdges;
}

With the proposed solution it would look like:

struct RrNodes {
	nodes @0 :List(Node);
}

struct RrNodesChunks {
    chunks @0 :List(RrNodes);
}

struct RrEdges {
	edges @0 :List(Edge);
}

struct RrEdgesChunks {
    chunks @0 :List(RrEdges);
}

struct RrGraph {
	toolComment @0 :Text;
	toolName @1 :Text;
	toolVersion @2 :Text;
	channels @3 :Channels;
	switches @4 :Switches;
	segments @5 :Segments;
	blockTypes @6 :BlockTypes;
	grid @7 :GridLocs;
	rrNodes @8 :RrNodes;
	rrEdges @9 :RrEdges;
	rrNodesChunks @10 :RrNodesChunks;
	rrEdgesChunks @11 :RrEdgesChunks;
}

Context

Working with large, externally loaded RRGs is cumbersome via the xml format due to the large sizes and high read/write times. Supporting arbitrarily-sized RRGs via Capnp is both the expected behavior and the only way to reduce VPR's overhead.

[AlexandreSinger]

@amin1377

[AlexandreSinger]

After talking with @amin1377 during the weekly VTR meeting, Amin said that he ran into this problem before and he was able to set an option within CapNProto which increased th size that CapNProto uses.

We may want to expose a command-line option that allows us to increase the size of CapNProto's buffer; or we can just set it to a larger size if we think its worth it.

[amin1377]

For reading from a large Cap’n Proto file, we can increase the size with certain parameters. However, for writing, there is a hard 2 GiB limit on list size (as @AlexPoupakis mentioned). The simplest solution seems to be splitting nodes/edges into chunks. I tried several alternative approaches, but none of them worked.

Implementing this solution would require us to move away from the auto-generated Cap’n Proto handler code. I’m not sure what @vaughnbetz thinks about this, but personally I believe supporting larger devices with Cap’n Proto is more important. With proper testing for reading and writing Cap’n Proto files, we can minimize the risks of dropping the generated code and manually handling the related data structures.

In this issue, Fahri also mentioned a similar solution and highlighted that we may need to move away from the auto-generated code.

[amin1377]

Looping in @ganeshgore in case he has another solution in mind.

[vaughnbetz]

Ugh. This is a pain. Auto-generating this code is very nice, but the 2 GB limit is annoying.
@amin1377 : I suggest you make a presentation outlining the options and trade-offs for the Thursday meeting. Some things to address:

• What size of device hits the 2 GB limit?
• How hard is it to generate the capnproto code manually? Does it make sense to auto-generate the smaller data structures and just write specific code to create the rr_nodes and rr_edges? Or could we break the rr-graph into pieces and then auto-generate code to write each one out? Basically I'm trying to minimize how much code we have to manually maintain.

[amin1377]

@vaughnbetz: Sounds good. I’ll outline the solutions we have and address your questions in the meeting.