Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Chemin critique

Résumé

Dans un problème d'ordonnancement en informatique théorique, ou en gestion de projet, un chemin critique désigne la (ou les) liste(s) ordonnée(s) des opérations nécessaires pour obtenir le résultat voulu, dont la durée totale donne la durée du projet. À partir de l'exemple donné C'est donc aussi, parmi les différents chemins constitués par les tâches (ordonnées selon la nécessité du projet), le (les) plus long(s) chemin(s) obtenu(s) ; il y a deux chemins critiques lorsque les deux listes de tâches correspondantes qui sont prévues demandent la même durée. C'est le cas dans l'exemple donné ci-contre, avec les deux chemins A→D→F (3+1+3 = 7 mois) et B→C, 7 mois également. L'activité E, qui n'est dans aucun des deux chemins critiques, est la seule tâche à ne pas être critique (et elle a donc une "marge totale" (float) non nulle, ici 1 mois = 7 - 6 mois (six mois étant la durée totale A-E). Inversement toute tâche faisant partie d'un chemin critique est nécessairement crit

Source officielle

https://fr.wikipedia.org/wiki/Chemin_critique

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (9)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (4)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (7)

Concepts associés

Chargement

Cours associés (4)

Pour acquérir une connaissance approfondie de l'espace et des travaux souterrains, y compris la planification, la gestion, les techniques de construction, l'évaluation de risques, et les considérations environnementales.

This course will cover all the aspects of product design and system engineering from learning relevant methods to the actual implementation in a hands-on practice of product development.

Ce cours a pour objectif de présenter l'approche générale du management de projet en intégrant la gestion du risque dans toutes les étapes du projet.

Afficher plus

Cours associés

Chargement

Séances de cours associées (6)

Afficher plus

Séances de cours associées

Chargement

Publications associées (9)

Finding a Needle in the Haystack of Hardened Interconnect Patterns

Paolo Ienne, Stefan Nikolic, Grace Zgheib

Circuits naturally exhibit recurring patterns of local interconnect. Hardening those patterns when designing Field Programmable Gate Array (FPGA) clusters can both eliminate slow programmable connections from the critical path and remove the need for transistors to implement them. While we may be able to manually design such clusters, based on intuition and observations, such an endeavour will always leave us in doubt whether we have used the potential of cheap and fast hardened connections to the fullest. On the other hand, since there are similar to 10(7) possible patterns of interconnect among only eight 5-input Look-Up Tables (LUTs), even without considering the possibilities for enforcing input sharing, performing an exhaustive exploration of the design space seems like a task as daunting as finding a needle in a haystack. Despite their enormous sizes, design spaces spanned by such cluster architectures are very well structured. In this paper, we leverage that structure to limit the search to only those points of the space that may perform better than any chosen reference. We demonstrate the usefulness of our techniques by narrowing the space spanned by five 5-LUT structures from hundreds of millions to a set of 261 structures that achieve >= 80% utilization on a set of standard benchmarks, while requiring only 12 external inputs. We believe that the exploration techniques presented here are an important step towards truly exploiting the potentials of hardening programmable connections.

IEEE2019

Chargement

Timing-Driven Placement for FPGA Architectures with Dedicated Routing Paths

Paolo Ienne, Stefan Nikolic, Grace Zgheib

The idea of introducing dedicated, fast paths between certain FPGA elements in order to reduce delay is neither new nor particularly hard to come up with. What is less obvious, however, is how to put such paths to actual use. In this work, we propose an effective ILP-based detailed placer for FPGA architectures with direct connections between LUTs. We discuss various aspects of making such an approach practicable, from efficient formulation of the integer programs themselves, to focused application of the placer on specific portions of the circuit where it could have the greatest impact. These careful considerations allow us to simultaneously move tens of LUTs with tens of candidate positions each, in a matter of minutes. This more than doubles the advantage of additional connections on the critical path delay compared to the previously reported results that relied on architecture-oblivious placement algorithms.

IEEE2020

Chargement

Straight to the Point: Intra- and Intercluster LUT Connections to Mitigate the Delay of Programmable Routing

Paolo Ienne, Stefan Nikolic, Grace Zgheib

Technology scaling makes metal delay ever more problematic, but routing between Look-Up Tables (LUTs) still passes through a series of transistors. It seems wise to avoid the corresponding delay whenever possible. Direct connections between LUTs, both within and across multiple clusters, can eschew the transistor delays of crossbars, connection blocks, and switch blocks. In this paper we investigate the usefulness of enhancing classical Field-Programmable Gate Array (FPGA) architectures with direct connections between LUTs. We present an efficient algorithm for searching automatically the most interesting patterns of such direct connections. Despite our methods being fairly conservative and relying on the use of unmodified standard CAD tools, we obtain a 2.77% improvement of the geometric mean critical path delay of a standard benchmark set, with improvement ranging from -0.17% to 7.3% for individual circuits. As modest as these results may seem at first glance, we believe that they position direct connections between LUTs as a promising topic for future research. Extending this work with dedicated CAD algorithms and exploiting the increased possibilities for optimal buffering, diagonal routing, and pipelining could prove direct connections important to the continuation of performance improvement into next generation FPGAs.

ASSOC COMPUTING MACHINERY2020

Chargement

Afficher plus