Arbitre du front d'onde

Une matrice de commutation est l'élément central d'une matrice de commutation qui relie les entrées aux sorties. À chaque période d'arbitrage, il est nécessaire de prendre des décisions concernant les entrées à connecter à chaque sortie. Dans les applications de commutation de cellules ou de paquets à haut débit , cette période d'arbitrage est extrêmement courte ; elle se compte souvent en millions, voire en milliards, par seconde.

Un arbitre est le circuit qui détermine lequel des nombreux commutateurs de la matrice de commutation doit être fermé. La rapidité est un critère de conception essentiel pour un arbitre dans certaines applications.

Un arbitre de front d'onde est un type particulier d'arbitre optimisé pour un fonctionnement à haute vitesse. Pour un commutateur unicast, l'algorithme est le suivant :

1. La décision commence à partir d'un point unique de la matrice xy qui représente les commutateurs physiques, par exemple le coin supérieur gauche.
2. En fonction des demandes, une décision est prise quant à la fermeture de cet interrupteur, connectant ainsi l'entrée et la sortie correspondantes.
3. Le résultat de cette décision est ensuite transmis vers la droite le long de l'axe de la matrice représentant l'entrée, et vers le bas le long de l'axe de la matrice représentant la sortie.
4. Les résultats du premier calcul permettent ensuite le calcul suivant au point situé à droite et au point situé en dessous, et la décision de fermeture de l'interrupteur est prise à chacun de ces deux points.
5. Les résultats de ces deux calculs sont ensuite transmis aux points situés en dessous et à leur droite. Ces résultats permettent alors de prendre les décisions aux trois points suivants, situés à leur droite et en dessous.
6. Ces résultats sont à nouveau affichés à droite et en dessous.
7. Dans le cas où le calcul n'a pas commencé dans le coin supérieur gauche, les résultats reviennent à droite jusqu'à la première colonne de gauche et en bas jusqu'à la première ligne.
8. Le calcul se poursuit jusqu'à ce que toutes les décisions aient été prises.

Les avantages de ce type de calcul sont les suivants :

• Vitesse – l’algorithme peut être implémenté de manière combinatoire (sans registres matériels ), permettant au front d’onde de se propager sur une grande partie ou la totalité de la matrice en une ou quelques périodes d’horloge.
• Régularité – les nœuds de la structure physique utilisée pour le calcul sont tous identiques. On parle alors de calcul systolique . Les structures régulières permettent parfois de réaliser des implémentations compactes sur semi-conducteurs .

Il existe de nombreuses variantes de cette méthode, notamment :

• L'ordre de présentation des lignes et des colonnes est aléatoire ou mélangé. Un mélange, même partiel, est généralement nécessaire pour garantir l'équité.
• Variantes multicast de cette méthode où une entrée peut être connectée à plusieurs sorties en une ou plusieurs passes.

• Description de l'algorithme dans les notes de cours de Stanford