Skip to Main content Skip to Navigation
Conference papers

Pipeline Optimization using a Cost Extension of Timed Petri Nets

Abstract : A major step in arithmetic operators design is the placement of pipeline stages, with the goal of drastically increase the data throughput. Approaches, such as the as-soon-as-possible greedy algorithm, allow pipelining with a frequency target. They can possibly be combined with a retiming operation to reduce the number of pipeline registers. This retiming step is based on a weighted directed graph model, from which the pipeline placement is reduced to an optimisation problem (for example ILP). However, this approach produces only a unique solution, and makes it difficult to add additional constraints on the resulting pipeline. We propose to use a Timed Petri Net extension with cost, where time captures the propagation delay and cost measures the size of pipeline registers. The state space of the model captures exactly the circuit states and the branching points, so its exploration can be guided by comparing the circuit states regarding any feature (number and size of registers, critical path, throughput, etc). The pipeline exploration can be reduced to a weighted branching-time logic model-checking problem, that we prove to be PSPACEcomplete on this model. We have implemented this exploration algorithm in a prototype tool. We apply it on some arithmetic operators provided by FloPoCo showing improvements up to 35% compared to the current implementation.
Document type :
Conference papers
Complete list of metadata
Contributor : Rémi Parrot Connect in order to contact the contributor
Submitted on : Friday, December 3, 2021 - 10:37:12 AM
Last modification on : Wednesday, January 19, 2022 - 3:48:24 PM


Files produced by the author(s)



Rémi Parrot, Mikael Briday, Olivier Roux. Pipeline Optimization using a Cost Extension of Timed Petri Nets. 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH), Jun 2021, Lyngby, Denmark. pp.37-44, ⟨10.1109/ARITH51176.2021.00018⟩. ⟨hal-03464317⟩



Les métriques sont temporairement indisponibles