Exploration of Using a Different Memory Allocator for VTR Runtime Improvement

[stefanpie]

Note, this is an independent exploration that I conducted, and I don't expect that VTR authors to immediately consider these changes in VTR. I merely want to provide some useful insight into VTR I gained from my own research to the authors of VTR to help make VTR better.

Motivation

Recently, I've been looking at ways to speed up EDA tools without the need to make changes to the underlying code of the EDA tools themselves. For example, I want to try to make Vitis HLS or Vivado run faster, but I don't have access to the Vitis HLS or Vivado source code, and I can't change it unless I go work or intern for AMD/Xilinx. I want to explore approaches that would let me speed up commercial EDA tools in a "black box" manner. My original intent with this idea was that I could speed up EDA tools that interact with LLM agents, since the bottleneck there is the EDA tools (which can take >30s to minutes) and not LLM inference (which is usually <20s). But this is also a useful pursuit in general for large-scale EDA dataset collection and EDA benchmarking.

Approach

One trick in this exploration was to use a different memory allocator than the default malloc implementation that was compiled or linked with the software. For my exploration, I was testing the use of mimalloc (https://github.com/microsoft/mimalloc), a custom memory allocator from Microsoft Research, which has many tunable and customizable parameters. Even better, you can override the default allocator used by any software that dynamically links malloc using LD_PRELOAD to swap in mimalloc instead.

The general idea here is that (assuming our system has lots of memory resources) we can tune the memory allocator to take advantage of memory resources to trade off faster program execution for a small amount of memory overhead. This can hopefully result in non-trivial speedups in runtime over many program executions. For example, if I have to place and route 1000 benchmarks and I can get a 0.9x-0.8x reduction in runtime with a better memory allocator, my benchmark evaluation can take 9-8 hours instead of 10 hours. However, this model of what I would expect speedups to be is not that realistic. Program execution and memory allocation in a tool may be complex. Running the program on small designs might yield a 0.99x reduction (virtually nothing) while running the program on larger designs might yield a 0.8x reduction. Some programs or phases of program execution (synth vs. pack vs. place vs. route) might also see different behaviors and runtime reductions as well.

I decided to also try to evaluate this approach on open-source EDA software like yosys (still testing) and VTR, and I was able to capture some simple initial results for VTR just by swapping in mimalloc with minimal tweaking of the allocator configuration.

Evaluation

Note that these initial results are not valid since I made a mistake, but a mistake in favor of good results once corrected. See my later post in this issue thread with corrected and improved results. The experimental setup described here is still consistent and worth reading.

I benchmarked the VTR execution using two designs:

• mcnc_simple: $VPR_BIN --pack --place --route --analysis --write_rr_graph rr_graph.xml -j1 ./EArch.xml ./sqrt8.blif
• mcnc_big: $VPR_BIN --pack --place --route --analysis --route_chan_width 128 --write_rr_graph rr_graph.xml -j1 ./EArch.xml ./clma.blif
• mcnc_big_search: $VPR_BIN --pack --place --route --analysis --write_rr_graph rr_graph.xml -j1 ./EArch.xml ./clma.blif

Each case was executed with 48 samples each, all running in parallel on 48 cores (on a 64 core machine), with each VTR run using no parallelism inside VTR. During the execution there, the total used memory was always way lower than the total system memory, so there should have been no weird memory throttling or swapping behavior.

The figures below show the results. For each execution, there is a base version where the design files are read and written to disk, a version where design files are read and written to memory filesystem (using the shm mount), and the case where files are accessed from a memory file system and also mimalloc is dropped in place with minimal tweaking of the configuration. The runtimes of each of these cases is plotted as a "histogram" (really a KDE plot).

I also included some tables showing the normalized runtime for each method for the mean, median, 5%-th percentile and 95%-th percentile of runtimes. These are all normalized to the "base" approach which means files on disk and no mimalloc used.

Results for vtr__mcnc_simple

Method	Mean	Median	5% Quantile	95% Quantile
disk	1	1	1	1
shm	0.85	0.91	0.64	0.89
shm+mimalloc	0.92	0.93	0.78	0.95

Results for vtr__mcnc_big

Method	Mean	Median	5% Quantile	95% Quantile
disk	1	1	1	1
shm	0.97	0.92	1.02	0.96
shm+mimalloc	0.98	0.94	1.03	0.97

Results for vtr__mcnc_big_search

Method	Mean	Median	5% Quantile	95% Quantile
disk	1	1	1	1
shm	0.97	0.92	0.92	1.06
shm+mimalloc	0.96	0.89	0.94	1.04

I also conducted some (non-rigorous) non-parametric statistical tests (since I don't know if I can assume normality) to see if there is a statistically significant difference in runtime. Although I would not draw any conclusive results from these results without many more samples, it's just a nice thing to set up in the code that is useful once I can test many more samples across more designs.

# Statistical Analysis Report: vtr__mcnc_simple
## Mann-Whitney U Test Results
- SHM < Disk: U-statistic = 89.00, p-value = 0.0000
- SHM + Mimalloc < Disk: U-statistic = 197.00, p-value = 0.0000

# Statistical Analysis Report: vtr__mcnc_big
## Mann-Whitney U Test Results
- SHM < Disk: U-statistic = 467.00, p-value = 0.2751
- SHM + Mimalloc < Disk: U-statistic = 485.00, p-value = 0.3610

# Statistical Analysis Report: vtr__mcnc_big_search
## Mann-Whitney U Test Results
- SHM < Disk: U-statistic = 447.00, p-value = 0.1932
- SHM + Mimalloc < Disk: U-statistic = 405.00, p-value = 0.0764

Conclusion

Looking at the simple results so far, it seems like there is a compelling case here to be made to explore further the use of an alternative memory allocator, especially mimalloc. The initial results on three execution VTR cases with different designs and minimal tweaking to mimalloc suggest that 1) with minimal changes we can get ~0.9x reduction in runtime 2) more benchmarking across many more designs and execution modes of VTR is needed and 3) more exploration of how to configure mimalloc for VTR is also needed. Since VTR is open-source, unlike the commercial EDA tools that motivated this exploration, I can actually also gain some insight from the VTR code itself to help guide the configuration of mimalloc. I also want to note that I plan to run further experiments to disentangle the effects of the other techniques I explore, using an in-memory file system, from the technique I propose here, using a different memory allocator. In the current results, there are no results for just adding mimalloc when files are still being read from and written to disk. But hopefully, as I explore other black-box EDA tool speedup techniques, I can update my VTR results alongside my other results from other tools.

Hopefully this provides some useful insights for the VTR authors, and I am definitely open to discussion on this idea!

[stefanpie]

For reproducibility and reference, here is the repo with all my code I used to create these results. As I work on these EDA tool speedup techniques and more benchmarking, I'll update the repo with more results and code.

https://github.com/stefanpie/faster-hls

Note, I will also at some point likely update the repo name to be more generic than just HLS. I started by messing with HLS tools, so that's why it's called faster-hls.

[stefanpie]

Important update since I made a mistake in my original issue post, but a good mistake in favor of good results.

The initial results I shared are janky since mimalloc was never enabled even for the "shm+mimalloc" cases. I was using my portable statically linked version of VTR that I built, and since that statically links malloc from GLIBC, the LD_PRELOAD does not do anything, and mimalloc is never swapped in. This means that any improvement seen in the original results I posted is just by coincidence (maybe CPU warmup or some other system in the OS somewhere making it slightly faster).

However, this is a good mistake to have as I expect (and show below) that actually enabling mimalloc will show much more significant differences and would only speed up the program rather than make it slower.

To fix this, I also added another build to my portable VTR builds (see issue #3122 and my repo https://github.com/stefanpie/portable-vtr) with mimalloc statically linked overriding malloc from GLIBC. I then collected more results, but this time, anytime there is a test case with mimalloc and VTR, I use the new portable vpr-mimalloc build. For the normal VTR test cases with no mimalloc, I just use the original portable vpr build with malloc from GLIBC.

I also added a test case for using mimalloc but reading and writing files from disk. This means there are now four test cases: ("disk", "in-memory") x ("default malloc", "mimalloc").

Below are the updated figures and metrics.

Results for vtr__mcnc_simple

Method	Mean	Median	5% Quantile	95% Quantile
FS on-disk (base)	1	1	1	1
FS on-disk + mimalloc	0.82	0.85	0.9	0.72
FS on-disk + mimalloc + LC_ALL=C	0.89	0.92	1.02	0.8
FS in-memory	0.95	1.01	0.98	0.8
FS in-memory + mimalloc	0.86	0.92	0.89	0.74

Results for vtr__mcnc_big

Method	Mean	Median	5% Quantile	95% Quantile
FS on-disk (base)	1	1	1	1
FS on-disk + mimalloc	0.82	0.84	0.78	0.86
FS on-disk + mimalloc + LC_ALL=C	0.85	0.88	0.81	0.88
FS in-memory	0.96	0.98	0.9	0.99
FS in-memory + mimalloc	0.84	0.84	0.78	0.86

Results for vtr__mcnc_big_search

Method	Mean	Median	5% Quantile	95% Quantile
FS on-disk (base)	1	1	1	1
FS on-disk + mimalloc	0.62	0.62	0.62	0.62
FS on-disk + mimalloc + LC_ALL=C	0.62	0.63	0.59	0.63
FS in-memory	0.99	1.01	0.92	1.01
FS in-memory + mimalloc	0.61	0.63	0.59	0.62

# Statistical Analysis Report: `vtr__mcnc_simple`
## Mann-Whitney U Test Results
- SHM < Disk: U-statistic = 1070.00, p-value = 0.2752
- SHM + Mimalloc < Disk: U-statistic = 540.00, p-value = 0.0000
- Disk + Mimalloc < Disk: U-statistic = 413.00, p-value = 0.0000
- Disk + Mimalloc + LC_ALL=C < Disk: U-statistic = 744.00, p-value = 0.0014

# Statistical Analysis Report: `vtr__mcnc_big`
## Mann-Whitney U Test Results
- SHM < Disk: U-statistic = 992.00, p-value = 0.1213
- SHM + Mimalloc < Disk: U-statistic = 336.00, p-value = 0.0000
- Disk + Mimalloc < Disk: U-statistic = 315.00, p-value = 0.0000
- Disk + Mimalloc + LC_ALL=C < Disk: U-statistic = 376.00, p-value = 0.0000

# Statistical Analysis Report: `vtr__mcnc_big_search`
## Mann-Whitney U Test Results
- SHM < Disk: U-statistic = 1179.00, p-value = 0.5799
- SHM + Mimalloc < Disk: U-statistic = 0.00, p-value = 0.0000
- Disk + Mimalloc < Disk: U-statistic = 0.00, p-value = 0.0000
- Disk + Mimalloc + LC_ALL=C < Disk: U-statistic = 0.00, p-value = 0.0000

From these results, we do see real and very significant runtime reduction: ~0.9x on small designs that take less than a second to run, 0.85x on large designs that take on the order of 30s to run, and ~0.6x on large designs on the order of minutes where repeated implementation is done to search for the minimum channel sizes. These corrected results suggest that this approach is worthwhile and does result in noticeable runtime reductions. Also note that there is still some tweaking with mimalloc itself that can be configured at runtime (even when statically linked, you can still set mimalloc config values via env vars), which are still to be explored.

Sorry for the confusion with my original results, but it's good to see that proper integration of mimalloc shows significantly better results than expected!

[stefanpie]

I have one more update I wanted to share. After tweaking the data collection to only allow 16 concurrent processes on a 64-core machine to collect 128 samples per test case, the results are much clearer now. This is in comparison to before where I was collecting 128 samples per test case but using 48 concurrent processes on our 64-core machine. I believe the pressure on the CPU scheduler and also contention with some other processes other users were running caused much more interference in the previous results I reported.

As shown below, now the improvement is much clearer for all VTR test cases.

What's also cool is that now, for the tiny design that runs the implementation in under a second, we can see the effect of reading the Verilog and architecture XML files from different file systems much more clearly at this scale. The in-memory file system is faster and more consistent than reading from disk.

Also, for considering an "end-to-end VTR flow" that uses Yosys, I also compiled a portable static build Yosys and abc to also use mimalloc and compared the results of running a Yosys script with the synth_xilinx -family xc7 -abc9 ... command as the main synthesis and tech. mapping step (this will technically call abc from Yosys as well, which is why I had to rebuild both with versions that use mimalloc).

We also see significant speed-ups (~0.8x) with Yosys/abc as shown below.

This Yosys/abc build and results thereof will solve the issue of making sure end-to-end tool chain speed-ups in VTR using this technique don't suffer from Amdahl's law. Just speeding up vpr without also speeding up yosys and abc is not as productive as speeding up both. I am ignoring Odin and Parmys for now, but getting that built the same way with mimalloc and being able to load it into the portable mimalloc version of Yosys is just more build scripting tweaks that I don't foresee being an issue.