ILP Based Multithreaded Code Generation for Simulink Model

Kai Huang 0002, Min Yu, Xiaomeng Zhang, Dandan Zheng, Siwen Xiu, Rongjie Yan, Kai Huang 0001, Zhili Liu, Xiaolang YanIEICE Trans. Information and Systems 2014 · DOI

Abstract

This paper introduces a novel framework for automatically generating high-performance multithreaded code from Simulink models for multiprocessor systems (MPSoCs). By combining a three-layered hierarchical software architecture (3LHS) with Integer Linear Programming (ILP) for optimal task mapping and scheduling, the proposed method achieves up to a 44% increase in throughput compared to traditional methods. The approach focuses on hiding communication latency and maximizing processor utilization through strategic thread management.

Introduction

As embedded applications, such as high-definition video processing, grow in complexity, engineers increasingly rely on Multiprocessor Systems-on-Chip (MPSoCs). However, programming these systems manually is a significant challenge, requiring developers to extract parallelism, manage complex inter-processor communication, and avoid deadlocks while maintaining high processor utilization.

While high-level tools like Simulink offer automatic code generation, the resulting code often suffers from poor performance due to two primary issues: low processor utilization caused by tasks idling for data, and high communication overhead from fine-grained threading. This research aims to bridge this gap by utilizing mathematical optimization to distribute workloads efficiently across hardware hierarchies.

Three-Layered Hierarchical Software (3LHS)

A core innovation of this work is the introduction of a middle Thread Layer to the traditional two-layer model (processor and task). This creates a Three-Layered Hierarchical Software (3LHS) architecture:

  • System Layer: Defines the global MPSoC environment, including CPUs and hardware interconnects.
  • Subsystem Layer: Groups tasks into specific threads assigned to individual CPUs.
  • Thread Layer: Contains the functional Simulink blocks that perform the actual computation.
The Three-Layered Hierarchical Software (3LHS) architecture showing System, Subsystem, and Thread layers.

This hierarchy enables "non-blocking" execution. If a thread on a CPU is stalled waiting for data from another processor, the system can immediately switch to another ready thread, preventing the CPU from idling.

ILP-Based Mapping and Scheduling

The framework employs Integer Linear Programming (ILP) to solve three critical optimization problems simultaneously:

  1. Processor Mapping: Assigning tasks to CPUs to balance workload while minimizing expensive inter-processor communication.
  2. Thread Mapping: Grouping tasks into threads to minimize intra-processor communication overhead.
  3. Intra-Thread Scheduling: A custom algorithm that orders blocks within a thread, strategically scheduling "send" blocks early and "receive" blocks late to "hide" communication latency.

Performance and Latency Hiding

The effectiveness of the 3LHS model lies in its ability to hide synchronization latencies. As shown in the execution sequences, traditional two-layer models (2LHS) often result in significant idle time while waiting for synchronization. By contrast, the 3LHS model allows for thread switching, which keeps the CPU productive during data transfer windows.

Comparison of execution sequences between 2LHS and 3LHS models, demonstrating how thread switching hides synchronization latency.

By pushing "receives" to the end of a thread's execution window, the intra-thread scheduling increases the probability that required data is already available when needed, further reducing stalls.

Experimental Results

The approach was evaluated using a functional model of an H.264 baseline decoder on an FPGA-emulated MPSoC platform. Key results include:

  • Throughput: A 44.34% increase in throughput compared to baseline configurations and an 18.08% improvement over standard automatic generation tools.
  • Utilization: Processor utilization in a 4-CPU setup increased from 35.63% to 64.02%.
  • Efficiency: The ILP mapping reduced inter-processor buffer sizes by 11.06% and idle state costs by 23.76%.

Conclusion

The proposed ILP-based multithreaded code generation framework significantly improves the performance of Simulink models on MPSoCs. By introducing an explicit thread layer and optimizing task placement, the system effectively hides communication latency. Future work will explore the scalability of ILP for massive models and the integration of software pipelining to further enhance utilization.

Summary updated

BibTeX
@article{huang2014ilp,
  author = {Kai Huang and Min Yu and Xiaomeng Zhang and Dandan Zheng and Siwen Xiu and Rongjie Yan and Kai Huang and Zhili Liu and Xiaolang Yan},
  title = {{ILP Based Multithreaded Code Generation for Simulink Model}},
  journal = {IEICE Trans. Information and Systems},
  year = {2014},
  doi = {10.1587/transinf.2014pap0015},
}
Figure