Polyhedral Analysis of Streaming Task-Parallel Applications

  • Nuno Miguel Nobre

Student thesis: Phd


The microprocessor industry constantly welcomes new hardware features. Within the last two decades alone, it witnessed the revolution that took desktop computing from the traditional uniprocessor to the ubiquitous multiprocessor, the pervasive adoption of the energy-minded heterogenous multiprocessor on mobile devices, and the emergence of on-chip specialised accelerators. Supporting the programmer in the development of parallel, efficient and portable applications has thus never been more relevant. Task-parallel programming is an increasingly popular solution to unleash the parallel processing power of modern architectures. By omitting platform-specific code and leaving the choice of when and where to execute tasks to a runtime system, it enhances performance portability. Yet, the programmer is still responsible for defining tasks and their interactions, ultimately dictating performance-sensitive properties such as the available concurrency, data access patterns and data communication volume. We leverage polyhedral compilation techniques to boost programmer productivity for OpenStream, a streaming dataflow language supporting the specification of concurrent tasks communicating through streams. First, we introduce a task fusion algorithm which improves performance by increasing data reuse within tasks and reducing communication volume across tasks. Second, we study program execution within limited memory by considering a subset of runtime behaviour where stream sizes fall below specified bounds, and exploit polynomial extensions to the polyhedral model to devise a strategy capable of conservatively certifying execution under such conditions.
Date of Award1 Aug 2022
Original languageEnglish
Awarding Institution
  • The University of Manchester
SupervisorGraham Riley (Supervisor) & Antoniu Pop (Supervisor)


  • Bounded Scheduling
  • OpenStream
  • Task Fusion
  • Streaming
  • Polyhedral Model
  • Dataflow

Cite this