← Research

Robotics: Science and Systems / 2019

Shannon MI Accelerator.

High-throughput Computation of Shannon Mutual Information on Chip

Peter Zhi Xuan Li*, Zhengdong Zhang*, Sertac Karaman, Vivienne Sze · *Equal contribution

A mini-racecar exploration experiment with its occupancy map and mutual-information surface.
≈100×faster MI evaluation vs. single-threaded Xeon
≈2 WFPGA dynamic power
16 coresparallel FPGA computation

This FPGA evaluates sensor viewpoints by their expected reduction in map uncertainty. Co-designed memory and computation supply sixteen parallel cores with map data.

Selecting informative sensor viewpoints

An exploring robot must select viewpoints for subsequent sensor measurements. Shannon mutual information quantifies the expected reduction in map uncertainty from a measurement. Evaluating this quantity across candidate viewpoints guides information-based exploration.

Evaluating many viewpoints requires repeated access to the same map data. The memory organization and processing hardware are co-designed to supply map data for parallel calculations. The prototype uses programmable hardware called a field-programmable gate array (FPGA), whose logic can be configured to test a specialized architecture.

The map is a two-dimensional occupancy grid: each cell stores the probability that a region contains an obstacle. The hardware evaluates the Fast Shannon Mutual Information (FSMI) algorithm for multiple beams from a distance-measuring sensor. It supplies information estimates to a planner, while other robot systems handle motion and map construction.

Original FSMI exploration experiment, shown at 4× real time. The mini-racecar uses motion capture for localization; the paired views show its occupancy map with planned path and mutual-information surface. Source: MIT EEMS.

Memory bandwidth constrains parallel computation

Different sensor beams can be evaluated in parallel, but each processing core needs access to the map. The rate at which memory supplies these values is its memory bandwidth. When bandwidth is insufficient, additional cores spend time waiting for data.

The target FPGA’s standard memory blocks can read two independent addresses per clock cycle. Supplying sixteen cores by replication would require eight complete map copies, substantially increasing storage requirements. The memory architecture instead partitions one map across independently accessible memory banks, providing parallel access without that replication overhead.

Original RSS presentation comparison. Left: one occupancy-map memory offers Port 1 and Port 2 to many computation cores. Right: the same map is partitioned into Bank 1 through Bank M, with two read ports per bank feeding an arbiter and the cores.
Two memory ports limit concurrent access for independent beam calculations. Partitioning the map into banks provides parallel access paths, while an arbiter schedules competing requests.Source: Li, Zhang, Karaman, and Sze, public RSS 2019 presentation, PDF page 4.

Co-designing map layout and parallel computation

Partitioning the map adds read ports, but the assignment of cells to banks determines how effectively those ports are used. A memory-access conflict occurs when more than two distinct addresses in the same dual-port bank are requested in one cycle. The additional requests must wait.

Candidate sensor viewpoints can lie anywhere in the map, so the architecture must accommodate different ray origins and directions. Assigning entire columns or rows to individual banks can concentrate simultaneous requests in one bank. The examples below show this limitation: three rays request different cells from the same bank at cycle 5.

Original vertical banking diagram: columns identify eight memory banks. Three red circles mark distinct cycle-5 requests in Bank 4; green circles mark requests in other banks.
Column banking: the three red-circled requests compete for Bank 4. Colors identify banks; numbers identify access cycles.Source: Peter Li, CICS 2019 presentation.
Original horizontal banking diagram: rows identify eight memory banks. Three red circles mark distinct cycle-5 requests in Bank 3; green circles mark requests in other banks.
Row banking: changing the partition moves the conflict to Bank 3. Neither layout distributes these ray accesses evenly.Source: Peter Li, CICS 2019 presentation.

The architecture distributes the map across 16 memory banks in a diagonal pattern chosen for the paths of sensor rays. This arrangement reduces competition for the same bank. An arbiter schedules requests that still conflict. Each address also groups four neighboring cells, supplying more map data per read.

These architectural choices align the map layout with the algorithm’s access pattern and the FPGA’s memory interfaces. The spatial model remains an occupancy grid, while its physical organization supports parallel computation without duplicating the map. The animation and companion diagram show how sensor rays traverse the grid and how the banks distribute their accesses.

Original animation of colored sensor rays crossing a grid, with accessed cells appearing over successive cycles numbered one through eight.
Original RSS 2019 animation of memory cells accessed by sensor rays at successive cycles. The numbers 1–8 denote access cycles.Source: Li, Zhang, Karaman, and Sze, original RSS 2019 presentation, slide 5.
Sensor beams cross a grid on the left; a matching diagonal pattern assigns cells to different memory banks on the right.
Companion diagrams relate the memory-access pattern (left) to the diagonal bank assignment (right). The bank illustration shows eight banks; the implemented architecture uses sixteen.Source: Li, Zhang, Karaman, and Sze, RSS 2019 presentation, slide 5; cropped to the two diagrams.

Evaluation and limits

The FPGA prototype runs at 62.5 MHz on a Xilinx Zynq-7000 XC7Z045 device. It evaluates a complete 200-by-200-cell information map twice per second (2 Hz). This grid covers 20 m by 20 m at 0.1 m resolution. The 2 Hz rate refers to complete information-map evaluations for viewpoint selection. It does not describe camera capture, robot control, or occupancy-map construction.

The published comparison reports roughly two orders of magnitude faster computation than a single-threaded FSMI implementation on an Intel Xeon E5-4627 v2. That CPU runs at 3.4 GHz. The paper reports approximately 2 W for the FPGA implementation. Its resource table specifies 1.977 W of dynamic power. The CPU comparison uses approximately 22 W above its idle power. These figures describe the evaluated computation, rather than total robot or board power.

Throughput versus number of FSMI cores: one memory bank saturates, while sixteen diagonal banks with two-by-two packing closely approach the unlimited-bandwidth reference.
Increasing core count improves throughput when the memory architecture can supply the cores. Here L is the cell-packing factor: L = 2 packs a two-by-two block per address.Source: Li, Zhang, Karaman, and Sze, RSS 2019, Figure 13(c); extracted without changing the plotted data.

The throughput comparison shows why memory organization matters as core count increases. A single bank limits the benefit of additional cores, while diagonal banking with two-by-two packing approaches the unlimited-bandwidth reference. Under the evaluated scan configurations with 200-cell beams, computation time is less than 6% above that reference. The architecture supports up to 512 by 512 map cells.

Near-optimal banking for the SRC extension

The diagonal layout raises a broader question: how should map cells be distributed to minimize competition for memory? For the ACM Student Research Competition extension, I analyzed Latin-square banking patterns. Within each repeating tile, every row and column uses each bank once, distributing accesses across the available banks.

I proved that this family is near-optimal for memory-access conflicts under the analyzed ray-access model. The result applies as the number of beams from one scan location and one angular region tends to infinity. This analysis connects the geometry of map access to a principled choice of memory layout.

Original Latin-square banking diagram. A square tile repeats across the occupancy grid on the left. The enlarged eight-by-eight tile on the right contains one cell from each of eight banks in every row and column, with sensor rays and access-cycle numbers overlaid.
A Latin-square tile repeats across the occupancy grid. Eight colors identify the illustrated banks; numbers along rays mark access cycles. H is the map width in cells and B is the number of banks.Source: Peter Zhi Xuan Li, Sertac Karaman, and Vivienne Sze, Hot Chips 2020 presentation, slide 7; cropped to the original diagrams and legend.

The SRC extension also evaluates how banking and request scheduling work together. In the cycle-accurate ASIC simulation below, Latin-square banking increases throughput by distributing requests more evenly. A priority arbiter further reduces delays by selecting which pending requests each bank serves.

Original CICS throughput comparison for an ASIC design, showing one-bank, vertical banking with round-robin arbitration, Latin-square banking with round-robin or priority arbitration, and unlimited-bandwidth reference curves for 2 to 16 FSMI cores.
Simulated throughput for the SRC ASIC design. LS denotes Latin-square banking. The dashed line is an unlimited-bandwidth reference; each colored curve changes the banking pattern or request scheduler.Source: Peter Li, CICS 2019 presentation.

At 16 cores, vertical banking with round-robin scheduling reaches approximately 30% of the reference throughput. Latin-square banking raises this to approximately 72%; adding priority scheduling raises it to approximately 91%. These simulated results illustrate the combined effect of memory layout and scheduling. They complement the near-optimality analysis and are separate from the RSS FPGA evaluation above.

Continuous mutual information

The RSS prototype and the IROS 2021 follow-up are separate hardware designs. Keshav Gupta, Peter Li, Sertac Karaman, and Vivienne Sze developed the IROS accelerator for map-scale continuous mutual information. It evaluates all cells in a 201-by-201 grid in 1.55 ms using 1.7 mJ per evaluation on a Zynq-7000 FPGA. These results belong to the continuous formulation evaluated at IROS 2021.

ACM recognition

For this SRC extension, I received the gold medal at the ACM Student Research Competition at MICRO-52 (2019). I subsequently received first place in the graduate category of the 2020 ACM Student Research Competition Grand Finals. The recognized project was “A Mutual Information Accelerator for Autonomous Robot Exploration.” Official ACM Grand Finals results; official ACM MICRO-52 results; ACM announcement.

The RSS spotlight presentation begins at 2:46:02 in the conference recording.

Cite this work

High-throughput Computation of Shannon Mutual Information on Chip

BibTeX
@inproceedings{li2019rss,
  author = {Li, Peter Zhi Xuan and Zhang, Zhengdong and Karaman, Sertac and Sze, Vivienne},
  title = {High-throughput Computation of Shannon Mutual Information on Chip},
  booktitle = {Robotics: Science and Systems},
  year = {2019}, doi = {10.15607/RSS.2019.XV.058},
  note = {First two authors contributed equally}
}

Related research