Pipeline Optimization using a Cost Extension of Timed Petri Nets
| Autor: | Mikaël Briday, Rémi Parrot, Olivier Roux |
|---|---|
| Přispěvatelé: | Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), École Centrale de Nantes (ECN) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
[INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR]
Computer science Pipeline (computing) arithmetic operator Directed graph Parallel computing Petri net Pipeline transport pipeline optimisation synchronous circuit Timed Petri Net Retiming Greedy algorithm Throughput (business) Critical path method |
| Zdroj: | 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH) 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH), Jun 2021, Lyngby, Denmark. pp.37-44, ⟨10.1109/ARITH51176.2021.00018⟩ ARITH |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|