FPGA accelerator design for urban digital twins

Master Student Assistant (only EPFL master students can apply)

Background

Mixed-Integer Linear Programming (MILP) is a critical optimization technique widely used in a variety of industries to solve complex decision-making problems that involve both continuous and discrete variables. MILP formulations are employed in logistics for optimizing supply chain networks, in finance for portfolio optimization and risk management, in energy systems for grid management and resource allocation, and in manufacturing for production planning and scheduling. These industries rely on MILP to make informed decisions that balance multiple objectives such as cost, efficiency, and environmental impact.

A key application of MILP in the context of Urban Digital Twins is the Renewable Energy Hub Optimizer (REHO), a decision support tool designed for sustainable urban energy system planning. REHO addresses the optimal design and operation of urban energy systems, balancing multi-objective considerations such as economic viability, environmental impact, and energy efficiency. By leveraging MILP, REHO can simultaneously optimize capacities and operational strategies, providing robust solutions for sustainable urban development. However, the computational demands of MILP, particularly for large-scale urban models, present challenges in terms of energy consumption and processing time.

Despite its widespread application, MILP is computationally intensive, especially as problem sizes grow, which can result in significant energy consumption and long processing times. This has driven the need for more efficient computational solutions. Commercial (GUROBI) and open-source (HiGHS) methods rely on general-purpose processor parallel execution, which can lead to high energy consumption and long execution times, especially as problem sizes grow. This motivates the exploration of hardware accelerators, particularly Field-Programmable Gate Arrays (FPGAs), which offer the potential for parallel processing and energy-efficient computation.

Project Objectives

The motivation of this project is to design and develop novel energy-efficient hardware accelerators for solving MILP problems on FPGA platforms. For fast prototyping, we will adopt a hardware-software co-design approach to explore novel domain-specific accelerators using High Level Synthesis. By leveraging the parallelism and reconfigurability of FPGAs, the goal is to achieve significant energy savings while maintaining or improving the computational performance of MILP solvers.

 

Obligatory Objectives

  1. Understand and Describe MILP Kernels:
    • Conduct an in-depth analysis of key MILP algorithms, focusing on the most computationally intensive kernels.
    • Identify the parts of the MILP solving process that can benefit most from hardware acceleration.
  2. Implement and Optimize MILP Kernels on FPGA Using High-Level Synthesis (HLS):
    • Design and implement at least two critical kernels of the MILP solving process using HLS tools.
    • Focus on optimizing these kernels for energy efficiency, resource usage, and latency.
  3. Evaluate and Explore Design Trade-offs:
    • Conduct a comprehensive design space exploration to evaluate the trade-offs between energy consumption, computational latency, resource usage, throughput and hypermeters of the solver.
    • Present at least three Pareto optimal solutions for each implemented kernel, demonstrating the balance between these metrics.
  4. Experimental Evaluation on FPGA:
    • Test and validate the designed accelerators on a selected FPGA platform.
    • Measure and compare energy consumption, execution time, and solution accuracy against traditional CPU-based implementations.
    • [Optional] Experimental validation of the proposed designs on UrbanTwin MILP problems, showcasing the advantages of FPGA-based acceleration.

 

Additional Objectives

  1. Integration with Full MILP Solver Pipeline:
    • Integrate the optimized MILP kernels into a complete MILP solver pipeline on FPGA.
    • Evaluate the performance of the integrated system in terms of energy efficiency and computational throughput.
  2. Qualitative Analysis of Solution Accuracy:
    • Assess the accuracy and quality of the solutions provided by the FPGA-accelerated MILP solver.
    • Compare the results with those obtained from traditional software-based solvers, focusing on metrics such as solution optimality and robustness.

Required Knowledge and Skills

  • Proven experience in hardware description languages such as VHDL or Verilog.
  • Experience with Xilinx FPGAs or Intel FPGAs and associated development tools.
  • Strong programming skills in Python, C/C++, and familiarity with High-Level Synthesis (HLS) tools.
  • Understanding of optimization techniques, particularly MILP.

Type of Work

  • Theoretical Analysis (30%): Involves understanding MILP algorithms, energy-efficient design principles, and FPGA architecture.
  • Design and Experimentation (70%): Focuses on the implementation, optimization, and evaluation of the MILP kernels on FPGA.

This project will be conducted under the supervision of experts in hardware design and optimization from the Embedded Systems Laboratory (ESL) and Industrial Process and Energy Systems Engineering (IPESE), providing the student with an opportunity to contribute to cutting-edge research in energy-efficient computing.

Denisa-Andreea Constantinescu [email protected], Rubén Rodríguez Álvarez [email protected], Ana Catarina Gouveia Braz [email protected], Cédric Terrier [email protected], David Atienza Alonso [email protected]   

References