Occam implementation of path-disjoint routing on the Hathi-2 transputer system

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

This paper describes how to develop an Occam program to heuristically solve the path-disjoint routing problem in transputer networks. In this paper, we first introduce the heuristic criteria for path-disjoint routing and a fast routing algorithm based on the criteria, then describe the design of the Occam program for path-disjoint routing based on the algorithm, and finally show some implementation results of the Occam program on the Hathi-2 transputer system. With the main feature of no batched data-swapping during program execution, our program can be efficiently implemented. For the problem of finding k edge-disjoint paths in a m × n mesh, multigrid or torus, the program runs in time O(k2 + km2n2) on one transputer. All paths in a successful solution produced by the program have a minimum total length and fewest total bends, which provides an optimally embedded layout.

Original languageEnglish
Pages (from-to)93-100
Number of pages8
JournalMicroprocessing and Microprogramming
Volume30
Issue number1-5
DOIs
Publication statusPublished - Aug 1990
Externally publishedYes

Keywords

  • Occam program
  • heuristic criteria
  • path-disjoint routing
  • route selection
  • routing order
  • transputer network

Fingerprint

Dive into the research topics of 'Occam implementation of path-disjoint routing on the Hathi-2 transputer system'. Together they form a unique fingerprint.

Cite this