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 -