|
Title:
|
A mathematical formulation of the loop pipelining problem
|
|
Author:
|
Cortadella, Jordi; Badia Sala, Rosa Maria; Sánchez Carracedo, Fermín
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals; Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions |
|
Abstract:
|
This paper presents a mathematical model for the loop pipelining problem that considers several parameters for optimization and supports any combination of resource and timing constraints. The unrolling degree of the loop is one of the variables explored by the model. By using Farey’s series, an optimal exploration of the unrolling degree is performed and optimal solutions not considered by other methods are obtained. Finding an optimal schedule that minimizes resource and register requirements is solved by using an Integer linear programming (ILP) model. A novel paradigm called branch and prune is proposed to eficiently converge towards the optimal schedule and prune the search tree for integer solutions, thus drastically reducing the running time. This is the first formulation that combines the unrolling degree of the loop with timing and resource constraints in a mathematical model that guarantees optimal solutions. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
-Integer programming
-Computational complexity
-Loop pipelining
-Farey’s series Integer
-Integer linear programming
-Programació en nombres enters
-Complexitat computacional |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Conference Object |
|
Published by:
|
Universitat Politècnica de Catalunya (UPC)
|
|
Share:
|
|
