On hardware for generating routes in Kautz graphs

Gerard J.M. Smit, Paul J.M. Havinga, Pierre G. Jansen, Fokke de Boer, Bert Molenkamp

Research output: Contribution to journalConference articleAcademicpeer-review

15 Downloads (Pure)

Abstract

In this paper we present a hardware implementation of an algorithm for generating node disjoint routes in a Kautz network. Kautz networks are based on a family of digraphs described by W.H. Kautz[Kautz 68]. A Kautz network with in-degree and out-degree d has N = dk + dk¿1 nodes (for any cardinals d, k>0). The diameter is at most k, the degree is fixed and independent of the network size. Moreover, it is fault-tolerant, the connectivity is d and the mapping of standard computation graphs such as a linear array, a ring and a tree on a Kautz network is straightforward. The network has a simple routing mechanism, even when nodes or links are faulty. Imase et al. [Imase 86] showed the existence of d node disjoint paths between any pair of vertices. In Smit et al. [Smit 91] an algorithm is described that generates d node disjoint routes between two arbitrary nodes in the network. In this paper we present a simple and fast hardware implementation of this algorithm. It can be realized with standard components (Field Programmable Gate Arrays).
Original languageEnglish
Pages (from-to)593-600
Number of pages8
JournalMicroprocessing and Microprogramming
Volume32
Issue number1-5
DOIs
Publication statusPublished - Aug 1991
EventEuromicro Conference on Hardware and Software Design Automation 1991 - Vienna, Austria
Duration: 2 Sep 19915 Sep 1991

Fingerprint

Hardware
Field programmable gate arrays (FPGA)

Keywords

  • Interconnection networks
  • Kautz graphs
  • Routing algorithms
  • Routing hardware
  • VHDL

Cite this

@article{874d26fad76b4ac7af2c01d99e47f444,
title = "On hardware for generating routes in Kautz graphs",
abstract = "In this paper we present a hardware implementation of an algorithm for generating node disjoint routes in a Kautz network. Kautz networks are based on a family of digraphs described by W.H. Kautz[Kautz 68]. A Kautz network with in-degree and out-degree d has N = dk + dk¿1 nodes (for any cardinals d, k>0). The diameter is at most k, the degree is fixed and independent of the network size. Moreover, it is fault-tolerant, the connectivity is d and the mapping of standard computation graphs such as a linear array, a ring and a tree on a Kautz network is straightforward. The network has a simple routing mechanism, even when nodes or links are faulty. Imase et al. [Imase 86] showed the existence of d node disjoint paths between any pair of vertices. In Smit et al. [Smit 91] an algorithm is described that generates d node disjoint routes between two arbitrary nodes in the network. In this paper we present a simple and fast hardware implementation of this algorithm. It can be realized with standard components (Field Programmable Gate Arrays).",
keywords = "Interconnection networks, Kautz graphs, Routing algorithms, Routing hardware, VHDL",
author = "Smit, {Gerard J.M.} and Havinga, {Paul J.M.} and Jansen, {Pierre G.} and {de Boer}, Fokke and Bert Molenkamp",
year = "1991",
month = "8",
doi = "10.1016/0165-6074(91)90407-K",
language = "English",
volume = "32",
pages = "593--600",
journal = "Journal of systems architecture",
issn = "1383-7621",
publisher = "Elsevier",
number = "1-5",

}

On hardware for generating routes in Kautz graphs. / Smit, Gerard J.M.; Havinga, Paul J.M.; Jansen, Pierre G.; de Boer, Fokke; Molenkamp, Bert.

In: Microprocessing and Microprogramming, Vol. 32, No. 1-5, 08.1991, p. 593-600.

Research output: Contribution to journalConference articleAcademicpeer-review

TY - JOUR

T1 - On hardware for generating routes in Kautz graphs

AU - Smit, Gerard J.M.

AU - Havinga, Paul J.M.

AU - Jansen, Pierre G.

AU - de Boer, Fokke

AU - Molenkamp, Bert

PY - 1991/8

Y1 - 1991/8

N2 - In this paper we present a hardware implementation of an algorithm for generating node disjoint routes in a Kautz network. Kautz networks are based on a family of digraphs described by W.H. Kautz[Kautz 68]. A Kautz network with in-degree and out-degree d has N = dk + dk¿1 nodes (for any cardinals d, k>0). The diameter is at most k, the degree is fixed and independent of the network size. Moreover, it is fault-tolerant, the connectivity is d and the mapping of standard computation graphs such as a linear array, a ring and a tree on a Kautz network is straightforward. The network has a simple routing mechanism, even when nodes or links are faulty. Imase et al. [Imase 86] showed the existence of d node disjoint paths between any pair of vertices. In Smit et al. [Smit 91] an algorithm is described that generates d node disjoint routes between two arbitrary nodes in the network. In this paper we present a simple and fast hardware implementation of this algorithm. It can be realized with standard components (Field Programmable Gate Arrays).

AB - In this paper we present a hardware implementation of an algorithm for generating node disjoint routes in a Kautz network. Kautz networks are based on a family of digraphs described by W.H. Kautz[Kautz 68]. A Kautz network with in-degree and out-degree d has N = dk + dk¿1 nodes (for any cardinals d, k>0). The diameter is at most k, the degree is fixed and independent of the network size. Moreover, it is fault-tolerant, the connectivity is d and the mapping of standard computation graphs such as a linear array, a ring and a tree on a Kautz network is straightforward. The network has a simple routing mechanism, even when nodes or links are faulty. Imase et al. [Imase 86] showed the existence of d node disjoint paths between any pair of vertices. In Smit et al. [Smit 91] an algorithm is described that generates d node disjoint routes between two arbitrary nodes in the network. In this paper we present a simple and fast hardware implementation of this algorithm. It can be realized with standard components (Field Programmable Gate Arrays).

KW - Interconnection networks

KW - Kautz graphs

KW - Routing algorithms

KW - Routing hardware

KW - VHDL

U2 - 10.1016/0165-6074(91)90407-K

DO - 10.1016/0165-6074(91)90407-K

M3 - Conference article

VL - 32

SP - 593

EP - 600

JO - Journal of systems architecture

JF - Journal of systems architecture

SN - 1383-7621

IS - 1-5

ER -