DP-DP Algorithm

This repository contains the implementation of the Depth-First Post-Order Dynamic Programming (DP-DP) algorithm, as introduced in our paper Uirapuru, accepted at MobiCom 2025.

DP-DP is a fast, adaptive, and optimal video frame tiling algorithm that generates high-quality tile plans and efficiently maps deep neural network (DNN) models to each tile in a high-resolution video frame. This enables efficient inference and thereby supports real-time, high-accuracy video analytics for high-resolution camera feeds on edge devices. For a detailed explanation and experimental results, please refer to the paper.

Repository Structure

The repository is organized into the following directories:

• partition_and_map: Implements the DP-DP tiling algorithm (class DepthfirstPostorderDPSolver)
• models_mapping: Implements an optimal algorithm for mapping DNN models to a given tile plan. This is used for brute-force evaluation of tile partitioning and mapping.
• data: Contains a simulated dataset used to test and validate the algorithm.

How to Run

Note: We tested the algorithm with Python version 3.10.12.

Clone this repository, for example, into your $HOME directory:

git clone <this_repo_url> ${HOME}/dp-dp-algorithm

Running the DP-DP Algorithm

1. Build the Cython source code

$ cd ${HOME}/dp-dp-algorithm/partition_and_map/cython && ./build.sh
$ cd ${HOME}/dp-dp-algorithm/models_mapping/cython && ./build.sh

2. Navigate back to the partition_and_map directory and run the DP-DP algorithm:

$ cd ${HOME}/dp-dp-algorithm/partition_and_map
$ root_path="${HOME}/dp-dp-algorithm" ./run.sh