Mutual Information (MI) is a crucial similarity metric widely used in image registration. However, the intensive computational demands of histogram extraction and entropy computation make it a challenging task. While GPU and FPGA accelerations have seen advancements, AI Engines remain underexplored for this purpose.
This project presents a hardware-accelerated solution leveraging the AI Engine of the ACAP Versal VCK5000 for efficient entropy computation using joint and marginal histograms of two digital images. Our approach focuses on extensive parallelization across multiple tiles and SIMD operations, enhancing performance significantly.
Key highlights of this work include:
-
Novel Vectorized Logarithm Implementation: We introduce a new vectorized base-two logarithm function, absent in the current AIE API, which outperforms the Intel i7-4770 CPU and the existing AIE API logarithm implementation. This new function achieves a
$1.49\times$ speedup with minimal error margins for values in the range$[0, 100]$ . -
Performance Evaluation: Through three different graph implementations of the AIE, we observe substantial speedups in entropy computation for MI, particularly with parallelized kernels, achieving a
$9.71\times$ improvement. - Broader Applications: While focused on image registration, our method has potential applications in other areas requiring efficient MI computation, such as feature selection and cryptanalysis.
Before running the project, ensure you have the necessary tools and dependencies installed, which might include:
- Xilinx Vivado or Vitis tools depending on your hardware platform (
xilinx_vck5000_gen4x8_qdma_2_202220_1
in this case). - Make sure
make
utility is installed on your system.
-
Clone the Project Repository
git clone <repository_url> cd <project_directory>
-
Set Environment Variables Ensure that the
TARGET
andPLATFORM
variables are set correctly in the Makefile:TARGET
: Specifies the target platform (hw
orhw_emu
).PLATFORM
: Specifies the Xilinx platform (xilinx_vck5000_gen4x8_qdma_2_202220_1
in your case).
You can adjust these variables directly in the Makefile or pass them as arguments when invoking
make
. -
Build Hardware (xclbin) Objects
make build_hw TARGET=hw PLATFORM=xilinx_vck5000_gen4x8_qdma_2_202220_1
This command will compile the AIE (AI Engine), data movers, and link them into a hardware binary (
overlay_hw.xclbin
). Note that we have already included the bitstream in thehw
directory, so this step can be skipped. -
Build Software Object
make build_sw
This command will compile the software components located in the
sw
directory../host_overlay.exe
This command (in the
sw
directory) will run the build. -
Pack the Build
make pack
This command will copy the necessary files (
host_overlay.exe
andoverlay_hw.xclbin
) into abuild/hw_build
directory. -
Run Testbenches with x86 (Optional)
make testbench_all
This command will compile AIE for x86, set up testbenches for joint AIE, and marginal AIE, and sink from AIE in the
data_movers
directory. -
Run AIE kernels with VLIW architecture (Optional)
make all
This command will first compile AIE for VLIW and then simulate it in the
aie
directory. -
Clean Up (Optional)
make clean
This command will clean up compiled binaries and temporary files from all directories (
aie
,data_movers
,hw
,sw
).
Further optional commands can be found in the Makefiles in the different directories
To accelerate Mutual Information computation with the AI Engine, we developed two different AIE graph configurations:
![](https://private-user-images.githubusercontent.com/102242995/344492804-84390ea6-a05e-4bac-a186-33aa9de447f8.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQxMTAzODEsIm5iZiI6MTcyNDExMDA4MSwicGF0aCI6Ii8xMDIyNDI5OTUvMzQ0NDkyODA0LTg0MzkwZWE2LWEwNWUtNGJhYy1hMTg2LTMzYWE5ZGU0NDdmOC5wbmc_WC1BbXotQWxnb3JpdGhtPUFXUzQtSE1BQy1TSEEyNTYmWC1BbXotQ3JlZGVudGlhbD1BS0lBVkNPRFlMU0E1M1BRSzRaQSUyRjIwMjQwODE5JTJGdXMtZWFzdC0xJTJGczMlMkZhd3M0X3JlcXVlc3QmWC1BbXotRGF0ZT0yMDI0MDgxOVQyMzI4MDFaJlgtQW16LUV4cGlyZXM9MzAwJlgtQW16LVNpZ25hdHVyZT05NTYxNWJjZWVhMDdkY2QwMTJjZDVlOTZmZTI0NTU0ZjdlMmNjMTEzZDNjZWQyOTU0ZTY3MDg1MjI1ODk4YmIyJlgtQW16LVNpZ25lZEhlYWRlcnM9aG9zdCZhY3Rvcl9pZD0wJmtleV9pZD0wJnJlcG9faWQ9MCJ9.O3yYXCSINqFRu8rHUnQFFzgNA1nC5Cgx4kDEs2DM0-c)
The first graph features three kernels: one computes the marginal entropy from two input histograms, another computes the joint entropy from the joint histogram, and the third calculates the Mutual Information by subtracting the marginal entropy from the joint entropy. The first two kernels operate concurrently, while the third kernel waits for their outputs before proceeding.
![](https://private-user-images.githubusercontent.com/102242995/344492802-c0168625-3f6c-4324-9ab1-ceffeebb5a3f.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQxMTAzODEsIm5iZiI6MTcyNDExMDA4MSwicGF0aCI6Ii8xMDIyNDI5OTUvMzQ0NDkyODAyLWMwMTY4NjI1LTNmNmMtNDMyNC05YWIxLWNlZmZlZWJiNWEzZi5wbmc_WC1BbXotQWxnb3JpdGhtPUFXUzQtSE1BQy1TSEEyNTYmWC1BbXotQ3JlZGVudGlhbD1BS0lBVkNPRFlMU0E1M1BRSzRaQSUyRjIwMjQwODE5JTJGdXMtZWFzdC0xJTJGczMlMkZhd3M0X3JlcXVlc3QmWC1BbXotRGF0ZT0yMDI0MDgxOVQyMzI4MDFaJlgtQW16LUV4cGlyZXM9MzAwJlgtQW16LVNpZ25hdHVyZT1kNjhlZWQ3MDFlNGQ2YjkyZTIyM2Q5NTk1YjZjYTYyZGM4MjkzOTYzMjQ2Y2EzOGQ3Mjg3NGM3MmQ3M2NiMzc1JlgtQW16LVNpZ25lZEhlYWRlcnM9aG9zdCZhY3Rvcl9pZD0wJmtleV9pZD0wJnJlcG9faWQ9MCJ9.syqY5E8Q6tGMeKr3aptx9V77z5rSfCw9PS2FtPLYYLM)
The second graph implements a systolic array with 8 kernels organized in a 4x2 matrix for computing the joint entropy, 1 kernel for marginal entropy, and 3 kernels for a reduce-structure to compute the final MI value efficiently.
These configurations were designed to distribute computation evenly among AIE kernels, leveraging parallelism and optimizing throughput. The systolic array arrangement, in particular, enhances efficiency by allowing each kernel to process distinct portions of the histogram concurrently, significantly speeding up the entropy computation process.
The following table presents the performance comparison for the logarithm computation, highlighting the latency, throughput, and speedup of our proposed vectorized base-two logarithm implementation compared to the CPU and AIE utilities.
Method | Latency (ms) | Throughput (10^6 log/s) | Speedup |
---|---|---|---|
CPU (Intel i7-4770) | 1.78 | 73.636 | +0% |
AIE (utils) | 20.6 | 6.363 | -91.37% |
AIE (our) | 1.21 | 108.324 | +49.46% |
To test the AMD Versal VCK5000 on the computation of Mutual Information, we created a test bench that consists of computing the MI from the marginal and joint histograms of 11 progressively more aligned image couples. This allows us to test the performance on a test case that is as similar as possible to a real scenario.
![](https://private-user-images.githubusercontent.com/102242995/344493449-0a176de3-b095-4828-b5ec-c0f05b6a2294.gif?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQxMTAzODEsIm5iZiI6MTcyNDExMDA4MSwicGF0aCI6Ii8xMDIyNDI5OTUvMzQ0NDkzNDQ5LTBhMTc2ZGUzLWIwOTUtNDgyOC1iNWVjLWMwZjA1YjZhMjI5NC5naWY_WC1BbXotQWxnb3JpdGhtPUFXUzQtSE1BQy1TSEEyNTYmWC1BbXotQ3JlZGVudGlhbD1BS0lBVkNPRFlMU0E1M1BRSzRaQSUyRjIwMjQwODE5JTJGdXMtZWFzdC0xJTJGczMlMkZhd3M0X3JlcXVlc3QmWC1BbXotRGF0ZT0yMDI0MDgxOVQyMzI4MDFaJlgtQW16LUV4cGlyZXM9MzAwJlgtQW16LVNpZ25hdHVyZT1hZTk2ZjdjMTZiMTZhZGYyNzA5ZTJiMmI0Zjk1ZWUzYTkyYTJiZTdlZWI3OGQ1ZmU0NzRiZjYyNDU2MzMyZWFiJlgtQW16LVNpZ25lZEhlYWRlcnM9aG9zdCZhY3Rvcl9pZD0wJmtleV9pZD0wJnJlcG9faWQ9MCJ9.w2RxkVmTsnp86WdmvaB53KIqBENZfQrpKs97q4af9A8)
The following table summarizes the average latency and throughput measurements for MI computation using the CPU and AI Engine (AIE) configurations with 3 and 12 kernels.
Method | Mean Latency (ms) | Mean Throughput (jobs/ms) |
---|---|---|
CPU (Intel i7-4770) | 1.515 | 1.123 |
AIE (3 kernels) | 0.720 | 1.436 |
AIE (12 kernels) | 0.156 | 6.684 |
As shown in the performance comparison table, a single AIE tile achieves a speedup of
In future work, we will integrate our technique to compute Mutual Information (MI) within an image registration, to execute all stages of image registration on the AMD ACAP Versal VCK5000. While this study concentrated on Mutual Information for image registration, future research could also investigate accelerating the computation of Mutual Information in other domains, such as feature selection or cryptanalysis.