Synthèse Haut Niveau de Circuits Articles

Synthèse Haut Niveau de Circuits

• Articles:

• Scheduling Algorithms For High-Level Synthesis

• Using Global Code Motions to Improve the Quality of Results for High-Level synthesis

Plan

• Scheduling Algorithms For High-Level Synthesis

• Introduction
• Ordonnancemment
• Classification des Algorithmes d’ordonnancement
• Considération Importantes
• Future de la Synthèse Haut Niveau

• Using Global Code Motions to Improve the Quality of Results for High-Level synthesis

• Introduction
• Spark
• Mouvements de Code
• L’Algorithme d’ordonnancement
• Résultats Experimentaux

• Conclusion

• Critique

Scheduling Algorithms For High-Level Sysnthesis

• Auteurs

• Sriram Govindarajan

Introduction

• “Design” des Systèmes Digitaux

Introduction

• Qu’est-ce “Synthèse Haut Niveau“?

Ordonnancement

• “L’ordonnancement est une tâche important dans la synthèse haut niveau parce qu’il va impacter l’équilibre entre design et performance"

Ordonnancement

Classification des Algorithmes d’ordonnancement

Classification des Algorithmes d’ordonnancement

• Les Algorithmes Basiques

Classification des Algorithmes d’ordonnancement

• Programation Mathematique (Integer Linear Programming)

Classification des Algorithmes d’ordonnancement

• Heuristiques Constructive (Force directed Scheduling)

• Réduire le nombre de FUs utilisés

Classification des Algorithmes d’ordonnancement

• Iterative Refinement (Réordonnancement Iteratif)

Classification des Algorithmes d’ordonnancement

• List-Based Scheduling

• ASAP + contraintes de resources

Classification des Algorithmes d’ordonnancement

• Simulated Annealing

• Table de 2 dimensions : Les Pas de Contrôle Versus FU (Unités Fonctionnels)
• 1 opération  1 pas de contrôle et 1 FU
• Modification iteratif de la table  Coût du déplacement de l’operation

• Path-Based Scheduling

• Minimisation du nombre de Pas de Contrôle
• Les chemins d’éxecution sont ordonnancés indépendamment
• Les ordonnancements de chaque chemin sont combinés pour générer l’ordonnancement final

Considérations Importantes

• Unités Fonctionnels (FU) avec différents delays

• Cycle d’horloge déterminé par l’unité la plus lente

• Unité Multi Fonctionnels

• Il y a des unités foctionnels qui peuvent éxecuter plusiers opérations

• Description Comportammental

• Constructions conditionnels: l’ordonnanceur doit être capable de partager les resources entre les opérations qui s’éxcluent.
• Boucles: peuvent contenir parallelism entre les iterations

Future de la Synthèse Haut-Niveau

• Problèmes à Solutionner

• L’ordonnancement Pipeliné
• Coût du Contrôleur (il faut le considerer)
• Contraints de Surface (prendre en compte)
• Réalisme (constructions spéciales de langage)

Using Global Code Motions to Improve the Quality of Results for High-Level Synthesis

• Auteurs:

• Sumit Gupta

• Nick Savoiu

• Nikil Dutt

• Rajesh Gupta

• Alex Nicolau

Introduction

• Nécessités

• Trasformations de haut niveau pour optimiser la synthèse indépendamment du flux de contrôle de la description d’entrée.

• Propositions de Solution

• Algorithmes d’ordonnancement qui utilisent des techniques de mouvement de code

Spark: Framework de Synthèse de Haut Niveau

• Optimisation de la qualité de la synthèse haut niveau  delays et surface

Spark – Description du Modèle

• ANSI-C: Description Comportamental

Spark – Description du Modèle

Mouvements de Code

• Resource idle = pas d’opération à exécuter

Mouvements de Code

• Spéculation:

Mouvements de Code

• Spéculation Inverse:

Mouvements de Code

• Exécution de condition au plus tôt:

Mouvements de Code

• Spéculation Conditionel:

Mouvement de Code

• Trailblazing: Technique hiérarchique de mouvement de code

Mouvement de Code

• Changement Dynamique de Nom

• Elimination de la dépendence de données

L’Algorithme d’ordonnancement

• Priority-Based Global List Scheduling Heuristic

L’Algorithme d’ordonnancement

• Spark peut ordonnancer tous les types de boucles

L’Algorithme d’ordonnancement

• Heuristique pour l’application de la Spéculation Conditionnel

Résultats Expérimentaux

• OBS:

• Le multiplicateur (*) s’exécute en 2 cycles
• Le diviseur (/) s’exécute en 5 cycles
• Tous les autres opérations s’exécutent en 1 cycle

Résultats Expérimentaux

Résultats Expérimentaux

Conclusion

• Mouvements de code  importants pour minimiser les effets du choix de flux de controle e style de programmation

• Les mouvements de code

• Il réduit le delays
• Mais... Augmente la surface!!!

• Spark prendre en compte de contraintes de delay e surface

• Contraintes de surface: pas de solution dans le premier article

• Pas d’améllioration en comparaison avec des autres travaux

Questions ?